ghash.c 50.2 KB
Newer Older
Owen Taylor's avatar
Owen Taylor committed
1 2 3 4
/* 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
5
 * modify it under the terms of the GNU Lesser General Public
Owen Taylor's avatar
Owen Taylor committed
6 7 8 9 10
 * 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
12
 * Lesser General Public License for more details.
Owen Taylor's avatar
Owen Taylor committed
13
 *
14
 * You should have received a copy of the GNU Lesser General Public
Owen Taylor's avatar
Owen Taylor committed
15 16 17 18
 * License along with this library; if not, write to the
 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 * Boston, MA 02111-1307, USA.
 */
19

20
/*
21
 * Modified by the GLib Team and others 1997-2000.  See the AUTHORS
22 23
 * file for a list of people on the GLib Team.  See the ChangeLog
 * files for a list of changes.  These files are distributed with
24
 * GLib at ftp://ftp.gtk.org/pub/gtk/.
25 26
 */

27
/*
28 29 30
 * MT safe
 */

31
#include "config.h"
32

33 34
#include <string.h>  /* memset */

Matthias Clasen's avatar
Matthias Clasen committed
35 36
#include "ghash.h"

37
#include "gstrfuncs.h"
38
#include "gatomic.h"
Matthias Clasen's avatar
Matthias Clasen committed
39
#include "gtestutils.h"
40
#include "gslice.h"
Matthias Clasen's avatar
Matthias Clasen committed
41

Owen Taylor's avatar
Owen Taylor committed
42

43
/**
44
 * SECTION:hash_tables
45 46
 * @title: Hash Tables
 * @short_description: associations between keys and values so that
Matthias Clasen's avatar
Matthias Clasen committed
47
 *     given a key the value can be found quickly
48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73
 *
 * A #GHashTable provides associations between keys and values which is
 * optimized so that given a key, the associated value can be found
 * very quickly.
 *
 * Note that neither keys nor values are copied when inserted into the
 * #GHashTable, so they must exist for the lifetime of the #GHashTable.
 * This means that the use of static strings is OK, but temporary
 * strings (i.e. those created in buffers and those returned by GTK+
 * widgets) should be copied with g_strdup() before being inserted.
 *
 * If keys or values are dynamically allocated, you must be careful to
 * ensure that they are freed when they are removed from the
 * #GHashTable, and also when they are overwritten by new insertions
 * into the #GHashTable. It is also not advisable to mix static strings
 * and dynamically-allocated strings in a #GHashTable, because it then
 * becomes difficult to determine whether the string should be freed.
 *
 * To create a #GHashTable, use g_hash_table_new().
 *
 * To insert a key and value into a #GHashTable, use
 * g_hash_table_insert().
 *
 * To lookup a value corresponding to a given key, use
 * g_hash_table_lookup() and g_hash_table_lookup_extended().
 *
74 75 76
 * g_hash_table_lookup_extended() can also be used to simply
 * check if a key is present in the hash table.
 *
77 78 79 80 81 82 83
 * To remove a key and value, use g_hash_table_remove().
 *
 * To call a function for each key and value pair use
 * g_hash_table_foreach() or use a iterator to iterate over the
 * key/value pairs in the hash table, see #GHashTableIter.
 *
 * To destroy a #GHashTable use g_hash_table_destroy().
84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
 *
 * <example>
 * <title>Using a GHashTable as a set</title>
 * <para>
 * A common use-case for hash tables is to store information about
 * a set of keys, without associating any particular value with each
 * key. GHashTable optimizes one way of doing so: If you store only
 * key-value pairs where key == value, then GHashTable does not
 * allocate memory to store the values, which can be a considerable
 * space saving, if your set is large.
 * </para>
 * <programlisting>
 * GHashTable *
 * set_new (GHashFunc      hash_func,
 *          GEqualFunc     equal_func,
 *          GDestroyNotify destroy)
 * {
101
 *   return g_hash_table_new_full (hash_func, equal_func, destroy, NULL);
102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126
 * }
 *
 * void
 * set_insert (GHashTable *set,
 *             gpointer    element)
 * {
 *   g_hash_table_insert (set, element, element);
 * }
 *
 * gboolean
 * set_contains (GHashTable *set,
 *               gpointer    element)
 * {
 *   return g_hash_table_lookup_extended (set, element, NULL, NULL);
 * }
 *
 * gboolean
 * set_remove (GHashTable *set,
 *             gpointer    element)
 * {
 *   return g_hash_table_remove (set, element);
 * }
 * </programlisting>
 * </example>
 */
127 128 129 130 131 132 133

/**
 * GHashTable:
 *
 * The #GHashTable struct is an opaque data structure to represent a
 * <link linkend="glib-Hash-Tables">Hash Table</link>. It should only be
 * accessed via the following functions.
Matthias Clasen's avatar
Matthias Clasen committed
134
 */
135 136 137

/**
 * GHashFunc:
Matthias Clasen's avatar
Matthias Clasen committed
138
 * @key: a key
139 140 141 142 143 144
 *
 * Specifies the type of the hash function which is passed to
 * g_hash_table_new() when a #GHashTable is created.
 *
 * The function is passed a key and should return a #guint hash value.
 * The functions g_direct_hash(), g_int_hash() and g_str_hash() provide
145
 * hash functions which can be used when the key is a #gpointer, #gint*,
146 147
 * and #gchar* respectively.
 *
148 149 150
 * g_direct_hash() is also the appropriate hash function for keys
 * of the form <literal>GINT_TO_POINTER (n)</literal> (or similar macros).
 *
151 152 153 154 155
 * <!-- FIXME: Need more here. --> The hash values should be evenly
 * distributed over a fairly large range? The modulus is taken with the
 * hash table size (a prime number) to find the 'bucket' to place each
 * key into. The function should also be very fast, since it is called
 * for each key lookup.
Matthias Clasen's avatar
Matthias Clasen committed
156 157 158
 *
 * Returns: the hash value corresponding to the key
 */
159 160 161

