Go to the documentation of this file.
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);
247 std::vector<SuffixTreeNode *> ToVisit;
253 const unsigned MinLength = 2;
263 std::vector<SuffixTreeNode *> LeafChildren;
266 while (!ToVisit.empty()) {
269 LeafChildren.clear();
278 for (
auto &ChildPair : Curr->
Children) {
280 if (!ChildPair.second->isLeaf())
281 ToVisit.push_back(ChildPair.second);
285 else if (Length >= MinLength)
286 LeafChildren.push_back(ChildPair.second);
295 if (LeafChildren.size() >= 2) {
329 return !(*
this ==
Other);
337 ToVisit.push_back(
N);
350 #endif // LLVM_SUPPORT_SUFFIXTREE_H
RepeatedSubstringIterator operator++(int I)
unsigned Length
The length of the string.
This is an optimization pass for GlobalISel generic memory operations.
std::vector< unsigned > StartIndices
The start indices of each occurrence.
A BumpPtrAllocator that allows only elements of a specific type to be allocated.
A data structure for fast substring queries.
SuffixTree(const std::vector< unsigned > &Str)
Construct a suffix tree from a sequence of unsigned integers.
bool operator==(const RepeatedSubstringIterator &Other) const
const unsigned EmptyIdx
Represents an undefined index in the suffix tree.
unsigned * EndIdx
The end index of this node's substring in the main string.
Iterator for finding all repeated substrings in the suffix tree.
bool operator!=(const RepeatedSubstringIterator &Other) const
RepeatedSubstring & operator*()
Return the current repeated substring.
SuffixTreeNode(unsigned StartIdx, unsigned *EndIdx, SuffixTreeNode *Link)
Allocate memory in an ever growing pool, as if by bump-pointer.
A repeated substring in the tree.
RepeatedSubstringIterator iterator
SuffixTreeNode * Link
For internal nodes, a pointer to the internal node representing the same sequence with the first char...
llvm::ArrayRef< unsigned > Str
Each element is an integer representing an instruction in the module.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
unsigned SuffixIdx
For leaves, the start index of the suffix represented by this node.
llvm::DenseMap< unsigned, SuffixTreeNode * > Children
The children of this node.
A node in a suffix tree which represents a substring or suffix.
bool isRoot() const
Returns true if this node is the root of its owning SuffixTree.
unsigned StartIdx
The start index of this node's substring in the main string.
bool isLeaf() const
Returns true if this node is a leaf.
unsigned ConcatLen
The length of the string formed by concatenating the edge labels from the root to this node.
size_t size() const
Return the number of elements in the substring associated with this node.
RepeatedSubstringIterator(SuffixTreeNode *N)
RepeatedSubstringIterator & operator++()
Optional< std::vector< StOtherPiece > > Other