diff options
Diffstat (limited to 'extern/quadriflow/src/dset.hpp')
| -rw-r--r-- | extern/quadriflow/src/dset.hpp | 163 |
1 files changed, 163 insertions, 0 deletions
diff --git a/extern/quadriflow/src/dset.hpp b/extern/quadriflow/src/dset.hpp new file mode 100644 index 00000000000..f8e6f6da6b6 --- /dev/null +++ b/extern/quadriflow/src/dset.hpp @@ -0,0 +1,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 */ |