1/*
2 * Copyright 2021 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 set of elements, which is often small. While the number of items is small,
19// the implementation simply stores them in an array that is linearly looked
20// through. Once the size is large enough, we switch to using a std::set or
21// std::unordered_set.
22//
23
24#ifndef wasm_support_small_set_h
25#define wasm_support_small_set_h
26
27#include <algorithm>
28#include <array>
29#include <cassert>
30#include <set>
31#include <unordered_set>
32
33#include "utilities.h"
34
35namespace wasm {
36
37template<typename T, size_t N> struct FixedStorageBase {
38 size_t used = 0;
39 std::array<T, N> storage;
40
41 enum InsertResult {
42 // Either we inserted a new item, or the item already existed, so no error
43 // occurred.
44 NoError,
45 // We needed to insert (the item did not exist), but we were already at full
46 // size, so we could not insert, which is an error condition that the caller
47 // must handle.
48 CouldNotInsert
49 };
50};
51
52template<typename T, size_t N>
53struct UnorderedFixedStorage : public FixedStorageBase<T, N> {
54 using InsertResult = typename FixedStorageBase<T, N>::InsertResult;
55
56 InsertResult insert(const T& x) {
57 for (size_t i = 0; i < this->used; i++) {
58 if (this->storage[i] == x) {
59 return InsertResult::NoError;
60 }
61 }
62 assert(this->used <= N);
63 if (this->used == N) {
64 return InsertResult::CouldNotInsert;
65 }
66 this->storage[this->used++] = x;
67 return InsertResult::NoError;
68 }
69
70 void erase(const T& x) {
71 for (size_t i = 0; i < this->used; i++) {
72 if (this->storage[i] == x) {
73 // We found the item; erase it by moving the final item to replace it
74 // and truncating the size.
75 this->used--;
76 this->storage[i] = this->storage[this->used];
77 return;
78 }
79 }
80 }
81};
82
83template<typename T, size_t N>
84struct OrderedFixedStorage : public FixedStorageBase<T, N> {
85 using InsertResult = typename FixedStorageBase<T, N>::InsertResult;
86
87 InsertResult insert(const T& x) {
88 // Find the insertion point |i| where x should be placed.
89 size_t i = 0;
90 while (i < this->used && this->storage[i] < x) {
91 i++;
92 }
93 if (i < this->used && this->storage[i] == x) {
94 // The item already exists.
95 return InsertResult::NoError;
96 }
97 // |i| is now the location where x should be placed.
98
99 assert(this->used <= N);
100 if (this->used == N) {
101 return InsertResult::CouldNotInsert;
102 }
103
104 if (i != this->used) {
105 // Push things forward to make room for x.
106 for (size_t j = this->used; j >= i + 1; j--) {
107 this->storage[j] = this->storage[j - 1];
108 }
109 }
110
111 this->storage[i] = x;
112 this->used++;
113 return InsertResult::NoError;
114 }
115
116 void erase(const T& x) {
117 for (size_t i = 0; i < this->used; i++) {
118 if (this->storage[i] == x) {
119 // We found the item; move things backwards and shrink.
120 for (size_t j = i + 1; j < this->used; j++) {
121 this->storage[j - 1] = this->storage[j];
122 }
123 this->used--;
124 return;
125 }
126 }
127 }
128};
129
130template<typename T, size_t N, typename FixedStorage, typename FlexibleSet>
131class SmallSetBase {
132 // fixed-space storage
133 FixedStorage fixed;
134
135 // flexible additional storage
136 FlexibleSet flexible;
137
138 bool usingFixed() const {
139 // If the flexible storage contains something, then we are using it.
140 // Otherwise we use the fixed storage. Note that if we grow and shrink then
141 // we will stay in flexible mode until we reach a size of zero, at which
142 // point we return to fixed mode. This is intentional, to avoid a lot of
143 // movement in switching between fixed and flexible mode.
144 return flexible.empty();
145 }
146
147public:
148 using value_type = T;
149 using key_type = T;
150 using reference = T&;
151 using const_reference = const T&;
152 using set_type = FlexibleSet;
153 using size_type = size_t;
154
155 SmallSetBase() {}
156 SmallSetBase(std::initializer_list<T> init) {
157 for (T item : init) {
158 insert(item);
159 }
160 }
161
162 void insert(const T& x) {
163 if (usingFixed()) {
164 if (fixed.insert(x) == FixedStorage::InsertResult::CouldNotInsert) {
165 // We need to add an item but no fixed storage remains to grow. Switch
166 // to flexible.
167 assert(fixed.used == N);
168 assert(flexible.empty());
169 flexible.insert(fixed.storage.begin(),
170 fixed.storage.begin() + fixed.used);
171 flexible.insert(x);
172 assert(!usingFixed());
173 fixed.used = 0;
174 }
175 } else {
176 flexible.insert(x);
177 }
178 }
179
180 void erase(const T& x) {
181 if (usingFixed()) {
182 fixed.erase(x);
183 } else {
184 flexible.erase(x);
185 }
186 }
187
188 size_t count(const T& x) const {
189 if (usingFixed()) {
190 // Do a linear search.
191 for (size_t i = 0; i < fixed.used; i++) {
192 if (fixed.storage[i] == x) {
193 return 1;
194 }
195 }
196 return 0;
197 } else {
198 return flexible.count(x);
199 }
200 }
201
202 size_t size() const {
203 if (usingFixed()) {
204 return fixed.used;
205 } else {
206 return flexible.size();
207 }
208 }
209
210 bool empty() const { return size() == 0; }
211
212 void clear() {
213 fixed.used = 0;
214 flexible.clear();
215 }
216
217 bool
218 operator==(const SmallSetBase<T, N, FixedStorage, FlexibleSet>& other) const {
219 if (size() != other.size()) {
220 return false;
221 }
222 if (usingFixed()) {
223 return std::all_of(fixed.storage.begin(),
224 fixed.storage.begin() + fixed.used,
225 [&other](const T& x) { return other.count(x); });
226 } else if (other.usingFixed()) {
227 return std::all_of(other.fixed.storage.begin(),
228 other.fixed.storage.begin() + other.fixed.used,
229 [this](const T& x) { return count(x); });
230 } else {
231 return flexible == other.flexible;
232 }
233 }
234
235 bool
236 operator!=(const SmallSetBase<T, N, FixedStorage, FlexibleSet>& other) const {
237 return !(*this == other);
238 }
239
240 // iteration
241
242 template<typename Parent, typename FlexibleIterator> struct IteratorBase {
243 using iterator_category = std::forward_iterator_tag;
244 using difference_type = long;
245 using value_type = T;
246 using pointer = const value_type*;
247 using reference = const value_type&;
248
249 const Parent* parent;
250
251 using Iterator = IteratorBase<Parent, FlexibleIterator>;
252
253 // Whether we are using fixed storage in the parent. When doing so we have
254 // the index in fixedIndex. Otherwise, we are using flexible storage, and we
255 // will use flexibleIterator.
256 bool usingFixed;
257 size_t fixedIndex;
258 FlexibleIterator flexibleIterator;
259
260 IteratorBase(const Parent* parent)
261 : parent(parent), usingFixed(parent->usingFixed()) {}
262
263 void setBegin() {
264 if (usingFixed) {
265 fixedIndex = 0;
266 } else {
267 flexibleIterator = parent->flexible.begin();
268 }
269 }
270
271 void setEnd() {
272 if (usingFixed) {
273 fixedIndex = parent->size();
274 } else {
275 flexibleIterator = parent->flexible.end();
276 }
277 }
278
279 bool operator==(const Iterator& other) const {
280 if (parent != other.parent) {
281 return false;
282 }
283 // std::set allows changes while iterating. For us here, though, it would
284 // be nontrivial to support that given we have two iterators that we
285 // generalize over (switching "in the middle" would not be easy or fast),
286 // so error on that.
287 if (usingFixed != other.usingFixed) {
288 Fatal() << "SmallSet does not support changes while iterating";
289 }
290 if (usingFixed) {
291 return fixedIndex == other.fixedIndex;
292 } else {
293 return flexibleIterator == other.flexibleIterator;
294 }
295 }
296
297 bool operator!=(const Iterator& other) const { return !(*this == other); }
298
299 Iterator& operator++() {
300 if (usingFixed) {
301 fixedIndex++;
302 } else {
303 flexibleIterator++;
304 }
305 return *this;
306 }
307
308 const value_type& operator*() const {
309 if (this->usingFixed) {
310 return this->parent->fixed.storage[this->fixedIndex];
311 } else {
312 return *this->flexibleIterator;
313 }
314 }
315 };
316
317 using Iterator = IteratorBase<SmallSetBase<T, N, FixedStorage, FlexibleSet>,
318 typename FlexibleSet::const_iterator>;
319
320 Iterator begin() {
321 auto ret = Iterator(this);
322 ret.setBegin();
323 return ret;
324 }
325 Iterator end() {
326 auto ret = Iterator(this);
327 ret.setEnd();
328 return ret;
329 }
330 Iterator begin() const {
331 auto ret = Iterator(this);
332 ret.setBegin();
333 return ret;
334 }
335 Iterator end() const {
336 auto ret = Iterator(this);
337 ret.setEnd();
338 return ret;
339 }
340
341 using iterator = Iterator;
342 using const_iterator = Iterator;
343
344 // Test-only method to allow unit tests to verify the right internal
345 // behavior.
346 bool TEST_ONLY_NEVER_USE_usingFixed() { return usingFixed(); }
347};
348
349template<typename T, size_t N>
350class SmallSet
351 : public SmallSetBase<T, N, OrderedFixedStorage<T, N>, std::set<T>> {};
352
353template<typename T, size_t N>
354class SmallUnorderedSet : public SmallSetBase<T,
355 N,
356 UnorderedFixedStorage<T, N>,
357 std::unordered_set<T>> {};
358
359} // namespace wasm
360
361#endif // wasm_support_small_set_h
362

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