/* GLIB - Library of useful routines for C programming

 * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald

 * Portions copyright (c) 2006-2009 Nokia Corporation.  All rights reserved.

 *

 * This library is free software; you can redistribute it and/or

 * modify it under the terms of the GNU Lesser 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

 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

 * Lesser General Public License for more details.

 *

 * You should have received a copy of the GNU Lesser 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.

 */

/*

 * Modified by the GLib Team and others 1997-2000.  See the AUTHORS

 * file for a list of people on the GLib Team.  See the ChangeLog

 * files for a list of changes.  These files are distributed with

 * GLib at ftp://ftp.gtk.org/pub/gtk/.

 */

/*

 * MT safe

 */

#include "config.h"

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

#include "glib.h"

#include "galias.h"

#define HASH_TABLE_MIN_SHIFT 3  /* 1 << 3 == 8 buckets */

typedef struct _GHashNode      GHashNode;

struct _GHashNode

{

  gpointer   key;

  gpointer   value;

  /* If key_hash == 0, node is not in use

   * If key_hash == 1, node is a tombstone

   * If key_hash >= 2, node contains data */

  guint      key_hash;

};

struct _GHashTable

{

  gint             size;

  gint             mod;

  guint            mask;

  gint             nnodes;

  gint             noccupied;  /* nnodes + tombstones */

  GHashNode       *nodes;

  GHashFunc        hash_func;

  GEqualFunc       key_equal_func;

  volatile gint    ref_count;

#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

  GDestroyNotify   key_destroy_func;

  GDestroyNotify   value_destroy_func;

};

typedef struct

{

  GHashTable  *hash_table;

  gpointer     dummy1;

  gpointer     dummy2;

  int          position;

  gboolean     dummy3;

  int          version;

} RealIter;

/* 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

 * good distribution with poor hash functions. */

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);

}

/*

 * g_hash_table_lookup_node:

 * @hash_table: our #GHashTable

 * @key: the key to lookup against

 * @hash_return: optional key hash return location

 * Return value: index of the described #GHashNode

 *

 * Performs a lookup in the hash table.  Virtually all hash operations

 * will use this function internally.

 *

 * 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 empty node (never a tombstone).

 */

static inline guint

g_hash_table_lookup_node (GHashTable    *hash_table,

                          gconstpointer  key)

{

  GHashNode *node;

  guint node_index;

  guint hash_value;

  guint step = 0;

  /* Empty buckets have hash_value set to 0, and for tombstones, it's 1.

   * We need to make sure our hash value is not one of these. */

  hash_value = (* hash_table->hash_func) (key);

  if (G_UNLIKELY (hash_value <= 1))

    hash_value = 2;

  node_index = hash_value % hash_table->mod;

  node = &hash_table->nodes [node_index];

  while (node->key_hash)

    {

      /*  We first check if our full hash values

       *  are equal so we can avoid calling the full-blown

       *  key equality function in most cases.

       */

      if (node->key_hash == hash_value)

        {

          if (hash_table->key_equal_func)

            {

              if (hash_table->key_equal_func (node->key, key))

                break;

            }

          else if (node->key == key)

            {

              break;

            }

        }

      step++;

      node_index += step;

      node_index &= hash_table->mask;

      node = &hash_table->nodes [node_index];

    }

  return node_index;

}

/*

 * g_hash_table_lookup_node_for_insertion:

 * @hash_table: our #GHashTable

 * @key: the key to lookup against

 * @hash_return: key hash return location

 * Return value: index of the described #GHashNode

 *

 * 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.

 */

static inline guint

g_hash_table_lookup_node_for_insertion (GHashTable    *hash_table,

                                        gconstpointer  key,

                                        guint         *hash_return)

{

  GHashNode *node;

  guint node_index;

  guint hash_value;

  guint first_tombstone;

  gboolean have_tombstone = FALSE;

  guint step = 0;

  /* Empty buckets have hash_value set to 0, and for tombstones, it's 1.

   * We need to make sure our hash value is not one of these. */

  hash_value = (* hash_table->hash_func) (key);

  if (G_UNLIKELY (hash_value <= 1))

    hash_value = 2;

  *hash_return = hash_value;

  node_index = hash_value % hash_table->mod;

  node = &hash_table->nodes [node_index];

  while (node->key_hash)

    {

      /*  We first check if our full hash values

       *  are equal so we can avoid calling the full-blown

       *  key equality function in most cases.

       */

      if (node->key_hash == hash_value)

        {

          if (hash_table->key_equal_func)

            {

              if (hash_table->key_equal_func (node->key, key))

                return node_index;

            }

          else if (node->key == key)

            {

              return node_index;

            }

        }

      else if (node->key_hash == 1 && !have_tombstone)

        {

          first_tombstone = node_index;

          have_tombstone = TRUE;

        }

      step++;

      node_index += step;

      node_index &= hash_table->mask;

      node = &hash_table->nodes [node_index];

    }

  if (have_tombstone)

    return first_tombstone;

  return node_index;

}

/*

 * g_hash_table_remove_node:

 * @hash_table: our #GHashTable

 * @node: pointer to node to remove

 * @notify: %TRUE if the destroy notify handlers are to be called

 *

 * Removes a node from the hash table and updates the node count.

 * The node is replaced by a tombstone. No table resize is performed.

 *

 * If @notify is %TRUE then the destroy notify functions are called

 * for the key and value of the hash node.

 */

