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