#include <stdlib.h>
#include <stdio.h>
#include <sys/time.h>
#include <stdint.h>
#include <string.h>

#define CHAINING 1
#define POWER_OF_2 1
#define INITIAL_SIZE 16
#define INITIAL_PRIME 17

#define ITERATIONS 1000000

typedef struct {
  const char* value;
  uint32_t hash;
} string_t;

struct bucket_t {
  string_t key;
  int value;
  struct bucket_t* next;
};

typedef struct {
#if CHAINING
  struct bucket_t** buckets;
#else
  string_t* keys;
  int* vals;
#endif
  int mask;
  int capacity;
  int entries;
} hashtable_t;

void ht_init(hashtable_t* ht) {
#if POWER_OF_2
  ht->capacity = INITIAL_SIZE;
  ht->mask = INITIAL_SIZE - 1;
#else
  ht->capacity = INITIAL_PRIME;
#endif
#if CHAINING
  ht->buckets = (struct bucket_t**)calloc(ht->capacity, sizeof(struct bucket_t*));
#else
  ht->entries = 0;
  ht->keys = (string_t*)calloc(ht->capacity, sizeof(string_t));
  ht->vals = (int*)calloc(ht->capacity, sizeof(int));
#endif
}

int ht_set(hashtable_t* ht, string_t str, int32_t value) {
#if CHAINING
#if POWER_OF_2
  int index = str.hash & ht->mask;
#else
  int index = str.hash % ht->capacity;
#endif
  for (struct bucket_t* b = ht->buckets[index]; b != NULL; b = b->next) {
    if (b->key.hash == str.hash && (strcmp(b->key.value, str.value) == 0)) {
      b->key = str;
      b->value = value;
      return 1; // found, ovewritten
    }
  }
  struct bucket_t* n = (struct bucket_t*)malloc(sizeof(struct bucket_t));
  n->next = ht->buckets[index];
  n->key = str;
  n->value = value;
  ht->buckets[index] = n;
  return 0; // not found, inserted
#else
  int initial = str.hash & ht->mask;
  int index = initial;
  do {
    string_t* e = &ht->keys[index];
    if (e->value == NULL) {
      *e = str;
      ht->vals[index] = value;
      return 0; // not found, inserted
    }
    if (e->hash == str.hash && (strcmp(e->value, str.value) == 0)) {
      *e = str;
      ht->vals[index] = value;
      return 1; // found, ovewritten
    }
#if POWER_OF_2
    index = (index + 1) & ht->mask;
#else
    index++;
    if (index == ht->capacity) index = 0;
#endif
  } while (index != initial);
  // TODO: resize
  return 0;
#endif
}

int ht_get(hashtable_t* ht, string_t str, int32_t* out) {
#if CHAINING
#if POWER_OF_2
  int index = str.hash & ht->mask;
#else
  int index = str.hash % ht->capacity;
#endif
  for (struct bucket_t* b = ht->buckets[index]; b != NULL; b = b->next) {
    if (b->key.hash == str.hash && (strcmp(b->key.value, str.value) == 0)) {
      *out = b->value;
      return 1;
    }
  }
  return 0;
#else
  int initial = str.hash & ht->mask;
  int index = initial;
  do {
    string_t* e = &ht->keys[index];
    if (e->value == NULL) {
      return 0; // not found
    }
    if (e->hash == str.hash && (strcmp(e->value, str.value) == 0)) {
      *out = ht->vals[index];
      return 1; // found
    }
#if POWER_OF_2
    index = (index + 1) & ht->mask;
#else
    index++;
    if (index == ht->capacity) index = 0;
#endif
  } while (index != initial);
  return 0;
#endif
}

int ht_delete(hashtable_t* ht, string_t* str);

string_t mk_string(const char* val) {
  int32_t hash = 0;
  while (*val != 0) {
    hash = hash * 33 + *val;
    val++;
  }
  string_t result = { val, hash };
  return result;
}

int main(int argc, char* argv[]) {
  struct timeval t;
  hashtable_t ht;
  ht_init(&ht);

  // SETUP
  for (int i = 0; i < argc; i++) {
    string_t str = mk_string(argv[i]);
    ht_set(&ht, str, i * 7 + 99);
  }
  
  gettimeofday(&t, NULL);
  double before = t.tv_sec * 1000000.0 + t.tv_usec;
  // TIMED LOOP
  string_t foo = mk_string("foo");
  int hits = 0;
  for (int i = 0; i < ITERATIONS; i++) {
    int val = 0;
    int there = ht_get(&ht, foo, &val);
    if (there) printf("found\n");
    there = ht_get(&ht, mk_string(argv[0]), &val);
    if (there) hits++;
  }
  
  gettimeofday(&t, NULL);
  double after = t.tv_sec * 1000000.0 + t.tv_usec;
  double diff = after - before;

  double it_s = 1000000.0 * ITERATIONS / diff;
  printf("time: %.3lf μs (%lf it/s) hits = %d, chaining = %d, power-of-2 = %d\n", diff, it_s, hits, CHAINING, POWER_OF_2);
  return 0;
}