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 macro to declare and define a debug-only global variable that may have a 41 // non-trivial constructor and destructor. When building with clang, this will suppress 42 // warnings about global constructors and exit-time destructors. 43 #ifndef NDEBUG 44 #if COMPILER(CLANG) 45 #define DEFINE_DEBUG_ONLY_GLOBAL(type, name, arguments) \ 46 _Pragma("clang diagnostic push") \ 47 _Pragma("clang diagnostic ignored \"-Wglobal-constructors\"") \ 48 _Pragma("clang diagnostic ignored \"-Wexit-time-destructors\"") \ 49 static type name arguments; \ 50 _Pragma("clang diagnostic pop") 51 #else 52 #define DEFINE_DEBUG_ONLY_GLOBAL(type, name, arguments) \ 53 static type name arguments; 54 #endif // COMPILER(CLANG) 55 #else 56 #define DEFINE_DEBUG_ONLY_GLOBAL(type, name, arguments) 57 #endif // NDEBUG 58 59 // OBJECT_OFFSETOF: Like the C++ offsetof macro, but you can use it with classes. 60 // The magic number 0x4000 is insignificant. We use it to avoid using NULL, since 61 // NULL can cause compiler problems, especially in cases of multiple inheritance. 62 #define OBJECT_OFFSETOF(class, field) (reinterpret_cast<ptrdiff_t>(&(reinterpret_cast<class*>(0x4000)->field)) - 0x4000) 63 64 // STRINGIZE: Can convert any value to quoted string, even expandable macros 65 #define STRINGIZE(exp) #exp 66 #define STRINGIZE_VALUE_OF(exp) STRINGIZE(exp) 67 68 /* 69 * The reinterpret_cast<Type1*>([pointer to Type2]) expressions - where 70 * sizeof(Type1) > sizeof(Type2) - cause the following warning on ARM with GCC: 71 * increases required alignment of target type. 72 * 73 * An implicit or an extra static_cast<void*> bypasses the warning. 74 * For more info see the following bugzilla entries: 75 * - https://bugs.webkit.org/show_bug.cgi?id=38045 76 * - http://gcc.gnu.org/bugzilla/show_bug.cgi?id=43976 77 */ 78 #if (CPU(ARM) || CPU(MIPS)) && COMPILER(GCC) 79 template<typename Type> 80 bool isPointerTypeAlignmentOkay(Type* ptr) 81 { 82 return !(reinterpret_cast<intptr_t>(ptr) % __alignof__(Type)); 83 } 84 85 template<typename TypePtr> 86 TypePtr reinterpret_cast_ptr(void* ptr) 87 { 88 ASSERT(isPointerTypeAlignmentOkay(reinterpret_cast<TypePtr>(ptr))); 89 return reinterpret_cast<TypePtr>(ptr); 90 } 91 92 template<typename TypePtr> 93 TypePtr reinterpret_cast_ptr(const void* ptr) 94 { 95 ASSERT(isPointerTypeAlignmentOkay(reinterpret_cast<TypePtr>(ptr))); 96 return reinterpret_cast<TypePtr>(ptr); 97 } 98 #else 99 template<typename Type> 100 bool isPointerTypeAlignmentOkay(Type*) 101 { 102 return true; 103 } 104 #define reinterpret_cast_ptr reinterpret_cast 105 #endif 106 107 namespace WTF { 108 109 static const size_t KB = 1024; 110 static const size_t MB = 1024 * 1024; 111 112 inline bool isPointerAligned(void* p) 113 { 114 return !((intptr_t)(p) & (sizeof(char*) - 1)); 115 } 116 117 inline bool is8ByteAligned(void* p) 118 { 119 return !((uintptr_t)(p) & (sizeof(double) - 1)); 120 } 121 122 /* 123 * C++'s idea of a reinterpret_cast lacks sufficient cojones. 124 */ 125 template<typename TO, typename FROM> 126 inline TO bitwise_cast(FROM from) 127 { 128 COMPILE_ASSERT(sizeof(TO) == sizeof(FROM), WTF_bitwise_cast_sizeof_casted_types_is_equal); 129 union { 130 FROM from; 131 TO to; 132 } u; 133 u.from = from; 134 return u.to; 135 } 136 137 template<typename To, typename From> 138 inline To safeCast(From value) 139 { 140 ASSERT(isInBounds<To>(value)); 141 return static_cast<To>(value); 142 } 143 144 // Returns a count of the number of bits set in 'bits'. 145 inline size_t bitCount(unsigned bits) 146 { 147 bits = bits - ((bits >> 1) & 0x55555555); 148 bits = (bits & 0x33333333) + ((bits >> 2) & 0x33333333); 149 return (((bits + (bits >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24; 150 } 151 152 // Macro that returns a compile time constant with the length of an array, but gives an error if passed a non-array. 153 template<typename T, size_t Size> char (&ArrayLengthHelperFunction(T (&)[Size]))[Size]; 154 // GCC needs some help to deduce a 0 length array. 155 #if COMPILER(GCC) 156 template<typename T> char (&ArrayLengthHelperFunction(T (&)[0]))[0]; 157 #endif 158 #define WTF_ARRAY_LENGTH(array) sizeof(::WTF::ArrayLengthHelperFunction(array)) 159 160 // Efficient implementation that takes advantage of powers of two. 161 inline size_t roundUpToMultipleOf(size_t divisor, size_t x) 162 { 163 ASSERT(divisor && !(divisor & (divisor - 1))); 164 size_t remainderMask = divisor - 1; 165 return (x + remainderMask) & ~remainderMask; 166 } 167 template<size_t divisor> inline size_t roundUpToMultipleOf(size_t x) 168 { 169 COMPILE_ASSERT(divisor && !(divisor & (divisor - 1)), divisor_is_a_power_of_two); 170 return roundUpToMultipleOf(divisor, x); 171 } 172 173 enum BinarySearchMode { 174 KeyMustBePresentInArray, 175 KeyMightNotBePresentInArray, 176 ReturnAdjacentElementIfKeyIsNotPresent 177 }; 178 179 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey, BinarySearchMode mode> 180 inline ArrayElementType* binarySearchImpl(ArrayType& array, size_t size, KeyType key, const ExtractKey& extractKey = ExtractKey()) 181 { 182 size_t offset = 0; 183 while (size > 1) { 184 size_t pos = (size - 1) >> 1; 185 KeyType val = extractKey(&array[offset + pos]); 186 187 if (val == key) 188 return &array[offset + pos]; 189 // The item we are looking for is smaller than the item being check; reduce the value of 'size', 190 // chopping off the right hand half of the array. 191 if (key < val) 192 size = pos; 193 // Discard all values in the left hand half of the array, up to and including the item at pos. 194 else { 195 size -= (pos + 1); 196 offset += (pos + 1); 197 } 198 199 ASSERT(mode != KeyMustBePresentInArray || size); 200 } 201 202 if (mode == KeyMightNotBePresentInArray && !size) 203 return 0; 204 205 ArrayElementType* result = &array[offset]; 206 207 if (mode == KeyMightNotBePresentInArray && key != extractKey(result)) 208 return 0; 209 210 if (mode == KeyMustBePresentInArray) { 211 ASSERT(size == 1); 212 ASSERT(key == extractKey(result)); 213 } 214 215 return result; 216 } 217 218 // If the element is not found, crash if asserts are enabled, and behave like approximateBinarySearch in release builds. 219 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey> 220 inline ArrayElementType* binarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey()) 221 { 222 return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMustBePresentInArray>(array, size, key, extractKey); 223 } 224 225 // Return zero if the element is not found. 226 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey> 227 inline ArrayElementType* tryBinarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey()) 228 { 229 return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMightNotBePresentInArray>(array, size, key, extractKey); 230 } 231 232 // Return the element that is either to the left, or the right, of where the element would have been found. 233 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey> 234 inline ArrayElementType* approximateBinarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey()) 235 { 236 return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, ReturnAdjacentElementIfKeyIsNotPresent>(array, size, key, extractKey); 237 } 238 239 // Variants of the above that use const. 240 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey> 241 inline ArrayElementType* binarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey()) 242 { 243 return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMustBePresentInArray>(const_cast<ArrayType&>(array), size, key, extractKey); 244 } 245 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey> 246 inline ArrayElementType* tryBinarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey()) 247 { 248 return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMightNotBePresentInArray>(const_cast<ArrayType&>(array), size, key, extractKey); 249 } 250 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey> 251 inline ArrayElementType* approximateBinarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey()) 252 { 253 return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, ReturnAdjacentElementIfKeyIsNotPresent>(const_cast<ArrayType&>(array), size, key, extractKey); 254 } 255 256 } // namespace WTF 257 258 // This version of placement new omits a 0 check. 259 enum NotNullTag { NotNull }; 260 inline void* operator new(size_t, NotNullTag, void* location) 261 { 262 ASSERT(location); 263 return location; 264 } 265 266 using WTF::KB; 267 using WTF::MB; 268 using WTF::isPointerAligned; 269 using WTF::is8ByteAligned; 270 using WTF::binarySearch; 271 using WTF::tryBinarySearch; 272 using WTF::approximateBinarySearch; 273 using WTF::bitwise_cast; 274 using WTF::safeCast; 275 276 #endif // WTF_StdLibExtras_h 277
