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