tests: more datastructure tests

A little something for everybody in here.

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

3 files changed, 106 insertions, 46 deletions

diff --git a/tests/lib/test_typelist.c b/tests/lib/test_typelist.c
index 3ca8bf303..2438fb5f0 100644
--- a/tests/lib/test_typelist.c
+++ b/tests/lib/test_typelist.c
@@ -52,46 +52,32 @@
 #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
-#define _U_SKIPLIST_UNIQ	1
-#define _U_SKIPLIST_NONUNIQ	0
-#define _U_RBTREE_UNIQ		1
-#define _U_RBTREE_NONUNIQ	0
-#define _U_ATOMSORT_UNIQ	1
-#define _U_ATOMSORT_NONUNIQ	0
-
-#define _IS_UNIQ(type)		_U_##type
-#define IS_UNIQ(type)		_IS_UNIQ(type)
-
-#define _H_SORTLIST_UNIQ	0
-#define _H_SORTLIST_NONUNIQ	0
-#define _H_HASH			1
-#define _H_SKIPLIST_UNIQ	0
-#define _H_SKIPLIST_NONUNIQ	0
-#define _H_RBTREE_UNIQ		0
-#define _H_RBTREE_NONUNIQ	0
-#define _H_ATOMSORT_UNIQ	0
-#define _H_ATOMSORT_NONUNIQ	0
-
-#define _IS_HASH(type)		_H_##type
-#define IS_HASH(type)		_IS_HASH(type)
+#define T_SORTED		(1 << 0)
+#define T_UNIQ			(1 << 1)
+#define T_HASH			(1 << 2)
+#define T_HEAP			(1 << 3)
+#define T_ATOMIC		(1 << 4)
+
+#define _T_LIST			(0)
+#define _T_DLIST		(0)
+#define _T_ATOMLIST		(0                 | T_ATOMIC)
+#define _T_HEAP			(T_SORTED          | T_HEAP)
+#define _T_SORTLIST_UNIQ	(T_SORTED | T_UNIQ)
+#define _T_SORTLIST_NONUNIQ	(T_SORTED)
+#define _T_HASH			(T_SORTED | T_UNIQ | T_HASH)
+#define _T_SKIPLIST_UNIQ	(T_SORTED | T_UNIQ)
+#define _T_SKIPLIST_NONUNIQ	(T_SORTED)
+#define _T_RBTREE_UNIQ		(T_SORTED | T_UNIQ)
+#define _T_RBTREE_NONUNIQ	(T_SORTED)
+#define _T_ATOMSORT_UNIQ	(T_SORTED | T_UNIQ | T_ATOMIC)
+#define _T_ATOMSORT_NONUNIQ	(T_SORTED          | T_ATOMIC)
+
+#define _T_TYPE(type)		_T_##type
+#define IS_SORTED(type)		(_T_TYPE(type) & T_SORTED)
+#define IS_UNIQ(type)		(_T_TYPE(type) & T_UNIQ)
+#define IS_HASH(type)		(_T_TYPE(type) & T_HASH)
+#define IS_HEAP(type)		(_T_TYPE(type) & T_HEAP)
+#define IS_ATOMIC(type)		(_T_TYPE(type) & T_ATOMIC)
 
 static struct timeval ref, ref0;
 
@@ -120,6 +106,12 @@ static void ts_end(void)
 #define TYPE DLIST
 #include "test_typelist.h"
 
+#define TYPE ATOMLIST
+#include "test_typelist.h"
+
+#define TYPE HEAP
+#include "test_typelist.h"
+
 #define TYPE SORTLIST_UNIQ
 #include "test_typelist.h"
 
@@ -159,6 +151,8 @@ int main(int argc, char **argv)
 
 	test_LIST();
 	test_DLIST();
+	test_ATOMLIST();
+	test_HEAP();
 	test_SORTLIST_UNIQ();
 	test_SORTLIST_NONUNIQ();
 	test_HASH();
diff --git a/tests/lib/test_typelist.h b/tests/lib/test_typelist.h
index b3f3d3b4e..f09175fea 100644
--- a/tests/lib/test_typelist.h
+++ b/tests/lib/test_typelist.h
@@ -131,7 +131,7 @@ static void ts_hash(const char *text, const char *expect)
 	monotime(&ref);
 }
 /* hashes will have different item ordering */