/**
 * GHFunc:
Matthias Clasen's avatar
Matthias Clasen committed
162 163 164
 * @key: a key
 * @value: the value corresponding to the key
 * @user_data: user data passed to g_hash_table_foreach()
165 166 167 168
 *
 * Specifies the type of the function passed to g_hash_table_foreach().
 * It is called with each key/value pair, together with the @user_data
 * parameter which is passed to g_hash_table_foreach().
Matthias Clasen's avatar
Matthias Clasen committed
169
 */
170 171 172

/**
 * GHRFunc:
Matthias Clasen's avatar
Matthias Clasen committed
173 174 175
 * @key: a key
 * @value: the value associated with the key
 * @user_data: user data passed to g_hash_table_remove()
176 177 178 179 180 181
 *
 * Specifies the type of the function passed to
 * g_hash_table_foreach_remove(). It is called with each key/value
 * pair, together with the @user_data parameter passed to
 * g_hash_table_foreach_remove(). It should return %TRUE if the
 * key/value pair should be removed from the #GHashTable.
Matthias Clasen's avatar
Matthias Clasen committed
182 183 184 185
 *
 * Returns: %TRUE if the key/value pair should be removed from the
 *     #GHashTable
 */
186 187 188

/**
 * GEqualFunc:
Matthias Clasen's avatar
Matthias Clasen committed
189 190
 * @a: a value
 * @b: a value to compare with
191 192 193 194
 *
 * Specifies the type of a function used to test two values for
 * equality. The function should return %TRUE if both values are equal
 * and %FALSE otherwise.
Matthias Clasen's avatar
Matthias Clasen committed
195 196 197
 *
 * Returns: %TRUE if @a = @b; %FALSE otherwise
 */
198 199 200 201 202 203 204 205

/**
 * GHashTableIter:
 *
 * A GHashTableIter structure represents an iterator that can be used
 * to iterate over the elements of a #GHashTable. GHashTableIter
 * structures are typically allocated on the stack and then initialized
 * with g_hash_table_iter_init().
Matthias Clasen's avatar
Matthias Clasen committed
206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222
 */

/**
 * g_hash_table_freeze:
 * @hash_table: a #GHashTable
 *
 * This function is deprecated and will be removed in the next major
 * release of GLib. It does nothing.
 */

/**
 * g_hash_table_thaw:
 * @hash_table: a #GHashTable
 *
 * This function is deprecated and will be removed in the next major
 * release of GLib. It does nothing.
 */
223

224
#define HASH_TABLE_MIN_SHIFT 3  /* 1 << 3 == 8 buckets */
Owen Taylor's avatar
Owen Taylor committed
225

226 227 228 229
#define UNUSED_HASH_VALUE 0
#define TOMBSTONE_HASH_VALUE 1
#define HASH_IS_UNUSED(h_) ((h_) == UNUSED_HASH_VALUE)
#define HASH_IS_TOMBSTONE(h_) ((h_) == TOMBSTONE_HASH_VALUE)
230 231
#define HASH_IS_REAL(h_) ((h_) >= 2)

232
struct _GHashTable
Owen Taylor's avatar
Owen Taylor committed
233
{
234
  gint             size;
235 236
  gint             mod;
  guint            mask;
237
  gint             nnodes;
238
  gint             noccupied;  /* nnodes + tombstones */
239 240 241 242 243

  gpointer        *keys;
  guint           *hashes;
  gpointer        *values;

244 245
  GHashFunc        hash_func;
  GEqualFunc       key_equal_func;
246
  gint             ref_count;
247 248 249 250 251 252 253 254
#ifndef G_DISABLE_ASSERT
  /*
   * Tracks the structure of the hash table, not its contents: is only
   * incremented when a node is added or removed (is not incremented
   * when the key or data of a node is modified).
   */
  int              version;
#endif
255 256
  GDestroyNotify   key_destroy_func;
  GDestroyNotify   value_destroy_func;
Owen Taylor's avatar
Owen Taylor committed
257 258
};

259 260
typedef struct
{
261 262 263 264 265 266
  GHashTable  *hash_table;
  gpointer     dummy1;
  gpointer     dummy2;
  int          position;
  gboolean     dummy3;
  int          version;
267 268
} RealIter;

269 270 271
/* Each table size has an associated prime modulo (the first prime
 * lower than the table size) used to find the initial bucket. Probing
 * then works modulo 2^n. The prime modulo is necessary to get a
Matthias Clasen's avatar
Matthias Clasen committed
272 273
 * good distribution with poor hash functions.
 */
274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349
static const gint prime_mod [] =
{
  1,          /* For 1 << 0 */
  2,
  3,
  7,
  13,
  31,
  61,
  127,
  251,
  509,
  1021,
  2039,
  4093,
  8191,
  16381,
  32749,
  65521,      /* For 1 << 16 */
  131071,
  262139,
  524287,
  1048573,
  2097143,
  4194301,
  8388593,
  16777213,
  33554393,
  67108859,
  134217689,
  268435399,
  536870909,
  1073741789,
  2147483647  /* For 1 << 31 */
};

static void
g_hash_table_set_shift (GHashTable *hash_table, gint shift)
{
  gint i;
  guint mask = 0;

  hash_table->size = 1 << shift;
  hash_table->mod  = prime_mod [shift];

  for (i = 0; i < shift; i++)
    {
      mask <<= 1;
      mask |= 1;
    }

  hash_table->mask = mask;
}

static gint
g_hash_table_find_closest_shift (gint n)
{
  gint i;

  for (i = 0; n; i++)
    n >>= 1;

  return i;
}

static void
g_hash_table_set_shift_from_size (GHashTable *hash_table, gint size)
{
  gint shift;

  shift = g_hash_table_find_closest_shift (size);
  shift = MAX (shift, HASH_TABLE_MIN_SHIFT);

  g_hash_table_set_shift (hash_table, shift);
}

