Source/WTF/wtf/StdLibExtras.h

   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/CheckedArithmetic.h>
  31
  32 // Use these to declare and define a static local variable (static T;) so that
  33 //  it is leaked so that its destructors are not called at exit. Using this
  34 //  macro also allows workarounds a compiler bug present in Apple's version of GCC 4.0.1.
  35 #ifndef DEFINE_STATIC_LOCAL
  36 #if COMPILER(GCC) && defined(__APPLE_CC__) && __GNUC__ == 4 && __GNUC_MINOR__ == 0 && __GNUC_PATCHLEVEL__ == 1
  37 #define DEFINE_STATIC_LOCAL(type, name, arguments) \
  38     static type* name##Ptr = new type arguments; \
  39     type& name = *name##Ptr
  40 #else
  41 #define DEFINE_STATIC_LOCAL(type, name, arguments) \
  42     static type& name = *new type arguments
  43 #endif
  44 #endif
  45
  46 // Use this macro to declare and define a debug-only global variable that may have a
  47 // non-trivial constructor and destructor. When building with clang, this will suppress
  48 // warnings about global constructors and exit-time destructors.
  49 #ifndef NDEBUG
  50 #if COMPILER(CLANG)
  51 #define DEFINE_DEBUG_ONLY_GLOBAL(type, name, arguments) \
  52     _Pragma("clang diagnostic push") \
  53     _Pragma("clang diagnostic ignored \"-Wglobal-constructors\"") \
  54     _Pragma("clang diagnostic ignored \"-Wexit-time-destructors\"") \
  55     static type name arguments; \
  56     _Pragma("clang diagnostic pop")
  57 #else
  58 #define DEFINE_DEBUG_ONLY_GLOBAL(type, name, arguments) \
  59     static type name arguments;
  60 #endif // COMPILER(CLANG)
  61 #else
  62 #define DEFINE_DEBUG_ONLY_GLOBAL(type, name, arguments)
  63 #endif // NDEBUG
  64
  65 // OBJECT_OFFSETOF: Like the C++ offsetof macro, but you can use it with classes.
  66 // The magic number 0x4000 is insignificant. We use it to avoid using NULL, since
  67 // NULL can cause compiler problems, especially in cases of multiple inheritance.
  68 #define OBJECT_OFFSETOF(class, field) (reinterpret_cast<ptrdiff_t>(&(reinterpret_cast<class*>(0x4000)->field)) - 0x4000)
  69
  70 // STRINGIZE: Can convert any value to quoted string, even expandable macros
  71 #define STRINGIZE(exp) #exp
  72 #define STRINGIZE_VALUE_OF(exp) STRINGIZE(exp)
  73
  74 /*
  75  * The reinterpret_cast<Type1*>([pointer to Type2]) expressions - where
  76  * sizeof(Type1) > sizeof(Type2) - cause the following warning on ARM with GCC:
  77  * increases required alignment of target type.
  78  *
  79  * An implicit or an extra static_cast<void*> bypasses the warning.
  80  * For more info see the following bugzilla entries:
  81  * - https://bugs.webkit.org/show_bug.cgi?id=38045
  82  * - http://gcc.gnu.org/bugzilla/show_bug.cgi?id=43976
  83  */
  84 #if (CPU(ARM) || CPU(MIPS)) && COMPILER(GCC)
  85 template<typename Type>
  86 bool isPointerTypeAlignmentOkay(Type* ptr)
  87 {
  88     return !(reinterpret_cast<intptr_t>(ptr) % __alignof__(Type));
  89 }
  90
  91 template<typename TypePtr>
  92 TypePtr reinterpret_cast_ptr(void* ptr)
  93 {
  94     ASSERT(isPointerTypeAlignmentOkay(reinterpret_cast<TypePtr>(ptr)));
  95     return reinterpret_cast<TypePtr>(ptr);
  96 }
  97
  98 template<typename TypePtr>
  99 TypePtr reinterpret_cast_ptr(const void* ptr)
 100 {
 101     ASSERT(isPointerTypeAlignmentOkay(reinterpret_cast<TypePtr>(ptr)));
 102     return reinterpret_cast<TypePtr>(ptr);
 103 }
 104 #else
 105 template<typename Type>
 106 bool isPointerTypeAlignmentOkay(Type*)
 107 {
 108     return true;
 109 }
 110 #define reinterpret_cast_ptr reinterpret_cast
 111 #endif
 112
 113 namespace WTF {
 114
 115 static const size_t KB = 1024;
 116 static const size_t MB = 1024 * 1024;
 117
 118 inline bool isPointerAligned(void* p)
 119 {
 120     return !((intptr_t)(p) & (sizeof(char*) - 1));
 121 }
 122
 123 inline bool is8ByteAligned(void* p)
 124 {
 125     return !((uintptr_t)(p) & (sizeof(double) - 1));
 126 }
 127
 128 /*
 129  * C++'s idea of a reinterpret_cast lacks sufficient cojones.
 130  */
 131 template<typename TO, typename FROM>
 132 inline TO bitwise_cast(FROM from)
 133 {
 134     COMPILE_ASSERT(sizeof(TO) == sizeof(FROM), WTF_bitwise_cast_sizeof_casted_types_is_equal);
 135     union {
 136         FROM from;
 137         TO to;
 138     } u;
 139     u.from = from;
 140     return u.to;
 141 }
 142
 143 template<typename To, typename From>
 144 inline To safeCast(From value)
 145 {
 146     ASSERT(isInBounds<To>(value));
 147     return static_cast<To>(value);
 148 }
 149
 150 // Returns a count of the number of bits set in 'bits'.
 151 inline size_t bitCount(unsigned bits)
 152 {
 153     bits = bits - ((bits >> 1) & 0x55555555);
 154     bits = (bits & 0x33333333) + ((bits >> 2) & 0x33333333);
 155     return (((bits + (bits >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24;
 156 }
 157
 158 // Macro that returns a compile time constant with the length of an array, but gives an error if passed a non-array.
 159 template<typename T, size_t Size> char (&ArrayLengthHelperFunction(T (&)[Size]))[Size];
 160 // GCC needs some help to deduce a 0 length array.
 161 #if COMPILER(GCC)
 162 template<typename T> char (&ArrayLengthHelperFunction(T (&)[0]))[0];
 163 #endif
 164 #define WTF_ARRAY_LENGTH(array) sizeof(::WTF::ArrayLengthHelperFunction(array))
 165
 166 // Efficient implementation that takes advantage of powers of two.
 167 inline size_t roundUpToMultipleOf(size_t divisor, size_t x)
 168 {
 169     ASSERT(divisor && !(divisor & (divisor - 1)));
 170     size_t remainderMask = divisor - 1;
 171     return (x + remainderMask) & ~remainderMask;
 172 }
 173 template<size_t divisor> inline size_t roundUpToMultipleOf(size_t x)
 174 {
 175     COMPILE_ASSERT(divisor && !(divisor & (divisor - 1)), divisor_is_a_power_of_two);
 176     return roundUpToMultipleOf(divisor, x);
 177 }
 178
 179 enum BinarySearchMode {
 180     KeyMustBePresentInArray,
 181     KeyMustNotBePresentInArray
 182 };
 183
 184 // Binary search algorithm, calls extractKey on pre-sorted elements in array,
 185 // compares result with key (KeyTypes should be comparable with '--', '<', '>').
 186 template<typename ArrayElementType, typename KeyType, KeyType(*extractKey)(ArrayElementType*)>
 187 inline ArrayElementType* binarySearch(ArrayElementType* array, size_t size, KeyType key, BinarySearchMode mode = KeyMustBePresentInArray)
 188 {
 189     // The array must contain at least one element (pre-condition, array does contain key).
 190     // If the array contains only one element, no need to do the comparison.
 191     while (size > 1) {
 192         // Pick an element to check, half way through the array, and read the value.
 193         int pos = (size - 1) >> 1;
 194         KeyType val = extractKey(&array[pos]);
 195
 196         // If the key matches, success!
 197         if (val == key)
 198             return &array[pos];
 199         // The item we are looking for is smaller than the item being check; reduce the value of 'size',
 200         // chopping off the right hand half of the array.
 201         else if (key < val)
 202             size = pos;
 203         // Discard all values in the left hand half of the array, up to and including the item at pos.
 204         else {
 205             size -= (pos + 1);
 206             array += (pos + 1);
 207         }
 208
 209         // In case of BinarySearchMode = KeyMustBePresentInArray 'size' should never reach zero.
 210         if (mode == KeyMustBePresentInArray)
 211             ASSERT(size);
 212     }
 213
 214     // In case of BinarySearchMode = KeyMustBePresentInArray if we reach this point
 215     // we've chopped down to one element, no need to check it matches
 216     if (mode == KeyMustBePresentInArray) {
 217         ASSERT(size == 1);
 218         ASSERT(key == extractKey(&array[0]));
 219     }
 220
 221     return &array[0];
 222 }
 223
 224 // Modified binary search algorithm that uses a functor. Note that this is strictly
 225 // more powerful than the above, but results in somewhat less template specialization.
 226 // Hence, depending on inlining heuristics, it might be slower.
 227 template<typename ArrayElementType, typename KeyType, typename ExtractKey>
 228 inline ArrayElementType* binarySearchWithFunctor(ArrayElementType* array, size_t size, KeyType key, BinarySearchMode mode = KeyMustBePresentInArray, const ExtractKey& extractKey = ExtractKey())
 229 {
 230     // The array must contain at least one element (pre-condition, array does contain key).
 231     // If the array contains only one element, no need to do the comparison.
 232     while (size > 1) {
 233         // Pick an element to check, half way through the array, and read the value.
 234         int pos = (size - 1) >> 1;
 235         KeyType val = extractKey(&array[pos]);
 236
 237         // If the key matches, success!
 238         if (val == key)
 239             return &array[pos];
 240         // The item we are looking for is smaller than the item being check; reduce the value of 'size',
 241         // chopping off the right hand half of the array.
 242         else if (key < val)
 243             size = pos;
 244         // Discard all values in the left hand half of the array, up to and including the item at pos.
 245         else {
 246             size -= (pos + 1);
 247             array += (pos + 1);
 248         }
 249
 250         // In case of BinarySearchMode = KeyMustBePresentInArray 'size' should never reach zero.
 251         if (mode == KeyMustBePresentInArray)
 252             ASSERT(size);
 253     }
 254
 255     // In case of BinarySearchMode = KeyMustBePresentInArray if we reach this point
 256     // we've chopped down to one element, no need to check it matches
 257     if (mode == KeyMustBePresentInArray) {
 258         ASSERT(size == 1);
 259         ASSERT(key == extractKey(&array[0]));
 260     }
 261
 262     return &array[0];
 263 }
 264
 265 // Modified binarySearch() algorithm designed for array-like classes that support
 266 // operator[] but not operator+=. One example of a class that qualifies is
 267 // SegmentedVector.
 268 template<typename ArrayElementType, typename KeyType, KeyType(*extractKey)(ArrayElementType*), typename ArrayType>
 269 inline ArrayElementType* genericBinarySearch(ArrayType& array, size_t size, KeyType key)
 270 {
 271     // The array must contain at least one element (pre-condition, array does conatin key).
 272     // If the array only contains one element, no need to do the comparison.
 273     size_t offset = 0;
 274     while (size > 1) {
 275         // Pick an element to check, half way through the array, and read the value.
 276         int pos = (size - 1) >> 1;
 277         KeyType val = extractKey(&array[offset + pos]);
 278
 279         // If the key matches, success!
 280         if (val == key)
 281             return &array[offset + pos];
 282         // The item we are looking for is smaller than the item being check; reduce the value of 'size',
 283         // chopping off the right hand half of the array.
 284         if (key < val)
 285             size = pos;
 286         // Discard all values in the left hand half of the array, up to and including the item at pos.
 287         else {
 288             size -= (pos + 1);
 289             offset += (pos + 1);
 290         }
 291
 292         // 'size' should never reach zero.
 293         ASSERT(size);
 294     }
 295
 296     // If we reach this point we've chopped down to one element, no need to check it matches
 297     ASSERT(size == 1);
 298     ASSERT(key == extractKey(&array[offset]));
 299     return &array[offset];
 300 }
 301
 302 } // namespace WTF
 303
 304 // This version of placement new omits a 0 check.
 305 enum NotNullTag { NotNull };
 306 inline void* operator new(size_t, NotNullTag, void* location)
 307 {
 308     ASSERT(location);
 309     return location;
 310 }
 311
 312 using WTF::KB;
 313 using WTF::MB;
 314 using WTF::isPointerAligned;
 315 using WTF::is8ByteAligned;
 316 using WTF::binarySearch;
 317 using WTF::bitwise_cast;
 318 using WTF::safeCast;
 319
 320 #endif // WTF_StdLibExtras_h