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)
90template<typename Type>
91bool isPointerTypeAlignmentOkay(Type* ptr)
92{
93 return !(reinterpret_cast<intptr_t>(ptr) % __alignof__(Type));
94}
95
96template<typename TypePtr>
97TypePtr reinterpret_cast_ptr(void* ptr)
98{
99 ASSERT(isPointerTypeAlignmentOkay(reinterpret_cast<TypePtr>(ptr)));
100 return reinterpret_cast<TypePtr>(ptr);
101}
102
103template<typename TypePtr>
104TypePtr reinterpret_cast_ptr(const void* ptr)
105{
106 ASSERT(isPointerTypeAlignmentOkay(reinterpret_cast<TypePtr>(ptr)));
107 return reinterpret_cast<TypePtr>(ptr);
108}
109#else
110template<typename Type>
111bool isPointerTypeAlignmentOkay(Type*)
112{
113 return true;
114}
115#define reinterpret_cast_ptr reinterpret_cast
116#endif
117
118namespace WTF {
119
120static const size_t KB = 1024;
121static const size_t MB = 1024 * 1024;
122
123inline bool isPointerAligned(void* p)
124{
125 return !((intptr_t)(p) & (sizeof(char*) - 1));
126}
127
128inline 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 */
136template<typename TO, typename FROM>
137inline 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
148template<typename To, typename From>
149inline 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'.
156inline 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.
164template<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)
167template<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.
172inline 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}
178template<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
184enum BinarySearchMode {
185 KeyMustBePresentInArray,
186 KeyMightNotBePresentInArray,
187 ReturnAdjacentElementIfKeyIsNotPresent
188};
189
190template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey, BinarySearchMode mode>
191inline 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.
230template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
231inline 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.
237template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
238inline 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.
244template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
245inline 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.
251template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
252inline 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}
256template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
257inline 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}
261template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
262inline 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.
270enum NotNullTag { NotNull };
271inline void* operator new(size_t, NotNullTag, void* location)
272{
273 ASSERT(location);
274 return location;
275}
276
277using WTF::KB;
278using WTF::MB;
279using WTF::isPointerAligned;
280using WTF::is8ByteAligned;
281using WTF::binarySearch;
282using WTF::tryBinarySearch;
283using WTF::approximateBinarySearch;
284using WTF::bitwise_cast;
285using WTF::safeCast;
286
287#endif // WTF_StdLibExtras_h
288

source code of qtdeclarative/src/3rdparty/masm/wtf/StdLibExtras.h