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 <string.h> /* memset */ 34 35 #include "glib.h" 36 #include "galias.h" 37 38 #define HASH_TABLE_MIN_SHIFT 3 /* 1 << 3 == 8 buckets */ 39 40 typedef struct _GHashNode GHashNode; 41 42 struct _GHashNode 43 { 44 gpointer key; 45 gpointer value; 46 47 /* If key_hash == 0, node is not in use 48 * If key_hash == 1, node is a tombstone 49 * If key_hash >= 2, node contains data */ 50 guint key_hash; 51 }; 52 53 struct _GHashTable 54 { 55 gint size; 56 gint mod; 57 guint mask; 58 gint nnodes; 59 gint noccupied; /* nnodes + tombstones */ 60 GHashNode *nodes; 61 GHashFunc hash_func; 62 GEqualFunc key_equal_func; 63 volatile gint ref_count; 64 #ifndef G_DISABLE_ASSERT 65 /* 66 * Tracks the structure of the hash table, not its contents: is only 67 * incremented when a node is added or removed (is not incremented 68 * when the key or data of a node is modified). 69 */ 70 int version; 71 #endif 72 GDestroyNotify key_destroy_func; 73 GDestroyNotify value_destroy_func; 74 }; 75 76 typedef struct 77 { 78 GHashTable *hash_table; 79 gpointer dummy1; 80 gpointer dummy2; 81 int position; 82 gboolean dummy3; 83 int version; 84 } RealIter; 85 86 /* Each table size has an associated prime modulo (the first prime 87 * lower than the table size) used to find the initial bucket. Probing 88 * then works modulo 2^n. The prime modulo is necessary to get a 89 * good distribution with poor hash functions. */ 90 static const gint prime_mod [] = 91 { 92 1, /* For 1 << 0 */ 93 2, 94 3, 95 7, 96 13, 97 31, 98 61, 99 127, 100 251, 101 509, 102 1021, 103 2039, 104 4093, 105 8191, 106 16381, 107 32749, 108 65521, /* For 1 << 16 */ 109 131071, 110 262139, 111 524287, 112 1048573, 113 2097143, 114 4194301, 115 8388593, 116 16777213, 117 33554393, 118 67108859, 119 134217689, 120 268435399, 121 536870909, 122 1073741789, 123 2147483647 /* For 1 << 31 */ 124 }; 125 126 static void 127 g_hash_table_set_shift (GHashTable *hash_table, gint shift) 128 { 129 gint i; 130 guint mask = 0; 131 132 hash_table->size = 1 << shift; 133 hash_table->mod = prime_mod [shift]; 134 135 for (i = 0; i < shift; i++) 136 { 137 mask <<= 1; 138 mask |= 1; 139 } 140 141 hash_table->mask = mask; 142 } 143 144 static gint 145 g_hash_table_find_closest_shift (gint n) 146 { 147 gint i; 148 149 for (i = 0; n; i++) 150 n >>= 1; 151 152 return i; 153 } 154 155 static void 156 g_hash_table_set_shift_from_size (GHashTable *hash_table, gint size) 157 { 158 gint shift; 159 160 shift = g_hash_table_find_closest_shift (size); 161 shift = MAX (shift, HASH_TABLE_MIN_SHIFT); 162 163 g_hash_table_set_shift (hash_table, shift); 164 } 165 166 /* 167 * g_hash_table_lookup_node: 168 * @hash_table: our #GHashTable 169 * @key: the key to lookup against 170 * @hash_return: optional key hash return location 171 * Return value: index of the described #GHashNode 172 * 173 * Performs a lookup in the hash table. Virtually all hash operations 174 * will use this function internally. 175 * 176 * This function first computes the hash value of the key using the 177 * user's hash function. 178 * 179 * If an entry in the table matching @key is found then this function 180 * returns the index of that entry in the table, and if not, the 181 * index of an empty node (never a tombstone). 182 */ 183 static inline guint 184 g_hash_table_lookup_node (GHashTable *hash_table, 185 gconstpointer key) 186 { 187 GHashNode *node; 188 guint node_index; 189 guint hash_value; 190 guint step = 0; 191 192 /* Empty buckets have hash_value set to 0, and for tombstones, it's 1. 193 * We need to make sure our hash value is not one of these. */ 194 195 hash_value = (* hash_table->hash_func) (key); 196 if (G_UNLIKELY (hash_value <= 1)) 197 hash_value = 2; 198 199 node_index = hash_value % hash_table->mod; 200 node = &hash_table->nodes [node_index]; 201 202 while (node->key_hash) 203 { 204 /* We first check if our full hash values 205 * are equal so we can avoid calling the full-blown 206 * key equality function in most cases. 207 */ 208 209 if (node->key_hash == hash_value) 210 { 211 if (hash_table->key_equal_func) 212 { 213 if (hash_table->key_equal_func (node->key, key)) 214 break; 215 } 216 else if (node->key == key) 217 { 218 break; 219 } 220 } 221 222 step++; 223 node_index += step; 224 node_index &= hash_table->mask; 225 node = &hash_table->nodes [node_index]; 226 } 227 228 return node_index; 229 } 230 231 /* 232 * g_hash_table_lookup_node_for_insertion: 233 * @hash_table: our #GHashTable 234 * @key: the key to lookup against 235 * @hash_return: key hash return location 236 * Return value: index of the described #GHashNode 237 * 238 * Performs a lookup in the hash table, preserving extra information 239 * usually needed for insertion. 240 * 241 * This function first computes the hash value of the key using the 242 * user's hash function. 243 * 244 * If an entry in the table matching @key is found then this function 245 * returns the index of that entry in the table, and if not, the 246 * index of an unused node (empty or tombstone) where the key can be 247 * inserted. 248 * 249 * The computed hash value is returned in the variable pointed to 250 * by @hash_return. This is to save insertions from having to compute 251 * the hash record again for the new record. 252 */ 253 static inline guint 254 g_hash_table_lookup_node_for_insertion (GHashTable *hash_table, 255 gconstpointer key, 256 guint *hash_return) 257 { 258 GHashNode *node; 259 guint node_index; 260 guint hash_value; 261 guint first_tombstone; 262 gboolean have_tombstone = FALSE; 263 guint step = 0; 264 265 /* Empty buckets have hash_value set to 0, and for tombstones, it's 1. 266 * We need to make sure our hash value is not one of these. */ 267 268 hash_value = (* hash_table->hash_func) (key); 269 if (G_UNLIKELY (hash_value <= 1)) 270 hash_value = 2; 271 272 *hash_return = hash_value; 273 274 node_index = hash_value % hash_table->mod; 275 node = &hash_table->nodes [node_index]; 276 277 while (node->key_hash) 278 { 279 /* We first check if our full hash values 280 * are equal so we can avoid calling the full-blown 281 * key equality function in most cases. 282 */ 283 284 if (node->key_hash == hash_value) 285 { 286 if (hash_table->key_equal_func) 287 { 288 if (hash_table->key_equal_func (node->key, key)) 289 return node_index; 290 } 291 else if (node->key == key) 292 { 293 return node_index; 294 } 295 } 296 else if (node->key_hash == 1 && !have_tombstone) 297 { 298 first_tombstone = node_index; 299 have_tombstone = TRUE; 300 } 301 302 step++; 303 node_index += step; 304 node_index &= hash_table->mask; 305 node = &hash_table->nodes [node_index]; 306 } 307 308 if (have_tombstone) 309 return first_tombstone; 310 311 return node_index; 312 } 313 314 /* 315 * g_hash_table_remove_node: 316 * @hash_table: our #GHashTable 317 * @node: pointer to node to remove 318 * @notify: %TRUE if the destroy notify handlers are to be called 319 * 320 * Removes a node from the hash table and updates the node count. 321 * The node is replaced by a tombstone. No table resize is performed. 322 * 323 * If @notify is %TRUE then the destroy notify functions are called 324 * for the key and value of the hash node. 325 */ 326 static void 327 g_hash_table_remove_node (GHashTable *hash_table, 328 GHashNode *node, 329 gboolean notify) 330 { 331 if (notify && hash_table->key_destroy_func) 332 hash_table->key_destroy_func (node->key); 333 334 if (notify && hash_table->value_destroy_func) 335 hash_table->value_destroy_func (node->value); 336 337 /* Erect tombstone */ 338 node->key_hash = 1; 339 340 /* Be GC friendly */ 341 node->key = NULL; 342 node->value = NULL; 343 344 hash_table->nnodes--; 345 } 346 347 /* 348 * g_hash_table_remove_all_nodes: 349 * @hash_table: our #GHashTable 350 * @notify: %TRUE if the destroy notify handlers are to be called 351 * 352 * Removes all nodes from the table. Since this may be a precursor to 353 * freeing the table entirely, no resize is performed. 354 * 355 * If @notify is %TRUE then the destroy notify functions are called 356 * for the key and value of the hash node. 357 */ 358 static void 359 g_hash_table_remove_all_nodes (GHashTable *hash_table, 360 gboolean notify) 361 { 362 int i; 363 364 for (i = 0; i < hash_table->size; i++) 365 { 366 GHashNode *node = &hash_table->nodes [i]; 367 368 if (node->key_hash > 1) 369 { 370 if (notify && hash_table->key_destroy_func) 371 hash_table->key_destroy_func (node->key); 372 373 if (notify && hash_table->value_destroy_func) 374 hash_table->value_destroy_func (node->value); 375 } 376 } 377 378 /* We need to set node->key_hash = 0 for all nodes - might as well be GC 379 * friendly and clear everything */ 380 memset (hash_table->nodes, 0, hash_table->size * sizeof (GHashNode)); 381 382 hash_table->nnodes = 0; 383 hash_table->noccupied = 0; 384 } 385 386 /* 387 * g_hash_table_resize: 388 * @hash_table: our #GHashTable 389 * 390 * Resizes the hash table to the optimal size based on the number of 391 * nodes currently held. If you call this function then a resize will 392 * occur, even if one does not need to occur. Use 393 * g_hash_table_maybe_resize() instead. 394 * 395 * This function may "resize" the hash table to its current size, with 396 * the side effect of cleaning up tombstones and otherwise optimizing 397 * the probe sequences. 398 */ 399 static void 400 g_hash_table_resize (GHashTable *hash_table) 401 { 402 GHashNode *new_nodes; 403 gint old_size; 404 gint i; 405 406 old_size = hash_table->size; 407 g_hash_table_set_shift_from_size (hash_table, hash_table->nnodes * 2); 408 409 new_nodes = g_new0 (GHashNode, hash_table->size); 410 411 for (i = 0; i < old_size; i++) 412 { 413 GHashNode *node = &hash_table->nodes [i]; 414 GHashNode *new_node; 415 guint hash_val; 416 guint step = 0; 417 418 if (node->key_hash <= 1) 419 continue; 420 421 hash_val = node->key_hash % hash_table->mod; 422 new_node = &new_nodes [hash_val]; 423 424 while (new_node->key_hash) 425 { 426 step++; 427 hash_val += step; 428 hash_val &= hash_table->mask; 429 new_node = &new_nodes [hash_val]; 430 } 431 432 *new_node = *node; 433 } 434 435 g_free (hash_table->nodes); 436 hash_table->nodes = new_nodes; 437 hash_table->noccupied = hash_table->nnodes; 438 } 439 440 /* 441 * g_hash_table_maybe_resize: 442 * @hash_table: our #GHashTable 443 * 444 * Resizes the hash table, if needed. 445 * 446 * Essentially, calls g_hash_table_resize() if the table has strayed 447 * too far from its ideal size for its number of nodes. 448 */ 449 static inline void 450 g_hash_table_maybe_resize (GHashTable *hash_table) 451 { 452 gint noccupied = hash_table->noccupied; 453 gint size = hash_table->size; 454 455 if ((size > hash_table->nnodes * 4 && size > 1 << HASH_TABLE_MIN_SHIFT) || 456 (size <= noccupied + (noccupied / 16))) 457 g_hash_table_resize (hash_table); 458 } 459 460 /** 461 * g_hash_table_new: 462 * @hash_func: a function to create a hash value from a key. 463 * Hash values are used to determine where keys are stored within the 464 * #GHashTable data structure. The g_direct_hash(), g_int_hash() and 465 * g_str_hash() functions are provided for some common types of keys. 466 * If hash_func is %NULL, g_direct_hash() is used. 467 * @key_equal_func: a function to check two keys for equality. This is 468 * used when looking up keys in the #GHashTable. The g_direct_equal(), 469 * g_int_equal() and g_str_equal() functions are provided for the most 470 * common types of keys. If @key_equal_func is %NULL, keys are compared 471 * directly in a similar fashion to g_direct_equal(), but without the 472 * overhead of a function call. 473 * 474 * Creates a new #GHashTable with a reference count of 1. 475 * 476 * Return value: a new #GHashTable. 477 **/ 478 GHashTable* 479 g_hash_table_new (GHashFunc hash_func, 480 GEqualFunc key_equal_func) 481 { 482 return g_hash_table_new_full (hash_func, key_equal_func, NULL, NULL); 483 } 484 485 486 /** 487 * g_hash_table_new_full: 488 * @hash_func: a function to create a hash value from a key. 489 * @key_equal_func: a function to check two keys for equality. 490 * @key_destroy_func: a function to free the memory allocated for the key 491 * used when removing the entry from the #GHashTable or %NULL if you 492 * don't want to supply such a function. 493 * @value_destroy_func: a function to free the memory allocated for the 494 * value used when removing the entry from the #GHashTable or %NULL if 495 * you don't want to supply such a function. 496 * 497 * Creates a new #GHashTable like g_hash_table_new() with a reference count 498 * of 1 and allows to specify functions to free the memory allocated for the 499 * key and value that get called when removing the entry from the #GHashTable. 500 * 501 * Return value: a new #GHashTable. 502 **/ 503 GHashTable* 504 g_hash_table_new_full (GHashFunc hash_func, 505 GEqualFunc key_equal_func, 506 GDestroyNotify key_destroy_func, 507 GDestroyNotify value_destroy_func) 508 { 509 GHashTable *hash_table; 510 511 hash_table = g_slice_new (GHashTable); 512 g_hash_table_set_shift (hash_table, HASH_TABLE_MIN_SHIFT); 513 hash_table->nnodes = 0; 514 hash_table->noccupied = 0; 515 hash_table->hash_func = hash_func ? hash_func : g_direct_hash; 516 hash_table->key_equal_func = key_equal_func; 517 hash_table->ref_count = 1; 518 #ifndef G_DISABLE_ASSERT 519 hash_table->version = 0; 520 #endif 521 hash_table->key_destroy_func = key_destroy_func; 522 hash_table->value_destroy_func = value_destroy_func; 523 hash_table->nodes = g_new0 (GHashNode, hash_table->size); 524 525 return hash_table; 526 } 527 528 /** 529 * g_hash_table_iter_init: 530 * @iter: an uninitialized #GHashTableIter. 531 * @hash_table: a #GHashTable. 532 * 533 * Initializes a key/value pair iterator and associates it with 534 * @hash_table. Modifying the hash table after calling this function 535 * invalidates the returned iterator. 536 * |[ 537 * GHashTableIter iter; 538 * gpointer key, value; 539 * 540 * g_hash_table_iter_init (&iter, hash_table); 541 * while (g_hash_table_iter_next (&iter, &key, &value)) 542 * { 543 * /* do something with key and value */ 544 * } 545 * ]| 546 * 547 * Since: 2.16 548 **/ 549 void 550 g_hash_table_iter_init (GHashTableIter *iter, 551 GHashTable *hash_table) 552 { 553 RealIter *ri = (RealIter *) iter; 554 555 g_return_if_fail (iter != NULL); 556 g_return_if_fail (hash_table != NULL); 557 558 ri->hash_table = hash_table; 559 ri->position = -1; 560 #ifndef G_DISABLE_ASSERT 561 ri->version = hash_table->version; 562 #endif 563 } 564 565 /** 566 * g_hash_table_iter_next: 567 * @iter: an initialized #GHashTableIter. 568 * @key: a location to store the key, or %NULL. 569 * @value: a location to store the value, or %NULL. 570 * 571 * Advances @iter and retrieves the key and/or value that are now 572 * pointed to as a result of this advancement. If %FALSE is returned, 573 * @key and @value are not set, and the iterator becomes invalid. 574 * 575 * Return value: %FALSE if the end of the #GHashTable has been reached. 576 * 577 * Since: 2.16 578 **/ 579 gboolean 580 g_hash_table_iter_next (GHashTableIter *iter, 581 gpointer *key, 582 gpointer *value) 583 { 584 RealIter *ri = (RealIter *) iter; 585 GHashNode *node; 586 gint position; 587 588 g_return_val_if_fail (iter != NULL, FALSE); 589 #ifndef G_DISABLE_ASSERT 590 g_return_val_if_fail (ri->version == ri->hash_table->version, FALSE); 591 #endif 592 g_return_val_if_fail (ri->position < ri->hash_table->size, FALSE); 593 594 position = ri->position; 595 596 do 597 { 598 position++; 599 if (position >= ri->hash_table->size) 600 { 601 ri->position = position; 602 return FALSE; 603 } 604 605 node = &ri->hash_table->nodes [position]; 606 } 607 while (node->key_hash <= 1); 608 609 if (key != NULL) 610 *key = node->key; 611 if (value != NULL) 612 *value = node->value; 613 614 ri->position = position; 615 return TRUE; 616 } 617 618 /** 619 * g_hash_table_iter_get_hash_table: 620 * @iter: an initialized #GHashTableIter. 621 * 622 * Returns the #GHashTable associated with @iter. 623 * 624 * Return value: the #GHashTable associated with @iter. 625 * 626 * Since: 2.16 627 **/ 628 GHashTable * 629 g_hash_table_iter_get_hash_table (GHashTableIter *iter) 630 { 631 g_return_val_if_fail (iter != NULL, NULL); 632 633 return ((RealIter *) iter)->hash_table; 634 } 635 636 static void 637 iter_remove_or_steal (RealIter *ri, gboolean notify) 638 { 639 g_return_if_fail (ri != NULL); 640 #ifndef G_DISABLE_ASSERT 641 g_return_if_fail (ri->version == ri->hash_table->version); 642 #endif 643 g_return_if_fail (ri->position >= 0); 644 g_return_if_fail (ri->position < ri->hash_table->size); 645 646 g_hash_table_remove_node (ri->hash_table, &ri->hash_table->nodes [ri->position], notify); 647 648 #ifndef G_DISABLE_ASSERT 649 ri->version++; 650 ri->hash_table->version++; 651 #endif 652 } 653 654 /** 655 * g_hash_table_iter_remove(): 656 * @iter: an initialized #GHashTableIter. 657 * 658 * Removes the key/value pair currently pointed to by the iterator 659 * from its associated #GHashTable. Can only be called after 660 * g_hash_table_iter_next() returned %TRUE, and cannot be called more 661 * than once for the same key/value pair. 662 * 663 * If the #GHashTable was created using g_hash_table_new_full(), the 664 * key and value are freed using the supplied destroy functions, otherwise 665 * you have to make sure that any dynamically allocated values are freed 666 * yourself. 667 * 668 * Since: 2.16 669 **/ 670 void 671 g_hash_table_iter_remove (GHashTableIter *iter) 672 { 673 iter_remove_or_steal ((RealIter *) iter, TRUE); 674 } 675 676 /** 677 * g_hash_table_iter_steal(): 678 * @iter: an initialized #GHashTableIter. 679 * 680 * Removes the key/value pair currently pointed to by the iterator 681 * from its associated #GHashTable, without calling the key and value 682 * destroy functions. Can only be called after 683 * g_hash_table_iter_next() returned %TRUE, and cannot be called more 684 * than once for the same key/value pair. 685 * 686 * Since: 2.16 687 **/ 688 void 689 g_hash_table_iter_steal (GHashTableIter *iter) 690 { 691 iter_remove_or_steal ((RealIter *) iter, FALSE); 692 } 693 694 695 /** 696 * g_hash_table_ref: 697 * @hash_table: a valid #GHashTable. 698 * 699 * Atomically increments the reference count of @hash_table by one. 700 * This function is MT-safe and may be called from any thread. 701 * 702 * Return value: the passed in #GHashTable. 703 * 704 * Since: 2.10 705 **/ 706 GHashTable* 707 g_hash_table_ref (GHashTable *hash_table) 708 { 709 g_return_val_if_fail (hash_table != NULL, NULL); 710 g_return_val_if_fail (hash_table->ref_count > 0, hash_table); 711 712 g_atomic_int_add (&hash_table->ref_count, 1); 713 return hash_table; 714 } 715 716 /** 717 * g_hash_table_unref: 718 * @hash_table: a valid #GHashTable. 719 * 720 * Atomically decrements the reference count of @hash_table by one. 721 * If the reference count drops to 0, all keys and values will be 722 * destroyed, and all memory allocated by the hash table is released. 723 * This function is MT-safe and may be called from any thread. 724 * 725 * Since: 2.10 726 **/ 727 void 728 g_hash_table_unref (GHashTable *hash_table) 729 { 730 g_return_if_fail (hash_table != NULL); 731 g_return_if_fail (hash_table->ref_count > 0); 732 733 if (g_atomic_int_exchange_and_add (&hash_table->ref_count, -1) - 1 == 0) 734 { 735 g_hash_table_remove_all_nodes (hash_table, TRUE); 736 g_free (hash_table->nodes); 737 g_slice_free (GHashTable, hash_table); 738 } 739 } 740 741 /** 742 * g_hash_table_destroy: 743 * @hash_table: a #GHashTable. 744 * 745 * Destroys all keys and values in the #GHashTable and decrements its 746 * reference count by 1. If keys and/or values are dynamically allocated, 747 * you should either free them first or create the #GHashTable with destroy 748 * notifiers using g_hash_table_new_full(). In the latter case the destroy 749 * functions you supplied will be called on all keys and values during the 750 * destruction phase. 751 **/ 752 void 753 g_hash_table_destroy (GHashTable *hash_table) 754 { 755 g_return_if_fail (hash_table != NULL); 756 g_return_if_fail (hash_table->ref_count > 0); 757 758 g_hash_table_remove_all (hash_table); 759 g_hash_table_unref (hash_table); 760 } 761 762 /** 763 * g_hash_table_lookup: 764 * @hash_table: a #GHashTable. 765 * @key: the key to look up. 766 * 767 * Looks up a key in a #GHashTable. Note that this function cannot 768 * distinguish between a key that is not present and one which is present 769 * and has the value %NULL. If you need this distinction, use 770 * g_hash_table_lookup_extended(). 771 * 772 * Return value: the associated value, or %NULL if the key is not found. 773 **/ 774 gpointer 775 g_hash_table_lookup (GHashTable *hash_table, 776 gconstpointer key) 777 { 778 GHashNode *node; 779 guint node_index; 780 781 g_return_val_if_fail (hash_table != NULL, NULL); 782 783 node_index = g_hash_table_lookup_node (hash_table, key); 784 node = &hash_table->nodes [node_index]; 785 786 return node->key_hash ? node->value : NULL; 787 } 788 789 /** 790 * g_hash_table_lookup_extended: 791 * @hash_table: a #GHashTable 792 * @lookup_key: the key to look up 793 * @orig_key: return location for the original key, or %NULL 794 * @value: return location for the value associated with the key, or %NULL 795 * 796 * Looks up a key in the #GHashTable, returning the original key and the 797 * associated value and a #gboolean which is %TRUE if the key was found. This 798 * is useful if you need to free the memory allocated for the original key, 799 * for example before calling g_hash_table_remove(). 800 * 801 * You can actually pass %NULL for @lookup_key to test 802 * whether the %NULL key exists. 803 * 804 * Return value: %TRUE if the key was found in the #GHashTable. 805 **/ 806 gboolean 807 g_hash_table_lookup_extended (GHashTable *hash_table, 808 gconstpointer lookup_key, 809 gpointer *orig_key, 810 gpointer *value) 811 { 812 GHashNode *node; 813 guint node_index; 814 815 g_return_val_if_fail (hash_table != NULL, FALSE); 816 817 node_index = g_hash_table_lookup_node (hash_table, lookup_key); 818 node = &hash_table->nodes [node_index]; 819 820 if (!node->key_hash) 821 return FALSE; 822 823 if (orig_key) 824 *orig_key = node->key; 825 826 if (value) 827 *value = node->value; 828 829 return TRUE; 830 } 831 832 /* 833 * g_hash_table_insert_internal: 834 * @hash_table: our #GHashTable 835 * @key: the key to insert 836 * @value: the value to insert 837 * @keep_new_key: if %TRUE and this key already exists in the table 838 * then call the destroy notify function on the old key. If %FALSE 839 * then call the destroy notify function on the new key. 840 * 841 * Implements the common logic for the g_hash_table_insert() and 842 * g_hash_table_replace() functions. 843 * 844 * Do a lookup of @key. If it is found, replace it with the new 845 * @value (and perhaps the new @key). If it is not found, create a 846 * new node. 847 */ 848 static void 849 g_hash_table_insert_internal (GHashTable *hash_table, 850 gpointer key, 851 gpointer value, 852 gboolean keep_new_key) 853 { 854 GHashNode *node; 855 guint node_index; 856 guint key_hash; 857 guint old_hash; 858 859 g_return_if_fail (hash_table != NULL); 860 g_return_if_fail (hash_table->ref_count > 0); 861 862 node_index = g_hash_table_lookup_node_for_insertion (hash_table, key, &key_hash); 863 node = &hash_table->nodes [node_index]; 864 865 old_hash = node->key_hash; 866 867 if (old_hash > 1) 868 { 869 if (keep_new_key) 870 { 871 if (hash_table->key_destroy_func) 872 hash_table->key_destroy_func (node->key); 873 node->key = key; 874 } 875 else 876 { 877 if (hash_table->key_destroy_func) 878 hash_table->key_destroy_func (key); 879 } 880 881 if (hash_table->value_destroy_func) 882 hash_table->value_destroy_func (node->value); 883 884 node->value = value; 885 } 886 else 887 { 888 node->key = key; 889 node->value = value; 890 node->key_hash = key_hash; 891 892 hash_table->nnodes++; 893 894 if (old_hash == 0) 895 { 896 /* We replaced an empty node, and not a tombstone */ 897 hash_table->noccupied++; 898 g_hash_table_maybe_resize (hash_table); 899 } 900 901 #ifndef G_DISABLE_ASSERT 902 hash_table->version++; 903 #endif 904 } 905 } 906 907 /** 908 * g_hash_table_insert: 909 * @hash_table: a #GHashTable. 910 * @key: a key to insert. 911 * @value: the value to associate with the key. 912 * 913 * Inserts a new key and value into a #GHashTable. 914 * 915 * If the key already exists in the #GHashTable its current value is replaced 916 * with the new value. If you supplied a @value_destroy_func when creating the 917 * #GHashTable, the old value is freed using that function. If you supplied 918 * a @key_destroy_func when creating the #GHashTable, the passed key is freed 919 * using that function. 920 **/ 921 void 922 g_hash_table_insert (GHashTable *hash_table, 923 gpointer key, 924 gpointer value) 925 { 926 g_hash_table_insert_internal (hash_table, key, value, FALSE); 927 } 928 929 /** 930 * g_hash_table_replace: 931 * @hash_table: a #GHashTable. 932 * @key: a key to insert. 933 * @value: the value to associate with the key. 934 * 935 * Inserts a new key and value into a #GHashTable similar to 936 * g_hash_table_insert(). The difference is that if the key already exists 937 * in the #GHashTable, it gets replaced by the new key. If you supplied a 938 * @value_destroy_func when creating the #GHashTable, the old value is freed 939 * using that function. If you supplied a @key_destroy_func when creating the 940 * #GHashTable, the old key is freed using that function. 941 **/ 942 void 943 g_hash_table_replace (GHashTable *hash_table, 944 gpointer key, 945 gpointer value) 946 { 947 g_hash_table_insert_internal (hash_table, key, value, TRUE); 948 } 949 950 /* 951 * g_hash_table_remove_internal: 952 * @hash_table: our #GHashTable 953 * @key: the key to remove 954 * @notify: %TRUE if the destroy notify handlers are to be called 955 * Return value: %TRUE if a node was found and removed, else %FALSE 956 * 957 * Implements the common logic for the g_hash_table_remove() and 958 * g_hash_table_steal() functions. 959 * 960 * Do a lookup of @key and remove it if it is found, calling the 961 * destroy notify handlers only if @notify is %TRUE. 962 */ 963 static gboolean 964 g_hash_table_remove_internal (GHashTable *hash_table, 965 gconstpointer key, 966 gboolean notify) 967 { 968 GHashNode *node; 969 guint node_index; 970 971 g_return_val_if_fail (hash_table != NULL, FALSE); 972 973 node_index = g_hash_table_lookup_node (hash_table, key); 974 node = &hash_table->nodes [node_index]; 975 976 /* g_hash_table_lookup_node() never returns a tombstone, so this is safe */ 977 if (!node->key_hash) 978 return FALSE; 979 980 g_hash_table_remove_node (hash_table, node, notify); 981 g_hash_table_maybe_resize (hash_table); 982 983 #ifndef G_DISABLE_ASSERT 984 hash_table->version++; 985 #endif 986 987 return TRUE; 988 } 989 990 /** 991 * g_hash_table_remove: 992 * @hash_table: a #GHashTable. 993 * @key: the key to remove. 994 * 995 * Removes a key and its associated value from a #GHashTable. 996 * 997 * If the #GHashTable was created using g_hash_table_new_full(), the 998 * key and value are freed using the supplied destroy functions, otherwise 999 * you have to make sure that any dynamically allocated values are freed 1000 * yourself. 1001 * 1002 * Return value: %TRUE if the key was found and removed from the #GHashTable. 1003 **/ 1004 gboolean 1005 g_hash_table_remove (GHashTable *hash_table, 1006 gconstpointer key) 1007 { 1008 return g_hash_table_remove_internal (hash_table, key, TRUE); 1009 } 1010 1011 /** 1012 * g_hash_table_steal: 1013 * @hash_table: a #GHashTable. 1014 * @key: the key to remove. 1015 * 1016 * Removes a key and its associated value from a #GHashTable without 1017 * calling the key and value destroy functions. 1018 * 1019 * Return value: %TRUE if the key was found and removed from the #GHashTable. 1020 **/ 1021 gboolean 1022 g_hash_table_steal (GHashTable *hash_table, 1023 gconstpointer key) 1024 { 1025 return g_hash_table_remove_internal (hash_table, key, FALSE); 1026 } 1027 1028 /** 1029 * g_hash_table_remove_all: 1030 * @hash_table: a #GHashTable 1031 * 1032 * Removes all keys and their associated values from a #GHashTable. 1033 * 1034 * If the #GHashTable was created using g_hash_table_new_full(), the keys 1035 * and values are freed using the supplied destroy functions, otherwise you 1036 * have to make sure that any dynamically allocated values are freed 1037 * yourself. 1038 * 1039 * Since: 2.12 1040 **/ 1041 void 1042 g_hash_table_remove_all (GHashTable *hash_table) 1043 { 1044 g_return_if_fail (hash_table != NULL); 1045 1046 #ifndef G_DISABLE_ASSERT 1047 if (hash_table->nnodes != 0) 1048 hash_table->version++; 1049 #endif 1050 1051 g_hash_table_remove_all_nodes (hash_table, TRUE); 1052 g_hash_table_maybe_resize (hash_table); 1053 } 1054 1055 /** 1056 * g_hash_table_steal_all: 1057 * @hash_table: a #GHashTable. 1058 * 1059 * Removes all keys and their associated values from a #GHashTable 1060 * without calling the key and value destroy functions. 1061 * 1062 * Since: 2.12 1063 **/ 1064 void 1065 g_hash_table_steal_all (GHashTable *hash_table) 1066 { 1067 g_return_if_fail (hash_table != NULL); 1068 1069 #ifndef G_DISABLE_ASSERT 1070 if (hash_table->nnodes != 0) 1071 hash_table->version++; 1072 #endif 1073 1074 g_hash_table_remove_all_nodes (hash_table, FALSE); 1075 g_hash_table_maybe_resize (hash_table); 1076 } 1077 1078 /* 1079 * g_hash_table_foreach_remove_or_steal: 1080 * @hash_table: our #GHashTable 1081 * @func: the user's callback function 1082 * @user_data: data for @func 1083 * @notify: %TRUE if the destroy notify handlers are to be called 1084 * 1085 * Implements the common logic for g_hash_table_foreach_remove() and 1086 * g_hash_table_foreach_steal(). 1087 * 1088 * Iterates over every node in the table, calling @func with the key 1089 * and value of the node (and @user_data). If @func returns %TRUE the 1090 * node is removed from the table. 1091 * 1092 * If @notify is true then the destroy notify handlers will be called 1093 * for each removed node. 1094 */ 1095 static guint 1096 g_hash_table_foreach_remove_or_steal (GHashTable *hash_table, 1097 GHRFunc func, 1098 gpointer user_data, 1099 gboolean notify) 1100 { 1101 guint deleted = 0; 1102 gint i; 1103 1104 for (i = 0; i < hash_table->size; i++) 1105 { 1106 GHashNode *node = &hash_table->nodes [i]; 1107 1108 if (node->key_hash > 1 && (* func) (node->key, node->value, user_data)) 1109 { 1110 g_hash_table_remove_node (hash_table, node, notify); 1111 deleted++; 1112 } 1113 } 1114 1115 g_hash_table_maybe_resize (hash_table); 1116 1117 #ifndef G_DISABLE_ASSERT 1118 if (deleted > 0) 1119 hash_table->version++; 1120 #endif 1121 1122 return deleted; 1123 } 1124 1125 /** 1126 * g_hash_table_foreach_remove: 1127 * @hash_table: a #GHashTable. 1128 * @func: the function to call for each key/value pair. 1129 * @user_data: user data to pass to the function. 1130 * 1131 * Calls the given function for each key/value pair in the #GHashTable. 1132 * If the function returns %TRUE, then the key/value pair is removed from the 1133 * #GHashTable. If you supplied key or value destroy functions when creating 1134 * the #GHashTable, they are used to free the memory allocated for the removed 1135 * keys and values. 1136 * 1137 * See #GHashTableIter for an alternative way to loop over the 1138 * key/value pairs in the hash table. 1139 * 1140 * Return value: the number of key/value pairs removed. 1141 **/ 1142 guint 1143 g_hash_table_foreach_remove (GHashTable *hash_table, 1144 GHRFunc func, 1145 gpointer user_data) 1146 { 1147 g_return_val_if_fail (hash_table != NULL, 0); 1148 g_return_val_if_fail (func != NULL, 0); 1149 1150 return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, TRUE); 1151 } 1152 1153 /** 1154 * g_hash_table_foreach_steal: 1155 * @hash_table: a #GHashTable. 1156 * @func: the function to call for each key/value pair. 1157 * @user_data: user data to pass to the function. 1158 * 1159 * Calls the given function for each key/value pair in the #GHashTable. 1160 * If the function returns %TRUE, then the key/value pair is removed from the 1161 * #GHashTable, but no key or value destroy functions are called. 1162 * 1163 * See #GHashTableIter for an alternative way to loop over the 1164 * key/value pairs in the hash table. 1165 * 1166 * Return value: the number of key/value pairs removed. 1167 **/ 1168 guint 1169 g_hash_table_foreach_steal (GHashTable *hash_table, 1170 GHRFunc func, 1171 gpointer user_data) 1172 { 1173 g_return_val_if_fail (hash_table != NULL, 0); 1174 g_return_val_if_fail (func != NULL, 0); 1175 1176 return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, FALSE); 1177 } 1178 1179 /** 1180 * g_hash_table_foreach: 1181 * @hash_table: a #GHashTable. 1182 * @func: the function to call for each key/value pair. 1183 * @user_data: user data to pass to the function. 1184 * 1185 * Calls the given function for each of the key/value pairs in the 1186 * #GHashTable. The function is passed the key and value of each 1187 * pair, and the given @user_data parameter. The hash table may not 1188 * be modified while iterating over it (you can't add/remove 1189 * items). To remove all items matching a predicate, use 1190 * g_hash_table_foreach_remove(). 1191 * 1192 * See g_hash_table_find() for performance caveats for linear 1193 * order searches in contrast to g_hash_table_lookup(). 1194 **/ 1195 void 1196 g_hash_table_foreach (GHashTable *hash_table, 1197 GHFunc func, 1198 gpointer user_data) 1199 { 1200 gint i; 1201 1202 g_return_if_fail (hash_table != NULL); 1203 g_return_if_fail (func != NULL); 1204 1205 for (i = 0; i < hash_table->size; i++) 1206 { 1207 GHashNode *node = &hash_table->nodes [i]; 1208 1209 if (node->key_hash > 1) 1210 (* func) (node->key, node->value, user_data); 1211 } 1212 } 1213 1214 /** 1215 * g_hash_table_find: 1216 * @hash_table: a #GHashTable. 1217 * @predicate: function to test the key/value pairs for a certain property. 1218 * @user_data: user data to pass to the function. 1219 * 1220 * Calls the given function for key/value pairs in the #GHashTable until 1221 * @predicate returns %TRUE. The function is passed the key and value of 1222 * each pair, and the given @user_data parameter. The hash table may not 1223 * be modified while iterating over it (you can't add/remove items). 1224 * 1225 * Note, that hash tables are really only optimized for forward lookups, 1226 * i.e. g_hash_table_lookup(). 1227 * So code that frequently issues g_hash_table_find() or 1228 * g_hash_table_foreach() (e.g. in the order of once per every entry in a 1229 * hash table) should probably be reworked to use additional or different 1230 * data structures for reverse lookups (keep in mind that an O(n) find/foreach 1231 * operation issued for all n values in a hash table ends up needing O(n*n) 1232 * operations). 1233 * 1234 * Return value: The value of the first key/value pair is returned, for which 1235 * func evaluates to %TRUE. If no pair with the requested property is found, 1236 * %NULL is returned. 1237 * 1238 * Since: 2.4 1239 **/ 1240 gpointer 1241 g_hash_table_find (GHashTable *hash_table, 1242 GHRFunc predicate, 1243 gpointer user_data) 1244 { 1245 gint i; 1246 1247 g_return_val_if_fail (hash_table != NULL, NULL); 1248 g_return_val_if_fail (predicate != NULL, NULL); 1249 1250 for (i = 0; i < hash_table->size; i++) 1251 { 1252 GHashNode *node = &hash_table->nodes [i]; 1253 1254 if (node->key_hash > 1 && predicate (node->key, node->value, user_data)) 1255 return node->value; 1256 } 1257 1258 return NULL; 1259 } 1260 1261 /** 1262 * g_hash_table_size: 1263 * @hash_table: a #GHashTable. 1264 * 1265 * Returns the number of elements contained in the #GHashTable. 1266 * 1267 * Return value: the number of key/value pairs in the #GHashTable. 1268 **/ 1269 guint 1270 g_hash_table_size (GHashTable *hash_table) 1271 { 1272 g_return_val_if_fail (hash_table != NULL, 0); 1273 1274 return hash_table->nnodes; 1275 } 1276 1277 /** 1278 * g_hash_table_get_keys: 1279 * @hash_table: a #GHashTable 1280 * 1281 * Retrieves every key inside @hash_table. The returned data is valid 1282 * until @hash_table is modified. 1283 * 1284 * Return value: a #GList containing all the keys inside the hash 1285 * table. The content of the list is owned by the hash table and 1286 * should not be modified or freed. Use g_list_free() when done 1287 * using the list. 1288 * 1289 * Since: 2.14 1290 */ 1291 GList * 1292 g_hash_table_get_keys (GHashTable *hash_table) 1293 { 1294 gint i; 1295 GList *retval; 1296 1297 g_return_val_if_fail (hash_table != NULL, NULL); 1298 1299 retval = NULL; 1300 for (i = 0; i < hash_table->size; i++) 1301 { 1302 GHashNode *node = &hash_table->nodes [i]; 1303 1304 if (node->key_hash > 1) 1305 retval = g_list_prepend (retval, node->key); 1306 } 1307 1308 return retval; 1309 } 1310 1311 /** 1312 * g_hash_table_get_values: 1313 * @hash_table: a #GHashTable 1314 * 1315 * Retrieves every value inside @hash_table. The returned data is 1316 * valid until @hash_table is modified. 1317 * 1318 * Return value: a #GList containing all the values inside the hash 1319 * table. The content of the list is owned by the hash table and 1320 * should not be modified or freed. Use g_list_free() when done 1321 * using the list. 1322 * 1323 * Since: 2.14 1324 */ 1325 GList * 1326 g_hash_table_get_values (GHashTable *hash_table) 1327 { 1328 gint i; 1329 GList *retval; 1330 1331 g_return_val_if_fail (hash_table != NULL, NULL); 1332 1333 retval = NULL; 1334 for (i = 0; i < hash_table->size; i++) 1335 { 1336 GHashNode *node = &hash_table->nodes [i]; 1337 1338 if (node->key_hash > 1) 1339 retval = g_list_prepend (retval, node->value); 1340 } 1341 1342 return retval; 1343 } 1344 1345 #define __G_HASH_C__ 1346 #include "galiasdef.c" 1347