diff options
author | Eric Wong <normalperson@yhbt.net> | 2010-02-10 17:45:53 -0800 |
---|---|---|
committer | Eric Wong <normalperson@yhbt.net> | 2010-02-10 17:45:53 -0800 |
commit | 643e2a5cf9235e27f3910f0de9b5dba0f518baf1 (patch) | |
tree | 5437f29f7694e75f3e57392e53c5856f06636adb | |
download | rpatricia-643e2a5cf9235e27f3910f0de9b5dba0f518baf1.tar.gz |
initial
-rw-r--r-- | Changes | 16 | ||||
-rw-r--r-- | README | 179 | ||||
-rw-r--r-- | TODO | 2 | ||||
-rw-r--r-- | copyright | 34 | ||||
-rw-r--r-- | credits.txt | 73 | ||||
-rwxr-xr-x | extconf.rb | 5 | ||||
-rw-r--r-- | patricia.c | 1038 | ||||
-rw-r--r-- | patricia.h | 147 | ||||
-rw-r--r-- | rpatricia.c | 225 | ||||
-rw-r--r-- | test.rb | 63 |
10 files changed, 1782 insertions, 0 deletions
@@ -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 @@ -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> @@ -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); + +} @@ -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 |