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