[irc/rqf/shadowircd.git] / include / patricia.h

/*
 * $Id: patricia.h 6 2005-09-10 01:02:21Z nenolod $
 * 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 _PATRICIA_H
#define _PATRICIA_H
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include <assert.h>
#ifndef TESTING
#include "class.h"
#include "client.h"
#include "common.h"
#include "irc_string.h"
#include "ircd.h"
#include "numeric.h"
#include "send.h"
#include "memory.h"
#include "config.h"
#endif


#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; */
typedef void (*void_fn_t) ();
#define prefix_touchar(prefix) ((u_char *)&(prefix)->add.sin)
#define MAXLINE 1024
#define BIT_TEST(f, b)  ((f) & (b))

#include <netinet/in.h>
#include <sys/socket.h>

typedef struct _prefix_t
{
	u_short family;		/* AF_INET | AF_INET6 */
	u_short bitlen;		/* same as mask? */
	int ref_count;		/* reference count */
	union
	{
		struct in_addr sin;
#ifdef IPV6
		struct in6_addr sin6;
#endif				/* IPV6 */
	}
	add;
}
prefix_t;


typedef struct _patricia_node_t
{
	u_int bit;		/* flag if this node used */
	prefix_t *prefix;	/* who we are in patricia tree */
	struct _patricia_node_t *l, *r;	/* left and right children */
	struct _patricia_node_t *parent;	/* may be used */
	void *data;
}
patricia_node_t;

typedef struct _patricia_tree_t
{
	patricia_node_t *head;
	u_int maxbits;		/* for IP, 32 bit addresses */
	int num_active_node;	/* for debug purpose */
}
patricia_tree_t;


patricia_node_t *match_ip(patricia_tree_t * tree, struct sockaddr  *ip);
patricia_node_t *match_string(patricia_tree_t * tree, const char *string);
patricia_node_t *match_exact_string(patricia_tree_t * tree, const char *string);
patricia_node_t *patricia_search_exact(patricia_tree_t * patricia, prefix_t * prefix);
patricia_node_t *patricia_search_best(patricia_tree_t * patricia, prefix_t * prefix);
patricia_node_t *patricia_search_best2(patricia_tree_t * patricia,
				       prefix_t * prefix, int inclusive);
patricia_node_t *patricia_lookup(patricia_tree_t * patricia, prefix_t * prefix);

void patricia_remove(patricia_tree_t * patricia, patricia_node_t * node);
patricia_tree_t *New_Patricia(int maxbits);
void Clear_Patricia(patricia_tree_t * patricia, void_fn_t func);
void Destroy_Patricia(patricia_tree_t * patricia, void_fn_t func);
void patricia_process(patricia_tree_t * patricia, void_fn_t func);
void init_patricia(void);


#if 0
prefix_t *ascii2prefix(int family, char *string);
#endif
patricia_node_t *make_and_lookup(patricia_tree_t * tree, const char *string);
patricia_node_t *make_and_lookup_ip(patricia_tree_t * tree, struct sockaddr *, int bitlen);


#define PATRICIA_MAXBITS 128
#define PATRICIA_NBIT(x)        (0x80 >> ((x) & 0x7f))
#define PATRICIA_NBYTE(x)       ((x) >> 3)

#define PATRICIA_DATA_GET(node, type) (type *)((node)->data)
#define PATRICIA_DATA_SET(node, value) ((node)->data = (void *)(value))

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

#define PATRICIA_WALK_ALL(Xhead, Xnode) \
do { \
        patricia_node_t *Xstack[PATRICIA_MAXBITS+1]; \
        patricia_node_t **Xsp = Xstack; \
        patricia_node_t *Xrn = (Xhead); \
        while ((Xnode = Xrn)) { \
	    if (1)

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

#define 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 = (patricia_node_t *) 0; \
            } \
        } \
    } while (0)

