text: /*
   * 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++) {
  			h = test[i][0];
  			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;
  }
  
  