| 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 | } |