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