. /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_; 38   T* next_;
39   T* prev_; 39   T* prev_;
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   10606 intrusive_list() = default; 47   10606 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.
  67 + T* front() const noexcept
  68 + {
  69 + return head_;
  70 + }
  71 +
HITCBC 66   40428 void push_back(T* w) noexcept 72   19346 void push_back(T* w) noexcept
67   { 73   {
HITCBC 68   40428 auto* n = static_cast<node*>(w); 74   19346 auto* n = static_cast<node*>(w);
HITCBC 69   40428 n->next_ = nullptr; 75   19346 n->next_ = nullptr;
HITCBC 70   40428 n->prev_ = tail_; 76   19346 n->prev_ = tail_;
HITCBC 71   40428 if (tail_) 77   19346 if (tail_)
HITCBC 72   23124 static_cast<node*>(tail_)->next_ = w; 78   10505 static_cast<node*>(tail_)->next_ = w;
73   else 79   else
HITCBC 74   17304 head_ = w; 80   8841 head_ = w;
HITCBC 75   40428 tail_ = w; 81   19346 tail_ = w;
HITCBC 76   40428 } 82   19346 }
77   83  
78   void splice_back(intrusive_list& other) noexcept 84   void splice_back(intrusive_list& other) noexcept
79   { 85   {
80   if (other.empty()) 86   if (other.empty())
81   return; 87   return;
82   if (tail_) 88   if (tail_)
83   { 89   {
84   static_cast<node*>(tail_)->next_ = other.head_; 90   static_cast<node*>(tail_)->next_ = other.head_;
85   static_cast<node*>(other.head_)->prev_ = tail_; 91   static_cast<node*>(other.head_)->prev_ = tail_;
86   tail_ = other.tail_; 92   tail_ = other.tail_;
87   } 93   }
88   else 94   else
89   { 95   {
90   head_ = other.head_; 96   head_ = other.head_;
91   tail_ = other.tail_; 97   tail_ = other.tail_;
92   } 98   }
93   other.head_ = nullptr; 99   other.head_ = nullptr;
94   other.tail_ = nullptr; 100   other.tail_ = nullptr;
95   } 101   }
96   102  
HITCBC 97   267686 T* pop_front() noexcept 103   236981 T* pop_front() noexcept
98   { 104   {
HITCBC 99   267686 if (!head_) 105   236981 if (!head_)
HITCBC 100   251434 return nullptr; 106   229191 return nullptr;
HITCBC 101   16252 T* w = head_; 107   7790 T* w = head_;
HITCBC 102   16252 head_ = static_cast<node*>(head_)->next_; 108   7790 head_ = static_cast<node*>(head_)->next_;
HITCBC 103   16252 if (head_) 109   7790 if (head_)
HITCBC 104   40 static_cast<node*>(head_)->prev_ = nullptr; 110   41 static_cast<node*>(head_)->prev_ = nullptr;
105   else 111   else
HITCBC 106   16212 tail_ = nullptr; 112   7749 tail_ = nullptr;
107   // Defensive: clear stale linkage so remove() on a 113   // Defensive: clear stale linkage so remove() on a
108   // popped node cannot corrupt the list. 114   // popped node cannot corrupt the list.
HITCBC 109   16252 auto* n = static_cast<node*>(w); 115   7790 auto* n = static_cast<node*>(w);
HITCBC 110   16252 n->next_ = nullptr; 116   7790 n->next_ = nullptr;
HITCBC 111   16252 n->prev_ = nullptr; 117   7790 n->prev_ = nullptr;
HITCBC 112   16252 return w; 118   7790 return w;
113   } 119   }
114   120  
HITCBC 115   24176 void remove(T* w) noexcept 121   11556 void remove(T* w) noexcept
116   { 122   {
HITCBC 117   24176 auto* n = static_cast<node*>(w); 123   11556 auto* n = static_cast<node*>(w);
118   // Already detached — nothing to do. 124   // Already detached — nothing to do.
HITCBC 119   24176 if (!n->next_ && !n->prev_ && head_ != w && tail_ != w) 125   11556 if (!n->next_ && !n->prev_ && head_ != w && tail_ != w)
MISUBC 120   ✗ return; 126   ✗ return;
HITCBC 121   24176 if (n->prev_) 127   11556 if (n->prev_)
HITCBC 122   7699 static_cast<node*>(n->prev_)->next_ = n->next_; 128   3491 static_cast<node*>(n->prev_)->next_ = n->next_;
123   else 129   else
HITCBC 124   16477 head_ = n->next_; 130   8065 head_ = n->next_;
HITCBC 125   24176 if (n->next_) 131   11556 if (n->next_)
HITCBC 126   15432 static_cast<node*>(n->next_)->prev_ = n->prev_; 132   7020 static_cast<node*>(n->next_)->prev_ = n->prev_;
127   else 133   else
HITCBC 128   8744 tail_ = n->prev_; 134   4536 tail_ = n->prev_;
HITCBC 129   24176 n->next_ = nullptr; 135   11556 n->next_ = nullptr;
HITCBC 130   24176 n->prev_ = nullptr; 136   11556 n->prev_ = nullptr;
131   } 137   }
132   138  
133   /// Invoke @p f for each element in the list. 139   /// Invoke @p f for each element in the list.
134   template<class F> 140   template<class F>
HITCBC 135   122 void for_each(F f) 141   122 void for_each(F f)
136   { 142   {
HITCBC 137   122 for (T* p = head_; p; p = static_cast<node*>(p)->next_) 143   122 for (T* p = head_; p; p = static_cast<node*>(p)->next_)
MISUBC 138   ✗ f(p); 144   ✗ f(p);
HITCBC 139   122 } 145   122 }
140   }; 146   };
141   147  
142   /** An intrusive singly linked FIFO queue. 148   /** An intrusive singly linked FIFO queue.
143   149  
144   This container provides O(1) push and pop operations for 150   This container provides O(1) push and pop operations for
145   elements that derive from @ref node. Elements are not 151   elements that derive from @ref node. Elements are not
146   copied or moved; they are linked directly into the queue. 152   copied or moved; they are linked directly into the queue.
147   153  
148   Unlike @ref intrusive_list, this uses only a single `next_` 154   Unlike @ref intrusive_list, this uses only a single `next_`
149   pointer per node, saving memory at the cost of not supporting 155   pointer per node, saving memory at the cost of not supporting
150   O(1) removal of arbitrary elements. 156   O(1) removal of arbitrary elements.
151   157  
152   @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`.
153   */ 159   */
154   template<class T> 160   template<class T>
155   class intrusive_queue 161   class intrusive_queue
156   { 162   {
157   public: 163   public:
158   /** Base class for queue elements. 164   /** Base class for queue elements.
159   165  
160   Derive from this class to make a type usable with 166   Derive from this class to make a type usable with
161   @ref intrusive_queue. The `next_` pointer is private 167   @ref intrusive_queue. The `next_` pointer is private
162   and accessible only to the queue. 168   and accessible only to the queue.
163   */ 169   */
164   class node 170   class node
165   { 171   {
166   friend class intrusive_queue; 172   friend class intrusive_queue;
167   173  
168   private: 174   private:
169   T* next_; 175   T* next_;
170   }; 176   };
171   177  
172   private: 178   private:
173   T* head_ = nullptr; 179   T* head_ = nullptr;
174   T* tail_ = nullptr; 180   T* tail_ = nullptr;
175   181  
176   public: 182   public:
HITCBC 177   2738 intrusive_queue() = default; 183   2758 intrusive_queue() = default;
178   184  
179   intrusive_queue(intrusive_queue&& other) noexcept 185   intrusive_queue(intrusive_queue&& other) noexcept
180   : head_(other.head_) 186   : head_(other.head_)
181   , tail_(other.tail_) 187   , tail_(other.tail_)
182   { 188   {
183   other.head_ = nullptr; 189   other.head_ = nullptr;
184   other.tail_ = nullptr; 190   other.tail_ = nullptr;
185   } 191   }
186   192  
187   intrusive_queue(intrusive_queue const&) = delete; 193   intrusive_queue(intrusive_queue const&) = delete;
188   intrusive_queue& operator=(intrusive_queue const&) = delete; 194   intrusive_queue& operator=(intrusive_queue const&) = delete;
189   intrusive_queue& operator=(intrusive_queue&&) = delete; 195   intrusive_queue& operator=(intrusive_queue&&) = delete;
190   196  
HITCBC 191   2085567 bool empty() const noexcept 197   1944717 bool empty() const noexcept
192   { 198   {
HITCBC 193   2085567 return head_ == nullptr; 199   1944717 return head_ == nullptr;
194   } 200   }
195   201  
HITCBC 196   640901 void push(T* w) noexcept 202   595008 void push(T* w) noexcept
197   { 203   {
HITCBC 198   640901 w->next_ = nullptr; 204   595008 w->next_ = nullptr;
HITCBC 199   640901 if (tail_) 205   595008 if (tail_)
HITCBC 200   280498 tail_->next_ = w; 206   258868 tail_->next_ = w;
201   else 207   else
HITCBC 202   360403 head_ = w; 208   336140 head_ = w;
HITCBC 203   640901 tail_ = w; 209   595008 tail_ = w;
HITCBC 204   640901 } 210   595008 }
205   211  
HITCBC 206   336934 void splice(intrusive_queue& other) noexcept 212   325824 void splice(intrusive_queue& other) noexcept
207   { 213   {
HITCBC 208   336934 if (other.empty()) 214   325824 if (other.empty())
MISUBC 209   ✗ return; 215   ✗ return;
HITCBC 210   336934 if (tail_) 216   325824 if (tail_)
HITCBC 211   128025 tail_->next_ = other.head_; 217   134315 tail_->next_ = other.head_;
212   else 218   else
HITCBC 213   208909 head_ = other.head_; 219   191509 head_ = other.head_;
HITCBC 214   336934 tail_ = other.tail_; 220   325824 tail_ = other.tail_;
HITCBC 215   336934 other.head_ = nullptr; 221   325824 other.head_ = nullptr;
HITCBC 216   336934 other.tail_ = nullptr; 222   325824 other.tail_ = nullptr;
217   } 223   }
218   224  
HITCBC 219   876322 T* pop() noexcept 225   825407 T* pop() noexcept
220   { 226   {
HITCBC 221   876322 if (!head_) 227   825407 if (!head_)
HITCBC 222   235421 return nullptr; 228   230399 return nullptr;
HITCBC 223   640901 T* w = head_; 229   595008 T* w = head_;
HITCBC 224   640901 head_ = head_->next_; 230   595008 head_ = head_->next_;
HITCBC 225   640901 if (!head_) 231   595008 if (!head_)
HITCBC 226   232378 tail_ = nullptr; 232   201825 tail_ = nullptr;
227   // Defensive: clear stale linkage on popped node. 233   // Defensive: clear stale linkage on popped node.
HITCBC 228   640901 w->next_ = nullptr; 234   595008 w->next_ = nullptr;
HITCBC 229   640901 return w; 235   595008 return w;
230   } 236   }
231   }; 237   };
232   238  
233   } // namespace boost::corosio::detail 239   } // namespace boost::corosio::detail
234   240  
235   #endif 241   #endif