8a3c3614aab0bc61565a7b2e2332470b5219c208
[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 #define reinterpret_cast_ptr reinterpret_cast
106 #endif
107
108 namespace WTF {
109
110 static const size_t KB = 1024;
111
112 inline bool isPointerAligned(void* p)
113 {
114     return !((intptr_t)(p) & (sizeof(char*) - 1));
115 }
116
117 inline bool is8ByteAligned(void* p)
118 {
119     return !((uintptr_t)(p) & (sizeof(double) - 1));
120 }
121
122 /*
123  * C++'s idea of a reinterpret_cast lacks sufficient cojones.
124  */
125 template<typename TO, typename FROM>
126 inline TO bitwise_cast(FROM from)
127 {
128     COMPILE_ASSERT(sizeof(TO) == sizeof(FROM), WTF_bitwise_cast_sizeof_casted_types_is_equal);
129     union {
130         FROM from;
131         TO to;
132     } u;
133     u.from = from;
134     return u.to;
135 }
136
137 template<typename To, typename From>
138 inline To safeCast(From value)
139 {
140     ASSERT(isInBounds<To>(value));
141     return static_cast<To>(value);
142 }
143
144 // Returns a count of the number of bits set in 'bits'.
145 inline size_t bitCount(unsigned bits)
146 {
147     bits = bits - ((bits >> 1) & 0x55555555);
148     bits = (bits & 0x33333333) + ((bits >> 2) & 0x33333333);
149     return (((bits + (bits >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24;
150 }
151
152 // Macro that returns a compile time constant with the length of an array, but gives an error if passed a non-array.
153 template<typename T, size_t Size> char (&ArrayLengthHelperFunction(T (&)[Size]))[Size];
154 // GCC needs some help to deduce a 0 length array.
155 #if COMPILER(GCC)
156 template<typename T> char (&ArrayLengthHelperFunction(T (&)[0]))[0];
157 #endif
158 #define WTF_ARRAY_LENGTH(array) sizeof(::WTF::ArrayLengthHelperFunction(array))
159
160 // Efficient implementation that takes advantage of powers of two.
161 inline size_t roundUpToMultipleOf(size_t divisor, size_t x)
162 {
163     ASSERT(divisor && !(divisor & (divisor - 1)));
164     size_t remainderMask = divisor - 1;
165     return (x + remainderMask) & ~remainderMask;
166 }
167 template<size_t divisor> inline size_t roundUpToMultipleOf(size_t x)
168 {
169     COMPILE_ASSERT(divisor && !(divisor & (divisor - 1)), divisor_is_a_power_of_two);
170     return roundUpToMultipleOf(divisor, x);
171 }
172
173 enum BinarySearchMode {
174     KeyMustBePresentInArray,
175     KeyMustNotBePresentInArray
176 };
177
178 // Binary search algorithm, calls extractKey on pre-sorted elements in array,
179 // compares result with key (KeyTypes should be comparable with '--', '<', '>').
180 template<typename ArrayElementType, typename KeyType, KeyType(*extractKey)(ArrayElementType*)>
181 inline ArrayElementType* binarySearch(ArrayElementType* array, size_t size, KeyType key, BinarySearchMode mode = KeyMustBePresentInArray)
182 {
183     // The array must contain at least one element (pre-condition, array does contain key).
184     // If the array contains only one element, no need to do the comparison.
185     while (size > 1) {
186         // Pick an element to check, half way through the array, and read the value.
187         int pos = (size - 1) >> 1;
188         KeyType val = extractKey(&array[pos]);
189
190         // If the key matches, success!
191         if (val == key)
192             return &array[pos];
193         // The item we are looking for is smaller than the item being check; reduce the value of 'size',
194         // chopping off the right hand half of the array.
195         else if (key < val)
196             size = pos;
197         // Discard all values in the left hand half of the array, up to and including the item at pos.
198         else {
199             size -= (pos + 1);
200             array += (pos + 1);
201         }
202
203         // In case of BinarySearchMode = KeyMustBePresentInArray 'size' should never reach zero.
204         if (mode == KeyMustBePresentInArray)
205             ASSERT(size);
206     }
207
208     // In case of BinarySearchMode = KeyMustBePresentInArray if we reach this point
209     // we've chopped down to one element, no need to check it matches
210     if (mode == KeyMustBePresentInArray) {
211         ASSERT(size == 1);
212         ASSERT(key == extractKey(&array[0]));
213     }
214
215     return &array[0];
216 }
217
218 // Modified binary search algorithm that uses a functor. Note that this is strictly
219 // more powerful than the above, but results in somewhat less template specialization.
220 // Hence, depending on inlining heuristics, it might be slower.
221 template<typename ArrayElementType, typename KeyType, typename ExtractKey>
222 inline ArrayElementType* binarySearchWithFunctor(ArrayElementType* array, size_t size, KeyType key, BinarySearchMode mode = KeyMustBePresentInArray, const ExtractKey& extractKey = ExtractKey())
223 {
224     // The array must contain at least one element (pre-condition, array does contain key).
225     // If the array contains only one element, no need to do the comparison.
226     while (size > 1) {
227         // Pick an element to check, half way through the array, and read the value.
228         int pos = (size - 1) >> 1;
229         KeyType val = extractKey(&array[pos]);
230
231         // If the key matches, success!
232         if (val == key)
233             return &array[pos];
234         // The item we are looking for is smaller than the item being check; reduce the value of 'size',
235         // chopping off the right hand half of the array.
236         else if (key < val)
237             size = pos;
238         // Discard all values in the left hand half of the array, up to and including the item at pos.
239         else {
240             size -= (pos + 1);
241             array += (pos + 1);
242         }
243
244         // In case of BinarySearchMode = KeyMustBePresentInArray 'size' should never reach zero.
245         if (mode == KeyMustBePresentInArray)
246             ASSERT(size);
247     }
248
249     // In case of BinarySearchMode = KeyMustBePresentInArray if we reach this point
250     // we've chopped down to one element, no need to check it matches
251     if (mode == KeyMustBePresentInArray) {
252         ASSERT(size == 1);
253         ASSERT(key == extractKey(&array[0]));
254     }
255
256     return &array[0];
257 }
258
259 // Modified binarySearch() algorithm designed for array-like classes that support
260 // operator[] but not operator+=. One example of a class that qualifies is
261 // SegmentedVector.
262 template<typename ArrayElementType, typename KeyType, KeyType(*extractKey)(ArrayElementType*), typename ArrayType>
263 inline ArrayElementType* genericBinarySearch(ArrayType& array, size_t size, KeyType key)
264 {
265     // The array must contain at least one element (pre-condition, array does conatin key).
266     // If the array only contains one element, no need to do the comparison.
267     size_t offset = 0;
268     while (size > 1) {
269         // Pick an element to check, half way through the array, and read the value.
270         int pos = (size - 1) >> 1;
271         KeyType val = extractKey(&array[offset + pos]);
272         
273         // If the key matches, success!
274         if (val == key)
275             return &array[offset + pos];
276         // The item we are looking for is smaller than the item being check; reduce the value of 'size',
277         // chopping off the right hand half of the array.
278         if (key < val)
279             size = pos;
280         // Discard all values in the left hand half of the array, up to and including the item at pos.
281         else {
282             size -= (pos + 1);
283             offset += (pos + 1);
284         }
285
286         // 'size' should never reach zero.
287         ASSERT(size);
288     }
289     
290     // If we reach this point we've chopped down to one element, no need to check it matches
291     ASSERT(size == 1);
292     ASSERT(key == extractKey(&array[offset]));
293     return &array[offset];
294 }
295
296 } // namespace WTF
297
298 // This version of placement new omits a 0 check.
299 enum NotNullTag { NotNull };
300 inline void* operator new(size_t, NotNullTag, void* location)
301 {
302     ASSERT(location);
303     return location;
304 }
305
306 using WTF::KB;
307 using WTF::isPointerAligned;
308 using WTF::is8ByteAligned;
309 using WTF::binarySearch;
310 using WTF::bitwise_cast;
311 using WTF::safeCast;
312
313 #endif // WTF_StdLibExtras_h