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.4 (Berkeley) 06/28/90 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 MAXKEYLEN 32 43 44 #define rn_dupedkey rn_u.rn_leaf.rn_Dupedkey 45 #define rn_key rn_u.rn_leaf.rn_Key 46 #define rn_mask rn_u.rn_leaf.rn_Mask 47 #define rn_off rn_u.rn_node.rn_Off 48 #define rn_l rn_u.rn_node.rn_L 49 #define rn_r rn_u.rn_node.rn_R 50 51 /* 52 * Annotations to tree concerning potential routes applying to subtrees. 53 */ 54 55 extern struct radix_mask { 56 short rm_b; /* bit offset; -1-index(netmask) */ 57 char rm_unused; /* cf. rn_bmask */ 58 u_char rm_flags; /* cf. rn_flags */ 59 struct radix_mask *rm_mklist; /* more masks to try */ 60 caddr_t rm_mask; /* the mask */ 61 int rm_refs; /* # of references to this struct */ 62 } *rn_mkfreelist; 63 64 #define MKGet(m) {\ 65 if (rn_mkfreelist) {\ 66 m = rn_mkfreelist; \ 67 rn_mkfreelist = (m)->rm_mklist; \ 68 } else \ 69 R_Malloc(m, struct radix_mask *, sizeof (*(m))); }\ 70 71 #define MKFree(m) { (m)->rm_mklist = rn_mkfreelist; rn_mkfreelist = (m);} 72 73 extern struct radix_node_head { 74 struct radix_node_head *rnh_next; 75 struct radix_node *rnh_treetop; 76 int rnh_af; 77 struct radix_node rnh_nodes[3]; 78 } *radix_node_head; 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