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