1 /* 2 * util/storage/dnstree.h - support for rbtree types suitable for DNS code. 3 * 4 * Copyright (c) 2008, NLnet Labs. All rights reserved. 5 * 6 * This software is open source. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 12 * Redistributions of source code must retain the above copyright notice, 13 * this list of conditions and the following disclaimer. 14 * 15 * Redistributions in binary form must reproduce the above copyright notice, 16 * this list of conditions and the following disclaimer in the documentation 17 * and/or other materials provided with the distribution. 18 * 19 * Neither the name of the NLNET LABS nor the names of its contributors may 20 * be used to endorse or promote products derived from this software without 21 * specific prior written permission. 22 * 23 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 24 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 25 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 26 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 27 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 28 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED 29 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 30 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 31 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 32 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 33 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 34 */ 35 36 /** 37 * \file 38 * 39 * This file contains structures combining types and functions to 40 * manipulate those structures that help building DNS lookup trees. 41 */ 42 43 #ifndef UTIL_STORAGE_DNSTREE_H 44 #define UTIL_STORAGE_DNSTREE_H 45 #include "util/rbtree.h" 46 47 /** 48 * Tree of domain names. Sorted first by class then by name. 49 * This is not sorted canonically, but fast. 50 * This can be looked up to obtain a closest encloser parent name. 51 * 52 * The tree itself is a rbtree_type. 53 * This is the element node put as first entry in the client structure. 54 */ 55 struct name_tree_node { 56 /** rbtree node, key is this struct : dclass and name */ 57 rbnode_type node; 58 /** parent in tree */ 59 struct name_tree_node* parent; 60 /** name in uncompressed wireformat */ 61 uint8_t* name; 62 /** length of name */ 63 size_t len; 64 /** labels in name */ 65 int labs; 66 /** the class of the name (host order) */ 67 uint16_t dclass; 68 }; 69 70 /** 71 * Tree of IP addresses. Sorted first by protocol, then by bits. 72 * This can be looked up to obtain the enclosing subnet. 73 * 74 * The tree itself is a rbtree_type. 75 * This is the element node put as first entry in the client structure. 76 */ 77 struct addr_tree_node { 78 /** rbtree node, key is this struct : proto and subnet */ 79 rbnode_type node; 80 /** parent in tree */ 81 struct addr_tree_node* parent; 82 /** address */ 83 struct sockaddr_storage addr; 84 /** length of addr */ 85 socklen_t addrlen; 86 /** netblock size */ 87 int net; 88 }; 89 90 /** 91 * Init a name tree to be empty 92 * @param tree: to init. 93 */ 94 void name_tree_init(rbtree_type* tree); 95 96 /** 97 * insert element into name tree. 98 * @param tree: name tree 99 * @param node: node element (at start of a structure that caller 100 * has allocated). 101 * @param name: name to insert (wireformat) 102 * this node has been allocated by the caller and it itself inserted. 103 * @param len: length of name 104 * @param labs: labels in name 105 * @param dclass: class of name 106 * @return false on error (duplicate element). 107 */ 108 int name_tree_insert(rbtree_type* tree, struct name_tree_node* node, 109 uint8_t* name, size_t len, int labs, uint16_t dclass); 110 111 /** 112 * Initialize parent pointers in name tree. 113 * Should be performed after insertions are done, before lookups 114 * @param tree: name tree 115 */ 116 void name_tree_init_parents(rbtree_type* tree); 117 118 /** 119 * Lookup exact match in name tree 120 * @param tree: name tree 121 * @param name: wireformat name 122 * @param len: length of name 123 * @param labs: labels in name 124 * @param dclass: class of name 125 * @return node or NULL if not found. 126 */ 127 struct name_tree_node* name_tree_find(rbtree_type* tree, uint8_t* name, 128 size_t len, int labs, uint16_t dclass); 129 130 /** 131 * Lookup closest encloser in name tree. 132 * @param tree: name tree 133 * @param name: wireformat name 134 * @param len: length of name 135 * @param labs: labels in name 136 * @param dclass: class of name 137 * @return closest enclosing node (could be equal) or NULL if not found. 138 */ 139 struct name_tree_node* name_tree_lookup(rbtree_type* tree, uint8_t* name, 140 size_t len, int labs, uint16_t dclass); 141 142 /** 143 * Find next root item in name tree. 144 * @param tree: the nametree. 145 * @param dclass: the class to look for next (or higher). 146 * @return false if no classes found, true means class put into c. 147 */ 148 int name_tree_next_root(rbtree_type* tree, uint16_t* dclass); 149 150 /** 151 * Init addr tree to be empty. 152 * @param tree: to init. 153 */ 154 void addr_tree_init(rbtree_type* tree); 155 156 /** 157 * Init addr tree to be empty. 158 * The comparison function to be used is addr_tree_addrport_compare. 159 * @param tree: to init. 160 */ 161 void addr_tree_addrport_init(rbtree_type* tree); 162 163 /** 164 * insert element into addr tree. 165 * @param tree: addr tree 166 * @param node: node element (at start of a structure that caller 167 * has allocated). 168 * @param addr: to insert (copied). 169 * @param addrlen: length of addr 170 * @param net: size of subnet. 171 * @return false on error (duplicate element). 172 */ 173 int addr_tree_insert(rbtree_type* tree, struct addr_tree_node* node, 174 struct sockaddr_storage* addr, socklen_t addrlen, int net); 175 176 /** 177 * Initialize parent pointers in addr tree. 178 * Should be performed after insertions are done, before lookups 179 * @param tree: addr tree 180 */ 181 void addr_tree_init_parents(rbtree_type* tree); 182 183 /** 184 * Initialize parent pointers in partial addr tree. 185 * Reinitialize pointer for part of tree, used after node deletion 186 * @param node: node to start parent pointer initialization for. 187 */ 188 void addr_tree_init_parents_node(struct addr_tree_node* node); 189 190 /** 191 * Lookup closest encloser in addr tree. 192 * @param tree: addr tree 193 * @param addr: to lookup. 194 * @param addrlen: length of addr 195 * @return closest enclosing node (could be equal) or NULL if not found. 196 */ 197 struct addr_tree_node* addr_tree_lookup(rbtree_type* tree, 198 struct sockaddr_storage* addr, socklen_t addrlen); 199 200 /** 201 * Find element in addr tree. (search a netblock, not a match for an address) 202 * @param tree: addr tree 203 * @param addr: netblock to lookup. 204 * @param addrlen: length of addr 205 * @param net: size of subnet 206 * @return addr tree element, or NULL if not found. 207 */ 208 struct addr_tree_node* addr_tree_find(rbtree_type* tree, 209 struct sockaddr_storage* addr, socklen_t addrlen, int net); 210 211 /** compare name tree nodes */ 212 int name_tree_compare(const void* k1, const void* k2); 213 214 /** compare addr tree nodes */ 215 int addr_tree_compare(const void* k1, const void* k2); 216 217 /** compare addr tree nodes (address and port only) */ 218 int addr_tree_addrport_compare(const void* k1, const void* k2); 219 220 #endif /* UTIL_STORAGE_DNSTREE_H */ 221