| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| #ifdef HAVE_CONFIG_H |
| #include "config.h" |
| #endif |
| |
| #include <stdlib.h> |
| #include <string.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") |
| |
| #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); |
| } |
| |
| |
| |
| 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; |
| |
| |
| 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--; |
| } |
| |
| |
| |
| 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); |
| |
| 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; |
| } |
| |
| |
| |
| 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; |
| |
| |
| 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; |
| } |
| |
| |
| |
| #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 = pos + 1; |
| |
| |
| downpos = HEAP_NARY * (pos + 1); |
| if (pos + 1 > ~0U / HEAP_NARY) |
| |
| |
| |
| |
| downpos = ~0U; |
| |
| |
| moveto = pos; |
| |
| #define nary_last(x) (((x) & (HEAP_NARY - 1)) == HEAP_NARY - 1) |
| if (downpos >= head->count |
| || cmpfn(head->array[downpos], item) >= 0) { |
| |
| if (nary_last(pos) || rghtpos >= head->count |
| || cmpfn(head->array[rghtpos], item) >= 0) |
| |
| break; |
| |
| moveto = rghtpos; |
| |
| |
| |
| } 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); |
| } |