10 // abstract queue for RCU-like queues
13 template <typename T, size_t N> struct basic_px_queue;
15 template <typename T, size_t N>
16 struct basic_px_group {
18 : next_(nullptr), rcu_tick_(0)
20 static event_counter evt_px_group_creates(
21 util::cxx_typename<T>::value() + std::string("_px_group_creates"));
22 ++evt_px_group_creates;
26 static event_counter evt_px_group_deletes(
27 util::cxx_typename<T>::value() + std::string("_px_group_deletes"));
28 ++evt_px_group_deletes;
32 basic_px_group(const basic_px_group &) = delete;
33 basic_px_group &operator=(const basic_px_group &) = delete;
34 basic_px_group(basic_px_group &&) = delete;
36 static const size_t GroupSize = N;
37 friend class basic_px_queue<T, N>;
40 basic_px_group *next_;
41 typename util::vec<T, GroupSize>::type pxs_;
42 uint64_t rcu_tick_; // all elements in pxs_ are from this tick,
43 // this number is only meaningful if pxs_ is
47 // not thread safe- should guard with lock for concurrent manipulation
48 template <typename T, size_t N>
49 struct basic_px_queue {
51 : head_(nullptr), tail_(nullptr),
52 freelist_head_(nullptr), freelist_tail_(nullptr),
55 typedef basic_px_group<T, N> px_group;
57 basic_px_queue(basic_px_queue &&) = default;
58 basic_px_queue(const basic_px_queue &) = delete;
59 basic_px_queue &operator=(const basic_px_queue &) = delete;
64 reap_chain(freelist_head_);
68 swap(basic_px_queue &other)
70 std::swap(head_, other.head_);
71 std::swap(tail_, other.tail_);
72 std::swap(freelist_head_, other.freelist_head_);
73 std::swap(freelist_tail_, other.freelist_tail_);
74 std::swap(ngroups_, other.ngroups_);
77 template <typename PtrType, typename ObjType>
78 class iterator_ : public std::iterator<std::forward_iterator_tag, ObjType> {
80 inline iterator_() : px_(nullptr), i_() {}
81 inline iterator_(PtrType *px) : px_(px), i_() {}
83 // allow iterator to assign to const_iterator
84 template <typename P, typename O>
85 inline iterator_(const iterator_<P, O> &o) : px_(o.px_), i_(o.i_) {}
96 return &px_->pxs_[i_];
102 return px_->rcu_tick_;
106 operator==(const iterator_ &o) const
108 return px_ == o.px_ && i_ == o.i_;
112 operator!=(const iterator_ &o) const
114 return !operator==(o);
121 if (i_ == px_->pxs_.size()) {
131 iterator_ cur = *this;
141 typedef iterator_<px_group, T> iterator;
142 typedef iterator_<const px_group, const T> const_iterator;
144 inline iterator begin() { return iterator(head_); }
145 inline const_iterator begin() const { return iterator(head_); }
147 inline iterator end() { return iterator(nullptr); }
148 inline const_iterator end() const { return iterator(nullptr); }
150 // enqueue t in epoch rcu_tick
151 // assumption: rcu_ticks can only go up!
153 enqueue(const T &t, uint64_t rcu_tick)
155 INVARIANT(bool(head_) == bool(tail_));
156 INVARIANT(bool(head_) == bool(ngroups_));
157 INVARIANT(!tail_ || tail_->pxs_.size() <= px_group::GroupSize);
158 INVARIANT(!tail_ || tail_->rcu_tick_ <= rcu_tick);
160 if (unlikely(!tail_ ||
161 tail_->pxs_.size() == px_group::GroupSize ||
162 tail_->rcu_tick_ != rcu_tick)) {
166 freelist_head_ = g->next_;
167 if (g == freelist_tail_)
168 freelist_tail_ = nullptr;
171 g->rcu_tick_ = rcu_tick;
184 INVARIANT(g->pxs_.size() < px_group::GroupSize);
185 INVARIANT(g->rcu_tick_ == rcu_tick);
186 INVARIANT(!g->next_);
187 INVARIANT(tail_ == g);
188 g->pxs_.emplace_back(t);
195 INVARIANT(bool(freelist_head_) == bool(freelist_tail_));
196 if (likely(freelist_head_))
198 const size_t nalloc = 16;
199 alloc_freelist(nalloc);
208 #ifdef CHECK_INVARIANTS
212 INVARIANT(bool(head_) == bool(tail_));
213 INVARIANT(!tail_ || ngroups_);
214 INVARIANT(!tail_ || !tail_->next_);
215 INVARIANT(bool(freelist_head_) == bool(freelist_tail_));
216 INVARIANT(!freelist_tail_ || !freelist_tail_->next_);
217 px_group *p = head_, *pprev = nullptr;
219 uint64_t prev_tick = 0;
221 INVARIANT(p->pxs_.size());
222 INVARIANT(p->pxs_.size() <= px_group::GroupSize);
223 INVARIANT(prev_tick <= p->rcu_tick_);
224 prev_tick = p->rcu_tick_;
229 INVARIANT(n == ngroups_);
230 INVARIANT(!pprev || tail_ == pprev);
237 INVARIANT(!pprev || freelist_tail_ == pprev);
240 inline ALWAYS_INLINE void sanity_check() const {}
243 // assumes this instance is EMPTY, accept from source
246 empty_accept_from(basic_px_queue &source, uint64_t rcu_tick)
248 ALWAYS_ASSERT(empty());
249 INVARIANT(this != &source);
251 px_group *p = source.head_, *pnext;
252 while (p && p->rcu_tick_ <= rcu_tick) {
263 source.head_ = p = pnext;
265 source.tail_ = nullptr;
268 source.sanity_check();
271 // transfer *this* elements freelist to dest
273 transfer_freelist(basic_px_queue &dest, ssize_t n = -1)
278 freelist_tail_->next_ = dest.freelist_head_;
279 if (!dest.freelist_tail_)
280 dest.freelist_tail_ = freelist_tail_;
281 dest.freelist_head_ = freelist_head_;
282 freelist_head_ = freelist_tail_ = nullptr;
284 px_group *p = freelist_head_;
286 while (p && c++ < static_cast<size_t>(n)) {
287 px_group *tmp = p->next_;
288 p->next_ = dest.freelist_head_;
289 dest.freelist_head_ = p;
290 if (!dest.freelist_tail_)
291 dest.freelist_tail_ = p;
292 if (p == freelist_tail_)
293 freelist_tail_ = nullptr;
306 tail_->next_ = freelist_head_;
308 freelist_tail_ = tail_;
309 freelist_head_ = head_;
310 head_ = tail_ = nullptr;
314 // adds n new groups to the freelist
316 alloc_freelist(size_t n)
318 for (size_t i = 0; i < n; i++) {
319 px_group *p = new px_group;
322 p->next_ = freelist_head_;
327 inline size_t get_ngroups() const { return ngroups_; }
330 get_latest_epoch(uint64_t &e) const
334 e = tail_->rcu_tick_;
340 reap_chain(px_group *px)
343 px_group *tmp = px->next_;
351 px_group *freelist_head_;
352 px_group *freelist_tail_;