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 31 // Use these to declare and define a static local variable (static T;) so that 32 // it is leaked so that its destructors are not called at exit. Using this 33 // macro also allows workarounds a compiler bug present in Apple's version of GCC 4.0.1. 34 #ifndef DEFINE_STATIC_LOCAL 35 #if COMPILER(GCC) && defined(__APPLE_CC__) && __GNUC__ == 4 && __GNUC_MINOR__ == 0 && __GNUC_PATCHLEVEL__ == 1 36 #define DEFINE_STATIC_LOCAL(type, name, arguments) \ 37 static type* name##Ptr = new type arguments; \ 38 type& name = *name##Ptr 39 #else 40 #define DEFINE_STATIC_LOCAL(type, name, arguments) \ 41 static type& name = *new type arguments 42 #endif 43 #endif 44 45 // OBJECT_OFFSETOF: Like the C++ offsetof macro, but you can use it with classes. 46 // The magic number 0x4000 is insignificant. We use it to avoid using NULL, since 47 // NULL can cause compiler problems, especially in cases of multiple inheritance. 48 #define OBJECT_OFFSETOF(class, field) (reinterpret_cast<ptrdiff_t>(&(reinterpret_cast<class*>(0x4000)->field)) - 0x4000) 49 50 // STRINGIZE: Can convert any value to quoted string, even expandable macros 51 #define STRINGIZE(exp) #exp 52 #define STRINGIZE_VALUE_OF(exp) STRINGIZE(exp) 53 54 /* 55 * The reinterpret_cast<Type1*>([pointer to Type2]) expressions - where 56 * sizeof(Type1) > sizeof(Type2) - cause the following warning on ARM with GCC: 57 * increases required alignment of target type. 58 * 59 * An implicit or an extra static_cast<void*> bypasses the warning. 60 * For more info see the following bugzilla entries: 61 * - https://bugs.webkit.org/show_bug.cgi?id=38045 62 * - http://gcc.gnu.org/bugzilla/show_bug.cgi?id=43976 63 */ 64 #if (CPU(ARM) || CPU(MIPS)) && COMPILER(GCC) 65 template<typename Type> 66 bool isPointerTypeAlignmentOkay(Type* ptr) 67 { 68 return !(reinterpret_cast<intptr_t>(ptr) % __alignof__(Type)); 69 } 70 71 template<typename TypePtr> 72 TypePtr reinterpret_cast_ptr(void* ptr) 73 { 74 ASSERT(isPointerTypeAlignmentOkay(reinterpret_cast<TypePtr>(ptr))); 75 return reinterpret_cast<TypePtr>(ptr); 76 } 77 78 template<typename TypePtr> 79 TypePtr reinterpret_cast_ptr(const void* ptr) 80 { 81 ASSERT(isPointerTypeAlignmentOkay(reinterpret_cast<TypePtr>(ptr))); 82 return reinterpret_cast<TypePtr>(ptr); 83 } 84 #else 85 #define reinterpret_cast_ptr reinterpret_cast 86 #endif 87 88 namespace WTF { 89 90 /* 91 * C++'s idea of a reinterpret_cast lacks sufficient cojones. 92 */ 93 template<typename TO, typename FROM> 94 inline TO bitwise_cast(FROM from) 95 { 96 COMPILE_ASSERT(sizeof(TO) == sizeof(FROM), WTF_bitwise_cast_sizeof_casted_types_is_equal); 97 union { 98 FROM from; 99 TO to; 100 } u; 101 u.from = from; 102 return u.to; 103 } 104 105 // Returns a count of the number of bits set in 'bits'. 106 inline size_t bitCount(unsigned bits) 107 { 108 bits = bits - ((bits >> 1) & 0x55555555); 109 bits = (bits & 0x33333333) + ((bits >> 2) & 0x33333333); 110 return (((bits + (bits >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24; 111 } 112 113 // Macro that returns a compile time constant with the length of an array, but gives an error if passed a non-array. 114 template<typename T, size_t Size> char (&ArrayLengthHelperFunction(T (&)[Size]))[Size]; 115 #define WTF_ARRAY_LENGTH(array) sizeof(::WTF::ArrayLengthHelperFunction(array)) 116 117 // Efficient implementation that takes advantage of powers of two. 118 template<size_t divisor> inline size_t roundUpToMultipleOf(size_t x) 119 { 120 COMPILE_ASSERT(divisor && !(divisor & (divisor - 1)), divisor_is_a_power_of_two); 121 122 size_t remainderMask = divisor - 1; 123 return (x + remainderMask) & ~remainderMask; 124 } 125 126 // Binary search algorithm, calls extractKey on pre-sorted elements in array, 127 // compares result with key (KeyTypes should be comparable with '--', '<', '>'). 128 // Optimized for cases where the array contains the key, checked by assertions. 129 template<typename ArrayType, typename KeyType, KeyType(*extractKey)(ArrayType*)> 130 inline ArrayType* binarySearch(ArrayType* array, size_t size, KeyType key) 131 { 132 // The array must contain at least one element (pre-condition, array does conatin key). 133 // If the array only contains one element, no need to do the comparison. 134 while (size > 1) { 135 // Pick an element to check, half way through the array, and read the value. 136 int pos = (size - 1) >> 1; 137 KeyType val = extractKey(&array[pos]); 138 139 // If the key matches, success! 140 if (val == key) 141 return &array[pos]; 142 // The item we are looking for is smaller than the item being check; reduce the value of 'size', 143 // chopping off the right hand half of the array. 144 else if (key < val) 145 size = pos; 146 // Discard all values in the left hand half of the array, up to and including the item at pos. 147 else { 148 size -= (pos + 1); 149 array += (pos + 1); 150 } 151 152 // 'size' should never reach zero. 153 ASSERT(size); 154 } 155 156 // If we reach this point we've chopped down to one element, no need to check it matches 157 ASSERT(size == 1); 158 ASSERT(key == extractKey(&array[0])); 159 return &array[0]; 160 } 161 162 } // namespace WTF 163 164 using WTF::binarySearch; 165 using WTF::bitwise_cast; 166 167 #endif // WTF_StdLibExtras_h 168