#endif /* _PATRICIA_H */
Commit	Line	Data
212380e3	1	/*
	2	* $Id: patricia.h 6 2005-09-10 01:02:21Z nenolod $
	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 _PATRICIA_H
	16	#define _PATRICIA_H
	17	#include <stdlib.h>
	18	#include <string.h>
	19	#include <sys/types.h>
	20	#include <netinet/in.h>
	21	#include <arpa/inet.h>
	22	#include <assert.h>
	23	#ifndef TESTING
	24	#include "class.h"
	25	#include "client.h"
	26	#include "common.h"
	27	#include "irc_string.h"
	28	#include "ircd.h"
	29	#include "numeric.h"
	30	#include "send.h"
	31	#include "memory.h"
	32	#include "config.h"
	33	#endif
	34
	35
	36	#ifndef FALSE
	37	#define FALSE 0
	38	#endif
	39	#ifndef TRUE
	40	#define TRUE !(FALSE)
	41	#endif
	42	#ifndef INET6_ADDRSTRLEN
	43	#define INET6_ADDRSTRLEN 46
	44	#endif
	45
	46	/* typedef unsigned int u_int; */
	47	typedef void (*void_fn_t) ();
	48	#define prefix_touchar(prefix) ((u_char *)&(prefix)->add.sin)
	49	#define MAXLINE 1024
	50	#define BIT_TEST(f, b) ((f) & (b))
	51
	52	#include <netinet/in.h>
	53	#include <sys/socket.h>
	54
	55	typedef struct _prefix_t
	56	{
	57	u_short family; /* AF_INET \| AF_INET6 */
	58	u_short bitlen; /* same as mask? */
	59	int ref_count; /* reference count */
	60	union
	61	{
	62	struct in_addr sin;
	63	#ifdef IPV6
	64	struct in6_addr sin6;
65	#endif /* IPV6 */
66	}
67	add;
68	}
69	prefix_t;
70
71
72	typedef struct _patricia_node_t
73	{
74	u_int bit; /* flag if this node used */
75	prefix_t prefix; / who we are in patricia tree */
76	struct _patricia_node_t l, r; /* left and right children */
77	struct _patricia_node_t parent; / may be used */
78	void *data;
79	}
80	patricia_node_t;
81
82	typedef struct _patricia_tree_t
83	{
84	patricia_node_t *head;
85	u_int maxbits; /* for IP, 32 bit addresses */
86	int num_active_node; /* for debug purpose */
87	}
88	patricia_tree_t;
89
90
91	patricia_node_t match_ip(patricia_tree_t tree, struct sockaddr *ip);
92	patricia_node_t match_string(patricia_tree_t tree, const char *string);
93	patricia_node_t match_exact_string(patricia_tree_t tree, const char *string);
94	patricia_node_t patricia_search_exact(patricia_tree_t patricia, prefix_t * prefix);
95	patricia_node_t patricia_search_best(patricia_tree_t patricia, prefix_t * prefix);
96	patricia_node_t patricia_search_best2(patricia_tree_t patricia,
97	prefix_t * prefix, int inclusive);
98	patricia_node_t patricia_lookup(patricia_tree_t patricia, prefix_t * prefix);
99
100	void patricia_remove(patricia_tree_t * patricia, patricia_node_t * node);
101	patricia_tree_t *New_Patricia(int maxbits);
102	void Clear_Patricia(patricia_tree_t * patricia, void_fn_t func);
103	void Destroy_Patricia(patricia_tree_t * patricia, void_fn_t func);
104	void patricia_process(patricia_tree_t * patricia, void_fn_t func);
105	void init_patricia(void);
106
107
108	#if 0
109	prefix_t ascii2prefix(int family, char string);
110	#endif
111	patricia_node_t make_and_lookup(patricia_tree_t tree, const char *string);
112	patricia_node_t make_and_lookup_ip(patricia_tree_t tree, struct sockaddr *, int bitlen);
113
114
115	#define PATRICIA_MAXBITS 128
116	#define PATRICIA_NBIT(x) (0x80 >> ((x) & 0x7f))
117	#define PATRICIA_NBYTE(x) ((x) >> 3)
118
119	#define PATRICIA_DATA_GET(node, type) (type *)((node)->data)
120	#define PATRICIA_DATA_SET(node, value) ((node)->data = (void *)(value))
121
122	#define PATRICIA_WALK(Xhead, Xnode) \
123	do { \
124	patricia_node_t *Xstack[PATRICIA_MAXBITS+1]; \
125	patricia_node_t **Xsp = Xstack; \
126	patricia_node_t *Xrn = (Xhead); \
127	while ((Xnode = Xrn)) { \
128	if (Xnode->prefix)
129
130	#define PATRICIA_WALK_ALL(Xhead, Xnode) \
131	do { \
132	patricia_node_t *Xstack[PATRICIA_MAXBITS+1]; \
133	patricia_node_t **Xsp = Xstack; \
134	patricia_node_t *Xrn = (Xhead); \
135	while ((Xnode = Xrn)) { \
136	if (1)
137
138	#define PATRICIA_WALK_BREAK { \
139	if (Xsp != Xstack) { \
140	Xrn = *(--Xsp); \
141	} else { \
142	Xrn = (patricia_node_t *) 0; \
143	} \
144	continue; }
145
146	#define PATRICIA_WALK_END \
147	if (Xrn->l) { \
148	if (Xrn->r) { \
149	*Xsp++ = Xrn->r; \
150	} \
151	Xrn = Xrn->l; \
152	} else if (Xrn->r) { \
153	Xrn = Xrn->r; \
154	} else if (Xsp != Xstack) { \
155	Xrn = *(--Xsp); \
156	} else { \
157	Xrn = (patricia_node_t *) 0; \
158	} \
159	} \
160	} while (0)
161
162	#endif /* _PATRICIA_H */