1/*
2 * Copyright (C) 2008 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 WTF_StdLibExtras_h
27#define WTF_StdLibExtras_h
28
29#include "wtf/Assertions.h"
30#include "wtf/CPU.h"
31#include "wtf/CheckedArithmetic.h"
32
33// Use this to declare and define a static local variable (static T;) so that
34//  it is leaked so that its destructors are not called at exit.
35#ifndef DEFINE_STATIC_LOCAL
36#define DEFINE_STATIC_LOCAL(type, name, arguments) \
37    static type& name = *new type arguments
38#endif
39
40// Use this to declare and define a static local pointer to a ref-counted object so that
41// it is leaked so that the object's destructors are not called at exit.
42// This macro should be used with ref-counted objects rather than DEFINE_STATIC_LOCAL macro,
43// as this macro does not lead to an extra memory allocation.
44#ifndef DEFINE_STATIC_REF
45#define DEFINE_STATIC_REF(type, name, arguments) \
46    static type* name = PassRefPtr<type>(arguments).leakRef();
47#endif
48
49// Use this macro to declare and define a debug-only global variable that may have a
50// non-trivial constructor and destructor. When building with clang, this will suppress
51// warnings about global constructors and exit-time destructors.
52#ifndef NDEBUG
53#if COMPILER(CLANG)
54#define DEFINE_DEBUG_ONLY_GLOBAL(type, name, arguments) \
55    _Pragma("clang diagnostic push") \
56    _Pragma("clang diagnostic ignored \"-Wglobal-constructors\"") \
57    _Pragma("clang diagnostic ignored \"-Wexit-time-destructors\"") \
58    static type name arguments; \
59    _Pragma("clang diagnostic pop")
60#else
61#define DEFINE_DEBUG_ONLY_GLOBAL(type, name, arguments) \
62    static type name arguments;
63#endif // COMPILER(CLANG)
64#else
65#define DEFINE_DEBUG_ONLY_GLOBAL(type, name, arguments)
66#endif // NDEBUG
67
68// OBJECT_OFFSETOF: Like the C++ offsetof macro, but you can use it with classes.
69// The magic number 0x4000 is insignificant. We use it to avoid using NULL, since
70// NULL can cause compiler problems, especially in cases of multiple inheritance.
71#define OBJECT_OFFSETOF(class, field) (reinterpret_cast<ptrdiff_t>(&(reinterpret_cast<class*>(0x4000)->field)) - 0x4000)
72
73// STRINGIZE: Can convert any value to quoted string, even expandable macros
74#define STRINGIZE(exp) #exp
75#define STRINGIZE_VALUE_OF(exp) STRINGIZE(exp)
76
77/*
78 * The reinterpret_cast<Type1*>([pointer to Type2]) expressions - where
79 * sizeof(Type1) > sizeof(Type2) - cause the following warning on ARM with GCC:
80 * increases required alignment of target type.
81 *
82 * An implicit or an extra static_cast<void*> bypasses the warning.
83 * For more info see the following bugzilla entries:
84 * - https://bugs.webkit.org/show_bug.cgi?id=38045
85 * - http://gcc.gnu.org/bugzilla/show_bug.cgi?id=43976
86 */
87#if CPU(ARM) && COMPILER(GCC)
88template<typename Type>
89bool isPointerTypeAlignmentOkay(Type* ptr)
90{
91    return !(reinterpret_cast<intptr_t>(ptr) % __alignof__(Type));
92}
93
94template<typename TypePtr>
95TypePtr reinterpret_cast_ptr(void* ptr)
96{
97    ASSERT(isPointerTypeAlignmentOkay(reinterpret_cast<TypePtr>(ptr)));
98    return reinterpret_cast<TypePtr>(ptr);
99}
100
101template<typename TypePtr>
102TypePtr reinterpret_cast_ptr(const void* ptr)
103{
104    ASSERT(isPointerTypeAlignmentOkay(reinterpret_cast<TypePtr>(ptr)));
105    return reinterpret_cast<TypePtr>(ptr);
106}
107#else
108template<typename Type>
109bool isPointerTypeAlignmentOkay(Type*)
110{
111    return true;
112}
113#define reinterpret_cast_ptr reinterpret_cast
114#endif
115
116namespace WTF {
117
118static const size_t KB = 1024;
119static const size_t MB = 1024 * 1024;
120
121inline bool isPointerAligned(void* p)
122{
123    return !((intptr_t)(p) & (sizeof(char*) - 1));
124}
125
126inline bool is8ByteAligned(void* p)
127{
128    return !((uintptr_t)(p) & (sizeof(double) - 1));
129}
130
131/*
132 * C++'s idea of a reinterpret_cast lacks sufficient cojones.
133 */
134template<typename TO, typename FROM>
135inline TO bitwise_cast(FROM from)
136{
137    COMPILE_ASSERT(sizeof(TO) == sizeof(FROM), WTF_bitwise_cast_sizeof_casted_types_is_equal);
138    union {
139        FROM from;
140        TO to;
141    } u;
142    u.from = from;
143    return u.to;
144}
145
146template<typename To, typename From>
147inline To safeCast(From value)
148{
149    ASSERT(isInBounds<To>(value));
150    return static_cast<To>(value);
151}
152
153// Returns a count of the number of bits set in 'bits'.
154inline size_t bitCount(unsigned bits)
155{
156    bits = bits - ((bits >> 1) & 0x55555555);
157    bits = (bits & 0x33333333) + ((bits >> 2) & 0x33333333);
158    return (((bits + (bits >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24;
159}
160
161// Macro that returns a compile time constant with the length of an array, but gives an error if passed a non-array.
162template<typename T, size_t Size> char (&ArrayLengthHelperFunction(T (&)[Size]))[Size];
163// GCC needs some help to deduce a 0 length array.
164#if COMPILER(GCC)
165template<typename T> char (&ArrayLengthHelperFunction(T (&)[0]))[0];
166#endif
167#define WTF_ARRAY_LENGTH(array) sizeof(::WTF::ArrayLengthHelperFunction(array))
168
169// Efficient implementation that takes advantage of powers of two.
170inline size_t roundUpToMultipleOf(size_t divisor, size_t x)
171{
172    ASSERT(divisor && !(divisor & (divisor - 1)));
173    size_t remainderMask = divisor - 1;
174    return (x + remainderMask) & ~remainderMask;
175}
176template<size_t divisor> inline size_t roundUpToMultipleOf(size_t x)
177{
178    COMPILE_ASSERT(divisor && !(divisor & (divisor - 1)), divisor_is_a_power_of_two);
179    return roundUpToMultipleOf(divisor, x);
180}
181
182enum BinarySearchMode {
183    KeyMustBePresentInArray,
184    KeyMightNotBePresentInArray,
185    ReturnAdjacentElementIfKeyIsNotPresent
186};
187
188template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey, BinarySearchMode mode>
189inline ArrayElementType* binarySearchImpl(ArrayType& array, size_t size, KeyType key, const ExtractKey& extractKey = ExtractKey())
190{
191    size_t offset = 0;
192    while (size > 1) {
193        size_t pos = (size - 1) >> 1;
194        KeyType val = extractKey(&array[offset + pos]);
195
196        if (val == key)
197            return &array[offset + pos];
198        // The item we are looking for is smaller than the item being check; reduce the value of 'size',
199        // chopping off the right hand half of the array.
200        if (key < val)
201            size = pos;
202        // Discard all values in the left hand half of the array, up to and including the item at pos.
203        else {
204            size -= (pos + 1);
205            offset += (pos + 1);
206        }
207
208        ASSERT(mode != KeyMustBePresentInArray || size);
209    }
210
211    if (mode == KeyMightNotBePresentInArray && !size)
212        return 0;
213
214    ArrayElementType* result = &array[offset];
215
216    if (mode == KeyMightNotBePresentInArray && key != extractKey(result))
217        return 0;
218
219    if (mode == KeyMustBePresentInArray) {
220        ASSERT(size == 1);
221        ASSERT(key == extractKey(result));
222    }
223
224    return result;
225}
226
227// If the element is not found, crash if asserts are enabled, and behave like approximateBinarySearch in release builds.
228template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
229inline ArrayElementType* binarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
230{
231    return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMustBePresentInArray>(array, size, key, extractKey);
232}
233
234// Return zero if the element is not found.
235template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
236inline ArrayElementType* tryBinarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
237{
238    return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMightNotBePresentInArray>(array, size, key, extractKey);
239}
240
241// Return the element that is either to the left, or the right, of where the element would have been found.
242template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
243inline ArrayElementType* approximateBinarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
244{
245    return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, ReturnAdjacentElementIfKeyIsNotPresent>(array, size, key, extractKey);
246}
247
248// Variants of the above that use const.
249template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
250inline ArrayElementType* binarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
251{
252    return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMustBePresentInArray>(const_cast<ArrayType&>(array), size, key, extractKey);
253}
254template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
255inline ArrayElementType* tryBinarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
256{
257    return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMightNotBePresentInArray>(const_cast<ArrayType&>(array), size, key, extractKey);
258}
259template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
260inline ArrayElementType* approximateBinarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
261{
262    return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, ReturnAdjacentElementIfKeyIsNotPresent>(const_cast<ArrayType&>(array), size, key, extractKey);
263}
264
265} // namespace WTF
266
267// This version of placement new omits a 0 check.
268enum NotNullTag { NotNull };
269inline void* operator new(size_t, NotNullTag, void* location)
270{
271    ASSERT(location);
272    return location;
273}
274
275using WTF::KB;
276using WTF::MB;
277using WTF::isPointerAligned;
278using WTF::is8ByteAligned;
279using WTF::binarySearch;
280using WTF::tryBinarySearch;
281using WTF::approximateBinarySearch;
282using WTF::bitwise_cast;
283using WTF::safeCast;
284
285#endif // WTF_StdLibExtras_h
286