trunk/src/patricia.h

/*
 * $Id: patricia.h,v 1.6 2005/12/07 20:53:01 dplonka Exp $
 * 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

/* typedef unsigned int u_int; */
typedef void (*void_fn_t)();
/* { from defs.h */
#define prefix_touchar(prefix) ((u_char *)&(prefix)->add.sin)
#define MAXLINE 1024
#define BIT_TEST(f, b)  ((f) & (b))
/* } */

#define addroute make_and_lookup

#include <sys/types.h> /* for u_* definitions (on FreeBSD 5) */

#include <errno.h> /* for EAFNOSUPPORT */
#ifndef EAFNOSUPPORT
#  defined EAFNOSUPPORT WSAEAFNOSUPPORT
#  include <winsock.h>
#else
#  include <netinet/in.h> /* for struct in_addr */
#endif

#include <sys/socket.h> /* for AF_INET */

/* { from mrt.h */

typedef struct _prefix4_t {
    u_short family;             /* AF_INET | AF_INET6 */
    u_short bitlen;             /* same as mask? */
    int ref_count;              /* reference count */
    struct in_addr sin;
} prefix4_t;

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;
                struct in6_addr sin6;
    } 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;                  /* pointer to data */
   void *user1;                 /* pointer to usr data (ex. route flap info) */
} 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;


extern patricia_node_t *patricia_search_exact (patricia_tree_t *patricia, prefix_t *prefix);
extern patricia_node_t *patricia_search_best (patricia_tree_t *patricia, prefix_t *prefix);
extern patricia_node_t * patricia_search_best2 (patricia_tree_t *patricia, prefix_t *prefix, 
                                   int inclusive);
extern patricia_node_t *patricia_lookup (patricia_tree_t *patricia, prefix_t *prefix);
extern void patricia_remove (patricia_tree_t *patricia, patricia_node_t *node);
extern patricia_tree_t *New_Patricia (int maxbits);
extern void Clear_Patricia (patricia_tree_t *patricia, void_fn_t func);
extern void Destroy_Patricia (patricia_tree_t *patricia, void_fn_t func);

extern void patricia_process (patricia_tree_t *patricia, void_fn_t func);

extern const char *prefix_toa (prefix_t * prefix);
extern void lookup_then_remove(patricia_tree_t *, char *);
extern patricia_node_t *try_search_exact(patricia_tree_t *, char *);
/* { from demo.c */

extern prefix_t *
ascii2prefix (int family, char *string);

extern patricia_node_t *
make_and_lookup (patricia_tree_t *tree, char *string);

/* } */

