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