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 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.
-
-
-
Method Detail
-
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 interfaceByteTrieIfc<T>
- Returns:
- if the trie is empty
-
size
public int size()
Returns the number of byte sequences in the trie.- Specified by:
size
in interfaceByteTrieIfc<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 interfaceByteTrieIfc<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 interfaceByteTrieIfc<T>
- Parameters:
value
- the byte sequence to insert into the trieitem
- 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 interfaceByteTrieIfc<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 interfaceByteTrieIfc<T>
- Parameters:
monitor
- a task monitorop
- 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 interfaceByteTrieIfc<T>
- Parameters:
text
- the bytes to searchmonitor
- a task monitor- Returns:
- a list of search results
- Throws:
CancelledException
-
search
public java.util.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 interfaceByteTrieIfc<T>
- Parameters:
memory
- the program memory managerview
- the address set view to searchmonitor
- a task monitor- Returns:
- a list of search results
- Throws:
MemoryAccessException
- if bytes are not availableCancelledException
- if the user cancels
-
-