diff options
Diffstat (limited to 'lib/typesafe.h')
| -rw-r--r-- | lib/typesafe.h | 109 |
1 files changed, 100 insertions, 9 deletions
diff --git a/lib/typesafe.h b/lib/typesafe.h index ecac1a4381..44c42ffbca 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) \ @@ -106,6 +132,10 @@ struct slist_head { size_t count; }; +/* this replaces NULL as the value for ->next on the last item. */ +extern struct slist_item typesafe_slist_sentinel; +#define _SLIST_LAST &typesafe_slist_sentinel + static inline void typesafe_list_add(struct slist_head *head, struct slist_item **pos, struct slist_item *item) { @@ -116,6 +146,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); @@ -136,6 +169,7 @@ MACRO_REQUIRE_SEMICOLON() /* end */ macro_inline void prefix ## _init(struct prefix##_head *h) \ { \ memset(h, 0, sizeof(*h)); \ + h->sh.first = _SLIST_LAST; \ h->sh.last_next = &h->sh.first; \ } \ macro_inline void prefix ## _fini(struct prefix##_head *h) \ @@ -161,25 +195,27 @@ macro_inline void prefix ## _add_after(struct prefix##_head *h, \ macro_inline type *prefix ## _del(struct prefix##_head *h, type *item) \ { \ struct slist_item **iter = &h->sh.first; \ - while (*iter && *iter != &item->field.si) \ + while (*iter != _SLIST_LAST && *iter != &item->field.si) \ iter = &(*iter)->next; \ - if (!*iter) \ + if (*iter == _SLIST_LAST) \ return NULL; \ h->sh.count--; \ *iter = item->field.si.next; \ - if (!item->field.si.next) \ + if (item->field.si.next == _SLIST_LAST) \ h->sh.last_next = iter; \ + item->field.si.next = NULL; \ return item; \ } \ macro_inline type *prefix ## _pop(struct prefix##_head *h) \ { \ struct slist_item *sitem = h->sh.first; \ - if (!sitem) \ + if (sitem == _SLIST_LAST) \ return NULL; \ h->sh.count--; \ h->sh.first = sitem->next; \ - if (h->sh.first == NULL) \ + if (h->sh.first == _SLIST_LAST) \ h->sh.last_next = &h->sh.first; \ + sitem->next = NULL; \ return container_of(sitem, type, field.si); \ } \ macro_inline void prefix ## _swap_all(struct prefix##_head *a, \ @@ -195,13 +231,17 @@ macro_inline void prefix ## _swap_all(struct prefix##_head *a, \ } \ macro_pure const type *prefix ## _const_first(const struct prefix##_head *h) \ { \ - return container_of_null(h->sh.first, type, field.si); \ + if (h->sh.first != _SLIST_LAST) \ + return container_of(h->sh.first, type, field.si); \ + return NULL; \ } \ macro_pure const type *prefix ## _const_next(const struct prefix##_head *h, \ const type *item) \ { \ const struct slist_item *sitem = &item->field.si; \ - return container_of_null(sitem->next, type, field.si); \ + if (sitem->next != _SLIST_LAST) \ + return container_of(sitem->next, type, field.si); \ + return NULL; \ } \ TYPESAFE_FIRST_NEXT(prefix, type) \ macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item) \ @@ -210,12 +250,23 @@ macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item) \ if (!item) \ return NULL; \ sitem = &item->field.si; \ - return container_of_null(sitem->next, type, field.si); \ + if (sitem->next != _SLIST_LAST) \ + return container_of(sitem->next, type, field.si); \ + return NULL; \ } \ macro_pure size_t prefix ## _count(const struct prefix##_head *h) \ { \ return h->sh.count; \ } \ +macro_pure bool prefix ## _anywhere(const type *item) \ +{ \ + return item->field.si.next != NULL; \ +} \ +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 */ @@ -267,6 +318,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) \ @@ -321,6 +375,7 @@ macro_inline type *prefix ## _pop(struct prefix##_head *h) \ ditem->prev->next = ditem->next; \ ditem->next->prev = ditem->prev; \ h->dh.count--; \ + ditem->prev = ditem->next = NULL; \ return container_of(ditem, type, field.di); \ } \ macro_inline void prefix ## _swap_all(struct prefix##_head *a, \ @@ -354,6 +409,16 @@ macro_pure size_t prefix ## _count(const struct prefix##_head *h) \ { \ return h->dh.count; \ } \ +macro_pure bool prefix ## _anywhere(const type *item) \ +{ \ + const struct dlist_item *ditem = &item->field.di; \ + return ditem->next && ditem->prev; \ +} \ +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 */ @@ -463,6 +528,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); @@ -565,6 +638,7 @@ macro_inline type *prefix ## _del(struct prefix##_head *h, type *item) \ return NULL; \ h->sh.count--; \ *iter = item->field.si.next; \ + item->field.si.next = NULL; \ return item; \ } \ macro_inline type *prefix ## _pop(struct prefix##_head *h) \ @@ -618,6 +692,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) \ @@ -633,6 +708,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 */ @@ -799,6 +875,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. @@ -937,6 +1026,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); \ @@ -968,6 +1058,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 */ |