#include <stdlib.h>
#include <strings.h>

#include "htable.h"

typedef struct htable HTABLE;
typedef struct entry ENTRY;

struct entry {
  ENTRY *link;
  void *data;
  } ;

struct htable {
  int entries;
  int maxentries;
  int tblsize;
  unsigned int (*sizefxn)(unsigned int);
  unsigned int (*hfxn)(void *, unsigned int);
  int (*cmpfxn)(void *, void *);
  ENTRY **table;
  } ;

static unsigned int hsizefxn(unsigned int old)
{
 if (old == 0) return(15);
 return(old+old+1);
}

static unsigned int gethash(HTABLE *t, void *e)
{
 unsigned int i;

 i = (*t->hfxn)(e,t->tblsize);
 return((int)(i%t->tblsize));
}

static void grow_table(HTABLE *t)
{
 unsigned int newsize;
 unsigned int oldsize;
 ENTRY **newtbl;
 ENTRY *e;
 ENTRY *e2;
 unsigned int h;
 int i;
 ENTRY **oldtbl;

 oldsize = t->tblsize;
 oldtbl = t->table;
 newsize = (*t->sizefxn)(oldsize);
 if (newsize <= oldsize) newsize = hsizefxn(oldsize);
 newtbl = malloc(newsize*sizeof(ENTRY *));
 t->tblsize = newsize;
 t->table = newtbl;
 t->maxentries = 2 * newsize;
 for (i=newsize-1;i>=0;i--) newtbl[i] = 0;
 for (i=oldsize-1;i>=0;i--)
  { for (e=oldtbl[i];e;e=e2)
     { e2 = e->link;
       h = gethash(t,e->data);
       e->link = newtbl[h];
       newtbl[h] = e;
     }
  }
 free(oldtbl);
}

void *new_htable(unsigned int (*hfxn)(void *, unsigned int), int (*cmpfxn)(void *, void *))
{
 HTABLE *h;

 h = malloc(sizeof(HTABLE));
 h->entries = 0;
 h->sizefxn = hsizefxn;
 h->tblsize = 0;
 h->hfxn = hfxn;
 h->cmpfxn = cmpfxn;
 h->table = 0;
 grow_table(h);
 return(h);
}

static int new_entry(HTABLE *t)
{
 t->entries ++;
 if (t->entries > t->maxentries)
  { grow_table(t);
    return(1);
  }
 else
  { return(0);
  }
}

#define tbl ((HTABLE *)Tbl)

int htable_entries(void *Tbl)
{
 return(tbl->entries);
}

void hset_cmpfxn(void *Tbl, int (*cmpfxn)(void *, void *))
{
 tbl->cmpfxn = cmpfxn;
}

void *find_hentry(void *Tbl, void *entry)
{
 ENTRY *e;

 for (e=tbl->table[gethash(tbl,entry)];e;e=e->link)
  { if ((*tbl->cmpfxn)(e->data,entry) == 0)
     { return(e->data);
     }
  }
 return(0);
}

void add_new_hentry(void *Tbl, void *entry)
{
 unsigned int h;
 ENTRY *e;

 new_entry(tbl);
 h = gethash(tbl,entry);
 e = malloc(sizeof(ENTRY));
 e->link = tbl->table[h];
 tbl->table[h] = e;
 e->data = entry;
}

void *add_hentry(void *Tbl, void *entry)
{
 unsigned int h;
 ENTRY *e;

 h = gethash(tbl,entry);
 for (e=tbl->table[h];e;e=e->link)
  { if ((*tbl->cmpfxn)(e->data,entry) == 0)
     { return(e->data);
     }
  }
 if (new_entry(tbl)) h = gethash(tbl,entry);
 e = malloc(sizeof(ENTRY));
 e->link = tbl->table[h];
 tbl->table[h] = e;
 e->data = entry;
 return(0);
}

void *del_hentry(void *Tbl, void *entry)
{
 ENTRY *e;
 ENTRY **E;
 void *rv;

 E = &tbl->table[gethash(tbl,entry)];
 while ((e = *E))
  { if ((*tbl->cmpfxn)(e->data,entry) == 0)
     { *E = e->link;
       rv = e->data;
       free(e);
       tbl->entries --;
       return(rv);
     }
    E = &e->link;
  }
 return(0);
}

void *del_one_hentry(void *Tbl)
{
 static unsigned int lastbucket = 0;
 unsigned int i;
 ENTRY *e;
 void *rv;

 if (tbl->entries == 0) return(0);
 lastbucket %= tbl->tblsize;
 i = lastbucket;
 if (!tbl->table[i])
  { for (i++;!tbl->table[i];i=(i+1)%tbl->tblsize)
     { if (i == lastbucket)
	{ abort();
	  exit(1);
	}
     }
  }
 lastbucket = i;
 e = tbl->table[i];
 tbl->table[i] = e->link;
 rv = e->data;
 free(e);
 tbl->entries --;
 return(rv);
}

int del_this_hentry(void *Tbl, void *entry)
{
 ENTRY *e;
 ENTRY **E;

 E = &tbl->table[gethash(tbl,entry)];
 while ((e = *E))
  { if (e->data == entry)
     { *E = e->link;
       free(e);
       tbl->entries --;
       return(1);
     }
    E = &e->link;
  }
 return(0);
}

void map_htable(void *Tbl, void (*fxn)(void *))
{
 int i;
 ENTRY *e;

 for (i=tbl->tblsize-1;i>=0;i--)
  { for (e=tbl->table[i];e;e=e->link)
     { (*fxn)(e->data);
     }
  }
}

void clear_htable(void *Tbl)
{
 int i;
 ENTRY *e;
 ENTRY *e2;

 for (i=tbl->tblsize-1;i>=0;i--)
  { for (e=tbl->table[i];e;e=e2)
     { e2 = e->link;
       free(e);
     }
    tbl->table[i] = 0;
  }
 tbl->entries = 0;
}

void free_htable(void *Tbl)
{
 clear_htable(Tbl);
 free((char *)tbl->table);
 free(tbl);
}

/* Now come the "provided" hfxns and cmpfxns */

unsigned int string_hfxn(void *str, unsigned int siz)
{
 unsigned int i;
 unsigned char *s;

 i = 0;
 for (s=str;*s;s++)
  { i = (i << 5) + (i >> 28) + *s;
  }
 i &= (-(unsigned int)1) >> 1;
 return(i%siz);
}

int string_cmpfxn(void *s1, void *s2)
{
 return(strcmp(s1,s2));
}