[mirror_frr.git] / tests / lib / test_typelist.h

/*
 * Copyright (c) 2019  David Lamparter, for NetDEF, Inc.
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

/* C++ called, they want their templates back */
#define item		concat(item_, TYPE)
#define itm		concat(itm_, TYPE)
#define head		concat(head_, TYPE)
#define list		concat(TYPE, )
#define list_head	concat(TYPE, _head)
#define list_item	concat(TYPE, _item)
#define list_cmp	concat(TYPE, _cmp)
#define list_hash	concat(TYPE, _hash)
#define list_init	concat(TYPE, _init)
#define list_fini	concat(TYPE, _fini)
#define list_first	concat(TYPE, _first)
#define list_next	concat(TYPE, _next)
#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

PREDECL(REALTYPE, list)
struct item {
	uint64_t val;
	struct list_item itm;
	int scratchpad;
};

#if IS_SORTED(REALTYPE)
static int list_cmp(const struct item *a, const struct item *b);

#if IS_HASH(REALTYPE)
static uint32_t list_hash(const struct item *a);
DECLARE(REALTYPE, list, struct item, itm, list_cmp, list_hash)

static uint32_t list_hash(const struct item *a)
{
#ifdef SHITTY_HASH
	/* crappy hash to get some hash collisions */
	return a->val ^ (a->val << 29) ^ 0x55AA0000U;
#else
	return jhash_1word(a->val, 0xdeadbeef);
#endif
}

#else
DECLARE(REALTYPE, list, struct item, itm, list_cmp)
#endif

static int list_cmp(const struct item *a, const struct item *b)
{
	if (a->val > b->val)
		return 1;
	if (a->val < b->val)
		return -1;
	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 swap_count, count;

	count = list_count(&head);
	swap_count = htonl(count);

	SHA256_Init(&ctx);
	SHA256_Update(&ctx, &swap_count, sizeof(swap_count));

	frr_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) || IS_HEAP(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 __attribute__((unused));
	struct item dummy __attribute__((unused));

	memset(itm, 0, sizeof(itm));
	for (i = 0; i < NITEM; i++)
		itm[i].val = i;

	printf("%s start\n", str(TYPE));
	ts_start();

	list_init(&head);
	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++) {
		j = prng_rand(prng) % NITEM;
		if (itm[j].scratchpad == 0) {
			list_add(&head, &itm[j]);
			itm[j].scratchpad = 1;
			k++;
		}
#if !IS_HEAP(REALTYPE)
		else
			assert(list_add(&head, &itm[j]) == &itm[j]);
#endif
	}
	assert(list_count(&head) == k);
	assert(list_first(&head) != NULL);
	ts_hashx("fill", "a538546a6e6ab0484e925940aa8dd02fd934408bbaed8cb66a0721841584d838");

	k = 0;
	prev = NULL;
	frr_each(list, &head, item) {
#if IS_HASH(REALTYPE) || IS_HEAP(REALTYPE)
		/* hash table doesn't give sorting */
		(void)prev;
#else
		assert(!prev || prev->val < item->val);
#endif
		prev = item;
		k++;
	}
	assert(list_count(&head) == k);
	ts_ref("walk");

#if IS_UNIQ(REALTYPE)
	prng_free(prng);
	prng = prng_new(0);

	for (i = 0; i < NITEM; i++) {
		j = prng_rand(prng) % NITEM;
		dummy.val = j;
		assert(list_find(&head, &dummy) == &itm[j]);
	}
	ts_ref("find");

	for (i = 0; i < NITEM; i++) {
		j = prng_rand(prng) % NITEM;
		memset(&dummy, 0, sizeof(dummy));
		dummy.val = j;
		if (itm[j].scratchpad)
			assert(list_add(&head, &dummy) == &itm[j]);
		else {
			assert(list_add(&head, &dummy) == NULL);
			assert(list_del(&head, &dummy) != NULL);
		}
	}
	ts_hashx("add-dup", "a538546a6e6ab0484e925940aa8dd02fd934408bbaed8cb66a0721841584d838");

