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