#define PATRICIA_MAXBITS        (sizeof(struct in6_addr) * 8)
#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 */
Revision:	5044
Committed:	Sat Dec 13 18:53:23 2014 UTC (10 years, 8 months ago) by michael
Content type:	text/x-chdr
Original Path:	*ircd-hybrid/trunk/include/patricia.h*
File size:	4605 byte(s)
Log Message:	- patricia.c, patricia.h: ipv6 is mandatory
#	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 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
18			/* typedef unsigned int u_int; */
19			typedef void (*void_fn_t)();
20			/* { from defs.h */
21			#define prefix_touchar(prefix) ((u_char *)&(prefix)->add.sin)
22			#define MAXLINE 1024
23			#define BIT_TEST(f, b) ((f) & (b))
24			/* } */
25
26			#define addroute make_and_lookup
27
28			#include <sys/types.h> /* for u_* definitions (on FreeBSD 5) */
29
30			#include <errno.h> /* for EAFNOSUPPORT */
31			#ifndef EAFNOSUPPORT
32			# defined EAFNOSUPPORT WSAEAFNOSUPPORT
33			# include <winsock.h>
34			#else
35			# include <netinet/in.h> /* for struct in_addr */
36			#endif
37
38			#include <sys/socket.h> /* for AF_INET */
39
40			/* { from mrt.h */
41
42			typedef struct _prefix4_t {
43			u_short family; /* AF_INET \| AF_INET6 */
44			u_short bitlen; /* same as mask? */
45			int ref_count; /* reference count */
46			struct in_addr sin;
47			} prefix4_t;
48
49			typedef struct _prefix_t {
50			u_short family; /* AF_INET \| AF_INET6 */
51			u_short bitlen; /* same as mask? */
52			int ref_count; /* reference count */
53			union {
54			struct in_addr sin;
55			struct in6_addr sin6;
56			} add;
57			} prefix_t;
58
59			/* } */
60
61			typedef struct _patricia_node_t {
62			u_int bit; /* flag if this node used */
63			prefix_t prefix; / who we are in patricia tree */
64			struct _patricia_node_t l, r; /* left and right children */
65			struct _patricia_node_t parent;/ may be used */
66			void data; / pointer to data */
67			void user1; / pointer to usr data (ex. route flap info) */
68			} patricia_node_t;
69
70			typedef struct _patricia_tree_t {
71			patricia_node_t *head;
72			u_int maxbits; /* for IP, 32 bit addresses */
73			int num_active_node; /* for debug purpose */
74			} patricia_tree_t;
75
76
77	michael	5043	extern patricia_node_t patricia_search_exact (patricia_tree_t patricia, prefix_t *prefix);
78			extern patricia_node_t patricia_search_best (patricia_tree_t patricia, prefix_t *prefix);
79			extern patricia_node_t * patricia_search_best2 (patricia_tree_t patricia, prefix_t prefix,
80	michael	5042	int inclusive);
81	michael	5043	extern patricia_node_t patricia_lookup (patricia_tree_t patricia, prefix_t *prefix);
82			extern void patricia_remove (patricia_tree_t patricia, patricia_node_t node);
83			extern patricia_tree_t *New_Patricia (int maxbits);
84			extern void Clear_Patricia (patricia_tree_t *patricia, void_fn_t func);
85			extern void Destroy_Patricia (patricia_tree_t *patricia, void_fn_t func);
86	michael	5042
87	michael	5043	extern void patricia_process (patricia_tree_t *patricia, void_fn_t func);
88	michael	5042
89	michael	5043	extern const char prefix_toa (prefix_t prefix);
90			extern void lookup_then_remove(patricia_tree_t , char );
91			extern patricia_node_t try_search_exact(patricia_tree_t , char *);
92	michael	5042	/* { from demo.c */
93
94	michael	5043	extern prefix_t *
95	michael	5042	ascii2prefix (int family, char *string);
96
97	michael	5043	extern patricia_node_t *
98	michael	5042	make_and_lookup (patricia_tree_t tree, char string);
99
100			/* } */
101
102			#define PATRICIA_MAXBITS (sizeof(struct in6_addr) * 8)
103			#define PATRICIA_NBIT(x) (0x80 >> ((x) & 0x7f))
104			#define PATRICIA_NBYTE(x) ((x) >> 3)
105
106			#define PATRICIA_DATA_GET(node, type) (type *)((node)->data)
107			#define PATRICIA_DATA_SET(node, value) ((node)->data = (void *)(value))
108
109			#define PATRICIA_WALK(Xhead, Xnode) \
110			do { \
111			patricia_node_t *Xstack[PATRICIA_MAXBITS+1]; \
112			patricia_node_t **Xsp = Xstack; \
113			patricia_node_t *Xrn = (Xhead); \
114			while ((Xnode = Xrn)) { \
115			if (Xnode->prefix)
116
117			#define PATRICIA_WALK_ALL(Xhead, Xnode) \
118			do { \
119			patricia_node_t *Xstack[PATRICIA_MAXBITS+1]; \
120			patricia_node_t **Xsp = Xstack; \
121			patricia_node_t *Xrn = (Xhead); \
122			while ((Xnode = Xrn)) { \
123			if (1)
124
125			#define PATRICIA_WALK_BREAK { \
126			if (Xsp != Xstack) { \
127			Xrn = *(--Xsp); \
128			} else { \
129			Xrn = (patricia_node_t *) 0; \
130			} \
131			continue; }
132
133			#define PATRICIA_WALK_END \
134			if (Xrn->l) { \
135			if (Xrn->r) { \
136			*Xsp++ = Xrn->r; \
137			} \
138			Xrn = Xrn->l; \
139			} else if (Xrn->r) { \
140			Xrn = Xrn->r; \
141			} else if (Xsp != Xstack) { \
142			Xrn = *(--Xsp); \
143			} else { \
144			Xrn = (patricia_node_t *) 0; \
145			} \
146			} \
147			} while (0)
148
149			#endif /* _PATRICIA_H */