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