CsLibGuarded  2.0.0
cs_rcu_list.h
1 /***********************************************************************
2 *
3 * Copyright (c) 2016-2025 Ansel Sermersheim
4 *
5 * This file is part of CsLibGuarded.
6 *
7 * CsLibGuarded is free software which is released under the BSD 2-Clause license.
8 * For license details refer to the LICENSE provided with this project.
9 *
10 * CsLibGuarded is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
13 *
14 * https://opensource.org/licenses/BSD-2-Clause
15 *
16 ***********************************************************************/
17 
18 #ifndef CSLIBGUARDED_RCU_LIST_H
19 #define CSLIBGUARDED_RCU_LIST_H
20 
21 #include "cs_rcu_guarded.h"
22 
23 #include <atomic>
24 #include <cstddef>
25 #include <initializer_list>
26 #include <memory>
27 #include <mutex>
28 
29 namespace libguarded
30 {
31 
32 // 19 comment line(s) omitted
51 template <typename T, typename M = std::mutex, typename Alloc = std::allocator<T>>
52 class rcu_list
53 {
54  public:
55  using value_type = T;
56  using allocator_type = Alloc;
57  using size_type = std::ptrdiff_t;
58  using reference = value_type &;
59  using const_reference = const value_type &;
60  using pointer = typename std::allocator_traits<Alloc>::pointer;
61  using const_pointer = typename std::allocator_traits<Alloc>::const_pointer;
62 
63  class iterator;
64  class const_iterator;
65  class reverse_iterator;
66  class const_reverse_iterator;
67  class end_iterator;
68  class end_reverse_iterator;
69 
70  class rcu_guard;
71  using rcu_write_guard = rcu_guard;
72  using rcu_read_guard = rcu_guard;
73 
74  rcu_list();
75  explicit rcu_list(const Alloc &alloc);
76 
77  rcu_list(const rcu_list &) = delete;
78  rcu_list(rcu_list &&) = delete;
79 
80  rcu_list &operator=(const rcu_list &) = delete;
81  rcu_list &operator=(rcu_list &&) = delete;
82 
83  ~rcu_list();
84 
85  [[nodiscard]] iterator begin();
86  [[nodiscard]] end_iterator end();
87  [[nodiscard]] const_iterator begin() const;
88  [[nodiscard]] end_iterator end() const;
89  [[nodiscard]] const_iterator cbegin() const;
90  [[nodiscard]] end_iterator cend() const;
91 
92  void clear();
93 
94  iterator insert(const_iterator pos, T value);
95  iterator insert(const_iterator pos, size_type count, const T &value);
96 
97  template <typename InputIter>
98  iterator insert(const_iterator pos, InputIter first, InputIter last);
99  iterator insert(const_iterator pos, std::initializer_list<T> ilist);
100 
101  template <typename... Us>
102  iterator emplace(const_iterator pos, Us &&... vs);
103 
104  void push_front(T value);
105  void push_back(T value);
106 
107  template <typename... Us>
108  void emplace_front(Us &&... vs);
109 
110  template <typename... Us>
111  void emplace_back(Us &&... vs);
112 
113  iterator erase(const_iterator pos);
114 
115  private:
116  struct node {
117  // uncopyable, unmoveable
118  node(const node &) = delete;
119  node(node &&) = delete;
120 
121  node &operator=(const node &) = delete;
122  node &operator=(node &&) = delete;
123 
124  template <typename... Us>
125  explicit node(Us &&... vs)
126  : data(std::forward<Us>(vs)...)
127  {
128  }
129 
130  std::atomic<node *> next{nullptr};
131  std::atomic<node *> back{nullptr};
132  bool deleted{false};
133  T data;
134  };
135 
136  struct zombie_list_node {
137  zombie_list_node(node *n) noexcept
138  : zombie_node(n)
139  {
140  }
141 
142  zombie_list_node(rcu_guard *g) noexcept
143  : owner(g)
144  {
145  }
146 
147  // uncopyable, unmoveable
148  zombie_list_node(const zombie_list_node &) = delete;
149  zombie_list_node(zombie_list_node &&) = delete;
150 
151  zombie_list_node &operator=(const zombie_list_node &) = delete;
152  zombie_list_node &operator=(zombie_list_node &&) = delete;
153 
154  std::atomic<zombie_list_node *> next{nullptr};
155  std::atomic<rcu_guard *> owner{nullptr};
156  node *zombie_node{nullptr};
157  };
158 
159  using alloc_trait = std::allocator_traits<Alloc>;
160  using node_alloc_t = typename alloc_trait::template rebind_alloc<node>;
161  using node_alloc_trait = std::allocator_traits<node_alloc_t>;
162  using zombie_alloc_t = typename alloc_trait::template rebind_alloc<zombie_list_node>;
163  using zombie_alloc_trait = std::allocator_traits<zombie_alloc_t>;
164 
165  std::atomic<node *> m_head{nullptr};
166  std::atomic<node *> m_tail{nullptr};
167 
168  mutable std::atomic<zombie_list_node *> m_zombie_head{nullptr};
169 
170  M m_write_mutex;
171 
172  mutable node_alloc_t m_node_alloc;
173  mutable zombie_alloc_t m_zombie_alloc;
174 };
175 
176 /*----------------------------------------*/
177 
178 namespace detail
179 {
180 
181 // allocator-aware deleter for unique_ptr
182 template <typename Alloc>
183 class deallocator
184 {
185  using allocator_type = Alloc;
186  using allocator_traits = std::allocator_traits<allocator_type>;
187  using pointer = typename allocator_traits::pointer;
188 
189  allocator_type m_alloc;
190 
191 public:
192  explicit deallocator(const allocator_type &alloc) noexcept
193  : m_alloc(alloc)
194  {
195  }
196 
197  void operator()(pointer p) {
198  if (p != nullptr) {
199  allocator_traits::destroy(m_alloc, p);
200  allocator_traits::deallocate(m_alloc, p, 1);
201  }
202  }
203 };
204 
205 // unique_ptr counterpart for std::allocate_shared()
206 template <typename T, typename Alloc, typename... Args>
207 std::unique_ptr<T, deallocator<Alloc>> allocate_unique(Alloc &alloc, Args &&... args)
208 {
209  using allocator_traits = std::allocator_traits<Alloc>;
210 
211  auto p = allocator_traits::allocate(alloc, 1);
212 
213  try {
214  allocator_traits::construct(alloc, p, std::forward<Args>(args)...);
215  return {p, deallocator<Alloc>{alloc}};
216 
217  } catch (...) {
218  allocator_traits::deallocate(alloc, p, 1);
219  throw;
220  }
221 }
222 
223 } // namespace detail
224 
225 /*----------------------------------------*/
226 
227 template <typename T, typename M, typename Alloc>
228 class rcu_list<T, M, Alloc>::rcu_guard
229 {
230  public:
231  rcu_guard() = default;
232 
233  rcu_guard(const rcu_guard &other) = delete;
234  rcu_guard &operator=(const rcu_guard &other) = delete;
235 
236  rcu_guard(rcu_guard &&other) {
237  m_zombie = other.m_zombie;
238  m_list = other.m_list;
239 
240  other.m_zombie = nullptr;
241  other.m_list = nullptr;
242  }
243 
244  rcu_guard &operator=(rcu_guard &&other) {
245  m_zombie = other.m_zombie;
246  m_list = other.m_list;
247 
248  other.m_zombie = nullptr;
249  other.m_list = nullptr;
250  }
251 
252  void rcu_read_lock(const rcu_list<T, M, Alloc> &list);
253  void rcu_read_unlock(const rcu_list<T, M, Alloc> &list);
254 
255  void rcu_write_lock(rcu_list<T, M, Alloc> &list);
256  void rcu_write_unlock(rcu_list<T, M, Alloc> &list);
257 
258  private:
259  void unlock();
260 
261  zombie_list_node *m_zombie;
262  const rcu_list<T, M, Alloc> *m_list;
263 };
264 
265 template <typename T, typename M, typename Alloc>
266 void rcu_list<T, M, Alloc>::rcu_guard::rcu_read_lock(const rcu_list<T, M, Alloc> &list)
267 {
268  m_list = &list;
269  m_zombie = zombie_alloc_trait::allocate(list.m_zombie_alloc, 1);
270  zombie_alloc_trait::construct(list.m_zombie_alloc, m_zombie, this);
271  zombie_list_node *oldNext = list.m_zombie_head.load(std::memory_order_relaxed);
272 
273  do {
274  m_zombie->next.store(oldNext, std::memory_order_relaxed);
275  } while (!list.m_zombie_head.compare_exchange_weak(oldNext, m_zombie));
276 }
277 
278 template <typename T, typename M, typename Alloc>
279 void rcu_list<T, M, Alloc>::rcu_guard::rcu_read_unlock(const rcu_list<T, M, Alloc> &)
280 {
281  unlock();
282 }
283 
284 template <typename T, typename M, typename Alloc>
285 void rcu_list<T, M, Alloc>::rcu_guard::unlock()
286 {
287  zombie_list_node *cached_next = m_zombie->next.load();
288  zombie_list_node *n = cached_next;
289 
290  bool last = true;
291 
292  while (n) {
293  if (n->owner.load() != nullptr) {
294  last = false;
295  break;
296  }
297 
298  n = n->next.load();
299  }
300 
301  n = cached_next;
302 
303  if (last) {
304  while (n) {
305  node *deadNode = n->zombie_node;
306 
307  if (deadNode != nullptr) {
308  node_alloc_trait::destroy(m_list->m_node_alloc, deadNode);
309  node_alloc_trait::deallocate(m_list->m_node_alloc, deadNode, 1);
310  }
311 
312  zombie_list_node *oldnode = n;
313  n = n->next.load();
314 
315  if (oldnode != nullptr) {
316  zombie_alloc_trait::destroy(m_list->m_zombie_alloc, oldnode);
317  zombie_alloc_trait::deallocate(m_list->m_zombie_alloc, oldnode, 1);
318  }
319  }
320 
321  m_zombie->next.store(n);
322  }
323 
324  m_zombie->owner.store(nullptr);
325 }
326 
327 template <typename T, typename M, typename Alloc>
328 void rcu_list<T, M, Alloc>::rcu_guard::rcu_write_lock(rcu_list<T, M, Alloc> &list)
329 {
330  rcu_read_lock(list);
331  list.m_write_mutex.lock();
332 }
333 
334 template <typename T, typename M, typename Alloc>
335 void rcu_list<T, M, Alloc>::rcu_guard::rcu_write_unlock(rcu_list<T, M, Alloc> &list)
336 {
337  list.m_write_mutex.unlock();
338  rcu_read_unlock(list);
339 }
340 
341 /*----------------------------------------*/
342 
343 template <typename T, typename M, typename Alloc>
344 class rcu_list<T, M, Alloc>::iterator
345 {
346  public:
347  using iterator_category = std::forward_iterator_tag;
348  using value_type = const T;
349  using pointer = const T *;
350  using reference = const T &;
351  using difference_type = size_t;
352 
353  iterator()
354  : m_current(nullptr)
355  {
356  }
357 
358  const T &operator*() const {
359  return m_current->data;
360  }
361 
362  const T *operator->() const {
363  return &(m_current->data);
364  }
365 
366  bool operator==(const end_iterator &) const {
367  return m_current == nullptr;
368  }
369 
370  bool operator!=(const end_iterator &) const {
371  return m_current != nullptr;
372  }
373 
374  iterator &operator++() {
375  m_current = m_current->next.load();
376  return *this;
377  }
378 
379  iterator &operator--() {
380  m_current = m_current->prev.load();
381  return *this;
382  }
383 
384  iterator operator++(int) {
385  iterator old(*this);
386  ++(*this);
387  return old;
388  }
389 
390  iterator operator--(int) {
391  iterator old(*this);
392  --(*this);
393  return old;
394  }
395 
396  private:
397  friend rcu_list<T, M, Alloc>;
398  friend rcu_list<T, M, Alloc>::const_iterator;
399 
400  explicit iterator(const typename rcu_list<T, M, Alloc>::const_iterator &it)
401  : m_current(it.m_current)
402  {
403  }
404 
405  explicit iterator(node *n)
406  : m_current(n)
407  {
408  }
409 
410  node *m_current;
411 };
412 
413 /*----------------------------------------*/
414 
415 template <typename T, typename M, typename Alloc>
416 class rcu_list<T, M, Alloc>::const_iterator
417 {
418  public:
419  using iterator_category = std::forward_iterator_tag;
420  using value_type = const T;
421  using pointer = const T *;
422  using reference = const T &;
423  using difference_type = size_t;
424 
425  const_iterator()
426  : m_current(nullptr)
427  {
428  }
429 
430  const_iterator(const typename rcu_list<T, M, Alloc>::iterator &it)
431  : m_current(it.m_current)
432  {
433  }
434 
435  const T &operator*() const {
436  return m_current->data;
437  }
438 
439  const T *operator->() const {
440  return &(m_current->data);
441  }
442 
443  bool operator==(const end_iterator &) const {
444  return m_current == nullptr;
445  }
446 
447  bool operator!=(const end_iterator &) const {
448  return m_current != nullptr;
449  }
450 
451  const_iterator &operator++() {
452  m_current = m_current->next.load();
453  return *this;
454  }
455 
456  const_iterator &operator--() {
457  m_current = m_current->prev.load();
458  return *this;
459  }
460 
461  const_iterator operator++(int) {
462  const_iterator old(*this);
463  ++(*this);
464  return old;
465  }
466 
467  const_iterator operator--(int) {
468  const_iterator old(*this);
469  --(*this);
470  return old;
471  }
472 
473  private:
474  friend rcu_list<T, M, Alloc>;
475 
476  explicit const_iterator(node *n)
477  : m_current(n)
478  {
479  }
480 
481  node *m_current;
482 };
483 
484 /*----------------------------------------*/
485 
486 template <typename T, typename M, typename Alloc>
487 class rcu_list<T, M, Alloc>::end_iterator
488 {
489  public:
490  bool operator==(iterator iter) const {
491  return iter == *this;
492  }
493 
494  bool operator!=(iterator iter) const {
495  return iter != *this;
496  }
497 
498  bool operator==(const_iterator iter) const {
499  return iter == *this;
500  }
501 
502  bool operator!=(const_iterator iter) const {
503  return iter != *this;
504  }
505 };
506 
507 /*----------------------------------------*/
508 
509 template <typename T, typename M, typename Alloc>
510 rcu_list<T, M, Alloc>::rcu_list()
511 {
512  m_head.store(nullptr);
513  m_tail.store(nullptr);
514 }
515 
516 template <typename T, typename M, typename Alloc>
517 rcu_list<T, M, Alloc>::rcu_list(const Alloc &alloc)
518  : m_node_alloc(alloc), m_zombie_alloc(alloc)
519 {
520 }
521 
522 template <typename T, typename M, typename Alloc>
523 rcu_list<T, M, Alloc>::~rcu_list()
524 {
525  node *n = m_head.load();
526 
527  while (n != nullptr) {
528  node *current = n;
529  n = n->next.load();
530 
531  if (current != nullptr) {
532  node_alloc_trait::destroy(m_node_alloc, current);
533  node_alloc_trait::deallocate(m_node_alloc, current, 1);
534  }
535  }
536 
537  zombie_list_node *zn = m_zombie_head.load();
538 
539  while (zn != nullptr && zn->owner.load() == nullptr) {
540  zombie_list_node *current = zn;
541  zn = zn->next.load();
542 
543  if (current->zombie_node != nullptr) {
544  node_alloc_trait::destroy(m_node_alloc, current->zombie_node);
545  node_alloc_trait::deallocate(m_node_alloc, current->zombie_node, 1);
546  }
547 
548  if (current != nullptr) {
549  zombie_alloc_trait::destroy(m_zombie_alloc, current);
550  zombie_alloc_trait::deallocate(m_zombie_alloc, current, 1);
551  }
552  }
553 }
554 
555 template <typename T, typename M, typename Alloc>
556 auto rcu_list<T, M, Alloc>::begin() -> iterator
557 {
558  return iterator(m_head.load());
559 }
560 
561 template <typename T, typename M, typename Alloc>
562 auto rcu_list<T, M, Alloc>::end() -> end_iterator
563 {
564  return end_iterator();
565 }
566 
567 template <typename T, typename M, typename Alloc>
568 auto rcu_list<T, M, Alloc>::begin() const -> const_iterator
569 {
570  return const_iterator(m_head.load());
571 }
572 
573 template <typename T, typename M, typename Alloc>
574 auto rcu_list<T, M, Alloc>::end() const -> end_iterator
575 {
576  return end_iterator();
577 }
578 
579 template <typename T, typename M, typename Alloc>
580 template <typename... Us>
581 auto rcu_list<T, M, Alloc>::emplace(const_iterator iter, Us &&...vs) -> iterator
582 {
583  auto newNode = detail::allocate_unique<node>(m_node_alloc, std::forward<Us>(vs)...);
584 
585  node *oldHead = m_head.load();
586  node *oldTail = m_tail.load();
587 
588  if (oldHead == nullptr) {
589  // inserting into an empty list
590  m_head.store(newNode.get());
591  m_tail.store(newNode.get());
592 
593  } else if (oldHead == iter.m_current) {
594  // inserting at the beginning of a non-empty list
595  newNode->next.store(oldHead);
596  oldHead->back.store(newNode.get());
597  m_head.store(newNode.get());
598 
599  } else if (oldTail == iter.m_current) {
600  // inserting at the end of a non-empty list
601  newNode->back.store(oldTail);
602  oldTail->next.store(newNode.get());
603  m_tail.store(newNode.get());
604 
605  } else {
606  // inserting in the middle of a non-empty list
607  node *oldBack = iter.m_current->back.load();
608 
609  newNode->next.store(iter.m_current);
610  newNode->back.store(oldBack);
611  iter.m_current->back.store(newNode.get());
612 
613  if (oldBack != nullptr) {
614  oldBack->next.store(newNode.get());
615  }
616  }
617 
618  return iterator(newNode.release());
619 }
620 
621 template <typename T, typename M, typename Alloc>
622 void rcu_list<T, M, Alloc>::push_front(T data)
623 {
624  auto newNode = detail::allocate_unique<node>(m_node_alloc, std::move(data));
625 
626  node *oldHead = m_head.load();
627 
628  if (oldHead == nullptr) {
629  m_head.store(newNode.get());
630  m_tail.store(newNode.release());
631  } else {
632  newNode->next.store(oldHead);
633  oldHead->back.store(newNode.get());
634  m_head.store(newNode.release());
635  }
636 }
637 
638 template <typename T, typename M, typename Alloc>
639 template <typename... Us>
640 void rcu_list<T, M, Alloc>::emplace_front(Us &&... vs)
641 {
642  auto newNode = detail::allocate_unique<node>(m_node_alloc, std::forward<Us>(vs)...);
643 
644  node *oldHead = m_head.load();
645 
646  if (oldHead == nullptr) {
647  m_head.store(newNode.get());
648  m_tail.store(newNode.release());
649  } else {
650  newNode->next.store(oldHead);
651  oldHead->back.store(newNode.get());
652  m_head.store(newNode.release());
653  }
654 }
655 
656 template <typename T, typename M, typename Alloc>
657 void rcu_list<T, M, Alloc>::push_back(T data)
658 {
659  auto newNode = detail::allocate_unique<node>(m_node_alloc, std::move(data));
660 
661  node *oldTail = m_tail.load(std::memory_order_relaxed);
662 
663  if (oldTail == nullptr) {
664  m_head.store(newNode.get());
665  m_tail.store(newNode.release());
666  } else {
667  newNode->back.store(oldTail);
668  oldTail->next.store(newNode.get());
669  m_tail.store(newNode.release());
670  }
671 }
672 
673 template <typename T, typename M, typename Alloc>
674 template <typename... Us>
675 void rcu_list<T, M, Alloc>::emplace_back(Us &&... vs)
676 {
677  auto newNode = detail::allocate_unique<node>(m_node_alloc, std::forward<Us>(vs)...);
678 
679  node *oldTail = m_tail.load(std::memory_order_relaxed);
680 
681  if (oldTail == nullptr) {
682  m_head.store(newNode.get());
683  m_tail.store(newNode.release());
684  } else {
685  newNode->back.store(oldTail);
686  oldTail->next.store(newNode.get());
687  m_tail.store(newNode.release());
688  }
689 }
690 
691 template <typename T, typename M, typename Alloc>
692 auto rcu_list<T, M, Alloc>::erase(const_iterator iter) -> iterator
693 {
694  // make sure the node has not already been marked for deletion
695  node *oldNext = iter.m_current->next.load();
696 
697  if (! iter.m_current->deleted) {
698  iter.m_current->deleted = true;
699 
700  node *oldPrev = iter.m_current->back.load();
701 
702  if (oldPrev) {
703  oldPrev->next.store(oldNext);
704  } else {
705  // no previous node, this node was the head
706  m_head.store(oldNext);
707  }
708 
709  if (oldNext) {
710  oldNext->back.store(oldPrev);
711  } else {
712  // no next node, this node was the tail
713  m_tail.store(oldPrev);
714  }
715 
716  auto newZombie = zombie_alloc_trait::allocate(m_zombie_alloc, 1);
717  zombie_alloc_trait::construct(m_zombie_alloc, newZombie, iter.m_current);
718 
719  zombie_list_node *oldZombie = m_zombie_head.load();
720 
721  do {
722  newZombie->next = oldZombie;
723  } while (! m_zombie_head.compare_exchange_weak(oldZombie, newZombie));
724  }
725 
726  return iterator(oldNext);
727 }
728 
729 template <typename T>
730 using SharedList = rcu_guarded<rcu_list<T>>;
731 
732 } // namespace libguarded
733 
734 #endif