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
;
62 #define G_HASH_TABLE_RESIZE(hash_table) \
64 if ((hash_table->size >= 3 * hash_table->nnodes && \
65 hash_table->size > HASH_TABLE_MIN_SIZE) || \
66 (3 * hash_table->size <= hash_table->nnodes && \
67 hash_table->size < HASH_TABLE_MAX_SIZE)) \
68 g_hash_table_resize (hash_table); \
71 static void g_hash_table_resize (GHashTable
*hash_table
);
72 static GHashNode
** g_hash_table_lookup_node (GHashTable
*hash_table
,
74 static GHashNode
* g_hash_node_new (gpointer key
,
76 static void g_hash_node_destroy (GHashNode
*hash_node
,
77 GDestroyNotify key_destroy_func
,
78 GDestroyNotify value_destroy_func
);
79 static void g_hash_nodes_destroy (GHashNode
*hash_node
,
80 GDestroyNotify key_destroy_func
,
81 GDestroyNotify value_destroy_func
);
82 static guint
g_hash_table_foreach_remove_or_steal (GHashTable
*hash_table
,
88 G_LOCK_DEFINE_STATIC (g_hash_global
);
90 static GMemChunk
*node_mem_chunk
= NULL
;
91 static GHashNode
*node_free_list
= NULL
;
95 * @hash_func: a function to create a hash value from a key.
96 * Hash values are used to determine where keys are stored within the
97 * #GHashTable data structure. The g_direct_hash(), g_int_hash() and
98 * g_str_hash() functions are provided for some common types of keys.
99 * If hash_func is %NULL, g_direct_hash() is used.
100 * @key_equal_func: a function to check two keys for equality. This is
101 * used when looking up keys in the #GHashTable. The g_direct_equal(),
102 * g_int_equal() and g_str_equal() functions are provided for the most
103 * common types of keys. If @key_equal_func is %NULL, keys are compared
104 * directly in a similar fashion to g_direct_equal(), but without the
105 * overhead of a function call.
107 * Creates a new #GHashTable.
109 * Return value: a new #GHashTable.
112 g_hash_table_new (GHashFunc hash_func
,
113 GEqualFunc key_equal_func
)
115 return g_hash_table_new_full (hash_func
, key_equal_func
, NULL
, NULL
);
120 * g_hash_table_new_full:
121 * @hash_func: a function to create a hash value from a key.
122 * @key_equal_func: a function to check two keys for equality.
123 * @key_destroy_func: a function to free the memory allocated for the key
124 * used when removing the entry from the #GHashTable or %NULL if you
125 * don't want to supply such a function.
126 * @value_destroy_func: a function to free the memory allocated for the
127 * value used when removing the entry from the #GHashTable or %NULL if
128 * you don't want to supply such a function.
130 * Creates a new #GHashTable like g_hash_table_new() and allows to specify
131 * functions to free the memory allocated for the key and value that get
132 * called when removing the entry from the #GHashTable.
134 * Return value: a new #GHashTable.
137 g_hash_table_new_full (GHashFunc hash_func
,
138 GEqualFunc key_equal_func
,
139 GDestroyNotify key_destroy_func
,
140 GDestroyNotify value_destroy_func
)
142 GHashTable
*hash_table
;
145 hash_table
= g_new (GHashTable
, 1);
146 hash_table
->size
= HASH_TABLE_MIN_SIZE
;
147 hash_table
->nnodes
= 0;
148 hash_table
->hash_func
= hash_func
? hash_func
: g_direct_hash
;
149 hash_table
->key_equal_func
= key_equal_func
;
150 hash_table
->key_destroy_func
= key_destroy_func
;
151 hash_table
->value_destroy_func
= value_destroy_func
;
152 hash_table
->nodes
= g_new (GHashNode
*, hash_table
->size
);
154 for (i
= 0; i
< hash_table
->size
; i
++)
155 hash_table
->nodes
[i
] = NULL
;
161 * g_hash_table_destroy:
162 * @hash_table: a #GHashTable.
164 * Destroys the #GHashTable. If keys and/or values are dynamically
165 * allocated, you should either free them first or create the #GHashTable
166 * using g_hash_table_new_full(). In the latter case the destroy functions
167 * you supplied will be called on all keys and values before destroying
171 g_hash_table_destroy (GHashTable
*hash_table
)
175 g_return_if_fail (hash_table
!= NULL
);
177 for (i
= 0; i
< hash_table
->size
; i
++)
178 g_hash_nodes_destroy (hash_table
->nodes
[i
],
179 hash_table
->key_destroy_func
,
180 hash_table
->value_destroy_func
);
182 g_free (hash_table
->nodes
);
186 static inline GHashNode
**
187 g_hash_table_lookup_node (GHashTable
*hash_table
,
192 node
= &hash_table
->nodes
193 [(* hash_table
->hash_func
) (key
) % hash_table
->size
];
195 /* Hash table lookup needs to be fast.
196 * We therefore remove the extra conditional of testing
197 * whether to call the key_equal_func or not from
200 if (hash_table
->key_equal_func
)
201 while (*node
&& !(*hash_table
->key_equal_func
) ((*node
)->key
, key
))
202 node
= &(*node
)->next
;
204 while (*node
&& (*node
)->key
!= key
)
205 node
= &(*node
)->next
;
211 * g_hash_table_lookup:
212 * @hash_table: a #GHashTable.
213 * @key: the key to look up.
215 * Looks up a key in a #GHashTable.
217 * Return value: the associated value, or %NULL if the key is not found.
220 g_hash_table_lookup (GHashTable
*hash_table
,
225 g_return_val_if_fail (hash_table
!= NULL
, NULL
);
227 node
= *g_hash_table_lookup_node (hash_table
, key
);
229 return node
? node
->value
: NULL
;
233 * g_hash_table_lookup_extended:
234 * @hash_table: a #GHashTable.
235 * @lookup_key: the key to look up.
236 * @orig_key: returns the original key.
237 * @value: returns the value associated with the key.
239 * Looks up a key in the #GHashTable, returning the original key and the
240 * associated value and a #gboolean which is %TRUE if the key was found. This
241 * is useful if you need to free the memory allocated for the original key,
242 * for example before calling g_hash_table_remove().
244 * Return value: %TRUE if the key was found in the #GHashTable.
247 g_hash_table_lookup_extended (GHashTable
*hash_table
,
248 gconstpointer lookup_key
,
254 g_return_val_if_fail (hash_table
!= NULL
, FALSE
);
256 node
= *g_hash_table_lookup_node (hash_table
, lookup_key
);
261 *orig_key
= node
->key
;
263 *value
= node
->value
;
271 * g_hash_table_insert:
272 * @hash_table: a #GHashTable.
273 * @key: a key to insert.
274 * @value: the value to associate with the key.
276 * Inserts a new key and value into a #GHashTable.
278 * If the key already exists in the #GHashTable its current value is replaced
279 * with the new value. If you supplied a @value_destroy_func when creating the
280 * #GHashTable, the old value is freed using that function. If you supplied
281 * a @key_destroy_func when creating the #GHashTable, the passed key is freed
282 * using that function.
285 g_hash_table_insert (GHashTable
*hash_table
,
291 g_return_if_fail (hash_table
!= NULL
);
293 node
= g_hash_table_lookup_node (hash_table
, key
);
297 /* do not reset node->key in this place, keeping
298 * the old key is the intended behaviour.
299 * g_hash_table_replace() can be used instead.
302 /* free the passed key */
303 if (hash_table
->key_destroy_func
)
304 hash_table
->key_destroy_func (key
);
306 if (hash_table
->value_destroy_func
)
307 hash_table
->value_destroy_func ((*node
)->value
);
309 (*node
)->value
= value
;
313 *node
= g_hash_node_new (key
, value
);
314 hash_table
->nnodes
++;
315 G_HASH_TABLE_RESIZE (hash_table
);
320 * g_hash_table_replace:
321 * @hash_table: a #GHashTable.
322 * @key: a key to insert.
323 * @value: the value to associate with the key.
325 * Inserts a new key and value into a #GHashTable similar to
326 * g_hash_table_insert(). The difference is that if the key already exists
327 * in the #GHashTable, it gets replaced by the new key. If you supplied a
328 * @value_destroy_func when creating the #GHashTable, the old value is freed
329 * using that function. If you supplied a @key_destroy_func when creating the
330 * #GHashTable, the old key is freed using that function.
333 g_hash_table_replace (GHashTable
*hash_table
,
339 g_return_if_fail (hash_table
!= NULL
);
341 node
= g_hash_table_lookup_node (hash_table
, key
);
345 if (hash_table
->key_destroy_func
)
346 hash_table
->key_destroy_func ((*node
)->key
);
348 if (hash_table
->value_destroy_func
)
349 hash_table
->value_destroy_func ((*node
)->value
);
352 (*node
)->value
= value
;
356 *node
= g_hash_node_new (key
, value
);
357 hash_table
->nnodes
++;
358 G_HASH_TABLE_RESIZE (hash_table
);
363 * g_hash_table_remove:
364 * @hash_table: a #GHashTable.
365 * @key: the key to remove.
367 * Removes a key and its associated value from a #GHashTable.
369 * If the #GHashTable was created using g_hash_table_new_full(), the
370 * key and value are freed using the supplied destroy functions, otherwise
371 * you have to make sure that any dynamically allocated values are freed
374 * Return value: %TRUE if the key was found and removed from the #GHashTable.
377 g_hash_table_remove (GHashTable
*hash_table
,
380 GHashNode
**node
, *dest
;
382 g_return_val_if_fail (hash_table
!= NULL
, FALSE
);
384 node
= g_hash_table_lookup_node (hash_table
, key
);
388 (*node
) = dest
->next
;
389 g_hash_node_destroy (dest
,
390 hash_table
->key_destroy_func
,
391 hash_table
->value_destroy_func
);
392 hash_table
->nnodes
--;
394 G_HASH_TABLE_RESIZE (hash_table
);
403 * g_hash_table_steal:
404 * @hash_table: a #GHashTable.
405 * @key: the key to remove.
407 * Removes a key and its associated value from a #GHashTable without
408 * calling the key and value destroy functions.
410 * Return value: %TRUE if the key was found and removed from the #GHashTable.
413 g_hash_table_steal (GHashTable
*hash_table
,
416 GHashNode
**node
, *dest
;
418 g_return_val_if_fail (hash_table
!= NULL
, FALSE
);
420 node
= g_hash_table_lookup_node (hash_table
, key
);
424 (*node
) = dest
->next
;
425 g_hash_node_destroy (dest
, NULL
, NULL
);
426 hash_table
->nnodes
--;
428 G_HASH_TABLE_RESIZE (hash_table
);
437 * g_hash_table_foreach_remove:
438 * @hash_table: a #GHashTable.
439 * @func: the function to call for each key/value pair.
440 * @user_data: user data to pass to the function.
442 * Calls the given function for each key/value pair in the #GHashTable.
443 * If the function returns %TRUE, then the key/value pair is removed from the
444 * #GHashTable. If you supplied key or value destroy functions when creating
445 * the #GHashTable, they are used to free the memory allocated for the removed
448 * Return value: the number of key/value pairs removed.
451 g_hash_table_foreach_remove (GHashTable
*hash_table
,
455 g_return_val_if_fail (hash_table
!= NULL
, 0);
456 g_return_val_if_fail (func
!= NULL
, 0);
458 return g_hash_table_foreach_remove_or_steal (hash_table
, func
, user_data
, TRUE
);
462 * g_hash_table_foreach_steal:
463 * @hash_table: a #GHashTable.
464 * @func: the function to call for each key/value pair.
465 * @user_data: user data to pass to the function.
467 * Calls the given function for each key/value pair in the #GHashTable.
468 * If the function returns %TRUE, then the key/value pair is removed from the
469 * #GHashTable, but no key or value destroy functions are called.
471 * Return value: the number of key/value pairs removed.
474 g_hash_table_foreach_steal (GHashTable
*hash_table
,
478 g_return_val_if_fail (hash_table
!= NULL
, 0);
479 g_return_val_if_fail (func
!= NULL
, 0);
481 return g_hash_table_foreach_remove_or_steal (hash_table
, func
, user_data
, FALSE
);
485 g_hash_table_foreach_remove_or_steal (GHashTable
*hash_table
,
490 GHashNode
*node
, *prev
;
494 for (i
= 0; i
< hash_table
->size
; i
++)
500 for (node
= hash_table
->nodes
[i
]; node
; prev
= node
, node
= node
->next
)
502 if ((* func
) (node
->key
, node
->value
, user_data
))
506 hash_table
->nnodes
-= 1;
510 prev
->next
= node
->next
;
511 g_hash_node_destroy (node
,
512 notify
? hash_table
->key_destroy_func
: NULL
,
513 notify
? hash_table
->value_destroy_func
: NULL
);
518 hash_table
->nodes
[i
] = node
->next
;
519 g_hash_node_destroy (node
,
520 notify
? hash_table
->key_destroy_func
: NULL
,
521 notify
? hash_table
->value_destroy_func
: NULL
);
528 G_HASH_TABLE_RESIZE (hash_table
);
534 * g_hash_table_foreach:
535 * @hash_table: a #GHashTable.
536 * @func: the function to call for each key/value pair.
537 * @user_data: user data to pass to the function.
539 * Calls the given function for each of the key/value pairs in the
540 * #GHashTable. The function is passed the key and value of each
541 * pair, and the given @user_data parameter. The hash table may not
542 * be modified while iterating over it (you can't add/remove
543 * items). To remove all items matching a predicate, use
544 * g_hash_table_remove().
547 g_hash_table_foreach (GHashTable
*hash_table
,
554 g_return_if_fail (hash_table
!= NULL
);
555 g_return_if_fail (func
!= NULL
);
557 for (i
= 0; i
< hash_table
->size
; i
++)
558 for (node
= hash_table
->nodes
[i
]; node
; node
= node
->next
)
559 (* func
) (node
->key
, node
->value
, user_data
);
564 * @hash_table: a #GHashTable.
566 * Returns the number of elements contained in the #GHashTable.
568 * Return value: the number of key/value pairs in the #GHashTable.
571 g_hash_table_size (GHashTable
*hash_table
)
573 g_return_val_if_fail (hash_table
!= NULL
, 0);
575 return hash_table
->nnodes
;
579 g_hash_table_resize (GHashTable
*hash_table
)
581 GHashNode
**new_nodes
;
588 new_size
= g_spaced_primes_closest (hash_table
->nnodes
);
589 new_size
= CLAMP (new_size
, HASH_TABLE_MIN_SIZE
, HASH_TABLE_MAX_SIZE
);
591 new_nodes
= g_new0 (GHashNode
*, new_size
);
593 for (i
= 0; i
< hash_table
->size
; i
++)
594 for (node
= hash_table
->nodes
[i
]; node
; node
= next
)
598 hash_val
= (* hash_table
->hash_func
) (node
->key
) % new_size
;
600 node
->next
= new_nodes
[hash_val
];
601 new_nodes
[hash_val
] = node
;
604 g_free (hash_table
->nodes
);
605 hash_table
->nodes
= new_nodes
;
606 hash_table
->size
= new_size
;
610 g_hash_node_new (gpointer key
,
613 GHashNode
*hash_node
;
615 G_LOCK (g_hash_global
);
618 hash_node
= node_free_list
;
619 node_free_list
= node_free_list
->next
;
624 node_mem_chunk
= g_mem_chunk_new ("hash node mem chunk",
628 hash_node
= g_chunk_new (GHashNode
, node_mem_chunk
);
630 G_UNLOCK (g_hash_global
);
632 hash_node
->key
= key
;
633 hash_node
->value
= value
;
634 hash_node
->next
= NULL
;
640 g_hash_node_destroy (GHashNode
*hash_node
,
641 GDestroyNotify key_destroy_func
,
642 GDestroyNotify value_destroy_func
)
644 if (key_destroy_func
)
645 key_destroy_func (hash_node
->key
);
646 if (value_destroy_func
)
647 value_destroy_func (hash_node
->value
);
649 #ifdef ENABLE_GC_FRIENDLY
650 hash_node
->key
= NULL
;
651 hash_node
->value
= NULL
;
652 #endif /* ENABLE_GC_FRIENDLY */
654 G_LOCK (g_hash_global
);
655 hash_node
->next
= node_free_list
;
656 node_free_list
= hash_node
;
657 G_UNLOCK (g_hash_global
);
661 g_hash_nodes_destroy (GHashNode
*hash_node
,
662 GFreeFunc key_destroy_func
,
663 GFreeFunc value_destroy_func
)
667 GHashNode
*node
= hash_node
;
671 if (key_destroy_func
)
672 key_destroy_func (node
->key
);
673 if (value_destroy_func
)
674 value_destroy_func (node
->value
);
676 #ifdef ENABLE_GC_FRIENDLY
679 #endif /* ENABLE_GC_FRIENDLY */
684 if (key_destroy_func
)
685 key_destroy_func (node
->key
);
686 if (value_destroy_func
)
687 value_destroy_func (node
->value
);
689 #ifdef ENABLE_GC_FRIENDLY
692 #endif /* ENABLE_GC_FRIENDLY */
694 G_LOCK (g_hash_global
);
695 node
->next
= node_free_list
;
696 node_free_list
= hash_node
;
697 G_UNLOCK (g_hash_global
);