FilesExpand file tree

master

/

cbtree.h

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

56 lines (49 loc) · 1.72 KB

master

/

cbtree.h

Copy path

Top

File metadata and controls

• Code
• Blame

56 lines (49 loc) · 1.72 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

/*

* crit-bit tree implementation, does no allocations internally

* For more information on crit-bit trees: https://cr.yp.to/critbit.html

* Based on Adam Langley's adaptation of Dan Bernstein's public domain code

* git clone https://github.com/agl/critbit.git

*

* This is adapted to store arbitrary data (not just NUL-terminated C strings

* and allocates no memory internally. The user needs to allocate

* "struct cb_node" and provide `key_offset` to indicate where the key can be

* found relative to the `struct cb_node` for memcmp.

* If "klen" is variable, then it should be embedded into the key.

* Recursion is bound by the maximum value of "klen" used.

*/

#ifndef CBTREE_H

#define CBTREE_H

struct cb_node;

struct cb_node {

struct cb_node *child[2];

/*

* n.b. uint32_t for `byte' is excessive for OIDs,

* we may consider shorter variants if nothing else gets stored.

*/

uint32_t byte;

uint8_t otherbits;

};

struct cb_tree {

struct cb_node *root;

ptrdiff_t key_offset;

};

static inline void cb_init(struct cb_tree *t,

ptrdiff_t key_offset)

{

struct cb_tree blank = {

.key_offset = key_offset,

};

memcpy(t, &blank, sizeof(*t));

}

struct cb_node *cb_lookup(struct cb_tree *, const uint8_t *k, size_t klen);

struct cb_node *cb_insert(struct cb_tree *, struct cb_node *, size_t klen);

/*

* Callback invoked by `cb_each()` for each node in the critbit tree. A return

* value of 0 will cause the iteration to continue, a non-zero return code will

* cause iteration to abort. The error code will be relayed back from

* `cb_each()` in that case.

*/

typedef int (*cb_iter)(struct cb_node *, void *arg);

int cb_each(struct cb_tree *, const uint8_t *kpfx, size_t klen,

cb_iter, void *arg);

#endif /* CBTREE_H */