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
|
/*
* udbradtree -- radix tree for binary strings for in udb file.
*
* Copyright (c) 2011, NLnet Labs. See LICENSE for license.
*/
#ifndef UDB_RADTREE_H
#define UDB_RADTREE_H
#include "udb.h"
struct udb_radnode;
/** length of the binary string */
typedef uint16_t udb_radstrlen_t;
/**
* 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.
*
* This is the tree on disk representation. It has _d suffix in the name
* to help delineate disk structures from normal structures.
*/
struct udb_radtree_d {
/** root node in tree, to udb_radnode_d */
struct udb_rel_ptr root;
/** count of number of elements */
uint64_t count;
};
/**
* A radix tree lookup node. It is stored on disk, and the lookup array
* is allocated.
*/
struct udb_radnode_d {
/** data element associated with the binary string up to this node */
struct udb_rel_ptr elem;
/** parent node (NULL for the root), to udb_radnode_d */
struct udb_rel_ptr parent;
/** the array structure, for lookup by [byte-offset]. udb_radarray_d */
struct udb_rel_ptr lookup;
/** index in the parent lookup array */
uint8_t pidx;
/** offset of the lookup array, add to [i] for lookups */
uint8_t offset;
};
/**
* radix select edge in array
* The string for this element is the Nth string in the stringarray.
*/
struct udb_radsel_d {
/** length of the additional string for this edge,
* additional string after the selection-byte for this edge.*/
udb_radstrlen_t len;
/** padding for non64bit compilers to 64bit boundaries, to make
* the udb file more portable, without this the file would work
* on the system it is created on (which is what we promise), but
* with this, you have a chance of it working on other platforms */
uint16_t padding16;
uint32_t padding32;
/** node that deals with byte+str, to udb_radnode_d */
struct udb_rel_ptr node;
};
/**
* Array of radsel elements.
* This is the header, the array is allocated contiguously behind it.
* The strings (often very short) are allocated behind the array.
* All strings are given the same amount of space (str_cap),
* so there is capacity*str_cap bytes at the end.
*/
struct udb_radarray_d {
/** length of the lookup array */
uint16_t len;
/** capacity of the lookup array (can be larger than length) */
uint16_t capacity;
/** space capacity of for every string */
udb_radstrlen_t str_cap;
/** padding to 64bit alignment, just in case compiler goes mad */
uint16_t padding;
/** the elements (allocated contiguously after this structure) */
struct udb_radsel_d array[0];
};
/**
* Create new radix tree on udb storage
* @param udb: the udb to allocate space on.
* @param ptr: ptr to the udbradtree is returned here. pass uninitialised.
* type is udb_radtree_d.
* @return 0 on alloc failure.
*/
int udb_radix_tree_create(udb_base* udb, udb_ptr* ptr);
/**
* Delete intermediate nodes from radix tree
* @param udb: the udb.
* @param rt: radix tree to be cleared. type udb_radtree_d.
*/
void udb_radix_tree_clear(udb_base* udb, udb_ptr* rt);
/**
* Delete radix tree.
* You must have deleted the elements, this deletes the nodes.
* @param udb: the udb.
* @param rt: radix tree to be deleted. type udb_radtree_d.
*/
void udb_radix_tree_delete(udb_base* udb, udb_ptr* rt);
/**
* Insert element into radix tree.
* @param udb: the udb.
* @param rt: the radix tree, type udb_radtree_d.
* @param key: key string.
* @param len: length of key.
* @param elem: pointer to element data, on the udb store.
* @param result: the inserted node is set to this value. Pass uninited.
Not set if the routine fails.
* @return NULL on failure - out of memory.
* NULL on failure - duplicate entry.
* On success the new radix node for this element (udb_radnode_d).
*/
udb_void udb_radix_insert(udb_base* udb, udb_ptr* rt, uint8_t* k,
udb_radstrlen_t len, udb_ptr* elem, udb_ptr* result);
/**
* Delete element from radix tree.
* @param udb: the udb.
* @param rt: the radix tree. type udb_radtree_d
* @param n: radix node for that element. type udb_radnode_d
* if NULL, nothing is deleted.
*/
void udb_radix_delete(udb_base* udb, udb_ptr* rt, udb_ptr* n);
/**
* Find radix element in tree.
* @param rt: the radix tree, type udb_radtree_d.
* @param key: key string.
* @param len: length of key.
* @return the radix node or NULL if not found. type udb_radnode_d
*/
udb_void udb_radix_search(udb_ptr* rt, uint8_t* k,
udb_radstrlen_t len);
/**
* Find radix element in tree, and if not found, find the closest smaller or
* equal element in the tree.
* @param udb: the udb.
* @param rt: the radix tree, type udb_radtree_d.
* @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). type udb_radnode_d.
* you can pass an uninitialized ptr, an unlinked or a zeroed one.
* @return true if exact match, false if no match.
*/
int udb_radix_find_less_equal(udb_base* udb, udb_ptr* rt, uint8_t* k,
udb_radstrlen_t len, udb_ptr* result);
/**
* Return the first (smallest) element in the tree.
* @param udb: the udb.
* @param rt: the radix tree, type udb_radtree_d.
* @param p: set to the first node in the tree, or NULL if none.
* type udb_radnode_d.
* pass uninited, zero or unlinked udb_ptr.
*/
void udb_radix_first(udb_base* udb, udb_ptr* rt, udb_ptr* p);
/**
* Return the last (largest) element in the tree.
* @param udb: the udb.
* @param rt: the radix tree, type udb_radtree_d.
* @param p: last node or NULL if none, type udb_radnode_d.
* pass uninited, zero or unlinked udb_ptr.
*/
void udb_radix_last(udb_base* udb, udb_ptr* rt, udb_ptr* p);
/**
* Return the next element.
* @param udb: the udb.
* @param n: adjusted to the next element, or NULL if none. type udb_radnode_d.
*/
void udb_radix_next(udb_base* udb, udb_ptr* n);
/**
* Return the previous element.
* @param udb: the udb.
* @param n: adjusted to the prev node or NULL if none. type udb_radnode_d.
*/
void udb_radix_prev(udb_base* udb, udb_ptr* n);
/*
* Perform a walk through all elements of the tree.
* node: variable of type struct radnode*.
* tree: pointer to the tree.
* for(udb_radix_first(tree, node); node->data; udb_radix_next(node))
*/
/** for use in udb-walkfunc, walks relptrs in udb_chunk_type_radtree */
void udb_radix_tree_walk_chunk(void* base, void* d, uint64_t s,
udb_walk_relptr_cb* cb, void* arg);
/** for use in udb-walkfunc, walks relptrs in udb_chunk_type_radnode */
void udb_radix_node_walk_chunk(void* base, void* d, uint64_t s,
udb_walk_relptr_cb* cb, void* arg);
/** for use in udb-walkfunc, walks relptrs in udb_chunk_type_radarray */
void udb_radix_array_walk_chunk(void* base, void* d, uint64_t s,
udb_walk_relptr_cb* cb, void* arg);
/** get the memory used by the lookup structure for a radnode */
size_t size_of_lookup_ext(udb_ptr* node);
/** insert radtree element, key is a domain name
* @param udb: udb.
* @param rt: the tree.
* @param dname: domain name in uncompressed wireformat.
* @param dlen: length of k.
* @param elem: element to store
* @param result: the inserted node is set to this value. Pass uninited.
Not set if the routine fails.
* @return 0 on failure
*/
udb_void udb_radname_insert(udb_base* udb, udb_ptr* rt, const uint8_t* dname,
size_t dlen, udb_ptr* elem, udb_ptr* result);
/** search for a radname element, key is a domain name.
* @param udb: udb
* @param rt: the tree
* @param dname: domain name in uncompressed wireformat.
* @param dlen: length of k.
* @param result: result ptr to store the node into.
* may be uninitialized.
* @return 0 if not found.
*/
int udb_radname_search(udb_base* udb, udb_ptr* rt, const uint8_t* dname,
size_t dlen, udb_ptr* result);
#define RADNODE(ptr) ((struct udb_radnode_d*)UDB_PTR(ptr))
#define RADTREE(ptr) ((struct udb_radtree_d*)UDB_PTR(ptr))
#endif /* UDB_RADTREE_H */
|
