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

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

#include "htable.h"

typedef struct htable HTABLE;
typedef struct entry ENTRY;

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

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

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

static int gethash(const HTABLE *t, const 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(unsigned int (*hfxn)(const void *, int), int (*cmpfxn)(const void *, const void *))
{
 HTABLE *h;
 int i;

 h = malloc(sizeof(HTABLE));
 h->entries = 0;
 h->sizefxn = hsizefxn;
 h->tblsize = 0;
 h->table = 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)
#define ctbl ((const HTABLE *)Tbl)

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

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

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

 for (e=ctbl->table[gethash(ctbl,entry)];e;e=e->link)
  { if ((*ctbl->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, const 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);
}

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);
}

unsigned int string_hfxn(const void *str, int siz)
{
 unsigned int i;
 unsigned long int v;

 v = 0x12345678;
 for (i=0;((const unsigned char *)str)[i];i++)
  { v ^= ((const unsigned char *)str)[i];
    if (v & 1) v = (v >> 1) ^ 0xedb88320; else v >>= 1;
  }
 return(v%siz);
}

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