350
/*
351 352
 * g_hash_table_lookup_node:
 * @hash_table: our #GHashTable
353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369
 * @key: the key to lookup against
 * @hash_return: key hash return location
 *
 * Performs a lookup in the hash table, preserving extra information
 * usually needed for insertion.
 *
 * This function first computes the hash value of the key using the
 * user's hash function.
 *
 * If an entry in the table matching @key is found then this function
 * returns the index of that entry in the table, and if not, the
 * index of an unused node (empty or tombstone) where the key can be
 * inserted.
 *
 * The computed hash value is returned in the variable pointed to
 * by @hash_return. This is to save insertions from having to compute
 * the hash record again for the new record.
Matthias Clasen's avatar
Matthias Clasen committed
370 371
 *
 * Returns: index of the described node
372 373
 */
static inline guint
374
g_hash_table_lookup_node (GHashTable    *hash_table,
375 376
                          gconstpointer  key,
                          guint         *hash_return)
377 378
{
  guint node_index;
Matthias Clasen's avatar
Matthias Clasen committed
379
  guint node_hash;
380
  guint hash_value;
Dan Winship's avatar
Dan Winship committed
381
  guint first_tombstone = 0;
382 383 384
  gboolean have_tombstone = FALSE;
  guint step = 0;

Matthias Clasen's avatar
Matthias Clasen committed
385
  hash_value = hash_table->hash_func (key);
386
  if (G_UNLIKELY (!HASH_IS_REAL (hash_value)))
387 388 389 390 391
    hash_value = 2;

  *hash_return = hash_value;

  node_index = hash_value % hash_table->mod;
Matthias Clasen's avatar
Matthias Clasen committed
392
  node_hash = hash_table->hashes[node_index];
393

Matthias Clasen's avatar
Matthias Clasen committed
394
  while (!HASH_IS_UNUSED (node_hash))
395
    {
Matthias Clasen's avatar
Matthias Clasen committed
396 397 398
      /* We first check if our full hash values
       * are equal so we can avoid calling the full-blown
       * key equality function in most cases.
399
       */
400
      if (node_hash == hash_value)
401
        {
402
          gpointer node_key = hash_table->keys[node_index];
403

404 405
          if (hash_table->key_equal_func)
            {
406
              if (hash_table->key_equal_func (node_key, key))
407 408
                return node_index;
            }
409
          else if (node_key == key)
410 411 412 413
            {
              return node_index;
            }
        }
Matthias Clasen's avatar
Matthias Clasen committed
414
      else if (HASH_IS_TOMBSTONE (node_hash) && !have_tombstone)
415 416 417
        {
          first_tombstone = node_index;
          have_tombstone = TRUE;
418
        }
419 420 421 422

      step++;
      node_index += step;
      node_index &= hash_table->mask;
Matthias Clasen's avatar
Matthias Clasen committed
423
      node_hash = hash_table->hashes[node_index];
424 425
    }

426 427 428 429
  if (have_tombstone)
    return first_tombstone;

  return node_index;
430 431
}

432
/*
433 434
 * g_hash_table_remove_node:
 * @hash_table: our #GHashTable
435
 * @node: pointer to node to remove
436 437
 * @notify: %TRUE if the destroy notify handlers are to be called
 *
438 439
 * Removes a node from the hash table and updates the node count.
 * The node is replaced by a tombstone. No table resize is performed.
440 441 442
 *
 * If @notify is %TRUE then the destroy notify functions are called
 * for the key and value of the hash node.
443
 */
444 445
static void
g_hash_table_remove_node (GHashTable   *hash_table,
Matthias Clasen's avatar
Matthias Clasen committed
446
                          gint          i,
447 448
                          gboolean      notify)
{
449 450
  gpointer key;
  gpointer value;
451

452 453
  key = hash_table->keys[i];
  value = hash_table->values[i];
454

455
  /* Erect tombstone */
456
  hash_table->hashes[i] = TOMBSTONE_HASH_VALUE;
457 458

  /* Be GC friendly */
459 460
  hash_table->keys[i] = NULL;
  hash_table->values[i] = NULL;
461 462

  hash_table->nnodes--;
463 464 465 466 467 468 469

  if (notify && hash_table->key_destroy_func)
    hash_table->key_destroy_func (key);

  if (notify && hash_table->value_destroy_func)
    hash_table->value_destroy_func (value);

470 471
}

472
/*
473 474 475 476 477 478 479 480 481
 * g_hash_table_remove_all_nodes:
 * @hash_table: our #GHashTable
 * @notify: %TRUE if the destroy notify handlers are to be called
 *
 * Removes all nodes from the table.  Since this may be a precursor to
 * freeing the table entirely, no resize is performed.
 *
 * If @notify is %TRUE then the destroy notify functions are called
 * for the key and value of the hash node.
482
 */
483 484 485 486 487
static void
g_hash_table_remove_all_nodes (GHashTable *hash_table,
                               gboolean    notify)
{
  int i;
488 489 490 491 492
  gpointer key;
  gpointer value;

  hash_table->nnodes = 0;
  hash_table->noccupied = 0;
493

494 495 496
  if (!notify ||
      (hash_table->key_destroy_func == NULL &&
       hash_table->value_destroy_func == NULL))
497
    {
498 499 500
      memset (hash_table->hashes, 0, hash_table->size * sizeof (guint));
      memset (hash_table->keys, 0, hash_table->size * sizeof (gpointer));
      memset (hash_table->values, 0, hash_table->size * sizeof (gpointer));
501

502
      return;
503 504
    }

505 506 507 508 509 510
  for (i = 0; i < hash_table->size; i++)
    {
      if (HASH_IS_REAL (hash_table->hashes[i]))
        {
          key = hash_table->keys[i];
          value = hash_table->values[i];
511

512
          hash_table->hashes[i] = UNUSED_HASH_VALUE;
513 514 515 516 517 518 519 520 521
          hash_table->keys[i] = NULL;
          hash_table->values[i] = NULL;

          if (hash_table->key_destroy_func != NULL)
            hash_table->key_destroy_func (key);

          if (hash_table->value_destroy_func != NULL)
            hash_table->value_destroy_func (value);
        }
522 523 524 525
      else if (HASH_IS_TOMBSTONE (hash_table->hashes[i]))
        {
          hash_table->hashes[i] = UNUSED_HASH_VALUE;
        }
526
    }
527 528
}

