. /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  
HITCBC 66   47706 void push_back(T* w) noexcept 66   48163 void push_back(T* w) noexcept
67   { 67   {
HITCBC 68   47706 auto* n = static_cast<node*>(w); 68   48163 auto* n = static_cast<node*>(w);
HITCBC 69   47706 n->next_ = nullptr; 69   48163 n->next_ = nullptr;
HITCBC 70   47706 n->prev_ = tail_; 70   48163 n->prev_ = tail_;
HITCBC 71   47706 if (tail_) 71   48163 if (tail_)
HITCBC 72   27482 static_cast<node*>(tail_)->next_ = w; 72   27742 static_cast<node*>(tail_)->next_ = w;
73   else 73   else
HITCBC 74   20224 head_ = w; 74   20421 head_ = w;
HITCBC 75   47706 tail_ = w; 75   48163 tail_ = w;
HITCBC 76   47706 } 76   48163 }
77   77  
78   void splice_back(intrusive_list& other) noexcept 78   void splice_back(intrusive_list& other) noexcept
79   { 79   {
80   if (other.empty()) 80   if (other.empty())
81   return; 81   return;
82   if (tail_) 82   if (tail_)
83   { 83   {
84   static_cast<node*>(tail_)->next_ = other.head_; 84   static_cast<node*>(tail_)->next_ = other.head_;
85   static_cast<node*>(other.head_)->prev_ = tail_; 85   static_cast<node*>(other.head_)->prev_ = tail_;
86   tail_ = other.tail_; 86   tail_ = other.tail_;
87   } 87   }
88   else 88   else
89   { 89   {
90   head_ = other.head_; 90   head_ = other.head_;
91   tail_ = other.tail_; 91   tail_ = other.tail_;
92   } 92   }
93   other.head_ = nullptr; 93   other.head_ = nullptr;
94   other.tail_ = nullptr; 94   other.tail_ = nullptr;
95   } 95   }
96   96  
HITCBC 97   325141 T* pop_front() noexcept 97   423156 T* pop_front() noexcept
98   { 98   {
HITCBC 99   325141 if (!head_) 99   423156 if (!head_)
HITCBC 100   305967 return nullptr; 100   403786 return nullptr;
HITCBC 101   19174 T* w = head_; 101   19370 T* w = head_;
HITCBC 102   19174 head_ = static_cast<node*>(head_)->next_; 102   19370 head_ = static_cast<node*>(head_)->next_;
HITCBC 103   19174 if (head_) 103   19370 if (head_)
HITCBC 104   42 static_cast<node*>(head_)->prev_ = nullptr; 104   41 static_cast<node*>(head_)->prev_ = nullptr;
105   else 105   else
HITCBC 106   19132 tail_ = nullptr; 106   19329 tail_ = nullptr;
107   // Defensive: clear stale linkage so remove() on a 107   // Defensive: clear stale linkage so remove() on a
108   // popped node cannot corrupt the list. 108   // popped node cannot corrupt the list.
HITCBC 109   19174 auto* n = static_cast<node*>(w); 109   19370 auto* n = static_cast<node*>(w);
HITCBC 110   19174 n->next_ = nullptr; 110   19370 n->next_ = nullptr;
HITCBC 111   19174 n->prev_ = nullptr; 111   19370 n->prev_ = nullptr;
HITCBC 112   19174 return w; 112   19370 return w;
113   } 113   }
114   114  
HITCBC 115   28532 void remove(T* w) noexcept 115   28793 void remove(T* w) noexcept
116   { 116   {
HITCBC 117   28532 auto* n = static_cast<node*>(w); 117   28793 auto* n = static_cast<node*>(w);
118   // Already detached — nothing to do. 118   // Already detached — nothing to do.
HITCBC 119   28532 if (!n->next_ && !n->prev_ && head_ != w && tail_ != w) 119   28793 if (!n->next_ && !n->prev_ && head_ != w && tail_ != w)
MISUBC 120   ✗ return; 120   ✗ return;
HITCBC 121   28532 if (n->prev_) 121   28793 if (n->prev_)
HITCBC 122   9150 static_cast<node*>(n->prev_)->next_ = n->next_; 122   9237 static_cast<node*>(n->prev_)->next_ = n->next_;
123   else 123   else
HITCBC 124   19382 head_ = n->next_; 124   19556 head_ = n->next_;
HITCBC 125   28532 if (n->next_) 125   28793 if (n->next_)
HITCBC 126   18337 static_cast<node*>(n->next_)->prev_ = n->prev_; 126   18511 static_cast<node*>(n->next_)->prev_ = n->prev_;
127   else 127   else
HITCBC 128   10195 tail_ = n->prev_; 128   10282 tail_ = n->prev_;
HITCBC 129   28532 n->next_ = nullptr; 129   28793 n->next_ = nullptr;
HITCBC 130   28532 n->prev_ = nullptr; 130   28793 n->prev_ = nullptr;
131   } 131   }
132   132  
133   /// Invoke @p f for each element in the list. 133   /// Invoke @p f for each element in the list.
134   template<class F> 134   template<class F>
HITCBC 135   122 void for_each(F f) 135   122 void for_each(F f)
136   { 136   {
HITCBC 137   122 for (T* p = head_; p; p = static_cast<node*>(p)->next_) 137   122 for (T* p = head_; p; p = static_cast<node*>(p)->next_)
MISUBC 138   ✗ f(p); 138   ✗ f(p);
HITCBC 139   122 } 139   122 }
140   }; 140   };
141   141  
142   /** An intrusive singly linked FIFO queue. 142   /** An intrusive singly linked FIFO queue.
143   143  
144   This container provides O(1) push and pop operations for 144   This container provides O(1) push and pop operations for
145   elements that derive from @ref node. Elements are not 145   elements that derive from @ref node. Elements are not
146   copied or moved; they are linked directly into the queue. 146   copied or moved; they are linked directly into the queue.
147   147  
148   Unlike @ref intrusive_list, this uses only a single `next_` 148   Unlike @ref intrusive_list, this uses only a single `next_`
149   pointer per node, saving memory at the cost of not supporting 149   pointer per node, saving memory at the cost of not supporting
150   O(1) removal of arbitrary elements. 150   O(1) removal of arbitrary elements.
151   151  
152   @tparam T The element type. Must derive from `intrusive_queue<T>::node`. 152   @tparam T The element type. Must derive from `intrusive_queue<T>::node`.
153   */ 153   */
154   template<class T> 154   template<class T>
155   class intrusive_queue 155   class intrusive_queue
156   { 156   {
157   public: 157   public:
158   /** Base class for queue elements. 158   /** Base class for queue elements.
159   159  
160   Derive from this class to make a type usable with 160   Derive from this class to make a type usable with
161   @ref intrusive_queue. The `next_` pointer is private 161   @ref intrusive_queue. The `next_` pointer is private
162   and accessible only to the queue. 162   and accessible only to the queue.
163   */ 163   */
164   class node 164   class node
165   { 165   {
166   friend class intrusive_queue; 166   friend class intrusive_queue;
167   167  
168   private: 168   private:
169   T* next_; 169   T* next_;
170   }; 170   };
171   171  
172   private: 172   private:
173   T* head_ = nullptr; 173   T* head_ = nullptr;
174   T* tail_ = nullptr; 174   T* tail_ = nullptr;
175   175  
176   public: 176   public:
HITCBC 177   2737 intrusive_queue() = default; 177   2760 intrusive_queue() = default;
178   178  
179   intrusive_queue(intrusive_queue&& other) noexcept 179   intrusive_queue(intrusive_queue&& other) noexcept
180   : head_(other.head_) 180   : head_(other.head_)
181   , tail_(other.tail_) 181   , tail_(other.tail_)
182   { 182   {
183   other.head_ = nullptr; 183   other.head_ = nullptr;
184   other.tail_ = nullptr; 184   other.tail_ = nullptr;
185   } 185   }
186   186  
187   intrusive_queue(intrusive_queue const&) = delete; 187   intrusive_queue(intrusive_queue const&) = delete;
188   intrusive_queue& operator=(intrusive_queue const&) = delete; 188   intrusive_queue& operator=(intrusive_queue const&) = delete;
189   intrusive_queue& operator=(intrusive_queue&&) = delete; 189   intrusive_queue& operator=(intrusive_queue&&) = delete;
190   190  
HITCBC 191   2554821 bool empty() const noexcept 191   3374273 bool empty() const noexcept
192   { 192   {
HITCBC 193   2554821 return head_ == nullptr; 193   3374273 return head_ == nullptr;
194   } 194   }
195   195  
HITCBC 196   784187 void push(T* w) noexcept 196   1028393 void push(T* w) noexcept
197   { 197   {
HITCBC 198   784187 w->next_ = nullptr; 198   1028393 w->next_ = nullptr;
HITCBC 199   784187 if (tail_) 199   1028393 if (tail_)
HITCBC 200   345274 tail_->next_ = w; 200   452080 tail_->next_ = w;
201   else 201   else
HITCBC 202   438913 head_ = w; 202   576313 head_ = w;
HITCBC 203   784187 tail_ = w; 203   1028393 tail_ = w;
HITCBC 204   784187 } 204   1028393 }
205   205  
HITCBC 206   412501 void splice(intrusive_queue& other) noexcept 206   548017 void splice(intrusive_queue& other) noexcept
207   { 207   {
HITCBC 208   412501 if (other.empty()) 208   548017 if (other.empty())
MISUBC 209   ✗ return; 209   ✗ return;
HITCBC 210   412501 if (tail_) 210   548017 if (tail_)
HITCBC 211   154412 tail_->next_ = other.head_; 211   203863 tail_->next_ = other.head_;
212   else 212   else
HITCBC 213   258089 head_ = other.head_; 213   344154 head_ = other.head_;
HITCBC 214   412501 tail_ = other.tail_; 214   548017 tail_ = other.tail_;
HITCBC 215   412501 other.head_ = nullptr; 215   548017 other.head_ = nullptr;
HITCBC 216   412501 other.tail_ = nullptr; 216   548017 other.tail_ = nullptr;
217   } 217   }
218   218  
HITCBC 219   1076364 T* pop() noexcept 219   1420823 T* pop() noexcept
220   { 220   {
HITCBC 221   1076364 if (!head_) 221   1420823 if (!head_)
HITCBC 222   292177 return nullptr; 222   392430 return nullptr;
HITCBC 223   784187 T* w = head_; 223   1028393 T* w = head_;
HITCBC 224   784187 head_ = head_->next_; 224   1028393 head_ = head_->next_;
HITCBC 225   784187 if (!head_) 225   1028393 if (!head_)
HITCBC 226   284501 tail_ = nullptr; 226   372450 tail_ = nullptr;
227   // Defensive: clear stale linkage on popped node. 227   // Defensive: clear stale linkage on popped node.
HITCBC 228   784187 w->next_ = nullptr; 228   1028393 w->next_ = nullptr;
HITCBC 229   784187 return w; 229   1028393 return w;
230   } 230   }
231   }; 231   };
232   232  
233   } // namespace boost::corosio::detail 233   } // namespace boost::corosio::detail
234   234  
235   #endif 235   #endif