/*
  Copyright 2011-2020 David Robillard <d@drobilla.net>

  Permission to use, copy, modify, and/or distribute this software for any
  purpose with or without fee is hereby granted, provided that the above
  copyright notice and this permission notice appear in all copies.

  THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
*/

#undef NDEBUG

#define ZIX_HASH_KEY_TYPE const char
#define ZIX_HASH_RECORD_TYPE const char

#include "test_data.h"
#include "test_malloc.h"

#include "zix/attributes.h"
#include "zix/common.h"
#include "zix/digest.h"
#include "zix/hash.h"

#include <assert.h>
#include <inttypes.h>
#include <stdarg.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static bool expect_failure = false;

ZIX_LOG_FUNC(1, 2)
static int
test_fail(const char* fmt, ...)
{
  if (expect_failure) {
    return 0;
  }
  va_list args;
  va_start(args, fmt);
  fprintf(stderr, "error: ");
  vfprintf(stderr, fmt, args);
  va_end(args);
  return 1;
}

ZIX_PURE_FUNC static const char*
identity(const char* record)
{
  return record;
}

/// Decent hash function using zix_digest (murmur2)
ZIX_PURE_FUNC static size_t
decent_string_hash(const char* const str)
{
  return zix_digest(0u, str, strlen(str));
}

/// Terrible hash function from K&R first edition
ZIX_PURE_FUNC static size_t
terrible_string_hash(const char* str)
{
  size_t  hash = 0u;
  uint8_t c    = 0u;

  while ((c = (uint8_t)*str++)) {
    hash += c;
  }

  return hash;
}

ZIX_PURE_FUNC static size_t
string_hash_aligned(const char* const str)
{
  size_t length = strlen(str);

  length = (length + (sizeof(size_t) - 1)) / sizeof(size_t) * sizeof(size_t);
  return zix_digest_aligned(0u, str, length);
}

ZIX_PURE_FUNC static size_t
string_hash32(const char* const str)
{
  return (size_t)zix_digest32(0u, str, strlen(str));
}

ZIX_PURE_FUNC static size_t
string_hash64(const char* const str)
{
  return (size_t)zix_digest64(0u, str, strlen(str));
}

ZIX_PURE_FUNC static size_t
string_hash32_aligned(const char* const str)
{
  size_t length = strlen(str);

  length = (length + 3u) / 4u * 4u;
  return (size_t)zix_digest32_aligned(0u, str, length);
}

#if UINTPTR_MAX >= UINT64_MAX

ZIX_PURE_FUNC static size_t
string_hash64_aligned(const char* const str)
{
  size_t length = strlen(str);

  length = (length + 7u) / 8u * 8u;
  return (size_t)zix_digest64_aligned(0u, str, length);
}

#endif

static bool
string_equal(const char* const a, const char* const b)
{
  return !strcmp(a, b);
}

static int
stress_with(const ZixHashFunc hash_func, const size_t n_elems)
{
  ZixHash* hash = zix_hash_new(identity, hash_func, string_equal);
  if (!hash) {
    return test_fail("Failed to allocate hash\n");
  }

  static const size_t string_length = 15;

  char* const  buffer  = (char*)calloc(1, n_elems * (string_length + 1));
  char** const strings = (char**)calloc(sizeof(char*), n_elems);
  if (!buffer || !strings) {
    free(buffer);
    free(strings);
    return test_fail("Failed to allocate strings\n");
  }

  uint32_t seed = 1u;
  for (size_t i = 0u; i < n_elems; ++i) {
    strings[i] = buffer + i * (string_length + 1);
    assert((uintptr_t)strings[i] % sizeof(size_t) == 0);
    assert((uintptr_t)strings[i] % sizeof(uint32_t) == 0);

    for (size_t j = 0u; j < string_length; ++j) {
      seed          = lcg32(seed);
      strings[i][j] = (char)('!' + (seed % 92));
    }
  }

  // Insert each string
  for (size_t i = 0; i < n_elems; ++i) {
    ZixStatus st = zix_hash_insert(hash, strings[i]);
    if (st) {
      return test_fail("Failed to insert `%s'\n", strings[i]);
    }
  }

  // Ensure hash size is correct
  if (zix_hash_size(hash) != n_elems) {
    return test_fail(
      "Hash size %" PRIuPTR " != %" PRIuPTR "\n", zix_hash_size(hash), n_elems);
  }

  // Attempt to insert each string again
  for (size_t i = 0; i < n_elems; ++i) {
    ZixStatus st = zix_hash_insert(hash, strings[i]);
    if (st != ZIX_STATUS_EXISTS) {
      return test_fail(
        "Double inserted `%s' (%s)\n", strings[i], zix_strerror(st));
    }
  }

  // Search for each string
  for (size_t i = 0; i < n_elems; ++i) {
    const char* match = (const char*)zix_hash_find_record(hash, strings[i]);
    if (!match) {
      return test_fail("Failed to find `%s'\n", strings[i]);
    }
    if (match != strings[i]) {
      return test_fail("Bad match for `%s': `%s'\n", strings[i], match);
    }
  }

  static const char* const not_indexed_string = "__not__indexed__";

  // Do a quick smoke test to ensure that false matches don't succeed
  char* const not_indexed = (char*)calloc(1, strlen(not_indexed_string) + 1);
  if (not_indexed) {
    memcpy(not_indexed, not_indexed_string, strlen(not_indexed_string) + 1);
    const char* match = (const char*)zix_hash_find_record(hash, not_indexed);
    if (match) {
      return test_fail("Unexpectedly found `%s'\n", not_indexed);
    }
    free(not_indexed);
  }

  // Remove strings
  for (size_t i = 0; i < n_elems; ++i) {
    const size_t initial_size = zix_hash_size(hash);

    // Remove string
    const char* removed = NULL;
    ZixStatus   st      = zix_hash_remove(hash, strings[i], &removed);
    if (st) {
      return test_fail("Failed to remove `%s'\n", strings[i]);
    }

    // Ensure the removed value is what we expected
    if (removed != strings[i]) {
      return test_fail("Removed `%s` instead of `%s`\n", removed, strings[i]);
    }

    // Ensure size is updated
    if (zix_hash_size(hash) != initial_size - 1) {
      return test_fail("Removing node did not decrease hash size\n");
    }

    // Ensure second removal fails
    st = zix_hash_remove(hash, strings[i], &removed);
    if (st != ZIX_STATUS_NOT_FOUND) {
      return test_fail("Unexpectedly removed `%s' twice\n", strings[i]);
    }

    // Ensure value can no longer be found
    assert(zix_hash_find(hash, strings[i]) == zix_hash_end(hash));

    // Check to ensure remaining strings are still present
    for (size_t j = i + 1; j < n_elems; ++j) {
      const char* match = (const char*)zix_hash_find_record(hash, strings[j]);
      if (!match) {
        return test_fail("Failed to find `%s' after remove\n", strings[j]);
      }
      if (match != strings[j]) {
        return test_fail("Bad match for `%s' after remove\n", strings[j]);
      }
    }
  }

  // Insert each string again (to check non-empty destruction)
  for (size_t i = 0; i < n_elems; ++i) {
    ZixHashInsertPlan plan = zix_hash_plan_insert(hash, strings[i]);

    assert(!zix_hash_record_at(hash, plan));
    ZixStatus st = zix_hash_insert_at(hash, plan, strings[i]);
    if (st) {
      return test_fail("Failed to insert `%s'\n", strings[i]);
    }
  }

  // Check key == value (and test zix_hash_foreach)
  size_t n_checked = 0u;
  for (ZixHashIter i = zix_hash_begin(hash); i != zix_hash_end(hash);
       i             = zix_hash_next(hash, i)) {
    const char* const string = (const char*)zix_hash_get(hash, i);
    assert(string);
    if (strlen(string) < 3) {
      return test_fail("Corrupt value `%s'\n", string);
    }

    ++n_checked;
  }
  if (n_checked != n_elems) {
    return test_fail("Check failed\n");
  }

  free(strings);
  free(buffer);
  zix_hash_free(hash);

  return 0;
}

