Radix.pm

NAME

Tree::Radix - Binary radix tree in perl

SYNOPSIS

use Tree::Radix; $key = Tree::Radix::Key->new(keyhex=>"42"); $tree = Tree::Radix->new(); $tree->insert($key); my $maybe_key = $tree->search($key); $tree->delete($key);

DESCRIPTION

Tree::Radix is a collection of classes for developing algorithms that use binary radix trees (e.g. routing tables). For references on the underlying algorithm, see Knuth Volume 3, Section 6.3 on digital trees, particularly patricia trees, or Sedgewick's Algorithms in Language on same.

Classes

This radix tree implementation is composed of five classes. In simple cases, only two of these classes need to be understood. For more complex cases, understanding the internals of the module may be required. The module has (hopefully) been engineered for overriding most behavior while saving some grunt work.

The top-level Tree::Radix class is a container class representing entire trees.

Tree::Radix::Key objects encapsulate the key data that is encoded in the radix tree. They are currently implemented using Bit::Vector objects.

Three other classes, Tree::Radix::Node, Tree::Radix::Node::Branch and Tree::Radix::Node::Leaf are used by the module to represent the structure of the tree. The Branch and Leaf classes are descended from the Node class. The Node class is only used as a base class; objects of this type are never created.

Using the Key Class

Tree::Radix::Key objects represent the keys that you are interested in inserting into your Radix tree. At some point you generally want to try to match arbitrary data against the keys you have inserted.

This class also abstracts the radix tree's idea of ``endianess'' of keys. The tree's internal representation always roots the tree at zero, and counts upward. The key class decides which end of the key is considered zero. The most signifigant bit of the key is considered zero, although this is designed to be easily overridden.

The Tree::Radix::Key class has the following methods:

new([ARGS])

This is the constructor for a new key object. When called to create a new object, it requires that ARGS be passed in a hash like fashion. At least one of the following arguments is required in the hash to create a key object:

keyvector - A Bit::Vector object to clone.

keyhex - A hexidecimal string (with no leading ``0x'' or similar prefix) representing the key.

keypacked - A packed binary string (ala pack) to use for the key data.

The number of bits used to represent newly created keys (this does apply to keys created from Bit::Vector objects) defaults to 32. You can pass a keybits option in the hash to use a different number of bits.

If new is called like a method on an already existing object, it will clone that object.

bitvec([NEWKEY])

Simple accessor/mutator for an internal variable. With no arguments, returns the Bit::Vector object representing the key. Given NEWKEY, mutates this slot of the object. This function is primarily for internal use.

data([NEWDATA])

Simple accessor/mutator for a user convenience variable. With no arguments, returns the whatever is sitting in the data slot. Given NEWDATA, mutates this slot of the object. This slot is provided for the conveniance of the user who doesn't want to go to the trouble of subclassing this object just to add space for some arbitrary data.

string()

Return a string representation of the key (for debugging convenience).

compare(KEY2)

Compare KEY2 to self's key (remember, this is a method), returning true if they match.

bit_diff(KEY2)

Return the first bit position where KEY2 differs from self's key. Override this method if you need to change which way the radix tree's endianness works.

bit_test(BIT)

Return true if BIT is set in self's key. Override this method if you need to change which way the radix tree's endianness works.

new_branch()

This is an internal function that Tree::Radix uses to create new internal nodes in the tree. Provided to be overrided by subclasses.

new_leaf()

This is an internal function that Tree::Radix uses to create new leaf nodes in the tree. Provided to be overrided by subclasses.

The Tree::Radix class

This class represents entire radix trees, and is where most of the functionality of the module is accessed. It has the following methods:

new(): Create a new Tree::Radix object. The created tree will be empty. If called as a method from an already created tree, it will create a new tree that is a deep clone (i.e. the contained node objects are copied as well) of the given tree.
root([NEWROOT]): Simple accessor/mutator for an internal variable. With no arguments, returns the Tree::Radix::Node derivative representing the tree root. Given NEWROOT, mutates this slot of the object. This function is primarily for internal use.
search(KEYOBJ): Searches the tree for a match for KEYOBJ, returning the matching key object from the tree if it exists, or undef if it doesn't.
insert(KEYOBJ): Inserts a copy of KEYOBJ into the tree. Will call croak if there is a key collision (Radix trees require unique keys). Returns the key object as it exists in the tree.
delete(KEYOBJ): Deletes KEYOBJ from the tree, returning the deleted key object if it existed.
treewalk(HOW, SUB): Higher order method to walk easily walk the tree. HOW is a string, ``depth'' or ``breadth'' representing which way to walk the tree. SUB is a subroutine that should expect a single argument, a Tree::Radix::Node derivative.
treecheck(): Debugging method that does some simple sanity checks on the state of the tree structure.
treestring(): Returns a string representing the tree structure. Useful for debugging.

Internal Structure

All of the Tree::Radix classes are represented as blessed hashes.

The radix tree is internally represented by derivatives of the Tree::Radix::Node class. A given Tree::Radix's root hash member points to the root of the radix tree. All node objects have a parent hash member that points to the node's parent node, or is undef if the node is the tree root.

Tree::Radix::Node::Leaf classes represent tree leaves; each has a Tree::Radix::Key associated with its key hash member.

Tree::Radix::Node::Branch classes represent tree branches. In a binary radix tree, there are always two populated branches in an internal node; one way branching is not allowed.

The node objects are created during by the Tree::Radix::insert method, by using the new_leaf and new_branch methods of the key object passed to insert.

Tree::Radix::Node interface

This base class defines common behavior for all tree nodes. You should never subclass this yourself; subclass the ::Leaf and ::Branch classes instead.

new(): Constructor for this class. If you override the constructor in a subclass, be sure to call SUPER::new in your constructor.
parent([NEWPARENT]): Simple accessor/mutator for an internal variable. With no arguments, returns the Tree::Radix::Node derivative representing this node's parent (it's undefined if the node doesn't have a parent). Given NEWPARENT, mutates this slot of the object. This function is primarily for internal use.
isleaf(): Used to differentiate between branch and leaf objects. Returns 1 if the node object is a leaf.
string(): Return a string representation of the node. Used by treestring. The ::Branch and ::Leaf classes subclass this to provide more information.

Tree::Radix::Node::Branch interface

This object represents internal branches within the radix tree. Being a binary radix tree, there are two forks in a branch.

bit([NEWBIT]): Simple accessor/mutator for an internal variable. With no arguments, returns the integer representing the particular bit to test. Given NEWBIT, mutates this slot of the object. This function is primarily for internal use.
branches([NEWARRAYREF]): Simple accessor/mutator for an internal variable. With no arguments, returns the array reference that contains references to the forks of the given branch object. Given NEWARRAYREF, mutates this slot of the object. This function is primarily for internal use.
test_and_set_branches(KEYNODE, OTHERNODE): Test KEYNODE's key object against the branch's bit position. Assign KEYNODE to the branch indicated by the bit test, and OTHERNODE to the other branch.
replace_branch(OLDBRANCH, NEWBRANCH): Replace the fork matching OLDBRANCH by NEWBRANCH.

Tree::Radix::Node::Leaf interface

key([NEWKEY]): Simple accessor/mutator for an internal variable. With no arguments, returns the Tree::Radix::Key object stored at this leaf. Given NEWKEY, mutates this slot of the object. This function is primarily for internal use.

BUGS

The module doesn't currently support variable length keys. This would be useful in (for example) an OSI network routing table.

Making the radix tree support a radix other than two would take some slashing.

AUTHOR

Daniel Hagerty, <hag@ai.mit.edu>