1238106Sdes/* 2238106Sdes * util/storage/dnstree.h - support for rbtree types suitable for DNS code. 3238106Sdes * 4238106Sdes * Copyright (c) 2008, NLnet Labs. All rights reserved. 5238106Sdes * 6238106Sdes * This software is open source. 7238106Sdes * 8238106Sdes * Redistribution and use in source and binary forms, with or without 9238106Sdes * modification, are permitted provided that the following conditions 10238106Sdes * are met: 11238106Sdes * 12238106Sdes * Redistributions of source code must retain the above copyright notice, 13238106Sdes * this list of conditions and the following disclaimer. 14238106Sdes * 15238106Sdes * Redistributions in binary form must reproduce the above copyright notice, 16238106Sdes * this list of conditions and the following disclaimer in the documentation 17238106Sdes * and/or other materials provided with the distribution. 18238106Sdes * 19238106Sdes * Neither the name of the NLNET LABS nor the names of its contributors may 20238106Sdes * be used to endorse or promote products derived from this software without 21238106Sdes * specific prior written permission. 22238106Sdes * 23238106Sdes * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 24266114Sdes * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 25266114Sdes * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 26266114Sdes * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 27266114Sdes * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 28266114Sdes * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED 29266114Sdes * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 30266114Sdes * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 31266114Sdes * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 32266114Sdes * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 33266114Sdes * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 34238106Sdes */ 35238106Sdes 36238106Sdes/** 37238106Sdes * \file 38238106Sdes * 39238106Sdes * This file contains structures combining types and functions to 40238106Sdes * manipulate those structures that help building DNS lookup trees. 41238106Sdes */ 42238106Sdes 43238106Sdes#ifndef UTIL_STORAGE_DNSTREE_H 44238106Sdes#define UTIL_STORAGE_DNSTREE_H 45238106Sdes#include "util/rbtree.h" 46238106Sdes 47238106Sdes/** 48238106Sdes * Tree of domain names. Sorted first by class then by name. 49238106Sdes * This is not sorted canonically, but fast. 50238106Sdes * This can be looked up to obtain a closest encloser parent name. 51238106Sdes * 52238106Sdes * The tree itself is a rbtree_t. 53238106Sdes * This is the element node put as first entry in the client structure. 54238106Sdes */ 55238106Sdesstruct name_tree_node { 56238106Sdes /** rbtree node, key is this struct : dclass and name */ 57238106Sdes rbnode_t node; 58238106Sdes /** parent in tree */ 59238106Sdes struct name_tree_node* parent; 60238106Sdes /** name in uncompressed wireformat */ 61238106Sdes uint8_t* name; 62238106Sdes /** length of name */ 63238106Sdes size_t len; 64238106Sdes /** labels in name */ 65238106Sdes int labs; 66238106Sdes /** the class of the name (host order) */ 67238106Sdes uint16_t dclass; 68238106Sdes}; 69238106Sdes 70238106Sdes/** 71238106Sdes * Tree of IP addresses. Sorted first by protocol, then by bits. 72238106Sdes * This can be looked up to obtain the enclosing subnet. 73238106Sdes * 74238106Sdes * The tree itself is a rbtree_t. 75238106Sdes * This is the element node put as first entry in the client structure. 76238106Sdes */ 77238106Sdesstruct addr_tree_node { 78238106Sdes /** rbtree node, key is this struct : proto and subnet */ 79238106Sdes rbnode_t node; 80238106Sdes /** parent in tree */ 81238106Sdes struct addr_tree_node* parent; 82238106Sdes /** address */ 83238106Sdes struct sockaddr_storage addr; 84238106Sdes /** length of addr */ 85238106Sdes socklen_t addrlen; 86238106Sdes /** netblock size */ 87238106Sdes int net; 88238106Sdes}; 89238106Sdes 90238106Sdes/** 91238106Sdes * Init a name tree to be empty 92238106Sdes * @param tree: to init. 93238106Sdes */ 94238106Sdesvoid name_tree_init(rbtree_t* tree); 95238106Sdes 96238106Sdes/** 97238106Sdes * insert element into name tree. 98238106Sdes * @param tree: name tree 99238106Sdes * @param node: node element (at start of a structure that caller 100238106Sdes * has allocated). 101238106Sdes * @param name: name to insert (wireformat) 102238106Sdes * this node has been allocated by the caller and it itself inserted. 103238106Sdes * @param len: length of name 104238106Sdes * @param labs: labels in name 105238106Sdes * @param dclass: class of name 106238106Sdes * @return false on error (duplicate element). 107238106Sdes */ 108238106Sdesint name_tree_insert(rbtree_t* tree, struct name_tree_node* node, 109238106Sdes uint8_t* name, size_t len, int labs, uint16_t dclass); 110238106Sdes 111238106Sdes/** 112238106Sdes * Initialize parent pointers in name tree. 113238106Sdes * Should be performed after insertions are done, before lookups 114238106Sdes * @param tree: name tree 115238106Sdes */ 116238106Sdesvoid name_tree_init_parents(rbtree_t* tree); 117238106Sdes 118238106Sdes/** 119238106Sdes * Lookup exact match in name tree 120238106Sdes * @param tree: name tree 121238106Sdes * @param name: wireformat name 122238106Sdes * @param len: length of name 123238106Sdes * @param labs: labels in name 124238106Sdes * @param dclass: class of name 125238106Sdes * @return node or NULL if not found. 126238106Sdes */ 127238106Sdesstruct name_tree_node* name_tree_find(rbtree_t* tree, uint8_t* name, 128238106Sdes size_t len, int labs, uint16_t dclass); 129238106Sdes 130238106Sdes/** 131238106Sdes * Lookup closest encloser in name tree. 132238106Sdes * @param tree: name tree 133238106Sdes * @param name: wireformat name 134238106Sdes * @param len: length of name 135238106Sdes * @param labs: labels in name 136238106Sdes * @param dclass: class of name 137238106Sdes * @return closest enclosing node (could be equal) or NULL if not found. 138238106Sdes */ 139238106Sdesstruct name_tree_node* name_tree_lookup(rbtree_t* tree, uint8_t* name, 140238106Sdes size_t len, int labs, uint16_t dclass); 141238106Sdes 142238106Sdes/** 143238106Sdes * Find next root item in name tree. 144238106Sdes * @param tree: the nametree. 145238106Sdes * @param dclass: the class to look for next (or higher). 146238106Sdes * @return false if no classes found, true means class put into c. 147238106Sdes */ 148238106Sdesint name_tree_next_root(rbtree_t* tree, uint16_t* dclass); 149238106Sdes 150238106Sdes/** 151238106Sdes * Init addr tree to be empty. 152238106Sdes * @param tree: to init. 153238106Sdes */ 154238106Sdesvoid addr_tree_init(rbtree_t* tree); 155238106Sdes 156238106Sdes/** 157238106Sdes * insert element into addr tree. 158238106Sdes * @param tree: addr tree 159238106Sdes * @param node: node element (at start of a structure that caller 160238106Sdes * has allocated). 161238106Sdes * @param addr: to insert (copied). 162238106Sdes * @param addrlen: length of addr 163238106Sdes * @param net: size of subnet. 164238106Sdes * @return false on error (duplicate element). 165238106Sdes */ 166238106Sdesint addr_tree_insert(rbtree_t* tree, struct addr_tree_node* node, 167238106Sdes struct sockaddr_storage* addr, socklen_t addrlen, int net); 168238106Sdes 169238106Sdes/** 170238106Sdes * Initialize parent pointers in addr tree. 171238106Sdes * Should be performed after insertions are done, before lookups 172238106Sdes * @param tree: addr tree 173238106Sdes */ 174238106Sdesvoid addr_tree_init_parents(rbtree_t* tree); 175238106Sdes 176238106Sdes/** 177238106Sdes * Lookup closest encloser in addr tree. 178238106Sdes * @param tree: addr tree 179238106Sdes * @param addr: to lookup. 180238106Sdes * @param addrlen: length of addr 181238106Sdes * @return closest enclosing node (could be equal) or NULL if not found. 182238106Sdes */ 183238106Sdesstruct addr_tree_node* addr_tree_lookup(rbtree_t* tree, 184238106Sdes struct sockaddr_storage* addr, socklen_t addrlen); 185238106Sdes 186238106Sdes/** compare name tree nodes */ 187238106Sdesint name_tree_compare(const void* k1, const void* k2); 188238106Sdes 189238106Sdes/** compare addr tree nodes */ 190238106Sdesint addr_tree_compare(const void* k1, const void* k2); 191238106Sdes 192238106Sdes#endif /* UTIL_STORAGE_DNSTREE_H */ 193