1 /*
2  * Copyright (c) 2021-2022 Facebook, Inc. and its affiliates
3  * Copyright (c) 2021-2024 NVIDIA Corporation
4  *
5  * Licensed under the Apache License Version 2.0 with LLVM Exceptions
6  * (the "License"); you may not use this file except in compliance with
7  * the License. You may obtain a copy of the License at
8  *
9  *   https://llvm.org/LICENSE.txt
10  *
11  * Unless required by applicable law or agreed to in writing, software
12  * distributed under the License is distributed on an "AS IS" BASIS,
13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  * See the License for the specific language governing permissions and
15  * limitations under the License.
16  */
17 #pragma once
18 
19 #include "__config.hpp"
20 
21 #include <cassert>
22 #include <cstddef>
23 #include <utility>
24 
25 namespace stdexec
26 {
27 namespace __queue
28 {
29 template <auto _Next>
30 class __intrusive_queue;
31 
32 template <class _Item, _Item* _Item::*_Next>
33 class __intrusive_queue<_Next>
34 {
35   public:
36     __intrusive_queue() noexcept = default;
37 
__intrusive_queue(__intrusive_queue && __other)38     __intrusive_queue(__intrusive_queue&& __other) noexcept :
39         __head_(std::exchange(__other.__head_, nullptr)),
40         __tail_(std::exchange(__other.__tail_, nullptr))
41     {}
42 
__intrusive_queue(_Item * __head,_Item * __tail)43     __intrusive_queue(_Item* __head, _Item* __tail) noexcept :
44         __head_(__head), __tail_(__tail)
45     {}
46 
operator =(__intrusive_queue __other)47     auto operator=(__intrusive_queue __other) noexcept -> __intrusive_queue&
48     {
49         std::swap(__head_, __other.__head_);
50         std::swap(__tail_, __other.__tail_);
51         return *this;
52     }
53 
~__intrusive_queue()54     ~__intrusive_queue()
55     {
56         STDEXEC_ASSERT(empty());
57     }
58 
make_reversed(_Item * __list)59     static auto make_reversed(_Item* __list) noexcept -> __intrusive_queue
60     {
61         _Item* __new_head = nullptr;
62         _Item* __new_tail = __list;
63         while (__list != nullptr)
64         {
65             _Item* __next = __list->*_Next;
66             __list->*_Next = __new_head;
67             __new_head = __list;
68             __list = __next;
69         }
70 
71         __intrusive_queue __result;
72         __result.__head_ = __new_head;
73         __result.__tail_ = __new_tail;
74         return __result;
75     }
76 
make(_Item * __list)77     static auto make(_Item* __list) noexcept -> __intrusive_queue
78     {
79         __intrusive_queue __result{};
80         __result.__head_ = __list;
81         __result.__tail_ = __list;
82         if (__list == nullptr)
83         {
84             return __result;
85         }
86         while (__result.__tail_->*_Next != nullptr)
87         {
88             __result.__tail_ = __result.__tail_->*_Next;
89         }
90         return __result;
91     }
92 
empty() const93     [[nodiscard]] auto empty() const noexcept -> bool
94     {
95         return __head_ == nullptr;
96     }
97 
clear()98     void clear() noexcept
99     {
100         __head_ = nullptr;
101         __tail_ = nullptr;
102     }
103 
pop_front()104     [[nodiscard]] auto pop_front() noexcept -> _Item*
105     {
106         STDEXEC_ASSERT(!empty());
107         _Item* __item = std::exchange(__head_, __head_->*_Next);
108         // This should test if __head_ == nullptr, but due to a bug in
109         // nvc++'s optimization, `__head_` isn't assigned until later.
110         // Filed as NVBug#3952534.
111         if (__item->*_Next == nullptr)
112         {
113             __tail_ = nullptr;
114         }
115         return __item;
116     }
117 
push_front(_Item * __item)118     void push_front(_Item* __item) noexcept
119     {
120         STDEXEC_ASSERT(__item != nullptr);
121         __item->*_Next = __head_;
122         __head_ = __item;
123         if (__tail_ == nullptr)
124         {
125             __tail_ = __item;
126         }
127     }
128 
push_back(_Item * __item)129     void push_back(_Item* __item) noexcept
130     {
131         STDEXEC_ASSERT(__item != nullptr);
132         __item->*_Next = nullptr;
133         if (__tail_ == nullptr)
134         {
135             __head_ = __item;
136         }
137         else
138         {
139             __tail_->*_Next = __item;
140         }
141         __tail_ = __item;
142     }
143 
append(__intrusive_queue __other)144     void append(__intrusive_queue __other) noexcept
145     {
146         if (__other.empty())
147             return;
148         auto* __other_head = std::exchange(__other.__head_, nullptr);
149         if (empty())
150         {
151             __head_ = __other_head;
152         }
153         else
154         {
155             __tail_->*_Next = __other_head;
156         }
157         __tail_ = std::exchange(__other.__tail_, nullptr);
158     }
159 
prepend(__intrusive_queue __other)160     void prepend(__intrusive_queue __other) noexcept
161     {
162         if (__other.empty())
163             return;
164 
165         __other.__tail_->*_Next = __head_;
166         __head_ = __other.__head_;
167         if (__tail_ == nullptr)
168         {
169             __tail_ = __other.__tail_;
170         }
171 
172         __other.__tail_ = nullptr;
173         __other.__head_ = nullptr;
174     }
175 
176     struct iterator
177     {
178         using difference_type = std::ptrdiff_t;
179         using value_type = _Item*;
180 
181         _Item* __predecessor_ = nullptr;
182         _Item* __item_ = nullptr;
183 
184         iterator() noexcept = default;
185 
iteratorstdexec::__queue::__intrusive_queue::iterator186         explicit iterator(_Item* __pred, _Item* __item) noexcept :
187             __predecessor_(__pred), __item_(__item)
188         {}
189 
operator *stdexec::__queue::__intrusive_queue::iterator190         [[nodiscard]] auto operator*() const noexcept -> _Item*
191         {
192             STDEXEC_ASSERT(__item_ != nullptr);
193             return __item_;
194         }
195 
operator ->stdexec::__queue::__intrusive_queue::iterator196         [[nodiscard]] auto operator->() const noexcept -> _Item**
197         {
198             STDEXEC_ASSERT(__item_ != nullptr);
199             return &__item_;
200         }
201 
operator ++stdexec::__queue::__intrusive_queue::iterator202         auto operator++() noexcept -> iterator&
203         {
204             __predecessor_ = __item_;
205             if (__item_)
206             {
207                 __item_ = __item_->*_Next;
208             }
209             return *this;
210         }
211 
operator ++stdexec::__queue::__intrusive_queue::iterator212         auto operator++(int) noexcept -> iterator
213         {
214             iterator __result = *this;
215             ++*this;
216             return __result;
217         }
218 
219         friend auto operator==(const iterator&,
220                                const iterator&) noexcept -> bool = default;
221     };
222 
begin() const223     [[nodiscard]] auto begin() const noexcept -> iterator
224     {
225         return iterator(nullptr, __head_);
226     }
227 
end() const228     [[nodiscard]] auto end() const noexcept -> iterator
229     {
230         return iterator(__tail_, nullptr);
231     }
232 
splice(iterator pos,__intrusive_queue & other,iterator first,iterator last)233     void splice(iterator pos, __intrusive_queue& other, iterator first,
234                 iterator last) noexcept
235     {
236         if (first == last)
237         {
238             return;
239         }
240         STDEXEC_ASSERT(first.__item_ != nullptr);
241         STDEXEC_ASSERT(last.__predecessor_ != nullptr);
242         if (other.__head_ == first.__item_)
243         {
244             other.__head_ = last.__item_;
245             if (other.__head_ == nullptr)
246             {
247                 other.__tail_ = nullptr;
248             }
249         }
250         else
251         {
252             STDEXEC_ASSERT(first.__predecessor_ != nullptr);
253             first.__predecessor_->*_Next = last.__item_;
254             last.__predecessor_->*_Next = pos.__item_;
255         }
256         if (empty())
257         {
258             __head_ = first.__item_;
259             __tail_ = last.__predecessor_;
260         }
261         else
262         {
263             pos.__predecessor_->*_Next = first.__item_;
264             if (pos.__item_ == nullptr)
265             {
266                 __tail_ = last.__predecessor_;
267             }
268         }
269     }
270 
front() const271     auto front() const noexcept -> _Item*
272     {
273         return __head_;
274     }
275 
back() const276     auto back() const noexcept -> _Item*
277     {
278         return __tail_;
279     }
280 
281   private:
282     _Item* __head_ = nullptr;
283     _Item* __tail_ = nullptr;
284 };
285 } // namespace __queue
286 
287 using __queue::__intrusive_queue;
288 
289 } // namespace stdexec
290