From fa56925a5de7384c03f4775822444095d38bf3ac Mon Sep 17 00:00:00 2001
From: Paul Duncan <pabs@pablotron.org>
Date: Tue, 8 Jan 2019 11:33:24 -0500
Subject: simplify move logic, add cache and solver

---
 src/libsok/sok-cache.c | 135 +++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 135 insertions(+)
 create mode 100644 src/libsok/sok-cache.c

(limited to 'src/libsok/sok-cache.c')

diff --git a/src/libsok/sok-cache.c b/src/libsok/sok-cache.c
new file mode 100644
index 0000000..748614e
--- /dev/null
+++ b/src/libsok/sok-cache.c
@@ -0,0 +1,135 @@
+#include <stdbool.h> // bool
+#include <stdint.h> // uint64_t
+#include <stdlib.h> // bsearch(), qsort()
+#include "sok.h"
+
+#define UNUSED(a) ((void) (a))
+#define GROW_SIZE (4096 / sizeof(uint64_t))
+
+static uint64_t
+hash_ctx(
+  const sok_ctx_t * const ctx
+) {
+  UNUSED(ctx);
+  // TODO
+  return 0;
+}
+
+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);
+  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
+) {
+  return !!bsearch(
+    &hash,
+    cache->vals,
+    cache->num_vals,
+    sizeof(uint64_t),
+    u64_cmp
+  );
+}
+
+bool
+sok_cache_has(
+  const sok_cache_t * const cache,
+  const sok_ctx_t * const ctx
+) {
+  return sok_cache_has_hash(cache, hash_ctx(ctx));
+}
+
+bool
+sok_cache_add(
+  sok_cache_t * const cache,
+  const sok_ctx_t * const ctx
+) {
+  // hash context
+  const uint64_t hash = hash_ctx(ctx);
+
+  // check for duplicates
+  if (sok_cache_has_hash(cache, hash)) {
+    return true;
+  }
+
+  // check capacity
+  if (cache->num_vals >= cache->capacity) {
+    // grow cache
+    if (!sok_cache_grow(cache)) {
+      // return failure
+      return false;
+    }
+  }
+
+  // append hash, sort values
+  cache->vals[cache->num_vals++] = hash_ctx(ctx);
+  qsort(cache->vals, cache->num_vals, sizeof(uint64_t), u64_cmp);
+
+  // 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(sizeof(uint64_t) * capacity);
+  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;
+  }
+}
-- 
cgit v1.2.3