ViewVC Help
View File | Revision Log | Show Annotations | View Changeset | Root Listing
root/svn/hopm/trunk/src/patricia.h
Revision: 5792
Committed: Tue Apr 14 17:58:04 2015 UTC (8 years, 11 months ago) by michael
Content type: text/x-chdr
Original Path: ircd-hybrid/trunk/include/patricia.h
File size: 5640 byte(s)
Log Message:
- patricia.h: removed some windows support leftovers

File Contents

# User Rev Content
1 michael 5042 /*
2     * $Id: patricia.h,v 1.6 2005/12/07 20:53:01 dplonka Exp $
3     * 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     /* typedef unsigned int u_int; */
40     typedef void (*void_fn_t)();
41     /* { from defs.h */
42     #define prefix_touchar(prefix) ((u_char *)&(prefix)->add.sin)
43     #define MAXLINE 1024
44     #define BIT_TEST(f, b) ((f) & (b))
45     /* } */
46    
47     #define addroute make_and_lookup
48    
49     #include <sys/types.h> /* for u_* definitions (on FreeBSD 5) */
50    
51     #include <errno.h> /* for EAFNOSUPPORT */
52 michael 5792 #include <netinet/in.h> /* for struct in_addr */
53 michael 5042 #include <sys/socket.h> /* for AF_INET */
54    
55     /* { from mrt.h */
56    
57     typedef struct _prefix4_t {
58     u_short family; /* AF_INET | AF_INET6 */
59     u_short bitlen; /* same as mask? */
60     int ref_count; /* reference count */
61     struct in_addr sin;
62     } prefix4_t;
63    
64     typedef struct _prefix_t {
65     u_short family; /* AF_INET | AF_INET6 */
66     u_short bitlen; /* same as mask? */
67     int ref_count; /* reference count */
68     union {
69     struct in_addr sin;
70     struct in6_addr sin6;
71     } add;
72     } prefix_t;
73    
74     /* } */
75    
76     typedef struct _patricia_node_t {
77     u_int bit; /* flag if this node used */
78     prefix_t *prefix; /* who we are in patricia tree */
79     struct _patricia_node_t *l, *r; /* left and right children */
80     struct _patricia_node_t *parent;/* may be used */
81     void *data; /* pointer to data */
82     void *user1; /* pointer to usr data (ex. route flap info) */
83     } patricia_node_t;
84    
85     typedef struct _patricia_tree_t {
86     patricia_node_t *head;
87     u_int maxbits; /* for IP, 32 bit addresses */
88     int num_active_node; /* for debug purpose */
89     } patricia_tree_t;
90    
91    
92 michael 5043 extern patricia_node_t *patricia_search_exact (patricia_tree_t *patricia, prefix_t *prefix);
93     extern patricia_node_t *patricia_search_best (patricia_tree_t *patricia, prefix_t *prefix);
94     extern patricia_node_t * patricia_search_best2 (patricia_tree_t *patricia, prefix_t *prefix,
95 michael 5042 int inclusive);
96 michael 5043 extern patricia_node_t *patricia_lookup (patricia_tree_t *patricia, prefix_t *prefix);
97     extern void patricia_remove (patricia_tree_t *patricia, patricia_node_t *node);
98     extern patricia_tree_t *New_Patricia (int maxbits);
99     extern void Clear_Patricia (patricia_tree_t *patricia, void_fn_t func);
100     extern void Destroy_Patricia (patricia_tree_t *patricia, void_fn_t func);
101 michael 5042
102 michael 5043 extern void patricia_process (patricia_tree_t *patricia, void_fn_t func);
103 michael 5042
104 michael 5043 extern const char *prefix_toa (prefix_t * prefix);
105     extern void lookup_then_remove(patricia_tree_t *, char *);
106     extern patricia_node_t *try_search_exact(patricia_tree_t *, char *);
107 michael 5042 /* { from demo.c */
108    
109 michael 5043 extern prefix_t *
110 michael 5042 ascii2prefix (int family, char *string);
111    
112 michael 5043 extern patricia_node_t *
113 michael 5042 make_and_lookup (patricia_tree_t *tree, char *string);
114    
115     /* } */
116    
117     #define PATRICIA_MAXBITS (sizeof(struct in6_addr) * 8)
118     #define PATRICIA_NBIT(x) (0x80 >> ((x) & 0x7f))
119     #define PATRICIA_NBYTE(x) ((x) >> 3)
120    
121     #define PATRICIA_DATA_GET(node, type) (type *)((node)->data)
122     #define PATRICIA_DATA_SET(node, value) ((node)->data = (void *)(value))
123    
124     #define PATRICIA_WALK(Xhead, Xnode) \
125     do { \
126     patricia_node_t *Xstack[PATRICIA_MAXBITS+1]; \
127     patricia_node_t **Xsp = Xstack; \
128     patricia_node_t *Xrn = (Xhead); \
129     while ((Xnode = Xrn)) { \
130     if (Xnode->prefix)
131    
132     #define PATRICIA_WALK_ALL(Xhead, Xnode) \
133     do { \
134     patricia_node_t *Xstack[PATRICIA_MAXBITS+1]; \
135     patricia_node_t **Xsp = Xstack; \
136     patricia_node_t *Xrn = (Xhead); \
137     while ((Xnode = Xrn)) { \
138     if (1)
139    
140     #define PATRICIA_WALK_BREAK { \
141     if (Xsp != Xstack) { \
142     Xrn = *(--Xsp); \
143     } else { \
144     Xrn = (patricia_node_t *) 0; \
145     } \
146     continue; }
147    
148     #define PATRICIA_WALK_END \
149     if (Xrn->l) { \
150     if (Xrn->r) { \
151     *Xsp++ = Xrn->r; \
152     } \
153     Xrn = Xrn->l; \
154     } else if (Xrn->r) { \
155     Xrn = Xrn->r; \
156     } else if (Xsp != Xstack) { \
157     Xrn = *(--Xsp); \
158     } else { \
159     Xrn = (patricia_node_t *) 0; \
160     } \
161     } \
162     } while (0)
163    
164     #endif /* _PATRICIA_H */