| 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 | { |
| 36 | struct cb_tree blank = { |
| 37 | .key_offset = key_offset, |
| 38 | }; |
| 39 | memcpy(t, &blank, sizeof(*t)); |
| 40 | } |
| 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 */ |