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 gpointer
 309 g_hash_table_lookup (GHashTable *hash, gconstpointer key)
 310 {
 311         gpointer orig_key, value;
 312
 313         if (g_hash_table_lookup_extended (hash, key, &orig_key, &value))
 314                 return value;
 315         else
 316                 return NULL;
 317 }
 318
 319 gboolean
 320 g_hash_table_lookup_extended (GHashTable *hash, gconstpointer key, gpointer *orig_key, gpointer *value)
 321 {
 322         GEqualFunc equal;
 323         Slot *s;
 324         guint hashcode;
 325
 326         g_return_val_if_fail (hash != NULL, FALSE);
 327         sanity_check (hash);
 328         equal = hash->key_equal_func;
 329
 330         hashcode = ((*hash->hash_func) (key)) % hash->table_size;
 331
 332         for (s = hash->table [hashcode]; s != NULL; s = s->next){
 333                 if ((*equal)(s->key, key)){
 334                         if (orig_key)
 335                                 *orig_key = s->key;
 336                         if (value)
 337                                 *value = s->value;
 338                         return TRUE;
 339                 }
 340         }
 341         return FALSE;
 342 }
 343
 344 void
 345 g_hash_table_foreach (GHashTable *hash, GHFunc func, gpointer user_data)
 346 {
 347         int i;
 348
 349         g_return_if_fail (hash != NULL);
 350         g_return_if_fail (func != NULL);
 351
 352         for (i = 0; i < hash->table_size; i++){
 353                 Slot *s;
 354
 355                 for (s = hash->table [i]; s != NULL; s = s->next)
 356                         (*func)(s->key, s->value, user_data);
 357         }
 358 }
 359
 360 gpointer
 361 g_hash_table_find (GHashTable *hash, GHRFunc predicate, gpointer user_data)
 362 {
 363         int i;
 364
 365         g_return_val_if_fail (hash != NULL, NULL);
 366         g_return_val_if_fail (predicate != NULL, NULL);
 367
 368         for (i = 0; i < hash->table_size; i++){
 369                 Slot *s;
 370
 371                 for (s = hash->table [i]; s != NULL; s = s->next)
 372                         if ((*predicate)(s->key, s->value, user_data))
 373                                 return s->value;
 374         }
 375         return NULL;
 376 }
 377
 378 void
 379 g_hash_table_remove_all (GHashTable *hash)
 380 {
 381         int i;
 382
 383         g_return_if_fail (hash != NULL);
 384
 385         for (i = 0; i < hash->table_size; i++){
 386                 Slot *s;
 387
 388                 while (hash->table [i]) {
 389                         s = hash->table [i];
 390                         g_hash_table_remove (hash, s->key);
 391                 }
 392         }
 393 }
 394
 395 gboolean
 396 g_hash_table_remove (GHashTable *hash, gconstpointer key)
 397 {
 398         GEqualFunc equal;
 399         Slot *s, *last;
 400         guint hashcode;
 401
 402         g_return_val_if_fail (hash != NULL, FALSE);
 403         sanity_check (hash);
 404         equal = hash->key_equal_func;
 405
 406         hashcode = ((*hash->hash_func)(key)) % hash->table_size;
 407         last = NULL;
 408         for (s = hash->table [hashcode]; s != NULL; s = s->next){
 409                 if ((*equal)(s->key, key)){
 410                         if (hash->key_destroy_func != NULL)
 411                                 (*hash->key_destroy_func)(s->key);
 412                         if (hash->value_destroy_func != NULL)
 413                                 (*hash->value_destroy_func)(s->value);
 414                         if (last == NULL)
 415                                 hash->table [hashcode] = s->next;
 416                         else
 417                                 last->next = s->next;
 418                         g_free (s);
 419                         hash->in_use--;
 420                         sanity_check (hash);
 421                         return TRUE;
 422                 }
 423                 last = s;
 424         }
 425         sanity_check (hash);
 426         return FALSE;
 427 }
 428
 429 guint
 430 g_hash_table_foreach_remove (GHashTable *hash, GHRFunc func, gpointer user_data)
 431 {
 432         int i;
 433         int count = 0;
 434
 435         g_return_val_if_fail (hash != NULL, 0);
 436         g_return_val_if_fail (func != NULL, 0);
 437
 438         sanity_check (hash);
 439         for (i = 0; i < hash->table_size; i++){
 440                 Slot *s, *last;
 441
 442                 last = NULL;
 443                 for (s = hash->table [i]; s != NULL; ){
 444                         if ((*func)(s->key, s->value, user_data)){
 445                                 Slot *n;
 446
 447                                 if (hash->key_destroy_func != NULL)
 448                                         (*hash->key_destroy_func)(s->key);
 449                                 if (hash->value_destroy_func != NULL)
 450                                         (*hash->value_destroy_func)(s->value);
 451                                 if (last == NULL){
 452                                         hash->table [i] = s->next;
 453                                         n = s->next;
 454                                 } else  {
 455                                         last->next = s->next;
 456                                         n = last->next;
 457                                 }
 458                                 g_free (s);
 459                                 hash->in_use--;
 460                                 count++;
 461                                 s = n;
 462                         } else {
 463                                 last = s;
 464                                 s = s->next;
 465                         }
 466                 }
 467         }
 468         sanity_check (hash);
 469         if (count > 0)
 470                 rehash (hash);
 471         return count;
 472 }
 473
 474 gboolean
 475 g_hash_table_steal (GHashTable *hash, gconstpointer key)
 476 {
 477         GEqualFunc equal;
 478         Slot *s, *last;
 479         guint hashcode;
 480
 481         g_return_val_if_fail (hash != NULL, FALSE);
 482         sanity_check (hash);
 483         equal = hash->key_equal_func;
 484
 485         hashcode = ((*hash->hash_func)(key)) % hash->table_size;
 486         last = NULL;
 487         for (s = hash->table [hashcode]; s != NULL; s = s->next){
 488                 if ((*equal)(s->key, key)) {
 489                         if (last == NULL)
 490                                 hash->table [hashcode] = s->next;
 491                         else
 492                                 last->next = s->next;
 493                         g_free (s);
 494                         hash->in_use--;
 495                         sanity_check (hash);
 496                         return TRUE;
 497                 }
 498                 last = s;
 499         }
 500         sanity_check (hash);
 501         return FALSE;
 502
 503 }
 504
 505 guint
 506 g_hash_table_foreach_steal (GHashTable *hash, GHRFunc func, gpointer user_data)
 507 {
 508         int i;
 509         int count = 0;
 510
 511         g_return_val_if_fail (hash != NULL, 0);
 512         g_return_val_if_fail (func != NULL, 0);
 513
 514         sanity_check (hash);
 515         for (i = 0; i < hash->table_size; i++){
 516                 Slot *s, *last;
 517
 518                 last = NULL;
 519                 for (s = hash->table [i]; s != NULL; ){
 520                         if ((*func)(s->key, s->value, user_data)){
 521                                 Slot *n;
 522
 523                                 if (last == NULL){
 524                                         hash->table [i] = s->next;
 525                                         n = s->next;
 526                                 } else  {
 527                                         last->next = s->next;
 528                                         n = last->next;
 529                                 }
 530                                 g_free (s);
 531                                 hash->in_use--;
 532                                 count++;
 533                                 s = n;
 534                         } else {
 535                                 last = s;
 536                                 s = s->next;
 537                         }
 538                 }
 539         }
 540         sanity_check (hash);
 541         if (count > 0)
 542                 rehash (hash);
 543         return count;
 544 }
 545
 546 void
 547 g_hash_table_destroy (GHashTable *hash)
 548 {
 549         int i;
 550
 551         if (!hash)
 552                 return;
 553
 554         for (i = 0; i < hash->table_size; i++){
 555                 Slot *s, *next;
 556
 557                 for (s = hash->table [i]; s != NULL; s = next){
 558                         next = s->next;
 559
 560                         if (hash->key_destroy_func != NULL)
 561                                 (*hash->key_destroy_func)(s->key);
 562                         if (hash->value_destroy_func != NULL)
 563                                 (*hash->value_destroy_func)(s->value);
 564                         g_free (s);
 565                 }
 566         }
 567         g_free (hash->table);
 568
 569         g_free (hash);
 570 }
 571
 572 void
 573 g_hash_table_print_stats (GHashTable *table)
 574 {
 575         int i, max_chain_index, chain_size, max_chain_size;
 576         Slot *node;
 577
 578         max_chain_size = 0;
 579         max_chain_index = -1;
 580         for (i = 0; i < table->table_size; i++) {
 581                 chain_size = 0;
 582                 for (node = table->table [i]; node; node = node->next)
 583                         chain_size ++;
 584                 if (chain_size > max_chain_size) {
 585                         max_chain_size = chain_size;
 586                         max_chain_index = i;
 587                 }
 588         }
 589
 590         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);
 591 }
 592
 593 void
 594 g_hash_table_iter_init (GHashTableIter *it, GHashTable *hash_table)
 595 {
 596         Iter *iter = (Iter*)it;
 597
 598         memset (iter, 0, sizeof (Iter));
 599         iter->ht = hash_table;
 600         iter->slot_index = -1;
 601 }
 602
 603 gboolean g_hash_table_iter_next (GHashTableIter *it, gpointer *key, gpointer *value)
 604 {
 605         Iter *iter = (Iter*)it;
 606
 607         GHashTable *hash = iter->ht;
 608
 609         g_assert (iter->slot_index != -2);
 610         g_assert (sizeof (Iter) <= sizeof (GHashTableIter));
 611
 612         if (!iter->slot) {
 613                 while (TRUE) {
 614                         iter->slot_index ++;
 615                         if (iter->slot_index >= hash->table_size) {
 616                                 iter->slot_index = -2;
 617                                 return FALSE;
 618                         }
 619                         if (hash->table [iter->slot_index])
 620                                 break;
 621                 }
 622                 iter->slot = hash->table [iter->slot_index];
 623         }
 624
 625         if (key)
 626                 *key = iter->slot->key;
 627         if (value)
 628                 *value = iter->slot->value;
 629         iter->slot = iter->slot->next;
 630
 631         return TRUE;
 632 }
 633
 634 gboolean
 635 g_direct_equal (gconstpointer v1, gconstpointer v2)
 636 {
 637         return v1 == v2;
 638 }
 639
 640 guint
 641 g_direct_hash (gconstpointer v1)
 642 {
 643         return GPOINTER_TO_UINT (v1);
 644 }
 645
 646 gboolean
 647 g_int_equal (gconstpointer v1, gconstpointer v2)
 648 {
 649         return *(gint *)v1 == *(gint *)v2;
 650 }
 651
 652 guint
 653 g_int_hash (gconstpointer v1)
 654 {
 655         return *(guint *)v1;
 656 }
 657
 658 gboolean
 659 g_str_equal (gconstpointer v1, gconstpointer v2)
 660 {
 661         return v1 == v2 || strcmp ((const char*)v1, (const char*)v2) == 0;
 662 }
 663
 664 guint
 665 g_str_hash (gconstpointer v1)
 666 {
 667         guint hash = 0;
 668         char *p = (char *) v1;
 669
 670         while (*p++)
 671                 hash = (hash << 5) - (hash + *p);
 672
 673         return hash;
 674 }