1 /* 2 * Copyright (c) 1988, 1989 Regents of the University of California. 3 * All rights reserved. 4 * 5 * %sccs.include.redist.c% 6 * 7 * @(#)radix.h 7.5 (Berkeley) 07/30/91 8 */ 9 10 /* 11 * Radix search tree node layout. 12 */ 13 14 struct radix_node { 15 struct radix_mask *rn_mklist; /* list of masks contained in subtree */ 16 struct radix_node *rn_p; /* parent */ 17 short rn_b; /* bit offset; -1-index(netmask) */ 18 char rn_bmask; /* node: mask for bit test*/ 19 u_char rn_flags; /* enumerated next */ 20 #define RNF_NORMAL 1 /* leaf contains normal route */ 21 #define RNF_ROOT 2 /* leaf is root leaf for tree */ 22 #define RNF_ACTIVE 4 /* This node is alive (for rtfree) */ 23 union { 24 struct { /* leaf only data: */ 25 caddr_t rn_Key; /* object of search */ 26 caddr_t rn_Mask; /* netmask, if present */ 27 struct radix_node *rn_Dupedkey; 28 } rn_leaf; 29 struct { /* node only data: */ 30 int rn_Off; /* where to start compare */ 31 struct radix_node *rn_L;/* progeny */ 32 struct radix_node *rn_R;/* progeny */ 33 }rn_node; 34 } rn_u; 35 #ifdef RN_DEBUG 36 int rn_info; 37 struct radix_node *rn_twin; 38 struct radix_node *rn_ybro; 39 #endif 40 }; 41 42 #define rn_dupedkey rn_u.rn_leaf.rn_Dupedkey 43 #define rn_key rn_u.rn_leaf.rn_Key 44 #define rn_mask rn_u.rn_leaf.rn_Mask 45 #define rn_off rn_u.rn_node.rn_Off 46 #define rn_l rn_u.rn_node.rn_L 47 #define rn_r rn_u.rn_node.rn_R 48 49 /* 50 * Annotations to tree concerning potential routes applying to subtrees. 51 */ 52 53 extern struct radix_mask { 54 short rm_b; /* bit offset; -1-index(netmask) */ 55 char rm_unused; /* cf. rn_bmask */ 56 u_char rm_flags; /* cf. rn_flags */ 57 struct radix_mask *rm_mklist; /* more masks to try */ 58 caddr_t rm_mask; /* the mask */ 59 int rm_refs; /* # of references to this struct */ 60 } *rn_mkfreelist; 61 62 #define MKGet(m) {\ 63 if (rn_mkfreelist) {\ 64 m = rn_mkfreelist; \ 65 rn_mkfreelist = (m)->rm_mklist; \ 66 } else \ 67 R_Malloc(m, struct radix_mask *, sizeof (*(m))); }\ 68 69 #define MKFree(m) { (m)->rm_mklist = rn_mkfreelist; rn_mkfreelist = (m);} 70 71 struct radix_node_head { 72 struct radix_node *rnh_treetop; 73 struct radix_node *(*rnh_add)(); 74 struct radix_node *(*rnh_delete)(); 75 struct radix_node *(*rnh_match)(); 76 int (*rnh_walk)(); 77 struct radix_node rnh_nodes[3]; 78 }; 79 80 81 #ifndef KERNEL 82 #define Bcmp(a, b, n) bcmp(((char *)(a)), ((char *)(b)), (n)) 83 #define Bzero(p, n) bzero((char *)(p), (int)(n)); 84 #define R_Malloc(p, t, n) (p = (t) malloc((unsigned int)(n))) 85 #define Free(p) free((char *)p); 86 #else 87 #define Bcmp(a, b, n) bcmp(((caddr_t)(a)), ((caddr_t)(b)), (unsigned)(n)) 88 #define Bcopy(a, b, n) bcopy(((caddr_t)(a)), ((caddr_t)(b)), (unsigned)(n)) 89 #define Bzero(p, n) bzero((caddr_t)(p), (unsigned)(n)); 90 #define R_Malloc(p, t, n) (p = (t) malloc((unsigned long)(n), M_RTABLE, M_DONTWAIT)) 91 #define Free(p) free((caddr_t)p, M_RTABLE); 92 #endif /*KERNEL*/ 93