ghash.c

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