lib: Impelement the `*_del` list API.

The new list api did not implement the `*_del` endpoint as
it was described in the docs here:

http://docs.frrouting.org/projects/dev-guide/en/latest/lists.html#c.Z_del

This patch implements the endpoints to return the object deleted if
found, otherwise NULL for all but the atomic lists.

The atomic list `*_del` code is marked as TODO and will remain undefined
for now.

Signed-off-by: Stephen Worley <sworley@cumulusnetworks.com>

5 files changed, 46 insertions, 24 deletions

diff --git a/lib/atomlist.h b/lib/atomlist.h
index e4098ccb5..621db6824 100644
--- a/lib/atomlist.h
+++ b/lib/atomlist.h
@@ -135,8 +135,10 @@ macro_inline void prefix ## _add_tail(struct prefix##_head *h, type *item)     \
 macro_inline void prefix ## _del_hint(struct prefix##_head *h, type *item,     \
 		_Atomic atomptr_t *hint)                                       \
 {	atomlist_del_hint(&h->ah, &item->field.ai, hint); }                    \
-macro_inline void prefix ## _del(struct prefix##_head *h, type *item)          \
-{	atomlist_del_hint(&h->ah, &item->field.ai, NULL); }                    \
+macro_inline type *prefix ## _del(struct prefix##_head *h, type *item)         \
+{	atomlist_del_hint(&h->ah, &item->field.ai, NULL);                      \
+	/* TODO: Return NULL if not found */                                   \
+	return item; }                                                         \
 macro_inline type *prefix ## _pop(struct prefix##_head *h)                     \
 {	char *p = (char *)atomlist_pop(&h->ah);                                \
 	return p ? (type *)(p - offsetof(type, field)) : NULL; }               \
@@ -273,9 +275,11 @@ macro_inline void prefix ## _del_hint(struct prefix##_head *h, type *item,     \
 {                                                                              \
 	atomsort_del_hint(&h->ah, &item->field.ai, hint);                      \
 }                                                                              \
-macro_inline void prefix ## _del(struct prefix##_head *h, type *item)          \
+macro_inline type *prefix ## _del(struct prefix##_head *h, type *item)         \
 {                                                                              \
 	atomsort_del_hint(&h->ah, &item->field.ai, NULL);                      \
+	/* TODO: Return NULL if not found */                                   \
+	return item;                                                           \
 }                                                                              \
 macro_inline size_t prefix ## _count(struct prefix##_head *h)                  \
 {                                                                              \
diff --git a/lib/typerb.c b/lib/typerb.c
index 4c48d6434..3886fc678 100644
--- a/lib/typerb.c
+++ b/lib/typerb.c
@@ -333,9 +333,10 @@ color:
 	return (old);
 }
 
