Source/WTF/wtf/StdLibExtras.h

   1 /*
   2  * Copyright (C) 2008, 2016 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 <string.h>
  33 #include <wtf/Assertions.h>
  34 #include <wtf/CheckedArithmetic.h>
  35
  36 // This was used to declare and define a static local variable (static T;) so that
  37 //  it was leaked so that its destructors were not called at exit.
  38 // Newly written code should use static NeverDestroyed<T> instead.
  39 #ifndef DEPRECATED_DEFINE_STATIC_LOCAL
  40 #define DEPRECATED_DEFINE_STATIC_LOCAL(type, name, arguments) \
  41     static type& name = *new type arguments
  42 #endif
  43
  44 // Use this macro to declare and define a debug-only global variable that may have a
  45 // non-trivial constructor and destructor. When building with clang, this will suppress
  46 // warnings about global constructors and exit-time destructors.
  47 #define DEFINE_GLOBAL_FOR_LOGGING(type, name, arguments) \
  48     _Pragma("clang diagnostic push") \
  49     _Pragma("clang diagnostic ignored \"-Wglobal-constructors\"") \
  50     _Pragma("clang diagnostic ignored \"-Wexit-time-destructors\"") \
  51     static type name arguments; \
  52     _Pragma("clang diagnostic pop")
  53
  54 #ifndef NDEBUG
  55 #if COMPILER(CLANG)
  56 #define DEFINE_DEBUG_ONLY_GLOBAL(type, name, arguments) DEFINE_GLOBAL_FOR_LOGGING(type, name, arguments)
  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 // Make "PRId64" format specifier work for Visual C++ on Windows.
  75 #if OS(WINDOWS) && !defined(PRId64)
  76 #define PRId64 "lld"
  77 #endif
  78
  79 /*
  80  * The reinterpret_cast<Type1*>([pointer to Type2]) expressions - where
  81  * sizeof(Type1) > sizeof(Type2) - cause the following warning on ARM with GCC:
  82  * increases required alignment of target type.
  83  *
  84  * An implicit or an extra static_cast<void*> bypasses the warning.
  85  * For more info see the following bugzilla entries:
  86  * - https://bugs.webkit.org/show_bug.cgi?id=38045
  87  * - http://gcc.gnu.org/bugzilla/show_bug.cgi?id=43976
  88  */
  89 #if (CPU(ARM) || CPU(MIPS)) && COMPILER(GCC_OR_CLANG)
  90 template<typename Type>
  91 inline bool isPointerTypeAlignmentOkay(Type* ptr)
  92 {
  93     return !(reinterpret_cast<intptr_t>(ptr) % __alignof__(Type));
  94 }
  95
  96 template<typename TypePtr>
  97 inline TypePtr reinterpret_cast_ptr(void* ptr)
  98 {
  99     ASSERT(isPointerTypeAlignmentOkay(reinterpret_cast<TypePtr>(ptr)));
 100     return reinterpret_cast<TypePtr>(ptr);
 101 }
 102
 103 template<typename TypePtr>
 104 inline TypePtr reinterpret_cast_ptr(const void* ptr)
 105 {
 106     ASSERT(isPointerTypeAlignmentOkay(reinterpret_cast<TypePtr>(ptr)));
 107     return reinterpret_cast<TypePtr>(ptr);
 108 }
 109 #else
 110 template<typename Type>
 111 inline bool isPointerTypeAlignmentOkay(Type*)
 112 {
 113     return true;
 114 }
 115 #define reinterpret_cast_ptr reinterpret_cast
 116 #endif
 117
 118 namespace WTF {
 119
 120 enum CheckMoveParameterTag { CheckMoveParameter };
 121
 122 static const size_t KB = 1024;
 123 static const size_t MB = 1024 * 1024;
 124
 125 inline bool isPointerAligned(void* p)
 126 {
 127     return !((intptr_t)(p) & (sizeof(char*) - 1));
 128 }
 129
 130 inline bool is8ByteAligned(void* p)
 131 {
 132     return !((uintptr_t)(p) & (sizeof(double) - 1));
 133 }
 134
 135 /*
 136  * C++'s idea of a reinterpret_cast lacks sufficient cojones.
 137  */
 138 template<typename ToType, typename FromType>
 139 inline ToType bitwise_cast(FromType from)
 140 {
 141     static_assert(sizeof(FromType) == sizeof(ToType), "bitwise_cast size of FromType and ToType must be equal!");
 142     union {
 143         FromType from;
 144         ToType to;
 145     } u;
 146     u.from = from;
 147     return u.to;
 148 }
 149
 150 template<typename ToType, typename FromType>
 151 inline ToType safeCast(FromType value)
 152 {
 153     ASSERT(isInBounds<ToType>(value));
 154     return static_cast<ToType>(value);
 155 }
 156
 157 // Returns a count of the number of bits set in 'bits'.
 158 inline size_t bitCount(unsigned bits)
 159 {
 160     bits = bits - ((bits >> 1) & 0x55555555);
 161     bits = (bits & 0x33333333) + ((bits >> 2) & 0x33333333);
 162     return (((bits + (bits >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24;
 163 }
 164
 165 inline size_t bitCount(uint64_t bits)
 166 {
 167     return bitCount(static_cast<unsigned>(bits)) + bitCount(static_cast<unsigned>(bits >> 32));
 168 }
 169
 170 // Macro that returns a compile time constant with the length of an array, but gives an error if passed a non-array.
 171 template<typename T, size_t Size> char (&ArrayLengthHelperFunction(T (&)[Size]))[Size];
 172 // GCC needs some help to deduce a 0 length array.
 173 #if COMPILER(GCC_OR_CLANG)
 174 template<typename T> char (&ArrayLengthHelperFunction(T (&)[0]))[0];
 175 #endif
 176 #define WTF_ARRAY_LENGTH(array) sizeof(::WTF::ArrayLengthHelperFunction(array))
 177
 178 // Efficient implementation that takes advantage of powers of two.
 179 inline size_t roundUpToMultipleOf(size_t divisor, size_t x)
 180 {
 181     ASSERT(divisor && !(divisor & (divisor - 1)));
 182     size_t remainderMask = divisor - 1;
 183     return (x + remainderMask) & ~remainderMask;
 184 }
 185
 186 template<size_t divisor> inline size_t roundUpToMultipleOf(size_t x)
 187 {
 188     static_assert(divisor && !(divisor & (divisor - 1)), "divisor must be a power of two!");
 189     return roundUpToMultipleOf(divisor, x);
 190 }
 191
 192 enum BinarySearchMode {
 193     KeyMustBePresentInArray,
 194     KeyMightNotBePresentInArray,
 195     ReturnAdjacentElementIfKeyIsNotPresent
 196 };
 197
 198 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey, BinarySearchMode mode>
 199 inline ArrayElementType* binarySearchImpl(ArrayType& array, size_t size, KeyType key, const ExtractKey& extractKey = ExtractKey())
 200 {
 201     size_t offset = 0;
 202     while (size > 1) {
 203         size_t pos = (size - 1) >> 1;
 204         KeyType val = extractKey(&array[offset + pos]);
 205
 206         if (val == key)
 207             return &array[offset + pos];
 208         // The item we are looking for is smaller than the item being check; reduce the value of 'size',
 209         // chopping off the right hand half of the array.
 210         if (key < val)
 211             size = pos;
 212         // Discard all values in the left hand half of the array, up to and including the item at pos.
 213         else {
 214             size -= (pos + 1);
 215             offset += (pos + 1);
 216         }
 217
 218         ASSERT(mode != KeyMustBePresentInArray || size);
 219     }
 220
 221     if (mode == KeyMightNotBePresentInArray && !size)
 222         return 0;
 223
 224     ArrayElementType* result = &array[offset];
 225
 226     if (mode == KeyMightNotBePresentInArray && key != extractKey(result))
 227         return 0;
 228
 229     if (mode == KeyMustBePresentInArray) {
 230         ASSERT(size == 1);
 231         ASSERT(key == extractKey(result));
 232     }
 233
 234     return result;
 235 }
 236
 237 // If the element is not found, crash if asserts are enabled, and behave like approximateBinarySearch in release builds.
 238 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
 239 inline ArrayElementType* binarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
 240 {
 241     return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMustBePresentInArray>(array, size, key, extractKey);
 242 }
 243
 244 // Return zero if the element is not found.
 245 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
 246 inline ArrayElementType* tryBinarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
 247 {
 248     return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMightNotBePresentInArray>(array, size, key, extractKey);
 249 }
 250
 251 // Return the element that is either to the left, or the right, of where the element would have been found.
 252 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
 253 inline ArrayElementType* approximateBinarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
 254 {
 255     return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, ReturnAdjacentElementIfKeyIsNotPresent>(array, size, key, extractKey);
 256 }
 257
 258 // Variants of the above that use const.
 259 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
 260 inline ArrayElementType* binarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
 261 {
 262     return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMustBePresentInArray>(const_cast<ArrayType&>(array), size, key, extractKey);
 263 }
 264 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
 265 inline ArrayElementType* tryBinarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
 266 {
 267     return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMightNotBePresentInArray>(const_cast<ArrayType&>(array), size, key, extractKey);
 268 }
 269 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
 270 inline ArrayElementType* approximateBinarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
 271 {
 272     return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, ReturnAdjacentElementIfKeyIsNotPresent>(const_cast<ArrayType&>(array), size, key, extractKey);
 273 }
 274
 275 template<typename VectorType, typename ElementType>
 276 inline void insertIntoBoundedVector(VectorType& vector, size_t size, const ElementType& element, size_t index)
 277 {
 278     for (size_t i = size; i-- > index + 1;)
 279         vector[i] = vector[i - 1];
 280     vector[index] = element;
 281 }
 282
 283 // This is here instead of CompilationThread.h to prevent that header from being included
 284 // everywhere. The fact that this method, and that header, exist outside of JSC is a bug.
 285 // https://bugs.webkit.org/show_bug.cgi?id=131815
 286 WTF_EXPORT_PRIVATE bool isCompilationThread();
 287
 288 template<typename Func>
 289 bool isStatelessLambda()
 290 {
 291     return std::is_empty<Func>::value;
 292 }
 293
 294 template<typename ResultType, typename Func, typename... ArgumentTypes>
 295 ResultType callStatelessLambda(ArgumentTypes&&... arguments)
 296 {
 297     uint64_t data[(sizeof(Func) + sizeof(uint64_t) - 1) / sizeof(uint64_t)];
 298     memset(data, 0, sizeof(data));
 299     return (*bitwise_cast<Func*>(data))(std::forward<ArgumentTypes>(arguments)...);
 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 // This adds various C++14 features for versions of the STL that may not yet have them.
 313 namespace std {
 314 // MSVC 2013 supports std::make_unique already.
 315 #if !defined(_MSC_VER) || _MSC_VER < 1800
 316 template<class T> struct _Unique_if {
 317     typedef unique_ptr<T> _Single_object;
 318 };
 319
 320 template<class T> struct _Unique_if<T[]> {
 321     typedef unique_ptr<T[]> _Unknown_bound;
 322 };
 323
 324 template<class T, size_t N> struct _Unique_if<T[N]> {
 325     typedef void _Known_bound;
 326 };
 327
 328 template<class T, class... Args> inline typename _Unique_if<T>::_Single_object
 329 make_unique(Args&&... args)
 330 {
 331     return unique_ptr<T>(new T(std::forward<Args>(args)...));
 332 }
 333
 334 template<class T> inline typename _Unique_if<T>::_Unknown_bound
 335 make_unique(size_t n)
 336 {
 337     typedef typename remove_extent<T>::type U;
 338     return unique_ptr<T>(new U[n]());
 339 }
 340
 341 template<class T, class... Args> typename _Unique_if<T>::_Known_bound
 342 make_unique(Args&&...) = delete;
 343 #endif
 344
 345 // MSVC 2015 supports these functions.
 346 #if !COMPILER(MSVC) || _MSC_VER < 1900
 347 // Compile-time integer sequences
 348 // http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3658.html
 349 // (Note that we only implement index_sequence, and not the more generic integer_sequence).
 350 template<size_t... indexes> struct index_sequence {
 351     static size_t size() { return sizeof...(indexes); }
 352 };
 353
 354 template<size_t currentIndex, size_t...indexes> struct make_index_sequence_helper;
 355
 356 template<size_t...indexes> struct make_index_sequence_helper<0, indexes...> {
 357     typedef std::index_sequence<indexes...> type;
 358 };
 359
 360 template<size_t currentIndex, size_t...indexes> struct make_index_sequence_helper {
 361     typedef typename make_index_sequence_helper<currentIndex - 1, currentIndex - 1, indexes...>::type type;
 362 };
 363
 364 template<size_t length> struct make_index_sequence : public make_index_sequence_helper<length>::type { };
 365
 366 // std::exchange
 367 template<class T, class U = T>
 368 T exchange(T& t, U&& newValue)
 369 {
 370     T oldValue = std::move(t);
 371     t = std::forward<U>(newValue);
 372
 373     return oldValue;
 374 }
 375 #endif
 376
 377 #if COMPILER_SUPPORTS(CXX_USER_LITERALS)
 378 // These literals are available in C++14, so once we require C++14 compilers we can get rid of them here.
 379 // (User-literals need to have a leading underscore so we add it here - the "real" literals don't have underscores).
 380 namespace literals {
 381 namespace chrono_literals {
 382     constexpr inline chrono::seconds operator"" _s(unsigned long long s)
 383     {
 384         return chrono::seconds(static_cast<chrono::seconds::rep>(s));
 385     }
 386
 387     constexpr chrono::milliseconds operator"" _ms(unsigned long long ms)
 388     {
 389         return chrono::milliseconds(static_cast<chrono::milliseconds::rep>(ms));
 390     }
 391 }
 392 }
 393 #endif
 394
 395 template<WTF::CheckMoveParameterTag, typename T>
 396 ALWAYS_INLINE constexpr typename remove_reference<T>::type&& move(T&& value)
 397 {
 398     static_assert(is_lvalue_reference<T>::value, "T is not an lvalue reference; move() is unnecessary.");
 399
 400     using NonRefQualifiedType = typename remove_reference<T>::type;
 401     static_assert(!is_const<NonRefQualifiedType>::value, "T is const qualified.");
 402
 403     return move(forward<T>(value));
 404 }
 405
 406 } // namespace std
 407
 408 #define WTFMove(value) std::move<WTF::CheckMoveParameter>(value)
 409
 410 using WTF::KB;
 411 using WTF::MB;
 412 using WTF::isCompilationThread;
 413 using WTF::insertIntoBoundedVector;
 414 using WTF::isPointerAligned;
 415 using WTF::is8ByteAligned;
 416 using WTF::binarySearch;
 417 using WTF::tryBinarySearch;
 418 using WTF::approximateBinarySearch;
 419 using WTF::bitwise_cast;
 420 using WTF::safeCast;
 421 using WTF::isStatelessLambda;
 422 using WTF::callStatelessLambda;
 423
 424 #if COMPILER_SUPPORTS(CXX_USER_LITERALS)
 425 // We normally don't want to bring in entire std namespaces, but literals are an exception.
 426 using namespace std::literals::chrono_literals;
 427 #endif
 428
 429 #endif // WTF_StdLibExtras_h