lib: add *_swap_all to typesafe containers

Signed-off-by: David Lamparter <equinox@opensourcerouting.org>

4 files changed, 201 insertions, 7 deletions

diff --git a/doc/developer/lists.rst b/doc/developer/lists.rst
index 86db788c0e..553bd1f596 100644
--- a/doc/developer/lists.rst
+++ b/doc/developer/lists.rst
@@ -108,6 +108,8 @@ Functions provided:
 | _first, _next, _next_safe,         | yes  | yes  | yes  | yes     | yes        |
 | _const_first, _const_next          |      |      |      |         |            |
 +------------------------------------+------+------+------+---------+------------+
+| _swap_all                          | yes  | yes  | yes  | yes     | yes        |
++------------------------------------+------+------+------+---------+------------+
 | _add_head, _add_tail, _add_after   | yes  | --   | --   | --      | --         |
 +------------------------------------+------+------+------+---------+------------+
 | _add                               | --   | yes  | yes  | yes     | yes        |
@@ -322,6 +324,14 @@ The following documentation assumes that a list has been defined using
       return ``item``.  The function may also call ``assert()`` (but most
       don't.)
 
+.. c:function:: itemtype *Z_swap_all(struct Z_head *, struct Z_head *)
+
+   Swap the contents of 2 containers (of identical type).  This exchanges the
+   contents of the two head structures and updates pointers if necessary for
+   the particular data structure.  Fast for all structures.
+
+   (Not currently available on atomic containers.)
+
 .. todo::
 
    ``Z_del_after()`` / ``Z_del_hint()``?
diff --git a/lib/typerb.h b/lib/typerb.h
index 60e6d09016..cbed8d4893 100644
--- a/lib/typerb.h
+++ b/lib/typerb.h
@@ -117,6 +117,7 @@ macro_inline type *prefix ## _pop(struct prefix##_head *h)                     \
 	typed_rb_remove(&h->rr, re);                                           \
 	return container_of(re, type, field.re);                               \
 }                                                                              \
+TYPESAFE_SWAP_ALL_SIMPLE(prefix)                                               \
 macro_pure const type *prefix ## _const_first(const struct prefix##_head *h)   \
 {                                                                              \
 	const struct typed_rb_entry *re;                                       \
diff --git a/lib/typesafe.h b/lib/typesafe.h
index 27e7be1286..ecac1a4381 100644
--- a/lib/typesafe.h
+++ b/lib/typesafe.h
@@ -78,6 +78,19 @@ macro_inline type *prefix ## _find_gteq(struct prefix##_head *h,               \
 }                                                                              \
 /* ... */
 
+/* SWAP_ALL_SIMPLE = for containers where the items don't point back to the
+ * head *AND* the head doesn'T points to itself (= everything except LIST,
+ * DLIST and SKIPLIST), just switch out the entire head
+ */
+#define TYPESAFE_SWAP_ALL_SIMPLE(prefix)                                       \
+macro_inline void prefix ## _swap_all(struct prefix##_head *a,                 \
+				      struct prefix##_head *b)                 \
+{                                                                              \
+	struct prefix##_head tmp = *a;                                         \
+	*a = *b;                                                               \
+	*b = tmp;                                                              \
+}                                                                              \
+/* ... */
 
 /* single-linked list, unsorted/arbitrary.
  * can be used as queue with add_tail / pop
@@ -169,6 +182,17 @@ macro_inline type *prefix ## _pop(struct prefix##_head *h)                     \
 		h->sh.last_next = &h->sh.first;                                \
 	return container_of(sitem, type, field.si);                            \
 }                                                                              \
+macro_inline void prefix ## _swap_all(struct prefix##_head *a,                 \
+				      struct prefix##_head *b)                 \
+{                                                                              \
+	struct prefix##_head tmp = *a;                                         \
+	*a = *b;                                                               \
+	*b = tmp;                                                              \
+	if (a->sh.last_next == &b->sh.first)                                   \
+		a->sh.last_next = &a->sh.first;                                \
+	if (b->sh.last_next == &a->sh.first)                                   \
+		b->sh.last_next = &b->sh.first;                                \
+}                                                                              \
 macro_pure const type *prefix ## _const_first(const struct prefix##_head *h)   \
 {                                                                              \
 	return container_of_null(h->sh.first, type, field.si);                 \
@@ -215,6 +239,34 @@ static inline void typesafe_dlist_add(struct dlist_head *head,
 	head->count++;
 }
 
+static inline void typesafe_dlist_swap_all(struct dlist_head *a,
+					   struct dlist_head *b)
+{
+	struct dlist_head tmp = *a;
+
+	a->count = b->count;
+	if (a->count) {
+		a->hitem.next = b->hitem.next;
+		a->hitem.prev = b->hitem.prev;
+		a->hitem.next->prev = &a->hitem;
+		a->hitem.prev->next = &a->hitem;
+	} else {
+		a->hitem.next = &a->hitem;
+		a->hitem.prev = &a->hitem;
+	}
+
+	b->count = tmp.count;
+	if (b->count) {
+		b->hitem.next = tmp.hitem.next;
+		b->hitem.prev = tmp.hitem.prev;
+		b->hitem.next->prev = &b->hitem;
+		b->hitem.prev->next = &b->hitem;
+	} else {
+		b->hitem.next = &b->hitem;
+		b->hitem.prev = &b->hitem;
+	}
+}
+
 /* double-linked list, for fast item deletion
  */
 #define PREDECL_DLIST(prefix)                                                  \
