git
/
oidtree.c
109 строк · 2.5 Кб
1/*
2* A wrapper around cbtree which stores oids
3* May be used to replace oid-array for prefix (abbreviation) matches
4*/
5#include "git-compat-util.h"6#include "oidtree.h"7#include "hash.h"8
9struct oidtree_iter_data {10oidtree_iter fn;11void *arg;12size_t *last_nibble_at;13int algo;14uint8_t last_byte;15};16
17void oidtree_init(struct oidtree *ot)18{
19cb_init(&ot->tree);20mem_pool_init(&ot->mem_pool, 0);21}
22
23void oidtree_clear(struct oidtree *ot)24{
25if (ot) {26mem_pool_discard(&ot->mem_pool, 0);27oidtree_init(ot);28}29}
30
31void oidtree_insert(struct oidtree *ot, const struct object_id *oid)32{
33struct cb_node *on;34struct object_id k;35
36if (!oid->algo)37BUG("oidtree_insert requires oid->algo");38
39on = mem_pool_alloc(&ot->mem_pool, sizeof(*on) + sizeof(*oid));40
41/*42* Clear the padding and copy the result in separate steps to
43* respect the 4-byte alignment needed by struct object_id.
44*/
45oidcpy(&k, oid);46memcpy(on->k, &k, sizeof(k));47
48/*49* n.b. Current callers won't get us duplicates, here. If a
50* future caller causes duplicates, there'll be a a small leak
51* that won't be freed until oidtree_clear. Currently it's not
52* worth maintaining a free list
53*/
54cb_insert(&ot->tree, on, sizeof(*oid));55}
56
57
58int oidtree_contains(struct oidtree *ot, const struct object_id *oid)59{
60struct object_id k;61size_t klen = sizeof(k);62
63oidcpy(&k, oid);64
65if (oid->algo == GIT_HASH_UNKNOWN)66klen -= sizeof(oid->algo);67
68/* cb_lookup relies on memcmp on the struct, so order matters: */69klen += BUILD_ASSERT_OR_ZERO(offsetof(struct object_id, hash) <70offsetof(struct object_id, algo));71
72return cb_lookup(&ot->tree, (const uint8_t *)&k, klen) ? 1 : 0;73}
74
75static enum cb_next iter(struct cb_node *n, void *arg)76{
77struct oidtree_iter_data *x = arg;78struct object_id k;79
80/* Copy to provide 4-byte alignment needed by struct object_id. */81memcpy(&k, n->k, sizeof(k));82
83if (x->algo != GIT_HASH_UNKNOWN && x->algo != k.algo)84return CB_CONTINUE;85
86if (x->last_nibble_at) {87if ((k.hash[*x->last_nibble_at] ^ x->last_byte) & 0xf0)88return CB_CONTINUE;89}90
91return x->fn(&k, x->arg);92}
93
94void oidtree_each(struct oidtree *ot, const struct object_id *oid,95size_t oidhexsz, oidtree_iter fn, void *arg)96{
97size_t klen = oidhexsz / 2;98struct oidtree_iter_data x = { 0 };99assert(oidhexsz <= GIT_MAX_HEXSZ);100
101x.fn = fn;102x.arg = arg;103x.algo = oid->algo;104if (oidhexsz & 1) {105x.last_byte = oid->hash[klen];106x.last_nibble_at = &klen;107}108cb_each(&ot->tree, (const uint8_t *)oid, klen, iter, &x);109}
110