util/neo_hash.c

/*
 * Copyright 2003-2004 Brandon Long
 * All Rights Reserved.
 *
 * ClearSilver Templating System
 *
 * This code is made available under the terms of the ClearSilver License.
 * http://www.clearsilver.net/license.hdf
 *
 */

#include "cs_config.h"

#include <stdlib.h>
#include <string.h>

#include "neo_misc.h"
#include "neo_err.h"
#include "neo_hash.h"

static NEOERR *_hash_resize(NE_HASH *hash);
static NE_HASHNODE **_hash_lookup_node (NE_HASH *hash, void *key, UINT32 *hashv);

NEOERR *ne_hash_init (NE_HASH **hash, NE_HASH_FUNC hash_func, NE_COMP_FUNC comp_func)
{
  NE_HASH *my_hash = NULL;

  my_hash = (NE_HASH *) calloc(1, sizeof(NE_HASH));
  if (my_hash == NULL)
    return nerr_raise(NERR_NOMEM, "Unable to allocate memory for NE_HASH");

  my_hash->size = 256;
  my_hash->num = 0;
  my_hash->hash_func = hash_func;
  my_hash->comp_func = comp_func;

  my_hash->nodes = (NE_HASHNODE **) calloc (my_hash->size, sizeof(NE_HASHNODE *));
  if (my_hash->nodes == NULL)
  {
    free(my_hash);
    return nerr_raise(NERR_NOMEM, "Unable to allocate memory for NE_HASHNODES");
  }

  *hash = my_hash;

  return STATUS_OK;
}

void ne_hash_destroy (NE_HASH **hash)
{
  NE_HASH *my_hash;
  NE_HASHNODE *node, *next;
  int x;

  if (hash == NULL || *hash == NULL)
    return;

  my_hash = *hash;

  for (x = 0; x < my_hash->size; x++)
  {
    node = my_hash->nodes[x];
    while (node)
    {
      next = node->next;
      free(node);
      node = next;
    }
  }
  free(my_hash->nodes);
  my_hash->nodes = NULL;
  free(my_hash);
  *hash = NULL;
}

NEOERR *ne_hash_insert(NE_HASH *hash, void *key, void *value)
{
  UINT32 hashv;
  NE_HASHNODE **node;

  node = _hash_lookup_node(hash, key, &hashv);

  if (*node)
  {
    (*node)->value = value;
  }
  else
  {
    *node = (NE_HASHNODE *) malloc(sizeof(NE_HASHNODE));
    if (node == NULL)
      return nerr_raise(NERR_NOMEM, "Unable to allocate NE_HASHNODE");

    (*node)->hashv = hashv;
    (*node)->key = key;
    (*node)->value = value;
    (*node)->next = NULL;
  }
  hash->num++;

  return _hash_resize(hash);
}

void *ne_hash_lookup(NE_HASH *hash, void *key)
{
  NE_HASHNODE *node;

  node = *_hash_lookup_node(hash, key, NULL);

  return (node) ? node->value : NULL;
}

void *ne_hash_remove(NE_HASH *hash, void *key)
{
  NE_HASHNODE **node, *remove;
  void *value = NULL;

  node = _hash_lookup_node(hash, key, NULL);
  if (*node)
  {
    remove = *node;
    *node = remove->next;
    value = remove->value;
    free(remove);
    hash->num--;
  }
  return value;
}

int ne_hash_has_key(NE_HASH *hash, void *key)
{
  NE_HASHNODE *node;

  node = *_hash_lookup_node(hash, key, NULL);

  if (node) return 1;
  return 0;
}

void *ne_hash_next(NE_HASH *hash, void **key)
{
  NE_HASHNODE **node = 0;
  UINT32 hashv, bucket;

  if (*key)
  {
    node = _hash_lookup_node(hash, key, NULL);

    if (*node)
    {
      bucket = (*node)->hashv & (hash->size - 1);
    }
    else
    {
      hashv = hash->hash_func(*key);
      bucket = hashv & (hash->size - 1);
    }
  }
  else
  {
    bucket = 0;
  }

  if (*node)
  {
    if ((*node)->next)
    {
      *key = (*node)->next->key;
      return (*node)->next->value;
    }
    bucket++;
  }

  while (bucket < hash->size)
  {
    if (hash->nodes[bucket])
    {
      *key = hash->nodes[bucket]->key;
      return hash->nodes[bucket]->value;
    }
    bucket++;
  }

  return NULL;
}

static NE_HASHNODE **_hash_lookup_node (NE_HASH *hash, void *key, UINT32 *o_hashv)
{
  UINT32 hashv, bucket;
  NE_HASHNODE **node;

  hashv = hash->hash_func(key);
  if (o_hashv) *o_hashv = hashv;
  bucket = hashv & (hash->size - 1);
  /* ne_warn("Lookup %s %d %d", key, hashv, bucket); */

  node = &(hash->nodes[bucket]);

  if (hash->comp_func)
  {
    while (*node && !(hash->comp_func((*node)->key, key)))
      node = &(*node)->next;
  }
  else
  {
    /* No comp_func means we're doing pointer comparisons */
    while (*node && (*node)->key != key)
      node = &(*node)->next;
  }

  /* ne_warn("Node %x", node); */
  return node;
}

/* Ok, we're doing some weirdness here... */
static NEOERR *_hash_resize(NE_HASH *hash)
{
  NE_HASHNODE **new_nodes;
  NE_HASHNODE *entry, *prev;
  int x, next_bucket;
  int orig_size = hash->size;
  UINT32 hash_mask;

  if (hash->size > hash->num)
    return STATUS_OK;

  /* We always double in size */
  new_nodes = (NE_HASHNODE **) realloc (hash->nodes, (hash->size*2) * sizeof(NE_HASHNODE));
  if (new_nodes == NULL)
    return nerr_raise(NERR_NOMEM, "Unable to allocate memory to resize NE_HASH");

  hash->nodes = new_nodes;
  orig_size = hash->size;
  hash->size = hash->size*2;

  /* Initialize new parts */
  for (x = orig_size; x < hash->size; x++)
  {
    hash->nodes[x] = NULL;
  }

  hash_mask = hash->size - 1;

  for (x = 0; x < orig_size; x++)
  {
    prev = NULL;
    next_bucket = x + orig_size;
    for (entry = hash->nodes[x]; 
	 entry; 
	 entry = prev ? prev->next : hash->nodes[x]) 
    {
      if ((entry->hashv & hash_mask) != x)
      {
	if (prev)
	{
	  prev->next = entry->next;
	}
	else
	{
	  hash->nodes[x] = entry->next;
	}
	entry->next = hash->nodes[next_bucket];
	hash->nodes[next_bucket] = entry;
      }
      else
      {
	prev = entry;
      }
    }
  }
  
  return STATUS_OK;
}

int ne_hash_str_comp(const void *a, const void *b)
{
  return !strcmp((const char *)a, (const char *)b);
}

UINT32 ne_hash_str_hash(const void *a)
{
  return ne_crc((unsigned char *)a, strlen((const char *)a));
}

int ne_hash_int_comp(const void *a, const void *b)
{
  if (a == b) return 1;
  return 0;
}

UINT32 ne_hash_int_hash(const void *a)
{
  return (UINT32)(long)(a);
}