| // Copyright 2018 the V8 project authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #ifndef V8_BASE_LIST_H_ |
| #define V8_BASE_LIST_H_ |
| |
| #include <atomic> |
| |
| #include "src/base/logging.h" |
| |
| namespace v8 { |
| namespace base { |
| |
| template <class T> |
| class List { |
| public: |
| List() : front_(nullptr), back_(nullptr) {} |
| |
| void PushBack(T* element) { |
| DCHECK(!element->list_node().next()); |
| DCHECK(!element->list_node().prev()); |
| if (back_) { |
| DCHECK(front_); |
| InsertAfter(element, back_); |
| } else { |
| AddFirstElement(element); |
| } |
| } |
| |
| void PushFront(T* element) { |
| DCHECK(!element->list_node().next()); |
| DCHECK(!element->list_node().prev()); |
| if (front_) { |
| DCHECK(back_); |
| InsertBefore(element, front_); |
| } else { |
| AddFirstElement(element); |
| } |
| } |
| |
| void Remove(T* element) { |
| DCHECK(Contains(element)); |
| if (back_ == element) { |
| back_ = element->list_node().prev(); |
| } |
| if (front_ == element) { |
| front_ = element->list_node().next(); |
| } |
| T* next = element->list_node().next(); |
| T* prev = element->list_node().prev(); |
| if (next) next->list_node().set_prev(prev); |
| if (prev) prev->list_node().set_next(next); |
| element->list_node().set_prev(nullptr); |
| element->list_node().set_next(nullptr); |
| } |
| |
| bool Contains(T* element) { |
| T* it = front_; |
| while (it) { |
| if (it == element) return true; |
| it = it->list_node().next(); |
| } |
| return false; |
| } |
| |
| bool Empty() { return !front_ && !back_; } |
| |
| T* front() { return front_; } |
| T* back() { return back_; } |
| |
| private: |
| void AddFirstElement(T* element) { |
| DCHECK(!back_); |
| DCHECK(!front_); |
| DCHECK(!element->list_node().next()); |
| DCHECK(!element->list_node().prev()); |
| element->list_node().set_prev(nullptr); |
| element->list_node().set_next(nullptr); |
| front_ = element; |
| back_ = element; |
| } |
| |
| void InsertAfter(T* element, T* other) { |
| T* other_next = other->list_node().next(); |
| element->list_node().set_next(other_next); |
| element->list_node().set_prev(other); |
| other->list_node().set_next(element); |
| if (other_next) |
| other_next->list_node().set_prev(element); |
| else |
| back_ = element; |
| } |
| |
| void InsertBefore(T* element, T* other) { |
| T* other_prev = other->list_node().prev(); |
| element->list_node().set_next(other); |
| element->list_node().set_prev(other_prev); |
| other->list_node().set_prev(element); |
| if (other_prev) { |
| other_prev->list_node().set_next(element); |
| } else { |
| front_ = element; |
| } |
| } |
| |
| T* front_; |
| T* back_; |
| }; |
| |
| template <class T> |
| class ListNode { |
| public: |
| ListNode() { Initialize(); } |
| |
| T* next() { return next_; } |
| T* prev() { return prev_; } |
| |
| void Initialize() { |
| next_ = nullptr; |
| prev_ = nullptr; |
| } |
| |
| private: |
| void set_next(T* next) { next_ = next; } |
| void set_prev(T* prev) { prev_ = prev; } |
| |
| T* next_; |
| T* prev_; |
| |
| friend class List<T>; |
| }; |
| } // namespace base |
| } // namespace v8 |
| |
| #endif // V8_BASE_LIST_H_ |