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 Free
16 * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
21 #define HASH_TABLE_MIN_SIZE 11
22 #define HASH_TABLE_MAX_SIZE 13845163
25 typedef struct _GHashNode GHashNode;
26 typedef struct _GRealHashTable GRealHashTable;
35 struct _GRealHashTable
42 GCompareFunc key_compare_func;
46 static void g_hash_table_resize (GHashTable *hash_table);
47 static gint g_hash_closest_prime (gint num);
48 static GHashNode* g_hash_node_new (gpointer key,
50 static void g_hash_node_destroy (GHashNode *hash_node);
51 static void g_hash_nodes_destroy (GHashNode *hash_node);
54 extern gint g_primes[];
55 extern gint g_nprimes;
57 static GMemChunk *node_mem_chunk = NULL;
58 static GHashNode *node_free_list = NULL;
62 g_hash_table_new (GHashFunc hash_func,
63 GCompareFunc key_compare_func)
65 GRealHashTable *hash_table;
67 g_return_val_if_fail (hash_func != NULL, NULL);
69 hash_table = g_new (GRealHashTable, 1);
71 hash_table->nnodes = 0;
72 hash_table->frozen = FALSE;
73 hash_table->nodes = NULL;
74 hash_table->hash_func = hash_func;
75 hash_table->key_compare_func = key_compare_func;
77 return ((GHashTable*) hash_table);
81 g_hash_table_destroy (GHashTable *hash_table)
83 GRealHashTable *rhash_table;
88 rhash_table = (GRealHashTable*) hash_table;
90 for (i = 0; i < rhash_table->size; i++)
91 g_hash_nodes_destroy (rhash_table->nodes[i]);
93 if (rhash_table->nodes)
94 g_free (rhash_table->nodes);
100 g_hash_table_insert (GHashTable *hash_table,
104 GRealHashTable *rhash_table;
110 rhash_table = (GRealHashTable*) hash_table;
112 if (rhash_table->size == 0)
113 g_hash_table_resize (hash_table);
115 hash_val = (* rhash_table->hash_func) (key) % rhash_table->size;
117 node = rhash_table->nodes[hash_val];
120 if ((rhash_table->key_compare_func &&
121 (* rhash_table->key_compare_func) (node->key, key)) ||
130 node = g_hash_node_new (key, value);
131 node->next = rhash_table->nodes[hash_val];
132 rhash_table->nodes[hash_val] = node;
134 rhash_table->nnodes += 1;
135 g_hash_table_resize (hash_table);
140 g_hash_table_remove (GHashTable *hash_table,
143 GRealHashTable *rhash_table;
148 rhash_table = (GRealHashTable*) hash_table;
149 if (hash_table && rhash_table->size)
151 hash_val = (* rhash_table->hash_func) (key) % rhash_table->size;
154 node = rhash_table->nodes[hash_val];
158 if ((rhash_table->key_compare_func &&
159 (* rhash_table->key_compare_func) (node->key, key)) ||
163 prev->next = node->next;
164 if (node == rhash_table->nodes[hash_val])
165 rhash_table->nodes[hash_val] = node->next;
167 g_hash_node_destroy (node);
169 rhash_table->nnodes -= 1;
170 g_hash_table_resize (hash_table);
181 g_hash_table_lookup (GHashTable *hash_table,
184 GRealHashTable *rhash_table;
188 rhash_table = (GRealHashTable*) hash_table;
189 if (hash_table && rhash_table->size)
191 hash_val = (* rhash_table->hash_func) (key) % rhash_table->size;
193 node = rhash_table->nodes[hash_val];
195 /* Hash table lookup needs to be fast.
196 * We therefore remove the extra conditional of testing
197 * whether to call the key_compare_func or not from
200 if (rhash_table->key_compare_func)
204 if ((* rhash_table->key_compare_func) (node->key, key))
213 if (node->key == key)
224 g_hash_table_freeze (GHashTable *hash_table)
226 GRealHashTable *rhash_table;
230 rhash_table = (GRealHashTable*) hash_table;
231 rhash_table->frozen = TRUE;
236 g_hash_table_thaw (GHashTable *hash_table)
238 GRealHashTable *rhash_table;
242 rhash_table = (GRealHashTable*) hash_table;
243 rhash_table->frozen = FALSE;
245 g_hash_table_resize (hash_table);
250 g_hash_table_foreach (GHashTable *hash_table,
254 GRealHashTable *rhash_table;
260 rhash_table = (GRealHashTable*) hash_table;
262 for (i = 0; i < rhash_table->size; i++)
264 node = rhash_table->nodes[i];
268 (* func) (node->key, node->value, user_data);
277 g_hash_table_resize (GHashTable *hash_table)
279 GRealHashTable *rhash_table;
280 GHashNode **new_nodes;
283 gfloat nodes_per_list;
291 rhash_table = (GRealHashTable*) hash_table;
293 if (rhash_table->size == 0)
295 rhash_table->size = HASH_TABLE_MIN_SIZE;
296 rhash_table->nodes = g_new (GHashNode*, rhash_table->size);
298 for (i = 0; i < rhash_table->size; i++)
299 rhash_table->nodes[i] = NULL;
301 else if (!rhash_table->frozen)
304 nodes_per_list = (gfloat) rhash_table->nnodes / (gfloat) rhash_table->size;
306 if (nodes_per_list < 0.3)
308 if (rhash_table->size > HASH_TABLE_MIN_SIZE)
311 else if (nodes_per_list > 3.0)
313 if (rhash_table->size < HASH_TABLE_MAX_SIZE)
319 new_size = g_hash_closest_prime (rhash_table->nnodes);
320 if (new_size < HASH_TABLE_MIN_SIZE)
321 new_size = HASH_TABLE_MIN_SIZE;
322 else if (new_size > HASH_TABLE_MAX_SIZE)
323 new_size = HASH_TABLE_MAX_SIZE;
325 new_nodes = g_new (GHashNode*, new_size);
327 for (i = 0; i < new_size; i++)
330 for (i = 0; i < rhash_table->size; i++)
332 node = rhash_table->nodes[i];
338 hash_val = (* rhash_table->hash_func) (node->key) % new_size;
339 node->next = new_nodes[hash_val];
340 new_nodes[hash_val] = node;
346 g_free (rhash_table->nodes);
348 rhash_table->nodes = new_nodes;
349 rhash_table->size = new_size;
356 g_hash_closest_prime (gint num)
360 for (i = 0; i < g_nprimes; i++)
361 if ((g_primes[i] - num) > 0)
364 return g_primes[g_nprimes - 1];
368 g_hash_node_new (gpointer key,
371 GHashNode *hash_node;
375 hash_node = node_free_list;
376 node_free_list = node_free_list->next;
381 node_mem_chunk = g_mem_chunk_new ("hash node mem chunk",
385 hash_node = g_chunk_new (GHashNode, node_mem_chunk);
388 hash_node->key = key;
389 hash_node->value = value;
390 hash_node->next = NULL;
396 g_hash_node_destroy (GHashNode *hash_node)
400 hash_node->next = node_free_list;
401 node_free_list = hash_node;
406 g_hash_nodes_destroy (GHashNode *hash_node)
415 node->next = node_free_list;
416 node_free_list = hash_node;