From e36b37583bebd229102f46c4ed7d2f6fad8697d4 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Fri, 23 Jul 2021 13:24:09 +0200 Subject: Adding upstream version 0.6.0. Signed-off-by: Daniel Baumann --- regressions/ck_hs/validate/Makefile | 17 ++ regressions/ck_hs/validate/serial.c | 315 ++++++++++++++++++++++++++++++++++++ 2 files changed, 332 insertions(+) create mode 100644 regressions/ck_hs/validate/Makefile create mode 100644 regressions/ck_hs/validate/serial.c (limited to 'regressions/ck_hs/validate') diff --git a/regressions/ck_hs/validate/Makefile b/regressions/ck_hs/validate/Makefile new file mode 100644 index 0000000..a96e652 --- /dev/null +++ b/regressions/ck_hs/validate/Makefile @@ -0,0 +1,17 @@ +.PHONY: check clean distribution + +OBJECTS=serial + +all: $(OBJECTS) + +serial: serial.c ../../../include/ck_hs.h ../../../src/ck_hs.c + $(CC) $(CFLAGS) -o serial serial.c ../../../src/ck_hs.c + +check: all + ./serial + +clean: + rm -rf *~ *.o $(OBJECTS) *.dSYM *.exe + +include ../../../build/regressions.build +CFLAGS+=-D_GNU_SOURCE diff --git a/regressions/ck_hs/validate/serial.c b/regressions/ck_hs/validate/serial.c new file mode 100644 index 0000000..a16fc82 --- /dev/null +++ b/regressions/ck_hs/validate/serial.c @@ -0,0 +1,315 @@ +/* + * 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 copyrighs + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyrighs + * 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 + +#include +#include +#include +#include +#include +#include + +#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 +}; + +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; + + 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 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; +} + -- cgit v1.2.3