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 FFRT_LINKED_LIST_H
17 #define FFRT_LINKED_LIST_H
18 
19 #include <cstddef>
20 #include <cstdint>
21 
22 namespace ffrt {
23 class LinkedList {
24 public:
LinkedList()25     LinkedList() : prev(this), next(this)
26     {
27     }
28 
LinkedList(LinkedList* prev, LinkedList* next)29     LinkedList(LinkedList* prev, LinkedList* next) : prev(prev), next(next)
30     {
31     }
32 
33     template <typename T>
34     static ptrdiff_t OffsetOf(LinkedList T::*member) noexcept
35     {
36         return reinterpret_cast<ptrdiff_t>(&(reinterpret_cast<T*>(0)->*member));
37     }
38 
39     template <typename T>
40     static T* ContainerOf(LinkedList* node, LinkedList T::*member) noexcept
41     {
42         return reinterpret_cast<T*>(reinterpret_cast<intptr_t>(node) - OffsetOf<T>(member));
43     }
44 
45     template <typename T>
46     T* ContainerOf(LinkedList T::*member) noexcept
47     {
48         return ContainerOf(this, member);
49     }
50 
51     static void InsertAfter(LinkedList* cur, LinkedList* node) noexcept
52     {
53         node->next = cur->next;
54         node->prev = cur;
55         cur->next->prev = node;
56         cur->next = node;
57     }
58 
59     static void InsertBefore(LinkedList* cur, LinkedList* node) noexcept
60     {
61         node->next = cur;
62         node->prev = cur->prev;
63         cur->prev->next = node;
64         cur->prev = node;
65     }
66 
67     static void Delete(LinkedList& node) noexcept
68     {
69         node.prev->next = node.next;
70         node.next->prev = node.prev;
71         node.next = &node;
72         node.prev = &node;
73     }
74 
75     static void Delete(LinkedList* node) noexcept
76     {
77         node->prev->next = node->next;
78         node->next->prev = node->prev;
79         node->next = node;
80         node->prev = node;
81     }
82 
83     static void RemoveCur(LinkedList& node) noexcept
84     {
85         if (node.Null()) {
86             return;
87         }
88         Delete(node);
89     }
90 
91     static void RemoveCur(LinkedList* node) noexcept
92     {
93         if (node->Null()) {
94             return;
95         }
96         Delete(node);
97     }
98 
99     static LinkedList* Next(LinkedList* cur) noexcept
100     {
101         if (cur->Empty()) {
102             return nullptr;
103         }
104 
105         LinkedList* next = cur->next;
106         return next;
107     }
108 
109     template <typename T>
110     static T* Next(LinkedList* cur, LinkedList T::*member) noexcept
111     {
112         if (cur->Empty()) {
113             return nullptr;
114         }
115 
116         LinkedList* next = cur->next;
117         return ContainerOf<T>(next, member);
118     }
119 
120     static LinkedList* RemoveNext(LinkedList* cur) noexcept
121     {
122         if (cur->Empty()) {
123             return nullptr;
124         }
125 
126         LinkedList* next = cur->next;
127         Delete(next);
128         return next;
129     }
130 
131     template <typename T>
132     static T* RemoveNext(LinkedList* cur, LinkedList T::*member) noexcept
133     {
134         if (cur->Empty()) {
135             return nullptr;
136         }
137 
138         LinkedList* next = cur->next;
139         Delete(next);
140         return ContainerOf<T>(next, member);
141     }
142 
143     static LinkedList* RemovePrev(LinkedList* cur) noexcept
144     {
145         if (cur->Empty()) {
146             return nullptr;
147         }
148 
149         LinkedList* prev = cur->prev;
150         Delete(prev);
151         return prev;
152     }
153 
154     template <typename T>
155     static T* RemovePrev(LinkedList* cur, LinkedList T::*member) noexcept
156     {
157         if (cur->Empty()) {
158             return nullptr;
159         }
160 
161         LinkedList* prev = cur->prev;
162         Delete(prev);
163         return ContainerOf<T>(prev, member);
164     }
165 
166     void InsertAfter(LinkedList& node) noexcept
167     {
168         InsertAfter(this, &node);
169     }
170 
171     void InsertAfter(LinkedList* node) noexcept
172     {
173         InsertAfter(this, node);
174     }
175 
176     void InsertBefore(LinkedList& node) noexcept
177     {
178         InsertBefore(this, &node);
179     }
180 
181     void InsertBefore(LinkedList* node) noexcept
182     {
183         InsertBefore(this, node);
184     }
185 
186     LinkedList* Next() noexcept
187     {
188         return Next(this);
189     }
190 
191     template <typename T>
192     T* Next(LinkedList T::*member) noexcept
193     {
194         return Next(this, member);
195     }
196 
197     LinkedList* RemoveNext() noexcept
198     {
199         return RemoveNext(this);
200     }
201 
202     template <typename T>
203     T* RemoveNext(LinkedList T::*member) noexcept
204     {
205         return RemoveNext(this, member);
206     }
207 
208     LinkedList* RemovePrev() noexcept
209     {
210         return RemovePrev(this);
211     }
212 
213     template <typename T>
214     T* RemovePrev(LinkedList T::*member) noexcept
215     {
216         return RemovePrev(this, member);
217     }
218 
219     void PushFront(LinkedList& node) noexcept
220     {
221         InsertAfter(&node);
222     }
223 
224     void PushFront(LinkedList* node) noexcept
225     {
226         InsertAfter(node);
227     }
228 
229     void PushBack(LinkedList& node) noexcept
230     {
231         InsertBefore(&node);
232     }
233 
234     void PushBack(LinkedList* node) noexcept
235     {
236         InsertBefore(node);
237     }
238 
239     LinkedList* Front() noexcept
240     {
241         return Next();
242     }
243 
244     template <typename T>
245     T* Front(LinkedList T::*member) noexcept
246     {
247         return Next(member);
248     }
249 
250     LinkedList* PopFront() noexcept
251     {
252         return RemoveNext();
253     }
254 
255     template <typename T>
256     T* PopFront(LinkedList T::*member) noexcept
257     {
258         return RemoveNext(member);
259     }
260 
261     LinkedList* PopBack() noexcept
262     {
263         return RemovePrev();
264     }
265 
266     template <typename T>
267     T* PopBack(LinkedList T::*member) noexcept
268     {
269         return RemovePrev(member);
270     }
271 
272     bool Empty() const noexcept
273     {
274         return next == this;
275     }
276 
277     bool Null() const noexcept
278     {
279         return prev == nullptr && next == nullptr;
280     }
281 
282     bool InList() const noexcept
283     {
284         return (next != nullptr && next != this);
285     }
286 
287 private:
288     LinkedList* prev;
289     LinkedList* next;
290 };
291 } // namespace ffrt
292 #endif
293