1 /* 2 * udbradtree -- radix tree for binary strings for in udb file. 3 * 4 * Copyright (c) 2011, NLnet Labs. See LICENSE for license. 5 */ 6 #ifndef UDB_RADTREE_H 7 #define UDB_RADTREE_H 8 #include "udb.h" 9 struct udb_radnode; 10 11 /** length of the binary string */ 12 typedef uint16_t udb_radstrlen_type; 13 14 /** 15 * The radix tree 16 * 17 * The elements are stored based on binary strings(0-255) of a given length. 18 * They are sorted, a prefix is sorted before its suffixes. 19 * If you want to know the key string, you should store it yourself, the 20 * tree stores it in the parts necessary for lookup. 21 * For binary strings for domain names see the radname routines. 22 * 23 * This is the tree on disk representation. It has _d suffix in the name 24 * to help delineate disk structures from normal structures. 25 */ 26 struct udb_radtree_d { 27 /** root node in tree, to udb_radnode_d */ 28 struct udb_rel_ptr root; 29 /** count of number of elements */ 30 uint64_t count; 31 }; 32 33 /** 34 * A radix tree lookup node. It is stored on disk, and the lookup array 35 * is allocated. 36 */ 37 struct udb_radnode_d { 38 /** data element associated with the binary string up to this node */ 39 struct udb_rel_ptr elem; 40 /** parent node (NULL for the root), to udb_radnode_d */ 41 struct udb_rel_ptr parent; 42 /** the array structure, for lookup by [byte-offset]. udb_radarray_d */ 43 struct udb_rel_ptr lookup; 44 /** index in the parent lookup array */ 45 uint8_t pidx; 46 /** offset of the lookup array, add to [i] for lookups */ 47 uint8_t offset; 48 }; 49 50 /** 51 * radix select edge in array 52 * The string for this element is the Nth string in the stringarray. 53 */ 54 struct udb_radsel_d { 55 /** length of the additional string for this edge, 56 * additional string after the selection-byte for this edge.*/ 57 udb_radstrlen_type len; 58 /** padding for non64bit compilers to 64bit boundaries, to make 59 * the udb file more portable, without this the file would work 60 * on the system it is created on (which is what we promise), but 61 * with this, you have a chance of it working on other platforms */ 62 uint16_t padding16; 63 uint32_t padding32; 64 /** node that deals with byte+str, to udb_radnode_d */ 65 struct udb_rel_ptr node; 66 }; 67 68 /** 69 * Array of radsel elements. 70 * This is the header, the array is allocated contiguously behind it. 71 * The strings (often very short) are allocated behind the array. 72 * All strings are given the same amount of space (str_cap), 73 * so there is capacity*str_cap bytes at the end. 74 */ 75 struct udb_radarray_d { 76 /** length of the lookup array */ 77 uint16_t len; 78 /** capacity of the lookup array (can be larger than length) */ 79 uint16_t capacity; 80 /** space capacity of for every string */ 81 udb_radstrlen_type str_cap; 82 /** padding to 64bit alignment, just in case compiler goes mad */ 83 uint16_t padding; 84 /** the elements (allocated contiguously after this structure) */ 85 struct udb_radsel_d array[0]; 86 }; 87 88 /** 89 * Create new radix tree on udb storage 90 * @param udb: the udb to allocate space on. 91 * @param ptr: ptr to the udbradtree is returned here. Pass uninitialised. 92 * type is udb_radtree_d. 93 * @return 0 on alloc failure. 94 */ 95 int udb_radix_tree_create(udb_base* udb, udb_ptr* ptr); 96 97 /** 98 * Delete intermediate nodes from radix tree 99 * @param udb: the udb. 100 * @param rt: radix tree to be cleared. type udb_radtree_d. 101 */ 102 void udb_radix_tree_clear(udb_base* udb, udb_ptr* rt); 103 104 /** 105 * Delete radix tree. 106 * You must have deleted the elements, this deletes the nodes. 107 * @param udb: the udb. 108 * @param rt: radix tree to be deleted. type udb_radtree_d. 109 */ 110 void udb_radix_tree_delete(udb_base* udb, udb_ptr* rt); 111 112 /** 113 * Insert element into radix tree. 114 * @param udb: the udb. 115 * @param rt: the radix tree, type udb_radtree_d. 116 * @param key: key string. 117 * @param len: length of key. 118 * @param elem: pointer to element data, on the udb store. 119 * @param result: the inserted node is set to this value. Pass uninitialised. 120 Not set if the routine fails. 121 * @return NULL on failure - out of memory. 122 * NULL on failure - duplicate entry. 123 * On success the new radix node for this element (udb_radnode_d). 124 */ 125 udb_void udb_radix_insert(udb_base* udb, udb_ptr* rt, uint8_t* k, 126 udb_radstrlen_type len, udb_ptr* elem, udb_ptr* result); 127 128 /** 129 * Delete element from radix tree. 130 * @param udb: the udb. 131 * @param rt: the radix tree. type udb_radtree_d 132 * @param n: radix node for that element. type udb_radnode_d 133 * if NULL, nothing is deleted. 134 */ 135 void udb_radix_delete(udb_base* udb, udb_ptr* rt, udb_ptr* n); 136 137 /** 138 * Find radix element in tree. 139 * @param rt: the radix tree, type udb_radtree_d. 140 * @param key: key string. 141 * @param len: length of key. 142 * @return the radix node or NULL if not found. type udb_radnode_d 143 */ 144 udb_void udb_radix_search(udb_ptr* rt, uint8_t* k, 145 udb_radstrlen_type len); 146 147 /** 148 * Find radix element in tree, and if not found, find the closest smaller or 149 * equal element in the tree. 150 * @param udb: the udb. 151 * @param rt: the radix tree, type udb_radtree_d. 152 * @param key: key string. 153 * @param len: length of key. 154 * @param result: returns the radix node or closest match (NULL if key is 155 * smaller than the smallest key in the tree). type udb_radnode_d. 156 * you can pass an uninitialized ptr, an unlinked or a zeroed one. 157 * @return true if exact match, false if no match. 158 */ 159 int udb_radix_find_less_equal(udb_base* udb, udb_ptr* rt, uint8_t* k, 160 udb_radstrlen_type len, udb_ptr* result); 161 162 /** 163 * Return the first (smallest) element in the tree. 164 * @param udb: the udb. 165 * @param rt: the radix tree, type udb_radtree_d. 166 * @param p: set to the first node in the tree, or NULL if none. 167 * type udb_radnode_d. 168 * pass uninitialised, zero or unlinked udb_ptr. 169 */ 170 void udb_radix_first(udb_base* udb, udb_ptr* rt, udb_ptr* p); 171 172 /** 173 * Return the last (largest) element in the tree. 174 * @param udb: the udb. 175 * @param rt: the radix tree, type udb_radtree_d. 176 * @param p: last node or NULL if none, type udb_radnode_d. 177 * pass uninitialised, zero or unlinked udb_ptr. 178 */ 179 void udb_radix_last(udb_base* udb, udb_ptr* rt, udb_ptr* p); 180 181 /** 182 * Return the next element. 183 * @param udb: the udb. 184 * @param n: adjusted to the next element, or NULL if none. type udb_radnode_d. 185 */ 186 void udb_radix_next(udb_base* udb, udb_ptr* n); 187 188 /** 189 * Return the previous element. 190 * @param udb: the udb. 191 * @param n: adjusted to the prev node or NULL if none. type udb_radnode_d. 192 */ 193 void udb_radix_prev(udb_base* udb, udb_ptr* n); 194 195 /* 196 * Perform a walk through all elements of the tree. 197 * node: variable of type struct radnode*. 198 * tree: pointer to the tree. 199 * for(udb_radix_first(tree, node); node->data; udb_radix_next(node)) 200 */ 201 202 /** for use in udb-walkfunc, walks relptrs in udb_chunk_type_radtree */ 203 void udb_radix_tree_walk_chunk(void* base, void* d, uint64_t s, 204 udb_walk_relptr_cb* cb, void* arg); 205 206 /** for use in udb-walkfunc, walks relptrs in udb_chunk_type_radnode */ 207 void udb_radix_node_walk_chunk(void* base, void* d, uint64_t s, 208 udb_walk_relptr_cb* cb, void* arg); 209 210 /** for use in udb-walkfunc, walks relptrs in udb_chunk_type_radarray */ 211 void udb_radix_array_walk_chunk(void* base, void* d, uint64_t s, 212 udb_walk_relptr_cb* cb, void* arg); 213 214 /** get the memory used by the lookup structure for a radnode */ 215 size_t size_of_lookup_ext(udb_ptr* node); 216 217 /** insert radtree element, key is a domain name 218 * @param udb: udb. 219 * @param rt: the tree. 220 * @param dname: domain name in uncompressed wireformat. 221 * @param dlen: length of k. 222 * @param elem: element to store 223 * @param result: the inserted node is set to this value. Pass uninitialised. 224 Not set if the routine fails. 225 * @return 0 on failure 226 */ 227 udb_void udb_radname_insert(udb_base* udb, udb_ptr* rt, const uint8_t* dname, 228 size_t dlen, udb_ptr* elem, udb_ptr* result); 229 230 /** search for a radname element, key is a domain name. 231 * @param udb: udb 232 * @param rt: the tree 233 * @param dname: domain name in uncompressed wireformat. 234 * @param dlen: length of k. 235 * @param result: result ptr to store the node into. 236 * may be uninitialized. 237 * @return 0 if not found. 238 */ 239 int udb_radname_search(udb_base* udb, udb_ptr* rt, const uint8_t* dname, 240 size_t dlen, udb_ptr* result); 241 242 #define RADNODE(ptr) ((struct udb_radnode_d*)UDB_PTR(ptr)) 243 #define RADTREE(ptr) ((struct udb_radtree_d*)UDB_PTR(ptr)) 244 245 #endif /* UDB_RADTREE_H */ 246