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) 88template<typename Type> 89bool isPointerTypeAlignmentOkay(Type* ptr) 90{ 91 return !(reinterpret_cast<intptr_t>(ptr) % __alignof__(Type)); 92} 93 94template<typename TypePtr> 95TypePtr reinterpret_cast_ptr(void* ptr) 96{ 97 ASSERT(isPointerTypeAlignmentOkay(reinterpret_cast<TypePtr>(ptr))); 98 return reinterpret_cast<TypePtr>(ptr); 99} 100 101template<typename TypePtr> 102TypePtr reinterpret_cast_ptr(const void* ptr) 103{ 104 ASSERT(isPointerTypeAlignmentOkay(reinterpret_cast<TypePtr>(ptr))); 105 return reinterpret_cast<TypePtr>(ptr); 106} 107#else 108template<typename Type> 109bool isPointerTypeAlignmentOkay(Type*) 110{ 111 return true; 112} 113#define reinterpret_cast_ptr reinterpret_cast 114#endif 115 116namespace WTF { 117 118static const size_t KB = 1024; 119static const size_t MB = 1024 * 1024; 120 121inline bool isPointerAligned(void* p) 122{ 123 return !((intptr_t)(p) & (sizeof(char*) - 1)); 124} 125 126inline 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 */ 134template<typename TO, typename FROM> 135inline 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 146template<typename To, typename From> 147inline 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'. 154inline 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. 162template<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) 165template<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. 170inline 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} 176template<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 182enum BinarySearchMode { 183 KeyMustBePresentInArray, 184 KeyMightNotBePresentInArray, 185 ReturnAdjacentElementIfKeyIsNotPresent 186}; 187 188template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey, BinarySearchMode mode> 189inline 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. 228template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey> 229inline 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. 235template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey> 236inline 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. 242template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey> 243inline 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. 249template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey> 250inline 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} 254template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey> 255inline 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} 259template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey> 260inline 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. 268enum NotNullTag { NotNull }; 269inline void* operator new(size_t, NotNullTag, void* location) 270{ 271 ASSERT(location); 272 return location; 273} 274 275using WTF::KB; 276using WTF::MB; 277using WTF::isPointerAligned; 278using WTF::is8ByteAligned; 279using WTF::binarySearch; 280using WTF::tryBinarySearch; 281using WTF::approximateBinarySearch; 282using WTF::bitwise_cast; 283using WTF::safeCast; 284 285#endif // WTF_StdLibExtras_h 286