Hash Table Facilities

htable.h

#ifndef HTABLE_H
#define HTABLE_H
#define HTABLE_INITIAL_CAPACITY 64

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

typedef struct htable_t {
  char **keys;
  void **values;
  size_t length, capacity;
} htable_t;

htable_t *halloc() {
  htable_t *t = malloc(sizeof(htable_t));
  if (!t) return 0;
  t->length = 0;
  t->capacity = HTABLE_INITIAL_CAPACITY;
  t->keys = calloc(t->capacity, sizeof(void*));
  t->values = calloc(t->capacity, sizeof(void*));
  if (!(t->keys && t->values)) {
    free(t);
    return 0;
  }
  return t;
}

void hfree(htable_t *t) {
  for (int i=0; i < t->capacity; i++)
    if (t->keys[i])
      free(t->keys[i]);
  free(t->keys);
  free(t->values);
  free(t);
}

/* https://en.wikipedia.org/wiki/Fowler–Noll–Vo_hash_function */
size_t khash(char *k, size_t capacity) {
  size_t h = 14695981039346656037U;
  for (char *p = k; *p; p++) {
    h ^= (unsigned)*p;
    h *= 1099511628211;
  }
  return h % capacity;
}

void *hget(htable_t *t, char *k) {
  size_t i = khash(k, t->capacity);
  while (t->keys[i]) {
    if (!strcmp(k, t->keys[i]))
      return t->values[i];
    if (i++ == t->capacity) i = 0;
  }
  return 0;
}

void *hfset(char **keys, void **values, size_t capacity, char *k, void *v, size_t *length) {
  size_t i = khash(k, capacity);
  while (keys[i]) {
    if (!strcmp(k, keys[i]))
      return values[i] = v;
    if (i++ == capacity) i = 0;
  }
  if (length)
    (*length)++;
  keys[i] = k;
  values[i] = v;
}

void *hset(htable_t *t, char *k, void *v) {
  if (!(k && v)) return 0;
  k = strdup(k);
  if (t->length >= t->capacity/2) {
    size_t new_capacity = t->capacity * 2;
    if (new_capacity < t->capacity)
      return 0;
    char **new_keys = calloc(new_capacity, sizeof(void*));
    void **new_values = calloc(new_capacity, sizeof(void*));
    if (!(new_keys && new_values)) return 0;
    for (size_t i = 0; i < t->capacity; i++) {
      if (t->keys[i])
        hfset(new_keys, new_values, new_capacity, t->keys[i], t->values[i], 0);
    }
    free(t->keys);
    free(t->values);
    t->keys = new_keys;
    t->values = new_values;
    t->capacity = new_capacity;
  }
  return hfset(t->keys, t->values, t->capacity, k, v, &t->length);
}

#define hset(t, k, v) (hset((t), (char*)(long)(k), (void*)(long)(v)))

#endif