/*
 * Copyright 2012 Samy Al Bahra.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyrights
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyrights
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

#include <ck_hs.h>

#include <assert.h>
#include <ck_malloc.h>
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "../../common.h"

static void *
hs_malloc(size_t r)
{

	return malloc(r);
}

static void
hs_free(void *p, size_t b, bool r)
{

	(void)b;
	(void)r;
	free(p);
	return;
}

static struct ck_malloc my_allocator = {
	.malloc = hs_malloc,
	.free = hs_free
};

static void
stub_free(void *p, size_t b, bool r)
{

	(void)b;
	(void)r;

	fprintf(stderr, "Ignoring reclamation of %p\n", p);
	return;
}

static struct ck_malloc stub_allocator = {
	.malloc = hs_malloc,
	.free = stub_free
};

const char *test[] = { "Samy", "Al", "Bahra", "dances", "in", "the", "wind.", "Once",
                       "upon", "a", "time", "his", "gypsy", "ate", "one", "itsy",
                       "bitsy", "spider.", "What", "goes", "up", "must",
                       "come", "down.", "What", "is", "down", "stays",
                       "down.", "A", "B", "C", "D", "E", "F", "G", "H",
                       "I", "J", "K", "L", "M", "N", "O", "P", "Q" };

const char *negative = "negative";

/* Purposefully crappy hash function. */
static unsigned long
hs_hash(const void *object, unsigned long seed)
{
	const char *c = object;
	unsigned long h;

	(void)seed;
	h = c[0];
	return h;
}

static bool
hs_compare(const void *previous, const void *compare)
{

	return strcmp(previous, compare) == 0;
}

static void *
test_ip(void *key, void *closure)
{
	const char *a = key;
	const char *b = closure;

	if (strcmp(a, b) != 0)
		ck_error("Mismatch: %s != %s\n", a, b);

	return closure;
}

static void *
test_negative(void *key, void *closure)
{

	(void)closure;
	if (key != NULL)
		ck_error("ERROR: Apply callback expects NULL argument instead of [%s]\n", key);

	return NULL;
}

static void *
test_unique(void *key, void *closure)
{

	if (key != NULL)
		ck_error("ERROR: Apply callback expects NULL argument instead of [%s]\n", key);

	return closure;
}

static void *
test_remove(void *key, void *closure)
{

	(void)key;
	(void)closure;

	return NULL;
}

