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  * NOTES:
  29  *
  30  *   In addition to supporting the standard g_hash_table behavior,
  31  *   this version adds support for providing a malloc/free set of
  32  *   routines, these by default are malloc and free, but with a GC,
  33  *   they could be GC_malloc and the free routine could be NULL.  If
  34  *   the value for free is NULL, we set all the fields that we would
  35  *   have otherwise released to NULL, to assist the garbage collector.
  36  *
  37  *   This is designed to support the GC-aware hashtable that Mono uses,
  38  *   and replaces mono-hash.c.   To do this, a new constructor is introduced
  39  *   that contains the extra parameters.
  40  */
  41 #include <stdio.h>
  42 #include <math.h>
  43 #include <glib.h>
  44
  45 typedef struct _Slot Slot;
  46
  47 struct _Slot {
  48         gpointer key;
  49         gpointer value;
  50         Slot    *next;
  51 };
  52
  53 static gpointer KEYMARKER_REMOVED = &KEYMARKER_REMOVED;
  54
  55 struct _GHashTable {
  56         GHashFunc      hash_func;
  57         GEqualFunc     key_equal_func;
  58
  59         Slot **table;
  60         int   table_size;
  61         int   in_use;
  62         int   threshold;
  63         int   last_rehash;
  64         GDestroyNotify value_destroy_func, key_destroy_func;
  65         GMFree  freefn;
  66         GMAlloc allocfn;
  67 };
  68
  69 static int prime_tbl[] = {
  70         11, 19, 37, 73, 109, 163, 251, 367, 557, 823, 1237,
  71         1861, 2777, 4177, 6247, 9371, 14057, 21089, 31627,
  72         47431, 71143, 106721, 160073, 240101, 360163,
  73         540217, 810343, 1215497, 1823231, 2734867, 4102283,
  74         6153409, 9230113, 13845163
  75 };
  76
  77 static gboolean
  78 test_prime (int x)
  79 {
  80         if ((x & 1) != 0) {
  81                 int n;
  82                 for (n = 3; n< (int)sqrt (x); n += 2) {
  83                         if ((x % n) == 0)
  84                                 return FALSE;
  85                 }
  86                 return TRUE;
  87         }
  88         // There is only one even prime - 2.
  89         return (x == 2);
  90 }
  91
  92 static int
  93 calc_prime (int x)
  94 {
  95         int i;
  96
  97         for (i = (x & (~1))-1; i< G_MAXINT32; i += 2) {
  98                 if (test_prime (i))
  99                         return i;
 100         }
 101         return x;
 102 }
 103
 104 static int
 105 to_prime (int x)
 106 {
 107         int i;
 108
 109         for (i = 0; i < G_N_ELEMENTS (prime_tbl); i++) {
 110                 if (x <= prime_tbl [i])
 111                         return prime_tbl [i];
 112         }
 113         return calc_prime (x);
 114 }
 115
 116 #undef g_new0
 117 static void *
 118 g_new0 (size_t t)
 119 {
 120         return calloc (1, t);
 121 }
 122
 123 GHashTable *
 124 g_hash_table_new (GHashFunc hash_func, GEqualFunc key_equal_func)
 125 {
 126         return g_hash_table_new_full_alloc (hash_func, key_equal_func, NULL, NULL, g_new0, free);
 127 }
 128
 129 GHashTable *
 130 g_hash_table_new_alloc (GHashFunc hash_func, GEqualFunc key_equal_func, GMAlloc allocfn, GMFree freefn)
 131 {
 132         return g_hash_table_new_full_alloc (hash_func, key_equal_func, NULL, NULL, allocfn, freefn);
 133 }
 134
 135
 136 GHashTable *
 137 g_hash_table_new_full (GHashFunc hash_func, GEqualFunc key_equal_func,
 138                        GDestroyNotify key_destroy_func, GDestroyNotify value_destroy_func)
 139 {
 140         return g_hash_table_new_full_alloc (hash_func, key_equal_func, key_destroy_func, value_destroy_func, g_new0, free);
 141 }
 142
 143 GHashTable *
 144 g_hash_table_new_full_alloc (GHashFunc hash_func, GEqualFunc key_equal_func,
 145                              GDestroyNotify key_destroy_func, GDestroyNotify value_destroy_func,
 146                              GMAlloc allocfn, GMFree freefn)
 147 {
 148         GHashTable *hash;
 149
 150         if (hash_func == NULL)
 151                 hash_func = g_direct_hash;
 152         if (key_equal_func == NULL)
 153                 key_equal_func = g_direct_equal;
 154
 155         hash = (*allocfn) (sizeof (GHashTable));
 156
 157         hash->hash_func = hash_func;
 158         hash->key_equal_func = key_equal_func;
 159         hash->key_destroy_func = key_destroy_func;
 160         hash->value_destroy_func = value_destroy_func;
 161         hash->table_size = to_prime (1);
 162         hash->table = (*allocfn) (sizeof (Slot *) * hash->table_size);
 163         hash->last_rehash = hash->table_size;
 164         hash->freefn = freefn;
 165         hash->allocfn = allocfn;
 166
 167         return hash;
 168 }
 169
 170 void
 171 do_rehash (GHashTable *hash)
 172 {
 173         int current_size, i;
 174         Slot **table;
 175
 176         /* printf ("Resizing diff=%d slots=%d\n", hash->in_use - hash->last_rehash, hash->table_size); */
 177         hash->last_rehash = hash->table_size;
 178         current_size = hash->table_size;
 179         hash->table_size = to_prime (hash->in_use);
 180         /* printf ("New size: %d\n", hash->table_size); */
 181         table = hash->table;
 182         hash->table = (*hash->allocfn)(sizeof (Slot *) * hash->table_size);
 183
 184         for (i = 0; i < current_size; i++){
 185                 Slot *s, *next;
 186
 187                 for (s = table [i]; s != NULL; s = next){
 188                         guint hashcode = ((*hash->hash_func) (s->key)) % hash->table_size;
 189                         next = s->next;
 190
 191                         s->next = hash->table [hashcode];
 192                         hash->table [hashcode] = s;
 193                 }
 194         }
 195         (*hash->freefn)(table);
 196 }
 197
 198 void
 199 rehash (GHashTable *hash)
 200 {
 201         int diff = ABS (hash->last_rehash, hash->in_use);
 202
 203         /* These are the factors to play with to change the rehashing strategy */
 204         /* I played with them with a large range, and could not really get */
 205         /* something that was too good, maybe the tests are not that great */
 206         if (!(diff * 0.75 > hash->table_size * 2))
 207                 return;
 208         do_rehash (hash);
 209 }
 210
 211 void
 212 g_hash_table_insert_replace (GHashTable *hash, gpointer key, gpointer value, gboolean replace)
 213 {
 214         guint hashcode;
 215         Slot *s;
 216         GEqualFunc equal;
 217
 218         g_return_if_fail (hash != NULL);
 219
 220         equal = hash->key_equal_func;
 221         if (hash->in_use >= hash->threshold)
 222                 rehash (hash);
 223
 224         hashcode = ((*hash->hash_func) (key)) % hash->table_size;
 225         for (s = hash->table [hashcode]; s != NULL; s = s->next){
 226                 if ((*equal) (s->key, key)){
 227                         if (replace){
 228                                 if (hash->key_destroy_func != NULL)
 229                                         (*hash->key_destroy_func)(s->key);
 230                                 s->key = key;
 231                         }
 232                         if (hash->value_destroy_func != NULL)
 233                                 (*hash->value_destroy_func) (s->value);
 234                         s->value = value;
 235                         return;
 236                 }
 237         }
 238         s = (*hash->allocfn) (sizeof (Slot));
 239         s->key = key;
 240         s->value = value;
 241         s->next = hash->table [hashcode];
 242         hash->table [hashcode] = s;
 243         hash->in_use++;
 244 }
 245
 246 guint
 247 g_hash_table_size (GHashTable *hash)
 248 {
 249         g_return_val_if_fail (hash != NULL, 0);
 250
 251         return hash->in_use;
 252 }
 253
 254 gpointer
 255 g_hash_table_lookup (GHashTable *hash, gconstpointer key)
 256 {
 257         gpointer orig_key, value;
 258
 259         if (g_hash_table_lookup_extended (hash, key, &orig_key, &value))
 260                 return value;
 261         else
 262                 return NULL;
 263 }
 264
 265 gboolean
 266 g_hash_table_lookup_extended (GHashTable *hash, gconstpointer key, gpointer *orig_key, gpointer *value)
 267 {
 268         GEqualFunc equal;
 269         Slot *s;
 270         guint hashcode;
 271
 272         g_return_val_if_fail (hash != NULL, FALSE);
 273         equal = hash->key_equal_func;
 274
 275         hashcode = ((*hash->hash_func) (key)) % hash->table_size;
 276
 277         for (s = hash->table [hashcode]; s != NULL; s = s->next){
 278                 if ((*equal)(s->key, key)){
 279                         *orig_key = s->key;
 280                         *value = s->value;
 281                         return TRUE;
 282                 }
 283         }
 284         return FALSE;
 285 }
 286
 287 void
 288 g_hash_table_foreach (GHashTable *hash, GHFunc func, gpointer user_data)
 289 {
 290         int i;
 291
 292         g_return_if_fail (hash != NULL);
 293         g_return_if_fail (func != NULL);
 294
 295         for (i = 0; i < hash->table_size; i++){
 296                 Slot *s;
 297
 298                 for (s = hash->table [i]; s != NULL; s = s->next)
 299                         (*func)(s->key, s->value, user_data);
 300         }
 301 }
 302
 303 gpointer
 304 g_hash_table_find (GHashTable *hash, GHRFunc predicate, gpointer user_data)
 305 {
 306         int i;
 307
 308         g_return_val_if_fail (hash != NULL, NULL);
 309         g_return_val_if_fail (predicate != NULL, 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                         if ((*predicate)(s->key, s->value, user_data))
 316                                 return s->value;
 317         }
 318         return NULL;
 319 }
 320
 321 gboolean
 322 g_hash_table_remove (GHashTable *hash, gconstpointer key)
 323 {
 324         GEqualFunc equal;
 325         Slot *s, *last;
 326         guint hashcode;
 327
 328         g_return_val_if_fail (hash != NULL, FALSE);
 329         equal = hash->key_equal_func;
 330
 331         hashcode = ((*hash->hash_func)(key)) % hash->table_size;
 332         last = NULL;
 333         for (s = hash->table [hashcode]; s != NULL; s = s->next){
 334                 if ((*equal)(s->key, key)){
 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 [hashcode] = s->next;
 341                         else
 342                                 last->next = s->next;
 343                         if (hash->freefn)
 344                                 (*hash->freefn) (s);
 345                         else {
 346                                 s->key = NULL;
 347                                 s->value = NULL;
 348                         }
 349                         hash->in_use--;
 350                         return TRUE;
 351                 }
 352                 last = s;
 353         }
 354         return FALSE;
 355 }
 356
 357 guint
 358 g_hash_table_foreach_remove (GHashTable *hash, GHRFunc func, gpointer user_data)
 359 {
 360         int i;
 361         int count = 0;
 362
 363         g_return_val_if_fail (hash != NULL, 0);
 364         g_return_val_if_fail (func != NULL, 0);
 365
 366         for (i = 0; i < hash->table_size; i++){
 367                 Slot *s, *last;
 368
 369                 last = NULL;
 370                 for (s = hash->table [i]; s != NULL; ){
 371                         if ((*func)(s->key, s->value, user_data)){
 372                                 Slot *n;
 373
 374                                 if (hash->key_destroy_func != NULL)
 375                                         (*hash->key_destroy_func)(s->key);
 376                                 if (hash->value_destroy_func != NULL)
 377                                         (*hash->value_destroy_func)(s->value);
 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                                 if (hash->freefn)
 386                                         (*hash->freefn)(s);
 387                                 else {
 388                                         s->key = NULL;
 389                                         s->value = NULL;
 390                                 }
 391
 392                                 hash->in_use--;
 393                                 count++;
 394                                 s = n;
 395                         } else {
 396                                 last = s;
 397                                 s = s->next;
 398                         }
 399                 }
 400         }
 401         if (count > 0)
 402                 rehash (hash);
 403         return count;
 404 }
 405
 406 void
 407 g_hash_table_destroy (GHashTable *hash)
 408 {
 409         int i;
 410
 411         g_return_if_fail (hash != NULL);
 412
 413         for (i = 0; i < hash->table_size; i++){
 414                 Slot *s, *next;
 415
 416                 for (s = hash->table [i]; s != NULL; s = next){
 417                         next = s->next;
 418
 419                         if (hash->key_destroy_func != NULL)
 420                                 (*hash->key_destroy_func)(s->key);
 421                         if (hash->value_destroy_func != NULL)
 422                                 (*hash->value_destroy_func)(s->value);
 423                         if (hash->freefn)
 424                                 (*hash->freefn)(s);
 425                         else {
 426                                 s->key = NULL;
 427                                 s->value = NULL;
 428                         }
 429                 }
 430         }
 431         if (hash->freefn){
 432                 (*hash->freefn) (hash->table);
 433                 (*hash->freefn) (hash);
 434         } else {
 435                 hash->table = NULL;
 436         }
 437 }
 438
 439 gboolean
 440 g_direct_equal (gconstpointer v1, gconstpointer v2)
 441 {
 442         return v1 == v2;
 443 }
 444
 445 guint
 446 g_direct_hash (gconstpointer v1)
 447 {
 448         return GPOINTER_TO_UINT (v1);
 449 }
 450
 451 gboolean
 452 g_int_equal (gconstpointer v1, gconstpointer v2)
 453 {
 454         return GPOINTER_TO_INT (v1) == GPOINTER_TO_INT (v2);
 455 }
 456
 457 guint
 458 g_int_hash (gconstpointer v1)
 459 {
 460         return GPOINTER_TO_UINT(v1);
 461 }
 462
 463 gboolean
 464 g_str_equal (gconstpointer v1, gconstpointer v2)
 465 {
 466         return strcmp (v1, v2) == 0;
 467 }
 468
 469 guint
 470 g_str_hash (gconstpointer v1)
 471 {
 472         guint hash = 0;
 473         char *p = (char *) v1;
 474
 475         while (*p++)
 476                 hash = (hash << 5) - (hash + *p);
 477
 478         return hash;
 479 }