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         GDestroyNotify value_destroy_func, key_destroy_func;
  51 };
  52
  53 static int prime_tbl[] = {
  54         11, 19, 37, 73, 109, 163, 251, 367, 557, 823, 1237,
  55         1861, 2777, 4177, 6247, 9371, 14057, 21089, 31627,
  56         47431, 71143, 106721, 160073, 240101, 360163,
  57         540217, 810343, 1215497, 1823231, 2734867, 4102283,
  58         6153409, 9230113, 13845163
  59 };
  60
  61 static gboolean
  62 test_prime (int x)
  63 {
  64         if ((x & 1) != 0) {
  65                 int n;
  66                 for (n = 3; n< (int)sqrt (x); n += 2) {
  67                         if ((x % n) == 0)
  68                                 return FALSE;
  69                 }
  70                 return TRUE;
  71         }
  72         // There is only one even prime - 2.
  73         return (x == 2);
  74 }
  75
  76 static int
  77 calc_prime (int x)
  78 {
  79         int i;
  80
  81         for (i = (x & (~1))-1; i< G_MAXINT32; i += 2) {
  82                 if (test_prime (i))
  83                         return i;
  84         }
  85         return x;
  86 }
  87
  88 static int
  89 to_prime (int x)
  90 {
  91         int i;
  92
  93         for (i = 0; i < G_N_ELEMENTS (prime_tbl); i++) {
  94                 if (x <= prime_tbl [i])
  95                         return prime_tbl [i];
  96         }
  97         return calc_prime (x);
  98 }
  99
 100 static void
 101 adjust_threshold (GHashTable *hash)
 102 {
 103         hash->threshold = (int) hash->table_size * 0.75;
 104         if (hash->threshold >= hash->table_size)
 105                 hash->threshold = hash->table_size-1;
 106         if (hash->threshold == 0)
 107                 hash->threshold = 1;
 108 }
 109
 110 GHashTable *
 111 g_hash_table_new (GHashFunc hash_func, GEqualFunc key_equal_func)
 112 {
 113         GHashTable *hash;
 114
 115         if (hash_func == NULL)
 116                 hash_func = g_direct_hash;
 117         if (key_equal_func == NULL)
 118                 key_equal_func = g_direct_equal;
 119         hash = g_new0 (GHashTable, 1);
 120
 121         hash->hash_func = hash_func;
 122         hash->key_equal_func = key_equal_func;
 123
 124         hash->table_size = to_prime (1);
 125         hash->table = g_new0 (Slot *, hash->table_size);
 126         adjust_threshold (hash);
 127
 128         return hash;
 129 }
 130
 131 GHashTable *
 132 g_hash_table_new_full (GHashFunc hash_func, GEqualFunc key_equal_func,
 133                        GDestroyNotify key_destroy_func, GDestroyNotify value_destroy_func)
 134 {
 135         GHashTable *hash = g_hash_table_new (hash_func, key_equal_func);
 136         if (hash == NULL)
 137                 return NULL;
 138
 139         hash->key_destroy_func = key_destroy_func;
 140         hash->value_destroy_func = value_destroy_func;
 141
 142         return hash;
 143 }
 144
 145 void
 146 rehash (GHashTable *hash)
 147 {
 148         /* FIXME */
 149 }
 150
 151 void
 152 g_hash_table_insert_replace (GHashTable *hash, gpointer key, gpointer value, gboolean replace)
 153 {
 154         guint hashcode;
 155         Slot *s;
 156         GEqualFunc equal;
 157
 158         g_return_if_fail (hash != NULL);
 159
 160         equal = hash->key_equal_func;
 161         if (hash->in_use >= hash->threshold)
 162                 rehash (hash);
 163
 164         hashcode = ((*hash->hash_func) (key)) % hash->table_size;
 165         for (s = hash->table [hashcode]; s != NULL; s = s->next){
 166                 if ((*equal) (s->key, key)){
 167                         if (replace){
 168                                 if (hash->key_destroy_func != NULL)
 169                                         (*hash->key_destroy_func)(s->key);
 170                                 s->key = key;
 171                         }
 172                         if (hash->value_destroy_func != NULL)
 173                                 (*hash->value_destroy_func) (s->value);
 174                         s->value = value;
 175                         return;
 176                 }
 177         }
 178         s = g_new (Slot, 1);
 179         s->key = key;
 180         s->value = value;
 181         s->next = hash->table [hashcode];
 182         hash->table [hashcode] = s;
 183         hash->in_use++;
 184 }
 185
 186 guint
 187 g_hash_table_size (GHashTable *hash)
 188 {
 189         g_return_val_if_fail (hash != NULL, 0);
 190
 191         return hash->in_use;
 192 }
 193
 194 gpointer
 195 g_hash_table_lookup (GHashTable *hash, gconstpointer key)
 196 {
 197         gpointer orig_key, value;
 198
 199         if (g_hash_table_lookup_extended (hash, key, &orig_key, &value))
 200                 return value;
 201         else
 202                 return NULL;
 203 }
 204
 205 gboolean
 206 g_hash_table_lookup_extended (GHashTable *hash, gconstpointer key, gpointer *orig_key, gpointer *value)
 207 {
 208         GEqualFunc equal;
 209         Slot *s;
 210         guint hashcode;
 211
 212         g_return_val_if_fail (hash != NULL, FALSE);
 213         equal = hash->key_equal_func;
 214
 215         hashcode = ((*hash->hash_func) (key)) % hash->table_size;
 216
 217         for (s = hash->table [hashcode]; s != NULL; s = s->next){
 218                 if ((*equal)(s->key, key)){
 219                         *orig_key = s->key;
 220                         *value = s->value;
 221                         return TRUE;
 222                 }
 223         }
 224         return FALSE;
 225 }
 226
 227 void
 228 g_hash_table_foreach (GHashTable *hash, GHFunc func, gpointer user_data)
 229 {
 230         int i;
 231
 232         g_return_if_fail (hash != NULL);
 233         g_return_if_fail (func != NULL);
 234
 235         for (i = 0; i < hash->table_size; i++){
 236                 Slot *s;
 237
 238                 for (s = hash->table [i]; s != NULL; s = s->next)
 239                         (*func)(s->key, s->value, user_data);
 240         }
 241 }
 242
 243 gpointer
 244 g_hash_table_find (GHashTable *hash, GHRFunc predicate, gpointer user_data)
 245 {
 246         int i;
 247
 248         g_return_val_if_fail (hash != NULL, NULL);
 249         g_return_val_if_fail (predicate != NULL, NULL);
 250
 251         for (i = 0; i < hash->table_size; i++){
 252                 Slot *s;
 253
 254                 for (s = hash->table [i]; s != NULL; s = s->next)
 255                         if ((*predicate)(s->key, s->value, user_data))
 256                                 return s->value;
 257         }
 258         return NULL;
 259 }
 260
 261 gboolean
 262 g_hash_table_remove (GHashTable *hash, gconstpointer key)
 263 {
 264         GEqualFunc equal;
 265         Slot *s, *last;
 266         guint hashcode;
 267
 268         g_return_val_if_fail (hash != NULL, FALSE);
 269         equal = hash->key_equal_func;
 270
 271         hashcode = ((*hash->hash_func)(key)) % hash->table_size;
 272         last = NULL;
 273         for (s = hash->table [hashcode]; s != NULL; s = s->next){
 274                 if ((*equal)(s->key, key)){
 275                         if (hash->key_destroy_func != NULL)
 276                                 (*hash->key_destroy_func)(s->key);
 277                         if (hash->value_destroy_func != NULL)
 278                                 (*hash->value_destroy_func)(s->value);
 279                         if (last == NULL)
 280                                 hash->table [hashcode] = s->next;
 281                         else
 282                                 last->next = s->next;
 283                         g_free (s);
 284                         hash->in_use--;
 285                         return TRUE;
 286                 }
 287                 last = s;
 288         }
 289         return FALSE;
 290 }
 291
 292 guint
 293 g_hash_table_foreach_remove (GHashTable *hash, GHRFunc func, gpointer user_data)
 294 {
 295         int i;
 296         int count = 0;
 297
 298         g_return_val_if_fail (hash != NULL, 0);
 299         g_return_val_if_fail (func != NULL, 0);
 300
 301         for (i = 0; i < hash->table_size; i++){
 302                 Slot *s, *last;
 303
 304                 last = NULL;
 305                 for (s = hash->table [i]; s != NULL; ){
 306                         if ((*func)(s->key, s->value, user_data)){
 307                                 Slot *n;
 308
 309                                 if (hash->key_destroy_func != NULL)
 310                                         (*hash->key_destroy_func)(s->key);
 311                                 if (hash->value_destroy_func != NULL)
 312                                         (*hash->value_destroy_func)(s->value);
 313                                 if (last == NULL){
 314                                         hash->table [i] = s->next;
 315                                         n = s->next;
 316                                 } else  {
 317                                         last->next = s->next;
 318                                         n = last->next;
 319                                 }
 320                                 g_free (s);
 321                                 hash->in_use--;
 322                                 count++;
 323                                 s = n;
 324                         } else {
 325                                 last = s;
 326                                 s = s->next;
 327                         }
 328                 }
 329         }
 330         if (count > 0)
 331                 rehash (hash);
 332         return count;
 333 }
 334
 335 void
 336 g_hash_table_destroy (GHashTable *hash)
 337 {
 338         int i;
 339
 340         g_return_if_fail (hash != NULL);
 341
 342         for (i = 0; i < hash->table_size; i++){
 343                 Slot *s, *next;
 344
 345                 for (s = hash->table [i]; s != NULL; s = next){
 346                         next = s->next;
 347
 348                         if (hash->key_destroy_func != NULL)
 349                                 (*hash->key_destroy_func)(s->key);
 350                         if (hash->value_destroy_func != NULL)
 351                                 (*hash->value_destroy_func)(s->value);
 352                         g_free (s);
 353                 }
 354         }
 355         g_free (hash->table);
 356
 357         g_free (hash);
 358 }
 359
 360 gboolean
 361 g_direct_equal (gconstpointer v1, gconstpointer v2)
 362 {
 363         return v1 == v2;
 364 }
 365
 366 guint
 367 g_direct_hash (gconstpointer v1)
 368 {
 369         return GPOINTER_TO_UINT (v1);
 370 }
 371
 372 gboolean
 373 g_int_equal (gconstpointer v1, gconstpointer v2)
 374 {
 375         return GPOINTER_TO_INT (v1) == GPOINTER_TO_INT (v2);
 376 }
 377
 378 guint
 379 g_int_hash (gconstpointer v1)
 380 {
 381         return GPOINTER_TO_UINT(v1);
 382 }
 383
 384 gboolean
 385 g_str_equal (gconstpointer v1, gconstpointer v2)
 386 {
 387         return strcmp (v1, v2) == 0;
 388 }
 389
 390 guint
 391 g_str_hash (gconstpointer v1)
 392 {
 393         guint hash = 0;
 394         char *p = (char *) v1;
 395
 396         while (*p++)
 397                 hash = (hash << 5) - (hash + *p);
 398
 399         return hash;
 400 }