. /include/boost/capy /detail /intrusive.hpp
100.00% Lines (81/81) 100.00% Functions (12/12)
[ ] 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/capy 7   // Official repository: https://github.com/cppalliance/capy
8   // 8   //
9   9  
10   #ifndef BOOST_CAPY_DETAIL_INTRUSIVE_HPP 10   #ifndef BOOST_CAPY_DETAIL_INTRUSIVE_HPP
11   #define BOOST_CAPY_DETAIL_INTRUSIVE_HPP 11   #define BOOST_CAPY_DETAIL_INTRUSIVE_HPP
12   12  
13   namespace boost { 13   namespace boost {
14   namespace capy { 14   namespace capy {
15   namespace detail { 15   namespace detail {
16   16  
17   //------------------------------------------------ 17   //------------------------------------------------
18   18  
19   /** An intrusive doubly linked list. 19   /** An intrusive doubly linked list.
20   20  
21   This container provides O(1) push and pop operations for 21   This container provides O(1) push and pop operations for
22   elements that derive from @ref node. Elements are not 22   elements that derive from @ref node. Elements are not
23   copied or moved; they are linked directly into the list. 23   copied or moved; they are linked directly into the list.
24   24  
25   @tparam T The element type. Must derive from `intrusive_list<T>::node`. 25   @tparam T The element type. Must derive from `intrusive_list<T>::node`.
26   */ 26   */
27   template<class T> 27   template<class T>
28   class intrusive_list 28   class intrusive_list
29   { 29   {
30   public: 30   public:
31   /** Base class for list elements. 31   /** Base class for list elements.
32   32  
33   Derive from this class to make a type usable with 33   Derive from this class to make a type usable with
34   @ref intrusive_list. The `next_` and `prev_` pointers 34   @ref intrusive_list. The `next_` and `prev_` pointers
35   are private and accessible only to the list. 35   are private and accessible only to the list.
36   */ 36   */
37   class node 37   class node
38   { 38   {
39   friend class intrusive_list; 39   friend class intrusive_list;
40   40  
41   private: 41   private:
42   T* next_; 42   T* next_;
43   T* prev_; 43   T* prev_;
44   bool linked_ = false; 44   bool linked_ = false;
45   }; 45   };
46   46  
47   private: 47   private:
48   T* head_ = nullptr; 48   T* head_ = nullptr;
49   T* tail_ = nullptr; 49   T* tail_ = nullptr;
50   50  
51   public: 51   public:
HITCBC 52   31 intrusive_list() = default; 52   31 intrusive_list() = default;
53   53  
HITCBC 54   2 intrusive_list(intrusive_list&& other) noexcept 54   2 intrusive_list(intrusive_list&& other) noexcept
HITCBC 55   2 : head_(other.head_) 55   2 : head_(other.head_)
HITCBC 56   2 , tail_(other.tail_) 56   2 , tail_(other.tail_)
57   { 57   {
HITCBC 58   2 other.head_ = nullptr; 58   2 other.head_ = nullptr;
HITCBC 59   2 other.tail_ = nullptr; 59   2 other.tail_ = nullptr;
HITCBC 60   2 } 60   2 }
61   61  
62   intrusive_list(intrusive_list const&) = delete; 62   intrusive_list(intrusive_list const&) = delete;
63   intrusive_list& operator=(intrusive_list const&) = delete; 63   intrusive_list& operator=(intrusive_list const&) = delete;
64   intrusive_list& operator=(intrusive_list&&) = delete; 64   intrusive_list& operator=(intrusive_list&&) = delete;
65   65  
66   bool 66   bool
HITCBC 67   36 empty() const noexcept 67   36 empty() const noexcept
68   { 68   {
HITCBC 69   36 return head_ == nullptr; 69   36 return head_ == nullptr;
70   } 70   }
71   71  
72   void 72   void
HITCBC 73   11512 push_back(T* w) noexcept 73   11512 push_back(T* w) noexcept
74   { 74   {
HITCBC 75   11512 w->next_ = nullptr; 75   11512 w->next_ = nullptr;
HITCBC 76   11512 w->prev_ = tail_; 76   11512 w->prev_ = tail_;
HITCBC 77   11512 if(tail_) 77   11512 if(tail_)
HITCBC 78   11441 tail_->next_ = w; 78   11441 tail_->next_ = w;
79   else 79   else
HITCBC 80   71 head_ = w; 80   71 head_ = w;
HITCBC 81   11512 tail_ = w; 81   11512 tail_ = w;
HITCBC 82   11512 w->linked_ = true; 82   11512 w->linked_ = true;
HITCBC 83   11512 } 83   11512 }
84   84  
85   void 85   void
HITCBC 86   4 splice_back(intrusive_list& other) noexcept 86   4 splice_back(intrusive_list& other) noexcept
87   { 87   {
HITCBC 88   4 if(other.empty()) 88   4 if(other.empty())
HITCBC 89   2 return; 89   2 return;
HITCBC 90   2 if(tail_) 90   2 if(tail_)
91   { 91   {
HITCBC 92   1 tail_->next_ = other.head_; 92   1 tail_->next_ = other.head_;
HITCBC 93   1 other.head_->prev_ = tail_; 93   1 other.head_->prev_ = tail_;
HITCBC 94   1 tail_ = other.tail_; 94   1 tail_ = other.tail_;
95   } 95   }
96   else 96   else
97   { 97   {
HITCBC 98   1 head_ = other.head_; 98   1 head_ = other.head_;
HITCBC 99   1 tail_ = other.tail_; 99   1 tail_ = other.tail_;
100   } 100   }
HITCBC 101   2 other.head_ = nullptr; 101   2 other.head_ = nullptr;
HITCBC 102   2 other.tail_ = nullptr; 102   2 other.tail_ = nullptr;
103   } 103   }
104   104  
105   T* 105   T*
HITCBC 106   121 pop_front() noexcept 106   121 pop_front() noexcept
107   { 107   {
HITCBC 108   121 if(!head_) 108   121 if(!head_)
HITCBC 109   69 return nullptr; 109   69 return nullptr;
HITCBC 110   52 T* w = head_; 110   52 T* w = head_;
HITCBC 111   52 head_ = head_->next_; 111   52 head_ = head_->next_;
HITCBC 112   52 if(head_) 112   52 if(head_)
HITCBC 113   22 head_->prev_ = nullptr; 113   22 head_->prev_ = nullptr;
114   else 114   else
HITCBC 115   30 tail_ = nullptr; 115   30 tail_ = nullptr;
HITCBC 116   52 w->linked_ = false; 116   52 w->linked_ = false;
HITCBC 117   52 return w; 117   52 return w;
118   } 118   }
119   119  
120   void 120   void
HITCBC 121   11461 remove(T* w) noexcept 121   11461 remove(T* w) noexcept
122   { 122   {
HITCBC 123   11461 if(!w->linked_) 123   11461 if(!w->linked_)
HITCBC 124   1 return; 124   1 return;
HITCBC 125   11460 if(w->prev_) 125   11460 if(w->prev_)
HITCBC 126   14 w->prev_->next_ = w->next_; 126   7 w->prev_->next_ = w->next_;
127   else 127   else
HITCBC 128   11446 head_ = w->next_; 128   11453 head_ = w->next_;
HITCBC 129   11460 if(w->next_) 129   11460 if(w->next_)
HITCBC 130   11415 w->next_->prev_ = w->prev_; 130   11415 w->next_->prev_ = w->prev_;
131   else 131   else
HITCBC 132   45 tail_ = w->prev_; 132   45 tail_ = w->prev_;
HITCBC 133   11460 w->linked_ = false; 133   11460 w->linked_ = false;
134   } 134   }
135   }; 135   };
136   136  
137   //------------------------------------------------ 137   //------------------------------------------------
138   138  
139   /** An intrusive singly linked FIFO queue. 139   /** An intrusive singly linked FIFO queue.
140   140  
141   This container provides O(1) push and pop operations for 141   This container provides O(1) push and pop operations for
142   elements that derive from @ref node. Elements are not 142   elements that derive from @ref node. Elements are not
143   copied or moved; they are linked directly into the queue. 143   copied or moved; they are linked directly into the queue.
144   144  
145   Unlike @ref intrusive_list, this uses only a single `next_` 145   Unlike @ref intrusive_list, this uses only a single `next_`
146   pointer per node, saving memory at the cost of not supporting 146   pointer per node, saving memory at the cost of not supporting
147   O(1) removal of arbitrary elements. 147   O(1) removal of arbitrary elements.
148   148  
149   @tparam T The element type. Must derive from `intrusive_queue<T>::node`. 149   @tparam T The element type. Must derive from `intrusive_queue<T>::node`.
150   */ 150   */
151   template<class T> 151   template<class T>
152   class intrusive_queue 152   class intrusive_queue
153   { 153   {
154   public: 154   public:
155   /** Base class for queue elements. 155   /** Base class for queue elements.
156   156  
157   Derive from this class to make a type usable with 157   Derive from this class to make a type usable with
158   @ref intrusive_queue. The `next_` pointer is private 158   @ref intrusive_queue. The `next_` pointer is private
159   and accessible only to the queue. 159   and accessible only to the queue.
160   */ 160   */
161   class node 161   class node
162   { 162   {
163   friend class intrusive_queue; 163   friend class intrusive_queue;
164   164  
165   private: 165   private:
166   T* next_; 166   T* next_;
167   }; 167   };
168   168  
169   private: 169   private:
170   T* head_ = nullptr; 170   T* head_ = nullptr;
171   T* tail_ = nullptr; 171   T* tail_ = nullptr;
172   172  
173   public: 173   public:
174   intrusive_queue() = default; 174   intrusive_queue() = default;
175   175  
HITCBC 176   2 intrusive_queue(intrusive_queue&& other) noexcept 176   2 intrusive_queue(intrusive_queue&& other) noexcept
HITCBC 177   2 : head_(other.head_) 177   2 : head_(other.head_)
HITCBC 178   2 , tail_(other.tail_) 178   2 , tail_(other.tail_)
179   { 179   {
HITCBC 180   2 other.head_ = nullptr; 180   2 other.head_ = nullptr;
HITCBC 181   2 other.tail_ = nullptr; 181   2 other.tail_ = nullptr;
HITCBC 182   2 } 182   2 }
183   183  
184   intrusive_queue(intrusive_queue const&) = delete; 184   intrusive_queue(intrusive_queue const&) = delete;
185   intrusive_queue& operator=(intrusive_queue const&) = delete; 185   intrusive_queue& operator=(intrusive_queue const&) = delete;
186   intrusive_queue& operator=(intrusive_queue&&) = delete; 186   intrusive_queue& operator=(intrusive_queue&&) = delete;
187   187  
188   bool 188   bool
HITCBC 189   27 empty() const noexcept 189   27 empty() const noexcept
190   { 190   {
HITCBC 191   27 return head_ == nullptr; 191   27 return head_ == nullptr;
192   } 192   }
193   193  
194   void 194   void
HITCBC 195   18 push(T* w) noexcept 195   18 push(T* w) noexcept
196   { 196   {
HITCBC 197   18 w->next_ = nullptr; 197   18 w->next_ = nullptr;
HITCBC 198   18 if(tail_) 198   18 if(tail_)
HITCBC 199   8 tail_->next_ = w; 199   8 tail_->next_ = w;
200   else 200   else
HITCBC 201   10 head_ = w; 201   10 head_ = w;
HITCBC 202   18 tail_ = w; 202   18 tail_ = w;
HITCBC 203   18 } 203   18 }
204   204  
205   void 205   void
HITCBC 206   4 splice(intrusive_queue& other) noexcept 206   4 splice(intrusive_queue& other) noexcept
207   { 207   {
HITCBC 208   4 if(other.empty()) 208   4 if(other.empty())
HITCBC 209   2 return; 209   2 return;
HITCBC 210   2 if(tail_) 210   2 if(tail_)
HITCBC 211   1 tail_->next_ = other.head_; 211   1 tail_->next_ = other.head_;
212   else 212   else
HITCBC 213   1 head_ = other.head_; 213   1 head_ = other.head_;
HITCBC 214   2 tail_ = other.tail_; 214   2 tail_ = other.tail_;
HITCBC 215   2 other.head_ = nullptr; 215   2 other.head_ = nullptr;
HITCBC 216   2 other.tail_ = nullptr; 216   2 other.tail_ = nullptr;
217   } 217   }
218   218  
219   T* 219   T*
HITCBC 220   21 pop() noexcept 220   21 pop() noexcept
221   { 221   {
HITCBC 222   21 if(!head_) 222   21 if(!head_)
HITCBC 223   3 return nullptr; 223   3 return nullptr;
HITCBC 224   18 T* w = head_; 224   18 T* w = head_;
HITCBC 225   18 head_ = head_->next_; 225   18 head_ = head_->next_;
HITCBC 226   18 if(!head_) 226   18 if(!head_)
HITCBC 227   9 tail_ = nullptr; 227   9 tail_ = nullptr;
HITCBC 228   18 return w; 228   18 return w;
229   } 229   }
230   }; 230   };
231   231  
232   } // detail 232   } // detail
233   } // capy 233   } // capy
234   } // boost 234   } // boost
235   235  
236   #endif 236   #endif