diff options
| author | David Lamparter <equinox@diac24.net> | 2020-05-04 21:36:03 +0200 |
|---|---|---|
| committer | David Lamparter <equinox@diac24.net> | 2020-05-04 22:13:28 +0200 |
| commit | daf3441d2bc7855a10886ec85ba0999be9e44e59 (patch) | |
| tree | 36e5b0ea841d9a44df549d6b4190581413f44828 /lib/typesafe.h | |
| parent | 15e9c561b2a10e90b1370e7a8d43d02ffde9e61a (diff) | |
lib: add const iteration & find to typesafe lists
Based on work originally by Mark Stapp <mjs@voltanet.io>.
Make it possible to iterate the typesafe lists in a const
context, as well as find items from them.
Signed-off-by: Mark Stapp <mjs@voltanet.io>
[above signoff was for the original version before modification]
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
Diffstat (limited to 'lib/typesafe.h')
| -rw-r--r-- | lib/typesafe.h | 144 |
1 files changed, 101 insertions, 43 deletions
diff --git a/lib/typesafe.h b/lib/typesafe.h index c30d73d1b3..e134316dd9 100644 --- a/lib/typesafe.h +++ b/lib/typesafe.h @@ -44,6 +44,41 @@ extern "C" { item; \ item = from, from = prefix##_next_safe(head, from)) + +/* non-const variants. these wrappers are the same for all the types, so + * bundle them together here. + */ +#define TYPESAFE_FIRST_NEXT(prefix, type) \ +macro_pure type *prefix ## _first(struct prefix##_head *h) \ +{ \ + return (type *)prefix ## _const_first(h); \ +} \ +macro_pure type *prefix ## _next(struct prefix##_head *h, type *item) \ +{ \ + return (type *)prefix ## _const_next(h, item); \ +} \ +/* ... */ +#define TYPESAFE_FIND(prefix, type) \ +macro_inline type *prefix ## _find(struct prefix##_head *h, \ + const type *item) \ +{ \ + return (type *)prefix ## _const_find(h, item); \ +} \ +/* ... */ +#define TYPESAFE_FIND_CMP(prefix, type) \ +macro_inline type *prefix ## _find_lt(struct prefix##_head *h, \ + const type *item) \ +{ \ + return (type *)prefix ## _const_find_lt(h, item); \ +} \ +macro_inline type *prefix ## _find_gteq(struct prefix##_head *h, \ + const type *item) \ +{ \ + return (type *)prefix ## _const_find_gteq(h, item); \ +} \ +/* ... */ + + /* single-linked list, unsorted/arbitrary. * can be used as queue with add_tail / pop */ @@ -133,15 +168,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_pure type *prefix ## _first(struct prefix##_head *h) \ +macro_pure const type *prefix ## _const_first(const struct prefix##_head *h) \ { \ return container_of_null(h->sh.first, type, field.si); \ } \ -macro_pure type *prefix ## _next(struct prefix##_head * h, type *item) \ +macro_pure const type *prefix ## _const_next(const struct prefix##_head *h, \ + const type *item) \ { \ - struct slist_item *sitem = &item->field.si; \ + const struct slist_item *sitem = &item->field.si; \ return container_of_null(sitem->next, type, field.si); \ } \ +TYPESAFE_FIRST_NEXT(prefix, type) \ macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item) \ { \ struct slist_item *sitem; \ @@ -232,20 +269,22 @@ macro_inline type *prefix ## _pop(struct prefix##_head *h) \ h->dh.count--; \ return container_of(ditem, type, field.di); \ } \ -macro_pure type *prefix ## _first(struct prefix##_head *h) \ +macro_pure const type *prefix ## _const_first(const struct prefix##_head *h) \ { \ - struct dlist_item *ditem = h->dh.hitem.next; \ + const struct dlist_item *ditem = h->dh.hitem.next; \ if (ditem == &h->dh.hitem) \ return NULL; \ return container_of(ditem, type, field.di); \ } \ -macro_pure type *prefix ## _next(struct prefix##_head * h, type *item) \ +macro_pure const type *prefix ## _const_next(const struct prefix##_head *h, \ + const type *item) \ { \ - struct dlist_item *ditem = &item->field.di; \ + const struct dlist_item *ditem = &item->field.di; \ if (ditem->next == &h->dh.hitem) \ return NULL; \ return container_of(ditem->next, type, field.di); \ } \ +TYPESAFE_FIRST_NEXT(prefix, type) \ macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item) \ { \ if (!item) \ @@ -338,19 +377,21 @@ macro_inline type *prefix ## _pop(struct prefix##_head *h) \ typesafe_heap_resize(&h->hh, false); \ return container_of(hitem, type, field.hi); \ } \ -macro_pure type *prefix ## _first(struct prefix##_head *h) \ +macro_pure const type *prefix ## _const_first(const struct prefix##_head *h) \ { \ if (h->hh.count == 0) \ return NULL; \ return container_of(h->hh.array[0], type, field.hi); \ } \ -macro_pure type *prefix ## _next(struct prefix##_head *h, type *item) \ +macro_pure const type *prefix ## _const_next(const struct prefix##_head *h, \ + const type *item) \ { \ uint32_t idx = item->field.hi.index + 1; \ if (idx >= h->hh.count) \ return NULL; \ return container_of(h->hh.array[idx], type, field.hi); \ } \ +TYPESAFE_FIRST_NEXT(prefix, type) \ macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item) \ { \ if (!item) \ @@ -431,26 +472,27 @@ macro_inline type *prefix ## _add(struct prefix##_head *h, type *item) \ h->sh.count++; \ return NULL; \ } \ -macro_inline type *prefix ## _find_gteq(struct prefix##_head *h, \ - const type *item) \ +macro_inline const type *prefix ## _const_find_gteq( \ + const struct prefix##_head *h, const type *item) \ { \ - struct ssort_item *sitem = h->sh.first; \ + const struct ssort_item *sitem = h->sh.first; \ int cmpval = 0; \ while (sitem && (cmpval = cmpfn_nuq( \ container_of(sitem, type, field.si), item)) < 0) \ sitem = sitem->next; \ return container_of_null(sitem, type, field.si); \ } \ -macro_inline type *prefix ## _find_lt(struct prefix##_head *h, \ - const type *item) \ +macro_inline const type *prefix ## _const_find_lt( \ + const struct prefix##_head *h, const type *item) \ { \ - struct ssort_item *prev = NULL, *sitem = h->sh.first; \ + const struct ssort_item *prev = NULL, *sitem = h->sh.first; \ int cmpval = 0; \ while (sitem && (cmpval = cmpfn_nuq( \ container_of(sitem, type, field.si), item)) < 0) \ sitem = (prev = sitem)->next; \ return container_of_null(prev, type, field.si); \ } \ +TYPESAFE_FIND_CMP(prefix, type) \ /* TODO: del_hint */ \ macro_inline type *prefix ## _del(struct prefix##_head *h, type *item) \ { \ @@ -472,15 +514,17 @@ macro_inline type *prefix ## _pop(struct prefix##_head *h) \ h->sh.first = sitem->next; \ return container_of(sitem, type, field.si); \ } \ -macro_pure type *prefix ## _first(struct prefix##_head *h) \ +macro_pure const type *prefix ## _const_first(const struct prefix##_head *h) \ { \ return container_of_null(h->sh.first, type, field.si); \ } \ -macro_pure type *prefix ## _next(struct prefix##_head *h, type *item) \ +macro_pure const type *prefix ## _const_next(const struct prefix##_head *h, \ + const type *item) \ { \ - struct ssort_item *sitem = &item->field.si; \ + const struct ssort_item *sitem = &item->field.si; \ return container_of_null(sitem->next, type, field.si); \ } \ +TYPESAFE_FIRST_NEXT(prefix, type) \ macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item) \ { \ struct ssort_item *sitem; \ @@ -497,10 +541,11 @@ macro_pure size_t prefix ## _count(const struct prefix##_head *h) \ #define DECLARE_SORTLIST_UNIQ(prefix, type, field, cmpfn) \ _DECLARE_SORTLIST(prefix, type, field, cmpfn, cmpfn) \ - \ -macro_inline type *prefix ## _find(struct prefix##_head *h, const type *item) \ + \ +macro_inline const type *prefix ## _const_find(const struct prefix##_head *h, \ + const type *item) \ { \ - struct ssort_item *sitem = h->sh.first; \ + const struct ssort_item *sitem = h->sh.first; \ int cmpval = 0; \ while (sitem && (cmpval = cmpfn( \ container_of(sitem, type, field.si), item)) < 0) \ @@ -509,6 +554,7 @@ macro_inline type *prefix ## _find(struct prefix##_head *h, const type *item) \ return NULL; \ return container_of(sitem, type, field.si); \ } \ +TYPESAFE_FIND(prefix, type) \ /* ... */ #define DECLARE_SORTLIST_NONUNIQ(prefix, type, field, cmpfn) \ @@ -606,12 +652,13 @@ macro_inline type *prefix ## _add(struct prefix##_head *h, type *item) \ *np = &item->field.hi; \ return NULL; \ } \ -macro_inline type *prefix ## _find(struct prefix##_head *h, const type *item) \ +macro_inline const type *prefix ## _const_find(const struct prefix##_head *h, \ + const type *item) \ { \ if (!h->hh.tabshift) \ return NULL; \ uint32_t hval = hashfn(item), hbits = HASH_KEY(h->hh, hval); \ - struct thash_item *hitem = h->hh.entries[hbits]; \ + const struct thash_item *hitem = h->hh.entries[hbits]; \ while (hitem && hitem->hashval < hval) \ hitem = hitem->next; \ while (hitem && hitem->hashval == hval) { \ @@ -621,6 +668,7 @@ macro_inline type *prefix ## _find(struct prefix##_head *h, const type *item) \ } \ return NULL; \ } \ +TYPESAFE_FIND(prefix, type) \ macro_inline type *prefix ## _del(struct prefix##_head *h, type *item) \ { \ if (!h->hh.tabshift) \ @@ -655,7 +703,7 @@ macro_inline type *prefix ## _pop(struct prefix##_head *h) \ } \ return NULL; \ } \ -macro_pure type *prefix ## _first(struct prefix##_head *h) \ +macro_pure const type *prefix ## _const_first(const struct prefix##_head *h) \ { \ uint32_t i; \ for (i = 0; i < HASH_SIZE(h->hh); i++) \ @@ -663,17 +711,19 @@ macro_pure type *prefix ## _first(struct prefix##_head *h) \ return container_of(h->hh.entries[i], type, field.hi); \ return NULL; \ } \ -macro_pure type *prefix ## _next(struct prefix##_head *h, type *item) \ +macro_pure const type *prefix ## _const_next(const struct prefix##_head *h, \ + const type *item) \ { \ - struct thash_item *hitem = &item->field.hi; \ + const struct thash_item *hitem = &item->field.hi; \ if (hitem->next) \ return container_of(hitem->next, type, field.hi); \ uint32_t i = HASH_KEY(h->hh, hitem->hashval) + 1; \ - for (; i < HASH_SIZE(h->hh); i++) \ + for (; i < HASH_SIZE(h->hh); i++) \ if (h->hh.entries[i]) \ return container_of(h->hh.entries[i], type, field.hi); \ return NULL; \ } \ +TYPESAFE_FIRST_NEXT(prefix, type) \ macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item) \ { \ if (!item) \ @@ -742,20 +792,21 @@ macro_inline type *prefix ## _add(struct prefix##_head *h, type *item) \ si = typesafe_skiplist_add(&h->sh, &item->field.si, cmpfn_uq); \ return container_of_null(si, type, field.si); \ } \ -macro_inline type *prefix ## _find_gteq(struct prefix##_head *h, \ - const type *item) \ +macro_inline const type *prefix ## _const_find_gteq( \ + const struct prefix##_head *h, const type *item) \ { \ - struct sskip_item *sitem = typesafe_skiplist_find_gteq(&h->sh, \ + const struct sskip_item *sitem = typesafe_skiplist_find_gteq(&h->sh, \ &item->field.si, cmpfn_nuq); \ return container_of_null(sitem, type, field.si); \ } \ -macro_inline type *prefix ## _find_lt(struct prefix##_head *h, \ - const type *item) \ +macro_inline const type *prefix ## _const_find_lt( \ + const struct prefix##_head *h, const type *item) \ { \ - struct sskip_item *sitem = typesafe_skiplist_find_lt(&h->sh, \ + const struct sskip_item *sitem = typesafe_skiplist_find_lt(&h->sh, \ &item->field.si, cmpfn_nuq); \ return container_of_null(sitem, type, field.si); \ } \ +TYPESAFE_FIND_CMP(prefix, type) \ macro_inline type *prefix ## _del(struct prefix##_head *h, type *item) \ { \ struct sskip_item *sitem = typesafe_skiplist_del(&h->sh, \ @@ -767,16 +818,18 @@ 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_pure type *prefix ## _first(struct prefix##_head *h) \ +macro_pure const type *prefix ## _const_first(const struct prefix##_head *h) \ { \ - struct sskip_item *first = h->sh.hitem.next[0]; \ + const struct sskip_item *first = h->sh.hitem.next[0]; \ return container_of_null(first, type, field.si); \ } \ -macro_pure type *prefix ## _next(struct prefix##_head *h, type *item) \ +macro_pure const type *prefix ## _const_next(const struct prefix##_head *h, \ + const type *item) \ { \ - struct sskip_item *next = item->field.si.next[0]; \ + const struct sskip_item *next = item->field.si.next[0]; \ return container_of_null(next, type, field.si); \ } \ +TYPESAFE_FIRST_NEXT(prefix, type) \ macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item) \ { \ struct sskip_item *next; \ @@ -792,19 +845,21 @@ macro_pure size_t prefix ## _count(const struct prefix##_head *h) \ #define PREDECL_SKIPLIST_UNIQ(prefix) \ _PREDECL_SKIPLIST(prefix) #define DECLARE_SKIPLIST_UNIQ(prefix, type, field, cmpfn) \ - \ + \ macro_inline int prefix ## __cmp(const struct sskip_item *a, \ const struct sskip_item *b) \ { \ return cmpfn(container_of(a, type, field.si), \ container_of(b, type, field.si)); \ } \ -macro_inline type *prefix ## _find(struct prefix##_head *h, const type *item) \ +macro_inline const type *prefix ## _const_find(const struct prefix##_head *h, \ + const type *item) \ { \ - struct sskip_item *sitem = typesafe_skiplist_find(&h->sh, \ + const struct sskip_item *sitem = typesafe_skiplist_find(&h->sh, \ &item->field.si, &prefix ## __cmp); \ return container_of_null(sitem, type, field.si); \ } \ +TYPESAFE_FIND(prefix, type) \ \ _DECLARE_SKIPLIST(prefix, type, field, \ prefix ## __cmp, prefix ## __cmp) \ @@ -843,15 +898,18 @@ extern struct sskip_item *typesafe_skiplist_add(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_find(struct sskip_head *head, +extern const struct sskip_item *typesafe_skiplist_find( + const struct sskip_head *head, const struct sskip_item *item, int (*cmpfn)( const struct sskip_item *a, const struct sskip_item *b)); -extern struct sskip_item *typesafe_skiplist_find_gteq(struct sskip_head *head, +extern const struct sskip_item *typesafe_skiplist_find_gteq( + const struct sskip_head *head, const struct sskip_item *item, int (*cmpfn)( const struct sskip_item *a, const struct sskip_item *b)); -extern struct sskip_item *typesafe_skiplist_find_lt(struct sskip_head *head, +extern const struct sskip_item *typesafe_skiplist_find_lt( + const struct sskip_head *head, const struct sskip_item *item, int (*cmpfn)( const struct sskip_item *a, const struct sskip_item *b)); |