mono/eglib/ghashtable.c

   1 /*
   2  * ghashtable.c: Hashtable implementation
   3  *
   4  * Author:
   5  *   Miguel de Icaza (miguel@novell.com)
   6  *
   7  * (C) 2006 Novell, Inc.
   8  *
   9  * Permission is hereby granted, free of charge, to any person obtaining
  10  * a copy of this software and associated documentation files (the
  11  * "Software"), to deal in the Software without restriction, including
  12  * without limitation the rights to use, copy, modify, merge, publish,
  13  * distribute, sublicense, and/or sell copies of the Software, and to
  14  * permit persons to whom the Software is furnished to do so, subject to
  15  * the following conditions:
  16  *
  17  * The above copyright notice and this permission notice shall be
  18  * included in all copies or substantial portions of the Software.
  19  *
  20  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  21  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  22  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  23  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  24  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  25  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  26  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  27  */
  28 #include <stdio.h>
  29 #include <math.h>
  30 #include <glib.h>
  31
  32 typedef struct _Slot Slot;
  33
  34 struct _Slot {
  35         gpointer key;
  36         gpointer value;
  37         Slot    *next;
  38 };
  39
  40 static gpointer KEYMARKER_REMOVED = &KEYMARKER_REMOVED;
  41
  42 struct _GHashTable {
  43         GHashFunc      hash_func;
  44         GEqualFunc     key_equal_func;
  45
  46         Slot **table;
  47         int   table_size;
  48         int   in_use;
  49         int   threshold;
  50         int   last_rehash;
  51         GDestroyNotify value_destroy_func, key_destroy_func;
  52 };
  53
  54 typedef struct {
  55         GHashTable *ht;
  56         int slot_index;
  57         Slot *slot;
  58 } Iter;
  59
  60 static const guint prime_tbl[] = {
  61         11, 19, 37, 73, 109, 163, 251, 367, 557, 823, 1237,
  62         1861, 2777, 4177, 6247, 9371, 14057, 21089, 31627,
  63         47431, 71143, 106721, 160073, 240101, 360163,
  64         540217, 810343, 1215497, 1823231, 2734867, 4102283,
  65         6153409, 9230113, 13845163
  66 };
  67
  68 static gboolean
  69 test_prime (int x)
  70 {
  71         if ((x & 1) != 0) {
  72                 int n;
  73                 for (n = 3; n< (int)sqrt (x); n += 2) {
  74                         if ((x % n) == 0)
  75                                 return FALSE;
  76                 }
  77                 return TRUE;
  78         }
  79         // There is only one even prime - 2.
  80         return (x == 2);
  81 }
  82
  83 static int
  84 calc_prime (int x)
  85 {
  86         int i;
  87
  88         for (i = (x & (~1))-1; i< G_MAXINT32; i += 2) {
  89                 if (test_prime (i))
  90                         return i;
  91         }
  92         return x;
  93 }
  94
  95 guint
  96 g_spaced_primes_closest (guint x)
  97 {
  98         int i;
  99
 100         for (i = 0; i < G_N_ELEMENTS (prime_tbl); i++) {
 101                 if (x <= prime_tbl [i])
 102                         return prime_tbl [i];
 103         }
 104         return calc_prime (x);
 105 }
 106
 107 GHashTable *
 108 g_hash_table_new (GHashFunc hash_func, GEqualFunc key_equal_func)
 109 {
 110         GHashTable *hash;
 111
 112         if (hash_func == NULL)
 113                 hash_func = g_direct_hash;
 114         if (key_equal_func == NULL)
 115                 key_equal_func = g_direct_equal;
 116         hash = g_new0 (GHashTable, 1);
 117
 118         hash->hash_func = hash_func;
 119         hash->key_equal_func = key_equal_func;
 120
 121         hash->table_size = g_spaced_primes_closest (1);
 122         hash->table = g_new0 (Slot *, hash->table_size);
 123         hash->last_rehash = hash->table_size;
 124
 125         return hash;
 126 }
 127
 128 GHashTable *
 129 g_hash_table_new_full (GHashFunc hash_func, GEqualFunc key_equal_func,
 130                        GDestroyNotify key_destroy_func, GDestroyNotify value_destroy_func)
 131 {
 132         GHashTable *hash = g_hash_table_new (hash_func, key_equal_func);
 133         if (hash == NULL)
 134                 return NULL;
 135
 136         hash->key_destroy_func = key_destroy_func;
 137         hash->value_destroy_func = value_destroy_func;
 138
 139         return hash;
 140 }
 141
 142 #if 0
 143 static void
 144 dump_hash_table (GHashTable *hash)
 145 {
 146         int i;
 147
 148         for (i = 0; i < hash->table_size; i++) {
 149                 Slot *s;
 150
 151                 for (s = hash->table [i]; s != NULL; s = s->next){
 152                         guint hashcode = (*hash->hash_func) (s->key);
 153                         guint slot = (hashcode) % hash->table_size;
 154                         printf ("key %p hash %x on slot %d correct slot %d tb size %d\n", s->key, hashcode, i, slot, hash->table_size);
 155                 }
 156         }
 157 }
 158 #endif
 159
 160 #ifdef SANITY_CHECK
 161 static void
 162 sanity_check (GHashTable *hash)
 163 {
 164         int i;
 165
 166         for (i = 0; i < hash->table_size; i++) {
 167                 Slot *s;
 168
 169                 for (s = hash->table [i]; s != NULL; s = s->next){
 170                         guint hashcode = (*hash->hash_func) (s->key);
 171                         guint slot = (hashcode) % hash->table_size;
 172                         if (slot != i) {
 173                                 dump_hashcode_func = 1;
 174                                 hashcode = (*hash->hash_func) (s->key);
 175                                 dump_hashcode_func = 0;
 176                                 g_error ("Key %p (bucket %d) on invalid bucket %d (hashcode %x) (tb size %d)", s->key, slot, i, hashcode, hash->table_size);
 177                         }
 178                 }
 179         }
 180 }
 181 #else
 182
 183 #define sanity_check(HASH) do {}while(0)
 184
 185 #endif
 186
 187 static void
 188 do_rehash (GHashTable *hash)
 189 {
 190         int current_size, i;
 191         Slot **table;
 192
 193         /* printf ("Resizing diff=%d slots=%d\n", hash->in_use - hash->last_rehash, hash->table_size); */
 194         hash->last_rehash = hash->table_size;
 195         current_size = hash->table_size;
 196         hash->table_size = g_spaced_primes_closest (hash->in_use);
 197         /* printf ("New size: %d\n", hash->table_size); */
 198         table = hash->table;
 199         hash->table = g_new0 (Slot *, hash->table_size);
 200
 201         for (i = 0; i < current_size; i++){
 202                 Slot *s, *next;
 203
 204                 for (s = table [i]; s != NULL; s = next){
 205                         guint hashcode = ((*hash->hash_func) (s->key)) % hash->table_size;
 206                         next = s->next;
 207
 208                         s->next = hash->table [hashcode];
 209                         hash->table [hashcode] = s;
 210                 }
 211         }
 212         g_free (table);
 213 }
 214
 215 static void
 216 rehash (GHashTable *hash)
 217 {
 218         int diff = ABS (hash->last_rehash - hash->in_use);
 219
 220         /* These are the factors to play with to change the rehashing strategy */
 221         /* I played with them with a large range, and could not really get */
 222         /* something that was too good, maybe the tests are not that great */
 223         if (!(diff * 0.75 > hash->table_size * 2))
 224                 return;
 225         do_rehash (hash);
 226         sanity_check (hash);
 227 }
 228
 229 void
 230 g_hash_table_insert_replace (GHashTable *hash, gpointer key, gpointer value, gboolean replace)
 231 {
 232         guint hashcode;
 233         Slot *s;
 234         GEqualFunc equal;
 235
 236         g_return_if_fail (hash != NULL);
 237         sanity_check (hash);
 238
 239         equal = hash->key_equal_func;
 240         if (hash->in_use >= hash->threshold)
 241                 rehash (hash);
 242
 243         hashcode = ((*hash->hash_func) (key)) % hash->table_size;
 244         for (s = hash->table [hashcode]; s != NULL; s = s->next){
 245                 if ((*equal) (s->key, key)){
 246                         if (replace){
 247                                 if (hash->key_destroy_func != NULL)
 248                                         (*hash->key_destroy_func)(s->key);
 249                                 s->key = key;
 250                         }
 251                         if (hash->value_destroy_func != NULL)
 252                                 (*hash->value_destroy_func) (s->value);
 253                         s->value = value;
 254                         sanity_check (hash);
 255                         return;
 256                 }
 257         }
 258         s = g_new (Slot, 1);
 259         s->key = key;
 260         s->value = value;
 261         s->next = hash->table [hashcode];
 262         hash->table [hashcode] = s;
 263         hash->in_use++;
 264         sanity_check (hash);
 265 }
 266
 267 GList*
 268 g_hash_table_get_keys (GHashTable *hash)
 269 {
 270         GHashTableIter iter;
 271         GList *rv = NULL;
 272         gpointer key;
 273
 274         g_hash_table_iter_init (&iter, hash);
 275
 276         while (g_hash_table_iter_next (&iter, &key, NULL))
 277                 rv = g_list_prepend (rv, key);
 278
 279         return g_list_reverse (rv);
 280 }
 281
 282 GList*
 283 g_hash_table_get_values (GHashTable *hash)
 284 {
 285         GHashTableIter iter;
 286         GList *rv = NULL;
 287         gpointer value;
 288
 289         g_hash_table_iter_init (&iter, hash);
 290
 291         while (g_hash_table_iter_next (&iter, NULL, &value))
 292                 rv = g_list_prepend (rv, value);
 293
 294         return g_list_reverse (rv);
 295 }
 296
 297
 298 guint
 299 g_hash_table_size (GHashTable *hash)
 300 {
 301         g_return_val_if_fail (hash != NULL, 0);
 302
 303         return hash->in_use;
 304 }
 305
 306 gpointer
 307 g_hash_table_lookup (GHashTable *hash, gconstpointer key)
 308 {
 309         gpointer orig_key, value;
 310
 311         if (g_hash_table_lookup_extended (hash, key, &orig_key, &value))
 312                 return value;
 313         else
 314                 return NULL;
 315 }
 316
 317 gboolean
 318 g_hash_table_lookup_extended (GHashTable *hash, gconstpointer key, gpointer *orig_key, gpointer *value)
 319 {
 320         GEqualFunc equal;
 321         Slot *s;
 322         guint hashcode;
 323
 324         g_return_val_if_fail (hash != NULL, FALSE);
 325         sanity_check (hash);
 326         equal = hash->key_equal_func;
 327
 328         hashcode = ((*hash->hash_func) (key)) % hash->table_size;
 329
 330         for (s = hash->table [hashcode]; s != NULL; s = s->next){
 331                 if ((*equal)(s->key, key)){
 332                         if (orig_key)
 333                                 *orig_key = s->key;
 334                         if (value)
 335                                 *value = s->value;
 336                         return TRUE;
 337                 }
 338         }
 339         return FALSE;
 340 }
 341
 342 void
 343 g_hash_table_foreach (GHashTable *hash, GHFunc func, gpointer user_data)
 344 {
 345         int i;
 346
 347         g_return_if_fail (hash != NULL);
 348         g_return_if_fail (func != NULL);
 349
 350         for (i = 0; i < hash->table_size; i++){
 351                 Slot *s;
 352
 353                 for (s = hash->table [i]; s != NULL; s = s->next)
 354                         (*func)(s->key, s->value, user_data);
 355         }
 356 }
 357
 358 gpointer
 359 g_hash_table_find (GHashTable *hash, GHRFunc predicate, gpointer user_data)
 360 {
 361         int i;
 362
 363         g_return_val_if_fail (hash != NULL, NULL);
 364         g_return_val_if_fail (predicate != NULL, NULL);
 365
 366         for (i = 0; i < hash->table_size; i++){
 367                 Slot *s;
 368
 369                 for (s = hash->table [i]; s != NULL; s = s->next)
 370                         if ((*predicate)(s->key, s->value, user_data))
 371                                 return s->value;
 372         }
 373         return NULL;
 374 }
 375
 376 void
 377 g_hash_table_remove_all (GHashTable *hash)
 378 {
 379         int i;
 380
 381         g_return_if_fail (hash != NULL);
 382
 383         for (i = 0; i < hash->table_size; i++){
 384                 Slot *s;
 385
 386                 while (hash->table [i]) {
 387                         s = hash->table [i];
 388                         g_hash_table_remove (hash, s->key);
 389                 }
 390         }
 391 }
 392
 393 gboolean
 394 g_hash_table_remove (GHashTable *hash, gconstpointer key)
 395 {
 396         GEqualFunc equal;
 397         Slot *s, *last;
 398         guint hashcode;
 399
 400         g_return_val_if_fail (hash != NULL, FALSE);
 401         sanity_check (hash);
 402         equal = hash->key_equal_func;
 403
 404         hashcode = ((*hash->hash_func)(key)) % hash->table_size;
 405         last = NULL;
 406         for (s = hash->table [hashcode]; s != NULL; s = s->next){
 407                 if ((*equal)(s->key, key)){
 408                         if (hash->key_destroy_func != NULL)
 409                                 (*hash->key_destroy_func)(s->key);
 410                         if (hash->value_destroy_func != NULL)
 411                                 (*hash->value_destroy_func)(s->value);
 412                         if (last == NULL)
 413                                 hash->table [hashcode] = s->next;
 414                         else
 415                                 last->next = s->next;
 416                         g_free (s);
 417                         hash->in_use--;
 418                         sanity_check (hash);
 419                         return TRUE;
 420                 }
 421                 last = s;
 422         }
 423         sanity_check (hash);
 424         return FALSE;
 425 }
 426
 427 guint
 428 g_hash_table_foreach_remove (GHashTable *hash, GHRFunc func, gpointer user_data)
 429 {
 430         int i;
 431         int count = 0;
 432
 433         g_return_val_if_fail (hash != NULL, 0);
 434         g_return_val_if_fail (func != NULL, 0);
 435
 436         sanity_check (hash);
 437         for (i = 0; i < hash->table_size; i++){
 438                 Slot *s, *last;
 439
 440                 last = NULL;
 441                 for (s = hash->table [i]; s != NULL; ){
 442                         if ((*func)(s->key, s->value, user_data)){
 443                                 Slot *n;
 444
 445                                 if (hash->key_destroy_func != NULL)
 446                                         (*hash->key_destroy_func)(s->key);
 447                                 if (hash->value_destroy_func != NULL)
 448                                         (*hash->value_destroy_func)(s->value);
 449                                 if (last == NULL){
 450                                         hash->table [i] = s->next;
 451                                         n = s->next;
 452                                 } else  {
 453                                         last->next = s->next;
 454                                         n = last->next;
 455                                 }
 456                                 g_free (s);
 457                                 hash->in_use--;
 458                                 count++;
 459                                 s = n;
 460                         } else {
 461                                 last = s;
 462                                 s = s->next;
 463                         }
 464                 }
 465         }
 466         sanity_check (hash);
 467         if (count > 0)
 468                 rehash (hash);
 469         return count;
 470 }
 471
 472 gboolean
 473 g_hash_table_steal (GHashTable *hash, gconstpointer key)
 474 {
 475         GEqualFunc equal;
 476         Slot *s, *last;
 477         guint hashcode;
 478
 479         g_return_val_if_fail (hash != NULL, FALSE);
 480         sanity_check (hash);
 481         equal = hash->key_equal_func;
 482
 483         hashcode = ((*hash->hash_func)(key)) % hash->table_size;
 484         last = NULL;
 485         for (s = hash->table [hashcode]; s != NULL; s = s->next){
 486                 if ((*equal)(s->key, key)) {
 487                         if (last == NULL)
 488                                 hash->table [hashcode] = s->next;
 489                         else
 490                                 last->next = s->next;
 491                         g_free (s);
 492                         hash->in_use--;
 493                         sanity_check (hash);
 494                         return TRUE;
 495                 }
 496                 last = s;
 497         }
 498         sanity_check (hash);
 499         return FALSE;
 500
 501 }
 502
 503 guint
 504 g_hash_table_foreach_steal (GHashTable *hash, GHRFunc func, gpointer user_data)
 505 {
 506         int i;
 507         int count = 0;
 508
 509         g_return_val_if_fail (hash != NULL, 0);
 510         g_return_val_if_fail (func != NULL, 0);
 511
 512         sanity_check (hash);
 513         for (i = 0; i < hash->table_size; i++){
 514                 Slot *s, *last;
 515
 516                 last = NULL;
 517                 for (s = hash->table [i]; s != NULL; ){
 518                         if ((*func)(s->key, s->value, user_data)){
 519                                 Slot *n;
 520
 521                                 if (last == NULL){
 522                                         hash->table [i] = s->next;
 523                                         n = s->next;
 524                                 } else  {
 525                                         last->next = s->next;
 526                                         n = last->next;
 527                                 }
 528                                 g_free (s);
 529                                 hash->in_use--;
 530                                 count++;
 531                                 s = n;
 532                         } else {
 533                                 last = s;
 534                                 s = s->next;
 535                         }
 536                 }
 537         }
 538         sanity_check (hash);
 539         if (count > 0)
 540                 rehash (hash);
 541         return count;
 542 }
 543
 544 void
 545 g_hash_table_destroy (GHashTable *hash)
 546 {
 547         int i;
 548
 549         g_return_if_fail (hash != NULL);
 550
 551         for (i = 0; i < hash->table_size; i++){
 552                 Slot *s, *next;
 553
 554                 for (s = hash->table [i]; s != NULL; s = next){
 555                         next = s->next;
 556
 557                         if (hash->key_destroy_func != NULL)
 558                                 (*hash->key_destroy_func)(s->key);
 559                         if (hash->value_destroy_func != NULL)
 560                                 (*hash->value_destroy_func)(s->value);
 561                         g_free (s);
 562                 }
 563         }
 564         g_free (hash->table);
 565
 566         g_free (hash);
 567 }
 568
 569 void
 570 g_hash_table_print_stats (GHashTable *table)
 571 {
 572         int i, max_chain_index, chain_size, max_chain_size;
 573         Slot *node;
 574
 575         max_chain_size = 0;
 576         max_chain_index = -1;
 577         for (i = 0; i < table->table_size; i++) {
 578                 chain_size = 0;
 579                 for (node = table->table [i]; node; node = node->next)
 580                         chain_size ++;
 581                 if (chain_size > max_chain_size) {
 582                         max_chain_size = chain_size;
 583                         max_chain_index = i;
 584                 }
 585         }
 586
 587         printf ("Size: %d Table Size: %d Max Chain Length: %d at %d\n", table->in_use, table->table_size, max_chain_size, max_chain_index);
 588 }
 589
 590 void
 591 g_hash_table_iter_init (GHashTableIter *it, GHashTable *hash_table)
 592 {
 593         Iter *iter = (Iter*)it;
 594
 595         memset (iter, 0, sizeof (Iter));
 596         iter->ht = hash_table;
 597         iter->slot_index = -1;
 598 }
 599
 600 gboolean g_hash_table_iter_next (GHashTableIter *it, gpointer *key, gpointer *value)
 601 {
 602         Iter *iter = (Iter*)it;
 603
 604         GHashTable *hash = iter->ht;
 605
 606         g_assert (iter->slot_index != -2);
 607         g_assert (sizeof (Iter) <= sizeof (GHashTableIter));
 608
 609         if (!iter->slot) {
 610                 while (TRUE) {
 611                         iter->slot_index ++;
 612                         if (iter->slot_index >= hash->table_size) {
 613                                 iter->slot_index = -2;
 614                                 return FALSE;
 615                         }
 616                         if (hash->table [iter->slot_index])
 617                                 break;
 618                 }
 619                 iter->slot = hash->table [iter->slot_index];
 620         }
 621
 622         if (key)
 623                 *key = iter->slot->key;
 624         if (value)
 625                 *value = iter->slot->value;
 626         iter->slot = iter->slot->next;
 627
 628         return TRUE;
 629 }
 630
 631 gboolean
 632 g_direct_equal (gconstpointer v1, gconstpointer v2)
 633 {
 634         return v1 == v2;
 635 }
 636
 637 guint
 638 g_direct_hash (gconstpointer v1)
 639 {
 640         return GPOINTER_TO_UINT (v1);
 641 }
 642
 643 gboolean
 644 g_int_equal (gconstpointer v1, gconstpointer v2)
 645 {
 646         return *(gint *)v1 == *(gint *)v2;
 647 }
 648
 649 guint
 650 g_int_hash (gconstpointer v1)
 651 {
 652         return *(guint *)v1;
 653 }
 654
 655 gboolean
 656 g_str_equal (gconstpointer v1, gconstpointer v2)
 657 {
 658         return strcmp (v1, v2) == 0;
 659 }
 660
 661 guint
 662 g_str_hash (gconstpointer v1)
 663 {
 664         guint hash = 0;
 665         char *p = (char *) v1;
 666
 667         while (*p++)
 668                 hash = (hash << 5) - (hash + *p);
 669
 670         return hash;
 671 }