529
/*
530 531 532 533
 * g_hash_table_resize:
 * @hash_table: our #GHashTable
 *
 * Resizes the hash table to the optimal size based on the number of
Matthias Clasen's avatar
Matthias Clasen committed
534 535 536
 * nodes currently held. If you call this function then a resize will
 * occur, even if one does not need to occur.
 * Use g_hash_table_maybe_resize() instead.
537 538 539 540
 *
 * This function may "resize" the hash table to its current size, with
 * the side effect of cleaning up tombstones and otherwise optimizing
 * the probe sequences.
541
 */
542 543 544
static void
g_hash_table_resize (GHashTable *hash_table)
{
545 546 547
  gpointer *new_keys;
  gpointer *new_values;
  guint *new_hashes;
548
  gint old_size;
549 550
  gint i;

551 552
  old_size = hash_table->size;
  g_hash_table_set_shift_from_size (hash_table, hash_table->nnodes * 2);
553

554 555 556 557 558
  new_keys = g_new0 (gpointer, hash_table->size);
  if (hash_table->keys == hash_table->values)
    new_values = new_keys;
  else
    new_values = g_new0 (gpointer, hash_table->size);
559
  new_hashes = g_new0 (guint, hash_table->size);
560

561 562
  for (i = 0; i < old_size; i++)
    {
563
      guint node_hash = hash_table->hashes[i];
564 565 566
      guint hash_val;
      guint step = 0;

567
      if (!HASH_IS_REAL (node_hash))
568
        continue;
569

570
      hash_val = node_hash % hash_table->mod;
571

572
      while (!HASH_IS_UNUSED (new_hashes[hash_val]))
573 574 575 576 577 578
        {
          step++;
          hash_val += step;
          hash_val &= hash_table->mask;
        }

579 580 581
      new_hashes[hash_val] = hash_table->hashes[i];
      new_keys[hash_val] = hash_table->keys[i];
      new_values[hash_val] = hash_table->values[i];
582
    }
583

584 585 586
  if (hash_table->keys != hash_table->values)
    g_free (hash_table->values);

587 588 589 590 591 592 593
  g_free (hash_table->keys);
  g_free (hash_table->hashes);

  hash_table->keys = new_keys;
  hash_table->values = new_values;
  hash_table->hashes = new_hashes;

594
  hash_table->noccupied = hash_table->nnodes;
595
}
Owen Taylor's avatar
Owen Taylor committed
596

597
/*
598 599 600 601 602 603 604
 * g_hash_table_maybe_resize:
 * @hash_table: our #GHashTable
 *
 * Resizes the hash table, if needed.
 *
 * Essentially, calls g_hash_table_resize() if the table has strayed
 * too far from its ideal size for its number of nodes.
605
 */
606 607 608
static inline void
g_hash_table_maybe_resize (GHashTable *hash_table)
{
609
  gint noccupied = hash_table->noccupied;
610 611
  gint size = hash_table->size;

612 613
  if ((size > hash_table->nnodes * 4 && size > 1 << HASH_TABLE_MIN_SHIFT) ||
      (size <= noccupied + (noccupied / 16)))
614 615
    g_hash_table_resize (hash_table);
}
Owen Taylor's avatar
Owen Taylor committed
616

617 618
/**
 * g_hash_table_new:
Matthias Clasen's avatar
Matthias Clasen committed
619 620
 * @hash_func: a function to create a hash value from a key
 * @key_equal_func: a function to check two keys for equality
621
 *
622
 * Creates a new #GHashTable with a reference count of 1.
623
 *
Matthias Clasen's avatar
Matthias Clasen committed
624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641
 * Hash values returned by @hash_func are used to determine where keys
 * are stored within the #GHashTable data structure. The g_direct_hash(),
 * g_int_hash(), g_int64_hash(), g_double_hash() and g_str_hash()
 * functions are provided for some common types of keys.
 * If @hash_func is %NULL, g_direct_hash() is used.
 *
 * @key_equal_func is used when looking up keys in the #GHashTable.
 * The g_direct_equal(), g_int_equal(), g_int64_equal(), g_double_equal()
 * and g_str_equal() functions are provided for the most common types
 * of keys. If @key_equal_func is %NULL, keys are compared directly in
 * a similar fashion to g_direct_equal(), but without the overhead of
 * a function call.
 *
 * Return value: a new #GHashTable
 */
GHashTable *
g_hash_table_new (GHashFunc  hash_func,
                  GEqualFunc key_equal_func)
642 643 644 645 646 647 648
{
  return g_hash_table_new_full (hash_func, key_equal_func, NULL, NULL);
}


/**
 * g_hash_table_new_full:
Matthias Clasen's avatar
Matthias Clasen committed
649 650
 * @hash_func: a function to create a hash value from a key
 * @key_equal_func: a function to check two keys for equality
651
 * @key_destroy_func: a function to free the memory allocated for the key
Matthias Clasen's avatar
Matthias Clasen committed
652 653
 *     used when removing the entry from the #GHashTable, or %NULL
 *     if you don't want to supply such a function.
654
 * @value_destroy_func: a function to free the memory allocated for the
Matthias Clasen's avatar
Matthias Clasen committed
655 656 657 658 659 660 661 662 663 664 665 666 667 668 669
 *     value used when removing the entry from the #GHashTable, or %NULL
 *     if you don't want to supply such a function.
 *
 * Creates a new #GHashTable like g_hash_table_new() with a reference
 * count of 1 and allows to specify functions to free the memory
 * allocated for the key and value that get called when removing the
 * entry from the #GHashTable.
 *
 * Return value: a new #GHashTable
 */
GHashTable *
g_hash_table_new_full (GHashFunc      hash_func,
                       GEqualFunc     key_equal_func,
                       GDestroyNotify key_destroy_func,
                       GDestroyNotify value_destroy_func)
