Package ghidra.util.search.trie

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 Summary

    Constructors
    Constructor
    Description
    ByteTrie()
     

  • Method Summary

    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.
    List<SearchResult<Integer,T>>
    search(byte[] text, TaskMonitor monitor)
    Search an array of bytes using the Aho-Corasick multiple string trie search algorithm.
    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 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