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