Add zix data structures

1 files changed, 230 insertions, 0 deletions

diff --git a/src/zix/hash.c b/src/zix/hash.c
new file mode 100644
index 00000000..81830820
--- /dev/null
+++ b/src/zix/hash.c
@@ -0,0 +1,230 @@
+/*
+  Copyright 2011-2020 David Robillard <d@drobilla.net>
+
+  Permission to use, copy, modify, and/or distribute this software for any
+  purpose with or without fee is hereby granted, provided that the above
+  copyright notice and this permission notice appear in all copies.
+
+  THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+  WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+  MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+  ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+  WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+  ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+  OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+*/
+
+#include "zix/hash.h"
+
+#include <assert.h>
+#include <stdlib.h>
+#include <string.h>
+
+/**
+   Primes, each slightly less than twice its predecessor, and as far away
+   from powers of two as possible.
+*/
+static const unsigned sizes[] = {
+  53,        97,        193,       389,       769,        1543,     3079,
+  6151,      12289,     24593,     49157,     98317,      196613,   393241,
+  786433,    1572869,   3145739,   6291469,   12582917,   25165843, 50331653,
+  100663319, 201326611, 402653189, 805306457, 1610612741, 0};
+
+typedef struct ZixHashEntry {
+  struct ZixHashEntry* next; ///< Next entry in bucket
+  uint32_t             hash; ///< Non-modulo hash value
+                             // Value follows here (access with zix_hash_value)
+} ZixHashEntry;
+
+struct ZixHashImpl {
+  ZixHashFunc     hash_func;
+  ZixEqualFunc    equal_func;
+  ZixHashEntry**  buckets;
+  const unsigned* n_buckets;
+  size_t          value_size;
+  unsigned        count;
+};
+
+static inline void*
+zix_hash_value(ZixHashEntry* entry)
+{
+  return entry + 1;
+}
+
+ZixHash*
+zix_hash_new(ZixHashFunc hash_func, ZixEqualFunc equal_func, size_t value_size)
+{
+  ZixHash* hash = (ZixHash*)malloc(sizeof(ZixHash));
+  if (hash) {
+    hash->hash_func  = hash_func;
+    hash->equal_func = equal_func;
+    hash->n_buckets  = &sizes[0];
+    hash->value_size = value_size;
+    hash->count      = 0;
+    if (!(hash->buckets =
+            (ZixHashEntry**)calloc(*hash->n_buckets, sizeof(ZixHashEntry*)))) {
+      free(hash);
+      return NULL;
+    }
+  }
+  return hash;
+}
+
+void
+zix_hash_free(ZixHash* hash)
+{
+  if (!hash) {
+    return;
+  }
+
+  for (unsigned b = 0; b < *hash->n_buckets; ++b) {
+    ZixHashEntry* bucket = hash->buckets[b];
+    for (ZixHashEntry* e = bucket; e;) {
+      ZixHashEntry* next = e->next;
+      free(e);
+      e = next;
+    }
+  }
+
+  free(hash->buckets);
+  free(hash);
+}
+
+size_t
+zix_hash_size(const ZixHash* hash)
+{
+  return hash->count;
+}
+
+static inline void
+insert_entry(ZixHashEntry** bucket, ZixHashEntry* entry)
+{
+  entry->next = *bucket;
+  *bucket     = entry;
+}
+
+static inline ZixStatus
+rehash(ZixHash* hash, unsigned new_n_buckets)
+{
+  ZixHashEntry** new_buckets =
+    (ZixHashEntry**)calloc(new_n_buckets, sizeof(ZixHashEntry*));
+  if (!new_buckets) {
+    return ZIX_STATUS_NO_MEM;
+  }
+
+  const unsigned old_n_buckets = *hash->n_buckets;
+  for (unsigned b = 0; b < old_n_buckets; ++b) {
+    for (ZixHashEntry* e = hash->buckets[b]; e;) {
+      ZixHashEntry* const next = e->next;
+      const unsigned      h    = e->hash % new_n_buckets;
+      insert_entry(&new_buckets[h], e);
+      e = next;
+    }
+  }
+
+  free(hash->buckets);
+  hash->buckets = new_buckets;
+
+  return ZIX_STATUS_SUCCESS;
+}
+
+static inline ZixHashEntry*
+find_entry(const ZixHash* hash,
+           const void*    key,
+           const unsigned h,
+           const unsigned h_nomod)
+{
+  for (ZixHashEntry* e = hash->buckets[h]; e; e = e->next) {
+    if (e->hash == h_nomod && hash->equal_func(zix_hash_value(e), key)) {
+      return e;
+    }
+  }
+  return NULL;
+}
+
+void*
+zix_hash_find(const ZixHash* hash, const void* value)
+{
+  const unsigned      h_nomod = hash->hash_func(value);
+  const unsigned      h       = h_nomod % *hash->n_buckets;
+  ZixHashEntry* const entry   = find_entry(hash, value, h, h_nomod);
+  return entry ? zix_hash_value(entry) : 0;
+}
+
+ZixStatus
+zix_hash_insert(ZixHash* hash, const void* value, void** inserted)
+{
+  unsigned h_nomod = hash->hash_func(value);
+  unsigned h       = h_nomod % *hash->n_buckets;
+
+  ZixHashEntry* elem = find_entry(hash, value, h, h_nomod);
+  if (elem) {
+    assert(elem->hash == h_nomod);
+    if (inserted) {
+      *inserted = zix_hash_value(elem);
+    }
+    return ZIX_STATUS_EXISTS;
+  }
+
+  elem = (ZixHashEntry*)malloc(sizeof(ZixHashEntry) + hash->value_size);
+  if (!elem) {
+    return ZIX_STATUS_NO_MEM;
+  }
+  elem->next = NULL;
+  elem->hash = h_nomod;
+  memcpy(elem + 1, value, hash->value_size);
+
+  const unsigned next_n_buckets = *(hash->n_buckets + 1);
+  if (next_n_buckets != 0 && (hash->count + 1) >= next_n_buckets) {
+    if (!rehash(hash, next_n_buckets)) {
+      h = h_nomod % *(++hash->n_buckets);
+    }
+  }
+
+  insert_entry(&hash->buckets[h], elem);
+  ++hash->count;
+  if (inserted) {
+    *inserted = zix_hash_value(elem);
+  }
+  return ZIX_STATUS_SUCCESS;
+}
+
+ZixStatus
+zix_hash_remove(ZixHash* hash, const void* value)
+{
+  const unsigned h_nomod = hash->hash_func(value);
+  const unsigned h       = h_nomod % *hash->n_buckets;
+
+  ZixHashEntry** next_ptr = &hash->buckets[h];
+  for (ZixHashEntry* e = hash->buckets[h]; e; e = e->next) {
+    if (h_nomod == e->hash && hash->equal_func(zix_hash_value(e), value)) {
+      *next_ptr = e->next;
+      free(e);
+      return ZIX_STATUS_SUCCESS;
+    }
+    next_ptr = &e->next;
+  }
+
+  if (hash->n_buckets != sizes) {
+    const unsigned prev_n_buckets = *(hash->n_buckets - 1);
+    if (hash->count - 1 <= prev_n_buckets) {
+      if (!rehash(hash, prev_n_buckets)) {
+        --hash->n_buckets;
+      }
+    }
+  }
+
+  --hash->count;
+  return ZIX_STATUS_NOT_FOUND;
+}
+
+void
+zix_hash_foreach(ZixHash* hash, ZixHashVisitFunc f, void* user_data)
+{
+  for (unsigned b = 0; b < *hash->n_buckets; ++b) {
+    ZixHashEntry* bucket = hash->buckets[b];
+    for (ZixHashEntry* e = bucket; e; e = e->next) {
+      f(zix_hash_value(e), user_data);
+    }
+  }
+}