ghash.c 8.39 KB
Newer Older
Owen Taylor's avatar
Owen Taylor committed
1 2 3 4 5 6 7 8 9 10
/* GLIB - Library of useful routines for C programming
 * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Library General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.	 See the GNU
Owen Taylor's avatar
Owen Taylor committed
12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
 * Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public
 * License along with this library; if not, write to the
 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 * Boston, MA 02111-1307, USA.
 */
#include "glib.h"


#define HASH_TABLE_MIN_SIZE 11
#define HASH_TABLE_MAX_SIZE 13845163


typedef struct _GHashNode      GHashNode;

struct _GHashNode
{
  gpointer key;
  gpointer value;
  GHashNode *next;
};

35
struct _GHashTable
Owen Taylor's avatar
Owen Taylor committed
36 37 38 39 40 41 42 43 44 45
{
  gint size;
  gint nnodes;
  gint frozen;
  GHashNode **nodes;
  GHashFunc hash_func;
  GCompareFunc key_compare_func;
};


46 47 48 49 50 51 52
static void		g_hash_table_resize	 (GHashTable	*hash_table);
static GHashNode**	g_hash_table_lookup_node (GHashTable	*hash_table,
						  gconstpointer	 key);
static GHashNode*	g_hash_node_new		 (gpointer	 key,
						  gpointer	 value);
static void		g_hash_node_destroy	 (GHashNode	*hash_node);
static void		g_hash_nodes_destroy	 (GHashNode	*hash_node);
Owen Taylor's avatar
Owen Taylor committed
53 54 55 56 57 58 59 60 61 62


static GMemChunk *node_mem_chunk = NULL;
static GHashNode *node_free_list = NULL;


GHashTable*
g_hash_table_new (GHashFunc    hash_func,
		  GCompareFunc key_compare_func)
{
63
  GHashTable *hash_table;
64 65
  guint i;
  
66 67
  hash_table = g_new (GHashTable, 1);
  hash_table->size = HASH_TABLE_MIN_SIZE;
Owen Taylor's avatar
Owen Taylor committed
68 69
  hash_table->nnodes = 0;
  hash_table->frozen = FALSE;
70
  hash_table->hash_func = hash_func ? hash_func : g_direct_hash;
Owen Taylor's avatar
Owen Taylor committed
71
  hash_table->key_compare_func = key_compare_func;
72
  hash_table->nodes = g_new (GHashNode*, hash_table->size);
73
  
74 75
  for (i = 0; i < hash_table->size; i++)
    hash_table->nodes[i] = NULL;
76
  
77
  return hash_table;
Owen Taylor's avatar
Owen Taylor committed
78 79 80 81 82
}

void
g_hash_table_destroy (GHashTable *hash_table)
{
83 84 85 86
  guint i;
  
  g_return_if_fail (hash_table != NULL);
  
87 88
  for (i = 0; i < hash_table->size; i++)
    g_hash_nodes_destroy (hash_table->nodes[i]);
89
  
90 91
  g_free (hash_table->nodes);
  g_free (hash_table);
Owen Taylor's avatar
Owen Taylor committed
92 93
}

94 95 96
static inline GHashNode**
g_hash_table_lookup_node (GHashTable	*hash_table,
			  gconstpointer	 key)
Owen Taylor's avatar
Owen Taylor committed
97
{
98
  GHashNode **node;
99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116
  
  node = &hash_table->nodes
    [(* hash_table->hash_func) (key) % hash_table->size];
  
  /* Hash table lookup needs to be fast.
   *  We therefore remove the extra conditional of testing
   *  whether to call the key_compare_func or not from
   *  the inner loop.
   */
  if (hash_table->key_compare_func)
    while (*node && !(*hash_table->key_compare_func) ((*node)->key, key))
      node = &(*node)->next;
  else
    while (*node && (*node)->key != key)
      node = &(*node)->next;
  
  return node;
}
Owen Taylor's avatar
Owen Taylor committed
117

118 119 120 121 122 123 124 125 126 127 128 129
gpointer
g_hash_table_lookup (GHashTable	  *hash_table,
		     gconstpointer key)
{
  GHashNode *node;
  
  g_return_val_if_fail (hash_table != NULL, NULL);
  
  node = *g_hash_table_lookup_node (hash_table, key);
  
  return node ? node->value : NULL;
}
130

