glib/ghash.c

   1 /* GLIB - Library of useful routines for C programming
   2  * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald
   3  * Copyright (C) 1999 The Free Software Foundation
   4  *
   5  * This library is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU Library General Public
   7  * License as published by the Free Software Foundation; either
   8  * version 2 of the License, or (at your option) any later version.
   9  *
  10  * This library is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  * Library General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU Library General Public
  16  * License along with this library; if not, write to the
  17  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  18  * Boston, MA 02111-1307, USA.
  19  */
  20
  21 /*
  22  * MT safe
  23  */
  24
  25 #include "glib.h"
  26
  27
  28 #define HASH_TABLE_MIN_SIZE 11
  29 #define HASH_TABLE_MAX_SIZE 13845163
  30
  31
  32 typedef struct _GHashNode      GHashNode;
  33
  34 struct _GHashNode
  35 {
  36   gpointer key;
  37   gpointer value;
  38   GHashNode *next;
  39 };
  40
  41 struct _GHashTable
  42 {
  43   gint size;
  44   gint nnodes;
  45   guint frozen;
  46   GHashNode **nodes;
  47   GHashFunc hash_func;
  48   GCompareFunc key_compare_func;
  49 };
  50
  51
  52 static void             g_hash_table_resize      (GHashTable    *hash_table);
  53 static GHashNode*       g_hash_table_lookup_node (GHashTable    *hash_table,
  54                                                   gconstpointer  key,
  55                                                   GHashNode    **last_p,
  56                                                   guint         *bucket_p);
  57 static GHashNode*       g_hash_node_new          (gpointer       key,
  58                                                   gpointer       value);
  59 static void             g_hash_node_destroy      (GHashNode     *hash_node);
  60 static void             g_hash_nodes_destroy     (GHashNode     *hash_node);
  61
  62 #define G_HASH_BUCKET(table,key) \
  63     ((* (table)->hash_func) (key) % (table)->size)
  64
  65 G_LOCK_DECLARE_STATIC (g_hash_global);
  66
  67 static GMemChunk *node_mem_chunk = NULL;
  68 static GHashNode *node_free_list = NULL;
  69
  70
  71 GHashTable*
  72 g_hash_table_new (GHashFunc    hash_func,
  73                   GCompareFunc key_compare_func)
  74 {
  75   GHashTable *hash_table;
  76   guint i;
  77
  78   hash_table = g_new (GHashTable, 1);
  79   hash_table->size = HASH_TABLE_MIN_SIZE;
  80   hash_table->nnodes = 0;
  81   hash_table->frozen = FALSE;
  82   hash_table->hash_func = hash_func ? hash_func : g_direct_hash;
  83   hash_table->key_compare_func = key_compare_func;
  84   hash_table->nodes = g_new (GHashNode*, hash_table->size);
  85
  86   for (i = 0; i < hash_table->size; i++)
  87     hash_table->nodes[i] = NULL;
  88
  89   return hash_table;
  90 }
  91
  92 void
  93 g_hash_table_destroy (GHashTable *hash_table)
  94 {
  95   guint i;
  96
  97   g_return_if_fail (hash_table != NULL);
  98
  99   for (i = 0; i < hash_table->size; i++)
 100     g_hash_nodes_destroy (hash_table->nodes[i]);
 101
 102   g_free (hash_table->nodes);
 103   g_free (hash_table);
 104 }
 105
 106 static inline GHashNode*
 107 g_hash_table_lookup_node (GHashTable     *hash_table,
 108                           gconstpointer   key,
 109                           GHashNode     **last_p,
 110                           guint         *bucket_p)
 111 {
 112   GHashNode *node, *last = NULL;
 113   guint bucket;
 114
 115   bucket = G_HASH_BUCKET (hash_table, key);
 116   node = hash_table->nodes [bucket];
 117
 118   /* Hash table lookup needs to be fast.
 119    *  We therefore remove the extra conditional of testing
 120    *  whether to call the key_compare_func or not from
 121    *  the inner loop.
 122    */
 123   if (hash_table->key_compare_func)
 124     while (node && !(*hash_table->key_compare_func) (node->key, key))
 125       {
 126         last = node;
 127         node = node->next;
 128       }
 129   else
 130     while (node && node->key != key)
 131       {
 132         last = node;
 133         node = node->next;
 134       }
 135
 136   if (last_p)
 137     *last_p = last;
 138   if (bucket_p)
 139     *bucket_p = bucket;
 140
 141   return node;
 142 }
 143
 144 gpointer
 145 g_hash_table_lookup (GHashTable   *hash_table,
 146                      gconstpointer key)
 147 {
 148   GHashNode *node;
 149
 150   g_return_val_if_fail (hash_table != NULL, NULL);
 151
 152   node = g_hash_table_lookup_node (hash_table, key, NULL, NULL);
 153
 154   return node ? node->value : NULL;
 155 }
 156
 157 void
 158 g_hash_table_insert (GHashTable *hash_table,
 159                      gpointer    key,
 160                      gpointer    value)
 161 {
 162   GHashNode *node, *last;
 163   guint bucket;
 164
 165   g_return_if_fail (hash_table != NULL);
 166
 167   node = g_hash_table_lookup_node (hash_table, key, &last, &bucket);
 168
 169   if (node == NULL)
 170     {
 171       node = g_hash_node_new (key, value);
 172
 173       if (last == NULL)
 174         hash_table->nodes [bucket] = node;
 175       else
 176         last->next = node;
 177
 178       hash_table->nnodes++;
 179       if (!hash_table->frozen)
 180         g_hash_table_resize (hash_table);
 181     }
 182   else
 183     {
 184       /* do not reset node->key in this place, keeping
 185        * the old key might be intended.
 186        * a g_hash_table_remove/g_hash_table_insert pair
 187        * can be used otherwise.
 188        *
 189        * node->key = key; */
 190       node->value = value;
 191     }
 192
 193 }
 194
 195 void
 196 g_hash_table_remove (GHashTable      *hash_table,
 197                      gconstpointer    key)
 198 {
 199   GHashNode *node, *last;
 200   guint bucket;
 201
 202   g_return_if_fail (hash_table != NULL);
 203
 204   node = g_hash_table_lookup_node (hash_table, key, &last, &bucket);
 205
 206   if (node)
 207     {
 208       if (last == NULL)
 209           hash_table->nodes [bucket] = node->next;
 210       else
 211           last->next = node->next;
 212
 213       g_hash_node_destroy (node);
 214
 215       hash_table->nnodes--;
 216
 217       if (!hash_table->frozen)
 218         g_hash_table_resize (hash_table);
 219     }
 220 }
 221
 222 gboolean
 223 g_hash_table_lookup_extended (GHashTable        *hash_table,
 224                               gconstpointer      lookup_key,
 225                               gpointer          *orig_key,
 226                               gpointer          *value)
 227 {
 228   GHashNode *node;
 229
 230   g_return_val_if_fail (hash_table != NULL, FALSE);
 231
 232   node = g_hash_table_lookup_node (hash_table, lookup_key, NULL, NULL);
 233
 234   if (node)
 235     {
 236       if (orig_key)
 237         *orig_key = node->key;
 238       if (value)
 239         *value = node->value;
 240       return TRUE;
 241     }
 242   else
 243     return FALSE;
 244 }
 245
 246 void
 247 g_hash_table_freeze (GHashTable *hash_table)
 248 {
 249   g_return_if_fail (hash_table != NULL);
 250
 251   hash_table->frozen++;
 252 }
 253
 254 void
 255 g_hash_table_thaw (GHashTable *hash_table)
 256 {
 257   g_return_if_fail (hash_table != NULL);
 258
 259   if (hash_table->frozen)
 260     if (!(--hash_table->frozen))
 261       g_hash_table_resize (hash_table);
 262 }
 263
 264 gint
 265 g_hash_table_foreach_remove (GHashTable *hash_table,
 266                              GHRFunc     func,
 267                              gpointer    user_data)
 268 {
 269   GHashNode *node, *prev;
 270   guint i;
 271   gint deleted = 0;
 272
 273   g_return_val_if_fail (hash_table != NULL, 0);
 274   g_return_val_if_fail (func != NULL, 0);
 275
 276   for (i = 0; i < hash_table->size; i++)
 277     {
 278     restart:
 279
 280       prev = NULL;
 281
 282       for (node = hash_table->nodes[i]; node; prev = node, node = node->next)
 283         {
 284           if ((* func) (node->key, node->value, user_data))
 285             {
 286               deleted += 1;
 287
 288               hash_table->nnodes -= 1;
 289
 290               if (prev)
 291                 {
 292                   prev->next = node->next;
 293                   g_hash_node_destroy (node);
 294                   node = prev;
 295                 }
 296               else
 297                 {
 298                   hash_table->nodes[i] = node->next;
 299                   g_hash_node_destroy (node);
 300                   goto restart;
 301                 }
 302             }
 303         }
 304     }
 305
 306   if (!hash_table->frozen)
 307     g_hash_table_resize (hash_table);
 308
 309   return deleted;
 310 }
 311
 312 void
 313 g_hash_table_foreach (GHashTable *hash_table,
 314                       GHFunc      func,
 315                       gpointer    user_data)
 316 {
 317   GHashNode *node;
 318   gint i;
 319
 320   g_return_if_fail (hash_table != NULL);
 321   g_return_if_fail (func != NULL);
 322
 323   for (i = 0; i < hash_table->size; i++)
 324     for (node = hash_table->nodes[i]; node; node = node->next)
 325       (* func) (node->key, node->value, user_data);
 326 }
 327
 328 /* Returns the number of elements contained in the hash table. */
 329 gint
 330 g_hash_table_size (GHashTable *hash_table)
 331 {
 332   g_return_val_if_fail (hash_table != NULL, 0);
 333
 334   return hash_table->nnodes;
 335 }
 336
 337 static void
 338 g_hash_table_resize (GHashTable *hash_table)
 339 {
 340   GHashNode **new_nodes;
 341   GHashNode *node;
 342   GHashNode *next;
 343   gfloat nodes_per_list;
 344   guint hash_val;
 345   gint new_size;
 346   gint i;
 347
 348   nodes_per_list = (gfloat) hash_table->nnodes / (gfloat) hash_table->size;
 349
 350   if ((nodes_per_list > 0.3 || hash_table->size <= HASH_TABLE_MIN_SIZE) &&
 351       (nodes_per_list < 3.0 || hash_table->size >= HASH_TABLE_MAX_SIZE))
 352     return;
 353
 354   new_size = CLAMP(g_spaced_primes_closest (hash_table->nnodes),
 355                    HASH_TABLE_MIN_SIZE,
 356                    HASH_TABLE_MAX_SIZE);
 357   new_nodes = g_new0 (GHashNode*, new_size);
 358
 359   for (i = 0; i < hash_table->size; i++)
 360     for (node = hash_table->nodes[i]; node; node = next)
 361       {
 362         next = node->next;
 363
 364         hash_val = (* hash_table->hash_func) (node->key) % new_size;
 365
 366         node->next = new_nodes[hash_val];
 367         new_nodes[hash_val] = node;
 368       }
 369
 370   g_free (hash_table->nodes);
 371   hash_table->nodes = new_nodes;
 372   hash_table->size = new_size;
 373 }
 374
 375 static GHashNode*
 376 g_hash_node_new (gpointer key,
 377                  gpointer value)
 378 {
 379   GHashNode *hash_node;
 380
 381   G_LOCK (g_hash_global);
 382   if (node_free_list)
 383     {
 384       hash_node = node_free_list;
 385       node_free_list = node_free_list->next;
 386     }
 387   else
 388     {
 389       if (!node_mem_chunk)
 390         node_mem_chunk = g_mem_chunk_new ("hash node mem chunk",
 391                                           sizeof (GHashNode),
 392                                           1024, G_ALLOC_ONLY);
 393
 394       hash_node = g_chunk_new (GHashNode, node_mem_chunk);
 395     }
 396   G_UNLOCK (g_hash_global);
 397
 398   hash_node->key = key;
 399   hash_node->value = value;
 400   hash_node->next = NULL;
 401
 402   return hash_node;
 403 }
 404
 405 static void
 406 g_hash_node_destroy (GHashNode *hash_node)
 407 {
 408   G_LOCK (g_hash_global);
 409   hash_node->next = node_free_list;
 410   node_free_list = hash_node;
 411   G_UNLOCK (g_hash_global);
 412 }
 413
 414 static void
 415 g_hash_nodes_destroy (GHashNode *hash_node)
 416 {
 417   if (hash_node)
 418     {
 419       GHashNode *node = hash_node;
 420
 421       while (node->next)
 422         node = node->next;
 423
 424       G_LOCK (g_hash_global);
 425       node->next = node_free_list;
 426       node_free_list = hash_node;
 427       G_UNLOCK (g_hash_global);
 428     }
 429 }