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 | |
30 | namespace wasm { |
31 | |
32 | template<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 | |
40 | public: |
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. |
196 | template<typename T, size_t N> |
197 | struct 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 | |