. /include/boost/corosio /detail /intrusive.hpp
95.59% Lines (65/68) 100.00% Functions (11/11)
[ ] 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   12913 intrusive_list() = default; 47   12913 intrusive_list() = default;
48   48  
49   intrusive_list(intrusive_list&& other) noexcept 49   intrusive_list(intrusive_list&& other) noexcept
50   : head_(other.head_) 50   : head_(other.head_)
51   , tail_(other.tail_) 51   , tail_(other.tail_)
52   { 52   {
53   other.head_ = nullptr; 53   other.head_ = nullptr;
54   other.tail_ = nullptr; 54   other.tail_ = nullptr;
55   } 55   }
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   38 bool empty() const noexcept 61   38 bool empty() const noexcept
62   { 62   {
HITCBC 63   38 return head_ == nullptr; 63   38 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.
67   T* front() const noexcept 67   T* front() const noexcept
68   { 68   {
69   return head_; 69   return head_;
70   } 70   }
71   71  
HITCBC 72   43830 void push_back(T* w) noexcept 72   43499 void push_back(T* w) noexcept
73   { 73   {
HITCBC 74   43830 auto* n = static_cast<node*>(w); 74   43499 auto* n = static_cast<node*>(w);
HITCBC 75   43830 n->next_ = nullptr; 75   43499 n->next_ = nullptr;
HITCBC 76   43830 n->prev_ = tail_; 76   43499 n->prev_ = tail_;
HITCBC 77   43830 if (tail_) 77   43499 if (tail_)
HITCBC 78   25072 static_cast<node*>(tail_)->next_ = w; 78   24868 static_cast<node*>(tail_)->next_ = w;
79   else 79   else
HITCBC 80   18758 head_ = w; 80   18631 head_ = w;
HITCBC 81   43830 tail_ = w; 81   43499 tail_ = w;
HITCBC 82   43830 } 82   43499 }
83   83  
84   void splice_back(intrusive_list& other) noexcept 84   void splice_back(intrusive_list& other) noexcept
85   { 85   {
86   if (other.empty()) 86   if (other.empty())
87   return; 87   return;
88   if (tail_) 88   if (tail_)
89   { 89   {
90   static_cast<node*>(tail_)->next_ = other.head_; 90   static_cast<node*>(tail_)->next_ = other.head_;
91   static_cast<node*>(other.head_)->prev_ = tail_; 91   static_cast<node*>(other.head_)->prev_ = tail_;
92   tail_ = other.tail_; 92   tail_ = other.tail_;
93   } 93   }
94   else 94   else
95   { 95   {
96   head_ = other.head_; 96   head_ = other.head_;
97   tail_ = other.tail_; 97   tail_ = other.tail_;
98   } 98   }
99   other.head_ = nullptr; 99   other.head_ = nullptr;
100   other.tail_ = nullptr; 100   other.tail_ = nullptr;
101   } 101   }
102   102  
HITCBC 103   299187 T* pop_front() noexcept 103   296632 T* pop_front() noexcept
104   { 104   {
HITCBC 105   299187 if (!head_) 105   296632 if (!head_)
HITCBC 106   281733 return nullptr; 106   279308 return nullptr;
HITCBC 107   17454 T* w = head_; 107   17324 T* w = head_;
HITCBC 108   17454 head_ = static_cast<node*>(head_)->next_; 108   17324 head_ = static_cast<node*>(head_)->next_;
HITCBC 109   17454 if (head_) 109   17324 if (head_)
HITCBC 110   43 static_cast<node*>(head_)->prev_ = nullptr; 110   40 static_cast<node*>(head_)->prev_ = nullptr;
111   else 111   else
HITCBC 112   17411 tail_ = nullptr; 112   17284 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   17454 auto* n = static_cast<node*>(w); 115   17324 auto* n = static_cast<node*>(w);
HITCBC 116   17454 n->next_ = nullptr; 116   17324 n->next_ = nullptr;
HITCBC 117   17454 n->prev_ = nullptr; 117   17324 n->prev_ = nullptr;
HITCBC 118   17454 return w; 118   17324 return w;
119   } 119   }
120   120  
HITCBC 121   26376 void remove(T* w) noexcept 121   26175 void remove(T* w) noexcept
122   { 122   {
HITCBC 123   26376 auto* n = static_cast<node*>(w); 123   26175 auto* n = static_cast<node*>(w);
124   // Already detached — nothing to do. 124   // Already detached — nothing to do.
HITCBC 125   26376 if (!n->next_ && !n->prev_ && head_ != w && tail_ != w) 125   26175 if (!n->next_ && !n->prev_ && head_ != w && tail_ != w)
MISUBC 126   ✗ return; 126   ✗ return;
HITCBC 127   26376 if (n->prev_) 127   26175 if (n->prev_)
HITCBC 128   8336 static_cast<node*>(n->prev_)->next_ = n->next_; 128   8270 static_cast<node*>(n->prev_)->next_ = n->next_;
129   else 129   else
HITCBC 130   18040 head_ = n->next_; 130   17905 head_ = n->next_;
HITCBC 131   26376 if (n->next_) 131   26175 if (n->next_)
HITCBC 132   16759 static_cast<node*>(n->next_)->prev_ = n->prev_; 132   16624 static_cast<node*>(n->next_)->prev_ = n->prev_;
133   else 133   else
HITCBC 134   9617 tail_ = n->prev_; 134   9551 tail_ = n->prev_;
HITCBC 135   26376 n->next_ = nullptr; 135   26175 n->next_ = nullptr;
HITCBC 136   26376 n->prev_ = nullptr; 136   26175 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   216 void for_each(F f) 141   216 void for_each(F f)
142   { 142   {
HITCBC 143   216 for (T* p = head_; p; p = static_cast<node*>(p)->next_) 143   216 for (T* p = head_; p; p = static_cast<node*>(p)->next_)
MISUBC 144   ✗ f(p); 144   ✗ f(p);
HITCBC 145   216 } 145   216 }
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   3352 intrusive_queue() = default; 183   3356 intrusive_queue() = default;
184   184  
185   intrusive_queue(intrusive_queue&& other) noexcept 185   intrusive_queue(intrusive_queue&& other) noexcept
186   : head_(other.head_) 186   : head_(other.head_)
187   , tail_(other.tail_) 187   , tail_(other.tail_)
188   { 188   {
189   other.head_ = nullptr; 189   other.head_ = nullptr;
190   other.tail_ = nullptr; 190   other.tail_ = nullptr;
191   } 191   }
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   2279644 bool empty() const noexcept 197   2266400 bool empty() const noexcept
198   { 198   {
HITCBC 199   2279644 return head_ == nullptr; 199   2266400 return head_ == nullptr;
200   } 200   }
201   201  
HITCBC 202   698546 void push(T* w) noexcept 202   693628 void push(T* w) noexcept
203   { 203   {
HITCBC 204   698546 w->next_ = nullptr; 204   693628 w->next_ = nullptr;
HITCBC 205   698546 if (tail_) 205   693628 if (tail_)
HITCBC 206   310139 tail_->next_ = w; 206   309221 tail_->next_ = w;
207   else 207   else
HITCBC 208   388407 head_ = w; 208   384407 head_ = w;
HITCBC 209   698546 tail_ = w; 209   693628 tail_ = w;
HITCBC 210   698546 } 210   693628 }
211   211  
HITCBC 212   362971 void splice(intrusive_queue& other) noexcept 212   358764 void splice(intrusive_queue& other) noexcept
213   { 213   {
HITCBC 214   362971 if (other.empty()) 214   358764 if (other.empty())
MISUBC 215   ✗ return; 215   ✗ return;
HITCBC 216   362971 if (tail_) 216   358764 if (tail_)
HITCBC 217   126172 tail_->next_ = other.head_; 217   121181 tail_->next_ = other.head_;
218   else 218   else
HITCBC 219   236799 head_ = other.head_; 219   237583 head_ = other.head_;
HITCBC 220   362971 tail_ = other.tail_; 220   358764 tail_ = other.tail_;
HITCBC 221   362971 other.head_ = nullptr; 221   358764 other.head_ = nullptr;
HITCBC 222   362971 other.tail_ = nullptr; 222   358764 other.tail_ = nullptr;
223   } 223   }
224   224  
HITCBC 225   959672 T* pop() noexcept 225   955867 T* pop() noexcept
226   { 226   {
HITCBC 227   959672 if (!head_) 227   955867 if (!head_)
HITCBC 228   261126 return nullptr; 228   262239 return nullptr;
HITCBC 229   698546 T* w = head_; 229   693628 T* w = head_;
HITCBC 230   698546 head_ = head_->next_; 230   693628 head_ = head_->next_;
HITCBC 231   698546 if (!head_) 231   693628 if (!head_)
HITCBC 232   262235 tail_ = nullptr; 232   263226 tail_ = nullptr;
233   // Defensive: clear stale linkage on popped node. 233   // Defensive: clear stale linkage on popped node.
HITCBC 234   698546 w->next_ = nullptr; 234   693628 w->next_ = nullptr;
HITCBC 235   698546 return w; 235   693628 return w;
236   } 236   }
237   }; 237   };
238   238  
239   } // namespace boost::corosio::detail 239   } // namespace boost::corosio::detail
240   240  
241   #endif 241   #endif