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