====== py-radix search_all_containing patch ======
===== What it is =====
[[http://www.mindrot.org/projects/py-radix/|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 [[http://net.doit.wisc.edu/~plonka/Net-Patricia/|Net::Patricia]] module. See the first link for the official [[http://www.mindrot.org/projects/py-radix/|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 [[http://www.mindrot.org/projects/py-radix/|py-radix]] source. It adds a method to the radix tree object.
===== search_all_containing =====
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.
===== An Example =====
This following example should illustrate the usage and results.
Usage:
Radix.search_all_containing() -> [ , , ... ]
#!/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']
===== The Patch =====
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: {{:programming:python:radix_python.c.patch.gz|}}
===== Patching =====
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.