#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));
		dummy.val = j;

		list_add(&head, &dummy);
		if (itm[j].scratchpad) {
			struct item *lt, *gteq, dummy2;

			assert(list_next(&head, &itm[j]) == &dummy ||
				list_next(&head, &dummy) == &itm[j]);

			memset(&dummy2, 0, sizeof(dummy));
			dummy2.val = j;
			lt = list_find_lt(&head, &dummy2);
			gteq = list_find_gteq(&head, &dummy2);

			assert(gteq == &itm[j] || gteq == &dummy);
			if (lt)
				assert(list_next(&head, lt) == &itm[j] ||
					list_next(&head, lt) == &dummy);
			else
				assert(list_first(&head) == &itm[j] ||
					list_first(&head) == &dummy);
		} else if (list_next(&head, &dummy))
			assert(list_next(&head, &dummy)->val > j);
		assert(list_del(&head, &dummy) != NULL);
	}
	ts_hash("add-dup+find_{lt,gteq}", "a538546a6e6ab0484e925940aa8dd02fd934408bbaed8cb66a0721841584d838");
#endif
#if !IS_HASH(REALTYPE) && !IS_HEAP(REALTYPE)
	prng_free(prng);
	prng = prng_new(123456);

	l = 0;
	for (i = 0; i < NITEM; i++) {
		struct item *lt, *gteq, *tmp;

		j = prng_rand(prng) % NITEM;
		dummy.val = j;

		lt = list_find_lt(&head, &dummy);
		gteq = list_find_gteq(&head, &dummy);

		if (lt) {
			assert(lt->val < j);
			tmp = list_next(&head, lt);
			assert(tmp == gteq);
			assert(!tmp || tmp->val >= j);
		} else
			assert(gteq == list_first(&head));

		if (gteq)
			assert(gteq->val >= j);
	}
	ts_ref("find_{lt,gteq}");
#endif /* !IS_HASH */

	prng_free(prng);
	prng = prng_new(0);

	l = 0;
	for (i = 0; i < NITEM; i++) {
		(void)prng_rand(prng);
		j = prng_rand(prng) % NITEM;
		if (itm[j].scratchpad == 1) {
			assert(list_del(&head, &itm[j]) != NULL);
			itm[j].scratchpad = 0;
			l++;
		}
	}
	assert(l + list_count(&head) == k);
	ts_hashx("del", "cb2e5d80f08a803ef7b56c15e981b681adcea214bebc2f55e12e0bfb242b07ca");

	frr_each_safe(list, &head, item) {
		assert(item->scratchpad != 0);

		if (item->val & 1) {
			assert(list_del(&head, item) != NULL);
			item->scratchpad = 0;
			l++;
		}
	}
	assert(l + list_count(&head) == k);
	ts_hashx("frr_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) {
			assert(list_del(&head, &itm[j]) != NULL);
			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) {
			assert(list_del(&head, &itm[j]) != NULL);
			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;
				assert(list_del(&head, item) != NULL);
			}
			item->scratchpad = 0;
			k--;
		} else {
			item = &itm[j];
			if (item->scratchpad != 0)
				continue;

			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;
				assert(list_del(&head, item) != NULL);
			}
			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/after/del", "84c5fc83294eabebb9808ccbba32a303c4fca084db87ed1277d2bae1f8c5bee4");
#endif

	l = 0;
#endif

	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");

	list_fini(&head);
	ts_ref("fini");
	ts_end();
	printf("%s end\n", str(TYPE));
}

#undef ts_hashx

#undef item
#undef itm
#undef head
#undef list
#undef list_head
#undef list_item
#undef list_cmp
#undef list_hash
#undef list_init
#undef list_fini
#undef list_first
#undef list_next
#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
#undef list_del
#undef list_pop

#undef REALTYPE
#undef TYPE
Commit	Line	Data
992f9967 DL	1	/*
	2	* Copyright (c) 2019 David Lamparter, for NetDEF, Inc.
	3	*
	4	* Permission to use, copy, modify, and distribute this software for any
	5	* purpose with or without fee is hereby granted, provided that the above
	6	* copyright notice and this permission notice appear in all copies.
	7	*
	8	* THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
	9	* WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
	10	* MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
	11	* ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
	12	* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
	13	* ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
	14	* OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
	15	*/
	16
	17	/* C++ called, they want their templates back */
	18	#define item concat(item_, TYPE)
	19	#define itm concat(itm_, TYPE)
	20	#define head concat(head_, TYPE)
	21	#define list concat(TYPE, )
	22	#define list_head concat(TYPE, _head)
	23	#define list_item concat(TYPE, _item)
	24	#define list_cmp concat(TYPE, _cmp)
	25	#define list_hash concat(TYPE, _hash)
	26	#define list_init concat(TYPE, _init)
	27	#define list_fini concat(TYPE, _fini)
	28	#define list_first concat(TYPE, _first)
	29	#define list_next concat(TYPE, _next)
	30	#define list_next_safe concat(TYPE, _next_safe)
	31	#define list_count concat(TYPE, _count)
	32	#define list_add concat(TYPE, _add)
