/****************************************************************************
    Copyright (C) 1987-2005 by Jeffery P. Hansen

    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    This program 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 General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program; if not, write to the Free Software
    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
****************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "hash.h"

void *ob_malloc(int,char*);
void *ob_calloc(int,int,char*);
void ob_free(void*);
char *ob_strdup(const char*);
void ob_touch(void*);

/*
   Round N up to a power of 2.
*/
static unsigned int roundup(unsigned int N)
{
  unsigned P = N & (N ^ -N);

  if (P) {
    do {
      N = P;
      P = N & (N ^ -N);
    } while (P);
    N <<= 1;
  }
  return N;
} 

static hashcode_t inthash(hashcode_t key)
{
  key += 123456;
  key += (key << 12);
  key ^= (key >> 22);
  key += (key << 4);
  key ^= (key >> 9);
  key += (key << 10);
  key ^= (key >> 2);
  key += (key << 7);
  key ^= (key >> 12);

  return key;
}

static hashcode_t strhash(const char *s)
{
  hashcode_t N = 0;
  hashcode_t H = 0;
  int i;

  for (i = 0;*s;s++, i++) {
    N <<= 8;
    N |= (unsigned char) *s;
    if ((i & 3) == 3)
      H = inthash(H + N);
  } 
  H = inthash(H + N);
  return H;
}


static HashElem *new_SHashElem(const char *key,hashcode_t hcode, void *val)
{	
  HashElem *E = (HashElem*) ob_malloc(sizeof(HashElem),"HashElem");

  E->key.s = ob_strdup(key);
  E->hashcode = hcode;
  E->value = val;
  E->next = 0;

  return E;
}

static HashElem *new_NHashElem(int key,hashcode_t hcode,void *val)
{	
  HashElem *E = (HashElem*) ob_malloc(sizeof(HashElem),"HashElem");

  E->key.d = key;
  E->hashcode = hcode;
  E->value = val;
  E->next = 0;

  return E;
}

void SHashElem_uninit(HashElem *E)
{
  ob_free(E->key.s);
}

Hash *new_Hash()
{
  Hash *H = (Hash*) ob_malloc(sizeof(Hash),"Hash");

  Hash_init(H);
  return H;
}

void delete_Hash(Hash *H,HashElemDelFunc *hdel)
{
  Hash_uninit(H,hdel);
  ob_free(H);
}

void Hash_init(Hash *H)
{
  ob_touch(H);
  H->size = roundup(INITIAL_HASHSIZE);
  H->mask = H->size-1; 
  H->num = 0;
  H->loop_ok = 0;
  H->elems = (HashElem**) ob_calloc(H->size,sizeof(HashElem*),"HashElem[]");
  ob_touch(H->elems);
}

void Hash_uninit(Hash *H,HashElemDelFunc *hdel)
{
  int i;

  ob_touch(H);
  ob_touch(H->elems);

  for (i = 0;i < H->size;i++) {
    HashElem *E,*N;
    for (E = H->elems[i];E;E = N) {
      N = E->next;
      if (hdel)
	(*hdel)(E);
      ob_free(E);
    }
  }
  ob_free(H->elems);
}

HashElem *Hash_first(Hash *H)
{
  int i;

  H->loop_ok = 1;		/* This debugging flag does not need an ob_touch */
  for (i = 0;i < H->size;i++)
    if (H->elems[i])
      return H->elems[i];
  return 0;
}

HashElem *Hash_next(Hash *H,HashElem *E)
{
  int A;

  if (!H->loop_ok) {
    printf("echo Illegal sequential hash table access.\n");
    fflush(stdout);
  }


  if (E->next) return E->next;

  for (A = (E->hashcode & H->mask) + 1;A < H->size;A++)
    if (H->elems[A])
      return H->elems[A];

  return 0;
}

/*
   Double the size of a hash table
*/
void Hash_grow(Hash *H)
{
  int S = H->size;
  int i;
  HashElem **nea;

  ob_touch(H);
  ob_touch(H->elems);

  H->size <<= 1;
  H->mask = H->size - 1;
  nea = (HashElem**) ob_calloc(H->size,sizeof(HashElem*),"HashElem[]");

  for (i = 0;i < S;i++) {
    HashElem *E;
    while ((E = H->elems[i])) {
      hashcode_t A = E->hashcode & H->mask;
      H->elems[i] = E->next;
      ob_touch(E);
      E->next = nea[A];
      nea[A] = E;
    }
  }
  ob_free(H->elems);
  H->elems = nea;
}

