This is Josh, commiting as Manish. This is completely new, and
[platform/upstream/glib.git] / ghash.c
1 /* GLIB - Library of useful routines for C programming
2  * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald
3  *
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.
8  *
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.
13  *
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.
18  */
19 #include "glib.h"
20
21
22 #define HASH_TABLE_MIN_SIZE 11
23 #define HASH_TABLE_MAX_SIZE 13845163
24
25
26 typedef struct _GHashNode      GHashNode;
27
28 struct _GHashNode
29 {
30   gpointer key;
31   gpointer value;
32   GHashNode *next;
33 };
34
35 struct _GHashTable
36 {
37   gint size;
38   gint nnodes;
39   gint frozen;
40   GHashNode **nodes;
41   GHashFunc hash_func;
42   GCompareFunc key_compare_func;
43 };
44
45
46 static void             g_hash_table_resize     (GHashTable     *hash_table);
47 static GHashNode**      g_hash_table_lookup_node(GHashTable     *hash_table,
48                                                  gconstpointer   key);
49 static GHashNode*       g_hash_node_new         (gpointer        key,
50                                                  gpointer        value);
51 static void             g_hash_node_destroy     (GHashNode      *hash_node);
52 static void             g_hash_nodes_destroy    (GHashNode      *hash_node);
53
54
55 static GMemChunk *node_mem_chunk = NULL;
56 static GHashNode *node_free_list = NULL;
57
58
59 GHashTable*
60 g_hash_table_new (GHashFunc    hash_func,
61                   GCompareFunc key_compare_func)
62 {
63   GHashTable *hash_table;
64   gint i;
65
66   hash_table = g_new (GHashTable, 1);
67   hash_table->size = HASH_TABLE_MIN_SIZE;
68   hash_table->nnodes = 0;
69   hash_table->frozen = FALSE;
70   hash_table->hash_func = hash_func ? hash_func : g_direct_hash;
71   hash_table->key_compare_func = key_compare_func;
72   hash_table->nodes = g_new (GHashNode*, hash_table->size);
73
74   for (i = 0; i < hash_table->size; i++)
75     hash_table->nodes[i] = NULL;
76
77   return hash_table;
78 }
79
80 void
81 g_hash_table_destroy (GHashTable *hash_table)
82 {
83   gint i;
84
85   g_return_if_fail (hash_table);
86
87   for (i = 0; i < hash_table->size; i++)
88     g_hash_nodes_destroy (hash_table->nodes[i]);
89
90   g_free (hash_table->nodes);
91   g_free (hash_table);
92 }
93
94 void
95 g_hash_table_insert (GHashTable *hash_table,
96                      gpointer    key,
97                      gpointer    value)
98 {
99   GHashNode **node;
100
101   g_return_if_fail (hash_table);
102
103   node = g_hash_table_lookup_node (hash_table, key);
104
105   if (*node)
106     {
107       /* do not reset node->key in this place, keeping
108        * the old key might be intended.
109        * a g_hash_table_remove/g_hash_table_insert pair
110        * can be used otherwise.
111        *
112        * node->key = key; */
113       (*node)->value = value;
114     }
115   else
116     {
117       *node = g_hash_node_new (key, value);
118       hash_table->nnodes++;
119       if (!hash_table->frozen)
120         g_hash_table_resize (hash_table);
121     }
122 }
123
124 void
125 g_hash_table_remove (GHashTable      *hash_table,
126                      gconstpointer    key)
127 {
128   GHashNode **node, *dest;
129
130   g_return_if_fail (hash_table);
131
132   while (*(node = g_hash_table_lookup_node (hash_table, key)))
133     {
134       dest = *node;
135       (*node) = dest->next;
136       g_hash_node_destroy (dest);
137       hash_table->nnodes--;
138     }
139   if (!hash_table->frozen)
140     g_hash_table_resize (hash_table);
141 }
142
143 gpointer
144 g_hash_table_lookup (GHashTable   *hash_table,
145                      gconstpointer key)
146 {
147   GHashNode *node;
148
149   g_return_val_if_fail (hash_table, NULL);
150
151   node = *g_hash_table_lookup_node (hash_table, key);
152   return node ? node->value : NULL;
153 }
154
155 gboolean
156 g_hash_table_lookup_extended (GHashTable        *hash_table,
157                               gconstpointer      lookup_key,
158                               gpointer          *orig_key,
159                               gpointer          *value)
160 {
161   GHashNode *node;
162
163   g_return_val_if_fail (hash_table, FALSE);
164
165   node = *g_hash_table_lookup_node (hash_table, lookup_key);
166
167   if (node)
168     {
169       if (orig_key)
170         *orig_key = node->key;
171       if (value)
172         *value = node->value;
173       return TRUE;
174     }
175   else
176     return FALSE;
177 }
178
179 void
180 g_hash_table_freeze (GHashTable *hash_table)
181 {
182   g_return_if_fail (hash_table);
183
184   hash_table->frozen = TRUE;
185 }
186
187 void
188 g_hash_table_thaw (GHashTable *hash_table)
189 {
190   g_return_if_fail (hash_table);
191
192   hash_table->frozen = FALSE;
193
194   g_hash_table_resize (hash_table);
195 }
196
197 gint
198 g_hash_table_foreach_remove     (GHashTable     *hash_table,
199                                  GHRFunc         func,
200                                  gpointer        user_data)
201 {
202   gint deleted = 0, i;
203   GHashNode *node, *prev;
204
205   g_return_val_if_fail (hash_table && func, -1);
206
207   for (i = 0; i < hash_table->size; i++)
208     {
209     restart:
210
211       prev = NULL;
212
213       for (node = hash_table->nodes[i]; node; prev = node, node = node->next)
214         {
215           if ((* func) (node->key, node->value, user_data))
216             {
217               deleted += 1;
218
219               hash_table->nnodes -= 1;
220
221               if (prev)
222                 {
223                   prev->next = node->next;
224                   g_hash_node_destroy (node);
225                   node = prev;
226                 }
227               else
228                 {
229                   hash_table->nodes[i] = node->next;
230                   g_hash_node_destroy (node);
231                   goto restart;
232                 }
233             }
234         }
235     }
236
237   if (! hash_table->frozen)
238     g_hash_table_resize (hash_table);
239
240   return deleted;
241 }
242
243 void
244 g_hash_table_foreach (GHashTable *hash_table,
245                       GHFunc      func,
246                       gpointer    user_data)
247 {
248   GHashNode *node;
249   gint i;
250
251   g_return_if_fail (hash_table);
252
253   for (i = 0; i < hash_table->size; i++)
254     for (node = hash_table->nodes[i]; node; node = node->next)
255       (* func) (node->key, node->value, user_data);
256 }
257
258 /* Returns the number of elements contained in the hash table. */
259 gint g_hash_table_size (GHashTable *hash_table)
260 {
261   g_return_val_if_fail (hash_table, 0);
262
263   return hash_table->nnodes;
264 }
265
266 static void
267 g_hash_table_resize (GHashTable *hash_table)
268 {
269   GHashNode **new_nodes;
270   GHashNode *node;
271   GHashNode *next;
272   gfloat nodes_per_list;
273   guint hash_val;
274   gint new_size;
275   gint i;
276
277   g_return_if_fail (hash_table);
278
279   nodes_per_list = (gfloat) hash_table->nnodes / (gfloat) hash_table->size;
280
281   if ((nodes_per_list > 0.3 || hash_table->size <= HASH_TABLE_MIN_SIZE) &&
282       (nodes_per_list < 3.0 || hash_table->size >= HASH_TABLE_MAX_SIZE))
283     return;
284
285   new_size = CLAMP(g_spaced_primes_closest (hash_table->nnodes),
286                    HASH_TABLE_MIN_SIZE,
287                    HASH_TABLE_MAX_SIZE);
288   new_nodes = g_new (GHashNode*, new_size);
289
290   for (i = 0; i < new_size; i++)
291     new_nodes[i] = NULL;
292
293   for (i = 0; i < hash_table->size; i++)
294     for (node = hash_table->nodes[i]; node; node = next)
295       {
296         next = node->next;
297         hash_val = (* hash_table->hash_func) (node->key) % new_size;
298         node->next = new_nodes[hash_val];
299         new_nodes[hash_val] = node;
300       }
301
302   g_free (hash_table->nodes);
303   hash_table->nodes = new_nodes;
304   hash_table->size = new_size;
305 }
306
307 static GHashNode **
308 g_hash_table_lookup_node (GHashTable    *hash_table,
309                           gconstpointer  key)
310 {
311   GHashNode **node;
312
313   g_return_val_if_fail (hash_table, NULL);
314
315   node = &hash_table->nodes
316     [(* hash_table->hash_func) (key) % hash_table->size];
317
318   /* Hash table lookup needs to be fast.
319    *  We therefore remove the extra conditional of testing
320    *  whether to call the key_compare_func or not from
321    *  the inner loop.
322    */
323   if (hash_table->key_compare_func)
324     while (*node && !(*hash_table->key_compare_func) ((*node)->key, key))
325       node = &(*node)->next;
326   else
327     while (*node && (*node)->key != key)
328       node = &(*node)->next;
329
330   return node;
331 }
332
333 static GHashNode*
334 g_hash_node_new (gpointer key,
335                  gpointer value)
336 {
337   GHashNode *hash_node;
338
339   if (node_free_list)
340     {
341       hash_node = node_free_list;
342       node_free_list = node_free_list->next;
343     }
344   else
345     {
346       if (!node_mem_chunk)
347         node_mem_chunk = g_mem_chunk_new ("hash node mem chunk",
348                                           sizeof (GHashNode),
349                                           1024, G_ALLOC_ONLY);
350
351       hash_node = g_chunk_new (GHashNode, node_mem_chunk);
352     }
353
354   hash_node->key = key;
355   hash_node->value = value;
356   hash_node->next = NULL;
357
358   return hash_node;
359 }
360
361 static void
362 g_hash_node_destroy (GHashNode *hash_node)
363 {
364   g_return_if_fail (hash_node);
365
366   hash_node->next = node_free_list;
367   node_free_list = hash_node;
368 }
369
370 static void
371 g_hash_nodes_destroy (GHashNode *hash_node)
372 {
373   GHashNode *node;
374
375   if (!hash_node)
376     return;
377
378   node = hash_node;
379
380   while (node->next)
381     node = node->next;
382
383   node->next = node_free_list;
384   node_free_list = hash_node;
385 }