trunk/include/patricia.h

/*
 * $Id$
 * Dave Plonka <plonka@doit.wisc.edu>
 *
 * 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.
 *
 * Copyright (c) 1999-2013
 *
 * The Regents of the University of Michigan ("The Regents") and Merit
 * Network, Inc.
 *
 * Redistributions of source code must retain the above copyright notice,
 * this list of conditions and the following disclaimer.
 *
 * Redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#ifndef _PATRICIA_H
#define _PATRICIA_H

/* { from defs.h */
#define prefix_touchar(prefix) ((unsigned char *)&(prefix)->add.sin)
#define BIT_TEST(f, b)  ((f) & (b))
/* } */

#include <netinet/in.h>  /* for struct in_addr */
#include <sys/socket.h>  /* for AF_INET */

/* { from mrt.h */
typedef struct _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;
    struct in6_addr sin6;
  } add;
} prefix_t;
/* } */

typedef struct _patricia_node_t
{
  unsigned 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 */
} patricia_node_t;

typedef struct _patricia_tree_t
{
  patricia_node_t *head;
  unsigned 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 *, prefix_t *);
extern patricia_node_t *patricia_search_best(patricia_tree_t *, prefix_t *);
extern patricia_node_t *patricia_search_best2(patricia_tree_t *, prefix_t *, int);
extern patricia_node_t *patricia_lookup(patricia_tree_t *, prefix_t *);
extern void patricia_remove(patricia_tree_t *, patricia_node_t *);
extern patricia_tree_t *patricia_new(unsigned int);
extern void patricia_clear(patricia_tree_t *, void (*)(void *));
extern void patricia_destroy(patricia_tree_t *, void (*)(void *));
extern void patricia_process(patricia_tree_t *, void (*)(prefix_t *, void *));
extern const char *patricia_prefix_toa(const prefix_t *, int);
extern void patricia_lookup_then_remove(patricia_tree_t *, const char *);
extern patricia_node_t *patricia_try_search_exact(patricia_tree_t *, const char *);
extern patricia_node_t *patricia_try_search_best(patricia_tree_t *, const char *);
extern patricia_node_t *patricia_try_search_exact_addr(patricia_tree_t *, struct sockaddr *, int);
extern patricia_node_t *patricia_try_search_best_addr(patricia_tree_t *, struct sockaddr *, int);

/* { from demo.c */
extern patricia_node_t *patricia_make_and_lookup(patricia_tree_t *, const char *);
extern patricia_node_t *patricia_make_and_lookup_addr(patricia_tree_t *, struct sockaddr *, int);
/* } */

