From 643e2a5cf9235e27f3910f0de9b5dba0f518baf1 Mon Sep 17 00:00:00 2001 From: Eric Wong Date: Wed, 10 Feb 2010 17:45:53 -0800 Subject: initial --- Changes | 16 + README | 179 +++++++++++ TODO | 2 + copyright | 34 ++ credits.txt | 73 +++++ extconf.rb | 5 + patricia.c | 1038 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ patricia.h | 147 +++++++++ rpatricia.c | 225 +++++++++++++ test.rb | 63 ++++ 10 files changed, 1782 insertions(+) create mode 100644 Changes create mode 100644 README create mode 100644 TODO create mode 100644 copyright create mode 100644 credits.txt create mode 100755 extconf.rb create mode 100644 patricia.c create mode 100644 patricia.h create mode 100644 rpatricia.c create mode 100644 test.rb 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 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 + * [3]Makaki Hirabaru + * [4]Farnam Jahanian + * Susan Hares + * Susan R. Harris + * Nathan Binkert + * Gerald Winters + + Project Alumni + + * [5]Marc Unangst + * John Scudder + + The BGP4+ extension was originally written by Francis Dupont + . + + The public domain Struct C-library of linked list, hash table and + memory allocation routines was developed by Jonathan Dekock + . + + Susan Rebecca Harris provided help with the + documentation. + David Ward 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 + . 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 + * + * 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 */ +#include /* isdigit */ +#include /* errno */ +#include /* sin */ +#include /* NULL */ +#include /* sprintf, fprintf, stderr */ +#include /* free, atol, calloc */ +#include /* memcpy, strchr, strlen */ +#include /* BSD: for inet_addr */ +#include /* BSD, Linux: for inet_addr */ +#include /* BSD, Linux: for inet_addr */ +#include /* 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 + * + * 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 /* for u_* definitions (on FreeBSD 5) */ + +#include /* for EAFNOSUPPORT */ +#ifndef EAFNOSUPPORT +# defined EAFNOSUPPORT WSAEAFNOSUPPORT +# include +#else +# include /* for struct in_addr */ +#endif + +#include /* 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 + */ + +#include "ruby.h" +#include /* printf */ +#include +#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 -- cgit v1.2.3-24-ge0c7