LLVM: include/llvm/Support/SuffixTree.h Source File (original) (raw)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32#ifndef LLVM_SUPPORT_SUFFIXTREE_H
33#define LLVM_SUPPORT_SUFFIXTREE_H
34
39
40namespace llvm {
42public:
43
45
46
48
49
57
58private:
59
61
63
64
65
66
67
69
70
72
73
74
75 struct ActiveState {
76
78
79
81
82
83 unsigned Len = 0;
84 };
85
86
87
88 ActiveState Active;
89
90
91
92
93
94
95
96
98 unsigned Edge);
99
100
101
102
103
104
105
106
107
109 unsigned StartIdx, unsigned EndIdx,
110 unsigned Edge);
111
112
113
114
116
117
118
119 void setSuffixIndices();
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135 unsigned extend(unsigned EndIdx, unsigned SuffixesToAdd);
136
137
138
139
140
141 std::vector<SuffixTreeLeafNode *> LeafNodes;
142
143
144
145
146
147
148 void setLeafNodes();
149
150public:
151
152
153
154
155
158
159
161 private:
162
164
165
167
168
170
171
172
173
174
175 const unsigned MinLength = 2;
176
177
178 const std::vector<SuffixTreeLeafNode *> &LeafNodes;
179
180
181 bool OutlinerLeafDescendants = !LeafNodes.empty();
182
183
185
186 public:
187
189
191 advance();
192 return *this;
193 }
194
197 advance();
198 return It;
199 }
200
202 return N == Other.N;
203 }
205 return !(*this == Other);
206 }
207
210 const std::vector<SuffixTreeLeafNode *> &LeafNodes = {})
211 : N(N), LeafNodes(LeafNodes) {
212
213 if ()
214 return;
215
216
218 advance();
219 }
220 };
221
225};
226
227}
228
229#endif
This file defines the BumpPtrAllocator interface.
static cl::opt< bool > OutlinerLeafDescendants("outliner-leaf-descendants", cl::init(true), cl::Hidden, cl::desc("Consider all leaf descendants of internal nodes of the suffix " "tree as candidates for outlining (if false, only leaf children " "are considered)"))
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
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.
LLVM_ABI SuffixTree(const ArrayRef< unsigned > &Str, bool OutlinerLeafDescendants=false)
Construct a suffix tree from a sequence of unsigned integers.
iterator begin()
Definition SuffixTree.h:223
iterator end()
Definition SuffixTree.h:224
ArrayRef< unsigned > Str
Each element is an integer representing an instruction in the module.
Definition SuffixTree.h:44
RepeatedSubstringIterator iterator
Definition SuffixTree.h:222
bool OutlinerLeafDescendants
Whether to consider leaf descendants or only leaf children.
Definition SuffixTree.h:47
This is an optimization pass for GlobalISel generic memory operations.
A node in a suffix tree which represents a substring or suffix.
static const unsigned EmptyIdx
Represents an undefined index in the suffix tree.
Iterator for finding all repeated substrings in the suffix tree.
Definition SuffixTree.h:160
RepeatedSubstringIterator operator++(int I)
Definition SuffixTree.h:195
RepeatedSubstringIterator(SuffixTreeInternalNode *N, const std::vector< SuffixTreeLeafNode * > &LeafNodes={})
Definition SuffixTree.h:208
bool operator!=(const RepeatedSubstringIterator &Other) const
Definition SuffixTree.h:204
RepeatedSubstring & operator*()
Return the current repeated substring.
Definition SuffixTree.h:188
bool operator==(const RepeatedSubstringIterator &Other) const
Definition SuffixTree.h:201
RepeatedSubstringIterator & operator++()
Definition SuffixTree.h:190
A repeated substring in the tree.
Definition SuffixTree.h:50
SmallVector< unsigned > StartIndices
The start indices of each occurrence.
Definition SuffixTree.h:55
unsigned Length
The length of the string.
Definition SuffixTree.h:52