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  * Modified by the GLib Team and others 1997-1999.  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   guint frozen;
  52   GHashNode **nodes;
  53   GHashFunc hash_func;
  54   GCompareFunc key_compare_func;
  55 };
  56
  57
  58 static void             g_hash_table_resize      (GHashTable    *hash_table);
  59 static GHashNode**      g_hash_table_lookup_node (GHashTable    *hash_table,
  60                                                   gconstpointer  key);
  61 static GHashNode*       g_hash_node_new          (gpointer       key,
  62                                                   gpointer       value);
  63 static void             g_hash_node_destroy      (GHashNode     *hash_node);
  64 static void             g_hash_nodes_destroy     (GHashNode     *hash_node);
  65
  66
  67 G_LOCK_DEFINE_STATIC (g_hash_global);
  68
  69 static GMemChunk *node_mem_chunk = NULL;
  70 static GHashNode *node_free_list = NULL;
  71
  72
  73 GHashTable*
  74 g_hash_table_new (GHashFunc    hash_func,
  75                   GCompareFunc key_compare_func)
  76 {
  77   GHashTable *hash_table;
  78   guint i;
  79
  80   hash_table = g_new (GHashTable, 1);
  81   hash_table->size = HASH_TABLE_MIN_SIZE;
  82   hash_table->nnodes = 0;
  83   hash_table->frozen = FALSE;
  84   hash_table->hash_func = hash_func ? hash_func : g_direct_hash;
  85   hash_table->key_compare_func = key_compare_func;
  86   hash_table->nodes = g_new (GHashNode*, hash_table->size);
  87
  88   for (i = 0; i < hash_table->size; i++)
  89     hash_table->nodes[i] = NULL;
  90
  91   return hash_table;
  92 }
  93
  94 void
  95 g_hash_table_destroy (GHashTable *hash_table)
  96 {
  97   guint i;
  98
  99   g_return_if_fail (hash_table != NULL);
 100
 101   for (i = 0; i < hash_table->size; i++)
 102     g_hash_nodes_destroy (hash_table->nodes[i]);
 103
 104   g_free (hash_table->nodes);
 105   g_free (hash_table);
 106 }
 107
 108 static inline GHashNode**
 109 g_hash_table_lookup_node (GHashTable    *hash_table,
 110                           gconstpointer  key)
 111 {
 112   GHashNode **node;
 113
 114   node = &hash_table->nodes
 115     [(* hash_table->hash_func) (key) % hash_table->size];
 116
 117   /* Hash table lookup needs to be fast.
 118    *  We therefore remove the extra conditional of testing
 119    *  whether to call the key_compare_func or not from
 120    *  the inner loop.
 121    */
 122   if (hash_table->key_compare_func)
 123     while (*node && !(*hash_table->key_compare_func) ((*node)->key, key))
 124       node = &(*node)->next;
 125   else
 126     while (*node && (*node)->key != key)
 127       node = &(*node)->next;
 128
 129   return node;
 130 }
 131
 132 gpointer
 133 g_hash_table_lookup (GHashTable   *hash_table,
 134                      gconstpointer key)
 135 {
 136   GHashNode *node;
 137
 138   g_return_val_if_fail (hash_table != NULL, NULL);
 139
 140   node = *g_hash_table_lookup_node (hash_table, key);
 141
 142   return node ? node->value : NULL;
 143 }
 144
 145 void
 146 g_hash_table_insert (GHashTable *hash_table,
 147                      gpointer    key,
 148                      gpointer    value)
 149 {
 150   GHashNode **node;
 151
 152   g_return_if_fail (hash_table != NULL);
 153
 154   node = g_hash_table_lookup_node (hash_table, key);
 155
 156   if (*node)
 157     {
 158       /* do not reset node->key in this place, keeping
 159        * the old key might be intended.
 160        * a g_hash_table_remove/g_hash_table_insert pair
 161        * can be used otherwise.
 162        *
 163        * node->key = key; */
 164       (*node)->value = value;
 165     }
 166   else
 167     {
 168       *node = g_hash_node_new (key, value);
 169       hash_table->nnodes++;
 170       if (!hash_table->frozen)
 171         g_hash_table_resize (hash_table);
 172     }
 173 }
 174
 175 void
 176 g_hash_table_remove (GHashTable      *hash_table,
 177                      gconstpointer    key)
 178 {
 179   GHashNode **node, *dest;
 180
 181   g_return_if_fail (hash_table != NULL);
 182
 183   node = g_hash_table_lookup_node (hash_table, key);
 184
 185   if (*node)
 186     {
 187       dest = *node;
 188       (*node) = dest->next;
 189       g_hash_node_destroy (dest);
 190       hash_table->nnodes--;
 191
 192       if (!hash_table->frozen)
 193         g_hash_table_resize (hash_table);
 194     }
 195 }
 196
 197 gboolean
 198 g_hash_table_lookup_extended (GHashTable        *hash_table,
 199                               gconstpointer      lookup_key,
 200                               gpointer          *orig_key,
 201                               gpointer          *value)
 202 {
 203   GHashNode *node;
 204
 205   g_return_val_if_fail (hash_table != NULL, FALSE);
 206
 207   node = *g_hash_table_lookup_node (hash_table, lookup_key);
 208
 209   if (node)
 210     {
 211       if (orig_key)
 212         *orig_key = node->key;
 213       if (value)
 214         *value = node->value;
 215       return TRUE;
 216     }
 217   else
 218     return FALSE;
 219 }
 220
 221 void
 222 g_hash_table_freeze (GHashTable *hash_table)
 223 {
 224   g_return_if_fail (hash_table != NULL);
 225
 226   hash_table->frozen++;
 227 }
 228
 229 void
 230 g_hash_table_thaw (GHashTable *hash_table)
 231 {
 232   g_return_if_fail (hash_table != NULL);
 233
 234   if (hash_table->frozen)
 235     if (!(--hash_table->frozen))
 236       g_hash_table_resize (hash_table);
 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   if (!hash_table->frozen)
 282     g_hash_table_resize (hash_table);
 283
 284   return deleted;
 285 }
 286
 287 void
 288 g_hash_table_foreach (GHashTable *hash_table,
 289                       GHFunc      func,
 290                       gpointer    user_data)
 291 {
 292   GHashNode *node;
 293   gint i;
 294
 295   g_return_if_fail (hash_table != NULL);
 296   g_return_if_fail (func != NULL);
 297
 298   for (i = 0; i < hash_table->size; i++)
 299     for (node = hash_table->nodes[i]; node; node = node->next)
 300       (* func) (node->key, node->value, user_data);
 301 }
 302
 303 /* Returns the number of elements contained in the hash table. */
 304 guint
 305 g_hash_table_size (GHashTable *hash_table)
 306 {
 307   g_return_val_if_fail (hash_table != NULL, 0);
 308
 309   return hash_table->nnodes;
 310 }
 311
 312 static void
 313 g_hash_table_resize (GHashTable *hash_table)
 314 {
 315   GHashNode **new_nodes;
 316   GHashNode *node;
 317   GHashNode *next;
 318   gfloat nodes_per_list;
 319   guint hash_val;
 320   gint new_size;
 321   gint i;
 322
 323   nodes_per_list = (gfloat) hash_table->nnodes / (gfloat) hash_table->size;
 324
 325   if ((nodes_per_list > 0.3 || hash_table->size <= HASH_TABLE_MIN_SIZE) &&
 326       (nodes_per_list < 3.0 || hash_table->size >= HASH_TABLE_MAX_SIZE))
 327     return;
 328
 329   new_size = CLAMP(g_spaced_primes_closest (hash_table->nnodes),
 330                    HASH_TABLE_MIN_SIZE,
 331                    HASH_TABLE_MAX_SIZE);
 332   new_nodes = g_new0 (GHashNode*, new_size);
 333
 334   for (i = 0; i < hash_table->size; i++)
 335     for (node = hash_table->nodes[i]; node; node = next)
 336       {
 337         next = node->next;
 338
 339         hash_val = (* hash_table->hash_func) (node->key) % new_size;
 340
 341         node->next = new_nodes[hash_val];
 342         new_nodes[hash_val] = node;
 343       }
 344
 345   g_free (hash_table->nodes);
 346   hash_table->nodes = new_nodes;
 347   hash_table->size = new_size;
 348 }
 349
 350 static GHashNode*
 351 g_hash_node_new (gpointer key,
 352                  gpointer value)
 353 {
 354   GHashNode *hash_node;
 355
 356   G_LOCK (g_hash_global);
 357   if (node_free_list)
 358     {
 359       hash_node = node_free_list;
 360       node_free_list = node_free_list->next;
 361     }
 362   else
 363     {
 364       if (!node_mem_chunk)
 365         node_mem_chunk = g_mem_chunk_new ("hash node mem chunk",
 366                                           sizeof (GHashNode),
 367                                           1024, G_ALLOC_ONLY);
 368
 369       hash_node = g_chunk_new (GHashNode, node_mem_chunk);
 370     }
 371   G_UNLOCK (g_hash_global);
 372
 373   hash_node->key = key;
 374   hash_node->value = value;
 375   hash_node->next = NULL;
 376
 377   return hash_node;
 378 }
 379
 380 static void
 381 g_hash_node_destroy (GHashNode *hash_node)
 382 {
 383   G_LOCK (g_hash_global);
 384   hash_node->next = node_free_list;
 385   node_free_list = hash_node;
 386   G_UNLOCK (g_hash_global);
 387 }
 388
 389 static void
 390 g_hash_nodes_destroy (GHashNode *hash_node)
 391 {
 392   if (hash_node)
 393     {
 394       GHashNode *node = hash_node;
 395
 396       while (node->next)
 397         node = node->next;
 398
 399       G_LOCK (g_hash_global);
 400       node->next = node_free_list;
 401       node_free_list = hash_node;
 402       G_UNLOCK (g_hash_global);
 403     }
 404 }