static int
stress(const size_t n_elems)
{
  if (stress_with(decent_string_hash, n_elems) ||
      stress_with(terrible_string_hash, n_elems / 4) ||
      stress_with(string_hash_aligned, n_elems / 4) ||
      stress_with(string_hash32, n_elems / 4) ||
      stress_with(string_hash64, n_elems / 4) ||
      stress_with(string_hash32_aligned, n_elems / 4)) {
    return 1;
  }

#if UINTPTR_MAX >= UINT64_MAX
  if (stress_with(string_hash64_aligned, n_elems / 4)) {
    return 1;
  }
#endif

  return 0;
}

/// Identity hash function for numeric strings for explicitly hitting cases
ZIX_PURE_FUNC static size_t
identity_index_hash(const char* const str)
{
  return strtoul(str, NULL, 10);
}

static void
test_all_tombstones(void)
{
  /* This tests an edge case where a minimum-sized table can be entirely full
     of tombstones.  If the search loop is not written carefully, then this can
     result in a hang.  This has been seen to occur in real code, though it's
     very hard to hit with a decent hash function.  So, we use the above
     degenerate index hashing function to explicitly place elements exactly
     where we want to hit this case. */

#define N_STRINGS 4

  static const char* original_strings[N_STRINGS] = {
    "0 a",
    "1 a",
    "2 a",
    "3 a",
  };

  static const char* collision_strings[N_STRINGS] = {
    "0 b",
    "1 b",
    "2 b",
    "3 b",
  };

  ZixStatus st   = ZIX_STATUS_SUCCESS;
  ZixHash*  hash = zix_hash_new(identity, identity_index_hash, string_equal);

  // Insert each element then immediately remove it
  for (unsigned i = 0u; i < N_STRINGS; ++i) {
    const char* removed = NULL;

    assert(!zix_hash_insert(hash, original_strings[i]));
    assert(!zix_hash_remove(hash, original_strings[i], &removed));
  }

  // Now the table should be "empty" but contain tombstones
  assert(zix_hash_size(hash) == 0);

  // Insert clashing elements which should hit the "all tombstones" case
  for (unsigned i = 0u; i < N_STRINGS; ++i) {
    assert(!zix_hash_insert(hash, collision_strings[i]));
    assert(!st);
  }

  zix_hash_free(hash);

#undef N_STRINGS
}

int
main(void)
{
  zix_hash_free(NULL);
  test_all_tombstones();

  static const size_t n_elems = 1024u;

  if (stress(n_elems)) {
    return 1;
  }

#ifdef ZIX_WITH_TEST_MALLOC
  const size_t total_n_allocs = test_malloc_get_n_allocs();
  printf("Testing 0 ... %" PRIuPTR " failed allocations\n", total_n_allocs);
  expect_failure = true;
  for (size_t i = 0; i < total_n_allocs; ++i) {
    test_malloc_reset(i);
    stress(n_elems);
  }

  test_malloc_reset((size_t)-1);
#endif

  return 0;
}