Skip to content
Lock-free parallel disjoint set data structure (aka UNION-FIND) with path compression and union by rank
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
LICENSE.txt
README.md
dset.h

README.md

Lock-free parallel disjoint set data structure

This is a small self-contained C++11 implementation of the UNION-FIND data structure with path compression and union by rank and a few extras It 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 for pairs of sets.

You can’t perform that action at this time.