1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
|
// 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_COMPILER_FUNCTIONAL_LIST_H_
#define V8_COMPILER_FUNCTIONAL_LIST_H_
#include "src/zone/zone.h"
namespace v8 {
namespace internal {
namespace compiler {
// A generic stack implemented as a purely functional singly-linked list, which
// results in an O(1) copy operation. It is the equivalent of functional lists
// in ML-like languages, with the only difference that it also caches the length
// of the list in each node.
// TODO(tebbi): Use this implementation also for RedundancyElimination.
template <class A>
class FunctionalList {
private:
struct Cons : ZoneObject {
Cons(A top, Cons* rest)
: top(std::move(top)), rest(rest), size(1 + (rest ? rest->size : 0)) {}
A const top;
Cons* const rest;
size_t const size;
};
public:
FunctionalList() : elements_(nullptr) {}
bool operator==(const FunctionalList<A>& other) const {
if (Size() != other.Size()) return false;
iterator it = begin();
iterator other_it = other.begin();
while (true) {
if (it == other_it) return true;
if (*it != *other_it) return false;
++it;
++other_it;
}
}
bool operator!=(const FunctionalList<A>& other) const {
return !(*this == other);
}
const A& Front() const {
DCHECK_GT(Size(), 0);
return elements_->top;
}
FunctionalList Rest() const {
FunctionalList result = *this;
result.DropFront();
return result;
}
void DropFront() {
CHECK_GT(Size(), 0);
elements_ = elements_->rest;
}
void PushFront(A a, Zone* zone) {
elements_ = new (zone) Cons(std::move(a), elements_);
}
// If {hint} happens to be exactly what we want to allocate, avoid allocation
// by reusing {hint}.
void PushFront(A a, Zone* zone, FunctionalList hint) {
if (hint.Size() == Size() + 1 && hint.Front() == a &&
hint.Rest() == *this) {
*this = hint;
} else {
PushFront(a, zone);
}
}
// Drop elements until the current stack is equal to the tail shared with
// {other}. The shared tail must not only be equal, but also refer to the
// same memory.
void ResetToCommonAncestor(FunctionalList other) {
while (other.Size() > Size()) other.DropFront();
while (other.Size() < Size()) DropFront();
while (elements_ != other.elements_) {
DropFront();
other.DropFront();
}
}
size_t Size() const { return elements_ ? elements_->size : 0; }
void Clear() { elements_ = nullptr; }
class iterator {
public:
explicit iterator(Cons* cur) : current_(cur) {}
const A& operator*() const { return current_->top; }
iterator& operator++() {
current_ = current_->rest;
return *this;
}
bool operator==(const iterator& other) const {
return this->current_ == other.current_;
}
bool operator!=(const iterator& other) const { return !(*this == other); }
private:
Cons* current_;
};
iterator begin() const { return iterator(elements_); }
iterator end() const { return iterator(nullptr); }
private:
Cons* elements_;
};
} // namespace compiler
} // namespace internal
} // namespace v8
#endif // V8_COMPILER_FUNCTIONAL_LIST_H_
|
