From 1aa27ed5589c1b310037b0e6d09765888f2da29a Mon Sep 17 00:00:00 2001
From: Paul Duncan <pabs@pablotron.org>
Date: Tue, 8 Jan 2019 23:17:26 -0500
Subject: add USE_QSORT

---
 src/libsok/sok-cache.c | 32 ++++++++++++++++++++++++++++----
 1 file changed, 28 insertions(+), 4 deletions(-)

diff --git a/src/libsok/sok-cache.c b/src/libsok/sok-cache.c
index 261d6b9..df3c729 100644
--- a/src/libsok/sok-cache.c
+++ b/src/libsok/sok-cache.c
@@ -7,6 +7,7 @@
 
 #define UNUSED(a) ((void) (a))
 #define GROW_SIZE (4096 / sizeof(uint64_t))
+#define USE_QSORT 1
 
 static int
 u64_cmp(
@@ -81,15 +82,15 @@ 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) {
@@ -101,11 +102,34 @@ sok_cache_add(
   }
 
   // append hash
-  cache->vals[cache->num_vals] = sok_ctx_hash(ctx);
+  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;
-- 
cgit v1.2.3