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 |
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> |
91 | bool isPointerTypeAlignmentOkay(Type* ptr) |
92 | { |
93 | return !(reinterpret_cast<intptr_t>(ptr) % __alignof__(Type)); |
94 | } |
95 | |
96 | template<typename TypePtr> |
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> |
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> |
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 | |
123 | inline bool isPointerAligned(void* p) |
124 | { |
125 | return !((intptr_t)(p) & (sizeof(char*) - 1)); |
126 | } |
127 | |
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> |
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> |
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'. |
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. |
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 | } |
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()) |
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()) |
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()) |
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()) |
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()) |
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()) |
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()) |
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 }; |
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 | |