]>
Commit | Line | Data |
---|---|---|
92d8ed8a EW |
1 | /* |
2 | * crit-bit tree implementation, does no allocations internally | |
3 | * For more information on crit-bit trees: https://cr.yp.to/critbit.html | |
4 | * Based on Adam Langley's adaptation of Dan Bernstein's public domain code | |
5 | * git clone https://github.com/agl/critbit.git | |
6 | * | |
7 | * This is adapted to store arbitrary data (not just NUL-terminated C strings | |
8 | * and allocates no memory internally. The user needs to allocate | |
9 | * "struct cb_node" and fill cb_node.k[] with arbitrary match data | |
10 | * for memcmp. | |
11 | * If "klen" is variable, then it should be embedded into "c_node.k[]" | |
12 | * Recursion is bound by the maximum value of "klen" used. | |
13 | */ | |
14 | #ifndef CBTREE_H | |
15 | #define CBTREE_H | |
16 | ||
17 | #include "git-compat-util.h" | |
18 | ||
19 | struct cb_node; | |
20 | struct cb_node { | |
21 | struct cb_node *child[2]; | |
22 | /* | |
23 | * n.b. uint32_t for `byte' is excessive for OIDs, | |
24 | * we may consider shorter variants if nothing else gets stored. | |
25 | */ | |
26 | uint32_t byte; | |
27 | uint8_t otherbits; | |
8bcda98d | 28 | uint8_t k[FLEX_ARRAY]; /* arbitrary data, unaligned */ |
92d8ed8a EW |
29 | }; |
30 | ||
31 | struct cb_tree { | |
32 | struct cb_node *root; | |
33 | }; | |
34 | ||
35 | enum cb_next { | |
36 | CB_CONTINUE = 0, | |
37 | CB_BREAK = 1 | |
38 | }; | |
39 | ||
538835d2 | 40 | #define CBTREE_INIT { 0 } |
92d8ed8a EW |
41 | |
42 | static inline void cb_init(struct cb_tree *t) | |
43 | { | |
538835d2 ÆAB |
44 | struct cb_tree blank = CBTREE_INIT; |
45 | memcpy(t, &blank, sizeof(*t)); | |
92d8ed8a EW |
46 | } |
47 | ||
48 | struct cb_node *cb_lookup(struct cb_tree *, const uint8_t *k, size_t klen); | |
49 | struct cb_node *cb_insert(struct cb_tree *, struct cb_node *, size_t klen); | |
92d8ed8a EW |
50 | |
51 | typedef enum cb_next (*cb_iter)(struct cb_node *, void *arg); | |
52 | ||
53 | void cb_each(struct cb_tree *, const uint8_t *kpfx, size_t klen, | |
54 | cb_iter, void *arg); | |
55 | ||
56 | #endif /* CBTREE_H */ |