. /include/boost/corosio /detail /intrusive.hpp
100.00% Lines (93/93) 100.00% Functions (15/15)
[ ] prev/next file n p prev/next uncovered line
TLA Baseline Branch
Line Hits Code Line Hits Code
1   // 1   //
2   // Copyright (c) 2025 Vinnie Falco (vinnie.falco@gmail.com) 2   // Copyright (c) 2025 Vinnie Falco (vinnie.falco@gmail.com)
3   // 3   //
4   // Distributed under the Boost Software License, Version 1.0. (See accompanying 4   // Distributed under the Boost Software License, Version 1.0. (See accompanying
5   // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) 5   // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6   // 6   //
7   // Official repository: https://github.com/cppalliance/corosio 7   // Official repository: https://github.com/cppalliance/corosio
8   // 8   //
9   9  
10   #ifndef BOOST_COROSIO_DETAIL_INTRUSIVE_HPP 10   #ifndef BOOST_COROSIO_DETAIL_INTRUSIVE_HPP
11   #define BOOST_COROSIO_DETAIL_INTRUSIVE_HPP 11   #define BOOST_COROSIO_DETAIL_INTRUSIVE_HPP
12   12  
13   namespace boost::corosio::detail { 13   namespace boost::corosio::detail {
14   14  
15   /** An intrusive doubly linked list. 15   /** An intrusive doubly linked list.
16   16  
17   This container provides O(1) push and pop operations for 17   This container provides O(1) push and pop operations for
18   elements that derive from @ref node. Elements are not 18   elements that derive from @ref node. Elements are not
19   copied or moved; they are linked directly into the list. 19   copied or moved; they are linked directly into the list.
20   20  
21   @tparam T The element type. Must derive from `intrusive_list<T>::node`. 21   @tparam T The element type. Must derive from `intrusive_list<T>::node`.
22   */ 22   */
23   template<class T> 23   template<class T>
24   class intrusive_list 24   class intrusive_list
25   { 25   {
26   public: 26   public:
27   /** Base class for list elements. 27   /** Base class for list elements.
28   28  
29   Derive from this class to make a type usable with 29   Derive from this class to make a type usable with
30   @ref intrusive_list. The `next_` and `prev_` pointers 30   @ref intrusive_list. The `next_` and `prev_` pointers
31   are private and accessible only to the list. 31   are private and accessible only to the list.
32   */ 32   */
33   class node 33   class node
34   { 34   {
35   friend class intrusive_list; 35   friend class intrusive_list;
36   36  
37   private: 37   private:
38   T* next_ = nullptr; 38   T* next_ = nullptr;
39   T* prev_ = nullptr; 39   T* prev_ = nullptr;
40   }; 40   };
41   41  
42   private: 42   private:
43   T* head_ = nullptr; 43   T* head_ = nullptr;
44   T* tail_ = nullptr; 44   T* tail_ = nullptr;
45   45  
46   public: 46   public:
HITCBC 47   3430 intrusive_list() = default; 47   3430 intrusive_list() = default;
48   48  
HITCBC 49   1 intrusive_list(intrusive_list&& other) noexcept 49   1 intrusive_list(intrusive_list&& other) noexcept
HITCBC 50   1 : head_(other.head_) 50   1 : head_(other.head_)
HITCBC 51   1 , tail_(other.tail_) 51   1 , tail_(other.tail_)
52   { 52   {
HITCBC 53   1 other.head_ = nullptr; 53   1 other.head_ = nullptr;
HITCBC 54   1 other.tail_ = nullptr; 54   1 other.tail_ = nullptr;
HITCBC 55   1 } 55   1 }
56   56  
57   intrusive_list(intrusive_list const&) = delete; 57   intrusive_list(intrusive_list const&) = delete;
58   intrusive_list& operator=(intrusive_list const&) = delete; 58   intrusive_list& operator=(intrusive_list const&) = delete;
59   intrusive_list& operator=(intrusive_list&&) = delete; 59   intrusive_list& operator=(intrusive_list&&) = delete;
60   60  
HITCBC 61   12 bool empty() const noexcept 61   12 bool empty() const noexcept
62   { 62   {
HITCBC 63   12 return head_ == nullptr; 63   12 return head_ == nullptr;
64   } 64   }
65   65  
66   /// Peek at the head element without removing it. 66   /// Peek at the head element without removing it.
HITCBC 67   6 T* front() const noexcept 67   6 T* front() const noexcept
68   { 68   {
HITCBC 69   6 return head_; 69   6 return head_;
70   } 70   }
71   71  
HITCBC 72   34983 void push_back(T* w) noexcept 72   34034 void push_back(T* w) noexcept
73   { 73   {
HITCBC 74   34983 auto* n = static_cast<node*>(w); 74   34034 auto* n = static_cast<node*>(w);
HITCBC 75   34983 n->next_ = nullptr; 75   34034 n->next_ = nullptr;
HITCBC 76   34983 n->prev_ = tail_; 76   34034 n->prev_ = tail_;
HITCBC 77   34983 if (tail_) 77   34034 if (tail_)
HITCBC 78   22114 static_cast<node*>(tail_)->next_ = w; 78   21281 static_cast<node*>(tail_)->next_ = w;
79   else 79   else
HITCBC 80   12869 head_ = w; 80   12753 head_ = w;
HITCBC 81   34983 tail_ = w; 81   34034 tail_ = w;
HITCBC 82   34983 } 82   34034 }
83   83  
HITCBC 84   3 void splice_back(intrusive_list& other) noexcept 84   3 void splice_back(intrusive_list& other) noexcept
85   { 85   {
HITCBC 86   3 if (other.empty()) 86   3 if (other.empty())
HITCBC 87   1 return; 87   1 return;
HITCBC 88   2 if (tail_) 88   2 if (tail_)
89   { 89   {
HITCBC 90   1 static_cast<node*>(tail_)->next_ = other.head_; 90   1 static_cast<node*>(tail_)->next_ = other.head_;
HITCBC 91   1 static_cast<node*>(other.head_)->prev_ = tail_; 91   1 static_cast<node*>(other.head_)->prev_ = tail_;
HITCBC 92   1 tail_ = other.tail_; 92   1 tail_ = other.tail_;
93   } 93   }
94   else 94   else
95   { 95   {
HITCBC 96   1 head_ = other.head_; 96   1 head_ = other.head_;
HITCBC 97   1 tail_ = other.tail_; 97   1 tail_ = other.tail_;
98   } 98   }
HITCBC 99   2 other.head_ = nullptr; 99   2 other.head_ = nullptr;
HITCBC 100   2 other.tail_ = nullptr; 100   2 other.tail_ = nullptr;
101   } 101   }
102   102  
HITCBC 103   62241 T* pop_front() noexcept 103   59284 T* pop_front() noexcept
104   { 104   {
HITCBC 105   62241 if (!head_) 105   59284 if (!head_)
HITCBC 106   44822 return nullptr; 106   42646 return nullptr;
HITCBC 107   17419 T* w = head_; 107   16638 T* w = head_;
HITCBC 108   17419 head_ = static_cast<node*>(head_)->next_; 108   16638 head_ = static_cast<node*>(head_)->next_;
HITCBC 109   17419 if (head_) 109   16638 if (head_)
HITCBC 110   7862 static_cast<node*>(head_)->prev_ = nullptr; 110   7197 static_cast<node*>(head_)->prev_ = nullptr;
111   else 111   else
HITCBC 112   9557 tail_ = nullptr; 112   9441 tail_ = nullptr;
113   // Defensive: clear stale linkage so remove() on a 113   // Defensive: clear stale linkage so remove() on a
114   // popped node cannot corrupt the list. 114   // popped node cannot corrupt the list.
HITCBC 115   17419 auto* n = static_cast<node*>(w); 115   16638 auto* n = static_cast<node*>(w);
HITCBC 116   17419 n->next_ = nullptr; 116   16638 n->next_ = nullptr;
HITCBC 117   17419 n->prev_ = nullptr; 117   16638 n->prev_ = nullptr;
HITCBC 118   17419 return w; 118   16638 return w;
119   } 119   }
120   120  
HITCBC 121   17562 void remove(T* w) noexcept 121   17394 void remove(T* w) noexcept
122   { 122   {
HITCBC 123   17562 auto* n = static_cast<node*>(w); 123   17394 auto* n = static_cast<node*>(w);
124   // Already detached — nothing to do. 124   // Already detached — nothing to do.
HITCBC 125   17562 if (!n->next_ && !n->prev_ && head_ != w && tail_ != w) 125   17394 if (!n->next_ && !n->prev_ && head_ != w && tail_ != w)
HITCBC 126   1 return; 126   1 return;
HITCBC 127   17561 if (n->prev_) 127   17393 if (n->prev_)
HITCBC 128   4875 static_cast<node*>(n->prev_)->next_ = n->next_; 128   4818 static_cast<node*>(n->prev_)->next_ = n->next_;
129   else 129   else
HITCBC 130   12686 head_ = n->next_; 130   12575 head_ = n->next_;
HITCBC 131   17561 if (n->next_) 131   17393 if (n->next_)
HITCBC 132   9510 static_cast<node*>(n->next_)->prev_ = n->prev_; 132   9397 static_cast<node*>(n->next_)->prev_ = n->prev_;
133   else 133   else
HITCBC 134   8051 tail_ = n->prev_; 134   7996 tail_ = n->prev_;
HITCBC 135   17561 n->next_ = nullptr; 135   17393 n->next_ = nullptr;
HITCBC 136   17561 n->prev_ = nullptr; 136   17393 n->prev_ = nullptr;
137   } 137   }
138   138  
139   /// Invoke @p f for each element in the list. 139   /// Invoke @p f for each element in the list.
140   template<class F> 140   template<class F>
HITCBC 141   652 void for_each(F f) 141   652 void for_each(F f)
142   { 142   {
HITCBC 143   663 for (T* p = head_; p; p = static_cast<node*>(p)->next_) 143   663 for (T* p = head_; p; p = static_cast<node*>(p)->next_)
HITCBC 144   11 f(p); 144   11 f(p);
HITCBC 145   652 } 145   652 }
146   }; 146   };
147   147  
148   /** An intrusive singly linked FIFO queue. 148   /** An intrusive singly linked FIFO queue.
149   149  
150   This container provides O(1) push and pop operations for 150   This container provides O(1) push and pop operations for
151   elements that derive from @ref node. Elements are not 151   elements that derive from @ref node. Elements are not
152   copied or moved; they are linked directly into the queue. 152   copied or moved; they are linked directly into the queue.
153   153  
154   Unlike @ref intrusive_list, this uses only a single `next_` 154   Unlike @ref intrusive_list, this uses only a single `next_`
155   pointer per node, saving memory at the cost of not supporting 155   pointer per node, saving memory at the cost of not supporting
156   O(1) removal of arbitrary elements. 156   O(1) removal of arbitrary elements.
157   157  
158   @tparam T The element type. Must derive from `intrusive_queue<T>::node`. 158   @tparam T The element type. Must derive from `intrusive_queue<T>::node`.
159   */ 159   */
160   template<class T> 160   template<class T>
161   class intrusive_queue 161   class intrusive_queue
162   { 162   {
163   public: 163   public:
164   /** Base class for queue elements. 164   /** Base class for queue elements.
165   165  
166   Derive from this class to make a type usable with 166   Derive from this class to make a type usable with
167   @ref intrusive_queue. The `next_` pointer is private 167   @ref intrusive_queue. The `next_` pointer is private
168   and accessible only to the queue. 168   and accessible only to the queue.
169   */ 169   */
170   class node 170   class node
171   { 171   {
172   friend class intrusive_queue; 172   friend class intrusive_queue;
173   173  
174   private: 174   private:
175   T* next_ = nullptr; 175   T* next_ = nullptr;
176   }; 176   };
177   177  
178   private: 178   private:
179   T* head_ = nullptr; 179   T* head_ = nullptr;
180   T* tail_ = nullptr; 180   T* tail_ = nullptr;
181   181  
182   public: 182   public:
HITCBC 183   2788 intrusive_queue() = default; 183   2788 intrusive_queue() = default;
184   184  
HITCBC 185   1 intrusive_queue(intrusive_queue&& other) noexcept 185   1 intrusive_queue(intrusive_queue&& other) noexcept
HITCBC 186   1 : head_(other.head_) 186   1 : head_(other.head_)
HITCBC 187   1 , tail_(other.tail_) 187   1 , tail_(other.tail_)
188   { 188   {
HITCBC 189   1 other.head_ = nullptr; 189   1 other.head_ = nullptr;
HITCBC 190   1 other.tail_ = nullptr; 190   1 other.tail_ = nullptr;
HITCBC 191   1 } 191   1 }
192   192  
193   intrusive_queue(intrusive_queue const&) = delete; 193   intrusive_queue(intrusive_queue const&) = delete;
194   intrusive_queue& operator=(intrusive_queue const&) = delete; 194   intrusive_queue& operator=(intrusive_queue const&) = delete;
195   intrusive_queue& operator=(intrusive_queue&&) = delete; 195   intrusive_queue& operator=(intrusive_queue&&) = delete;
196   196  
HITCBC 197   1932 bool empty() const noexcept 197   1931 bool empty() const noexcept
198   { 198   {
HITCBC 199   1932 return head_ == nullptr; 199   1931 return head_ == nullptr;
200   } 200   }
201   201  
HITCBC 202   1134 void push(T* w) noexcept 202   1182 void push(T* w) noexcept
203   { 203   {
HITCBC 204   1134 w->next_ = nullptr; 204   1182 w->next_ = nullptr;
HITCBC 205   1134 if (tail_) 205   1182 if (tail_)
HITCBC 206   268 tail_->next_ = w; 206   266 tail_->next_ = w;
207   else 207   else
HITCBC 208   866 head_ = w; 208   916 head_ = w;
HITCBC 209   1134 tail_ = w; 209   1182 tail_ = w;
HITCBC 210   1134 } 210   1182 }
211   211  
HITCBC 212   3 void splice(intrusive_queue& other) noexcept 212   3 void splice(intrusive_queue& other) noexcept
213   { 213   {
HITCBC 214   3 if (other.empty()) 214   3 if (other.empty())
HITCBC 215   1 return; 215   1 return;
HITCBC 216   2 if (tail_) 216   2 if (tail_)
HITCBC 217   1 tail_->next_ = other.head_; 217   1 tail_->next_ = other.head_;
218   else 218   else
HITCBC 219   1 head_ = other.head_; 219   1 head_ = other.head_;
HITCBC 220   2 tail_ = other.tail_; 220   2 tail_ = other.tail_;
HITCBC 221   2 other.head_ = nullptr; 221   2 other.head_ = nullptr;
HITCBC 222   2 other.tail_ = nullptr; 222   2 other.tail_ = nullptr;
223   } 223   }
224   224  
HITCBC 225   4625 T* pop() noexcept 225   4673 T* pop() noexcept
226   { 226   {
HITCBC 227   4625 if (!head_) 227   4673 if (!head_)
HITCBC 228   3491 return nullptr; 228   3491 return nullptr;
HITCBC 229   1134 T* w = head_; 229   1182 T* w = head_;
HITCBC 230   1134 head_ = head_->next_; 230   1182 head_ = head_->next_;
HITCBC 231   1134 if (!head_) 231   1182 if (!head_)
HITCBC 232   865 tail_ = nullptr; 232   915 tail_ = nullptr;
233   // Defensive: clear stale linkage on popped node. 233   // Defensive: clear stale linkage on popped node.
HITCBC 234   1134 w->next_ = nullptr; 234   1182 w->next_ = nullptr;
HITCBC 235   1134 return w; 235   1182 return w;
236   } 236   }
237   }; 237   };
238   238  
239   } // namespace boost::corosio::detail 239   } // namespace boost::corosio::detail
240   240  
241   #endif 241   #endif