#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))

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
  cache->vals[cache->num_vals] = sok_ctx_hash(ctx);
  cache->num_vals++;

  // sort values
  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(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;
  }
}