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>

diff --git a/lib/atomlist.h b/lib/atomlist.h
index e4098ccb54d12b2140e810efac7d7691142c4adb..621db6824f21a83418322feb1a24b88fa328922a 100644 (file)
--- 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 4c48d6434f411cdd8bf19381dadb542f9e2cf0ef..3886fc678e33850801b987a08874ca5e2bea5319 100644 (file)
--- 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 ce8446f853a901c503e5c09105ba2277aa3f1202..4dc74afdca781eba06463f2fa07dadacdf626407 100644 (file)
--- 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 f2ca67b7c66b690f5f10c0b66ae0d9cbfa595184..7e5939d5b3bb084e94e048c88a76805447ed7ff2 100644 (file)
--- 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 ee244c78aedae3624ac819cf2664a12dc7cff1fe..08460687437c009240bcd8dd224c7b02c2318541 100644 (file)
--- 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);