Package 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

  • Constructor Details

    • 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 Details

    • getRoot

      public RadixTrie<T>.TrieNode getRoot()

    • getMaxbits

      public int getMaxbits()

    • getSize

      public long getSize()

    • insert

      public RadixTrie<T>.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<T>.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<T>.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<T>.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<T>.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<T>.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<T>.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<T>.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<T>.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.