Change a couple of COMPILE_ASSERTs to static_assert
[WebKit-https.git] / Source / WTF / wtf / StdLibExtras.h
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 <wtf/Assertions.h>
31 #include <wtf/CheckedArithmetic.h>
32
33 // Use these 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. Using this
35 //  macro also allows workarounds a compiler bug present in Apple's version of GCC 4.0.1.
36 #ifndef DEFINE_STATIC_LOCAL
37 #if COMPILER(GCC) && defined(__APPLE_CC__) && __GNUC__ == 4 && __GNUC_MINOR__ == 0 && __GNUC_PATCHLEVEL__ == 1
38 #define DEFINE_STATIC_LOCAL(type, name, arguments) \
39     static type* name##Ptr = new type arguments; \
40     type& name = *name##Ptr
41 #else
42 #define DEFINE_STATIC_LOCAL(type, name, arguments) \
43     static type& name = *new type arguments
44 #endif
45 #endif
46
47 // Use this macro to declare and define a debug-only global variable that may have a
48 // non-trivial constructor and destructor. When building with clang, this will suppress
49 // warnings about global constructors and exit-time destructors.
50 #ifndef NDEBUG
51 #if COMPILER(CLANG)
52 #define DEFINE_DEBUG_ONLY_GLOBAL(type, name, arguments) \
53     _Pragma("clang diagnostic push") \
54     _Pragma("clang diagnostic ignored \"-Wglobal-constructors\"") \
55     _Pragma("clang diagnostic ignored \"-Wexit-time-destructors\"") \
56     static type name arguments; \
57     _Pragma("clang diagnostic pop")
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 /*
76  * The reinterpret_cast<Type1*>([pointer to Type2]) expressions - where
77  * sizeof(Type1) > sizeof(Type2) - cause the following warning on ARM with GCC:
78  * increases required alignment of target type.
79  *
80  * An implicit or an extra static_cast<void*> bypasses the warning.
81  * For more info see the following bugzilla entries:
82  * - https://bugs.webkit.org/show_bug.cgi?id=38045
83  * - http://gcc.gnu.org/bugzilla/show_bug.cgi?id=43976
84  */
85 #if (CPU(ARM) || CPU(MIPS)) && COMPILER(GCC)
86 template<typename Type>
87 bool isPointerTypeAlignmentOkay(Type* ptr)
88 {
89     return !(reinterpret_cast<intptr_t>(ptr) % __alignof__(Type));
90 }
91
92 template<typename TypePtr>
93 TypePtr reinterpret_cast_ptr(void* ptr)
94 {
95     ASSERT(isPointerTypeAlignmentOkay(reinterpret_cast<TypePtr>(ptr)));
96     return reinterpret_cast<TypePtr>(ptr);
97 }
98
99 template<typename TypePtr>
100 TypePtr reinterpret_cast_ptr(const void* ptr)
101 {
102     ASSERT(isPointerTypeAlignmentOkay(reinterpret_cast<TypePtr>(ptr)));
103     return reinterpret_cast<TypePtr>(ptr);
104 }
105 #else
106 template<typename Type>
107 bool isPointerTypeAlignmentOkay(Type*)
108 {
109     return true;
110 }
111 #define reinterpret_cast_ptr reinterpret_cast
112 #endif
113
114 namespace WTF {
115
116 static const size_t KB = 1024;
117 static const size_t MB = 1024 * 1024;
118
119 inline bool isPointerAligned(void* p)
120 {
121     return !((intptr_t)(p) & (sizeof(char*) - 1));
122 }
123
124 inline 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  */
132 template<typename ToType, typename FromType>
133 inline 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
144 template<typename ToType, typename FromType>
145 inline 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'.
152 inline 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
159 // Macro that returns a compile time constant with the length of an array, but gives an error if passed a non-array.
160 template<typename T, size_t Size> char (&ArrayLengthHelperFunction(T (&)[Size]))[Size];
161 // GCC needs some help to deduce a 0 length array.
162 #if COMPILER(GCC)
163 template<typename T> char (&ArrayLengthHelperFunction(T (&)[0]))[0];
164 #endif
165 #define WTF_ARRAY_LENGTH(array) sizeof(::WTF::ArrayLengthHelperFunction(array))
166
167 // Efficient implementation that takes advantage of powers of two.
168 inline size_t roundUpToMultipleOf(size_t divisor, size_t x)
169 {
170     ASSERT(divisor && !(divisor & (divisor - 1)));
171     size_t remainderMask = divisor - 1;
172     return (x + remainderMask) & ~remainderMask;
173 }
174
175 template<size_t divisor> inline size_t roundUpToMultipleOf(size_t x)
176 {
177     static_assert(divisor && !(divisor & (divisor - 1)), "divisor must be a power of two!");
178     return roundUpToMultipleOf(divisor, x);
179 }
180
181 enum BinarySearchMode {
182     KeyMustBePresentInArray,
183     KeyMightNotBePresentInArray,
184     ReturnAdjacentElementIfKeyIsNotPresent
185 };
186
187 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey, BinarySearchMode mode>
188 inline ArrayElementType* binarySearchImpl(ArrayType& array, size_t size, KeyType key, const ExtractKey& extractKey = ExtractKey())
189 {
190     size_t offset = 0;
191     while (size > 1) {
192         size_t pos = (size - 1) >> 1;
193         KeyType val = extractKey(&array[offset + pos]);
194         
195         if (val == key)
196             return &array[offset + pos];
197         // The item we are looking for is smaller than the item being check; reduce the value of 'size',
198         // chopping off the right hand half of the array.
199         if (key < val)
200             size = pos;
201         // Discard all values in the left hand half of the array, up to and including the item at pos.
202         else {
203             size -= (pos + 1);
204             offset += (pos + 1);
205         }
206
207         ASSERT(mode != KeyMustBePresentInArray || size);
208     }
209     
210     if (mode == KeyMightNotBePresentInArray && !size)
211         return 0;
212     
213     ArrayElementType* result = &array[offset];
214
215     if (mode == KeyMightNotBePresentInArray && key != extractKey(result))
216         return 0;
217
218     if (mode == KeyMustBePresentInArray) {
219         ASSERT(size == 1);
220         ASSERT(key == extractKey(result));
221     }
222
223     return result;
224 }
225
226 // If the element is not found, crash if asserts are enabled, and behave like approximateBinarySearch in release builds.
227 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
228 inline ArrayElementType* binarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
229 {
230     return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMustBePresentInArray>(array, size, key, extractKey);
231 }
232
233 // Return zero if the element is not found.
234 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
235 inline ArrayElementType* tryBinarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
236 {
237     return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMightNotBePresentInArray>(array, size, key, extractKey);
238 }
239
240 // Return the element that is either to the left, or the right, of where the element would have been found.
241 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
242 inline ArrayElementType* approximateBinarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
243 {
244     return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, ReturnAdjacentElementIfKeyIsNotPresent>(array, size, key, extractKey);
245 }
246
247 // Variants of the above that use const.
248 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
249 inline ArrayElementType* binarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
250 {
251     return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMustBePresentInArray>(const_cast<ArrayType&>(array), size, key, extractKey);
252 }
253 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
254 inline ArrayElementType* tryBinarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
255 {
256     return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMightNotBePresentInArray>(const_cast<ArrayType&>(array), size, key, extractKey);
257 }
258 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
259 inline ArrayElementType* approximateBinarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
260 {
261     return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, ReturnAdjacentElementIfKeyIsNotPresent>(const_cast<ArrayType&>(array), size, key, extractKey);
262 }
263
264 template<typename VectorType, typename ElementType>
265 inline void insertIntoBoundedVector(VectorType& vector, size_t size, const ElementType& element, size_t index)
266 {
267     for (size_t i = size; i-- > index + 1;)
268         vector[i] = vector[i - 1];
269     vector[index] = element;
270 }
271
272 } // namespace WTF
273
274 #if OS(WINCE)
275 // Windows CE CRT has does not implement bsearch().
276 inline void* wtf_bsearch(const void* key, const void* base, size_t count, size_t size, int (*compare)(const void *, const void *))
277 {
278     const char* first = static_cast<const char*>(base);
279
280     while (count) {
281         size_t pos = (count - 1) >> 1;
282         const char* item = first + pos * size;
283         int compareResult = compare(item, key);
284         if (!compareResult)
285             return const_cast<char*>(item);
286         if (compareResult < 0) {
287             count -= (pos + 1);
288             first += (pos + 1) * size;
289         } else
290             count = pos;
291     }
292
293     return 0;
294 }
295
296 #define bsearch(key, base, count, size, compare) wtf_bsearch(key, base, count, size, compare)
297 #endif
298
299 // This version of placement new omits a 0 check.
300 enum NotNullTag { NotNull };
301 inline void* operator new(size_t, NotNullTag, void* location)
302 {
303     ASSERT(location);
304     return location;
305 }
306
307 using WTF::KB;
308 using WTF::MB;
309 using WTF::insertIntoBoundedVector;
310 using WTF::isPointerAligned;
311 using WTF::is8ByteAligned;
312 using WTF::binarySearch;
313 using WTF::tryBinarySearch;
314 using WTF::approximateBinarySearch;
315 using WTF::bitwise_cast;
316 using WTF::safeCast;
317
318 #endif // WTF_StdLibExtras_h