/*- * Copyright (c) 2015--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. */ #ifdef _KERNEL #include #include #define assert KASSERT #else /* !_KERNEL */ #include #include #include #include #include #ifndef __diagused #ifdef NDEBUG #define __diagused __unused #else #define __diagused #endif #endif #if CRITBIT_DEBUG #define __dbgused #else #define __dbgused __unused #endif #endif /* _KERNEL */ #include "container_of.h" #include "critbit.h" #if CRITBIT_DEBUG #define DBG(x) x /* * Bits in the lower 9 bits, magic in the upper 7 bits, of a 16-bit * quantity. */ #define CRITBIT_BITS_MASK 0x01ff #define CRITBIT_MAGIC_MASK 0xfe00 /* The magic numbers differ pairwise by at least two bits out of paranoia. */ #define CRITBIT_MAGIC_INIT 0x0200 /* initialized */ #define CRITBIT_MAGIC_INSERTED 0x0600 /* inserted and not deleted */ #define CRITBIT_MAGIC_PENDING 0x0c00 /* deleted but not committed */ #define CRITBIT_MAGIC_DELETED 0x1400 /* deleted, _maybe_ committed */ #define CRITBIT_MAGIC_DEAD 0x1800 /* destroyed */ static inline unsigned critbits(const struct critbit_branch *B) { return B->cbb_bits & CRITBIT_BITS_MASK; } static inline void set_critbits(struct critbit_branch *B, unsigned bits) { assert((bits & CRITBIT_BITS_MASK) == bits); B->cbb_bits &= ~CRITBIT_BITS_MASK; B->cbb_bits |= bits; } static inline unsigned critbit_branch_magic(const struct critbit_branch *B) { return B->cbb_bits & CRITBIT_MAGIC_MASK; } static inline void set_critbit_branch_magic(struct critbit_branch *B, unsigned magic) { assert((magic & CRITBIT_MAGIC_MASK) == magic); B->cbb_bits &= ~CRITBIT_MAGIC_MASK; B->cbb_bits |= magic; } static inline unsigned critbit_node_magic(const struct critbit_node *N) { return critbit_branch_magic(&N->cbn_branch); } static inline void set_critbit_node_magic(struct critbit_node *N, unsigned magic) { set_critbit_branch_magic(&N->cbn_branch, magic); } #define N_INIT(N) set_critbit_node_magic(N, CRITBIT_MAGIC_INIT) #define N_INSERTED(N) set_critbit_node_magic(N, CRITBIT_MAGIC_INSERTED) #define N_PENDING(N) set_critbit_node_magic(N, CRITBIT_MAGIC_PENDING) #define N_DELETED(N) set_critbit_node_magic(N, CRITBIT_MAGIC_DELETED) #define N_DEAD(N) set_critbit_node_magic(N, CRITBIT_MAGIC_DEAD) #define N_ASSERT_INSERTED(N) B_ASSERT_INSERTED(&(N)->cbn_branch) #define N_ASSERT_MAYBE_INSERTED(N) B_ASSERT_MAYBE_INSERTED(&(N)->cbn_branch) #define N_ASSERT_NOT_INSERTED(N) B_ASSERT_NOT_INSERTED(&(N)->cbn_branch) #define N_ASSERT_PENDING(N) B_ASSERT_PENDING(&(N)->cbn_branch) #define N_ASSERT_DELETED(N) B_ASSERT_DELETED(&(N)->cbn_branch) #define N_ASSERT_NOT_COMMITTED(N) B_ASSERT_NOT_COMMITTED(&(N)->cbn_branch) #define B_ASSERT_INSERTED(B) \ assert(critbit_branch_magic(B) == CRITBIT_MAGIC_INSERTED) #define B_ASSERT_MAYBE_INSERTED(B) \ assert(critbit_branch_magic(B) == CRITBIT_MAGIC_INSERTED || \ critbit_branch_magic(B) == CRITBIT_MAGIC_PENDING || \ critbit_branch_magic(B) == CRITBIT_MAGIC_DELETED) #define B_ASSERT_NOT_INSERTED(B) \ assert(critbit_branch_magic(B) == CRITBIT_MAGIC_INIT || \ critbit_branch_magic(B) == CRITBIT_MAGIC_DELETED) #define B_ASSERT_PENDING(B) \ assert(critbit_branch_magic(B) == CRITBIT_MAGIC_PENDING) #define B_ASSERT_DELETED(B) \ assert(critbit_branch_magic(B) == CRITBIT_MAGIC_DELETED) #define B_ASSERT_NOT_COMMITTED(B) \ assert(critbit_branch_magic(B) == CRITBIT_MAGIC_INSERTED || \ critbit_branch_magic(B) == CRITBIT_MAGIC_PENDING) #else /* !CRITBIT_DEBUG */ #define DBG(x) ((void)0) static inline unsigned critbits(const struct critbit_branch *B) { return B->cbb_bits; } static inline void set_critbits(struct critbit_branch *B, unsigned bits) { B->cbb_bits = bits; } #endif #define MIN(x, y) ((x) < (y) ? (x) : (y)) /* Child pointer load and store ordering */ /* * load_child(C, childp) * * Atomically load a tagged child pointer from *childp and return * it. Guarantees to load a single snapshot of the value of the * pointer, and to load it only once. Makes no guarantees about * subsequent loads. Caller is responsible for issuing a * data-dependent read barrier if the tagged child pointer is of * interest -- this is not even a `consume' load, let alone an * `acquire' load. */ static inline uintptr_t load_child(const struct critbit *C __unused, const volatile uintptr_t *childp) { uintptr_t child; child = *childp; __insn_barrier(); return child; } /* * store_child(C, childp, child) * * Atomically store a tagged child pointer to *childp. Guarantees * all prior stores in program order have completed before the * store to *childp. */ static inline void store_child(struct critbit *C, volatile uintptr_t *childp, uintptr_t child) { (*C->cb_ops->cbo_membar_producer)(); *childp = child; } /* Tagged child pointers */ static bool isbranch(uintptr_t child) { return (child & 1) == 1; } static bool __diagused isleaf(uintptr_t child) { return (child & 1) == 0; } static uintptr_t branch2child(struct critbit_branch *B) { assert((uintptr_t)B != 0); assert(((uintptr_t)B & 1) == 0); return (uintptr_t)B | 1; } static uintptr_t leaf2child(struct critbit_node *N) { assert((uintptr_t)N != 0); assert(((uintptr_t)N & 1) == 0); return (uintptr_t)N; } static struct critbit_branch * child2branch(uintptr_t child) { struct critbit_branch *B; assert((child & 1) == 1); B = (struct critbit_branch *)(child - 1); assert(B != NULL); return B; } static struct critbit_node * child2leaf(uintptr_t child) { struct critbit_node *N; assert((child & 1) == 0); N = (struct critbit_node *)child; assert(N != NULL); return N; } /* Direction and iteration paths */ static inline unsigned revdir(unsigned dir) { /* * Could use 1 - dir instead, but that usually takes one more * instruction on common CPU architectures, since subtraction * instructions usually accept a immediate subtrahend but not * an immediate minuend, while xor is commutative so it doesn't * matter. */ return 1 ^ dir; } static inline unsigned getdir(unsigned char *S, unsigned d) { const unsigned i = d / CHAR_BIT; const unsigned j = d % CHAR_BIT; assert(d <= CHAR_BIT*CRITBIT_MAX_KEYLEN); return 1 & (S[i] >> j); } static inline void setdir(unsigned char *S, unsigned d, unsigned dir) { const unsigned i = d / CHAR_BIT; const unsigned j = d % CHAR_BIT; assert(d <= CHAR_BIT*CRITBIT_MAX_KEYLEN); assert(dir == (dir & 1)); S[i] &= ~(1 << j); S[i] |= dir << j; } /* Critbit tree and node creation and destruction */ void critbit_init(struct critbit *C, const struct critbit_ops *ops) { C->cb_root = 0; C->cb_ops = ops; } void critbit_destroy(struct critbit *C) { assert(C->cb_root == 0); assert(C->cb_ops != NULL); C->cb_root = -1; C->cb_ops = NULL; } void critbit_node_init(struct critbit_node *N __dbgused __diagused, const void *key __diagused, size_t keylen __diagused) { assert(((uintptr_t)N & 1) == 0); assert(((uintptr_t)&N->cbn_branch & 1) == 0); assert(key != NULL); assert(0 < keylen); assert(keylen <= CRITBIT_MAX_KEYLEN); DBG(N_INIT(N)); } void critbit_node_destroy(struct critbit_node *N __dbgused) { DBG(N_ASSERT_NOT_INSERTED(N)); N->cbn_branch.cbb_child[0] = 12345; N->cbn_branch.cbb_child[1] = 54321; N->cbn_branch.cbb_idx = 65535; N->cbn_branch.cbb_bits = 0x53; DBG(N_DEAD(N)); } bool critbit_empty(const struct critbit *C) { return (C->cb_root == 0); } static const uint8_t * critbit_key(const struct critbit *C, const struct critbit_node *N, size_t *keylenp) { const uint8_t *k; k = (*C->cb_ops->cbo_key)(C, N, keylenp); assert(k != NULL); assert(*keylenp <= CRITBIT_MAX_KEYLEN); return k; } /* Lookup */ struct critbit_node * critbit_lookup(const struct critbit *C, const void *key, size_t keylen) { const uint8_t *const k = key; const struct critbit_branch *B; uintptr_t child; unsigned dir; struct critbit_node *N; const uint8_t *k0; size_t keylen0; size_t i; assert(keylen <= CRITBIT_MAX_KEYLEN); /* If the tree is empty, not there. */ if ((child = load_child(C, &C->cb_root)) == 0) return NULL; /* Find the first candidate match. */ for (; isbranch(child); child = load_child(C, &B->cbb_child[dir])) { unsigned byte; B = child2branch(child); (*C->cb_ops->cbo_membar_datadep_consumer)(); DBG(B_ASSERT_MAYBE_INSERTED(B)); byte = (B->cbb_idx < keylen? 0x100 | k[B->cbb_idx] : 0); dir = (1 + (critbits(B) | byte)) >> 9; } /* Get the node. */ assert(isleaf(child)); N = child2leaf(child); (*C->cb_ops->cbo_membar_datadep_consumer)(); DBG(N_ASSERT_MAYBE_INSERTED(N)); k0 = critbit_key(C, N, &keylen0); /* Reject if the key doesn't match. */ if (keylen0 != keylen) return NULL; for (i = 0; i < keylen; i++) if (k[i] != k0[i]) return NULL; /* Success! */ return N; } /* Min/max */ static struct critbit_node * critbit_extreme(const struct critbit *C, unsigned dir) { struct critbit_branch *B; struct critbit_node *N; uintptr_t child; if ((child = load_child(C, &C->cb_root)) == 0) return NULL; for (; isbranch(child); child = load_child(C, &B->cbb_child[dir])) { B = child2branch(child); (*C->cb_ops->cbo_membar_datadep_consumer)(); DBG(B_ASSERT_MAYBE_INSERTED(B)); } assert(isleaf(child)); N = child2leaf(child); (*C->cb_ops->cbo_membar_datadep_consumer)(); DBG(N_ASSERT_MAYBE_INSERTED(N)); return N; } struct critbit_node * critbit_min(const struct critbit *C) { return critbit_extreme(C, 0); } struct critbit_node * critbit_max(const struct critbit *C) { return critbit_extreme(C, 1); } /* Min/max with prefix */ static struct critbit_node * critbit_extreme_prefix(const struct critbit *C, const void *key, size_t keylen, unsigned subdir) { const uint8_t *const k = key; const struct critbit_branch *B; uintptr_t child; unsigned dir; struct critbit_node *N; const uint8_t *k0; size_t keylen0; size_t i; assert(keylen <= CRITBIT_MAX_KEYLEN); /* If the tree is empty, not there. */ if ((child = load_child(C, &C->cb_root)) == 0) return NULL; /* Find the first candidate match. */ for (; isbranch(child); child = load_child(C, &B->cbb_child[dir])) { unsigned byte; B = child2branch(child); (*C->cb_ops->cbo_membar_datadep_consumer)(); DBG(B_ASSERT_MAYBE_INSERTED(B)); if (B->cbb_idx < keylen) { byte = 0x100 | k[B->cbb_idx]; dir = (1 + (critbits(B) | byte)) >> 9; } else { dir = subdir; } } /* Get the node. */ assert(isleaf(child)); N = child2leaf(child); (*C->cb_ops->cbo_membar_datadep_consumer)(); DBG(N_ASSERT_MAYBE_INSERTED(N)); k0 = critbit_key(C, N, &keylen0); /* Reject if the prefix doesn't match. */ if (keylen0 < keylen) return NULL; for (i = 0; i < keylen; i++) if (k[i] != k0[i]) return NULL; /* Success! */ return N; } struct critbit_node * critbit_min_prefix(const struct critbit *C, const void *key, size_t keylen) { return critbit_extreme_prefix(C, key, keylen, 0); } struct critbit_node * critbit_max_prefix(const struct critbit *C, const void *key, size_t keylen) { return critbit_extreme_prefix(C, key, keylen, 1); } /* Insert */ struct critbit_node * critbit_insert(struct critbit *C, struct critbit_node *N) { size_t keylen, keylen0; const uint8_t *k, *k0; struct critbit_branch *B; uintptr_t child, *childp; unsigned dir, byte = 0 /*XXXGCC*/, newdir, newbyte; struct critbit_node *N0; uint32_t i, diff, newbits; DBG(N_ASSERT_NOT_INSERTED(N)); /* Get the key. */ k = critbit_key(C, N, &keylen); assert(k != NULL); assert(keylen <= CRITBIT_MAX_KEYLEN); /* If the tree is empty, insert it at the root. */ if (C->cb_root == 0) { DBG(N_INSERTED(N)); store_child(C, &C->cb_root, leaf2child(N)); DBG(N_ASSERT_INSERTED(N)); return N; /* inserted */ } /* Find the first candidate match. */ for (child = C->cb_root; isbranch(child); child = B->cbb_child[dir]) { B = child2branch(child); DBG(B_ASSERT_INSERTED(B)); byte = (B->cbb_idx < keylen? 0x100 | k[B->cbb_idx] : 0); dir = (1 + (critbits(B) | byte)) >> 9; } /* Get the candidate node. */ assert(isleaf(child)); N0 = child2leaf(child); DBG(N_ASSERT_INSERTED(N0)); k0 = critbit_key(C, N0, &keylen0); /* Find the index of the critical byte. */ for (i = 0; i < MIN(keylen, keylen0); i++) { newbyte = k[i]; if ((diff = k0[i] ^ newbyte) != 0) goto branch; } if (keylen < keylen0) { /* new key k is shorter */ newbyte = 0; diff = 0x100 | k0[i]; goto branch; } else if (keylen0 < keylen) { /* existing key k0 is shorter */ newbyte = k[i]; diff = 0x100 | newbyte; goto branch; } DBG(N_ASSERT_INSERTED(N0)); return N0; /* collision */ branch: /* * Find the critical bit: * * . Set all bits from LSB up to the critical bit. * . Clear all bits but the critical bit. * . Complement -- set all bits but the critical bit. * * This way, newbits | b is 0x1ff iff b has 1 in the critical * bit, so that (1 + (newbits | b)) >> 9 is 1 iff b has 1 in * the critical bit. */ diff |= diff >> 1; diff |= diff >> 2; diff |= diff >> 4; diff |= diff >> 8; diff ^= diff >> 1; newbits = diff ^ 0x1ff; /* Direction from parent in which to put the new item. */ newdir = (1 + (newbits | newbyte)) >> 9; /* Find where to insert a new branch. */ for (childp = &C->cb_root; isbranch(*childp); childp = &B->cbb_child[dir]) { B = child2branch(*childp); DBG(B_ASSERT_INSERTED(B)); if (i < B->cbb_idx) break; if (i == B->cbb_idx && newbits < critbits(B)) break; byte = (B->cbb_idx < keylen? 0x100 | k[B->cbb_idx] : 0); dir = (1 + (critbits(B) | byte)) >> 9; } /* Initialize the new branch. */ B = &N->cbn_branch; B->cbb_idx = i; set_critbits(B, newbits); B->cbb_child[newdir] = leaf2child(N); B->cbb_child[1 - newdir] = *childp; /* Mark the node inserted. */ DBG(N_INSERTED(N)); /* * Insert it. Note that there is a path up from N to its * branch B. This will remain so under future insertions * because they never move subtrees around, and under future * deletions because they recycle deleted branch structures * only for higher branches. */ store_child(C, childp, branch2child(B)); DBG(N_ASSERT_INSERTED(N)); return N; /* inserted */ } /* Delete */ struct critbit_node * critbit_txn_delete_key(struct critbit *C, const void *key, size_t keylen, struct critbit_txn_delete *T) { const uint8_t *const k = key; struct critbit_branch *B = NULL; uintptr_t *childp, *parentp = NULL; unsigned dir = 0 /*XXXGCC*/, byte; struct critbit_node *N; const uint8_t *k0; size_t keylen0; uint32_t i; struct critbit_txn_delete_1 *T1, *T1_B = NULL, *T1_N = NULL; /* If the tree is empty, do nothing. */ if (C->cb_root == 0) return NULL; /* Find the closest node. */ for (childp = &C->cb_root; isbranch(*childp); childp = &B->cbb_child[dir]) { parentp = childp; B = child2branch(*childp); DBG(B_ASSERT_NOT_COMMITTED(B)); byte = (B->cbb_idx < keylen? 0x100 | k[B->cbb_idx] : 0); dir = (1 + (critbits(B) | byte)) >> 9; } /* Ignore it if it doesn't match. */ assert(isleaf(*childp)); N = child2leaf(*childp); DBG(N_ASSERT_NOT_COMMITTED(N)); k0 = critbit_key(C, N, &keylen0); if (keylen0 != keylen) return NULL; for (i = 0; i < keylen; i++) { if (k0[i] != k[i]) return NULL; } DBG(N_ASSERT_INSERTED(N)); /* If the root was a leaf, just replace it by empty. */ if (parentp == NULL) { assert(childp == &C->cb_root); assert(C->cb_root == leaf2child(N)); C->cb_root = 0; DBG(N_ASSERT_INSERTED(N)); DBG(N_DELETED(N)); return N; } /* Otherwise, replace it by the other child. */ assert(B != NULL); assert(B->cbb_child[dir] == leaf2child(N)); *parentp = B->cbb_child[revdir(dir)]; DBG(struct critbit_txn_delete_1 *T1_ = NULL); DBG(N_PENDING(N)); /* Search for overlapping deletion or recycling. */ for (T1 = T->ctd_q; T1 < T->ctd_q + T->ctd_i; T1++) { /* * Skip discarded records. Any node left to be deleted * here had better be in the PENDING state. */ assert((T1->ctd1_delete == NULL) == (T1->ctd1_recycle == NULL)); if (T1->ctd1_delete == NULL) continue; DBG(N_ASSERT_PENDING(T1->ctd1_delete)); /* Check whether we were going to delete B's node. */ if (T1->ctd1_delete == container_of(B, struct critbit_node, cbn_branch)) { assert(T1_B == NULL); T1_B = T1; } /* Check whether someone was hoping to recycle N's branch. */ if (T1->ctd1_recycle == &N->cbn_branch) { assert(T1_N == NULL); T1_N = T1; } } /* Decide what to do if we found overlapping deletion/recycling. */ if (T1_B && T1_N) { /* * The node of B is being deleted and recycled to some * branch B', and some node N' is being deleted and * recycled to the branch of N. Recycle N' to B' * instead, and forget about B and N. * * It is possible that the records coincide, if a node * is being deleted and recycled (but not in the same * step), in which case this has the effect of * discarding the common record. * * If they do not coincide, then: * * (a) there is a path up from B' to B, * (b) there is a path up from the branch of N to the * branch of N'. * * Since we know there is additionally a path up from B * to the branch of N, there is a path up from B' to * the branch of N'. */ assert(T1_B->ctd1_delete == container_of(B, struct critbit_node, cbn_branch)); assert(T1_N->ctd1_recycle == &N->cbn_branch); assert((T1_N->ctd1_delete == T1_B->ctd1_delete) == (T1_N == T1_B)); if (T1_N != T1_B) { DBG(N_ASSERT_PENDING(T1_B->ctd1_delete)); DBG(N_ASSERT_PENDING(T1_N->ctd1_delete)); DBG(N_DELETED(T1_B->ctd1_delete)); T1_B->ctd1_delete = T1_N->ctd1_delete; } else { DBG(N_ASSERT_PENDING(T1_N->ctd1_delete)); DBG(N_DELETED(T1_N->ctd1_delete)); } T1_N->ctd1_delete = NULL; T1_N->ctd1_recycle = NULL; DBG(N_ASSERT_PENDING(N)); DBG(N_DELETED(N)); goto out; } else if (T1_B) { /* * The node of B is being deleted and recycled to some * branch B'. Forget about B; recycle N to B'. * * If the node of B is being recycled to B', then there * is a path up from the node of B via B' to B. Since * there is also a path up from N via B to the branch * of N, there is a path up from B' to the branch of N. */ assert(T1_B->ctd1_delete == container_of(B, struct critbit_node, cbn_branch)); DBG(N_ASSERT_PENDING(T1_B->ctd1_delete)); DBG(N_DELETED(T1_B->ctd1_delete)); T1_B->ctd1_delete = N; DBG(T1_ = T1_B); DBG(N_ASSERT_PENDING(N)); goto out; } else if (T1_N) { /* * Some node N' is being deleted and recycled to the * branch of N. Forget about N; recycle N' to B. * * If N' is being recycled to the branch of N, then * there is a path up from the branch of N to the * branch of N'. Since there is also a path up from N * via B to the branch of N, there is a path up from B * to the branch of N'. */ assert(T1_N->ctd1_recycle == &N->cbn_branch); DBG(N_ASSERT_PENDING(N)); DBG(N_DELETED(N)); DBG(N_ASSERT_PENDING(T1_N->ctd1_delete)); T1_N->ctd1_recycle = B; goto out; } /* If we removed N's branch, we're done. */ if (B == &N->cbn_branch) { DBG(N_ASSERT_PENDING(N)); DBG(N_DELETED(N)); goto out; } /* * Otherwise, queue B up for recycling so we can delete N. * There is guaranteed to be a path up from B to the branch of * N if the branch of N is in use. Thus recycled branches only * ever move up in the tree, which means their nodes still have * paths up to them. */ assert(T->ctd_i < T->ctd_n); T1 = &T->ctd_q[T->ctd_i++]; T1->ctd1_delete = N; T1->ctd1_recycle = B; DBG(N_ASSERT_PENDING(N)); DBG(T1_ = T1); out: /* * - T1_ is N's entry in the queue, if any. * - N is pending or deleted at this point. * - N is pending iff it appears in the queue. * - N is deleted iff it does not appear in the queue. */ DBG(assert(T1_ == NULL || T1_->ctd1_delete == N)); DBG(if (T1_ != NULL) N_ASSERT_PENDING(N)); DBG(if (T1_ == NULL) N_ASSERT_DELETED(N)); return N; } /* Delete transaction */ void critbit_txn_delete_begin(struct critbit *C __unused, struct critbit_txn_delete *T, struct critbit_txn_delete_1 *T1, size_t n) { T->ctd_q = T1; T->ctd_i = 0; T->ctd_n = n; } void critbit_txn_delete_commit(struct critbit *C, struct critbit_txn_delete *T) { size_t i; /* Wait for all users of branches we may recycle to drain. */ (*C->cb_ops->cbo_sync)(C); /* * For each node N to delete, find whether its branch is still * in use. If it is, recycle its chosen extant branch for it. */ for (i = 0; i < T->ctd_i; i++) { const struct critbit_txn_delete_1 *const T1 = &T->ctd_q[i]; struct critbit_node *const N = T1->ctd1_delete; struct critbit_branch *B = NULL; const uint8_t *k; size_t keylen; uintptr_t *childp; unsigned dir, byte; if (N == NULL) continue; DBG(N_ASSERT_PENDING(N)); /* Find where N is. */ k = critbit_key(C, N, &keylen); for (childp = &C->cb_root; isbranch(*childp); childp = &B->cbb_child[dir]) { B = child2branch(*childp); DBG(B_ASSERT_NOT_COMMITTED(B)); if (B == &N->cbn_branch) break; byte = (B->cbb_idx < keylen? 0x100 | k[B->cbb_idx] : 0); dir = (1 + (critbits(B) | byte)) >> 9; } assert(childp != NULL); /* Didn't find it, so no need to recycle. */ if (B != &N->cbn_branch) continue; /* Found it at childp. Recycle (but preserve magic). */ #if CRITBIT_DEBUG { const unsigned magic = critbit_branch_magic(T1->ctd1_recycle); *T1->ctd1_recycle = *B; set_critbit_branch_magic(T1->ctd1_recycle, magic); } #else *T1->ctd1_recycle = *B; #endif /* Publish the recycled branch. */ store_child(C, childp, branch2child(T1->ctd1_recycle)); } /* Wait for all users of deleted nodes to drain. */ (*C->cb_ops->cbo_sync)(C); /* Mark all of the deleted nodes as newly initialized. */ for (i = 0; i < T->ctd_i; i++) { const struct critbit_txn_delete_1 *const T1 = &T->ctd_q[i]; struct critbit_node *const N = T1->ctd1_delete; if (N == NULL) continue; DBG(N_ASSERT_PENDING(N)); DBG(N_INIT(N)); } } /* Delete utilities */ void critbit_txn_delete(struct critbit *C, struct critbit_node *N, struct critbit_txn_delete *T) { struct critbit_node *N0; const void *key; size_t keylen; /* Get the key. */ key = critbit_key(C, N, &keylen); /* * Delete by the key. Without parent pointers, we can do no * better than this. */ N0 = critbit_txn_delete_key(C, key, keylen, T); /* The node had better be the same one. */ assert(N0 == N); } struct critbit_node * critbit_delete_key(struct critbit *C, const void *key, size_t keylen) { struct critbit_txn_delete_1 txn1, *T1 = &txn1; struct critbit_txn_delete txn, *T = &txn; struct critbit_node *N; /* Delete the key in a single-operation transaction. */ critbit_txn_delete_begin(C, T, T1, 1); N = critbit_txn_delete_key(C, key, keylen, T); critbit_txn_delete_commit(C, T); DBG(if (N != NULL) N_ASSERT_NOT_INSERTED(N)); return N; } void critbit_delete(struct critbit *C, struct critbit_node *N) { struct critbit_txn_delete_1 txn1, *T1 = &txn1; struct critbit_txn_delete txn, *T = &txn; /* Delete the node in a single-operation transaction. */ critbit_txn_delete_begin(C, T, T1, 1); critbit_txn_delete(C, N, T); critbit_txn_delete_commit(C, T); DBG(N_ASSERT_NOT_INSERTED(N)); } /* Iteration */ void critbit_iter_init(struct critbit *C, struct critbit_iter *I, void *stack, size_t stacklen) { assert(stacklen <= CRITBIT_MAX_KEYLEN); I->cbi_critbit = C; I->cbi_stack = stack; I->cbi_stacklen = stacklen; I->cbi_depth = 0; } void critbit_iter_destroy(struct critbit *C __diagused, struct critbit_iter *I) { assert(I->cbi_critbit == C); assert(I->cbi_stack != NULL); I->cbi_critbit = NULL; I->cbi_stack = NULL; I->cbi_stacklen = 0; I->cbi_depth = UINT_MAX; } static struct critbit_node * critbit_iter_extreme(struct critbit *C, struct critbit_iter *I, unsigned dir) { unsigned char *S = I->cbi_stack; const unsigned maxdepth __diagused = CHAR_BIT*I->cbi_stacklen; struct critbit_branch *B; uintptr_t child; unsigned d; assert(I->cbi_critbit == C); assert(I->cbi_depth == 0); /* If there's nothing in the tree, we're done. */ if (C->cb_root == 0) return NULL; /* Move down and in the designated direction until we hit a leaf. */ for (d = 0, child = C->cb_root; assert(d < maxdepth), isbranch(child); d++, child = B->cbb_child[dir]) { B = child2branch(child); setdir(S, d, dir); } /* Mark where we were and return the node. */ assert(d < maxdepth); I->cbi_depth = d; I->cbi_root = C->cb_root; return child2leaf(child); } struct critbit_node * critbit_iter_min(struct critbit *C, struct critbit_iter *I) { return critbit_iter_extreme(C, I, 0); } struct critbit_node * critbit_iter_max(struct critbit *C, struct critbit_iter *I) { return critbit_iter_extreme(C, I, 1); } struct critbit_node * critbit_iter_extreme_prefix(struct critbit *C, struct critbit_iter *I, const void *key, size_t keylen, unsigned subdir) { unsigned char *S = I->cbi_stack; const unsigned maxdepth __diagused = CHAR_BIT*I->cbi_stacklen; const uint8_t *const k = key; const struct critbit_branch *B; uintptr_t child, root = C->cb_root; unsigned dir; struct critbit_node *N; const uint8_t *k0; size_t keylen0; size_t i; unsigned d = 0; assert(keylen <= CRITBIT_MAX_KEYLEN); /* If the tree is empty, not there. */ if (C->cb_root == 0) return NULL; /* Find the first candidate match. */ for (child = C->cb_root; isbranch(child); child = B->cbb_child[dir]) { unsigned byte; B = child2branch(child); DBG(B_ASSERT_MAYBE_INSERTED(B)); if (B->cbb_idx < keylen) { byte = 0x100 | k[B->cbb_idx]; dir = (1 + (critbits(B) | byte)) >> 9; root = B->cbb_child[dir]; } else { assert(d < maxdepth); setdir(S, d++, subdir); dir = subdir; } } /* Get the node. */ assert(isleaf(child)); N = child2leaf(child); DBG(N_ASSERT_INSERTED(N)); k0 = critbit_key(C, N, &keylen0); /* Reject if the prefix doesn't match. */ if (keylen0 < keylen) return NULL; for (i = 0; i < keylen; i++) if (k[i] != k0[i]) return NULL; /* Mark where we were and return the node. */ assert(d < maxdepth); I->cbi_depth = d; I->cbi_root = root; return child2leaf(child); } struct critbit_node * critbit_iter_min_prefix(struct critbit *C, struct critbit_iter *I, const void *key, size_t keylen) { return critbit_iter_extreme_prefix(C, I, key, keylen, 0); } struct critbit_node * critbit_iter_max_prefix(struct critbit *C, struct critbit_iter *I, const void *key, size_t keylen) { return critbit_iter_extreme_prefix(C, I, key, keylen, 1); } static struct critbit_node * critbit_iter_adjacent(struct critbit *C __diagused, struct critbit_iter *I, unsigned dir) { unsigned char *S = I->cbi_stack; const unsigned maxdepth __diagused = CHAR_BIT*I->cbi_stacklen; struct critbit_branch *B; unsigned d0, d, dir0; uintptr_t child; assert(I->cbi_critbit == C); /* Move back up until we can move forward. */ for (d0 = I->cbi_depth; d0 --> 0;) { /* Can we move forward? */ if (getdir(S, d0) != dir) { /* Yes. First, make one step forward. */ setdir(S, d0++, dir); /* Next, follow the path down the stack. */ for (d = 0, child = I->cbi_root; d < d0; d++, child = B->cbb_child[dir0]) { assert(isbranch(child)); B = child2branch(child); dir0 = getdir(S, d); } /* Now move down and in reverse as far as we can. */ for (; assert(d < maxdepth), isbranch(child); d++, child = B->cbb_child[revdir(dir)]) { B = child2branch(child); setdir(S, d, revdir(dir)); } /* Stop here. We are done. */ assert(d < maxdepth); I->cbi_depth = d; return child2leaf(child); } } /* There is nothing more. Note that we are done. */ I->cbi_depth = 0; return NULL; } struct critbit_node * critbit_iter_next(struct critbit *C, struct critbit_iter *I) { return critbit_iter_adjacent(C, I, 1); } struct critbit_node * critbit_iter_prev(struct critbit *C, struct critbit_iter *I) { return critbit_iter_adjacent(C, I, 0); } /* Consistency check */ static void critbit_check_leaf(const struct critbit *C, const struct critbit_node *N) { const uint8_t *k; size_t keylen; const struct critbit_branch *B; uintptr_t child; unsigned dir; DBG(N_ASSERT_INSERTED(N)); k = critbit_key(C, N, &keylen); assert(C->cb_root != 0); for (child = C->cb_root; isbranch(child); child = B->cbb_child[dir]) { unsigned byte; B = child2branch(child); DBG(B_ASSERT_INSERTED(B)); byte = (B->cbb_idx < keylen? 0x100 | k[B->cbb_idx] : 0); dir = (1 + (critbits(B) | byte)) >> 9; } assert(isleaf(child)); assert(N == child2leaf(child)); } static void critbit_check_child(struct critbit *C, uintptr_t child, size_t idx __diagused) { if (isbranch(child)) { struct critbit_branch *B = child2branch(child); assert(idx <= B->cbb_idx); DBG(B_ASSERT_INSERTED(B)); critbit_check_child(C, B->cbb_child[0], B->cbb_idx); critbit_check_child(C, B->cbb_child[1], B->cbb_idx); } else { critbit_check_leaf(C, child2leaf(child)); } } void critbit_check(struct critbit *C) { if (C->cb_root == 0) return; critbit_check_child(C, C->cb_root, 0); } /* Print */ /* * WARNING: This debugging operation requires that the node's key be a * NUL-terminated printable string. */ #include #include static void critbit_print_child(struct critbit *C, uintptr_t child, unsigned indent) { if (isbranch(child)) { struct critbit_branch *const B = child2branch(child); printf("%*sbranch on 8*%u + %u (0x%02x) @ %p\n", indent*2, "", B->cbb_idx, 9 - ffs(0x1ff ^ critbits(B)), 0x1ff ^ critbits(B), B); critbit_print_child(C, B->cbb_child[0], indent + 1); critbit_print_child(C, B->cbb_child[1], indent + 1); } else { struct critbit_node *const N = child2leaf(child); size_t keylen __unused; const uint8_t *const k = critbit_key(C, N, &keylen); printf("%*sleaf @ %p: %s\n", indent*2, "", N, k); } } void critbit_print(struct critbit *C) { if (C->cb_root == 0) { printf("empty\n"); return; } critbit_print_child(C, C->cb_root, 0); }