. /include/boost/corosio /detail /intrusive.hpp
100.00% Lines (103/103) 100.00% Functions (16/16)
[ ] 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   2862 intrusive_list() = default; 47   10576 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   16 bool empty() const noexcept
62   { 62   {
HITCBC 63   12 return head_ == nullptr; 63   16 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  
HITGNC   72 + 20476 void push_front(T* w) noexcept
  73 + {
HITGNC   74 + 20476 auto* n = static_cast<node*>(w);
HITGNC   75 + 20476 n->prev_ = nullptr;
HITGNC   76 + 20476 n->next_ = head_;
HITGNC   77 + 20476 if (head_)
HITGNC   78 + 12504 static_cast<node*>(head_)->prev_ = w;
  79 + else
HITGNC   80 + 7972 tail_ = w;
HITGNC   81 + 20476 head_ = w;
HITGNC   82 + 20476 }
  83 +
HITCBC 72   33373 void push_back(T* w) noexcept 84   55789 void push_back(T* w) noexcept
73   { 85   {
HITCBC 74   33373 auto* n = static_cast<node*>(w); 86   55789 auto* n = static_cast<node*>(w);
HITCBC 75   33373 n->next_ = nullptr; 87   55789 n->next_ = nullptr;
HITCBC 76   33373 n->prev_ = tail_; 88   55789 n->prev_ = tail_;
HITCBC 77   33373 if (tail_) 89   55789 if (tail_)
HITCBC 78   21178 static_cast<node*>(tail_)->next_ = w; 90   40606 static_cast<node*>(tail_)->next_ = w;
79   else 91   else
HITCBC 80   12195 head_ = w; 92   15183 head_ = w;
HITCBC 81   33373 tail_ = w; 93   55789 tail_ = w;
HITCBC 82   33373 } 94   55789 }
83   95  
HITCBC 84   3 void splice_back(intrusive_list& other) noexcept 96   3 void splice_back(intrusive_list& other) noexcept
85   { 97   {
HITCBC 86   3 if (other.empty()) 98   3 if (other.empty())
HITCBC 87   1 return; 99   1 return;
HITCBC 88   2 if (tail_) 100   2 if (tail_)
89   { 101   {
HITCBC 90   1 static_cast<node*>(tail_)->next_ = other.head_; 102   1 static_cast<node*>(tail_)->next_ = other.head_;
HITCBC 91   1 static_cast<node*>(other.head_)->prev_ = tail_; 103   1 static_cast<node*>(other.head_)->prev_ = tail_;
HITCBC 92   1 tail_ = other.tail_; 104   1 tail_ = other.tail_;
93   } 105   }
94   else 106   else
95   { 107   {
HITCBC 96   1 head_ = other.head_; 108   1 head_ = other.head_;
HITCBC 97   1 tail_ = other.tail_; 109   1 tail_ = other.tail_;
98   } 110   }
HITCBC 99   2 other.head_ = nullptr; 111   2 other.head_ = nullptr;
HITCBC 100   2 other.tail_ = nullptr; 112   2 other.tail_ = nullptr;
101   } 113   }
102   114  
HITCBC 103   321578 T* pop_front() noexcept 115   346627 T* pop_front() noexcept
104   { 116   {
HITCBC 105   321578 if (!head_) 117   346627 if (!head_)
HITCBC 106   305195 return nullptr; 118   306027 return nullptr;
HITCBC 107   16383 T* w = head_; 119   40600 T* w = head_;
HITCBC 108   16383 head_ = static_cast<node*>(head_)->next_; 120   40600 head_ = static_cast<node*>(head_)->next_;
HITCBC 109   16383 if (head_) 121   40600 if (head_)
HITCBC 110   6940 static_cast<node*>(head_)->prev_ = nullptr; 122   22167 static_cast<node*>(head_)->prev_ = nullptr;
111   else 123   else
HITCBC 112   9443 tail_ = nullptr; 124   18433 tail_ = nullptr;
113   // Defensive: clear stale linkage so remove() on a 125   // Defensive: clear stale linkage so remove() on a
114   // popped node cannot corrupt the list. 126   // popped node cannot corrupt the list.
HITCBC 115   16383 auto* n = static_cast<node*>(w); 127   40600 auto* n = static_cast<node*>(w);
HITCBC 116   16383 n->next_ = nullptr; 128   40600 n->next_ = nullptr;
HITCBC 117   16383 n->prev_ = nullptr; 129   40600 n->prev_ = nullptr;
HITCBC 118   16383 return w; 130   40600 return w;
119   } 131   }
120   132  
ECB 121 - 16988 void remove(T* w) noexcept 133 + /** Unlink @p w if it is a member of this list.
  134 +
  135 + @pre @p w is either a genuine member of `*this` list, or is
  136 + fully detached (not linked in *any* `intrusive_list<T>`,
  137 + including a different instance over the same `T`). This is
  138 + not a membership test: `T::node` holds one shared `next_`/
  139 + `prev_` pair regardless of which list currently owns it, so a
  140 + node actually linked in a different list looks "not detached"
  141 + here and would be spliced out using *this* list's `head_`/
  142 + `tail_` for the boundary cases — corrupting both lists. A
  143 + caller that cannot rule that out needs its own bookkeeping
  144 + (e.g. a flag for which list currently owns the node) before
  145 + calling this.
  146 +
  147 + @return True if @p w was linked in and has now been removed;
  148 + false if it was already detached (e.g. a reentrant call from
  149 + a self-referential keepalive dropping during the same
  150 + teardown that already popped it elsewhere). Callers that gate
  151 + a one-time action (recycling, deleting) on actually having
  152 + removed something rely on this to make that action idempotent.
  153 + */
HITGNC   154 + 35665 bool remove(T* w) noexcept
122   { 155   {
HITCBC 123   16988 auto* n = static_cast<node*>(w); 156   35665 auto* n = static_cast<node*>(w);
124   // Already detached — nothing to do. 157   // Already detached — nothing to do.
HITCBC 125   16988 if (!n->next_ && !n->prev_ && head_ != w && tail_ != w) 158   35665 if (!n->next_ && !n->prev_ && head_ != w && tail_ != w)
HITCBC 126 - 1 return; 159 + 3 return false;
HITCBC 127   16987 if (n->prev_) 160   35662 if (n->prev_)
HITCBC 128   4871 static_cast<node*>(n->prev_)->next_ = n->next_; 161   20020 static_cast<node*>(n->prev_)->next_ = n->next_;
129   else 162   else
HITCBC 130   12116 head_ = n->next_; 163   15642 head_ = n->next_;
HITCBC 131   16987 if (n->next_) 164   35662 if (n->next_)
HITCBC 132   9494 static_cast<node*>(n->next_)->prev_ = n->prev_; 165   20091 static_cast<node*>(n->next_)->prev_ = n->prev_;
133   else 166   else
HITCBC 134   7493 tail_ = n->prev_; 167   15571 tail_ = n->prev_;
HITCBC 135   16987 n->next_ = nullptr; 168   35662 n->next_ = nullptr;
HITCBC 136   16987 n->prev_ = nullptr; 169   35662 n->prev_ = nullptr;
HITGNC   170 + 35662 return true;
137   } 171   }
138   172  
139   /// Invoke @p f for each element in the list. 173   /// Invoke @p f for each element in the list.
140   template<class F> 174   template<class F>
HITCBC 141   625 void for_each(F f) 175   5710 void for_each(F f)
142   { 176   {
HITCBC 143   634 for (T* p = head_; p; p = static_cast<node*>(p)->next_) 177   6109 for (T* p = head_; p; p = static_cast<node*>(p)->next_)
HITCBC 144   9 f(p); 178   399 f(p);
HITCBC 145   625 } 179   5710 }
146   }; 180   };
147   181  
148   /** An intrusive singly linked FIFO queue. 182   /** An intrusive singly linked FIFO queue.
149   183  
150   This container provides O(1) push and pop operations for 184   This container provides O(1) push and pop operations for
151   elements that derive from @ref node. Elements are not 185   elements that derive from @ref node. Elements are not
152   copied or moved; they are linked directly into the queue. 186   copied or moved; they are linked directly into the queue.
153   187  
154   Unlike @ref intrusive_list, this uses only a single `next_` 188   Unlike @ref intrusive_list, this uses only a single `next_`
155   pointer per node, saving memory at the cost of not supporting 189   pointer per node, saving memory at the cost of not supporting
156   O(1) removal of arbitrary elements. 190   O(1) removal of arbitrary elements.
157   191  
158   @tparam T The element type. Must derive from `intrusive_queue<T>::node`. 192   @tparam T The element type. Must derive from `intrusive_queue<T>::node`.
159   */ 193   */
160   template<class T> 194   template<class T>
161   class intrusive_queue 195   class intrusive_queue
162   { 196   {
163   public: 197   public:
164   /** Base class for queue elements. 198   /** Base class for queue elements.
165   199  
166   Derive from this class to make a type usable with 200   Derive from this class to make a type usable with
167   @ref intrusive_queue. The `next_` pointer is private 201   @ref intrusive_queue. The `next_` pointer is private
168   and accessible only to the queue. 202   and accessible only to the queue.
169   */ 203   */
170   class node 204   class node
171   { 205   {
172   friend class intrusive_queue; 206   friend class intrusive_queue;
173   207  
174   private: 208   private:
175   T* next_ = nullptr; 209   T* next_ = nullptr;
176   }; 210   };
177   211  
178   private: 212   private:
179   T* head_ = nullptr; 213   T* head_ = nullptr;
180   T* tail_ = nullptr; 214   T* tail_ = nullptr;
181   215  
182   public: 216   public:
HITCBC 183   2246 intrusive_queue() = default; 217   2313 intrusive_queue() = default;
184   218  
HITCBC 185   1 intrusive_queue(intrusive_queue&& other) noexcept 219   1 intrusive_queue(intrusive_queue&& other) noexcept
HITCBC 186   1 : head_(other.head_) 220   1 : head_(other.head_)
HITCBC 187   1 , tail_(other.tail_) 221   1 , tail_(other.tail_)
188   { 222   {
HITCBC 189   1 other.head_ = nullptr; 223   1 other.head_ = nullptr;
HITCBC 190   1 other.tail_ = nullptr; 224   1 other.tail_ = nullptr;
HITCBC 191   1 } 225   1 }
192   226  
193   intrusive_queue(intrusive_queue const&) = delete; 227   intrusive_queue(intrusive_queue const&) = delete;
194   intrusive_queue& operator=(intrusive_queue const&) = delete; 228   intrusive_queue& operator=(intrusive_queue const&) = delete;
195   intrusive_queue& operator=(intrusive_queue&&) = delete; 229   intrusive_queue& operator=(intrusive_queue&&) = delete;
196   230  
HITCBC 197   1183 bool empty() const noexcept 231   1351 bool empty() const noexcept
198   { 232   {
HITCBC 199   1183 return head_ == nullptr; 233   1351 return head_ == nullptr;
200   } 234   }
201   235  
HITCBC 202   754 void push(T* w) noexcept 236   834 void push(T* w) noexcept
203   { 237   {
HITCBC 204   754 w->next_ = nullptr; 238   834 w->next_ = nullptr;
HITCBC 205   754 if (tail_) 239   834 if (tail_)
HITCBC 206   257 tail_->next_ = w; 240   262 tail_->next_ = w;
207   else 241   else
HITCBC 208   497 head_ = w; 242   572 head_ = w;
HITCBC 209   754 tail_ = w; 243   834 tail_ = w;
HITCBC 210   754 } 244   834 }
211   245  
HITCBC 212   3 void splice(intrusive_queue& other) noexcept 246   3 void splice(intrusive_queue& other) noexcept
213   { 247   {
HITCBC 214   3 if (other.empty()) 248   3 if (other.empty())
HITCBC 215   1 return; 249   1 return;
HITCBC 216   2 if (tail_) 250   2 if (tail_)
HITCBC 217   1 tail_->next_ = other.head_; 251   1 tail_->next_ = other.head_;
218   else 252   else
HITCBC 219   1 head_ = other.head_; 253   1 head_ = other.head_;
HITCBC 220   2 tail_ = other.tail_; 254   2 tail_ = other.tail_;
HITCBC 221   2 other.head_ = nullptr; 255   2 other.head_ = nullptr;
HITCBC 222   2 other.tail_ = nullptr; 256   2 other.tail_ = nullptr;
223   } 257   }
224   258  
HITCBC 225   3286 T* pop() noexcept 259   3446 T* pop() noexcept
226   { 260   {
HITCBC 227   3286 if (!head_) 261   3446 if (!head_)
HITCBC 228   2532 return nullptr; 262   2612 return nullptr;
HITCBC 229   754 T* w = head_; 263   834 T* w = head_;
HITCBC 230   754 head_ = head_->next_; 264   834 head_ = head_->next_;
HITCBC 231   754 if (!head_) 265   834 if (!head_)
HITCBC 232   496 tail_ = nullptr; 266   571 tail_ = nullptr;
233   // Defensive: clear stale linkage on popped node. 267   // Defensive: clear stale linkage on popped node.
HITCBC 234   754 w->next_ = nullptr; 268   834 w->next_ = nullptr;
HITCBC 235   754 return w; 269   834 return w;
236   } 270   }
237   }; 271   };
238   272  
239   } // namespace boost::corosio::detail 273   } // namespace boost::corosio::detail
240   274  
241   #endif 275   #endif