radix.h
Go to the documentation of this file.
1/*
2 * Copyright (C) 1996-2023 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 */
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 */
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
137SQUIDCEXTERN void squid_rn_init (void);
138
140SQUIDCEXTERN int squid_rn_refines(void *, void *);
141
142SQUIDCEXTERN int squid_rn_walktree(struct squid_radix_node_head *, int (*)(struct squid_radix_node *, void *), void *);
143
144SQUIDCEXTERN struct squid_radix_node *squid_rn_addmask(void *, int, int);
145
147
149
151
153
154SQUIDCEXTERN struct squid_radix_node *squid_rn_newpair(void *, int, struct squid_radix_node[2]);
155
157
158SQUIDCEXTERN struct squid_radix_node *squid_rn_search_m(void *, struct squid_radix_node *, void *);
159
161
162#endif /* SQUID_RADIX_H */
163
squidaio_request_t * head
Definition: aiops.cc:127
SQUIDCEXTERN struct squid_radix_node * squid_rn_lookup(void *, void *, struct squid_radix_node_head *)
Definition: radix.c:207
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_search(void *, struct squid_radix_node *)
Definition: radix.c:152
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_insert(void *, struct squid_radix_node_head *, int *, struct squid_radix_node[2])
Definition: radix.c:358
SQUIDCEXTERN struct squid_radix_node * squid_rn_delete(void *, void *, struct squid_radix_node_head *)
Definition: radix.c:665
SQUIDCEXTERN struct squid_radix_node * squid_rn_match(void *, struct squid_radix_node_head *)
Definition: radix.c:245
SQUIDCEXTERN int squid_rn_inithead(struct squid_radix_node_head **, int)
Definition: radix.c:854
SQUIDCEXTERN int squid_rn_walktree(struct squid_radix_node_head *, int(*)(struct squid_radix_node *, void *), void *)
Definition: radix.c:818
SQUIDCEXTERN struct squid_radix_node * squid_rn_addmask(void *, int, int)
Definition: radix.c:414
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 void squid_rn_init(void)
Definition: radix.c:884
SQUIDCEXTERN int squid_rn_refines(void *, void *)
Definition: radix.c:181
#define SQUIDCEXTERN
Definition: squid.h:21
char rm_unused
Definition: radix.h:91
char * rmu_mask
Definition: radix.h:96
struct squid_radix_node * rmu_leaf
Definition: radix.h:98
union squid_radix_mask::@18 rm_rmu
unsigned char rm_flags
Definition: radix.h:92
short rm_b
Definition: radix.h:90
struct squid_radix_mask * rm_mklist
Definition: radix.h:94
int rnh_walktree(struct squid_radix_node_head *head, int(*f)(struct squid_radix_node *, void *), void *w)
struct squid_radix_node * rnh_treetop
Definition: radix.h:105
struct squid_radix_node rnh_nodes[3]
Definition: radix.h:134
struct squid_radix_node * rn_Dupedkey
Definition: radix.h:69
struct squid_radix_node * rn_p
Definition: radix.h:55
struct squid_radix_node::@15::@16 rn_leaf
short rn_b
Definition: radix.h:56
char rn_bmask
Definition: radix.h:57
struct squid_radix_mask * rn_mklist
Definition: radix.h:53
struct squid_radix_node::@15::@17 rn_node
union squid_radix_node::@15 rn_u
char * rn_Key
Definition: radix.h:66
char * rn_Mask
Definition: radix.h:67
struct squid_radix_node * rn_L
Definition: radix.h:75
struct squid_radix_node * rn_R
Definition: radix.h:77
unsigned char rn_flags
Definition: radix.h:58
int unsigned int
Definition: stub_fd.cc:19

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors