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