org.opendaylight.lispflowmapping.inmemorydb.radixtrie

Class RadixTrie<T>

java.lang.Object

org.opendaylight.lispflowmapping.inmemorydb.radixtrie.RadixTrie<T>

Type Parameters:

T - Data type stored in each tree node

public class RadixTrie<T>
extends Object

Radix trie/tree (also known as Patricia tree) implementation. Supports CRD operations for generic, big endian (network byte order) prefixes. It can do exact and longest prefix matching, post order iteration over the entries in the tree and can lookup widest negative prefixes (i.e., shortest overlapping prefix not registered in the tree).

Author:

Florin Coras

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
class	RadixTrie.TrieNode Trie node definition.

Constructor Summary

Constructors

Constructor and Description
RadixTrie(int bits) RadixTrie constructor.
RadixTrie(int bits, boolean rootZero) Radix trie constructors.

Method Summary

Modifier and Type	Method and Description
int	getMaxbits()
RadixTrie.TrieNode	getRoot()
long	getSize()
RadixTrie.TrieNode	insert(byte[] prefix, int preflen, T data) Insert prefix-data tuple into radix trie.
RadixTrie.TrieNode	lookupBest(byte[] prefix, int preflen) Longest prefix match of prefix/preflen.
RadixTrie.TrieNode	lookupCoveringLessSpecific(byte[] prefix, int preflen) Look up the covering prefix for the argument, but exclude the argument itself, so the result is always less specific than the lookup key.
RadixTrie.TrieNode	lookupExact(byte[] prefix, int preflen) Exact prefix match of prefix/preflen.
RadixTrie.TrieNode	lookupParent(byte[] prefix, int preflen) Given an EID, lookup the longest prefix match, then return its parent node.
RadixTrie.TrieNode	lookupSibling(byte[] prefix, int preflen) Given an EID, lookup the longest prefix match, then return its sibling node.
Set<RadixTrie.TrieNode>	lookupSubtree(byte[] prefix, int preflen) Return the subtree for a prefix, including the prefix itself if present, excluding virtual nodes.
RadixTrie.TrieNode	lookupVirtualParentSibling(byte[] prefix, int preflen) Given an EID, lookup the longest prefix match, then return its direct parent's sibling node, if the parent is a virtual node.
RadixTrie.TrieNode	lookupWidestNegative(byte[] prefix, int preflen) Lookup widest negative (i.e., overlapping but not present in trie) prefix for given prefix and prefix length.
void	remove(byte[] prefix, int preflen) Remove prefix from radix trie.
void	removeAll() Remove all entries in the trie.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

RadixTrie

public RadixTrie(int bits)

RadixTrie constructor.

Parameters:

bits - Maximum prefix length supported.

RadixTrie

public RadixTrie(int bits,
                 boolean rootZero)

Radix trie constructors.

Parameters:

bits - Maximum prefix length supported

rootZero - Flag that decides if 0/0 should be inserted as a non-prefix root node or not

Method Detail

getRoot

public RadixTrie.TrieNode getRoot()

getMaxbits

public int getMaxbits()

getSize

public long getSize()

insert

public RadixTrie.TrieNode insert(byte[] prefix,
                                 int preflen,
                                 T data)

Insert prefix-data tuple into radix trie.

Parameters:

prefix - Big endian (network order) byte array representation of the prefix

preflen - Prefix length

data - Data to be stored in the tree

Returns:

Newly inserted TrieNode

lookupBest

public RadixTrie.TrieNode lookupBest(byte[] prefix,
                                     int preflen)

Longest prefix match of prefix/preflen.

Parameters:

prefix - Big endian byte array representation of the prefix to be looked up.

preflen - Prefix length

Returns:

Node with longest prefix match or null if nothing is found.

lookupCoveringLessSpecific

public RadixTrie.TrieNode lookupCoveringLessSpecific(byte[] prefix,
                                                     int preflen)

Look up the covering prefix for the argument, but exclude the argument itself, so the result is always less specific than the lookup key.

Parameters:

prefix - Big endian byte array representation of the prefix argument

preflen - Prefix length

Returns:

Covering node

lookupParent

public RadixTrie.TrieNode lookupParent(byte[] prefix,
                                       int preflen)

Given an EID, lookup the longest prefix match, then return its parent node.

Parameters:

prefix - Prefix looked up.

preflen - Prefix length.

Returns:

Parent node of longest prefix match or null if nothing is found.

lookupSibling

public RadixTrie.TrieNode lookupSibling(byte[] prefix,
                                        int preflen)

Given an EID, lookup the longest prefix match, then return its sibling node.

Parameters:

prefix - Prefix looked up.

preflen - Prefix length.

Returns:

Sibling node of longest prefix match or null if nothing is found.

lookupVirtualParentSibling

public RadixTrie.TrieNode lookupVirtualParentSibling(byte[] prefix,
                                                     int preflen)

Given an EID, lookup the longest prefix match, then return its direct parent's sibling node, if the parent is a virtual node.

Parameters:

prefix - Prefix looked up.

preflen - Prefix length.

Returns:

The longest prefix match node's virtual parent's sibling or null if nothing is found.

lookupWidestNegative

public RadixTrie.TrieNode lookupWidestNegative(byte[] prefix,
                                               int preflen)

Lookup widest negative (i.e., overlapping but not present in trie) prefix for given prefix and prefix length.

Parameters:

prefix - Prefix looked up.

preflen - Prefix length.

Returns:

Node containing the widest negative prefix.

lookupExact

public RadixTrie.TrieNode lookupExact(byte[] prefix,
                                      int preflen)

Exact prefix match of prefix/preflen.

Parameters:

prefix - Big endian byte array representation of the prefix to be looked up.

preflen - Prefix length

Returns:

Node with exact prefix match or null

lookupSubtree

public Set<RadixTrie.TrieNode> lookupSubtree(byte[] prefix,
                                             int preflen)

Return the subtree for a prefix, including the prefix itself if present, excluding virtual nodes.

Parameters:

prefix - Big endian byte array representation of the prefix to be looked up.

preflen - Prefix length

Returns:

Subtree from the prefix

remove

public void remove(byte[] prefix,
                   int preflen)

Remove prefix from radix trie.

Parameters:

prefix - Big endian byte array representation of the prefix to be removed.

preflen - Prefix length.

removeAll

public void removeAll()

Remove all entries in the trie.