1   
//
1   
//
2   
// Copyright (c) 2025 Vinnie Falco (vinnie dot falco at gmail dot com)
2   
// Copyright (c) 2025 Vinnie Falco (vinnie dot falco at gmail dot 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  
53   
    intrusive_list(intrusive_list&& other) noexcept
53   
    intrusive_list(intrusive_list&& other) noexcept
54   
        : head_(other.head_)
54   
        : head_(other.head_)
55   
        , tail_(other.tail_)
55   
        , tail_(other.tail_)
56   
    {
56   
    {
57   
        other.head_ = nullptr;
57   
        other.head_ = nullptr;
58   
        other.tail_ = nullptr;
58   
        other.tail_ = nullptr;
59   
    }
59   
    }
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
66   
    empty() const noexcept
66   
    empty() const noexcept
67   
    {
67   
    {
68   
        return head_ == nullptr;
68   
        return head_ == nullptr;
69   
    }
69   
    }
70  
70  
71   
    void
71   
    void
72   
    push_back(T* w) noexcept
72   
    push_back(T* w) noexcept
73   
    {
73   
    {
74   
        w->next_ = nullptr;
74   
        w->next_ = nullptr;
75   
        w->prev_ = tail_;
75   
        w->prev_ = tail_;
76   
        if(tail_)
76   
        if(tail_)
77   
            tail_->next_ = w;
77   
            tail_->next_ = w;
78   
        else
78   
        else
79   
            head_ = w;
79   
            head_ = w;
80   
        tail_ = w;
80   
        tail_ = w;
81   
    }
81   
    }
82  
82  
83   
    void
83   
    void
84   
    splice_back(intrusive_list& other) noexcept
84   
    splice_back(intrusive_list& other) noexcept
85   
    {
85   
    {
86   
        if(other.empty())
86   
        if(other.empty())
87   
            return;
87   
            return;
88   
        if(tail_)
88   
        if(tail_)
89   
        {
89   
        {
90   
            tail_->next_ = other.head_;
90   
            tail_->next_ = other.head_;
91   
            other.head_->prev_ = tail_;
91   
            other.head_->prev_ = tail_;
92   
            tail_ = other.tail_;
92   
            tail_ = other.tail_;
93   
        }
93   
        }
94   
        else
94   
        else
95   
        {
95   
        {
96   
            head_ = other.head_;
96   
            head_ = other.head_;
97   
            tail_ = other.tail_;
97   
            tail_ = other.tail_;
98   
        }
98   
        }
99   
        other.head_ = nullptr;
99   
        other.head_ = nullptr;
100   
        other.tail_ = nullptr;
100   
        other.tail_ = nullptr;
101   
    }
101   
    }
102  
102  
103   
    T*
103   
    T*
104   
    pop_front() noexcept
104   
    pop_front() noexcept
105   
    {
105   
    {
106   
        if(!head_)
106   
        if(!head_)
107   
            return nullptr;
107   
            return nullptr;
108   
        T* w = head_;
108   
        T* w = head_;
109   
        head_ = head_->next_;
109   
        head_ = head_->next_;
110   
        if(head_)
110   
        if(head_)
111   
            head_->prev_ = nullptr;
111   
            head_->prev_ = nullptr;
112   
        else
112   
        else
113   
            tail_ = nullptr;
113   
            tail_ = nullptr;
114   
        return w;
114   
        return w;
115   
    }
115   
    }
116  
116  
117   
    void
117   
    void
118   
    remove(T* w) noexcept
118   
    remove(T* w) noexcept
119   
    {
119   
    {
120   
        if(w->prev_)
120   
        if(w->prev_)
121   
            w->prev_->next_ = w->next_;
121   
            w->prev_->next_ = w->next_;
122   
        else
122   
        else
123   
            head_ = w->next_;
123   
            head_ = w->next_;
124   
        if(w->next_)
124   
        if(w->next_)
125   
            w->next_->prev_ = w->prev_;
125   
            w->next_->prev_ = w->prev_;
126   
        else
126   
        else
127   
            tail_ = w->prev_;
127   
            tail_ = w->prev_;
128   
    }
128   
    }
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  
170   
    intrusive_queue(intrusive_queue&& other) noexcept
170   
    intrusive_queue(intrusive_queue&& other) noexcept
171   
        : head_(other.head_)
171   
        : head_(other.head_)
172   
        , tail_(other.tail_)
172   
        , tail_(other.tail_)
173   
    {
173   
    {
174   
        other.head_ = nullptr;
174   
        other.head_ = nullptr;
175   
        other.tail_ = nullptr;
175   
        other.tail_ = nullptr;
176   
    }
176   
    }
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
183   
    empty() const noexcept
183   
    empty() const noexcept
184   
    {
184   
    {
185   
        return head_ == nullptr;
185   
        return head_ == nullptr;
186   
    }
186   
    }
187  
187  
188   
    void
188   
    void
189   
    push(T* w) noexcept
189   
    push(T* w) noexcept
190   
    {
190   
    {
191   
        w->next_ = nullptr;
191   
        w->next_ = nullptr;
192   
        if(tail_)
192   
        if(tail_)
193   
            tail_->next_ = w;
193   
            tail_->next_ = w;
194   
        else
194   
        else
195   
            head_ = w;
195   
            head_ = w;
196   
        tail_ = w;
196   
        tail_ = w;
197   
    }
197   
    }
198  
198  
199   
    void
199   
    void
200   
    splice(intrusive_queue& other) noexcept
200   
    splice(intrusive_queue& other) noexcept
201   
    {
201   
    {
202   
        if(other.empty())
202   
        if(other.empty())
203   
            return;
203   
            return;
204   
        if(tail_)
204   
        if(tail_)
205   
            tail_->next_ = other.head_;
205   
            tail_->next_ = other.head_;
206   
        else
206   
        else
207   
            head_ = other.head_;
207   
            head_ = other.head_;
208   
        tail_ = other.tail_;
208   
        tail_ = other.tail_;
209   
        other.head_ = nullptr;
209   
        other.head_ = nullptr;
210   
        other.tail_ = nullptr;
210   
        other.tail_ = nullptr;
211   
    }
211   
    }
212  
212  
213   
    T*
213   
    T*
214   
    pop() noexcept
214   
    pop() noexcept
215   
    {
215   
    {
216   
        if(!head_)
216   
        if(!head_)
217   
            return nullptr;
217   
            return nullptr;
218   
        T* w = head_;
218   
        T* w = head_;
219   
        head_ = head_->next_;
219   
        head_ = head_->next_;
220   
        if(!head_)
220   
        if(!head_)
221   
            tail_ = nullptr;
221   
            tail_ = nullptr;
222   
        return w;
222   
        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