Package ghidra.util.search.trie

Class ByteTrie<T>

  • Type Parameters:
    T - the item storage type
    All Implemented Interfaces:
    ByteTrieIfc<T>
    Direct Known Subclasses:
    CaseInsensitiveByteTrie
    public class ByteTrie<T>
extends java.lang.Object
implements ByteTrieIfc<T>
    ByteTrie is a byte-based trie specifically designed to implement the Aho-Corasick string search algorithm.

    • Constructor Summary

      Constructors 
      Constructor Description
      ByteTrie()  

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      boolean add​(byte[] value, T item)
      Adds a byte sequence to the trie, with corresponding user item.
      ByteTrieNodeIfc<T> find​(byte[] value)
      Finds a byte sequence in the trie and returns a node interface object for it, or null if not present.
      protected ByteTrieNode<T> generateNode​(byte id, ByteTrieNode<T> parent, int length)  
      void inorder​(TaskMonitor monitor, Op<T> op)
      Visits all the nodes in the trie such that the visitation order is properly ordered (even though the actual algorithm below is a PREORDER traversal).
      boolean isEmpty()
      Returns if the trie is empty.
      int numberOfNodes()
      Returns the number of nodes in the trie; this is essentially equal to the sum of the number of characters in all byte sequences present in the trie, minus their shared prefixes.
      java.util.List<SearchResult<java.lang.Integer,​T>> search​(byte[] text, TaskMonitor monitor)
      Search an array of bytes using the Aho-Corasick multiple string trie search algorithm.
      java.util.List<SearchResult<Address,​T>> search​(Memory memory, AddressSetView view, TaskMonitor monitor)
      Search memory using the Aho-Corasick multiple string trie search algorithm.
      int size()
      Returns the number of byte sequences in the trie.

      • Methods inherited from class java.lang.Object

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

    • Constructor Detail

      • ByteTrie

        public ByteTrie()

    • Method Detail

      • isEmpty

        public boolean isEmpty()
        Returns if the trie is empty.
        Specified by:
        isEmpty in interface ByteTrieIfc<T>
        Returns:
        if the trie is empty

      • size

        public int size()
        Returns the number of byte sequences in the trie.
        Specified by:
        size in interface ByteTrieIfc<T>
        Returns:
        the number of byte sequences in the trie

      • numberOfNodes

        public int numberOfNodes()
        Returns the number of nodes in the trie; this is essentially equal to the sum of the number of characters in all byte sequences present in the trie, minus their shared prefixes.
        Specified by:
        numberOfNodes in interface ByteTrieIfc<T>
        Returns:
        the number of nodes in the trie

      • add

        public boolean add​(byte[] value,
                   T item)
        Adds a byte sequence to the trie, with corresponding user item. Returns if the add took place, or if this add was essentially a replacement of a previously present value (previous user item is lost forever).
        Specified by:
        add in interface ByteTrieIfc<T>
        Parameters:
        value - the byte sequence to insert into the trie
        item - a user item to store in that location
        Returns:
        whether the add took place

      • find

        public ByteTrieNodeIfc<T> find​(byte[] value)
        Finds a byte sequence in the trie and returns a node interface object for it, or null if not present.
        Specified by:
        find in interface ByteTrieIfc<T>
        Parameters:
        value - the byte sequence sought
        Returns:
        the node interface if present, or null

      • inorder

        public void inorder​(TaskMonitor monitor,
                    Op<T> op)
             throws CancelledException
        Visits all the nodes in the trie such that the visitation order is properly ordered (even though the actual algorithm below is a PREORDER traversal). The client is responsible for not performing actions on non-terminal nodes as necessary.
        Specified by:
        inorder in interface ByteTrieIfc<T>
        Parameters:
        monitor - a task monitor
        op - the operation to perform
        Throws:
        CancelledException - if the user cancels

      • search

        public java.util.List<SearchResult<java.lang.Integer,​T>> search​(byte[] text,
                                                                      TaskMonitor monitor)
                                                               throws CancelledException
        Search an array of bytes using the Aho-Corasick multiple string trie search algorithm.
        Specified by:
        search in interface ByteTrieIfc<T>
        Parameters:
        text - the bytes to search
        monitor - a task monitor
        Returns:
        a list of search results
        Throws:
        CancelledException