radix.h revision 190715
1184610Salfred/* 2184610Salfred * Copyright (c) 1988, 1989, 1993 3184610Salfred * The Regents of the University of California. All rights reserved. 4184610Salfred * 5184610Salfred * Redistribution and use in source and binary forms, with or without 6184610Salfred * modification, are permitted provided that the following conditions 7184610Salfred * are met: 8184610Salfred * 1. Redistributions of source code must retain the above copyright 9184610Salfred * notice, this list of conditions and the following disclaimer. 10184610Salfred * 2. Redistributions in binary form must reproduce the above copyright 11184610Salfred * notice, this list of conditions and the following disclaimer in the 12184610Salfred * documentation and/or other materials provided with the distribution. 13184610Salfred * 4. Neither the name of the University nor the names of its contributors 14184610Salfred * may be used to endorse or promote products derived from this software 15184610Salfred * without specific prior written permission. 16184610Salfred * 17184610Salfred * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 18184610Salfred * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 19184610Salfred * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 20184610Salfred * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 21184610Salfred * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 22184610Salfred * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 23184610Salfred * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 24184610Salfred * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 25184610Salfred * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 26184610Salfred * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 27184610Salfred * SUCH DAMAGE. 28184610Salfred * 29184610Salfred * @(#)radix.h 8.2 (Berkeley) 10/31/94 30248236Shselasky * 31248236Shselasky * $FreeBSD: head/sbin/routed/radix.h 190715 2009-04-05 15:55:09Z phk $ 32184610Salfred */ 33203815Swkoszek 34248236Shselasky#ifndef __RADIX_H_ 35184610Salfred#define __RADIX_H_ 36184610Salfred 37184610Salfred#include <sys/cdefs.h> 38184610Salfredstruct walkarg; 39184610Salfred 40184610Salfred/* 41184610Salfred * Radix search tree node layout. 42184610Salfred */ 43184610Salfred 44184610Salfredstruct radix_node { 45184610Salfred struct radix_mask *rn_mklist; /* list of masks contained in subtree */ 46184610Salfred struct radix_node *rn_p; /* parent */ 47184610Salfred short rn_b; /* bit offset; -1-index(netmask) */ 48184610Salfred char rn_bmask; /* node: mask for bit test*/ 49184610Salfred u_char rn_flags; /* enumerated next */ 50184610Salfred#define RNF_NORMAL 1 /* leaf contains normal route */ 51184610Salfred#define RNF_ROOT 2 /* leaf is root leaf for tree */ 52184610Salfred#define RNF_ACTIVE 4 /* This node is alive (for rtfree) */ 53184610Salfred union { 54184610Salfred struct { /* leaf only data: */ 55184610Salfred caddr_t rn_Key; /* object of search */ 56184610Salfred caddr_t rn_Mask; /* netmask, if present */ 57184610Salfred struct radix_node *rn_Dupedkey; 58184610Salfred } rn_leaf; 59184610Salfred struct { /* node only data: */ 60184610Salfred int rn_Off; /* where to start compare */ 61184610Salfred struct radix_node *rn_L;/* progeny */ 62184610Salfred struct radix_node *rn_R;/* progeny */ 63184610Salfred }rn_node; 64184610Salfred } rn_u; 65184610Salfred#ifdef RN_DEBUG 66184610Salfred int rn_info; 67184610Salfred struct radix_node *rn_twin; 68184610Salfred struct radix_node *rn_ybro; 69184610Salfred#endif 70184610Salfred}; 71184610Salfred 72184610Salfred#define rn_dupedkey rn_u.rn_leaf.rn_Dupedkey 73184610Salfred#define rn_key rn_u.rn_leaf.rn_Key 74184610Salfred#define rn_mask rn_u.rn_leaf.rn_Mask 75184610Salfred#define rn_off rn_u.rn_node.rn_Off 76184610Salfred#define rn_l rn_u.rn_node.rn_L 77184610Salfred#define rn_r rn_u.rn_node.rn_R 78184610Salfred 79184610Salfred/* 80184610Salfred * Annotations to tree concerning potential routes applying to subtrees. 81184610Salfred */ 82184610Salfred 83184610Salfredstruct radix_mask { 84184610Salfred short rm_b; /* bit offset; -1-index(netmask) */ 85184610Salfred char rm_unused; /* cf. rn_bmask */ 86184610Salfred u_char rm_flags; /* cf. rn_flags */ 87184610Salfred struct radix_mask *rm_mklist; /* more masks to try */ 88184610Salfred union { 89184610Salfred caddr_t rmu_mask; /* the mask */ 90184610Salfred struct radix_node *rmu_leaf; /* for normal routes */ 91184610Salfred } rm_rmu; 92184610Salfred int rm_refs; /* # of references to this struct */ 93184610Salfred}; 94184610Salfred 95184610Salfred#define rm_mask rm_rmu.rmu_mask 96184610Salfred#define rm_leaf rm_rmu.rmu_leaf /* extra field would make 32 bytes */ 97184610Salfred 98184610Salfred#define MKGet(m) {\ 99184610Salfred if (rn_mkfreelist) {\ 100184610Salfred m = rn_mkfreelist; \ 101184610Salfred rn_mkfreelist = (m)->rm_mklist; \ 102184610Salfred } else \ 103184610Salfred m = (struct radix_mask *)rtmalloc(sizeof(*(m)), "MKGet"); }\ 104184610Salfred 105184610Salfred#define MKFree(m) { (m)->rm_mklist = rn_mkfreelist; rn_mkfreelist = (m);} 106184610Salfred 107184610Salfredstruct radix_node_head { 108184610Salfred struct radix_node *rnh_treetop; 109184610Salfred int rnh_addrsize; /* permit, but not require fixed keys */ 110184610Salfred int rnh_pktsize; /* permit, but not require fixed keys */ 111184610Salfred struct radix_node *(*rnh_addaddr) /* add based on sockaddr */ 112184610Salfred (void *v, void *mask, 113184610Salfred struct radix_node_head *head, struct radix_node nodes[]); 114184610Salfred struct radix_node *(*rnh_addpkt) /* add based on packet hdr */ 115184610Salfred (void *v, void *mask, 116184610Salfred struct radix_node_head *head, struct radix_node nodes[]); 117184610Salfred struct radix_node *(*rnh_deladdr) /* remove based on sockaddr */ 118184610Salfred (void *v, void *mask, struct radix_node_head *head); 119184610Salfred struct radix_node *(*rnh_delpkt) /* remove based on packet hdr */ 120184610Salfred (void *v, void *mask, struct radix_node_head *head); 121184610Salfred struct radix_node *(*rnh_matchaddr) /* locate based on sockaddr */ 122184610Salfred (void *v, struct radix_node_head *head); 123184610Salfred struct radix_node *(*rnh_lookup) /* locate based on sockaddr */ 124184610Salfred (void *v, void *mask, struct radix_node_head *head); 125184610Salfred struct radix_node *(*rnh_matchpkt) /* locate based on packet hdr */ 126184610Salfred (void *v, struct radix_node_head *head); 127184610Salfred int (*rnh_walktree) /* traverse tree */ 128184610Salfred (struct radix_node_head *head, 129184610Salfred int (*f)(struct radix_node *, struct walkarg *), 130184610Salfred struct walkarg *w); 131184610Salfred struct radix_node rnh_nodes[3]; /* empty tree for common case */ 132184610Salfred}; 133184610Salfred 134184610Salfred 135184610Salfred#define Bcmp(a, b, n) memcmp(((void *)(a)), ((void *)(b)), (n)) 136184610Salfred#define Bcopy(a, b, n) memmove(((void *)(b)), ((void *)(a)), (size_t)(n)) 137184610Salfred#define Bzero(p, n) memset((void *)(p), 0, (size_t)(n)); 138184610Salfred#define Free(p) free((void *)p); 139184610Salfred 140184610Salfredvoid rn_init(void); 141184610Salfredint rn_inithead(struct radix_node_head **head, int off); 142184610Salfredint rn_walktree(struct radix_node_head *, 143184610Salfred int (*)(struct radix_node *, struct walkarg *), 144184610Salfred struct walkarg *); 145184610Salfred 146184610Salfred#endif /* __RADIX_H_ */ 147184610Salfred