#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
Revision:	8597
Committed:	Mon Oct 22 18:53:58 2018 UTC (5 years, 5 months ago) by michael
Content type:	text/x-chdr
File size:	5194 byte(s)
Log Message:	- patricia.c:ascii2prefix(): don't allow to overflow 'save'; change size of 'save' to INET6_ADDRSTRLEN
#	Content
1	/*
2	* $Id$
3	* Dave Plonka <plonka@doit.wisc.edu>
4	*
5	* This file had been called "radix.h" in the MRT sources.
6	*
7	* I renamed it to "patricia.h" since it's not an implementation of a general
8	* radix trie. Also, pulled in various requirements from "mrt.h" and added
9	* some other things it could be used as a standalone API.
10	*
11	* Copyright (c) 1999-2013
12	*
13	* The Regents of the University of Michigan ("The Regents") and Merit
14	* Network, Inc.
15	*
16	* Redistributions of source code must retain the above copyright notice,
17	* this list of conditions and the following disclaimer.
18	*
19	* Redistributions in binary form must reproduce the above copyright
20	* notice, this list of conditions and the following disclaimer in the
21	* documentation and/or other materials provided with the distribution.
22	*
23	* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
24	* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
25	* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
26	* A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
27	* HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
28	* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
29	* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
30	* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
31	* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
32	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
33	* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
34	*/
35
36	#ifndef _PATRICIA_H
37	#define _PATRICIA_H
38
39	/* { from defs.h */
40	#define prefix_touchar(prefix) ((unsigned char *)&(prefix)->add.sin)
41	#define BIT_TEST(f, b) ((f) & (b))
42	/* } */
43
44	#include <netinet/in.h> /* for struct in_addr */
45	#include <sys/socket.h> /* for AF_INET */
46
47	/* { from mrt.h */
48	typedef struct _prefix_t
49	{
50	unsigned short family; /* AF_INET \| AF_INET6 */
51	unsigned short bitlen; /* same as mask? */
52	int ref_count; /* reference count */
53
54	union
55	{
56	struct in_addr sin;
57	struct in6_addr sin6;
58	} add;
59	} prefix_t;
60	/* } */
61
62	typedef struct _patricia_node_t
63	{
64	unsigned int bit; /* flag if this node used */
65	prefix_t prefix; / who we are in patricia tree */
66	struct _patricia_node_t l, r; /* left and right children */
67	struct _patricia_node_t parent; / may be used */
68	void data; / pointer to data */
69	} patricia_node_t;
70
71	typedef struct _patricia_tree_t
72	{
73	patricia_node_t *head;
74	unsigned int maxbits; /* for IP, 32 bit addresses */
75	int num_active_node; /* for debug purpose */
76	} patricia_tree_t;
77
78
79	extern patricia_node_t patricia_search_exact(patricia_tree_t , prefix_t *);
80	extern patricia_node_t patricia_search_best(patricia_tree_t , prefix_t *);
81	extern patricia_node_t patricia_search_best2(patricia_tree_t , prefix_t *, int);
82	extern patricia_node_t patricia_lookup(patricia_tree_t , prefix_t *);
83	extern void patricia_remove(patricia_tree_t , patricia_node_t );
84	extern patricia_tree_t *patricia_new(unsigned int);
85	extern void patricia_clear(patricia_tree_t , void ()(void *));
86	extern void patricia_destroy(patricia_tree_t , void ()(void *));
87	extern void patricia_process(patricia_tree_t , void ()(prefix_t , void ));
88	extern const char patricia_prefix_toa(const prefix_t , int);
89	extern void patricia_lookup_then_remove(patricia_tree_t , const char );
90	extern patricia_node_t patricia_try_search_exact(patricia_tree_t , const char *);
91	extern patricia_node_t patricia_try_search_best(patricia_tree_t , const char *);
92	extern patricia_node_t patricia_try_search_exact_addr(patricia_tree_t , struct sockaddr *, int);
93	extern patricia_node_t patricia_try_search_best_addr(patricia_tree_t , struct sockaddr *, int);
94
95	/* { from demo.c */
96	extern patricia_node_t patricia_make_and_lookup(patricia_tree_t , const char *);
97	extern patricia_node_t patricia_make_and_lookup_addr(patricia_tree_t , struct sockaddr *, int);
98	/* } */
99
100	#define PATRICIA_MAXBITS (sizeof(struct in6_addr) * 8)
101	#define PATRICIA_NBIT(x) (0x80 >> ((x) & 0x7f))
102	#define PATRICIA_NBYTE(x) ((x) >> 3)
103
104	#define PATRICIA_DATA_GET(node, type) (type *)((node)->data)
105	#define PATRICIA_DATA_SET(node, value) ((node)->data = (void *)(value))
106
107	#define PATRICIA_WALK(Xhead, Xnode) \
108	do { \
109	patricia_node_t *Xstack[PATRICIA_MAXBITS + 1]; \
110	patricia_node_t **Xsp = Xstack; \
111	patricia_node_t *Xrn = (Xhead); \
112	while ((Xnode = Xrn)) { \
113	if (Xnode->prefix)
114
115	#define PATRICIA_WALK_ALL(Xhead, Xnode) \
116	do { \
117	patricia_node_t *Xstack[PATRICIA_MAXBITS + 1]; \
118	patricia_node_t **Xsp = Xstack; \
119	patricia_node_t *Xrn = (Xhead); \
120	while ((Xnode = Xrn)) { \
121	if (1)
122
123	#define PATRICIA_WALK_BREAK { \
124	if (Xsp != Xstack) { \
125	Xrn = *(--Xsp); \
126	} else { \
127	Xrn = (patricia_node_t *)0; \
128	} \
129	continue; }
130
131	#define PATRICIA_WALK_END \
132	if (Xrn->l) { \
133	if (Xrn->r) { \
134	*Xsp++ = Xrn->r; \
135	} \
136	Xrn = Xrn->l; \
137	} else if (Xrn->r) { \
138	Xrn = Xrn->r; \
139	} else if (Xsp != Xstack) { \
140	Xrn = *(--Xsp); \
141	} else { \
142	Xrn = (patricia_node_t *)0; \
143	} \
144	} \
145	} while (0)
146
147	#endif