/* This file is in the public domain. */

#include <stdio.h>
#include <stdlib.h>

#include "htable.h"

typedef struct htable HTABLE;
typedef struct entry ENTRY;

struct entry {
  struct entry *link;
  char *data; };

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

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

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

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

static void grow_table(HTABLE *t)
{
 int newsize;
 int oldsize;
 ENTRY **newtbl;
 ENTRY *e;
 ENTRY *e2;
 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(int (*hfxn)(void *, unsigned int), int (*cmpfxn)(void *, void *))
{
 HTABLE *h;
 int i;

 h = malloc(sizeof(HTABLE));
 h->entries = 0;
 h->sizefxn = hsizefxn;
 h->tblsize = 0;
 grow_table(h);
 h->hfxn = hfxn;
 h->cmpfxn = cmpfxn;
 h->table = malloc(h->tblsize*sizeof(ENTRY *));
 for (i=h->tblsize-1;i>=0;i--) h->table[i] = 0;
 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)
{
 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)
{
 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;
 char *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 int lastbucket = 0;
 int i;
 ENTRY *e;
 char *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)
	{ fprintf(stderr,"incorrect tbl->entries in hash table\n");
	  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);
}

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

 n = 0;
 for (i=tbl->tblsize-1;i>=0;i--)
  { for (e=tbl->table[i];e;e=e->link)
     { v = (*fxn)(e->data);
       if (v < 0) return(v);
       n += v;
     }
  }
 return(n);
}

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(tbl->table);
 free(tbl);
}

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

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

 i = 0;
 for (str=svp;*str;str++)
  { i = (i << 5) + (i >> 28) + *str;
  }
 i &= (~0U) >> 1;
 return(i%siz);
}

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