-void typed_rb_remove(struct rbt_tree *rbt, struct rb_entry *rbe)
+struct typed_rb_entry *typed_rb_remove(struct rbt_tree *rbt,
+				       struct rb_entry *rbe)
 {
-	rbe_remove(rbt, rbe);
+	return rbe_remove(rbt, rbe);
 }
 
 struct typed_rb_entry *typed_rb_insert(struct rbt_tree *rbt,
diff --git a/lib/typerb.h b/lib/typerb.h
index ce8446f85..4dc74afdc 100644
--- a/lib/typerb.h
+++ b/lib/typerb.h
@@ -43,7 +43,8 @@ struct typed_rb_entry *typed_rb_insert(struct typed_rb_root *,
 		int (*cmpfn)(
 			const struct typed_rb_entry *a,
 			const struct typed_rb_entry *b));
-void typed_rb_remove(struct typed_rb_root *, struct typed_rb_entry *rbe);
+struct typed_rb_entry *typed_rb_remove(struct typed_rb_root *,
+				       struct typed_rb_entry *rbe);
 struct typed_rb_entry *typed_rb_find(struct typed_rb_root *,
 		const struct typed_rb_entry *rbe,
 		int (*cmpfn)(
@@ -99,9 +100,11 @@ macro_inline type *prefix ## _find_lt(struct prefix##_head *h,                 \
 	re = typed_rb_find_lt(&h->rr, &item->field.re, cmpfn_nuq);             \
 	return container_of_null(re, type, field.re);                          \
 }                                                                              \
-macro_inline void prefix ## _del(struct prefix##_head *h, type *item)          \
+macro_inline type *prefix ## _del(struct prefix##_head *h, type *item)         \
 {                                                                              \
-	typed_rb_remove(&h->rr, &item->field.re);                              \
+	struct typed_rb_entry *re;                                             \
+	re = typed_rb_remove(&h->rr, &item->field.re);                         \
+	return container_of_null(re, type, field.re);                          \
 }                                                                              \
 macro_inline type *prefix ## _pop(struct prefix##_head *h)                     \
 {                                                                              \
diff --git a/lib/typesafe.c b/lib/typesafe.c
index f2ca67b7c..7e5939d5b 100644
--- a/lib/typesafe.c
+++ b/lib/typesafe.c
@@ -341,13 +341,14 @@ struct sskip_item *typesafe_skiplist_find_lt(struct sskip_head *head,
 	return best;
 }
 
-void typesafe_skiplist_del(struct sskip_head *head, struct sskip_item *item,
-		int (*cmpfn)(const struct sskip_item *a,
-				const struct sskip_item *b))
+struct sskip_item *typesafe_skiplist_del(
+	struct sskip_head *head, struct sskip_item *item,
+	int (*cmpfn)(const struct sskip_item *a, const struct sskip_item *b))
 {
 	size_t level = SKIPLIST_MAXDEPTH;
 	struct sskip_item *prev = &head->hitem, *next;
 	int cmpval;
+	bool found = false;
 
 	while (level) {
 		next = sl_level_get(prev, level - 1);
@@ -359,6 +360,7 @@ void typesafe_skiplist_del(struct sskip_head *head, struct sskip_item *item,
 			sl_level_set(prev, level - 1,
 				sl_level_get(item, level - 1));
 			level--;
+			found = true;
 			continue;
 		}
 		cmpval = cmpfn(next, item);
@@ -369,6 +371,9 @@ void typesafe_skiplist_del(struct sskip_head *head, struct sskip_item *item,
 		level--;
 	}
 
+	if (!found)
+		return NULL;
+
 	/* TBD: assert when trying to remove non-existing item? */
 	head->count--;
 
@@ -379,6 +384,8 @@ void typesafe_skiplist_del(struct sskip_head *head, struct sskip_item *item,
 		XFREE(MTYPE_SKIPLIST_OFLOW, oflow);
 	}
 	memset(item, 0, sizeof(*item));
+
+	return item;
 }
 
 struct sskip_item *typesafe_skiplist_pop(struct sskip_head *head)
diff --git a/lib/typesafe.h b/lib/typesafe.h
index ee244c78a..084606874 100644
--- a/lib/typesafe.h
+++ b/lib/typesafe.h
@@ -109,17 +109,18 @@ macro_inline void prefix ## _add_after(struct prefix##_head *h,                \
 	typesafe_list_add(&h->sh, nextp, &item->field.si);                     \
 }                                                                              \
 /* TODO: del_hint */                                                           \
-macro_inline void prefix ## _del(struct prefix##_head *h, type *item)          \
+macro_inline type *prefix ## _del(struct prefix##_head *h, type *item)         \
 {                                                                              \
 	struct slist_item **iter = &h->sh.first;                               \
 	while (*iter && *iter != &item->field.si)                              \
 		iter = &(*iter)->next;                                         \
 	if (!*iter)                                                            \
-		return;                                                        \
+		return NULL;                                                   \
 	h->sh.count--;                                                         \
 	*iter = item->field.si.next;                                           \
 	if (!item->field.si.next)                                              \
 		h->sh.last_next = iter;                                        \
+	return item;                                                           \
 }                                                                              \
 macro_inline type *prefix ## _pop(struct prefix##_head *h)                     \
 {                                                                              \
@@ -212,13 +213,14 @@ macro_inline void prefix ## _add_after(struct prefix##_head *h,                \
 	prev = after ? &after->field.di : &h->dh.hitem;                        \
 	typesafe_dlist_add(&h->dh, prev, &item->field.di);                     \
 }                                                                              \
-macro_inline void prefix ## _del(struct prefix##_head *h, type *item)          \
+macro_inline type *prefix ## _del(struct prefix##_head *h, type *item)         \
 {                                                                              \
 	struct dlist_item *ditem = &item->field.di;                            \
 	ditem->prev->next = ditem->next;                                       \
 	ditem->next->prev = ditem->prev;                                       \
 	h->dh.count--;                                                         \
 	ditem->prev = ditem->next = NULL;                                      \
+	return item;                                                           \
 }                                                                              \
 macro_inline type *prefix ## _pop(struct prefix##_head *h)                     \
 {                                                                              \
@@ -308,7 +310,7 @@ macro_inline type *prefix ## _add(struct prefix##_head *h, type *item)         \
 	h->hh.count++;                                                         \
 	return NULL;                                                           \
 }                                                                              \
-macro_inline void prefix ## _del(struct prefix##_head *h, type *item)          \
+macro_inline type *prefix ## _del(struct prefix##_head *h, type *item)         \
 {                                                                              \
 	struct heap_item *other;                                               \
 	uint32_t index = item->field.hi.index;                                 \
@@ -321,6 +323,7 @@ macro_inline void prefix ## _del(struct prefix##_head *h, type *item)          \
 		typesafe_heap_pushdown(&h->hh, index, other, prefix ## __cmp); \
 	if (HEAP_RESIZE_TRESH_DN(h))                                           \
 		typesafe_heap_resize(&h->hh, false);                           \
+	return item;                                                           \
 }                                                                              \
 macro_inline type *prefix ## _pop(struct prefix##_head *h)                     \
 {                                                                              \
@@ -449,15 +452,16 @@ macro_inline type *prefix ## _find_lt(struct prefix##_head *h,                 \
 	return container_of_null(prev, type, field.si);                        \
 }                                                                              \
 /* TODO: del_hint */                                                           \
-macro_inline void prefix ## _del(struct prefix##_head *h, type *item)          \
+macro_inline type *prefix ## _del(struct prefix##_head *h, type *item)         \
 {                                                                              \
 	struct ssort_item **iter = &h->sh.first;                               \
 	while (*iter && *iter != &item->field.si)                              \
 		iter = &(*iter)->next;                                         \
 	if (!*iter)                                                            \
-		return;                                                        \
+		return NULL;                                                   \
 	h->sh.count--;                                                         \
 	*iter = item->field.si.next;                                           \
+	return item;                                                           \
 }                                                                              \
 macro_inline type *prefix ## _pop(struct prefix##_head *h)                     \
 {                                                                              \
@@ -617,10 +621,10 @@ macro_inline type *prefix ## _find(struct prefix##_head *h, const type *item)  \
 	}                                                                      \
 	return NULL;                                                           \
 }                                                                              \
-macro_inline void prefix ## _del(struct prefix##_head *h, type *item)          \
+macro_inline type *prefix ## _del(struct prefix##_head *h, type *item)         \
 {                                                                              \
 	if (!h->hh.tabshift)                                                   \
-		return;                                                        \
+		return NULL;                                                   \
 	uint32_t hval = item->field.hi.hashval, hbits = HASH_KEY(h->hh, hval); \
 	struct thash_item **np = &h->hh.entries[hbits];                        \
 	while (*np && (*np)->hashval < hval)                                   \
@@ -628,12 +632,13 @@ macro_inline void prefix ## _del(struct prefix##_head *h, type *item)          \
 	while (*np && *np != &item->field.hi && (*np)->hashval == hval)        \
 		np = &(*np)->next;                                             \
 	if (*np != &item->field.hi)                                            \
-		return;                                                        \
+		return NULL;                                                   \
 	*np = item->field.hi.next;                                             \
 	item->field.hi.next = NULL;                                            \
 	h->hh.count--;                                                         \
 	if (HASH_SHRINK_THRESHOLD(h->hh))                                      \
 		typesafe_hash_shrink(&h->hh);                                  \
+	return item;                                                           \
 }                                                                              \
 macro_inline type *prefix ## _pop(struct prefix##_head *h)                     \
 {                                                                              \
@@ -751,9 +756,11 @@ macro_inline type *prefix ## _find_lt(struct prefix##_head *h,                 \
 			&item->field.si, cmpfn_nuq);                           \
 	return container_of_null(sitem, type, field.si);                       \
 }                                                                              \
-macro_inline void prefix ## _del(struct prefix##_head *h, type *item)          \
+macro_inline type *prefix ## _del(struct prefix##_head *h, type *item)         \
 {                                                                              \
-	typesafe_skiplist_del(&h->sh, &item->field.si, cmpfn_uq);              \
+	struct sskip_item *sitem = typesafe_skiplist_del(&h->sh,               \
+			&item->field.si, cmpfn_uq);                            \
+	return container_of_null(sitem, type, field.si);                       \
 }                                                                              \
 macro_inline type *prefix ## _pop(struct prefix##_head *h)                     \
 {                                                                              \
@@ -848,8 +855,8 @@ extern struct sskip_item *typesafe_skiplist_find_lt(struct sskip_head *head,
 		const struct sskip_item *item, int (*cmpfn)(
 			const struct sskip_item *a,
 			const struct sskip_item *b));
-extern void typesafe_skiplist_del(struct sskip_head *head,
-		struct sskip_item *item, int (*cmpfn)(
+extern struct sskip_item *typesafe_skiplist_del(
+		struct sskip_head *head, struct sskip_item *item, int (*cmpfn)(
 			const struct sskip_item *a,
 			const struct sskip_item *b));
 extern struct sskip_item *typesafe_skiplist_pop(struct sskip_head *head);