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