Commit | Line | Data |
---|---|---|
2c436e5d | 1 | /* |
c8dfc989 KB |
2 | * Copyright (c) 1988, 1989, 1993 |
3 | * The Regents of the University of California. All rights reserved. | |
2c436e5d | 4 | * |
dbf0c423 | 5 | * %sccs.include.redist.c% |
2c436e5d | 6 | * |
4ba36fcc | 7 | * @(#)radix.h 8.2 (Berkeley) %G% |
2c436e5d KS |
8 | */ |
9 | ||
4a3f9c07 KM |
10 | #ifndef _RADIX_H_ |
11 | #define _RADIX_H_ | |
12 | ||
2c436e5d KS |
13 | /* |
14 | * Radix search tree node layout. | |
15 | */ | |
16 | ||
17 | struct radix_node { | |
52e31907 | 18 | struct radix_node *rn_mklist; /* list of masks contained in subtree */ |
2c436e5d KS |
19 | struct radix_node *rn_p; /* parent */ |
20 | short rn_b; /* bit offset; -1-index(netmask) */ | |
21 | char rn_bmask; /* node: mask for bit test*/ | |
22 | u_char rn_flags; /* enumerated next */ | |
23 | #define RNF_NORMAL 1 /* leaf contains normal route */ | |
24 | #define RNF_ROOT 2 /* leaf is root leaf for tree */ | |
25 | #define RNF_ACTIVE 4 /* This node is alive (for rtfree) */ | |
26 | union { | |
27 | struct { /* leaf only data: */ | |
573d82c4 KS |
28 | caddr_t rn_Key; /* object of search */ |
29 | caddr_t rn_Mask; /* netmask, if present */ | |
2c436e5d KS |
30 | struct radix_node *rn_Dupedkey; |
31 | } rn_leaf; | |
32 | struct { /* node only data: */ | |
33 | int rn_Off; /* where to start compare */ | |
34 | struct radix_node *rn_L;/* progeny */ | |
35 | struct radix_node *rn_R;/* progeny */ | |
36 | }rn_node; | |
37 | } rn_u; | |
38 | #ifdef RN_DEBUG | |
39 | int rn_info; | |
40 | struct radix_node *rn_twin; | |
41 | struct radix_node *rn_ybro; | |
42 | #endif | |
43 | }; | |
44 | ||
45 | #define rn_dupedkey rn_u.rn_leaf.rn_Dupedkey | |
46 | #define rn_key rn_u.rn_leaf.rn_Key | |
47 | #define rn_mask rn_u.rn_leaf.rn_Mask | |
48 | #define rn_off rn_u.rn_node.rn_Off | |
49 | #define rn_l rn_u.rn_node.rn_L | |
50 | #define rn_r rn_u.rn_node.rn_R | |
573d82c4 | 51 | |
39d2b165 | 52 | struct radix_node_head { |
573d82c4 | 53 | struct radix_node *rnh_treetop; |
d2ca79ee KS |
54 | int rnh_addrsize; /* permit, but not require fixed keys */ |
55 | int rnh_pktsize; /* permit, but not require fixed keys */ | |
56 | struct radix_node *(*rnh_addaddr) /* add based on sockaddr */ | |
6d869adf | 57 | __P((void *v, void *mask, |
d2ca79ee KS |
58 | struct radix_node_head *head, struct radix_node nodes[])); |
59 | struct radix_node *(*rnh_addpkt) /* add based on packet hdr */ | |
6d869adf | 60 | __P((void *v, void *mask, |
d2ca79ee KS |
61 | struct radix_node_head *head, struct radix_node nodes[])); |
62 | struct radix_node *(*rnh_deladdr) /* remove based on sockaddr */ | |
6d869adf | 63 | __P((void *v, void *mask, struct radix_node_head *head)); |
d2ca79ee | 64 | struct radix_node *(*rnh_delpkt) /* remove based on packet hdr */ |
6d869adf | 65 | __P((void *v, void *mask, struct radix_node_head *head)); |
d2ca79ee | 66 | struct radix_node *(*rnh_matchaddr) /* locate based on sockaddr */ |
6d869adf | 67 | __P((void *v, struct radix_node_head *head)); |
c280fd00 KS |
68 | struct radix_node *(*rnh_lookup) /* locate based on sockaddr */ |
69 | __P((void *v, void *mask, struct radix_node_head *head)); | |
4ba36fcc KS |
70 | struct radix_node *(*rnh_lookup) /* locate based on sockaddr */ |
71 | __P((void *v, void *mask, struct radix_node_head *head)); | |
d2ca79ee | 72 | struct radix_node *(*rnh_matchpkt) /* locate based on packet hdr */ |
6d869adf | 73 | __P((void *v, struct radix_node_head *head)); |
d2ca79ee KS |
74 | int (*rnh_walktree) /* traverse tree */ |
75 | __P((struct radix_node_head *head, int (*f)(), void *w)); | |
52e31907 KS |
76 | /* mapping stuff */ |
77 | struct radix_index_table { | |
78 | short limit; | |
79 | short offset; | |
80 | } *rnh_table; /* how to re-order the bits */ | |
81 | int rnh_offset; /* for martialed keys */ | |
82 | int (*rnh_bits_matched) /* used in matching, insert */ | |
83 | __P((void *trial, void *ref, | |
84 | struct radix_node_head *head, int masklen)); | |
85 | int (*rnh_set_mask) /* used in insertion */ | |
86 | __P((int index, | |
87 | struct radix_node *rn, struct radix_node_head *rnh)); | |
88 | /* the treetop itself */ | |
d2ca79ee | 89 | struct radix_node rnh_nodes[3]; /* empty tree for common case */ |
39d2b165 | 90 | }; |
573d82c4 | 91 | |
2c436e5d KS |
92 | |
93 | #ifndef KERNEL | |
2c436e5d | 94 | #define Bcmp(a, b, n) bcmp(((char *)(a)), ((char *)(b)), (n)) |
c280fd00 | 95 | #define Bcopy(a, b, n) bcopy(((char *)(a)), ((char *)(b)), (unsigned)(n)) |
4ba36fcc | 96 | #define Bcopy(a, b, n) bcopy(((char *)(a)), ((char *)(b)), (unsigned)(n)) |
2c436e5d | 97 | #define Bzero(p, n) bzero((char *)(p), (int)(n)); |
573d82c4 | 98 | #define R_Malloc(p, t, n) (p = (t) malloc((unsigned int)(n))) |
2c436e5d | 99 | #define Free(p) free((char *)p); |
2c436e5d | 100 | #else |
b72a6efb KS |
101 | #define Bcmp(a, b, n) bcmp(((caddr_t)(a)), ((caddr_t)(b)), (unsigned)(n)) |
102 | #define Bcopy(a, b, n) bcopy(((caddr_t)(a)), ((caddr_t)(b)), (unsigned)(n)) | |
103 | #define Bzero(p, n) bzero((caddr_t)(p), (unsigned)(n)); | |
104 | #define R_Malloc(p, t, n) (p = (t) malloc((unsigned long)(n), M_RTABLE, M_DONTWAIT)) | |
105 | #define Free(p) free((caddr_t)p, M_RTABLE); | |
52e31907 | 106 | #endif /*KERNEL*/ |
c280fd00 | 107 | #endif /*KERNEL*/ |
4ba36fcc | 108 | #endif /*KERNEL*/ |
5c48f39f | 109 | |
6d869adf KB |
110 | void rn_init __P((void)); |
111 | int rn_inithead __P((void **, int)); | |
112 | int rn_refines __P((void *, void *)); | |
113 | int rn_walktree __P((struct radix_node_head *, int (*)(), void *)); | |
114 | struct radix_node | |
115 | *rn_addmask __P((void *, int, int)), | |
116 | *rn_addroute __P((void *, void *, struct radix_node_head *, | |
117 | struct radix_node [2])), | |
118 | *rn_delete __P((void *, void *, struct radix_node_head *)), | |
119 | *rn_insert __P((void *, struct radix_node_head *, int *, | |
120 | struct radix_node [2])), | |
121 | *rn_match __P((void *, struct radix_node_head *)), | |
122 | *rn_newpair __P((void *, int, struct radix_node[2])), | |
123 | *rn_search __P((void *, struct radix_node *)), | |
52e31907 KS |
124 | *rn_search_unmapped __P((void *, struct radix_node_head *)); |
125 | ||
126 | int rn_set_unmapped_mask | |
127 | __P((int, struct radix_node *, struct radix_node_head *)), | |
128 | rn_set_mapped_mask | |
129 | __P((int, struct radix_node *, struct radix_node_head *)), | |
130 | rn_mapped_bits_matched | |
131 | __P((void *, void *, struct radix_node_head *, int)), | |
132 | rn_unmapped_bits_matched | |
133 | __P((void *, void *, struct radix_node_head *, int)); | |
134 | ||
6d869adf | 135 | |
4a3f9c07 | 136 | #endif /* _RADIX_H_ */ |