/*- * Copyright (c) 2019 Taylor R. Campbell * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. */ #include "cradix.h" #ifdef _KERNEL #include #include #include #include #include #define assert KASSERT #else /* !_KERNEL */ #include #include #include #include #include #include #include #include #include /* XXX C11 */ #define atomic_load_consume(p) (*(p)) #define atomic_store_release(p,v) (*(p) = (v)) #define atomic_store_relaxed(p,v) (*(p) = (v)) #ifdef NDEBUG #define __diagused __unused #else #define __diagused #endif #define howmany(X,N) (((X) + ((N) - 1))/(N)) #define roundup(X,N) (howmany(X,N)*(N)) #define rounddown(X,N) (((X)/(N))*(N)) #endif /* _KERNEL */ #define arraycount(A) (sizeof(A)/sizeof(*(A))) #define ffsl ffs32 /* XXX */ #define flsl fls32 /* XXX */ #define CHUNK_SIZE CRADIX_CHUNK_SIZE #define CHUNK_MASK CRADIX_CHUNK_MASK #define MAX_FANOUT CRADIX_MAX_FANOUT #ifdef _LP64 __CTASSERT(sizeof(long) == 8); #define belongdec be64dec #else __CTASSERT(sizeof(long) == 4); #define belongdec be32dec #endif struct cradix_branch { cradix_bitmap_t bitmap; uint8_t i; /* key index */ uint8_t n; /* number of children allocated */ uintptr_t child[]; }; __CTASSERT(sizeof(struct cradix_branch) == sizeof(void *)); #ifdef _KERNEL static void * cradix_default_alloc(size_t size) { return kmem_alloc(size, KM_SLEEP); } static void cradix_default_free(void *ptr, size_t size) { return kmem_free(ptr, size); } static void cradix_default_recycle(void *ptr, size_t size) { return kmem_free(ptr, size); } #else static void * cradix_default_alloc(size_t size) { return malloc(size); } static void cradix_default_free(void *ptr, size_t size __unused) { return free(ptr); } static void cradix_default_recycle(void *ptr, size_t size __unused) { return free(ptr); } #endif static struct cradix_branch * cradix_branch_alloc(struct cradix *C, unsigned n) { size_t size = offsetof(struct cradix_branch, child[n]); struct cradix_branch *B; if (C->ops->alloc) B = (*C->ops->alloc)(C, size); else B = cradix_default_alloc(size); if (B == NULL) return NULL; B->n = n; return B; } static void cradix_branch_free(struct cradix *C, struct cradix_branch *B) { size_t size = offsetof(struct cradix_branch, child[B->n]); if (C->ops->free) (*C->ops->free)(C, B, size); else cradix_default_free(B, size); } static void cradix_branch_recycle(struct cradix *C, struct cradix_branch *B) { size_t size = offsetof(struct cradix_branch, child[B->n]); if (C->ops->recycle) (*C->ops->recycle)(C, B, size); else cradix_default_recycle(B, size); } void cradix_init(struct cradix *C, const struct cradix_ops *ops) { assert(ops->keylen <= CRADIX_MAX_KEYLEN); C->root = 0; C->ops = ops; } void cradix_destroy(struct cradix *C) { assert(C->root == 0); C->root = 2; /* poison */ C->ops = NULL; } static const void * cradix_key(const struct cradix *C, const struct cradix_node *N) { return (*C->ops->key)(C, N); } static unsigned key_chunk_long(unsigned long key, unsigned i) { const unsigned nbits = CHAR_BIT*sizeof(key); const unsigned nchunks = (nbits + CHUNK_SIZE - 1)/CHUNK_SIZE; const unsigned lastshift = nchunks*CHUNK_SIZE - nbits; uint64_t s; if (lastshift && i == nchunks - 1) s = key << lastshift; else s = key >> ((nchunks - 1 - i)*CHUNK_SIZE - lastshift); return (s & CHUNK_MASK); } static unsigned __noinline key_chunk_byte(const uint8_t *key, unsigned i, unsigned keylen) { unsigned bitpos, bytepos, shift, msb, lsb, x, chunk; /* * We assume a chunk fits in a byte, so that at most it * straddles two bytes and not more. */ __CTASSERT(CHUNK_SIZE <= CHAR_BIT); bitpos = i*CHUNK_SIZE; bytepos = bitpos/CHAR_BIT; shift = 2*CHAR_BIT - CHUNK_SIZE - bitpos%CHAR_BIT; msb = key[bytepos]; lsb = ((bytepos + 1 == keylen) ? 0 : key[bytepos + 1]); x = (msb << 8) | lsb; chunk = (CHUNK_MASK & (x >> shift)); return chunk; } static unsigned key_chunk(const uint8_t *key, unsigned i, unsigned keylen) { /* Fast path for aligned keys of up to unsigned long. */ if (__predict_true(((uintptr_t)key & (sizeof(long) - 1)) == 0) && __predict_true(keylen <= sizeof(long))) return key_chunk_long(belongdec(key), i); else return key_chunk_byte(key, i, keylen); } static cradix_bitmap_t map_chunk(cradix_bitmap_t bitmap, unsigned chunk) { return bitmap | ((cradix_bitmap_t)1 << chunk); } static cradix_bitmap_t unmap_chunk(cradix_bitmap_t bitmap, unsigned chunk) { return bitmap & ~((cradix_bitmap_t)1 << chunk); } static bool chunk_mapped(cradix_bitmap_t bitmap, unsigned chunk) { return bitmap & ((cradix_bitmap_t)1 << chunk); } static unsigned chunkpos(cradix_bitmap_t bitmap, unsigned chunk) { return popcountl(bitmap & ~(~(cradix_bitmap_t)0 << chunk)); } /* * compute_submask(byte, keylen) * * byte is the last 8-bit (or, CHAR_BIT-bit) unit of a keylen-unit * string, which ends in a partial chunk. Return a bit map with a * bit set for every chunk that matches that partial chunk. */ static cradix_bitmap_t partial_submask(uint8_t byte, unsigned keylen) { unsigned unconstrained, constrained, lo, hi; cradix_bitmap_t lomask, himask; /* * Example: | key ends after first 8-bit byte * 000000001111111122222222 (numbered bytes) * aaaaabbbbbcccccdddddeeee (lettered chunks) * ***^^ * ^ unconstrained * * constrained */ unconstrained = roundup(CHAR_BIT*keylen, CHUNK_SIZE) - CHAR_BIT*keylen; constrained = CHAR_BIT*keylen - rounddown(CHAR_BIT*keylen, CHUNK_SIZE); assert(unconstrained); assert(constrained); assert(constrained + unconstrained == CHUNK_SIZE); /* If our pattern is BBB??, set lo = BBB00 and hi = BBB11. */ lo = (byte & ~(~0u << constrained)) << unconstrained; hi = lo | ~(~0u << unconstrained); /* * Set lomask to a bit map that includes lo and everything * above it, and himask to a bit map that includes hi and * everything below it. */ lomask = ~(cradix_bitmap_t)0 << lo; himask = (hi + 1 == CHAR_BIT*sizeof(cradix_bitmap_t) ? ~(cradix_bitmap_t)0 : ~(~(cradix_bitmap_t)0 << (hi + 1))); /* Intersect lomask & himask. */ return lomask & himask; } /* Tagged child pointers */ static inline bool isbranch(uintptr_t child) { return (child & 1) == 1; } static inline bool __diagused isleaf(uintptr_t child) { return (child & 1) == 0; } static inline uintptr_t branch2child(struct cradix_branch *B) { assert((uintptr_t)B != 0); assert(((uintptr_t)B & 1) == 0); return (uintptr_t)B | 1; } static inline uintptr_t leaf2child(struct cradix_node *N) { assert((uintptr_t)N != 0); assert(((uintptr_t)N & 1) == 0); return (uintptr_t)N; } static inline struct cradix_branch * child2branch(uintptr_t child) { struct cradix_branch *B; assert((child & 1) == 1); B = (struct cradix_branch *)(child - 1); assert(B != NULL); return B; } static inline struct cradix_node * child2leaf(uintptr_t child) { struct cradix_node *N; assert((child & 1) == 0); N = (struct cradix_node *)child; assert(N != NULL); return N; } /* Lookup */ bool cradix_empty(const struct cradix *C) { return C->root == 0; } struct cradix_node * cradix_lookup(const struct cradix *C, const void *key) { const unsigned keylen = C->ops->keylen; uintptr_t child; const struct cradix_branch *B; unsigned chunk, pos; struct cradix_node *N0; const void *key0; /* Load the root. If there's nothing there, fail. */ if ((child = atomic_load_consume(&C->root)) == 0) return NULL; /* Find the best candidate match. */ for (; isbranch(child); child = atomic_load_consume(&B->child[pos])) { B = child2branch(child); chunk = key_chunk(key, B->i, keylen); if (!chunk_mapped(B->bitmap, chunk)) return NULL; pos = chunkpos(B->bitmap, chunk); } /* Ignore tombstones. */ if (child == 0) return NULL; /* Verify whether it matches. */ assert(isleaf(child)); N0 = child2leaf(child); key0 = cradix_key(C, N0); if (memcmp(key0, key, keylen) != 0) return NULL; return N0; } static uintptr_t first_child(const struct cradix_branch *B) { uintptr_t child; unsigned pos, npos __diagused = popcountl(B->bitmap); for (pos = 0; pos < B->n; pos++) { assert(pos < npos); if ((child = atomic_load_consume(&B->child[pos])) != 0) return child; } assert(!"childless cradix branch"); return -1; } static uintptr_t last_child(const struct cradix_branch *B) { uintptr_t child; unsigned pos, npos = popcountl(B->bitmap); for (pos = npos; pos --> 0;) { if ((child = atomic_load_consume(&B->child[pos])) != 0) return child; } assert(!"childless cradix branch"); return -1; } static uintptr_t first_child_submap(const struct cradix_branch *B, cradix_bitmap_t bitmap, unsigned *chunkp) { uintptr_t child; unsigned chunk, pos; assert(bitmap); do { chunk = ffsl(bitmap) - 1; pos = chunkpos(B->bitmap, chunk); if ((child = atomic_load_consume(&B->child[pos])) != 0) { if (chunkp) *chunkp = chunk; return child; } } while ((bitmap = unmap_chunk(bitmap, chunk)) != 0); /* All the child pointers matching this bitmap are tombstones. */ return 0; } static uintptr_t last_child_submap(const struct cradix_branch *B, cradix_bitmap_t bitmap, unsigned *chunkp) { uintptr_t child; unsigned chunk, pos; assert(bitmap); do { chunk = flsl(bitmap) - 1; pos = chunkpos(B->bitmap, chunk); if ((child = atomic_load_consume(&B->child[pos])) != 0) { if (chunkp) *chunkp = chunk; return child; } } while ((bitmap = unmap_chunk(bitmap, chunk)) != 0); /* All the child pointers matching this bitmap are tombstones. */ return 0; } /* Min/max */ struct cradix_node * cradix_min(const struct cradix *C) { struct cradix_branch *B; uintptr_t child; /* Load the root. If there's nothing there, fail. */ if ((child = atomic_load_consume(&C->root)) == 0) return NULL; /* Find the first leaf. */ while (isbranch(child)) { B = child2branch(child); child = first_child(B); assert(child); } assert(isleaf(child)); return child2leaf(child); } struct cradix_node * cradix_max(const struct cradix *C) { struct cradix_branch *B; uintptr_t child; /* Load the root. If there's nothing there, fail. */ if ((child = atomic_load_consume(&C->root)) == 0) return NULL; /* Find the last leaf. */ while (isbranch(child)) { B = child2branch(child); child = last_child(B); assert(child); } assert(isleaf(child)); return child2leaf(child); } static struct cradix_node * cradix_extreme_prefix(const struct cradix *C, const void *prefix, size_t prefixlen, bool forward) { const unsigned keylen = C->ops->keylen; const struct cradix_branch *B; uintptr_t child; struct cradix_node *N; const void *key; unsigned chunk, pos, submask = ~0u; cradix_bitmap_t bitmap; assert(prefixlen <= keylen); /* If the tree is empty, not there. */ if ((child = atomic_load_consume(&C->root)) == 0) return NULL; /* Find the first candidate match. */ while (isbranch(child)) { B = child2branch(child); /* Check how this branch position sits in our prefix. */ if (CHUNK_SIZE*(B->i + 1) <= CHAR_BIT*prefixlen) { /* Fits fully in our prefix. Keep searching. */ chunk = key_chunk(prefix, B->i, prefixlen); if (!chunk_mapped(B->bitmap, chunk)) return NULL; pos = chunkpos(B->bitmap, chunk); if ((child = atomic_load_consume(&B->child[pos])) == 0) return NULL; } else if (CHAR_BIT*prefixlen <= CHUNK_SIZE*B->i) { /* Prefix has ended. Just go left/rightmost. */ child = (forward ? first_child(B) : last_child(B)); assert(child); } else { /* * Our prefix covers only part of the chunk * this branch discriminates on. Compute the * mask narrowing the bitmap to the children * matching our partial chunk, and go to the * extreme child of those. */ const uint8_t *const k = prefix; submask = partial_submask(k[prefixlen - 1], prefixlen); bitmap = B->bitmap & submask; if (bitmap == 0) return NULL; if (forward) child = first_child_submap(B, bitmap, NULL); else child = last_child_submap(B, bitmap, NULL); if (child == 0) return NULL; } } /* Verify whether it matches. */ assert(isleaf(child)); N = child2leaf(child); key = cradix_key(C, N); if (memcmp(prefix, key, prefixlen) != 0) return NULL; return N; } struct cradix_node * cradix_min_prefix(const struct cradix *C, const void *prefix, size_t prefixlen) { return cradix_extreme_prefix(C, prefix, prefixlen, true); } struct cradix_node * cradix_max_prefix(const struct cradix *C, const void *prefix, size_t prefixlen) { return cradix_extreme_prefix(C, prefix, prefixlen, false); } bool cradix_insert_begin(struct cradix *C, struct cradix_insert *I) { unsigned i; /* Preallocate one of each branch size we might need. */ for (i = 0; i < arraycount(I->alloc); i++) { unsigned n = 1u << (i + 1); if ((I->alloc[i] = cradix_branch_alloc(C, n)) == NULL) goto fail; } /* Initialize I->recycle to NULL. */ I->recycle = NULL; return true; fail: while (i --> 0) { cradix_branch_free(C, I->alloc[i]); I->alloc[i] = NULL; /* paranoia */ } return false; } void cradix_insert_end(struct cradix *C, struct cradix_insert *I) { unsigned i; /* Free all the preallocated branches we didn't use. */ for (i = 0; i < arraycount(I->alloc); i++) { if (I->alloc[i]) cradix_branch_free(C, I->alloc[i]); I->alloc[i] = NULL; /* paranoia */ } /* If we have a node to recycle, schedule it for recycling. */ if (I->recycle) { cradix_branch_recycle(C, I->recycle); I->recycle = NULL; /* paranoia */ } } static struct cradix_branch * new_branch(struct cradix *C, struct cradix_insert *I) { struct cradix_branch *B0; /* Allocate a 2-child branch. */ if (I) { B0 = I->alloc[0]; assert(B0 != NULL); assert(B0->n >= 2); I->alloc[0] = NULL; } else { if ((B0 = cradix_branch_alloc(C, 2)) == NULL) return NULL; } return B0; } static struct cradix_branch * grow_branch(struct cradix *C, struct cradix_insert *I, struct cradix_branch *B, unsigned new_chunk, uintptr_t new_child) { struct cradix_branch *B0; cradix_bitmap_t bitmap, bitmap0; unsigned n0, chunk; /* Count the nondeleted children and assemble a bitmap of them. */ n0 = 0; bitmap0 = 0; bitmap = B->bitmap; while (bitmap) { chunk = ffsl(bitmap) - 1; assert(chunk != new_chunk); bitmap = unmap_chunk(bitmap, chunk); if (B->child[chunkpos(B->bitmap, chunk)] == 0) continue; n0++; bitmap0 = map_chunk(bitmap0, chunk); } assert(1 < n0); assert(n0 < CRADIX_MAX_FANOUT); assert(n0 <= B->n); /* Count the new child and enter it into the bitmap. */ n0++; bitmap0 = map_chunk(bitmap0, new_chunk); /* Allocate a branch -- possibly smaller than before! */ if (I) { unsigned i = ilog2(n0 - 1); B0 = I->alloc[i]; assert(B0 != NULL); assert(B0->n >= n0); I->alloc[i] = NULL; } else { if ((B0 = cradix_branch_alloc(C, n0)) == NULL) return NULL; } B0->bitmap = bitmap0; B0->i = B->i; /* Copy over the existing nondeleted chunks. */ bitmap = B->bitmap; while (bitmap) { chunk = ffsl(bitmap) - 1; assert(chunk != new_chunk); bitmap = unmap_chunk(bitmap, chunk); if (B->child[chunkpos(B->bitmap, chunk)] == 0) continue; B0->child[chunkpos(B0->bitmap, chunk)] = B->child[chunkpos(B->bitmap, chunk)]; } /* Copy over the new chunk. */ B0->child[chunkpos(B0->bitmap, new_chunk)] = new_child; /* Recycle the old branch. */ if (I) I->recycle = B; else cradix_branch_recycle(C, B); return B0; } /* * Pick a leaf -- any leaf -- in the subtree rooted at B. */ static uintptr_t pick_leaf(struct cradix_branch *B) { cradix_bitmap_t bitmap; unsigned chunk; uintptr_t child, candidate = 0; /* * Search breadth-first to try everything we can in the cache * first. No need for a queue because if we descend far enough * we'll eventually hit a leaf. * * Conceivably we could store some metadata to reduce the time * for this search, e.g. the maximum depth of a subtree, but * it's not clear that maintaining the metadata is worth it. */ for (;;) { bitmap = B->bitmap; while (bitmap) { chunk = ffsl(bitmap) - 1; bitmap = unmap_chunk(bitmap, chunk); child = B->child[chunkpos(B->bitmap, chunk)]; if (child == 0) { /* * If we found a tombstone, there must * be other child pointers that are not * tombstones; we don't leave branches * with fewer than two live children. */ assert(bitmap); continue; } if (isleaf(child)) return child; candidate = child; } assert(candidate); assert(isbranch(candidate)); B = child2branch(candidate); } } struct cradix_node * cradix_insert(struct cradix *C, struct cradix_node *N, struct cradix_insert *I) { const unsigned keylen = C->ops->keylen; const void *key0, *key = cradix_key(C, N); uintptr_t child, *childp; struct cradix_branch *B, *B0; unsigned chunk0, chunk, pos, i; struct cradix_node *N0; /* If the tree is empty, insert it at the root. */ if (C->root == 0) { atomic_store_release(&C->root, leaf2child(N)); return N; } /* Find the first candidate match. */ for (child = C->root; isbranch(child); child = B->child[pos]) { B = child2branch(child); chunk = key_chunk(key, B->i, keylen); if (!chunk_mapped(B->bitmap, chunk)) { child = 0; break; } pos = chunkpos(B->bitmap, chunk); } /* * If we hit a dead end, find any other node in the subtree as * a candidate -- we know all nodes in this subtree agree on * the all chunks up to the one we stopped at, so we just need * any one of them to see whether we disagree earlier. */ if (child == 0) child = pick_leaf(B); assert(child != 0); /* Get the candidate node and key. */ assert(isleaf(child)); N0 = child2leaf(child); key0 = cradix_key(C, N0); /* Find the index of the first mismatching chunk. */ #if 1 for (i = 0; i < howmany(CHAR_BIT*keylen, CHUNK_SIZE); i++) { if (key_chunk(key0, i, keylen) != key_chunk(key, i, keylen)) goto branch; } #else /* * Search bytewise first and then convert byte position to * chunk position. Despite the complexity of key_chunk, it's * not clear this is a performance advantage. */ for (i = 0; i < keylen; i++) { const uint8_t *k = key; const uint8_t *k0 = key0; if (k[i] != k0[i]) { unsigned bitpos = i * CHAR_BIT; unsigned chunkpos = bitpos / CHUNK_SIZE; unsigned shift = bitpos % CHUNK_SIZE; if ((k[i] & ~(~0u << (CHUNK_SIZE - shift))) == (k0[i] & ~(~0u << (CHUNK_SIZE - shift)))) { assert((k[i] >> (CHUNK_SIZE - shift)) != (k0[i] >> (CHUNK_SIZE - shift))); chunkpos++; } i = chunkpos; goto branch; } } #endif return N0; /* collision */ branch: /* Find where to insert a new branch and insert it. */ for (childp = &C->root; isbranch(*childp); childp = &B->child[pos]) { B = child2branch(*childp); if (i < B->i) /* * We disagree with the subtree before the * branch, so we need to splice a new branch * above it. */ break; chunk = key_chunk(key, B->i, keylen); if (i == B->i) /* * We disagree with the subtree at the branch, * so we need to grow a new leaf on it. */ goto leaf; assert(chunk_mapped(B->bitmap, chunk)); pos = chunkpos(B->bitmap, chunk); } /* * Can't be a tombstone -- otherwise we would have decided to * grow a new leaf in this place. */ assert(*childp != 0); /* Splice a new branch at *childp. */ chunk = key_chunk(key, i, keylen); chunk0 = key_chunk(key0, i, keylen); if ((B0 = new_branch(C, I)) == NULL) return NULL; B0->i = i; B0->bitmap = 0; B0->bitmap = map_chunk(B0->bitmap, chunk); B0->bitmap = map_chunk(B0->bitmap, chunk0); B0->child[chunkpos(B0->bitmap, chunk)] = leaf2child(N); B0->child[chunkpos(B0->bitmap, chunk0)] = *childp; atomic_store_release(childp, branch2child(B0)); return N; leaf: /* * Grow a new leaf under this branch. If the branch already * has space for it filled with a tombstone, use that space; * otherwise grow a larger branch. */ if (chunk_mapped(B->bitmap, chunk)) { pos = chunkpos(B->bitmap, chunk); assert(B->child[pos] == 0); atomic_store_release(&B->child[pos], leaf2child(N)); } else { if ((B0 = grow_branch(C, I, B, chunk, leaf2child(N))) == NULL) return NULL; atomic_store_release(childp, branch2child(B0)); } return N; } void cradix_delete_begin(struct cradix *C __unused, struct cradix_delete *D) { D->recycle = NULL; } void cradix_delete_end(struct cradix *C, struct cradix_delete *D) { if (D->recycle) { cradix_branch_recycle(C, D->recycle); D->recycle = NULL; /* paranoia */ } } void cradix_delete(struct cradix *C, struct cradix_node *N, struct cradix_delete *D) { const void *key; struct cradix_node *N0; key = cradix_key(C, N); N0 = cradix_delete_key(C, key, D); assert(N0 == N); } static void prune_branch(struct cradix *C, struct cradix_delete *D, struct cradix_branch *B, unsigned del_chunk, uintptr_t *nodep) { cradix_bitmap_t bitmap, bitmap0; unsigned n0, chunk; assert(*nodep == branch2child(B)); assert(chunk_mapped(B->bitmap, del_chunk)); assert(B->child[chunkpos(B->bitmap, del_chunk)] != 0); /* Count the nondeleted children. */ n0 = 0; bitmap = B->bitmap; bitmap0 = 0; while (bitmap) { chunk = ffsl(bitmap) - 1; bitmap = unmap_chunk(bitmap, chunk); if (B->child[chunkpos(B->bitmap, chunk)] == 0) continue; bitmap0 = map_chunk(bitmap0, chunk); n0++; } assert(1 < n0); assert(n0 <= CRADIX_MAX_FANOUT); /* Check whether what's left is the last one. */ if (n0 == 2) { /* It's the last one -- splice and recycle the branch. */ bitmap0 = unmap_chunk(bitmap0, del_chunk); chunk = ffsl(bitmap0) - 1; atomic_store_relaxed(nodep, B->child[chunkpos(B->bitmap, chunk)]); if (D) D->recycle = B; else cradix_branch_recycle(C, B); } else { /* There are siblings remaining. Just leave a tombstone. */ atomic_store_relaxed(&B->child[chunkpos(B->bitmap, del_chunk)], 0); } } struct cradix_node * cradix_delete_key(struct cradix *C, const void *key, struct cradix_delete *D) { const unsigned keylen = C->ops->keylen; struct cradix_branch *B = NULL /*XXXGCC*/; struct cradix_node *N0; uintptr_t *parentp, *childp; const void *key0; unsigned chunk = -1 /*XXXGCC*/, pos = -1 /*XXXGCC*/; /* If there's nothing at the root, fail. */ if (C->root == 0) return NULL; /* Find the position of the best candidate match. */ for (parentp = NULL, childp = &C->root; isbranch(*childp); parentp = childp, childp = &B->child[pos]) { B = child2branch(*childp); chunk = key_chunk(key, B->i, keylen); if (!chunk_mapped(B->bitmap, chunk)) return NULL; pos = chunkpos(B->bitmap, chunk); } /* If it's a tombstone, nothing to do. */ if (*childp == 0) return NULL; /* Verify whether it matches. */ assert(isleaf(*childp)); N0 = child2leaf(*childp); key0 = cradix_key(C, N0); if (memcmp(key0, key, keylen) != 0) return NULL; /* Were we at the root or a branch? */ if (parentp == NULL) { /* Root -- just replace it by empty. */ assert(childp == &C->root); assert(C->root == leaf2child(N0)); atomic_store_relaxed(&C->root, 0); } else { /* Branch -- prune it. */ assert(B != NULL); assert(B->child[pos] == leaf2child(N0)); prune_branch(C, D, B, chunk, parentp); } /* Return the node we deleted. */ return N0; } /* Iteration */ void cradix_iter_init(struct cradix *C, struct cradix_iter *I, void *stack, size_t stacklen) { struct { const struct cradix_branch * branchstack[CRADIX_ITER_STACKDEPTH(C->ops->keylen)]; uint8_t chunkstack[CRADIX_ITER_STACKDEPTH(C->ops->keylen)]; } *distract; assert(stacklen >= sizeof(*distract)); distract = stack; assert((void *)distract == (void *)distract->branchstack); I->cradix = C; I->depth = 0; I->branchstack = distract->branchstack; I->chunkstack = distract->chunkstack; } void cradix_iter_destroy(struct cradix *C __diagused, struct cradix_iter *I) { assert(I->cradix == C); I->cradix = NULL; I->depth = UINT_MAX; I->branchstack = NULL; I->chunkstack = NULL; } bool cradix_iter_begin(struct cradix *C, struct cradix_iter *I) { void *stack; size_t stacklen = CRADIX_ITER_STACKSIZE(C->ops->keylen); if (C->ops->alloc) stack = (*C->ops->alloc)(C, stacklen); else stack = cradix_default_alloc(stacklen); if (stack == NULL) return false; cradix_iter_init(C, I, stack, stacklen); return true; } void cradix_iter_end(struct cradix *C, struct cradix_iter *I) { void *stack = I->branchstack; size_t stacklen = CRADIX_ITER_STACKSIZE(C->ops->keylen); cradix_iter_destroy(C, I); if (C->ops->free) (*C->ops->free)(C, stack, stacklen); else cradix_default_free(stack, stacklen); } static unsigned findnextchunk(cradix_bitmap_t bitmap, unsigned chunk) { cradix_bitmap_t mask; /* Set bit chunk and all bits below it. */ mask = map_chunk(0, chunk); mask |= mask - 1; /* Clear those bits. */ bitmap &= ~mask; /* Find the first set bit after clearing them. */ assert(bitmap); return ffsl(bitmap) - 1; } static unsigned findprevchunk(cradix_bitmap_t bitmap, unsigned chunk) { cradix_bitmap_t mask; /* Set all bits below chunk. */ mask = map_chunk(0, chunk) - 1; /* Clear the other bits. */ bitmap &= mask; /* Find the last set bit after clearing them. */ assert(bitmap); return flsl(bitmap) - 1; } static struct cradix_node * cradix_iter_extreme(struct cradix *C, struct cradix_iter *I, bool forward) { const unsigned keylen = C->ops->keylen; const unsigned maxdepth __diagused = howmany(CHAR_BIT*keylen, CHUNK_SIZE); struct cradix_branch *B; uintptr_t child; unsigned chunk, pos, d; assert(I->cradix == C); assert(I->depth == 0); /* If there's nothing in the tree, we're done. */ if ((child = atomic_load_consume(&C->root)) == 0) return NULL; /* Move down and in the designated direction until we hit a leaf. */ for (d = 0; assert(d < maxdepth), isbranch(child); d++, child = atomic_load_consume(&B->child[pos])) { B = child2branch(child); assert(B->bitmap); if (forward) { chunk = ffsl(B->bitmap) - 1; pos = 0; } else { chunk = flsl(B->bitmap) - 1; pos = popcountl(B->bitmap) - 1; } assert(pos == chunkpos(B->bitmap, chunk)); I->branchstack[d] = B; I->chunkstack[d] = chunk; } /* Mark where we were and return the node. */ assert(d < maxdepth); I->depth = d; I->submask = ~(cradix_bitmap_t)0; return child2leaf(child); } struct cradix_node * cradix_iter_extreme_prefix(struct cradix *C, struct cradix_iter *I, const void *prefix, size_t prefixlen, bool forward) { const unsigned keylen = C->ops->keylen; const unsigned maxdepth __diagused = howmany(CHAR_BIT*keylen, CHUNK_SIZE); const struct cradix_branch *B; uintptr_t child; struct cradix_node *N; const void *key; unsigned chunk, pos, d = 0, submask = ~0u; cradix_bitmap_t bitmap; assert(prefixlen <= keylen); /* If the tree is empty, not there. */ if ((child = atomic_load_consume(&C->root)) == 0) return NULL; /* Find the first candidate match. */ while (isbranch(child)) { B = child2branch(child); /* Check how this branch position sits in our prefix. */ if (CHUNK_SIZE*(B->i + 1) <= CHAR_BIT*prefixlen) { /* Fits fully in our prefix. Keep searching. */ chunk = key_chunk(prefix, B->i, prefixlen); if (!chunk_mapped(B->bitmap, chunk)) return NULL; pos = chunkpos(B->bitmap, chunk); if ((child = atomic_load_consume(&B->child[pos])) == 0) return NULL; } else if (CHAR_BIT*prefixlen <= CHUNK_SIZE*B->i) { /* Prefix has ended. Just go left/rightmost. */ if (forward) { child = first_child_submap(B, B->bitmap, &chunk); } else { child = last_child_submap(B, B->bitmap, &chunk); } assert(child); I->branchstack[d] = B; I->chunkstack[d] = chunk; d++; } else { /* * Our prefix covers only part of the chunk * this branch discriminates on. Compute the * mask narrowing the bitmap to the children * matching our partial chunk, and go to the * extreme child of those. */ const uint8_t *const k = prefix; submask = partial_submask(k[prefixlen - 1], prefixlen); bitmap = B->bitmap & submask; if (bitmap == 0) return NULL; if (forward) child = first_child_submap(B, bitmap, &chunk); else child = last_child_submap(B, bitmap, &chunk); if (child == 0) return NULL; assert(d == 0); I->branchstack[0] = B; I->chunkstack[0] = chunk; d = 1; } } /* Verify whether it matches. */ assert(isleaf(child)); N = child2leaf(child); key = cradix_key(C, N); if (memcmp(prefix, key, prefixlen) != 0) return NULL; /* Mark where we were and return the node. */ assert(d < maxdepth); I->depth = d; I->submask = submask; return N; } struct cradix_node * cradix_iter_min(struct cradix *C, struct cradix_iter *I) { return cradix_iter_extreme(C, I, true); } struct cradix_node * cradix_iter_max(struct cradix *C, struct cradix_iter *I) { return cradix_iter_extreme(C, I, false); } struct cradix_node * cradix_iter_min_prefix(struct cradix *C, struct cradix_iter *I, const void *key, size_t keylen) { return cradix_iter_extreme_prefix(C, I, key, keylen, true); } struct cradix_node * cradix_iter_max_prefix(struct cradix *C, struct cradix_iter *I, const void *key, size_t keylen) { return cradix_iter_extreme_prefix(C, I, key, keylen, false); } static struct cradix_node * cradix_iter_adjacent(struct cradix *C __diagused, struct cradix_iter *I, bool forward) { const unsigned keylen = C->ops->keylen; const unsigned maxdepth __diagused = howmany(CHAR_BIT*keylen, CHUNK_SIZE); const struct cradix_branch *B; cradix_bitmap_t bitmap; unsigned d, chunk, lastchunk, pos; uintptr_t child; assert(I->cradix == C); /* Move back up until we can move laterally. */ for (d = I->depth; d --> 0;) { /* Get the current branch. */ B = I->branchstack[d]; chunk = I->chunkstack[d]; /* * Narrow the bitmap to the ones of interest if we're * at the top of the tree. */ bitmap = B->bitmap; if (d == 0) bitmap &= I->submask; /* * Find the last matching chunk at this level. If * we're already at it, keep moving up. */ lastchunk = (forward ? flsl(bitmap) : ffsl(bitmap)) - 1; if (chunk == lastchunk) continue; /* Move forward by one. */ chunk = (forward ? findnextchunk(bitmap, chunk) : findprevchunk(bitmap, chunk)); assert(I->branchstack[d] == B); I->chunkstack[d] = chunk; pos = chunkpos(B->bitmap, chunk); child = atomic_load_consume(&B->child[pos]); d++; /* Now move down and in reverse as far as we can. */ for (; assert(d < maxdepth), isbranch(child); d++, child = atomic_load_consume(&B->child[pos])) { B = child2branch(child); assert(B->bitmap); chunk = (forward ? ffsl(B->bitmap) : flsl(B->bitmap)) - 1; pos = (forward ? 0 : popcountl(B->bitmap) - 1); assert(pos == chunkpos(B->bitmap, chunk)); I->branchstack[d] = B; I->chunkstack[d] = chunk; } /* Stop here. We have found the next leaf. */ assert(d < maxdepth); I->depth = d; return child2leaf(child); } /* There is nothing more. Note that we are done. */ I->depth = 0; return NULL; } struct cradix_node * cradix_iter_next(struct cradix *C, struct cradix_iter *I) { return cradix_iter_adjacent(C, I, true); } struct cradix_node * cradix_iter_prev(struct cradix *C, struct cradix_iter *I) { return cradix_iter_adjacent(C, I, false); } #include static void cradix_dump_child(const struct cradix *C, uintptr_t child, unsigned indent) { if (child == 0) { printf("tombstone\n"); } else if (isleaf(child)) { struct cradix_node *N = child2leaf(child); const uint8_t *key = cradix_key(C, N); unsigned i = 0; printf("leaf @ %p: ", N); for (i = 0; i < C->ops->keylen; i++) printf("%02hhx", key[i]); printf("\n"); } else { struct cradix_branch *B = child2branch(child); cradix_bitmap_t bitmap; unsigned chunk, pos; uintptr_t child; printf("branch @ %p on chunk %u\n", B, B->i); indent++; bitmap = B->bitmap; while (bitmap) { chunk = ffsl(bitmap) - 1; bitmap = unmap_chunk(bitmap, chunk); pos = chunkpos(B->bitmap, chunk); child = atomic_load_consume(&B->child[pos]); printf("%*s[%02x] ", indent*2, "", chunk); cradix_dump_child(C, child, indent); } } } void cradix_dump(const struct cradix *C) { uintptr_t root; root = atomic_load_consume(&C->root); if (root == 0) printf("empty\n"); else cradix_dump_child(C, root, 0); }