summaryrefslogtreecommitdiff
path: root/oidtree.c
diff options
context:
space:
mode:
Diffstat (limited to 'oidtree.c')
-rw-r--r--oidtree.c104
1 files changed, 104 insertions, 0 deletions
diff --git a/oidtree.c b/oidtree.c
new file mode 100644
index 0000000000..7eb0e9ba05
--- /dev/null
+++ b/oidtree.c
@@ -0,0 +1,104 @@
+/*
+ * A wrapper around cbtree which stores oids
+ * May be used to replace oid-array for prefix (abbreviation) matches
+ */
+#include "oidtree.h"
+#include "alloc.h"
+#include "hash.h"
+
+struct oidtree_node {
+ /* n.k[] is used to store "struct object_id" */
+ struct cb_node n;
+};
+
+struct oidtree_iter_data {
+ oidtree_iter fn;
+ void *arg;
+ size_t *last_nibble_at;
+ int algo;
+ uint8_t last_byte;
+};
+
+void oidtree_init(struct oidtree *ot)
+{
+ cb_init(&ot->tree);
+ mem_pool_init(&ot->mem_pool, 0);
+}
+
+void oidtree_clear(struct oidtree *ot)
+{
+ if (ot) {
+ mem_pool_discard(&ot->mem_pool, 0);
+ oidtree_init(ot);
+ }
+}
+
+void oidtree_insert(struct oidtree *ot, const struct object_id *oid)
+{
+ struct oidtree_node *on;
+
+ if (!oid->algo)
+ BUG("oidtree_insert requires oid->algo");
+
+ on = mem_pool_alloc(&ot->mem_pool, sizeof(*on) + sizeof(*oid));
+ oidcpy_with_padding((struct object_id *)on->n.k, oid);
+
+ /*
+ * n.b. Current callers won't get us duplicates, here. If a
+ * future caller causes duplicates, there'll be a a small leak
+ * that won't be freed until oidtree_clear. Currently it's not
+ * worth maintaining a free list
+ */
+ cb_insert(&ot->tree, &on->n, sizeof(*oid));
+}
+
+
+int oidtree_contains(struct oidtree *ot, const struct object_id *oid)
+{
+ struct object_id k;
+ size_t klen = sizeof(k);
+
+ oidcpy_with_padding(&k, oid);
+
+ if (oid->algo == GIT_HASH_UNKNOWN)
+ klen -= sizeof(oid->algo);
+
+ /* cb_lookup relies on memcmp on the struct, so order matters: */
+ klen += BUILD_ASSERT_OR_ZERO(offsetof(struct object_id, hash) <
+ offsetof(struct object_id, algo));
+
+ return cb_lookup(&ot->tree, (const uint8_t *)&k, klen) ? 1 : 0;
+}
+
+static enum cb_next iter(struct cb_node *n, void *arg)
+{
+ struct oidtree_iter_data *x = arg;
+ const struct object_id *oid = (const struct object_id *)n->k;
+
+ if (x->algo != GIT_HASH_UNKNOWN && x->algo != oid->algo)
+ return CB_CONTINUE;
+
+ if (x->last_nibble_at) {
+ if ((oid->hash[*x->last_nibble_at] ^ x->last_byte) & 0xf0)
+ return CB_CONTINUE;
+ }
+
+ return x->fn(oid, x->arg);
+}
+
+void oidtree_each(struct oidtree *ot, const struct object_id *oid,
+ size_t oidhexsz, oidtree_iter fn, void *arg)
+{
+ size_t klen = oidhexsz / 2;
+ struct oidtree_iter_data x = { 0 };
+ assert(oidhexsz <= GIT_MAX_HEXSZ);
+
+ x.fn = fn;
+ x.arg = arg;
+ x.algo = oid->algo;
+ if (oidhexsz & 1) {
+ x.last_byte = oid->hash[klen];
+ x.last_nibble_at = &klen;
+ }
+ cb_each(&ot->tree, (const uint8_t *)oid, klen, iter, &x);
+}