. /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   14180 intrusive_list() = default; 47   14420 intrusive_list() = default;
48   48  
HITGIC 49   intrusive_list(intrusive_list&& other) noexcept 49   1 intrusive_list(intrusive_list&& other) noexcept
HITGIC 50   : head_(other.head_) 50   1 : head_(other.head_)
HITGIC 51   , tail_(other.tail_) 51   1 , tail_(other.tail_)
52   { 52   {
HITGIC 53   other.head_ = nullptr; 53   1 other.head_ = nullptr;
HITGIC 54   other.tail_ = nullptr; 54   1 other.tail_ = nullptr;
HITGIC 55   } 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  
HITGIC 61   bool empty() const noexcept 61   12 bool empty() const noexcept
62   { 62   {
HITGIC 63   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.
HITGIC 67   T* front() const noexcept 67   6 T* front() const noexcept
68   { 68   {
HITGIC 69   return head_; 69   6 return head_;
70   } 70   }
71   71  
HITCBC 72   31184 void push_back(T* w) noexcept 72   34532 void push_back(T* w) noexcept
73   { 73   {
HITCBC 74   31184 auto* n = static_cast<node*>(w); 74   34532 auto* n = static_cast<node*>(w);
HITCBC 75   31184 n->next_ = nullptr; 75   34532 n->next_ = nullptr;
HITCBC 76   31184 n->prev_ = tail_; 76   34532 n->prev_ = tail_;
HITCBC 77   31184 if (tail_) 77   34532 if (tail_)
HITCBC 78   22011 static_cast<node*>(tail_)->next_ = w; 78   24500 static_cast<node*>(tail_)->next_ = w;
79   else 79   else
HITCBC 80   9173 head_ = w; 80   10032 head_ = w;
HITCBC 81   31184 tail_ = w; 81   34532 tail_ = w;
HITCBC 82   31184 } 82   34532 }
83   83  
HITGIC 84   void splice_back(intrusive_list& other) noexcept 84   3 void splice_back(intrusive_list& other) noexcept
85   { 85   {
HITGIC 86   if (other.empty()) 86   3 if (other.empty())
HITGIC 87   return; 87   1 return;
HITGIC 88   if (tail_) 88   2 if (tail_)
89   { 89   {
HITGIC 90   static_cast<node*>(tail_)->next_ = other.head_; 90   1 static_cast<node*>(tail_)->next_ = other.head_;
HITGIC 91   static_cast<node*>(other.head_)->prev_ = tail_; 91   1 static_cast<node*>(other.head_)->prev_ = tail_;
HITGIC 92   tail_ = other.tail_; 92   1 tail_ = other.tail_;
93   } 93   }
94   else 94   else
95   { 95   {
HITGIC 96   head_ = other.head_; 96   1 head_ = other.head_;
HITGIC 97   tail_ = other.tail_; 97   1 tail_ = other.tail_;
98   } 98   }
HITGIC 99   other.head_ = nullptr; 99   2 other.head_ = nullptr;
HITGIC 100   other.tail_ = nullptr; 100   2 other.tail_ = nullptr;
101   } 101   }
102   102  
HITCBC 103   353398 T* pop_front() noexcept 103   302702 T* pop_front() noexcept
104   { 104   {
HITCBC 105   353398 if (!head_) 105   302702 if (!head_)
HITCBC 106   345758 return nullptr; 106   294217 return nullptr;
HITCBC 107   7640 T* w = head_; 107   8485 T* w = head_;
HITCBC 108   7640 head_ = static_cast<node*>(head_)->next_; 108   8485 head_ = static_cast<node*>(head_)->next_;
HITCBC 109   7640 if (head_) 109   8485 if (head_)
HITGBC 110   ✗ static_cast<node*>(head_)->prev_ = nullptr; 110   13 static_cast<node*>(head_)->prev_ = nullptr;
111   else 111   else
HITCBC 112   7640 tail_ = nullptr; 112   8472 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   7640 auto* n = static_cast<node*>(w); 115   8485 auto* n = static_cast<node*>(w);
HITCBC 116   7640 n->next_ = nullptr; 116   8485 n->next_ = nullptr;
HITCBC 117   7640 n->prev_ = nullptr; 117   8485 n->prev_ = nullptr;
HITCBC 118   7640 return w; 118   8485 return w;
119   } 119   }
120   120  
HITCBC 121   23544 void remove(T* w) noexcept 121   26045 void remove(T* w) noexcept
122   { 122   {
HITCBC 123   23544 auto* n = static_cast<node*>(w); 123   26045 auto* n = static_cast<node*>(w);
124   // Already detached — nothing to do. 124   // Already detached — nothing to do.
HITCBC 125   23544 if (!n->next_ && !n->prev_ && head_ != w && tail_ != w) 125   26045 if (!n->next_ && !n->prev_ && head_ != w && tail_ != w)
HITGBC 126   ✗ return; 126   1 return;
HITCBC 127   23544 if (n->prev_) 127   26044 if (n->prev_)
HITCBC 128   7311 static_cast<node*>(n->prev_)->next_ = n->next_; 128   8147 static_cast<node*>(n->prev_)->next_ = n->next_;
129   else 129   else
HITCBC 130   16233 head_ = n->next_; 130   17897 head_ = n->next_;
HITCBC 131   23544 if (n->next_) 131   26044 if (n->next_)
HITCBC 132   14783 static_cast<node*>(n->next_)->prev_ = n->prev_; 132   16423 static_cast<node*>(n->next_)->prev_ = n->prev_;
133   else 133   else
HITCBC 134   8761 tail_ = n->prev_; 134   9621 tail_ = n->prev_;
HITCBC 135   23544 n->next_ = nullptr; 135   26044 n->next_ = nullptr;
HITCBC 136   23544 n->prev_ = nullptr; 136   26044 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   227 void for_each(F f) 141   228 void for_each(F f)
142   { 142   {
HITCBC 143   227 for (T* p = head_; p; p = static_cast<node*>(p)->next_) 143   231 for (T* p = head_; p; p = static_cast<node*>(p)->next_)
HITGBC 144   ✗ f(p); 144   3 f(p);
HITCBC 145   227 } 145   228 }
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   1412 intrusive_queue() = default; 183   1436 intrusive_queue() = default;
184   184  
HITGIC 185   intrusive_queue(intrusive_queue&& other) noexcept 185   1 intrusive_queue(intrusive_queue&& other) noexcept
HITGIC 186   : head_(other.head_) 186   1 : head_(other.head_)
HITGIC 187   , tail_(other.tail_) 187   1 , tail_(other.tail_)
188   { 188   {
HITGIC 189   other.head_ = nullptr; 189   1 other.head_ = nullptr;
HITGIC 190   other.tail_ = nullptr; 190   1 other.tail_ = nullptr;
HITGIC 191   } 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   1740 bool empty() const noexcept 197   1140 bool empty() const noexcept
198   { 198   {
HITCBC 199   1740 return head_ == nullptr; 199   1140 return head_ == nullptr;
200   } 200   }
201   201  
HITCBC 202   382 void push(T* w) noexcept 202   391 void push(T* w) noexcept
203   { 203   {
HITCBC 204   382 w->next_ = nullptr; 204   391 w->next_ = nullptr;
HITCBC 205   382 if (tail_) 205   391 if (tail_)
HITCBC 206   183 tail_->next_ = w; 206   257 tail_->next_ = w;
207   else 207   else
HITCBC 208   199 head_ = w; 208   134 head_ = w;
HITCBC 209   382 tail_ = w; 209   391 tail_ = w;
HITCBC 210   382 } 210   391 }
211   211  
HITGIC 212   void splice(intrusive_queue& other) noexcept 212   3 void splice(intrusive_queue& other) noexcept
213   { 213   {
HITGIC 214   if (other.empty()) 214   3 if (other.empty())
HITGIC 215   return; 215   1 return;
HITGIC 216   if (tail_) 216   2 if (tail_)
HITGIC 217   tail_->next_ = other.head_; 217   1 tail_->next_ = other.head_;
218   else 218   else
HITGIC 219   head_ = other.head_; 219   1 head_ = other.head_;
HITGIC 220   tail_ = other.tail_; 220   2 tail_ = other.tail_;
HITGIC 221   other.head_ = nullptr; 221   2 other.head_ = nullptr;
HITGIC 222   other.tail_ = nullptr; 222   2 other.tail_ = nullptr;
223   } 223   }
224   224  
HITCBC 225   3217 T* pop() noexcept 225   3275 T* pop() noexcept
226   { 226   {
HITCBC 227   3217 if (!head_) 227   3275 if (!head_)
HITCBC 228   2835 return nullptr; 228   2884 return nullptr;
HITCBC 229   382 T* w = head_; 229   391 T* w = head_;
HITCBC 230   382 head_ = head_->next_; 230   391 head_ = head_->next_;
HITCBC 231   382 if (!head_) 231   391 if (!head_)
HITCBC 232   199 tail_ = nullptr; 232   133 tail_ = nullptr;
233   // Defensive: clear stale linkage on popped node. 233   // Defensive: clear stale linkage on popped node.
HITCBC 234   382 w->next_ = nullptr; 234   391 w->next_ = nullptr;
HITCBC 235   382 return w; 235   391 return w;
236   } 236   }
237   }; 237   };
238   238  
239   } // namespace boost::corosio::detail 239   } // namespace boost::corosio::detail
240   240  
241   #endif 241   #endif