Line data    Source code

       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      889817 :   List() : front_(nullptr), back_(nullptr) {}
      19             : 
      20             :   void PushBack(T* element) {
      21             :     DCHECK(!element->list_node().next());
      22             :     DCHECK(!element->list_node().prev());
      23     1142569 :     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        2574 :     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     1141397 :     if (back_ == element) {
      45      459395 :       back_ = element->list_node().prev();
      46             :     }
      47      279262 :     if (front_ == element) {
      48     1063206 :       front_ = element->list_node().next();
      49             :     }
      50             :     T* next = element->list_node().next();
      51             :     T* prev = element->list_node().prev();
      52     1145021 :     if (next) next->list_node().set_prev(prev);
      53     1145021 :     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           1 :     while (it) {
      61           1 :       if (it == element) return true;
      62             :       it = it->list_node().next();
      63             :     }
      64             :     return false;
      65             :   }
      66             : 
      67     1722651 :   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      417178 :     front_ = element;
      81      417178 :     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      725389 :     if (other_next)
      90             :       other_next->list_node().set_prev(element);
      91             :     else
      92      725371 :       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        2573 :     if (other_prev) {
     101             :       other_prev->list_node().set_next(element);
     102             :     } else {
     103        2564 :       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      966553 :     next_ = nullptr;
     121      966553 :     prev_ = nullptr;
     122             :   }
     123             : 
     124             :  private:
     125     3097355 :   void set_next(T* next) { next_ = next; }
     126     2975778 :   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_