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