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 104294706Smelifarostruct radix_head; 105294706Smelifaro 10692725Salfredtypedef int walktree_f_t(struct radix_node *, void *); 107294706Smelifarotypedef struct radix_node *rn_matchaddr_f_t(void *v, 108294706Smelifaro struct radix_head *head); 109294706Smelifarotypedef struct radix_node *rn_addaddr_f_t(void *v, void *mask, 110294706Smelifaro struct radix_head *head, struct radix_node nodes[]); 111294706Smelifarotypedef struct radix_node *rn_deladdr_f_t(void *v, void *mask, 112294706Smelifaro struct radix_head *head); 113294706Smelifarotypedef struct radix_node *rn_lookup_f_t(void *v, void *mask, 114294706Smelifaro struct radix_head *head); 115294706Smelifarotypedef int rn_walktree_t(struct radix_head *head, walktree_f_t *f, 116294706Smelifaro void *w); 117294706Smelifarotypedef int rn_walktree_from_t(struct radix_head *head, 118294706Smelifaro void *a, void *m, walktree_f_t *f, void *w); 119294706Smelifarotypedef void rn_close_t(struct radix_node *rn, struct radix_head *head); 1204469Sbde 121294706Smelifarostruct radix_mask_head; 122294706Smelifaro 123294706Smelifarostruct radix_head { 124294706Smelifaro struct radix_node *rnh_treetop; 125294706Smelifaro struct radix_mask_head *rnh_masks; /* Storage for our masks */ 126294706Smelifaro}; 127294706Smelifaro 1281541Srgrimesstruct radix_node_head { 129294706Smelifaro struct radix_head rh; 130294706Smelifaro rn_matchaddr_f_t *rnh_matchaddr; /* longest match for sockaddr */ 131294706Smelifaro rn_addaddr_f_t *rnh_addaddr; /* add based on sockaddr*/ 132294706Smelifaro rn_deladdr_f_t *rnh_deladdr; /* remove based on sockaddr */ 133294706Smelifaro rn_lookup_f_t *rnh_lookup; /* exact match for sockaddr */ 134294706Smelifaro rn_walktree_t *rnh_walktree; /* traverse tree */ 135294706Smelifaro rn_walktree_from_t *rnh_walktree_from; /* traverse tree below a */ 136294706Smelifaro rn_close_t *rnh_close; /*do something when the last ref drops*/ 1371541Srgrimes struct radix_node rnh_nodes[3]; /* empty tree for common case */ 138110527Shsu#ifdef _KERNEL 139185747Skmacy struct rwlock rnh_lock; /* locks entire radix tree */ 140110527Shsu#endif 1411541Srgrimes}; 1421541Srgrimes 143294706Smelifarostruct radix_mask_head { 144294706Smelifaro struct radix_head head; 145294706Smelifaro struct radix_node mask_nodes[3]; 146294706Smelifaro}; 147294706Smelifaro 148294706Smelifarovoid rn_inithead_internal(struct radix_head *rh, struct radix_node *base_nodes, 149294706Smelifaro int off); 150294706Smelifaro 15155205Speter#ifndef _KERNEL 1521541Srgrimes#define R_Malloc(p, t, n) (p = (t) malloc((unsigned int)(n))) 153119135Ssam#define R_Zalloc(p, t, n) (p = (t) calloc(1,(unsigned int)(n))) 154256586Sglebius#define R_Free(p) free((char *)p); 1551541Srgrimes#else 156108107Sbmilekic#define R_Malloc(p, t, n) (p = (t) malloc((unsigned long)(n), M_RTABLE, M_NOWAIT)) 157119135Ssam#define R_Zalloc(p, t, n) (p = (t) malloc((unsigned long)(n), M_RTABLE, M_NOWAIT | M_ZERO)) 158286057Sloos#define R_Free(p) free((caddr_t)p, M_RTABLE); 159108250Shsu 160110527Shsu#define RADIX_NODE_HEAD_LOCK_INIT(rnh) \ 161185747Skmacy rw_init_flags(&(rnh)->rnh_lock, "radix node head", 0) 162185747Skmacy#define RADIX_NODE_HEAD_LOCK(rnh) rw_wlock(&(rnh)->rnh_lock) 163185747Skmacy#define RADIX_NODE_HEAD_UNLOCK(rnh) rw_wunlock(&(rnh)->rnh_lock) 164185747Skmacy#define RADIX_NODE_HEAD_RLOCK(rnh) rw_rlock(&(rnh)->rnh_lock) 165185747Skmacy#define RADIX_NODE_HEAD_RUNLOCK(rnh) rw_runlock(&(rnh)->rnh_lock) 166185747Skmacy#define RADIX_NODE_HEAD_LOCK_TRY_UPGRADE(rnh) rw_try_upgrade(&(rnh)->rnh_lock) 167185747Skmacy 168185747Skmacy 169185747Skmacy#define RADIX_NODE_HEAD_DESTROY(rnh) rw_destroy(&(rnh)->rnh_lock) 170262758Sgnn#define RADIX_NODE_HEAD_LOCK_ASSERT(rnh) rw_assert(&(rnh)->rnh_lock, RA_LOCKED) 171185747Skmacy#define RADIX_NODE_HEAD_WLOCK_ASSERT(rnh) rw_assert(&(rnh)->rnh_lock, RA_WLOCKED) 17255205Speter#endif /* _KERNEL */ 1731541Srgrimes 17492725Salfredint rn_inithead(void **, int); 175204808Sbzint rn_detachhead(void **); 17692725Salfredint rn_refines(void *, void *); 177294706Smelifarostruct radix_node *rn_addroute(void *, void *, struct radix_head *, 178294706Smelifaro struct radix_node[2]); 179294706Smelifarostruct radix_node *rn_delete(void *, void *, struct radix_head *); 180294706Smelifarostruct radix_node *rn_lookup (void *v_arg, void *m_arg, 181294706Smelifaro struct radix_head *head); 182294706Smelifarostruct radix_node *rn_match(void *, struct radix_head *); 183294706Smelifaroint rn_walktree_from(struct radix_head *h, void *a, void *m, 184294706Smelifaro walktree_f_t *f, void *w); 185294706Smelifaroint rn_walktree(struct radix_head *, walktree_f_t *, void *); 1861541Srgrimes 1878152Spst#endif /* _RADIX_H_ */ 188