diff options
| -rw-r--r-- | lib/typerb.c | 8 | ||||
| -rw-r--r-- | lib/typerb.h | 7 | ||||
| -rw-r--r-- | lib/typesafe.c | 38 | ||||
| -rw-r--r-- | lib/typesafe.h | 69 | ||||
| -rw-r--r-- | tests/lib/test_typelist.h | 57 |
5 files changed, 175 insertions, 4 deletions
diff --git a/lib/typerb.c b/lib/typerb.c index 151d91ce20..e1346df191 100644 --- a/lib/typerb.c +++ b/lib/typerb.c @@ -480,3 +480,11 @@ struct rb_entry *typed_rb_min(const struct rbt_tree *rbt) return parent; } + +bool typed_rb_member(const struct typed_rb_root *rbt, + const struct typed_rb_entry *rbe) +{ + while (rbe->rbt_parent) + rbe = rbe->rbt_parent; + return rbe == rbt->rbt_root; +} diff --git a/lib/typerb.h b/lib/typerb.h index cbed8d4893..d22d864aae 100644 --- a/lib/typerb.h +++ b/lib/typerb.h @@ -62,6 +62,8 @@ const struct typed_rb_entry *typed_rb_find_lt(const struct typed_rb_root *rbt, const struct typed_rb_entry *b)); struct typed_rb_entry *typed_rb_min(const struct typed_rb_root *rbt); struct typed_rb_entry *typed_rb_next(const struct typed_rb_entry *rbe); +bool typed_rb_member(const struct typed_rb_root *rbt, + const struct typed_rb_entry *rbe); #define _PREDECL_RBTREE(prefix) \ struct prefix ## _head { struct typed_rb_root rr; }; \ @@ -142,6 +144,11 @@ macro_pure size_t prefix ## _count(const struct prefix##_head *h) \ { \ return h->rr.count; \ } \ +macro_pure bool prefix ## _member(const struct prefix##_head *h, \ + const type *item) \ +{ \ + return typed_rb_member(&h->rr, &item->field.re); \ +} \ MACRO_REQUIRE_SEMICOLON() /* end */ #define PREDECL_RBTREE_UNIQ(prefix) \ diff --git a/lib/typesafe.c b/lib/typesafe.c index 76705fad0d..f886c5bdf6 100644 --- a/lib/typesafe.c +++ b/lib/typesafe.c @@ -29,6 +29,44 @@ DEFINE_MTYPE_STATIC(LIB, TYPEDHASH_BUCKET, "Typed-hash bucket"); DEFINE_MTYPE_STATIC(LIB, SKIPLIST_OFLOW, "Skiplist overflow"); DEFINE_MTYPE_STATIC(LIB, HEAP_ARRAY, "Typed-heap array"); +bool typesafe_list_member(const struct slist_head *head, + const struct slist_item *item) +{ + struct slist_item *fromhead = head->first; + struct slist_item **fromnext = (struct slist_item **)&item->next; + + while (fromhead) { + if (fromhead == item || fromnext == head->last_next) + return true; + + fromhead = fromhead->next; + if (!*fromnext) + break; + fromnext = &(*fromnext)->next; + } + + return false; +} + +bool typesafe_dlist_member(const struct dlist_head *head, + const struct dlist_item *item) +{ + const struct dlist_item *fromhead = head->hitem.next; + const struct dlist_item *fromitem = item->next; + + if (!item->prev || !item->next) + return false; + + while (fromhead != &head->hitem && fromitem != item) { + if (fromitem == &head->hitem || fromhead == item) + return true; + fromhead = fromhead->next; + fromitem = fromitem->next; + } + + return false; +} + #if 0 static void hash_consistency_check(struct thash_head *head) { diff --git a/lib/typesafe.h b/lib/typesafe.h index 6d6fcf282e..ecf7d10eb1 100644 --- a/lib/typesafe.h +++ b/lib/typesafe.h @@ -78,8 +78,34 @@ macro_inline type *prefix ## _find_gteq(struct prefix##_head *h, \ } \ /* ... */ +/* *_member via find - when there is no better membership check than find() */ +#define TYPESAFE_MEMBER_VIA_FIND(prefix, type) \ +macro_inline bool prefix ## _member(struct prefix##_head *h, \ + const type *item) \ +{ \ + return item == prefix ## _const_find(h, item); \ +} \ +/* ... */ + +/* *_member via find_gteq - same for non-unique containers */ +#define TYPESAFE_MEMBER_VIA_FIND_GTEQ(prefix, type, cmpfn) \ +macro_inline bool prefix ## _member(struct prefix##_head *h, \ + const type *item) \ +{ \ + const type *iter; \ + for (iter = prefix ## _const_find_gteq(h, item); iter; \ + iter = prefix ## _const_next(h, iter)) { \ + if (iter == item) \ + return true; \ + if (cmpfn(iter, item) > 0) \ + break; \ + } \ + return false; \ +} \ +/* ... */ + /* 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, + * head *AND* the head doesn't point to itself (= everything except LIST, * DLIST and SKIPLIST), just switch out the entire head */ #define TYPESAFE_SWAP_ALL_SIMPLE(prefix) \ @@ -116,6 +142,9 @@ static inline void typesafe_list_add(struct slist_head *head, head->count++; } +extern bool typesafe_list_member(const struct slist_head *head, + const struct slist_item *item); + /* use as: * * PREDECL_LIST(namelist); @@ -218,6 +247,11 @@ macro_pure size_t prefix ## _count(const struct prefix##_head *h) \ { \ return h->sh.count; \ } \ +macro_pure bool prefix ## _member(const struct prefix##_head *h, \ + const type *item) \ +{ \ + return typesafe_list_member(&h->sh, &item->field.si); \ +} \ MACRO_REQUIRE_SEMICOLON() /* end */ /* don't use these structs directly */ @@ -269,6 +303,9 @@ static inline void typesafe_dlist_swap_all(struct dlist_head *a, } } +extern bool typesafe_dlist_member(const struct dlist_head *head, + const struct dlist_item *item); + /* double-linked list, for fast item deletion */ #define PREDECL_DLIST(prefix) \ @@ -357,6 +394,11 @@ macro_pure size_t prefix ## _count(const struct prefix##_head *h) \ { \ return h->dh.count; \ } \ +macro_pure bool prefix ## _member(const struct prefix##_head *h, \ + const type *item) \ +{ \ + return typesafe_dlist_member(&h->dh, &item->field.di); \ +} \ MACRO_REQUIRE_SEMICOLON() /* end */ /* note: heap currently caps out at 4G items */ @@ -466,6 +508,14 @@ macro_pure size_t prefix ## _count(const struct prefix##_head *h) \ { \ return h->hh.count; \ } \ +macro_pure bool prefix ## _member(const struct prefix##_head *h, \ + const type *item) \ +{ \ + uint32_t idx = item->field.hi.index; \ + if (idx >= h->hh.count) \ + return false; \ + return h->hh.array[idx] == &item->field.hi; \ +} \ MACRO_REQUIRE_SEMICOLON() /* end */ extern void typesafe_heap_resize(struct heap_head *head, bool grow); @@ -622,6 +672,7 @@ macro_inline const type *prefix ## _const_find(const struct prefix##_head *h, \ return container_of(sitem, type, field.si); \ } \ TYPESAFE_FIND(prefix, type) \ +TYPESAFE_MEMBER_VIA_FIND(prefix, type) \ MACRO_REQUIRE_SEMICOLON() /* end */ #define DECLARE_SORTLIST_NONUNIQ(prefix, type, field, cmpfn) \ @@ -637,6 +688,7 @@ macro_inline int _ ## prefix ## _cmp(const type *a, const type *b) \ return 0; \ } \ _DECLARE_SORTLIST(prefix, type, field, cmpfn, _ ## prefix ## _cmp); \ +TYPESAFE_MEMBER_VIA_FIND_GTEQ(prefix, type, cmpfn) \ MACRO_REQUIRE_SEMICOLON() /* end */ @@ -803,6 +855,19 @@ macro_pure size_t prefix ## _count(const struct prefix##_head *h) \ { \ return h->hh.count; \ } \ +macro_pure bool prefix ## _member(const struct prefix##_head *h, \ + const type *item) \ +{ \ + uint32_t hval = item->field.hi.hashval, hbits = HASH_KEY(h->hh, hval); \ + const struct thash_item *hitem = h->hh.entries[hbits]; \ + while (hitem && hitem->hashval < hval) \ + hitem = hitem->next; \ + for (hitem = h->hh.entries[hbits]; hitem && hitem->hashval <= hval; \ + hitem = hitem->next) \ + if (hitem == &item->field.hi) \ + return true; \ + return false; \ +} \ MACRO_REQUIRE_SEMICOLON() /* end */ /* skiplist, sorted. @@ -941,6 +1006,7 @@ macro_inline const type *prefix ## _const_find(const struct prefix##_head *h, \ return container_of_null(sitem, type, field.si); \ } \ TYPESAFE_FIND(prefix, type) \ +TYPESAFE_MEMBER_VIA_FIND(prefix, type) \ \ _DECLARE_SKIPLIST(prefix, type, field, \ prefix ## __cmp, prefix ## __cmp); \ @@ -972,6 +1038,7 @@ macro_inline int prefix ## __cmp_uq(const struct sskip_item *a, \ \ _DECLARE_SKIPLIST(prefix, type, field, \ prefix ## __cmp, prefix ## __cmp_uq); \ +TYPESAFE_MEMBER_VIA_FIND_GTEQ(prefix, type, cmpfn) \ MACRO_REQUIRE_SEMICOLON() /* end */ diff --git a/tests/lib/test_typelist.h b/tests/lib/test_typelist.h index be37a9e6c9..a12a995bf6 100644 --- a/tests/lib/test_typelist.h +++ b/tests/lib/test_typelist.h @@ -39,6 +39,7 @@ #define list_find concat(TYPE, _find) #define list_find_lt concat(TYPE, _find_lt) #define list_find_gteq concat(TYPE, _find_gteq) +#define list_member concat(TYPE, _member) #define list_del concat(TYPE, _del) #define list_pop concat(TYPE, _pop) #define list_swap_all concat(TYPE, _swap_all) @@ -301,7 +302,7 @@ static void concat(test_, TYPE)(void) #elif IS_HEAP(REALTYPE) /* heap - partially sorted. */ prev = NULL; - l = k / 2; + l = k / 4; for (i = 0; i < l; i++) { item = list_pop(&head); if (prev) @@ -310,7 +311,24 @@ static void concat(test_, TYPE)(void) k--; prev = item; } - ts_hash("pop", NULL); + ts_hash("pop#1", NULL); + + for (i = 0; i < NITEM; i++) + assertf(list_member(&head, &itm[i]) == itm[i].scratchpad, + "%zu should:%d is:%d", i, itm[i].scratchpad, + list_member(&head, &itm[i])); + ts_hash("member", NULL); + + l = k / 2; + for (; i < l; i++) { + item = list_pop(&head); + if (prev) + assert(prev->val < item->val); + item->scratchpad = 0; + k--; + prev = item; + } + ts_hash("pop#2", NULL); #else /* !IS_UNIQ(REALTYPE) && !IS_HEAP(REALTYPE) */ for (i = 0; i < NITEM; i++) { @@ -387,6 +405,14 @@ static void concat(test_, TYPE)(void) assert(l + list_count(&head) == k); ts_hashx("del", "cb2e5d80f08a803ef7b56c15e981b681adcea214bebc2f55e12e0bfb242b07ca"); +#if !IS_ATOMIC(REALTYPE) + for (i = 0; i < NITEM; i++) + assertf(list_member(&head, &itm[i]) == itm[i].scratchpad, + "%zu should:%d is:%d", i, itm[i].scratchpad, + list_member(&head, &itm[i])); + ts_hashx("member", "cb2e5d80f08a803ef7b56c15e981b681adcea214bebc2f55e12e0bfb242b07ca"); +#endif + frr_each_safe(list, &head, item) { assert(item->scratchpad != 0); @@ -475,7 +501,31 @@ static void concat(test_, TYPE)(void) } ts_hash("del-prng", "86d568a95eb429dab3162976c5a5f3f75aabc835932cd682aa280b6923549564"); +#if !IS_ATOMIC(REALTYPE) + for (i = 0; i < NITEM; i++) + assertf(list_member(&head, &itm[i]) == itm[i].scratchpad, + "%zu should:%d is:%d", i, itm[i].scratchpad, + list_member(&head, &itm[i])); + ts_hash("member", "86d568a95eb429dab3162976c5a5f3f75aabc835932cd682aa280b6923549564"); +#endif + l = 0; + while (l < (k / 4) && (prev = list_pop(&head))) { + assert(prev->scratchpad != 0); + + prev->scratchpad = 0; + l++; + } + ts_hash("pop#1", "42b8950c880535b2d2e0c980f9845f7841ecf675c0fb9801aec4170d2036349d"); + +#if !IS_ATOMIC(REALTYPE) + for (i = 0; i < NITEM; i++) + assertf(list_member(&head, &itm[i]) == itm[i].scratchpad, + "%zu should:%d is:%d", i, itm[i].scratchpad, + list_member(&head, &itm[i])); + ts_hash("member", "42b8950c880535b2d2e0c980f9845f7841ecf675c0fb9801aec4170d2036349d"); +#endif + while ((item = list_pop(&head))) { assert(item->scratchpad != 0); @@ -485,7 +535,7 @@ static void concat(test_, TYPE)(void) assert(l == k); assert(list_count(&head) == 0); assert(list_first(&head) == NULL); - ts_hash("pop", "df3f619804a92fdb4057192dc43dd748ea778adc52bc498ce80524c014b81119"); + ts_hash("pop#2", "df3f619804a92fdb4057192dc43dd748ea778adc52bc498ce80524c014b81119"); prng_free(prng); prng = prng_new(0x1e5a2d69); @@ -695,6 +745,7 @@ static void concat(test_, TYPE)(void) #undef list_find #undef list_find_lt #undef list_find_gteq +#undef list_member #undef list_del #undef list_pop #undef list_swap_all |