diff options
| author | David Lamparter <equinox@diac24.net> | 2019-05-12 12:05:14 +0200 |
|---|---|---|
| committer | David Lamparter <equinox@diac24.net> | 2019-05-21 05:18:16 +0200 |
| commit | 01734da376d0ed6ce355f27e4d19b5496f8ae94f (patch) | |
| tree | 2a72a8f261537e9a562cde365bcc1ac683010822 | |
| parent | a6002ca58481d6b724d932b2243f39bd740f6499 (diff) | |
lib: add dedicated pop() to DECLARE_SKIPLIST
The skiplist code was previously falling back to the del() code path for
a pop() on a skiplist. This is unneeded complexity, a pop() can be done
more efficiently.
Signed-off-by: David Lamparter <equinox@diac24.net>
| -rw-r--r-- | lib/typesafe.c | 32 | ||||
| -rw-r--r-- | lib/typesafe.h | 8 |
2 files changed, 35 insertions, 5 deletions
diff --git a/lib/typesafe.c b/lib/typesafe.c index bd269e9b54..4b07c482e8 100644 --- a/lib/typesafe.c +++ b/lib/typesafe.c @@ -375,3 +375,35 @@ void typesafe_skiplist_del(struct sskip_head *head, struct sskip_item *item, } memset(item, 0, sizeof(*item)); } + +struct sskip_item *typesafe_skiplist_pop(struct sskip_head *head) +{ + size_t level = SKIPLIST_MAXDEPTH; + struct sskip_item *prev = &head->hitem, *next, *item; + + item = sl_level_get(prev, 0); + if (!item) + return NULL; + + do { + level--; + + next = sl_level_get(prev, level); + if (next != item) + continue; + + sl_level_set(prev, level, sl_level_get(item, level)); + } while (level); + + head->count--; + + if ((uintptr_t)item->next[SKIPLIST_OVERFLOW] & 1) { + uintptr_t ptrval = (uintptr_t)item->next[SKIPLIST_OVERFLOW]; + ptrval &= UINTPTR_MAX - 3; + struct sskip_overflow *oflow = (struct sskip_overflow *)ptrval; + XFREE(MTYPE_SKIPLIST_OFLOW, oflow); + } + memset(item, 0, sizeof(*item)); + + return item; +} diff --git a/lib/typesafe.h b/lib/typesafe.h index 94002da599..c08a222091 100644 --- a/lib/typesafe.h +++ b/lib/typesafe.h @@ -538,11 +538,8 @@ macro_inline void prefix ## _del(struct prefix##_head *h, type *item) \ } \ macro_inline type *prefix ## _pop(struct prefix##_head *h) \ { \ - struct sskip_item *sitem = h->sh.hitem.next[0]; \ - if (!sitem) \ - return NULL; \ - typesafe_skiplist_del(&h->sh, sitem, cmpfn_uq); \ - return container_of(sitem, type, field.si); \ + 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) \ { \ @@ -636,6 +633,7 @@ extern void 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); /* this needs to stay at the end because both files include each other. * the resolved order is typesafe.h before typerb.h |