20 #ifndef GALOIS_FIXEDSIZERING_H
21 #define GALOIS_FIXEDSIZERING_H
26 #include <boost/mpl/if.hpp>
27 #include <boost/iterator/iterator_facade.hpp>
28 #include <boost/iterator/reverse_iterator.hpp>
30 #include "galois/config.h"
37 template <
typename T,
unsigned ChunkSize,
bool Concurrent>
40 typedef typename boost::mpl::if_c<Concurrent, std::atomic<unsigned>,
41 unsigned>::type Count;
44 T* at(
unsigned i) {
return &datac[i]; }
45 const T* at(
unsigned i)
const {
return &datac[i]; }
47 bool precondition()
const {
return count <= ChunkSize; }
55 typedef boost::reverse_iterator<pointer>
iterator;
62 template <
typename InputIterator>
64 while (first != last) {
65 assert(count < ChunkSize);
66 datac.
emplace(count++, *first++);
76 assert(precondition());
81 assert(precondition());
86 assert(precondition());
87 return count == ChunkSize;
91 assert(precondition());
92 for (
unsigned x = 0; x < count; ++x)
102 template <
typename... Args>
107 template <
typename U,
bool C = Concurrent>
108 auto push_front(U&& val) ->
typename std::enable_if<!C, pointer>::type {
112 template <
bool C = Concurrent>
114 typename std::enable_if<C, pointer>::type {
117 top = count.load(std::memory_order_relaxed);
118 if (top >= ChunkSize)
120 }
while (!count.compare_exchange_weak(top, top + 1));
121 return datac.
emplace(top, val);
129 template <
typename... Args,
bool C = Concurrent>
131 typename std::enable_if<!C, pointer>::type {
134 unsigned top = count++;
135 return datac.
emplace(top, std::forward<Args>(args)...);
145 assert(precondition());
147 return *at(count - 1);
152 template <
bool C = Concurrent>
154 typename std::enable_if<!C, galois::optional<value_type>>::type {
164 template <
bool C = Concurrent>
165 auto pop_front() ->
typename std::enable_if<C, bool>::type {
168 top = count.load(std::memory_order_relaxed);
171 }
while (!count.compare_exchange_weak(top, top - 1));
177 template <
bool C = Concurrent>
178 auto pop_front() ->
typename std::enable_if<!C, bool>::type {
197 template <
typename T,
unsigned ChunkSize = 64>
202 template <
typename T,
unsigned ChunkSize = 64>
206 template <
typename T,
unsigned ChunkSize = 64>
212 T* at(
unsigned i) {
return &datac[i]; }
213 const T* at(
unsigned i)
const {
return &datac[i]; }
215 bool precondition()
const {
return count <= ChunkSize && start <= ChunkSize; }
217 template <
typename U>
219 :
public boost::iterator_facade<Iterator<U>, U,
220 boost::random_access_traversal_tag> {
221 friend class boost::iterator_core_access;
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;
232 U& dereference()
const {
return base[cur]; }
235 assert(base && count != 0);
237 cur = (cur + 1) % ChunkSize;
241 assert(base && count < ChunkSize);
243 cur = (cur + ChunkSize - 1) % ChunkSize;
246 void advance(ptrdiff_t x) {
248 cur = (cur + ChunkSize + x) % ChunkSize;
251 ptrdiff_t distance_to(
const Iterator& o)
const {
253 ptrdiff_t oc = o.count;
258 Iterator() : base(0), cur(0), count(0) {}
260 template <
typename OtherTy>
261 Iterator(
const Iterator<OtherTy>& o)
262 : base(o.base), cur(o.cur), count(o.count) {}
264 Iterator(U* b,
unsigned c,
unsigned co) : base(b), cur(c), count(co) {}
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++);
293 assert(precondition());
298 assert(precondition());
303 assert(precondition());
304 return count == ChunkSize;
308 assert(precondition());
310 return *at((start + x) % ChunkSize);
314 assert(precondition());
316 return *at((start + x) % ChunkSize);
320 assert(precondition());
321 for (
unsigned x = 0; x < count; ++x)
322 datac.
destroy((start + x) % ChunkSize);
329 template <
typename... Args>
334 if (pos ==
begin()) {
335 i = start = (start + ChunkSize - 1) % ChunkSize;
337 }
else if (pos ==
end()) {
338 i = (start + count) % ChunkSize;
341 auto d = std::distance(
begin(), pos);
342 i = (start + d) % ChunkSize;
347 return datac.
emplace(i, std::forward<Args>(args)...);
350 template <
typename U>
355 template <
typename... Args>
359 start = (start + ChunkSize - 1) % ChunkSize;
361 return datac.
emplace(start, std::forward<Args>(args)...);
364 template <
typename U>
369 template <
typename... Args>
373 unsigned end = (start + count) % ChunkSize;
375 return datac.
emplace(end, std::forward<Args>(args)...);
379 assert(precondition());
385 assert(precondition());
400 assert(precondition());
403 start = (start + 1) % ChunkSize;
408 assert(precondition());
410 return *at((start + count - 1) % ChunkSize);
414 assert(precondition());
416 return *at((start + count - 1) % ChunkSize);
429 assert(precondition());
431 datac.
destroy((start + count - 1) % ChunkSize);
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