1 /** 2 * Copyright (c) 2025 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 ES2PANDA_UTIL_DOUBLE_LINKED_LIST_H 17 #define ES2PANDA_UTIL_DOUBLE_LINKED_LIST_H 18 19 #include "mem/arena_allocator.h" 20 21 namespace ark::es2panda::util { 22 23 template <typename T> 24 class ArenaDoubleLinkedList { 25 public: ArenaDoubleLinkedList(ArenaAllocator * allocator)26 explicit ArenaDoubleLinkedList(ArenaAllocator *allocator) : allocator_ {allocator} {} 27 28 struct Item { 29 T data {}; 30 Item *next {nullptr}; 31 Item *prev {nullptr}; 32 }; 33 Head()34 Item *Head() 35 { 36 return head_; 37 } 38 Tail()39 Item *Tail() 40 { 41 return tail_; 42 } 43 Empty()44 bool Empty() 45 { 46 return head_ == nullptr; 47 }; 48 Allocator()49 ArenaAllocator *Allocator() 50 { 51 return allocator_; 52 } 53 Append(const T & data)54 Item *Append(const T &data) 55 { 56 auto item = allocator_->New<Item>(); 57 ES2PANDA_ASSERT(item != nullptr); 58 item->data = data; 59 Append(item); 60 return item; 61 } 62 Append(Item * item)63 void Append(Item *item) 64 { 65 item->next = nullptr; 66 item->prev = nullptr; 67 68 if (Empty()) { 69 head_ = item; 70 tail_ = item; 71 } else { 72 tail_->next = item; 73 item->prev = tail_; 74 tail_ = item; 75 } 76 } 77 Prepend(const T & data)78 Item *Prepend(const T &data) 79 { 80 auto item = allocator_->New<Item>(); 81 ES2PANDA_ASSERT(item != nullptr); 82 item->data = data; 83 Prepend(item); 84 return item; 85 } 86 Prepend(Item * item)87 void Prepend(Item *item) 88 { 89 item->next = nullptr; 90 item->prev = nullptr; 91 92 if (Empty()) { 93 head_ = item; 94 tail_ = item; 95 } else { 96 head_->prev = item; 97 item->next = head_; 98 head_ = item; 99 } 100 } 101 Insert(Item * after,const T & data)102 Item *Insert(Item *after, const T &data) 103 { 104 auto item = allocator_->New<Item>(); 105 ES2PANDA_ASSERT(item != nullptr); 106 item->data = data; 107 Insert(after, item); 108 return item; 109 } 110 Insert(Item * after,Item * item)111 void Insert(Item *after, Item *item) 112 { 113 ES2PANDA_ASSERT(!Empty()); 114 ES2PANDA_ASSERT(after != nullptr); 115 ES2PANDA_ASSERT(item != nullptr); 116 117 auto afterNext = after->next; 118 119 after->next = item; 120 item->prev = after; 121 122 item->next = afterNext; 123 if (afterNext != nullptr) { 124 afterNext->prev = item; 125 } 126 127 if (after == tail_) { 128 tail_ = item; 129 } 130 } 131 Erase(Item * item)132 void Erase(Item *item) 133 { 134 ES2PANDA_ASSERT(!Empty()); 135 ES2PANDA_ASSERT(item != nullptr); 136 137 if (item == head_ && item == tail_) { 138 // Item is the only element in list 139 head_ = nullptr; 140 tail_ = nullptr; 141 } else if (item == head_) { 142 head_ = head_->next; 143 if (head_ != nullptr) { 144 head_->prev = nullptr; 145 } 146 } else if (item == tail_) { 147 tail_ = tail_->prev; 148 if (tail_ != nullptr) { 149 tail_->next = nullptr; 150 } 151 } else { 152 // Item is not a head or tail element of list 153 auto prev = item->prev; 154 auto next = item->next; 155 156 ES2PANDA_ASSERT(prev != nullptr && next != nullptr); 157 prev->next = next; 158 next->prev = prev; 159 } 160 161 item->next = nullptr; 162 item->prev = nullptr; 163 } 164 165 private: 166 Item *head_ {nullptr}; 167 Item *tail_ {nullptr}; 168 ArenaAllocator *allocator_; 169 }; 170 } // namespace ark::es2panda::util 171 #endif 172