Owen Taylor's avatar
Owen Taylor committed
670
{
671
  GHashTable *hash_table;
672

673
  hash_table = g_slice_new (GHashTable);
674
  g_hash_table_set_shift (hash_table, HASH_TABLE_MIN_SHIFT);
675
  hash_table->nnodes             = 0;
676
  hash_table->noccupied          = 0;
677 678
  hash_table->hash_func          = hash_func ? hash_func : g_direct_hash;
  hash_table->key_equal_func     = key_equal_func;
679
  hash_table->ref_count          = 1;
680 681 682
#ifndef G_DISABLE_ASSERT
  hash_table->version            = 0;
#endif
683 684
  hash_table->key_destroy_func   = key_destroy_func;
  hash_table->value_destroy_func = value_destroy_func;
685
  hash_table->keys               = g_new0 (gpointer, hash_table->size);
686
  hash_table->values             = hash_table->keys;
687
  hash_table->hashes             = g_new0 (guint, hash_table->size);
688

689
  return hash_table;
Owen Taylor's avatar
Owen Taylor committed
690 691
}

692 693
/**
 * g_hash_table_iter_init:
Matthias Clasen's avatar
Matthias Clasen committed
694 695
 * @iter: an uninitialized #GHashTableIter
 * @hash_table: a #GHashTable
696 697 698 699
 *
 * Initializes a key/value pair iterator and associates it with
 * @hash_table. Modifying the hash table after calling this function
 * invalidates the returned iterator.
Matthias Clasen's avatar
Matthias Clasen committed
700
 * |[
701 702 703
 * GHashTableIter iter;
 * gpointer key, value;
 *
Matthias Clasen's avatar
Matthias Clasen committed
704
 * g_hash_table_iter_init (&iter, hash_table);
Matthias Clasen's avatar
Matthias Clasen committed
705
 * while (g_hash_table_iter_next (&iter, &key, &value))
Matthias Clasen's avatar
Matthias Clasen committed
706 707 708 709
 *   {
 *     /&ast; do something with key and value &ast;/
 *   }
 * ]|
710 711
 *
 * Since: 2.16
Matthias Clasen's avatar
Matthias Clasen committed
712
 */
713 714
void
g_hash_table_iter_init (GHashTableIter *iter,
715
                        GHashTable     *hash_table)
716 717 718 719 720 721 722 723 724 725 726 727 728 729 730
{
  RealIter *ri = (RealIter *) iter;

  g_return_if_fail (iter != NULL);
  g_return_if_fail (hash_table != NULL);

  ri->hash_table = hash_table;
  ri->position = -1;
#ifndef G_DISABLE_ASSERT
  ri->version = hash_table->version;
#endif
}

/**
 * g_hash_table_iter_next:
Matthias Clasen's avatar
Matthias Clasen committed
731 732 733
 * @iter: an initialized #GHashTableIter
 * @key: a location to store the key, or %NULL
 * @value: a location to store the value, or %NULL
734 735 736 737 738 739 740 741
 *
 * Advances @iter and retrieves the key and/or value that are now
 * pointed to as a result of this advancement. If %FALSE is returned,
 * @key and @value are not set, and the iterator becomes invalid.
 *
 * Return value: %FALSE if the end of the #GHashTable has been reached.
 *
 * Since: 2.16
Matthias Clasen's avatar
Matthias Clasen committed
742
 */
743 744
gboolean
g_hash_table_iter_next (GHashTableIter *iter,
745 746
                        gpointer       *key,
                        gpointer       *value)
747 748
{
  RealIter *ri = (RealIter *) iter;
749
  gint position;
750 751

  g_return_val_if_fail (iter != NULL, FALSE);
752
#ifndef G_DISABLE_ASSERT
753
  g_return_val_if_fail (ri->version == ri->hash_table->version, FALSE);
754
#endif
755
  g_return_val_if_fail (ri->position < ri->hash_table->size, FALSE);
756

757
  position = ri->position;
758

759
  do
760
    {
761 762 763 764 765 766
      position++;
      if (position >= ri->hash_table->size)
        {
          ri->position = position;
          return FALSE;
        }
767
    }
768
  while (!HASH_IS_REAL (ri->hash_table->hashes[position]));
769 770

  if (key != NULL)
771
    *key = ri->hash_table->keys[position];
772
  if (value != NULL)
773
    *value = ri->hash_table->values[position];
774

775
  ri->position = position;
776 777 778 779 780
  return TRUE;
}

/**
 * g_hash_table_iter_get_hash_table:
Matthias Clasen's avatar
Matthias Clasen committed
781
 * @iter: an initialized #GHashTableIter
782 783 784 785 786 787
 *
 * Returns the #GHashTable associated with @iter.
 *
 * Return value: the #GHashTable associated with @iter.
 *
 * Since: 2.16
Matthias Clasen's avatar
Matthias Clasen committed
788
 */
789 790 791 792 793 794 795 796 797 798 799 800
GHashTable *
g_hash_table_iter_get_hash_table (GHashTableIter *iter)
{
  g_return_val_if_fail (iter != NULL, NULL);

  return ((RealIter *) iter)->hash_table;
}

static void
iter_remove_or_steal (RealIter *ri, gboolean notify)
{
  g_return_if_fail (ri != NULL);
801
#ifndef G_DISABLE_ASSERT
802
  g_return_if_fail (ri->version == ri->hash_table->version);
803
#endif
804 805
  g_return_if_fail (ri->position >= 0);
  g_return_if_fail (ri->position < ri->hash_table->size);
806

807
  g_hash_table_remove_node (ri->hash_table, ri->position, notify);
808 809 810 811 812

#ifndef G_DISABLE_ASSERT
  ri->version++;
  ri->hash_table->version++;
#endif
813 814 815
}

