Package org.opendaylight.lispflowmapping.inmemorydb.radixtrie

Class RadixTrie<T>

  • Type Parameters:
    T - Data type stored in each tree node
    public class RadixTrie<T>
extends java.lang.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 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

      • 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 java.util.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.