8c3d03b3 DL	33	#define list_add_head concat(TYPE, _add_head)
	34	#define list_add_tail concat(TYPE, _add_tail)
	35	#define list_add_after concat(TYPE, _add_after)
992f9967 DL	36	#define list_find concat(TYPE, _find)
	37	#define list_find_lt concat(TYPE, _find_lt)
	38	#define list_find_gteq concat(TYPE, _find_gteq)
	39	#define list_del concat(TYPE, _del)
	40	#define list_pop concat(TYPE, _pop)
	41
8c3d03b3 DL	42	#define ts_hash concat(ts_hash_, TYPE)
8c3d03b3 DL	43
2214f160 DL	44	#ifndef REALTYPE
	45	#define REALTYPE TYPE
	46	#endif
	47
	48	PREDECL(REALTYPE, list)
992f9967 DL	49	struct item {
	50	uint64_t val;
	51	struct list_item itm;
	52	int scratchpad;
	53	};
	54
8c3d03b3	55	#if IS_SORTED(REALTYPE)
992f9967 DL	56	static int list_cmp(const struct item a, const struct item b);
992f9967 DL	57
2214f160	58	#if IS_HASH(REALTYPE)
992f9967	59	static uint32_t list_hash(const struct item *a);
2214f160	60	DECLARE(REALTYPE, list, struct item, itm, list_cmp, list_hash)
992f9967 DL	61
	62	static uint32_t list_hash(const struct item *a)
	63	{
2214f160	64	#ifdef SHITTY_HASH
992f9967 DL	65	/* crappy hash to get some hash collisions */
992f9967 DL	66	return a->val ^ (a->val << 29) ^ 0x55AA0000U;
2214f160 DL	67	#else
	68	return jhash_1word(a->val, 0xdeadbeef);
	69	#endif
992f9967 DL	70	}
	71
	72	#else
2214f160	73	DECLARE(REALTYPE, list, struct item, itm, list_cmp)
992f9967 DL	74	#endif
	75
	76	static int list_cmp(const struct item a, const struct item b)
	77	{
	78	if (a->val > b->val)
	79	return 1;
	80	if (a->val < b->val)
	81	return -1;
	82	return 0;
	83	}
	84
8c3d03b3 DL	85	#else /* !IS_SORTED */
	86	DECLARE(REALTYPE, list, struct item, itm)
	87	#endif
	88
992f9967 DL	89	#define NITEM 10000
992f9967 DL	90	struct item itm[NITEM];
2214f160	91	static struct list_head head = concat(INIT_, REALTYPE)(head);
992f9967	92
8c3d03b3 DL	93	static void ts_hash(const char text, const char expect)
	94	{
	95	int64_t us = monotime_since(&ref, NULL);
	96	SHA256_CTX ctx;
	97	struct item *item;
	98	unsigned i = 0;
	99	uint8_t hash[32];
	100	char hashtext[65];
1dc46d1e	101	uint32_t swap_count, count;
8c3d03b3	102
1dc46d1e MS	103	count = list_count(&head);
1dc46d1e MS	104	swap_count = htonl(count);
8c3d03b3 DL	105
8c3d03b3 DL	106	SHA256_Init(&ctx);
1dc46d1e	107	SHA256_Update(&ctx, &swap_count, sizeof(swap_count));
8c3d03b3	108
81fddbe7	109	frr_each (list, &head, item) {
8c3d03b3 DL	110	struct {
	111	uint32_t val_upper, val_lower, index;
	112	} hashitem = {
	113	htonl(item->val >> 32),
	114	htonl(item->val & 0xFFFFFFFFULL),
	115	htonl(i),
	116	};
	117	SHA256_Update(&ctx, &hashitem, sizeof(hashitem));
	118	i++;
1dc46d1e	119	assert(i <= count);
8c3d03b3 DL	120	}
	121	SHA256_Final(hash, &ctx);
	122
	123	for (i = 0; i < sizeof(hash); i++)
	124	sprintf(hashtext + i * 2, "%02x", hash[i]);
	125
	126	printf("%7"PRId64"us %-25s %s%s\n", us, text,
	127	expect ? " " : "*", hashtext);
	128	if (expect && strcmp(expect, hashtext)) {
	129	printf("%-21s %s\n", "EXPECTED:", expect);
	130	assert(0);
	131	}
	132	monotime(&ref);
	133	}
	134	/* hashes will have different item ordering */
