1 /*
2  * Copyright (c) 2023 Huawei Device Co., Ltd.
3  * Licensed under the Apache License, Version 2.0 (the "License");
4  * you may not use this file except in compliance with the License.
5  * You may obtain a copy of the License at
6  *
7  *     http://www.apache.org/licenses/LICENSE-2.0
8  *
9  * Unless required by applicable law or agreed to in writing, software
10  * distributed under the License is distributed on an "AS IS" BASIS,
11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12  * See the License for the specific language governing permissions and
13  * limitations under the License.
14  */
15 
16 #ifndef _INTRUSIVELIST_H_
17 #define _INTRUSIVELIST_H_
18 #include <cassert>
19 #include <utility>
20 #include <cstddef>
21 namespace ffrt {
22 ///////////////////////////////////////////////////////////////////////////////
23 template <typename Tag>
24 struct SListNode {
25     // if next point to self, isn't in list
IsLinkedSListNode26     bool IsLinked() const noexcept
27     {
28         return next != this;
29     }
SListNodeSListNode30     explicit SListNode(SListNode* p) noexcept : next {p}
31     {
32     }
33     SListNode() noexcept = default;
34 
35 private:
SwapSListNode36     void Swap(SListNode& rhs) noexcept
37     {
38         std::swap(next, rhs.next);
39     }
40 
41 private:
42     template <typename, typename>
43     friend struct SList;
44     SListNode* next {this};
45 };
46 
47 template <typename T, typename NodeType>
48 struct SList {
emptySList49     bool empty() const noexcept
50     {
51         return m_head.next == nullptr;
52     }
53 
54     SList() noexcept = default;
55 
SListSList56     SList(SList&& rhs) noexcept
57     {
58         Swap(rhs);
59     }
60     SList& operator=(SList&& rhs) noexcept
61     {
62         if (this != &rhs) {
63             SList tmp {std::move(rhs)};
64             Swap(tmp);
65         }
66         return *this;
67     }
68 
PushFrontSList69     void PushFront(T& node) noexcept
70     {
71         auto& nd = static_cast<NodeType&>(node);
72         nd.next = std::exchange(m_head.next, &nd);
73     }
74 
PopFrontSList75     T* PopFront() noexcept
76     {
77         if (empty()) {
78             return nullptr;
79         } else {
80             auto node = m_head.next;
81             m_head.next = std::exchange(node->next, node);
82             return static_cast<T*>(node);
83         }
84     }
85 
86 private:
SwapSList87     void Swap(SList& rhs) noexcept
88     {
89         m_head.Swap(rhs.m_head);
90     }
91 
92 private:
93     NodeType m_head {nullptr};
94 };
95 
96 ///////////////////////////////////////////////////////////////////////////////
97 struct ListNode {
IsLinkedListNode98     bool IsLinked() const noexcept
99     {
100         return next != this && prev != this;
101     }
102 
ListNodeListNode103     ListNode(ListNode* p, ListNode* n) noexcept : prev {p}, next {n}
104     {
105     }
106     ListNode() noexcept = default;
107 
108 private:
109     template <typename, typename>
110     friend struct List;
111     ListNode* prev {this};
112     ListNode* next {this};
113 };
114 
115 template <typename T, typename NodeType>
116 struct List {
ListList117     List() noexcept : m_head {&m_tail, &m_tail}, m_tail {&m_head, &m_head}
118     {
119     }
120 
ListList121     List(List&& rhs) noexcept : List()
122     {
123         if (!rhs.empty()) {
124             NodeType* x = rhs.m_head.next;
125             m_head.next = x;
126             x->prev = &m_head;
127 
128             NodeType* y = rhs.m_tail.prev;
129             y->next = &m_tail;
130             m_tail.prev = y;
131 
132             m_size = rhs.m_size;
133             // reset rhs to empty
134             rhs.Reset();
135         }
136     }
137 
138     List& operator=(List&& rhs) noexcept
139     {
140         if (this != &rhs && !rhs.empty()) {
141             Reset();
142             NodeType* x = rhs.m_head.next;
143             m_head.next = x;
144             x->prev = &m_head;
145 
146             NodeType* y = rhs.m_tail.prev;
147             y->next = &m_tail;
148             m_tail.prev = y;
149 
150             m_size = rhs.m_size;
151             // reset rhs to empty
152             rhs.Reset();
153         }
154         return *this;
155     }
156 
emptyList157     bool empty() const noexcept
158     {
159         return Size() == 0;
160     }
161 
SizeList162     size_t Size() const noexcept
163     {
164         return m_size;
165     }
166 
PushFrontList167     void PushFront(T& node) noexcept
168     {
169         auto& nd = static_cast<NodeType&>(node);
170 
171         m_head.next->prev = &nd;
172         nd.prev = &m_head;
173         nd.next = m_head.next;
174         m_head.next = &nd;
175         ++m_size;
176     }
177 
PushBackList178     void PushBack(T& node) noexcept
179     {
180         auto& nd = static_cast<NodeType&>(node);
181 
182         m_tail.prev->next = &nd;
183         nd.prev = m_tail.prev;
184         nd.next = &m_tail;
185         m_tail.prev = &nd;
186         ++m_size;
187     }
188 
PopFrontList189     T* PopFront() noexcept
190     {
191         if (empty()) {
192             return nullptr;
193         } else {
194             auto node = static_cast<T*>(m_head.next);
195             Unlink(*node);
196             return node;
197         }
198     }
199 
FrontList200     T* Front() noexcept
201     {
202         return empty() ? nullptr : static_cast<T*>(m_head.next);
203     }
204 
PopBackList205     T* PopBack() noexcept
206     {
207         if (empty()) {
208             return nullptr;
209         } else {
210             auto node = static_cast<T*>(m_tail.prev);
211             Unlink(*node);
212             return node;
213         }
214     }
215 
EraseList216     void Erase(T& node) noexcept
217     {
218         Unlink(node);
219     }
220 
221 private:
UnlinkList222     void Unlink(NodeType& node) noexcept
223     {
224         assert(node.IsLinked());
225         node.prev->next = node.next;
226         node.next->prev = node.prev;
227         node.next = node.prev = &node;
228         --m_size;
229     }
230 
231 private:
ResetList232     void Reset() noexcept
233     {
234         m_tail.prev = &m_head;
235         m_tail.next = &m_head;
236         m_head.prev = &m_tail;
237         m_head.next = &m_tail;
238         m_size = 0;
239     }
240 
241 private:
242     NodeType m_head;
243     NodeType m_tail;
244     size_t m_size {0};
245 };
246 } // namespace ffrt
247 #endif // HICORO_INTRUSIVELIST_H
248