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 static const guint prime_tbl[] = {
  55         11, 19, 37, 73, 109, 163, 251, 367, 557, 823, 1237,
  56         1861, 2777, 4177, 6247, 9371, 14057, 21089, 31627,
  57         47431, 71143, 106721, 160073, 240101, 360163,
  58         540217, 810343, 1215497, 1823231, 2734867, 4102283,
  59         6153409, 9230113, 13845163
  60 };
  61
  62 static gboolean
  63 test_prime (int x)
  64 {
  65         if ((x & 1) != 0) {
  66                 int n;
  67                 for (n = 3; n< (int)sqrt (x); n += 2) {
  68                         if ((x % n) == 0)
  69                                 return FALSE;
  70                 }
  71                 return TRUE;
  72         }
  73         // There is only one even prime - 2.
  74         return (x == 2);
  75 }
  76
  77 static int
  78 calc_prime (int x)
  79 {
  80         int i;
  81
  82         for (i = (x & (~1))-1; i< G_MAXINT32; i += 2) {
  83                 if (test_prime (i))
  84                         return i;
  85         }
  86         return x;
  87 }
  88
  89 guint
  90 g_spaced_primes_closest (guint x)
  91 {
  92         int i;
  93
  94         for (i = 0; i < G_N_ELEMENTS (prime_tbl); i++) {
  95                 if (x <= prime_tbl [i])
  96                         return prime_tbl [i];
  97         }
  98         return calc_prime (x);
  99 }
 100
 101 GHashTable *
 102 g_hash_table_new (GHashFunc hash_func, GEqualFunc key_equal_func)
 103 {
 104         GHashTable *hash;
 105
 106         if (hash_func == NULL)
 107                 hash_func = g_direct_hash;
 108         if (key_equal_func == NULL)
 109                 key_equal_func = g_direct_equal;
 110         hash = g_new0 (GHashTable, 1);
 111
 112         hash->hash_func = hash_func;
 113         hash->key_equal_func = key_equal_func;
 114
 115         hash->table_size = g_spaced_primes_closest (1);
 116         hash->table = g_new0 (Slot *, hash->table_size);
 117         hash->last_rehash = hash->table_size;
 118
 119         return hash;
 120 }
 121
 122 GHashTable *
 123 g_hash_table_new_full (GHashFunc hash_func, GEqualFunc key_equal_func,
 124                        GDestroyNotify key_destroy_func, GDestroyNotify value_destroy_func)
 125 {
 126         GHashTable *hash = g_hash_table_new (hash_func, key_equal_func);
 127         if (hash == NULL)
 128                 return NULL;
 129
 130         hash->key_destroy_func = key_destroy_func;
 131         hash->value_destroy_func = value_destroy_func;
 132
 133         return hash;
 134 }
 135
 136 #if 0
 137 static void
 138 dump_hash_table (GHashTable *hash)
 139 {
 140         int i;
 141
 142         for (i = 0; i < hash->table_size; i++) {
 143                 Slot *s;
 144
 145                 for (s = hash->table [i]; s != NULL; s = s->next){
 146                         guint hashcode = (*hash->hash_func) (s->key);
 147                         guint slot = (hashcode) % hash->table_size;
 148                         printf ("key %p hash %x on slot %d correct slot %d tb size %d\n", s->key, hashcode, i, slot, hash->table_size);
 149                 }
 150         }
 151 }
 152 #endif
 153
 154 #ifdef SANITY_CHECK
 155 static void
 156 sanity_check (GHashTable *hash)
 157 {
 158         int i;
 159
 160         for (i = 0; i < hash->table_size; i++) {
 161                 Slot *s;
 162
 163                 for (s = hash->table [i]; s != NULL; s = s->next){
 164                         guint hashcode = (*hash->hash_func) (s->key);
 165                         guint slot = (hashcode) % hash->table_size;
 166                         if (slot != i) {
 167                                 dump_hashcode_func = 1;
 168                                 hashcode = (*hash->hash_func) (s->key);
 169                                 dump_hashcode_func = 0;
 170                                 g_error ("Key %p (bucket %d) on invalid bucket %d (hashcode %x) (tb size %d)", s->key, slot, i, hashcode, hash->table_size);
 171                         }
 172                 }
 173         }
 174 }
 175 #else
 176
 177 #define sanity_check(HASH) do {}while(0)
 178
 179 #endif
 180
 181 static void
 182 do_rehash (GHashTable *hash)
 183 {
 184         int current_size, i;
 185         Slot **table;
 186
 187         /* printf ("Resizing diff=%d slots=%d\n", hash->in_use - hash->last_rehash, hash->table_size); */
 188         hash->last_rehash = hash->table_size;
 189         current_size = hash->table_size;
 190         hash->table_size = g_spaced_primes_closest (hash->in_use);
 191         /* printf ("New size: %d\n", hash->table_size); */
 192         table = hash->table;
 193         hash->table = g_new0 (Slot *, hash->table_size);
 194
 195         for (i = 0; i < current_size; i++){
 196                 Slot *s, *next;
 197
 198                 for (s = table [i]; s != NULL; s = next){
 199                         guint hashcode = ((*hash->hash_func) (s->key)) % hash->table_size;
 200                         next = s->next;
 201
 202                         s->next = hash->table [hashcode];
 203                         hash->table [hashcode] = s;
 204                 }
 205         }
 206         g_free (table);
 207 }
 208
 209 static void
 210 rehash (GHashTable *hash)
 211 {
 212         int diff = ABS (hash->last_rehash - hash->in_use);
 213
 214         /* These are the factors to play with to change the rehashing strategy */
 215         /* I played with them with a large range, and could not really get */
 216         /* something that was too good, maybe the tests are not that great */
 217         if (!(diff * 0.75 > hash->table_size * 2))
 218                 return;
 219         do_rehash (hash);
 220         sanity_check (hash);
 221 }
 222
 223 void
 224 g_hash_table_insert_replace (GHashTable *hash, gpointer key, gpointer value, gboolean replace)
 225 {
 226         guint hashcode;
 227         Slot *s;
 228         GEqualFunc equal;
 229
 230         g_return_if_fail (hash != NULL);
 231         sanity_check (hash);
 232
 233         equal = hash->key_equal_func;
 234         if (hash->in_use >= hash->threshold)
 235                 rehash (hash);
 236
 237         hashcode = ((*hash->hash_func) (key)) % hash->table_size;
 238         for (s = hash->table [hashcode]; s != NULL; s = s->next){
 239                 if ((*equal) (s->key, key)){
 240                         if (replace){
 241                                 if (hash->key_destroy_func != NULL)
 242                                         (*hash->key_destroy_func)(s->key);
 243                                 s->key = key;
 244                         }
 245                         if (hash->value_destroy_func != NULL)
 246                                 (*hash->value_destroy_func) (s->value);
 247                         s->value = value;
 248                         sanity_check (hash);
 249                         return;
 250                 }
 251         }
 252         s = g_new (Slot, 1);
 253         s->key = key;
 254         s->value = value;
 255         s->next = hash->table [hashcode];
 256         hash->table [hashcode] = s;
 257         hash->in_use++;
 258         sanity_check (hash);
 259 }
 260
 261 guint
 262 g_hash_table_size (GHashTable *hash)
 263 {
 264         g_return_val_if_fail (hash != NULL, 0);
 265
 266         return hash->in_use;
 267 }
 268
 269 gpointer
 270 g_hash_table_lookup (GHashTable *hash, gconstpointer key)
 271 {
 272         gpointer orig_key, value;
 273
 274         if (g_hash_table_lookup_extended (hash, key, &orig_key, &value))
 275                 return value;
 276         else
 277                 return NULL;
 278 }
 279
 280 gboolean
 281 g_hash_table_lookup_extended (GHashTable *hash, gconstpointer key, gpointer *orig_key, gpointer *value)
 282 {
 283         GEqualFunc equal;
 284         Slot *s;
 285         guint hashcode;
 286
 287         g_return_val_if_fail (hash != NULL, FALSE);
 288         sanity_check (hash);
 289         equal = hash->key_equal_func;
 290
 291         hashcode = ((*hash->hash_func) (key)) % hash->table_size;
 292
 293         for (s = hash->table [hashcode]; s != NULL; s = s->next){
 294                 if ((*equal)(s->key, key)){
 295                         *orig_key = s->key;
 296                         *value = s->value;
 297                         return TRUE;
 298                 }
 299         }
 300         return FALSE;
 301 }
 302
 303 void
 304 g_hash_table_foreach (GHashTable *hash, GHFunc func, gpointer user_data)
 305 {
 306         int i;
 307
 308         g_return_if_fail (hash != NULL);
 309         g_return_if_fail (func != NULL);
 310
 311         for (i = 0; i < hash->table_size; i++){
 312                 Slot *s;
 313
 314                 for (s = hash->table [i]; s != NULL; s = s->next)
 315                         (*func)(s->key, s->value, user_data);
 316         }
 317 }
 318
 319 gpointer
 320 g_hash_table_find (GHashTable *hash, GHRFunc predicate, gpointer user_data)
 321 {
 322         int i;
 323
 324         g_return_val_if_fail (hash != NULL, NULL);
 325         g_return_val_if_fail (predicate != NULL, NULL);
 326
 327         for (i = 0; i < hash->table_size; i++){
 328                 Slot *s;
 329
 330                 for (s = hash->table [i]; s != NULL; s = s->next)
 331                         if ((*predicate)(s->key, s->value, user_data))
 332                                 return s->value;
 333         }
 334         return NULL;
 335 }
 336
 337 void
 338 g_hash_table_remove_all (GHashTable *hash)
 339 {
 340         int i;
 341
 342         g_return_if_fail (hash != NULL);
 343
 344         for (i = 0; i < hash->table_size; i++){
 345                 Slot *s;
 346
 347                 for (s = hash->table [i]; s != NULL; s = s->next)
 348                         g_hash_table_remove (hash, s->key);
 349         }
 350 }
 351
 352 gboolean
 353 g_hash_table_remove (GHashTable *hash, gconstpointer key)
 354 {
 355         GEqualFunc equal;
 356         Slot *s, *last;
 357         guint hashcode;
 358
 359         g_return_val_if_fail (hash != NULL, FALSE);
 360         sanity_check (hash);
 361         equal = hash->key_equal_func;
 362
 363         hashcode = ((*hash->hash_func)(key)) % hash->table_size;
 364         last = NULL;
 365         for (s = hash->table [hashcode]; s != NULL; s = s->next){
 366                 if ((*equal)(s->key, key)){
 367                         if (hash->key_destroy_func != NULL)
 368                                 (*hash->key_destroy_func)(s->key);
 369                         if (hash->value_destroy_func != NULL)
 370                                 (*hash->value_destroy_func)(s->value);
 371                         if (last == NULL)
 372                                 hash->table [hashcode] = s->next;
 373                         else
 374                                 last->next = s->next;
 375                         g_free (s);
 376                         hash->in_use--;
 377                         sanity_check (hash);
 378                         return TRUE;
 379                 }
 380                 last = s;
 381         }
 382         sanity_check (hash);
 383         return FALSE;
 384 }
 385
 386 guint
 387 g_hash_table_foreach_remove (GHashTable *hash, GHRFunc func, gpointer user_data)
 388 {
 389         int i;
 390         int count = 0;
 391
 392         g_return_val_if_fail (hash != NULL, 0);
 393         g_return_val_if_fail (func != NULL, 0);
 394
 395         sanity_check (hash);
 396         for (i = 0; i < hash->table_size; i++){
 397                 Slot *s, *last;
 398
 399                 last = NULL;
 400                 for (s = hash->table [i]; s != NULL; ){
 401                         if ((*func)(s->key, s->value, user_data)){
 402                                 Slot *n;
 403
 404                                 if (hash->key_destroy_func != NULL)
 405                                         (*hash->key_destroy_func)(s->key);
 406                                 if (hash->value_destroy_func != NULL)
 407                                         (*hash->value_destroy_func)(s->value);
 408                                 if (last == NULL){
 409                                         hash->table [i] = s->next;
 410                                         n = s->next;
 411                                 } else  {
 412                                         last->next = s->next;
 413                                         n = last->next;
 414                                 }
 415                                 g_free (s);
 416                                 hash->in_use--;
 417                                 count++;
 418                                 s = n;
 419                         } else {
 420                                 last = s;
 421                                 s = s->next;
 422                         }
 423                 }
 424         }
 425         sanity_check (hash);
 426         if (count > 0)
 427                 rehash (hash);
 428         return count;
 429 }
 430
 431 guint
 432 g_hash_table_foreach_steal (GHashTable *hash, GHRFunc func, gpointer user_data)
 433 {
 434         int i;
 435         int count = 0;
 436
 437         g_return_val_if_fail (hash != NULL, 0);
 438         g_return_val_if_fail (func != NULL, 0);
 439
 440         sanity_check (hash);
 441         for (i = 0; i < hash->table_size; i++){
 442                 Slot *s, *last;
 443
 444                 last = NULL;
 445                 for (s = hash->table [i]; s != NULL; ){
 446                         if ((*func)(s->key, s->value, user_data)){
 447                                 Slot *n;
 448
 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 void
 473 g_hash_table_destroy (GHashTable *hash)
 474 {
 475         int i;
 476
 477         g_return_if_fail (hash != NULL);
 478
 479         for (i = 0; i < hash->table_size; i++){
 480                 Slot *s, *next;
 481
 482                 for (s = hash->table [i]; s != NULL; s = next){
 483                         next = s->next;
 484
 485                         if (hash->key_destroy_func != NULL)
 486                                 (*hash->key_destroy_func)(s->key);
 487                         if (hash->value_destroy_func != NULL)
 488                                 (*hash->value_destroy_func)(s->value);
 489                         g_free (s);
 490                 }
 491         }
 492         g_free (hash->table);
 493
 494         g_free (hash);
 495 }
 496
 497 void
 498 g_hash_table_print_stats (GHashTable *table)
 499 {
 500         int i, max_chain_index, chain_size, max_chain_size;
 501         Slot *node;
 502
 503         max_chain_size = 0;
 504         max_chain_index = -1;
 505         for (i = 0; i < table->table_size; i++) {
 506                 chain_size = 0;
 507                 for (node = table->table [i]; node; node = node->next)
 508                         chain_size ++;
 509                 if (chain_size > max_chain_size) {
 510                         max_chain_size = chain_size;
 511                         max_chain_index = i;
 512                 }
 513         }
 514
 515         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);
 516 }
 517
 518 gboolean
 519 g_direct_equal (gconstpointer v1, gconstpointer v2)
 520 {
 521         return v1 == v2;
 522 }
 523
 524 guint
 525 g_direct_hash (gconstpointer v1)
 526 {
 527         return GPOINTER_TO_UINT (v1);
 528 }
 529
 530 gboolean
 531 g_int_equal (gconstpointer v1, gconstpointer v2)
 532 {
 533         return GPOINTER_TO_INT (v1) == GPOINTER_TO_INT (v2);
 534 }
 535
 536 guint
 537 g_int_hash (gconstpointer v1)
 538 {
 539         return GPOINTER_TO_UINT(v1);
 540 }
 541
 542 gboolean
 543 g_str_equal (gconstpointer v1, gconstpointer v2)
 544 {
 545         return strcmp (v1, v2) == 0;
 546 }
 547
 548 guint
 549 g_str_hash (gconstpointer v1)
 550 {
 551         guint hash = 0;
 552         char *p = (char *) v1;
 553
 554         while (*p++)
 555                 hash = (hash << 5) - (hash + *p);
 556
 557         return hash;
 558 }