@@ -271,6 +323,11 @@ macro_inline type *prefix ## _pop(struct prefix##_head *h)                     \
 	h->dh.count--;                                                         \
 	return container_of(ditem, type, field.di);                            \
 }                                                                              \
+macro_inline void prefix ## _swap_all(struct prefix##_head *a,                 \
+				      struct prefix##_head *b)                 \
+{                                                                              \
+	typesafe_dlist_swap_all(&a->dh, &b->dh);                               \
+}                                                                              \
 macro_pure const type *prefix ## _const_first(const struct prefix##_head *h)   \
 {                                                                              \
 	const struct dlist_item *ditem = h->dh.hitem.next;                     \
@@ -380,6 +437,7 @@ macro_inline type *prefix ## _pop(struct prefix##_head *h)                     \
 		typesafe_heap_resize(&h->hh, false);                           \
 	return container_of(hitem, type, field.hi);                            \
 }                                                                              \
+TYPESAFE_SWAP_ALL_SIMPLE(prefix)                                               \
 macro_pure const type *prefix ## _const_first(const struct prefix##_head *h)   \
 {                                                                              \
 	if (h->hh.count == 0)                                                  \
@@ -518,6 +576,7 @@ macro_inline type *prefix ## _pop(struct prefix##_head *h)                     \
 	h->sh.first = sitem->next;                                             \
 	return container_of(sitem, type, field.si);                            \
 }                                                                              \
+TYPESAFE_SWAP_ALL_SIMPLE(prefix)                                               \
 macro_pure const type *prefix ## _const_first(const struct prefix##_head *h)   \
 {                                                                              \
 	return container_of_null(h->sh.first, type, field.si);                 \
@@ -708,6 +767,7 @@ macro_inline type *prefix ## _pop(struct prefix##_head *h)                     \
 		}                                                              \
 	return NULL;                                                           \
 }                                                                              \
+TYPESAFE_SWAP_ALL_SIMPLE(prefix)                                               \
 macro_pure const type *prefix ## _const_first(const struct prefix##_head *h)   \
 {                                                                              \
 	uint32_t i;                                                            \
@@ -824,6 +884,17 @@ macro_inline type *prefix ## _pop(struct prefix##_head *h)                     \
 	struct sskip_item *sitem = typesafe_skiplist_pop(&h->sh);              \
 	return container_of_null(sitem, type, field.si);                       \
 }                                                                              \
