Home | History | Annotate | Download | only in base 
      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:
     18   List() : front_(nullptr), back_(nullptr) {}
     19 
     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 
     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 
     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 
     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 
     67   bool Empty() { return !front_ && !back_; }
     68 
     69   T* front() { return front_; }
     70   T* back() { return back_; }
     71 
     72  private:
     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 
     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 
     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:
    114   ListNode() { Initialize(); }
    115 
    116   T* next() { return next_; }
    117   T* prev() { return prev_; }
    118 
    119   void Initialize() {
    120     next_ = nullptr;
    121     prev_ = nullptr;
    122   }
    123 
    124  private:
    125   void set_next(T* next) { next_ = next; }
    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