]>
jfr.im git - irc/rqf/shadowircd.git/blob - libratbox/include/rb_patricia.h
2 * $Id: patricia.h 23020 2006-09-01 18:20:19Z androsyn $
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.
15 #ifndef _RB_PATRICIA_H
16 #define _RB_PATRICIA_H
24 #ifndef INET6_ADDRSTRLEN
25 #define INET6_ADDRSTRLEN 46
28 /* typedef unsigned int u_int; */
29 typedef void (*void_fn_t
) ();
30 #define rb_prefix_touchar(prefix) ((unsigned char *)&(prefix)->add.sin)
32 #define BIT_TEST(f, b) ((f) & (b))
34 typedef struct _rb_prefix_t
36 unsigned short family
; /* AF_INET | AF_INET6 */
37 unsigned short bitlen
; /* same as mask? */
38 int ref_count
; /* reference count */
51 typedef struct _rb_patricia_node_t
53 unsigned int bit
; /* flag if this node used */
54 rb_prefix_t
*prefix
; /* who we are in patricia tree */
55 struct _rb_patricia_node_t
*l
, *r
; /* left and right children */
56 struct _rb_patricia_node_t
*parent
; /* may be used */
61 typedef struct _rb_patricia_tree_t
63 rb_patricia_node_t
*head
;
64 unsigned int maxbits
; /* for IP, 32 bit addresses */
65 int num_active_node
; /* for debug purpose */
70 rb_patricia_node_t
*rb_match_ip(rb_patricia_tree_t
* tree
, struct sockaddr
*ip
);
71 rb_patricia_node_t
*rb_match_ip_exact(rb_patricia_tree_t
* tree
, struct sockaddr
*ip
, unsigned int len
);
72 rb_patricia_node_t
*rb_match_string(rb_patricia_tree_t
* tree
, const char *string
);
73 rb_patricia_node_t
*rb_match_exact_string(rb_patricia_tree_t
* tree
, const char *string
);
74 rb_patricia_node_t
*rb_patricia_search_exact(rb_patricia_tree_t
* patricia
, rb_prefix_t
* prefix
);
75 rb_patricia_node_t
*rb_patricia_search_best(rb_patricia_tree_t
* patricia
, rb_prefix_t
* prefix
);
76 rb_patricia_node_t
*rb_patricia_search_best2(rb_patricia_tree_t
* patricia
,
77 rb_prefix_t
* prefix
, int inclusive
);
78 rb_patricia_node_t
*rb_patricia_lookup(rb_patricia_tree_t
* patricia
, rb_prefix_t
* prefix
);
80 void rb_patricia_remove(rb_patricia_tree_t
* patricia
, rb_patricia_node_t
* node
);
81 rb_patricia_tree_t
*rb_new_patricia(int maxbits
);
82 void rb_clear_patricia(rb_patricia_tree_t
* patricia
, void_fn_t func
);
83 void rb_destroy_patricia(rb_patricia_tree_t
* patricia
, void_fn_t func
);
84 void rb_patricia_process(rb_patricia_tree_t
* patricia
, void_fn_t func
);
85 void rb_init_patricia(void);
89 rb_prefix_t
*ascii2prefix(int family
, char *string
);
91 rb_patricia_node_t
*make_and_lookup(rb_patricia_tree_t
* tree
, const char *string
);
92 rb_patricia_node_t
*make_and_lookup_ip(rb_patricia_tree_t
* tree
, struct sockaddr
*, int bitlen
);
95 #define RB_PATRICIA_MAXBITS 128
96 #define RB_PATRICIA_NBIT(x) (0x80 >> ((x) & 0x7f))
97 #define RB_PATRICIA_NBYTE(x) ((x) >> 3)
99 #define RB_PATRICIA_DATA_GET(node, type) (type *)((node)->data)
100 #define RB_PATRICIA_DATA_SET(node, value) ((node)->data = (void *)(value))
102 #define RB_PATRICIA_WALK(Xhead, Xnode) \
104 rb_patricia_node_t *Xstack[RB_PATRICIA_MAXBITS+1]; \
105 rb_patricia_node_t **Xsp = Xstack; \
106 rb_patricia_node_t *Xrn = (Xhead); \
107 while ((Xnode = Xrn)) { \
110 #define RB_PATRICIA_WALK_ALL(Xhead, Xnode) \
112 rb_patricia_node_t *Xstack[RB_PATRICIA_MAXBITS+1]; \
113 rb_patricia_node_t **Xsp = Xstack; \
114 rb_patricia_node_t *Xrn = (Xhead); \
115 while ((Xnode = Xrn)) { \
118 #define RB_PATRICIA_WALK_BREAK { \
119 if (Xsp != Xstack) { \
122 Xrn = (rb_patricia_node_t *) 0; \
126 #define RB_PATRICIA_WALK_END \
132 } else if (Xrn->r) { \
134 } else if (Xsp != Xstack) { \
137 Xrn = (rb_patricia_node_t *) 0; \
142 #endif /* _RB_PATRICIA_H */