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