/[svn]/hopm/trunk/src/patricia.h
ViewVC logotype

Annotation of /hopm/trunk/src/patricia.h

Parent Directory Parent Directory | Revision Log Revision Log


Revision 8753 - (hide annotations)
Tue Jan 1 13:56:48 2019 UTC (22 months, 3 weeks ago) by michael
File MIME type: text/x-csrc
File size: 5194 byte(s)
- patricia: update to latest version from ircd-hybrid

1 michael 5042 /*
2 michael 6259 * $Id$
3 michael 5042 * Dave Plonka <plonka@doit.wisc.edu>
4     *
5     * This file had been called "radix.h" in the MRT sources.
6     *
7     * I renamed it to "patricia.h" since it's not an implementation of a general
8     * radix trie. Also, pulled in various requirements from "mrt.h" and added
9     * some other things it could be used as a standalone API.
10 michael 5046 *
11     * Copyright (c) 1999-2013
12     *
13     * The Regents of the University of Michigan ("The Regents") and Merit
14     * Network, Inc.
15     *
16     * Redistributions of source code must retain the above copyright notice,
17     * this list of conditions and the following disclaimer.
18     *
19     * Redistributions in binary form must reproduce the above copyright
20     * notice, this list of conditions and the following disclaimer in the
21     * documentation and/or other materials provided with the distribution.
22     *
23     * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
24     * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
25     * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
26     * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
27     * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
28     * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
29     * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
30     * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
31     * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
32     * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
33     * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
34 michael 5042 */
35    
36     #ifndef _PATRICIA_H
37     #define _PATRICIA_H
38    
39     /* { from defs.h */
40 michael 7806 #define prefix_touchar(prefix) ((unsigned char *)&(prefix)->add.sin)
41 michael 5042 #define BIT_TEST(f, b) ((f) & (b))
42     /* } */
43    
44 michael 7834 #include <netinet/in.h> /* for struct in_addr */
45     #include <sys/socket.h> /* for AF_INET */
46 michael 5042
47     /* { from mrt.h */
48 michael 7834 typedef struct _prefix_t
49     {
50     unsigned short family; /* AF_INET | AF_INET6 */
51     unsigned short bitlen; /* same as mask? */
52     int ref_count; /* reference count */
53 michael 5042
54 michael 7834 union
55     {
56     struct in_addr sin;
57     struct in6_addr sin6;
58     } add;
59 michael 5042 } prefix_t;
60     /* } */
61    
62 michael 7834 typedef struct _patricia_node_t
63     {
64     unsigned int bit; /* flag if this node used */
65     prefix_t *prefix; /* who we are in patricia tree */
66     struct _patricia_node_t *l, *r; /* left and right children */
67     struct _patricia_node_t *parent; /* may be used */
68     void *data; /* pointer to data */
69 michael 5042 } patricia_node_t;
70    
71 michael 7834 typedef struct _patricia_tree_t
72     {
73     patricia_node_t *head;
74     unsigned int maxbits; /* for IP, 32 bit addresses */
75     int num_active_node; /* for debug purpose */
76 michael 5042 } patricia_tree_t;
77    
78    
79 michael 7834 extern patricia_node_t *patricia_search_exact(patricia_tree_t *, prefix_t *);
80     extern patricia_node_t *patricia_search_best(patricia_tree_t *, prefix_t *);
81     extern patricia_node_t *patricia_search_best2(patricia_tree_t *, prefix_t *, int);
82     extern patricia_node_t *patricia_lookup(patricia_tree_t *, prefix_t *);
83     extern void patricia_remove(patricia_tree_t *, patricia_node_t *);
84 michael 7846 extern patricia_tree_t *patricia_new(unsigned int);
85     extern void patricia_clear(patricia_tree_t *, void (*)(void *));
86     extern void patricia_destroy(patricia_tree_t *, void (*)(void *));
87 michael 7834 extern void patricia_process(patricia_tree_t *, void (*)(prefix_t *, void *));
88 michael 7846 extern const char *patricia_prefix_toa(const prefix_t *, int);
89     extern void patricia_lookup_then_remove(patricia_tree_t *, const char *);
90     extern patricia_node_t *patricia_try_search_exact(patricia_tree_t *, const char *);
91     extern patricia_node_t *patricia_try_search_best(patricia_tree_t *, const char *);
92 michael 7847 extern patricia_node_t *patricia_try_search_exact_addr(patricia_tree_t *, struct sockaddr *, int);
93     extern patricia_node_t *patricia_try_search_best_addr(patricia_tree_t *, struct sockaddr *, int);
94 michael 7834
95 michael 5042 /* { from demo.c */
96 michael 7846 extern patricia_node_t *patricia_make_and_lookup(patricia_tree_t *, const char *);
97 michael 8753 extern patricia_node_t *patricia_make_and_lookup_addr(patricia_tree_t *, struct sockaddr *, int);
98 michael 5042 /* } */
99    
100 michael 7834 #define PATRICIA_MAXBITS (sizeof(struct in6_addr) * 8)
101     #define PATRICIA_NBIT(x) (0x80 >> ((x) & 0x7f))
102     #define PATRICIA_NBYTE(x) ((x) >> 3)
103 michael 5042
104     #define PATRICIA_DATA_GET(node, type) (type *)((node)->data)
105     #define PATRICIA_DATA_SET(node, value) ((node)->data = (void *)(value))
106    
107     #define PATRICIA_WALK(Xhead, Xnode) \
108 michael 7834 do { \
109     patricia_node_t *Xstack[PATRICIA_MAXBITS + 1]; \
110     patricia_node_t **Xsp = Xstack; \
111     patricia_node_t *Xrn = (Xhead); \
112     while ((Xnode = Xrn)) { \
113     if (Xnode->prefix)
114 michael 5042
115     #define PATRICIA_WALK_ALL(Xhead, Xnode) \
116 michael 7834 do { \
117     patricia_node_t *Xstack[PATRICIA_MAXBITS + 1]; \
118     patricia_node_t **Xsp = Xstack; \
119     patricia_node_t *Xrn = (Xhead); \
120     while ((Xnode = Xrn)) { \
121     if (1)
122 michael 5042
123     #define PATRICIA_WALK_BREAK { \
124 michael 7834 if (Xsp != Xstack) { \
125     Xrn = *(--Xsp); \
126     } else { \
127     Xrn = (patricia_node_t *)0; \
128     } \
129     continue; }
130 michael 5042
131     #define PATRICIA_WALK_END \
132 michael 7834 if (Xrn->l) { \
133     if (Xrn->r) { \
134     *Xsp++ = Xrn->r; \
135     } \
136     Xrn = Xrn->l; \
137     } else if (Xrn->r) { \
138     Xrn = Xrn->r; \
139     } else if (Xsp != Xstack) { \
140     Xrn = *(--Xsp); \
141     } else { \
142     Xrn = (patricia_node_t *)0; \
143     } \
144     } \
145     } while (0)
146 michael 5042
147 michael 7834 #endif

Properties

Name Value
svn:eol-style native
svn:keywords Id

svnadmin@ircd-hybrid.org
ViewVC Help
Powered by ViewVC 1.1.28