/**
Allison Karlitskaya's avatar
Allison Karlitskaya committed
816
 * g_hash_table_iter_remove:
Matthias Clasen's avatar
Matthias Clasen committed
817
 * @iter: an initialized #GHashTableIter
818 819 820
 *
 * Removes the key/value pair currently pointed to by the iterator
 * from its associated #GHashTable. Can only be called after
Matthias Clasen's avatar
Matthias Clasen committed
821 822
 * g_hash_table_iter_next() returned %TRUE, and cannot be called
 * more than once for the same key/value pair.
823
 *
Matthias Clasen's avatar
Matthias Clasen committed
824 825 826 827
 * If the #GHashTable was created using g_hash_table_new_full(),
 * the key and value are freed using the supplied destroy functions,
 * otherwise you have to make sure that any dynamically allocated
 * values are freed yourself.
828 829
 *
 * Since: 2.16
Matthias Clasen's avatar
Matthias Clasen committed
830
 */
831 832 833 834 835 836
void
g_hash_table_iter_remove (GHashTableIter *iter)
{
  iter_remove_or_steal ((RealIter *) iter, TRUE);
}

837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902
/*
 * g_hash_table_insert_node:
 * @hash_table: our #GHashTable
 * @node_index: pointer to node to insert/replace
 * @key_hash: key hash
 * @key: key to replace with
 * @value: value to replace with
 *
 * Inserts a value at @node_index in the hash table and updates it.
 */
static void
g_hash_table_insert_node (GHashTable *hash_table,
                          guint       node_index,
                          guint       key_hash,
                          gpointer    key,
                          gpointer    value,
                          gboolean    keep_new_key)
{
  guint old_hash;
  gpointer old_key;
  gpointer old_value;

  if (G_UNLIKELY (hash_table->keys == hash_table->values && key != value))
    hash_table->values = g_memdup (hash_table->keys, sizeof (gpointer) * hash_table->size);

  old_hash = hash_table->hashes[node_index];
  old_key = hash_table->keys[node_index];
  old_value = hash_table->values[node_index];

  if (HASH_IS_REAL (old_hash))
    {
      if (keep_new_key)
        hash_table->keys[node_index] = key;
      hash_table->values[node_index] = value;
    }
  else
    {
      hash_table->keys[node_index] = key;
      hash_table->values[node_index] = value;
      hash_table->hashes[node_index] = key_hash;

      hash_table->nnodes++;

      if (HASH_IS_UNUSED (old_hash))
        {
          /* We replaced an empty node, and not a tombstone */
          hash_table->noccupied++;
          g_hash_table_maybe_resize (hash_table);
        }

#ifndef G_DISABLE_ASSERT
      hash_table->version++;
#endif
    }

  if (HASH_IS_REAL (old_hash))
    {
      if (hash_table->key_destroy_func)
        hash_table->key_destroy_func (keep_new_key ? old_key : key);
      if (hash_table->value_destroy_func)
        hash_table->value_destroy_func (old_value);
    }
}

/**
 * g_hash_table_iter_replace:
Matthias Clasen's avatar
Matthias Clasen committed
903
 * @iter: an initialized #GHashTableIter
904 905 906 907 908 909
 * @value: the value to replace with
 *
 * Replaces the value currently pointed to by the iterator
 * from its associated #GHashTable. Can only be called after
 * g_hash_table_iter_next() returned %TRUE.
 *
Matthias Clasen's avatar
Matthias Clasen committed
910 911
 * If you supplied a @value_destroy_func when creating the
 * #GHashTable, the old value is freed using that function.
912
 *
Matthias Clasen's avatar
Matthias Clasen committed
913 914
 * Since: 2.30
 */
915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942
void
g_hash_table_iter_replace (GHashTableIter *iter,
                           gpointer        value)
{
  RealIter *ri;
  guint node_hash;
  gpointer key;

  ri = (RealIter *) iter;

  g_return_if_fail (ri != NULL);
#ifndef G_DISABLE_ASSERT
  g_return_if_fail (ri->version == ri->hash_table->version);
#endif
  g_return_if_fail (ri->position >= 0);
  g_return_if_fail (ri->position < ri->hash_table->size);

  node_hash = ri->hash_table->hashes[ri->position];
  key = ri->hash_table->keys[ri->position];

  g_hash_table_insert_node (ri->hash_table, ri->position, node_hash, key, value, TRUE);

#ifndef G_DISABLE_ASSERT
  ri->version++;
  ri->hash_table->version++;
#endif
}

943
/**
Allison Karlitskaya's avatar
Allison Karlitskaya committed
944
 * g_hash_table_iter_steal:
Matthias Clasen's avatar
Matthias Clasen committed
945
 * @iter: an initialized #GHashTableIter
946
 *
Matthias Clasen's avatar
Matthias Clasen committed
947 948 949 950 951
 * Removes the key/value pair currently pointed to by the
 * iterator from its associated #GHashTable, without calling
 * the key and value destroy functions. Can only be called
 * after g_hash_table_iter_next() returned %TRUE, and cannot
 * be called more than once for the same key/value pair.
952 953
 *
 * Since: 2.16
Matthias Clasen's avatar
Matthias Clasen committed
954
 */
955 956 957 958 959 960
void
g_hash_table_iter_steal (GHashTableIter *iter)
{
  iter_remove_or_steal ((RealIter *) iter, FALSE);
}

961 962 963

/**
 * g_hash_table_ref:
Matthias Clasen's avatar
Matthias Clasen committed
964
 * @hash_table: a valid #GHashTable
965
 *
966 967
 * Atomically increments the reference count of @hash_table by one.
 * This function is MT-safe and may be called from any thread.
968
 *
Matthias Clasen's avatar
Matthias Clasen committed
969
 * Return value: the passed in #GHashTable
970
 *
Matthias Clasen's avatar
Matthias Clasen committed
971
 * Since: 2.10
Matthias Clasen's avatar
Matthias Clasen committed
972 973
 */
GHashTable *
974 975 976 977
g_hash_table_ref (GHashTable *hash_table)
{
  g_return_val_if_fail (hash_table != NULL, NULL);

Matthias Clasen's avatar
Matthias Clasen committed
978 979
  g_atomic_int_inc (&hash_table->ref_count);

980 981 982 983 984
  return hash_table;
}

