Adding upstream version 0.5.upstream/0.5upstream

Signed-off-by: Daniel Baumann <daniel@debian.org>

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 */