tests: extend DECLARE_* tests

The unsorted datastructures (LIST, DLIST) had no test before this.  Also
add a hash check (mostly to make testing the unsorted lists easier.)

Signed-off-by: David Lamparter <equinox@diac24.net>

3 files changed, 255 insertions, 11 deletions

diff --git a/tests/lib/test_typelist.c b/tests/lib/test_typelist.c
index df71da892..3ca8bf303 100644
--- a/tests/lib/test_typelist.c
+++ b/tests/lib/test_typelist.c
@@ -25,6 +25,7 @@
 #include <string.h>
 #include <unistd.h>
 #include <assert.h>
+#include <arpa/inet.h>
 
 #define WNO_ATOMLIST_UNSAFE_FIND
 
@@ -33,6 +34,7 @@
 #include "memory.h"
 #include "monotime.h"
 #include "jhash.h"
+#include "sha256.h"
 
 #include "tests/helpers/c/prng.h"
 
@@ -50,6 +52,21 @@
 #define _DECLARE(type, ...)	DECLARE_##type(__VA_ARGS__)
 #define DECLARE(type, ...)	_DECLARE(type, __VA_ARGS__)
 
+#define _S_LIST			0
+#define _S_DLIST		0
+#define _S_SORTLIST_UNIQ	1
+#define _S_SORTLIST_NONUNIQ	1
+#define _S_HASH			1
+#define _S_SKIPLIST_UNIQ	1
+#define _S_SKIPLIST_NONUNIQ	1
+#define _S_RBTREE_UNIQ		1
+#define _S_RBTREE_NONUNIQ	1
+#define _S_ATOMSORT_UNIQ	1
+#define _S_ATOMSORT_NONUNIQ	1
+
+#define _IS_SORTED(type)	_S_##type
+#define IS_SORTED(type)		_IS_SORTED(type)
+
 #define _U_SORTLIST_UNIQ	1
 #define _U_SORTLIST_NONUNIQ	0
 #define _U_HASH			1
@@ -97,6 +114,12 @@ static void ts_end(void)
 	printf("%7"PRId64"us  total\n", us);
 }
 
+#define TYPE LIST
+#include "test_typelist.h"
+
+#define TYPE DLIST
+#include "test_typelist.h"
+
 #define TYPE SORTLIST_UNIQ
 #include "test_typelist.h"
 
@@ -134,6 +157,8 @@ int main(int argc, char **argv)
 {
 	srandom(1);
 
+	test_LIST();
+	test_DLIST();
 	test_SORTLIST_UNIQ();
 	test_SORTLIST_NONUNIQ();
 	test_HASH();
diff --git a/tests/lib/test_typelist.h b/tests/lib/test_typelist.h
index 196a85889..b3f3d3b4e 100644
--- a/tests/lib/test_typelist.h
+++ b/tests/lib/test_typelist.h
@@ -30,12 +30,17 @@
 #define list_next_safe	concat(TYPE, _next_safe)
 #define list_count	concat(TYPE, _count)
 #define list_add	concat(TYPE, _add)
+#define list_add_head	concat(TYPE, _add_head)
+#define list_add_tail	concat(TYPE, _add_tail)
+#define list_add_after	concat(TYPE, _add_after)
 #define list_find	concat(TYPE, _find)
 #define list_find_lt	concat(TYPE, _find_lt)
 #define list_find_gteq	concat(TYPE, _find_gteq)
 #define list_del	concat(TYPE, _del)
 #define list_pop	concat(TYPE, _pop)
 
+#define ts_hash		concat(ts_hash_, TYPE)
+
 #ifndef REALTYPE
 #define REALTYPE TYPE
 #endif
@@ -47,6 +52,7 @@ struct item {
 	int scratchpad;
 };
 
+#if IS_SORTED(REALTYPE)
 static int list_cmp(const struct item *a, const struct item *b);
 
 #if IS_HASH(REALTYPE)
@@ -76,16 +82,67 @@ static int list_cmp(const struct item *a, const struct item *b)
 	return 0;
 }
 
