/*
 * Copyright (C) 1996-1998 Ilya Ryzhenkov (orangy@inetlab.com)
 * This file maintains hash tables management.
 */
#include <limits.h>
#include "helpdefs.h"
#include "hash.h"


THashTab *_hash_createtab( unsigned maxsize, unsigned long (*hash)(void*), int(*cmp)(void*,void*))
{
 int i;
 THashTab *tab;
 if (maxsize<16 || !hash || !cmp) return 0;
 tab=NEW(THashTab);
 if (!tab) return 0;
 tab->items=NEWAR(THashElem,maxsize);
 for (i=0; i<maxsize; i++)
   tab->items[i].next=tab->items[i].prev=tab->items[i].item=0;

 tab->size=maxsize;
 tab->numitems=0;
 tab->hash=hash;
 tab->cmp=cmp;
 return tab;
}

int _hash_addsym(THashTab *tab, void *item)
{
 unsigned int hashval;
 THashElem *list=0,*nw;
 if (!tab || !item) return 0;
 //printf("Adding '%s' \n ",*(char**)item);
 hashval=(tab->hash(item))%(tab->size);
 list=tab->items+hashval;
 if (!list->item) { list->item=item; return 1; }
 nw=NEW(THashElem);
 nw->prev=list; nw->next=list->next;
 if (nw->next) nw->next->prev=nw;
 list->next=nw;
 nw->item=list->item;
 list->item=item;
 return 1;
}

static THashElem *lastfound;
void *_hash_findsym(THashTab *tab , void *item)
{
 unsigned int hashval;
 THashElem *list=0;
 if (!tab || !item) return 0;
 hashval=(tab->hash(item))%(tab->size);
 list=tab->items+hashval;
 if (!list->item) return 0;
 //printf("Searching for '%s' \n",*(char**)item);
 while (list) {
   if (tab->cmp(item,list->item)) { lastfound=list; return list->item; }
   list=list->next;
 }
 //printf("Failed!\n");
 lastfound=0;
 return 0;
}

void *_hash_delsym(THashTab *tab, void *item )
{
 void *retval;
 if (!tab || !item) return 0;
 //printf("Deleting '%s' \n ",*(char**)item);
 _hash_findsym(tab,item);
 if (!lastfound) return 0;
 retval=lastfound->item;

 if (!lastfound->prev) // allocated - not first
 {
  if (!lastfound->next) // the only one
   {
    lastfound->item=0;
    return retval;
   }
  lastfound->item=lastfound->next->item;
  lastfound=lastfound->next;
 }
 if (lastfound->prev) lastfound->prev->next=lastfound->next;
 if (lastfound->next) lastfound->next->prev=lastfound->prev;
 free(lastfound);
 return retval;
}

int _hash_deltab(THashTab *tab)
{
 int i;
 THashElem *list,*p;
 for (i=0; i<tab->size; i++)
  {
   list=(tab->items+i)->next;
   while (list)
   {
    p=list->next;
    FREE(list->item);
    free(list);
    list=p;
   }
  }
 free(tab->items);
 return 1;
}

static THashTab *_htab;
static unsigned long _hidx;
static THashElem *_helem;

int _hash_iter_init(THashTab *tab)
{
 _helem=0;
 if (!tab) return 0;
 _htab=tab;
 for (_hidx=0; _hidx<tab->size; _hidx++)
  if (tab->items[_hidx].item) break;
 if (_hidx==tab->size) return 0;
 _helem=tab->items+_hidx;
 return 1;
}

void *_hash_iter_next(void)
{
 void *retval;
 if (!_helem) return 0;
 retval=_helem->item;
 _helem=_helem->next;
 if (!_helem)
 {
  _hidx++;
  for (; _hidx<_htab->size; _hidx++)
   if (_htab->items[_hidx].item) break;
  if (_hidx==_htab->size) _helem=0; else _helem=_htab->items+_hidx;
 }
 return retval;
}

#define BITS_IN_int		( sizeof(int) * CHAR_BIT )
#define THREE_QUARTERS	((int) ((BITS_IN_int * 3) / 4 ))
#define ONE_EIGTH		((int) (BITS_IN_int / 8))
#define HIGH_BITS		( ~((unsigned int)(~0) >> ONE_EIGTH ))

unsigned int FHashString ( const char * datum )
{
 unsigned int hash_value, i;
 for ( hash_value = 0; *datum; ++datum )
   {
    hash_value<<=ONE_EIGTH;
    hash_value+=*datum;
    if (( i = hash_value & HIGH_BITS ) != 0 )
    hash_value=(hash_value^(i>>THREE_QUARTERS))&~HIGH_BITS;
   }
 return hash_value;
}