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