Typo in comment.
[platform/upstream/glib.git] / glib / 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 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.
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  * Lesser General Public License for more details.
13  *
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.
18  */
19
20 /*
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/. 
25  */
26
27 /* 
28  * MT safe
29  */
30
31 #include "config.h"
32
33 #include "glib.h"
34 #include "galias.h"
35
36
37 #define HASH_TABLE_MIN_SIZE 11
38 #define HASH_TABLE_MAX_SIZE 13845163
39
40
41 typedef struct _GHashNode      GHashNode;
42
43 struct _GHashNode
44 {
45   gpointer   key;
46   gpointer   value;
47   GHashNode *next;
48 };
49
50 struct _GHashTable
51 {
52   gint             size;
53   gint             nnodes;
54   GHashNode      **nodes;
55   GHashFunc        hash_func;
56   GEqualFunc       key_equal_func;
57   volatile guint   ref_count;
58   GDestroyNotify   key_destroy_func;
59   GDestroyNotify   value_destroy_func;
60 };
61
62 #define G_HASH_TABLE_RESIZE(hash_table)                         \
63    G_STMT_START {                                               \
64      if ((hash_table->size >= 3 * hash_table->nnodes &&         \
65           hash_table->size > HASH_TABLE_MIN_SIZE) ||            \
66          (3 * hash_table->size <= hash_table->nnodes &&         \
67           hash_table->size < HASH_TABLE_MAX_SIZE))              \
68            g_hash_table_resize (hash_table);                    \
69    } G_STMT_END
70
71 static void             g_hash_table_resize       (GHashTable     *hash_table);
72 static GHashNode**      g_hash_table_lookup_node  (GHashTable     *hash_table,
73                                                    gconstpointer   key);
74 static GHashNode*       g_hash_node_new           (gpointer        key,
75                                                    gpointer        value);
76 static void             g_hash_node_destroy       (GHashNode      *hash_node,
77                                                    GDestroyNotify  key_destroy_func,
78                                                    GDestroyNotify  value_destroy_func);
79 static void             g_hash_nodes_destroy      (GHashNode      *hash_node,
80                                                   GDestroyNotify   key_destroy_func,
81                                                   GDestroyNotify   value_destroy_func);
82 static guint g_hash_table_foreach_remove_or_steal (GHashTable     *hash_table,
83                                                    GHRFunc         func,
84                                                    gpointer        user_data,
85                                                    gboolean        notify);
86
87
88 /**
89  * g_hash_table_new:
90  * @hash_func: a function to create a hash value from a key.
91  *   Hash values are used to determine where keys are stored within the
92  *   #GHashTable data structure. The g_direct_hash(), g_int_hash() and 
93  *   g_str_hash() functions are provided for some common types of keys. 
94  *   If hash_func is %NULL, g_direct_hash() is used.
95  * @key_equal_func: a function to check two keys for equality.  This is
96  *   used when looking up keys in the #GHashTable.  The g_direct_equal(),
97  *   g_int_equal() and g_str_equal() functions are provided for the most
98  *   common types of keys. If @key_equal_func is %NULL, keys are compared
99  *   directly in a similar fashion to g_direct_equal(), but without the
100  *   overhead of a function call.
101  *
102  * Creates a new #GHashTable with a reference count of 1.
103  * 
104  * Return value: a new #GHashTable.
105  **/
106 GHashTable*
107 g_hash_table_new (GHashFunc    hash_func,
108                   GEqualFunc   key_equal_func)
109 {
110   return g_hash_table_new_full (hash_func, key_equal_func, NULL, NULL);
111 }
112
113
114 /**
115  * g_hash_table_new_full:
116  * @hash_func: a function to create a hash value from a key.
117  * @key_equal_func: a function to check two keys for equality.
118  * @key_destroy_func: a function to free the memory allocated for the key 
119  *   used when removing the entry from the #GHashTable or %NULL if you 
120  *   don't want to supply such a function.
121  * @value_destroy_func: a function to free the memory allocated for the 
122  *   value used when removing the entry from the #GHashTable or %NULL if 
123  *   you don't want to supply such a function.
124  * 
125  * Creates a new #GHashTable like g_hash_table_new() with a reference count
126  * of 1 and allows to specify functions to free the memory allocated for the
127  * key and value that get called when removing the entry from the #GHashTable.
128  * 
129  * Return value: a new #GHashTable.
130  **/
131 GHashTable*
132 g_hash_table_new_full (GHashFunc       hash_func,
133                        GEqualFunc      key_equal_func,
134                        GDestroyNotify  key_destroy_func,
135                        GDestroyNotify  value_destroy_func)
136 {
137   GHashTable *hash_table;
138   
139   hash_table = g_slice_new (GHashTable);
140   hash_table->size               = HASH_TABLE_MIN_SIZE;
141   hash_table->nnodes             = 0;
142   hash_table->hash_func          = hash_func ? hash_func : g_direct_hash;
143   hash_table->key_equal_func     = key_equal_func;
144   hash_table->ref_count          = 1;
145   hash_table->key_destroy_func   = key_destroy_func;
146   hash_table->value_destroy_func = value_destroy_func;
147   hash_table->nodes              = g_new0 (GHashNode*, hash_table->size);
148   
149   return hash_table;
150 }
151
152
153 /**
154  * g_hash_table_ref:
155  * @hash_table: a valid #GHashTable.
156  * 
157  * Atomically increments the reference count of @hash_table by one.
158  * This function is MT-safe and may be called from any thread.
159  * 
160  * Return value: the passed in #GHashTable.
161  * 
162  * Since: 2.10
163  **/
164 GHashTable*
165 g_hash_table_ref (GHashTable *hash_table)
166 {
167   g_return_val_if_fail (hash_table != NULL, NULL);
168   g_return_val_if_fail (hash_table->ref_count > 0, hash_table);
169
170   g_atomic_int_add (&hash_table->ref_count, 1);
171   return hash_table;
172 }
173
174 /**
175  * g_hash_table_unref:
176  * @hash_table: a valid #GHashTable.
177  * 
178  * Atomically decrements the reference count of @hash_table by one.
179  * If the reference count drops to 0, all keys and values will be
180  * destroyed, and all memory allocated by the hash table is released.
181  * This function is MT-safe and may be called from any thread.
182  * 
183  * Since: 2.10
184  **/
185 void
186 g_hash_table_unref (GHashTable *hash_table)
187 {
188   g_return_if_fail (hash_table != NULL);
189   g_return_if_fail (hash_table->ref_count > 0);
190
191   if (g_atomic_int_exchange_and_add (&hash_table->ref_count, -1) - 1 == 0)
192     {
193       guint i;
194       for (i = 0; i < hash_table->size; i++)
195         g_hash_nodes_destroy (hash_table->nodes[i], 
196                               hash_table->key_destroy_func,
197                               hash_table->value_destroy_func);
198       g_free (hash_table->nodes);
199       g_slice_free (GHashTable, hash_table);
200     }
201 }
202
203 /**
204  * g_hash_table_destroy:
205  * @hash_table: a #GHashTable.
206  * 
207  * Destroys all keys and values in the #GHashTable and decrements its
208  * reference count by 1. If keys and/or values are dynamically allocated,
209  * you should either free them first or create the #GHashTable with destroy
210  * notifiers using g_hash_table_new_full(). In the latter case the destroy
211  * functions you supplied will be called on all keys and values during the
212  * destruction phase.
213  **/
214 void
215 g_hash_table_destroy (GHashTable *hash_table)
216 {
217   guint i;
218   
219   g_return_if_fail (hash_table != NULL);
220   g_return_if_fail (hash_table->ref_count > 0);
221   
222   for (i = 0; i < hash_table->size; i++)
223     {
224       g_hash_nodes_destroy (hash_table->nodes[i], 
225                             hash_table->key_destroy_func,
226                             hash_table->value_destroy_func);
227       hash_table->nodes[i] = NULL;
228     }
229   hash_table->nnodes = 0;
230   hash_table->size = HASH_TABLE_MIN_SIZE;
231
232   g_hash_table_unref (hash_table);
233 }
234
235 static inline GHashNode**
236 g_hash_table_lookup_node (GHashTable    *hash_table,
237                           gconstpointer  key)
238 {
239   GHashNode **node;
240   
241   node = &hash_table->nodes
242     [(* hash_table->hash_func) (key) % hash_table->size];
243   
244   /* Hash table lookup needs to be fast.
245    *  We therefore remove the extra conditional of testing
246    *  whether to call the key_equal_func or not from
247    *  the inner loop.
248    */
249   if (hash_table->key_equal_func)
250     while (*node && !(*hash_table->key_equal_func) ((*node)->key, key))
251       node = &(*node)->next;
252   else
253     while (*node && (*node)->key != key)
254       node = &(*node)->next;
255   
256   return node;
257 }
258
259 /**
260  * g_hash_table_lookup:
261  * @hash_table: a #GHashTable.
262  * @key: the key to look up.
263  * 
264  * Looks up a key in a #GHashTable. Note that this function cannot
265  * distinguish between a key that is not present and one which is present
266  * and has the value %NULL. If you need this distinction, use
267  * g_hash_table_lookup_extended().
268  * 
269  * Return value: the associated value, or %NULL if the key is not found.
270  **/
271 gpointer
272 g_hash_table_lookup (GHashTable   *hash_table,
273                      gconstpointer key)
274 {
275   GHashNode *node;
276   
277   g_return_val_if_fail (hash_table != NULL, NULL);
278   
279   node = *g_hash_table_lookup_node (hash_table, key);
280   
281   return node ? node->value : NULL;
282 }
283
284 /**
285  * g_hash_table_lookup_extended:
286  * @hash_table: a #GHashTable.
287  * @lookup_key: the key to look up.
288  * @orig_key: returns the original key.
289  * @value: returns the value associated with the key.
290  * 
291  * Looks up a key in the #GHashTable, returning the original key and the
292  * associated value and a #gboolean which is %TRUE if the key was found. This 
293  * is useful if you need to free the memory allocated for the original key, 
294  * for example before calling g_hash_table_remove().
295  * 
296  * Return value: %TRUE if the key was found in the #GHashTable.
297  **/
298 gboolean
299 g_hash_table_lookup_extended (GHashTable    *hash_table,
300                               gconstpointer  lookup_key,
301                               gpointer      *orig_key,
302                               gpointer      *value)
303 {
304   GHashNode *node;
305   
306   g_return_val_if_fail (hash_table != NULL, FALSE);
307   
308   node = *g_hash_table_lookup_node (hash_table, lookup_key);
309   
310   if (node)
311     {
312       if (orig_key)
313         *orig_key = node->key;
314       if (value)
315         *value = node->value;
316       return TRUE;
317     }
318   else
319     return FALSE;
320 }
321
322 /**
323  * g_hash_table_insert:
324  * @hash_table: a #GHashTable.
325  * @key: a key to insert.
326  * @value: the value to associate with the key.
327  * 
328  * Inserts a new key and value into a #GHashTable.
329  * 
330  * If the key already exists in the #GHashTable its current value is replaced
331  * with the new value. If you supplied a @value_destroy_func when creating the 
332  * #GHashTable, the old value is freed using that function. If you supplied
333  * a @key_destroy_func when creating the #GHashTable, the passed key is freed 
334  * using that function.
335  **/
336 void
337 g_hash_table_insert (GHashTable *hash_table,
338                      gpointer    key,
339                      gpointer    value)
340 {
341   GHashNode **node;
342   
343   g_return_if_fail (hash_table != NULL);
344   g_return_if_fail (hash_table->ref_count > 0);
345   
346   node = g_hash_table_lookup_node (hash_table, key);
347   
348   if (*node)
349     {
350       /* do not reset node->key in this place, keeping
351        * the old key is the intended behaviour. 
352        * g_hash_table_replace() can be used instead.
353        */
354
355       /* free the passed key */
356       if (hash_table->key_destroy_func)
357         hash_table->key_destroy_func (key);
358       
359       if (hash_table->value_destroy_func)
360         hash_table->value_destroy_func ((*node)->value);
361
362       (*node)->value = value;
363     }
364   else
365     {
366       *node = g_hash_node_new (key, value);
367       hash_table->nnodes++;
368       G_HASH_TABLE_RESIZE (hash_table);
369     }
370 }
371
372 /**
373  * g_hash_table_replace:
374  * @hash_table: a #GHashTable.
375  * @key: a key to insert.
376  * @value: the value to associate with the key.
377  * 
378  * Inserts a new key and value into a #GHashTable similar to 
379  * g_hash_table_insert(). The difference is that if the key already exists 
380  * in the #GHashTable, it gets replaced by the new key. If you supplied a 
381  * @value_destroy_func when creating the #GHashTable, the old value is freed 
382  * using that function. If you supplied a @key_destroy_func when creating the 
383  * #GHashTable, the old key is freed using that function. 
384  **/
385 void
386 g_hash_table_replace (GHashTable *hash_table,
387                       gpointer    key,
388                       gpointer    value)
389 {
390   GHashNode **node;
391   
392   g_return_if_fail (hash_table != NULL);
393   g_return_if_fail (hash_table->ref_count > 0);
394   
395   node = g_hash_table_lookup_node (hash_table, key);
396   
397   if (*node)
398     {
399       if (hash_table->key_destroy_func)
400         hash_table->key_destroy_func ((*node)->key);
401       
402       if (hash_table->value_destroy_func)
403         hash_table->value_destroy_func ((*node)->value);
404
405       (*node)->key   = key;
406       (*node)->value = value;
407     }
408   else
409     {
410       *node = g_hash_node_new (key, value);
411       hash_table->nnodes++;
412       G_HASH_TABLE_RESIZE (hash_table);
413     }
414 }
415
416 /**
417  * g_hash_table_remove:
418  * @hash_table: a #GHashTable.
419  * @key: the key to remove.
420  * 
421  * Removes a key and its associated value from a #GHashTable.
422  *
423  * If the #GHashTable was created using g_hash_table_new_full(), the
424  * key and value are freed using the supplied destroy functions, otherwise
425  * you have to make sure that any dynamically allocated values are freed 
426  * yourself.
427  * 
428  * Return value: %TRUE if the key was found and removed from the #GHashTable.
429  **/
430 gboolean
431 g_hash_table_remove (GHashTable    *hash_table,
432                      gconstpointer  key)
433 {
434   GHashNode **node, *dest;
435   
436   g_return_val_if_fail (hash_table != NULL, FALSE);
437   
438   node = g_hash_table_lookup_node (hash_table, key);
439   if (*node)
440     {
441       dest = *node;
442       (*node) = dest->next;
443       g_hash_node_destroy (dest, 
444                            hash_table->key_destroy_func,
445                            hash_table->value_destroy_func);
446       hash_table->nnodes--;
447   
448       G_HASH_TABLE_RESIZE (hash_table);
449
450       return TRUE;
451     }
452
453   return FALSE;
454 }
455
456 /**
457  * g_hash_table_steal:
458  * @hash_table: a #GHashTable.
459  * @key: the key to remove.
460  * 
461  * Removes a key and its associated value from a #GHashTable without
462  * calling the key and value destroy functions.
463  *
464  * Return value: %TRUE if the key was found and removed from the #GHashTable.
465  **/
466 gboolean
467 g_hash_table_steal (GHashTable    *hash_table,
468                     gconstpointer  key)
469 {
470   GHashNode **node, *dest;
471   
472   g_return_val_if_fail (hash_table != NULL, FALSE);
473   
474   node = g_hash_table_lookup_node (hash_table, key);
475   if (*node)
476     {
477       dest = *node;
478       (*node) = dest->next;
479       g_hash_node_destroy (dest, NULL, NULL);
480       hash_table->nnodes--;
481   
482       G_HASH_TABLE_RESIZE (hash_table);
483
484       return TRUE;
485     }
486
487   return FALSE;
488 }
489
490 /**
491  * g_hash_table_foreach_remove:
492  * @hash_table: a #GHashTable.
493  * @func: the function to call for each key/value pair.
494  * @user_data: user data to pass to the function.
495  * 
496  * Calls the given function for each key/value pair in the #GHashTable.
497  * If the function returns %TRUE, then the key/value pair is removed from the
498  * #GHashTable. If you supplied key or value destroy functions when creating
499  * the #GHashTable, they are used to free the memory allocated for the removed
500  * keys and values.
501  * 
502  * Return value: the number of key/value pairs removed.
503  **/
504 guint
505 g_hash_table_foreach_remove (GHashTable *hash_table,
506                              GHRFunc     func,
507                              gpointer    user_data)
508 {
509   g_return_val_if_fail (hash_table != NULL, 0);
510   g_return_val_if_fail (func != NULL, 0);
511   
512   return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, TRUE);
513 }
514
515 /**
516  * g_hash_table_foreach_steal:
517  * @hash_table: a #GHashTable.
518  * @func: the function to call for each key/value pair.
519  * @user_data: user data to pass to the function.
520  * 
521  * Calls the given function for each key/value pair in the #GHashTable.
522  * If the function returns %TRUE, then the key/value pair is removed from the
523  * #GHashTable, but no key or value destroy functions are called.
524  * 
525  * Return value: the number of key/value pairs removed.
526  **/
527 guint
528 g_hash_table_foreach_steal (GHashTable *hash_table,
529                             GHRFunc     func,
530                             gpointer    user_data)
531 {
532   g_return_val_if_fail (hash_table != NULL, 0);
533   g_return_val_if_fail (func != NULL, 0);
534   
535   return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, FALSE);
536 }
537
538 static guint
539 g_hash_table_foreach_remove_or_steal (GHashTable *hash_table,
540                                       GHRFunc     func,
541                                       gpointer    user_data,
542                                       gboolean    notify)
543 {
544   GHashNode *node, *prev;
545   guint i;
546   guint deleted = 0;
547   
548   for (i = 0; i < hash_table->size; i++)
549     {
550     restart:
551       
552       prev = NULL;
553       
554       for (node = hash_table->nodes[i]; node; prev = node, node = node->next)
555         {
556           if ((* func) (node->key, node->value, user_data))
557             {
558               deleted += 1;
559               
560               hash_table->nnodes -= 1;
561               
562               if (prev)
563                 {
564                   prev->next = node->next;
565                   g_hash_node_destroy (node,
566                                        notify ? hash_table->key_destroy_func : NULL,
567                                        notify ? hash_table->value_destroy_func : NULL);
568                   node = prev;
569                 }
570               else
571                 {
572                   hash_table->nodes[i] = node->next;
573                   g_hash_node_destroy (node,
574                                        notify ? hash_table->key_destroy_func : NULL,
575                                        notify ? hash_table->value_destroy_func : NULL);
576                   goto restart;
577                 }
578             }
579         }
580     }
581   
582   G_HASH_TABLE_RESIZE (hash_table);
583   
584   return deleted;
585 }
586
587 /**
588  * g_hash_table_foreach:
589  * @hash_table: a #GHashTable.
590  * @func: the function to call for each key/value pair.
591  * @user_data: user data to pass to the function.
592  * 
593  * Calls the given function for each of the key/value pairs in the
594  * #GHashTable.  The function is passed the key and value of each
595  * pair, and the given @user_data parameter.  The hash table may not
596  * be modified while iterating over it (you can't add/remove
597  * items). To remove all items matching a predicate, use
598  * g_hash_table_foreach_remove().
599  **/
600 void
601 g_hash_table_foreach (GHashTable *hash_table,
602                       GHFunc      func,
603                       gpointer    user_data)
604 {
605   GHashNode *node;
606   gint i;
607   
608   g_return_if_fail (hash_table != NULL);
609   g_return_if_fail (func != NULL);
610   
611   for (i = 0; i < hash_table->size; i++)
612     for (node = hash_table->nodes[i]; node; node = node->next)
613       (* func) (node->key, node->value, user_data);
614 }
615
616 /**
617  * g_hash_table_find:
618  * @hash_table: a #GHashTable.
619  * @predicate:  function to test the key/value pairs for a certain property.
620  * @user_data:  user data to pass to the function.
621  * 
622  * Calls the given function for key/value pairs in the #GHashTable until 
623  * @predicate returns %TRUE.  The function is passed the key and value of 
624  * each pair, and the given @user_data parameter. The hash table may not
625  * be modified while iterating over it (you can't add/remove items). 
626  *
627  * Return value: The value of the first key/value pair is returned, for which 
628  * func evaluates to %TRUE. If no pair with the requested property is found, 
629  * %NULL is returned.
630  *
631  * Since: 2.4
632  **/
633 gpointer
634 g_hash_table_find (GHashTable      *hash_table,
635                    GHRFunc          predicate,
636                    gpointer         user_data)
637 {
638   GHashNode *node;
639   gint i;
640   
641   g_return_val_if_fail (hash_table != NULL, NULL);
642   g_return_val_if_fail (predicate != NULL, NULL);
643   
644   for (i = 0; i < hash_table->size; i++)
645     for (node = hash_table->nodes[i]; node; node = node->next)
646       if (predicate (node->key, node->value, user_data))
647         return node->value;       
648   return NULL;
649 }
650
651 /**
652  * g_hash_table_size:
653  * @hash_table: a #GHashTable.
654  * 
655  * Returns the number of elements contained in the #GHashTable.
656  * 
657  * Return value: the number of key/value pairs in the #GHashTable.
658  **/
659 guint
660 g_hash_table_size (GHashTable *hash_table)
661 {
662   g_return_val_if_fail (hash_table != NULL, 0);
663   
664   return hash_table->nnodes;
665 }
666
667 static void
668 g_hash_table_resize (GHashTable *hash_table)
669 {
670   GHashNode **new_nodes;
671   GHashNode *node;
672   GHashNode *next;
673   guint hash_val;
674   gint new_size;
675   gint i;
676
677   new_size = g_spaced_primes_closest (hash_table->nnodes);
678   new_size = CLAMP (new_size, HASH_TABLE_MIN_SIZE, HASH_TABLE_MAX_SIZE);
679  
680   new_nodes = g_new0 (GHashNode*, new_size);
681   
682   for (i = 0; i < hash_table->size; i++)
683     for (node = hash_table->nodes[i]; node; node = next)
684       {
685         next = node->next;
686
687         hash_val = (* hash_table->hash_func) (node->key) % new_size;
688
689         node->next = new_nodes[hash_val];
690         new_nodes[hash_val] = node;
691       }
692   
693   g_free (hash_table->nodes);
694   hash_table->nodes = new_nodes;
695   hash_table->size = new_size;
696 }
697
698 static GHashNode*
699 g_hash_node_new (gpointer key,
700                  gpointer value)
701 {
702   GHashNode *hash_node = g_slice_new (GHashNode);
703   
704   hash_node->key = key;
705   hash_node->value = value;
706   hash_node->next = NULL;
707   
708   return hash_node;
709 }
710
711 static void
712 g_hash_node_destroy (GHashNode      *hash_node,
713                      GDestroyNotify  key_destroy_func,
714                      GDestroyNotify  value_destroy_func)
715 {
716   if (key_destroy_func)
717     key_destroy_func (hash_node->key);
718   if (value_destroy_func)
719     value_destroy_func (hash_node->value);
720   
721 #ifdef ENABLE_GC_FRIENDLY
722   hash_node->key = NULL;
723   hash_node->value = NULL;
724 #endif /* ENABLE_GC_FRIENDLY */
725
726   g_slice_free (GHashNode, hash_node);
727 }
728
729 static void
730 g_hash_nodes_destroy (GHashNode *hash_node,
731                       GFreeFunc  key_destroy_func,
732                       GFreeFunc  value_destroy_func)
733 {
734   while (hash_node)
735     {
736       GHashNode *next = hash_node->next;
737       if (key_destroy_func)
738         key_destroy_func (hash_node->key);
739       if (value_destroy_func)
740         value_destroy_func (hash_node->value);
741       g_slice_free (GHashNode, hash_node);
742       hash_node = next;
743     }
744 }
745
746
747 #define __G_HASH_C__
748 #include "galiasdef.c"