diff options
| author | Jiang Xin <worldhello.net@gmail.com> | 2021-08-03 17:03:35 +0800 |
|---|---|---|
| committer | Jiang Xin <worldhello.net@gmail.com> | 2021-08-03 17:03:35 +0800 |
| commit | 972c9cf6aed660f3b4189a8f2adda505e67110ff (patch) | |
| tree | 350bb2a29eb3360cdf36a30d8c8e7c76c3e61851 /cbtree.c | |
| parent | ae4e099e7cd2fcb7abdcce1b4fe02b40d5e4a61b (diff) | |
| parent | 66262451ec94d30ac4b80eb3123549cf7a788afd (diff) | |
| download | git-972c9cf6aed660f3b4189a8f2adda505e67110ff.tar.gz | |
Merge branch 'master' of github.com:git/git
* 'master' of github.com:git/git: (397 commits)
Git 2.33-rc0
The seventh batch
ci/install-dependencies: handle "sparse" job package installs
ci: run "apt-get update" before "apt-get install"
cache-tree: prefetch in partial clone read-tree
unpack-trees: refactor prefetching code
pack-bitmap: check pack validity when opening bitmap
bundle tests: use test_cmp instead of grep
bundle tests: use ">file" not ": >file"
The sixth batch
doc: pull: fix rebase=false documentation
pack-bitmap: clarify comment in filter_bitmap_exclude_type()
doc: clarify description of 'submodule.recurse'
doc/git-config: simplify "override" advice for FILES section
doc/git-config: clarify GIT_CONFIG environment variable
doc/git-config: explain --file instead of referring to GIT_CONFIG
t0000: fix test if run with TEST_OUTPUT_DIRECTORY
multi-pack-index: fix potential segfault without sub-command
refs/debug: quote prefix
t0000: clear GIT_SKIP_TESTS before running sub-tests
...
Diffstat (limited to 'cbtree.c')
| -rw-r--r-- | cbtree.c | 167 |
1 files changed, 167 insertions, 0 deletions
diff --git a/cbtree.c b/cbtree.c new file mode 100644 index 0000000000..b0c65d810f --- /dev/null +++ b/cbtree.c @@ -0,0 +1,167 @@ +/* + * crit-bit tree implementation, does no allocations internally + * For more information on crit-bit trees: https://cr.yp.to/critbit.html + * Based on Adam Langley's adaptation of Dan Bernstein's public domain code + * git clone https://github.com/agl/critbit.git + */ +#include "cbtree.h" + +static struct cb_node *cb_node_of(const void *p) +{ + return (struct cb_node *)((uintptr_t)p - 1); +} + +/* locate the best match, does not do a final comparision */ +static struct cb_node *cb_internal_best_match(struct cb_node *p, + const uint8_t *k, size_t klen) +{ + while (1 & (uintptr_t)p) { + struct cb_node *q = cb_node_of(p); + uint8_t c = q->byte < klen ? k[q->byte] : 0; + size_t direction = (1 + (q->otherbits | c)) >> 8; + + p = q->child[direction]; + } + return p; +} + +/* returns NULL if successful, existing cb_node if duplicate */ +struct cb_node *cb_insert(struct cb_tree *t, struct cb_node *node, size_t klen) +{ + size_t newbyte, newotherbits; + uint8_t c; + int newdirection; + struct cb_node **wherep, *p; + + assert(!((uintptr_t)node & 1)); /* allocations must be aligned */ + + if (!t->root) { /* insert into empty tree */ + t->root = node; + return NULL; /* success */ + } + + /* see if a node already exists */ + p = cb_internal_best_match(t->root, node->k, klen); + + /* find first differing byte */ + for (newbyte = 0; newbyte < klen; newbyte++) { + if (p->k[newbyte] != node->k[newbyte]) + goto different_byte_found; + } + return p; /* element exists, let user deal with it */ + +different_byte_found: + newotherbits = p->k[newbyte] ^ node->k[newbyte]; + newotherbits |= newotherbits >> 1; + newotherbits |= newotherbits >> 2; + newotherbits |= newotherbits >> 4; + newotherbits = (newotherbits & ~(newotherbits >> 1)) ^ 255; + c = p->k[newbyte]; + newdirection = (1 + (newotherbits | c)) >> 8; + + node->byte = newbyte; + node->otherbits = newotherbits; + node->child[1 - newdirection] = node; + + /* find a place to insert it */ + wherep = &t->root; + for (;;) { + struct cb_node *q; + size_t direction; + + p = *wherep; + if (!(1 & (uintptr_t)p)) + break; + q = cb_node_of(p); + if (q->byte > newbyte) + break; + if (q->byte == newbyte && q->otherbits > newotherbits) + break; + c = q->byte < klen ? node->k[q->byte] : 0; + direction = (1 + (q->otherbits | c)) >> 8; + wherep = q->child + direction; + } + + node->child[newdirection] = *wherep; + *wherep = (struct cb_node *)(1 + (uintptr_t)node); + + return NULL; /* success */ +} + +struct cb_node *cb_lookup(struct cb_tree *t, const uint8_t *k, size_t klen) +{ + struct cb_node *p = cb_internal_best_match(t->root, k, klen); + + return p && !memcmp(p->k, k, klen) ? p : NULL; +} + +struct cb_node *cb_unlink(struct cb_tree *t, const uint8_t *k, size_t klen) +{ + struct cb_node **wherep = &t->root; + struct cb_node **whereq = NULL; + struct cb_node *q = NULL; + size_t direction = 0; + uint8_t c; + struct cb_node *p = t->root; + + if (!p) return NULL; /* empty tree, nothing to delete */ + + /* traverse to find best match, keeping link to parent */ + while (1 & (uintptr_t)p) { + whereq = wherep; + q = cb_node_of(p); + c = q->byte < klen ? k[q->byte] : 0; + direction = (1 + (q->otherbits | c)) >> 8; + wherep = q->child + direction; + p = *wherep; + } + + if (memcmp(p->k, k, klen)) + return NULL; /* no match, nothing unlinked */ + + /* found an exact match */ + if (whereq) /* update parent */ + *whereq = q->child[1 - direction]; + else + t->root = NULL; + return p; +} + +static enum cb_next cb_descend(struct cb_node *p, cb_iter fn, void *arg) +{ + if (1 & (uintptr_t)p) { + struct cb_node *q = cb_node_of(p); + enum cb_next n = cb_descend(q->child[0], fn, arg); + + return n == CB_BREAK ? n : cb_descend(q->child[1], fn, arg); + } else { + return fn(p, arg); + } +} + +void cb_each(struct cb_tree *t, const uint8_t *kpfx, size_t klen, + cb_iter fn, void *arg) +{ + struct cb_node *p = t->root; + struct cb_node *top = p; + size_t i = 0; + + if (!p) return; /* empty tree */ + + /* Walk tree, maintaining top pointer */ + while (1 & (uintptr_t)p) { + struct cb_node *q = cb_node_of(p); + uint8_t c = q->byte < klen ? kpfx[q->byte] : 0; + size_t direction = (1 + (q->otherbits | c)) >> 8; + + p = q->child[direction]; + if (q->byte < klen) + top = p; + } + + for (i = 0; i < klen; i++) { + if (p->k[i] != kpfx[i]) + return; /* "best" match failed */ + } + cb_descend(top, fn, arg); +} |