Home | History | Annotate | Download | only in wtf 
      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