dnstree.h revision 269257
10Sstevel@tonic-gate/* 20Sstevel@tonic-gate * util/storage/dnstree.h - support for rbtree types suitable for DNS code. 30Sstevel@tonic-gate * 40Sstevel@tonic-gate * Copyright (c) 2008, NLnet Labs. All rights reserved. 50Sstevel@tonic-gate * 60Sstevel@tonic-gate * This software is open source. 70Sstevel@tonic-gate * 80Sstevel@tonic-gate * Redistribution and use in source and binary forms, with or without 90Sstevel@tonic-gate * modification, are permitted provided that the following conditions 100Sstevel@tonic-gate * are met: 110Sstevel@tonic-gate * 120Sstevel@tonic-gate * Redistributions of source code must retain the above copyright notice, 130Sstevel@tonic-gate * this list of conditions and the following disclaimer. 140Sstevel@tonic-gate * 150Sstevel@tonic-gate * Redistributions in binary form must reproduce the above copyright notice, 160Sstevel@tonic-gate * this list of conditions and the following disclaimer in the documentation 170Sstevel@tonic-gate * and/or other materials provided with the distribution. 180Sstevel@tonic-gate * 190Sstevel@tonic-gate * Neither the name of the NLNET LABS nor the names of its contributors may 200Sstevel@tonic-gate * be used to endorse or promote products derived from this software without 210Sstevel@tonic-gate * specific prior written permission. 220Sstevel@tonic-gate * 230Sstevel@tonic-gate * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 240Sstevel@tonic-gate * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 250Sstevel@tonic-gate * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 260Sstevel@tonic-gate * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 270Sstevel@tonic-gate * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 280Sstevel@tonic-gate * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED 290Sstevel@tonic-gate * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 300Sstevel@tonic-gate * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 310Sstevel@tonic-gate * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 320Sstevel@tonic-gate * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 330Sstevel@tonic-gate * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 340Sstevel@tonic-gate */ 350Sstevel@tonic-gate 360Sstevel@tonic-gate/** 370Sstevel@tonic-gate * \file 380Sstevel@tonic-gate * 390Sstevel@tonic-gate * This file contains structures combining types and functions to 400Sstevel@tonic-gate * manipulate those structures that help building DNS lookup trees. 410Sstevel@tonic-gate */ 420Sstevel@tonic-gate 430Sstevel@tonic-gate#ifndef UTIL_STORAGE_DNSTREE_H 440Sstevel@tonic-gate#define UTIL_STORAGE_DNSTREE_H 450Sstevel@tonic-gate#include "util/rbtree.h" 460Sstevel@tonic-gate 470Sstevel@tonic-gate/** 480Sstevel@tonic-gate * Tree of domain names. Sorted first by class then by name. 490Sstevel@tonic-gate * This is not sorted canonically, but fast. 500Sstevel@tonic-gate * This can be looked up to obtain a closest encloser parent name. 510Sstevel@tonic-gate * 520Sstevel@tonic-gate * The tree itself is a rbtree_t. 530Sstevel@tonic-gate * This is the element node put as first entry in the client structure. 540Sstevel@tonic-gate */ 550Sstevel@tonic-gatestruct name_tree_node { 560Sstevel@tonic-gate /** rbtree node, key is this struct : dclass and name */ 570Sstevel@tonic-gate rbnode_t node; 580Sstevel@tonic-gate /** parent in tree */ 590Sstevel@tonic-gate struct name_tree_node* parent; 600Sstevel@tonic-gate /** name in uncompressed wireformat */ 610Sstevel@tonic-gate uint8_t* name; 620Sstevel@tonic-gate /** length of name */ 630Sstevel@tonic-gate size_t len; 640Sstevel@tonic-gate /** labels in name */ 650Sstevel@tonic-gate int labs; 660Sstevel@tonic-gate /** the class of the name (host order) */ 670Sstevel@tonic-gate uint16_t dclass; 680Sstevel@tonic-gate}; 690Sstevel@tonic-gate 700Sstevel@tonic-gate/** 710Sstevel@tonic-gate * Tree of IP addresses. Sorted first by protocol, then by bits. 720Sstevel@tonic-gate * This can be looked up to obtain the enclosing subnet. 730Sstevel@tonic-gate * 740Sstevel@tonic-gate * The tree itself is a rbtree_t. 750Sstevel@tonic-gate * This is the element node put as first entry in the client structure. 760Sstevel@tonic-gate */ 770Sstevel@tonic-gatestruct addr_tree_node { 780Sstevel@tonic-gate /** rbtree node, key is this struct : proto and subnet */ 790Sstevel@tonic-gate rbnode_t node; 800Sstevel@tonic-gate /** parent in tree */ 810Sstevel@tonic-gate struct addr_tree_node* parent; 820Sstevel@tonic-gate /** address */ 830Sstevel@tonic-gate struct sockaddr_storage addr; 840Sstevel@tonic-gate /** length of addr */ 850Sstevel@tonic-gate socklen_t addrlen; 860Sstevel@tonic-gate /** netblock size */ 870Sstevel@tonic-gate int net; 880Sstevel@tonic-gate}; 890Sstevel@tonic-gate 900Sstevel@tonic-gate/** 910Sstevel@tonic-gate * Init a name tree to be empty 920Sstevel@tonic-gate * @param tree: to init. 930Sstevel@tonic-gate */ 940Sstevel@tonic-gatevoid name_tree_init(rbtree_t* tree); 950Sstevel@tonic-gate 960Sstevel@tonic-gate/** 970Sstevel@tonic-gate * insert element into name tree. 980Sstevel@tonic-gate * @param tree: name tree 990Sstevel@tonic-gate * @param node: node element (at start of a structure that caller 1000Sstevel@tonic-gate * has allocated). 1010Sstevel@tonic-gate * @param name: name to insert (wireformat) 1020Sstevel@tonic-gate * this node has been allocated by the caller and it itself inserted. 1030Sstevel@tonic-gate * @param len: length of name 1040Sstevel@tonic-gate * @param labs: labels in name 1050Sstevel@tonic-gate * @param dclass: class of name 1060Sstevel@tonic-gate * @return false on error (duplicate element). 1070Sstevel@tonic-gate */ 1080Sstevel@tonic-gateint name_tree_insert(rbtree_t* tree, struct name_tree_node* node, 1090Sstevel@tonic-gate uint8_t* name, size_t len, int labs, uint16_t dclass); 1100Sstevel@tonic-gate 1110Sstevel@tonic-gate/** 1120Sstevel@tonic-gate * Initialize parent pointers in name tree. 1130Sstevel@tonic-gate * Should be performed after insertions are done, before lookups 1140Sstevel@tonic-gate * @param tree: name tree 1150Sstevel@tonic-gate */ 1160Sstevel@tonic-gatevoid name_tree_init_parents(rbtree_t* tree); 1170Sstevel@tonic-gate 1180Sstevel@tonic-gate/** 1190Sstevel@tonic-gate * Lookup exact match in name tree 1200Sstevel@tonic-gate * @param tree: name tree 1210Sstevel@tonic-gate * @param name: wireformat name 1220Sstevel@tonic-gate * @param len: length of name 1230Sstevel@tonic-gate * @param labs: labels in name 1240Sstevel@tonic-gate * @param dclass: class of name 1250Sstevel@tonic-gate * @return node or NULL if not found. 1260Sstevel@tonic-gate */ 1270Sstevel@tonic-gatestruct name_tree_node* name_tree_find(rbtree_t* tree, uint8_t* name, 1280Sstevel@tonic-gate size_t len, int labs, uint16_t dclass); 1290Sstevel@tonic-gate 1300Sstevel@tonic-gate/** 1310Sstevel@tonic-gate * Lookup closest encloser in name tree. 1320Sstevel@tonic-gate * @param tree: name tree 1330Sstevel@tonic-gate * @param name: wireformat name 1340Sstevel@tonic-gate * @param len: length of name 1350Sstevel@tonic-gate * @param labs: labels in name 1360Sstevel@tonic-gate * @param dclass: class of name 1370Sstevel@tonic-gate * @return closest enclosing node (could be equal) or NULL if not found. 1380Sstevel@tonic-gate */ 1390Sstevel@tonic-gatestruct name_tree_node* name_tree_lookup(rbtree_t* tree, uint8_t* name, 1400Sstevel@tonic-gate size_t len, int labs, uint16_t dclass); 1410Sstevel@tonic-gate 1420Sstevel@tonic-gate/** 1430Sstevel@tonic-gate * Find next root item in name tree. 1440Sstevel@tonic-gate * @param tree: the nametree. 1450Sstevel@tonic-gate * @param dclass: the class to look for next (or higher). 1460Sstevel@tonic-gate * @return false if no classes found, true means class put into c. 1470Sstevel@tonic-gate */ 1480Sstevel@tonic-gateint name_tree_next_root(rbtree_t* tree, uint16_t* dclass); 1490Sstevel@tonic-gate 1500Sstevel@tonic-gate/** 1510Sstevel@tonic-gate * Init addr tree to be empty. 1520Sstevel@tonic-gate * @param tree: to init. 1530Sstevel@tonic-gate */ 1540Sstevel@tonic-gatevoid addr_tree_init(rbtree_t* tree); 1550Sstevel@tonic-gate 1560Sstevel@tonic-gate/** 1570Sstevel@tonic-gate * insert element into addr tree. 1580Sstevel@tonic-gate * @param tree: addr tree 1590Sstevel@tonic-gate * @param node: node element (at start of a structure that caller 1600Sstevel@tonic-gate * has allocated). 1610Sstevel@tonic-gate * @param addr: to insert (copied). 1620Sstevel@tonic-gate * @param addrlen: length of addr 1630Sstevel@tonic-gate * @param net: size of subnet. 1640Sstevel@tonic-gate * @return false on error (duplicate element). 1650Sstevel@tonic-gate */ 1660Sstevel@tonic-gateint addr_tree_insert(rbtree_t* tree, struct addr_tree_node* node, 1670Sstevel@tonic-gate struct sockaddr_storage* addr, socklen_t addrlen, int net); 1680Sstevel@tonic-gate 1690Sstevel@tonic-gate/** 1700Sstevel@tonic-gate * Initialize parent pointers in addr tree. 1710Sstevel@tonic-gate * Should be performed after insertions are done, before lookups 1720Sstevel@tonic-gate * @param tree: addr tree 1730Sstevel@tonic-gate */ 1740Sstevel@tonic-gatevoid addr_tree_init_parents(rbtree_t* tree); 1750Sstevel@tonic-gate 1760Sstevel@tonic-gate/** 1770Sstevel@tonic-gate * Lookup closest encloser in addr tree. 1780Sstevel@tonic-gate * @param tree: addr tree 1790Sstevel@tonic-gate * @param addr: to lookup. 1800Sstevel@tonic-gate * @param addrlen: length of addr 1810Sstevel@tonic-gate * @return closest enclosing node (could be equal) or NULL if not found. 1820Sstevel@tonic-gate */ 1830Sstevel@tonic-gatestruct addr_tree_node* addr_tree_lookup(rbtree_t* tree, 1840Sstevel@tonic-gate struct sockaddr_storage* addr, socklen_t addrlen); 1850Sstevel@tonic-gate 1860Sstevel@tonic-gate/** compare name tree nodes */ 1870Sstevel@tonic-gateint name_tree_compare(const void* k1, const void* k2); 1880Sstevel@tonic-gate 1890Sstevel@tonic-gate/** compare addr tree nodes */ 1900Sstevel@tonic-gateint addr_tree_compare(const void* k1, const void* k2); 1910Sstevel@tonic-gate 1920Sstevel@tonic-gate#endif /* UTIL_STORAGE_DNSTREE_H */ 1930Sstevel@tonic-gate