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>
isPointerTypeAlignmentOkay(Type * ptr)66 bool isPointerTypeAlignmentOkay(Type* ptr)
67 {
68 return !(reinterpret_cast<intptr_t>(ptr) % __alignof__(Type));
69 }
70
71 template<typename TypePtr>
reinterpret_cast_ptr(void * ptr)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>
reinterpret_cast_ptr(const void * ptr)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>
bitwise_cast(FROM 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'.
bitCount(unsigned 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.
roundUpToMultipleOf(size_t x)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*)>
binarySearch(ArrayType * array,size_t size,KeyType key)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