Blender V5.3
BLI_atomic_disjoint_set.hh
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
8
9#pragma once
10
11#include <atomic>
12
13#include "BLI_array.hh"
14
15namespace blender {
16
27 private:
28 /* Can generally used relaxed memory order with this algorithm. */
29 static constexpr auto relaxed = std::memory_order_relaxed;
30
31 struct Item {
32 int parent;
33 int rank;
34 };
35
40 mutable Array<std::atomic<Item>> items_;
41
42 public:
46 AtomicDisjointSet(const int size);
47
52 void join(int x, int y)
53 {
54 while (true) {
55 x = this->find_root(x);
56 y = this->find_root(y);
57
58 if (x == y) {
59 /* They are in the same set already. */
60 return;
61 }
62
63 int x_rank = items_[x].load(relaxed).rank;
64 int y_rank = items_[y].load(relaxed).rank;
65
66 if (
67 /* Implement union by rank heuristic. */
68 x_rank > y_rank
69 /* If the rank is the same, make a consistent decision. */
70 || (x_rank == y_rank && x < y))
71 {
72 std::swap(x_rank, y_rank);
73 std::swap(x, y);
74 }
75
76 /* Update parent of item x. */
77 Item x_item_old = {x, x_rank};
78 const Item x_item_new{y, x_rank};
79 if (!items_[x].compare_exchange_strong(x_item_old, x_item_new, relaxed)) {
80 /* Another thread has updated item x, start again. */
81 continue;
82 }
83
84 if (x_rank == y_rank) {
85 /* Increase rank of item y. This may fail when another thread has updated item y in the
86 * meantime. That may lead to worse behavior with the union by rank heuristic, but seems to
87 * be ok in practice. */
88 Item y_item_old{y, y_rank};
89 const Item y_item_new{y, y_rank + 1};
90 items_[y].compare_exchange_weak(y_item_old, y_item_new, relaxed);
91 }
92
93 return;
94 }
95 }
96
100 bool in_same_set(int x, int y) const
101 {
102 while (true) {
103 x = this->find_root(x);
104 y = this->find_root(y);
105 if (x == y) {
106 return true;
107 }
108 if (items_[x].load(relaxed).parent == x) {
109 return false;
110 }
111 }
112 }
113
117 int find_root(int x) const
118 {
119 while (true) {
120 const Item item = items_[x].load(relaxed);
121 if (x == item.parent) {
122 return x;
123 }
124 const int new_parent = items_[item.parent].load(relaxed).parent;
125 if (item.parent != new_parent) {
126 /* This halves the path for faster future lookups. That fail but that does not change
127 * correctness. */
128 Item expected = item;
129 const Item desired{new_parent, item.rank};
130 items_[x].compare_exchange_weak(expected, desired, relaxed);
131 }
132 x = new_parent;
133 }
134 }
135
139 bool is_root(const int x) const
140 {
141 const Item item = items_[x].load(relaxed);
142 return item.parent == x;
143 }
144
152
156 int count_sets() const;
157};
158
159} // namespace blender
int calc_reduced_ids(MutableSpan< int > result) const
bool in_same_set(int x, int y) const
BMesh Iterators.