[irc/rqf/shadowircd.git] / libratbox / include / rb_patricia.h

/*
 * $Id: patricia.h 23020 2006-09-01 18:20:19Z androsyn $
 * Dave Plonka <plonka@doit.wisc.edu>
 *
 * This product includes software developed by the University of Michigan,
 * Merit Network, Inc., and their contributors. 
 *
 * This file had been called "radix.h" in the MRT sources.
 *
 * I renamed it to "patricia.h" since it's not an implementation of a general
 * radix trie.  Also, pulled in various requirements from "mrt.h" and added
 * some other things it could be used as a standalone API.
 */

#ifndef _RB_PATRICIA_H
#define _RB_PATRICIA_H

#ifndef FALSE
#define FALSE 0
#endif
#ifndef TRUE
#define TRUE !(FALSE)
#endif
#ifndef INET6_ADDRSTRLEN
#define INET6_ADDRSTRLEN 46
#endif

/* typedef unsigned int u_int; */
#define rb_prefix_touchar(prefix) ((unsigned char *)&(prefix)->add.sin)
#define MAXLINE 1024
#define BIT_TEST(f, b)  ((f) & (b))

typedef struct _rb_prefix_t
{
	unsigned short family;	/* AF_INET | AF_INET6 */
	unsigned short bitlen;	/* same as mask? */
	int ref_count;		/* reference count */
	union
	{
		struct in_addr sin;
#ifdef RB_IPV6
		struct in6_addr sin6;
#endif				/* RB_IPV6 */
	}
	add;
}
rb_prefix_t;


typedef struct _rb_patricia_node_t
{
	unsigned int bit;	/* flag if this node used */
	rb_prefix_t *prefix;	/* who we are in patricia tree */
	struct _rb_patricia_node_t *l, *r;	/* left and right children */
	struct _rb_patricia_node_t *parent;	/* may be used */
	void *data;
}
rb_patricia_node_t;

typedef struct _rb_patricia_tree_t
{
	rb_patricia_node_t *head;
	unsigned int maxbits;	/* for IP, 32 bit addresses */
	int num_active_node;	/* for debug purpose */
}
rb_patricia_tree_t;


rb_patricia_node_t *rb_match_ip(rb_patricia_tree_t *tree, struct sockaddr *ip);
rb_patricia_node_t *rb_match_ip_exact(rb_patricia_tree_t *tree, struct sockaddr *ip,
				      unsigned int len);
rb_patricia_node_t *rb_match_string(rb_patricia_tree_t *tree, const char *string);
rb_patricia_node_t *rb_match_exact_string(rb_patricia_tree_t *tree, const char *string);
rb_patricia_node_t *rb_patricia_search_exact(rb_patricia_tree_t *patricia, rb_prefix_t *prefix);
rb_patricia_node_t *rb_patricia_search_best(rb_patricia_tree_t *patricia, rb_prefix_t *prefix);
rb_patricia_node_t *rb_patricia_search_best2(rb_patricia_tree_t *patricia,
					     rb_prefix_t *prefix, int inclusive);
rb_patricia_node_t *rb_patricia_lookup(rb_patricia_tree_t *patricia, rb_prefix_t *prefix);

void rb_patricia_remove(rb_patricia_tree_t *patricia, rb_patricia_node_t *node);
rb_patricia_tree_t *rb_new_patricia(int maxbits);
void rb_clear_patricia(rb_patricia_tree_t *patricia, void (*func) (void *));
void rb_destroy_patricia(rb_patricia_tree_t *patricia, void (*func) (void *));
void rb_patricia_process(rb_patricia_tree_t *patricia, void (*func) (rb_prefix_t *, void *));
void rb_init_patricia(void);


#if 0
rb_prefix_t *ascii2prefix(int family, char *string);
#endif
rb_patricia_node_t *make_and_lookup(rb_patricia_tree_t *tree, const char *string);
rb_patricia_node_t *make_and_lookup_ip(rb_patricia_tree_t *tree, struct sockaddr *, int bitlen);


#define RB_PATRICIA_MAXBITS 128
#define RB_PATRICIA_NBIT(x)        (0x80 >> ((x) & 0x7f))
#define RB_PATRICIA_NBYTE(x)       ((x) >> 3)

#define RB_PATRICIA_DATA_GET(node, type) (type *)((node)->data)
#define RB_PATRICIA_DATA_SET(node, value) ((node)->data = (void *)(value))

