code.vuplus.com Git - vuplus_webkit/blob - Source/JavaScriptCore/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
  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 enum BinarySearchMode {
 127     KeyMustBePresentInArray,
 128     KeyMustNotBePresentInArray
 129 };
 130
 131 // Binary search algorithm, calls extractKey on pre-sorted elements in array,
 132 // compares result with key (KeyTypes should be comparable with '--', '<', '>').
 133 template<typename ArrayElementType, typename KeyType, KeyType(*extractKey)(ArrayElementType*)>
 134 inline ArrayElementType* binarySearch(ArrayElementType* array, size_t size, KeyType key, BinarySearchMode mode = KeyMustBePresentInArray)
 135 {
 136     // The array must contain at least one element (pre-condition, array does contain key).
 137     // If the array contains only one element, no need to do the comparison.
 138     while (size > 1) {
 139         // Pick an element to check, half way through the array, and read the value.
 140         int pos = (size - 1) >> 1;
 141         KeyType val = extractKey(&array[pos]);
 142
 143         // If the key matches, success!
 144         if (val == key)
 145             return &array[pos];
 146         // The item we are looking for is smaller than the item being check; reduce the value of 'size',
 147         // chopping off the right hand half of the array.
 148         else if (key < val)
 149             size = pos;
 150         // Discard all values in the left hand half of the array, up to and including the item at pos.
 151         else {
 152             size -= (pos + 1);
 153             array += (pos + 1);
 154         }
 155
 156         // In case of BinarySearchMode = KeyMustBePresentInArray 'size' should never reach zero.
 157         if (mode == KeyMustBePresentInArray)
 158             ASSERT(size);
 159     }
 160
 161     // In case of BinarySearchMode = KeyMustBePresentInArray if we reach this point
 162     // we've chopped down to one element, no need to check it matches
 163     if (mode == KeyMustBePresentInArray) {
 164         ASSERT(size == 1);
 165         ASSERT(key == extractKey(&array[0]));
 166     }
 167
 168     return &array[0];
 169 }
 170
 171 // Modified binarySearch() algorithm designed for array-like classes that support
 172 // operator[] but not operator+=. One example of a class that qualifies is
 173 // SegmentedVector.
 174 template<typename ArrayElementType, typename KeyType, KeyType(*extractKey)(ArrayElementType*), typename ArrayType>
 175 inline ArrayElementType* genericBinarySearch(ArrayType& array, size_t size, KeyType key)
 176 {
 177     // The array must contain at least one element (pre-condition, array does conatin key).
 178     // If the array only contains one element, no need to do the comparison.
 179     size_t offset = 0;
 180     while (size > 1) {
 181         // Pick an element to check, half way through the array, and read the value.
 182         int pos = (size - 1) >> 1;
 183         KeyType val = extractKey(&array[offset + pos]);
 184
 185         // If the key matches, success!
 186         if (val == key)
 187             return &array[offset + pos];
 188         // The item we are looking for is smaller than the item being check; reduce the value of 'size',
 189         // chopping off the right hand half of the array.
 190         if (key < val)
 191             size = pos;
 192         // Discard all values in the left hand half of the array, up to and including the item at pos.
 193         else {
 194             size -= (pos + 1);
 195             offset += (pos + 1);
 196         }
 197
 198         // 'size' should never reach zero.
 199         ASSERT(size);
 200     }
 201
 202     // If we reach this point we've chopped down to one element, no need to check it matches
 203     ASSERT(size == 1);
 204     ASSERT(key == extractKey(&array[offset]));
 205     return &array[offset];
 206 }
 207
 208 } // namespace WTF
 209
 210 using WTF::binarySearch;
 211 using WTF::bitwise_cast;
 212
 213 #endif // WTF_StdLibExtras_h