py-radix is an implementation of a radix tree data structure for the storage 
and retrieval of IPv4 and IPv6 network prefixes.

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

To install, use the standard Python distutils incantation:

	python setup.py build
	python setup.py install

Regression tests are in the test.py file.

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 to Damien Miller <djm@mindrot.org>. Please check the TODO
file first, in case your problem is something I already know about (please
send patches!)

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("10.0.0.0/8")
	rnode.data["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("10.0.0.0/16")
	rnode = rtree.add("10.0.0.0", 16)
	rnode = rtree.add(network = "10.0.0.0", 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("172.18.22.0")
	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("10.0.0.0/8")
	# Get your data back out
	print rnode.data["blah"]
	# Use a packed address
	addr = socket.inet_ntoa("10.0.0.0")
	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("10.123.45.6")

	# There are a couple of implicit members of a RadixNode:
	print rnode.network	# -> "10.0.0.0"
	print rnode.prefix	# -> "10.0.0.0/8"
	print rnode.prefixlen	# -> 8
	print rnode.family	# -> 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


$Id$