Skip to main content

Pure-Python radix tree implementation

Project description


ppy-radix is a pure-Python fork of py-radix_, which implements the radix tree
data structure for the storage andretrieval of IPv4 and IPv6 network prefixes.

.. _py-radix:

The radix tree is commonly used for routing table lookups. It efficiently
stores network prefixes of varying lengths and allows fast lookups of
containing networks.

(In this fork, the C implementation has been removed in order to simplify use
with AWS Lambda in non-performance-critical cases. Otherwise this fork tracks
the upstream py-radix repo. The better solution would be to build a
`manylinux1 wheel`__ for py-radix.)

.. _manylinux1 wheel:


Installation is a breeze via pip: ::

pip install ppy-radix

Or with the standard Python distutils incantation: ::

python build
python install

Tests are in the ``tests/`` directory and can be run with
``python nosetests``.


A simple example that demonstrates most of the features: ::

import radix

# Create a new tree
rtree = radix.Radix()

# Adding a node returns a RadixNode object. You can create
# arbitrary members in its 'data' dict to store your data
rnode = rtree.add("")["blah"] = "whatever you want"

# You can specify nodes as CIDR addresses, or networks with
# separate mask lengths. The following three invocations are
# identical:
rnode = rtree.add("")
rnode = rtree.add("", 16)
rnode = rtree.add(network = "", masklen = 16)

# It is also possible to specify nodes using binary packed
# addresses, such as those returned by the socket module
# functions. In this case, the radix module will assume that
# a four-byte address is an IPv4 address and a sixteen-byte
# address is an IPv6 address. For example:
binary_addr = inet_ntoa("")
rnode = rtree.add(packed = binary_addr, masklen = 23)

# Exact search will only return prefixes you have entered
# You can use all of the above ways to specify the address
rnode = rtree.search_exact("")
# Get your data back out
# Use a packed address
addr = socket.inet_ntoa("")
rnode = rtree.search_exact(packed = addr, masklen = 8)

# Best-match search will return the longest matching prefix
# that contains the search term (routing-style lookup)
rnode = rtree.search_best("")

# Worst-search will return the shortest matching prefix
# that contains the search term (inverse routing-style lookup)
rnode = rtree.search_worst("")

# Covered search will return all prefixes inside the given
# search term, as a list (including the search term itself,
# if present in the tree)
rnodes = rtree.search_covered("")

# There are a couple of implicit members of a RadixNode:
print # -> ""
print rnode.prefix # -> ""
print rnode.prefixlen # -> 8
print # -> socket.AF_INET
print rnode.packed # -> '\n\x00\x00\x00'

# IPv6 prefixes are fully supported in the same tree
rnode = rtree.add("2001:DB8::/3")
rnode = rtree.add("::/0")

# Use the nodes() method to return all RadixNodes created
nodes = rtree.nodes()
for rnode in nodes:
print rnode.prefix

# The prefixes() method will return all the prefixes (as a
# list of strings) that have been entered
prefixes = rtree.prefixes()

# You can also directly iterate over the tree itself
# this would save some memory if the tree is big
# NB. Don't modify the tree (add or delete nodes) while
# iterating otherwise you will abort the iteration and
# receive a RuntimeWarning. Changing a node's data dict
# is permitted.
for rnode in rtree:
print rnode.prefix


ppy-radix, like py-radix, is licensed under a ISC/BSD licence. The underlying
radix tree implementation is taken (and modified) from MRTd and is subject to
a 4-term BSD license. See the LICENSE file for details.


Please report bugs via GitHub to the original py-radix project at
Code changes can be contributed through a pull request on GitHub or emailed
directly to the upstream author <>.

The main portions of the directory tree are as follows: ::

├── radix/*.py # Pure Python code
├── tests/ # Tests (regression and unit)
└── # Standard for installation/testing/etc.

Project details

Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

ppy-radix-0.10.0.tar.gz (10.1 kB view hashes)

Uploaded Source

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page