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