Change LayoutTests' f*-j* files to use pre and post js files in LayoutTests/resources.
[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 TO, typename FROM>
133 inline TO bitwise_cast(FROM from)
134 {
135     COMPILE_ASSERT(sizeof(TO) == sizeof(FROM), WTF_bitwise_cast_sizeof_casted_types_is_equal);
136     union {
137         FROM from;
138         TO to;
139     } u;
140     u.from = from;
141     return u.to;
142 }
143
144 template<typename To, typename From>
145 inline To safeCast(From value)
146 {
147     ASSERT(isInBounds<To>(value));
148     return static_cast<To>(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 template<size_t divisor> inline size_t roundUpToMultipleOf(size_t x)
175 {
176     COMPILE_ASSERT(divisor && !(divisor & (divisor - 1)), divisor_is_a_power_of_two);
177     return roundUpToMultipleOf(divisor, x);
178 }
179
180 enum BinarySearchMode {
181     KeyMustBePresentInArray,
182     KeyMightNotBePresentInArray,
183     ReturnAdjacentElementIfKeyIsNotPresent
184 };
185
186 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey, BinarySearchMode mode>
187 inline ArrayElementType* binarySearchImpl(ArrayType& array, size_t size, KeyType key, const ExtractKey& extractKey = ExtractKey())
188 {
189     size_t offset = 0;
190     while (size > 1) {
191         size_t pos = (size - 1) >> 1;
192         KeyType val = extractKey(&array[offset + pos]);
193         
194         if (val == key)
195             return &array[offset + pos];
196         // The item we are looking for is smaller than the item being check; reduce the value of 'size',
197         // chopping off the right hand half of the array.
198         if (key < val)
199             size = pos;
200         // Discard all values in the left hand half of the array, up to and including the item at pos.
201         else {
202             size -= (pos + 1);
203             offset += (pos + 1);
204         }
205
206         ASSERT(mode != KeyMustBePresentInArray || size);
207     }
208     
209     if (mode == KeyMightNotBePresentInArray && !size)
210         return 0;
211     
212     ArrayElementType* result = &array[offset];
213
214     if (mode == KeyMightNotBePresentInArray && key != extractKey(result))
215         return 0;
216
217     if (mode == KeyMustBePresentInArray) {
218         ASSERT(size == 1);
219         ASSERT(key == extractKey(result));
220     }
221
222     return result;
223 }
224
225 // If the element is not found, crash if asserts are enabled, and behave like approximateBinarySearch in release builds.
226 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
227 inline ArrayElementType* binarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
228 {
229     return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMustBePresentInArray>(array, size, key, extractKey);
230 }
231
232 // Return zero if the element is not found.
233 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
234 inline ArrayElementType* tryBinarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
235 {
236     return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMightNotBePresentInArray>(array, size, key, extractKey);
237 }
238
239 // Return the element that is either to the left, or the right, of where the element would have been found.
240 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
241 inline ArrayElementType* approximateBinarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
242 {
243     return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, ReturnAdjacentElementIfKeyIsNotPresent>(array, size, key, extractKey);
244 }
245
246 // Variants of the above that use const.
247 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
248 inline ArrayElementType* binarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
249 {
250     return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMustBePresentInArray>(const_cast<ArrayType&>(array), size, key, extractKey);
251 }
252 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
253 inline ArrayElementType* tryBinarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
254 {
255     return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMightNotBePresentInArray>(const_cast<ArrayType&>(array), size, key, extractKey);
256 }
257 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
258 inline ArrayElementType* approximateBinarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
259 {
260     return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, ReturnAdjacentElementIfKeyIsNotPresent>(const_cast<ArrayType&>(array), size, key, extractKey);
261 }
262
263 template<typename VectorType, typename ElementType>
264 inline void insertIntoBoundedVector(VectorType& vector, size_t size, const ElementType& element, size_t index)
265 {
266     for (unsigned i = size; i-- > index + 1;)
267         vector[i] = vector[i - 1];
268     vector[index] = element;
269 }
270
271 } // namespace WTF
272
273 #if OS(WINCE)
274 // Windows CE CRT has does not implement bsearch().
275 inline void* wtf_bsearch(const void* key, const void* base, size_t count, size_t size, int (*compare)(const void *, const void *))
276 {
277     const char* first = static_cast<const char*>(base);
278
279     while (count) {
280         size_t pos = (count - 1) >> 1;
281         const char* item = first + pos * size;
282         int compareResult = compare(item, key);
283         if (!compareResult)
284             return const_cast<char*>(item);
285         if (compareResult < 0) {
286             count -= (pos + 1);
287             first += (pos + 1) * size;
288         } else
289             count = pos;
290     }
291
292     return 0;
293 }
294
295 #define bsearch(key, base, count, size, compare) wtf_bsearch(key, base, count, size, compare)
296 #endif
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::MB;
308 using WTF::insertIntoBoundedVector;
309 using WTF::isPointerAligned;
310 using WTF::is8ByteAligned;
311 using WTF::binarySearch;
312 using WTF::tryBinarySearch;
313 using WTF::approximateBinarySearch;
314 using WTF::bitwise_cast;
315 using WTF::safeCast;
316
317 #endif // WTF_StdLibExtras_h