Line | Count | Source (jump to first uncovered line) |
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 | | struct cb_node; |
18 | | struct cb_node { |
19 | | struct cb_node *child[2]; |
20 | | /* |
21 | | * n.b. uint32_t for `byte' is excessive for OIDs, |
22 | | * we may consider shorter variants if nothing else gets stored. |
23 | | */ |
24 | | uint32_t byte; |
25 | | uint8_t otherbits; |
26 | | uint8_t k[FLEX_ARRAY]; /* arbitrary data, unaligned */ |
27 | | }; |
28 | | |
29 | | struct cb_tree { |
30 | | struct cb_node *root; |
31 | | }; |
32 | | |
33 | | enum cb_next { |
34 | | CB_CONTINUE = 0, |
35 | | CB_BREAK = 1 |
36 | | }; |
37 | | |
38 | 0 | #define CBTREE_INIT { 0 } |
39 | | |
40 | | static inline void cb_init(struct cb_tree *t) |
41 | 0 | { |
42 | 0 | struct cb_tree blank = CBTREE_INIT; |
43 | 0 | memcpy(t, &blank, sizeof(*t)); |
44 | 0 | } Unexecuted instantiation: object-file.c:cb_init Unexecuted instantiation: object-name.c:cb_init Unexecuted instantiation: oidtree.c:cb_init Unexecuted instantiation: cbtree.c:cb_init Unexecuted instantiation: loose.c:cb_init |
45 | | |
46 | | struct cb_node *cb_lookup(struct cb_tree *, const uint8_t *k, size_t klen); |
47 | | struct cb_node *cb_insert(struct cb_tree *, struct cb_node *, size_t klen); |
48 | | |
49 | | typedef enum cb_next (*cb_iter)(struct cb_node *, void *arg); |
50 | | |
51 | | void cb_each(struct cb_tree *, const uint8_t *kpfx, size_t klen, |
52 | | cb_iter, void *arg); |
53 | | |
54 | | #endif /* CBTREE_H */ |