-#if IS_HASH(REALTYPE)
+#if IS_HASH(REALTYPE) || IS_HEAP(REALTYPE)
 #define ts_hashx(pos, csum) ts_hash(pos, NULL)
 #else
 #define ts_hashx(pos, csum) ts_hash(pos, csum)
@@ -165,8 +165,11 @@ static void concat(test_, TYPE)(void)
 			list_add(&head, &itm[j]);
 			itm[j].scratchpad = 1;
 			k++;
-		} else
+		}
+#if !IS_HEAP(REALTYPE)
+		else
 			assert(list_add(&head, &itm[j]) == &itm[j]);
+#endif
 	}
 	assert(list_count(&head) == k);
 	assert(list_first(&head) != NULL);
@@ -175,7 +178,7 @@ static void concat(test_, TYPE)(void)
 	k = 0;
 	prev = NULL;
 	for_each(list, &head, item) {
-#if IS_HASH(REALTYPE)
+#if IS_HASH(REALTYPE) || IS_HEAP(REALTYPE)
 		/* hash table doesn't give sorting */
 		(void)prev;
 #else
@@ -210,7 +213,22 @@ static void concat(test_, TYPE)(void)
 		}
 	}
 	ts_hashx("add-dup", "a538546a6e6ab0484e925940aa8dd02fd934408bbaed8cb66a0721841584d838");
-#else /* !IS_UNIQ(REALTYPE) */
+
+#elif IS_HEAP(REALTYPE)
+	/* heap - partially sorted. */
+	prev = NULL;
+	l = k / 2;
+	for (i = 0; i < l; i++) {
+		item = list_pop(&head);
+		if (prev)
+			assert(prev->val < item->val);
+		item->scratchpad = 0;
+		k--;
+		prev = item;
+	}
+	ts_hash("pop", NULL);
+
+#else /* !IS_UNIQ(REALTYPE) && !IS_HEAP(REALTYPE) */
 	for (i = 0; i < NITEM; i++) {
 		j = prng_rand(prng) % NITEM;
 		memset(&dummy, 0, sizeof(dummy));
@@ -241,7 +259,7 @@ static void concat(test_, TYPE)(void)
 	}
 	ts_hash("add-dup+find_{lt,gteq}", "a538546a6e6ab0484e925940aa8dd02fd934408bbaed8cb66a0721841584d838");
 #endif
-#if !IS_HASH(REALTYPE)
+#if !IS_HASH(REALTYPE) && !IS_HEAP(REALTYPE)
 	prng_free(prng);
 	prng = prng_new(123456);
 
@@ -418,6 +436,51 @@ static void concat(test_, TYPE)(void)
 			item->scratchpad = 1;
 			k++;
 
+			switch ((op >> 1) & 1) {
+			case 0:
+				list_add_head(&head, item);
+				break;
+			case 1:
+				list_add_tail(&head, item);
+				break;
+			default:
+				assert(0);
+			}
+		}
+	}
+	assert(list_count(&head) == k);
+	assert(list_first(&head) != NULL);
+	ts_hash("prng add/del", "4909f31d06bb006efca4dfeebddb8de071733ddf502f89b6d532155208bbc6df");
+
+#if !IS_ATOMIC(REALTYPE)
+	/* variant with add_after */
+
+	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);
@@ -446,7 +509,8 @@ static void concat(test_, TYPE)(void)
 	}
 	assert(list_count(&head) == k);
 	assert(list_first(&head) != NULL);
-	ts_hash("prng add/del", "8c5dd192505c8cc8337f9b936f88e90dbc5854cb3fd7391c47189d131fa399fd");
+	ts_hash("prng add/after/del", "84c5fc83294eabebb9808ccbba32a303c4fca084db87ed1277d2bae1f8c5bee4");
+#endif
 
 	l = 0;
 #endif
diff --git a/tests/lib/test_typelist.py b/tests/lib/test_typelist.py
index 9866cdf38..0b3c74397 100644
--- a/tests/lib/test_typelist.py
+++ b/tests/lib/test_typelist.py
@@ -5,6 +5,8 @@ class TestTypelist(frrtest.TestMultiOut):
 
 TestTypelist.onesimple('LIST end')
 TestTypelist.onesimple('DLIST end')
+TestTypelist.onesimple('ATOMLIST end')
+TestTypelist.onesimple('HEAP end')
 TestTypelist.onesimple('SORTLIST_UNIQ end')
 TestTypelist.onesimple('SORTLIST_NONUNIQ end')
 TestTypelist.onesimple('HASH end')