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

#include "callcheck.h"
#include "hash_table.h"
#include "wrappers.h"


#define INITIAL_HASH 0
#define EMPTY_TABLE 0

#define TRUE 1
#define FALSE 0

#define NO_ERROR 0

#define EMPTY 0


/*
 * calculates base raised to the exponent
 *
 * Takes the base and the power, returns the result.
 * 
 * http://mitpress.mit.edu/sicp/chapter1/node15.html
 *
 * b^n = b * b^(n-1) for odd n
 * b^n = b^(n/2) * b^(n/2) for even n
 */
unsigned int powi (unsigned int base, unsigned int power) {
  int temp;

  if (power == 0) {
    return 1;
  }
  else if (power % 2 == 0) {
    temp = powi(base, power / 2);
    return temp * temp;
  }
  else {
    return base * powi(base, power - 1);
  }
}


/*
 * calclulates a hash code for a string
 * 
 * Takes a pointer to the string, returns the key.
 * 
 * http://java.sun.com/j2se/1.5.0/docs/api/java/lang/String.html#hashCode()
 *
 * code = s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
 * n = length, ^ = exponent
 */
unsigned int str_hash_code (const void *v_ptr) {
  const char *ptr;
  unsigned int code = 0;
  unsigned int n;
  unsigned int i;

  ptr = v_ptr;
  n = strlen(ptr);

  for (i = EMPTY; i < n; i++) {
    code += ptr[i] * powi(31, n - (i + 1));
  }

  return code;
}


/*
 * initializes the hash table to a given capacity, load factor, with the
 * given comparator and hash functions
 */
void hash_init (hash_table_t *ht, int capacity, int lf,
		unsigned int (*hash)(const void *),
		int (*cmp)(const void *, const void *)) {
  void **temp;
  int i;

  temp = ra_malloc(sizeof(void *) * (size_t) capacity);
  callcheck(temp != NULL);

  for (i = EMPTY; i < capacity; i++) {
    temp[i] = NULL;
  }

  ht->lf = lf;
  ht->capacity = capacity;
  ht->count = EMPTY_TABLE;
  ht->table = temp;
  ht->hash = hash;
  ht->cmp = cmp;
}


/*
 * inserts a value into the hash table, possibly reallocating and rehashing it
 */
void hash_insert (hash_table_t *ht, void *ptr) {
  unsigned int i;
  hash_table_t temp;

  /*
   * 2^P - 1 is either prime or doesn't have many factors (many are Mersenne
   * primes). I allocate the whole page to be nice to malloc.
   */
  i = ht->hash(ptr);
  i %= (ht->capacity - 1);
  
  /*
   * use linear collision avoidance
   */
  while (ht->table[i] != NULL) {
    if (!ht->cmp(ht->table[i], ptr)) {
      return;
    }

    i = (i + 1) % (ht->capacity - 1);
  }

  ht->table[i] = ptr;
  ht->count++;

  /*
   * reallocate and rehash the table
   */
  if (ht->count * ht->lf > ht->capacity) {
    hash_init(&temp, ht->capacity * ht->lf, ht->lf, ht->hash, ht->cmp);

    for (i = EMPTY; i < ht->capacity - 1; i++) {
      if (ht->table[i] != NULL) {
	hash_insert(&temp, ht->table[i]);
      }
    }

    free(ht->table);
    *ht = temp;
  }
}


/*
 * tests if a value is present in the hash table
 */
int hash_test (hash_table_t *ht, void *ptr) {
  unsigned int i;

  i = ht->hash(ptr);
  i %= ht->capacity - 1;

  while (TRUE) {
    if (ht->table[i] == NULL) {
      return FALSE;
    }
    else if (!ht->cmp(ht->table[i], ptr)) {
      return TRUE;
    }

    /*
     * linear collision avoidance
     */
    i++;
    i %= ht->capacity - 1;
  }

  return FALSE;
}