radix.h
Go to the documentation of this file.
1 /*
2  * Copyright (C) 1996-2017 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 #undef RN_DEBUG
48 /*
49  * Radix search tree node layout.
50  */
51 
53 
54  struct squid_radix_mask *rn_mklist; /* list of masks contained in subtree */
55 
56  struct squid_radix_node *rn_p; /* parent */
57  short rn_b; /* bit offset; -1-index(netmask) */
58  char rn_bmask; /* node: mask for bit test */
59  unsigned char rn_flags; /* enumerated next */
60 #define RNF_NORMAL 1 /* leaf contains normal route */
61 #define RNF_ROOT 2 /* leaf is root leaf for tree */
62 #define RNF_ACTIVE 4 /* This node is alive (for rtfree) */
63 
64  union {
65 
66  struct { /* leaf only data: */
67  char *rn_Key; /* object of search */
68  char *rn_Mask; /* netmask, if present */
69 
71  } rn_leaf;
72 
73  struct { /* node only data: */
74  int rn_Off; /* where to start compare */
75 
76  struct squid_radix_node *rn_L; /* progeny */
77 
78  struct squid_radix_node *rn_R; /* progeny */
79  } rn_node;
80  } rn_u;
81 #ifdef RN_DEBUG
82 
83  int rn_info;
84 
85  struct squid_radix_node *rn_twin;
86 
87  struct squid_radix_node *rn_ybro;
88 #endif
89 };
90 
91 #define rn_key rn_u.rn_leaf.rn_Key
92 #define rn_mask rn_u.rn_leaf.rn_Mask
93 
94 /*
95  * Annotations to tree concerning potential routes applying to subtrees.
96  */
97 
99  short rm_b; /* bit offset; -1-index(netmask) */
100  char rm_unused; /* cf. rn_bmask */
101  unsigned char rm_flags; /* cf. rn_flags */
102 
103  struct squid_radix_mask *rm_mklist; /* more masks to try */
104  union {
105  char *rmu_mask; /* the mask */
106 
107  struct squid_radix_node *rmu_leaf; /* for normal routes */
108  } rm_rmu;
109  int rm_refs; /* # of references to this struct */
110 };
111 
113 
115  int rnh_addrsize; /* permit, but not require fixed keys */
116  int rnh_pktsize; /* permit, but not require fixed keys */
117 
118  struct squid_radix_node *(*rnh_addaddr) /* add based on sockaddr */
119  (void *v, void *mask, struct squid_radix_node_head * head, struct squid_radix_node nodes[]);
120 
121  struct squid_radix_node *(*rnh_addpkt) /* add based on packet hdr */
122  (void *v, void *mask, struct squid_radix_node_head * head, struct squid_radix_node nodes[]);
123 
124  struct squid_radix_node *(*rnh_deladdr) /* remove based on sockaddr */
125  (void *v, void *mask, struct squid_radix_node_head * head);
126 
127  struct squid_radix_node *(*rnh_delpkt) /* remove based on packet hdr */
128  (void *v, void *mask, struct squid_radix_node_head * head);
129 
130  struct squid_radix_node *(*rnh_matchaddr) /* locate based on sockaddr */
131  (void *v, struct squid_radix_node_head * head);
132 
133  struct squid_radix_node *(*rnh_lookup) /* locate based on sockaddr */
134 
135  (void *v, void *mask, struct squid_radix_node_head * head);
136 
137  struct squid_radix_node *(*rnh_matchpkt) /* locate based on packet hdr */
138  (void *v, struct squid_radix_node_head * head);
139 
140  int (*rnh_walktree) /* traverse tree */
141  (struct squid_radix_node_head * head, int (*f) (struct squid_radix_node *, void *), void *w);
142 
143  struct squid_radix_node rnh_nodes[3]; /* empty tree for common case */
144 };
145 
146 SQUIDCEXTERN void squid_rn_init (void);
147 
149 SQUIDCEXTERN int squid_rn_refines(void *, void *);
150 
151 SQUIDCEXTERN int squid_rn_walktree(struct squid_radix_node_head *, int (*)(struct squid_radix_node *, void *), void *);
152 
153 SQUIDCEXTERN struct squid_radix_node *squid_rn_addmask(void *, int, int);
154 
155 SQUIDCEXTERN struct squid_radix_node *squid_rn_addroute(void *, void *, struct squid_radix_node_head *, struct squid_radix_node[2]);
156 
157 SQUIDCEXTERN struct squid_radix_node *squid_rn_delete(void *, void *, struct squid_radix_node_head *);
158 
159 SQUIDCEXTERN struct squid_radix_node *squid_rn_insert(void *, struct squid_radix_node_head *, int *, struct squid_radix_node[2]);
160 
162 
163 SQUIDCEXTERN struct squid_radix_node *squid_rn_newpair(void *, int, struct squid_radix_node[2]);
164 
166 
167 SQUIDCEXTERN struct squid_radix_node *squid_rn_search_m(void *, struct squid_radix_node *, void *);
168 
169 SQUIDCEXTERN struct squid_radix_node *squid_rn_lookup(void *, void *, struct squid_radix_node_head *);
170 
171 #endif /* SQUID_RADIX_H */
172 
struct squid_radix_mask * rm_mklist
Definition: radix.h:103
struct squid_radix_node * rmu_leaf
Definition: radix.h:107
SQUIDCEXTERN int squid_rn_refines(void *, void *)
Definition: radix.c:181
unsigned char rm_flags
Definition: radix.h:101
char rn_bmask
Definition: radix.h:58
SQUIDCEXTERN struct squid_radix_node * squid_rn_insert(void *, struct squid_radix_node_head *, int *, struct squid_radix_node[2])
Definition: radix.c:372
#define SQUIDCEXTERN
Definition: squid.h:26
SQUIDCEXTERN struct squid_radix_node * squid_rn_lookup(void *, void *, struct squid_radix_node_head *)
Definition: radix.c:207
struct squid_radix_node * rn_R
Definition: radix.h:78
SQUIDCEXTERN struct squid_radix_node * squid_rn_search(void *, struct squid_radix_node *)
Definition: radix.c:152
SQUIDCEXTERN int squid_rn_walktree(struct squid_radix_node_head *, int(*)(struct squid_radix_node *, void *), void *)
Definition: radix.c:875
short rm_b
Definition: radix.h:99
struct squid_radix_node * rn_p
Definition: radix.h:56
struct squid_radix_node::@16::@18 rn_node
SQUIDCEXTERN struct squid_radix_node * squid_rn_delete(void *, void *, struct squid_radix_node_head *)
Definition: radix.c:696
SQUIDCEXTERN struct squid_radix_node * squid_rn_search_m(void *, struct squid_radix_node *, void *)
Definition: radix.c:166
struct squid_radix_node rnh_nodes[3]
Definition: radix.h:143
SQUIDCEXTERN struct squid_radix_node * squid_rn_match(void *, struct squid_radix_node_head *)
Definition: radix.c:245
SQUIDCEXTERN struct squid_radix_node * squid_rn_addmask(void *, int, int)
Definition: radix.c:437
char * rmu_mask
Definition: radix.h:105
unsigned char rn_flags
Definition: radix.h:59
bool SIGHDLR int STUB void int
Definition: stub_tools.cc:68
struct squid_radix_node * rnh_treetop
Definition: radix.h:114
union squid_radix_node::@16 rn_u
struct squid_radix_node * rn_Dupedkey
Definition: radix.h:70
short rn_b
Definition: radix.h:57
union squid_radix_mask::@19 rm_rmu
int rnh_walktree(struct squid_radix_node_head *head, int(*f)(struct squid_radix_node *, void *), void *w)
SQUIDCEXTERN struct squid_radix_node * squid_rn_newpair(void *, int, struct squid_radix_node[2])
Definition: radix.c:351
SQUIDCEXTERN int squid_rn_inithead(struct squid_radix_node_head **, int)
Definition: radix.c:911
struct squid_radix_mask * rn_mklist
Definition: radix.h:54
struct squid_radix_node * rn_L
Definition: radix.h:76
char * rn_Key
Definition: radix.h:67
char rm_unused
Definition: radix.h:100
SQUIDCEXTERN struct squid_radix_node * squid_rn_addroute(void *, void *, struct squid_radix_node_head *, struct squid_radix_node[2])
Definition: radix.c:543
squidaio_request_t * head
Definition: aiops.cc:127
struct squid_radix_node::@16::@17 rn_leaf
char * rn_Mask
Definition: radix.h:68
SQUIDCEXTERN void squid_rn_init(void)
Definition: radix.c:941

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors