1 /* GLIB - Library of useful routines for C programming
2 * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Lesser General Public
6 * License as published by the Free Software Foundation; either
7 * version 2 of the License, or (at your option) any later version.
9 * This library is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * Lesser General Public License for more details.
14 * You should have received a copy of the GNU Lesser General Public
15 * License along with this library; if not, write to the
16 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17 * Boston, MA 02111-1307, USA.
21 * Modified by the GLib Team and others 1997-2000. See the AUTHORS
22 * file for a list of people on the GLib Team. See the ChangeLog
23 * files for a list of changes. These files are distributed with
24 * GLib at ftp://ftp.gtk.org/pub/gtk/.
37 #define HASH_TABLE_MIN_SIZE 11
38 #define HASH_TABLE_MAX_SIZE 13845163
41 typedef struct _GHashNode GHashNode;
56 GEqualFunc key_equal_func;
57 GDestroyNotify key_destroy_func;
58 GDestroyNotify value_destroy_func;
61 #define G_HASH_TABLE_RESIZE(hash_table) \
63 if ((hash_table->size >= 3 * hash_table->nnodes && \
64 hash_table->size > HASH_TABLE_MIN_SIZE) || \
65 (3 * hash_table->size <= hash_table->nnodes && \
66 hash_table->size < HASH_TABLE_MAX_SIZE)) \
67 g_hash_table_resize (hash_table); \
70 static void g_hash_table_resize (GHashTable *hash_table);
71 static GHashNode** g_hash_table_lookup_node (GHashTable *hash_table,
73 static GHashNode* g_hash_node_new (gpointer key,
75 static void g_hash_node_destroy (GHashNode *hash_node,
76 GDestroyNotify key_destroy_func,
77 GDestroyNotify value_destroy_func);
78 static void g_hash_nodes_destroy (GHashNode *hash_node,
79 GDestroyNotify key_destroy_func,
80 GDestroyNotify value_destroy_func);
81 static guint g_hash_table_foreach_remove_or_steal (GHashTable *hash_table,
87 #ifndef DISABLE_MEM_POOLS
88 G_LOCK_DEFINE_STATIC (g_hash_global);
90 static GMemChunk *node_mem_chunk = NULL;
91 static GHashNode *node_free_list = NULL;
96 * @hash_func: a function to create a hash value from a key.
97 * Hash values are used to determine where keys are stored within the
98 * #GHashTable data structure. The g_direct_hash(), g_int_hash() and
99 * g_str_hash() functions are provided for some common types of keys.
100 * If hash_func is %NULL, g_direct_hash() is used.
101 * @key_equal_func: a function to check two keys for equality. This is
102 * used when looking up keys in the #GHashTable. The g_direct_equal(),
103 * g_int_equal() and g_str_equal() functions are provided for the most
104 * common types of keys. If @key_equal_func is %NULL, keys are compared
105 * directly in a similar fashion to g_direct_equal(), but without the
106 * overhead of a function call.
108 * Creates a new #GHashTable.
110 * Return value: a new #GHashTable.
113 g_hash_table_new (GHashFunc hash_func,
114 GEqualFunc key_equal_func)
116 return g_hash_table_new_full (hash_func, key_equal_func, NULL, NULL);
121 * g_hash_table_new_full:
122 * @hash_func: a function to create a hash value from a key.
123 * @key_equal_func: a function to check two keys for equality.
124 * @key_destroy_func: a function to free the memory allocated for the key
125 * used when removing the entry from the #GHashTable or %NULL if you
126 * don't want to supply such a function.
127 * @value_destroy_func: a function to free the memory allocated for the
128 * value used when removing the entry from the #GHashTable or %NULL if
129 * you don't want to supply such a function.
131 * Creates a new #GHashTable like g_hash_table_new() and allows to specify
132 * functions to free the memory allocated for the key and value that get
133 * called when removing the entry from the #GHashTable.
135 * Return value: a new #GHashTable.
138 g_hash_table_new_full (GHashFunc hash_func,
139 GEqualFunc key_equal_func,
140 GDestroyNotify key_destroy_func,
141 GDestroyNotify value_destroy_func)
143 GHashTable *hash_table;
146 hash_table = g_new (GHashTable, 1);
147 hash_table->size = HASH_TABLE_MIN_SIZE;
148 hash_table->nnodes = 0;
149 hash_table->hash_func = hash_func ? hash_func : g_direct_hash;
150 hash_table->key_equal_func = key_equal_func;
151 hash_table->key_destroy_func = key_destroy_func;
152 hash_table->value_destroy_func = value_destroy_func;
153 hash_table->nodes = g_new (GHashNode*, hash_table->size);
155 for (i = 0; i < hash_table->size; i++)
156 hash_table->nodes[i] = NULL;
162 * g_hash_table_destroy:
163 * @hash_table: a #GHashTable.
165 * Destroys the #GHashTable. If keys and/or values are dynamically
166 * allocated, you should either free them first or create the #GHashTable
167 * using g_hash_table_new_full(). In the latter case the destroy functions
168 * you supplied will be called on all keys and values before destroying
172 g_hash_table_destroy (GHashTable *hash_table)
176 g_return_if_fail (hash_table != NULL);
178 for (i = 0; i < hash_table->size; i++)
179 g_hash_nodes_destroy (hash_table->nodes[i],
180 hash_table->key_destroy_func,
181 hash_table->value_destroy_func);
183 g_free (hash_table->nodes);
187 static inline GHashNode**
188 g_hash_table_lookup_node (GHashTable *hash_table,
193 node = &hash_table->nodes
194 [(* hash_table->hash_func) (key) % hash_table->size];
196 /* Hash table lookup needs to be fast.
197 * We therefore remove the extra conditional of testing
198 * whether to call the key_equal_func or not from
201 if (hash_table->key_equal_func)
202 while (*node && !(*hash_table->key_equal_func) ((*node)->key, key))
203 node = &(*node)->next;
205 while (*node && (*node)->key != key)
206 node = &(*node)->next;
212 * g_hash_table_lookup:
213 * @hash_table: a #GHashTable.
214 * @key: the key to look up.
216 * Looks up a key in a #GHashTable. Note that this function cannot
217 * distinguish between a key that is not present and one which is present
218 * and has the value %NULL. If you need this distinction, use
219 * g_hash_table_lookup_extended().
221 * Return value: the associated value, or %NULL if the key is not found.
224 g_hash_table_lookup (GHashTable *hash_table,
229 g_return_val_if_fail (hash_table != NULL, NULL);
231 node = *g_hash_table_lookup_node (hash_table, key);
233 return node ? node->value : NULL;
237 * g_hash_table_lookup_extended:
238 * @hash_table: a #GHashTable.
239 * @lookup_key: the key to look up.
240 * @orig_key: returns the original key.
241 * @value: returns the value associated with the key.
243 * Looks up a key in the #GHashTable, returning the original key and the
244 * associated value and a #gboolean which is %TRUE if the key was found. This
245 * is useful if you need to free the memory allocated for the original key,
246 * for example before calling g_hash_table_remove().
248 * Return value: %TRUE if the key was found in the #GHashTable.
251 g_hash_table_lookup_extended (GHashTable *hash_table,
252 gconstpointer lookup_key,
258 g_return_val_if_fail (hash_table != NULL, FALSE);
260 node = *g_hash_table_lookup_node (hash_table, lookup_key);
265 *orig_key = node->key;
267 *value = node->value;
275 * g_hash_table_insert:
276 * @hash_table: a #GHashTable.
277 * @key: a key to insert.
278 * @value: the value to associate with the key.
280 * Inserts a new key and value into a #GHashTable.
282 * If the key already exists in the #GHashTable its current value is replaced
283 * with the new value. If you supplied a @value_destroy_func when creating the
284 * #GHashTable, the old value is freed using that function. If you supplied
285 * a @key_destroy_func when creating the #GHashTable, the passed key is freed
286 * using that function.
289 g_hash_table_insert (GHashTable *hash_table,
295 g_return_if_fail (hash_table != NULL);
297 node = g_hash_table_lookup_node (hash_table, key);
301 /* do not reset node->key in this place, keeping
302 * the old key is the intended behaviour.
303 * g_hash_table_replace() can be used instead.
306 /* free the passed key */
307 if (hash_table->key_destroy_func)
308 hash_table->key_destroy_func (key);
310 if (hash_table->value_destroy_func)
311 hash_table->value_destroy_func ((*node)->value);
313 (*node)->value = value;
317 *node = g_hash_node_new (key, value);
318 hash_table->nnodes++;
319 G_HASH_TABLE_RESIZE (hash_table);
324 * g_hash_table_replace:
325 * @hash_table: a #GHashTable.
326 * @key: a key to insert.
327 * @value: the value to associate with the key.
329 * Inserts a new key and value into a #GHashTable similar to
330 * g_hash_table_insert(). The difference is that if the key already exists
331 * in the #GHashTable, it gets replaced by the new key. If you supplied a
332 * @value_destroy_func when creating the #GHashTable, the old value is freed
333 * using that function. If you supplied a @key_destroy_func when creating the
334 * #GHashTable, the old key is freed using that function.
337 g_hash_table_replace (GHashTable *hash_table,
343 g_return_if_fail (hash_table != NULL);
345 node = g_hash_table_lookup_node (hash_table, key);
349 if (hash_table->key_destroy_func)
350 hash_table->key_destroy_func ((*node)->key);
352 if (hash_table->value_destroy_func)
353 hash_table->value_destroy_func ((*node)->value);
356 (*node)->value = value;
360 *node = g_hash_node_new (key, value);
361 hash_table->nnodes++;
362 G_HASH_TABLE_RESIZE (hash_table);
367 * g_hash_table_remove:
368 * @hash_table: a #GHashTable.
369 * @key: the key to remove.
371 * Removes a key and its associated value from a #GHashTable.
373 * If the #GHashTable was created using g_hash_table_new_full(), the
374 * key and value are freed using the supplied destroy functions, otherwise
375 * you have to make sure that any dynamically allocated values are freed
378 * Return value: %TRUE if the key was found and removed from the #GHashTable.
381 g_hash_table_remove (GHashTable *hash_table,
384 GHashNode **node, *dest;
386 g_return_val_if_fail (hash_table != NULL, FALSE);
388 node = g_hash_table_lookup_node (hash_table, key);
392 (*node) = dest->next;
393 g_hash_node_destroy (dest,
394 hash_table->key_destroy_func,
395 hash_table->value_destroy_func);
396 hash_table->nnodes--;
398 G_HASH_TABLE_RESIZE (hash_table);
407 * g_hash_table_steal:
408 * @hash_table: a #GHashTable.
409 * @key: the key to remove.
411 * Removes a key and its associated value from a #GHashTable without
412 * calling the key and value destroy functions.
414 * Return value: %TRUE if the key was found and removed from the #GHashTable.
417 g_hash_table_steal (GHashTable *hash_table,
420 GHashNode **node, *dest;
422 g_return_val_if_fail (hash_table != NULL, FALSE);
424 node = g_hash_table_lookup_node (hash_table, key);
428 (*node) = dest->next;
429 g_hash_node_destroy (dest, NULL, NULL);
430 hash_table->nnodes--;
432 G_HASH_TABLE_RESIZE (hash_table);
441 * g_hash_table_foreach_remove:
442 * @hash_table: a #GHashTable.
443 * @func: the function to call for each key/value pair.
444 * @user_data: user data to pass to the function.
446 * Calls the given function for each key/value pair in the #GHashTable.
447 * If the function returns %TRUE, then the key/value pair is removed from the
448 * #GHashTable. If you supplied key or value destroy functions when creating
449 * the #GHashTable, they are used to free the memory allocated for the removed
452 * Return value: the number of key/value pairs removed.
455 g_hash_table_foreach_remove (GHashTable *hash_table,
459 g_return_val_if_fail (hash_table != NULL, 0);
460 g_return_val_if_fail (func != NULL, 0);
462 return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, TRUE);
466 * g_hash_table_foreach_steal:
467 * @hash_table: a #GHashTable.
468 * @func: the function to call for each key/value pair.
469 * @user_data: user data to pass to the function.
471 * Calls the given function for each key/value pair in the #GHashTable.
472 * If the function returns %TRUE, then the key/value pair is removed from the
473 * #GHashTable, but no key or value destroy functions are called.
475 * Return value: the number of key/value pairs removed.
478 g_hash_table_foreach_steal (GHashTable *hash_table,
482 g_return_val_if_fail (hash_table != NULL, 0);
483 g_return_val_if_fail (func != NULL, 0);
485 return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, FALSE);
489 g_hash_table_foreach_remove_or_steal (GHashTable *hash_table,
494 GHashNode *node, *prev;
498 for (i = 0; i < hash_table->size; i++)
504 for (node = hash_table->nodes[i]; node; prev = node, node = node->next)
506 if ((* func) (node->key, node->value, user_data))
510 hash_table->nnodes -= 1;
514 prev->next = node->next;
515 g_hash_node_destroy (node,
516 notify ? hash_table->key_destroy_func : NULL,
517 notify ? hash_table->value_destroy_func : NULL);
522 hash_table->nodes[i] = node->next;
523 g_hash_node_destroy (node,
524 notify ? hash_table->key_destroy_func : NULL,
525 notify ? hash_table->value_destroy_func : NULL);
532 G_HASH_TABLE_RESIZE (hash_table);
538 * g_hash_table_foreach:
539 * @hash_table: a #GHashTable.
540 * @func: the function to call for each key/value pair.
541 * @user_data: user data to pass to the function.
543 * Calls the given function for each of the key/value pairs in the
544 * #GHashTable. The function is passed the key and value of each
545 * pair, and the given @user_data parameter. The hash table may not
546 * be modified while iterating over it (you can't add/remove
547 * items). To remove all items matching a predicate, use
548 * g_hash_table_remove().
551 g_hash_table_foreach (GHashTable *hash_table,
558 g_return_if_fail (hash_table != NULL);
559 g_return_if_fail (func != NULL);
561 for (i = 0; i < hash_table->size; i++)
562 for (node = hash_table->nodes[i]; node; node = node->next)
563 (* func) (node->key, node->value, user_data);
568 * @hash_table: a #GHashTable.
569 * @predicate: function to test the key/value pairs for a certain property.
570 * @user_data: user data to pass to the function.
572 * Calls the given function for key/value pairs in the #GHashTable until
573 * @predicate returns %TRUE. The function is passed the key and value of
574 * each pair, and the given @user_data parameter. The hash table may not
575 * be modified while iterating over it (you can't add/remove items).
577 * Return value: The value of the first key/value pair is returned, for which
578 * func evaluates to %TRUE. If no pair with the requested property is found,
584 g_hash_table_find (GHashTable *hash_table,
591 g_return_val_if_fail (hash_table != NULL, NULL);
592 g_return_val_if_fail (predicate != NULL, NULL);
594 for (i = 0; i < hash_table->size; i++)
595 for (node = hash_table->nodes[i]; node; node = node->next)
596 if (predicate (node->key, node->value, user_data))
603 * @hash_table: a #GHashTable.
605 * Returns the number of elements contained in the #GHashTable.
607 * Return value: the number of key/value pairs in the #GHashTable.
610 g_hash_table_size (GHashTable *hash_table)
612 g_return_val_if_fail (hash_table != NULL, 0);
614 return hash_table->nnodes;
618 g_hash_table_resize (GHashTable *hash_table)
620 GHashNode **new_nodes;
627 new_size = g_spaced_primes_closest (hash_table->nnodes);
628 new_size = CLAMP (new_size, HASH_TABLE_MIN_SIZE, HASH_TABLE_MAX_SIZE);
630 new_nodes = g_new0 (GHashNode*, new_size);
632 for (i = 0; i < hash_table->size; i++)
633 for (node = hash_table->nodes[i]; node; node = next)
637 hash_val = (* hash_table->hash_func) (node->key) % new_size;
639 node->next = new_nodes[hash_val];
640 new_nodes[hash_val] = node;
643 g_free (hash_table->nodes);
644 hash_table->nodes = new_nodes;
645 hash_table->size = new_size;
649 g_hash_node_new (gpointer key,
652 GHashNode *hash_node;
654 #ifdef DISABLE_MEM_POOLS
655 hash_node = g_new (GHashNode, 1);
657 G_LOCK (g_hash_global);
660 hash_node = node_free_list;
661 node_free_list = node_free_list->next;
666 node_mem_chunk = g_mem_chunk_new ("hash node mem chunk",
670 hash_node = g_chunk_new (GHashNode, node_mem_chunk);
672 G_UNLOCK (g_hash_global);
675 hash_node->key = key;
676 hash_node->value = value;
677 hash_node->next = NULL;
683 g_hash_node_destroy (GHashNode *hash_node,
684 GDestroyNotify key_destroy_func,
685 GDestroyNotify value_destroy_func)
687 if (key_destroy_func)
688 key_destroy_func (hash_node->key);
689 if (value_destroy_func)
690 value_destroy_func (hash_node->value);
692 #ifdef ENABLE_GC_FRIENDLY
693 hash_node->key = NULL;
694 hash_node->value = NULL;
695 #endif /* ENABLE_GC_FRIENDLY */
697 #ifdef DISABLE_MEM_POOLS
700 G_LOCK (g_hash_global);
701 hash_node->next = node_free_list;
702 node_free_list = hash_node;
703 G_UNLOCK (g_hash_global);
708 g_hash_nodes_destroy (GHashNode *hash_node,
709 GFreeFunc key_destroy_func,
710 GFreeFunc value_destroy_func)
712 #ifdef DISABLE_MEM_POOLS
715 GHashNode *next = hash_node->next;
717 if (key_destroy_func)
718 key_destroy_func (hash_node->key);
719 if (value_destroy_func)
720 value_destroy_func (hash_node->value);
728 GHashNode *node = hash_node;
732 if (key_destroy_func)
733 key_destroy_func (node->key);
734 if (value_destroy_func)
735 value_destroy_func (node->value);
737 #ifdef ENABLE_GC_FRIENDLY
740 #endif /* ENABLE_GC_FRIENDLY */
745 if (key_destroy_func)
746 key_destroy_func (node->key);
747 if (value_destroy_func)
748 value_destroy_func (node->value);
750 #ifdef ENABLE_GC_FRIENDLY
753 #endif /* ENABLE_GC_FRIENDLY */
755 G_LOCK (g_hash_global);
756 node->next = node_free_list;
757 node_free_list = hash_node;
758 G_UNLOCK (g_hash_global);