]>
jfr.im git - irc/quakenet/newserv.git/blob - patricia/patricia.h
2 * $Id: patricia.h,v 1.6 2005/12/07 20:53:01 dplonka Exp $
3 * Dave Plonka <plonka@doit.wisc.edu>
5 * This product includes software developed by the University of Michigan,
6 * Merit Network, Inc., and their contributors.
8 * This file had been called "radix.h" in the MRT sources.
10 * I renamed it to "patricia.h" since it's not an implementation of a general
11 * radix trie. Also, pulled in various requirements from "mrt.h" and added
12 * some other things it could be used as a standalone API.
18 #include "../lib/irc_ipv6.h"
20 typedef unsigned short u_short
;
21 typedef unsigned int u_int
;
22 typedef unsigned char u_char
;
24 /* typedef unsigned int u_int; */
25 typedef void (*void_fn_t
)();
27 #define prefix_touchar(prefix) ((u_char *)&(prefix)->sin)
31 #include <sys/types.h> /* for u_* definitions (on FreeBSD 5) */
33 #include <errno.h> /* for EAFNOSUPPORT */
35 # defined EAFNOSUPPORT WSAEAFNOSUPPORT
38 # include <netinet/in.h> /* for struct in_addr */
41 #include <sys/socket.h> /* for AF_INET */
45 #define PATRICIA_MAXSLOTS 7
48 typedef struct _prefix_t
{
49 u_short bitlen
; /* same as mask? */
50 int ref_count
; /* reference count */
51 struct irc_in_addr sin
;
55 struct _prefix_t prefix
;
61 typedef struct _patricia_node_t
{
62 unsigned char bit
; /* flag if this node used */
63 int usercount
; /* number of users on a given node */
64 prefix_t
*prefix
; /* who we are in patricia tree */
65 struct _patricia_node_t
*l
, *r
; /* left and right children */
66 struct _patricia_node_t
*parent
;/* may be used */
67 void *exts
[PATRICIA_MAXSLOTS
];
70 typedef struct _patricia_tree_t
{
71 patricia_node_t
*head
;
72 u_int maxbits
; /* for IPv6, 128 bit addresses */
73 int num_active_node
; /* for debug purpose */
76 extern patricia_tree_t
*iptree
;
78 prefix_t
*patricia_new_prefix (struct irc_in_addr
*dest
, int bitlen
);
79 prefix_t
* patricia_ref_prefix (prefix_t
* prefix
);
80 void patricia_deref_prefix (prefix_t
* prefix
);
82 patricia_node_t
*patricia_search_exact (patricia_tree_t
*patricia
, struct irc_in_addr
*sin
, unsigned char bitlen
);
83 patricia_node_t
*patricia_search_best (patricia_tree_t
*patricia
, struct irc_in_addr
*sin
, unsigned char bitlen
);
84 patricia_node_t
* patricia_search_best2 (patricia_tree_t
*patricia
, struct irc_in_addr
*sin
, unsigned char bitlen
,
86 patricia_node_t
*patricia_lookup (patricia_tree_t
*patricia
, prefix_t
*prefix
);
87 void patricia_remove (patricia_tree_t
*patricia
, patricia_node_t
*node
);
88 patricia_tree_t
*patricia_new_tree (int maxbits
);
89 void patricia_clear_tree (patricia_tree_t
*patricia
, void_fn_t func
);
90 void patricia_destroy_tree (patricia_tree_t
*patricia
, void_fn_t func
);
91 void patricia_process (patricia_tree_t
*patricia
, void_fn_t func
);
93 patricia_node_t
*patricia_new_node(patricia_tree_t
*patricia
, unsigned char bit
,prefix_t
*prefix
);
95 int registernodeext(const char *name
);
96 int findnodeext(const char *name
);
97 void releasenodeext(int index
);
99 void node_increment_usercount( patricia_node_t
*node
);
100 void node_decrement_usercount( patricia_node_t
*node
);
101 int is_normalized_ipmask( struct irc_in_addr
*sin
, unsigned char bitlen
);
104 void freeprefix (prefix_t
*prefix
);
105 prefix_t
*newprefix();
106 patricia_node_t
*newnode();
107 void freenode (patricia_node_t
*node
);
111 patricia_node_t
*refnode(patricia_tree_t
*tree
, struct irc_in_addr
*sin
, int bitlen
);
112 void derefnode(patricia_tree_t
*tree
, patricia_node_t
*node
);
114 #define get_byte_for_bit(base, nr) (base)[(nr) >> 3]
115 #define bigendian_bitfor(nr) (0x80 >> ((nr) & 0x07))
116 #define is_bit_set(base, nr) (get_byte_for_bit(base, nr) & bigendian_bitfor(nr))
118 #define PATRICIA_MAXBITS 128
120 #define PATRICIA_WALK(Xhead, Xnode) \
122 patricia_node_t *Xstack[PATRICIA_MAXBITS+1]; \
123 patricia_node_t **Xsp = Xstack; \
124 patricia_node_t *Xrn = (Xhead); \
125 while ((Xnode = Xrn)) { \
128 #define PATRICIA_WALK_ALL(Xhead, Xnode) \
130 patricia_node_t *Xstack[PATRICIA_MAXBITS+1]; \
131 patricia_node_t **Xsp = Xstack; \
132 patricia_node_t *Xrn = (Xhead); \
133 while ((Xnode = Xrn)) { \
136 #define PATRICIA_WALK_BREAK { \
137 if (Xsp != Xstack) { \
140 Xrn = (patricia_node_t *) 0; \
144 #define PATRICIA_WALK_END \
150 } else if (Xrn->r) { \
152 } else if (Xsp != Xstack) { \
155 Xrn = (patricia_node_t *) 0; \
160 #define PATRICIA_WALK_CLEAR(Xhead, Xnode) \
161 patricia_node_t *Xstack[PATRICIA_MAXBITS+1]; \
162 patricia_node_t **Xsp = Xstack; \
163 patricia_node_t *Xrn = (Xhead); \
164 while ((Xnode = Xrn)) { \
165 patricia_node_t *l = Xrn->l; \
166 patricia_node_t *r = Xrn->r; \
168 #define PATRICIA_WALK_CLEAR_END \
176 } else if (Xsp != Xstack) { \
179 Xrn = (patricia_node_t *) 0; \
183 #endif /* _PATRICIA_H */