1/*
2 * Copyright (C) 2015-2018 Apple Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 *
13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#pragma once
27
28#include <wtf/Assertions.h>
29#include <wtf/FastMalloc.h>
30
31namespace JSC { namespace DFG {
32class StructureAbstractValue;
33} } // namespace JSC::DFG
34
35namespace WTF {
36
37// FIXME: This currently only works for types that are pointer-like: they should have the size
38// of a pointer and like a pointer they should not have assignment operators, copy constructors,
39// non-trivial default constructors, and non-trivial destructors. It may be possible to lift all
40// of these restrictions. If we succeeded then this should be renamed to just TinySet.
41// https://bugs.webkit.org/show_bug.cgi?id=145741
42
43template<typename T>
44class TinyPtrSet {
45 static_assert(sizeof(T) == sizeof(void*), "It's in the title of the class.");
46public:
47 TinyPtrSet()
48 : m_pointer(0)
49 {
50 setEmpty();
51 }
52
53 TinyPtrSet(T element)
54 : m_pointer(0)
55 {
56 set(element);
57 }
58
59 ALWAYS_INLINE TinyPtrSet(const TinyPtrSet& other)
60 : m_pointer(0)
61 {
62 copyFrom(other);
63 }
64
65 ALWAYS_INLINE TinyPtrSet& operator=(const TinyPtrSet& other)
66 {
67 if (this == &other)
68 return *this;
69 deleteListIfNecessary();
70 copyFrom(other);
71 return *this;
72 }
73
74 ~TinyPtrSet()
75 {
76 deleteListIfNecessary();
77 }
78
79 void clear()
80 {
81 deleteListIfNecessary();
82 setEmpty();
83 }
84
85 // Returns the only entry if the array has exactly one entry.
86 T onlyEntry() const
87 {
88 if (isThin())
89 return singleEntry();
90 OutOfLineList* list = this->list();
91 if (list->m_length != 1)
92 return T();
93 return list->list()[0];
94 }
95
96 bool isEmpty() const
97 {
98 bool result = isThin() && !singleEntry();
99 if (result)
100 ASSERT(m_pointer != reservedValue);
101 return result;
102 }
103
104 // Returns true if the value was added, or false if the value was already there.
105 ALWAYS_INLINE bool add(T value)
106 {
107 ASSERT(value);
108 if (isThin()) {
109 if (singleEntry() == value)
110 return false;
111 if (!singleEntry()) {
112 set(value);
113 return true;
114 }
115
116 OutOfLineList* list = OutOfLineList::create(defaultStartingSize);
117 list->m_length = 2;
118 list->list()[0] = singleEntry();
119 list->list()[1] = value;
120 set(list);
121 return true;
122 }
123
124 return addOutOfLine(value);
125 }
126
127 bool remove(T value)
128 {
129 if (isThin()) {
130 if (singleEntry() == value) {
131 setEmpty();
132 return true;
133 }
134 return false;
135 }
136
137 OutOfLineList* list = this->list();
138 for (unsigned i = 0; i < list->m_length; ++i) {
139 if (list->list()[i] != value)
140 continue;
141 list->list()[i] = list->list()[--list->m_length];
142 if (!list->m_length) {
143 OutOfLineList::destroy(list);
144 setEmpty();
145 }
146 return true;
147 }
148 return false;
149 }
150
151 bool contains(T value) const
152 {
153 if (isThin())
154 return singleEntry() == value;
155 return containsOutOfLine(value);
156 }
157
158 ALWAYS_INLINE bool merge(const TinyPtrSet& other)
159 {
160 if (other.isThin()) {
161 if (other.singleEntry())
162 return add(other.singleEntry());
163 return false;
164 }
165
166 return mergeOtherOutOfLine(other);
167 }
168
169 template<typename Functor>
170 void forEach(const Functor& functor) const
171 {
172 if (isThin()) {
173 if (!singleEntry())
174 return;
175 functor(singleEntry());
176 return;
177 }
178
179 OutOfLineList* list = this->list();
180 for (unsigned i = 0; i < list->m_length; ++i)
181 functor(list->list()[i]);
182 }
183
184 template<typename Functor>
185 void genericFilter(const Functor& functor)
186 {
187 if (isThin()) {
188 if (!singleEntry())
189 return;
190 if (functor(singleEntry()))
191 return;
192 clear();
193 return;
194 }
195
196 OutOfLineList* list = this->list();
197 for (unsigned i = 0; i < list->m_length; ++i) {
198 if (functor(list->list()[i]))
199 continue;
200 list->list()[i--] = list->list()[--list->m_length];
201 }
202 if (!list->m_length)
203 clear();
204 }
205
206 void filter(const TinyPtrSet& other)
207 {
208 if (other.isThin()) {
209 if (!other.singleEntry() || !contains(other.singleEntry()))
210 clear();
211 else {
212 clear();
213 set(other.singleEntry());
214 }
215 return;
216 }
217
218 genericFilter([&] (T value) { return other.containsOutOfLine(value); });
219 }
220
221 void exclude(const TinyPtrSet& other)
222 {
223 if (other.isThin()) {
224 if (other.singleEntry())
225 remove(other.singleEntry());
226 return;
227 }
228
229 genericFilter([&] (T value) { return !other.containsOutOfLine(value); });
230 }
231
232 bool isSubsetOf(const TinyPtrSet& other) const
233 {
234 if (isThin()) {
235 if (!singleEntry())
236 return true;
237 return other.contains(singleEntry());
238 }
239
240 if (other.isThin()) {
241 if (!other.singleEntry())
242 return false;
243 OutOfLineList* list = this->list();
244 if (list->m_length >= 2)
245 return false;
246 if (list->list()[0] == other.singleEntry())
247 return true;
248 return false;
249 }
250
251 OutOfLineList* list = this->list();
252 for (unsigned i = 0; i < list->m_length; ++i) {
253 if (!other.containsOutOfLine(list->list()[i]))
254 return false;
255 }
256 return true;
257 }
258
259 bool isSupersetOf(const TinyPtrSet& other) const
260 {
261 return other.isSubsetOf(*this);
262 }
263
264 bool overlaps(const TinyPtrSet& other) const
265 {
266 if (isThin()) {
267 if (!singleEntry())
268 return false;
269 return other.contains(singleEntry());
270 }
271
272 if (other.isThin()) {
273 if (!other.singleEntry())
274 return false;
275 return containsOutOfLine(other.singleEntry());
276 }
277
278 OutOfLineList* list = this->list();
279 for (unsigned i = 0; i < list->m_length; ++i) {
280 if (other.containsOutOfLine(list->list()[i]))
281 return true;
282 }
283 return false;
284 }
285
286 size_t size() const
287 {
288 if (isThin())
289 return !!singleEntry();
290 return list()->m_length;
291 }
292
293 T at(size_t i) const
294 {
295 if (isThin()) {
296 ASSERT(!i);
297 ASSERT(singleEntry());
298 return singleEntry();
299 }
300 ASSERT(i < list()->m_length);
301 return list()->list()[i];
302 }
303
304 T operator[](size_t i) const { return at(i); }
305
306 T last() const
307 {
308 if (isThin()) {
309 ASSERT(singleEntry());
310 return singleEntry();
311 }
312 return list()->list()[list()->m_length - 1];
313 }
314
315 class iterator {
316 public:
317 iterator()
318 : m_set(nullptr)
319 , m_index(0)
320 {
321 }
322
323 iterator(const TinyPtrSet* set, size_t index)
324 : m_set(set)
325 , m_index(index)
326 {
327 }
328
329 T operator*() const { return m_set->at(m_index); }
330 iterator& operator++()
331 {
332 m_index++;
333 return *this;
334 }
335 bool operator==(const iterator& other) const { return m_index == other.m_index; }
336 bool operator!=(const iterator& other) const { return !(*this == other); }
337
338 private:
339 const TinyPtrSet* m_set;
340 size_t m_index;
341 };
342
343 iterator begin() const { return iterator(this, 0); }
344 iterator end() const { return iterator(this, size()); }
345
346 bool operator==(const TinyPtrSet& other) const
347 {
348 if (size() != other.size())
349 return false;
350 return isSubsetOf(other);
351 }
352
353 bool operator!=(const TinyPtrSet& other) const
354 {
355 return !(*this == other);
356 }
357
358private:
359 friend class JSC::DFG::StructureAbstractValue;
360
361 static const uintptr_t fatFlag = 1;
362 static const uintptr_t reservedFlag = 2;
363 static const uintptr_t flags = fatFlag | reservedFlag;
364 static const uintptr_t reservedValue = 4;
365
366 static const unsigned defaultStartingSize = 4;
367
368 NEVER_INLINE bool addOutOfLine(T value)
369 {
370 OutOfLineList* list = this->list();
371 for (unsigned i = 0; i < list->m_length; ++i) {
372 if (list->list()[i] == value)
373 return false;
374 }
375
376 if (list->m_length < list->m_capacity) {
377 list->list()[list->m_length++] = value;
378 return true;
379 }
380
381 OutOfLineList* newList = OutOfLineList::create(list->m_capacity * 2);
382 newList->m_length = list->m_length + 1;
383 for (unsigned i = list->m_length; i--;)
384 newList->list()[i] = list->list()[i];
385 newList->list()[list->m_length] = value;
386 OutOfLineList::destroy(list);
387 set(newList);
388 return true;
389 }
390
391 NEVER_INLINE bool mergeOtherOutOfLine(const TinyPtrSet& other)
392 {
393 OutOfLineList* list = other.list();
394 if (list->m_length >= 2) {
395 if (isThin()) {
396 OutOfLineList* myNewList = OutOfLineList::create(
397 list->m_length + !!singleEntry());
398 if (singleEntry()) {
399 myNewList->m_length = 1;
400 myNewList->list()[0] = singleEntry();
401 }
402 set(myNewList);
403 }
404 bool changed = false;
405 for (unsigned i = 0; i < list->m_length; ++i)
406 changed |= addOutOfLine(list->list()[i]);
407 return changed;
408 }
409
410 ASSERT(list->m_length);
411 return add(list->list()[0]);
412 }
413
414 bool containsOutOfLine(T value) const
415 {
416 OutOfLineList* list = this->list();
417 for (unsigned i = 0; i < list->m_length; ++i) {
418 if (list->list()[i] == value)
419 return true;
420 }
421 return false;
422 }
423
424 ALWAYS_INLINE void copyFrom(const TinyPtrSet& other)
425 {
426 if (other.isThin() || other.m_pointer == reservedValue) {
427 bool value = getReservedFlag();
428 m_pointer = other.m_pointer;
429 setReservedFlag(value);
430 return;
431 }
432 copyFromOutOfLine(other);
433 }
434
435 NEVER_INLINE void copyFromOutOfLine(const TinyPtrSet& other)
436 {
437 ASSERT(!other.isThin() && other.m_pointer != reservedValue);
438 OutOfLineList* otherList = other.list();
439 OutOfLineList* myList = OutOfLineList::create(otherList->m_length);
440 myList->m_length = otherList->m_length;
441 for (unsigned i = otherList->m_length; i--;)
442 myList->list()[i] = otherList->list()[i];
443 set(myList);
444 }
445
446 class OutOfLineList {
447 public:
448 static OutOfLineList* create(unsigned capacity)
449 {
450 return new (NotNull, fastMalloc(sizeof(OutOfLineList) + capacity * sizeof(T))) OutOfLineList(0, capacity);
451 }
452
453 static void destroy(OutOfLineList* list)
454 {
455 fastFree(list);
456 }
457
458 T* list() { return bitwise_cast<T*>(this + 1); }
459
460 OutOfLineList(unsigned length, unsigned capacity)
461 : m_length(length)
462 , m_capacity(capacity)
463 {
464 }
465
466 unsigned m_length;
467 unsigned m_capacity;
468 };
469
470 ALWAYS_INLINE void deleteListIfNecessary()
471 {
472 if (!isThin()) {
473 ASSERT(m_pointer != reservedValue);
474 OutOfLineList::destroy(list());
475 }
476 }
477
478 bool isThin() const { return !(m_pointer & fatFlag); }
479
480 void* pointer() const
481 {
482 return bitwise_cast<void*>(m_pointer & ~flags);
483 }
484
485 T singleEntry() const
486 {
487 ASSERT(isThin());
488 return bitwise_cast<T>(pointer());
489 }
490
491 OutOfLineList* list() const
492 {
493 ASSERT(!isThin());
494 return static_cast<OutOfLineList*>(pointer());
495 }
496
497 void set(T value)
498 {
499 set(bitwise_cast<uintptr_t>(value), true);
500 }
501 void set(OutOfLineList* list)
502 {
503 set(bitwise_cast<uintptr_t>(list), false);
504 }
505 void setEmpty()
506 {
507 set(0, true);
508 }
509 void set(uintptr_t pointer, bool singleEntry)
510 {
511 m_pointer = pointer | (singleEntry ? 0 : fatFlag) | (m_pointer & reservedFlag);
512 }
513 bool getReservedFlag() const { return m_pointer & reservedFlag; }
514 void setReservedFlag(bool value)
515 {
516 if (value)
517 m_pointer |= reservedFlag;
518 else
519 m_pointer &= ~reservedFlag;
520 }
521
522 uintptr_t m_pointer;
523};
524
525} // namespace WTF
526
527using WTF::TinyPtrSet;
528