FastBitVector should have efficient and easy-to-use vector-vector operations
[WebKit-https.git] / Source / WTF / wtf / StdLibExtras.h
1 /*
2  * Copyright (C) 2008, 2016 Apple Inc. All Rights Reserved.
3  * Copyright (C) 2013 Patrick Gansterer <paroga@paroga.com>
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  * 1. Redistributions of source code must retain the above copyright
9  *    notice, this list of conditions and the following disclaimer.
10  * 2. Redistributions in binary form must reproduce the above copyright
11  *    notice, this list of conditions and the following disclaimer in the
12  *    documentation and/or other materials provided with the distribution.
13  *
14  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
15  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
17  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
18  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
19  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
20  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
21  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
22  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
24  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
25  */
26
27 #ifndef WTF_StdLibExtras_h
28 #define WTF_StdLibExtras_h
29
30 #include <chrono>
31 #include <cstring>
32 #include <memory>
33 #include <wtf/Assertions.h>
34 #include <wtf/CheckedArithmetic.h>
35 #include <wtf/Compiler.h>
36
37 // This was used to declare and define a static local variable (static T;) so that
38 //  it was leaked so that its destructors were not called at exit.
39 // Newly written code should use static NeverDestroyed<T> instead.
40 #ifndef DEPRECATED_DEFINE_STATIC_LOCAL
41 #define DEPRECATED_DEFINE_STATIC_LOCAL(type, name, arguments) \
42     static type& name = *new type arguments
43 #endif
44
45 // Use this macro to declare and define a debug-only global variable that may have a
46 // non-trivial constructor and destructor. When building with clang, this will suppress
47 // warnings about global constructors and exit-time destructors.
48 #define DEFINE_GLOBAL_FOR_LOGGING(type, name, arguments) \
49     _Pragma("clang diagnostic push") \
50     _Pragma("clang diagnostic ignored \"-Wglobal-constructors\"") \
51     _Pragma("clang diagnostic ignored \"-Wexit-time-destructors\"") \
52     static type name arguments; \
53     _Pragma("clang diagnostic pop")
54
55 #ifndef NDEBUG
56 #if COMPILER(CLANG)
57 #define DEFINE_DEBUG_ONLY_GLOBAL(type, name, arguments) DEFINE_GLOBAL_FOR_LOGGING(type, name, arguments)
58 #else
59 #define DEFINE_DEBUG_ONLY_GLOBAL(type, name, arguments) \
60     static type name arguments;
61 #endif // COMPILER(CLANG)
62 #else
63 #define DEFINE_DEBUG_ONLY_GLOBAL(type, name, arguments)
64 #endif // NDEBUG
65
66 // OBJECT_OFFSETOF: Like the C++ offsetof macro, but you can use it with classes.
67 // The magic number 0x4000 is insignificant. We use it to avoid using NULL, since
68 // NULL can cause compiler problems, especially in cases of multiple inheritance.
69 #define OBJECT_OFFSETOF(class, field) (reinterpret_cast<ptrdiff_t>(&(reinterpret_cast<class*>(0x4000)->field)) - 0x4000)
70
71 // STRINGIZE: Can convert any value to quoted string, even expandable macros
72 #define STRINGIZE(exp) #exp
73 #define STRINGIZE_VALUE_OF(exp) STRINGIZE(exp)
74
75 // WTF_CONCAT: concatenate two symbols into one, even expandable macros
76 #define WTF_CONCAT_INTERNAL_DONT_USE(a, b) a ## b
77 #define WTF_CONCAT(a, b) WTF_CONCAT_INTERNAL_DONT_USE(a, b)
78
79
80 // Make "PRId64" format specifier work for Visual C++ on Windows.
81 #if OS(WINDOWS) && !defined(PRId64)
82 #define PRId64 "lld"
83 #endif
84
85 /*
86  * The reinterpret_cast<Type1*>([pointer to Type2]) expressions - where
87  * sizeof(Type1) > sizeof(Type2) - cause the following warning on ARM with GCC:
88  * increases required alignment of target type.
89  *
90  * An implicit or an extra static_cast<void*> bypasses the warning.
91  * For more info see the following bugzilla entries:
92  * - https://bugs.webkit.org/show_bug.cgi?id=38045
93  * - http://gcc.gnu.org/bugzilla/show_bug.cgi?id=43976
94  */
95 #if (CPU(ARM) || CPU(MIPS)) && COMPILER(GCC_OR_CLANG)
96 template<typename Type>
97 inline bool isPointerTypeAlignmentOkay(Type* ptr)
98 {
99     return !(reinterpret_cast<intptr_t>(ptr) % __alignof__(Type));
100 }
101
102 template<typename TypePtr>
103 inline TypePtr reinterpret_cast_ptr(void* ptr)
104 {
105     ASSERT(isPointerTypeAlignmentOkay(reinterpret_cast<TypePtr>(ptr)));
106     return reinterpret_cast<TypePtr>(ptr);
107 }
108
109 template<typename TypePtr>
110 inline TypePtr reinterpret_cast_ptr(const void* ptr)
111 {
112     ASSERT(isPointerTypeAlignmentOkay(reinterpret_cast<TypePtr>(ptr)));
113     return reinterpret_cast<TypePtr>(ptr);
114 }
115 #else
116 template<typename Type>
117 inline bool isPointerTypeAlignmentOkay(Type*)
118 {
119     return true;
120 }
121 #define reinterpret_cast_ptr reinterpret_cast
122 #endif
123
124 namespace WTF {
125
126 enum CheckMoveParameterTag { CheckMoveParameter };
127
128 static const size_t KB = 1024;
129 static const size_t MB = 1024 * 1024;
130 static const size_t GB = 1024 * 1024 * 1024;
131
132 inline bool isPointerAligned(void* p)
133 {
134     return !((intptr_t)(p) & (sizeof(char*) - 1));
135 }
136
137 inline bool is8ByteAligned(void* p)
138 {
139     return !((uintptr_t)(p) & (sizeof(double) - 1));
140 }
141
142 /*
143  * C++'s idea of a reinterpret_cast lacks sufficient cojones.
144  */
145 template<typename ToType, typename FromType>
146 inline ToType bitwise_cast(FromType from)
147 {
148     static_assert(sizeof(FromType) == sizeof(ToType), "bitwise_cast size of FromType and ToType must be equal!");
149 #if COMPILER_SUPPORTS(BUILTIN_IS_TRIVIALLY_COPYABLE)
150     // Not all recent STL implementations support the std::is_trivially_copyable type trait. Work around this by only checking on toolchains which have the equivalent compiler intrinsic.
151     static_assert(__is_trivially_copyable(ToType), "bitwise_cast of non-trivially-copyable type!");
152     static_assert(__is_trivially_copyable(FromType), "bitwise_cast of non-trivially-copyable type!");
153 #endif
154     typename std::remove_const<ToType>::type to { };
155     std::memcpy(&to, &from, sizeof(to));
156     return to;
157 }
158
159 template<typename ToType, typename FromType>
160 inline ToType safeCast(FromType value)
161 {
162     ASSERT(isInBounds<ToType>(value));
163     return static_cast<ToType>(value);
164 }
165
166 // Returns a count of the number of bits set in 'bits'.
167 inline size_t bitCount(unsigned bits)
168 {
169     bits = bits - ((bits >> 1) & 0x55555555);
170     bits = (bits & 0x33333333) + ((bits >> 2) & 0x33333333);
171     return (((bits + (bits >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24;
172 }
173
174 inline size_t bitCount(uint64_t bits)
175 {
176     return bitCount(static_cast<unsigned>(bits)) + bitCount(static_cast<unsigned>(bits >> 32));
177 }
178
179 // Macro that returns a compile time constant with the length of an array, but gives an error if passed a non-array.
180 template<typename T, size_t Size> char (&ArrayLengthHelperFunction(T (&)[Size]))[Size];
181 // GCC needs some help to deduce a 0 length array.
182 #if COMPILER(GCC_OR_CLANG)
183 template<typename T> char (&ArrayLengthHelperFunction(T (&)[0]))[0];
184 #endif
185 #define WTF_ARRAY_LENGTH(array) sizeof(::WTF::ArrayLengthHelperFunction(array))
186
187 // Efficient implementation that takes advantage of powers of two.
188 inline size_t roundUpToMultipleOf(size_t divisor, size_t x)
189 {
190     ASSERT(divisor && !(divisor & (divisor - 1)));
191     size_t remainderMask = divisor - 1;
192     return (x + remainderMask) & ~remainderMask;
193 }
194
195 template<size_t divisor> inline size_t roundUpToMultipleOf(size_t x)
196 {
197     static_assert(divisor && !(divisor & (divisor - 1)), "divisor must be a power of two!");
198     return roundUpToMultipleOf(divisor, x);
199 }
200
201 enum BinarySearchMode {
202     KeyMustBePresentInArray,
203     KeyMightNotBePresentInArray,
204     ReturnAdjacentElementIfKeyIsNotPresent
205 };
206
207 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey, BinarySearchMode mode>
208 inline ArrayElementType* binarySearchImpl(ArrayType& array, size_t size, KeyType key, const ExtractKey& extractKey = ExtractKey())
209 {
210     size_t offset = 0;
211     while (size > 1) {
212         size_t pos = (size - 1) >> 1;
213         KeyType val = extractKey(&array[offset + pos]);
214         
215         if (val == key)
216             return &array[offset + pos];
217         // The item we are looking for is smaller than the item being check; reduce the value of 'size',
218         // chopping off the right hand half of the array.
219         if (key < val)
220             size = pos;
221         // Discard all values in the left hand half of the array, up to and including the item at pos.
222         else {
223             size -= (pos + 1);
224             offset += (pos + 1);
225         }
226
227         ASSERT(mode != KeyMustBePresentInArray || size);
228     }
229     
230     if (mode == KeyMightNotBePresentInArray && !size)
231         return 0;
232     
233     ArrayElementType* result = &array[offset];
234
235     if (mode == KeyMightNotBePresentInArray && key != extractKey(result))
236         return 0;
237
238     if (mode == KeyMustBePresentInArray) {
239         ASSERT(size == 1);
240         ASSERT(key == extractKey(result));
241     }
242
243     return result;
244 }
245
246 // If the element is not found, crash if asserts are enabled, and behave like approximateBinarySearch in release builds.
247 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
248 inline ArrayElementType* binarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
249 {
250     return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMustBePresentInArray>(array, size, key, extractKey);
251 }
252
253 // Return zero if the element is not found.
254 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
255 inline ArrayElementType* tryBinarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
256 {
257     return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMightNotBePresentInArray>(array, size, key, extractKey);
258 }
259
260 // Return the element that is either to the left, or the right, of where the element would have been found.
261 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
262 inline ArrayElementType* approximateBinarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
263 {
264     return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, ReturnAdjacentElementIfKeyIsNotPresent>(array, size, key, extractKey);
265 }
266
267 // Variants of the above that use const.
268 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
269 inline ArrayElementType* binarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
270 {
271     return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMustBePresentInArray>(const_cast<ArrayType&>(array), size, key, extractKey);
272 }
273 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
274 inline ArrayElementType* tryBinarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
275 {
276     return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMightNotBePresentInArray>(const_cast<ArrayType&>(array), size, key, extractKey);
277 }
278 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
279 inline ArrayElementType* approximateBinarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
280 {
281     return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, ReturnAdjacentElementIfKeyIsNotPresent>(const_cast<ArrayType&>(array), size, key, extractKey);
282 }
283
284 template<typename VectorType, typename ElementType>
285 inline void insertIntoBoundedVector(VectorType& vector, size_t size, const ElementType& element, size_t index)
286 {
287     for (size_t i = size; i-- > index + 1;)
288         vector[i] = vector[i - 1];
289     vector[index] = element;
290 }
291
292 // This is here instead of CompilationThread.h to prevent that header from being included
293 // everywhere. The fact that this method, and that header, exist outside of JSC is a bug.
294 // https://bugs.webkit.org/show_bug.cgi?id=131815
295 WTF_EXPORT_PRIVATE bool isCompilationThread();
296
297 template<typename Func>
298 bool isStatelessLambda()
299 {
300     return std::is_empty<Func>::value;
301 }
302
303 template<typename ResultType, typename Func, typename... ArgumentTypes>
304 ResultType callStatelessLambda(ArgumentTypes&&... arguments)
305 {
306     uint64_t data[(sizeof(Func) + sizeof(uint64_t) - 1) / sizeof(uint64_t)];
307     memset(data, 0, sizeof(data));
308     return (*bitwise_cast<Func*>(data))(std::forward<ArgumentTypes>(arguments)...);
309 }
310
311 template<typename T, typename U>
312 bool checkAndSet(T& left, U right)
313 {
314     if (left == right)
315         return false;
316     left = right;
317     return true;
318 }
319
320 template<typename T>
321 bool findBitInWord(T word, size_t& index, size_t endIndex, bool value)
322 {
323     static_assert(std::is_unsigned<T>::value, "Type used in findBitInWord must be unsigned");
324     
325     word >>= index;
326     
327     while (index < endIndex) {
328         if ((word & 1) == static_cast<T>(value))
329             return true;
330         index++;
331         word >>= 1;
332     }
333     
334     index = endIndex;
335     return false;
336 }
337
338 // Visitor adapted from http://stackoverflow.com/questions/25338795/is-there-a-name-for-this-tuple-creation-idiom
339
340 template <class A, class... B>
341 struct Visitor : Visitor<A>, Visitor<B...> {
342     Visitor(A a, B... b)
343         : Visitor<A>(a)
344         , Visitor<B...>(b...)
345     {
346     }
347
348     using Visitor<A>::operator ();
349     using Visitor<B...>::operator ();
350 };
351   
352 template <class A>
353 struct Visitor<A> : A {
354     Visitor(A a)
355         : A(a)
356     {
357     }
358
359     using A::operator();
360 };
361  
362 template <class... F>
363 Visitor<F...> makeVisitor(F... f)
364 {
365     return Visitor<F...>(f...);
366 }
367
368 } // namespace WTF
369
370 // This version of placement new omits a 0 check.
371 enum NotNullTag { NotNull };
372 inline void* operator new(size_t, NotNullTag, void* location)
373 {
374     ASSERT(location);
375     return location;
376 }
377
378 // This adds various C++14 features for versions of the STL that may not yet have them.
379 namespace std {
380 #if COMPILER(CLANG) && __cplusplus < 201400L
381 template<class T> struct _Unique_if {
382     typedef unique_ptr<T> _Single_object;
383 };
384
385 template<class T> struct _Unique_if<T[]> {
386     typedef unique_ptr<T[]> _Unknown_bound;
387 };
388
389 template<class T, size_t N> struct _Unique_if<T[N]> {
390     typedef void _Known_bound;
391 };
392
393 template<class T, class... Args> inline typename _Unique_if<T>::_Single_object
394 make_unique(Args&&... args)
395 {
396     return unique_ptr<T>(new T(std::forward<Args>(args)...));
397 }
398
399 template<class T> inline typename _Unique_if<T>::_Unknown_bound
400 make_unique(size_t n)
401 {
402     typedef typename remove_extent<T>::type U;
403     return unique_ptr<T>(new U[n]());
404 }
405
406 template<class T, class... Args> typename _Unique_if<T>::_Known_bound
407 make_unique(Args&&...) = delete;
408
409 // std::exchange
410 template<class T, class U = T>
411 T exchange(T& t, U&& newValue)
412 {
413     T oldValue = std::move(t);
414     t = std::forward<U>(newValue);
415
416     return oldValue;
417 }
418 #endif
419
420 template<WTF::CheckMoveParameterTag, typename T>
421 ALWAYS_INLINE constexpr typename remove_reference<T>::type&& move(T&& value)
422 {
423     static_assert(is_lvalue_reference<T>::value, "T is not an lvalue reference; move() is unnecessary.");
424
425     using NonRefQualifiedType = typename remove_reference<T>::type;
426     static_assert(!is_const<NonRefQualifiedType>::value, "T is const qualified.");
427
428     return move(forward<T>(value));
429 }
430
431 } // namespace std
432
433 #define WTFMove(value) std::move<WTF::CheckMoveParameter>(value)
434
435 using WTF::KB;
436 using WTF::MB;
437 using WTF::approximateBinarySearch;
438 using WTF::binarySearch;
439 using WTF::bitwise_cast;
440 using WTF::callStatelessLambda;
441 using WTF::checkAndSet;
442 using WTF::findBitInWord;
443 using WTF::insertIntoBoundedVector;
444 using WTF::isCompilationThread;
445 using WTF::isPointerAligned;
446 using WTF::isStatelessLambda;
447 using WTF::is8ByteAligned;
448 using WTF::safeCast;
449 using WTF::tryBinarySearch;
450
451 #if !COMPILER(CLANG) || __cplusplus >= 201400L
452 // We normally don't want to bring in entire std namespaces, but literals are an exception.
453 using namespace std::literals::chrono_literals;
454 #endif
455
456 #endif // WTF_StdLibExtras_h