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_BASE_LIST_H_ 6 #define V8_BASE_LIST_H_ 7 8 #include <atomic> 9 10 #include "src/base/logging.h" 11 12 namespace v8 { 13 namespace base { 14 15 template <class T> 16 class List { 17 public: List()18 List() : front_(nullptr), back_(nullptr) {} 19 PushBack(T * element)20 void PushBack(T* element) { 21 DCHECK(!element->list_node().next()); 22 DCHECK(!element->list_node().prev()); 23 if (back_) { 24 DCHECK(front_); 25 InsertAfter(element, back_); 26 } else { 27 AddFirstElement(element); 28 } 29 } 30 PushFront(T * element)31 void PushFront(T* element) { 32 DCHECK(!element->list_node().next()); 33 DCHECK(!element->list_node().prev()); 34 if (front_) { 35 DCHECK(back_); 36 InsertBefore(element, front_); 37 } else { 38 AddFirstElement(element); 39 } 40 } 41 Remove(T * element)42 void Remove(T* element) { 43 DCHECK(Contains(element)); 44 if (back_ == element) { 45 back_ = element->list_node().prev(); 46 } 47 if (front_ == element) { 48 front_ = element->list_node().next(); 49 } 50 T* next = element->list_node().next(); 51 T* prev = element->list_node().prev(); 52 if (next) next->list_node().set_prev(prev); 53 if (prev) prev->list_node().set_next(next); 54 element->list_node().set_prev(nullptr); 55 element->list_node().set_next(nullptr); 56 } 57 Contains(T * element)58 bool Contains(T* element) { 59 T* it = front_; 60 while (it) { 61 if (it == element) return true; 62 it = it->list_node().next(); 63 } 64 return false; 65 } 66 Empty()67 bool Empty() { return !front_ && !back_; } 68 front()69 T* front() { return front_; } back()70 T* back() { return back_; } 71 72 private: AddFirstElement(T * element)73 void AddFirstElement(T* element) { 74 DCHECK(!back_); 75 DCHECK(!front_); 76 DCHECK(!element->list_node().next()); 77 DCHECK(!element->list_node().prev()); 78 element->list_node().set_prev(nullptr); 79 element->list_node().set_next(nullptr); 80 front_ = element; 81 back_ = element; 82 } 83 InsertAfter(T * element,T * other)84 void InsertAfter(T* element, T* other) { 85 T* other_next = other->list_node().next(); 86 element->list_node().set_next(other_next); 87 element->list_node().set_prev(other); 88 other->list_node().set_next(element); 89 if (other_next) 90 other_next->list_node().set_prev(element); 91 else 92 back_ = element; 93 } 94 InsertBefore(T * element,T * other)95 void InsertBefore(T* element, T* other) { 96 T* other_prev = other->list_node().prev(); 97 element->list_node().set_next(other); 98 element->list_node().set_prev(other_prev); 99 other->list_node().set_prev(element); 100 if (other_prev) { 101 other_prev->list_node().set_next(element); 102 } else { 103 front_ = element; 104 } 105 } 106 107 T* front_; 108 T* back_; 109 }; 110 111 template <class T> 112 class ListNode { 113 public: ListNode()114 ListNode() { Initialize(); } 115 next()116 T* next() { return next_; } prev()117 T* prev() { return prev_; } 118 Initialize()119 void Initialize() { 120 next_ = nullptr; 121 prev_ = nullptr; 122 } 123 124 private: set_next(T * next)125 void set_next(T* next) { next_ = next; } set_prev(T * prev)126 void set_prev(T* prev) { prev_ = prev; } 127 128 T* next_; 129 T* prev_; 130 131 friend class List<T>; 132 }; 133 } // namespace base 134 } // namespace v8 135 136 #endif // V8_BASE_LIST_H_ 137