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/.
38 #define HASH_TABLE_MIN_SIZE 11
39 #define HASH_TABLE_MAX_SIZE 13845163
42 typedef struct _GHashNode GHashNode;
57 GEqualFunc key_equal_func;
58 GDestroyNotify key_destroy_func;
59 GDestroyNotify value_destroy_func;
63 static void g_hash_table_resize (GHashTable *hash_table);
64 static GHashNode** g_hash_table_lookup_node (GHashTable *hash_table,
66 static GHashNode* g_hash_node_new (gpointer key,
68 static void g_hash_node_destroy (GHashNode *hash_node,
69 GDestroyNotify key_destroy_func,
70 GDestroyNotify value_destroy_func);
71 static void g_hash_nodes_destroy (GHashNode *hash_node,
72 GDestroyNotify key_destroy_func,
73 GDestroyNotify value_destroy_func);
74 static guint g_hash_table_foreach_remove_or_steal (GHashTable *hash_table,
80 G_LOCK_DEFINE_STATIC (g_hash_global);
82 static GMemChunk *node_mem_chunk = NULL;
83 static GHashNode *node_free_list = NULL;
87 * @hash_func: a function to create a hash value from a key.
88 * Hash values are used to determine where keys are stored within the
89 * #GHashTable data structure. The g_direct_hash(), g_int_hash() and
90 * g_str_hash() functions are provided for some common types of keys.
91 * If hash_func is NULL, g_direct_hash() is used.
92 * @key_equal_func: a function to check two keys for equality. This is
93 * used when looking up keys in the #GHashTable. The g_direct_equal(),
94 * g_int_equal() and g_str_equal() functions are provided for the most
95 * common types of keys. If @key_equal_func is NULL, keys are compared
96 * directly in a similar fashion to g_direct_equal(), but without the
97 * overhead of a function call.
99 * Creates a new #GHashTable.
101 * Return value: a new #GHashTable.
104 g_hash_table_new (GHashFunc hash_func,
105 GEqualFunc key_equal_func)
107 return g_hash_table_new_full (hash_func, key_equal_func, NULL, NULL);
112 * g_hash_table_new_full:
113 * @hash_func: a function to create a hash value from a key.
114 * @key_equal_func: a function to check two keys for equality.
115 * @key_destroy_func: a function to free the memory allocated for the key
116 * used when removing the entry from the #GHashTable or #NULL if you
117 * don't want to supply such a function.
118 * @value_destroy_func: a function to free the memory allocated for the
119 * value used when removing the entry from the #GHashTable or #NULL if
120 * you don't want to supply such a function.
122 * Creates a new #GHashTable like g_hash_table_new() and allows to specify
123 * functions to free the memory allocated for the key and value that get
124 * called when removing the entry from the #GHashTable.
126 * Return value: a new #GHashTable.
129 g_hash_table_new_full (GHashFunc hash_func,
130 GEqualFunc key_equal_func,
131 GDestroyNotify key_destroy_func,
132 GDestroyNotify value_destroy_func)
134 GHashTable *hash_table;
137 hash_table = g_new (GHashTable, 1);
138 hash_table->size = HASH_TABLE_MIN_SIZE;
139 hash_table->nnodes = 0;
140 hash_table->hash_func = hash_func ? hash_func : g_direct_hash;
141 hash_table->key_equal_func = key_equal_func;
142 hash_table->key_destroy_func = key_destroy_func;
143 hash_table->value_destroy_func = value_destroy_func;
144 hash_table->nodes = g_new (GHashNode*, hash_table->size);
146 for (i = 0; i < hash_table->size; i++)
147 hash_table->nodes[i] = NULL;
153 * g_hash_table_destroy:
154 * @hash_table: a #GHashTable.
156 * Destroys the #GHashTable. If keys and/or values are dynamically
157 * allocated, you should either free them first or create the #GHashTable
158 * using g_hash_table_new_full(). In the latter case the destroy functions
159 * you supplied will be called on all keys and values before destroying
163 g_hash_table_destroy (GHashTable *hash_table)
167 g_return_if_fail (hash_table != NULL);
169 for (i = 0; i < hash_table->size; i++)
170 g_hash_nodes_destroy (hash_table->nodes[i],
171 hash_table->key_destroy_func,
172 hash_table->value_destroy_func);
174 g_free (hash_table->nodes);
178 static inline GHashNode**
179 g_hash_table_lookup_node (GHashTable *hash_table,
184 node = &hash_table->nodes
185 [(* hash_table->hash_func) (key) % hash_table->size];
187 /* Hash table lookup needs to be fast.
188 * We therefore remove the extra conditional of testing
189 * whether to call the key_equal_func or not from
192 if (hash_table->key_equal_func)
193 while (*node && !(*hash_table->key_equal_func) ((*node)->key, key))
194 node = &(*node)->next;
196 while (*node && (*node)->key != key)
197 node = &(*node)->next;
203 * g_hash_table_lookup:
204 * @hash_table: a #GHashTable.
205 * @key: the key to look up.
207 * Looks up a key in a #GHashTable.
209 * Return value: the associated value, or NULL if the key is not found.
212 g_hash_table_lookup (GHashTable *hash_table,
217 g_return_val_if_fail (hash_table != NULL, NULL);
219 node = *g_hash_table_lookup_node (hash_table, key);
221 return node ? node->value : NULL;
225 * g_hash_table_lookup_extended:
226 * @hash_table: a #GHashTable.
227 * @lookup_key: the key to look up.
228 * @orig_key: returns the original key.
229 * @value: returns the value associated with the key.
231 * Looks up a key in the #GHashTable, returning the original key and the
232 * associated value and a gboolean which is TRUE if the key was found. This
233 * is useful if you need to free the memory allocated for the original key,
234 * for example before calling g_hash_table_remove().
236 * Return value: #TRUE if the key was found in the #GHashTable.
239 g_hash_table_lookup_extended (GHashTable *hash_table,
240 gconstpointer lookup_key,
246 g_return_val_if_fail (hash_table != NULL, FALSE);
248 node = *g_hash_table_lookup_node (hash_table, lookup_key);
253 *orig_key = node->key;
255 *value = node->value;
263 * g_hash_table_insert:
264 * @hash_table: a #GHashTable.
265 * @key: a key to insert.
266 * @value: the value to associate with the key.
268 * Inserts a new key and value into a #GHashTable.
270 * If the key already exists in the #GHashTable its current value is replaced
271 * with the new value. If you supplied a value_destroy_func when creating the
272 * #GHashTable, the old value is freed using that function. If you supplied
273 * a key_destroy_func when creating the #GHashTable, the passed key is freed
274 * using that function.
277 g_hash_table_insert (GHashTable *hash_table,
283 g_return_if_fail (hash_table != NULL);
285 node = g_hash_table_lookup_node (hash_table, key);
289 /* do not reset node->key in this place, keeping
290 * the old key is the intended behaviour.
291 * g_hash_table_replace() can be used instead.
294 /* free the passed key */
295 if (hash_table->key_destroy_func)
296 hash_table->key_destroy_func (key);
298 if (hash_table->value_destroy_func)
299 hash_table->value_destroy_func ((*node)->value);
301 (*node)->value = value;
305 *node = g_hash_node_new (key, value);
306 hash_table->nnodes++;
307 g_hash_table_resize (hash_table);
312 * g_hash_table_replace:
313 * @hash_table: a #GHashTable.
314 * @key: a key to insert.
315 * @value: the value to associate with the key.
317 * Inserts a new key and value into a #GHashTable similar to
318 * g_hash_table_insert(). The difference is that if the key already exists
319 * in the #GHashTable, it gets replaced by the new key. If you supplied a
320 * value_destroy_func when creating the #GHashTable, the old value is freed
321 * using that function. If you supplied a key_destroy_func when creating the
322 * #GHashTable, the old key is freed using that function.
325 g_hash_table_replace (GHashTable *hash_table,
331 g_return_if_fail (hash_table != NULL);
333 node = g_hash_table_lookup_node (hash_table, key);
337 if (hash_table->key_destroy_func)
338 hash_table->key_destroy_func ((*node)->key);
340 if (hash_table->value_destroy_func)
341 hash_table->value_destroy_func ((*node)->value);
344 (*node)->value = value;
348 *node = g_hash_node_new (key, value);
349 hash_table->nnodes++;
350 g_hash_table_resize (hash_table);
355 * g_hash_table_remove:
356 * @hash_table: a #GHashTable.
357 * @key: the key to remove.
359 * Removes a key and its associated value from a #GHashTable.
361 * If the #GHashTable was created using g_hash_table_new_full(), the
362 * key and value are freed using the supplied destroy_functions, otherwise
363 * you have to make sure that any dynamically allocated values are freed
366 * Return value: #TRUE if the key was found and removed from the #GHashTable.
369 g_hash_table_remove (GHashTable *hash_table,
372 GHashNode **node, *dest;
374 g_return_val_if_fail (hash_table != NULL, FALSE);
376 node = g_hash_table_lookup_node (hash_table, key);
380 (*node) = dest->next;
381 g_hash_node_destroy (dest,
382 hash_table->key_destroy_func,
383 hash_table->value_destroy_func);
384 hash_table->nnodes--;
386 g_hash_table_resize (hash_table);
395 * g_hash_table_steal:
396 * @hash_table: a #GHashTable.
397 * @key: the key to remove.
399 * Removes a key and its associated value from a #GHashTable without
400 * calling the key and value destroy functions.
402 * Return value: #TRUE if the key was found and removed from the #GHashTable.
405 g_hash_table_steal (GHashTable *hash_table,
408 GHashNode **node, *dest;
410 g_return_val_if_fail (hash_table != NULL, FALSE);
412 node = g_hash_table_lookup_node (hash_table, key);
416 (*node) = dest->next;
417 g_hash_node_destroy (dest, NULL, NULL);
418 hash_table->nnodes--;
420 g_hash_table_resize (hash_table);
429 * g_hash_table_foreach_remove:
430 * @hash_table: a #GHashTable.
431 * @func: the function to call for each key/value pair.
432 * @user_data: user data to pass to the function.
434 * Calls the given function for each key/value pair in the #GHashTable.
435 * If the function returns TRUE, then the key/value pair is removed from the
436 * #GHashTable. If you supplied key or value destroy functions when creating
437 * the #GHashTable, they are used to free the memory allocated for the removed
440 * Return value: the number of key/value pairs removed.
443 g_hash_table_foreach_remove (GHashTable *hash_table,
447 g_return_val_if_fail (hash_table != NULL, 0);
448 g_return_val_if_fail (func != NULL, 0);
450 return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, TRUE);
454 * g_hash_table_foreach_steal:
455 * @hash_table: a #GHashTable.
456 * @func: the function to call for each key/value pair.
457 * @user_data: user data to pass to the function.
459 * Calls the given function for each key/value pair in the #GHashTable.
460 * If the function returns TRUE, then the key/value pair is removed from the
461 * #GHashTable, but no key or value destroy functions are called.
463 * Return value: the number of key/value pairs removed.
466 g_hash_table_foreach_steal (GHashTable *hash_table,
470 g_return_val_if_fail (hash_table != NULL, 0);
471 g_return_val_if_fail (func != NULL, 0);
473 return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, FALSE);
477 g_hash_table_foreach_remove_or_steal (GHashTable *hash_table,
482 GHashNode *node, *prev;
486 for (i = 0; i < hash_table->size; i++)
492 for (node = hash_table->nodes[i]; node; prev = node, node = node->next)
494 if ((* func) (node->key, node->value, user_data))
498 hash_table->nnodes -= 1;
502 prev->next = node->next;
503 g_hash_node_destroy (node,
504 notify ? hash_table->value_destroy_func : NULL,
505 notify ? hash_table->key_destroy_func : NULL);
510 hash_table->nodes[i] = node->next;
511 g_hash_node_destroy (node,
512 notify ? hash_table->value_destroy_func : NULL,
513 notify ? hash_table->key_destroy_func : NULL);
520 g_hash_table_resize (hash_table);
526 * g_hash_table_foreach:
527 * @hash_table: a #GHashTable.
528 * @func: the function to call for each key/value pair.
529 * @user_data: user data to pass to the function.
531 * Calls the given function for each of the key/value pairs in the #GHashTable.
532 * The function is passed the key and value of each pair, and the given
533 * @user_data parameter.
536 g_hash_table_foreach (GHashTable *hash_table,
543 g_return_if_fail (hash_table != NULL);
544 g_return_if_fail (func != NULL);
546 for (i = 0; i < hash_table->size; i++)
547 for (node = hash_table->nodes[i]; node; node = node->next)
548 (* func) (node->key, node->value, user_data);
553 * @hash_table: a #GHashTable.
555 * Returns the number of elements contained in the #GHashTable.
557 * Return value: the number of key/value pairs in the #GHashTable.
560 g_hash_table_size (GHashTable *hash_table)
562 g_return_val_if_fail (hash_table != NULL, 0);
564 return hash_table->nnodes;
568 g_hash_table_resize (GHashTable *hash_table)
570 GHashNode **new_nodes;
573 gfloat nodes_per_list;
578 nodes_per_list = (gfloat) hash_table->nnodes / (gfloat) hash_table->size;
580 if ((nodes_per_list > 0.3 || hash_table->size <= HASH_TABLE_MIN_SIZE) &&
581 (nodes_per_list < 3.0 || hash_table->size >= HASH_TABLE_MAX_SIZE))
584 new_size = CLAMP(g_spaced_primes_closest (hash_table->nnodes),
586 HASH_TABLE_MAX_SIZE);
587 new_nodes = g_new0 (GHashNode*, new_size);
589 for (i = 0; i < hash_table->size; i++)
590 for (node = hash_table->nodes[i]; node; node = next)
594 hash_val = (* hash_table->hash_func) (node->key) % new_size;
596 node->next = new_nodes[hash_val];
597 new_nodes[hash_val] = node;
600 g_free (hash_table->nodes);
601 hash_table->nodes = new_nodes;
602 hash_table->size = new_size;
606 g_hash_node_new (gpointer key,
609 GHashNode *hash_node;
611 G_LOCK (g_hash_global);
614 hash_node = node_free_list;
615 node_free_list = node_free_list->next;
620 node_mem_chunk = g_mem_chunk_new ("hash node mem chunk",
624 hash_node = g_chunk_new (GHashNode, node_mem_chunk);
626 G_UNLOCK (g_hash_global);
628 hash_node->key = key;
629 hash_node->value = value;
630 hash_node->next = NULL;
636 g_hash_node_destroy (GHashNode *hash_node,
637 GDestroyNotify key_destroy_func,
638 GDestroyNotify value_destroy_func)
640 if (key_destroy_func)
641 key_destroy_func (hash_node->key);
642 if (value_destroy_func)
643 value_destroy_func (hash_node->value);
645 #ifdef ENABLE_GC_FRIENDLY
646 hash_node->key = NULL;
647 hash_node->value = NULL;
648 #endif /* ENABLE_GC_FRIENDLY */
650 G_LOCK (g_hash_global);
651 hash_node->next = node_free_list;
652 node_free_list = hash_node;
653 G_UNLOCK (g_hash_global);
657 g_hash_nodes_destroy (GHashNode *hash_node,
658 GFreeFunc key_destroy_func,
659 GFreeFunc value_destroy_func)
663 GHashNode *node = hash_node;
667 if (key_destroy_func)
668 key_destroy_func (node->key);
669 if (value_destroy_func)
670 value_destroy_func (node->value);
672 #ifdef ENABLE_GC_FRIENDLY
675 #endif /* ENABLE_GC_FRIENDLY */
680 if (key_destroy_func)
681 key_destroy_func (node->key);
682 if (value_destroy_func)
683 value_destroy_func (node->value);
685 #ifdef ENABLE_GC_FRIENDLY
688 #endif /* ENABLE_GC_FRIENDLY */
690 G_LOCK (g_hash_global);
691 node->next = node_free_list;
692 node_free_list = hash_node;
693 G_UNLOCK (g_hash_global);