static void
run_test(unsigned int is, unsigned int ad)
{
	ck_hs_t hs[16];
	const size_t size = sizeof(hs) / sizeof(*hs);
	size_t i, j;
	const char *blob = "#blobs";
	unsigned long h;
	ck_hs_iterator_t it;

	if (ck_hs_init(&hs[0], CK_HS_MODE_SPMC | CK_HS_MODE_OBJECT | ad, hs_hash, hs_compare, &my_allocator, is, 6602834) == false)
		ck_error("ck_hs_init\n");

	for (j = 0; j < size; j++) {
		for (i = 0; i < sizeof(test) / sizeof(*test); i++) {
			unsigned long h_1;

			h = CK_HS_HASH(&hs[j], hs_hash, test[i]);
			h_1 = ck_hs_hash(&hs[j], test[i]);

			if (h != h_1)
				ck_error("h != h_1 (%lu != %lu)\n", h, h_1);

			if (ck_hs_get(&hs[j], h, test[i]) != NULL) {
				continue;
			}

			if (i & 1) {
				if (ck_hs_put_unique(&hs[j], h, test[i]) == false)
					ck_error("ERROR [%zu]: Failed to insert unique (%s)\n", j, test[i]);
			} else if (ck_hs_apply(&hs[j], h, test[i], test_unique, (void *)(uintptr_t)test[i]) == false) {
				ck_error("ERROR: Failed to apply for insertion.\n");
			}

			if (i & 1) {
				if (ck_hs_remove(&hs[j], h, test[i]) == false)
					ck_error("ERROR [%zu]: Failed to remove unique (%s)\n", j, test[i]);
			} else if (ck_hs_apply(&hs[j], h, test[i], test_remove, NULL) == false) {
				ck_error("ERROR: Failed to remove apply.\n");
			}

			if (ck_hs_apply(&hs[j], h, test[i], test_negative, (char *)(uintptr_t)test[i]) == false)
				ck_error("ERROR: Failed to apply.\n");

			break;
		}

		if (ck_hs_gc(&hs[j], 0, 0) == false)
			ck_error("ERROR: Failed to GC empty set.\n");

		for (i = 0; i < sizeof(test) / sizeof(*test); i++) {
			h = test[i][0];
			ck_hs_put(&hs[j], h, test[i]);
			if (ck_hs_put(&hs[j], h, test[i]) == true) {
				ck_error("ERROR [%u] [1]: put must fail on collision (%s).\n", is, test[i]);
			}
			if (ck_hs_get(&hs[j], h, test[i]) == NULL) {
				ck_error("ERROR [%u]: get must not fail after put\n", is);
			}
		}

		/* Test iteration */
		if (j == 0) {
			/* Avoid the blob stuff as it's not in the test array. */
			ck_hs_iterator_init(&it);
			void *k = NULL;
			int matches = 0;
			int entries = 0;
			while (ck_hs_next(&hs[j], &it, &k) == true) {
				entries++;
				for (i = 0; i < sizeof(test) / sizeof(*test); i++) {
					int x = strcmp(test[i], (char *)k);
					if (x == 0) {
						matches++;
						break;
					}
				}
			}

			if (entries != matches) {
				ck_error("Iteration must match all elements, has: %d, matched: %d [%d]", entries, matches, is);
			}

			/*
			 * Now test iteration in the face of grows (spmc).
			 * In order to test usage after reclamation, we
			 * stub the allocator.
			 */
			ck_hs_iterator_init(&it);
			k = NULL;
			matches = 0;
			entries = 0;
			hs[j].m = &stub_allocator;
			while (ck_hs_next_spmc(&hs[j], &it, &k) == true) {
				entries++;
				for (i = 0; i < sizeof(test) / sizeof(*test); i++) {
					int x = strcmp(test[i], (char *)k);
					if (x == 0) {
						matches++;
						break;
					}
				}
				if (entries == 20) {
					ck_hs_grow(&hs[j], 128);
				}
			}
			hs[j].m = &my_allocator;

			if (entries != matches) {
				ck_error("After growth, iteration must match all elements, has: %d, matched: %d [%d]", entries, matches, is);
			}
		}

		/* Test grow semantics. */
		ck_hs_grow(&hs[j], 128);
		for (i = 0; i < sizeof(test) / sizeof(*test); i++) {
			h = test[i][0];
			if (ck_hs_put(&hs[j], h, test[i]) == true) {
				ck_error("ERROR [%u] [2]: put must fail on collision.\n", is);
			}

			if (ck_hs_get(&hs[j], h, test[i]) == NULL) {
				ck_error("ERROR [%u]: get must not fail\n", is);
			}
		}

		h = blob[0];
		if (ck_hs_get(&hs[j], h, blob) == NULL) {
			if (j > 0)
				ck_error("ERROR [%u]: Blob must always exist after first.\n", is);

			if (ck_hs_put(&hs[j], h, blob) == false) {
				ck_error("ERROR [%u]: A unique blob put failed.\n", is);
			}
		} else {
			if (ck_hs_put(&hs[j], h, blob) == true) {
				ck_error("ERROR [%u]: Duplicate blob put succeeded.\n", is);
			}
		}

		/* Grow set and check get semantics. */
		ck_hs_grow(&hs[j], 512);
		for (i = 0; i < sizeof(test) / sizeof(*test); i++) {
			h = test[i][0];
			if (ck_hs_get(&hs[j], h, test[i]) == NULL) {
				ck_error("ERROR [%u]: get must not fail\n", is);
			}
		}

		/* Delete and check negative membership. */
		for (i = 0; i < sizeof(test) / sizeof(*test); i++) {
			void *r;

			h = test[i][0];
			if (ck_hs_get(&hs[j], h, test[i]) == NULL)
				continue;

			if (r = ck_hs_remove(&hs[j], h, test[i]), r == NULL) {
				ck_error("ERROR [%u]: remove must not fail\n", is);
			}

			if (strcmp(r, test[i]) != 0) {
				ck_error("ERROR [%u]: Removed incorrect node (%s != %s)\n", (char *)r, test[i], is);
			}
		}

		/* Test replacement semantics. */
		for (i = 0; i < sizeof(test) / sizeof(*test); i++) {
			void *r;
			bool d;

			h = test[i][0];
			d = ck_hs_get(&hs[j], h, test[i]) != NULL;
			if (ck_hs_set(&hs[j], h, test[i], &r) == false) {
				ck_error("ERROR [%u]: Failed to set\n", is);
			}

			/* Expected replacement. */
			if (d == true && (r == NULL || strcmp(r, test[i]) != 0)) {
				ck_error("ERROR [%u]: Incorrect previous value: %s != %s\n",
				    is, test[i], (char *)r);
			}

			/* Replacement should succeed. */
			if (ck_hs_fas(&hs[j], h, test[i], &r) == false)
				ck_error("ERROR [%u]: ck_hs_fas must succeed.\n", is);

			if (strcmp(r, test[i]) != 0) {
				ck_error("ERROR [%u]: Incorrect replaced value: %s != %s\n",
				    is, test[i], (char *)r);
			}

			if (ck_hs_fas(&hs[j], h, negative, &r) == true)
				ck_error("ERROR [%u]: Replacement of negative should fail.\n", is);

			if (ck_hs_set(&hs[j], h, test[i], &r) == false) {
				ck_error("ERROR [%u]: Failed to set [1]\n", is);
			}

			if (strcmp(r, test[i]) != 0) {
				ck_error("ERROR [%u]: Invalid &hs[j]: %s != %s\n", is, test[i], (char *)r);
			}

			/* Attempt in-place mutation. */
			if (ck_hs_apply(&hs[j], h, test[i], test_ip, (void *)(uintptr_t)test[i]) == false)
				ck_error("ERROR [%u]: Failed to apply: %s != %s\n", is, (char *)r, test[i]);

			d = ck_hs_get(&hs[j], h, test[i]) != NULL;
			if (d == false)
				ck_error("ERROR [%u]: Expected [%s] to exist.\n", is, test[i]);
		}

		if (j == size - 1)
			break;

		if (ck_hs_move(&hs[j + 1], &hs[j], hs_hash, hs_compare, &my_allocator) == false)
			ck_error("Failed to move hash table");

		if (j & 1) {
			ck_hs_gc(&hs[j + 1], 0, 0);
		} else {
			ck_hs_gc(&hs[j + 1], 26, 26);
		}

		if (ck_hs_rebuild(&hs[j + 1]) == false)
			ck_error("Failed to rebuild");
	}

	return;
}

int
main(void)
{
	unsigned int k;

	for (k = 16; k <= 64; k <<= 1) {
		run_test(k, 0);
		run_test(k, CK_HS_MODE_DELETE);
		break;
	}

	return 0;
}