1 /*
2  * Copyright (c) 2024 NVIDIA Corporation
3  *
4  * Licensed under the Apache License Version 2.0 with LLVM Exceptions
5  * (the "License"); you may not use this file except in compliance with
6  * the License. You may obtain a copy of the License at
7  *
8  *   https://llvm.org/LICENSE.txt
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 #pragma once
17 
18 #include "__config.hpp"
19 
20 #include <cassert>
21 #include <cstddef>
22 #include <iterator>
23 #include <utility>
24 
25 namespace stdexec
26 {
27 namespace __slist
28 {
29 template <auto _Next>
30 class __intrusive_slist;
31 
32 template <class _Item, _Item* _Item::*_Next>
33 class __intrusive_slist<_Next>
34 {
35   public:
36     __intrusive_slist() noexcept = default;
37 
__intrusive_slist(__intrusive_slist && __other)38     __intrusive_slist(__intrusive_slist&& __other) noexcept :
39         __head_(std::exchange(__other.__head_, nullptr))
40     {}
41 
__intrusive_slist(_Item * __head)42     __intrusive_slist(_Item* __head) noexcept : __head_(__head) {}
43 
swap(__intrusive_slist & __other)44     auto swap(__intrusive_slist& __other) noexcept -> void
45     {
46         std::swap(__head_, __other.__head_);
47     }
48 
operator =(__intrusive_slist __other)49     auto operator=(__intrusive_slist __other) noexcept -> __intrusive_slist&
50     {
51         swap(__other);
52         return *this;
53     }
54 
empty() const55     [[nodiscard]] auto empty() const noexcept -> bool
56     {
57         return __head_ == nullptr;
58     }
59 
front() const60     auto front() const noexcept -> _Item*
61     {
62         return __head_;
63     }
64 
clear()65     void clear() noexcept
66     {
67         __head_ = nullptr;
68     }
69 
pop_front()70     [[nodiscard]] auto pop_front() noexcept -> _Item*
71     {
72         STDEXEC_ASSERT(!empty());
73         return std::exchange(__head_, __head_->*_Next);
74     }
75 
push_front(_Item * __item)76     void push_front(_Item* __item) noexcept
77     {
78         STDEXEC_ASSERT(__item != nullptr);
79         __item->*_Next = std::exchange(__head_, __item);
80     }
81 
remove(_Item * __item)82     [[nodiscard]] _Item* remove(_Item* __item) noexcept
83     {
84         STDEXEC_ASSERT(__item != nullptr);
85         if (__head_ == __item)
86         {
87             return pop_front();
88         }
89 
90         for (_Item* __current : *this)
91         {
92             if (__current->*_Next == __item)
93             {
94                 __current->*_Next = __item->*_Next;
95                 return __item;
96             }
97         }
98 
99         return nullptr;
100     }
101 
102     struct iterator
103     {
104         using iterator_category = std::forward_iterator_tag;
105         using difference_type = std::ptrdiff_t;
106         using value_type = _Item*;
107         using reference = _Item*;
108         using pointer = _Item**;
109 
110         _Item* __item_ = nullptr;
111 
112         iterator() noexcept = default;
113 
iteratorstdexec::__slist::__intrusive_slist::iterator114         explicit iterator(_Item* __item) noexcept : __item_(__item) {}
115 
operator *stdexec::__slist::__intrusive_slist::iterator116         [[nodiscard]] auto operator*() const noexcept -> _Item*
117         {
118             STDEXEC_ASSERT(__item_ != nullptr);
119             return __item_;
120         }
121 
operator ->stdexec::__slist::__intrusive_slist::iterator122         [[nodiscard]] auto operator->() const noexcept -> _Item**
123         {
124             STDEXEC_ASSERT(__item_ != nullptr);
125             return &__item_;
126         }
127 
operator ++stdexec::__slist::__intrusive_slist::iterator128         auto operator++() noexcept -> iterator&
129         {
130             STDEXEC_ASSERT(__item_ != nullptr);
131             __item_ = __item_->*_Next;
132             return *this;
133         }
134 
operator ++stdexec::__slist::__intrusive_slist::iterator135         auto operator++(int) noexcept -> iterator
136         {
137             iterator __result = *this;
138             ++*this;
139             return __result;
140         }
141 
142         auto operator==(const iterator&) const noexcept -> bool = default;
143     };
144 
begin() const145     [[nodiscard]] auto begin() const noexcept -> iterator
146     {
147         return iterator(__head_);
148     }
149 
end() const150     [[nodiscard]] auto end() const noexcept -> iterator
151     {
152         return iterator(nullptr);
153     }
154 
155   private:
156     _Item* __head_ = nullptr;
157 };
158 } // namespace __slist
159 
160 using __slist::__intrusive_slist;
161 
162 } // namespace stdexec
163