+macro_inline void prefix ## _swap_all(struct prefix##_head *a,                 \
+				      struct prefix##_head *b)                 \
+{                                                                              \
+	struct prefix##_head tmp = *a;                                         \
+	*a = *b;                                                               \
+	*b = tmp;                                                              \
+	a->sh.hitem.next[SKIPLIST_OVERFLOW] = (struct sskip_item *)            \
+		((uintptr_t)a->sh.overflow | 1);                               \
+	b->sh.hitem.next[SKIPLIST_OVERFLOW] = (struct sskip_item *)            \
+		((uintptr_t)b->sh.overflow | 1);                               \
+}                                                                              \
 macro_pure const type *prefix ## _const_first(const struct prefix##_head *h)   \
 {                                                                              \
 	const struct sskip_item *first = h->sh.hitem.next[0];                  \
diff --git a/tests/lib/test_typelist.h b/tests/lib/test_typelist.h
index 32331c14a0..379a2396b4 100644
--- a/tests/lib/test_typelist.h
+++ b/tests/lib/test_typelist.h
@@ -17,6 +17,7 @@
 /* C++ called, they want their templates back */
 #define item		concat(item_, TYPE)
 #define itm		concat(itm_, TYPE)
+#define itmswap		concat(itmswap_, TYPE)
 #define head		concat(head_, TYPE)
 #define list		concat(TYPE, )
 #define list_head	concat(TYPE, _head)
@@ -40,8 +41,9 @@
 #define list_find_gteq	concat(TYPE, _find_gteq)
 #define list_del	concat(TYPE, _del)
 #define list_pop	concat(TYPE, _pop)
+#define list_swap_all	concat(TYPE, _swap_all)
 
-#define ts_hash		concat(ts_hash_, TYPE)
+#define ts_hash_head	concat(ts_hash_head_, TYPE)
 
 #ifndef REALTYPE
 #define REALTYPE TYPE
@@ -89,10 +91,12 @@ DECLARE(REALTYPE, list, struct item, itm);
 #endif
 
 #define NITEM 10000
-struct item itm[NITEM];
+#define NITEM_SWAP 100 /* other container for swap */
+struct item itm[NITEM], itmswap[NITEM_SWAP];
 static struct list_head head = concat(INIT_, REALTYPE)(head);
 
-static void ts_hash(const char *text, const char *expect)
+static void ts_hash_head(struct list_head *h, const char *text,
+			 const char *expect)
 {
 	int64_t us = monotime_since(&ref, NULL);
 	SHA256_CTX ctx;
@@ -102,13 +106,13 @@ static void ts_hash(const char *text, const char *expect)
 	char hashtext[65];
 	uint32_t swap_count, count;
 
-	count = list_count(&head);
+	count = list_count(h);
 	swap_count = htonl(count);
 
 	SHA256_Init(&ctx);
 	SHA256_Update(&ctx, &swap_count, sizeof(swap_count));
 
-	frr_each (list, &head, item) {
+	frr_each (list, h, item) {
 		struct {
 			uint32_t val_upper, val_lower, index;
 		} hashitem = {
@@ -135,15 +139,20 @@ static void ts_hash(const char *text, const char *expect)
 }
 /* hashes will have different item ordering */
 #if IS_HASH(REALTYPE) || IS_HEAP(REALTYPE)
-#define ts_hashx(pos, csum) ts_hash(pos, NULL)
+#define ts_hash(pos, csum) ts_hash_head(&head, pos, NULL)
+#define ts_hashx(pos, csum) ts_hash_head(&head, pos, NULL)
+#define ts_hash_headx(head, pos, csum) ts_hash_head(head, pos, NULL)
 #else
-#define ts_hashx(pos, csum) ts_hash(pos, csum)
+#define ts_hash(pos, csum) ts_hash_head(&head, pos, csum)
+#define ts_hashx(pos, csum) ts_hash_head(&head, pos, csum)
+#define ts_hash_headx(head, pos, csum) ts_hash_head(head, pos, csum)
 #endif
 
 static void concat(test_, TYPE)(void)
 {
 	size_t i, j, k, l;
 	struct prng *prng;
+	struct prng *prng_swap __attribute__((unused));
 	struct item *item, *prev __attribute__((unused));
 	struct item dummy __attribute__((unused));
 
@@ -151,6 +160,10 @@ static void concat(test_, TYPE)(void)
 	for (i = 0; i < NITEM; i++)
 		itm[i].val = i;
 
+	memset(itmswap, 0, sizeof(itmswap));
+	for (i = 0; i < NITEM_SWAP; i++)
+		itmswap[i].val = i;
+
 	printfrr("%s start\n", str(TYPE));
 	ts_start();
 
@@ -178,6 +191,56 @@ static void concat(test_, TYPE)(void)
 	assert(list_first(&head) != NULL);
 	ts_hashx("fill", "a538546a6e6ab0484e925940aa8dd02fd934408bbaed8cb66a0721841584d838");
 
+#if !IS_ATOMIC(REALTYPE)
+	struct list_head other;
+
+	list_init(&other);
+	list_swap_all(&head, &other);
+
+	assert(list_count(&head) == 0);
+	assert(!list_first(&head));
+	assert(list_count(&other) == k);
+	assert(list_first(&other) != NULL);
+	ts_hash_headx(
+		&other, "swap1",
+		"a538546a6e6ab0484e925940aa8dd02fd934408bbaed8cb66a0721841584d838");
+
+	prng_swap = prng_new(0x1234dead);
+	l = 0;
+	for (i = 0; i < NITEM_SWAP; i++) {
+		j = prng_rand(prng_swap) % NITEM_SWAP;
+		if (itmswap[j].scratchpad == 0) {
+			list_add(&head, &itmswap[j]);
+			itmswap[j].scratchpad = 1;
+			l++;
+		}
+#if !IS_HEAP(REALTYPE)
+		else {
+			struct item *rv = list_add(&head, &itmswap[j]);
+			assert(rv == &itmswap[j]);
+		}
+#endif
+	}
+	assert(list_count(&head) == l);
+	assert(list_first(&head) != NULL);
+	ts_hash_headx(
+		&head, "swap-fill",
+		"26df437174051cf305d1bbb62d779ee450ca764167a1e7a94be1aece420008e6");
+
+	list_swap_all(&head, &other);
+
+	assert(list_count(&other) == l);
+	assert(list_first(&other));
+	ts_hash_headx(
+		&other, "swap2a",
+		"26df437174051cf305d1bbb62d779ee450ca764167a1e7a94be1aece420008e6");
+	assert(list_count(&head) == k);
+	assert(list_first(&head) != NULL);
+	ts_hash_headx(
+		&head, "swap2b",
+		"a538546a6e6ab0484e925940aa8dd02fd934408bbaed8cb66a0721841584d838");
+#endif /* !IS_ATOMIC */
+
 	k = 0;
 
 #if IS_ATOMIC(REALTYPE)
@@ -344,6 +407,50 @@ static void concat(test_, TYPE)(void)
 	assert(list_first(&head) != NULL);
 	ts_hash("fill / add_tail", "eabfcf1413936daaf20965abced95762f45110a6619b84aac7d38481bce4ea19");
 
+#if !IS_ATOMIC(REALTYPE)
+	struct list_head other;
+
+	list_init(&other);
+	list_swap_all(&head, &other);
+
+	assert(list_count(&head) == 0);
+	assert(!list_first(&head));
+	assert(list_count(&other) == k);
+	assert(list_first(&other) != NULL);
+	ts_hash_head(
+		&other, "swap1",
+		"eabfcf1413936daaf20965abced95762f45110a6619b84aac7d38481bce4ea19");
+
+	prng_swap = prng_new(0x1234dead);
+	l = 0;
+	for (i = 0; i < NITEM_SWAP; i++) {
+		j = prng_rand(prng_swap) % NITEM_SWAP;
+		if (itmswap[j].scratchpad == 0) {
+			list_add_tail(&head, &itmswap[j]);
+			itmswap[j].scratchpad = 1;
+			l++;
+		}
+	}
+	assert(list_count(&head) == l);
+	assert(list_first(&head) != NULL);
+	ts_hash_head(
+		&head, "swap-fill",
+		"833e6ae437e322dfbd36eda8cfc33a61109be735b43f15d256c05e52d1b01909");
+
+	list_swap_all(&head, &other);
+
+	assert(list_count(&other) == l);
+	assert(list_first(&other));
+	ts_hash_head(
+		&other, "swap2a",
+		"833e6ae437e322dfbd36eda8cfc33a61109be735b43f15d256c05e52d1b01909");
+	assert(list_count(&head) == k);
+	assert(list_first(&head) != NULL);
+	ts_hash_head(
+		&head, "swap2b",
+		"eabfcf1413936daaf20965abced95762f45110a6619b84aac7d38481bce4ea19");
+#endif
+
 	for (i = 0; i < NITEM / 2; i++) {
 		j = prng_rand(prng) % NITEM;
 		if (itm[j].scratchpad == 1) {
@@ -546,10 +653,14 @@ static void concat(test_, TYPE)(void)
 	printfrr("%s end\n", str(TYPE));
 }
 
+#undef ts_hash
 #undef ts_hashx
+#undef ts_hash_head
+#undef ts_hash_headx
 
 #undef item
 #undef itm
+#undef itmswap
 #undef head
 #undef list
 #undef list_head
@@ -571,6 +682,7 @@ static void concat(test_, TYPE)(void)
 #undef list_find_gteq
 #undef list_del
 #undef list_pop
+#undef list_swap_all
 
 #undef REALTYPE
 #undef TYPE