25 unsigned SuffixesToAdd = 0;
30 for (
unsigned PfxEndIdx = 0, End =
Str.
size(); PfxEndIdx < End; PfxEndIdx++) {
32 LeafEndIdx = PfxEndIdx;
33 SuffixesToAdd = extend(PfxEndIdx, SuffixesToAdd);
37 assert(Root &&
"Root node can't be nullptr!");
42 unsigned StartIdx,
unsigned Edge) {
44 assert(StartIdx <= LeafEndIdx &&
"String can't start after it ends!");
55 unsigned EndIdx,
unsigned Edge) {
57 assert(StartIdx <= EndIdx &&
"String can't start after it ends!");
59 "Non-root internal nodes must have parents!");
61 unsigned *
E =
new (InternalEndIdxAllocator)
unsigned(EndIdx);
70void SuffixTree::setSuffixIndices() {
79 unsigned CurrNodeLen = 0;
80 ToVisit.
push_back({CurrNode, CurrNodeLen});
81 while (!ToVisit.
empty()) {
82 std::tie(CurrNode, CurrNodeLen) = ToVisit.
back();
85 for (
auto &ChildPair : CurrNode->
Children) {
86 assert(ChildPair.second &&
"Node had a null child!");
88 {ChildPair.second, CurrNodeLen + ChildPair.second->size()});
97unsigned SuffixTree::extend(
unsigned EndIdx,
unsigned SuffixesToAdd) {
100 while (SuffixesToAdd > 0) {
103 if (Active.Len == 0) {
108 assert(Active.Idx <= EndIdx &&
"Start index can't be after end index!");
111 unsigned FirstChar =
Str[Active.Idx];
114 if (Active.Node->Children.count(FirstChar) == 0) {
116 insertLeaf(*Active.Node, EndIdx, FirstChar);
121 NeedsLink->
Link = Active.Node;
129 unsigned SubstringLen = NextNode->
size();
133 if (Active.Len >= SubstringLen) {
136 Active.Idx += SubstringLen;
137 Active.Len -= SubstringLen;
138 Active.Node = NextNode;
144 unsigned LastChar =
Str[EndIdx];
147 if (
Str[NextNode->
StartIdx + Active.Len] == LastChar) {
151 if (NeedsLink && !Active.Node->isRoot()) {
152 NeedsLink->
Link = Active.Node;
175 insertInternalNode(Active.Node, NextNode->
StartIdx,
176 NextNode->
StartIdx + Active.Len - 1, FirstChar);
180 insertLeaf(*SplitNode, EndIdx, LastChar);
189 NeedsLink->
Link = SplitNode;
191 NeedsLink = SplitNode;
198 if (Active.Node->isRoot()) {
199 if (Active.Len > 0) {
201 Active.Idx = EndIdx - SuffixesToAdd + 1;
205 Active.Node = Active.Node->Link;
209 return SuffixesToAdd;
This file defines the BumpPtrAllocator interface.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
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.
const unsigned EmptyIdx
Represents an undefined index in the suffix tree.
A node in a suffix tree which represents a substring or suffix.
unsigned SuffixIdx
For leaves, the start index of the suffix represented by this node.
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.