Line | Count | Source |
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 | | |
9 | | struct oidtree_node { |
10 | | struct cb_node base; |
11 | | struct object_id key; |
12 | | void *data; |
13 | | }; |
14 | | |
15 | | void oidtree_init(struct oidtree *ot) |
16 | 0 | { |
17 | 0 | cb_init(&ot->tree, offsetof(struct oidtree_node, key)); |
18 | 0 | mem_pool_init(&ot->mem_pool, 0); |
19 | 0 | } |
20 | | |
21 | | void oidtree_clear(struct oidtree *ot) |
22 | 0 | { |
23 | 0 | if (ot) { |
24 | 0 | mem_pool_discard(&ot->mem_pool, 0); |
25 | 0 | oidtree_init(ot); |
26 | 0 | } |
27 | 0 | } |
28 | | |
29 | | struct oidtree_data { |
30 | | struct object_id oid; |
31 | | }; |
32 | | |
33 | | void oidtree_insert(struct oidtree *ot, const struct object_id *oid, |
34 | | void *data) |
35 | 0 | { |
36 | 0 | struct oidtree_node *on; |
37 | 0 | struct cb_node *node; |
38 | |
|
39 | 0 | if (!oid->algo) |
40 | 0 | BUG("oidtree_insert requires oid->algo"); |
41 | | |
42 | 0 | on = mem_pool_alloc(&ot->mem_pool, sizeof(*on)); |
43 | 0 | oidcpy(&on->key, oid); |
44 | 0 | on->data = data; |
45 | | |
46 | | /* |
47 | | * n.b. Current callers won't get us duplicates, here. If a |
48 | | * future caller causes duplicates, there'll be a small leak |
49 | | * that won't be freed until oidtree_clear. Currently it's not |
50 | | * worth maintaining a free list |
51 | | */ |
52 | 0 | node = cb_insert(&ot->tree, &on->base, sizeof(*oid)); |
53 | 0 | if (node) { |
54 | 0 | struct oidtree_node *preexisting = container_of(node, struct oidtree_node, base); |
55 | 0 | preexisting->data = data; |
56 | 0 | } |
57 | 0 | } |
58 | | |
59 | | static struct oidtree_node *oidtree_lookup(struct oidtree *ot, |
60 | | const struct object_id *oid) |
61 | 0 | { |
62 | 0 | struct object_id k; |
63 | 0 | size_t klen = sizeof(k); |
64 | 0 | struct cb_node *node; |
65 | |
|
66 | 0 | oidcpy(&k, oid); |
67 | |
|
68 | 0 | if (oid->algo == GIT_HASH_UNKNOWN) |
69 | 0 | klen -= sizeof(oid->algo); |
70 | | |
71 | | /* cb_lookup relies on memcmp on the struct, so order matters: */ |
72 | 0 | klen += BUILD_ASSERT_OR_ZERO(offsetof(struct object_id, hash) < |
73 | 0 | offsetof(struct object_id, algo)); |
74 | |
|
75 | 0 | node = cb_lookup(&ot->tree, (const uint8_t *)&k, klen); |
76 | 0 | return node ? container_of(node, struct oidtree_node, base) : NULL; |
77 | 0 | } |
78 | | |
79 | | bool oidtree_contains(struct oidtree *ot, const struct object_id *oid) |
80 | 0 | { |
81 | 0 | struct oidtree_node *node = oidtree_lookup(ot, oid); |
82 | 0 | return node ? 1 : 0; |
83 | 0 | } |
84 | | |
85 | | void *oidtree_get(struct oidtree *ot, const struct object_id *oid) |
86 | 0 | { |
87 | 0 | struct oidtree_node *node = oidtree_lookup(ot, oid); |
88 | 0 | return node ? node->data : NULL; |
89 | 0 | } |
90 | | |
91 | | struct oidtree_each_data { |
92 | | oidtree_each_cb cb; |
93 | | void *cb_data; |
94 | | size_t *last_nibble_at; |
95 | | uint32_t algo; |
96 | | uint8_t last_byte; |
97 | | }; |
98 | | |
99 | | static int iter(struct cb_node *n, void *cb_data) |
100 | 0 | { |
101 | 0 | struct oidtree_node *node = container_of(n, struct oidtree_node, base); |
102 | 0 | struct oidtree_each_data *data = cb_data; |
103 | |
|
104 | 0 | if (data->algo != GIT_HASH_UNKNOWN && data->algo != node->key.algo) |
105 | 0 | return 0; |
106 | | |
107 | 0 | if (data->last_nibble_at) { |
108 | 0 | if ((node->key.hash[*data->last_nibble_at] ^ data->last_byte) & 0xf0) |
109 | 0 | return 0; |
110 | 0 | } |
111 | | |
112 | 0 | return data->cb(&node->key, node->data, data->cb_data); |
113 | 0 | } |
114 | | |
115 | | int oidtree_each(struct oidtree *ot, const struct object_id *prefix, |
116 | | size_t prefix_hex_len, oidtree_each_cb cb, void *cb_data) |
117 | 0 | { |
118 | 0 | struct oidtree_each_data data = { |
119 | 0 | .cb = cb, |
120 | 0 | .cb_data = cb_data, |
121 | 0 | .algo = prefix->algo, |
122 | 0 | }; |
123 | 0 | size_t klen = prefix_hex_len / 2; |
124 | 0 | assert(prefix_hex_len <= GIT_MAX_HEXSZ); |
125 | |
|
126 | 0 | if (prefix_hex_len & 1) { |
127 | 0 | data.last_byte = prefix->hash[klen]; |
128 | 0 | data.last_nibble_at = &klen; |
129 | 0 | } |
130 | |
|
131 | 0 | return cb_each(&ot->tree, prefix->hash, klen, iter, &data); |
132 | 0 | } |