22 assert(
N &&
"Got a null node?");
23 if (
auto *Internal = dyn_cast<SuffixTreeInternalNode>(
N))
24 if (Internal->isRoot())
26 return N->getEndIdx() -
N->getStartIdx() + 1;
35 unsigned SuffixesToAdd = 0;
40 for (
unsigned PfxEndIdx = 0,
End =
Str.
size(); PfxEndIdx <
End; PfxEndIdx++) {
42 LeafEndIdx = PfxEndIdx;
43 SuffixesToAdd = extend(PfxEndIdx, SuffixesToAdd);
47 assert(Root &&
"Root node can't be nullptr!");
52 unsigned StartIdx,
unsigned Edge) {
53 assert(StartIdx <= LeafEndIdx &&
"String can't start after it ends!");
54 auto *
N =
new (LeafNodeAllocator.Allocate())
62 unsigned StartIdx,
unsigned EndIdx,
64 assert(StartIdx <= EndIdx &&
"String can't start after it ends!");
66 "Non-root internal nodes must have parents!");
67 auto *
N =
new (InternalNodeAllocator.Allocate())
79void SuffixTree::setSuffixIndices() {
88 unsigned CurrNodeLen = 0;
89 ToVisit.
push_back({CurrNode, CurrNodeLen});
90 while (!ToVisit.
empty()) {
91 std::tie(CurrNode, CurrNodeLen) = ToVisit.
back();
95 if (
auto *InternalNode = dyn_cast<SuffixTreeInternalNode>(CurrNode))
96 for (
auto &ChildPair : InternalNode->Children) {
97 assert(ChildPair.second &&
"Node had a null child!");
103 if (
auto *LeafNode = dyn_cast<SuffixTreeLeafNode>(CurrNode))
104 LeafNode->setSuffixIdx(
Str.
size() - CurrNodeLen);
108unsigned SuffixTree::extend(
unsigned EndIdx,
unsigned SuffixesToAdd) {
111 while (SuffixesToAdd > 0) {
114 if (Active.Len == 0) {
119 assert(Active.Idx <= EndIdx &&
"Start index can't be after end index!");
122 unsigned FirstChar =
Str[Active.Idx];
125 if (Active.Node->Children.count(FirstChar) == 0) {
127 insertLeaf(*Active.Node, EndIdx, FirstChar);
132 NeedsLink->
setLink(Active.Node);
144 if (Active.Len >= SubstringLen) {
147 assert(isa<SuffixTreeInternalNode>(NextNode) &&
148 "Expected an internal node?");
149 Active.Idx += SubstringLen;
150 Active.Len -= SubstringLen;
151 Active.Node = cast<SuffixTreeInternalNode>(NextNode);
157 unsigned LastChar =
Str[EndIdx];
164 if (NeedsLink && !Active.Node->isRoot()) {
165 NeedsLink->
setLink(Active.Node);
189 NextNode->
getStartIdx() + Active.Len - 1, FirstChar);
193 insertLeaf(*SplitNode, EndIdx, LastChar);
204 NeedsLink = SplitNode;
211 if (Active.Node->isRoot()) {
212 if (Active.Len > 0) {
214 Active.Idx = EndIdx - SuffixesToAdd + 1;
218 Active.Node = Active.Node->getLink();
222 return SuffixesToAdd;
225void SuffixTree::RepeatedSubstringIterator::advance() {
228 RS = RepeatedSubstring();
235 while (!InternalNodesToVisit.empty()) {
236 RepeatedSubstringStarts.
clear();
237 auto *Curr = InternalNodesToVisit.back();
238 InternalNodesToVisit.pop_back();
242 unsigned Length = Curr->getConcatLen();
247 for (
auto &ChildPair : Curr->Children) {
249 if (
auto *InternalChild =
250 dyn_cast<SuffixTreeInternalNode>(ChildPair.second)) {
251 InternalNodesToVisit.push_back(InternalChild);
259 auto *Leaf = cast<SuffixTreeLeafNode>(ChildPair.second);
260 RepeatedSubstringStarts.
push_back(Leaf->getSuffixIdx());
269 if (RepeatedSubstringStarts.
size() < 2)
275 for (
unsigned StartIdx : RepeatedSubstringStarts)
This file defines the BumpPtrAllocator interface.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static size_t numElementsInSubstring(const SuffixTreeNode *N)
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
size_t size() const
size - Get the array size.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
SuffixTree(const ArrayRef< unsigned > &Str)
Construct a suffix tree from a sequence of unsigned integers.
ArrayRef< unsigned > Str
Each element is an integer representing an instruction in the module.
This is an optimization pass for GlobalISel generic memory operations.
DenseMap< unsigned, SuffixTreeNode * > Children
The children of this node.
void setLink(SuffixTreeInternalNode *L)
Sets Link to L. Assumes L is not null.
A node in a suffix tree which represents a substring or suffix.
void incrementStartIdx(unsigned Inc)
Advance this node's StartIdx by Inc.
void setConcatLen(unsigned Len)
Set the length of the string from the root to this node to Len.
static const unsigned EmptyIdx
Represents an undefined index in the suffix tree.
unsigned getStartIdx() const
SmallVector< unsigned > StartIndices
The start indices of each occurrence.
unsigned Length
The length of the string.