1/*
2 * Copyright 2019 WebAssembly Community Group participants
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17//
18// A vector of elements, which may be small, and uses a fixed space
19// for those small elements.
20//
21
22#ifndef wasm_support_small_vector_h
23#define wasm_support_small_vector_h
24
25#include <array>
26#include <cassert>
27#include <iterator>
28#include <vector>
29
30namespace wasm {
31
32template<typename T, size_t N> class SmallVector {
33 // fixed-space storage
34 size_t usedFixed = 0;
35 std::array<T, N> fixed;
36
37 // flexible additional storage
38 std::vector<T> flexible;
39
40public:
41 using value_type = T;
42
43 SmallVector() {}
44 SmallVector(std::initializer_list<T> init) {
45 for (T item : init) {
46 push_back(item);
47 }
48 }
49 SmallVector(size_t initialSize) { resize(initialSize); }
50
51 T& operator[](size_t i) {
52 if (i < N) {
53 return fixed[i];
54 } else {
55 return flexible[i - N];
56 }
57 }
58
59 const T& operator[](size_t i) const {
60 return const_cast<SmallVector<T, N>&>(*this)[i];
61 }
62
63 void push_back(const T& x) {
64 if (usedFixed < N) {
65 fixed[usedFixed++] = x;
66 } else {
67 flexible.push_back(x);
68 }
69 }
70
71 template<typename... ArgTypes> void emplace_back(ArgTypes&&... Args) {
72 if (usedFixed < N) {
73 new (&fixed[usedFixed++]) T(std::forward<ArgTypes>(Args)...);
74 } else {
75 flexible.emplace_back(std::forward<ArgTypes>(Args)...);
76 }
77 }
78
79 void pop_back() {
80 if (flexible.empty()) {
81 assert(usedFixed > 0);
82 usedFixed--;
83 } else {
84 flexible.pop_back();
85 }
86 }
87
88 T& back() {
89 if (flexible.empty()) {
90 assert(usedFixed > 0);
91 return fixed[usedFixed - 1];
92 } else {
93 return flexible.back();
94 }
95 }
96
97 const T& back() const {
98 if (flexible.empty()) {
99 assert(usedFixed > 0);
100 return fixed[usedFixed - 1];
101 } else {
102 return flexible.back();
103 }
104 }
105
106 size_t size() const { return usedFixed + flexible.size(); }
107
108 bool empty() const { return size() == 0; }
109
110 void clear() {
111 usedFixed = 0;
112 flexible.clear();
113 }
114
115 void resize(size_t newSize) {
116 usedFixed = std::min(N, newSize);
117 if (newSize > N) {
118 flexible.resize(newSize - N);
119 } else {
120 flexible.clear();
121 }
122 }
123
124 void reserve(size_t reservedSize) {
125 if (reservedSize > N) {
126 flexible.reserve(reservedSize - N);
127 }
128 }
129
130 size_t capacity() const { return N + flexible.capacity(); }
131
132 bool operator==(const SmallVector<T, N>& other) const {
133 if (usedFixed != other.usedFixed) {
134 return false;
135 }
136 for (size_t i = 0; i < usedFixed; i++) {
137 if (fixed[i] != other.fixed[i]) {
138 return false;
139 }
140 }
141 return flexible == other.flexible;
142 }
143
144 bool operator!=(const SmallVector<T, N>& other) const {
145 return !(*this == other);
146 }
147
148 // iteration
149
150 template<typename Parent, typename Iterator> struct IteratorBase {
151 using value_type = T;
152 using difference_type = long;
153 using reference = T&;
154
155 Parent* parent;
156 size_t index;
157
158 IteratorBase(Parent* parent, size_t index) : parent(parent), index(index) {}
159
160 bool operator!=(const Iterator& other) const {
161 return index != other.index || parent != other.parent;
162 }
163
164 void operator++() { index++; }
165
166 Iterator& operator+=(difference_type off) {
167 index += off;
168 return *this;
169 }
170
171 const Iterator operator+(difference_type off) const {
172 return Iterator(*this) += off;
173 }
174 };
175
176 struct Iterator : IteratorBase<SmallVector<T, N>, Iterator> {
177 Iterator(SmallVector<T, N>* parent, size_t index)
178 : IteratorBase<SmallVector<T, N>, Iterator>(parent, index) {}
179 value_type& operator*() { return (*this->parent)[this->index]; }
180 };
181
182 struct ConstIterator : IteratorBase<const SmallVector<T, N>, ConstIterator> {
183 ConstIterator(const SmallVector<T, N>* parent, size_t index)
184 : IteratorBase<const SmallVector<T, N>, ConstIterator>(parent, index) {}
185 const value_type& operator*() const { return (*this->parent)[this->index]; }
186 };
187
188 Iterator begin() { return Iterator(this, 0); }
189 Iterator end() { return Iterator(this, size()); }
190 ConstIterator begin() const { return ConstIterator(this, 0); }
191 ConstIterator end() const { return ConstIterator(this, size()); }
192};
193
194// A SmallVector for which some values may be read before they are written, and
195// in that case they have the value zero.
196template<typename T, size_t N>
197struct ZeroInitSmallVector : public SmallVector<T, N> {
198 T& operator[](size_t i) {
199 if (i >= this->size()) {
200 resize(i + 1);
201 }
202 return SmallVector<T, N>::operator[](i);
203 }
204
205 const T& operator[](size_t i) const {
206 return const_cast<ZeroInitSmallVector<T, N>&>(*this)[i];
207 }
208
209 void resize(size_t newSize) {
210 auto oldSize = this->size();
211 SmallVector<T, N>::resize(newSize);
212 for (size_t i = oldSize; i < this->size(); i++) {
213 (*this)[i] = 0;
214 }
215 }
216};
217
218} // namespace wasm
219
220#endif // wasm_support_small_vector_h
221

source code of dart_sdk/third_party/binaryen/src/src/support/small_vector.h