aboutsummaryrefslogtreecommitdiff
path: root/src/libsok
diff options
context:
space:
mode:
authorPaul Duncan <pabs@pablotron.org>2019-01-08 23:17:26 -0500
committerPaul Duncan <pabs@pablotron.org>2019-01-08 23:17:26 -0500
commit1aa27ed5589c1b310037b0e6d09765888f2da29a (patch)
treee03107361b7c5fa344f59e5baab737a4dc0e2e6e /src/libsok
parent423f574fe41e95a474182b2b0333fb5810556f13 (diff)
downloadsok-1aa27ed5589c1b310037b0e6d09765888f2da29a.tar.bz2
sok-1aa27ed5589c1b310037b0e6d09765888f2da29a.zip
add USE_QSORT
Diffstat (limited to 'src/libsok')
-rw-r--r--src/libsok/sok-cache.c32
1 files 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;