/* Basic hashtables that grow as needed

   Do not mix iteration and insertion, as insertion may cause the
   table to grow!

   Before including this file, some definitions/inclusions are needed.

   key and value must be the appropriate types.
   pair must be defined to be a struct containing a key k and a value v.
   list must be defined to be a list of pairs (see list.h).
   hash is the hashtable type.

   hashcode(key k, int N) must be supplied and must return an int between
   0 and N - 1 inclusive.

   make_pair(k, v) must return a pair.

   cons(), head(), tail(), set_tail(), dreverse(), and freecell() must be 
   defined on lists. (freecell() is like tail(), but also frees the memory for
   the first cons cell.)

   ALLOC(type, number) is used to allocate space.
   FREE(pointer) is used to deallocate.

   functions defined are:
   hashtable()
   hashtable_with_size()
   delete_hashtable()
   insert()
   delete()
   contains()
   get()
   get_if_present()

   get() returns NOT_FOUND, which defaults to 0, if the key is not found.

   The user may also set INITIAL_SIZE, NEXT_SIZE, and RESIZE_RATIO.
*/

#include "bool.h"

#ifndef NOT_FOUND
#define NOT_FOUND 0
#endif

#ifndef INITIAL_SIZE
#define INITIAL_SIZE 7
#endif

#ifndef NEXT_SIZE
#define NEXT_SIZE(x) ((x) * 2 - 1)
#endif

#ifndef RESIZE_RATIO
#define RESIZE_RATIO 0.9
#endif

typedef struct hash {
  int N;
  list **bucket; /* each of N buckets is a linked list */
  int entries;
} hash;

TI_INLINE(hashtable_with_size) hash *hashtable_with_size(int size)
{
  int i;
  hash *h = ALLOC(hash, 1);
  h->N = size;
  h->bucket = ALLOC(list *, size);
  for (i = 0; i < size; i++)
    h->bucket[i] = NULL;
  h->entries = 0;
  return h;
}

TI_INLINE(hashtable) hash *hashtable()
{
  return hashtable_with_size(INITIAL_SIZE);
}

TI_INLINE(delete_hashtable) void delete_hashtable(hash *h)
{
  FREE(h->bucket);
  FREE(h);
}

TI_INLINE(insert) void insert(key k, value v, hash *h)
{
  int q;
  if (h->entries > h->N * RESIZE_RATIO) {
    hash *z = hashtable_with_size(NEXT_SIZE(h->N));
    list *l;
    int i;
    for (i = 0; i < h->N; i++)
      for (l = h->bucket[i]; l != NULL; l = freecell(l))
	insert(head(l).k, head(l).v, z);
    FREE(h->bucket);
    h->N = z->N;
    h->bucket = z->bucket;
    FREE(z);
    for (i = 0; i < h->N; i++)
      h->bucket[i] = dreverse(h->bucket[i]);
    /* printf("resized to %d\n", h->N); */
  }
  q = hashcode(k, h->N);
  h->bucket[q] = cons(make_pair(k, v), h->bucket[q]);
  h->entries++;
}

TI_INLINE(delete) void delete(key k, hash *h)
{
  int q = hashcode(k, h->N);
  list *l = h->bucket[q];
  if (l == NULL)
    return;
  else if (head(l).k == k) {
    h->bucket[q] = freecell(h->bucket[q]);
    h->entries--;
    return;
  } else {
    for (; tail(l) != NULL; l = tail(l))
      if (head(tail(l)).k == k) {
	set_tail(l, freecell(tail(l)));
	h->entries--;
	return;
      }
  }
}

TI_INLINE(contains) bool contains(key k, hash *h)
{
  list *l;
  for (l = h->bucket[hashcode(k, h->N)]; l != NULL; l = tail(l))
    if (head(l).k == k)
      return true;
  return false;
}

TI_INLINE(get) value get(key k, hash *h)
{
  list *l;
  for (l = h->bucket[hashcode(k, h->N)]; l != NULL; l = tail(l))
    if (head(l).k == k)
      return head(l).v;
  return NOT_FOUND;
}

TI_INLINE(get_if_present) bool get_if_present(key k, value *v, hash *h)
{
  list *l;
  for (l = h->bucket[hashcode(k, h->N)]; l != NULL; l = tail(l))
    if (head(l).k == k)
      return ((*v = head(l).v), true);
  return false;
}