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