Class ByteTrie<T>

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

  • Constructor Details

    • ByteTrie

      public ByteTrie()

  • Method Details

    • generateNode

      protected ByteTrieNode<T> generateNode(byte id, ByteTrieNode<T> parent, int length)

    • 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 List<SearchResult<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

    • search

      public List<SearchResult<Address,T>> search(Memory memory, AddressSetView view, TaskMonitor monitor) throws MemoryAccessException, CancelledException
      Search memory using the Aho-Corasick multiple string trie search algorithm.
      Specified by:
      search in interface ByteTrieIfc<T>
      Parameters:
      memory - the program memory manager
      view - the address set view to search
      monitor - a task monitor
      Returns:
      a list of search results
      Throws:
      MemoryAccessException - if bytes are not available
      CancelledException - if the user cancels