Line | Count | Source |
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 provide `key_offset` to indicate where the key can be |
10 | | * found relative to the `struct cb_node` for memcmp. |
11 | | * If "klen" is variable, then it should be embedded into the key. |
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 | | }; |
27 | | |
28 | | struct cb_tree { |
29 | | struct cb_node *root; |
30 | | ptrdiff_t key_offset; |
31 | | }; |
32 | | |
33 | | static inline void cb_init(struct cb_tree *t, |
34 | | ptrdiff_t key_offset) |
35 | 0 | { |
36 | 0 | struct cb_tree blank = { |
37 | 0 | .key_offset = key_offset, |
38 | 0 | }; |
39 | 0 | memcpy(t, &blank, sizeof(*t)); |
40 | 0 | } Unexecuted instantiation: source-inmemory.c:cb_init Unexecuted instantiation: source-loose.c:cb_init Unexecuted instantiation: oidtree.c:cb_init Unexecuted instantiation: cbtree.c:cb_init Unexecuted instantiation: loose.c:cb_init |
41 | | |
42 | | struct cb_node *cb_lookup(struct cb_tree *, const uint8_t *k, size_t klen); |
43 | | struct cb_node *cb_insert(struct cb_tree *, struct cb_node *, size_t klen); |
44 | | |
45 | | /* |
46 | | * Callback invoked by `cb_each()` for each node in the critbit tree. A return |
47 | | * value of 0 will cause the iteration to continue, a non-zero return code will |
48 | | * cause iteration to abort. The error code will be relayed back from |
49 | | * `cb_each()` in that case. |
50 | | */ |
51 | | typedef int (*cb_iter)(struct cb_node *, void *arg); |
52 | | |
53 | | int cb_each(struct cb_tree *, const uint8_t *kpfx, size_t klen, |
54 | | cb_iter, void *arg); |
55 | | |
56 | | #endif /* CBTREE_H */ |