ghash.c revision 00c2db4e4b992a4fa667d49289c55b9d5f3fcf04
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 41typedef struct _GHashNode GHashNode; 42 43struct _GHashNode 44{ 45 gpointer key; 46 gpointer value; 47 GHashNode *next; 48 guint key_hash; 49}; 50 51struct _GHashTable 52{ 53 gint size; 54 gint nnodes; 55 GHashNode **nodes; 56 GHashFunc hash_func; 57 GEqualFunc key_equal_func; 58 volatile gint ref_count; 59 GDestroyNotify key_destroy_func; 60 GDestroyNotify value_destroy_func; 61}; 62 63static void g_hash_table_resize (GHashTable *hash_table); 64static GHashNode** g_hash_table_lookup_node (GHashTable *hash_table, 65 gconstpointer key, 66 guint *hash_return); 67static GHashNode* g_hash_node_new (gpointer key, 68 gpointer value, 69 guint key_hash); 70static guint g_hash_table_foreach_remove_or_steal (GHashTable *hash_table, 71 GHRFunc func, 72 gpointer user_data, 73 gboolean notify); 74static void g_hash_table_remove_all_nodes (GHashTable *hash_table, 75 gboolean notify); 76 77static inline void 78g_hash_table_maybe_resize (GHashTable *hash_table) 79{ 80 gint nnodes = hash_table->nnodes; 81 gint size = hash_table->size; 82 83 if ((size >= 3 * nnodes && size > HASH_TABLE_MIN_SIZE) || 84 (3 * size <= nnodes && size < HASH_TABLE_MAX_SIZE)) 85 g_hash_table_resize (hash_table); 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 **/ 106GHashTable* 107g_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 **/ 131GHashTable* 132g_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 **/ 164GHashTable* 165g_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 **/ 185void 186g_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 g_hash_table_remove_all_nodes (hash_table, FALSE); 194 g_free (hash_table->nodes); 195 g_slice_free (GHashTable, hash_table); 196 } 197} 198 199/** 200 * g_hash_table_destroy: 201 * @hash_table: a #GHashTable. 202 * 203 * Destroys all keys and values in the #GHashTable and decrements its 204 * reference count by 1. If keys and/or values are dynamically allocated, 205 * you should either free them first or create the #GHashTable with destroy 206 * notifiers using g_hash_table_new_full(). In the latter case the destroy 207 * functions you supplied will be called on all keys and values during the 208 * destruction phase. 209 **/ 210void 211g_hash_table_destroy (GHashTable *hash_table) 212{ 213 g_return_if_fail (hash_table != NULL); 214 g_return_if_fail (hash_table->ref_count > 0); 215 216 g_hash_table_remove_all (hash_table); 217 g_hash_table_unref (hash_table); 218} 219 220static inline GHashNode** 221g_hash_table_lookup_node (GHashTable *hash_table, 222 gconstpointer key, 223 guint *hash_return) 224{ 225 GHashNode **node; 226 guint hash_value; 227 228 hash_value = (* hash_table->hash_func) (key); 229 node = &hash_table->nodes[hash_value % hash_table->size]; 230 231 if (hash_return) 232 *hash_return = hash_value; 233 234 /* Hash table lookup needs to be fast. 235 * We therefore remove the extra conditional of testing 236 * whether to call the key_equal_func or not from 237 * the inner loop. 238 * 239 * Additional optimisation: first check if our full hash 240 * values are equal so we can avoid calling the full-blown 241 * key equality function in most cases. 242 */ 243 if (hash_table->key_equal_func) 244 while (*node && (((*node)->key_hash != hash_value) || 245 !(*hash_table->key_equal_func) ((*node)->key, key))) 246 node = &(*node)->next; 247 else 248 while (*node && (*node)->key != key) 249 node = &(*node)->next; 250 251 return node; 252} 253 254/** 255 * g_hash_table_lookup: 256 * @hash_table: a #GHashTable. 257 * @key: the key to look up. 258 * 259 * Looks up a key in a #GHashTable. Note that this function cannot 260 * distinguish between a key that is not present and one which is present 261 * and has the value %NULL. If you need this distinction, use 262 * g_hash_table_lookup_extended(). 263 * 264 * Return value: the associated value, or %NULL if the key is not found. 265 **/ 266gpointer 267g_hash_table_lookup (GHashTable *hash_table, 268 gconstpointer key) 269{ 270 GHashNode *node; 271 272 g_return_val_if_fail (hash_table != NULL, NULL); 273 274 node = *g_hash_table_lookup_node (hash_table, key, NULL); 275 276 return node ? node->value : NULL; 277} 278 279/** 280 * g_hash_table_lookup_extended: 281 * @hash_table: a #GHashTable. 282 * @lookup_key: the key to look up. 283 * @orig_key: returns the original key. 284 * @value: returns the value associated with the key. 285 * 286 * Looks up a key in the #GHashTable, returning the original key and the 287 * associated value and a #gboolean which is %TRUE if the key was found. This 288 * is useful if you need to free the memory allocated for the original key, 289 * for example before calling g_hash_table_remove(). 290 * 291 * Return value: %TRUE if the key was found in the #GHashTable. 292 **/ 293gboolean 294g_hash_table_lookup_extended (GHashTable *hash_table, 295 gconstpointer lookup_key, 296 gpointer *orig_key, 297 gpointer *value) 298{ 299 GHashNode *node; 300 301 g_return_val_if_fail (hash_table != NULL, FALSE); 302 303 node = *g_hash_table_lookup_node (hash_table, lookup_key, NULL); 304 305 if (node) 306 { 307 if (orig_key) 308 *orig_key = node->key; 309 if (value) 310 *value = node->value; 311 return TRUE; 312 } 313 else 314 return FALSE; 315} 316 317static void 318g_hash_table_insert_internal (GHashTable *hash_table, 319 gpointer key, 320 gpointer value, 321 gboolean keep_new_key) 322{ 323 GHashNode **node; 324 guint key_hash; 325 326 g_return_if_fail (hash_table != NULL); 327 g_return_if_fail (hash_table->ref_count > 0); 328 329 node = g_hash_table_lookup_node (hash_table, key, &key_hash); 330 331 if (*node) 332 { 333 if (keep_new_key) 334 { 335 if (hash_table->key_destroy_func) 336 hash_table->key_destroy_func ((*node)->key); 337 (*node)->key = key; 338 } 339 else 340 { 341 if (hash_table->key_destroy_func) 342 hash_table->key_destroy_func (key); 343 } 344 345 if (hash_table->value_destroy_func) 346 hash_table->value_destroy_func ((*node)->value); 347 348 (*node)->value = value; 349 } 350 else 351 { 352 *node = g_hash_node_new (key, value, key_hash); 353 hash_table->nnodes++; 354 g_hash_table_maybe_resize (hash_table); 355 } 356} 357 358/** 359 * g_hash_table_insert: 360 * @hash_table: a #GHashTable. 361 * @key: a key to insert. 362 * @value: the value to associate with the key. 363 * 364 * Inserts a new key and value into a #GHashTable. 365 * 366 * If the key already exists in the #GHashTable its current value is replaced 367 * with the new value. If you supplied a @value_destroy_func when creating the 368 * #GHashTable, the old value is freed using that function. If you supplied 369 * a @key_destroy_func when creating the #GHashTable, the passed key is freed 370 * using that function. 371 **/ 372void 373g_hash_table_insert (GHashTable *hash_table, 374 gpointer key, 375 gpointer value) 376{ 377 return g_hash_table_insert_internal (hash_table, key, value, FALSE); 378} 379 380/** 381 * g_hash_table_replace: 382 * @hash_table: a #GHashTable. 383 * @key: a key to insert. 384 * @value: the value to associate with the key. 385 * 386 * Inserts a new key and value into a #GHashTable similar to 387 * g_hash_table_insert(). The difference is that if the key already exists 388 * in the #GHashTable, it gets replaced by the new key. If you supplied a 389 * @value_destroy_func when creating the #GHashTable, the old value is freed 390 * using that function. If you supplied a @key_destroy_func when creating the 391 * #GHashTable, the old key is freed using that function. 392 **/ 393void 394g_hash_table_replace (GHashTable *hash_table, 395 gpointer key, 396 gpointer value) 397{ 398 return g_hash_table_insert_internal (hash_table, key, value, TRUE); 399} 400 401static void 402g_hash_table_remove_node (GHashTable *hash_table, 403 GHashNode ***node_ptr_ptr, 404 gboolean notify) 405{ 406 GHashNode **node_ptr, *node; 407 408 node_ptr = *node_ptr_ptr; 409 node = *node_ptr; 410 411 *node_ptr = node->next; 412 413 if (notify && hash_table->key_destroy_func) 414 hash_table->key_destroy_func (node->key); 415 416 if (notify && hash_table->value_destroy_func) 417 hash_table->value_destroy_func (node->value); 418 419 g_slice_free (GHashNode, node); 420 421 hash_table->nnodes--; 422} 423 424static void 425g_hash_table_remove_all_nodes (GHashTable *hash_table, 426 gboolean notify) 427{ 428 GHashNode **node_ptr; 429 int i; 430 431 for (i = 0; i < hash_table->size; i++) 432 for (node_ptr = &hash_table->nodes[i]; *node_ptr != NULL;) 433 g_hash_table_remove_node (hash_table, &node_ptr, notify); 434 435 hash_table->nnodes = 0; 436} 437 438static gboolean 439g_hash_table_remove_internal (GHashTable *hash_table, 440 gconstpointer key, 441 gboolean notify) 442{ 443 GHashNode **node_ptr; 444 445 g_return_val_if_fail (hash_table != NULL, FALSE); 446 447 node_ptr = g_hash_table_lookup_node (hash_table, key, NULL); 448 if (*node_ptr == NULL) 449 return FALSE; 450 451 g_hash_table_remove_node (hash_table, &node_ptr, notify); 452 g_hash_table_maybe_resize (hash_table); 453 454 return TRUE; 455} 456 457/** 458 * g_hash_table_remove: 459 * @hash_table: a #GHashTable. 460 * @key: the key to remove. 461 * 462 * Removes a key and its associated value from a #GHashTable. 463 * 464 * If the #GHashTable was created using g_hash_table_new_full(), the 465 * key and value are freed using the supplied destroy functions, otherwise 466 * you have to make sure that any dynamically allocated values are freed 467 * yourself. 468 * 469 * Return value: %TRUE if the key was found and removed from the #GHashTable. 470 **/ 471gboolean 472g_hash_table_remove (GHashTable *hash_table, 473 gconstpointer key) 474{ 475 return g_hash_table_remove_internal (hash_table, key, TRUE); 476} 477 478/** 479 * g_hash_table_remove_all: 480 * @hash_table: a #GHashTable 481 * 482 * Removes all keys and their associated values from a #GHashTable. 483 * 484 * If the #GHashTable was created using g_hash_table_new_full(), the keys 485 * and values are freed using the supplied destroy functions, otherwise you 486 * have to make sure that any dynamically allocated values are freed 487 * yourself. 488 * 489 * Since: 2.12 490 **/ 491void 492g_hash_table_remove_all (GHashTable *hash_table) 493{ 494 g_return_if_fail (hash_table != NULL); 495 496 g_hash_table_remove_all_nodes (hash_table, TRUE); 497 g_hash_table_maybe_resize (hash_table); 498} 499 500/** 501 * g_hash_table_steal: 502 * @hash_table: a #GHashTable. 503 * @key: the key to remove. 504 * 505 * Removes a key and its associated value from a #GHashTable without 506 * calling the key and value destroy functions. 507 * 508 * Return value: %TRUE if the key was found and removed from the #GHashTable. 509 **/ 510gboolean 511g_hash_table_steal (GHashTable *hash_table, 512 gconstpointer key) 513{ 514 return g_hash_table_remove_internal (hash_table, key, FALSE); 515} 516 517/** 518 * g_hash_table_steal_all: 519 * @hash_table: a #GHashTable. 520 * 521 * Removes all keys and their associated values from a #GHashTable 522 * without calling the key and value destroy functions. 523 * 524 * Since: 2.12 525 **/ 526void 527g_hash_table_steal_all (GHashTable *hash_table) 528{ 529 g_return_if_fail (hash_table != NULL); 530 531 g_hash_table_remove_all_nodes (hash_table, FALSE); 532 g_hash_table_maybe_resize (hash_table); 533} 534 535/** 536 * g_hash_table_foreach_remove: 537 * @hash_table: a #GHashTable. 538 * @func: the function to call for each key/value pair. 539 * @user_data: user data to pass to the function. 540 * 541 * Calls the given function for each key/value pair in the #GHashTable. 542 * If the function returns %TRUE, then the key/value pair is removed from the 543 * #GHashTable. If you supplied key or value destroy functions when creating 544 * the #GHashTable, they are used to free the memory allocated for the removed 545 * keys and values. 546 * 547 * Return value: the number of key/value pairs removed. 548 **/ 549guint 550g_hash_table_foreach_remove (GHashTable *hash_table, 551 GHRFunc func, 552 gpointer user_data) 553{ 554 g_return_val_if_fail (hash_table != NULL, 0); 555 g_return_val_if_fail (func != NULL, 0); 556 557 return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, TRUE); 558} 559 560/** 561 * g_hash_table_foreach_steal: 562 * @hash_table: a #GHashTable. 563 * @func: the function to call for each key/value pair. 564 * @user_data: user data to pass to the function. 565 * 566 * Calls the given function for each key/value pair in the #GHashTable. 567 * If the function returns %TRUE, then the key/value pair is removed from the 568 * #GHashTable, but no key or value destroy functions are called. 569 * 570 * Return value: the number of key/value pairs removed. 571 **/ 572guint 573g_hash_table_foreach_steal (GHashTable *hash_table, 574 GHRFunc func, 575 gpointer user_data) 576{ 577 g_return_val_if_fail (hash_table != NULL, 0); 578 g_return_val_if_fail (func != NULL, 0); 579 580 return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, FALSE); 581} 582 583static guint 584g_hash_table_foreach_remove_or_steal (GHashTable *hash_table, 585 GHRFunc func, 586 gpointer user_data, 587 gboolean notify) 588{ 589 GHashNode *node, **node_ptr; 590 guint deleted = 0; 591 gint i; 592 593 for (i = 0; i < hash_table->size; i++) 594 for (node_ptr = &hash_table->nodes[i]; (node = *node_ptr) != NULL;) 595 if ((* func) (node->key, node->value, user_data)) 596 { 597 g_hash_table_remove_node (hash_table, &node_ptr, notify); 598 deleted++; 599 } 600 else 601 node_ptr = &node->next; 602 603 g_hash_table_maybe_resize (hash_table); 604 605 return deleted; 606} 607 608/** 609 * g_hash_table_foreach: 610 * @hash_table: a #GHashTable. 611 * @func: the function to call for each key/value pair. 612 * @user_data: user data to pass to the function. 613 * 614 * Calls the given function for each of the key/value pairs in the 615 * #GHashTable. The function is passed the key and value of each 616 * pair, and the given @user_data parameter. The hash table may not 617 * be modified while iterating over it (you can't add/remove 618 * items). To remove all items matching a predicate, use 619 * g_hash_table_foreach_remove(). 620 * 621 * See g_hash_table_find() for performance caveats for linear 622 * order searches in contrast to g_hash_table_lookup(). 623 **/ 624void 625g_hash_table_foreach (GHashTable *hash_table, 626 GHFunc func, 627 gpointer user_data) 628{ 629 GHashNode *node; 630 gint i; 631 632 g_return_if_fail (hash_table != NULL); 633 g_return_if_fail (func != NULL); 634 635 for (i = 0; i < hash_table->size; i++) 636 for (node = hash_table->nodes[i]; node; node = node->next) 637 (* func) (node->key, node->value, user_data); 638} 639 640/** 641 * g_hash_table_find: 642 * @hash_table: a #GHashTable. 643 * @predicate: function to test the key/value pairs for a certain property. 644 * @user_data: user data to pass to the function. 645 * 646 * Calls the given function for key/value pairs in the #GHashTable until 647 * @predicate returns %TRUE. The function is passed the key and value of 648 * each pair, and the given @user_data parameter. The hash table may not 649 * be modified while iterating over it (you can't add/remove items). 650 * 651 * Note, that hash tables are really only optimized for forward lookups, 652 * i.e. g_hash_table_lookup(). 653 * So code that frequently issues g_hash_table_find() or 654 * g_hash_table_foreach() (e.g. in the order of once per every entry in a 655 * hash table) should probably be reworked to use additional or different 656 * data structures for reverse lookups (keep in mind that an O(n) find/foreach 657 * operation issued for all n values in a hash table ends up needing O(n*n) 658 * operations). 659 * 660 * Return value: The value of the first key/value pair is returned, for which 661 * func evaluates to %TRUE. If no pair with the requested property is found, 662 * %NULL is returned. 663 * 664 * Since: 2.4 665 **/ 666gpointer 667g_hash_table_find (GHashTable *hash_table, 668 GHRFunc predicate, 669 gpointer user_data) 670{ 671 GHashNode *node; 672 gint i; 673 674 g_return_val_if_fail (hash_table != NULL, NULL); 675 g_return_val_if_fail (predicate != NULL, NULL); 676 677 for (i = 0; i < hash_table->size; i++) 678 for (node = hash_table->nodes[i]; node; node = node->next) 679 if (predicate (node->key, node->value, user_data)) 680 return node->value; 681 return NULL; 682} 683 684/** 685 * g_hash_table_size: 686 * @hash_table: a #GHashTable. 687 * 688 * Returns the number of elements contained in the #GHashTable. 689 * 690 * Return value: the number of key/value pairs in the #GHashTable. 691 **/ 692guint 693g_hash_table_size (GHashTable *hash_table) 694{ 695 g_return_val_if_fail (hash_table != NULL, 0); 696 697 return hash_table->nnodes; 698} 699 700/** 701 * g_hash_table_get_keys: 702 * @hash_table: a #GHashTable 703 * 704 * Retrieves every key inside @hash_table. The returned data is valid 705 * until @hash_table is modified. 706 * 707 * Return value: a #GList containing all the keys inside the hash 708 * table. The content of the list is owned by the hash table and 709 * should not be modified or freed. Use g_list_free() when done 710 * using the list. 711 * 712 * Since: 2.14 713 */ 714GList * 715g_hash_table_get_keys (GHashTable *hash_table) 716{ 717 GHashNode *node; 718 gint i; 719 GList *retval; 720 721 g_return_val_if_fail (hash_table != NULL, NULL); 722 723 retval = NULL; 724 for (i = 0; i < hash_table->size; i++) 725 for (node = hash_table->nodes[i]; node; node = node->next) 726 retval = g_list_prepend (retval, node->key); 727 728 return retval; 729} 730 731/** 732 * g_hash_table_get_values: 733 * @hash_table: a #GHashTable 734 * 735 * Retrieves every value inside @hash_table. The returned data is 736 * valid until @hash_table is modified. 737 * 738 * Return value: a #GList containing all the values inside the hash 739 * table. The content of the list is owned by the hash table and 740 * should not be modified or freed. Use g_list_free() when done 741 * using the list. 742 * 743 * Since: 2.14 744 */ 745GList * 746g_hash_table_get_values (GHashTable *hash_table) 747{ 748 GHashNode *node; 749 gint i; 750 GList *retval; 751 752 g_return_val_if_fail (hash_table != NULL, NULL); 753 754 retval = NULL; 755 for (i = 0; i < hash_table->size; i++) 756 for (node = hash_table->nodes[i]; node; node = node->next) 757 retval = g_list_prepend (retval, node->value); 758 759 return retval; 760} 761 762static void 763g_hash_table_resize (GHashTable *hash_table) 764{ 765 GHashNode **new_nodes; 766 GHashNode *node; 767 GHashNode *next; 768 guint hash_val; 769 gint new_size; 770 gint i; 771 772 new_size = g_spaced_primes_closest (hash_table->nnodes); 773 new_size = CLAMP (new_size, HASH_TABLE_MIN_SIZE, HASH_TABLE_MAX_SIZE); 774 775 new_nodes = g_new0 (GHashNode*, new_size); 776 777 for (i = 0; i < hash_table->size; i++) 778 for (node = hash_table->nodes[i]; node; node = next) 779 { 780 next = node->next; 781 782 hash_val = node->key_hash % new_size; 783 784 node->next = new_nodes[hash_val]; 785 new_nodes[hash_val] = node; 786 } 787 788 g_free (hash_table->nodes); 789 hash_table->nodes = new_nodes; 790 hash_table->size = new_size; 791} 792 793static GHashNode* 794g_hash_node_new (gpointer key, 795 gpointer value, 796 guint key_hash) 797{ 798 GHashNode *hash_node = g_slice_new (GHashNode); 799 800 hash_node->key = key; 801 hash_node->value = value; 802 hash_node->key_hash = key_hash; 803 hash_node->next = NULL; 804 805 return hash_node; 806} 807 808#define __G_HASH_C__ 809#include "galiasdef.c" 810