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 #ifdef HAVE_CONFIG_H
  32 #include <config.h>
  33 #endif
  34
  35 #include "glib.h"
  36
  37
  38 #define HASH_TABLE_MIN_SIZE 11
  39 #define HASH_TABLE_MAX_SIZE 13845163
  40
  41
  42 typedef struct _GHashNode      GHashNode;
  43
  44 struct _GHashNode
  45 {
  46   gpointer key;
  47   gpointer value;
  48   GHashNode *next;
  49 };
  50
  51 struct _GHashTable
  52 {
  53   gint size;
  54   gint nnodes;
  55   GHashNode **nodes;
  56   GHashFunc hash_func;
  57   GEqualFunc key_equal_func;
  58 };
  59
  60
  61 static void             g_hash_table_resize      (GHashTable    *hash_table);
  62 static GHashNode**      g_hash_table_lookup_node (GHashTable    *hash_table,
  63                                                   gconstpointer  key);
  64 static GHashNode*       g_hash_node_new          (gpointer       key,
  65                                                   gpointer       value);
  66 static void             g_hash_node_destroy      (GHashNode     *hash_node);
  67 static void             g_hash_nodes_destroy     (GHashNode     *hash_node);
  68
  69
  70 G_LOCK_DEFINE_STATIC (g_hash_global);
  71
  72 static GMemChunk *node_mem_chunk = NULL;
  73 static GHashNode *node_free_list = NULL;
  74
  75
  76 GHashTable*
  77 g_hash_table_new (GHashFunc    hash_func,
  78                   GEqualFunc   key_equal_func)
  79 {
  80   GHashTable *hash_table;
  81   guint i;
  82
  83   hash_table = g_new (GHashTable, 1);
  84   hash_table->size = HASH_TABLE_MIN_SIZE;
  85   hash_table->nnodes = 0;
  86   hash_table->hash_func = hash_func ? hash_func : g_direct_hash;
  87   hash_table->key_equal_func = key_equal_func;
  88   hash_table->nodes = g_new (GHashNode*, hash_table->size);
  89
  90   for (i = 0; i < hash_table->size; i++)
  91     hash_table->nodes[i] = NULL;
  92
  93   return hash_table;
  94 }
  95
  96 void
  97 g_hash_table_destroy (GHashTable *hash_table)
  98 {
  99   guint i;
 100
 101   g_return_if_fail (hash_table != NULL);
 102
 103   for (i = 0; i < hash_table->size; i++)
 104     g_hash_nodes_destroy (hash_table->nodes[i]);
 105
 106   g_free (hash_table->nodes);
 107   g_free (hash_table);
 108 }
 109
 110 static inline GHashNode**
 111 g_hash_table_lookup_node (GHashTable    *hash_table,
 112                           gconstpointer  key)
 113 {
 114   GHashNode **node;
 115
 116   node = &hash_table->nodes
 117     [(* hash_table->hash_func) (key) % hash_table->size];
 118
 119   /* Hash table lookup needs to be fast.
 120    *  We therefore remove the extra conditional of testing
 121    *  whether to call the key_equal_func or not from
 122    *  the inner loop.
 123    */
 124   if (hash_table->key_equal_func)
 125     while (*node && !(*hash_table->key_equal_func) ((*node)->key, key))
 126       node = &(*node)->next;
 127   else
 128     while (*node && (*node)->key != key)
 129       node = &(*node)->next;
 130
 131   return node;
 132 }
 133
 134 gpointer
 135 g_hash_table_lookup (GHashTable   *hash_table,
 136                      gconstpointer key)
 137 {
 138   GHashNode *node;
 139
 140   g_return_val_if_fail (hash_table != NULL, NULL);
 141
 142   node = *g_hash_table_lookup_node (hash_table, key);
 143
 144   return node ? node->value : NULL;
 145 }
 146
 147 void
 148 g_hash_table_insert (GHashTable *hash_table,
 149                      gpointer    key,
 150                      gpointer    value)
 151 {
 152   GHashNode **node;
 153
 154   g_return_if_fail (hash_table != NULL);
 155
 156   node = g_hash_table_lookup_node (hash_table, key);
 157
 158   if (*node)
 159     {
 160       /* do not reset node->key in this place, keeping
 161        * the old key might be intended.
 162        * a g_hash_table_remove/g_hash_table_insert pair
 163        * can be used otherwise.
 164        *
 165        * node->key = key; */
 166       (*node)->value = value;
 167     }
 168   else
 169     {
 170       *node = g_hash_node_new (key, value);
 171       hash_table->nnodes++;
 172       g_hash_table_resize (hash_table);
 173     }
 174 }
 175
 176 gboolean
 177 g_hash_table_remove (GHashTable   *hash_table,
 178                      gconstpointer key)
 179 {
 180   GHashNode **node, *dest;
 181
 182   g_return_val_if_fail (hash_table != NULL, FALSE);
 183
 184   node = g_hash_table_lookup_node (hash_table, key);
 185   if (*node)
 186     {
 187       dest = *node;
 188       (*node) = dest->next;
 189       g_hash_node_destroy (dest);
 190       hash_table->nnodes--;
 191
 192       g_hash_table_resize (hash_table);
 193
 194       return TRUE;
 195     }
 196
 197   return FALSE;
 198 }
 199
 200 gboolean
 201 g_hash_table_lookup_extended (GHashTable        *hash_table,
 202                               gconstpointer      lookup_key,
 203                               gpointer          *orig_key,
 204                               gpointer          *value)
 205 {
 206   GHashNode *node;
 207
 208   g_return_val_if_fail (hash_table != NULL, FALSE);
 209
 210   node = *g_hash_table_lookup_node (hash_table, lookup_key);
 211
 212   if (node)
 213     {
 214       if (orig_key)
 215         *orig_key = node->key;
 216       if (value)
 217         *value = node->value;
 218       return TRUE;
 219     }
 220   else
 221     return FALSE;
 222 }
 223
 224 void
 225 g_hash_table_freeze (GHashTable *hash_table)
 226 {
 227 #ifdef G_ENABLE_DEBUG
 228   static gboolean first_call = TRUE;
 229
 230   if (first_call)
 231     {
 232       g_warning("g_hash_table_freeze and g_hash_table_thaw are deprecated.");
 233       first_call = FALSE;
 234     }
 235 #endif /* G_ENABLE_DEBUG */
 236 }
 237
 238 void
 239 g_hash_table_thaw (GHashTable *hash_table)
 240 {
 241 }
 242
 243 guint
 244 g_hash_table_foreach_remove (GHashTable *hash_table,
 245                              GHRFunc     func,
 246                              gpointer    user_data)
 247 {
 248   GHashNode *node, *prev;
 249   guint i;
 250   guint deleted = 0;
 251
 252   g_return_val_if_fail (hash_table != NULL, 0);
 253   g_return_val_if_fail (func != NULL, 0);
 254
 255   for (i = 0; i < hash_table->size; i++)
 256     {
 257     restart:
 258
 259       prev = NULL;
 260
 261       for (node = hash_table->nodes[i]; node; prev = node, node = node->next)
 262         {
 263           if ((* func) (node->key, node->value, user_data))
 264             {
 265               deleted += 1;
 266
 267               hash_table->nnodes -= 1;
 268
 269               if (prev)
 270                 {
 271                   prev->next = node->next;
 272                   g_hash_node_destroy (node);
 273                   node = prev;
 274                 }
 275               else
 276                 {
 277                   hash_table->nodes[i] = node->next;
 278                   g_hash_node_destroy (node);
 279                   goto restart;
 280                 }
 281             }
 282         }
 283     }
 284
 285   g_hash_table_resize (hash_table);
 286
 287   return deleted;
 288 }
 289
 290 void
 291 g_hash_table_foreach (GHashTable *hash_table,
 292                       GHFunc      func,
 293                       gpointer    user_data)
 294 {
 295   GHashNode *node;
 296   gint i;
 297
 298   g_return_if_fail (hash_table != NULL);
 299   g_return_if_fail (func != NULL);
 300
 301   for (i = 0; i < hash_table->size; i++)
 302     for (node = hash_table->nodes[i]; node; node = node->next)
 303       (* func) (node->key, node->value, user_data);
 304 }
 305
 306 /* Returns the number of elements contained in the hash table. */
 307 guint
 308 g_hash_table_size (GHashTable *hash_table)
 309 {
 310   g_return_val_if_fail (hash_table != NULL, 0);
 311
 312   return hash_table->nnodes;
 313 }
 314
 315 static void
 316 g_hash_table_resize (GHashTable *hash_table)
 317 {
 318   GHashNode **new_nodes;
 319   GHashNode *node;
 320   GHashNode *next;
 321   gfloat nodes_per_list;
 322   guint hash_val;
 323   gint new_size;
 324   gint i;
 325
 326   nodes_per_list = (gfloat) hash_table->nnodes / (gfloat) hash_table->size;
 327
 328   if ((nodes_per_list > 0.3 || hash_table->size <= HASH_TABLE_MIN_SIZE) &&
 329       (nodes_per_list < 3.0 || hash_table->size >= HASH_TABLE_MAX_SIZE))
 330     return;
 331
 332   new_size = CLAMP(g_spaced_primes_closest (hash_table->nnodes),
 333                    HASH_TABLE_MIN_SIZE,
 334                    HASH_TABLE_MAX_SIZE);
 335   new_nodes = g_new0 (GHashNode*, new_size);
 336
 337   for (i = 0; i < hash_table->size; i++)
 338     for (node = hash_table->nodes[i]; node; node = next)
 339       {
 340         next = node->next;
 341
 342         hash_val = (* hash_table->hash_func) (node->key) % new_size;
 343
 344         node->next = new_nodes[hash_val];
 345         new_nodes[hash_val] = node;
 346       }
 347
 348   g_free (hash_table->nodes);
 349   hash_table->nodes = new_nodes;
 350   hash_table->size = new_size;
 351 }
 352
 353 static GHashNode*
 354 g_hash_node_new (gpointer key,
 355                  gpointer value)
 356 {
 357   GHashNode *hash_node;
 358
 359   G_LOCK (g_hash_global);
 360   if (node_free_list)
 361     {
 362       hash_node = node_free_list;
 363       node_free_list = node_free_list->next;
 364     }
 365   else
 366     {
 367       if (!node_mem_chunk)
 368         node_mem_chunk = g_mem_chunk_new ("hash node mem chunk",
 369                                           sizeof (GHashNode),
 370                                           1024, G_ALLOC_ONLY);
 371
 372       hash_node = g_chunk_new (GHashNode, node_mem_chunk);
 373     }
 374   G_UNLOCK (g_hash_global);
 375
 376   hash_node->key = key;
 377   hash_node->value = value;
 378   hash_node->next = NULL;
 379
 380   return hash_node;
 381 }
 382
 383 static void
 384 g_hash_node_destroy (GHashNode *hash_node)
 385 {
 386
 387 #ifdef ENABLE_GC_FRIENDLY
 388   hash_node->key = NULL;
 389   hash_node->value = NULL;
 390 #endif /* ENABLE_GC_FRIENDLY */
 391
 392   G_LOCK (g_hash_global);
 393   hash_node->next = node_free_list;
 394   node_free_list = hash_node;
 395   G_UNLOCK (g_hash_global);
 396 }
 397
 398 static void
 399 g_hash_nodes_destroy (GHashNode *hash_node)
 400 {
 401   if (hash_node)
 402     {
 403       GHashNode *node = hash_node;
 404
 405       while (node->next)
 406         {
 407 #ifdef ENABLE_GC_FRIENDLY
 408           node->key = NULL;
 409           node->value = NULL;
 410 #endif /* ENABLE_GC_FRIENDLY */
 411           node = node->next;
 412         }
 413
 414 #ifdef ENABLE_GC_FRIENDLY
 415       node->key = NULL;
 416       node->value = NULL;
 417 #endif /* ENABLE_GC_FRIENDLY */
 418
 419       G_LOCK (g_hash_global);
 420       node->next = node_free_list;
 421       node_free_list = hash_node;
 422       G_UNLOCK (g_hash_global);
 423     }
 424 }