static void

g_hash_table_remove_node (GHashTable   *hash_table,

                          GHashNode    *node,

                          gboolean      notify)

{

  if (notify && hash_table->key_destroy_func)

    hash_table->key_destroy_func (node->key);

  if (notify && hash_table->value_destroy_func)

    hash_table->value_destroy_func (node->value);

  /* Erect tombstone */

  node->key_hash = 1;

  /* Be GC friendly */

  node->key = NULL;

  node->value = NULL;

  hash_table->nnodes--;

}

/*

 * 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.

 */

static void

g_hash_table_remove_all_nodes (GHashTable *hash_table,

                               gboolean    notify)

{

  int i;

  for (i = 0; i < hash_table->size; i++)

    {

      GHashNode *node = &hash_table->nodes [i];

      if (node->key_hash > 1)

        {

          if (notify && hash_table->key_destroy_func)

            hash_table->key_destroy_func (node->key);

          if (notify && hash_table->value_destroy_func)

            hash_table->value_destroy_func (node->value);

        }

    }

  /* We need to set node->key_hash = 0 for all nodes - might as well be GC

   * friendly and clear everything */

  memset (hash_table->nodes, 0, hash_table->size * sizeof (GHashNode));

  hash_table->nnodes = 0;

  hash_table->noccupied = 0;

}

/*

 * g_hash_table_resize:

 * @hash_table: our #GHashTable

 *

 * Resizes the hash table to the optimal size based on the number of

 * 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.

 *

 * 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.

 */

static void

g_hash_table_resize (GHashTable *hash_table)

{

  GHashNode *new_nodes;

  gint old_size;

  gint i;

  old_size = hash_table->size;

  g_hash_table_set_shift_from_size (hash_table, hash_table->nnodes * 2);

  new_nodes = g_new0 (GHashNode, hash_table->size);

  for (i = 0; i < old_size; i++)

    {

      GHashNode *node = &hash_table->nodes [i];

      GHashNode *new_node;

      guint hash_val;

      guint step = 0;

      if (node->key_hash <= 1)

        continue;

      hash_val = node->key_hash % hash_table->mod;

      new_node = &new_nodes [hash_val];

      while (new_node->key_hash)

        {

          step++;

          hash_val += step;

          hash_val &= hash_table->mask;

          new_node = &new_nodes [hash_val];

        }

      *new_node = *node;

    }

  g_free (hash_table->nodes);

  hash_table->nodes = new_nodes;

  hash_table->noccupied = hash_table->nnodes;

}

/*

 * 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.

 */

static inline void

g_hash_table_maybe_resize (GHashTable *hash_table)

{

  gint noccupied = hash_table->noccupied;

  gint size = hash_table->size;

  if ((size > hash_table->nnodes * 4 && size > 1 << HASH_TABLE_MIN_SHIFT) ||

      (size <= noccupied + (noccupied / 16)))

    g_hash_table_resize (hash_table);

}

/**

 * g_hash_table_new:

 * @hash_func: a function to create a hash value from a key.

 *   Hash values are used to determine where keys are stored within the

 *   #GHashTable data structure. The g_direct_hash(), g_int_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: a function to check two keys for equality.  This is

 *   used when looking up keys in the #GHashTable.  The g_direct_equal(),

 *   g_int_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.

 *

 * Creates a new #GHashTable with a reference count of 1.

 *

 * Return value: a new #GHashTable.

 **/

EXPORT_C GHashTable*

g_hash_table_new (GHashFunc    hash_func,

                  GEqualFunc   key_equal_func)

{

  return g_hash_table_new_full (hash_func, key_equal_func, NULL, NULL);

}

/**

 * g_hash_table_new_full:

 * @hash_func: a function to create a hash value from a key.

 * @key_equal_func: a function to check two keys for equality.

 * @key_destroy_func: a function to free the memory allocated for the key

 *   used when removing the entry from the #GHashTable or %NULL if you

 *   don't want to supply such a function.

 * @value_destroy_func: a function to free the memory allocated for the

 *   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.

 **/

EXPORT_C GHashTable*

g_hash_table_new_full (GHashFunc       hash_func,

                       GEqualFunc      key_equal_func,

                       GDestroyNotify  key_destroy_func,

                       GDestroyNotify  value_destroy_func)

{

  GHashTable *hash_table;

  hash_table = g_slice_new (GHashTable);

  g_hash_table_set_shift (hash_table, HASH_TABLE_MIN_SHIFT);

  hash_table->nnodes             = 0;

  hash_table->noccupied          = 0;

  hash_table->hash_func          = hash_func ? hash_func : g_direct_hash;

  hash_table->key_equal_func     = key_equal_func;

  hash_table->ref_count          = 1;

#ifndef G_DISABLE_ASSERT

  hash_table->version            = 0;

#endif

  hash_table->key_destroy_func   = key_destroy_func;

  hash_table->value_destroy_func = value_destroy_func;

  hash_table->nodes              = g_new0 (GHashNode, hash_table->size);

  return hash_table;

}