/**
 * g_hash_table_unref:
Matthias Clasen's avatar
Matthias Clasen committed
985
 * @hash_table: a valid #GHashTable
986
 *
987 988 989 990
 * Atomically decrements the reference count of @hash_table by one.
 * If the reference count drops to 0, all keys and values will be
 * destroyed, and all memory allocated by the hash table is released.
 * This function is MT-safe and may be called from any thread.
991
 *
Matthias Clasen's avatar
Matthias Clasen committed
992
 * Since: 2.10
Matthias Clasen's avatar
Matthias Clasen committed
993
 */
994 995 996 997 998
void
g_hash_table_unref (GHashTable *hash_table)
{
  g_return_if_fail (hash_table != NULL);

Matthias Clasen's avatar
Matthias Clasen committed
999
  if (g_atomic_int_dec_and_test (&hash_table->ref_count))
1000
    {
1001
      g_hash_table_remove_all_nodes (hash_table, TRUE);
1002 1003
      if (hash_table->keys != hash_table->values)
        g_free (hash_table->values);
1004 1005
      g_free (hash_table->keys);
      g_free (hash_table->hashes);
1006 1007 1008 1009
      g_slice_free (GHashTable, hash_table);
    }
}

1010 1011
/**
 * g_hash_table_destroy:
Matthias Clasen's avatar
Matthias Clasen committed
1012
 * @hash_table: a #GHashTable
1013
 *
Morten Welinder's avatar
Morten Welinder committed
1014
 * Destroys all keys and values in the #GHashTable and decrements its
1015 1016 1017 1018 1019
 * reference count by 1. If keys and/or values are dynamically allocated,
 * you should either free them first or create the #GHashTable with destroy
 * notifiers using g_hash_table_new_full(). In the latter case the destroy
 * functions you supplied will be called on all keys and values during the
 * destruction phase.
Matthias Clasen's avatar
Matthias Clasen committed
1020
 */
Owen Taylor's avatar
Owen Taylor committed
1021 1022 1023
void
g_hash_table_destroy (GHashTable *hash_table)
{
1024
  g_return_if_fail (hash_table != NULL);
1025

1026
  g_hash_table_remove_all (hash_table);
1027
  g_hash_table_unref (hash_table);
Owen Taylor's avatar
Owen Taylor committed
1028 1029
}

1030 1031
/**
 * g_hash_table_lookup:
Matthias Clasen's avatar
Matthias Clasen committed
1032 1033
 * @hash_table: a #GHashTable
 * @key: the key to look up
1034
 *
1035 1036 1037 1038
 * Looks up a key in a #GHashTable. Note that this function cannot
 * distinguish between a key that is not present and one which is present
 * and has the value %NULL. If you need this distinction, use
 * g_hash_table_lookup_extended().
1039
 *
Matthias Clasen's avatar
Matthias Clasen committed
1040 1041
 * Return value: the associated value, or %NULL if the key is not found
 */
1042
gpointer
Matthias Clasen's avatar
Matthias Clasen committed
1043 1044
g_hash_table_lookup (GHashTable    *hash_table,
                     gconstpointer  key)
1045
{
1046 1047
  guint node_index;
  guint node_hash;
1048

1049
  g_return_val_if_fail (hash_table != NULL, NULL);
1050

1051
  node_index = g_hash_table_lookup_node (hash_table, key, &node_hash);
1052

1053 1054 1055
  return HASH_IS_REAL (hash_table->hashes[node_index])
    ? hash_table->values[node_index]
    : NULL;
1056
}
1057

1058 1059
/**
 * g_hash_table_lookup_extended:
1060 1061 1062 1063
 * @hash_table: a #GHashTable
 * @lookup_key: the key to look up
 * @orig_key: return location for the original key, or %NULL
 * @value: return location for the value associated with the key, or %NULL
1064
 *
1065
 * Looks up a key in the #GHashTable, returning the original key and the
1066 1067
 * associated value and a #gboolean which is %TRUE if the key was found. This
 * is useful if you need to free the memory allocated for the original key,
1068
 * for example before calling g_hash_table_remove().
1069
 *
1070
 * You can actually pass %NULL for @lookup_key to test
1071 1072
 * whether the %NULL key exists, provided the hash and equal functions
 * of @hash_table are %NULL-safe.
1073
 *
Matthias Clasen's avatar
Matthias Clasen committed
1074 1075
 * Return value: %TRUE if the key was found in the #GHashTable
 */
1076 1077
gboolean
g_hash_table_lookup_extended (GHashTable    *hash_table,
1078 1079 1080
                              gconstpointer  lookup_key,
                              gpointer      *orig_key,
                              gpointer      *value)
1081
{
1082 1083
  guint node_index;
  guint node_hash;
1084

1085
  g_return_val_if_fail (hash_table != NULL, FALSE);
1086

1087
  node_index = g_hash_table_lookup_node (hash_table, lookup_key, &node_hash);
1088

1089
  if (!HASH_IS_REAL (hash_table->hashes[node_index]))
1090
    return FALSE;
1091 1092

  if (orig_key)
1093
    *orig_key = hash_table->keys[node_index];
1094 1095

  if (value)
1096
    *value = hash_table->values[node_index];
1097 1098

  return TRUE;
1099 1100
}

1101
/*
1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112
 * g_hash_table_insert_internal:
 * @hash_table: our #GHashTable
 * @key: the key to insert
 * @value: the value to insert
 * @keep_new_key: if %TRUE and this key already exists in the table
 *   then call the destroy notify function on the old key.  If %FALSE
 *   then call the destroy notify function on the new key.
 *
 * Implements the common logic for the g_hash_table_insert() and
 * g_hash_table_replace() functions.
 *
Matthias Clasen's avatar
Matthias Clasen committed
1113 1114 1115
 * Do a lookup of @key. If it is found, replace it with the new
 * @value (and perhaps the new @key). If it is not found, create
 * a new node.
1116
 */
1117 1118 1119 1120 1121
static void
g_hash_table_insert_internal (GHashTable *hash_table,
                              gpointer    key,
                              gpointer    value,
                              gboolean    keep_new_key)
