1/*
2 * Copyright (C) 2008 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 <memory>
32#include <wtf/Assertions.h>
33#include <wtf/CheckedArithmetic.h>
34
35// This was used to declare and define a static local variable (static T;) so that
36// it was leaked so that its destructors were not called at exit.
37// Newly written code should use static NeverDestroyed<T> instead.
38#ifndef DEPRECATED_DEFINE_STATIC_LOCAL
39#define DEPRECATED_DEFINE_STATIC_LOCAL(type, name, arguments) \
40 static type& name = *new type arguments
41#endif
42
43// Use this macro to declare and define a debug-only global variable that may have a
44// non-trivial constructor and destructor. When building with clang, this will suppress
45// warnings about global constructors and exit-time destructors.
46#define DEFINE_GLOBAL_FOR_LOGGING(type, name, arguments) \
47 _Pragma("clang diagnostic push") \
48 _Pragma("clang diagnostic ignored \"-Wglobal-constructors\"") \
49 _Pragma("clang diagnostic ignored \"-Wexit-time-destructors\"") \
50 static type name arguments; \
51 _Pragma("clang diagnostic pop")
52
53#ifndef NDEBUG
54#if COMPILER(CLANG)
55#define DEFINE_DEBUG_ONLY_GLOBAL(type, name, arguments) DEFINE_GLOBAL_FOR_LOGGING(type, name, arguments)
56#else
57#define DEFINE_DEBUG_ONLY_GLOBAL(type, name, arguments) \
58 static type name arguments;
59#endif // COMPILER(CLANG)
60#else
61#define DEFINE_DEBUG_ONLY_GLOBAL(type, name, arguments)
62#endif // NDEBUG
63
64// OBJECT_OFFSETOF: Like the C++ offsetof macro, but you can use it with classes.
65// The magic number 0x4000 is insignificant. We use it to avoid using NULL, since
66// NULL can cause compiler problems, especially in cases of multiple inheritance.
67#define OBJECT_OFFSETOF(class, field) (reinterpret_cast<ptrdiff_t>(&(reinterpret_cast<class*>(0x4000)->field)) - 0x4000)
68
69// STRINGIZE: Can convert any value to quoted string, even expandable macros
70#define STRINGIZE(exp) #exp
71#define STRINGIZE_VALUE_OF(exp) STRINGIZE(exp)
72
73/*
74 * The reinterpret_cast<Type1*>([pointer to Type2]) expressions - where
75 * sizeof(Type1) > sizeof(Type2) - cause the following warning on ARM with GCC:
76 * increases required alignment of target type.
77 *
78 * An implicit or an extra static_cast<void*> bypasses the warning.
79 * For more info see the following bugzilla entries:
80 * - https://bugs.webkit.org/show_bug.cgi?id=38045
81 * - http://gcc.gnu.org/bugzilla/show_bug.cgi?id=43976
82 */
83#if (CPU(ARM) || CPU(MIPS)) && COMPILER(GCC_OR_CLANG)
84template<typename Type>
85inline bool isPointerTypeAlignmentOkay(Type* ptr)
86{
87 return !(reinterpret_cast<intptr_t>(ptr) % __alignof__(Type));
88}
89
90template<typename TypePtr>
91inline TypePtr reinterpret_cast_ptr(void* ptr)
92{
93 ASSERT(isPointerTypeAlignmentOkay(reinterpret_cast<TypePtr>(ptr)));
94 return reinterpret_cast<TypePtr>(ptr);
95}
96
97template<typename TypePtr>
98inline TypePtr reinterpret_cast_ptr(const void* ptr)
99{
100 ASSERT(isPointerTypeAlignmentOkay(reinterpret_cast<TypePtr>(ptr)));
101 return reinterpret_cast<TypePtr>(ptr);
102}
103#else
104template<typename Type>
105inline bool isPointerTypeAlignmentOkay(Type*)
106{
107 return true;
108}
109#define reinterpret_cast_ptr reinterpret_cast
110#endif
111
112namespace WTF {
113
114enum CheckMoveParameterTag { CheckMoveParameter };
115
116static const size_t KB = 1024;
117static const size_t MB = 1024 * 1024;
118
119inline bool isPointerAligned(void* p)
120{
121 return !((intptr_t)(p) & (sizeof(char*) - 1));
122}
123
124inline bool is8ByteAligned(void* p)
125{
126 return !((uintptr_t)(p) & (sizeof(double) - 1));
127}
128
129/*
130 * C++'s idea of a reinterpret_cast lacks sufficient cojones.
131 */
132template<typename ToType, typename FromType>
133inline ToType bitwise_cast(FromType from)
134{
135 static_assert(sizeof(FromType) == sizeof(ToType), "bitwise_cast size of FromType and ToType must be equal!");
136 union {
137 FromType from;
138 ToType to;
139 } u;
140 u.from = from;
141 return u.to;
142}
143
144template<typename ToType, typename FromType>
145inline ToType safeCast(FromType value)
146{
147 ASSERT(isInBounds<ToType>(value));
148 return static_cast<ToType>(value);
149}
150
151// Returns a count of the number of bits set in 'bits'.
152inline size_t bitCount(unsigned bits)
153{
154 bits = bits - ((bits >> 1) & 0x55555555);
155 bits = (bits & 0x33333333) + ((bits >> 2) & 0x33333333);
156 return (((bits + (bits >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24;
157}
158
159inline size_t bitCount(uint64_t bits)
160{
161 return bitCount(static_cast<unsigned>(bits)) + bitCount(static_cast<unsigned>(bits >> 32));
162}
163
164// Macro that returns a compile time constant with the length of an array, but gives an error if passed a non-array.
165template<typename T, size_t Size> char (&ArrayLengthHelperFunction(T (&)[Size]))[Size];
166// GCC needs some help to deduce a 0 length array.
167#if COMPILER(GCC_OR_CLANG)
168template<typename T> char (&ArrayLengthHelperFunction(T (&)[0]))[0];
169#endif
170#define WTF_ARRAY_LENGTH(array) sizeof(::WTF::ArrayLengthHelperFunction(array))
171
172// Efficient implementation that takes advantage of powers of two.
173inline size_t roundUpToMultipleOf(size_t divisor, size_t x)
174{
175 ASSERT(divisor && !(divisor & (divisor - 1)));
176 size_t remainderMask = divisor - 1;
177 return (x + remainderMask) & ~remainderMask;
178}
179
180template<size_t divisor> inline size_t roundUpToMultipleOf(size_t x)
181{
182 static_assert(divisor && !(divisor & (divisor - 1)), "divisor must be a power of two!");
183 return roundUpToMultipleOf(divisor, x);
184}
185
186enum BinarySearchMode {
187 KeyMustBePresentInArray,
188 KeyMightNotBePresentInArray,
189 ReturnAdjacentElementIfKeyIsNotPresent
190};
191
192template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey, BinarySearchMode mode>
193inline ArrayElementType* binarySearchImpl(ArrayType& array, size_t size, KeyType key, const ExtractKey& extractKey = ExtractKey())
194{
195 size_t offset = 0;
196 while (size > 1) {
197 size_t pos = (size - 1) >> 1;
198 KeyType val = extractKey(&array[offset + pos]);
199
200 if (val == key)
201 return &array[offset + pos];
202 // The item we are looking for is smaller than the item being check; reduce the value of 'size',
203 // chopping off the right hand half of the array.
204 if (key < val)
205 size = pos;
206 // Discard all values in the left hand half of the array, up to and including the item at pos.
207 else {
208 size -= (pos + 1);
209 offset += (pos + 1);
210 }
211
212 ASSERT(mode != KeyMustBePresentInArray || size);
213 }
214
215 if (mode == KeyMightNotBePresentInArray && !size)
216 return 0;
217
218 ArrayElementType* result = &array[offset];
219
220 if (mode == KeyMightNotBePresentInArray && key != extractKey(result))
221 return 0;
222
223 if (mode == KeyMustBePresentInArray) {
224 ASSERT(size == 1);
225 ASSERT(key == extractKey(result));
226 }
227
228 return result;
229}
230
231// If the element is not found, crash if asserts are enabled, and behave like approximateBinarySearch in release builds.
232template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
233inline ArrayElementType* binarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
234{
235 return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMustBePresentInArray>(array, size, key, extractKey);
236}
237
238// Return zero if the element is not found.
239template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
240inline ArrayElementType* tryBinarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
241{
242 return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMightNotBePresentInArray>(array, size, key, extractKey);
243}
244
245// Return the element that is either to the left, or the right, of where the element would have been found.
246template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
247inline ArrayElementType* approximateBinarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
248{
249 return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, ReturnAdjacentElementIfKeyIsNotPresent>(array, size, key, extractKey);
250}
251
252// Variants of the above that use const.
253template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
254inline ArrayElementType* binarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
255{
256 return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMustBePresentInArray>(const_cast<ArrayType&>(array), size, key, extractKey);
257}
258template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
259inline ArrayElementType* tryBinarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
260{
261 return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMightNotBePresentInArray>(const_cast<ArrayType&>(array), size, key, extractKey);
262}
263template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
264inline ArrayElementType* approximateBinarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
265{
266 return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, ReturnAdjacentElementIfKeyIsNotPresent>(const_cast<ArrayType&>(array), size, key, extractKey);
267}
268
269template<typename VectorType, typename ElementType>
270inline void insertIntoBoundedVector(VectorType& vector, size_t size, const ElementType& element, size_t index)
271{
272 for (size_t i = size; i-- > index + 1;)
273 vector[i] = vector[i - 1];
274 vector[index] = element;
275}
276
277// This is here instead of CompilationThread.h to prevent that header from being included
278// everywhere. The fact that this method, and that header, exist outside of JSC is a bug.
279// https://bugs.webkit.org/show_bug.cgi?id=131815
280WTF_EXPORT_PRIVATE bool isCompilationThread();
281
282} // namespace WTF
283
284// This version of placement new omits a 0 check.
285enum NotNullTag { NotNull };
286inline void* operator new(size_t, NotNullTag, void* location)
287{
288 ASSERT(location);
289 return location;
290}
291
292// This adds various C++14 features for versions of the STL that may not yet have them.
293namespace std {
294// MSVC 2013 supports std::make_unique already.
295#if !defined(_MSC_VER) || _MSC_VER < 1800
296template<class T> struct _Unique_if {
297 typedef unique_ptr<T> _Single_object;
298};
299
300template<class T> struct _Unique_if<T[]> {
301 typedef unique_ptr<T[]> _Unknown_bound;
302};
303
304template<class T, size_t N> struct _Unique_if<T[N]> {
305 typedef void _Known_bound;
306};
307
308template<class T, class... Args> inline typename _Unique_if<T>::_Single_object
309make_unique(Args&&... args)
310{
311 return unique_ptr<T>(new T(std::forward<Args>(args)...));
312}
313
314template<class T> inline typename _Unique_if<T>::_Unknown_bound
315make_unique(size_t n)
316{
317 typedef typename remove_extent<T>::type U;
318 return unique_ptr<T>(new U[n]());
319}
320
321template<class T, class... Args> typename _Unique_if<T>::_Known_bound
322make_unique(Args&&...) = delete;
323#endif
324
325// MSVC 2015 supports these functions.
326#if !COMPILER(MSVC) || _MSC_VER < 1900
327// Compile-time integer sequences
328// http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3658.html
329// (Note that we only implement index_sequence, and not the more generic integer_sequence).
330template<size_t... indexes> struct index_sequence {
331 static size_t size() { return sizeof...(indexes); }
332};
333
334template<size_t currentIndex, size_t...indexes> struct make_index_sequence_helper;
335
336template<size_t...indexes> struct make_index_sequence_helper<0, indexes...> {
337 typedef std::index_sequence<indexes...> type;
338};
339
340template<size_t currentIndex, size_t...indexes> struct make_index_sequence_helper {
341 typedef typename make_index_sequence_helper<currentIndex - 1, currentIndex - 1, indexes...>::type type;
342};
343
344template<size_t length> struct make_index_sequence : public make_index_sequence_helper<length>::type { };
345
346// std::exchange
347template<class T, class U = T>
348T exchange(T& t, U&& newValue)
349{
350 T oldValue = std::move(t);
351 t = std::forward<U>(newValue);
352
353 return oldValue;
354}
355#endif
356
357#if COMPILER_SUPPORTS(CXX_USER_LITERALS)
358// These literals are available in C++14, so once we require C++14 compilers we can get rid of them here.
359// (User-literals need to have a leading underscore so we add it here - the "real" literals don't have underscores).
360namespace literals {
361namespace chrono_literals {
362 constexpr inline chrono::seconds operator"" _s(unsigned long long s)
363 {
364 return chrono::seconds(static_cast<chrono::seconds::rep>(s));
365 }
366
367 constexpr chrono::milliseconds operator"" _ms(unsigned long long ms)
368 {
369 return chrono::milliseconds(static_cast<chrono::milliseconds::rep>(ms));
370 }
371}
372}
373#endif
374
375template<WTF::CheckMoveParameterTag, typename T>
376ALWAYS_INLINE constexpr typename remove_reference<T>::type&& move(T&& value)
377{
378 static_assert(is_lvalue_reference<T>::value, "T is not an lvalue reference; move() is unnecessary.");
379
380 using NonRefQualifiedType = typename remove_reference<T>::type;
381 static_assert(!is_const<NonRefQualifiedType>::value, "T is const qualified.");
382
383 return move(forward<T>(value));
384}
385
386} // namespace std
387
388#define WTFMove(value) std::move<WTF::CheckMoveParameter>(value)
389
390using WTF::KB;
391using WTF::MB;
392using WTF::isCompilationThread;
393using WTF::insertIntoBoundedVector;
394using WTF::isPointerAligned;
395using WTF::is8ByteAligned;
396using WTF::binarySearch;
397using WTF::tryBinarySearch;
398using WTF::approximateBinarySearch;
399using WTF::bitwise_cast;
400using WTF::safeCast;
401
402#if COMPILER_SUPPORTS(CXX_USER_LITERALS)
403// We normally don't want to bring in entire std namespaces, but literals are an exception.
404using namespace std::literals::chrono_literals;
405#endif
406
407#endif // WTF_StdLibExtras_h
408