diff options
Diffstat (limited to 'patricia.h')
| -rw-r--r-- | patricia.h | 218 |
1 files changed, 218 insertions, 0 deletions
diff --git a/patricia.h b/patricia.h new file mode 100644 index 0000000..7597248 --- /dev/null +++ b/patricia.h @@ -0,0 +1,218 @@ +/* + * This file is part of Pytricia. + * Joel Sommers <jsommers@colgate.edu> + * + * Pytricia is free software: you can redistribute it and/or modify + * it under the terms of the GNU Lesser General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * Pytricia is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public License + * along with Pytricia. If not, see <http://www.gnu.org/licenses/>. + */ + +/* + * $Id: patricia.h 6811 2009-07-06 20:41:10Z robin $ + * 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. + */ + +/* From copyright.txt: + * + * Copyright (c) 1997, 1998, 1999 + * + * + * The Regents of the University of Michigan ("The Regents") and Merit Network, + * Inc. All rights reserved. + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * 1. Redistributions of source code must retain the above + * copyright notice, this list of conditions and the + * following disclaimer. + * 2. 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. + * 3. All advertising materials mentioning features or use of + * this software must display the following acknowledgement: + * This product includes software developed by the University of Michigan, Merit + * Network, Inc., and their contributors. + * 4. Neither the name of the University, Merit Network, nor the + * names of their contributors may be used to endorse or + * promote products derived from this software without + * specific prior written permission. + * THIS SOFTWARE IS PROVIDED BY THE REGENTS 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 REGENTS 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 + +#include <sys/types.h> + +#define HAVE_IPV6 1 // JS: force use of ip6 + + +/* { 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 + +#if defined(_WIN32) || defined(_WIN64) +#include <winsock2.h> +#include <ws2tcpip.h> +#pragma comment(lib, "Ws2_32.lib") +#else +#include <netinet/in.h> +#include <sys/socket.h> +#endif + +/* { from mrt.h */ + +typedef struct _prefix4_t { + u_short family; + u_short bitlen; + int ref_count; + struct in_addr sin; +} prefix4_t; + +typedef struct _prefix6_t { + u_short family; + u_short bitlen; + int ref_count; + struct in6_addr sin6; +} prefix6_t; + +typedef struct _prefix_t { + u_short family; + u_short bitlen; + int ref_count; + union { + struct in_addr sin; +#ifdef HAVE_IPV6 + struct in6_addr sin6; +#endif /* IPV6 */ + } add; +} prefix_t; + +/* } */ + +/* typedef unsigned int u_int; */ +typedef void (*void_fn1_t)(void *); +typedef void (*void_fn2_t)(struct _prefix_t *, void *); + +typedef struct _patricia_node_t { + u_int bit; + prefix_t *prefix; + struct _patricia_node_t *l, *r; + struct _patricia_node_t *parent; + void *data; + void *user1; +} patricia_node_t; + +typedef struct _patricia_tree_t { + patricia_node_t *head; + u_int maxbits; + int num_active_node; +} patricia_tree_t; + + +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_fn1_t func); +void Destroy_Patricia (patricia_tree_t *patricia, void_fn1_t func); +void patricia_process (patricia_tree_t *patricia, void_fn2_t func); + +void Deref_Prefix (prefix_t * prefix); +prefix_t * New_Prefix(int, void *, int); + +/* { from demo.c */ + +prefix_t * +ascii2prefix (int family, char *string); + +char * +prefix_toa2x(prefix_t *prefix, char *buff, int with_len); + +patricia_node_t * +make_and_lookup (patricia_tree_t *tree, char *string); + +/* } */ + +#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 */ |