Galois
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
FixedSizeRing.h
Go to the documentation of this file.
1 /*
2  * This file belongs to the Galois project, a C++ library for exploiting
3  * parallelism. The code is being released under the terms of the 3-Clause BSD
4  * License (a copy is located in LICENSE.txt at the top-level directory).
5  *
6  * Copyright (C) 2018, The University of Texas at Austin. All rights reserved.
7  * UNIVERSITY EXPRESSLY DISCLAIMS ANY AND ALL WARRANTIES CONCERNING THIS
8  * SOFTWARE AND DOCUMENTATION, INCLUDING ANY WARRANTIES OF MERCHANTABILITY,
9  * FITNESS FOR ANY PARTICULAR PURPOSE, NON-INFRINGEMENT AND WARRANTIES OF
10  * PERFORMANCE, AND ANY WARRANTY THAT MIGHT OTHERWISE ARISE FROM COURSE OF
11  * DEALING OR USAGE OF TRADE. NO WARRANTY IS EITHER EXPRESS OR IMPLIED WITH
12  * RESPECT TO THE USE OF THE SOFTWARE OR DOCUMENTATION. Under no circumstances
13  * shall University be liable for incidental, special, indirect, direct or
14  * consequential damages or loss of profits, interruption of business, or
15  * related expenses which may arise from use of Software or Documentation,
16  * including but not limited to those resulting from defects in Software and/or
17  * Documentation, or loss or inaccuracy of data of any kind.
18  */
19 
20 #ifndef GALOIS_FIXEDSIZERING_H
21 #define GALOIS_FIXEDSIZERING_H
22 
23 #include <atomic>
24 #include <utility>
25 
26 #include <boost/mpl/if.hpp>
27 #include <boost/iterator/iterator_facade.hpp>
28 #include <boost/iterator/reverse_iterator.hpp>
29 
30 #include "galois/config.h"
31 #include "galois/optional.h"
32 #include "galois/LazyArray.h"
33 
34 namespace galois {
35 
37 template <typename T, unsigned ChunkSize, bool Concurrent>
40  typedef typename boost::mpl::if_c<Concurrent, std::atomic<unsigned>,
41  unsigned>::type Count;
42  Count count;
43 
44  T* at(unsigned i) { return &datac[i]; }
45  const T* at(unsigned i) const { return &datac[i]; }
46 
47  bool precondition() const { return count <= ChunkSize; }
48 
49 public:
50  typedef T value_type;
51  typedef T* pointer;
52  typedef const T* const_pointer;
53  typedef T& reference;
54  typedef const T& const_reference;
55  typedef boost::reverse_iterator<pointer> iterator;
56  typedef boost::reverse_iterator<const_pointer> const_iterator;
59 
60  FixedSizeBagBase() : count(0) {}
61 
62  template <typename InputIterator>
63  FixedSizeBagBase(InputIterator first, InputIterator last) : count(0) {
64  while (first != last) {
65  assert(count < ChunkSize);
66  datac.emplace(count++, *first++);
67  }
68  }
69 
70  FixedSizeBagBase(const FixedSizeBagBase& o) = delete;
71  FixedSizeBagBase& operator=(const FixedSizeBagBase& o) = delete;
72 
74 
75  unsigned size() const {
76  assert(precondition());
77  return count;
78  }
79 
80  bool empty() const {
81  assert(precondition());
82  return count == 0;
83  }
84 
85  bool full() const {
86  assert(precondition());
87  return count == ChunkSize;
88  }
89 
90  void clear() {
91  assert(precondition());
92  for (unsigned x = 0; x < count; ++x)
93  datac.destroy(x);
94  count = 0;
95  }
96 
97  template <typename U>
98  pointer push_back(U&& val) {
99  return push_front(std::forward<U>(val));
100  }
101 
102  template <typename... Args>
103  pointer emplace_back(Args&&... args) {
104  return emplace_front(std::forward<Args>(args)...);
105  }
106 
107  template <typename U, bool C = Concurrent>
108  auto push_front(U&& val) -> typename std::enable_if<!C, pointer>::type {
109  return emplace_front(std::forward<U>(val));
110  }
111 
112  template <bool C = Concurrent>
113  auto push_front(const value_type& val) ->
114  typename std::enable_if<C, pointer>::type {
115  unsigned top;
116  do {
117  top = count.load(std::memory_order_relaxed);
118  if (top >= ChunkSize)
119  return nullptr;
120  } while (!count.compare_exchange_weak(top, top + 1));
121  return datac.emplace(top, val);
122  }
123 
129  template <typename... Args, bool C = Concurrent>
130  auto emplace_front(Args&&... args) ->
131  typename std::enable_if<!C, pointer>::type {
132  if (full())
133  return 0;
134  unsigned top = count++;
135  return datac.emplace(top, std::forward<Args>(args)...);
136  }
137 
138  reference back() { return front(); }
139  const_reference back() const { return front(); }
141 
142  bool pop_back() { return pop_front(); }
143 
145  assert(precondition());
146  assert(!empty());
147  return *at(count - 1);
148  }
149 
150  const_reference front() const { return *at(count - 1); }
151 
152  template <bool C = Concurrent>
153  auto extract_front() ->
154  typename std::enable_if<!C, galois::optional<value_type>>::type {
155  if (!empty()) {
157  pop_back();
158  return retval;
159  }
161  }
162 
164  template <bool C = Concurrent>
165  auto pop_front() -> typename std::enable_if<C, bool>::type {
166  unsigned top;
167  do {
168  top = count.load(std::memory_order_relaxed);
169  if (top == 0)
170  return false;
171  } while (!count.compare_exchange_weak(top, top - 1));
172  datac.destroy(top);
173  return true;
174  }
175 
177  template <bool C = Concurrent>
178  auto pop_front() -> typename std::enable_if<!C, bool>::type {
179  if (count == 0)
180  return false;
181  datac.destroy(--count);
182  return true;
183  }
184 
185  reverse_iterator rbegin() { return &datac[0]; }
186  reverse_iterator rend() { return &datac[count]; }
187  const_reverse_iterator rbegin() const { return &datac[0]; }
188  const_reverse_iterator rend() const { return &datac[count]; }
189 
190  iterator begin() { return iterator(rend()); }
191  iterator end() { return iterator(rbegin()); }
192  const_iterator begin() const { return const_iterator(rend()); }
193  const_iterator end() const { return const_iterator(rbegin()); }
194 };
195 
197 template <typename T, unsigned ChunkSize = 64>
199 
202 template <typename T, unsigned ChunkSize = 64>
204 
206 template <typename T, unsigned ChunkSize = 64>
209  unsigned start;
210  unsigned count;
211 
212  T* at(unsigned i) { return &datac[i]; }
213  const T* at(unsigned i) const { return &datac[i]; }
214 
215  bool precondition() const { return count <= ChunkSize && start <= ChunkSize; }
216 
217  template <typename U>
218  class Iterator
219  : public boost::iterator_facade<Iterator<U>, U,
220  boost::random_access_traversal_tag> {
221  friend class boost::iterator_core_access;
222  U* base;
223  unsigned cur;
224  unsigned count;
225 
226  template <typename OtherTy>
227  bool equal(const Iterator<OtherTy>& o) const {
228  assert(base && o.base);
229  return &base[cur] == &o.base[o.cur] && count == o.count;
230  }
231 
232  U& dereference() const { return base[cur]; }
233 
234  void increment() {
235  assert(base && count != 0);
236  count -= 1;
237  cur = (cur + 1) % ChunkSize;
238  }
239 
240  void decrement() {
241  assert(base && count < ChunkSize);
242  count += 1;
243  cur = (cur + ChunkSize - 1) % ChunkSize;
244  }
245 
246  void advance(ptrdiff_t x) {
247  count -= x;
248  cur = (cur + ChunkSize + x) % ChunkSize;
249  }
250 
251  ptrdiff_t distance_to(const Iterator& o) const {
252  ptrdiff_t c = count;
253  ptrdiff_t oc = o.count;
254  return c - oc;
255  }
256 
257  public:
258  Iterator() : base(0), cur(0), count(0) {}
259 
260  template <typename OtherTy>
261  Iterator(const Iterator<OtherTy>& o)
262  : base(o.base), cur(o.cur), count(o.count) {}
263 
264  Iterator(U* b, unsigned c, unsigned co) : base(b), cur(c), count(co) {}
265  };
266 
267 public:
268  typedef T value_type;
269  typedef T* pointer;
270  typedef T& reference;
271  typedef const T& const_reference;
272  typedef Iterator<T> iterator;
273  typedef Iterator<const T> const_iterator;
274  typedef boost::reverse_iterator<Iterator<T>> reverse_iterator;
275  typedef boost::reverse_iterator<Iterator<const T>> const_reverse_iterator;
276 
277  FixedSizeRing() : start(0), count(0) {}
278 
279  template <typename InputIterator>
280  FixedSizeRing(InputIterator first, InputIterator last) : start(0), count(0) {
281  while (first != last) {
282  assert(count < ChunkSize);
283  datac.emplace(count++, *first++);
284  }
285  }
286 
287  FixedSizeRing(const FixedSizeRing& o) = delete;
288  FixedSizeRing& operator=(const FixedSizeRing& o) = delete;
289 
291 
292  unsigned size() const {
293  assert(precondition());
294  return count;
295  }
296 
297  bool empty() const {
298  assert(precondition());
299  return count == 0;
300  }
301 
302  bool full() const {
303  assert(precondition());
304  return count == ChunkSize;
305  }
306 
307  reference getAt(unsigned x) {
308  assert(precondition());
309  assert(!empty());
310  return *at((start + x) % ChunkSize);
311  }
312 
313  const_reference getAt(unsigned x) const {
314  assert(precondition());
315  assert(!empty());
316  return *at((start + x) % ChunkSize);
317  }
318 
319  void clear() {
320  assert(precondition());
321  for (unsigned x = 0; x < count; ++x)
322  datac.destroy((start + x) % ChunkSize);
323  count = 0;
324  start = 0;
325  }
326 
327  // NB(ddn): Keeping emplace_front/_back code paths separate to improve
328  // branch prediction etc
329  template <typename... Args>
330  pointer emplace(iterator pos, Args&&... args) {
331  if (full())
332  return 0;
333  unsigned i;
334  if (pos == begin()) {
335  i = start = (start + ChunkSize - 1) % ChunkSize;
336  ++count;
337  } else if (pos == end()) {
338  i = (start + count) % ChunkSize;
339  ++count;
340  } else {
341  auto d = std::distance(begin(), pos);
342  i = (start + d) % ChunkSize;
343  emplace_back();
344  std::move_backward(begin() + d, end() - 1, end());
345  datac.destroy(i);
346  }
347  return datac.emplace(i, std::forward<Args>(args)...);
348  }
349 
350  template <typename U>
351  pointer push_front(U&& val) {
352  return emplace_front(std::forward<U>(val));
353  }
354 
355  template <typename... Args>
356  pointer emplace_front(Args&&... args) {
357  if (full())
358  return 0;
359  start = (start + ChunkSize - 1) % ChunkSize;
360  ++count;
361  return datac.emplace(start, std::forward<Args>(args)...);
362  }
363 
364  template <typename U>
365  pointer push_back(U&& val) {
366  return emplace_back(std::forward<U>(val));
367  }
368 
369  template <typename... Args>
370  pointer emplace_back(Args&&... args) {
371  if (full())
372  return 0;
373  unsigned end = (start + count) % ChunkSize;
374  ++count;
375  return datac.emplace(end, std::forward<Args>(args)...);
376  }
377 
379  assert(precondition());
380  assert(!empty());
381  return *at(start);
382  }
383 
385  assert(precondition());
386  assert(!empty());
387  return *at(start);
388  }
389 
391  if (!empty()) {
393  pop_front();
394  return retval;
395  }
397  }
398 
399  void pop_front() {
400  assert(precondition());
401  assert(!empty());
402  datac.destroy(start);
403  start = (start + 1) % ChunkSize;
404  --count;
405  }
406 
408  assert(precondition());
409  assert(!empty());
410  return *at((start + count - 1) % ChunkSize);
411  }
412 
414  assert(precondition());
415  assert(!empty());
416  return *at((start + count - 1) % ChunkSize);
417  }
418 
420  if (!empty()) {
422  pop_back();
423  return retval;
424  }
426  }
427 
428  void pop_back() {
429  assert(precondition());
430  assert(!empty());
431  datac.destroy((start + count - 1) % ChunkSize);
432  --count;
433  }
434 
435  iterator begin() { return iterator(at(0), start, count); }
436  iterator end() { return iterator(at(0), (start + count) % ChunkSize, 0); }
437  const_iterator begin() const { return const_iterator(at(0), start, count); }
438  const_iterator end() const {
439  return const_iterator(at(0), (start + count) % ChunkSize, 0);
440  }
441 
446 };
447 
448 } // namespace galois
449 #endif
void pop_back()
Definition: FixedSizeRing.h:428
iterator end()
Definition: FixedSizeRing.h:191
auto push_front(U &&val) -> typename std::enable_if<!C, pointer >::type
Definition: FixedSizeRing.h:108
unsigned size() const
Definition: FixedSizeRing.h:75
const_reference back() const
Definition: FixedSizeRing.h:413
const T & const_reference
Definition: FixedSizeRing.h:271
FixedSizeBagBase(InputIterator first, InputIterator last)
Definition: FixedSizeRing.h:63
FixedSizeBagBase()
Definition: FixedSizeRing.h:60
pointer emplace(size_type __n, Args &&...args)
Definition: LazyArray.h:113
pointer emplace_back(Args &&...args)
Definition: FixedSizeRing.h:370
Unordered collection of bounded size.
Definition: FixedSizeRing.h:38
auto pop_front() -> typename std::enable_if< C, bool >::type
returns true if something was popped
Definition: FixedSizeRing.h:165
bool full() const
Definition: FixedSizeRing.h:85
const_reverse_iterator rbegin() const
Definition: FixedSizeRing.h:187
pointer push_back(U &&val)
Definition: FixedSizeRing.h:98
auto emplace_front(Args &&...args) -> typename std::enable_if<!C, pointer >::type
emplace_front is not available for concurrent versions because it is not possible for clients to know...
Definition: FixedSizeRing.h:130
pointer push_back(U &&val)
Definition: FixedSizeRing.h:365
reverse_iterator rend()
Definition: FixedSizeRing.h:186
FixedSizeRing & operator=(const FixedSizeRing &o)=delete
galois::optional< value_type > extract_front()
Definition: FixedSizeRing.h:390
reference front()
Definition: FixedSizeRing.h:144
boost::reverse_iterator< Iterator< T > > reverse_iterator
Definition: FixedSizeRing.h:274
T * pointer
Definition: FixedSizeRing.h:269
T value_type
Definition: FixedSizeRing.h:50
const_reference front() const
Definition: FixedSizeRing.h:384
bool full() const
Definition: FixedSizeRing.h:302
T * pointer
Definition: FixedSizeRing.h:51
bool pop_back()
Definition: FixedSizeRing.h:142
T value_type
Definition: FixedSizeRing.h:268
reference back()
Definition: FixedSizeRing.h:138
bool empty() const
Definition: FixedSizeRing.h:297
const T & const_reference
Definition: FixedSizeRing.h:54
galois::optional< value_type > extract_back()
Definition: FixedSizeRing.h:140
galois::optional< value_type > extract_back()
Definition: FixedSizeRing.h:419
iterator end()
Definition: FixedSizeRing.h:436
const_reference getAt(unsigned x) const
Definition: FixedSizeRing.h:313
~FixedSizeBagBase()
Definition: FixedSizeRing.h:73
iterator begin()
Definition: FixedSizeRing.h:435
iterator begin()
Definition: FixedSizeRing.h:190
const T * const_pointer
Definition: FixedSizeRing.h:52
bool empty() const
Definition: FixedSizeRing.h:80
T & reference
Definition: FixedSizeRing.h:53
Galois version of boost::optional.
Definition: optional.h:34
const_iterator end() const
Definition: FixedSizeRing.h:193
void destroy(size_type __n)
Definition: LazyArray.h:122
Ordered collection of bounded size.
Definition: FixedSizeRing.h:207
boost::reverse_iterator< pointer > iterator
Definition: FixedSizeRing.h:55
const_iterator rend() const
Definition: FixedSizeRing.h:445
const_reverse_iterator rend() const
Definition: FixedSizeRing.h:188
const_iterator rbegin() const
Definition: FixedSizeRing.h:444
reverse_iterator rbegin()
Definition: FixedSizeRing.h:442
const_iterator begin() const
Definition: FixedSizeRing.h:437
pointer reverse_iterator
Definition: FixedSizeRing.h:57
FixedSizeBagBase & operator=(const FixedSizeBagBase &o)=delete
pointer emplace_front(Args &&...args)
Definition: FixedSizeRing.h:356
Iterator< const T > const_iterator
Definition: FixedSizeRing.h:273
reference back()
Definition: FixedSizeRing.h:407
const_pointer const_reverse_iterator
Definition: FixedSizeRing.h:58
~FixedSizeRing()
Definition: FixedSizeRing.h:290
pointer emplace_back(Args &&...args)
Definition: FixedSizeRing.h:103
boost::reverse_iterator< const_pointer > const_iterator
Definition: FixedSizeRing.h:56
auto extract_front() -> typename std::enable_if<!C, galois::optional< value_type >>::type
Definition: FixedSizeRing.h:153
pointer push_front(U &&val)
Definition: FixedSizeRing.h:351
const_reference front() const
Definition: FixedSizeRing.h:150
FixedSizeRing(InputIterator first, InputIterator last)
Definition: FixedSizeRing.h:280
T & reference
Definition: FixedSizeRing.h:270
void pop_front()
Definition: FixedSizeRing.h:399
unsigned size() const
Definition: FixedSizeRing.h:292
void clear()
Definition: FixedSizeRing.h:90
auto push_front(const value_type &val) -> typename std::enable_if< C, pointer >::type
Definition: FixedSizeRing.h:113
const_iterator begin() const
Definition: FixedSizeRing.h:192
pointer emplace(iterator pos, Args &&...args)
Definition: FixedSizeRing.h:330
const_reference back() const
Definition: FixedSizeRing.h:139
reverse_iterator rbegin()
Definition: FixedSizeRing.h:185
reference front()
Definition: FixedSizeRing.h:378
void clear()
Definition: FixedSizeRing.h:319
reverse_iterator rend()
Definition: FixedSizeRing.h:443
auto pop_front() -> typename std::enable_if<!C, bool >::type
returns true if something was popped
Definition: FixedSizeRing.h:178
reference getAt(unsigned x)
Definition: FixedSizeRing.h:307
boost::reverse_iterator< Iterator< const T > > const_reverse_iterator
Definition: FixedSizeRing.h:275
FixedSizeRing()
Definition: FixedSizeRing.h:277
Iterator< T > iterator
Definition: FixedSizeRing.h:272
const_iterator end() const
Definition: FixedSizeRing.h:438