]>
git.ipfire.org Git - thirdparty/git.git/blob - oidtree.c
2 * A wrapper around cbtree which stores oids
3 * May be used to replace oid-array for prefix (abbreviation) matches
9 struct oidtree_iter_data
{
12 size_t *last_nibble_at
;
17 void oidtree_init(struct oidtree
*ot
)
20 mem_pool_init(&ot
->mem_pool
, 0);
23 void oidtree_clear(struct oidtree
*ot
)
26 mem_pool_discard(&ot
->mem_pool
, 0);
31 void oidtree_insert(struct oidtree
*ot
, const struct object_id
*oid
)
37 BUG("oidtree_insert requires oid->algo");
39 on
= mem_pool_alloc(&ot
->mem_pool
, sizeof(*on
) + sizeof(*oid
));
42 * Clear the padding and copy the result in separate steps to
43 * respect the 4-byte alignment needed by struct object_id.
45 oidcpy_with_padding(&k
, oid
);
46 memcpy(on
->k
, &k
, sizeof(k
));
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
54 cb_insert(&ot
->tree
, on
, sizeof(*oid
));
58 int oidtree_contains(struct oidtree
*ot
, const struct object_id
*oid
)
61 size_t klen
= sizeof(k
);
63 oidcpy_with_padding(&k
, oid
);
65 if (oid
->algo
== GIT_HASH_UNKNOWN
)
66 klen
-= sizeof(oid
->algo
);
68 /* cb_lookup relies on memcmp on the struct, so order matters: */
69 klen
+= BUILD_ASSERT_OR_ZERO(offsetof(struct object_id
, hash
) <
70 offsetof(struct object_id
, algo
));
72 return cb_lookup(&ot
->tree
, (const uint8_t *)&k
, klen
) ? 1 : 0;
75 static enum cb_next
iter(struct cb_node
*n
, void *arg
)
77 struct oidtree_iter_data
*x
= arg
;
80 /* Copy to provide 4-byte alignment needed by struct object_id. */
81 memcpy(&k
, n
->k
, sizeof(k
));
83 if (x
->algo
!= GIT_HASH_UNKNOWN
&& x
->algo
!= k
.algo
)
86 if (x
->last_nibble_at
) {
87 if ((k
.hash
[*x
->last_nibble_at
] ^ x
->last_byte
) & 0xf0)
91 return x
->fn(&k
, x
->arg
);
94 void oidtree_each(struct oidtree
*ot
, const struct object_id
*oid
,
95 size_t oidhexsz
, oidtree_iter fn
, void *arg
)
97 size_t klen
= oidhexsz
/ 2;
98 struct oidtree_iter_data x
= { 0 };
99 assert(oidhexsz
<= GIT_MAX_HEXSZ
);
105 x
.last_byte
= oid
->hash
[klen
];
106 x
.last_nibble_at
= &klen
;
108 cb_each(&ot
->tree
, (const uint8_t *)oid
, klen
, iter
, &x
);