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