d0a0e597	135	#if IS_HASH(REALTYPE) \|\| IS_HEAP(REALTYPE)
8c3d03b3 DL	136	#define ts_hashx(pos, csum) ts_hash(pos, NULL)
	137	#else
	138	#define ts_hashx(pos, csum) ts_hash(pos, csum)
	139	#endif
	140
992f9967 DL	141	static void concat(test_, TYPE)(void)
	142	{
	143	size_t i, j, k, l;
	144	struct prng *prng;
8c3d03b3 DL	145	struct item item, prev __attribute__((unused));
8c3d03b3 DL	146	struct item dummy __attribute__((unused));
992f9967 DL	147
	148	memset(itm, 0, sizeof(itm));
	149	for (i = 0; i < NITEM; i++)
	150	itm[i].val = i;
	151
	152	printf("%s start\n", str(TYPE));
	153	ts_start();
	154
	155	list_init(&head);
992f9967 DL	156	assert(list_first(&head) == NULL);
992f9967 DL	157
8c3d03b3 DL	158	ts_hash("init", "df3f619804a92fdb4057192dc43dd748ea778adc52bc498ce80524c014b81119");
	159
	160	#if IS_SORTED(REALTYPE)
992f9967 DL	161	prng = prng_new(0);
	162	k = 0;
	163	for (i = 0; i < NITEM; i++) {
	164	j = prng_rand(prng) % NITEM;
	165	if (itm[j].scratchpad == 0) {
	166	list_add(&head, &itm[j]);
	167	itm[j].scratchpad = 1;
	168	k++;
d0a0e597 DL	169	}
	170	#if !IS_HEAP(REALTYPE)
	171	else
992f9967	172	assert(list_add(&head, &itm[j]) == &itm[j]);
d0a0e597	173	#endif
992f9967 DL	174	}
	175	assert(list_count(&head) == k);
	176	assert(list_first(&head) != NULL);
8c3d03b3	177	ts_hashx("fill", "a538546a6e6ab0484e925940aa8dd02fd934408bbaed8cb66a0721841584d838");
992f9967 DL	178
	179	k = 0;
	180	prev = NULL;
81fddbe7	181	frr_each(list, &head, item) {
d0a0e597	182	#if IS_HASH(REALTYPE) \|\| IS_HEAP(REALTYPE)
992f9967 DL	183	/* hash table doesn't give sorting */
	184	(void)prev;
	185	#else
	186	assert(!prev \|\| prev->val < item->val);
	187	#endif
	188	prev = item;
	189	k++;
	190	}
	191	assert(list_count(&head) == k);
	192	ts_ref("walk");
	193
2214f160	194	#if IS_UNIQ(REALTYPE)
992f9967 DL	195	prng_free(prng);
	196	prng = prng_new(0);
	197
	198	for (i = 0; i < NITEM; i++) {
	199	j = prng_rand(prng) % NITEM;
	200	dummy.val = j;
	201	assert(list_find(&head, &dummy) == &itm[j]);
	202	}
	203	ts_ref("find");
	204
	205	for (i = 0; i < NITEM; i++) {
	206	j = prng_rand(prng) % NITEM;
	207	memset(&dummy, 0, sizeof(dummy));
	208	dummy.val = j;
	209	if (itm[j].scratchpad)
	210	assert(list_add(&head, &dummy) == &itm[j]);
	211	else {
	212	assert(list_add(&head, &dummy) == NULL);
7de7c75b	213	assert(list_del(&head, &dummy) != NULL);
992f9967 DL	214	}
992f9967 DL	215	}
8c3d03b3	216	ts_hashx("add-dup", "a538546a6e6ab0484e925940aa8dd02fd934408bbaed8cb66a0721841584d838");
d0a0e597 DL	217
	218	#elif IS_HEAP(REALTYPE)
	219	/* heap - partially sorted. */
	220	prev = NULL;
	221	l = k / 2;
	222	for (i = 0; i < l; i++) {
	223	item = list_pop(&head);
	224	if (prev)
	225	assert(prev->val < item->val);
	226	item->scratchpad = 0;
	227	k--;
	228	prev = item;
	229	}
	230	ts_hash("pop", NULL);
	231
	232	#else /* !IS_UNIQ(REALTYPE) && !IS_HEAP(REALTYPE) */
992f9967 DL	233	for (i = 0; i < NITEM; i++) {
	234	j = prng_rand(prng) % NITEM;
	235	memset(&dummy, 0, sizeof(dummy));
	236	dummy.val = j;
	237
	238	list_add(&head, &dummy);
	239	if (itm[j].scratchpad) {
	240	struct item lt, gteq, dummy2;
	241
	242	assert(list_next(&head, &itm[j]) == &dummy \|\|
	243	list_next(&head, &dummy) == &itm[j]);
	244
	245	memset(&dummy2, 0, sizeof(dummy));
	246	dummy2.val = j;
	247	lt = list_find_lt(&head, &dummy2);
	248	gteq = list_find_gteq(&head, &dummy2);
	249
	250	assert(gteq == &itm[j] \|\| gteq == &dummy);
	251	if (lt)
	252	assert(list_next(&head, lt) == &itm[j] \|\|
	253	list_next(&head, lt) == &dummy);
	254	else
	255	assert(list_first(&head) == &itm[j] \|\|
	256	list_first(&head) == &dummy);
	257	} else if (list_next(&head, &dummy))
	258	assert(list_next(&head, &dummy)->val > j);
7de7c75b	259	assert(list_del(&head, &dummy) != NULL);
992f9967	260	}
8c3d03b3	261	ts_hash("add-dup+find_{lt,gteq}", "a538546a6e6ab0484e925940aa8dd02fd934408bbaed8cb66a0721841584d838");
992f9967	262	#endif
d0a0e597	263	#if !IS_HASH(REALTYPE) && !IS_HEAP(REALTYPE)
992f9967 DL	264	prng_free(prng);
	265	prng = prng_new(123456);
	266
	267	l = 0;
	268	for (i = 0; i < NITEM; i++) {
	269	struct item lt, gteq, *tmp;
	270
	271	j = prng_rand(prng) % NITEM;
	272	dummy.val = j;
	273
	274	lt = list_find_lt(&head, &dummy);
	275	gteq = list_find_gteq(&head, &dummy);
	276
	277	if (lt) {
	278	assert(lt->val < j);
	279	tmp = list_next(&head, lt);
	280	assert(tmp == gteq);
	281	assert(!tmp \|\| tmp->val >= j);
	282	} else
	283	assert(gteq == list_first(&head));
c258527b	284
992f9967 DL	285	if (gteq)
	286	assert(gteq->val >= j);
	287	}
	288	ts_ref("find_{lt,gteq}");
	289	#endif /* !IS_HASH */
	290
	291	prng_free(prng);
	292	prng = prng_new(0);
	293
	294	l = 0;
	295	for (i = 0; i < NITEM; i++) {
	296	(void)prng_rand(prng);
	297	j = prng_rand(prng) % NITEM;
	298	if (itm[j].scratchpad == 1) {
7de7c75b	299	assert(list_del(&head, &itm[j]) != NULL);
992f9967 DL	300	itm[j].scratchpad = 0;
	301	l++;
	302	}
	303	}
	304	assert(l + list_count(&head) == k);
8c3d03b3	305	ts_hashx("del", "cb2e5d80f08a803ef7b56c15e981b681adcea214bebc2f55e12e0bfb242b07ca");
992f9967	306
81fddbe7	307	frr_each_safe(list, &head, item) {
992f9967 DL	308	assert(item->scratchpad != 0);
	309
	310	if (item->val & 1) {
7de7c75b	311	assert(list_del(&head, item) != NULL);
992f9967 DL	312	item->scratchpad = 0;
	313	l++;
	314	}
	315	}
	316	assert(l + list_count(&head) == k);
81fddbe7	317	ts_hashx("frr_each_safe+del", "e0beb71dd963a75af05b722b8e71b61b304587d860c8accdc4349067542b86bb");
8c3d03b3 DL	318
	319	#else /* !IS_SORTED */
	320	prng = prng_new(0);
	321	k = 0;
	322	for (i = 0; i < NITEM; i++) {
	323	j = prng_rand(prng) % NITEM;
	324	if (itm[j].scratchpad == 0) {
	325	list_add_tail(&head, &itm[j]);
	326	itm[j].scratchpad = 1;
	327	k++;
	328	}
	329	}
	330	assert(list_count(&head) == k);
	331	assert(list_first(&head) != NULL);
	332	ts_hash("fill / add_tail", "eabfcf1413936daaf20965abced95762f45110a6619b84aac7d38481bce4ea19");
	333
	334	for (i = 0; i < NITEM / 2; i++) {
	335	j = prng_rand(prng) % NITEM;
	336	if (itm[j].scratchpad == 1) {
7de7c75b	337	assert(list_del(&head, &itm[j]) != NULL);
8c3d03b3 DL	338	itm[j].scratchpad = 0;
	339	k--;
	340	}
	341	}
	342	ts_hash("del-prng", "86d568a95eb429dab3162976c5a5f3f75aabc835932cd682aa280b6923549564");
	343
	344	l = 0;
	345	while ((item = list_pop(&head))) {
	346	assert(item->scratchpad != 0);
	347
	348	item->scratchpad = 0;
	349	l++;
	350	}
	351	assert(l == k);
	352	assert(list_count(&head) == 0);
	353	assert(list_first(&head) == NULL);
	354	ts_hash("pop", "df3f619804a92fdb4057192dc43dd748ea778adc52bc498ce80524c014b81119");
	355
	356	prng_free(prng);
	357	prng = prng_new(0x1e5a2d69);
	358
	359	k = 0;
	360	for (i = 0; i < NITEM; i++) {
	361	j = prng_rand(prng) % NITEM;
	362	if (itm[j].scratchpad == 0) {
	363	list_add_head(&head, &itm[j]);
	364	itm[j].scratchpad = 1;
	365	k++;
	366	}
	367	}
	368	assert(list_count(&head) == k);
	369	assert(list_first(&head) != NULL);
	370	ts_hash("fill / add_head", "3084d8f8a28b8c756ccc0a92d60d86f6d776273734ddc3f9e1d89526f5ca2795");
	371
	372	for (i = 0; i < NITEM / 2; i++) {
	373	j = prng_rand(prng) % NITEM;
	374	if (itm[j].scratchpad == 1) {
7de7c75b	375	assert(list_del(&head, &itm[j]) != NULL);
8c3d03b3 DL	376	itm[j].scratchpad = 0;
	377	k--;
	378	}
	379	}
	380	ts_hash("del-prng", "dc916fa7ea4418792c7c8232d74df2887f9975ead4222f4b977be6bc0b52285e");
	381
	382	l = 0;
	383	while ((item = list_pop(&head))) {
	384	assert(item->scratchpad != 0);
	385
	386	item->scratchpad = 0;
	387	l++;
	388	}
	389	assert(l == k);
	390	assert(list_count(&head) == 0);
	391	assert(list_first(&head) == NULL);
	392	ts_hash("pop", "df3f619804a92fdb4057192dc43dd748ea778adc52bc498ce80524c014b81119");
	393
	394	prng_free(prng);
	395	prng = prng_new(0x692d1e5a);
	396
	397	k = 0;
	398	for (i = 0; i < NITEM; i++) {
	399	j = prng_rand(prng) % NITEM;
	400	if (itm[j].scratchpad == 0) {
	401	if (prng_rand(prng) & 1) {
	402	list_add_tail(&head, &itm[j]);
	403	} else {
	404	list_add_head(&head, &itm[j]);
	405	}
	406	itm[j].scratchpad = 1;
	407	k++;
	408	}
	409	}
	410	assert(list_count(&head) == k);
	411	assert(list_first(&head) != NULL);
	412	ts_hash("fill / add_{head,tail}", "93fa180a575c96e4b6c3775c2de7843ee3254dd6ed5af699bbe155f994114b06");
	413
d0a0e597 DL	414	for (i = 0; i < NITEM * 3; i++) {
	415	int op = prng_rand(prng);
	416	j = prng_rand(prng) % NITEM;
	417
	418	if (op & 1) {
	419	/* delete or pop */
	420	if (op & 2) {
	421	item = list_pop(&head);
	422	if (!item)
	423	continue;
	424	} else {
	425	item = &itm[j];
	426	if (item->scratchpad == 0)
	427	continue;
7de7c75b	428	assert(list_del(&head, item) != NULL);
d0a0e597 DL	429	}
	430	item->scratchpad = 0;
	431	k--;
	432	} else {
	433	item = &itm[j];
	434	if (item->scratchpad != 0)
	435	continue;
	436
	437	item->scratchpad = 1;
	438	k++;
	439
	440	switch ((op >> 1) & 1) {
	441	case 0:
	442	list_add_head(&head, item);
	443	break;
	444	case 1:
	445	list_add_tail(&head, item);
	446	break;
	447	default:
	448	assert(0);
	449	}
	450	}
	451	}
	452	assert(list_count(&head) == k);
	453	assert(list_first(&head) != NULL);
	454	ts_hash("prng add/del", "4909f31d06bb006efca4dfeebddb8de071733ddf502f89b6d532155208bbc6df");
	455
	456	#if !IS_ATOMIC(REALTYPE)
	457	/* variant with add_after */
	458
8c3d03b3 DL	459	for (i = 0; i < NITEM * 3; i++) {
	460	int op = prng_rand(prng);
	461	j = prng_rand(prng) % NITEM;
	462
	463	if (op & 1) {
	464	/* delete or pop */
	465	if (op & 2) {
	466	item = list_pop(&head);
	467	if (!item)
	468	continue;
	469	} else {
	470	item = &itm[j];
	471	if (item->scratchpad == 0)
	472	continue;
7de7c75b	473	assert(list_del(&head, item) != NULL);
8c3d03b3 DL	474	}
	475	item->scratchpad = 0;
	476	k--;
	477	} else {
	478	item = &itm[j];
	479	if (item->scratchpad != 0)
	480	continue;
	481
	482	item->scratchpad = 1;
	483	k++;
	484
	485	switch ((op >> 1) & 3) {
	486	case 0:
	487	list_add_head(&head, item);
	488	break;
	489	case 1:
	490	list_add_tail(&head, item);
	491	break;
	492	case 2:
	493	case 3:
	494	prev = NULL;
	495	l = 0;
	496	do {
	497	j = prng_rand(prng) % NITEM;
	498	prev = &itm[j];
	499	if (prev->scratchpad == 0
	500	\|\| prev == item)
	501	prev = NULL;
	502	l++;
	503	} while (!prev && l < 10);
	504	list_add_after(&head, prev, item);
	505	break;
	506	default:
	507	assert(0);
	508	}
	509	}
	510	}
	511	assert(list_count(&head) == k);
	512	assert(list_first(&head) != NULL);
d0a0e597 DL	513	ts_hash("prng add/after/del", "84c5fc83294eabebb9808ccbba32a303c4fca084db87ed1277d2bae1f8c5bee4");
d0a0e597 DL	514	#endif
8c3d03b3 DL	515
	516	l = 0;
	517	#endif
992f9967 DL	518
	519	while ((item = list_pop(&head))) {
	520	assert(item->scratchpad != 0);
	521
	522	item->scratchpad = 0;
	523	l++;
	524	}
	525	assert(l == k);
	526	assert(list_count(&head) == 0);
	527	assert(list_first(&head) == NULL);
8c3d03b3	528	ts_hash("pop", "df3f619804a92fdb4057192dc43dd748ea778adc52bc498ce80524c014b81119");
992f9967 DL	529
	530	list_fini(&head);
	531	ts_ref("fini");
	532	ts_end();
	533	printf("%s end\n", str(TYPE));
	534	}
	535
8c3d03b3 DL	536	#undef ts_hashx
8c3d03b3 DL	537
992f9967 DL	538	#undef item
	539	#undef itm
	540	#undef head
	541	#undef list
	542	#undef list_head
	543	#undef list_item
	544	#undef list_cmp
	545	#undef list_hash
	546	#undef list_init
	547	#undef list_fini
	548	#undef list_first
	549	#undef list_next
	550	#undef list_next_safe
	551	#undef list_count
	552	#undef list_add
8c3d03b3 DL	553	#undef list_add_head
	554	#undef list_add_tail
	555	#undef list_add_after
992f9967 DL	556	#undef list_find
	557	#undef list_find_lt
	558	#undef list_find_gteq
	559	#undef list_del
	560	#undef list_pop
	561
2214f160	562	#undef REALTYPE
992f9967	563	#undef TYPE