131 132 133 134 135 136 137 138 139
void
g_hash_table_insert (GHashTable *hash_table,
		     gpointer	 key,
		     gpointer	 value)
{
  GHashNode **node;
  
  g_return_if_fail (hash_table != NULL);
  
140
  node = g_hash_table_lookup_node (hash_table, key);
141
  
142 143 144 145 146 147 148 149 150 151 152 153 154 155 156
  if (*node)
    {
      /* do not reset node->key in this place, keeping
       * the old key might be intended.
       * a g_hash_table_remove/g_hash_table_insert pair
       * can be used otherwise.
       *
       * node->key = key; */
      (*node)->value = value;
    }
  else
    {
      *node = g_hash_node_new (key, value);
      hash_table->nnodes++;
      if (!hash_table->frozen)
Owen Taylor's avatar
Owen Taylor committed
157 158 159 160 161
	g_hash_table_resize (hash_table);
    }
}

void
162
g_hash_table_remove (GHashTable	     *hash_table,
Owen Taylor's avatar
Owen Taylor committed
163 164
		     gconstpointer    key)
{
165
  GHashNode **node, *dest;
166 167 168
  
  g_return_if_fail (hash_table != NULL);
  
169
  while (*(node = g_hash_table_lookup_node (hash_table, key)))
Owen Taylor's avatar
Owen Taylor committed
170
    {
171 172 173 174
      dest = *node;
      (*node) = dest->next;
      g_hash_node_destroy (dest);
      hash_table->nnodes--;
Owen Taylor's avatar
Owen Taylor committed
175
    }
176
  
177 178
  if (!hash_table->frozen)
    g_hash_table_resize (hash_table);
Owen Taylor's avatar
Owen Taylor committed
179 180
}

181
gboolean
182 183 184 185
g_hash_table_lookup_extended (GHashTable	*hash_table,
			      gconstpointer	 lookup_key,
			      gpointer		*orig_key,
			      gpointer		*value)
186 187
{
  GHashNode *node;
188 189 190
  
  g_return_val_if_fail (hash_table != NULL, FALSE);
  
191
  node = *g_hash_table_lookup_node (hash_table, lookup_key);
192
  
193
  if (node)
Owen Taylor's avatar
Owen Taylor committed
194
    {
195 196 197 198 199
      if (orig_key)
	*orig_key = node->key;
      if (value)
	*value = node->value;
      return TRUE;
Owen Taylor's avatar
Owen Taylor committed
200
    }
201 202
  else
    return FALSE;
Owen Taylor's avatar
Owen Taylor committed
203 204 205 206 207
}

void
g_hash_table_freeze (GHashTable *hash_table)
{
208 209
  g_return_if_fail (hash_table != NULL);
  
210
  hash_table->frozen = TRUE;
Owen Taylor's avatar
Owen Taylor committed
211 212 213 214 215
}

void
g_hash_table_thaw (GHashTable *hash_table)
{
216 217
  g_return_if_fail (hash_table != NULL);
  
218
  hash_table->frozen = FALSE;
219
  
220
  g_hash_table_resize (hash_table);
Owen Taylor's avatar
Owen Taylor committed
221 222
}

223
gint
224 225 226
g_hash_table_foreach_remove (GHashTable	*hash_table,
			     GHRFunc	 func,
			     gpointer	 user_data)
227 228
{
  GHashNode *node, *prev;
229 230 231 232 233 234
  guint i;
  gint deleted = 0;
  
  g_return_val_if_fail (hash_table != NULL, 0);
  g_return_val_if_fail (func != NULL, 0);
  
235 236 237
  for (i = 0; i < hash_table->size; i++)
    {
    restart:
238
      
239
      prev = NULL;
240
      
241 242 243 244 245
      for (node = hash_table->nodes[i]; node; prev = node, node = node->next)
	{
	  if ((* func) (node->key, node->value, user_data))
	    {
	      deleted += 1;
246
	      
247
	      hash_table->nnodes -= 1;
248
	      
249 250 251 252 253 254 255 256 257 258 259 260 261 262 263
	      if (prev)
		{
		  prev->next = node->next;
		  g_hash_node_destroy (node);
		  node = prev;
		}
	      else
		{
		  hash_table->nodes[i] = node->next;
		  g_hash_node_destroy (node);
		  goto restart;
		}
	    }
	}
    }
264 265
  
  if (!hash_table->frozen)
266
    g_hash_table_resize (hash_table);
267
  
268 269 270
  return deleted;
}

