StuffIveLearned.org

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== 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:
<code>
Radix.search_all_containing(<network>) -> [ <node> , <node> , ... ]
</code>
<code python>
#!/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']
</code>

===== The Patch =====
Here is the code for the patch, followed by a link to the file.
<code>
--- 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            },
</code>

The patch file: {{:programming:python:radix_python.c.patch.gz|}}

===== Patching =====
Download the above patch file and do the following:
<code>
# 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
</code>
The last line there will install the patched module.