1 // Copyright 2018 the V8 project authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #ifndef V8_HEAP_LIST_H_ 6 #define V8_HEAP_LIST_H_ 7 8 #include <atomic> 9 10 #include "src/base/logging.h" 11 12 namespace v8 { 13 namespace internal { 14 namespace heap { 15 16 template <class T> 17 class List { 18 public: List()19 List() : front_(nullptr), back_(nullptr) {} List(List && other)20 List(List&& other) V8_NOEXCEPT : front_(std::exchange(other.front_, nullptr)), 21 back_(std::exchange(other.back_, nullptr)) {} 22 List& operator=(List&& other) V8_NOEXCEPT { 23 front_ = std::exchange(other.front_, nullptr); 24 back_ = std::exchange(other.back_, nullptr); 25 return *this; 26 } 27 ShallowCopyTo(List * other)28 void ShallowCopyTo(List* other) const { 29 other->front_ = front_; 30 other->back_ = back_; 31 } 32 PushBack(T * element)33 void PushBack(T* element) { 34 DCHECK(!element->list_node().next()); 35 DCHECK(!element->list_node().prev()); 36 if (back_) { 37 DCHECK(front_); 38 InsertAfter(element, back_); 39 } else { 40 AddFirstElement(element); 41 } 42 } 43 PushFront(T * element)44 void PushFront(T* element) { 45 DCHECK(!element->list_node().next()); 46 DCHECK(!element->list_node().prev()); 47 if (front_) { 48 DCHECK(back_); 49 InsertBefore(element, front_); 50 } else { 51 AddFirstElement(element); 52 } 53 } 54 Remove(T * element)55 void Remove(T* element) { 56 DCHECK(Contains(element)); 57 if (back_ == element) { 58 back_ = element->list_node().prev(); 59 } 60 if (front_ == element) { 61 front_ = element->list_node().next(); 62 } 63 T* next = element->list_node().next(); 64 T* prev = element->list_node().prev(); 65 if (next) next->list_node().set_prev(prev); 66 if (prev) prev->list_node().set_next(next); 67 element->list_node().set_prev(nullptr); 68 element->list_node().set_next(nullptr); 69 } 70 Contains(T * element)71 bool Contains(T* element) const { 72 const T* it = front_; 73 while (it) { 74 if (it == element) return true; 75 it = it->list_node().next(); 76 } 77 return false; 78 } 79 Empty()80 bool Empty() const { return !front_ && !back_; } 81 front()82 T* front() { return front_; } back()83 T* back() { return back_; } 84 front()85 const T* front() const { return front_; } back()86 const T* back() const { return back_; } 87 88 private: AddFirstElement(T * element)89 void AddFirstElement(T* element) { 90 DCHECK(!back_); 91 DCHECK(!front_); 92 DCHECK(!element->list_node().next()); 93 DCHECK(!element->list_node().prev()); 94 element->list_node().set_prev(nullptr); 95 element->list_node().set_next(nullptr); 96 front_ = element; 97 back_ = element; 98 } 99 InsertAfter(T * element,T * other)100 void InsertAfter(T* element, T* other) { 101 T* other_next = other->list_node().next(); 102 element->list_node().set_next(other_next); 103 element->list_node().set_prev(other); 104 other->list_node().set_next(element); 105 if (other_next) 106 other_next->list_node().set_prev(element); 107 else 108 back_ = element; 109 } 110 InsertBefore(T * element,T * other)111 void InsertBefore(T* element, T* other) { 112 T* other_prev = other->list_node().prev(); 113 element->list_node().set_next(other); 114 element->list_node().set_prev(other_prev); 115 other->list_node().set_prev(element); 116 if (other_prev) { 117 other_prev->list_node().set_next(element); 118 } else { 119 front_ = element; 120 } 121 } 122 123 T* front_; 124 T* back_; 125 }; 126 127 template <class T> 128 class ListNode { 129 public: ListNode()130 ListNode() { Initialize(); } 131 next()132 T* next() { return next_; } prev()133 T* prev() { return prev_; } 134 next()135 const T* next() const { return next_; } prev()136 const T* prev() const { return prev_; } 137 Initialize()138 void Initialize() { 139 next_ = nullptr; 140 prev_ = nullptr; 141 } 142 143 private: set_next(T * next)144 void set_next(T* next) { next_ = next; } set_prev(T * prev)145 void set_prev(T* prev) { prev_ = prev; } 146 147 T* next_; 148 T* prev_; 149 150 friend class List<T>; 151 }; 152 } // namespace heap 153 } // namespace internal 154 } // namespace v8 155 156 #endif // V8_HEAP_LIST_H_ 157