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> OffsetOf(LinkedList T::* member)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> ContainerOf(LinkedList * node,LinkedList T::* member)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> ContainerOf(LinkedList T::* member)46 T* ContainerOf(LinkedList T::*member) noexcept 47 { 48 return ContainerOf(this, member); 49 } 50 InsertAfter(LinkedList * cur,LinkedList * node)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 InsertBefore(LinkedList * cur,LinkedList * node)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 Delete(LinkedList & node)67 static void Delete(LinkedList& node) noexcept 68 { 69 node.prev->next = node.next; 70 node.next->prev = node.prev; 71 node.next = nullptr; 72 node.prev = nullptr; 73 } 74 Delete(LinkedList * node)75 static void Delete(LinkedList* node) noexcept 76 { 77 node->prev->next = node->next; 78 node->next->prev = node->prev; 79 node->next = nullptr; 80 node->prev = nullptr; 81 } 82 RemoveCur(LinkedList & node)83 static void RemoveCur(LinkedList& node) noexcept 84 { 85 if (node.Null()) { 86 return; 87 } 88 Delete(node); 89 } 90 RemoveCur(LinkedList * node)91 static void RemoveCur(LinkedList* node) noexcept 92 { 93 if (node->Null()) { 94 return; 95 } 96 Delete(node); 97 } 98 RemoveNext(LinkedList * cur)99 static LinkedList* RemoveNext(LinkedList* cur) noexcept 100 { 101 if (cur->Empty()) { 102 return nullptr; 103 } 104 105 LinkedList* next = cur->next; 106 Delete(next); 107 return next; 108 } 109 110 template <typename T> RemoveNext(LinkedList * cur,LinkedList T::* member)111 static T* RemoveNext(LinkedList* cur, LinkedList T::*member) noexcept 112 { 113 if (cur->Empty()) { 114 return nullptr; 115 } 116 117 LinkedList* next = cur->next; 118 Delete(next); 119 return ContainerOf<T>(next, member); 120 } 121 RemovePrev(LinkedList * cur)122 static LinkedList* RemovePrev(LinkedList* cur) noexcept 123 { 124 if (cur->Empty()) { 125 return nullptr; 126 } 127 128 LinkedList* prev = cur->prev; 129 Delete(prev); 130 return prev; 131 } 132 133 template <typename T> RemovePrev(LinkedList * cur,LinkedList T::* member)134 static T* RemovePrev(LinkedList* cur, LinkedList T::*member) noexcept 135 { 136 if (cur->Empty()) { 137 return nullptr; 138 } 139 140 LinkedList* prev = cur->prev; 141 Delete(prev); 142 return ContainerOf<T>(prev, member); 143 } 144 InsertAfter(LinkedList & node)145 void InsertAfter(LinkedList& node) noexcept 146 { 147 InsertAfter(this, &node); 148 } 149 InsertAfter(LinkedList * node)150 void InsertAfter(LinkedList* node) noexcept 151 { 152 InsertAfter(this, node); 153 } 154 InsertBefore(LinkedList & node)155 void InsertBefore(LinkedList& node) noexcept 156 { 157 InsertBefore(this, &node); 158 } 159 InsertBefore(LinkedList * node)160 void InsertBefore(LinkedList* node) noexcept 161 { 162 InsertBefore(this, node); 163 } 164 RemoveNext()165 LinkedList* RemoveNext() noexcept 166 { 167 return RemoveNext(this); 168 } 169 170 template <typename T> RemoveNext(LinkedList T::* member)171 T* RemoveNext(LinkedList T::*member) noexcept 172 { 173 return RemoveNext(this, member); 174 } 175 RemovePrev()176 LinkedList* RemovePrev() noexcept 177 { 178 return RemovePrev(this); 179 } 180 181 template <typename T> RemovePrev(LinkedList T::* member)182 T* RemovePrev(LinkedList T::*member) noexcept 183 { 184 return RemovePrev(this, member); 185 } 186 PushFront(LinkedList & node)187 void PushFront(LinkedList& node) noexcept 188 { 189 InsertAfter(&node); 190 } 191 PushFront(LinkedList * node)192 void PushFront(LinkedList* node) noexcept 193 { 194 InsertAfter(node); 195 } 196 PushBack(LinkedList & node)197 void PushBack(LinkedList& node) noexcept 198 { 199 InsertBefore(&node); 200 } 201 PushBack(LinkedList * node)202 void PushBack(LinkedList* node) noexcept 203 { 204 InsertBefore(node); 205 } 206 PopFront()207 LinkedList* PopFront() noexcept 208 { 209 return RemoveNext(); 210 } 211 212 template <typename T> PopFront(LinkedList T::* member)213 T* PopFront(LinkedList T::*member) noexcept 214 { 215 return RemoveNext(member); 216 } 217 PopBack()218 LinkedList* PopBack() noexcept 219 { 220 return RemovePrev(); 221 } 222 223 template <typename T> PopBack(LinkedList T::* member)224 T* PopBack(LinkedList T::*member) noexcept 225 { 226 return RemovePrev(member); 227 } 228 Empty()229 bool Empty() const noexcept 230 { 231 return next == this; 232 } 233 Null()234 bool Null() const noexcept 235 { 236 return prev == nullptr && next == nullptr; 237 } 238 InList()239 bool InList() const noexcept 240 { 241 return (next != nullptr && next != this); 242 } 243 244 private: 245 LinkedList* prev; 246 LinkedList* next; 247 }; 248 } // namespace ffrt 249 #endif