12#ifndef LLVM_SUPPORT_SUFFIXTREE_H
13#define LLVM_SUPPORT_SUFFIXTREE_H
171 unsigned LeafEndIdx = -1;
209 unsigned EndIdx,
unsigned Edge);
213 void setSuffixIndices();
229 unsigned extend(
unsigned EndIdx,
unsigned SuffixesToAdd);
253 const unsigned MinLength = 2;
266 while (!ToVisit.
empty()) {
269 LeafChildren.
clear();
278 for (
auto &ChildPair : Curr->
Children) {
280 if (!ChildPair.second->isLeaf())
285 else if (
Length >= MinLength)
286 LeafChildren.
push_back(ChildPair.second);
295 if (LeafChildren.
size() >= 2) {
329 return !(*
this ==
Other);
This file defines the BumpPtrAllocator interface.
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
This file defines the DenseMap class.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Allocate memory in an ever growing pool, as if by bump-pointer.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
A BumpPtrAllocator that allows only elements of a specific type to be allocated.
A data structure for fast substring queries.
ArrayRef< unsigned > Str
Each element is an integer representing an instruction in the module.
RepeatedSubstringIterator iterator
This is an optimization pass for GlobalISel generic memory operations.
const unsigned EmptyIdx
Represents an undefined index in the suffix tree.
A node in a suffix tree which represents a substring or suffix.
unsigned * EndIdx
The end index of this node's substring in the main string.
bool isLeaf() const
Returns true if this node is a leaf.
unsigned SuffixIdx
For leaves, the start index of the suffix represented by this node.
SuffixTreeNode(unsigned StartIdx, unsigned *EndIdx, SuffixTreeNode *Link)
size_t size() const
Return the number of elements in the substring associated with this node.
unsigned ConcatLen
The length of the string formed by concatenating the edge labels from the root to this node.
SuffixTreeNode * Link
For internal nodes, a pointer to the internal node representing the same sequence with the first char...
DenseMap< unsigned, SuffixTreeNode * > Children
The children of this node.
unsigned StartIdx
The start index of this node's substring in the main string.
bool isRoot() const
Returns true if this node is the root of its owning SuffixTree.
Iterator for finding all repeated substrings in the suffix tree.
RepeatedSubstringIterator operator++(int I)
RepeatedSubstringIterator(SuffixTreeNode *N)
bool operator!=(const RepeatedSubstringIterator &Other) const
RepeatedSubstring & operator*()
Return the current repeated substring.
bool operator==(const RepeatedSubstringIterator &Other) const
RepeatedSubstringIterator & operator++()
A repeated substring in the tree.
SmallVector< unsigned > StartIndices
The start indices of each occurrence.
unsigned Length
The length of the string.