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