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

#define ARR_SIZE 24

struct htype {
  int index;
  const char * val;
  struct htype *next;
};

unsigned long genHash(const char *str, const size_t size){
  unsigned long hash = 5381;
  int c;

  while ((c = *str++))
    hash = ((hash << 5) + hash) + c;

  return hash % size;
}

void initHashTable(struct htype * ht, const size_t size) {
  size_t i = 0;
  for (i = 0; i < size; i++) {
    ht->index = -1;
    ht->val = NULL;
    ht->next = NULL;
    ++ht;
  }
}

struct htype* createHashTable(const size_t size) {
  void * mem = calloc(size, sizeof(struct htype));
  if (mem == NULL) {
    fputs("Memory allocation failed!", stderr);
    exit(0);
  }
  return mem;
}

void displayList(const struct htype *h) {
  fprintf(stdout, "\t\t%d %s\n", h->index, h->val);
  if (h->next) {
    displayList(h->next);
  }
}

void display(const struct htype * ht, const size_t size) {
  size_t i = 0;
  for (; i < size; ++i) {
    if (ht->val != NULL) {
      fprintf(stdout, "[%ld]: %d, %s, %p\n", i, ht->index, ht->val, (void*)ht->next);
      if (ht->next) {
	displayList(ht->next);
      }
    }
    ht++;
  }
} 

void addString(struct htype * ht, const char * str, const size_t size) {
  unsigned long hsh = genHash(str, size);
  struct htype * pos = ht + hsh;
  if (pos->index == -1) {
    pos->index = hsh;
    pos->val = str;
  }else {
    if (strcmp(str, pos->val) != 0) {
      struct htype *n = pos->next;
      while (n) {
	if (strcmp(n->val, str) == 0) {
	  return;
	}else {
	  n = n->next;
	}
      }
      struct htype * nt = (struct htype*)malloc(sizeof(struct htype));
      if (nt == NULL) {
	fputs("malloc failed!\n", stderr);
      }
      struct htype *old = pos->next;
      nt->index = hsh;
      nt->val = str;
      nt->next = old;
      pos->next = nt;
    }
  }
}

bool findStr(const struct htype * ht, const char * str, const size_t size) {
  unsigned long hv = genHash(str, size);
  const struct htype * pos = ht + hv;
  if (strcmp(pos->val, str) == 0) {
    return true;
  }else {
    struct htype * n = pos->next;
    while (n) {
      if (strcmp(n->val, str) == 0) {
	return true;
      }
      n = n->next;
    }
  }
  return false;
}

void removeStr(struct htype * ht, const char * str, const size_t size) {
  unsigned long hv = genHash(str, size);
  struct htype * pos = ht + hv;
  if (pos->index != -1) {
    if (strcmp(pos->val, str) == 0) {
      if (pos->next) {
	struct htype * nt = pos->next->next;
	pos->index = pos->next->index;
	pos->val = pos->next->val;
	pos->next = nt;
	free(pos->next);
      }else {
	pos->index = -1;
	pos->val = NULL;
      }
      return;
    }
    struct htype * nt = pos;
    while (nt->next) {
      if (strcmp(nt->next->val, str) == 0) {
	struct htype *nn = nt->next->next;
	free(nt->next);
	nt->next = nn;
	return;
      }
      nt = nt->next;
    }
  }
}

void freeList(struct htype * ht) {
  if (ht->next) {
    freeList(ht->next);
  }
  free(ht);
}

void freeHashTable(struct htype * ht, const size_t size) {
  struct htype * orig = ht;
  size_t i = 0;
  for (; i < size; ++i) {
    if ((ht + i)->next) {
      freeList((ht + i)->next);
    }
  }
  free(orig);
}

int main(int argc, char **argv) {
  struct htype * hashTable = createHashTable(ARR_SIZE);
  initHashTable(hashTable, ARR_SIZE);
  addString(hashTable, "Salty", ARR_SIZE);
  addString(hashTable, "Cracker", ARR_SIZE);
  addString(hashTable, "Emily", ARR_SIZE);
  addString(hashTable, "Angela", ARR_SIZE);
  addString(hashTable, "Richard", ARR_SIZE);
  addString(hashTable, "John", ARR_SIZE);
  addString(hashTable, "Betty", ARR_SIZE);
  addString(hashTable, "Zebra", ARR_SIZE);
  addString(hashTable, "Bobby", ARR_SIZE);
  addString(hashTable, "Kenny", ARR_SIZE);
  addString(hashTable, "Brenda", ARR_SIZE);
  addString(hashTable, "Dart", ARR_SIZE);
  addString(hashTable, "Cat", ARR_SIZE);
  addString(hashTable, "Dog", ARR_SIZE);
  addString(hashTable, "Bird", ARR_SIZE);
  addString(hashTable, "Lion", ARR_SIZE);
  addString(hashTable, "Tweety", ARR_SIZE);
  addString(hashTable, "Tank", ARR_SIZE);
  addString(hashTable, "Car", ARR_SIZE);
  addString(hashTable, "Gun", ARR_SIZE);
  addString(hashTable, "Apple", ARR_SIZE);
  addString(hashTable, "Plum", ARR_SIZE);
  addString(hashTable, "Run", ARR_SIZE);
  addString(hashTable, "Peel", ARR_SIZE);
  addString(hashTable, "See", ARR_SIZE);
  addString(hashTable, "Sun", ARR_SIZE);
  addString(hashTable, "Mouse", ARR_SIZE);
  addString(hashTable, "Speaker", ARR_SIZE);
  addString(hashTable, "Key", ARR_SIZE);
  addString(hashTable, "Song", ARR_SIZE);
  addString(hashTable, "Switch", ARR_SIZE);
  addString(hashTable, "On", ARR_SIZE);
  removeStr(hashTable, "Gun", ARR_SIZE);
  removeStr(hashTable, "Apple", ARR_SIZE);
  removeStr(hashTable, "Switch", ARR_SIZE);
  removeStr(hashTable, "Lion", ARR_SIZE);
  display(hashTable, ARR_SIZE);
  removeStr(hashTable, "Gun", ARR_SIZE);
  display(hashTable, ARR_SIZE);
  freeHashTable(hashTable, ARR_SIZE);
  return 0;
}