+#else /* !IS_SORTED */
+DECLARE(REALTYPE, list, struct item, itm)
+#endif
+
 #define NITEM 10000
 struct item itm[NITEM];
 static struct list_head head = concat(INIT_, REALTYPE)(head);
 
+static void ts_hash(const char *text, const char *expect)
+{
+	int64_t us = monotime_since(&ref, NULL);
+	SHA256_CTX ctx;
+	struct item *item;
+	unsigned i = 0;
+	uint8_t hash[32];
+	char hashtext[65];
+	uint32_t count;
+
+	count = htonl(list_count(&head));
+
+	SHA256_Init(&ctx);
+	SHA256_Update(&ctx, &count, sizeof(count));
+
+	for_each (list, &head, item) {
+		struct {
+			uint32_t val_upper, val_lower, index;
+		} hashitem = {
+			htonl(item->val >> 32),
+			htonl(item->val & 0xFFFFFFFFULL),
+			htonl(i),
+		};
+		SHA256_Update(&ctx, &hashitem, sizeof(hashitem));
+		i++;
+		assert(i < count);
+	}
+	SHA256_Final(hash, &ctx);
+
+	for (i = 0; i < sizeof(hash); i++)
+		sprintf(hashtext + i * 2, "%02x", hash[i]);
+
+	printf("%7"PRId64"us  %-25s %s%s\n", us, text,
+	       expect ? " " : "*", hashtext);
+	if (expect && strcmp(expect, hashtext)) {
+		printf("%-21s %s\n", "EXPECTED:", expect);
+		assert(0);
+	}
+	monotime(&ref);
+}
+/* hashes will have different item ordering */
+#if IS_HASH(REALTYPE)
+#define ts_hashx(pos, csum) ts_hash(pos, NULL)
+#else
+#define ts_hashx(pos, csum) ts_hash(pos, csum)
+#endif
+
 static void concat(test_, TYPE)(void)
 {
 	size_t i, j, k, l;
 	struct prng *prng;
-	struct item *item, *prev;
-	struct item dummy;
+	struct item *item, *prev __attribute__((unused));
+	struct item dummy __attribute__((unused));
 
 	memset(itm, 0, sizeof(itm));
 	for (i = 0; i < NITEM; i++)
@@ -95,10 +152,11 @@ static void concat(test_, TYPE)(void)
 	ts_start();
 
 	list_init(&head);
-	ts_ref("init");
-
 	assert(list_first(&head) == NULL);
 
+	ts_hash("init", "df3f619804a92fdb4057192dc43dd748ea778adc52bc498ce80524c014b81119");
+
+#if IS_SORTED(REALTYPE)
 	prng = prng_new(0);
 	k = 0;
 	for (i = 0; i < NITEM; i++) {
@@ -112,7 +170,7 @@ static void concat(test_, TYPE)(void)
 	}
 	assert(list_count(&head) == k);
 	assert(list_first(&head) != NULL);
-	ts_ref("fill");
+	ts_hashx("fill", "a538546a6e6ab0484e925940aa8dd02fd934408bbaed8cb66a0721841584d838");
 
 	k = 0;
 	prev = NULL;
@@ -151,8 +209,8 @@ static void concat(test_, TYPE)(void)
 			list_del(&head, &dummy);
 		}
 	}
-	ts_ref("add-dup");
-#else /* !IS_UNIQ(TYPE) */
+	ts_hashx("add-dup", "a538546a6e6ab0484e925940aa8dd02fd934408bbaed8cb66a0721841584d838");
+#else /* !IS_UNIQ(REALTYPE) */
 	for (i = 0; i < NITEM; i++) {
 		j = prng_rand(prng) % NITEM;
 		memset(&dummy, 0, sizeof(dummy));
@@ -181,7 +239,7 @@ static void concat(test_, TYPE)(void)
 			assert(list_next(&head, &dummy)->val > j);
 		list_del(&head, &dummy);
 	}
