diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-28 09:53:30 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-28 09:53:30 +0000 |
commit | 2c7cac91ed6e7db0f6937923d2b57f97dbdbc337 (patch) | |
tree | c05dc0f8e6aa3accc84e3e5cffc933ed94941383 /lib/typesafe.c | |
parent | Initial commit. (diff) | |
download | frr-upstream/8.4.4.tar.xz frr-upstream/8.4.4.zip |
Adding upstream version 8.4.4.upstream/8.4.4upstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to '')
-rw-r--r-- | lib/typesafe.c | 611 |
1 files changed, 611 insertions, 0 deletions
diff --git a/lib/typesafe.c b/lib/typesafe.c new file mode 100644 index 0000000..3b65a2d --- /dev/null +++ b/lib/typesafe.c @@ -0,0 +1,611 @@ +/* + * Copyright (c) 2019 David Lamparter, for NetDEF, Inc. + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif + +#include <stdlib.h> +#include <string.h> +#include <assert.h> + +#include "typesafe.h" +#include "memory.h" +#include "network.h" + +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"); + +struct slist_item typesafe_slist_sentinel = { NULL }; + +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 != _SLIST_LAST) { + if (fromhead == item || fromnext == head->last_next) + return true; + + fromhead = fromhead->next; + if (!*fromnext || *fromnext == _SLIST_LAST) + 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) +{ + uint32_t i; + struct thash_item *item, *prev; + + for (i = 0; i < HASH_SIZE(*head); i++) { + item = head->entries[i]; + prev = NULL; + while (item) { + assert(HASH_KEY(*head, item->hashval) == i); + assert(!prev || item->hashval >= prev->hashval); + prev = item; + item = item->next; + } + } +} +#else +#define hash_consistency_check(x) +#endif + +void typesafe_hash_grow(struct thash_head *head) +{ + uint32_t newsize = head->count, i, j; + uint8_t newshift, delta; + + hash_consistency_check(head); + + newsize |= newsize >> 1; + newsize |= newsize >> 2; + newsize |= newsize >> 4; + newsize |= newsize >> 8; + newsize |= newsize >> 16; + newsize++; + newshift = __builtin_ctz(newsize) + 1; + + if (head->maxshift && newshift > head->maxshift) + newshift = head->maxshift; + if (newshift == head->tabshift) + return; + newsize = _HASH_SIZE(newshift); + + head->entries = XREALLOC(MTYPE_TYPEDHASH_BUCKET, head->entries, + sizeof(head->entries[0]) * newsize); + memset(head->entries + HASH_SIZE(*head), 0, + sizeof(head->entries[0]) * + (newsize - HASH_SIZE(*head))); + + delta = newshift - head->tabshift; + + i = HASH_SIZE(*head); + if (i == 0) + goto out; + do { + struct thash_item **apos, *item; + + i--; + apos = &head->entries[i]; + + for (j = 0; j < (1U << delta); j++) { + item = *apos; + *apos = NULL; + + head->entries[(i << delta) + j] = item; + apos = &head->entries[(i << delta) + j]; + + while ((item = *apos)) { + uint32_t midbits; + midbits = _HASH_KEY(newshift, item->hashval); + midbits &= (1 << delta) - 1; + if (midbits > j) + break; + apos = &item->next; + } + } + } while (i > 0); + +out: + head->tabshift = newshift; + hash_consistency_check(head); +} + +void typesafe_hash_shrink(struct thash_head *head) +{ + uint32_t newsize = head->count, i, j; + uint8_t newshift, delta; + + hash_consistency_check(head); + + if (!head->count) { + XFREE(MTYPE_TYPEDHASH_BUCKET, head->entries); + head->tabshift = 0; + return; + } + + newsize |= newsize >> 1; + newsize |= newsize >> 2; + newsize |= newsize >> 4; + newsize |= newsize >> 8; + newsize |= newsize >> 16; + newsize++; + newshift = __builtin_ctz(newsize) + 1; + + if (head->minshift && newshift < head->minshift) + newshift = head->minshift; + if (newshift == head->tabshift) + return; + newsize = _HASH_SIZE(newshift); + + delta = head->tabshift - newshift; + + for (i = 0; i < newsize; i++) { + struct thash_item **apos = &head->entries[i]; + + for (j = 0; j < (1U << delta); j++) { + *apos = head->entries[(i << delta) + j]; + while (*apos) + apos = &(*apos)->next; + } + } + head->entries = XREALLOC(MTYPE_TYPEDHASH_BUCKET, head->entries, + sizeof(head->entries[0]) * newsize); + head->tabshift = newshift; + + hash_consistency_check(head); +} + +/* skiplist */ + +static inline struct sskip_item *sl_level_get(const struct sskip_item *item, + size_t level) +{ + if (level < SKIPLIST_OVERFLOW) + return item->next[level]; + if (level == SKIPLIST_OVERFLOW && !((uintptr_t)item->next[level] & 1)) + return item->next[level]; + + uintptr_t ptrval = (uintptr_t)item->next[SKIPLIST_OVERFLOW]; + ptrval &= UINTPTR_MAX - 3; + struct sskip_overflow *oflow = (struct sskip_overflow *)ptrval; + return oflow->next[level - SKIPLIST_OVERFLOW]; +} + +static inline void sl_level_set(struct sskip_item *item, size_t level, + struct sskip_item *value) +{ + if (level < SKIPLIST_OVERFLOW) + item->next[level] = value; + else if (level == SKIPLIST_OVERFLOW && !((uintptr_t)item->next[level] & 1)) + item->next[level] = value; + else { + uintptr_t ptrval = (uintptr_t)item->next[SKIPLIST_OVERFLOW]; + ptrval &= UINTPTR_MAX - 3; + struct sskip_overflow *oflow = (struct sskip_overflow *)ptrval; + oflow->next[level - SKIPLIST_OVERFLOW] = value; + } +} + +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)) +{ + size_t level = SKIPLIST_MAXDEPTH, newlevel, auxlevel; + struct sskip_item *prev = &head->hitem, *next, *auxprev, *auxnext; + int cmpval; + + /* level / newlevel are 1-counted here */ + newlevel = __builtin_ctz(frr_weak_random()) + 1; + if (newlevel > SKIPLIST_MAXDEPTH) + newlevel = SKIPLIST_MAXDEPTH; + + next = NULL; + while (level >= newlevel) { + next = sl_level_get(prev, level - 1); + if (!next) { + level--; + continue; + } + cmpval = cmpfn(next, item); + if (cmpval < 0) { + prev = next; + continue; + } else if (cmpval == 0) { + return next; + } + level--; + } + + /* check for duplicate item - could be removed if code doesn't rely + * on it, but not really work the complication. */ + auxlevel = level; + auxprev = prev; + while (auxlevel) { + auxlevel--; + auxnext = sl_level_get(auxprev, auxlevel); + cmpval = 1; + while (auxnext && (cmpval = cmpfn(auxnext, item)) < 0) { + auxprev = auxnext; + auxnext = sl_level_get(auxprev, auxlevel); + } + if (cmpval == 0) + return auxnext; + }; + + head->count++; + memset(item, 0, sizeof(*item)); + if (newlevel > SKIPLIST_EMBED) { + struct sskip_overflow *oflow; + oflow = XMALLOC(MTYPE_SKIPLIST_OFLOW, sizeof(void *) + * (newlevel - SKIPLIST_OVERFLOW)); + item->next[SKIPLIST_OVERFLOW] = (struct sskip_item *) + ((uintptr_t)oflow | 1); + } + + sl_level_set(item, level, next); + sl_level_set(prev, level, item); + /* level is now 0-counted and < newlevel*/ + while (level) { + level--; + next = sl_level_get(prev, level); + while (next && cmpfn(next, item) < 0) { + prev = next; + next = sl_level_get(prev, level); + } + + sl_level_set(item, level, next); + sl_level_set(prev, level, item); + }; + return NULL; +} + +/* NOTE: level counting below is 1-based since that makes the code simpler! */ + +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)) +{ + size_t level = SKIPLIST_MAXDEPTH; + const struct sskip_item *prev = &head->hitem, *next; + int cmpval; + + while (level) { + next = sl_level_get(prev, level - 1); + if (!next) { + level--; + continue; + } + cmpval = cmpfn(next, item); + if (cmpval < 0) { + prev = next; + continue; + } + if (cmpval == 0) + return next; + level--; + } + return NULL; +} + +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)) +{ + size_t level = SKIPLIST_MAXDEPTH; + const struct sskip_item *prev = &head->hitem, *next; + int cmpval; + + while (level) { + next = sl_level_get(prev, level - 1); + if (!next) { + level--; + continue; + } + cmpval = cmpfn(next, item); + if (cmpval < 0) { + prev = next; + continue; + } + if (cmpval == 0) + return next; + level--; + } + return next; +} + +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)) +{ + size_t level = SKIPLIST_MAXDEPTH; + const struct sskip_item *prev = &head->hitem, *next, *best = NULL; + int cmpval; + + while (level) { + next = sl_level_get(prev, level - 1); + if (!next) { + level--; + continue; + } + cmpval = cmpfn(next, item); + if (cmpval < 0) { + best = prev = next; + continue; + } + level--; + } + return best; +} + +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); + if (!next) { + level--; + continue; + } + if (next == item) { + sl_level_set(prev, level - 1, + sl_level_get(item, level - 1)); + level--; + found = true; + continue; + } + cmpval = cmpfn(next, item); + if (cmpval < 0) { + prev = next; + continue; + } + level--; + } + + if (!found) + return NULL; + + /* TBD: assert when trying to remove non-existing item? */ + 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; +} + +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; +} + +/* heap */ + +#if 0 +static void heap_consistency_check(struct heap_head *head, + int (*cmpfn)(const struct heap_item *a, + const struct heap_item *b), + uint32_t pos) +{ + uint32_t rghtpos = pos + 1; + uint32_t downpos = HEAP_NARY * (pos + 1); + + if (pos + 1 > ~0U / HEAP_NARY) + downpos = ~0U; + + if ((pos & (HEAP_NARY - 1)) != HEAP_NARY - 1 && rghtpos < head->count) { + assert(cmpfn(head->array[rghtpos], head->array[pos]) >= 0); + heap_consistency_check(head, cmpfn, rghtpos); + } + if (downpos < head->count) { + assert(cmpfn(head->array[downpos], head->array[pos]) >= 0); + heap_consistency_check(head, cmpfn, downpos); + } +} +#else +#define heap_consistency_check(head, cmpfn, pos) +#endif + +void typesafe_heap_resize(struct heap_head *head, bool grow) +{ + uint32_t newsize; + + if (grow) { + newsize = head->arraysz; + if (newsize <= 36) + newsize = 72; + else if (newsize < 262144) + newsize += newsize / 2; + else if (newsize < 0xaaaa0000) + newsize += newsize / 3; + else + assert(!newsize); + } else if (head->count > 0) { + newsize = head->count; + } else { + XFREE(MTYPE_HEAP_ARRAY, head->array); + head->arraysz = 0; + return; + } + + newsize += HEAP_NARY - 1; + newsize &= ~(HEAP_NARY - 1); + if (newsize == head->arraysz) + return; + + head->array = XREALLOC(MTYPE_HEAP_ARRAY, head->array, + newsize * sizeof(struct heap_item *)); + head->arraysz = newsize; +} + +void typesafe_heap_pushdown(struct heap_head *head, uint32_t pos, + struct heap_item *item, + int (*cmpfn)(const struct heap_item *a, + const struct heap_item *b)) +{ + uint32_t rghtpos, downpos, moveto; + + while (1) { + /* rghtpos: neighbor to the "right", inside block of NARY. + * may be invalid if last in block, check nary_last() + * downpos: first neighbor in the "downwards" block further + * away from the root + */ + rghtpos = pos + 1; + + /* make sure we can use the full 4G items */ + downpos = HEAP_NARY * (pos + 1); + if (pos + 1 > ~0U / HEAP_NARY) + /* multiplication overflowed. ~0U is guaranteed + * to be an invalid index; size limit is enforced in + * resize() + */ + downpos = ~0U; + + /* only used on break */ + moveto = pos; + +#define nary_last(x) (((x) & (HEAP_NARY - 1)) == HEAP_NARY - 1) + if (downpos >= head->count + || cmpfn(head->array[downpos], item) >= 0) { + /* not moving down; either at end or down is >= item */ + if (nary_last(pos) || rghtpos >= head->count + || cmpfn(head->array[rghtpos], item) >= 0) + /* not moving right either - got our spot */ + break; + + moveto = rghtpos; + + /* else: downpos is valid and < item. choose between down + * or right (if the latter is an option) */ + } else if (nary_last(pos) || cmpfn(head->array[rghtpos], + head->array[downpos]) >= 0) + moveto = downpos; + else + moveto = rghtpos; +#undef nary_last + + head->array[pos] = head->array[moveto]; + head->array[pos]->index = pos; + pos = moveto; + } + + head->array[moveto] = item; + item->index = moveto; + + heap_consistency_check(head, cmpfn, 0); +} + +void typesafe_heap_pullup(struct heap_head *head, uint32_t pos, + struct heap_item *item, + int (*cmpfn)(const struct heap_item *a, + const struct heap_item *b)) +{ + uint32_t moveto; + + while (pos != 0) { + if ((pos & (HEAP_NARY - 1)) == 0) + moveto = pos / HEAP_NARY - 1; + else + moveto = pos - 1; + + if (cmpfn(head->array[moveto], item) <= 0) + break; + + head->array[pos] = head->array[moveto]; + head->array[pos]->index = pos; + + pos = moveto; + } + + head->array[pos] = item; + item->index = pos; + + heap_consistency_check(head, cmpfn, 0); +} |