1139823Simp/*- 21541Srgrimes * Copyright (c) 1988, 1989, 1993 31541Srgrimes * The Regents of the University of California. All rights reserved. 41541Srgrimes * 51541Srgrimes * Redistribution and use in source and binary forms, with or without 61541Srgrimes * modification, are permitted provided that the following conditions 71541Srgrimes * are met: 81541Srgrimes * 1. Redistributions of source code must retain the above copyright 91541Srgrimes * notice, this list of conditions and the following disclaimer. 101541Srgrimes * 2. Redistributions in binary form must reproduce the above copyright 111541Srgrimes * notice, this list of conditions and the following disclaimer in the 121541Srgrimes * documentation and/or other materials provided with the distribution. 131541Srgrimes * 4. Neither the name of the University nor the names of its contributors 141541Srgrimes * may be used to endorse or promote products derived from this software 151541Srgrimes * without specific prior written permission. 161541Srgrimes * 171541Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 181541Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 191541Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 201541Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 211541Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 221541Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 231541Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 241541Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 251541Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 261541Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 271541Srgrimes * SUCH DAMAGE. 281541Srgrimes * 298152Spst * @(#)radix.h 8.2 (Berkeley) 10/31/94 3050477Speter * $FreeBSD$ 311541Srgrimes */ 321541Srgrimes 338152Spst#ifndef _RADIX_H_ 348152Spst#define _RADIX_H_ 351541Srgrimes 36110527Shsu#ifdef _KERNEL 37110527Shsu#include <sys/_lock.h> 38110527Shsu#include <sys/_mutex.h> 39185747Skmacy#include <sys/_rwlock.h> 40110527Shsu#endif 41108250Shsu 4230354Sphk#ifdef MALLOC_DECLARE 4330354SphkMALLOC_DECLARE(M_RTABLE); 4430354Sphk#endif 4530354Sphk 461541Srgrimes/* 471541Srgrimes * Radix search tree node layout. 481541Srgrimes */ 491541Srgrimes 501541Srgrimesstruct radix_node { 511541Srgrimes struct radix_mask *rn_mklist; /* list of masks contained in subtree */ 5259529Swollman struct radix_node *rn_parent; /* parent */ 5359529Swollman short rn_bit; /* bit offset; -1-index(netmask) */ 541541Srgrimes char rn_bmask; /* node: mask for bit test*/ 551541Srgrimes u_char rn_flags; /* enumerated next */ 561541Srgrimes#define RNF_NORMAL 1 /* leaf contains normal route */ 571541Srgrimes#define RNF_ROOT 2 /* leaf is root leaf for tree */ 581541Srgrimes#define RNF_ACTIVE 4 /* This node is alive (for rtfree) */ 591541Srgrimes union { 601541Srgrimes struct { /* leaf only data: */ 618152Spst caddr_t rn_Key; /* object of search */ 621541Srgrimes caddr_t rn_Mask; /* netmask, if present */ 631541Srgrimes struct radix_node *rn_Dupedkey; 641541Srgrimes } rn_leaf; 651541Srgrimes struct { /* node only data: */ 661541Srgrimes int rn_Off; /* where to start compare */ 671541Srgrimes struct radix_node *rn_L;/* progeny */ 681541Srgrimes struct radix_node *rn_R;/* progeny */ 698152Spst } rn_node; 701541Srgrimes } rn_u; 711541Srgrimes#ifdef RN_DEBUG 721541Srgrimes int rn_info; 731541Srgrimes struct radix_node *rn_twin; 741541Srgrimes struct radix_node *rn_ybro; 751541Srgrimes#endif 761541Srgrimes}; 771541Srgrimes 7859529Swollman#define rn_dupedkey rn_u.rn_leaf.rn_Dupedkey 7959529Swollman#define rn_key rn_u.rn_leaf.rn_Key 8059529Swollman#define rn_mask rn_u.rn_leaf.rn_Mask 8159529Swollman#define rn_offset rn_u.rn_node.rn_Off 8259529Swollman#define rn_left rn_u.rn_node.rn_L 8359529Swollman#define rn_right rn_u.rn_node.rn_R 841541Srgrimes 851541Srgrimes/* 861541Srgrimes * Annotations to tree concerning potential routes applying to subtrees. 871541Srgrimes */ 881541Srgrimes 8929189Sbdestruct radix_mask { 9059529Swollman short rm_bit; /* bit offset; -1-index(netmask) */ 911541Srgrimes char rm_unused; /* cf. rn_bmask */ 921541Srgrimes u_char rm_flags; /* cf. rn_flags */ 931541Srgrimes struct radix_mask *rm_mklist; /* more masks to try */ 948152Spst union { 958152Spst caddr_t rmu_mask; /* the mask */ 968152Spst struct radix_node *rmu_leaf; /* for normal routes */ 978152Spst } rm_rmu; 981541Srgrimes int rm_refs; /* # of references to this struct */ 9929189Sbde}; 1001541Srgrimes 10159529Swollman#define rm_mask rm_rmu.rmu_mask 10259529Swollman#define rm_leaf rm_rmu.rmu_leaf /* extra field would make 32 bytes */ 1038152Spst 10492725Salfredtypedef int walktree_f_t(struct radix_node *, void *); 1054469Sbde 1061541Srgrimesstruct radix_node_head { 1071541Srgrimes struct radix_node *rnh_treetop; 108225698Skmacy u_int rnh_gen; /* generation counter */ 109225698Skmacy int rnh_multipath; /* multipath capable ? */ 1101541Srgrimes int rnh_addrsize; /* permit, but not require fixed keys */ 1111541Srgrimes int rnh_pktsize; /* permit, but not require fixed keys */ 1121541Srgrimes struct radix_node *(*rnh_addaddr) /* add based on sockaddr */ 11392725Salfred (void *v, void *mask, 11492725Salfred struct radix_node_head *head, struct radix_node nodes[]); 1151541Srgrimes struct radix_node *(*rnh_addpkt) /* add based on packet hdr */ 11692725Salfred (void *v, void *mask, 11792725Salfred struct radix_node_head *head, struct radix_node nodes[]); 1181541Srgrimes struct radix_node *(*rnh_deladdr) /* remove based on sockaddr */ 11992725Salfred (void *v, void *mask, struct radix_node_head *head); 1201541Srgrimes struct radix_node *(*rnh_delpkt) /* remove based on packet hdr */ 12192725Salfred (void *v, void *mask, struct radix_node_head *head); 122265708Smelifaro struct radix_node *(*rnh_matchaddr) /* longest match for sockaddr */ 12392725Salfred (void *v, struct radix_node_head *head); 124265708Smelifaro struct radix_node *(*rnh_lookup) /*exact match for sockaddr*/ 12592725Salfred (void *v, void *mask, struct radix_node_head *head); 1261541Srgrimes struct radix_node *(*rnh_matchpkt) /* locate based on packet hdr */ 12792725Salfred (void *v, struct radix_node_head *head); 1281541Srgrimes int (*rnh_walktree) /* traverse tree */ 12992725Salfred (struct radix_node_head *head, walktree_f_t *f, void *w); 1307197Swollman int (*rnh_walktree_from) /* traverse tree below a */ 13192725Salfred (struct radix_node_head *head, void *a, void *m, 13292725Salfred walktree_f_t *f, void *w); 1334073Swollman void (*rnh_close) /* do something when the last ref drops */ 13492725Salfred (struct radix_node *rn, struct radix_node_head *head); 1351541Srgrimes struct radix_node rnh_nodes[3]; /* empty tree for common case */ 136110527Shsu#ifdef _KERNEL 137185747Skmacy struct rwlock rnh_lock; /* locks entire radix tree */ 138110527Shsu#endif 139257330Smelifaro struct radix_node_head *rnh_masks; /* Storage for our masks */ 1401541Srgrimes}; 1411541Srgrimes 14255205Speter#ifndef _KERNEL 1431541Srgrimes#define R_Malloc(p, t, n) (p = (t) malloc((unsigned int)(n))) 144119135Ssam#define R_Zalloc(p, t, n) (p = (t) calloc(1,(unsigned int)(n))) 1451541Srgrimes#define Free(p) free((char *)p); 1461541Srgrimes#else 147108107Sbmilekic#define R_Malloc(p, t, n) (p = (t) malloc((unsigned long)(n), M_RTABLE, M_NOWAIT)) 148119135Ssam#define R_Zalloc(p, t, n) (p = (t) malloc((unsigned long)(n), M_RTABLE, M_NOWAIT | M_ZERO)) 1491541Srgrimes#define Free(p) free((caddr_t)p, M_RTABLE); 150108250Shsu 151110527Shsu#define RADIX_NODE_HEAD_LOCK_INIT(rnh) \ 152185747Skmacy rw_init_flags(&(rnh)->rnh_lock, "radix node head", 0) 153185747Skmacy#define RADIX_NODE_HEAD_LOCK(rnh) rw_wlock(&(rnh)->rnh_lock) 154185747Skmacy#define RADIX_NODE_HEAD_UNLOCK(rnh) rw_wunlock(&(rnh)->rnh_lock) 155185747Skmacy#define RADIX_NODE_HEAD_RLOCK(rnh) rw_rlock(&(rnh)->rnh_lock) 156185747Skmacy#define RADIX_NODE_HEAD_RUNLOCK(rnh) rw_runlock(&(rnh)->rnh_lock) 157185747Skmacy#define RADIX_NODE_HEAD_LOCK_TRY_UPGRADE(rnh) rw_try_upgrade(&(rnh)->rnh_lock) 158185747Skmacy 159185747Skmacy 160185747Skmacy#define RADIX_NODE_HEAD_DESTROY(rnh) rw_destroy(&(rnh)->rnh_lock) 161185747Skmacy#define RADIX_NODE_HEAD_LOCK_ASSERT(rnh) rw_assert(&(rnh)->rnh_lock, RA_LOCKED) 162185747Skmacy#define RADIX_NODE_HEAD_WLOCK_ASSERT(rnh) rw_assert(&(rnh)->rnh_lock, RA_WLOCKED) 16355205Speter#endif /* _KERNEL */ 1641541Srgrimes 165200537Sluigivoid rn_init(int); 16692725Salfredint rn_inithead(void **, int); 167204808Sbzint rn_detachhead(void **); 16892725Salfredint rn_refines(void *, void *); 1691541Srgrimesstruct radix_node 17092725Salfred *rn_addmask(void *, int, int), 171257330Smelifaro *rn_addmask_r(void *, struct radix_node_head *, int, int), 17292725Salfred *rn_addroute (void *, void *, struct radix_node_head *, 17392725Salfred struct radix_node [2]), 17492725Salfred *rn_delete(void *, void *, struct radix_node_head *), 17592725Salfred *rn_lookup (void *v_arg, void *m_arg, 17692725Salfred struct radix_node_head *head), 17792725Salfred *rn_match(void *, struct radix_node_head *); 1781541Srgrimes 1798152Spst#endif /* _RADIX_H_ */ 180