Source/WTF/wtf/StdLibExtras.h

   1 /*
   2  * Copyright (C) 2008 Apple Inc. All Rights Reserved.
   3  * Copyright (C) 2013 Patrick Gansterer <paroga@paroga.com>
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  *
  14  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
  15  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
  18  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  19  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  20  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  21  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
  22  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  23  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  24  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  25  */
  26
  27 #ifndef WTF_StdLibExtras_h
  28 #define WTF_StdLibExtras_h
  29
  30 #include <chrono>
  31 #include <memory>
  32 #include <wtf/Assertions.h>
  33 #include <wtf/CheckedArithmetic.h>
  34
  35 // This was used to declare and define a static local variable (static T;) so that
  36 //  it was leaked so that its destructors were not called at exit. Using this
  37 //  macro also allowed to workaround a compiler bug present in Apple's version of GCC 4.0.1.
  38 //
  39 // Newly written code should use static NeverDestroyed<T> instead.
  40 #ifndef DEPRECATED_DEFINE_STATIC_LOCAL
  41 #if COMPILER(GCC) && defined(__APPLE_CC__) && __GNUC__ == 4 && __GNUC_MINOR__ == 0 && __GNUC_PATCHLEVEL__ == 1
  42 #define DEPRECATED_DEFINE_STATIC_LOCAL(type, name, arguments) \
  43     static type* name##Ptr = new type arguments; \
  44     type& name = *name##Ptr
  45 #else
  46 #define DEPRECATED_DEFINE_STATIC_LOCAL(type, name, arguments) \
  47     static type& name = *new type arguments
  48 #endif
  49 #endif
  50
  51 // Use this macro to declare and define a debug-only global variable that may have a
  52 // non-trivial constructor and destructor. When building with clang, this will suppress
  53 // warnings about global constructors and exit-time destructors.
  54 #define DEFINE_GLOBAL_FOR_LOGGING(type, name, arguments) \
  55     _Pragma("clang diagnostic push") \
  56     _Pragma("clang diagnostic ignored \"-Wglobal-constructors\"") \
  57     _Pragma("clang diagnostic ignored \"-Wexit-time-destructors\"") \
  58     static type name arguments; \
  59     _Pragma("clang diagnostic pop")
  60
  61 #ifndef NDEBUG
  62 #if COMPILER(CLANG)
  63 #define DEFINE_DEBUG_ONLY_GLOBAL(type, name, arguments) DEFINE_GLOBAL_FOR_LOGGING(type, name, arguments)
  64 #else
  65 #define DEFINE_DEBUG_ONLY_GLOBAL(type, name, arguments) \
  66     static type name arguments;
  67 #endif // COMPILER(CLANG)
  68 #else
  69 #define DEFINE_DEBUG_ONLY_GLOBAL(type, name, arguments)
  70 #endif // NDEBUG
  71
  72 // OBJECT_OFFSETOF: Like the C++ offsetof macro, but you can use it with classes.
  73 // The magic number 0x4000 is insignificant. We use it to avoid using NULL, since
  74 // NULL can cause compiler problems, especially in cases of multiple inheritance.
  75 #define OBJECT_OFFSETOF(class, field) (reinterpret_cast<ptrdiff_t>(&(reinterpret_cast<class*>(0x4000)->field)) - 0x4000)
  76
  77 // STRINGIZE: Can convert any value to quoted string, even expandable macros
  78 #define STRINGIZE(exp) #exp
  79 #define STRINGIZE_VALUE_OF(exp) STRINGIZE(exp)
  80
  81 /*
  82  * The reinterpret_cast<Type1*>([pointer to Type2]) expressions - where
  83  * sizeof(Type1) > sizeof(Type2) - cause the following warning on ARM with GCC:
  84  * increases required alignment of target type.
  85  *
  86  * An implicit or an extra static_cast<void*> bypasses the warning.
  87  * For more info see the following bugzilla entries:
  88  * - https://bugs.webkit.org/show_bug.cgi?id=38045
  89  * - http://gcc.gnu.org/bugzilla/show_bug.cgi?id=43976
  90  */
  91 #if (CPU(ARM) || CPU(MIPS)) && COMPILER(GCC)
  92 template<typename Type>
  93 inline bool isPointerTypeAlignmentOkay(Type* ptr)
  94 {
  95     return !(reinterpret_cast<intptr_t>(ptr) % __alignof__(Type));
  96 }
  97
  98 template<typename TypePtr>
  99 inline TypePtr reinterpret_cast_ptr(void* ptr)
 100 {
 101     ASSERT(isPointerTypeAlignmentOkay(reinterpret_cast<TypePtr>(ptr)));
 102     return reinterpret_cast<TypePtr>(ptr);
 103 }
 104
 105 template<typename TypePtr>
 106 inline TypePtr reinterpret_cast_ptr(const void* ptr)
 107 {
 108     ASSERT(isPointerTypeAlignmentOkay(reinterpret_cast<TypePtr>(ptr)));
 109     return reinterpret_cast<TypePtr>(ptr);
 110 }
 111 #else
 112 template<typename Type>
 113 inline bool isPointerTypeAlignmentOkay(Type*)
 114 {
 115     return true;
 116 }
 117 #define reinterpret_cast_ptr reinterpret_cast
 118 #endif
 119
 120 namespace WTF {
 121
 122 template<typename T>
 123 ALWAYS_INLINE typename std::remove_reference<T>::type&& move(T&& value)
 124 {
 125     static_assert(std::is_lvalue_reference<T>::value, "T is not an lvalue reference; move() is unnecessary.");
 126
 127     using NonRefQualifiedType = typename std::remove_reference<T>::type;
 128     static_assert(!std::is_const<NonRefQualifiedType>::value, "T is const qualified.");
 129     return std::move(value);
 130 }
 131
 132 static const size_t KB = 1024;
 133 static const size_t MB = 1024 * 1024;
 134
 135 inline bool isPointerAligned(void* p)
 136 {
 137     return !((intptr_t)(p) & (sizeof(char*) - 1));
 138 }
 139
 140 inline bool is8ByteAligned(void* p)
 141 {
 142     return !((uintptr_t)(p) & (sizeof(double) - 1));
 143 }
 144
 145 /*
 146  * C++'s idea of a reinterpret_cast lacks sufficient cojones.
 147  */
 148 template<typename ToType, typename FromType>
 149 inline ToType bitwise_cast(FromType from)
 150 {
 151     static_assert(sizeof(FromType) == sizeof(ToType), "bitwise_cast size of FromType and ToType must be equal!");
 152     union {
 153         FromType from;
 154         ToType to;
 155     } u;
 156     u.from = from;
 157     return u.to;
 158 }
 159
 160 template<typename ToType, typename FromType>
 161 inline ToType safeCast(FromType value)
 162 {
 163     ASSERT(isInBounds<ToType>(value));
 164     return static_cast<ToType>(value);
 165 }
 166
 167 // Returns a count of the number of bits set in 'bits'.
 168 inline size_t bitCount(unsigned bits)
 169 {
 170     bits = bits - ((bits >> 1) & 0x55555555);
 171     bits = (bits & 0x33333333) + ((bits >> 2) & 0x33333333);
 172     return (((bits + (bits >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24;
 173 }
 174
 175 inline size_t bitCount(uint64_t bits)
 176 {
 177     return bitCount(static_cast<unsigned>(bits)) + bitCount(static_cast<unsigned>(bits >> 32));
 178 }
 179
 180 // Macro that returns a compile time constant with the length of an array, but gives an error if passed a non-array.
 181 template<typename T, size_t Size> char (&ArrayLengthHelperFunction(T (&)[Size]))[Size];
 182 // GCC needs some help to deduce a 0 length array.
 183 #if COMPILER(GCC)
 184 template<typename T> char (&ArrayLengthHelperFunction(T (&)[0]))[0];
 185 #endif
 186 #define WTF_ARRAY_LENGTH(array) sizeof(::WTF::ArrayLengthHelperFunction(array))
 187
 188 // Efficient implementation that takes advantage of powers of two.
 189 inline size_t roundUpToMultipleOf(size_t divisor, size_t x)
 190 {
 191     ASSERT(divisor && !(divisor & (divisor - 1)));
 192     size_t remainderMask = divisor - 1;
 193     return (x + remainderMask) & ~remainderMask;
 194 }
 195
 196 template<size_t divisor> inline size_t roundUpToMultipleOf(size_t x)
 197 {
 198     static_assert(divisor && !(divisor & (divisor - 1)), "divisor must be a power of two!");
 199     return roundUpToMultipleOf(divisor, x);
 200 }
 201
 202 enum BinarySearchMode {
 203     KeyMustBePresentInArray,
 204     KeyMightNotBePresentInArray,
 205     ReturnAdjacentElementIfKeyIsNotPresent
 206 };
 207
 208 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey, BinarySearchMode mode>
 209 inline ArrayElementType* binarySearchImpl(ArrayType& array, size_t size, KeyType key, const ExtractKey& extractKey = ExtractKey())
 210 {
 211     size_t offset = 0;
 212     while (size > 1) {
 213         size_t pos = (size - 1) >> 1;
 214         KeyType val = extractKey(&array[offset + pos]);
 215
 216         if (val == key)
 217             return &array[offset + pos];
 218         // The item we are looking for is smaller than the item being check; reduce the value of 'size',
 219         // chopping off the right hand half of the array.
 220         if (key < val)
 221             size = pos;
 222         // Discard all values in the left hand half of the array, up to and including the item at pos.
 223         else {
 224             size -= (pos + 1);
 225             offset += (pos + 1);
 226         }
 227
 228         ASSERT(mode != KeyMustBePresentInArray || size);
 229     }
 230
 231     if (mode == KeyMightNotBePresentInArray && !size)
 232         return 0;
 233
 234     ArrayElementType* result = &array[offset];
 235
 236     if (mode == KeyMightNotBePresentInArray && key != extractKey(result))
 237         return 0;
 238
 239     if (mode == KeyMustBePresentInArray) {
 240         ASSERT(size == 1);
 241         ASSERT(key == extractKey(result));
 242     }
 243
 244     return result;
 245 }
 246
 247 // If the element is not found, crash if asserts are enabled, and behave like approximateBinarySearch in release builds.
 248 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
 249 inline ArrayElementType* binarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
 250 {
 251     return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMustBePresentInArray>(array, size, key, extractKey);
 252 }
 253
 254 // Return zero if the element is not found.
 255 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
 256 inline ArrayElementType* tryBinarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
 257 {
 258     return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMightNotBePresentInArray>(array, size, key, extractKey);
 259 }
 260
 261 // Return the element that is either to the left, or the right, of where the element would have been found.
 262 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
 263 inline ArrayElementType* approximateBinarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
 264 {
 265     return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, ReturnAdjacentElementIfKeyIsNotPresent>(array, size, key, extractKey);
 266 }
 267
 268 // Variants of the above that use const.
 269 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
 270 inline ArrayElementType* binarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
 271 {
 272     return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMustBePresentInArray>(const_cast<ArrayType&>(array), size, key, extractKey);
 273 }
 274 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
 275 inline ArrayElementType* tryBinarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
 276 {
 277     return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMightNotBePresentInArray>(const_cast<ArrayType&>(array), size, key, extractKey);
 278 }
 279 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
 280 inline ArrayElementType* approximateBinarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
 281 {
 282     return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, ReturnAdjacentElementIfKeyIsNotPresent>(const_cast<ArrayType&>(array), size, key, extractKey);
 283 }
 284
 285 template<typename VectorType, typename ElementType>
 286 inline void insertIntoBoundedVector(VectorType& vector, size_t size, const ElementType& element, size_t index)
 287 {
 288     for (size_t i = size; i-- > index + 1;)
 289         vector[i] = vector[i - 1];
 290     vector[index] = element;
 291 }
 292
 293 // This is here instead of CompilationThread.h to prevent that header from being included
 294 // everywhere. The fact that this method, and that header, exist outside of JSC is a bug.
 295 // https://bugs.webkit.org/show_bug.cgi?id=131815
 296 WTF_EXPORT_PRIVATE bool isCompilationThread();
 297
 298 } // namespace WTF
 299
 300 // This version of placement new omits a 0 check.
 301 enum NotNullTag { NotNull };
 302 inline void* operator new(size_t, NotNullTag, void* location)
 303 {
 304     ASSERT(location);
 305     return location;
 306 }
 307
 308 // This adds various C++14 features for versions of the STL that may not yet have them.
 309 namespace std {
 310 // MSVC 2013 supports std::make_unique already.
 311 #if !defined(_MSC_VER) || _MSC_VER < 1800
 312 template<class T> struct _Unique_if {
 313     typedef unique_ptr<T> _Single_object;
 314 };
 315
 316 template<class T> struct _Unique_if<T[]> {
 317     typedef unique_ptr<T[]> _Unknown_bound;
 318 };
 319
 320 template<class T, size_t N> struct _Unique_if<T[N]> {
 321     typedef void _Known_bound;
 322 };
 323
 324 template<class T, class... Args> inline typename _Unique_if<T>::_Single_object
 325 make_unique(Args&&... args)
 326 {
 327     return unique_ptr<T>(new T(std::forward<Args>(args)...));
 328 }
 329
 330 template<class T> inline typename _Unique_if<T>::_Unknown_bound
 331 make_unique(size_t n)
 332 {
 333     typedef typename remove_extent<T>::type U;
 334     return unique_ptr<T>(new U[n]());
 335 }
 336
 337 template<class T, class... Args> typename _Unique_if<T>::_Known_bound
 338 make_unique(Args&&...) = delete;
 339 #endif
 340
 341 // MSVC 2015 supports these functions.
 342 #if !COMPILER(MSVC) || _MSC_VER < 1900
 343 // Compile-time integer sequences
 344 // http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3658.html
 345 // (Note that we only implement index_sequence, and not the more generic integer_sequence).
 346 template<size_t... indexes> struct index_sequence {
 347     static size_t size() { return sizeof...(indexes); }
 348 };
 349
 350 template<size_t currentIndex, size_t...indexes> struct make_index_sequence_helper;
 351
 352 template<size_t...indexes> struct make_index_sequence_helper<0, indexes...> {
 353     typedef std::index_sequence<indexes...> type;
 354 };
 355
 356 template<size_t currentIndex, size_t...indexes> struct make_index_sequence_helper {
 357     typedef typename make_index_sequence_helper<currentIndex - 1, currentIndex - 1, indexes...>::type type;
 358 };
 359
 360 template<size_t length> struct make_index_sequence : public make_index_sequence_helper<length>::type { };
 361
 362 // std::exchange
 363 template<class T, class U = T>
 364 T exchange(T& t, U&& newValue)
 365 {
 366     T oldValue = std::move(t);
 367     t = std::forward<U>(newValue);
 368
 369     return oldValue;
 370 }
 371 #endif
 372
 373 #if COMPILER_SUPPORTS(CXX_USER_LITERALS)
 374 // These literals are available in C++14, so once we require C++14 compilers we can get rid of them here.
 375 // (User-literals need to have a leading underscore so we add it here - the "real" literals don't have underscores).
 376 namespace literals {
 377 namespace chrono_literals {
 378     CONSTEXPR inline chrono::seconds operator"" _s(unsigned long long s)
 379     {
 380         return chrono::seconds(static_cast<chrono::seconds::rep>(s));
 381     }
 382
 383     CONSTEXPR chrono::milliseconds operator"" _ms(unsigned long long ms)
 384     {
 385         return chrono::milliseconds(static_cast<chrono::milliseconds::rep>(ms));
 386     }
 387 }
 388 }
 389 #endif
 390 }
 391
 392 using WTF::KB;
 393 using WTF::MB;
 394 using WTF::isCompilationThread;
 395 using WTF::insertIntoBoundedVector;
 396 using WTF::isPointerAligned;
 397 using WTF::is8ByteAligned;
 398 using WTF::binarySearch;
 399 using WTF::tryBinarySearch;
 400 using WTF::approximateBinarySearch;
 401 using WTF::bitwise_cast;
 402 using WTF::safeCast;
 403
 404 #if COMPILER_SUPPORTS(CXX_USER_LITERALS)
 405 // We normally don't want to bring in entire std namespaces, but literals are an exception.
 406 using namespace std::literals::chrono_literals;
 407 #endif
 408
 409 #endif // WTF_StdLibExtras_h