Line data Source code
1 : //===- llvm/ADT/EquivalenceClasses.h - Generic Equiv. Classes ---*- C++ -*-===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : //
10 : // Generic implementation of equivalence classes through the use Tarjan's
11 : // efficient union-find algorithm.
12 : //
13 : //===----------------------------------------------------------------------===//
14 :
15 : #ifndef LLVM_ADT_EQUIVALENCECLASSES_H
16 : #define LLVM_ADT_EQUIVALENCECLASSES_H
17 :
18 : #include <cassert>
19 : #include <cstddef>
20 : #include <cstdint>
21 : #include <iterator>
22 : #include <set>
23 :
24 : namespace llvm {
25 :
26 : /// EquivalenceClasses - This represents a collection of equivalence classes and
27 : /// supports three efficient operations: insert an element into a class of its
28 : /// own, union two classes, and find the class for a given element. In
29 : /// addition to these modification methods, it is possible to iterate over all
30 : /// of the equivalence classes and all of the elements in a class.
31 : ///
32 : /// This implementation is an efficient implementation that only stores one copy
33 : /// of the element being indexed per entry in the set, and allows any arbitrary
34 : /// type to be indexed (as long as it can be ordered with operator<).
35 : ///
36 : /// Here is a simple example using integers:
37 : ///
38 : /// \code
39 : /// EquivalenceClasses<int> EC;
40 : /// EC.unionSets(1, 2); // insert 1, 2 into the same set
41 : /// EC.insert(4); EC.insert(5); // insert 4, 5 into own sets
42 : /// EC.unionSets(5, 1); // merge the set for 1 with 5's set.
43 : ///
44 : /// for (EquivalenceClasses<int>::iterator I = EC.begin(), E = EC.end();
45 : /// I != E; ++I) { // Iterate over all of the equivalence sets.
46 : /// if (!I->isLeader()) continue; // Ignore non-leader sets.
47 : /// for (EquivalenceClasses<int>::member_iterator MI = EC.member_begin(I);
48 : /// MI != EC.member_end(); ++MI) // Loop over members in this set.
49 : /// cerr << *MI << " "; // Print member.
50 : /// cerr << "\n"; // Finish set.
51 : /// }
52 : /// \endcode
53 : ///
54 : /// This example prints:
55 : /// 4
56 : /// 5 1 2
57 : ///
58 : template <class ElemTy>
59 4358441 : class EquivalenceClasses {
60 : /// ECValue - The EquivalenceClasses data structure is just a set of these.
61 : /// Each of these represents a relation for a value. First it stores the
62 : /// value itself, which provides the ordering that the set queries. Next, it
63 : /// provides a "next pointer", which is used to enumerate all of the elements
64 : /// in the unioned set. Finally, it defines either a "end of list pointer" or
65 : /// "leader pointer" depending on whether the value itself is a leader. A
66 : /// "leader pointer" points to the node that is the leader for this element,
67 : /// if the node is not a leader. A "end of list pointer" points to the last
68 : /// node in the list of members of this list. Whether or not a node is a
69 : /// leader is determined by a bit stolen from one of the pointers.
70 : class ECValue {
71 : friend class EquivalenceClasses;
72 :
73 : mutable const ECValue *Leader, *Next;
74 : ElemTy Data;
75 :
76 : // ECValue ctor - Start out with EndOfList pointing to this node, Next is
77 : // Null, isLeader = true.
78 4319209 : ECValue(const ElemTy &Elt)
79 4292329 : : Leader(this), Next((ECValue*)(intptr_t)1), Data(Elt) {}
80 :
81 11224899 : const ECValue *getLeader() const {
82 22449798 : if (isLeader()) return this;
83 15937956 : if (Leader->isLeader()) return Leader;
84 : // Path compression.
85 2369421 : return Leader = Leader->getLeader();
86 : }
87 6101848 :
88 12203696 : const ECValue *getEndOfList() const {
89 9007712 : assert(isLeader() && "Cannot get the end of a list for a non-leader!");
90 0 : return Leader;
91 1133988 : }
92 :
93 5027983 : void setNext(const ECValue *NewNext) const {
94 10055966 : assert(getNext() == nullptr && "Already has a next pointer!");
95 6863792 : Next = (const ECValue*)((intptr_t)NewNext | (intptr_t)isLeader());
96 : }
97 1227806 :
98 : public:
99 0 : ECValue(const ECValue &RHS) : Leader(this), Next((ECValue*)(intptr_t)1),
100 0 : Data(RHS.Data) {
101 : // Only support copying of singleton nodes.
102 0 : assert(RHS.isLeader() && RHS.getNext() == nullptr && "Not a singleton!");
103 0 : }
104 0 :
105 206552 : bool operator<(const ECValue &UFN) const { return Data < UFN.Data; }
106 0 :
107 95336 : bool isLeader() const { return (intptr_t)Next & 1; }
108 20100 : const ElemTy &getData() const { return Data; }
109 :
110 0 : const ECValue *getNext() const {
111 30980 : return (ECValue*)((intptr_t)Next & ~(intptr_t)1);
112 : }
113 :
114 : template<typename T>
115 4260646 : bool operator<(const T &Val) const { return Data < Val; }
116 : };
117 :
118 : /// TheMapping - This implicitly provides a mapping from ElemTy values to the
119 0 : /// ECValues, it just keeps the key as part of the value.
120 0 : std::set<ECValue> TheMapping;
121 :
122 : public:
123 : EquivalenceClasses() = default;
124 : EquivalenceClasses(const EquivalenceClasses &RHS) {
125 29215256 : operator=(RHS);
126 : }
127 11129831 :
128 13495 : const EquivalenceClasses &operator=(const EquivalenceClasses &RHS) {
129 : TheMapping.clear();
130 13495 : for (iterator I = RHS.begin(), E = RHS.end(); I != E; ++I)
131 2130323 : if (I->isLeader()) {
132 : member_iterator MI = RHS.member_begin(I);
133 0 : member_iterator LeaderIt = member_begin(insert(*MI));
134 0 : for (++MI; MI != member_end(); ++MI)
135 0 : unionSets(LeaderIt, member_begin(insert(*MI)));
136 0 : }
137 13495 : return *this;
138 : }
139 :
140 : //===--------------------------------------------------------------------===//
141 : // Inspection methods
142 : //
143 :
144 : /// iterator* - Provides a way to iterate over all values in the set.
145 : using iterator = typename std::set<ECValue>::const_iterator;
146 :
147 : iterator begin() const { return TheMapping.begin(); }
148 : iterator end() const { return TheMapping.end(); }
149 :
150 : bool empty() const { return TheMapping.empty(); }
151 :
152 : /// member_* Iterate over the members of an equivalence class.
153 : class member_iterator;
154 0 : member_iterator member_begin(iterator I) const {
155 : // Only leaders provide anything to iterate over.
156 7793 : return member_iterator(I->isLeader() ? &*I : nullptr);
157 : }
158 0 : member_iterator member_end() const {
159 0 : return member_iterator(nullptr);
160 : }
161 :
162 : /// findValue - Return an iterator to the specified value. If it does not
163 : /// exist, end() is returned.
164 0 : iterator findValue(const ElemTy &V) const {
165 0 : return TheMapping.find(V);
166 : }
167 :
168 : /// getLeaderValue - Return the leader for the specified value that is in the
169 : /// set. It is an error to call this method for a value that is not yet in
170 : /// the set. For that, call getOrInsertLeaderValue(V).
171 0 : const ElemTy &getLeaderValue(const ElemTy &V) const {
172 22176 : member_iterator MI = findLeader(V);
173 : assert(MI != member_end() && "Value is not in the set!");
174 22176 : return *MI;
175 : }
176 :
177 : /// getOrInsertLeaderValue - Return the leader for the specified value that is
178 : /// in the set. If the member is not in the set, it is inserted, then
179 : /// returned.
180 0 : const ElemTy &getOrInsertLeaderValue(const ElemTy &V) {
181 0 : member_iterator MI = findLeader(insert(V));
182 : assert(MI != member_end() && "Value is not in the set!");
183 0 : return *MI;
184 0 : }
185 0 :
186 : /// getNumClasses - Return the number of equivalence classes in this set.
187 0 : /// Note that this is a linear time operation.
188 0 : unsigned getNumClasses() const {
189 : unsigned NC = 0;
190 0 : for (iterator I = begin(), E = end(); I != E; ++I)
191 0 : if (I->isLeader()) ++NC;
192 : return NC;
193 : }
194 :
195 : //===--------------------------------------------------------------------===//
196 : // Mutation methods
197 :
198 : /// insert - Insert a new value into the union/find set, ignoring the request
199 : /// if the value already exists.
200 0 : iterator insert(const ElemTy &Data) {
201 43488 : return TheMapping.insert(ECValue(Data)).first;
202 : }
203 :
204 : /// findLeader - Given a value in the set, return a member iterator for the
205 : /// equivalence class it is in. This does the path-compression part that
206 : /// makes union-find "union findy". This returns an end iterator if the value
207 : /// is not in the equivalence class.
208 : member_iterator findLeader(iterator I) const {
209 30194 : if (I == TheMapping.end()) return member_end();
210 30194 : return member_iterator(I->getLeader());
211 : }
212 0 : member_iterator findLeader(const ElemTy &V) const {
213 0 : return findLeader(TheMapping.find(V));
214 : }
215 :
216 : /// union - Merge the two equivalence sets for the specified values, inserting
217 : /// them if they do not already exist in the equivalence set.
218 15075 : member_iterator unionSets(const ElemTy &V1, const ElemTy &V2) {
219 11626 : iterator V1I = insert(V1), V2I = insert(V2);
220 15075 : return unionSets(findLeader(V1I), findLeader(V2I));
221 : }
222 0 : member_iterator unionSets(member_iterator L1, member_iterator L2) {
223 : assert(L1 != member_end() && L2 != member_end() && "Illegal inputs!");
224 15093 : if (L1 == L2) return L1; // Unifying the same two sets, noop.
225 :
226 : // Otherwise, this is a real union operation. Set the end of the L1 list to
227 : // point to the L2 leader node.
228 : const ECValue &L1LV = *L1.Node, &L2LV = *L2.Node;
229 14109 : L1LV.getEndOfList()->setNext(&L2LV);
230 :
231 : // Update L1LV's end of list pointer.
232 14109 : L1LV.Leader = L2LV.getEndOfList();
233 2130323 :
234 : // Clear L2's leader flag:
235 28218 : L2LV.Next = L2LV.getNext();
236 0 :
237 : // L2's leader is now L1.
238 14109 : L2LV.Leader = &L1LV;
239 0 : return L1;
240 : }
241 :
242 : // isEquivalent - Return true if V1 is equivalent to V2. This can happen if
243 : // V1 is equal to V2 or if they belong to one equivalence class.
244 0 : bool isEquivalent(const ElemTy &V1, const ElemTy &V2) const {
245 : // Fast path: any element is equivalent to itself.
246 0 : if (V1 == V2)
247 4260646 : return true;
248 4260646 : auto It = findLeader(V1);
249 0 : return It != member_end() && It == findLeader(V2);
250 0 : }
251 0 :
252 : class member_iterator : public std::iterator<std::forward_iterator_tag,
253 0 : const ElemTy, ptrdiff_t> {
254 0 : friend class EquivalenceClasses;
255 :
256 0 : using super = std::iterator<std::forward_iterator_tag,
257 0 : const ElemTy, ptrdiff_t>;
258 :
259 : const ECValue *Node;
260 :
261 : public:
262 2130323 : using size_type = size_t;
263 2130323 : using pointer = typename super::pointer;
264 2130323 : using reference = typename super::reference;
265 :
266 832311 : explicit member_iterator() = default;
267 832311 : explicit member_iterator(const ECValue *N) : Node(N) {}
268 832311 :
269 0 : reference operator*() const {
270 1298012 : assert(Node != nullptr && "Dereferencing end()!");
271 1298012 : return Node->getData();
272 1298012 : }
273 : pointer operator->() const { return &operator*(); }
274 0 :
275 : member_iterator &operator++() {
276 2130323 : assert(Node != nullptr && "++'d off the end of the list!");
277 16871 : Node = Node->getNext();
278 : return *this;
279 : }
280 :
281 2130323 : member_iterator operator++(int) { // postincrement operators.
282 0 : member_iterator tmp = *this;
283 : ++*this;
284 2130323 : return tmp;
285 : }
286 :
287 4260646 : bool operator==(const member_iterator &RHS) const {
288 0 : return Node == RHS.Node;
289 : }
290 2130323 : bool operator!=(const member_iterator &RHS) const {
291 0 : return Node != RHS.Node;
292 : }
293 0 : };
294 : };
295 0 :
296 : } // end namespace llvm
297 :
298 : #endif // LLVM_ADT_EQUIVALENCECLASSES_H
|
