py-radix search_all_containing patch

py-radix is a python library written to handle lookups for IPv4 and IPv6 addresses and is basically the equivalent of Dave Plonka's Perl Net::Patricia module. See the first link for the official py-radix page, which contains more information.

The patch for this that I have written covers one of the items on the TODO list included with py-radix source. It adds a method to the radix tree object.

This method can be called to return the node hierarchy for a search_best() type of search instead of just the best matching node. This method is called in exactly the same way as the search_best() method is. See the module's documentation for more info.

This following example should illustrate the usage and results.

Usage:

Radix.search_all_containing(<network>) -> [ <node> , <node> , ... ]

#!/usr/bin/env python
 
import radix
 
r = radix.Radix()
 
n = r.add('0/0')
n.data['s'] = '0/0 test'
n = r.add('10.0.0.1/8')
n.data['s'] = '10/8 test'
n = r.add('10.0.1.1/24')
n.data['s'] = '10.0.1/24 test'
n = r.add('10.0.1.69')
n.data['s'] = '10.0.1.69/32 test'
n =r.add('192.168.0.1/16')
n.data['s'] = '192.168/16 test'
 
s1 = '10.0.1.5'
s2 = '192.168.0.1'
s3 = '209.98.98.98'
s4 = '10.0.1.69'
 
for p in r.prefixes():
    print p
print
 
print 'search_best(%s): %s' % (s1 , r.search_best(s1).prefix)
    PRINTS: search_best(10.0.1.5): 10.0.1.0/24
 
print 'search_all(%s): %s' % (s1 , [n.prefix for n in r.search_all_containing(s1)])
    PRINTS: search_all(10.0.1.5): ['10.0.1.0/24', '10.0.0.0/8', '0.0.0.0/0']
 
print 'search_all(%s): %s' % (s2 , [n.prefix for n in r.search_all_containing(s2)])
    PRINTS: search_all(192.168.0.1): ['192.168.0.0/16', '0.0.0.0/0']
 
print 'search_all(%s): %s' % (s3 , [n.prefix for n in r.search_all_containing(s3)])
    PRINTS: search_all(209.98.98.98): ['0.0.0.0/0']
 
print 'search_all(%s): %s' % (s4 , [n.data['s'] for n in r.search_all_containing(s4)])
    PRINTS: search_all(10.0.1.69): ['10.0.1.69/32', '10.0.1.0/24', '10.0.0.0/8', '0.0.0.0/0']

Here is the code for the patch, followed by a link to the file.

--- radix_python.c  2008-07-05 17:08:51.000000000 -0500
+++ radix_python.c.new  2008-07-05 17:08:11.000000000 -0500
@@ -453,6 +453,52 @@
    return (PyObject *)node_obj;
 }

+PyDoc_STRVAR(Radix_search_all_containing_doc,
+"Radix.search_all_containing(network[, masklen][, packed] -> None\n\
+\n\
+Search for the specified network in the radix tree and return a list\n\
+of all networks containing the queried item from most specific to \n\
+least specific\n\
+\n\
+If no match is found, then returns None.");
+
+static PyObject *
+Radix_search_all_containing(RadixObject *self, PyObject *args,
+       PyObject *kw_args)
+{
+   radix_node_t *node , *parent;
+   RadixNodeObject *node_obj;
+   PyObject *node_list;
+   prefix_t *prefix;
+   static char *keywords[] = { "network", "masklen", "packed", NULL };
+
+   char *addr = NULL, *packed = NULL;
+   long prefixlen = -1;
+   int packlen = -1;
+   if ((node_list = PyList_New(0)) == NULL)
+       return NULL;
+
+   if (!PyArg_ParseTupleAndKeywords(args, kw_args, "|sls#:search_all_containing", keywords,
+       &addr, &prefixlen, &packed, &packlen))
+       return NULL;
+   if ((prefix = args_to_prefix(addr, packed, packlen, prefixlen)) == NULL)
+       return NULL;
+
+   if ((node = radix_search_best(PICKRT(prefix, self), prefix)) == NULL ||
+       node->data == NULL) {
+       Deref_Prefix(prefix);
+       return node_list;
+   }
+   Deref_Prefix(prefix);
+   PyList_Append(node_list , (PyObject *)node->data);
+   while ((parent = node->parent) != NULL) {
+        if (parent->data != NULL)
+            PyList_Append(node_list , (PyObject *)parent->data);
+       node = parent;
+   }
+   return node_list;
+}
+
 PyDoc_STRVAR(Radix_nodes_doc,
 "Radix.nodes(prefix) -> List of RadixNode\n\
 \n\
@@ -640,6 +686,7 @@
    {"delete",  (PyCFunction)Radix_delete,  METH_VARARGS|METH_KEYWORDS, Radix_delete_doc    },
    {"search_exact",(PyCFunction)Radix_search_exact,METH_VARARGS|METH_KEYWORDS, Radix_search_exact_doc  },
    {"search_best", (PyCFunction)Radix_search_best, METH_VARARGS|METH_KEYWORDS, Radix_search_best_doc   },
+   {"search_all_containing",   (PyCFunction)Radix_search_all_containing,   METH_VARARGS|METH_KEYWORDS, Radix_search_all_containing_doc },
    {"nodes",   (PyCFunction)Radix_nodes,   METH_VARARGS,           Radix_nodes_doc     },
    {"prefixes",    (PyCFunction)Radix_prefixes,    METH_VARARGS,           Radix_prefixes_doc  },
    {"__getstate__",(PyCFunction)Radix_getstate,    METH_VARARGS,           NULL            },

The patch file: radix_python.c.patch.gz

Download the above patch file and do the following:

# cp radix_python.c.patch.gz /path/to/untarred/py-radix/source/directory
# cd /path/to/untarred/py-radix/source/directory
# gunzip radix_python.c.patch.gz
# patch -p0 radix_python.c < radix_python.c.patch
# python setup.py install

The last line there will install the patched module.