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
);
764 #include "galiasdef.c"