void Hash_removeElem(Hash *H,int A,HashElem *E)
{
  HashElem *P;

  ob_touch(H);

  H->num--;

  H->loop_ok = 0;

  if (H->elems[A] == E) {
    ob_touch(H->elems);
    H->elems[A] = E->next;
    return;
  }

  for (P = H->elems[A];P->next != E;P = P->next);

  ob_touch(P);
  P->next = E->next;
}

void *SHash_find(Hash *H,const char *key)
{
  hashcode_t HC = strhash(key);
  hashcode_t A = HC & H->mask;
  HashElem *E;

  for (E = H->elems[A];E;E = E->next)
    if (E->hashcode == HC && strcmp(E->key.s,key) == 0)
      return E->value;
  return 0;
}

int SHash_insert(Hash *H,const char *key,void* val)
{
  hashcode_t HC = strhash(key);
  hashcode_t A = HC & H->mask;
  HashElem *E;

  ob_touch(H);

  H->loop_ok = 0;
  for (E = H->elems[A];E;E = E->next)
    if (E->hashcode == HC && strcmp(E->key.s,key) == 0)
      return -1;

  ob_touch(H->elems);
  E = new_SHashElem(key,HC,val);
  E->next = H->elems[A];
  H->elems[A] = E;
  H->num++;
  if (H->size*HASH_MAXLOAD < H->num)
    Hash_grow(H);

  return 0;
}

int SHash_replace(Hash *H,const char *key,void* val)
{
  hashcode_t HC = strhash(key);
  hashcode_t A = HC & H->mask;
  HashElem *E;

  ob_touch(H);
  ob_touch(H->elems);

  H->loop_ok = 0;
  for (E = H->elems[A];E;E = E->next)
    if (E->hashcode == HC && strcmp(E->key.s,key) == 0) {
      ob_touch(E);
      E->value = val;
      return 1;
    }

  E = new_SHashElem(key,HC,val);
  E->next = H->elems[A];
  H->elems[A] = E;
  H->num++;
  if (H->size*HASH_MAXLOAD < H->num)
    Hash_grow(H);

  return 0;
}

int SHash_remove(Hash *H,const char *key)
{
  hashcode_t HC = strhash(key);
  hashcode_t A = HC & H->mask;
  HashElem *E;

  ob_touch(H);

  H->loop_ok = 0;
  for (E = H->elems[A];E;E = E->next)
    if (E->hashcode == HC && strcmp(E->key.s,key) == 0) {
      Hash_removeElem(H,A,E);
      ob_free(E->key.s);
      ob_free(E);
      return 0;
    }

  return -1;
}

void Hash_flush(Hash *H,HashElemDelFunc *hdel)
{
  int i;

  ob_touch(H);
  ob_touch(H->elems);

  H->loop_ok = 0;

  for (i = 0;i < H->size;i++) {
    HashElem *E = H->elems[i];
    HashElem *N;
    for (;E;E = N) {
      N = E->next;
      if (hdel) (*hdel)(E);
      ob_free(E);
    }
    H->elems[i] = 0;
  }
  H->num = 0;
}



void *NHash_find(Hash *H,nkey_t key)
{
  hashcode_t HC = inthash(key);
  hashcode_t A = HC & H->mask;
  HashElem *E;

  for (E = H->elems[A];E;E = E->next)
    if (E->key.d == key)
      return E->value;
  return 0;
}

int NHash_insert(Hash *H,nkey_t key,void* val)
{
  hashcode_t HC = inthash(key);
  hashcode_t A = HC & H->mask;
  HashElem *E;

  ob_touch(H);
  ob_touch(H->elems);

  H->loop_ok = 0;

  for (E = H->elems[A];E;E = E->next)
    if (E->key.d == key)
      return -1;

  E = new_NHashElem(key,HC,val);
  E->next = H->elems[A];
  H->elems[A] = E;
  H->num++;
  if (H->size*HASH_MAXLOAD < H->num)
    Hash_grow(H);

  return 0;
}

int NHash_remove(Hash *H,nkey_t key)
{
  hashcode_t HC = inthash(key);
  hashcode_t A = HC & H->mask;
  HashElem *E;

  ob_touch(H);
  H->loop_ok = 0;

  for (E = H->elems[A];E;E = E->next)
    if (E->key.d == key) {
      Hash_removeElem(H,A,E);
      ob_free(E);
      return 0;
    }

  return -1;
}