@leroysheep / rag-system
Code Commits Pulls CI/CD 81,972
jch
bisect jch maint master next seen test todo
c 132 lines 3.11 KB
Raw
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 {
17 cb_init(&ot->tree, offsetof(struct oidtree_node, key));
18 mem_pool_init(&ot->mem_pool, 0);
19 }
20
21 void oidtree_clear(struct oidtree *ot)
22 {
23 if (ot) {
24 mem_pool_discard(&ot->mem_pool, 0);
25 oidtree_init(ot);
26 }
27 }
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 {
36 struct oidtree_node *on;
37 struct cb_node *node;
38
39 if (!oid->algo)
40 BUG("oidtree_insert requires oid->algo");
41
42 on = mem_pool_alloc(&ot->mem_pool, sizeof(*on));
43 oidcpy(&on->key, oid);
44 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 node = cb_insert(&ot->tree, &on->base, sizeof(*oid));
53 if (node) {
54 struct oidtree_node *preexisting = container_of(node, struct oidtree_node, base);
55 preexisting->data = data;
56 }
57 }
58
59 static struct oidtree_node *oidtree_lookup(struct oidtree *ot,
60 const struct object_id *oid)
61 {
62 struct object_id k;
63 size_t klen = sizeof(k);
64 struct cb_node *node;
65
66 oidcpy(&k, oid);
67
68 if (oid->algo == GIT_HASH_UNKNOWN)
69 klen -= sizeof(oid->algo);
70
71 /* cb_lookup relies on memcmp on the struct, so order matters: */
72 klen += BUILD_ASSERT_OR_ZERO(offsetof(struct object_id, hash) <
73 offsetof(struct object_id, algo));
74
75 node = cb_lookup(&ot->tree, (const uint8_t *)&k, klen);
76 return node ? container_of(node, struct oidtree_node, base) : NULL;
77 }
78
79 bool oidtree_contains(struct oidtree *ot, const struct object_id *oid)
80 {
81 struct oidtree_node *node = oidtree_lookup(ot, oid);
82 return node ? 1 : 0;
83 }
84
85 void *oidtree_get(struct oidtree *ot, const struct object_id *oid)
86 {
87 struct oidtree_node *node = oidtree_lookup(ot, oid);
88 return node ? node->data : NULL;
89 }
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 {
101 struct oidtree_node *node = container_of(n, struct oidtree_node, base);
102 struct oidtree_each_data *data = cb_data;
103
104 if (data->algo != GIT_HASH_UNKNOWN && data->algo != node->key.algo)
105 return 0;
106
107 if (data->last_nibble_at) {
108 if ((node->key.hash[*data->last_nibble_at] ^ data->last_byte) & 0xf0)
109 return 0;
110 }
111
112 return data->cb(&node->key, node->data, data->cb_data);
113 }
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 {
118 struct oidtree_each_data data = {
119 .cb = cb,
120 .cb_data = cb_data,
121 .algo = prefix->algo,
122 };
123 size_t klen = prefix_hex_len / 2;
124 assert(prefix_hex_len <= GIT_MAX_HEXSZ);
125
126 if (prefix_hex_len & 1) {
127 data.last_byte = prefix->hash[klen];
128 data.last_nibble_at = &klen;
129 }
130
131 return cb_each(&ot->tree, prefix->hash, klen, iter, &data);
132 }