1122
{
1123
  guint key_hash;
1124
  guint node_index;
1125

1126
  g_return_if_fail (hash_table != NULL);
1127

1128
  node_index = g_hash_table_lookup_node (hash_table, key, &key_hash);
1129

1130
  g_hash_table_insert_node (hash_table, node_index, key_hash, key, value, keep_new_key);
1131 1132
}

1133 1134
/**
 * g_hash_table_insert:
Matthias Clasen's avatar
Matthias Clasen committed
1135 1136 1137
 * @hash_table: a #GHashTable
 * @key: a key to insert
 * @value: the value to associate with the key
1138
 *
1139
 * Inserts a new key and value into a #GHashTable.
1140
 *
Matthias Clasen's avatar
Matthias Clasen committed
1141 1142 1143 1144 1145 1146 1147
 * If the key already exists in the #GHashTable its current
 * value is replaced with the new value. If you supplied a
 * @value_destroy_func when creating the #GHashTable, the old
 * value is freed using that function. If you supplied a
 * @key_destroy_func when creating the #GHashTable, the passed
 * key is freed using that function.
 */
1148 1149
void
g_hash_table_insert (GHashTable *hash_table,
1150 1151
                     gpointer    key,
                     gpointer    value)
1152
{
1153
  g_hash_table_insert_internal (hash_table, key, value, FALSE);
1154 1155
}

1156 1157
/**
 * g_hash_table_replace:
Matthias Clasen's avatar
Matthias Clasen committed
1158 1159 1160
 * @hash_table: a #GHashTable
 * @key: a key to insert
 * @value: the value to associate with the key
1161 1162
 *
 * Inserts a new key and value into a #GHashTable similar to
Matthias Clasen's avatar
Matthias Clasen committed
1163 1164 1165 1166 1167
 * g_hash_table_insert(). The difference is that if the key
 * already exists in the #GHashTable, it gets replaced by the
 * new key. If you supplied a @value_destroy_func when creating
 * the #GHashTable, the old value is freed using that function.
 * If you supplied a @key_destroy_func when creating the
1168
 * #GHashTable, the old key is freed using that function.
Matthias Clasen's avatar
Matthias Clasen committed
1169
 */
1170 1171
void
g_hash_table_replace (GHashTable *hash_table,
1172 1173
                      gpointer    key,
                      gpointer    value)
1174
{
1175
  g_hash_table_insert_internal (hash_table, key, value, TRUE);
Owen Taylor's avatar
Owen Taylor committed
1176 1177
}

1178
/*
1179 1180 1181 1182 1183 1184 1185 1186 1187 1188 1189
 * g_hash_table_remove_internal:
 * @hash_table: our #GHashTable
 * @key: the key to remove
 * @notify: %TRUE if the destroy notify handlers are to be called
 * Return value: %TRUE if a node was found and removed, else %FALSE
 *
 * Implements the common logic for the g_hash_table_remove() and
 * g_hash_table_steal() functions.
 *
 * Do a lookup of @key and remove it if it is found, calling the
 * destroy notify handlers only if @notify is %TRUE.
1190
 */
1191 1192 1193 1194 1195
static gboolean
g_hash_table_remove_internal (GHashTable    *hash_table,
                              gconstpointer  key,
                              gboolean       notify)
{
1196
  guint node_index;
1197
  guint node_hash;
1198

1199
  g_return_val_if_fail (hash_table != NULL, FALSE);
1200

1201
  node_index = g_hash_table_lookup_node (hash_table, key, &node_hash);
1202

1203
  if (!HASH_IS_REAL (hash_table->hashes[node_index]))
1204 1205
    return FALSE;

1206
  g_hash_table_remove_node (hash_table, node_index, notify);
1207
  g_hash_table_maybe_resize (hash_table);
1208

1209 1210 1211 1212
#ifndef G_DISABLE_ASSERT
  hash_table->version++;
#endif

1213 1214 1215
  return TRUE;
}

1216 1217
/**
 * g_hash_table_remove:
Matthias Clasen's avatar
Matthias Clasen committed
1218 1219
 * @hash_table: a #GHashTable
 * @key: the key to remove
1220
 *
1221 1222 1223
 * Removes a key and its associated value from a #GHashTable.
 *
 * If the #GHashTable was created using g_hash_table_new_full(), the
Matthias Clasen's avatar
Matthias Clasen committed
1224
 * key and value are freed using the supplied destroy functions, otherwise
1225
 * you have to make sure that any dynamically allocated values are freed
1226
 * yourself.
1227
 *
Matthias Clasen's avatar
Matthias Clasen committed
1228 1229
 * Returns: %TRUE if the key was found and removed from the #GHashTable
 */
1230
gboolean
1231
g_hash_table_remove (GHashTable    *hash_table,
1232
                     gconstpointer  key)
Owen Taylor's avatar
Owen Taylor committed
1233
{
1234
  return g_hash_table_remove_internal (hash_table, key, TRUE);
Owen Taylor's avatar
Owen Taylor committed
1235 1236
}

1237 1238
/**
 * g_hash_table_steal:
Matthias Clasen's avatar
Matthias Clasen committed
1239 1240
 * @hash_table: a #GHashTable
 * @key: the key to remove
1241 1242 1243 1244
 *
 * Removes a key and its associated value from a #GHashTable without
 * calling the key and value destroy functions.
 *
Matthias Clasen's avatar
Matthias Clasen committed
1245 1246
 * Returns: %TRUE if the key was found and removed from the #GHashTable
 */
1247 1248 1249 1250 1251 1252 1253
gboolean
g_hash_table_steal (GHashTable    *hash_table,
                    gconstpointer  key)
{
  return g_hash_table_remove_internal (hash_table, key, FALSE);
}

1254 1255 1256 1257 1258 1259
/**
 * g_hash_table_remove_all:
 * @hash_table: a #GHashTable
 *
 * Removes all keys and their associated values from a #GHashTable.
 *
Matthias Clasen's avatar
Matthias Clasen committed
1260 1261 1262 1263
 * If the #GHashTable was created using g_hash_table_new_full(),
 * the keys and values are freed using the supplied destroy functions,
 * otherwise you have to make sure that any dynamically a