1/*
2 * Copyright (C) 2016 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#include <wtf/HashFunctions.h>
31#include <wtf/Noncopyable.h>
32
33namespace WTF {
34
35template<typename PtrType, unsigned SmallArraySize = 8>
36class SmallPtrSet {
37 WTF_MAKE_NONCOPYABLE(SmallPtrSet);
38 static_assert(std::is_trivially_destructible<PtrType>::value, "We currently don't support non-trivially destructible pointer types.");
39 static_assert(sizeof(PtrType) == sizeof(void*), "Only support pointer sized things.");
40 static_assert(!(SmallArraySize & (SmallArraySize - 1)), "Inline size must be a power of two.");
41
42public:
43 SmallPtrSet()
44 {
45 initialize();
46 }
47
48 // We take care to have SmallPtrSet have partial move semantics allowable through
49 // memcpy. It's partial move semantics because our destructor should not be called
50 // on the SmallPtrObject in the old memory we were moved from (otherwise, we might free m_buffer twice)
51 // unless that old memory is reset to be isSmall(). See move constructor below.
52 // To maintain these semantics, we determine if we're small by checking our size
53 // and not our m_buffer pointer. And when we're small, we don't do operations on
54 // m_buffer, instead, we perform operations on m_smallStorage directly. The reason we want
55 // these semantics is that it's beneficial to have a Vector that contains SmallPtrSet
56 // (or an object with SmallPtrSet as a field) be allowed to use memcpy for its move operation.
57
58 SmallPtrSet(SmallPtrSet&& other)
59 {
60 memcpy(this, &other, sizeof(SmallPtrSet));
61 other.initialize();
62 }
63
64 SmallPtrSet& operator=(SmallPtrSet&& other)
65 {
66 this->~SmallPtrSet();
67 new (this) SmallPtrSet(WTFMove(other));
68 return *this;
69 }
70
71 ~SmallPtrSet()
72 {
73 if (!isSmall())
74 fastFree(m_buffer);
75 }
76
77 inline void add(PtrType ptr)
78 {
79 ASSERT(isValidEntry(ptr));
80
81 if (isSmall()) {
82 for (unsigned i = 0; i < m_size; i++) {
83 if (m_smallStorage[i] == ptr)
84 return;
85 }
86
87 if (m_size < SmallArraySize) {
88 m_smallStorage[m_size] = ptr;
89 ++m_size;
90 return;
91 }
92
93 grow(std::max(64u, SmallArraySize * 2));
94 // Fall through. We're no longer small :(
95 }
96
97 // If we're more than 3/4ths full we grow.
98 if (UNLIKELY(m_size * 4 >= m_capacity * 3)) {
99 grow(m_capacity * 2);
100 ASSERT(!(m_capacity & (m_capacity - 1)));
101 }
102
103 void** bucket = this->bucket(ptr);
104 if (*bucket != ptr) {
105 *bucket = ptr;
106 ++m_size;
107 }
108 }
109
110 inline bool contains(PtrType ptr) const
111 {
112 ASSERT(isValidEntry(ptr));
113 if (isSmall()) {
114 for (unsigned i = 0; i < m_size; i++) { // We only need to search up to m_size because we store things linearly inside m_smallStorage.
115 if (m_smallStorage[i] == ptr)
116 return true;
117 }
118 return false;
119 }
120
121 void** bucket = this->bucket(ptr);
122 return *bucket == ptr;
123 }
124
125 class iterator {
126 public:
127 iterator& operator++()
128 {
129 m_index++;
130 ASSERT(m_index <= m_capacity);
131 while (m_index < m_capacity && m_buffer[m_index] == emptyValue())
132 m_index++;
133 return *this;
134 }
135
136 PtrType operator*() const { ASSERT(m_index < m_capacity); return static_cast<PtrType>(m_buffer[m_index]); }
137 bool operator==(const iterator& other) const { ASSERT(m_buffer == other.m_buffer); return m_index == other.m_index; }
138 bool operator!=(const iterator& other) const { ASSERT(m_buffer == other.m_buffer); return !(*this == other); }
139
140 private:
141 template<typename U, unsigned S> friend class WTF::SmallPtrSet;
142 unsigned m_index;
143 unsigned m_capacity;
144 void** m_buffer;
145 };
146
147 iterator begin() const
148 {
149 iterator it;
150 it.m_index = std::numeric_limits<unsigned>::max();
151 it.m_capacity = m_capacity;
152 if (isSmall())
153 it.m_buffer = const_cast<void**>(m_smallStorage);
154 else
155 it.m_buffer = m_buffer;
156
157 ++it;
158
159 return it;
160 }
161
162 iterator end() const
163 {
164 iterator it;
165 it.m_index = m_capacity;
166 it.m_capacity = m_capacity;
167 if (isSmall())
168 it.m_buffer = const_cast<void**>(m_smallStorage);
169 else
170 it.m_buffer = m_buffer;
171
172 return it;
173 }
174
175 inline unsigned size() const { return m_size; }
176
177private:
178 constexpr static void* emptyValue()
179 {
180 return bitwise_cast<void*>(std::numeric_limits<uintptr_t>::max());
181 }
182
183 bool isValidEntry(const PtrType ptr) const
184 {
185 return ptr != emptyValue();
186 }
187
188 inline bool isSmall() const
189 {
190 return m_capacity == SmallArraySize;
191 }
192
193 inline void initialize()
194 {
195 m_size = 0;
196 m_buffer = nullptr;
197 m_capacity = SmallArraySize;
198 memset(m_smallStorage, -1, sizeof(void*) * SmallArraySize);
199 ASSERT(isSmall());
200 }
201
202 inline void grow(unsigned size)
203 {
204 ASSERT(static_cast<int32_t>(bitwise_cast<intptr_t>(emptyValue())) == -1);
205
206 size_t allocationSize = sizeof(void*) * size;
207 bool wasSmall = isSmall();
208 void** oldBuffer = wasSmall ? m_smallStorage : m_buffer;
209 unsigned oldCapacity = m_capacity;
210 m_buffer = static_cast<void**>(fastMalloc(allocationSize));
211 memset(m_buffer, -1, allocationSize);
212 m_capacity = size;
213
214 for (unsigned i = 0; i < oldCapacity; i++) {
215 if (oldBuffer[i] != emptyValue()) {
216 void** ptr = this->bucket(static_cast<PtrType>(oldBuffer[i]));
217 *ptr = oldBuffer[i];
218 }
219 }
220
221 if (!wasSmall)
222 fastFree(oldBuffer);
223 }
224
225
226 inline void** bucket(PtrType target) const
227 {
228 ASSERT(!(m_capacity & (m_capacity - 1)));
229 unsigned bucket = PtrHashBase<PtrType, false /* isSmartPtr */>::hash(target) & (m_capacity - 1);
230 unsigned index = 0;
231 while (true) {
232 void** ptr = m_buffer + bucket;
233 if (*ptr == emptyValue())
234 return ptr;
235 if (*ptr == target)
236 return ptr;
237 index++;
238 bucket = (bucket + index) & (m_capacity - 1);
239 }
240 }
241
242 unsigned m_size;
243 unsigned m_capacity;
244 void** m_buffer;
245 void* m_smallStorage[SmallArraySize];
246};
247
248} // namespace WTF
249
250using WTF::SmallPtrSet;
251