-	ts_ref("add-dup+find_{lt,gteq}");
+	ts_hash("add-dup+find_{lt,gteq}", "a538546a6e6ab0484e925940aa8dd02fd934408bbaed8cb66a0721841584d838");
 #endif
 #if !IS_HASH(REALTYPE)
 	prng_free(prng);
@@ -225,7 +283,7 @@ static void concat(test_, TYPE)(void)
 		}
 	}
 	assert(l + list_count(&head) == k);
-	ts_ref("del");
+	ts_hashx("del", "cb2e5d80f08a803ef7b56c15e981b681adcea214bebc2f55e12e0bfb242b07ca");
 
 	for_each_safe(list, &head, item) {
 		assert(item->scratchpad != 0);
@@ -237,7 +295,161 @@ static void concat(test_, TYPE)(void)
 		}
 	}
 	assert(l + list_count(&head) == k);
-	ts_ref("for_each_safe+del");
+	ts_hashx("for_each_safe+del", "e0beb71dd963a75af05b722b8e71b61b304587d860c8accdc4349067542b86bb");
+
+#else /* !IS_SORTED */
+	prng = prng_new(0);
+	k = 0;
+	for (i = 0; i < NITEM; i++) {
+		j = prng_rand(prng) % NITEM;
+		if (itm[j].scratchpad == 0) {
+			list_add_tail(&head, &itm[j]);
+			itm[j].scratchpad = 1;
+			k++;
+		}
+	}
+	assert(list_count(&head) == k);
+	assert(list_first(&head) != NULL);
+	ts_hash("fill / add_tail", "eabfcf1413936daaf20965abced95762f45110a6619b84aac7d38481bce4ea19");
+
+	for (i = 0; i < NITEM / 2; i++) {
+		j = prng_rand(prng) % NITEM;
+		if (itm[j].scratchpad == 1) {
+			list_del(&head, &itm[j]);
+			itm[j].scratchpad = 0;
+			k--;
+		}
+	}
+	ts_hash("del-prng", "86d568a95eb429dab3162976c5a5f3f75aabc835932cd682aa280b6923549564");
+
+	l = 0;
+	while ((item = list_pop(&head))) {
+		assert(item->scratchpad != 0);
+
+		item->scratchpad = 0;
+		l++;
+	}
+	assert(l == k);
+	assert(list_count(&head) == 0);
+	assert(list_first(&head) == NULL);
+	ts_hash("pop", "df3f619804a92fdb4057192dc43dd748ea778adc52bc498ce80524c014b81119");
+
+	prng_free(prng);
+	prng = prng_new(0x1e5a2d69);
+
+	k = 0;
+	for (i = 0; i < NITEM; i++) {
+		j = prng_rand(prng) % NITEM;
+		if (itm[j].scratchpad == 0) {
+			list_add_head(&head, &itm[j]);
+			itm[j].scratchpad = 1;
+			k++;
+		}
+	}
+	assert(list_count(&head) == k);
+	assert(list_first(&head) != NULL);
+	ts_hash("fill / add_head", "3084d8f8a28b8c756ccc0a92d60d86f6d776273734ddc3f9e1d89526f5ca2795");
+
+	for (i = 0; i < NITEM / 2; i++) {
+		j = prng_rand(prng) % NITEM;
+		if (itm[j].scratchpad == 1) {
+			list_del(&head, &itm[j]);
+			itm[j].scratchpad = 0;
+			k--;
+		}
+	}
+	ts_hash("del-prng", "dc916fa7ea4418792c7c8232d74df2887f9975ead4222f4b977be6bc0b52285e");
+
+	l = 0;
+	while ((item = list_pop(&head))) {
+		assert(item->scratchpad != 0);
+
+		item->scratchpad = 0;
+		l++;
+	}
+	assert(l == k);
+	assert(list_count(&head) == 0);
+	assert(list_first(&head) == NULL);
+	ts_hash("pop", "df3f619804a92fdb4057192dc43dd748ea778adc52bc498ce80524c014b81119");
+
+	prng_free(prng);
+	prng = prng_new(0x692d1e5a);
+
+	k = 0;
+	for (i = 0; i < NITEM; i++) {
+		j = prng_rand(prng) % NITEM;
+		if (itm[j].scratchpad == 0) {
+			if (prng_rand(prng) & 1) {
+				list_add_tail(&head, &itm[j]);
+			} else {
+				list_add_head(&head, &itm[j]);
+			}
+			itm[j].scratchpad = 1;
+			k++;
+		}
+	}
+	assert(list_count(&head) == k);
+	assert(list_first(&head) != NULL);
+	ts_hash("fill / add_{head,tail}", "93fa180a575c96e4b6c3775c2de7843ee3254dd6ed5af699bbe155f994114b06");
+
+	for (i = 0; i < NITEM * 3; i++) {
+		int op = prng_rand(prng);
+		j = prng_rand(prng) % NITEM;
+
+		if (op & 1) {
+			/* delete or pop */
+			if (op & 2) {
+				item = list_pop(&head);
+				if (!item)
+					continue;
+			} else {
+				item = &itm[j];
+				if (item->scratchpad == 0)
+					continue;
+				list_del(&head, item);
+			}
+			item->scratchpad = 0;
+			k--;
+		} else {
+			item = &itm[j];
+			if (item->scratchpad != 0)
+				continue;
+
+			item->scratchpad = 1;
+			k++;
+
+			switch ((op >> 1) & 3) {
+			case 0:
+				list_add_head(&head, item);
+				break;
+			case 1:
+				list_add_tail(&head, item);
+				break;
+			case 2:
+			case 3:
+				prev = NULL;
+				l = 0;
+				do {
+					j = prng_rand(prng) % NITEM;
+					prev = &itm[j];
+					if (prev->scratchpad == 0
+					    || prev == item)
+						prev = NULL;
+					l++;
+				} while (!prev && l < 10);
+				list_add_after(&head, prev, item);
+				break;
+			default:
+				assert(0);
+			}
+		}
+	}
+	assert(list_count(&head) == k);
+	assert(list_first(&head) != NULL);
+	ts_hash("prng add/del", "8c5dd192505c8cc8337f9b936f88e90dbc5854cb3fd7391c47189d131fa399fd");
+
+	l = 0;
+#endif
 
 	while ((item = list_pop(&head))) {
 		assert(item->scratchpad != 0);
@@ -248,7 +460,7 @@ static void concat(test_, TYPE)(void)
 	assert(l == k);
 	assert(list_count(&head) == 0);
 	assert(list_first(&head) == NULL);
-	ts_ref("pop");
+	ts_hash("pop", "df3f619804a92fdb4057192dc43dd748ea778adc52bc498ce80524c014b81119");
 
 	list_fini(&head);
 	ts_ref("fini");
@@ -256,6 +468,8 @@ static void concat(test_, TYPE)(void)
 	printf("%s end\n", str(TYPE));
 }
 
+#undef ts_hashx
+
 #undef item
 #undef itm
 #undef head
@@ -271,6 +485,9 @@ static void concat(test_, TYPE)(void)
 #undef list_next_safe
 #undef list_count
 #undef list_add
+#undef list_add_head
+#undef list_add_tail
+#undef list_add_after
 #undef list_find
 #undef list_find_lt
 #undef list_find_gteq
diff --git a/tests/lib/test_typelist.py b/tests/lib/test_typelist.py
index 11cabecd2..9866cdf38 100644
--- a/tests/lib/test_typelist.py
+++ b/tests/lib/test_typelist.py
@@ -3,6 +3,8 @@ import frrtest
 class TestTypelist(frrtest.TestMultiOut):
     program = './test_typelist'
 
+TestTypelist.onesimple('LIST end')
+TestTypelist.onesimple('DLIST end')
 TestTypelist.onesimple('SORTLIST_UNIQ end')
 TestTypelist.onesimple('SORTLIST_NONUNIQ end')
 TestTypelist.onesimple('HASH end')