Geogram  Version 1.9.1-rc
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 
52 namespace GEO {
53 
63  public:
64  typedef uint8_t cell_status_t;
65  static constexpr cell_status_t FREE_CELL = 127;
66  static constexpr cell_status_t THREAD_MASK = 127;
67  static constexpr cell_status_t CONFLICT_MASK = 128;
68 
72  CellStatusArray() : cell_status_(nullptr), size_(0), capacity_(0) {
73  }
74 
80  cell_status_(nullptr), size_(0), capacity_(0) {
81  resize(size_in,size_in);
82  }
83 
91  clear();
92  }
93 
97  CellStatusArray(const CellStatusArray& rhs) = delete;
98 
103 
113  cell_status_t acquire_cell(index_t cell, cell_status_t status) {
114  geo_debug_assert(cell < size_);
115  cell_status_t expected = FREE_CELL;
116  // strong: acquire_cell is not used in a spinlock-like
117  // spinning loop (so we do not want to have "false negatives")
118  cell_status_[cell].compare_exchange_strong(
119  expected,status,
120  std::memory_order_acquire,std::memory_order_acquire
121  ); // this one could probably be relaxed ----^
122  // if compare_exchange was not sucessful, expected contains
123  // the current stored value.
124  return (expected & THREAD_MASK);
125  }
126 
132  void release_cell(index_t cell) {
133  geo_debug_assert(cell < size_);
134  cell_status_[cell].store(FREE_CELL, std::memory_order_release);
135  }
136 
143  cell_status_t cell_thread(index_t cell) const {
144  geo_debug_assert(cell < size_);
145  return (
146  cell_status_[cell].load(std::memory_order_relaxed) &
147  THREAD_MASK
148  );
149  }
150 
159  geo_debug_assert(cell < size_);
160  return(
161  (
162  cell_status_[cell].load(std::memory_order_relaxed) &
163  CONFLICT_MASK
164  ) != 0
165  );
166  }
167 
174  // we could also use std::atomic::fetch_or(), but it
175  // would constrain the operation to be atomic, which we
176  // do not need since this function is always used by
177  // a thread that previously acquired the cell (well in
178  // practice it gives approximately the same performance).
179  cell_status_[cell].store(
180  cell_status_[cell].load(
181  std::memory_order_relaxed
182  ) | CONFLICT_MASK, std::memory_order_relaxed
183  );
184  }
185 
192  void set_cell_status(index_t cell, cell_status_t status) {
193  geo_debug_assert(cell < size_);
194  cell_status_[cell].store(status, std::memory_order_relaxed);
195  }
196 
204  void resize(index_t size_in, index_t capacity_in) {
205  geo_debug_assert(capacity_in >= size_in);
207  if(capacity_in > capacity_) {
208  capacity_ = capacity_in;
209  std::atomic<cell_status_t>* old_cell_status = cell_status_;
210  cell_status_ = new std::atomic<cell_status_t>[capacity_];
211  for(index_t i=0; i<capacity_; ++i) {
212  cell_status_t val = (i < size_) ?
213  old_cell_status[i].load(std::memory_order_relaxed) :
214  FREE_CELL;
215  std::atomic_init(&cell_status_[i],val);
216  }
217  delete[] old_cell_status;
218  }
219  size_ = size_in;
220 #ifdef __cpp_lib_atomic_is_always_lock_free
221  static_assert(std::atomic<cell_status_t>::is_always_lock_free);
222 #else
223  geo_debug_assert(size_ == 0 || cell_status_[0].is_lock_free());
224 #endif
225  }
226 
232  void resize(index_t size_in) {
233  resize(size_in, size_in);
234  }
235 
243  void reserve(index_t new_capacity) {
244  if(new_capacity > capacity_) {
245  resize(size_, new_capacity);
246  }
247  }
248 
253  void grow() {
254  if(size_+1 >= capacity_) {
255  resize(size_+1, std::max(capacity_*2,size_+1));
256  } else {
257  resize(size_+1, capacity_);
258  }
259  }
260 
265  index_t size() const {
266  return size_;
267  }
268 
274  void clear() {
276 #ifdef GEO_DEBUG
277  for(index_t i=0; i<size_; ++i) {
278  geo_debug_assert(cell_thread(i) == FREE_CELL);
279  }
280 #endif
281  delete[] cell_status_;
282  size_ = 0;
283  capacity_ = 0;
284  }
285 
286  private:
287  std::atomic<cell_status_t>* cell_status_;
288  index_t size_;
289  index_t capacity_;
290  };
291 }
292 
293 #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:62
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:79
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:72
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.
Definition: delaunay_sync.h:90
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