unbound/util/storage/dnstree.h

   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_t.
  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_t 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_t.
  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_t 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_t* 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_t* 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_t* 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_t* 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_t* 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_t* 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_t* tree);
 155
 156 /**
 157  * insert element into addr tree.
 158  * @param tree: addr tree
 159  * @param node: node element (at start of a structure that caller
 160  *      has allocated).
 161  * @param addr: to insert (copied).
 162  * @param addrlen: length of addr
 163  * @param net: size of subnet.
 164  * @return false on error (duplicate element).
 165  */
 166 int addr_tree_insert(rbtree_t* tree, struct addr_tree_node* node,
 167         struct sockaddr_storage* addr, socklen_t addrlen, int net);
 168
 169 /**
 170  * Initialize parent pointers in addr tree.
 171  * Should be performed after insertions are done, before lookups
 172  * @param tree: addr tree
 173  */
 174 void addr_tree_init_parents(rbtree_t* tree);
 175
 176 /**
 177  * Lookup closest encloser in addr tree.
 178  * @param tree: addr tree
 179  * @param addr: to lookup.
 180  * @param addrlen: length of addr
 181  * @return closest enclosing node (could be equal) or NULL if not found.
 182  */
 183 struct addr_tree_node* addr_tree_lookup(rbtree_t* tree,
 184         struct sockaddr_storage* addr, socklen_t addrlen);
 185
 186 /** compare name tree nodes */
 187 int name_tree_compare(const void* k1, const void* k2);
 188
 189 /** compare addr tree nodes */
 190 int addr_tree_compare(const void* k1, const void* k2);
 191
 192 #endif /* UTIL_STORAGE_DNSTREE_H */