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 875218 : List() : front_(nullptr), back_(nullptr) {}
19 :
20 : void PushBack(T* element) {
21 : DCHECK(!element->list_node().next());
22 : DCHECK(!element->list_node().prev());
23 889406 : 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 1476 : if (front_) {
35 : DCHECK(back_);
36 : InsertBefore(element, front_);
37 : } else {
38 : AddFirstElement(element);
39 : }
40 : }
41 :
42 890791 : void Remove(T* element) {
43 : DCHECK(Contains(element));
44 890791 : if (back_ == element) {
45 465893 : back_ = element->list_node().prev();
46 : }
47 890791 : if (front_ == element) {
48 826368 : front_ = element->list_node().next();
49 : }
50 890791 : T* next = element->list_node().next();
51 890791 : T* prev = element->list_node().prev();
52 890791 : if (next) next->list_node().set_prev(prev);
53 890791 : if (prev) prev->list_node().set_next(next);
54 : element->list_node().set_prev(nullptr);
55 : element->list_node().set_next(nullptr);
56 890791 : }
57 :
58 : bool Contains(T* element) {
59 : T* it = front_;
60 1 : while (it) {
61 1 : if (it == element) return true;
62 0 : it = it->list_node().next();
63 : }
64 : return false;
65 : }
66 :
67 1494539 : 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 429465 : front_ = element;
81 429465 : back_ = element;
82 : }
83 :
84 : void InsertAfter(T* element, T* other) {
85 459943 : 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 459943 : if (other_next)
90 : other_next->list_node().set_prev(element);
91 : else
92 459943 : back_ = element;
93 : }
94 :
95 : void InsertBefore(T* element, T* other) {
96 1474 : 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 1474 : if (other_prev) {
101 : other_prev->list_node().set_next(element);
102 : } else {
103 1474 : 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 728603 : next_ = nullptr;
121 728603 : prev_ = nullptr;
122 : }
123 :
124 : private:
125 2306038 : void set_next(T* next) { next_ = next; }
126 2206570 : 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_
|