radix.h
Go to the documentation of this file.
1 /*
2  * Copyright (C) 1996-2022 The Squid Software Foundation and contributors
3  *
4  * Squid software is distributed under GPLv2+ license and includes
5  * contributions from numerous individuals and organizations.
6  * Please see the COPYING and CONTRIBUTORS files for details.
7  */
8 
9 #ifndef SQUID_RADIX_H
10 #define SQUID_RADIX_H
11 
12 /*
13  * Copyright (c) 1988, 1989, 1993
14  * The Regents of the University of California. All rights reserved.
15  *
16  * Redistribution and use in source and binary forms, with or without
17  * modification, are permitted provided that the following conditions
18  * are met:
19  * 1. Redistributions of source code must retain the above copyright
20  * notice, this list of conditions and the following disclaimer.
21  * 2. Redistributions in binary form must reproduce the above copyright
22  * notice, this list of conditions and the following disclaimer in the
23  * documentation and/or other materials provided with the distribution.
24  * 3. All advertising materials mentioning features or use of this software
25  * must display the following acknowledgement:
26  * This product includes software developed by the University of
27  * California, Berkeley and its contributors.
28  * 4. Neither the name of the University nor the names of its contributors
29  * may be used to endorse or promote products derived from this software
30  * without specific prior written permission.
31  *
32  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
33  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
34  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
35  * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
36  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
37  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
38  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
39  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
40  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
41  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
42  * SUCH DAMAGE.
43  *
44  * @(#)radix.h 8.2 (Berkeley) 10/31/94
45  */
46 
47 /*
48  * Radix search tree node layout.
49  */
50 
52 
53  struct squid_radix_mask *rn_mklist; /* list of masks contained in subtree */
54 
55  struct squid_radix_node *rn_p; /* parent */
56  short rn_b; /* bit offset; -1-index(netmask) */
57  char rn_bmask; /* node: mask for bit test */
58  unsigned char rn_flags; /* enumerated next */
59 #define RNF_NORMAL 1 /* leaf contains normal route */
60 #define RNF_ROOT 2 /* leaf is root leaf for tree */
61 #define RNF_ACTIVE 4 /* This node is alive (for rtfree) */
62 
63  union {
64 
65  struct { /* leaf only data: */
66  char *rn_Key; /* object of search */
67  char *rn_Mask; /* netmask, if present */
68 
71 
72  struct { /* node only data: */
73  int rn_Off; /* where to start compare */
74 
75  struct squid_radix_node *rn_L; /* progeny */
76 
77  struct squid_radix_node *rn_R; /* progeny */
79  } rn_u;
80 };
81 
82 #define rn_key rn_u.rn_leaf.rn_Key
83 #define rn_mask rn_u.rn_leaf.rn_Mask
84 
85 /*
86  * Annotations to tree concerning potential routes applying to subtrees.
87  */
88 
90  short rm_b; /* bit offset; -1-index(netmask) */
91  char rm_unused; /* cf. rn_bmask */
92  unsigned char rm_flags; /* cf. rn_flags */
93 
94  struct squid_radix_mask *rm_mklist; /* more masks to try */
95  union {
96  char *rmu_mask; /* the mask */
97 
98  struct squid_radix_node *rmu_leaf; /* for normal routes */
99  } rm_rmu;
100  int rm_refs; /* # of references to this struct */
101 };
102 
104 
106  int rnh_addrsize; /* permit, but not require fixed keys */
107  int rnh_pktsize; /* permit, but not require fixed keys */
108 
109  struct squid_radix_node *(*rnh_addaddr) /* add based on sockaddr */
110  (void *v, void *mask, struct squid_radix_node_head * head, struct squid_radix_node nodes[]);
111 
112  struct squid_radix_node *(*rnh_addpkt) /* add based on packet hdr */
113  (void *v, void *mask, struct squid_radix_node_head * head, struct squid_radix_node nodes[]);
114 
115  struct squid_radix_node *(*rnh_deladdr) /* remove based on sockaddr */
116  (void *v, void *mask, struct squid_radix_node_head * head);
117 
118  struct squid_radix_node *(*rnh_delpkt) /* remove based on packet hdr */
119  (void *v, void *mask, struct squid_radix_node_head * head);
120 
121  struct squid_radix_node *(*rnh_matchaddr) /* locate based on sockaddr */
122  (void *v, struct squid_radix_node_head * head);
123 
124  struct squid_radix_node *(*rnh_lookup) /* locate based on sockaddr */
125 
126  (void *v, void *mask, struct squid_radix_node_head * head);
127 
128  struct squid_radix_node *(*rnh_matchpkt) /* locate based on packet hdr */
129  (void *v, struct squid_radix_node_head * head);
130 
131  int (*rnh_walktree) /* traverse tree */
132  (struct squid_radix_node_head * head, int (*f) (struct squid_radix_node *, void *), void *w);
133 
134  struct squid_radix_node rnh_nodes[3]; /* empty tree for common case */
135 };
136 
137 SQUIDCEXTERN void squid_rn_init (void);
138 
140 SQUIDCEXTERN int squid_rn_refines(void *, void *);
141 
142 SQUIDCEXTERN int squid_rn_walktree(struct squid_radix_node_head *, int (*)(struct squid_radix_node *, void *), void *);
143 
144 SQUIDCEXTERN struct squid_radix_node *squid_rn_addmask(void *, int, int);
145 
146 SQUIDCEXTERN struct squid_radix_node *squid_rn_addroute(void *, void *, struct squid_radix_node_head *, struct squid_radix_node[2]);
147 
148 SQUIDCEXTERN struct squid_radix_node *squid_rn_delete(void *, void *, struct squid_radix_node_head *);
149 
150 SQUIDCEXTERN struct squid_radix_node *squid_rn_insert(void *, struct squid_radix_node_head *, int *, struct squid_radix_node[2]);
151 
153 
154 SQUIDCEXTERN struct squid_radix_node *squid_rn_newpair(void *, int, struct squid_radix_node[2]);
155 
157 
158 SQUIDCEXTERN struct squid_radix_node *squid_rn_search_m(void *, struct squid_radix_node *, void *);
159 
160 SQUIDCEXTERN struct squid_radix_node *squid_rn_lookup(void *, void *, struct squid_radix_node_head *);
161 
162 #endif /* SQUID_RADIX_H */
163 
char rn_bmask
Definition: radix.h:57
SQUIDCEXTERN struct squid_radix_node * squid_rn_search_m(void *, struct squid_radix_node *, void *)
Definition: radix.c:166
SQUIDCEXTERN struct squid_radix_node * squid_rn_insert(void *, struct squid_radix_node_head *, int *, struct squid_radix_node[2])
Definition: radix.c:358
short rn_b
Definition: radix.h:56
SQUIDCEXTERN int squid_rn_refines(void *, void *)
Definition: radix.c:181
unsigned char rn_flags
Definition: radix.h:58
union squid_radix_mask::@19 rm_rmu
SQUIDCEXTERN int squid_rn_walktree(struct squid_radix_node_head *, int(*)(struct squid_radix_node *, void *), void *)
Definition: radix.c:818
short rm_b
Definition: radix.h:90
unsigned char rm_flags
Definition: radix.h:92
struct squid_radix_node * rn_p
Definition: radix.h:55
char * rn_Key
Definition: radix.h:66
struct squid_radix_mask * rm_mklist
Definition: radix.h:94
char rm_unused
Definition: radix.h:91
SQUIDCEXTERN void squid_rn_init(void)
Definition: radix.c:884
struct squid_radix_node::@16::@18 rn_node
#define SQUIDCEXTERN
Definition: squid.h:21
SQUIDCEXTERN int squid_rn_inithead(struct squid_radix_node_head **, int)
Definition: radix.c:854
SQUIDCEXTERN struct squid_radix_node * squid_rn_addroute(void *, void *, struct squid_radix_node_head *, struct squid_radix_node[2])
Definition: radix.c:520
SQUIDCEXTERN struct squid_radix_node * squid_rn_newpair(void *, int, struct squid_radix_node[2])
Definition: radix.c:344
SQUIDCEXTERN struct squid_radix_node * squid_rn_search(void *, struct squid_radix_node *)
Definition: radix.c:152
struct squid_radix_node rnh_nodes[3]
Definition: radix.h:134
char * rn_Mask
Definition: radix.h:67
union squid_radix_node::@16 rn_u
struct squid_radix_node * rmu_leaf
Definition: radix.h:98
SQUIDCEXTERN struct squid_radix_node * squid_rn_match(void *, struct squid_radix_node_head *)
Definition: radix.c:245
struct squid_radix_node * rnh_treetop
Definition: radix.h:105
struct squid_radix_node * rn_R
Definition: radix.h:77
SQUIDCEXTERN struct squid_radix_node * squid_rn_lookup(void *, void *, struct squid_radix_node_head *)
Definition: radix.c:207
squidaio_request_t * head
Definition: aiops.cc:126
struct squid_radix_node * rn_L
Definition: radix.h:75
SQUIDCEXTERN struct squid_radix_node * squid_rn_delete(void *, void *, struct squid_radix_node_head *)
Definition: radix.c:665
struct squid_radix_node * rn_Dupedkey
Definition: radix.h:69
SQUIDCEXTERN struct squid_radix_node * squid_rn_addmask(void *, int, int)
Definition: radix.c:414
int rnh_walktree(struct squid_radix_node_head *head, int(*f)(struct squid_radix_node *, void *), void *w)
char * rmu_mask
Definition: radix.h:96
int unsigned int
Definition: stub_fd.cc:19
struct squid_radix_mask * rn_mklist
Definition: radix.h:53
struct squid_radix_node::@16::@17 rn_leaf

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors