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_CHECKstatic void
 155 sanity_check (GHashTable *hash)
 156 {
 157         int i;
 158
 159         for (i = 0; i < hash->table_size; i++) {
 160                 Slot *s;
 161
 162                 for (s = hash->table [i]; s != NULL; s = s->next){
 163                         guint hashcode = (*hash->hash_func) (s->key);
 164                         guint slot = (hashcode) % hash->table_size;
 165                         if (slot != i) {
 166                                 dump_hashcode_func = 1;
 167                                 hashcode = (*hash->hash_func) (s->key);
 168                                 dump_hashcode_func = 0;
 169                                 g_error ("Key %p (bucket %d) on invalid bucket %d (hashcode %x) (tb size %d)", s->key, slot, i, hashcode, hash->table_size);
 170                         }
 171                 }
 172         }
 173 }
 174 #else
 175
 176 #define sanity_check(HASH) do {}while(0)
 177
 178 #endif
 179
 180 static void
 181 do_rehash (GHashTable *hash)
 182 {
 183         int current_size, i;
 184         Slot **table;
 185
 186         /* printf ("Resizing diff=%d slots=%d\n", hash->in_use - hash->last_rehash, hash->table_size); */
 187         hash->last_rehash = hash->table_size;
 188         current_size = hash->table_size;
 189         hash->table_size = g_spaced_primes_closest (hash->in_use);
 190         /* printf ("New size: %d\n", hash->table_size); */
 191         table = hash->table;
 192         hash->table = g_new0 (Slot *, hash->table_size);
 193
 194         for (i = 0; i < current_size; i++){
 195                 Slot *s, *next;
 196
 197                 for (s = table [i]; s != NULL; s = next){
 198                         guint hashcode = ((*hash->hash_func) (s->key)) % hash->table_size;
 199                         next = s->next;
 200
 201                         s->next = hash->table [hashcode];
 202                         hash->table [hashcode] = s;
 203                 }
 204         }
 205         g_free (table);
 206 }
 207
 208 static void
 209 rehash (GHashTable *hash)
 210 {
 211         int diff = ABS (hash->last_rehash - hash->in_use);
 212
 213         /* These are the factors to play with to change the rehashing strategy */
 214         /* I played with them with a large range, and could not really get */
 215         /* something that was too good, maybe the tests are not that great */
 216         if (!(diff * 0.75 > hash->table_size * 2))
 217                 return;
 218         do_rehash (hash);
 219         sanity_check (hash);
 220 }
 221
 222 void
 223 g_hash_table_insert_replace (GHashTable *hash, gpointer key, gpointer value, gboolean replace)
 224 {
 225         guint hashcode;
 226         Slot *s;
 227         GEqualFunc equal;
 228
 229         g_return_if_fail (hash != NULL);
 230         sanity_check (hash);
 231
 232         equal = hash->key_equal_func;
 233         if (hash->in_use >= hash->threshold)
 234                 rehash (hash);
 235
 236         hashcode = ((*hash->hash_func) (key)) % hash->table_size;
 237         for (s = hash->table [hashcode]; s != NULL; s = s->next){
 238                 if ((*equal) (s->key, key)){
 239                         if (replace){
 240                                 if (hash->key_destroy_func != NULL)
 241                                         (*hash->key_destroy_func)(s->key);
 242                                 s->key = key;
 243                         }
 244                         if (hash->value_destroy_func != NULL)
 245                                 (*hash->value_destroy_func) (s->value);
 246                         s->value = value;
 247                         sanity_check (hash);
 248                         return;
 249                 }
 250         }
 251         s = g_new (Slot, 1);
 252         s->key = key;
 253         s->value = value;
 254         s->next = hash->table [hashcode];
 255         hash->table [hashcode] = s;
 256         hash->in_use++;
 257         sanity_check (hash);
 258 }
 259
 260 guint
 261 g_hash_table_size (GHashTable *hash)
 262 {
 263         g_return_val_if_fail (hash != NULL, 0);
 264
 265         return hash->in_use;
 266 }
 267
 268 gpointer
 269 g_hash_table_lookup (GHashTable *hash, gconstpointer key)
 270 {
 271         gpointer orig_key, value;
 272
 273         if (g_hash_table_lookup_extended (hash, key, &orig_key, &value))
 274                 return value;
 275         else
 276                 return NULL;
 277 }
 278
 279 gboolean
 280 g_hash_table_lookup_extended (GHashTable *hash, gconstpointer key, gpointer *orig_key, gpointer *value)
 281 {
 282         GEqualFunc equal;
 283         Slot *s;
 284         guint hashcode;
 285
 286         g_return_val_if_fail (hash != NULL, FALSE);
 287         sanity_check (hash);
 288         equal = hash->key_equal_func;
 289
 290         hashcode = ((*hash->hash_func) (key)) % hash->table_size;
 291
 292         for (s = hash->table [hashcode]; s != NULL; s = s->next){
 293                 if ((*equal)(s->key, key)){
 294                         *orig_key = s->key;
 295                         *value = s->value;
 296                         return TRUE;
 297                 }
 298         }
 299         return FALSE;
 300 }
 301
 302 void
 303 g_hash_table_foreach (GHashTable *hash, GHFunc func, gpointer user_data)
 304 {
 305         int i;
 306
 307         g_return_if_fail (hash != NULL);
 308         g_return_if_fail (func != NULL);
 309
 310         for (i = 0; i < hash->table_size; i++){
 311                 Slot *s;
 312
 313                 for (s = hash->table [i]; s != NULL; s = s->next)
 314                         (*func)(s->key, s->value, user_data);
 315         }
 316 }
 317
 318 gpointer
 319 g_hash_table_find (GHashTable *hash, GHRFunc predicate, gpointer user_data)
 320 {
 321         int i;
 322
 323         g_return_val_if_fail (hash != NULL, NULL);
 324         g_return_val_if_fail (predicate != NULL, NULL);
 325
 326         for (i = 0; i < hash->table_size; i++){
 327                 Slot *s;
 328
 329                 for (s = hash->table [i]; s != NULL; s = s->next)
 330                         if ((*predicate)(s->key, s->value, user_data))
 331                                 return s->value;
 332         }
 333         return NULL;
 334 }
 335
 336 gboolean
 337 g_hash_table_remove (GHashTable *hash, gconstpointer key)
 338 {
 339         GEqualFunc equal;
 340         Slot *s, *last;
 341         guint hashcode;
 342
 343         g_return_val_if_fail (hash != NULL, FALSE);
 344         sanity_check (hash);
 345         equal = hash->key_equal_func;
 346
 347         hashcode = ((*hash->hash_func)(key)) % hash->table_size;
 348         last = NULL;
 349         for (s = hash->table [hashcode]; s != NULL; s = s->next){
 350                 if ((*equal)(s->key, key)){
 351                         if (hash->key_destroy_func != NULL)
 352                                 (*hash->key_destroy_func)(s->key);
 353                         if (hash->value_destroy_func != NULL)
 354                                 (*hash->value_destroy_func)(s->value);
 355                         if (last == NULL)
 356                                 hash->table [hashcode] = s->next;
 357                         else
 358                                 last->next = s->next;
 359                         g_free (s);
 360                         hash->in_use--;
 361                         sanity_check (hash);
 362                         return TRUE;
 363                 }
 364                 last = s;
 365         }
 366         sanity_check (hash);
 367         return FALSE;
 368 }
 369
 370 guint
 371 g_hash_table_foreach_remove (GHashTable *hash, GHRFunc func, gpointer user_data)
 372 {
 373         int i;
 374         int count = 0;
 375
 376         g_return_val_if_fail (hash != NULL, 0);
 377         g_return_val_if_fail (func != NULL, 0);
 378
 379         sanity_check (hash);
 380         for (i = 0; i < hash->table_size; i++){
 381                 Slot *s, *last;
 382
 383                 last = NULL;
 384                 for (s = hash->table [i]; s != NULL; ){
 385                         if ((*func)(s->key, s->value, user_data)){
 386                                 Slot *n;
 387
 388                                 if (hash->key_destroy_func != NULL)
 389                                         (*hash->key_destroy_func)(s->key);
 390                                 if (hash->value_destroy_func != NULL)
 391                                         (*hash->value_destroy_func)(s->value);
 392                                 if (last == NULL){
 393                                         hash->table [i] = s->next;
 394                                         n = s->next;
 395                                 } else  {
 396                                         last->next = s->next;
 397                                         n = last->next;
 398                                 }
 399                                 g_free (s);
 400                                 hash->in_use--;
 401                                 count++;
 402                                 s = n;
 403                         } else {
 404                                 last = s;
 405                                 s = s->next;
 406                         }
 407                 }
 408         }
 409         sanity_check (hash);
 410         if (count > 0)
 411                 rehash (hash);
 412         return count;
 413 }
 414
 415 guint
 416 g_hash_table_foreach_steal (GHashTable *hash, GHRFunc func, gpointer user_data)
 417 {
 418         int i;
 419         int count = 0;
 420
 421         g_return_val_if_fail (hash != NULL, 0);
 422         g_return_val_if_fail (func != NULL, 0);
 423
 424         sanity_check (hash);
 425         for (i = 0; i < hash->table_size; i++){
 426                 Slot *s, *last;
 427
 428                 last = NULL;
 429                 for (s = hash->table [i]; s != NULL; ){
 430                         if ((*func)(s->key, s->value, user_data)){
 431                                 Slot *n;
 432
 433                                 if (last == NULL){
 434                                         hash->table [i] = s->next;
 435                                         n = s->next;
 436                                 } else  {
 437                                         last->next = s->next;
 438                                         n = last->next;
 439                                 }
 440                                 g_free (s);
 441                                 hash->in_use--;
 442                                 count++;
 443                                 s = n;
 444                         } else {
 445                                 last = s;
 446                                 s = s->next;
 447                         }
 448                 }
 449         }
 450         sanity_check (hash);
 451         if (count > 0)
 452                 rehash (hash);
 453         return count;
 454 }
 455
 456 void
 457 g_hash_table_destroy (GHashTable *hash)
 458 {
 459         int i;
 460
 461         g_return_if_fail (hash != NULL);
 462
 463         for (i = 0; i < hash->table_size; i++){
 464                 Slot *s, *next;
 465
 466                 for (s = hash->table [i]; s != NULL; s = next){
 467                         next = s->next;
 468
 469                         if (hash->key_destroy_func != NULL)
 470                                 (*hash->key_destroy_func)(s->key);
 471                         if (hash->value_destroy_func != NULL)
 472                                 (*hash->value_destroy_func)(s->value);
 473                         g_free (s);
 474                 }
 475         }
 476         g_free (hash->table);
 477
 478         g_free (hash);
 479 }
 480
 481 gboolean
 482 g_direct_equal (gconstpointer v1, gconstpointer v2)
 483 {
 484         return v1 == v2;
 485 }
 486
 487 guint
 488 g_direct_hash (gconstpointer v1)
 489 {
 490         return GPOINTER_TO_UINT (v1);
 491 }
 492
 493 gboolean
 494 g_int_equal (gconstpointer v1, gconstpointer v2)
 495 {
 496         return GPOINTER_TO_INT (v1) == GPOINTER_TO_INT (v2);
 497 }
 498
 499 guint
 500 g_int_hash (gconstpointer v1)
 501 {
 502         return GPOINTER_TO_UINT(v1);
 503 }
 504
 505 gboolean
 506 g_str_equal (gconstpointer v1, gconstpointer v2)
 507 {
 508         return strcmp (v1, v2) == 0;
 509 }
 510
 511 guint
 512 g_str_hash (gconstpointer v1)
 513 {
 514         guint hash = 0;
 515         char *p = (char *) v1;
 516
 517         while (*p++)
 518                 hash = (hash << 5) - (hash + *p);
 519
 520         return hash;
 521 }