Geogram  Version 1.9.1
A programming library of geometric algorithms
delaunay_sync.h
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2000-2022 Inria
3  * All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions are met:
7  *
8  * * Redistributions of source code must retain the above copyright notice,
9  * this list of conditions and the following disclaimer.
10  * * Redistributions in binary form must reproduce the above copyright notice,
11  * this list of conditions and the following disclaimer in the documentation
12  * and/or other materials provided with the distribution.
13  * * Neither the name of the ALICE Project-Team nor the names of its
14  * contributors may be used to endorse or promote products derived from this
15  * software without specific prior written permission.
16  *
17  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
18  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
21  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
22  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
23  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
24  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
25  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
26  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
27  * POSSIBILITY OF SUCH DAMAGE.
28  *
29  * Contact: Bruno Levy
30  *
31  * https://www.inria.fr/fr/bruno-levy
32  *
33  * Inria,
34  * Domaine de Voluceau,
35  * 78150 Le Chesnay - Rocquencourt
36  * FRANCE
37  *
38  */
39 
40 #ifndef DELAUNAY_SYNC_H
41 #define DELAUNAY_SYNC_H
42 
43 #include <geogram/basic/common.h>
44 #include <geogram/basic/assert.h>
45 #include <atomic>
46 
47 // In GARGANTUA mode (64-bit indices), we also enable
48 // more than 127 concurrent threads.
49 #ifdef GARGANTUA
50 #define GEO_CONNECTION_MACHINE
51 #endif
52 
58 namespace GEO {
59 
69  public:
70 #ifdef GEO_CONNECTION_MACHINE
71  // For machines that can run more than 127 concurrent threads
72  typedef uint16_t thread_index_t;
73  typedef uint16_t cell_status_t;
74  static constexpr cell_status_t FREE_CELL = 32767;
75  static constexpr cell_status_t THREAD_MASK = 32767;
76  static constexpr cell_status_t CONFLICT_MASK = 32768;
77 #else
78  typedef uint8_t thread_index_t;
79  typedef uint8_t cell_status_t;
80  static constexpr cell_status_t FREE_CELL = 127;
81  static constexpr cell_status_t THREAD_MASK = 127;
82  static constexpr cell_status_t CONFLICT_MASK = 128;
83 #endif
84 
85  static constexpr index_t MAX_THREADS = index_t(THREAD_MASK)-1;
86 
90  CellStatusArray() : cell_status_(nullptr), size_(0), capacity_(0) {
91  }
92 
98  cell_status_(nullptr), size_(0), capacity_(0) {
99  resize(size_in,size_in);
100  }
101 
109  clear();
110  }
111 
115  CellStatusArray(const CellStatusArray& rhs) = delete;
116 
121 
131  cell_status_t acquire_cell(index_t cell, cell_status_t status) {
132  geo_debug_assert(cell < size_);
133  cell_status_t expected = FREE_CELL;
134  // strong: acquire_cell is not used in a spinlock-like
135  // spinning loop (so we do not want to have "false negatives")
136  cell_status_[cell].compare_exchange_strong(
137  expected,status,
138  std::memory_order_acquire,std::memory_order_acquire
139  ); // this one could probably be relaxed ----^
140  // if compare_exchange was not sucessful, expected contains
141  // the current stored value.
142  return (expected & THREAD_MASK);
143  }
144 
150  void release_cell(index_t cell) {
151  geo_debug_assert(cell < size_);
152  cell_status_[cell].store(FREE_CELL, std::memory_order_release);
153  }
154 
161  cell_status_t cell_thread(index_t cell) const {
162  geo_debug_assert(cell < size_);
163  return (
164  cell_status_[cell].load(std::memory_order_relaxed) &
165  THREAD_MASK
166  );
167  }
168 
177  geo_debug_assert(cell < size_);
178  return(
179  (
180  cell_status_[cell].load(std::memory_order_relaxed) &
181  CONFLICT_MASK
182  ) != 0
183  );
184  }
185 
192  // memory_order_relaxed because this function is always called from
193  // a thread that previously acquired the cell.
194  cell_status_[cell].fetch_or(
195  CONFLICT_MASK, std::memory_order_relaxed
196  );
197  }
198 
205  void set_cell_status(index_t cell, cell_status_t status) {
206  geo_debug_assert(cell < size_);
207  cell_status_[cell].store(status, std::memory_order_relaxed);
208  }
209 
217  void resize(index_t size_in, index_t capacity_in) {
218  geo_debug_assert(capacity_in >= size_in);
220  if(capacity_in > capacity_) {
221  capacity_ = capacity_in;
222  std::atomic<cell_status_t>* old_cell_status = cell_status_;
223  cell_status_ = new std::atomic<cell_status_t>[capacity_];
224  for(index_t i=0; i<capacity_; ++i) {
225  cell_status_t val = (i < size_) ?
226  old_cell_status[i].load(std::memory_order_relaxed) :
227  FREE_CELL;
228  std::atomic_init(&cell_status_[i],val);
229  }
230  delete[] old_cell_status;
231  }
232  size_ = size_in;
233 #ifdef __cpp_lib_atomic_is_always_lock_free
234  static_assert(std::atomic<cell_status_t>::is_always_lock_free);
235 #else
236  geo_debug_assert(size_ == 0 || cell_status_[0].is_lock_free());
237 #endif
238  }
239 
245  void resize(index_t size_in) {
246  resize(size_in, size_in);
247  }
248 
256  void reserve(index_t new_capacity) {
257  if(new_capacity > capacity_) {
258  resize(size_, new_capacity);
259  }
260  }
261 
266  void grow() {
267  if(size_+1 >= capacity_) {
268  resize(size_+1, std::max(capacity_*2,size_+1));
269  } else {
270  resize(size_+1, capacity_);
271  }
272  }
273 
278  index_t size() const {
279  return size_;
280  }
281 
287  void clear() {
289 #ifdef GEO_DEBUG
290  for(index_t i=0; i<size_; ++i) {
291  geo_debug_assert(cell_thread(i) == FREE_CELL);
292  }
293 #endif
294  delete[] cell_status_;
295  size_ = 0;
296  capacity_ = 0;
297  }
298 
299  private:
300  std::atomic<cell_status_t>* cell_status_;
301  index_t size_;
302  index_t capacity_;
303  };
304 }
305 
306 #endif
Assertion checking mechanism.
#define geo_debug_assert(x)
Verifies that a condition is met.
Definition: assert.h:196
An array of cell status codes associates to each tetrahedron in a Delaunay tetrahedralization.
Definition: delaunay_sync.h:68
void resize(index_t size_in)
Resizes this CellStatusArray.
void reserve(index_t new_capacity)
Reserves additional space.
void grow()
Increases the size of the array for one additional element.
CellStatusArray(index_t size_in)
Creates a CellStatusArray.
Definition: delaunay_sync.h:97
CellStatusArray(const CellStatusArray &rhs)=delete
Forbids copy.
void mark_cell_as_conflict(index_t cell)
Marks a cell as conflict.
CellStatusArray()
Creates an empty CellStatusArray.
Definition: delaunay_sync.h:90
void release_cell(index_t cell)
Releases a cell.
void resize(index_t size_in, index_t capacity_in)
Resizes this CellStatusArray.
void clear()
Clears this CellStatusArray.
bool cell_is_marked_as_conflict(index_t cell) const
Tests whether a cell is marked as conflict.
~CellStatusArray()
CellStatusArray destructor.
CellStatusArray & operator=(const CellStatusArray &rhs)=delete
Forbids copy.
void set_cell_status(index_t cell, cell_status_t status)
Sets the status of a cell.
index_t size() const
Gets the size of this CellStatusArray.
cell_status_t cell_thread(index_t cell) const
Gets the thread that acquired a cell.
cell_status_t acquire_cell(index_t cell, cell_status_t status)
Tentatively acquires a cell.
Common include file, providing basic definitions. Should be included before anything else by all head...
bool is_running_threads()
Checks whether threads are running.
Global Vorpaline namespace.
Definition: basic.h:55
geo_index_t index_t
The type for storing and manipulating indices.
Definition: numeric.h:329