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_type; 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 } ATTR_PACKED; 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_type len; 62 /** node that deals with byte+str */ 63 struct radnode* node; 64 } ATTR_PACKED; 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, 103 radstrlen_type len, 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, 121 radstrlen_type len); 122 123 /** 124 * Find radix element in tree, and if not found, find the closest smaller or 125 * equal element in the tree. 126 * @param rt: the radix tree. 127 * @param key: key string. 128 * @param len: length of key. 129 * @param result: returns the radix node or closest match (NULL if key is 130 * smaller than the smallest key in the tree). 131 * @return true if exact match, false if no match. 132 */ 133 int radix_find_less_equal(struct radtree* rt, uint8_t* k, radstrlen_type len, 134 struct radnode** result); 135 136 /** 137 * Return the first (smallest) element in the tree. 138 * @param rt: the radix tree. 139 * @return: first node or NULL if none. 140 */ 141 struct radnode* radix_first(struct radtree* rt); 142 143 /** 144 * Return the last (largest) element in the tree. 145 * @param rt: the radix tree. 146 * @return: last node or NULL if none. 147 */ 148 struct radnode* radix_last(struct radtree* rt); 149 150 /** 151 * Return the next element. 152 * @param n: the element to go from. 153 * @return: next node or NULL if none. 154 */ 155 struct radnode* radix_next(struct radnode* n); 156 157 /** 158 * Return the previous element. 159 * @param n: the element to go from. 160 * @return: prev node or NULL if none. 161 */ 162 struct radnode* radix_prev(struct radnode* n); 163 164 /* 165 * Perform a walk through all elements of the tree. 166 * node: variable of type struct radnode*. 167 * tree: pointer to the tree. 168 * for(node=radix_first(tree); node; node=radix_next(node)) 169 */ 170 171 /** 172 * Create a binary string to represent a domain name 173 * @param k: string buffer to store into 174 * @param len: output length, initially, the max, output the result. 175 * @param dname: the domain name to convert, in wireformat. 176 * @param dlen: length of space for dname. 177 */ 178 void radname_d2r(uint8_t* k, radstrlen_type* len, const uint8_t* dname, 179 size_t dlen); 180 181 /** 182 * Convert a binary string back to a domain name. 183 * @param k: the binary string. 184 * @param len: length of k. 185 * @param dname: buffer to store domain name into. 186 * @param dlen: length of dname (including root label). 187 */ 188 void radname_r2d(uint8_t* k, radstrlen_type len, uint8_t* dname, size_t* dlen); 189 190 /** 191 * Search the radix tree using a domain name. 192 * The name is internally converted to a radname. 193 * @param rt: tree 194 * @param d: domain name, no compression pointers allowed. 195 * @param max: max length to go from d. 196 * @return NULL on parse error or if not found. 197 */ 198 struct radnode* radname_search(struct radtree* rt, const uint8_t* d, 199 size_t max); 200 201 /** 202 * Find radix element in tree by domain name, and if not found, 203 * find the closest smaller or equal element in the tree. 204 * The name is internally converted to a radname (same sorting order). 205 * @param rt: the radix tree. 206 * @param d: domain name, no compression pointers allowed. 207 * @param max: max length to go from d. 208 * @param result: returns the radix node or closest match (NULL if key is 209 * smaller than the smallest key in the tree). 210 * could result in NULL on a parse error as well (with return false). 211 * @return true if exact match, false if no match. 212 */ 213 int radname_find_less_equal(struct radtree* rt, const uint8_t* d, size_t max, 214 struct radnode** result); 215 216 /** 217 * Insert radix element by domain name. 218 * @param rt: the radix tree 219 * @param d: domain name, no compression pointers. 220 * @param max: max length from d. 221 * @param elem: the element pointer to insert. 222 * @return NULL on failure - out of memory. 223 * NULL on failure - duplicate entry. 224 * NULL on failure - parse error. 225 * On success the radix node for this element. 226 */ 227 struct radnode* radname_insert(struct radtree* rt, const uint8_t* d, 228 size_t max, void* elem); 229 230 /** 231 * Delete element by domain name from radix tree. 232 * @param rt: the radix tree. 233 * @param d: the domain name. If it is not in the tree nothing happens. 234 * @param max: max length. 235 */ 236 void radname_delete(struct radtree* rt, const uint8_t* d, size_t max); 237 238 /** number of bytes in common in strings */ 239 radstrlen_type bstr_common_ext(uint8_t* x, radstrlen_type xlen, uint8_t* y, 240 radstrlen_type ylen); 241 /** true if one is prefix of the other */ 242 int bstr_is_prefix_ext(uint8_t* p, radstrlen_type plen, uint8_t* x, 243 radstrlen_type xlen); 244 245 #endif /* RADTREE_H */ 246