V8 API Reference, 7.2.502.16 (for Deno 0.2.4)
list.h
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_
Definition: libplatform.h:13