. /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   18324 intrusive_list() = default; 47   11346 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   17 bool empty() const noexcept 61   21 bool empty() const noexcept
62   { 62   {
HITCBC 63   17 return head_ == nullptr; 63   21 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   30125 void push_front(T* w) noexcept 72   29886 void push_front(T* w) noexcept
73   { 73   {
HITCBC 74   30125 auto* n = static_cast<node*>(w); 74   29886 auto* n = static_cast<node*>(w);
HITCBC 75   30125 n->prev_ = nullptr; 75   29886 n->prev_ = nullptr;
HITCBC 76   30125 n->next_ = head_; 76   29886 n->next_ = head_;
HITCBC 77   30125 if (head_) 77   29886 if (head_)
HITCBC 78   16910 static_cast<node*>(head_)->prev_ = w; 78   16581 static_cast<node*>(head_)->prev_ = w;
79   else 79   else
HITCBC 80   13215 tail_ = w; 80   13305 tail_ = w;
HITCBC 81   30125 head_ = w; 81   29886 head_ = w;
HITCBC 82   30125 } 82   29886 }
83   83  
HITCBC 84   74300 void push_back(T* w) noexcept 84   72667 void push_back(T* w) noexcept
85   { 85   {
HITCBC 86   74300 auto* n = static_cast<node*>(w); 86   72667 auto* n = static_cast<node*>(w);
HITCBC 87   74300 n->next_ = nullptr; 87   72667 n->next_ = nullptr;
HITCBC 88   74300 n->prev_ = tail_; 88   72667 n->prev_ = tail_;
HITCBC 89   74300 if (tail_) 89   72667 if (tail_)
HITCBC 90   53621 static_cast<node*>(tail_)->next_ = w; 90   52416 static_cast<node*>(tail_)->next_ = w;
91   else 91   else
HITCBC 92   20679 head_ = w; 92   20251 head_ = w;
HITCBC 93   74300 tail_ = w; 93   72667 tail_ = w;
HITCBC 94   74300 } 94   72667 }
95   95  
HITCBC 96   3 void splice_back(intrusive_list& other) noexcept 96   3 void splice_back(intrusive_list& other) noexcept
97   { 97   {
HITCBC 98   3 if (other.empty()) 98   3 if (other.empty())
HITCBC 99   1 return; 99   1 return;
HITCBC 100   2 if (tail_) 100   2 if (tail_)
101   { 101   {
HITCBC 102   1 static_cast<node*>(tail_)->next_ = other.head_; 102   1 static_cast<node*>(tail_)->next_ = other.head_;
HITCBC 103   1 static_cast<node*>(other.head_)->prev_ = tail_; 103   1 static_cast<node*>(other.head_)->prev_ = tail_;
HITCBC 104   1 tail_ = other.tail_; 104   1 tail_ = other.tail_;
105   } 105   }
106   else 106   else
107   { 107   {
HITCBC 108   1 head_ = other.head_; 108   1 head_ = other.head_;
HITCBC 109   1 tail_ = other.tail_; 109   1 tail_ = other.tail_;
110   } 110   }
HITCBC 111   2 other.head_ = nullptr; 111   2 other.head_ = nullptr;
HITCBC 112   2 other.tail_ = nullptr; 112   2 other.tail_ = nullptr;
113   } 113   }
114   114  
HITCBC 115   242126 T* pop_front() noexcept 115   113154 T* pop_front() noexcept
116   { 116   {
HITCBC 117   242126 if (!head_) 117   113154 if (!head_)
HITCBC 118   192194 return nullptr; 118   64694 return nullptr;
HITCBC 119   49932 T* w = head_; 119   48460 T* w = head_;
HITCBC 120   49932 head_ = static_cast<node*>(head_)->next_; 120   48460 head_ = static_cast<node*>(head_)->next_;
HITCBC 121   49932 if (head_) 121   48460 if (head_)
HITCBC 122   26369 static_cast<node*>(head_)->prev_ = nullptr; 122   24993 static_cast<node*>(head_)->prev_ = nullptr;
123   else 123   else
HITCBC 124   23563 tail_ = nullptr; 124   23467 tail_ = nullptr;
125   // Defensive: clear stale linkage so remove() on a 125   // Defensive: clear stale linkage so remove() on a
126   // popped node cannot corrupt the list. 126   // popped node cannot corrupt the list.
HITCBC 127   49932 auto* n = static_cast<node*>(w); 127   48460 auto* n = static_cast<node*>(w);
HITCBC 128   49932 n->next_ = nullptr; 128   48460 n->next_ = nullptr;
HITCBC 129   49932 n->prev_ = nullptr; 129   48460 n->prev_ = nullptr;
HITCBC 130   49932 return w; 130   48460 return w;
131   } 131   }
132   132  
133   /** Unlink @p w if it is a member of this list. 133   /** Unlink @p w if it is a member of this list.
134   134  
135   @pre @p w is either a genuine member of `*this` list, or is 135   @pre @p w is either a genuine member of `*this` list, or is
136   fully detached (not linked in *any* `intrusive_list<T>`, 136   fully detached (not linked in *any* `intrusive_list<T>`,
137   including a different instance over the same `T`). This is 137   including a different instance over the same `T`). This is
138   not a membership test: `T::node` holds one shared `next_`/ 138   not a membership test: `T::node` holds one shared `next_`/
139   `prev_` pair regardless of which list currently owns it, so a 139   `prev_` pair regardless of which list currently owns it, so a
140   node actually linked in a different list looks "not detached" 140   node actually linked in a different list looks "not detached"
141   here and would be spliced out using *this* list's `head_`/ 141   here and would be spliced out using *this* list's `head_`/
142   `tail_` for the boundary cases — corrupting both lists. A 142   `tail_` for the boundary cases — corrupting both lists. A
143   caller that cannot rule that out needs its own bookkeeping 143   caller that cannot rule that out needs its own bookkeeping
144   (e.g. a flag for which list currently owns the node) before 144   (e.g. a flag for which list currently owns the node) before
145   calling this. 145   calling this.
146   146  
147   @return True if @p w was linked in and has now been removed; 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 148   false if it was already detached (e.g. a reentrant call from
149   a self-referential keepalive dropping during the same 149   a self-referential keepalive dropping during the same
150   teardown that already popped it elsewhere). Callers that gate 150   teardown that already popped it elsewhere). Callers that gate
151   a one-time action (recycling, deleting) on actually having 151   a one-time action (recycling, deleting) on actually having
152   removed something rely on this to make that action idempotent. 152   removed something rely on this to make that action idempotent.
153   */ 153   */
HITCBC 154   54492 bool remove(T* w) noexcept 154   54092 bool remove(T* w) noexcept
155   { 155   {
HITCBC 156   54492 auto* n = static_cast<node*>(w); 156   54092 auto* n = static_cast<node*>(w);
157   // Already detached — nothing to do. 157   // Already detached — nothing to do.
HITCBC 158   54492 if (!n->next_ && !n->prev_ && head_ != w && tail_ != w) 158   54092 if (!n->next_ && !n->prev_ && head_ != w && tail_ != w)
HITCBC 159   2 return false; 159   2 return false;
HITCBC 160   54490 if (n->prev_) 160   54090 if (n->prev_)
HITCBC 161   21424 static_cast<node*>(n->prev_)->next_ = n->next_; 161   21108 static_cast<node*>(n->prev_)->next_ = n->next_;
162   else 162   else
HITCBC 163   33066 head_ = n->next_; 163   32982 head_ = n->next_;
HITCBC 164   54490 if (n->next_) 164   54090 if (n->next_)
HITCBC 165   33258 static_cast<node*>(n->next_)->prev_ = n->prev_; 165   33102 static_cast<node*>(n->next_)->prev_ = n->prev_;
166   else 166   else
HITCBC 167   21232 tail_ = n->prev_; 167   20988 tail_ = n->prev_;
HITCBC 168   54490 n->next_ = nullptr; 168   54090 n->next_ = nullptr;
HITCBC 169   54490 n->prev_ = nullptr; 169   54090 n->prev_ = nullptr;
HITCBC 170   54490 return true; 170   54090 return true;
171   } 171   }
172   172  
173   /// Invoke @p f for each element in the list. 173   /// Invoke @p f for each element in the list.
174   template<class F> 174   template<class F>
HITCBC 175   27399 void for_each(F f) 175   11579 void for_each(F f)
176   { 176   {
HITCBC 177   45893 for (T* p = head_; p; p = static_cast<node*>(p)->next_) 177   30025 for (T* p = head_; p; p = static_cast<node*>(p)->next_)
HITCBC 178   18494 f(p); 178   18446 f(p);
HITCBC 179   27399 } 179   11579 }
180   }; 180   };
181   181  
182   /** An intrusive singly linked FIFO queue. 182   /** An intrusive singly linked FIFO queue.
183   183  
184   This container provides O(1) push and pop operations for 184   This container provides O(1) push and pop operations for
185   elements that derive from @ref node. Elements are not 185   elements that derive from @ref node. Elements are not
186   copied or moved; they are linked directly into the queue. 186   copied or moved; they are linked directly into the queue.
187   187  
188   Unlike @ref intrusive_list, this uses only a single `next_` 188   Unlike @ref intrusive_list, this uses only a single `next_`
189   pointer per node, saving memory at the cost of not supporting 189   pointer per node, saving memory at the cost of not supporting
190   O(1) removal of arbitrary elements. 190   O(1) removal of arbitrary elements.
191   191  
192   @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`.
193   */ 193   */
194   template<class T> 194   template<class T>
195   class intrusive_queue 195   class intrusive_queue
196   { 196   {
197   public: 197   public:
198   /** Base class for queue elements. 198   /** Base class for queue elements.
199   199  
200   Derive from this class to make a type usable with 200   Derive from this class to make a type usable with
201   @ref intrusive_queue. The `next_` pointer is private 201   @ref intrusive_queue. The `next_` pointer is private
202   and accessible only to the queue. 202   and accessible only to the queue.
203   */ 203   */
204   class node 204   class node
205   { 205   {
206   friend class intrusive_queue; 206   friend class intrusive_queue;
207   207  
208   private: 208   private:
209   T* next_ = nullptr; 209   T* next_ = nullptr;
210   }; 210   };
211   211  
212   private: 212   private:
213   T* head_ = nullptr; 213   T* head_ = nullptr;
214   T* tail_ = nullptr; 214   T* tail_ = nullptr;
215   215  
216   public: 216   public:
HITCBC 217   4421 intrusive_queue() = default; 217   4430 intrusive_queue() = default;
218   218  
HITCBC 219   1 intrusive_queue(intrusive_queue&& other) noexcept 219   1 intrusive_queue(intrusive_queue&& other) noexcept
HITCBC 220   1 : head_(other.head_) 220   1 : head_(other.head_)
HITCBC 221   1 , tail_(other.tail_) 221   1 , tail_(other.tail_)
222   { 222   {
HITCBC 223   1 other.head_ = nullptr; 223   1 other.head_ = nullptr;
HITCBC 224   1 other.tail_ = nullptr; 224   1 other.tail_ = nullptr;
HITCBC 225   1 } 225   1 }
226   226  
227   intrusive_queue(intrusive_queue const&) = delete; 227   intrusive_queue(intrusive_queue const&) = delete;
228   intrusive_queue& operator=(intrusive_queue const&) = delete; 228   intrusive_queue& operator=(intrusive_queue const&) = delete;
229   intrusive_queue& operator=(intrusive_queue&&) = delete; 229   intrusive_queue& operator=(intrusive_queue&&) = delete;
230   230  
HITCBC 231   6654 bool empty() const noexcept 231   6697 bool empty() const noexcept
232   { 232   {
HITCBC 233   6654 return head_ == nullptr; 233   6697 return head_ == nullptr;
234   } 234   }
235   235  
HITCBC 236   5076 void push(T* w) noexcept 236   3677 void push(T* w) noexcept
237   { 237   {
HITCBC 238   5076 w->next_ = nullptr; 238   3677 w->next_ = nullptr;
HITCBC 239   5076 if (tail_) 239   3677 if (tail_)
HITCBC 240   4071 tail_->next_ = w; 240   2646 tail_->next_ = w;
241   else 241   else
HITCBC 242   1005 head_ = w; 242   1031 head_ = w;
HITCBC 243   5076 tail_ = w; 243   3677 tail_ = w;
HITCBC 244   5076 } 244   3677 }
245   245  
HITCBC 246   4441 void splice(intrusive_queue& other) noexcept 246   4450 void splice(intrusive_queue& other) noexcept
247   { 247   {
HITCBC 248   4441 if (other.empty()) 248   4450 if (other.empty())
HITCBC 249   4418 return; 249   4427 return;
HITCBC 250   23 if (tail_) 250   23 if (tail_)
HITCBC 251   1 tail_->next_ = other.head_; 251   1 tail_->next_ = other.head_;
252   else 252   else
HITCBC 253   22 head_ = other.head_; 253   22 head_ = other.head_;
HITCBC 254   23 tail_ = other.tail_; 254   23 tail_ = other.tail_;
HITCBC 255   23 other.head_ = nullptr; 255   23 other.head_ = nullptr;
HITCBC 256   23 other.tail_ = nullptr; 256   23 other.tail_ = nullptr;
257   } 257   }
258   258  
HITCBC 259   9515 T* pop() noexcept 259   8125 T* pop() noexcept
260   { 260   {
HITCBC 261   9515 if (!head_) 261   8125 if (!head_)
HITCBC 262   4439 return nullptr; 262   4448 return nullptr;
HITCBC 263   5076 T* w = head_; 263   3677 T* w = head_;
HITCBC 264   5076 head_ = head_->next_; 264   3677 head_ = head_->next_;
HITCBC 265   5076 if (!head_) 265   3677 if (!head_)
HITCBC 266   1004 tail_ = nullptr; 266   1030 tail_ = nullptr;
267   // Defensive: clear stale linkage on popped node. 267   // Defensive: clear stale linkage on popped node.
HITCBC 268   5076 w->next_ = nullptr; 268   3677 w->next_ = nullptr;
HITCBC 269   5076 return w; 269   3677 return w;
270   } 270   }
271   }; 271   };
272   272  
273   } // namespace boost::corosio::detail 273   } // namespace boost::corosio::detail
274   274  
275   #endif 275   #endif