initial

10 files changed, 1782 insertions, 0 deletions

diff --git a/Changes b/Changes
new file mode 100644
index 0000000..8646f57
--- /dev/null
+++ b/Changes
@@ -0,0 +1,16 @@
+0.04 2008/2/19
+ - fixed the bug of "clear" method (destroy)
+   node data were not cleared correctly
+
+ - fixed the memory leak in search methods
+   I had to clear the prefix instances
+
+0.03 2008/2/17
+ - fixed the bug of allocating user_data strings
+
+0.02 2008/1/31
+ - fixed the bug of printing prefix for 64-bit architecture 
+   from Aki Nakao
+
+0.01 2007/11/16
+ - the first version
diff --git a/README b/README
new file mode 100644
index 0000000..23ce6c1
--- /dev/null
+++ b/README
@@ -0,0 +1,179 @@
+README for Ruby wrapper of Net::Patricia
+---------------------------------------
+
+rPatricia - A ruby wrapper of Net::Patricia
+
+DESCRIPTION
+-----------
+
+  This is a ruby wrapper of Net::Patricia, which has been developed by 
+  Dave Plonka. The original Net::Patricia and its C API are available
+  from:
+  http://net.doit.wisc.edu/~plonka/Net-Patricia/
+
+  Net::Patricia is a module for fast IP address/prefix lookups.
+  I have modified some interfaces for the Ruby wrapper version. 
+
+NO WARANTY
+----------    
+    THE PROGRAM IS DISTRIBUTED IN THE HOPE THAT IT WILL BE USEFUL, BUT
+    WITHOUT ANY WARRANTY. IT IS PROVIDED "AS IS" WITHOUT WARRANTY OF
+    ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED
+    TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
+    PARTICULAR PURPOSE. THE ENTIRE RISK AS TO THE QUALITY AND
+    PERFORMANCE OF THE PROGRAM IS WITH YOU. SHOULD THE PROGRAM PROVE
+    DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING, REPAIR
+    OR CORRECTION. 
+
+INSTALLATION
+------------
+
+   This package extracts, builds, installs in the usual fashion, i.e.:
+
+      $ tar xvfz rpatricia.tar.gz
+      $ cd rpatricia
+      $ ruby extconf.rb
+      $ make
+      $ ruby test.rb
+      # make install
+
+SYNOPSIS
+--------
+
+  require 'rpatricia'
+  pt = Patricia.new
+  pt.add("192.168.1.0/24")
+  pt.add("127.0.0.0/8", "user_data")
+  node = pt.search_best("127.0.0.1")
+  puts node.data
+  puts node.prefix
+  puts node.network
+  puts node.prefixlen
+  pt.remove("127.0.0.0/8")
+  puts pt.num_nodes
+  pt.show_nodes
+  pt.clear
+
+METHODS
+-------
+new:
+
+      pt = Patricia.new
+
+    This is the class' constructor - it returns a Patricia object upon
+    success or nil on failure. For now, the constructor takes no
+    arguments, and defaults to creating a tree which uses AF_INET IPv4
+    address and mask values as keys. 
+
+    The Patricia object will be destroyed automatically when there are
+    no longer any references to it.
+
+add:
+      pt.add(key_string[,user_data])
+
+    The first argument, key_string, is a network or subnet
+    specification in canonical form, e.g. ``10.0.0.0/8'', where the
+    number after the slash represents the number of bits in the
+    netmask. If no mask width is specified, the longest possible mask
+    is assumed, i.e. 32 bits for AF_INET addresses.
+
+    The second argument, user_data, is optional. If supplied, it
+    should be a STRING object specifying the user data that will be 
+    stored in the Patricia Trie node. Subsequently, this value will
+    be returned by the match methods described below to indicate a 
+    successful search. 
+
+    If no second argument is passed, the key_string will be stored as
+    the user data and therfore will likewise be returned by the match
+    functions.
+
+    On success, this method returns the object of the Patricia Trie 
+    node.
+
+add_node:    An alias of add.
+
+search_best:
+
+      pt.search_best(key_string);
+
+    This method searches the Patricia Trie to find a matching node,
+    according to normal subnetting rules for the address and mask
+    specified.
+
+    The key_string argument is a network or subnet specification in
+    canonical form, e.g. ``10.0.0.0/8'', where the number after the
+    slash represents the number of bits in the netmask. If no mask
+    width value is specified, the longest mask is assumed, i.e. 32
+    bits for AF_INET addresses.
+
+    If a matching node is found in the Patricia Trie, this method
+    returns the object of the node. This method returns nil on
+    failure.
+
+match_best:    An alias of search_best.
+
+search_exact:
+
+      pt.search_exact(key_string);
+
+    This method searches the Patricia Trie to find a matching
+    node. Its semantics are exactly the same as those described for
+    search_best except that the key must match a node exactly. I.e.,
+    it is not sufficient that the address and mask specified merely
+    falls within the subnet specified by a particular node.
+
+match_exact:        An alias of search_exact.
+
+remove:
+
+      pt.remove(key_string);
+
+    This method removes the node which exactly matches the the address
+    and mask specified from the Patricia Trie.
+
+    If the matching node is found in the Patricia Trie, it is removed,
+    and this method returns the true. This method returns nil on
+    failure. 
+
+remove_node:         An alias of remove
+
+num_nodes:
+       
+       pt.num_nodes
+
+     This method returns the number of nodes in the Patricia Trie.
+
+show_nodes:
+
+       pt.print_nodes
+
+     This method prints all the nodes in the Patricia Trie.
+
+data:
+
+       node.data
+   
+     This method returns the user data of the Patricia Trie node.
+
+network:
+
+       node.network
+   
+     This method returns the network of the Patricia Trie node.
+
+prefix:
+
+       node.prefix
+   
+     This method returns the prefix of the Patricia Trie node.
+
+prefixlen:
+
+       node.prefixlen
+   
+     This method returns the prefix length of the Patricia Trie 
+     node.
+
+AUTHOR
+------
+Tatsuya Mori <mori.tatsuya@gmail.com>
diff --git a/TODO b/TODO
new file mode 100644
index 0000000..65329b6
--- /dev/null
+++ b/TODO
@@ -0,0 +1,2 @@
+1. figure out bugs
+2. extension for AF_INET6
diff --git a/copyright b/copyright
new file mode 100644
index 0000000..53677ed
--- /dev/null
+++ b/copyright
@@ -0,0 +1,34 @@
+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.  
+
+
diff --git a/credits.txt b/credits.txt
new file mode 100644
index 0000000..cef1252
--- /dev/null
+++ b/credits.txt
@@ -0,0 +1,73 @@
+
+   [newtool.gif]
+   
+MRT Credits
+
+    The Multi-Threaded Routing Toolkit
+     _________________________________________________________________
+   
+   MRT was developed by [1]Merit Network, Inc., under National Science
+   Foundation grant NCR-9318902, "Experimentation with Routing Technology
+   to be Used for Inter-Domain Routing in the Internet."
+   
+    Current MRT Staff
+    
+     * [2]Craig Labovitz <labovit@merit.edu>
+     * [3]Makaki Hirabaru <masaki@merit.edu>
+     * [4]Farnam Jahanian <farnam@eecs.umich.edu>
+     * Susan Hares <skh@merit.edu>
+     * Susan R. Harris <srh@merit.edu>
+     * Nathan Binkert <binkertn@eecs.umich.edu>
+     * Gerald Winters <gerald@merit.edu>
+       
+    Project Alumni
+    
+     * [5]Marc Unangst <mju@merit.edu>
+     * John Scudder <jgs@ieng.com>
+       
+   The BGP4+ extension was originally written by Francis Dupont
+   <Francis.Dupont@inria.fr>.
+   
+   The public domain Struct C-library of linked list, hash table and
+   memory allocation routines was developed by Jonathan Dekock
+   <dekock@cadence.com>.
+   
+   Susan Rebecca Harris <srh@merit.edu> provided help with the
+   documentation.
+   David Ward <dward@netstar.com> provided bug fixes and helpful
+   suggestions.
+   Some sections of code and architecture ideas were taken from the GateD
+   routing daemon.
+   
+   The first port to Linux with IPv6 was done by Pedro Roque
+   <roque@di.fc.ul.pt>. Some interface routines to the Linux kernel were
+   originally written by him.
+   
+   Alexey Kuznetsov made enhancements to 1.4.3a and fixed the Linux
+   kernel intarface. Linux's netlink interface was written, referring to
+   his code "iproute2".
+   
+   We would also like to thank our other colleagues in Japan, Portugal,
+   the Netherlands, the UK, and the US for their many contributions to
+   the MRT development effort.
+     _________________________________________________________________
+   
+   Cisco is a registered trademark of Cisco Systems Inc.
+     _________________________________________________________________
+                                                                         
+        Merit Network 4251 Plymouth Road Suite C Ann Arbor, MI 48105-2785
+                                                             734-764-9430
+                                                           info@merit.edu
+     _________________________________________________________________
+                                                                         
+                                               © 1999 Merit Network, Inc.
+                                                         [6]www@merit.edu
+
+References
+
+   1. http://www.merit.edu/
+   2. http://www.merit.edu/~labovit
+   3. http://www.merit.edu/~masaki
+   4. http://www.eecs.umich.edu/~farnam
+   5. http://www.contrib.andrew.cmu.edu/~mju/
+   6. mailto:www@merit.edu
diff --git a/extconf.rb b/extconf.rb
new file mode 100755
index 0000000..ac42e36
--- /dev/null
+++ b/extconf.rb
@@ -0,0 +1,5 @@
+#!/usr/bin/env ruby 
+require "mkmf"
+
+create_makefile("rpatricia")
+
diff --git a/patricia.c b/patricia.c
new file mode 100644
index 0000000..d211a34
--- /dev/null
+++ b/patricia.c
@@ -0,0 +1,1038 @@
+/*
+ * $Id: patricia.c,v 1.7 2005/12/07 20:46:41 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.c" in the MRT sources.
+ *
+ * I renamed it to "patricia.c" since it's not an implementation of a general
+ * radix trie.  Also I pulled in various requirements from "prefix.c" and
+ * "demo.c" so that it could be used as a standalone API.
+ */
+
+static char copyright[] =
+"This product includes software developed by the University of Michigan, Merit"
+"Network, Inc., and their contributors.";
+
+#include <assert.h> /* assert */
+#include <ctype.h> /* isdigit */
+#include <errno.h> /* errno */
+#include <math.h> /* sin */
+#include <stddef.h> /* NULL */
+#include <stdio.h> /* sprintf, fprintf, stderr */
+#include <stdlib.h> /* free, atol, calloc */
+#include <string.h> /* memcpy, strchr, strlen */
+#include <sys/types.h> /* BSD: for inet_addr */
+#include <sys/socket.h> /* BSD, Linux: for inet_addr */
+#include <netinet/in.h> /* BSD, Linux: for inet_addr */
+#include <arpa/inet.h> /* BSD, Linux, Solaris: for inet_addr */
+
+#include "patricia.h"
+
+#define Delete free
+
+/* { from prefix.c */
+
+/* prefix_tochar
+ * convert prefix information to bytes
+ */
+u_char *
+prefix_tochar (prefix_t * prefix)
+{
+    if (prefix == NULL)
+        return (NULL);
+
+    return ((u_char *) & prefix->add.sin);
+}
+
+int 
+comp_with_mask (void *addr, void *dest, u_int mask)
+{
+
+    if ( /* mask/8 == 0 || */ memcmp (addr, dest, mask / 8) == 0) {
+        int n = mask / 8;
+        int m = ((-1) << (8 - (mask % 8)));
+
+        if (mask % 8 == 0 || (((u_char *)addr)[n] & m) == (((u_char *)dest)[n] & m))
+            return (1);
+    }
+    return (0);
+}
+
+/* inet_pton substitute implementation
+ * Uses inet_addr to convert an IP address in dotted decimal notation into 
+ * unsigned long and copies the result to dst.
+ * Only supports AF_INET.  Follows standard error return conventions of 
+ * inet_pton.
+ */
+int
+inet_pton (int af, const char *src, void *dst)
+{
+    u_long result;  
+
+    if (af == AF_INET) {
+        result = inet_addr(src);
+        if (result == -1)
+            return 0;
+        else {
+                        memcpy (dst, &result, 4);
+            return 1;
+                }
+        }
+#ifdef NT
+#ifdef HAVE_IPV6
+        else if (af == AF_INET6) {
+                struct in6_addr Address;
+                return (inet6_addr(src, &Address));
+        }
+#endif /* HAVE_IPV6 */
+#endif /* NT */
+#ifndef NT
+    else {
+
+        errno = EAFNOSUPPORT;
+        return -1;
+    }
+#endif /* NT */
+}
+
+/* this allows imcomplete prefix */
+int
+my_inet_pton (int af, const char *src, void *dst)
+{
+    if (af == AF_INET) {
+        int i, c, val;
+        u_char xp[4] = {0, 0, 0, 0};
+
+        for (i = 0; ; i++) {
+            c = *src++;
+            if (!isdigit (c))
+                return (-1);
+            val = 0;
+            do {
+                val = val * 10 + c - '0';
+                if (val > 255)
+                    return (0);
+                c = *src++;
+            } while (c && isdigit (c));
+            xp[i] = val;
+            if (c == '\0')
+                break;
+            if (c != '.')
+                return (0);
+            if (i >= 3)
+                return (0);
+        }
+        memcpy (dst, xp, 4);
+        return (1);
+#ifdef HAVE_IPV6
+    } else if (af == AF_INET6) {
+        return (inet_pton (af, src, dst));
+#endif /* HAVE_IPV6 */
+    } else {
+#ifndef NT
+        errno = EAFNOSUPPORT;
+#endif /* NT */
+        return -1;
+    }
+}
+
+/* 
+ * convert prefix information to ascii string with length
+ * thread safe and (almost) re-entrant implementation
+ */
+char *
+prefix_toa2x (prefix_t *prefix, char *buff, int with_len)
+{
+    if (prefix == NULL)
+        return ("(Null)");
+    assert (prefix->ref_count >= 0);
+    if (buff == NULL) {
+
+        struct buffer {
+            char buffs[16][48+5];
+            u_int i;
+        } *buffp;
+
+#    if 0
+        THREAD_SPECIFIC_DATA (struct buffer, buffp, 1);
+#    else
+        { /* for scope only */
+           static struct buffer local_buff;
+           buffp = &local_buff;
+        }
+#    endif
+        if (buffp == NULL) {
+            /* XXX should we report an error? */
+            return (NULL);
+        }
+
+        buff = buffp->buffs[buffp->i++%16];
+    }
+    if (prefix->family == AF_INET) {
+        u_char *a;
+        assert (prefix->bitlen <= 32);
+        a = prefix_touchar (prefix);
+        if (with_len) {
+            sprintf (buff, "%d.%d.%d.%d/%d", a[0], a[1], a[2], a[3],
+                     prefix->bitlen);
+        }
+        else {
+            sprintf (buff, "%d.%d.%d.%d", a[0], a[1], a[2], a[3]);
+        }
+        return (buff);
+    }
+#ifdef HAVE_IPV6
+    else if (prefix->family == AF_INET6) {
+        char *r;
+        r = (char *) inet_ntop (AF_INET6, &prefix->add.sin6, buff, 48 /* a guess value */ );
+        if (r && with_len) {
+            assert (prefix->bitlen <= 128);
+            sprintf (buff + strlen (buff), "/%d", prefix->bitlen);
+        }
+        return (buff);
+    }
+#endif /* HAVE_IPV6 */
+    else
+        return (NULL);
+}
+
+/* prefix_toa2
+ * convert prefix information to ascii string
+ */
+char *
+prefix_toa2 (prefix_t *prefix, char *buff)
+{
+    return (prefix_toa2x (prefix, buff, 0));
+}
+
+/* prefix_toa
+ */
+char *
+prefix_toa (prefix_t * prefix)
+{
+    return (prefix_toa2 (prefix, (char *) NULL));
+}
+
+prefix_t *
+New_Prefix2 (int family, void *dest, int bitlen, prefix_t *prefix)
+{
+    int dynamic_allocated = 0;
+    int default_bitlen = 32;
+
+#ifdef HAVE_IPV6
+    if (family == AF_INET6) {
+        default_bitlen = 128;
+        if (prefix == NULL) {
+            prefix = calloc(1, sizeof (prefix6_t));
+            dynamic_allocated++;
+        }
+        memcpy (&prefix->add.sin6, dest, 16);
+    }
+    else
+#endif /* HAVE_IPV6 */
+    if (family == AF_INET) {
+                if (prefix == NULL) {
+#ifndef NT
+            prefix = calloc(1, sizeof (prefix4_t));
+#else
+                        //for some reason, compiler is getting
+                        //prefix4_t size incorrect on NT
+                        prefix = calloc(1, sizeof (prefix_t)); 
+#endif /* NT */
+                
+                        dynamic_allocated++;
+                }
+                memcpy (&prefix->add.sin, dest, 4);
+    }
+    else {
+        return (NULL);
+    }
+
+    prefix->bitlen = (bitlen >= 0)? bitlen: default_bitlen;
+    prefix->family = family;
+    prefix->ref_count = 0;
+    if (dynamic_allocated) {
+        prefix->ref_count++;
+   }
+/* fprintf(stderr, "[C %s, %d]\n", prefix_toa (prefix), prefix->ref_count); */
+    return (prefix);
+}
+
+prefix_t *
+New_Prefix (int family, void *dest, int bitlen)
+{
+    return (New_Prefix2 (family, dest, bitlen, NULL));
+}
+
+/* ascii2prefix
+ */
+prefix_t *
+ascii2prefix (int family, char *string)
+{
+    u_long bitlen, maxbitlen = 0;
+    char *cp;
+    struct in_addr sin;
+#ifdef HAVE_IPV6
+    struct in6_addr sin6;
+#endif /* HAVE_IPV6 */
+    int result;
+    char save[MAXLINE];
+
+    if (string == NULL)
+                return (NULL);
+
+    /* easy way to handle both families */
+    if (family == 0) {
+       family = AF_INET;
+#ifdef HAVE_IPV6
+       if (strchr (string, ':')) family = AF_INET6;
+#endif /* HAVE_IPV6 */
+    }
+
+    if (family == AF_INET) {
+                maxbitlen = 32;
+    }
+#ifdef HAVE_IPV6
+    else if (family == AF_INET6) {
+                maxbitlen = 128;
+    }
+#endif /* HAVE_IPV6 */
+
+    if ((cp = strchr (string, '/')) != NULL) {
+                bitlen = atol (cp + 1);
+                /* *cp = '\0'; */
+                /* copy the string to save. Avoid destroying the string */
+                assert (cp - string < MAXLINE);
+                memcpy (save, string, cp - string);
+                save[cp - string] = '\0';
+                string = save;
+                if (bitlen < 0 || bitlen > maxbitlen)
+                        bitlen = maxbitlen;
+                }
+                else {
+                        bitlen = maxbitlen;
+                }
+
+                if (family == AF_INET) {
+                        if ((result = my_inet_pton (AF_INET, string, &sin)) <= 0)
+                                return (NULL);
+                        return (New_Prefix (AF_INET, &sin, bitlen));
+                }
+
+#ifdef HAVE_IPV6
+                else if (family == AF_INET6) {
+// Get rid of this with next IPv6 upgrade
+#if defined(NT) && !defined(HAVE_INET_NTOP)
+                        inet6_addr(string, &sin6);
+                        return (New_Prefix (AF_INET6, &sin6, bitlen));
+#else
+                        if ((result = inet_pton (AF_INET6, string, &sin6)) <= 0)
+                                return (NULL);
+#endif /* NT */
+                        return (New_Prefix (AF_INET6, &sin6, bitlen));
+                }
+#endif /* HAVE_IPV6 */
+                else
+                        return (NULL);
+}
+
+prefix_t *
+Ref_Prefix (prefix_t * prefix)
+{
+    if (prefix == NULL)
+        return (NULL);
+    if (prefix->ref_count == 0) {
+        /* make a copy in case of a static prefix */
+        return (New_Prefix2 (prefix->family, &prefix->add, prefix->bitlen, NULL));
+    }
+    prefix->ref_count++;
+/* fprintf(stderr, "[A %s, %d]\n", prefix_toa (prefix), prefix->ref_count); */
+    return (prefix);
+}
+
+void 
+Deref_Prefix (prefix_t * prefix)
+{
+    if (prefix == NULL)
+        return;
+    /* for secure programming, raise an assert. no static prefix can call this */
+    assert (prefix->ref_count > 0);
+
+    prefix->ref_count--;
+    assert (prefix->ref_count >= 0);
+    if (prefix->ref_count <= 0) {
+        Delete (prefix);
+        return;
+    }
+}
+
+/* } */
+
+/* #define PATRICIA_DEBUG 1 */
+
+static int num_active_patricia = 0;
+
+/* these routines support continuous mask only */
+
+patricia_tree_t *
+New_Patricia (int maxbits)
+{
+    patricia_tree_t *patricia = calloc(1, sizeof *patricia);
+
+    patricia->maxbits = maxbits;
+    patricia->head = NULL;
+    patricia->num_active_node = 0;
+    assert (maxbits <= PATRICIA_MAXBITS); /* XXX */
+    num_active_patricia++;
+    return (patricia);
+}
+
+
+/*
+ * if func is supplied, it will be called as func(node->data)
+ * before deleting the node
+ */
+
+void
+Clear_Patricia (patricia_tree_t *patricia, void_fn_t func)
+{
+    assert (patricia);
+    if (patricia->head) {
+
+        patricia_node_t *Xstack[PATRICIA_MAXBITS+1];
+        patricia_node_t **Xsp = Xstack;
+        patricia_node_t *Xrn = patricia->head;
+
+        while (Xrn) {
+            patricia_node_t *l = Xrn->l;
+            patricia_node_t *r = Xrn->r;
+
+                if (Xrn->prefix) {
+                Deref_Prefix (Xrn->prefix);
+                if (Xrn->data && func)
+                        func (Xrn->data);
+                }
+                else {
+                assert (Xrn->data == NULL);
+                }
+                Delete (Xrn);
+            patricia->num_active_node--;
+
+            if (l) {
+                if (r) {
+                    *Xsp++ = r;
+                }
+                Xrn = l;
+            } else if (r) {
+                Xrn = r;
+            } else if (Xsp != Xstack) {
+                Xrn = *(--Xsp);
+            } else {
+                Xrn = (patricia_node_t *) 0;
+            }
+        }
+    }
+    assert (patricia->num_active_node == 0);
+    /* Delete (patricia); */
+}
+
+
+void
+Destroy_Patricia (patricia_tree_t *patricia, void_fn_t func)
+{
+    Clear_Patricia (patricia, func);
+    Delete (patricia);
+    num_active_patricia--;
+}
+
+
+/*
+ * if func is supplied, it will be called as func(node->prefix, node->data)
+ */
+
+void
+patricia_process (patricia_tree_t *patricia, void_fn_t func)
+{
+    patricia_node_t *node;
+    assert (func);
+
+    PATRICIA_WALK (patricia->head, node) {
+        func (node->prefix, node->data);
+    } PATRICIA_WALK_END;
+}
+
+size_t
+patricia_walk_inorder(patricia_node_t *node, void_fn_t func)
+{
+    size_t n = 0;
+    assert(func);
+
+    if (node->l) {
+         n += patricia_walk_inorder(node->l, func);
+    }
+
+    if (node->prefix) {
+        func(node->prefix, node->data);
+        n++;
+    }
+        
+    if (node->r) {
+         n += patricia_walk_inorder(node->r, func);
+    }
+
+    return n;
+}
+
+
+patricia_node_t *
+patricia_search_exact (patricia_tree_t *patricia, prefix_t *prefix)
+{
+    patricia_node_t *node;
+    u_char *addr;
+    u_int bitlen;
+
+    assert (patricia);
+    assert (prefix);
+    assert (prefix->bitlen <= patricia->maxbits);
+
+    if (patricia->head == NULL)
+        return (NULL);
+
+    node = patricia->head;
+    addr = prefix_touchar (prefix);
+    bitlen = prefix->bitlen;
+
+    while (node->bit < bitlen) {
+
+        if (BIT_TEST (addr[node->bit >> 3], 0x80 >> (node->bit & 0x07))) {
+#ifdef PATRICIA_DEBUG
+            if (node->prefix)
+                    fprintf (stderr, "patricia_search_exact: take right %s/%d\n", 
+                         prefix_toa (node->prefix), node->prefix->bitlen);
+            else
+                    fprintf (stderr, "patricia_search_exact: take right at %d\n", 
+                         node->bit);
+#endif /* PATRICIA_DEBUG */
+            node = node->r;
+        }
+        else {
+#ifdef PATRICIA_DEBUG
+            if (node->prefix)
+                    fprintf (stderr, "patricia_search_exact: take left %s/%d\n", 
+                         prefix_toa (node->prefix), node->prefix->bitlen);
+            else
+                    fprintf (stderr, "patricia_search_exact: take left at %d\n", 
+                         node->bit);
+#endif /* PATRICIA_DEBUG */
+            node = node->l;
+        }
+
+        if (node == NULL)
+            return (NULL);
+    }
+
+#ifdef PATRICIA_DEBUG
+    if (node->prefix)
+        fprintf (stderr, "patricia_search_exact: stop at %s/%d\n", 
+                 prefix_toa (node->prefix), node->prefix->bitlen);
+    else
+        fprintf (stderr, "patricia_search_exact: stop at %d\n", node->bit);
+#endif /* PATRICIA_DEBUG */
+    if (node->bit > bitlen || node->prefix == NULL)
+        return (NULL);
+    assert (node->bit == bitlen);
+    assert (node->bit == node->prefix->bitlen);
+    if (comp_with_mask (prefix_tochar (node->prefix), prefix_tochar (prefix),
+                        bitlen)) {
+#ifdef PATRICIA_DEBUG
+        fprintf (stderr, "patricia_search_exact: found %s/%d\n", 
+                 prefix_toa (node->prefix), node->prefix->bitlen);
+#endif /* PATRICIA_DEBUG */
+        return (node);
+    }
+    return (NULL);
+}
+
+
+/* if inclusive != 0, "best" may be the given prefix itself */
+patricia_node_t *
+patricia_search_best2 (patricia_tree_t *patricia, prefix_t *prefix, int inclusive)
+{
+    patricia_node_t *node;
+    patricia_node_t *stack[PATRICIA_MAXBITS + 1];
+    u_char *addr;
+    u_int bitlen;
+    int cnt = 0;
+
+    assert (patricia);
+    assert (prefix);
+    assert (prefix->bitlen <= patricia->maxbits);
+
+    if (patricia->head == NULL)
+        return (NULL);
+
+    node = patricia->head;
+    addr = prefix_touchar (prefix);
+    bitlen = prefix->bitlen;
+
+    while (node->bit < bitlen) {
+
+        if (node->prefix) {
+#ifdef PATRICIA_DEBUG
+            fprintf (stderr, "patricia_search_best: push %s/%d\n", 
+                     prefix_toa (node->prefix), node->prefix->bitlen);
+#endif /* PATRICIA_DEBUG */
+            stack[cnt++] = node;
+        }
+
+        if (BIT_TEST (addr[node->bit >> 3], 0x80 >> (node->bit & 0x07))) {
+#ifdef PATRICIA_DEBUG
+            if (node->prefix)
+                    fprintf (stderr, "patricia_search_best: take right %s/%d\n", 
+                         prefix_toa (node->prefix), node->prefix->bitlen);
+            else
+                    fprintf (stderr, "patricia_search_best: take right at %d\n", 
+                         node->bit);
+#endif /* PATRICIA_DEBUG */
+            node = node->r;
+        }
+        else {
+#ifdef PATRICIA_DEBUG
+            if (node->prefix)
+                    fprintf (stderr, "patricia_search_best: take left %s/%d\n", 
+                         prefix_toa (node->prefix), node->prefix->bitlen);
+            else
+                    fprintf (stderr, "patricia_search_best: take left at %d\n", 
+                         node->bit);
+#endif /* PATRICIA_DEBUG */
+            node = node->l;
+        }
+
+        if (node == NULL)
+            break;
+    }
+
+    if (inclusive && node && node->prefix)
+        stack[cnt++] = node;
+
+#ifdef PATRICIA_DEBUG
+    if (node == NULL)
+        fprintf (stderr, "patricia_search_best: stop at null\n");
+    else if (node->prefix)
+        fprintf (stderr, "patricia_search_best: stop at %s/%d\n", 
+                 prefix_toa (node->prefix), node->prefix->bitlen);
+    else
+        fprintf (stderr, "patricia_search_best: stop at %d\n", node->bit);
+#endif /* PATRICIA_DEBUG */
+
+    if (cnt <= 0)
+        return (NULL);
+
+    while (--cnt >= 0) {
+        node = stack[cnt];
+#ifdef PATRICIA_DEBUG
+        fprintf (stderr, "patricia_search_best: pop %s/%d\n", 
+                 prefix_toa (node->prefix), node->prefix->bitlen);
+#endif /* PATRICIA_DEBUG */
+        if (comp_with_mask (prefix_tochar (node->prefix), 
+                            prefix_tochar (prefix),
+                            node->prefix->bitlen)) {
+#ifdef PATRICIA_DEBUG
+            fprintf (stderr, "patricia_search_best: found %s/%d\n", 
+                     prefix_toa (node->prefix), node->prefix->bitlen);
+#endif /* PATRICIA_DEBUG */
+            return (node);
+        }
+    }
+    return (NULL);
+}
+
+
+patricia_node_t *
+patricia_search_best (patricia_tree_t *patricia, prefix_t *prefix)
+{
+    return (patricia_search_best2 (patricia, prefix, 1));
+}
+
+
+patricia_node_t *
+patricia_lookup (patricia_tree_t *patricia, prefix_t *prefix)
+{
+    patricia_node_t *node, *new_node, *parent, *glue;
+    u_char *addr, *test_addr;
+    u_int bitlen, check_bit, differ_bit;
+    int i, j, r;
+
+    assert (patricia);
+    assert (prefix);
+    assert (prefix->bitlen <= patricia->maxbits);
+
+    if (patricia->head == NULL) {
+        node = calloc(1, sizeof *node);
+        node->bit = prefix->bitlen;
+        node->prefix = Ref_Prefix (prefix);
+        node->parent = NULL;
+        node->l = node->r = NULL;
+        node->data = NULL;
+        patricia->head = node;
+#ifdef PATRICIA_DEBUG
+        fprintf (stderr, "patricia_lookup: new_node #0 %s/%d (head)\n", 
+                 prefix_toa (prefix), prefix->bitlen);
+#endif /* PATRICIA_DEBUG */
+        patricia->num_active_node++;
+        return (node);
+    }
+
+    addr = prefix_touchar (prefix);
+    bitlen = prefix->bitlen;
+    node = patricia->head;
+
+    while (node->bit < bitlen || node->prefix == NULL) {
+
+        if (node->bit < patricia->maxbits &&
+            BIT_TEST (addr[node->bit >> 3], 0x80 >> (node->bit & 0x07))) {
+            if (node->r == NULL)
+                break;
+#ifdef PATRICIA_DEBUG
+            if (node->prefix)
+                    fprintf (stderr, "patricia_lookup: take right %s/%d\n", 
+                         prefix_toa (node->prefix), node->prefix->bitlen);
+            else
+                    fprintf (stderr, "patricia_lookup: take right at %d\n", node->bit);
+#endif /* PATRICIA_DEBUG */
+            node = node->r;
+        }
+        else {
+            if (node->l == NULL)
+                break;
+#ifdef PATRICIA_DEBUG
+            if (node->prefix)
+                    fprintf (stderr, "patricia_lookup: take left %s/%d\n", 
+                     prefix_toa (node->prefix), node->prefix->bitlen);
+            else
+                    fprintf (stderr, "patricia_lookup: take left at %d\n", node->bit);
+#endif /* PATRICIA_DEBUG */
+            node = node->l;
+        }
+
+        assert (node);
+    }
+
+    assert (node->prefix);
+#ifdef PATRICIA_DEBUG
+    fprintf (stderr, "patricia_lookup: stop at %s/%d\n", 
+             prefix_toa (node->prefix), node->prefix->bitlen);
+#endif /* PATRICIA_DEBUG */
+
+    test_addr = prefix_touchar (node->prefix);
+    /* find the first bit different */
+    check_bit = (node->bit < bitlen)? node->bit: bitlen;
+    differ_bit = 0;
+    for (i = 0; i*8 < check_bit; i++) {
+        if ((r = (addr[i] ^ test_addr[i])) == 0) {
+            differ_bit = (i + 1) * 8;
+            continue;
+        }
+        /* I know the better way, but for now */
+        for (j = 0; j < 8; j++) {
+            if (BIT_TEST (r, (0x80 >> j)))
+                break;
+        }
+        /* must be found */
+        assert (j < 8);
+        differ_bit = i * 8 + j;
+        break;
+    }
+    if (differ_bit > check_bit)
+        differ_bit = check_bit;
+#ifdef PATRICIA_DEBUG
+    fprintf (stderr, "patricia_lookup: differ_bit %d\n", differ_bit);
+#endif /* PATRICIA_DEBUG */
+
+    parent = node->parent;
+    while (parent && parent->bit >= differ_bit) {
+        node = parent;
+        parent = node->parent;
+#ifdef PATRICIA_DEBUG
+        if (node->prefix)
+            fprintf (stderr, "patricia_lookup: up to %s/%d\n", 
+                     prefix_toa (node->prefix), node->prefix->bitlen);
+        else
+            fprintf (stderr, "patricia_lookup: up to %d\n", node->bit);
+#endif /* PATRICIA_DEBUG */
+    }
+
+    if (differ_bit == bitlen && node->bit == bitlen) {
+        if (node->prefix) {
+#ifdef PATRICIA_DEBUG 
+                fprintf (stderr, "patricia_lookup: found %s/%d\n", 
+                     prefix_toa (node->prefix), node->prefix->bitlen);
+#endif /* PATRICIA_DEBUG */
+            return (node);
+        }
+        node->prefix = Ref_Prefix (prefix);
+#ifdef PATRICIA_DEBUG
+        fprintf (stderr, "patricia_lookup: new node #1 %s/%d (glue mod)\n",
+                 prefix_toa (prefix), prefix->bitlen);
+#endif /* PATRICIA_DEBUG */
+        assert (node->data == NULL);
+        return (node);
+    }
+
+    new_node = calloc(1, sizeof *new_node);
+    new_node->bit = prefix->bitlen;
+    new_node->prefix = Ref_Prefix (prefix);
+    new_node->parent = NULL;
+    new_node->l = new_node->r = NULL;
+    new_node->data = NULL;
+    patricia->num_active_node++;
+
+    if (node->bit == differ_bit) {
+        new_node->parent = node;
+        if (node->bit < patricia->maxbits &&
+            BIT_TEST (addr[node->bit >> 3], 0x80 >> (node->bit & 0x07))) {
+            assert (node->r == NULL);
+            node->r = new_node;
+        }
+        else {
+            assert (node->l == NULL);
+            node->l = new_node;
+        }
+#ifdef PATRICIA_DEBUG
+        fprintf (stderr, "patricia_lookup: new_node #2 %s/%d (child)\n", 
+                 prefix_toa (prefix), prefix->bitlen);
+#endif /* PATRICIA_DEBUG */
+        return (new_node);
+    }
+
+    if (bitlen == differ_bit) {
+        if (bitlen < patricia->maxbits &&
+            BIT_TEST (test_addr[bitlen >> 3], 0x80 >> (bitlen & 0x07))) {
+            new_node->r = node;
+        }
+        else {
+            new_node->l = node;
+        }
+        new_node->parent = node->parent;
+        if (node->parent == NULL) {
+            assert (patricia->head == node);
+            patricia->head = new_node;
+        }
+        else if (node->parent->r == node) {
+            node->parent->r = new_node;
+        }
+        else {
+            node->parent->l = new_node;
+        }
+        node->parent = new_node;
+#ifdef PATRICIA_DEBUG
+        fprintf (stderr, "patricia_lookup: new_node #3 %s/%d (parent)\n", 
+                 prefix_toa (prefix), prefix->bitlen);
+#endif /* PATRICIA_DEBUG */
+    }
+    else {
+        glue = calloc(1, sizeof *glue);
+        glue->bit = differ_bit;
+        glue->prefix = NULL;
+        glue->parent = node->parent;
+        glue->data = NULL;
+        patricia->num_active_node++;
+        if (differ_bit < patricia->maxbits &&
+            BIT_TEST (addr[differ_bit >> 3], 0x80 >> (differ_bit & 0x07))) {
+            glue->r = new_node;
+            glue->l = node;
+        }
+        else {
+            glue->r = node;
+            glue->l = new_node;
+        }
+        new_node->parent = glue;
+
+        if (node->parent == NULL) {
+            assert (patricia->head == node);
+            patricia->head = glue;
+        }
+        else if (node->parent->r == node) {
+            node->parent->r = glue;
+        }
+        else {
+            node->parent->l = glue;
+        }
+        node->parent = glue;
+#ifdef PATRICIA_DEBUG
+        fprintf (stderr, "patricia_lookup: new_node #4 %s/%d (glue+node)\n", 
+                 prefix_toa (prefix), prefix->bitlen);
+#endif /* PATRICIA_DEBUG */
+    }
+    return (new_node);
+}
+
+
+void
+patricia_remove (patricia_tree_t *patricia, patricia_node_t *node)
+{
+    patricia_node_t *parent, *child;
+
+    assert (patricia);
+    assert (node);
+
+    if (node->r && node->l) {
+#ifdef PATRICIA_DEBUG
+        fprintf (stderr, "patricia_remove: #0 %s/%d (r & l)\n", 
+                 prefix_toa (node->prefix), node->prefix->bitlen);
+#endif /* PATRICIA_DEBUG */
+        
+        /* this might be a placeholder node -- have to check and make sure
+         * there is a prefix aossciated with it ! */
+        if (node->prefix != NULL) 
+          Deref_Prefix (node->prefix);
+        node->prefix = NULL;
+        /* Also I needed to clear data pointer -- masaki */
+        node->data = NULL;
+        return;
+    }
+
+    if (node->r == NULL && node->l == NULL) {
+#ifdef PATRICIA_DEBUG
+        fprintf (stderr, "patricia_remove: #1 %s/%d (!r & !l)\n", 
+                 prefix_toa (node->prefix), node->prefix->bitlen);
+#endif /* PATRICIA_DEBUG */
+        parent = node->parent;
+        Deref_Prefix (node->prefix);
+        Delete (node);
+        patricia->num_active_node--;
+
+        if (parent == NULL) {
+            assert (patricia->head == node);
+            patricia->head = NULL;
+            return;
+        }
+
+        if (parent->r == node) {
+            parent->r = NULL;
+            child = parent->l;
+        }
+        else {
+            assert (parent->l == node);
+            parent->l = NULL;
+            child = parent->r;
+        }
+
+        if (parent->prefix)
+            return;
+
+        /* we need to remove parent too */
+
+        if (parent->parent == NULL) {
+            assert (patricia->head == parent);
+            patricia->head = child;
+        }
+        else if (parent->parent->r == parent) {
+            parent->parent->r = child;
+        }
+        else {
+            assert (parent->parent->l == parent);
+            parent->parent->l = child;
+        }
+        child->parent = parent->parent;
+        Delete (parent);
+        patricia->num_active_node--;
+        return;
+    }
+
+#ifdef PATRICIA_DEBUG
+    fprintf (stderr, "patricia_remove: #2 %s/%d (r ^ l)\n", 
+             prefix_toa (node->prefix), node->prefix->bitlen);
+#endif /* PATRICIA_DEBUG */
+    if (node->r) {
+        child = node->r;
+    }
+    else {
+        assert (node->l);
+        child = node->l;
+    }
+    parent = node->parent;
+    child->parent = parent;
+
+    Deref_Prefix (node->prefix);
+    Delete (node);
+    patricia->num_active_node--;
+
+    if (parent == NULL) {
+        assert (patricia->head == node);
+        patricia->head = child;
+        return;
+    }
+
+    if (parent->r == node) {
+        parent->r = child;
+    }
+    else {
+        assert (parent->l == node);
+        parent->l = child;
+    }
+}
+
+/* { from demo.c */
+
+patricia_node_t *
+make_and_lookup (patricia_tree_t *tree, char *string)
+{
+    prefix_t *prefix;
+    patricia_node_t *node;
+
+    prefix = ascii2prefix (AF_INET, string);
+    printf ("make_and_lookup: %s/%d\n", prefix_toa (prefix), prefix->bitlen);
+    node = patricia_lookup (tree, prefix);
+    Deref_Prefix (prefix);
+    return (node);
+}
+
+patricia_node_t *
+try_search_exact (patricia_tree_t *tree, char *string)
+{
+    prefix_t *prefix;
+    patricia_node_t *node;
+
+    prefix = ascii2prefix (AF_INET, string);
+    printf ("try_search_exact: %s/%d\n", prefix_toa (prefix), prefix->bitlen);
+    if ((node = patricia_search_exact (tree, prefix)) == NULL) {
+        printf ("try_search_exact: not found\n");
+    }
+    else {
+        printf ("try_search_exact: %s/%d found\n", 
+                prefix_toa (node->prefix), node->prefix->bitlen);
+    }
+    Deref_Prefix (prefix);
+    return (node);
+}
+
+void
+lookup_then_remove (patricia_tree_t *tree, char *string)
+{
+    patricia_node_t *node;
+
+    if (node = try_search_exact (tree, string))
+        patricia_remove (tree, node);
+}
+
+patricia_node_t *
+try_search_best (patricia_tree_t *tree, char *string)
+{
+    prefix_t *prefix;
+    patricia_node_t *node;
+
+    prefix = ascii2prefix (AF_INET, string);
+    printf ("try_search_best: %s/%d\n", prefix_toa (prefix), prefix->bitlen);
+    if ((node = patricia_search_best (tree, prefix)) == NULL)
+        printf ("try_search_best: not found\n");
+    else
+        printf ("try_search_best: %s/%d found\n", 
+                prefix_toa (node->prefix), node->prefix->bitlen);
+    Deref_Prefix (prefix);
+}
+
+/* } */
diff --git a/patricia.h b/patricia.h
new file mode 100644
index 0000000..ee12744
--- /dev/null
+++ b/patricia.h
@@ -0,0 +1,147 @@
+/*
+ * $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;
+#ifdef HAVE_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;                        /* pointer to data */
+   void        *user;                /* 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;
+
+
+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);
+
+/* { from demo.c */
+
+prefix_t *
+ascii2prefix (int family, char *string);
+
+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 */
diff --git a/rpatricia.c b/rpatricia.c
new file mode 100644
index 0000000..75000e1
--- /dev/null
+++ b/rpatricia.c
@@ -0,0 +1,225 @@
+/*
+ *   rpatricia.c - Ruby wrapper of Net::Patricia
+ *   Tatsuya Mori <mori.tatsuya@gmail.com>
+ */
+
+#include "ruby.h"
+#include <stdio.h> /* printf */
+#include <stdlib.h>
+#include "patricia.h"
+
+VALUE cPatricia;
+
+void dummy(void) {}
+
+static VALUE
+p_destroy (VALUE self)
+{
+  patricia_tree_t *tree;
+  Data_Get_Struct(self, patricia_tree_t, tree);
+  Destroy_Patricia(tree, free);
+  return Qtrue;
+}
+
+VALUE
+p_add (int argc, VALUE *argv, VALUE self)
+{
+  int str_len;
+  char *user_data;
+  patricia_tree_t *tree;
+  patricia_node_t *node;
+  prefix_t *prefix;
+
+  if (argc > 2 || argc < 1) 
+    return Qnil;
+
+  Data_Get_Struct(self, patricia_tree_t, tree);
+  prefix = ascii2prefix(AF_INET, STR2CSTR(argv[0]));
+  node = patricia_lookup(tree, prefix);
+  Deref_Prefix(prefix);
+
+  if (argc == 2) {
+    user_data = STR2CSTR(argv[1]);
+    str_len = strlen(user_data);
+    node->data = (char *) malloc((str_len + 1) * sizeof(char));
+    sprintf((char *)node->data, user_data);
+  } else {
+    node->data = (char *) malloc(sizeof(char));
+    sprintf((char *)node->data, "");
+  }
+  return Data_Wrap_Struct(cPatricia, 0, 0, node);
+}
+
+static VALUE
+p_remove (VALUE self, VALUE r_key)
+{
+  char *c_key;
+  patricia_tree_t *tree;
+  patricia_node_t *node;
+  prefix_t *prefix;
+
+  Data_Get_Struct(self, patricia_tree_t, tree);
+  c_key = STR2CSTR(r_key);
+  prefix = ascii2prefix (AF_INET, c_key);
+  node = patricia_search_exact(tree, prefix);
+  Deref_Prefix (prefix);
+
+  if (node) {
+    patricia_remove (tree, node);
+    return Qtrue;
+  } else {
+    return Qfalse;
+  }
+}
+
+static VALUE
+p_match (VALUE self, VALUE r_key)
+{
+  patricia_tree_t *tree;
+  patricia_node_t *node;
+  prefix_t *prefix;
+  
+  Data_Get_Struct(self, patricia_tree_t, tree);
+  prefix = ascii2prefix (AF_INET, STR2CSTR(r_key));
+  node = patricia_search_best(tree, prefix);
+  Deref_Prefix (prefix);
+
+  if (node)
+    return Data_Wrap_Struct(cPatricia, 0, 0, node);
+  else 
+    return Qfalse;
+
+}
+
+static VALUE
+p_match_exact (VALUE self, VALUE r_key)
+{
+  patricia_tree_t *tree;
+  patricia_node_t *node;
+  prefix_t *prefix;
+
+  Data_Get_Struct(self, patricia_tree_t, tree);
+  prefix = ascii2prefix (AF_INET, STR2CSTR(r_key));
+  node = patricia_search_exact(tree, prefix);
+  Deref_Prefix (prefix);
+
+  if (node)
+    return Data_Wrap_Struct(cPatricia, 0, 0, node);
+  else 
+    return Qfalse;
+}
+
+static VALUE
+p_num_nodes (VALUE self)
+{
+  int n;
+  patricia_tree_t *tree;
+
+  Data_Get_Struct(self, patricia_tree_t, tree);
+  n = patricia_walk_inorder(tree->head, dummy);
+
+  return INT2NUM(n);
+}
+
+static VALUE
+p_print_nodes (VALUE self)
+{
+  int n;
+  char buff[32];
+  patricia_tree_t *tree;
+  patricia_node_t *node;
+  Data_Get_Struct(self, patricia_tree_t, tree);
+
+  PATRICIA_WALK(tree->head, node) {
+    prefix_toa2x(node->prefix, buff, 1);
+    printf("node: %s\n", buff);
+  } PATRICIA_WALK_END;
+  return Qtrue;
+}
+
+static VALUE
+p_data (VALUE self)
+{
+  patricia_node_t *node;
+  Data_Get_Struct(self, patricia_node_t, node);
+  return rb_str_new2((char *)node->data);
+}
+
+static VALUE
+p_network (VALUE self)
+{
+  char buff[32];
+  patricia_node_t *node;
+  Data_Get_Struct(self, patricia_node_t, node);
+  prefix_toa2x (node->prefix, buff, 0);
+  return rb_str_new2(buff);
+}
+
+static VALUE
+p_prefix (VALUE self)
+{
+  char buff[32];
+  patricia_node_t *node;
+  Data_Get_Struct(self, patricia_node_t, node);
+  prefix_toa2 (node->prefix, buff);
+  return rb_str_new2(buff);
+}
+
+static VALUE
+p_prefixlen (VALUE self)
+{
+  patricia_node_t *node;
+  Data_Get_Struct(self, patricia_node_t, node);
+  return INT2NUM(node->prefix->bitlen);
+}
+
+static VALUE
+p_new (VALUE self) 
+{
+  patricia_tree_t *tree;
+  tree = New_Patricia(32); /* assuming only IPv4 */
+  return Data_Wrap_Struct(cPatricia, 0, 0, tree);
+}
+
+void
+Init_rpatricia (void)
+{
+  cPatricia = rb_define_class("Patricia", rb_cObject);
+
+  /* create new Patricia object */
+  rb_define_singleton_method(cPatricia, "new", p_new, 0);
+
+  /*---------- methods to tree ----------*/
+  /* add string */
+  rb_define_method(cPatricia, "add", p_add, -1);
+  rb_define_method(cPatricia, "add_node", p_add, -1);
+
+  /* match prefix */
+  rb_define_method(cPatricia, "match_best", p_match, 1); 
+  rb_define_method(cPatricia, "search_best", p_match, 1); 
+
+  /* exact match  */
+  rb_define_method(cPatricia, "match_exact", p_match_exact, 1); 
+  rb_define_method(cPatricia, "search_exact", p_match_exact, 1); 
+
+  /* removal */
+  rb_define_method(cPatricia, "remove", p_remove, 1); 
+  rb_define_method(cPatricia, "remove_node", p_remove, 1); 
+
+  /* derivatives of climb */
+  rb_define_method(cPatricia, "num_nodes", p_num_nodes, 0);
+  rb_define_method(cPatricia, "show_nodes", p_print_nodes, 0); 
+
+  /* destroy tree */
+  rb_define_method(cPatricia, "destroy", p_destroy, 0); 
+  rb_define_method(cPatricia, "clear", p_destroy, 0); 
+
+  /*---------- methods to node ----------*/
+  rb_define_method(cPatricia, "data", p_data, 0);
+  rb_define_method(cPatricia, "show_data", p_data, 0);
+  rb_define_method(cPatricia, "network", p_network, 0);
+  rb_define_method(cPatricia, "prefix", p_prefix, 0);
+  rb_define_method(cPatricia, "prefixlen", p_prefixlen, 0);
+  //  rb_define_method(cPatricia, "family", p_family, 0); 
+
+}
diff --git a/test.rb b/test.rb
new file mode 100644
index 0000000..09a11d0
--- /dev/null
+++ b/test.rb
@@ -0,0 +1,63 @@
+require 'rpatricia'
+
+def my_test condition
+  puts (condition)? "ok!" : "error!"
+end
+
+puts "test: creating Patricia object"
+my_test(t = Patricia.new) 
+
+puts "test: adding 127.0.0.0/24"
+my_test(n = t.add("127.0.0.0/24"))
+
+puts "  data of added node = #{n.data}"
+puts "  prefix of added node = #{n.prefix}"
+puts "  network of added node = #{n.network}"
+puts "  prefixlen of added node = #{n.prefixlen}"
+
+puts "adding 192.168.1.0/24, 192.168.2.0/24, 192.168.3.100"
+t.add("192.168.1.0/24")
+t.add("192.168.2.0/24")
+t.add("192.168.3.100")
+
+puts "test: match_best 127.0.0.1"
+my_test(n = t.match_best("127.0.0.1"))
+
+puts "test: match_exact 192.168.3.100"
+my_test(n = t.match_best("192.168.3.100"))
+
+puts "  data of matched node = #{n.data}"
+puts "  prefix of matched node = #{n.prefix}"
+puts "  network of matched node = #{n.network}"
+puts "  prefixlen of matched node = #{n.prefixlen}"
+
+puts "test: adding prefix 10.0.0.0/8 with user data of 'pref_10.0.0.0/8'"
+my_test(n = t.add("10.0.0.0/8", "pref_10"))
+
+puts "  data of added node = #{n.data}"
+puts "  prefix of added node = #{n.prefix}"
+puts "  network of added node = #{n.network}"
+puts "  prefixlen of added node = #{n.prefixlen}"
+
+puts "test: match string 10.0.0.1"
+my_test(n = t.match_best("10.0.0.1"))
+
+puts "  data of matched node = #{n.data}"
+puts "  prefix of matched node = #{n.prefix}"
+puts "  network of matched node = #{n.network}"
+puts "  prefixlen of matched node = #{n.prefixlen}"
+
+puts "test: remove '42.0.0.0/8'; should return nil"
+my_test(!t.remove("42.0.0.0/8"))
+
+puts "test: remove '10.0.0.0/8'"
+my_test(n= t.remove("10.0.0.0/8"))
+
+
+puts "test: number of nodes in the tree should be '4'"
+my_test(4 == t.num_nodes)
+
+puts "test: showing all nodes"
+t.show_nodes
+
+t.destroy