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