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 Library 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 * Library General Public License for more details.
14 * You should have received a copy of the GNU Library 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.
22 #define HASH_TABLE_MIN_SIZE 11
23 #define HASH_TABLE_MAX_SIZE 13845163
26 typedef struct _GHashNode GHashNode;
27 typedef struct _GRealHashTable GRealHashTable;
36 struct _GRealHashTable
43 GCompareFunc key_compare_func;
47 static void g_hash_table_resize (GHashTable *hash_table);
48 static gint g_hash_closest_prime (gint num);
49 static GHashNode* g_hash_node_new (gpointer key,
51 static void g_hash_node_destroy (GHashNode *hash_node);
52 static void g_hash_nodes_destroy (GHashNode *hash_node);
55 extern gint g_primes[];
56 extern gint g_nprimes;
58 static GMemChunk *node_mem_chunk = NULL;
59 static GHashNode *node_free_list = NULL;
63 g_hash_table_new (GHashFunc hash_func,
64 GCompareFunc key_compare_func)
66 GRealHashTable *hash_table;
68 g_return_val_if_fail (hash_func != NULL, NULL);
70 hash_table = g_new (GRealHashTable, 1);
72 hash_table->nnodes = 0;
73 hash_table->frozen = FALSE;
74 hash_table->nodes = NULL;
75 hash_table->hash_func = hash_func;
76 hash_table->key_compare_func = key_compare_func;
78 return ((GHashTable*) hash_table);
82 g_hash_table_destroy (GHashTable *hash_table)
84 GRealHashTable *rhash_table;
89 rhash_table = (GRealHashTable*) hash_table;
91 for (i = 0; i < rhash_table->size; i++)
92 g_hash_nodes_destroy (rhash_table->nodes[i]);
94 if (rhash_table->nodes)
95 g_free (rhash_table->nodes);
101 g_hash_table_insert (GHashTable *hash_table,
105 GRealHashTable *rhash_table;
111 rhash_table = (GRealHashTable*) hash_table;
113 if (rhash_table->size == 0)
114 g_hash_table_resize (hash_table);
116 hash_val = (* rhash_table->hash_func) (key) % rhash_table->size;
118 node = rhash_table->nodes[hash_val];
121 if ((rhash_table->key_compare_func &&
122 (* rhash_table->key_compare_func) (node->key, key)) ||
125 /* do not reset node->key in this place, keeping
126 * the old key might be intended.
127 * a g_hash_table_remove/g_hash_table_insert pair
128 * can be used otherwise.
138 node = g_hash_node_new (key, value);
139 node->next = rhash_table->nodes[hash_val];
140 rhash_table->nodes[hash_val] = node;
142 rhash_table->nnodes += 1;
143 g_hash_table_resize (hash_table);
148 g_hash_table_remove (GHashTable *hash_table,
151 GRealHashTable *rhash_table;
156 rhash_table = (GRealHashTable*) hash_table;
157 if (hash_table && rhash_table->size)
159 hash_val = (* rhash_table->hash_func) (key) % rhash_table->size;
162 node = rhash_table->nodes[hash_val];
166 if ((rhash_table->key_compare_func &&
167 (* rhash_table->key_compare_func) (node->key, key)) ||
171 prev->next = node->next;
172 if (node == rhash_table->nodes[hash_val])
173 rhash_table->nodes[hash_val] = node->next;
175 g_hash_node_destroy (node);
177 rhash_table->nnodes -= 1;
178 g_hash_table_resize (hash_table);
189 g_hash_table_lookup (GHashTable *hash_table,
192 GRealHashTable *rhash_table;
196 rhash_table = (GRealHashTable*) hash_table;
197 if (hash_table && rhash_table->size)
199 hash_val = (* rhash_table->hash_func) (key) % rhash_table->size;
201 node = rhash_table->nodes[hash_val];
203 /* Hash table lookup needs to be fast.
204 * We therefore remove the extra conditional of testing
205 * whether to call the key_compare_func or not from
208 if (rhash_table->key_compare_func)
212 if ((* rhash_table->key_compare_func) (node->key, key))
221 if (node->key == key)
232 g_hash_table_freeze (GHashTable *hash_table)
234 GRealHashTable *rhash_table;
238 rhash_table = (GRealHashTable*) hash_table;
239 rhash_table->frozen = TRUE;
244 g_hash_table_thaw (GHashTable *hash_table)
246 GRealHashTable *rhash_table;
250 rhash_table = (GRealHashTable*) hash_table;
251 rhash_table->frozen = FALSE;
253 g_hash_table_resize (hash_table);
258 g_hash_table_foreach (GHashTable *hash_table,
262 GRealHashTable *rhash_table;
268 rhash_table = (GRealHashTable*) hash_table;
270 for (i = 0; i < rhash_table->size; i++)
272 node = rhash_table->nodes[i];
276 (* func) (node->key, node->value, user_data);
285 g_hash_table_resize (GHashTable *hash_table)
287 GRealHashTable *rhash_table;
288 GHashNode **new_nodes;
291 gfloat nodes_per_list;
299 rhash_table = (GRealHashTable*) hash_table;
301 if (rhash_table->size == 0)
303 rhash_table->size = HASH_TABLE_MIN_SIZE;
304 rhash_table->nodes = g_new (GHashNode*, rhash_table->size);
306 for (i = 0; i < rhash_table->size; i++)
307 rhash_table->nodes[i] = NULL;
309 else if (!rhash_table->frozen)
312 nodes_per_list = (gfloat) rhash_table->nnodes / (gfloat) rhash_table->size;
314 if (nodes_per_list < 0.3)
316 if (rhash_table->size > HASH_TABLE_MIN_SIZE)
319 else if (nodes_per_list > 3.0)
321 if (rhash_table->size < HASH_TABLE_MAX_SIZE)
327 new_size = g_hash_closest_prime (rhash_table->nnodes);
328 if (new_size < HASH_TABLE_MIN_SIZE)
329 new_size = HASH_TABLE_MIN_SIZE;
330 else if (new_size > HASH_TABLE_MAX_SIZE)
331 new_size = HASH_TABLE_MAX_SIZE;
333 new_nodes = g_new (GHashNode*, new_size);
335 for (i = 0; i < new_size; i++)
338 for (i = 0; i < rhash_table->size; i++)
340 node = rhash_table->nodes[i];
346 hash_val = (* rhash_table->hash_func) (node->key) % new_size;
347 node->next = new_nodes[hash_val];
348 new_nodes[hash_val] = node;
354 g_free (rhash_table->nodes);
356 rhash_table->nodes = new_nodes;
357 rhash_table->size = new_size;
364 g_hash_closest_prime (gint num)
368 for (i = 0; i < g_nprimes; i++)
369 if ((g_primes[i] - num) > 0)
372 return g_primes[g_nprimes - 1];
376 g_hash_node_new (gpointer key,
379 GHashNode *hash_node;
383 hash_node = node_free_list;
384 node_free_list = node_free_list->next;
389 node_mem_chunk = g_mem_chunk_new ("hash node mem chunk",
393 hash_node = g_chunk_new (GHashNode, node_mem_chunk);
396 hash_node->key = key;
397 hash_node->value = value;
398 hash_node->next = NULL;
404 g_hash_node_destroy (GHashNode *hash_node)
408 hash_node->next = node_free_list;
409 node_free_list = hash_node;
414 g_hash_nodes_destroy (GHashNode *hash_node)
423 node->next = node_free_list;
424 node_free_list = hash_node;