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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
|
#if !defined(__UNIONFIND_H)
#define __UNIONFIND_H
#include <vector>
#include <atomic>
#include <iostream>
namespace qflow {
/**
* Lock-free parallel disjoint set data structure (aka UNION-FIND)
* with path compression and union by rank
*
* Supports concurrent find(), same() and unite() calls as described
* in the paper
*
* "Wait-free Parallel Algorithms for the Union-Find Problem"
* by Richard J. Anderson and Heather Woll
*
* In addition, this class supports optimistic locking (try_lock/unlock)
* of disjoint sets and a combined unite+unlock operation.
*
* \author Wenzel Jakob
*/
class DisjointSets {
public:
DisjointSets(uint32_t size) : mData(size) {
for (uint32_t i = 0; i<size; ++i)
mData[i] = (uint32_t)i;
}
uint32_t find(uint32_t id) const {
while (id != parent(id)) {
uint64_t value = mData[id];
uint32_t new_parent = parent((uint32_t)value);
uint64_t new_value =
(value & 0xFFFFFFFF00000000ULL) | new_parent;
/* Try to update parent (may fail, that's ok) */
if (value != new_value)
mData[id].compare_exchange_weak(value, new_value);
id = new_parent;
}
return id;
}
bool same(uint32_t id1, uint32_t id2) const {
for (;;) {
id1 = find(id1);
id2 = find(id2);
if (id1 == id2)
return true;
if (parent(id1) == id1)
return false;
}
}
uint32_t unite(uint32_t id1, uint32_t id2) {
for (;;) {
id1 = find(id1);
id2 = find(id2);
if (id1 == id2)
return id1;
uint32_t r1 = rank(id1), r2 = rank(id2);
if (r1 > r2 || (r1 == r2 && id1 < id2)) {
std::swap(r1, r2);
std::swap(id1, id2);
}
uint64_t oldEntry = ((uint64_t)r1 << 32) | id1;
uint64_t newEntry = ((uint64_t)r1 << 32) | id2;
if (!mData[id1].compare_exchange_strong(oldEntry, newEntry))
continue;
if (r1 == r2) {
oldEntry = ((uint64_t)r2 << 32) | id2;
newEntry = ((uint64_t)(r2 + 1) << 32) | id2;
/* Try to update the rank (may fail, that's ok) */
mData[id2].compare_exchange_weak(oldEntry, newEntry);
}
break;
}
return id2;
}
/**
* Try to lock the a disjoint union identified by one
* of its elements (this can occasionally fail when there
* are concurrent operations). The parameter 'id' will be
* updated to store the current representative ID of the
* union
*/
bool try_lock(uint32_t &id) {
const uint64_t lock_flag = 1ULL << 63;
id = find(id);
uint64_t value = mData[id];
if ((value & lock_flag) || (uint32_t)value != id)
return false;
// On IA32/x64, a PAUSE instruction is recommended for CAS busy loops
#if defined(__i386__) || defined(__amd64__)
__asm__ __volatile__("pause\n");
#endif
return mData[id].compare_exchange_strong(value, value | lock_flag);
}
void unlock(uint32_t id) {
const uint64_t lock_flag = 1ULL << 63;
mData[id] &= ~lock_flag;
}
/**
* Return the representative index of the set that results from merging
* locked disjoint sets 'id1' and 'id2'
*/
uint32_t unite_index_locked(uint32_t id1, uint32_t id2) const {
uint32_t r1 = rank(id1), r2 = rank(id2);
return (r1 > r2 || (r1 == r2 && id1 < id2)) ? id1 : id2;
}
/**
* Atomically unite two locked disjoint sets and unlock them. Assumes
* that here are no other concurrent unite() involving the same sets
*/
uint32_t unite_unlock(uint32_t id1, uint32_t id2) {
uint32_t r1 = rank(id1), r2 = rank(id2);
if (r1 > r2 || (r1 == r2 && id1 < id2)) {
std::swap(r1, r2);
std::swap(id1, id2);
}
mData[id1] = ((uint64_t)r1 << 32) | id2;
mData[id2] = ((uint64_t)(r2 + ((r1 == r2) ? 1 : 0)) << 32) | id2;
return id2;
}
uint32_t size() const { return (uint32_t)mData.size(); }
uint32_t rank(uint32_t id) const {
return ((uint32_t)(mData[id] >> 32)) & 0x7FFFFFFFu;
}
uint32_t parent(uint32_t id) const {
return (uint32_t)mData[id];
}
friend std::ostream &operator<<(std::ostream &os, const DisjointSets &f) {
for (size_t i = 0; i<f.mData.size(); ++i)
os << i << ": parent=" << f.parent(i) << ", rank=" << f.rank(i) << std::endl;
return os;
}
mutable std::vector<std::atomic<uint64_t>> mData;
};
} // namespace qflow
#endif /* __UNIONFIND_H */
|
