FilesExpand file tree

master

/

cbtree.h

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

54 lines (45 loc) · 1.48 KB

master

/

cbtree.h

Copy path

Top

File metadata and controls

• Code
• Blame

54 lines (45 loc) · 1.48 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

/*

* 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 fill cb_node.k[] with arbitrary match data

* for memcmp.

* If "klen" is variable, then it should be embedded into "c_node.k[]"

* 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;

uint8_t k[FLEX_ARRAY]; /* arbitrary data, unaligned */

};

struct cb_tree {

struct cb_node *root;

};

enum cb_next {

CB_CONTINUE = 0,

CB_BREAK = 1

};

#define CBTREE_INIT { 0 }

static inline void cb_init(struct cb_tree *t)

{

struct cb_tree blank = CBTREE_INIT;

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);

typedef enum cb_next (*cb_iter)(struct cb_node *, void *arg);

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

cb_iter, void *arg);

#endif /* CBTREE_H */