#define RB_PATRICIA_WALK(Xhead, Xnode) \
    do { \
	rb_patricia_node_t *Xstack[RB_PATRICIA_MAXBITS+1]; \
	rb_patricia_node_t **Xsp = Xstack; \
	rb_patricia_node_t *Xrn = (Xhead); \
	while ((Xnode = Xrn)) { \
	    if (Xnode->prefix)

#define RB_PATRICIA_WALK_ALL(Xhead, Xnode) \
do { \
	rb_patricia_node_t *Xstack[RB_PATRICIA_MAXBITS+1]; \
	rb_patricia_node_t **Xsp = Xstack; \
	rb_patricia_node_t *Xrn = (Xhead); \
	while ((Xnode = Xrn)) { \
	    if (1)

#define RB_PATRICIA_WALK_BREAK { \
	    if (Xsp != Xstack) { \
		Xrn = *(--Xsp); \
	     } else { \
		Xrn = (rb_patricia_node_t *) 0; \
	    } \
	    continue; }

#define RB_PATRICIA_WALK_END \
	    if (Xrn->l) { \
		if (Xrn->r) { \
		    *Xsp++ = Xrn->r; \
		} \
		Xrn = Xrn->l; \
	    } else if (Xrn->r) { \
		Xrn = Xrn->r; \
	    } else if (Xsp != Xstack) { \
		Xrn = *(--Xsp); \
	    } else { \
		Xrn = (rb_patricia_node_t *) 0; \
	    } \
	} \
    } while (0)

#endif /* _RB_PATRICIA_H */
Commit	Line	Data
b57f37fb WP	1	/*
	2	* $Id: patricia.h 23020 2006-09-01 18:20:19Z androsyn $
	3	* Dave Plonka <plonka@doit.wisc.edu>
	4	*
	5	* This product includes software developed by the University of Michigan,
	6	* Merit Network, Inc., and their contributors.
	7	*
	8	* This file had been called "radix.h" in the MRT sources.
	9	*
	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.
	13	*/
	14
	15	#ifndef _RB_PATRICIA_H
	16	#define _RB_PATRICIA_H
	17
	18	#ifndef FALSE
	19	#define FALSE 0
	20	#endif
	21	#ifndef TRUE
	22	#define TRUE !(FALSE)
	23	#endif
	24	#ifndef INET6_ADDRSTRLEN
	25	#define INET6_ADDRSTRLEN 46
	26	#endif
	27
	28	/* typedef unsigned int u_int; */
b57f37fb WP	29	#define rb_prefix_touchar(prefix) ((unsigned char *)&(prefix)->add.sin)
	30	#define MAXLINE 1024
	31	#define BIT_TEST(f, b) ((f) & (b))
	32
	33	typedef struct _rb_prefix_t
	34	{
94b4fbf9 VY	35	unsigned short family; /* AF_INET \| AF_INET6 */
94b4fbf9 VY	36	unsigned short bitlen; /* same as mask? */
b57f37fb WP	37	int ref_count; /* reference count */
	38	union
	39	{
	40	struct in_addr sin;
	41	#ifdef RB_IPV6
	42	struct in6_addr sin6;
	43	#endif /* RB_IPV6 */
	44	}
	45	add;
	46	}
	47	rb_prefix_t;
	48
	49
	50	typedef struct _rb_patricia_node_t
	51	{
94b4fbf9	52	unsigned int bit; /* flag if this node used */
b57f37fb WP	53	rb_prefix_t prefix; / who we are in patricia tree */
	54	struct _rb_patricia_node_t l, r; /* left and right children */
	55	struct _rb_patricia_node_t parent; / may be used */
	56	void *data;
	57	}
	58	rb_patricia_node_t;
	59
	60	typedef struct _rb_patricia_tree_t
	61	{
	62	rb_patricia_node_t *head;
94b4fbf9	63	unsigned int maxbits; /* for IP, 32 bit addresses */
b57f37fb WP	64	int num_active_node; /* for debug purpose */
	65	}
	66	rb_patricia_tree_t;
	67
	68
94b4fbf9 VY	69	rb_patricia_node_t rb_match_ip(rb_patricia_tree_t tree, struct sockaddr *ip);
	70	rb_patricia_node_t rb_match_ip_exact(rb_patricia_tree_t tree, struct sockaddr *ip,
	71	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);
b57f37fb	79
94b4fbf9	80	void rb_patricia_remove(rb_patricia_tree_t patricia, rb_patricia_node_t node);
b57f37fb	81	rb_patricia_tree_t *rb_new_patricia(int maxbits);
94b4fbf9 VY	82	void rb_clear_patricia(rb_patricia_tree_t patricia, void (func) (void *));
	83	void rb_destroy_patricia(rb_patricia_tree_t patricia, void (func) (void *));
	84	void rb_patricia_process(rb_patricia_tree_t patricia, void (func) (rb_prefix_t , void ));
b57f37fb WP	85	void rb_init_patricia(void);
	86
	87
	88	#if 0
	89	rb_prefix_t ascii2prefix(int family, char string);
	90	#endif
94b4fbf9 VY	91	rb_patricia_node_t make_and_lookup(rb_patricia_tree_t tree, const char *string);
94b4fbf9 VY	92	rb_patricia_node_t make_and_lookup_ip(rb_patricia_tree_t tree, struct sockaddr *, int bitlen);
b57f37fb WP	93
	94
	95	#define RB_PATRICIA_MAXBITS 128
	96	#define RB_PATRICIA_NBIT(x) (0x80 >> ((x) & 0x7f))
	97	#define RB_PATRICIA_NBYTE(x) ((x) >> 3)
	98
	99	#define RB_PATRICIA_DATA_GET(node, type) (type *)((node)->data)
	100	#define RB_PATRICIA_DATA_SET(node, value) ((node)->data = (void *)(value))
	101
	102	#define RB_PATRICIA_WALK(Xhead, Xnode) \
	103	do { \
	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)) { \
	108	if (Xnode->prefix)
	109
	110	#define RB_PATRICIA_WALK_ALL(Xhead, Xnode) \
	111	do { \
	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)) { \
	116	if (1)
	117
	118	#define RB_PATRICIA_WALK_BREAK { \
	119	if (Xsp != Xstack) { \
	120	Xrn = *(--Xsp); \
	121	} else { \
	122	Xrn = (rb_patricia_node_t *) 0; \
	123	} \
	124	continue; }
	125
	126	#define RB_PATRICIA_WALK_END \
	127	if (Xrn->l) { \
	128	if (Xrn->r) { \
	129	*Xsp++ = Xrn->r; \
	130	} \
	131	Xrn = Xrn->l; \
	132	} else if (Xrn->r) { \
	133	Xrn = Xrn->r; \
	134	} else if (Xsp != Xstack) { \
	135	Xrn = *(--Xsp); \
	136	} else { \
	137	Xrn = (rb_patricia_node_t *) 0; \
	138	} \
	139	} \
	140	} while (0)
	141
	142	#endif /* _RB_PATRICIA_H */