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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
|
/*
* radtree -- generic radix tree for binary strings.
*
* Copyright (c) 2010, NLnet Labs. See LICENSE for license.
*/
#ifndef RADTREE_H
#define RADTREE_H
struct radnode;
struct region;
/** length of the binary string */
typedef uint16_t radstrlen_type;
/**
* The radix tree
*
* The elements are stored based on binary strings(0-255) of a given length.
* They are sorted, a prefix is sorted before its suffixes.
* If you want to know the key string, you should store it yourself, the
* tree stores it in the parts necessary for lookup.
* For binary strings for domain names see the radname routines.
*/
struct radtree {
/** root node in tree */
struct radnode* root;
/** count of number of elements */
size_t count;
/** region for allocation */
struct region* region;
};
/**
* A radix tree lookup node.
* The array is malloced separately from the radnode.
*/
struct radnode {
/** data element associated with the binary string up to this node */
void* elem;
/** parent node (NULL for the root) */
struct radnode* parent;
/** index in the parent lookup array */
uint8_t pidx;
/** offset of the lookup array, add to [i] for lookups */
uint8_t offset;
/** length of the lookup array */
uint16_t len;
/** capacity of the lookup array (can be larger than length) */
uint16_t capacity;
/** the lookup array by [byte-offset] */
struct radsel* array;
} ATTR_PACKED;
/**
* radix select edge in array
*/
struct radsel {
/** additional string after the selection-byte for this edge. */
uint8_t* str;
/** length of the additional string for this edge */
radstrlen_type len;
/** node that deals with byte+str */
struct radnode* node;
} ATTR_PACKED;
/**
* Create new radix tree
* @param region: where to allocate the tree.
* @return new tree or NULL on alloc failure.
*/
struct radtree* radix_tree_create(struct region* region);
/**
* Init new radix tree.
* @param rt: radix tree to be initialized.
*/
void radix_tree_init(struct radtree* rt);
/**
* Delete intermediate nodes from radix tree
* @param rt: radix tree to be initialized.
*/
void radix_tree_clear(struct radtree* rt);
/**
* Delete radix tree.
* @param rt: radix tree to be deleted.
*/
void radix_tree_delete(struct radtree* rt);
/**
* Insert element into radix tree.
* @param rt: the radix tree.
* @param key: key string.
* @param len: length of key.
* @param elem: pointer to element data.
* @return NULL on failure - out of memory.
* NULL on failure - duplicate entry.
* On success the new radix node for this element.
*/
struct radnode* radix_insert(struct radtree* rt, uint8_t* k,
radstrlen_type len, void* elem);
/**
* Delete element from radix tree.
* @param rt: the radix tree.
* @param n: radix node for that element.
* if NULL, nothing is deleted.
*/
void radix_delete(struct radtree* rt, struct radnode* n);
/**
* Find radix element in tree.
* @param rt: the radix tree.
* @param key: key string.
* @param len: length of key.
* @return the radix node or NULL if not found.
*/
struct radnode* radix_search(struct radtree* rt, uint8_t* k,
radstrlen_type len);
/**
* Find radix element in tree, and if not found, find the closest smaller or
* equal element in the tree.
* @param rt: the radix tree.
* @param key: key string.
* @param len: length of key.
* @param result: returns the radix node or closest match (NULL if key is
* smaller than the smallest key in the tree).
* @return true if exact match, false if no match.
*/
int radix_find_less_equal(struct radtree* rt, uint8_t* k, radstrlen_type len,
struct radnode** result);
/**
* Return the first (smallest) element in the tree.
* @param rt: the radix tree.
* @return: first node or NULL if none.
*/
struct radnode* radix_first(struct radtree* rt);
/**
* Return the last (largest) element in the tree.
* @param rt: the radix tree.
* @return: last node or NULL if none.
*/
struct radnode* radix_last(struct radtree* rt);
/**
* Return the next element.
* @param n: the element to go from.
* @return: next node or NULL if none.
*/
struct radnode* radix_next(struct radnode* n);
/**
* Return the previous element.
* @param n: the element to go from.
* @return: prev node or NULL if none.
*/
struct radnode* radix_prev(struct radnode* n);
/*
* Perform a walk through all elements of the tree.
* node: variable of type struct radnode*.
* tree: pointer to the tree.
* for(node=radix_first(tree); node; node=radix_next(node))
*/
/**
* Create a binary string to represent a domain name
* @param k: string buffer to store into
* @param len: output length, initially, the max, output the result.
* @param dname: the domain name to convert, in wireformat.
* @param dlen: length of space for dname.
*/
void radname_d2r(uint8_t* k, radstrlen_type* len, const uint8_t* dname,
size_t dlen);
/**
* Convert a binary string back to a domain name.
* @param k: the binary string.
* @param len: length of k.
* @param dname: buffer to store domain name into.
* @param dlen: length of dname (including root label).
*/
void radname_r2d(uint8_t* k, radstrlen_type len, uint8_t* dname, size_t* dlen);
/**
* Search the radix tree using a domain name.
* The name is internally converted to a radname.
* @param rt: tree
* @param d: domain name, no compression pointers allowed.
* @param max: max length to go from d.
* @return NULL on parse error or if not found.
*/
struct radnode* radname_search(struct radtree* rt, const uint8_t* d,
size_t max);
/**
* Find radix element in tree by domain name, and if not found,
* find the closest smaller or equal element in the tree.
* The name is internally converted to a radname (same sorting order).
* @param rt: the radix tree.
* @param d: domain name, no compression pointers allowed.
* @param max: max length to go from d.
* @param result: returns the radix node or closest match (NULL if key is
* smaller than the smallest key in the tree).
* could result in NULL on a parse error as well (with return false).
* @return true if exact match, false if no match.
*/
int radname_find_less_equal(struct radtree* rt, const uint8_t* d, size_t max,
struct radnode** result);
/**
* Insert radix element by domain name.
* @param rt: the radix tree
* @param d: domain name, no compression pointers.
* @param max: max length from d.
* @param elem: the element pointer to insert.
* @return NULL on failure - out of memory.
* NULL on failure - duplicate entry.
* NULL on failure - parse error.
* On success the radix node for this element.
*/
struct radnode* radname_insert(struct radtree* rt, const uint8_t* d,
size_t max, void* elem);
/**
* Delete element by domain name from radix tree.
* @param rt: the radix tree.
* @param d: the domain name. If it is not in the tree nothing happens.
* @param max: max length.
*/
void radname_delete(struct radtree* rt, const uint8_t* d, size_t max);
/** number of bytes in common in strings */
radstrlen_type bstr_common_ext(uint8_t* x, radstrlen_type xlen, uint8_t* y,
radstrlen_type ylen);
/** true if one is prefix of the other */
int bstr_is_prefix_ext(uint8_t* p, radstrlen_type plen, uint8_t* x,
radstrlen_type xlen);
#endif /* RADTREE_H */
|
