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/.
34 #define HASH_TABLE_MIN_SIZE 11
35 #define HASH_TABLE_MAX_SIZE 13845163
38 typedef struct _GHashNode GHashNode;
53 GEqualFunc key_equal_func;
57 static void g_hash_table_resize (GHashTable *hash_table);
58 static GHashNode** g_hash_table_lookup_node (GHashTable *hash_table,
60 static GHashNode* g_hash_node_new (gpointer key,
62 static void g_hash_node_destroy (GHashNode *hash_node);
63 static void g_hash_nodes_destroy (GHashNode *hash_node);
66 G_LOCK_DEFINE_STATIC (g_hash_global);
68 static GMemChunk *node_mem_chunk = NULL;
69 static GHashNode *node_free_list = NULL;
73 g_hash_table_new (GHashFunc hash_func,
74 GEqualFunc key_equal_func)
76 GHashTable *hash_table;
79 hash_table = g_new (GHashTable, 1);
80 hash_table->size = HASH_TABLE_MIN_SIZE;
81 hash_table->nnodes = 0;
82 hash_table->hash_func = hash_func ? hash_func : g_direct_hash;
83 hash_table->key_equal_func = key_equal_func;
84 hash_table->nodes = g_new (GHashNode*, hash_table->size);
86 for (i = 0; i < hash_table->size; i++)
87 hash_table->nodes[i] = NULL;
93 g_hash_table_destroy (GHashTable *hash_table)
97 g_return_if_fail (hash_table != NULL);
99 for (i = 0; i < hash_table->size; i++)
100 g_hash_nodes_destroy (hash_table->nodes[i]);
102 g_free (hash_table->nodes);
106 static inline GHashNode**
107 g_hash_table_lookup_node (GHashTable *hash_table,
112 node = &hash_table->nodes
113 [(* hash_table->hash_func) (key) % hash_table->size];
115 /* Hash table lookup needs to be fast.
116 * We therefore remove the extra conditional of testing
117 * whether to call the key_equal_func or not from
120 if (hash_table->key_equal_func)
121 while (*node && !(*hash_table->key_equal_func) ((*node)->key, key))
122 node = &(*node)->next;
124 while (*node && (*node)->key != key)
125 node = &(*node)->next;
131 g_hash_table_lookup (GHashTable *hash_table,
136 g_return_val_if_fail (hash_table != NULL, NULL);
138 node = *g_hash_table_lookup_node (hash_table, key);
140 return node ? node->value : NULL;
144 g_hash_table_insert (GHashTable *hash_table,
150 g_return_if_fail (hash_table != NULL);
152 node = g_hash_table_lookup_node (hash_table, key);
156 /* do not reset node->key in this place, keeping
157 * the old key might be intended.
158 * a g_hash_table_remove/g_hash_table_insert pair
159 * can be used otherwise.
161 * node->key = key; */
162 (*node)->value = value;
166 *node = g_hash_node_new (key, value);
167 hash_table->nnodes++;
168 g_hash_table_resize (hash_table);
173 g_hash_table_remove (GHashTable *hash_table,
176 GHashNode **node, *dest;
178 g_return_val_if_fail (hash_table != NULL, FALSE);
180 node = g_hash_table_lookup_node (hash_table, key);
184 (*node) = dest->next;
185 g_hash_node_destroy (dest);
186 hash_table->nnodes--;
188 g_hash_table_resize (hash_table);
197 g_hash_table_lookup_extended (GHashTable *hash_table,
198 gconstpointer lookup_key,
204 g_return_val_if_fail (hash_table != NULL, FALSE);
206 node = *g_hash_table_lookup_node (hash_table, lookup_key);
211 *orig_key = node->key;
213 *value = node->value;
221 g_hash_table_freeze (GHashTable *hash_table)
223 #ifdef G_ENABLE_DEBUG
224 static gboolean first_call = TRUE;
228 g_warning("g_hash_table_freeze and g_hash_table_thaw are deprecated.");
231 #endif /* G_ENABLE_DEBUG */
235 g_hash_table_thaw (GHashTable *hash_table)
240 g_hash_table_foreach_remove (GHashTable *hash_table,
244 GHashNode *node, *prev;
248 g_return_val_if_fail (hash_table != NULL, 0);
249 g_return_val_if_fail (func != NULL, 0);
251 for (i = 0; i < hash_table->size; i++)
257 for (node = hash_table->nodes[i]; node; prev = node, node = node->next)
259 if ((* func) (node->key, node->value, user_data))
263 hash_table->nnodes -= 1;
267 prev->next = node->next;
268 g_hash_node_destroy (node);
273 hash_table->nodes[i] = node->next;
274 g_hash_node_destroy (node);
281 g_hash_table_resize (hash_table);
287 g_hash_table_foreach (GHashTable *hash_table,
294 g_return_if_fail (hash_table != NULL);
295 g_return_if_fail (func != NULL);
297 for (i = 0; i < hash_table->size; i++)
298 for (node = hash_table->nodes[i]; node; node = node->next)
299 (* func) (node->key, node->value, user_data);
302 /* Returns the number of elements contained in the hash table. */
304 g_hash_table_size (GHashTable *hash_table)
306 g_return_val_if_fail (hash_table != NULL, 0);
308 return hash_table->nnodes;
312 g_hash_table_resize (GHashTable *hash_table)
314 GHashNode **new_nodes;
317 gfloat nodes_per_list;
322 nodes_per_list = (gfloat) hash_table->nnodes / (gfloat) hash_table->size;
324 if ((nodes_per_list > 0.3 || hash_table->size <= HASH_TABLE_MIN_SIZE) &&
325 (nodes_per_list < 3.0 || hash_table->size >= HASH_TABLE_MAX_SIZE))
328 new_size = CLAMP(g_spaced_primes_closest (hash_table->nnodes),
330 HASH_TABLE_MAX_SIZE);
331 new_nodes = g_new0 (GHashNode*, new_size);
333 for (i = 0; i < hash_table->size; i++)
334 for (node = hash_table->nodes[i]; node; node = next)
338 hash_val = (* hash_table->hash_func) (node->key) % new_size;
340 node->next = new_nodes[hash_val];
341 new_nodes[hash_val] = node;
344 g_free (hash_table->nodes);
345 hash_table->nodes = new_nodes;
346 hash_table->size = new_size;
350 g_hash_node_new (gpointer key,
353 GHashNode *hash_node;
355 G_LOCK (g_hash_global);
358 hash_node = node_free_list;
359 node_free_list = node_free_list->next;
364 node_mem_chunk = g_mem_chunk_new ("hash node mem chunk",
368 hash_node = g_chunk_new (GHashNode, node_mem_chunk);
370 G_UNLOCK (g_hash_global);
372 hash_node->key = key;
373 hash_node->value = value;
374 hash_node->next = NULL;
380 g_hash_node_destroy (GHashNode *hash_node)
383 #ifdef ENABLE_GC_FRIENDLY
384 hash_node->key = NULL;
385 hash_node->value = NULL;
386 #endif /* ENABLE_GC_FRIENDLY */
388 G_LOCK (g_hash_global);
389 hash_node->next = node_free_list;
390 node_free_list = hash_node;
391 G_UNLOCK (g_hash_global);
395 g_hash_nodes_destroy (GHashNode *hash_node)
399 GHashNode *node = hash_node;
403 #ifdef ENABLE_GC_FRIENDLY
406 #endif /* ENABLE_GC_FRIENDLY */
410 #ifdef ENABLE_GC_FRIENDLY
413 #endif /* ENABLE_GC_FRIENDLY */
415 G_LOCK (g_hash_global);
416 node->next = node_free_list;
417 node_free_list = hash_node;
418 G_UNLOCK (g_hash_global);