1 files changed, 168 insertions, 0 deletions
diff --git a/src/core/sok-cache.c b/src/core/sok-cache.c
new file mode 100644
index 0000000..df3c729
--- /dev/null
+++ b/src/core/sok-cache.c
@@ -0,0 +1,168 @@
+#include <stdbool.h> // bool
+#include <stdint.h> // uint64_t
+#include <stdlib.h> // bsearch(), qsort()
+#include <string.h> // memcpy
+#include <stdio.h> // debug
+#include "sok.h"
+
+#define UNUSED(a) ((void) (a))
+#define GROW_SIZE (4096 / sizeof(uint64_t))
+#define USE_QSORT 1
+
+static int
+u64_cmp(
+  const void * const ap,
+  const void * const bp
+) {
+  const uint64_t a = *((uint64_t*) ap),
+                 b = *((uint64_t*) bp);
+
+  return (a > b) ? -1 : ((a == b) ? 0 : 1);
+}
+
+static bool
+sok_cache_grow(
+  sok_cache_t * const cache
+) {
+  // calculate new capacity
+  const size_t new_capacity = cache->capacity + GROW_SIZE;
+  if (new_capacity < cache->capacity) {
+    return false;
+  }
+
+  // reallocate memory
+  uint64_t * const vals = realloc(cache->vals, new_capacity * sizeof(uint64_t));
+  if (!vals) {
+    return false;
+  }
+
+  // update data
+  cache->vals = vals;
+  cache->capacity = new_capacity;
+
+  // return success
+  return true;
+}
+
+static bool
+sok_cache_has_hash(
+  const sok_cache_t * const cache,
+  const uint64_t hash
+) {
+#if 0
+  for (size_t i = 0; i < cache->num_vals; i++) {
+    if (cache->vals[i] == hash) {
+      return true;
+    }
+  }
+
+  // return failure
+  return false;
+#else
+  return !!bsearch(
+    &hash,
+    cache->vals,
+    cache->num_vals,
+    sizeof(uint64_t),
+    u64_cmp
+  );
+#endif /* 0 */
+}
+
+bool
+sok_cache_has(
+  const sok_cache_t * const cache,
+  const sok_ctx_t * const ctx
+) {
+  return sok_cache_has_hash(cache, sok_ctx_hash(ctx));
+}
+
+bool
+sok_cache_add(
+  sok_cache_t * const cache,
+  const sok_ctx_t * const ctx
+) {
+/*
+ *   // hash context
+ *   const uint64_t hash = sok_ctx_hash(ctx);
+ *
+ *   // check for duplicates
+ *   if (sok_cache_has_hash(cache, hash)) {
+ *     return false;
+ *   }
+ */
+
+  // check capacity
+  if (cache->num_vals >= cache->capacity) {
+    // grow cache
+    if (!sok_cache_grow(cache)) {
+      // return failure
+      return false;
+    }
+  }
+
+  // append hash
+  const uint64_t hash = sok_ctx_hash(ctx);
+#if USE_QSORT
+  cache->vals[cache->num_vals] = hash;
+  cache->num_vals++;
+
+  // sort values
+  qsort(cache->vals, cache->num_vals, sizeof(uint64_t), u64_cmp);
+#else
+  size_t i;
+  for (i = 0; cache->vals[i] < hash && i < cache->num_vals; i++);
+  if (i < cache->num_vals) {
+    if (cache->vals[i] == hash) {
+      return true;
+    }
+
+    // move remaining data
+    const size_t num_bytes = (cache->num_vals - i) * sizeof(uint64_t);
+    memmove(cache->vals + (i + 1), cache->vals + i, num_bytes);
+
+    // insert value
+    cache->vals[i] = hash;
+    cache->num_vals++;
+  } else {
+    // append value
+    cache->vals[cache->num_vals] = hash;
+    cache->num_vals++;
+  }
+#endif /* USE_QSORT */
+
+  // return success
+  return true;
+}
+
+bool
+sok_cache_init(
+  sok_cache_t * const cache,
+  const size_t capacity
+) {
+  // alloc memory, check for error
+  uint64_t * const vals = malloc(capacity * sizeof(uint64_t));
+  if (!vals) {
+    // return failure
+    return false;
+  }
+
+  // populate cache
+  cache->vals = vals;
+  cache->num_vals = 0;
+  cache->capacity = capacity;
+
+  // return success
+  return true;
+}
+
+void
+sok_cache_fini(
+  sok_cache_t * const cache
+) {
+  if (cache->vals) {
+    // free memory
+    free(cache->vals);
+    cache->vals = NULL;
+  }
+}