Owen Taylor's avatar
Owen Taylor committed
271 272
void
g_hash_table_foreach (GHashTable *hash_table,
273 274
		      GHFunc	  func,
		      gpointer	  user_data)
Owen Taylor's avatar
Owen Taylor committed
275 276 277
{
  GHashNode *node;
  gint i;
278 279 280 281
  
  g_return_if_fail (hash_table != NULL);
  g_return_if_fail (func != NULL);
  
282 283 284
  for (i = 0; i < hash_table->size; i++)
    for (node = hash_table->nodes[i]; node; node = node->next)
      (* func) (node->key, node->value, user_data);
Owen Taylor's avatar
Owen Taylor committed
285 286
}

287
/* Returns the number of elements contained in the hash table. */
288 289
gint
g_hash_table_size (GHashTable *hash_table)
290
{
291 292
  g_return_val_if_fail (hash_table != NULL, 0);
  
293 294
  return hash_table->nnodes;
}
Owen Taylor's avatar
Owen Taylor committed
295 296 297 298 299 300 301 302 303 304 305

static void
g_hash_table_resize (GHashTable *hash_table)
{
  GHashNode **new_nodes;
  GHashNode *node;
  GHashNode *next;
  gfloat nodes_per_list;
  guint hash_val;
  gint new_size;
  gint i;
306
  
307
  nodes_per_list = (gfloat) hash_table->nnodes / (gfloat) hash_table->size;
308
  
309 310 311
  if ((nodes_per_list > 0.3 || hash_table->size <= HASH_TABLE_MIN_SIZE) &&
      (nodes_per_list < 3.0 || hash_table->size >= HASH_TABLE_MAX_SIZE))
    return;
312
  
313
  new_size = CLAMP(g_spaced_primes_closest (hash_table->nnodes),
314 315 316
		   HASH_TABLE_MIN_SIZE,
		   HASH_TABLE_MAX_SIZE);
  new_nodes = g_new (GHashNode*, new_size);
317
  
318 319
  for (i = 0; i < new_size; i++)
    new_nodes[i] = NULL;
320
  
321 322 323 324 325 326 327 328
  for (i = 0; i < hash_table->size; i++)
    for (node = hash_table->nodes[i]; node; node = next)
      {
	next = node->next;
	hash_val = (* hash_table->hash_func) (node->key) % new_size;
	node->next = new_nodes[hash_val];
	new_nodes[hash_val] = node;
      }
329
  
330 331 332 333 334
  g_free (hash_table->nodes);
  hash_table->nodes = new_nodes;
  hash_table->size = new_size;
}

Owen Taylor's avatar
Owen Taylor committed
335 336 337 338 339
static GHashNode*
g_hash_node_new (gpointer key,
		 gpointer value)
{
  GHashNode *hash_node;
340
  
Owen Taylor's avatar
Owen Taylor committed
341 342 343 344 345 346 347 348 349 350 351
  if (node_free_list)
    {
      hash_node = node_free_list;
      node_free_list = node_free_list->next;
    }
  else
    {
      if (!node_mem_chunk)
	node_mem_chunk = g_mem_chunk_new ("hash node mem chunk",
					  sizeof (GHashNode),
					  1024, G_ALLOC_ONLY);
352
      
Owen Taylor's avatar
Owen Taylor committed
353 354
      hash_node = g_chunk_new (GHashNode, node_mem_chunk);
    }
355
  
Owen Taylor's avatar
Owen Taylor committed
356 357 358
  hash_node->key = key;
  hash_node->value = value;
  hash_node->next = NULL;
359
  
Owen Taylor's avatar
Owen Taylor committed
360 361 362 363 364 365
  return hash_node;
}

static void
g_hash_node_destroy (GHashNode *hash_node)
{
366 367
  hash_node->next = node_free_list;
  node_free_list = hash_node;
Owen Taylor's avatar
Owen Taylor committed
368 369 370 371 372 373
}

static void
g_hash_nodes_destroy (GHashNode *hash_node)
{
  GHashNode *node;
374
  
375 376
  if (!hash_node)
    return;
377
  
378
  node = hash_node;
379
  
380 381
  while (node->next)
    node = node->next;
382
  
383 384
  node->next = node_free_list;
  node_free_list = hash_node;
385
}