/* 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
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * 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_SET_MIN_SIZE 11
#define HASH_SET_MAX_SIZE 13845163


struct _GHashSet
{
  gint size;
  gint nnodes;
  gint frozen;
  GSList **nodes;
  GHashFunc hash_func;
  GCompareFunc compare_func;
};


static void       g_hash_set_resize  (GHashSet *hash_set);
static GSList **  g_hash_set_lookup_node (GHashSet *hash_set,
					  gconstpointer value);
static gint       g_hash_closest_prime (gint        num);


extern gint g_primes[];
extern gint g_nprimes;


GHashSet*
g_hash_set_new (GHashFunc    hash_func,
		GCompareFunc compare_func)
{
  GHashSet *hash_set;

  hash_set = g_new (GHashSet, 1);
  hash_set->size = 1;
  hash_set->nnodes = 0;
  hash_set->frozen = FALSE;
  hash_set->nodes = g_new (GSList*, 1);
  hash_set->hash_func = hash_func ? hash_func : g_direct_hash;
  hash_set->compare_func = compare_func;

  return hash_set;
}

void
g_hash_set_destroy (GHashSet *hash_set)
{
  gint i;

  g_return_if_fail (hash_set);
  
  for (i = 0; i < hash_set->size; i++)
    g_slist_free (hash_set->nodes[i]);

  if (hash_set->nodes)
    g_free (hash_set->nodes);
  g_free (hash_set);
}

static GSList **
g_hash_set_lookup_node (GHashSet *hash_set, gconstpointer value)
{
  GSList **node;
  GCompareFunc compare_func;
  
  compare_func = hash_set->compare_func;
  node = &hash_set->nodes[(* hash_set->hash_func) (value) % hash_set->size];

  if (compare_func)
    while (*node && !compare_func ((*node)->data, value))
      node = &(*node)->next;
  else
    while (*node && (*node)->data != value)
      node = &(*node)->next;

  return node;
}

void
g_hash_set_insert (GHashSet *hash_set, gpointer value)
{
  GSList **node;

  g_return_if_fail (hash_set);

  g_hash_set_resize (hash_set);

  node = g_hash_set_lookup_node (hash_set, value);

  if (!*node)
    {
      *node = g_slist_alloc();
      (*node)->data = value;
      hash_set->nnodes++;
      if (! hash_set->frozen)
	g_hash_set_resize (hash_set);
    }
  else
    (*node)->data = value;
}

void
g_hash_set_remove (GHashSet      *hash_set,
		   gconstpointer  value)
{
  GSList **node;
  GSList *del_node;

  g_return_if_fail (hash_set);

  node = g_hash_set_lookup_node (hash_set, value);

  if (!*node)
    return;
  
  del_node = *node;
  *node = (*node)->next;
  g_slist_free_1 (del_node);
}

gpointer
g_hash_set_lookup (GHashSet   *hash_set,
		   gconstpointer value)
{
  GSList *node;

  g_return_val_if_fail (hash_set, NULL);

  node = *g_hash_set_lookup_node (hash_set, value);
  
  return node ? node->data : NULL;
}

void
g_hash_set_freeze (GHashSet *hash_set)
{
  g_return_if_fail (hash_set);

  hash_set->frozen = TRUE;
}

void
g_hash_set_thaw (GHashSet *hash_set)
{
  g_return_if_fail (hash_set);

  hash_set->frozen = FALSE;

  g_hash_set_resize (hash_set);
}

void
g_hash_set_foreach (GHashSet *hash_set,
		    GFunc      func,
		    gpointer    user_data)
{
  gint i;

  g_return_if_fail (hash_set);

  for (i = 0; i < hash_set->size; i++)
    g_slist_foreach (hash_set->nodes[i], func, user_data);
}


static void
g_hash_set_resize (GHashSet *hash_set)
{
  GSList **new_nodes;
  GSList *node;
  GSList *next;
  gfloat nodes_per_list;
  guint hash_value;
  gint new_size;
  gint i;

  g_return_if_fail (hash_set);

  nodes_per_list = (gfloat) hash_set->nnodes / (gfloat) hash_set->size;

  if ((nodes_per_list > 0.3 || hash_set->size <= HASH_SET_MIN_SIZE)
      && (nodes_per_list < 3.0 || hash_set->size >= HASH_SET_MAX_SIZE))
    return;

  new_size = CLAMP(g_hash_closest_prime (hash_set->nnodes),
		   HASH_SET_MIN_SIZE,
		   HASH_SET_MAX_SIZE);
  new_nodes = g_new (GSList*, new_size);
  
  for (i = 0; i < new_size; i++)
    new_nodes[i] = NULL;
  
  for (i = 0; i < hash_set->size; i++)
    {
      node = hash_set->nodes[i];

      while (node)
	{
	  next = node->next;
	  hash_value = (* hash_set->hash_func) (node->data) % new_size;
	  node->next = new_nodes[hash_value];
	  new_nodes[hash_value] = node;
	  node = next;
	}
    }
  
  g_free (hash_set->nodes);
  
  hash_set->nodes = new_nodes;
  hash_set->size = new_size;
}

static gint
g_hash_closest_prime (gint num)
{
  gint i;

  for (i = 0; i < g_nprimes; i++)
    if ((g_primes[i] - num) > 0)
      return g_primes[i];

  return g_primes[g_nprimes - 1];
}

/* Returns the number of elements contained in the hash set. */
gint g_hash_set_size (GHashSet *hash_set)
{
  g_return_val_if_fail (hash_set, 0);

  return hash_set->nnodes;
}