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