From 1bf1084f2b10c3b47fd1a588d85d21ed0eb41d0c Mon Sep 17 00:00:00 2001 From: Lorry Tar Creator Date: Tue, 27 Jun 2017 06:07:23 +0000 Subject: webkitgtk-2.16.5 --- Source/WTF/wtf/ASCIICType.h | 220 +- Source/WTF/wtf/AVLTree.h | 960 ---- Source/WTF/wtf/Assertions.cpp | 246 +- Source/WTF/wtf/Assertions.h | 232 +- Source/WTF/wtf/Atomics.cpp | 53 +- Source/WTF/wtf/Atomics.h | 585 ++- Source/WTF/wtf/AutodrainedPool.h | 8 +- Source/WTF/wtf/AutomaticThread.cpp | 235 + Source/WTF/wtf/AutomaticThread.h | 193 + Source/WTF/wtf/BackwardsGraph.h | 295 ++ Source/WTF/wtf/Bag.h | 46 +- Source/WTF/wtf/BagToHashMap.h | 6 +- Source/WTF/wtf/BitVector.cpp | 44 + Source/WTF/wtf/BitVector.h | 162 +- Source/WTF/wtf/Bitmap.h | 208 +- Source/WTF/wtf/BlockObjCExceptions.h | 32 + Source/WTF/wtf/BlockPtr.h | 169 + Source/WTF/wtf/BloomFilter.h | 184 +- Source/WTF/wtf/BoundsCheckedPointer.h | 286 -- Source/WTF/wtf/Box.h | 81 + Source/WTF/wtf/Brigand.h | 2489 ++++++++++ Source/WTF/wtf/BubbleSort.h | 102 + Source/WTF/wtf/ByteOrder.h | 2 - Source/WTF/wtf/ByteSpinLock.h | 71 - Source/WTF/wtf/CMakeLists.txt | 356 ++ Source/WTF/wtf/CONTRIBUTORS.pthreads-win32 | 137 + Source/WTF/wtf/CheckedArithmetic.h | 173 +- Source/WTF/wtf/ClockType.cpp | 47 + Source/WTF/wtf/ClockType.h | 44 + Source/WTF/wtf/CommaPrinter.h | 17 +- Source/WTF/wtf/CompilationThread.cpp | 6 +- Source/WTF/wtf/CompilationThread.h | 2 - Source/WTF/wtf/Compiler.h | 149 +- Source/WTF/wtf/Compression.cpp | 179 - Source/WTF/wtf/Compression.h | 149 - Source/WTF/wtf/Condition.h | 193 + Source/WTF/wtf/CrossThreadCopier.cpp | 83 + Source/WTF/wtf/CrossThreadCopier.h | 139 + Source/WTF/wtf/CrossThreadQueue.h | 96 + Source/WTF/wtf/CrossThreadTask.h | 102 + Source/WTF/wtf/CryptographicUtilities.cpp | 44 + Source/WTF/wtf/CryptographicUtilities.h | 38 + Source/WTF/wtf/CryptographicallyRandomNumber.cpp | 7 +- Source/WTF/wtf/CryptographicallyRandomNumber.h | 4 +- Source/WTF/wtf/CurrentTime.cpp | 86 +- Source/WTF/wtf/CurrentTime.h | 25 +- Source/WTF/wtf/DataLog.cpp | 108 +- Source/WTF/wtf/DataLog.h | 96 +- Source/WTF/wtf/DateMath.cpp | 80 +- Source/WTF/wtf/Decoder.h | 57 - Source/WTF/wtf/DeferrableRefCounted.h | 38 +- Source/WTF/wtf/DeprecatedOptional.h | 51 + Source/WTF/wtf/Deque.h | 1189 ++--- Source/WTF/wtf/DisallowCType.h | 5 +- Source/WTF/wtf/Dominators.h | 752 +++ Source/WTF/wtf/DynamicAnnotations.cpp | 61 - Source/WTF/wtf/DynamicAnnotations.h | 98 - Source/WTF/wtf/Encoder.h | 57 - Source/WTF/wtf/EnumTraits.h | 64 + Source/WTF/wtf/Expected.h | 456 ++ Source/WTF/wtf/ExportMacros.h | 26 +- Source/WTF/wtf/FastBitVector.cpp | 48 +- Source/WTF/wtf/FastBitVector.h | 561 ++- Source/WTF/wtf/FastMalloc.cpp | 5147 +------------------- Source/WTF/wtf/FastMalloc.h | 338 +- Source/WTF/wtf/FeatureDefines.h | 433 +- Source/WTF/wtf/FilePrintStream.h | 5 +- Source/WTF/wtf/FlipBytes.h | 2 - Source/WTF/wtf/ForbidHeapAllocation.h | 37 + Source/WTF/wtf/Forward.h | 33 +- Source/WTF/wtf/Function.h | 100 + Source/WTF/wtf/FunctionDispatcher.h | 8 +- Source/WTF/wtf/Functional.h | 782 --- Source/WTF/wtf/GetPtr.h | 59 +- Source/WTF/wtf/GraphNodeWorklist.h | 223 + Source/WTF/wtf/GregorianDateTime.cpp | 23 +- Source/WTF/wtf/HashCountedSet.h | 104 +- Source/WTF/wtf/HashFunctions.h | 52 +- Source/WTF/wtf/HashIterators.h | 26 +- Source/WTF/wtf/HashMap.h | 187 +- Source/WTF/wtf/HashMethod.h | 45 + Source/WTF/wtf/HashSet.h | 104 +- Source/WTF/wtf/HashTable.cpp | 15 +- Source/WTF/wtf/HashTable.h | 356 +- Source/WTF/wtf/HashTraits.h | 143 +- Source/WTF/wtf/Hasher.h | 389 ++ Source/WTF/wtf/HexNumber.h | 43 +- Source/WTF/wtf/Indenter.h | 67 + Source/WTF/wtf/IndexMap.h | 82 + Source/WTF/wtf/IndexSet.h | 163 + Source/WTF/wtf/IndexSparseSet.h | 147 + Source/WTF/wtf/IndexedContainerIterator.h | 81 + Source/WTF/wtf/InlineASM.h | 11 +- Source/WTF/wtf/Insertion.h | 31 +- Source/WTF/wtf/IteratorAdaptors.h | 20 +- Source/WTF/wtf/IteratorRange.h | 4 +- Source/WTF/wtf/LEBDecoder.h | 107 + Source/WTF/wtf/ListDump.h | 67 +- Source/WTF/wtf/ListHashSet.h | 404 +- Source/WTF/wtf/Lock.cpp | 52 + Source/WTF/wtf/Lock.h | 153 + Source/WTF/wtf/LockAlgorithm.h | 238 + Source/WTF/wtf/LockedPrintStream.cpp | 64 + Source/WTF/wtf/LockedPrintStream.h | 58 + Source/WTF/wtf/Locker.h | 81 +- Source/WTF/wtf/LoggingAccumulator.h | 38 + Source/WTF/wtf/MD5.cpp | 22 + Source/WTF/wtf/MD5.h | 8 + Source/WTF/wtf/MainThread.cpp | 180 +- Source/WTF/wtf/MainThread.h | 46 +- Source/WTF/wtf/MallocPtr.h | 19 +- Source/WTF/wtf/MathExtras.h | 184 +- Source/WTF/wtf/MediaTime.cpp | 243 +- Source/WTF/wtf/MediaTime.h | 58 +- Source/WTF/wtf/MemoryFootprint.cpp | 50 + Source/WTF/wtf/MemoryFootprint.h | 37 + Source/WTF/wtf/MessageQueue.h | 75 +- Source/WTF/wtf/MetaAllocator.cpp | 41 +- Source/WTF/wtf/MetaAllocator.h | 13 +- Source/WTF/wtf/MetaAllocatorHandle.h | 7 +- Source/WTF/wtf/MonotonicTime.cpp | 53 + Source/WTF/wtf/MonotonicTime.h | 144 + Source/WTF/wtf/NakedPtr.h | 119 + Source/WTF/wtf/NeverDestroyed.h | 62 +- Source/WTF/wtf/NumberOfCores.cpp | 21 +- Source/WTF/wtf/OSAllocator.h | 20 +- Source/WTF/wtf/OSAllocatorPosix.cpp | 18 +- Source/WTF/wtf/OSAllocatorWin.cpp | 8 +- Source/WTF/wtf/OSObjectPtr.h | 136 + Source/WTF/wtf/OSRandomSource.cpp | 43 +- Source/WTF/wtf/OSRandomSource.h | 2 +- Source/WTF/wtf/OptionSet.h | 144 + Source/WTF/wtf/Optional.h | 1109 +++++ Source/WTF/wtf/OrderMaker.h | 143 + Source/WTF/wtf/OwnPtr.h | 193 - Source/WTF/wtf/OwnPtrCommon.h | 70 - Source/WTF/wtf/PageAllocationAligned.cpp | 85 - Source/WTF/wtf/PageAllocationAligned.h | 70 - Source/WTF/wtf/PageBlock.h | 1 - Source/WTF/wtf/PageReservation.h | 7 - Source/WTF/wtf/ParallelHelperPool.cpp | 237 + Source/WTF/wtf/ParallelHelperPool.h | 220 + Source/WTF/wtf/ParallelJobsGeneric.cpp | 10 +- Source/WTF/wtf/ParallelJobsGeneric.h | 10 +- Source/WTF/wtf/ParallelVectorIterator.h | 82 + Source/WTF/wtf/ParkingLot.cpp | 813 ++++ Source/WTF/wtf/ParkingLot.h | 182 + Source/WTF/wtf/PassOwnPtr.h | 170 - Source/WTF/wtf/PassRef.h | 162 - Source/WTF/wtf/PassRefPtr.h | 39 +- Source/WTF/wtf/Platform.h | 764 +-- Source/WTF/wtf/PlatformGTK.cmake | 26 + Source/WTF/wtf/PlatformJSCOnly.cmake | 32 + Source/WTF/wtf/PlatformUserPreferredLanguages.h | 45 + .../WTF/wtf/PlatformUserPreferredLanguagesUnix.cpp | 52 + .../WTF/wtf/PlatformUserPreferredLanguagesWin.cpp | 83 + Source/WTF/wtf/PointerComparison.h | 40 + Source/WTF/wtf/PossiblyNull.h | 59 - Source/WTF/wtf/PrintStream.cpp | 35 + Source/WTF/wtf/PrintStream.h | 319 +- Source/WTF/wtf/ProcessID.h | 2 - Source/WTF/wtf/RAMSize.cpp | 57 +- Source/WTF/wtf/RandomNumber.cpp | 4 +- Source/WTF/wtf/RandomNumber.h | 4 +- Source/WTF/wtf/RandomNumberSeed.h | 7 +- Source/WTF/wtf/RangeSet.h | 195 + Source/WTF/wtf/RecursiveLockAdapter.h | 93 + Source/WTF/wtf/RedBlackTree.h | 2 +- Source/WTF/wtf/Ref.h | 184 +- Source/WTF/wtf/RefCounted.h | 30 +- Source/WTF/wtf/RefCountedArray.h | 13 +- Source/WTF/wtf/RefCountedLeakCounter.cpp | 4 + Source/WTF/wtf/RefCounter.h | 132 + Source/WTF/wtf/RefPtr.h | 389 +- Source/WTF/wtf/RefPtrHashMap.h | 334 -- Source/WTF/wtf/RetainPtr.h | 487 +- Source/WTF/wtf/RunLoop.cpp | 50 +- Source/WTF/wtf/RunLoop.h | 123 +- Source/WTF/wtf/RunLoopTimer.h | 83 + Source/WTF/wtf/RunLoopTimerCF.cpp | 92 + Source/WTF/wtf/SHA1.cpp | 68 +- Source/WTF/wtf/SHA1.h | 14 +- Source/WTF/wtf/SaturatedArithmetic.h | 54 +- Source/WTF/wtf/SchedulePair.h | 94 + Source/WTF/wtf/SchedulePairCF.cpp | 45 + Source/WTF/wtf/Scope.h | 79 + Source/WTF/wtf/ScopedLambda.h | 190 + Source/WTF/wtf/Seconds.cpp | 78 + Source/WTF/wtf/Seconds.h | 265 + Source/WTF/wtf/SegmentedVector.h | 144 +- Source/WTF/wtf/SentinelLinkedList.h | 109 +- Source/WTF/wtf/SetForScope.h | 71 + Source/WTF/wtf/SharedTask.h | 131 + Source/WTF/wtf/SimpleStats.h | 8 +- Source/WTF/wtf/SixCharacterHash.cpp | 24 +- Source/WTF/wtf/SizeLimits.cpp | 83 + Source/WTF/wtf/SmallPtrSet.h | 253 + Source/WTF/wtf/Spectrum.h | 41 +- Source/WTF/wtf/StackBounds.cpp | 13 +- Source/WTF/wtf/StackBounds.h | 42 +- Source/WTF/wtf/StackStats.cpp | 302 ++ Source/WTF/wtf/StackStats.h | 7 +- Source/WTF/wtf/StaticConstructors.h | 2 +- Source/WTF/wtf/StdLibExtras.h | 286 +- Source/WTF/wtf/Stopwatch.h | 95 + Source/WTF/wtf/StreamBuffer.h | 6 +- Source/WTF/wtf/StringExtras.h | 57 +- Source/WTF/wtf/StringHasher.h | 296 -- Source/WTF/wtf/StringPrintStream.cpp | 34 +- Source/WTF/wtf/StringPrintStream.h | 56 +- Source/WTF/wtf/SynchronizedFixedQueue.h | 121 + Source/WTF/wtf/SystemTracing.h | 119 + Source/WTF/wtf/TCPackedCache.h | 234 - Source/WTF/wtf/TCPageMap.h | 361 -- Source/WTF/wtf/TCSpinLock.h | 133 - Source/WTF/wtf/TCSystemAlloc.cpp | 513 -- Source/WTF/wtf/TCSystemAlloc.h | 75 - Source/WTF/wtf/TemporaryChange.h | 68 - Source/WTF/wtf/ThreadFunctionInvocation.h | 2 +- Source/WTF/wtf/ThreadIdentifierDataPthreads.cpp | 7 +- Source/WTF/wtf/ThreadSafeRefCounted.h | 88 +- Source/WTF/wtf/ThreadSpecific.h | 160 +- Source/WTF/wtf/ThreadSpecificWin.cpp | 101 +- Source/WTF/wtf/Threading.cpp | 145 +- Source/WTF/wtf/Threading.h | 66 +- Source/WTF/wtf/ThreadingPrimitives.h | 4 +- Source/WTF/wtf/ThreadingPthreads.cpp | 61 +- Source/WTF/wtf/ThreadingWin.cpp | 56 +- Source/WTF/wtf/TimeWithDynamicClockType.cpp | 147 + Source/WTF/wtf/TimeWithDynamicClockType.h | 145 + Source/WTF/wtf/TinyLRUCache.h | 84 + Source/WTF/wtf/TinyPtrSet.h | 521 ++ Source/WTF/wtf/TypeCasts.h | 112 + Source/WTF/wtf/UniStdExtras.cpp | 67 + Source/WTF/wtf/UniStdExtras.h | 5 + Source/WTF/wtf/UniqueRef.h | 79 + Source/WTF/wtf/VMTags.h | 7 - Source/WTF/wtf/Variant.h | 2079 ++++++++ Source/WTF/wtf/Vector.h | 575 ++- Source/WTF/wtf/VectorTraits.h | 24 +- Source/WTF/wtf/WTFThreadData.cpp | 54 +- Source/WTF/wtf/WTFThreadData.h | 92 +- Source/WTF/wtf/WallTime.cpp | 53 + Source/WTF/wtf/WallTime.h | 143 + Source/WTF/wtf/WeakPtr.h | 84 +- Source/WTF/wtf/WeakRandom.h | 113 + Source/WTF/wtf/WindowsExtras.h | 17 - Source/WTF/wtf/WordLock.cpp | 267 + Source/WTF/wtf/WordLock.h | 118 + Source/WTF/wtf/WorkQueue.cpp | 158 + Source/WTF/wtf/WorkQueue.h | 117 + Source/WTF/wtf/dtoa.cpp | 15 +- Source/WTF/wtf/dtoa.h | 15 +- Source/WTF/wtf/dtoa/COPYING | 26 + Source/WTF/wtf/dtoa/LICENSE | 26 + Source/WTF/wtf/dtoa/README | 11 + Source/WTF/wtf/dtoa/bignum.cc | 18 +- Source/WTF/wtf/dtoa/double-conversion.cc | 13 +- Source/WTF/wtf/dtoa/strtod.cc | 13 +- Source/WTF/wtf/dtoa/utils.h | 6 +- Source/WTF/wtf/generic/MainThreadGeneric.cpp | 43 + Source/WTF/wtf/generic/RunLoopGeneric.cpp | 288 ++ Source/WTF/wtf/generic/WorkQueueGeneric.cpp | 73 + Source/WTF/wtf/glib/GLibUtilities.cpp | 65 + Source/WTF/wtf/glib/GLibUtilities.h | 37 + Source/WTF/wtf/glib/GMutexLocker.h | 102 + Source/WTF/wtf/glib/GRefPtr.cpp | 161 + Source/WTF/wtf/glib/GRefPtr.h | 261 + Source/WTF/wtf/glib/GTypedefs.h | 111 + Source/WTF/wtf/glib/GUniquePtr.h | 128 + Source/WTF/wtf/glib/MainThreadGLib.cpp | 81 + Source/WTF/wtf/glib/RunLoopGLib.cpp | 215 + Source/WTF/wtf/gobject/GMutexLocker.h | 72 - Source/WTF/wtf/gobject/GRefPtr.cpp | 164 - Source/WTF/wtf/gobject/GRefPtr.h | 245 - Source/WTF/wtf/gobject/GTypedefs.h | 109 - Source/WTF/wtf/gobject/GUniquePtr.h | 127 - Source/WTF/wtf/gobject/GlibUtilities.cpp | 65 - Source/WTF/wtf/gobject/GlibUtilities.h | 28 - Source/WTF/wtf/gtk/MainThreadGtk.cpp | 52 - Source/WTF/wtf/gtk/RunLoopGtk.cpp | 169 - Source/WTF/wtf/mbmalloc.cpp | 58 + Source/WTF/wtf/persistence/Coder.h | 47 + Source/WTF/wtf/persistence/Coders.cpp | 156 + Source/WTF/wtf/persistence/Coders.h | 302 ++ Source/WTF/wtf/persistence/Decoder.cpp | 133 + Source/WTF/wtf/persistence/Decoder.h | 100 + Source/WTF/wtf/persistence/Encoder.cpp | 126 + Source/WTF/wtf/persistence/Encoder.h | 114 + Source/WTF/wtf/spi/darwin/CommonCryptoSPI.h | 46 + Source/WTF/wtf/spi/darwin/SandboxSPI.h | 55 + Source/WTF/wtf/spi/darwin/XPCSPI.h | 162 + Source/WTF/wtf/spi/darwin/dyldSPI.h | 69 + Source/WTF/wtf/text/ASCIIFastPath.h | 16 +- Source/WTF/wtf/text/AtomicString.cpp | 467 +- Source/WTF/wtf/text/AtomicString.h | 250 +- Source/WTF/wtf/text/AtomicStringHash.h | 21 +- Source/WTF/wtf/text/AtomicStringImpl.cpp | 540 ++ Source/WTF/wtf/text/AtomicStringImpl.h | 91 +- Source/WTF/wtf/text/AtomicStringTable.cpp | 15 +- Source/WTF/wtf/text/AtomicStringTable.h | 1 + Source/WTF/wtf/text/Base64.cpp | 76 +- Source/WTF/wtf/text/Base64.h | 134 +- Source/WTF/wtf/text/CString.cpp | 14 +- Source/WTF/wtf/text/CString.h | 8 +- Source/WTF/wtf/text/IntegerToStringConversion.h | 84 +- Source/WTF/wtf/text/LChar.h | 8 +- Source/WTF/wtf/text/LineBreakIteratorPoolICU.h | 132 + Source/WTF/wtf/text/OrdinalNumber.h | 54 + Source/WTF/wtf/text/StringBuffer.h | 2 +- Source/WTF/wtf/text/StringBuilder.cpp | 153 +- Source/WTF/wtf/text/StringBuilder.h | 55 +- Source/WTF/wtf/text/StringCommon.h | 656 +++ Source/WTF/wtf/text/StringConcatenate.h | 893 +--- Source/WTF/wtf/text/StringConcatenateNumbers.h | 175 + Source/WTF/wtf/text/StringHash.h | 37 +- Source/WTF/wtf/text/StringImpl.cpp | 942 ++-- Source/WTF/wtf/text/StringImpl.h | 974 ++-- Source/WTF/wtf/text/StringOperators.h | 8 +- Source/WTF/wtf/text/StringStatics.cpp | 36 +- Source/WTF/wtf/text/StringView.cpp | 285 ++ Source/WTF/wtf/text/StringView.h | 952 +++- Source/WTF/wtf/text/SymbolImpl.cpp | 59 + Source/WTF/wtf/text/SymbolImpl.h | 126 + Source/WTF/wtf/text/SymbolRegistry.cpp | 63 + Source/WTF/wtf/text/SymbolRegistry.h | 113 + Source/WTF/wtf/text/TextBreakIterator.cpp | 448 ++ Source/WTF/wtf/text/TextBreakIterator.h | 191 + Source/WTF/wtf/text/TextBreakIteratorInternalICU.h | 37 + Source/WTF/wtf/text/TextPosition.h | 37 +- Source/WTF/wtf/text/UniquedStringImpl.h | 65 + Source/WTF/wtf/text/WTFString.cpp | 273 +- Source/WTF/wtf/text/WTFString.h | 352 +- Source/WTF/wtf/text/icu/UTextProvider.cpp | 72 + Source/WTF/wtf/text/icu/UTextProvider.h | 111 + Source/WTF/wtf/text/icu/UTextProviderLatin1.cpp | 394 ++ Source/WTF/wtf/text/icu/UTextProviderLatin1.h | 46 + Source/WTF/wtf/text/icu/UTextProviderUTF16.cpp | 184 + Source/WTF/wtf/text/icu/UTextProviderUTF16.h | 37 + .../text/unix/TextBreakIteratorInternalICUUnix.cpp | 41 + Source/WTF/wtf/threads/BinarySemaphore.cpp | 11 +- Source/WTF/wtf/threads/BinarySemaphore.h | 13 +- Source/WTF/wtf/unicode/CharacterNames.h | 36 +- Source/WTF/wtf/unicode/Collator.h | 53 +- Source/WTF/wtf/unicode/CollatorDefault.cpp | 48 +- Source/WTF/wtf/unicode/ScriptCodesFromICU.h | 153 - Source/WTF/wtf/unicode/UTF8.cpp | 42 +- Source/WTF/wtf/unicode/UTF8.h | 11 +- Source/WTF/wtf/unicode/Unicode.h | 35 - Source/WTF/wtf/unicode/UnicodeMacrosFromICU.h | 100 - Source/WTF/wtf/unicode/icu/CollatorICU.cpp | 267 +- Source/WTF/wtf/unicode/icu/UnicodeIcu.h | 32 - Source/WTF/wtf/win/GDIObject.h | 131 - 353 files changed, 37149 insertions(+), 20290 deletions(-) delete mode 100644 Source/WTF/wtf/AVLTree.h create mode 100644 Source/WTF/wtf/AutomaticThread.cpp create mode 100644 Source/WTF/wtf/AutomaticThread.h create mode 100644 Source/WTF/wtf/BackwardsGraph.h create mode 100644 Source/WTF/wtf/BlockObjCExceptions.h create mode 100644 Source/WTF/wtf/BlockPtr.h delete mode 100644 Source/WTF/wtf/BoundsCheckedPointer.h create mode 100644 Source/WTF/wtf/Box.h create mode 100644 Source/WTF/wtf/Brigand.h create mode 100644 Source/WTF/wtf/BubbleSort.h delete mode 100644 Source/WTF/wtf/ByteSpinLock.h create mode 100644 Source/WTF/wtf/CMakeLists.txt create mode 100644 Source/WTF/wtf/CONTRIBUTORS.pthreads-win32 create mode 100644 Source/WTF/wtf/ClockType.cpp create mode 100644 Source/WTF/wtf/ClockType.h delete mode 100644 Source/WTF/wtf/Compression.cpp delete mode 100644 Source/WTF/wtf/Compression.h create mode 100644 Source/WTF/wtf/Condition.h create mode 100644 Source/WTF/wtf/CrossThreadCopier.cpp create mode 100644 Source/WTF/wtf/CrossThreadCopier.h create mode 100644 Source/WTF/wtf/CrossThreadQueue.h create mode 100644 Source/WTF/wtf/CrossThreadTask.h create mode 100644 Source/WTF/wtf/CryptographicUtilities.cpp create mode 100644 Source/WTF/wtf/CryptographicUtilities.h delete mode 100644 Source/WTF/wtf/Decoder.h create mode 100644 Source/WTF/wtf/DeprecatedOptional.h create mode 100644 Source/WTF/wtf/Dominators.h delete mode 100644 Source/WTF/wtf/DynamicAnnotations.cpp delete mode 100644 Source/WTF/wtf/DynamicAnnotations.h delete mode 100644 Source/WTF/wtf/Encoder.h create mode 100644 Source/WTF/wtf/EnumTraits.h create mode 100644 Source/WTF/wtf/Expected.h create mode 100644 Source/WTF/wtf/ForbidHeapAllocation.h create mode 100644 Source/WTF/wtf/Function.h delete mode 100644 Source/WTF/wtf/Functional.h create mode 100644 Source/WTF/wtf/GraphNodeWorklist.h create mode 100644 Source/WTF/wtf/HashMethod.h create mode 100644 Source/WTF/wtf/Hasher.h create mode 100644 Source/WTF/wtf/Indenter.h create mode 100644 Source/WTF/wtf/IndexMap.h create mode 100644 Source/WTF/wtf/IndexSet.h create mode 100644 Source/WTF/wtf/IndexSparseSet.h create mode 100644 Source/WTF/wtf/IndexedContainerIterator.h create mode 100644 Source/WTF/wtf/LEBDecoder.h create mode 100644 Source/WTF/wtf/Lock.cpp create mode 100644 Source/WTF/wtf/Lock.h create mode 100644 Source/WTF/wtf/LockAlgorithm.h create mode 100644 Source/WTF/wtf/LockedPrintStream.cpp create mode 100644 Source/WTF/wtf/LockedPrintStream.h create mode 100644 Source/WTF/wtf/LoggingAccumulator.h create mode 100644 Source/WTF/wtf/MemoryFootprint.cpp create mode 100644 Source/WTF/wtf/MemoryFootprint.h create mode 100644 Source/WTF/wtf/MonotonicTime.cpp create mode 100644 Source/WTF/wtf/MonotonicTime.h create mode 100644 Source/WTF/wtf/NakedPtr.h create mode 100644 Source/WTF/wtf/OSObjectPtr.h create mode 100644 Source/WTF/wtf/OptionSet.h create mode 100644 Source/WTF/wtf/Optional.h create mode 100644 Source/WTF/wtf/OrderMaker.h delete mode 100644 Source/WTF/wtf/OwnPtr.h delete mode 100644 Source/WTF/wtf/OwnPtrCommon.h delete mode 100644 Source/WTF/wtf/PageAllocationAligned.cpp delete mode 100644 Source/WTF/wtf/PageAllocationAligned.h create mode 100644 Source/WTF/wtf/ParallelHelperPool.cpp create mode 100644 Source/WTF/wtf/ParallelHelperPool.h create mode 100644 Source/WTF/wtf/ParallelVectorIterator.h create mode 100644 Source/WTF/wtf/ParkingLot.cpp create mode 100644 Source/WTF/wtf/ParkingLot.h delete mode 100644 Source/WTF/wtf/PassOwnPtr.h delete mode 100644 Source/WTF/wtf/PassRef.h create mode 100644 Source/WTF/wtf/PlatformGTK.cmake create mode 100644 Source/WTF/wtf/PlatformJSCOnly.cmake create mode 100644 Source/WTF/wtf/PlatformUserPreferredLanguages.h create mode 100644 Source/WTF/wtf/PlatformUserPreferredLanguagesUnix.cpp create mode 100644 Source/WTF/wtf/PlatformUserPreferredLanguagesWin.cpp create mode 100644 Source/WTF/wtf/PointerComparison.h delete mode 100644 Source/WTF/wtf/PossiblyNull.h create mode 100644 Source/WTF/wtf/RangeSet.h create mode 100644 Source/WTF/wtf/RecursiveLockAdapter.h create mode 100644 Source/WTF/wtf/RefCounter.h delete mode 100644 Source/WTF/wtf/RefPtrHashMap.h create mode 100644 Source/WTF/wtf/RunLoopTimer.h create mode 100644 Source/WTF/wtf/RunLoopTimerCF.cpp create mode 100644 Source/WTF/wtf/SchedulePair.h create mode 100644 Source/WTF/wtf/SchedulePairCF.cpp create mode 100644 Source/WTF/wtf/Scope.h create mode 100644 Source/WTF/wtf/ScopedLambda.h create mode 100644 Source/WTF/wtf/Seconds.cpp create mode 100644 Source/WTF/wtf/Seconds.h create mode 100644 Source/WTF/wtf/SetForScope.h create mode 100644 Source/WTF/wtf/SharedTask.h create mode 100644 Source/WTF/wtf/SizeLimits.cpp create mode 100644 Source/WTF/wtf/SmallPtrSet.h create mode 100644 Source/WTF/wtf/StackStats.cpp create mode 100644 Source/WTF/wtf/Stopwatch.h delete mode 100644 Source/WTF/wtf/StringHasher.h create mode 100644 Source/WTF/wtf/SynchronizedFixedQueue.h create mode 100644 Source/WTF/wtf/SystemTracing.h delete mode 100644 Source/WTF/wtf/TCPackedCache.h delete mode 100644 Source/WTF/wtf/TCPageMap.h delete mode 100644 Source/WTF/wtf/TCSpinLock.h delete mode 100644 Source/WTF/wtf/TCSystemAlloc.cpp delete mode 100644 Source/WTF/wtf/TCSystemAlloc.h delete mode 100644 Source/WTF/wtf/TemporaryChange.h create mode 100644 Source/WTF/wtf/TimeWithDynamicClockType.cpp create mode 100644 Source/WTF/wtf/TimeWithDynamicClockType.h create mode 100644 Source/WTF/wtf/TinyLRUCache.h create mode 100644 Source/WTF/wtf/TinyPtrSet.h create mode 100644 Source/WTF/wtf/TypeCasts.h create mode 100644 Source/WTF/wtf/UniStdExtras.cpp create mode 100644 Source/WTF/wtf/UniqueRef.h create mode 100644 Source/WTF/wtf/Variant.h create mode 100644 Source/WTF/wtf/WallTime.cpp create mode 100644 Source/WTF/wtf/WallTime.h create mode 100644 Source/WTF/wtf/WeakRandom.h create mode 100644 Source/WTF/wtf/WordLock.cpp create mode 100644 Source/WTF/wtf/WordLock.h create mode 100644 Source/WTF/wtf/WorkQueue.cpp create mode 100644 Source/WTF/wtf/WorkQueue.h create mode 100644 Source/WTF/wtf/dtoa/COPYING create mode 100644 Source/WTF/wtf/dtoa/LICENSE create mode 100644 Source/WTF/wtf/dtoa/README create mode 100644 Source/WTF/wtf/generic/MainThreadGeneric.cpp create mode 100644 Source/WTF/wtf/generic/RunLoopGeneric.cpp create mode 100644 Source/WTF/wtf/generic/WorkQueueGeneric.cpp create mode 100644 Source/WTF/wtf/glib/GLibUtilities.cpp create mode 100644 Source/WTF/wtf/glib/GLibUtilities.h create mode 100644 Source/WTF/wtf/glib/GMutexLocker.h create mode 100644 Source/WTF/wtf/glib/GRefPtr.cpp create mode 100644 Source/WTF/wtf/glib/GRefPtr.h create mode 100644 Source/WTF/wtf/glib/GTypedefs.h create mode 100644 Source/WTF/wtf/glib/GUniquePtr.h create mode 100644 Source/WTF/wtf/glib/MainThreadGLib.cpp create mode 100644 Source/WTF/wtf/glib/RunLoopGLib.cpp delete mode 100644 Source/WTF/wtf/gobject/GMutexLocker.h delete mode 100644 Source/WTF/wtf/gobject/GRefPtr.cpp delete mode 100644 Source/WTF/wtf/gobject/GRefPtr.h delete mode 100644 Source/WTF/wtf/gobject/GTypedefs.h delete mode 100644 Source/WTF/wtf/gobject/GUniquePtr.h delete mode 100644 Source/WTF/wtf/gobject/GlibUtilities.cpp delete mode 100644 Source/WTF/wtf/gobject/GlibUtilities.h delete mode 100644 Source/WTF/wtf/gtk/MainThreadGtk.cpp delete mode 100644 Source/WTF/wtf/gtk/RunLoopGtk.cpp create mode 100644 Source/WTF/wtf/mbmalloc.cpp create mode 100644 Source/WTF/wtf/persistence/Coder.h create mode 100644 Source/WTF/wtf/persistence/Coders.cpp create mode 100644 Source/WTF/wtf/persistence/Coders.h create mode 100644 Source/WTF/wtf/persistence/Decoder.cpp create mode 100644 Source/WTF/wtf/persistence/Decoder.h create mode 100644 Source/WTF/wtf/persistence/Encoder.cpp create mode 100644 Source/WTF/wtf/persistence/Encoder.h create mode 100644 Source/WTF/wtf/spi/darwin/CommonCryptoSPI.h create mode 100644 Source/WTF/wtf/spi/darwin/SandboxSPI.h create mode 100644 Source/WTF/wtf/spi/darwin/XPCSPI.h create mode 100644 Source/WTF/wtf/spi/darwin/dyldSPI.h create mode 100644 Source/WTF/wtf/text/AtomicStringImpl.cpp create mode 100644 Source/WTF/wtf/text/LineBreakIteratorPoolICU.h create mode 100644 Source/WTF/wtf/text/OrdinalNumber.h create mode 100644 Source/WTF/wtf/text/StringCommon.h create mode 100644 Source/WTF/wtf/text/StringConcatenateNumbers.h create mode 100644 Source/WTF/wtf/text/StringView.cpp create mode 100644 Source/WTF/wtf/text/SymbolImpl.cpp create mode 100644 Source/WTF/wtf/text/SymbolImpl.h create mode 100644 Source/WTF/wtf/text/SymbolRegistry.cpp create mode 100644 Source/WTF/wtf/text/SymbolRegistry.h create mode 100644 Source/WTF/wtf/text/TextBreakIterator.cpp create mode 100644 Source/WTF/wtf/text/TextBreakIterator.h create mode 100644 Source/WTF/wtf/text/TextBreakIteratorInternalICU.h create mode 100644 Source/WTF/wtf/text/UniquedStringImpl.h create mode 100644 Source/WTF/wtf/text/icu/UTextProvider.cpp create mode 100644 Source/WTF/wtf/text/icu/UTextProvider.h create mode 100644 Source/WTF/wtf/text/icu/UTextProviderLatin1.cpp create mode 100644 Source/WTF/wtf/text/icu/UTextProviderLatin1.h create mode 100644 Source/WTF/wtf/text/icu/UTextProviderUTF16.cpp create mode 100644 Source/WTF/wtf/text/icu/UTextProviderUTF16.h create mode 100644 Source/WTF/wtf/text/unix/TextBreakIteratorInternalICUUnix.cpp delete mode 100644 Source/WTF/wtf/unicode/ScriptCodesFromICU.h delete mode 100644 Source/WTF/wtf/unicode/Unicode.h delete mode 100644 Source/WTF/wtf/unicode/UnicodeMacrosFromICU.h delete mode 100644 Source/WTF/wtf/unicode/icu/UnicodeIcu.h delete mode 100644 Source/WTF/wtf/win/GDIObject.h (limited to 'Source/WTF/wtf') diff --git a/Source/WTF/wtf/ASCIICType.h b/Source/WTF/wtf/ASCIICType.h index 18e108e1b..f5540b834 100644 --- a/Source/WTF/wtf/ASCIICType.h +++ b/Source/WTF/wtf/ASCIICType.h @@ -1,5 +1,5 @@ /* - * Copyright (C) 2007, 2008, 2009, 2011 Apple Inc. All rights reserved. + * Copyright (C) 2007-2016 Apple Inc. All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions @@ -10,7 +10,7 @@ * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. - * 3. Neither the name of Apple Computer, Inc. ("Apple") nor the names of + * 3. Neither the name of Apple Inc. ("Apple") nor the names of * its contributors may be used to endorse or promote products derived * from this software without specific prior written permission. * @@ -30,6 +30,7 @@ #define WTF_ASCIICType_h #include +#include // The behavior of many of the functions in the header is dependent // on the current locale. But in the WebKit project, all uses of those functions @@ -43,126 +44,216 @@ namespace WTF { -template inline bool isASCII(CharType c) +template bool isASCII(CharacterType); +template bool isASCIIAlpha(CharacterType); +template bool isASCIIAlphanumeric(CharacterType); +template bool isASCIIBinaryDigit(CharacterType); +template bool isASCIIDigit(CharacterType); +template bool isASCIIHexDigit(CharacterType); +template bool isASCIILower(CharacterType); +template bool isASCIIOctalDigit(CharacterType); +template bool isASCIIPrintable(CharacterType); +template bool isASCIISpace(CharacterType); +template bool isASCIIUpper(CharacterType); + +template CharacterType toASCIILower(CharacterType); +template CharacterType toASCIIUpper(CharacterType); + +template uint8_t toASCIIHexValue(CharacterType); +template uint8_t toASCIIHexValue(CharacterType firstCharacter, CharacterType secondCharacter); + +char lowerNibbleToASCIIHexDigit(uint8_t); +char upperNibbleToASCIIHexDigit(uint8_t); +char lowerNibbleToLowercaseASCIIHexDigit(uint8_t); +char upperNibbleToLowercaseASCIIHexDigit(uint8_t); + +template bool isASCIIAlphaCaselessEqual(CharacterType, char expectedASCIILowercaseLetter); + +// The toASCIILowerUnchecked function can be used for comparing any input character +// to a lowercase English character. The isASCIIAlphaCaselessEqual function should +// be used for regular comparison of ASCII alpha characters, but switch statements +// in the CSS tokenizer, for example, instead make direct use toASCIILowerUnchecked. +template CharacterType toASCIILowerUnchecked(CharacterType); + +const unsigned char asciiCaseFoldTable[256] = { + 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, + 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f, + 0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 0x28, 0x29, 0x2a, 0x2b, 0x2c, 0x2d, 0x2e, 0x2f, + 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f, + 0x40, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67, 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f, + 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, 0x78, 0x79, 0x7a, 0x5b, 0x5c, 0x5d, 0x5e, 0x5f, + 0x60, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67, 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f, + 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, 0x78, 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f, + 0x80, 0x81, 0x82, 0x83, 0x84, 0x85, 0x86, 0x87, 0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e, 0x8f, + 0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97, 0x98, 0x99, 0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f, + 0xa0, 0xa1, 0xa2, 0xa3, 0xa4, 0xa5, 0xa6, 0xa7, 0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf, + 0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7, 0xb8, 0xb9, 0xba, 0xbb, 0xbc, 0xbd, 0xbe, 0xbf, + 0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 0xc6, 0xc7, 0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf, + 0xd0, 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7, 0xd8, 0xd9, 0xda, 0xdb, 0xdc, 0xdd, 0xde, 0xdf, + 0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 0xe7, 0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef, + 0xf0, 0xf1, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7, 0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 0xfd, 0xfe, 0xff +}; + +template inline bool isASCII(CharacterType character) +{ + return !(character & ~0x7F); +} + +template inline bool isASCIILower(CharacterType character) { - return !(c & ~0x7F); + return character >= 'a' && character <= 'z'; } -template inline bool isASCIIAlpha(CharType c) +template inline CharacterType toASCIILowerUnchecked(CharacterType character) { - return (c | 0x20) >= 'a' && (c | 0x20) <= 'z'; + // This function can be used for comparing any input character + // to a lowercase English character. The isASCIIAlphaCaselessEqual + // below should be used for regular comparison of ASCII alpha + // characters, but switch statements in CSS tokenizer instead make + // direct use of this function. + return character | 0x20; } -template inline bool isASCIIDigit(CharType c) +template inline bool isASCIIAlpha(CharacterType character) { - return c >= '0' && c <= '9'; + return isASCIILower(toASCIILowerUnchecked(character)); } -template inline bool isASCIIAlphanumeric(CharType c) +template inline bool isASCIIDigit(CharacterType character) { - return isASCIIDigit(c) || isASCIIAlpha(c); + return character >= '0' && character <= '9'; } -template inline bool isASCIIHexDigit(CharType c) +template inline bool isASCIIAlphanumeric(CharacterType character) { - return isASCIIDigit(c) || ((c | 0x20) >= 'a' && (c | 0x20) <= 'f'); + return isASCIIDigit(character) || isASCIIAlpha(character); } -template inline bool isASCIILower(CharType c) +template inline bool isASCIIHexDigit(CharacterType character) { - return c >= 'a' && c <= 'z'; + return isASCIIDigit(character) || (toASCIILowerUnchecked(character) >= 'a' && toASCIILowerUnchecked(character) <= 'f'); } -template inline bool isASCIIOctalDigit(CharType c) +template inline bool isASCIIBinaryDigit(CharacterType character) { - return (c >= '0') & (c <= '7'); + return character == '0' || character == '1'; } -template inline bool isASCIIPrintable(CharType c) +template inline bool isASCIIOctalDigit(CharacterType character) { - return c >= ' ' && c <= '~'; + return character >= '0' && character <= '7'; +} + +template inline bool isASCIIPrintable(CharacterType character) +{ + return character >= ' ' && character <= '~'; } /* - Statistics from a run of Apple's page load test for callers of isASCIISpace: - - character count - --------- ----- - non-spaces 689383 - 20 space 294720 - 0A \n 89059 - 09 \t 28320 - 0D \r 0 - 0C \f 0 - 0B \v 0 - */ -template inline bool isASCIISpace(CharType c) + Statistics from a run of Apple's page load test for callers of isASCIISpace: + + character count + --------- ----- + non-spaces 689383 + 20 space 294720 + 0A \n 89059 + 09 \t 28320 + 0D \r 0 + 0C \f 0 + 0B \v 0 + + Because of those, we first check to quickly return false for non-control characters, + then check for space itself to quickly return true for that case, then do the rest. +*/ +template inline bool isASCIISpace(CharacterType character) { - return c <= ' ' && (c == ' ' || (c <= 0xD && c >= 0x9)); + return character <= ' ' && (character == ' ' || (character <= 0xD && character >= 0x9)); } -template inline bool isASCIIUpper(CharType c) +template inline bool isASCIIUpper(CharacterType character) { - return c >= 'A' && c <= 'Z'; + return character >= 'A' && character <= 'Z'; } -template inline CharType toASCIILower(CharType c) +template inline CharacterType toASCIILower(CharacterType character) { - return c | ((c >= 'A' && c <= 'Z') << 5); + return character | (isASCIIUpper(character) << 5); } -template inline CharType toASCIILowerUnchecked(CharType character) +template<> inline char toASCIILower(char character) { - // This function can be used for comparing any input character - // to a lowercase English character. The isASCIIAlphaCaselessEqual - // below should be used for regular comparison of ASCII alpha - // characters, but switch statements in CSS tokenizer require - // direct use of this function. - return character | 0x20; + return static_cast(asciiCaseFoldTable[static_cast(character)]); } -template inline CharType toASCIIUpper(CharType c) +template<> inline LChar toASCIILower(LChar character) { - return c & ~((c >= 'a' && c <= 'z') << 5); + return asciiCaseFoldTable[character]; } -template inline int toASCIIHexValue(CharType c) +template inline CharacterType toASCIIUpper(CharacterType character) { - ASSERT(isASCIIHexDigit(c)); - return c < 'A' ? c - '0' : (c - 'A' + 10) & 0xF; + return character & ~(isASCIILower(character) << 5); } -template inline int toASCIIHexValue(CharType upperValue, CharType lowerValue) +template inline uint8_t toASCIIHexValue(CharacterType character) { - ASSERT(isASCIIHexDigit(upperValue) && isASCIIHexDigit(lowerValue)); - return ((toASCIIHexValue(upperValue) << 4) & 0xF0) | toASCIIHexValue(lowerValue); + ASSERT(isASCIIHexDigit(character)); + return character < 'A' ? character - '0' : (character - 'A' + 10) & 0xF; } -inline char lowerNibbleToASCIIHexDigit(char c) +template inline uint8_t toASCIIHexValue(CharacterType firstCharacter, CharacterType secondCharacter) { - char nibble = c & 0xF; - return nibble < 10 ? '0' + nibble : 'A' + nibble - 10; + return toASCIIHexValue(firstCharacter) << 4 | toASCIIHexValue(secondCharacter); } -inline char upperNibbleToASCIIHexDigit(char c) +inline char lowerNibbleToASCIIHexDigit(uint8_t value) { - char nibble = (c >> 4) & 0xF; - return nibble < 10 ? '0' + nibble : 'A' + nibble - 10; + uint8_t nibble = value & 0xF; + return nibble + (nibble < 10 ? '0' : 'A' - 10); } -template inline bool isASCIIAlphaCaselessEqual(CharType cssCharacter, char character) +inline char upperNibbleToASCIIHexDigit(uint8_t value) { - // This function compares a (preferrably) constant ASCII - // lowercase letter to any input character. - ASSERT(character >= 'a' && character <= 'z'); - return LIKELY(toASCIILowerUnchecked(cssCharacter) == character); + uint8_t nibble = value >> 4; + return nibble + (nibble < 10 ? '0' : 'A' - 10); +} + +inline char lowerNibbleToLowercaseASCIIHexDigit(uint8_t value) +{ + uint8_t nibble = value & 0xF; + return nibble + (nibble < 10 ? '0' : 'a' - 10); +} + +inline char upperNibbleToLowercaseASCIIHexDigit(uint8_t value) +{ + uint8_t nibble = value >> 4; + return nibble + (nibble < 10 ? '0' : 'a' - 10); +} + +template inline bool isASCIIAlphaCaselessEqual(CharacterType inputCharacter, char expectedASCIILowercaseLetter) +{ + // Name of this argument says this must be a lowercase letter, but it can actually be: + // - a lowercase letter + // - a numeric digit + // - a space + // - punctuation in the range 0x21-0x3F, including "-", "/", and "+" + // It cannot be: + // - an uppercase letter + // - a non-ASCII character + // - other punctuation, such as underscore and backslash + // - a control character such as "\n" + // FIXME: Would be nice to make both the function name and expectedASCIILowercaseLetter argument name clearer. + ASSERT(toASCIILowerUnchecked(expectedASCIILowercaseLetter) == expectedASCIILowercaseLetter); + return LIKELY(toASCIILowerUnchecked(inputCharacter) == expectedASCIILowercaseLetter); } } using WTF::isASCII; using WTF::isASCIIAlpha; +using WTF::isASCIIAlphaCaselessEqual; using WTF::isASCIIAlphanumeric; +using WTF::isASCIIBinaryDigit; using WTF::isASCIIDigit; using WTF::isASCIIHexDigit; using WTF::isASCIILower; @@ -170,12 +261,13 @@ using WTF::isASCIIOctalDigit; using WTF::isASCIIPrintable; using WTF::isASCIISpace; using WTF::isASCIIUpper; +using WTF::lowerNibbleToASCIIHexDigit; +using WTF::lowerNibbleToLowercaseASCIIHexDigit; using WTF::toASCIIHexValue; using WTF::toASCIILower; using WTF::toASCIILowerUnchecked; using WTF::toASCIIUpper; -using WTF::lowerNibbleToASCIIHexDigit; using WTF::upperNibbleToASCIIHexDigit; -using WTF::isASCIIAlphaCaselessEqual; +using WTF::upperNibbleToLowercaseASCIIHexDigit; #endif diff --git a/Source/WTF/wtf/AVLTree.h b/Source/WTF/wtf/AVLTree.h deleted file mode 100644 index 61d76fb98..000000000 --- a/Source/WTF/wtf/AVLTree.h +++ /dev/null @@ -1,960 +0,0 @@ -/* - * Copyright (C) 2008 Apple Inc. All rights reserved. - * - * Based on Abstract AVL Tree Template v1.5 by Walt Karas - * . - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * - * 1. Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * 2. Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * 3. Neither the name of Apple Computer, Inc. ("Apple") nor the names of - * its contributors may be used to endorse or promote products derived - * from this software without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY - * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED - * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE - * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY - * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES - * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; - * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND - * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT - * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF - * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - */ - -#ifndef AVL_TREE_H_ -#define AVL_TREE_H_ - -#include -#include - -namespace WTF { - -// Here is the reference class for BSet. -// -// class BSet -// { -// public: -// -// class ANY_bitref -// { -// public: -// operator bool (); -// void operator = (bool b); -// }; -// -// // Does not have to initialize bits. -// BSet(); -// -// // Must return a valid value for index when 0 <= index < maxDepth -// ANY_bitref operator [] (unsigned index); -// -// // Set all bits to 1. -// void set(); -// -// // Set all bits to 0. -// void reset(); -// }; - -template -class AVLTreeDefaultBSet { -public: - bool& operator[](unsigned i) { ASSERT_WITH_SECURITY_IMPLICATION(i < maxDepth); return m_data[i]; } - void set() { for (unsigned i = 0; i < maxDepth; ++i) m_data[i] = true; } - void reset() { for (unsigned i = 0; i < maxDepth; ++i) m_data[i] = false; } - -private: - std::array m_data; -}; - -// How to determine maxDepth: -// d Minimum number of nodes -// 2 2 -// 3 4 -// 4 7 -// 5 12 -// 6 20 -// 7 33 -// 8 54 -// 9 88 -// 10 143 -// 11 232 -// 12 376 -// 13 609 -// 14 986 -// 15 1,596 -// 16 2,583 -// 17 4,180 -// 18 6,764 -// 19 10,945 -// 20 17,710 -// 21 28,656 -// 22 46,367 -// 23 75,024 -// 24 121,392 -// 25 196,417 -// 26 317,810 -// 27 514,228 -// 28 832,039 -// 29 1,346,268 -// 30 2,178,308 -// 31 3,524,577 -// 32 5,702,886 -// 33 9,227,464 -// 34 14,930,351 -// 35 24,157,816 -// 36 39,088,168 -// 37 63,245,985 -// 38 102,334,154 -// 39 165,580,140 -// 40 267,914,295 -// 41 433,494,436 -// 42 701,408,732 -// 43 1,134,903,169 -// 44 1,836,311,902 -// 45 2,971,215,072 -// -// E.g., if, in a particular instantiation, the maximum number of nodes in a tree instance is 1,000,000, the maximum depth should be 28. -// You pick 28 because MN(28) is 832,039, which is less than or equal to 1,000,000, and MN(29) is 1,346,268, which is strictly greater than 1,000,000. - -template > -class AVLTree { -public: - - typedef typename Abstractor::key key; - typedef typename Abstractor::handle handle; - typedef typename Abstractor::size size; - - enum SearchType { - EQUAL = 1, - LESS = 2, - GREATER = 4, - LESS_EQUAL = EQUAL | LESS, - GREATER_EQUAL = EQUAL | GREATER - }; - - - Abstractor& abstractor() { return abs; } - - inline handle insert(handle h); - - inline handle search(key k, SearchType st = EQUAL); - inline handle search_least(); - inline handle search_greatest(); - - inline handle remove(key k); - - inline handle subst(handle new_node); - - void purge() { abs.root = null(); } - - bool is_empty() { return abs.root == null(); } - - AVLTree() { abs.root = null(); } - - class Iterator { - public: - - // Initialize depth to invalid value, to indicate iterator is - // invalid. (Depth is zero-base.) - Iterator() { depth = ~0U; } - - void start_iter(AVLTree &tree, key k, SearchType st = EQUAL) - { - // Mask of high bit in an int. - const int MASK_HIGH_BIT = (int) ~ ((~ (unsigned) 0) >> 1); - - // Save the tree that we're going to iterate through in a - // member variable. - tree_ = &tree; - - int cmp, target_cmp; - handle h = tree_->abs.root; - unsigned d = 0; - - depth = ~0U; - - if (h == null()) - // Tree is empty. - return; - - if (st & LESS) - // Key can be greater than key of starting node. - target_cmp = 1; - else if (st & GREATER) - // Key can be less than key of starting node. - target_cmp = -1; - else - // Key must be same as key of starting node. - target_cmp = 0; - - for (;;) { - cmp = cmp_k_n(k, h); - if (cmp == 0) { - if (st & EQUAL) { - // Equal node was sought and found as starting node. - depth = d; - break; - } - cmp = -target_cmp; - } else if (target_cmp != 0) { - if (!((cmp ^ target_cmp) & MASK_HIGH_BIT)) { - // cmp and target_cmp are both negative or both positive. - depth = d; - } - } - h = cmp < 0 ? get_lt(h) : get_gt(h); - if (h == null()) - break; - branch[d] = cmp > 0; - path_h[d++] = h; - } - } - - void start_iter_least(AVLTree &tree) - { - tree_ = &tree; - - handle h = tree_->abs.root; - - depth = ~0U; - - branch.reset(); - - while (h != null()) { - if (depth != ~0U) - path_h[depth] = h; - depth++; - h = get_lt(h); - } - } - - void start_iter_greatest(AVLTree &tree) - { - tree_ = &tree; - - handle h = tree_->abs.root; - - depth = ~0U; - - branch.set(); - - while (h != null()) { - if (depth != ~0U) - path_h[depth] = h; - depth++; - h = get_gt(h); - } - } - - handle operator*() - { - if (depth == ~0U) - return null(); - - return depth == 0 ? tree_->abs.root : path_h[depth - 1]; - } - - void operator++() - { - if (depth != ~0U) { - handle h = get_gt(**this); - if (h == null()) { - do { - if (depth == 0) { - depth = ~0U; - break; - } - depth--; - } while (branch[depth]); - } else { - branch[depth] = true; - path_h[depth++] = h; - for (;;) { - h = get_lt(h); - if (h == null()) - break; - branch[depth] = false; - path_h[depth++] = h; - } - } - } - } - - void operator--() - { - if (depth != ~0U) { - handle h = get_lt(**this); - if (h == null()) - do { - if (depth == 0) { - depth = ~0U; - break; - } - depth--; - } while (!branch[depth]); - else { - branch[depth] = false; - path_h[depth++] = h; - for (;;) { - h = get_gt(h); - if (h == null()) - break; - branch[depth] = true; - path_h[depth++] = h; - } - } - } - } - - void operator++(int) { ++(*this); } - void operator--(int) { --(*this); } - - protected: - - // Tree being iterated over. - AVLTree *tree_; - - // Records a path into the tree. If branch[n] is true, indicates - // take greater branch from the nth node in the path, otherwise - // take the less branch. branch[0] gives branch from root, and - // so on. - BSet branch; - - // Zero-based depth of path into tree. - unsigned depth; - - // Handles of nodes in path from root to current node (returned by *). - handle path_h[maxDepth - 1]; - - int cmp_k_n(key k, handle h) { return tree_->abs.compare_key_node(k, h); } - int cmp_n_n(handle h1, handle h2) { return tree_->abs.compare_node_node(h1, h2); } - handle get_lt(handle h) { return tree_->abs.get_less(h); } - handle get_gt(handle h) { return tree_->abs.get_greater(h); } - handle null() { return tree_->abs.null(); } - }; - - template - bool build(fwd_iter p, size num_nodes) - { - if (num_nodes == 0) { - abs.root = null(); - return true; - } - - // Gives path to subtree being built. If branch[N] is false, branch - // less from the node at depth N, if true branch greater. - BSet branch; - - // If rem[N] is true, then for the current subtree at depth N, it's - // greater subtree has one more node than it's less subtree. - BSet rem; - - // Depth of root node of current subtree. - unsigned depth = 0; - - // Number of nodes in current subtree. - size num_sub = num_nodes; - - // The algorithm relies on a stack of nodes whose less subtree has - // been built, but whose right subtree has not yet been built. The - // stack is implemented as linked list. The nodes are linked - // together by having the "greater" handle of a node set to the - // next node in the list. "less_parent" is the handle of the first - // node in the list. - handle less_parent = null(); - - // h is root of current subtree, child is one of its children. - handle h, child; - - for (;;) { - while (num_sub > 2) { - // Subtract one for root of subtree. - num_sub--; - rem[depth] = !!(num_sub & 1); - branch[depth++] = false; - num_sub >>= 1; - } - - if (num_sub == 2) { - // Build a subtree with two nodes, slanting to greater. - // I arbitrarily chose to always have the extra node in the - // greater subtree when there is an odd number of nodes to - // split between the two subtrees. - - h = *p; - p++; - child = *p; - p++; - set_lt(child, null()); - set_gt(child, null()); - set_bf(child, 0); - set_gt(h, child); - set_lt(h, null()); - set_bf(h, 1); - } else { // num_sub == 1 - // Build a subtree with one node. - - h = *p; - p++; - set_lt(h, null()); - set_gt(h, null()); - set_bf(h, 0); - } - - while (depth) { - depth--; - if (!branch[depth]) - // We've completed a less subtree. - break; - - // We've completed a greater subtree, so attach it to - // its parent (that is less than it). We pop the parent - // off the stack of less parents. - child = h; - h = less_parent; - less_parent = get_gt(h); - set_gt(h, child); - // num_sub = 2 * (num_sub - rem[depth]) + rem[depth] + 1 - num_sub <<= 1; - num_sub += 1 - rem[depth]; - if (num_sub & (num_sub - 1)) - // num_sub is not a power of 2 - set_bf(h, 0); - else - // num_sub is a power of 2 - set_bf(h, 1); - } - - if (num_sub == num_nodes) - // We've completed the full tree. - break; - - // The subtree we've completed is the less subtree of the - // next node in the sequence. - - child = h; - h = *p; - p++; - set_lt(h, child); - - // Put h into stack of less parents. - set_gt(h, less_parent); - less_parent = h; - - // Proceed to creating greater than subtree of h. - branch[depth] = true; - num_sub += rem[depth++]; - - } // end for (;;) - - abs.root = h; - - return true; - } - -protected: - - friend class Iterator; - - // Create a class whose sole purpose is to take advantage of - // the "empty member" optimization. - struct abs_plus_root : public Abstractor { - // The handle of the root element in the AVL tree. - handle root; - }; - - abs_plus_root abs; - - - handle get_lt(handle h) { return abs.get_less(h); } - void set_lt(handle h, handle lh) { abs.set_less(h, lh); } - - handle get_gt(handle h) { return abs.get_greater(h); } - void set_gt(handle h, handle gh) { abs.set_greater(h, gh); } - - int get_bf(handle h) { return abs.get_balance_factor(h); } - void set_bf(handle h, int bf) { abs.set_balance_factor(h, bf); } - - int cmp_k_n(key k, handle h) { return abs.compare_key_node(k, h); } - int cmp_n_n(handle h1, handle h2) { return abs.compare_node_node(h1, h2); } - - handle null() { return abs.null(); } - -private: - - // Balances subtree, returns handle of root node of subtree - // after balancing. - handle balance(handle bal_h) - { - handle deep_h; - - // Either the "greater than" or the "less than" subtree of - // this node has to be 2 levels deeper (or else it wouldn't - // need balancing). - - if (get_bf(bal_h) > 0) { - // "Greater than" subtree is deeper. - - deep_h = get_gt(bal_h); - - if (get_bf(deep_h) < 0) { - handle old_h = bal_h; - bal_h = get_lt(deep_h); - - set_gt(old_h, get_lt(bal_h)); - set_lt(deep_h, get_gt(bal_h)); - set_lt(bal_h, old_h); - set_gt(bal_h, deep_h); - - int bf = get_bf(bal_h); - if (bf != 0) { - if (bf > 0) { - set_bf(old_h, -1); - set_bf(deep_h, 0); - } else { - set_bf(deep_h, 1); - set_bf(old_h, 0); - } - set_bf(bal_h, 0); - } else { - set_bf(old_h, 0); - set_bf(deep_h, 0); - } - } else { - set_gt(bal_h, get_lt(deep_h)); - set_lt(deep_h, bal_h); - if (get_bf(deep_h) == 0) { - set_bf(deep_h, -1); - set_bf(bal_h, 1); - } else { - set_bf(deep_h, 0); - set_bf(bal_h, 0); - } - bal_h = deep_h; - } - } else { - // "Less than" subtree is deeper. - - deep_h = get_lt(bal_h); - - if (get_bf(deep_h) > 0) { - handle old_h = bal_h; - bal_h = get_gt(deep_h); - set_lt(old_h, get_gt(bal_h)); - set_gt(deep_h, get_lt(bal_h)); - set_gt(bal_h, old_h); - set_lt(bal_h, deep_h); - - int bf = get_bf(bal_h); - if (bf != 0) { - if (bf < 0) { - set_bf(old_h, 1); - set_bf(deep_h, 0); - } else { - set_bf(deep_h, -1); - set_bf(old_h, 0); - } - set_bf(bal_h, 0); - } else { - set_bf(old_h, 0); - set_bf(deep_h, 0); - } - } else { - set_lt(bal_h, get_gt(deep_h)); - set_gt(deep_h, bal_h); - if (get_bf(deep_h) == 0) { - set_bf(deep_h, 1); - set_bf(bal_h, -1); - } else { - set_bf(deep_h, 0); - set_bf(bal_h, 0); - } - bal_h = deep_h; - } - } - - return bal_h; - } - -}; - -template -inline typename AVLTree::handle -AVLTree::insert(handle h) -{ - set_lt(h, null()); - set_gt(h, null()); - set_bf(h, 0); - - if (abs.root == null()) - abs.root = h; - else { - // Last unbalanced node encountered in search for insertion point. - handle unbal = null(); - // Parent of last unbalanced node. - handle parent_unbal = null(); - // Balance factor of last unbalanced node. - int unbal_bf; - - // Zero-based depth in tree. - unsigned depth = 0, unbal_depth = 0; - - // Records a path into the tree. If branch[n] is true, indicates - // take greater branch from the nth node in the path, otherwise - // take the less branch. branch[0] gives branch from root, and - // so on. - BSet branch; - - handle hh = abs.root; - handle parent = null(); - int cmp; - - do { - if (get_bf(hh) != 0) { - unbal = hh; - parent_unbal = parent; - unbal_depth = depth; - } - cmp = cmp_n_n(h, hh); - if (cmp == 0) - // Duplicate key. - return hh; - parent = hh; - hh = cmp < 0 ? get_lt(hh) : get_gt(hh); - branch[depth++] = cmp > 0; - } while (hh != null()); - - // Add node to insert as leaf of tree. - if (cmp < 0) - set_lt(parent, h); - else - set_gt(parent, h); - - depth = unbal_depth; - - if (unbal == null()) - hh = abs.root; - else { - cmp = branch[depth++] ? 1 : -1; - unbal_bf = get_bf(unbal); - if (cmp < 0) - unbal_bf--; - else // cmp > 0 - unbal_bf++; - hh = cmp < 0 ? get_lt(unbal) : get_gt(unbal); - if ((unbal_bf != -2) && (unbal_bf != 2)) { - // No rebalancing of tree is necessary. - set_bf(unbal, unbal_bf); - unbal = null(); - } - } - - if (hh != null()) - while (h != hh) { - cmp = branch[depth++] ? 1 : -1; - if (cmp < 0) { - set_bf(hh, -1); - hh = get_lt(hh); - } else { // cmp > 0 - set_bf(hh, 1); - hh = get_gt(hh); - } - } - - if (unbal != null()) { - unbal = balance(unbal); - if (parent_unbal == null()) - abs.root = unbal; - else { - depth = unbal_depth - 1; - cmp = branch[depth] ? 1 : -1; - if (cmp < 0) - set_lt(parent_unbal, unbal); - else // cmp > 0 - set_gt(parent_unbal, unbal); - } - } - } - - return h; -} - -template -inline typename AVLTree::handle -AVLTree::search(key k, typename AVLTree::SearchType st) -{ - const int MASK_HIGH_BIT = (int) ~ ((~ (unsigned) 0) >> 1); - - int cmp, target_cmp; - handle match_h = null(); - handle h = abs.root; - - if (st & LESS) - target_cmp = 1; - else if (st & GREATER) - target_cmp = -1; - else - target_cmp = 0; - - while (h != null()) { - cmp = cmp_k_n(k, h); - if (cmp == 0) { - if (st & EQUAL) { - match_h = h; - break; - } - cmp = -target_cmp; - } else if (target_cmp != 0) - if (!((cmp ^ target_cmp) & MASK_HIGH_BIT)) - // cmp and target_cmp are both positive or both negative. - match_h = h; - h = cmp < 0 ? get_lt(h) : get_gt(h); - } - - return match_h; -} - -template -inline typename AVLTree::handle -AVLTree::search_least() -{ - handle h = abs.root, parent = null(); - - while (h != null()) { - parent = h; - h = get_lt(h); - } - - return parent; -} - -template -inline typename AVLTree::handle -AVLTree::search_greatest() -{ - handle h = abs.root, parent = null(); - - while (h != null()) { - parent = h; - h = get_gt(h); - } - - return parent; -} - -template -inline typename AVLTree::handle -AVLTree::remove(key k) -{ - // Zero-based depth in tree. - unsigned depth = 0, rm_depth; - - // Records a path into the tree. If branch[n] is true, indicates - // take greater branch from the nth node in the path, otherwise - // take the less branch. branch[0] gives branch from root, and - // so on. - BSet branch; - - handle h = abs.root; - handle parent = null(), child; - int cmp, cmp_shortened_sub_with_path = 0; - - for (;;) { - if (h == null()) - // No node in tree with given key. - return null(); - cmp = cmp_k_n(k, h); - if (cmp == 0) - // Found node to remove. - break; - parent = h; - h = cmp < 0 ? get_lt(h) : get_gt(h); - branch[depth++] = cmp > 0; - cmp_shortened_sub_with_path = cmp; - } - handle rm = h; - handle parent_rm = parent; - rm_depth = depth; - - // If the node to remove is not a leaf node, we need to get a - // leaf node, or a node with a single leaf as its child, to put - // in the place of the node to remove. We will get the greatest - // node in the less subtree (of the node to remove), or the least - // node in the greater subtree. We take the leaf node from the - // deeper subtree, if there is one. - - if (get_bf(h) < 0) { - child = get_lt(h); - branch[depth] = false; - cmp = -1; - } else { - child = get_gt(h); - branch[depth] = true; - cmp = 1; - } - depth++; - - if (child != null()) { - cmp = -cmp; - do { - parent = h; - h = child; - if (cmp < 0) { - child = get_lt(h); - branch[depth] = false; - } else { - child = get_gt(h); - branch[depth] = true; - } - depth++; - } while (child != null()); - - if (parent == rm) - // Only went through do loop once. Deleted node will be replaced - // in the tree structure by one of its immediate children. - cmp_shortened_sub_with_path = -cmp; - else - cmp_shortened_sub_with_path = cmp; - - // Get the handle of the opposite child, which may not be null. - child = cmp > 0 ? get_lt(h) : get_gt(h); - } - - if (parent == null()) - // There were only 1 or 2 nodes in this tree. - abs.root = child; - else if (cmp_shortened_sub_with_path < 0) - set_lt(parent, child); - else - set_gt(parent, child); - - // "path" is the parent of the subtree being eliminated or reduced - // from a depth of 2 to 1. If "path" is the node to be removed, we - // set path to the node we're about to poke into the position of the - // node to be removed. - handle path = parent == rm ? h : parent; - - if (h != rm) { - // Poke in the replacement for the node to be removed. - set_lt(h, get_lt(rm)); - set_gt(h, get_gt(rm)); - set_bf(h, get_bf(rm)); - if (parent_rm == null()) - abs.root = h; - else { - depth = rm_depth - 1; - if (branch[depth]) - set_gt(parent_rm, h); - else - set_lt(parent_rm, h); - } - } - - if (path != null()) { - // Create a temporary linked list from the parent of the path node - // to the root node. - h = abs.root; - parent = null(); - depth = 0; - while (h != path) { - if (branch[depth++]) { - child = get_gt(h); - set_gt(h, parent); - } else { - child = get_lt(h); - set_lt(h, parent); - } - parent = h; - h = child; - } - - // Climb from the path node to the root node using the linked - // list, restoring the tree structure and rebalancing as necessary. - bool reduced_depth = true; - int bf; - cmp = cmp_shortened_sub_with_path; - for (;;) { - if (reduced_depth) { - bf = get_bf(h); - if (cmp < 0) - bf++; - else // cmp > 0 - bf--; - if ((bf == -2) || (bf == 2)) { - h = balance(h); - bf = get_bf(h); - } else - set_bf(h, bf); - reduced_depth = (bf == 0); - } - if (parent == null()) - break; - child = h; - h = parent; - cmp = branch[--depth] ? 1 : -1; - if (cmp < 0) { - parent = get_lt(h); - set_lt(h, child); - } else { - parent = get_gt(h); - set_gt(h, child); - } - } - abs.root = h; - } - - return rm; -} - -template -inline typename AVLTree::handle -AVLTree::subst(handle new_node) -{ - handle h = abs.root; - handle parent = null(); - int cmp, last_cmp; - - /* Search for node already in tree with same key. */ - for (;;) { - if (h == null()) - /* No node in tree with same key as new node. */ - return null(); - cmp = cmp_n_n(new_node, h); - if (cmp == 0) - /* Found the node to substitute new one for. */ - break; - last_cmp = cmp; - parent = h; - h = cmp < 0 ? get_lt(h) : get_gt(h); - } - - /* Copy tree housekeeping fields from node in tree to new node. */ - set_lt(new_node, get_lt(h)); - set_gt(new_node, get_gt(h)); - set_bf(new_node, get_bf(h)); - - if (parent == null()) - /* New node is also new root. */ - abs.root = new_node; - else { - /* Make parent point to new node. */ - if (last_cmp < 0) - set_lt(parent, new_node); - else - set_gt(parent, new_node); - } - - return h; -} - -} - -#endif diff --git a/Source/WTF/wtf/Assertions.cpp b/Source/WTF/wtf/Assertions.cpp index a37030245..8613df5de 100644 --- a/Source/WTF/wtf/Assertions.cpp +++ b/Source/WTF/wtf/Assertions.cpp @@ -12,10 +12,10 @@ * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * - * THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``AS IS'' AND ANY + * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR - * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE COMPUTER, INC. OR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR @@ -35,27 +35,31 @@ #include "Assertions.h" #include "Compiler.h" +#include +#include +#include +#include +#include +#include #include #include #include +#include #include -#include -#include - #if HAVE(SIGNAL_H) #include #endif #if USE(CF) #include -#if PLATFORM(IOS) || __MAC_OS_X_VERSION_MIN_REQUIRED >= 1080 -#define WTF_USE_APPLE_SYSTEM_LOG 1 +#if PLATFORM(COCOA) +#define USE_APPLE_SYSTEM_LOG 1 #include #endif #endif // USE(CF) -#if COMPILER(MSVC) && !OS(WINCE) +#if COMPILER(MSVC) #include #endif @@ -63,7 +67,12 @@ #include #endif -#if OS(DARWIN) || (OS(LINUX) && !defined(__UCLIBC__)) +#if OS(DARWIN) +#include +#include +#endif + +#if OS(DARWIN) || (OS(LINUX) && defined(__GLIBC__) && !defined(__UCLIBC__)) #include #include #include @@ -71,6 +80,17 @@ extern "C" { +static void logToStderr(const char* buffer) +{ +#if USE(APPLE_SYSTEM_LOG) +#pragma clang diagnostic push +#pragma clang diagnostic ignored "-Wdeprecated-declarations" + asl_log(0, 0, ASL_LEVEL_NOTICE, "%s", buffer); +#pragma clang diagnostic pop +#endif + fputs(buffer, stderr); +} + WTF_ATTRIBUTE_PRINTF(1, 0) static void vprintf_stderr_common(const char* format, va_list args) { @@ -91,10 +111,7 @@ static void vprintf_stderr_common(const char* format, va_list args) CFStringGetCString(str, buffer, length, kCFStringEncodingUTF8); -#if USE(APPLE_SYSTEM_LOG) - asl_log(0, 0, ASL_LEVEL_NOTICE, "%s", buffer); -#endif - fputs(buffer, stderr); + logToStderr(buffer); free(buffer); CFRelease(str); @@ -103,10 +120,13 @@ static void vprintf_stderr_common(const char* format, va_list args) } #if USE(APPLE_SYSTEM_LOG) +#pragma clang diagnostic push +#pragma clang diagnostic ignored "-Wdeprecated-declarations" va_list copyOfArgs; va_copy(copyOfArgs, args); asl_vlog(0, 0, ASL_LEVEL_NOTICE, format, copyOfArgs); va_end(copyOfArgs); +#pragma clang diagnostic pop #endif // Fall through to write to stderr in the same manner as other platforms. @@ -121,21 +141,8 @@ static void vprintf_stderr_common(const char* format, va_list args) if (buffer == NULL) break; - if (_vsnprintf(buffer, size, format, args) != -1) { -#if OS(WINCE) - // WinCE only supports wide chars - wchar_t* wideBuffer = (wchar_t*)malloc(size * sizeof(wchar_t)); - if (wideBuffer == NULL) - break; - for (unsigned int i = 0; i < size; ++i) { - if (!(wideBuffer[i] = buffer[i])) - break; - } - OutputDebugStringW(wideBuffer); - free(wideBuffer); -#else + if (vsnprintf(buffer, size, format, args) != -1) { OutputDebugStringA(buffer); -#endif free(buffer); break; } @@ -148,7 +155,7 @@ static void vprintf_stderr_common(const char* format, va_list args) vfprintf(stderr, format, args); } -#if COMPILER(CLANG) || (COMPILER(GCC) && GCC_VERSION_AT_LEAST(4, 6, 0)) +#if COMPILER(GCC_OR_CLANG) #pragma GCC diagnostic push #pragma GCC diagnostic ignored "-Wformat-nonliteral" #endif @@ -181,7 +188,7 @@ static void vprintf_stderr_with_trailing_newline(const char* format, va_list arg vprintf_stderr_common(formatWithNewline.get(), args); } -#if COMPILER(CLANG) || (COMPILER(GCC) && GCC_VERSION_AT_LEAST(4, 6, 0)) +#if COMPILER(GCC_OR_CLANG) #pragma GCC diagnostic pop #endif @@ -196,7 +203,7 @@ static void printf_stderr_common(const char* format, ...) static void printCallSite(const char* file, int line, const char* function) { -#if OS(WINDOWS) && !OS(WINCE) && defined(_DEBUG) +#if OS(WINDOWS) && defined(_DEBUG) _CrtDbgReport(_CRT_WARN, file, line, NULL, "%s\n", function); #else // By using this format, which matches the format used by MSVC for compiler errors, developers @@ -233,24 +240,10 @@ void WTFReportArgumentAssertionFailure(const char* file, int line, const char* f void WTFGetBacktrace(void** stack, int* size) { -#if OS(DARWIN) || (OS(LINUX) && !defined(__UCLIBC__)) +#if OS(DARWIN) || (OS(LINUX) && defined(__GLIBC__) && !defined(__UCLIBC__)) *size = backtrace(stack, *size); -#elif OS(WINDOWS) && !OS(WINCE) - // The CaptureStackBackTrace function is available in XP, but it is not defined - // in the Windows Server 2003 R2 Platform SDK. So, we'll grab the function - // through GetProcAddress. - typedef WORD (NTAPI* RtlCaptureStackBackTraceFunc)(DWORD, DWORD, PVOID*, PDWORD); - HMODULE kernel32 = ::GetModuleHandleW(L"Kernel32.dll"); - if (!kernel32) { - *size = 0; - return; - } - RtlCaptureStackBackTraceFunc captureStackBackTraceFunc = reinterpret_cast( - ::GetProcAddress(kernel32, "RtlCaptureStackBackTrace")); - if (captureStackBackTraceFunc) - *size = captureStackBackTraceFunc(0, *size, stack, 0); - else - *size = 0; +#elif OS(WINDOWS) + *size = RtlCaptureStackBackTrace(0, *size, stack, 0); #else *size = 0; #endif @@ -270,10 +263,10 @@ void WTFReportBacktrace() #if OS(DARWIN) || OS(LINUX) # if PLATFORM(GTK) # if defined(__GLIBC__) && !defined(__UCLIBC__) -# define WTF_USE_BACKTRACE_SYMBOLS 1 +# define USE_BACKTRACE_SYMBOLS 1 # endif # else -# define WTF_USE_DLADDR 1 +# define USE_DLADDR 1 # endif #endif @@ -310,8 +303,8 @@ void WTFPrintBacktrace(void** stack, int size) #endif } -#undef WTF_USE_BACKTRACE_SYMBOLS -#undef WTF_USE_DLADDR +#undef USE_BACKTRACE_SYMBOLS +#undef USE_DLADDR static WTFCrashHookFunction globalHook = 0; @@ -320,10 +313,7 @@ void WTFSetCrashHook(WTFCrashHookFunction function) globalHook = function; } -void WTFInvokeCrashHook() -{ -} - +#if !defined(NDEBUG) || !OS(DARWIN) void WTFCrash() { if (globalHook) @@ -332,25 +322,25 @@ void WTFCrash() WTFReportBacktrace(); *(int *)(uintptr_t)0xbbadbeef = 0; // More reliable, but doesn't say BBADBEEF. -#if COMPILER(CLANG) +#if COMPILER(GCC_OR_CLANG) __builtin_trap(); #else ((void(*)())0)(); #endif } - +#else +// We need to keep WTFCrash() around (even on non-debug OS(DARWIN) builds) as a workaround +// for presently shipping (circa early 2016) SafariForWebKitDevelopment binaries which still +// expects to link to it. +void WTFCrash() +{ + CRASH(); +} +#endif // !defined(NDEBUG) || !OS(DARWIN) + void WTFCrashWithSecurityImplication() { - if (globalHook) - globalHook(); - WTFReportBacktrace(); - *(int *)(uintptr_t)0xfbadbeef = 0; - // More reliable, but doesn't say fbadbeef. -#if COMPILER(CLANG) - __builtin_trap(); -#else - ((void(*)())0)(); -#endif + CRASH(); } #if HAVE(SIGNAL_H) @@ -389,6 +379,20 @@ void WTFInstallReportBacktraceOnCrashHook() #endif } +bool WTFIsDebuggerAttached() +{ +#if OS(DARWIN) + struct kinfo_proc info; + int mib[] = { CTL_KERN, KERN_PROC, KERN_PROC_PID, getpid() }; + size_t size = sizeof(info); + if (sysctl(mib, sizeof(mib) / sizeof(mib[0]), &info, &size, nullptr, 0) == -1) + return false; + return info.kp_proc.p_flag & P_TRACED; +#else + return false; +#endif +} + void WTFReportFatalError(const char* file, int line, const char* function, const char* format, ...) { va_list args; @@ -409,15 +413,83 @@ void WTFReportError(const char* file, int line, const char* function, const char printCallSite(file, line, function); } +class WTFLoggingAccumulator { +public: + void accumulate(const String&); + void resetAccumulatedLogs(); + String getAndResetAccumulatedLogs(); + +private: + Lock accumulatorLock; + StringBuilder loggingAccumulator; +}; + +void WTFLoggingAccumulator::accumulate(const String& log) +{ + Locker locker(accumulatorLock); + loggingAccumulator.append(log); +} + +void WTFLoggingAccumulator::resetAccumulatedLogs() +{ + Locker locker(accumulatorLock); + loggingAccumulator.clear(); +} + +String WTFLoggingAccumulator::getAndResetAccumulatedLogs() +{ + Locker locker(accumulatorLock); + String result = loggingAccumulator.toString(); + loggingAccumulator.clear(); + return result; +} + +static WTFLoggingAccumulator& loggingAccumulator() +{ + static WTFLoggingAccumulator* accumulator; + static std::once_flag initializeAccumulatorOnce; + std::call_once(initializeAccumulatorOnce, [] { + accumulator = new WTFLoggingAccumulator; + }); + + return *accumulator; +} + void WTFLog(WTFLogChannel* channel, const char* format, ...) { - if (channel->state != WTFLogChannelOn) + if (channel->state == WTFLogChannelOff) return; + if (channel->state == WTFLogChannelOn) { + va_list args; + va_start(args, format); + vprintf_stderr_with_trailing_newline(format, args); + va_end(args); + return; + } + + ASSERT(channel->state == WTFLogChannelOnWithAccumulation); + va_list args; va_start(args, format); - vprintf_stderr_with_trailing_newline(format, args); + +#if COMPILER(CLANG) +#pragma clang diagnostic push +#pragma clang diagnostic ignored "-Wformat-nonliteral" +#endif + String loggingString = String::format(format, args); +#if COMPILER(CLANG) +#pragma clang diagnostic pop +#endif + va_end(args); + + if (!loggingString.endsWith('\n')) + loggingString.append('\n'); + + loggingAccumulator().accumulate(loggingString); + + logToStderr(loggingString.utf8().data()); } void WTFLogVerbose(const char* file, int line, const char* function, WTFLogChannel* channel, const char* format, ...) @@ -427,7 +499,16 @@ void WTFLogVerbose(const char* file, int line, const char* function, WTFLogChann va_list args; va_start(args, format); - vprintf_stderr_with_trailing_newline(format, args); + +#if COMPILER(CLANG) +#pragma clang diagnostic push +#pragma clang diagnostic ignored "-Wformat-nonliteral" +#endif + WTFLog(channel, format, args); +#if COMPILER(CLANG) +#pragma clang diagnostic pop +#endif + va_end(args); printCallSite(file, line, function); @@ -452,7 +533,7 @@ void WTFLogAlwaysAndCrash(const char* format, ...) va_start(args, format); WTFLogAlwaysV(format, args); va_end(args); - WTFCrash(); + CRASH(); } WTFLogChannel* WTFLogChannelByName(WTFLogChannel* channels[], size_t count, const char* name) @@ -474,6 +555,13 @@ static void setStateOfAllChannels(WTFLogChannel* channels[], size_t channelCount void WTFInitializeLogChannelStatesFromString(WTFLogChannel* channels[], size_t count, const char* logLevel) { +#if !RELEASE_LOG_DISABLED + for (size_t i = 0; i < count; ++i) { + WTFLogChannel* channel = channels[i]; + channel->osLogChannel = os_log_create(channel->subsystem, channel->name); + } +#endif + String logLevelString = logLevel; Vector components; logLevelString.split(',', components); @@ -487,7 +575,7 @@ void WTFInitializeLogChannelStatesFromString(WTFLogChannel* channels[], size_t c component = component.substring(1); } - if (equalIgnoringCase(component, "all")) { + if (equalLettersIgnoringASCIICase(component, "all")) { setStateOfAllChannels(channels, count, logChannelState); continue; } @@ -500,3 +588,17 @@ void WTFInitializeLogChannelStatesFromString(WTFLogChannel* channels[], size_t c } } // extern "C" + +namespace WTF { + +void resetAccumulatedLogs() +{ + loggingAccumulator().resetAccumulatedLogs(); +} + +String getAndResetAccumulatedLogs() +{ + return loggingAccumulator().getAndResetAccumulatedLogs(); +} + +} // namespace WTF diff --git a/Source/WTF/wtf/Assertions.h b/Source/WTF/wtf/Assertions.h index 4d968b865..3158c1039 100644 --- a/Source/WTF/wtf/Assertions.h +++ b/Source/WTF/wtf/Assertions.h @@ -10,10 +10,10 @@ * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * - * THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``AS IS'' AND ANY + * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR - * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE COMPUTER, INC. OR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR @@ -26,20 +26,30 @@ #ifndef WTF_Assertions_h #define WTF_Assertions_h +#include + /* no namespaces because this file has to be includable from C and Objective-C Note, this file uses many GCC extensions, but it should be compatible with C, Objective C, C++, and Objective C++. - For non-debug builds, everything is disabled by default. - Defining any of the symbols explicitly prevents this from having any effect. + For non-debug builds, everything is disabled by default except for "always + on" logging. Defining any of the symbols explicitly prevents this from + having any effect. */ +#undef __STDC_FORMAT_MACROS +#define __STDC_FORMAT_MACROS #include #include +#include #include -#include +#include + +#if USE(OS_LOG) +#include +#endif #ifdef NDEBUG /* Disable ASSERT* macros in release mode. */ @@ -76,16 +86,23 @@ #define LOG_DISABLED ASSERTIONS_DISABLED_DEFAULT #endif -#if COMPILER(GCC) +#ifndef RELEASE_LOG_DISABLED +#define RELEASE_LOG_DISABLED !(USE(OS_LOG)) +#endif + +#if COMPILER(GCC_OR_CLANG) #define WTF_PRETTY_FUNCTION __PRETTY_FUNCTION__ #else #define WTF_PRETTY_FUNCTION __FUNCTION__ #endif +#if COMPILER(MINGW) +/* By default MinGW emits warnings when C99 format attributes are used, even if __USE_MINGW_ANSI_STDIO is defined */ +#define WTF_ATTRIBUTE_PRINTF(formatStringArgument, extraArguments) __attribute__((__format__(gnu_printf, formatStringArgument, extraArguments))) +#elif COMPILER(GCC_OR_CLANG) && !defined(__OBJC__) /* WTF logging functions can process %@ in the format string to log a NSObject* but the printf format attribute emits a warning when %@ is used in the format string. Until is resolved we can't include the attribute when being used from Objective-C code in case it decides to use %@. */ -#if COMPILER(GCC) && !defined(__OBJC__) #define WTF_ATTRIBUTE_PRINTF(formatStringArgument, extraArguments) __attribute__((__format__(printf, formatStringArgument, extraArguments))) #else #define WTF_ATTRIBUTE_PRINTF(formatStringArgument, extraArguments) @@ -112,19 +129,43 @@ extern "C" { Signals are ignored by the crash reporter on OS X so we must do better. */ -#if COMPILER(CLANG) +#if COMPILER(GCC_OR_CLANG) || COMPILER(MSVC) #define NO_RETURN_DUE_TO_CRASH NO_RETURN #else #define NO_RETURN_DUE_TO_CRASH #endif -typedef enum { WTFLogChannelOff, WTFLogChannelOn } WTFLogChannelState; +typedef enum { WTFLogChannelOff, WTFLogChannelOn, WTFLogChannelOnWithAccumulation } WTFLogChannelState; typedef struct { WTFLogChannelState state; const char* name; +#if !RELEASE_LOG_DISABLED + const char* subsystem; + __unsafe_unretained os_log_t osLogChannel; +#endif } WTFLogChannel; +#define LOG_CHANNEL(name) JOIN_LOG_CHANNEL_WITH_PREFIX(LOG_CHANNEL_PREFIX, name) +#define LOG_CHANNEL_ADDRESS(name) &LOG_CHANNEL(name), +#define JOIN_LOG_CHANNEL_WITH_PREFIX(prefix, channel) JOIN_LOG_CHANNEL_WITH_PREFIX_LEVEL_2(prefix, channel) +#define JOIN_LOG_CHANNEL_WITH_PREFIX_LEVEL_2(prefix, channel) prefix ## channel + +#define LOG_CHANNEL_WEBKIT_SUBSYSTEM "com.apple.WebKit" + +#define DECLARE_LOG_CHANNEL(name) \ + extern WTFLogChannel LOG_CHANNEL(name); + +#if !defined(DEFINE_LOG_CHANNEL) +#if RELEASE_LOG_DISABLED +#define DEFINE_LOG_CHANNEL(name, subsystem) \ + WTFLogChannel LOG_CHANNEL(name) = { WTFLogChannelOff, #name }; +#else +#define DEFINE_LOG_CHANNEL(name, subsystem) \ + WTFLogChannel LOG_CHANNEL(name) = { WTFLogChannelOff, #name, subsystem, OS_LOG_DEFAULT }; +#endif +#endif + WTF_EXPORT_PRIVATE void WTFReportAssertionFailure(const char* file, int line, const char* function, const char* assertion); WTF_EXPORT_PRIVATE void WTFReportAssertionFailureWithMessage(const char* file, int line, const char* function, const char* assertion, const char* format, ...) WTF_ATTRIBUTE_PRINTF(5, 6); WTF_EXPORT_PRIVATE void WTFReportArgumentAssertionFailure(const char* file, int line, const char* function, const char* argName, const char* assertion); @@ -134,7 +175,7 @@ WTF_EXPORT_PRIVATE void WTFLog(WTFLogChannel*, const char* format, ...) WTF_ATTR WTF_EXPORT_PRIVATE void WTFLogVerbose(const char* file, int line, const char* function, WTFLogChannel*, const char* format, ...) WTF_ATTRIBUTE_PRINTF(5, 6); WTF_EXPORT_PRIVATE void WTFLogAlwaysV(const char* format, va_list); WTF_EXPORT_PRIVATE void WTFLogAlways(const char* format, ...) WTF_ATTRIBUTE_PRINTF(1, 2); -WTF_EXPORT_PRIVATE void WTFLogAlwaysAndCrash(const char* format, ...) WTF_ATTRIBUTE_PRINTF(1, 2) NO_RETURN_DUE_TO_CRASH; +WTF_EXPORT_PRIVATE NO_RETURN_DUE_TO_CRASH void WTFLogAlwaysAndCrash(const char* format, ...) WTF_ATTRIBUTE_PRINTF(1, 2); WTF_EXPORT_PRIVATE WTFLogChannel* WTFLogChannelByName(WTFLogChannel*[], size_t count, const char*); WTF_EXPORT_PRIVATE void WTFInitializeLogChannelStatesFromString(WTFLogChannel*[], size_t count, const char*); @@ -146,32 +187,42 @@ typedef void (*WTFCrashHookFunction)(); WTF_EXPORT_PRIVATE void WTFSetCrashHook(WTFCrashHookFunction); WTF_EXPORT_PRIVATE void WTFInstallReportBacktraceOnCrashHook(); -// Exist for binary compatibility with older Safari. Do not use. -WTF_EXPORT_PRIVATE void WTFInvokeCrashHook(); -#ifdef __cplusplus -} -#endif +WTF_EXPORT_PRIVATE bool WTFIsDebuggerAttached(); #ifndef CRASH -#define CRASH() WTFCrash() -#endif -#ifdef __cplusplus -extern "C" { +#if defined(NDEBUG) && OS(DARWIN) +#if CPU(X86_64) || CPU(X86) +#define WTFBreakpointTrap() __asm__ volatile ("int3") +#elif CPU(ARM_THUMB2) +#define WTFBreakpointTrap() __asm__ volatile ("bkpt #0") +#elif CPU(ARM64) +#define WTFBreakpointTrap() __asm__ volatile ("brk #0") +#else +#error "Unsupported CPU". #endif -WTF_EXPORT_PRIVATE void WTFCrash() NO_RETURN_DUE_TO_CRASH; -#ifdef __cplusplus -} + +// Crash with a SIGTRAP i.e EXC_BREAKPOINT. +// We are not using __builtin_trap because it is only guaranteed to abort, but not necessarily +// trigger a SIGTRAP. Instead, we use inline asm to ensure that we trigger the SIGTRAP. +#define CRASH() do { \ + WTFBreakpointTrap(); \ + __builtin_unreachable(); \ +} while (0) +#else +#define CRASH() WTFCrash() #endif +#endif // CRASH + +WTF_EXPORT_PRIVATE NO_RETURN_DUE_TO_CRASH void WTFCrash(); + #ifndef CRASH_WITH_SECURITY_IMPLICATION #define CRASH_WITH_SECURITY_IMPLICATION() WTFCrashWithSecurityImplication() #endif -#ifdef __cplusplus -extern "C" { -#endif - WTF_EXPORT_PRIVATE void WTFCrashWithSecurityImplication() NO_RETURN_DUE_TO_CRASH; +WTF_EXPORT_PRIVATE NO_RETURN_DUE_TO_CRASH void WTFCrashWithSecurityImplication(); + #ifdef __cplusplus } #endif @@ -199,14 +250,6 @@ extern "C" { Expressions inside them are evaluated in debug builds only. */ -#if OS(WINCE) -/* FIXME: We include this here only to avoid a conflict with the ASSERT macro. */ -#include -#undef min -#undef max -#undef ERROR -#endif - #if OS(WINDOWS) /* FIXME: Change to use something other than ASSERT to avoid this conflict with the underlying platform */ #undef ASSERT @@ -217,11 +260,12 @@ extern "C" { #define ASSERT(assertion) ((void)0) #define ASSERT_AT(assertion, file, line, function) ((void)0) #define ASSERT_NOT_REACHED() ((void)0) +#define ASSERT_IMPLIES(condition, assertion) ((void)0) #define NO_RETURN_DUE_TO_ASSERT #define ASSERT_UNUSED(variable, assertion) ((void)variable) -#ifdef ADDRESS_SANITIZER +#if ENABLE(SECURITY_ASSERTIONS) #define ASSERT_WITH_SECURITY_IMPLICATION(assertion) \ (!(assertion) ? \ (WTFReportAssertionFailure(__FILE__, __LINE__, WTF_PRETTY_FUNCTION, #assertion), \ @@ -236,23 +280,32 @@ extern "C" { #else -#define ASSERT(assertion) \ - (!(assertion) ? \ - (WTFReportAssertionFailure(__FILE__, __LINE__, WTF_PRETTY_FUNCTION, #assertion), \ - CRASH()) : \ - (void)0) +#define ASSERT(assertion) do { \ + if (!(assertion)) { \ + WTFReportAssertionFailure(__FILE__, __LINE__, WTF_PRETTY_FUNCTION, #assertion); \ + CRASH(); \ + } \ +} while (0) -#define ASSERT_AT(assertion, file, line, function) \ - (!(assertion) ? \ - (WTFReportAssertionFailure(file, line, function, #assertion), \ - CRASH()) : \ - (void)0) +#define ASSERT_AT(assertion, file, line, function) do { \ + if (!(assertion)) { \ + WTFReportAssertionFailure(file, line, function, #assertion); \ + CRASH(); \ + } \ +} while (0) #define ASSERT_NOT_REACHED() do { \ WTFReportAssertionFailure(__FILE__, __LINE__, WTF_PRETTY_FUNCTION, 0); \ CRASH(); \ } while (0) +#define ASSERT_IMPLIES(condition, assertion) do { \ + if ((condition) && !(assertion)) { \ + WTFReportAssertionFailure(__FILE__, __LINE__, WTF_PRETTY_FUNCTION, #condition " => " #assertion); \ + CRASH(); \ + } \ +} while (0) + #define ASSERT_UNUSED(variable, assertion) ASSERT(assertion) #define NO_RETURN_DUE_TO_ASSERT NO_RETURN_DUE_TO_CRASH @@ -278,12 +331,12 @@ extern "C" { #if ASSERT_MSG_DISABLED #define ASSERT_WITH_MESSAGE(assertion, ...) ((void)0) #else -#define ASSERT_WITH_MESSAGE(assertion, ...) do \ +#define ASSERT_WITH_MESSAGE(assertion, ...) do { \ if (!(assertion)) { \ WTFReportAssertionFailureWithMessage(__FILE__, __LINE__, WTF_PRETTY_FUNCTION, #assertion, __VA_ARGS__); \ CRASH(); \ } \ -while (0) +} while (0) #endif /* ASSERT_WITH_MESSAGE_UNUSED */ @@ -291,12 +344,12 @@ while (0) #if ASSERT_MSG_DISABLED #define ASSERT_WITH_MESSAGE_UNUSED(variable, assertion, ...) ((void)variable) #else -#define ASSERT_WITH_MESSAGE_UNUSED(variable, assertion, ...) do \ +#define ASSERT_WITH_MESSAGE_UNUSED(variable, assertion, ...) do { \ if (!(assertion)) { \ WTFReportAssertionFailureWithMessage(__FILE__, __LINE__, WTF_PRETTY_FUNCTION, #assertion, __VA_ARGS__); \ CRASH(); \ } \ -while (0) +} while (0) #endif @@ -308,12 +361,12 @@ while (0) #else -#define ASSERT_ARG(argName, assertion) do \ +#define ASSERT_ARG(argName, assertion) do { \ if (!(assertion)) { \ WTFReportArgumentAssertionFailure(__FILE__, __LINE__, WTF_PRETTY_FUNCTION, #argName, #assertion); \ CRASH(); \ } \ -while (0) +} while (0) #endif @@ -351,9 +404,7 @@ while (0) #if LOG_DISABLED #define LOG(channel, ...) ((void)0) #else -#define LOG(channel, ...) WTFLog(&JOIN_LOG_CHANNEL_WITH_PREFIX(LOG_CHANNEL_PREFIX, channel), __VA_ARGS__) -#define JOIN_LOG_CHANNEL_WITH_PREFIX(prefix, channel) JOIN_LOG_CHANNEL_WITH_PREFIX_LEVEL_2(prefix, channel) -#define JOIN_LOG_CHANNEL_WITH_PREFIX_LEVEL_2(prefix, channel) prefix ## channel +#define LOG(channel, ...) WTFLog(&LOG_CHANNEL(channel), __VA_ARGS__) #endif /* LOG_VERBOSE */ @@ -361,7 +412,39 @@ while (0) #if LOG_DISABLED #define LOG_VERBOSE(channel, ...) ((void)0) #else -#define LOG_VERBOSE(channel, ...) WTFLogVerbose(__FILE__, __LINE__, WTF_PRETTY_FUNCTION, &JOIN_LOG_CHANNEL_WITH_PREFIX(LOG_CHANNEL_PREFIX, channel), __VA_ARGS__) +#define LOG_VERBOSE(channel, ...) WTFLogVerbose(__FILE__, __LINE__, WTF_PRETTY_FUNCTION, &LOG_CHANNEL(channel), __VA_ARGS__) +#endif + +/* RELEASE_LOG */ + +#if RELEASE_LOG_DISABLED +#define RELEASE_LOG( channel, format, ...) ((void)0) +#define RELEASE_LOG_ERROR(channel, format, ...) LOG_ERROR(format, ##__VA_ARGS__) + +#define RELEASE_LOG_IF( isAllowed, channel, format, ...) ((void)0) +#define RELEASE_LOG_ERROR_IF(isAllowed, channel, format, ...) do { if (isAllowed) RELEASE_LOG_ERROR(channel, format, ##__VA_ARGS__); } while (0) +#else +#define RELEASE_LOG( channel, format, ...) os_log( LOG_CHANNEL(channel).osLogChannel, format, ##__VA_ARGS__) +#define RELEASE_LOG_ERROR(channel, format, ...) os_log_error(LOG_CHANNEL(channel).osLogChannel, format, ##__VA_ARGS__) + +#define RELEASE_LOG_IF( isAllowed, channel, format, ...) do { if (isAllowed) RELEASE_LOG( channel, format, ##__VA_ARGS__); } while (0) +#define RELEASE_LOG_ERROR_IF(isAllowed, channel, format, ...) do { if (isAllowed) RELEASE_LOG_ERROR(channel, format, ##__VA_ARGS__); } while (0) +#endif + + +/* RELEASE_ASSERT */ + +#if ASSERT_DISABLED +#define RELEASE_ASSERT(assertion) do { \ + if (UNLIKELY(!(assertion))) \ + CRASH(); \ +} while (0) +#define RELEASE_ASSERT_WITH_MESSAGE(assertion, ...) RELEASE_ASSERT(assertion) +#define RELEASE_ASSERT_NOT_REACHED() CRASH() +#else +#define RELEASE_ASSERT(assertion) ASSERT(assertion) +#define RELEASE_ASSERT_WITH_MESSAGE(assertion, ...) ASSERT_WITH_MESSAGE(assertion, __VA_ARGS__) +#define RELEASE_ASSERT_NOT_REACHED() ASSERT_NOT_REACHED() #endif /* UNREACHABLE_FOR_PLATFORM */ @@ -373,47 +456,12 @@ while (0) #pragma clang diagnostic ignored "-Wmissing-noreturn" static inline void UNREACHABLE_FOR_PLATFORM() { - ASSERT_NOT_REACHED(); + RELEASE_ASSERT_NOT_REACHED(); } #pragma clang diagnostic pop #else -#define UNREACHABLE_FOR_PLATFORM() ASSERT_NOT_REACHED() -#endif - -#if ASSERT_DISABLED -#define RELEASE_ASSERT(assertion) (UNLIKELY(!(assertion)) ? (CRASH()) : (void)0) -#define RELEASE_ASSERT_WITH_MESSAGE(assertion, ...) RELEASE_ASSERT(assertion) -#define RELEASE_ASSERT_NOT_REACHED() CRASH() -#else -#define RELEASE_ASSERT(assertion) ASSERT(assertion) -#define RELEASE_ASSERT_WITH_MESSAGE(assertion, ...) ASSERT_WITH_MESSAGE(assertion, __VA_ARGS__) -#define RELEASE_ASSERT_NOT_REACHED() ASSERT_NOT_REACHED() +#define UNREACHABLE_FOR_PLATFORM() RELEASE_ASSERT_NOT_REACHED() #endif -/* TYPE CAST */ - -#define TYPE_CASTS_BASE(ToClassName, argumentType, argumentName, pointerPredicate, referencePredicate) \ -inline ToClassName* to##ToClassName(argumentType* argumentName) \ -{ \ - ASSERT_WITH_SECURITY_IMPLICATION(!argumentName || (pointerPredicate)); \ - return static_cast(argumentName); \ -} \ -inline const ToClassName* to##ToClassName(const argumentType* argumentName) \ -{ \ - ASSERT_WITH_SECURITY_IMPLICATION(!argumentName || (pointerPredicate)); \ - return static_cast(argumentName); \ -} \ -inline ToClassName& to##ToClassName(argumentType& argumentName) \ -{ \ - ASSERT_WITH_SECURITY_IMPLICATION(referencePredicate); \ - return static_cast(argumentName); \ -} \ -inline const ToClassName& to##ToClassName(const argumentType& argumentName) \ -{ \ - ASSERT_WITH_SECURITY_IMPLICATION(referencePredicate); \ - return static_cast(argumentName); \ -} \ -void to##ToClassName(const ToClassName*); \ -void to##ToClassName(const ToClassName&); #endif /* WTF_Assertions_h */ diff --git a/Source/WTF/wtf/Atomics.cpp b/Source/WTF/wtf/Atomics.cpp index 01a4650c4..9f3dcf7c5 100644 --- a/Source/WTF/wtf/Atomics.cpp +++ b/Source/WTF/wtf/Atomics.cpp @@ -1,59 +1,26 @@ /* - * Copyright (C) 2007, 2008, 2010, 2012 Apple Inc. All rights reserved. + * Copyright (C) 2007, 2008, 2010, 2012, 2015 Apple Inc. All rights reserved. * Copyright (C) 2007 Justin Haygood (jhaygood@reaktix.com) * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: - * * 1. Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. + * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * 3. Neither the name of Apple Computer, Inc. ("Apple") nor the names of - * its contributors may be used to endorse or promote products derived - * from this software without specific prior written permission. + * documentation and/or other materials provided with the distribution. * - * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY + * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS'' AND ANY * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE - * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY + * DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS BE LIABLE FOR ANY * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; - * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND - * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT - * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF - * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - * - * - * Note: The implementations of InterlockedIncrement and InterlockedDecrement are based - * on atomic_increment and atomic_exchange_and_add from the Boost C++ Library. The license - * is virtually identical to the Apple license above but is included here for completeness. - * - * Boost Software License - Version 1.0 - August 17th, 2003 - * - * Permission is hereby granted, free of charge, to any person or organization - * obtaining a copy of the software and accompanying documentation covered by - * this license (the "Software") to use, reproduce, display, distribute, - * execute, and transmit the Software, and to prepare derivative works of the - * Software, and to permit third-parties to whom the Software is furnished to - * do so, all subject to the following: - * - * The copyright notices in the Software and this entire statement, including - * the above license grant, this restriction and the following disclaimer, - * must be included in all copies of the Software, in whole or in part, and - * all derivative works of the Software, unless such copies or derivative - * works are solely in the form of machine-executable object code generated by - * a source language processor. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR - * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT - * SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE - * FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE, - * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER - * DEALINGS IN THE SOFTWARE. + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON + * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #include "config.h" @@ -65,7 +32,7 @@ // (http://gcc.gnu.org/bugzilla/show_bug.cgi?id=56296). GCC >= 4.8 will support __atomic_* builtin // functions for this purpose for all the GCC targets, but for current compilers we have to include // our own implementation. -#if COMPILER(GCC) && !defined(__GCC_HAVE_SYNC_COMPARE_AND_SWAP_8) && USE(PTHREADS) +#if COMPILER(GCC_OR_CLANG) && !defined(__GCC_HAVE_SYNC_COMPARE_AND_SWAP_8) && USE(PTHREADS) #include "ThreadingPrimitives.h" diff --git a/Source/WTF/wtf/Atomics.h b/Source/WTF/wtf/Atomics.h index 83eb0d6f4..4a8ee48e7 100644 --- a/Source/WTF/wtf/Atomics.h +++ b/Source/WTF/wtf/Atomics.h @@ -1,221 +1,209 @@ /* - * Copyright (C) 2007, 2008, 2010, 2012, 2013 Apple Inc. All rights reserved. + * Copyright (C) 2007-2008, 2010, 2012-2016 Apple Inc. All rights reserved. * Copyright (C) 2007 Justin Haygood (jhaygood@reaktix.com) * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: - * * 1. Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. + * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * 3. Neither the name of Apple Computer, Inc. ("Apple") nor the names of - * its contributors may be used to endorse or promote products derived - * from this software without specific prior written permission. + * documentation and/or other materials provided with the distribution. * - * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY + * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS'' AND ANY * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE - * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY + * DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS BE LIABLE FOR ANY * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; - * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND - * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT - * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF - * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - * - * - * Note: The implementations of InterlockedIncrement and InterlockedDecrement are based - * on atomic_increment and atomic_exchange_and_add from the Boost C++ Library. The license - * is virtually identical to the Apple license above but is included here for completeness. - * - * Boost Software License - Version 1.0 - August 17th, 2003 - * - * Permission is hereby granted, free of charge, to any person or organization - * obtaining a copy of the software and accompanying documentation covered by - * this license (the "Software") to use, reproduce, display, distribute, - * execute, and transmit the Software, and to prepare derivative works of the - * Software, and to permit third-parties to whom the Software is furnished to - * do so, all subject to the following: - * - * The copyright notices in the Software and this entire statement, including - * the above license grant, this restriction and the following disclaimer, - * must be included in all copies of the Software, in whole or in part, and - * all derivative works of the Software, unless such copies or derivative - * works are solely in the form of machine-executable object code generated by - * a source language processor. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR - * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT - * SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE - * FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE, - * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER - * DEALINGS IN THE SOFTWARE. + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON + * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #ifndef Atomics_h #define Atomics_h -#include +#include #include #if OS(WINDOWS) -#if !COMPILER(GCC) +#if !COMPILER(GCC_OR_CLANG) extern "C" void _ReadWriteBarrier(void); #pragma intrinsic(_ReadWriteBarrier) #endif #include +#include #endif namespace WTF { -#if OS(WINDOWS) && !COMPILER(GCC) -inline bool weakCompareAndSwap(volatile unsigned* location, unsigned expected, unsigned newValue) +// Atomic wraps around std::atomic with the sole purpose of making the compare_exchange +// operations not alter the expected value. This is more in line with how we typically +// use CAS in our code. +// +// Atomic is a struct without explicitly defined constructors so that it can be +// initialized at compile time. + +template +struct Atomic { + // Don't pass a non-default value for the order parameter unless you really know + // what you are doing and have thought about it very hard. The cost of seq_cst + // is usually not high enough to justify the risk. + + ALWAYS_INLINE T load(std::memory_order order = std::memory_order_seq_cst) const { return value.load(order); } + + ALWAYS_INLINE T loadRelaxed() const { return load(std::memory_order_relaxed); } + + ALWAYS_INLINE void store(T desired, std::memory_order order = std::memory_order_seq_cst) { value.store(desired, order); } + + ALWAYS_INLINE bool compareExchangeWeak(T expected, T desired, std::memory_order order = std::memory_order_seq_cst) + { + T expectedOrActual = expected; + return value.compare_exchange_weak(expectedOrActual, desired, order); + } + + ALWAYS_INLINE bool compareExchangeWeakRelaxed(T expected, T desired) + { + return compareExchangeWeak(expected, desired, std::memory_order_relaxed); + } + + ALWAYS_INLINE bool compareExchangeWeak(T expected, T desired, std::memory_order order_success, std::memory_order order_failure) + { + T expectedOrActual = expected; + return value.compare_exchange_weak(expectedOrActual, desired, order_success, order_failure); + } + + ALWAYS_INLINE T compareExchangeStrong(T expected, T desired, std::memory_order order = std::memory_order_seq_cst) + { + T expectedOrActual = expected; + value.compare_exchange_strong(expectedOrActual, desired, order); + return expectedOrActual; + } + + ALWAYS_INLINE T compareExchangeStrong(T expected, T desired, std::memory_order order_success, std::memory_order order_failure) + { + T expectedOrActual = expected; + value.compare_exchange_strong(expectedOrActual, desired, order_success, order_failure); + return expectedOrActual; + } + + template + ALWAYS_INLINE T exchangeAdd(U operand, std::memory_order order = std::memory_order_seq_cst) { return value.fetch_add(operand, order); } + + template + ALWAYS_INLINE T exchangeAnd(U operand, std::memory_order order = std::memory_order_seq_cst) { return value.fetch_and(operand, order); } + + template + ALWAYS_INLINE T exchangeOr(U operand, std::memory_order order = std::memory_order_seq_cst) { return value.fetch_or(operand, order); } + + template + ALWAYS_INLINE T exchangeSub(U operand, std::memory_order order = std::memory_order_seq_cst) { return value.fetch_sub(operand, order); } + + template + ALWAYS_INLINE T exchangeXor(U operand, std::memory_order order = std::memory_order_seq_cst) { return value.fetch_xor(operand, order); } + + ALWAYS_INLINE T exchange(T newValue, std::memory_order order = std::memory_order_seq_cst) { return value.exchange(newValue, order); } + + template + ALWAYS_INLINE bool tryTransactionRelaxed(const Func& func) + { + T oldValue = load(std::memory_order_relaxed); + T newValue = oldValue; + func(newValue); + return compareExchangeWeakRelaxed(oldValue, newValue); + } + + template + ALWAYS_INLINE void transactionRelaxed(const Func& func) + { + while (!tryTransationRelaxed(func)) { } + } + + template + ALWAYS_INLINE bool tryTransaction(const Func& func) + { + T oldValue = load(std::memory_order_relaxed); + T newValue = oldValue; + func(newValue); + return compareExchangeWeak(oldValue, newValue); + } + + template + ALWAYS_INLINE void transaction(const Func& func) + { + while (!tryTransaction(func)) { } + } + + std::atomic value; +}; + +template +inline T atomicLoad(T* location, std::memory_order order = std::memory_order_seq_cst) { -#if OS(WINCE) - return InterlockedCompareExchange(reinterpret_cast(const_cast(location)), static_cast(newValue), static_cast(expected)) == static_cast(expected); -#else - return InterlockedCompareExchange(reinterpret_cast(location), static_cast(newValue), static_cast(expected)) == static_cast(expected); -#endif + return bitwise_cast*>(location)->load(order); } -inline bool weakCompareAndSwap(void*volatile* location, void* expected, void* newValue) +template +inline void atomicStore(T* location, T newValue, std::memory_order order = std::memory_order_seq_cst) { - return InterlockedCompareExchangePointer(location, newValue, expected) == expected; + bitwise_cast*>(location)->store(newValue, order); } -#else // OS(WINDOWS) && !COMPILER(GCC) --> not windows, but maybe mingw -inline bool weakCompareAndSwap(volatile unsigned* location, unsigned expected, unsigned newValue) + +template +inline bool atomicCompareExchangeWeak(T* location, T expected, T newValue, std::memory_order order = std::memory_order_seq_cst) { -#if ENABLE(COMPARE_AND_SWAP) -#if CPU(X86) || CPU(X86_64) - unsigned char result; - asm volatile( - "lock; cmpxchgl %3, %2\n\t" - "sete %1" - : "+a"(expected), "=q"(result), "+m"(*location) - : "r"(newValue) - : "memory" - ); -#elif CPU(ARM_THUMB2) - unsigned tmp; - unsigned result; - asm volatile( - "movw %1, #1\n\t" - "ldrex %2, %0\n\t" - "cmp %3, %2\n\t" - "bne.n 0f\n\t" - "strex %1, %4, %0\n\t" - "0:" - : "+Q"(*location), "=&r"(result), "=&r"(tmp) - : "r"(expected), "r"(newValue) - : "memory"); - result = !result; -#elif CPU(ARM64) && COMPILER(GCC) - unsigned tmp; - unsigned result; - asm volatile( - "mov %w1, #1\n\t" - "ldxr %w2, [%0]\n\t" - "cmp %w3, %w2\n\t" - "b.ne 0f\n\t" - "stxr %w1, %w4, [%0]\n\t" - "0:" - : "+r"(location), "=&r"(result), "=&r"(tmp) - : "r"(expected), "r"(newValue) - : "memory"); - result = !result; -#elif CPU(ARM64) - unsigned tmp; - unsigned result; - asm volatile( - "mov %w1, #1\n\t" - "ldxr %w2, %0\n\t" - "cmp %w3, %w2\n\t" - "b.ne 0f\n\t" - "stxr %w1, %w4, %0\n\t" - "0:" - : "+m"(*location), "=&r"(result), "=&r"(tmp) - : "r"(expected), "r"(newValue) - : "memory"); - result = !result; -#else -#error "Bad architecture for compare and swap." -#endif - return result; -#else - UNUSED_PARAM(location); - UNUSED_PARAM(expected); - UNUSED_PARAM(newValue); - CRASH(); - return false; -#endif + return bitwise_cast*>(location)->compareExchangeWeak(expected, newValue, order); } -inline bool weakCompareAndSwap(void*volatile* location, void* expected, void* newValue) +template +inline bool atomicCompareExchangeWeakRelaxed(T* location, T expected, T newValue) { -#if ENABLE(COMPARE_AND_SWAP) -#if CPU(X86_64) - bool result; - asm volatile( - "lock; cmpxchgq %3, %2\n\t" - "sete %1" - : "+a"(expected), "=q"(result), "+m"(*location) - : "r"(newValue) - : "memory" - ); - return result; -#elif CPU(ARM64) && COMPILER(GCC) - bool result; - void* tmp; - asm volatile( - "mov %w1, #1\n\t" - "ldxr %x2, [%0]\n\t" - "cmp %x3, %x2\n\t" - "b.ne 0f\n\t" - "stxr %w1, %x4, [%0]\n\t" - "0:" - : "+r"(location), "=&r"(result), "=&r"(tmp) - : "r"(expected), "r"(newValue) - : "memory"); - return !result; -#elif CPU(ARM64) - bool result; - void* tmp; - asm volatile( - "mov %w1, #1\n\t" - "ldxr %x2, %0\n\t" - "cmp %x3, %x2\n\t" - "b.ne 0f\n\t" - "stxr %w1, %x4, %0\n\t" - "0:" - : "+m"(*location), "=&r"(result), "=&r"(tmp) - : "r"(expected), "r"(newValue) - : "memory"); - return !result; -#else - return weakCompareAndSwap(bitwise_cast(location), bitwise_cast(expected), bitwise_cast(newValue)); -#endif -#else // ENABLE(COMPARE_AND_SWAP) - UNUSED_PARAM(location); - UNUSED_PARAM(expected); - UNUSED_PARAM(newValue); - CRASH(); - return 0; -#endif // ENABLE(COMPARE_AND_SWAP) + return bitwise_cast*>(location)->compareExchangeWeakRelaxed(expected, newValue); } -#endif // OS(WINDOWS) && !COMPILER(GCC) (end of the not-windows (but maybe mingw) case) -inline bool weakCompareAndSwapUIntPtr(volatile uintptr_t* location, uintptr_t expected, uintptr_t newValue) +template +inline T atomicCompareExchangeStrong(T* location, T expected, T newValue, std::memory_order order = std::memory_order_seq_cst) { - return weakCompareAndSwap(reinterpret_cast(location), reinterpret_cast(expected), reinterpret_cast(newValue)); + return bitwise_cast*>(location)->compareExchangeStrong(expected, newValue, order); } -inline bool weakCompareAndSwapSize(volatile size_t* location, size_t expected, size_t newValue) +template +inline T atomicExchangeAdd(T* location, U operand, std::memory_order order = std::memory_order_seq_cst) { - return weakCompareAndSwap(reinterpret_cast(location), reinterpret_cast(expected), reinterpret_cast(newValue)); + return bitwise_cast*>(location)->exchangeAdd(operand, order); +} + +template +inline T atomicExchangeAnd(T* location, U operand, std::memory_order order = std::memory_order_seq_cst) +{ + return bitwise_cast*>(location)->exchangeAnd(operand, order); +} + +template +inline T atomicExchangeOr(T* location, U operand, std::memory_order order = std::memory_order_seq_cst) +{ + return bitwise_cast*>(location)->exchangeOr(operand, order); +} + +template +inline T atomicExchangeSub(T* location, U operand, std::memory_order order = std::memory_order_seq_cst) +{ + return bitwise_cast*>(location)->exchangeSub(operand, order); +} + +template +inline T atomicExchangeXor(T* location, U operand, std::memory_order order = std::memory_order_seq_cst) +{ + return bitwise_cast*>(location)->exchangeXor(operand, order); +} + +template +inline T atomicExchange(T* location, T newValue, std::memory_order order = std::memory_order_seq_cst) +{ + return bitwise_cast*>(location)->exchange(newValue, order); } // Just a compiler fence. Has no effect on the hardware, but tells the compiler @@ -223,7 +211,7 @@ inline bool weakCompareAndSwapSize(volatile size_t* location, size_t expected, s // to do things like register allocation and code motion over pure operations. inline void compilerFence() { -#if OS(WINDOWS) && !COMPILER(GCC) +#if OS(WINDOWS) && !COMPILER(GCC_OR_CLANG) _ReadWriteBarrier(); #else asm volatile("" ::: "memory"); @@ -234,122 +222,207 @@ inline void compilerFence() // Full memory fence. No accesses will float above this, and no accesses will sink // below it. -inline void armV7_dmb() +inline void arm_dmb() { - asm volatile("dmb sy" ::: "memory"); + asm volatile("dmb ish" ::: "memory"); } // Like the above, but only affects stores. -inline void armV7_dmb_st() +inline void arm_dmb_st() +{ + asm volatile("dmb ishst" ::: "memory"); +} + +inline void arm_isb() { - asm volatile("dmb st" ::: "memory"); + asm volatile("isb" ::: "memory"); } -inline void loadLoadFence() { armV7_dmb(); } -inline void loadStoreFence() { armV7_dmb(); } -inline void storeLoadFence() { armV7_dmb(); } -inline void storeStoreFence() { armV7_dmb_st(); } -inline void memoryBarrierAfterLock() { armV7_dmb(); } -inline void memoryBarrierBeforeUnlock() { armV7_dmb(); } +inline void loadLoadFence() { arm_dmb(); } +inline void loadStoreFence() { arm_dmb(); } +inline void storeLoadFence() { arm_dmb(); } +inline void storeStoreFence() { arm_dmb_st(); } +inline void memoryBarrierAfterLock() { arm_dmb(); } +inline void memoryBarrierBeforeUnlock() { arm_dmb(); } +inline void crossModifyingCodeFence() { arm_isb(); } #elif CPU(X86) || CPU(X86_64) -inline void x86_mfence() +inline void x86_ortop() { -#if OS(WINDOWS) && !COMPILER(GCC) - // I think that this does the equivalent of a dummy interlocked instruction, - // instead of using the 'mfence' instruction, at least according to MSDN. I - // know that it is equivalent for our purposes, but it would be good to - // investigate if that is actually better. +#if OS(WINDOWS) MemoryBarrier(); +#elif CPU(X86_64) + // This has acqrel semantics and is much cheaper than mfence. For exampe, in the JSC GC, using + // mfence as a store-load fence was a 9% slow-down on Octane/splay while using this was neutral. + asm volatile("lock; orl $0, (%%rsp)" ::: "memory"); +#else + asm volatile("lock; orl $0, (%%esp)" ::: "memory"); +#endif +} + +inline void x86_cpuid() +{ +#if OS(WINDOWS) + int info[4]; + __cpuid(info, 0); +#elif CPU(X86) + // GCC 4.9 on x86 in PIC mode can't use %ebx, so we have to save and restore it manually. + // But since we don't care about what cpuid returns (we use it as a serializing instruction), + // we can simply throw away what cpuid put in %ebx. + intptr_t a = 0, c, d; + asm volatile( + "pushl %%ebx\n\t" + "cpuid\n\t" + "popl %%ebx\n\t" + : "+a"(a), "=c"(c), "=d"(d) + : + : "memory"); #else - asm volatile("mfence" ::: "memory"); + intptr_t a = 0, b, c, d; + asm volatile( + "cpuid" + : "+a"(a), "=b"(b), "=c"(c), "=d"(d) + : + : "memory"); #endif } inline void loadLoadFence() { compilerFence(); } inline void loadStoreFence() { compilerFence(); } -inline void storeLoadFence() { x86_mfence(); } +inline void storeLoadFence() { x86_ortop(); } inline void storeStoreFence() { compilerFence(); } inline void memoryBarrierAfterLock() { compilerFence(); } inline void memoryBarrierBeforeUnlock() { compilerFence(); } +inline void crossModifyingCodeFence() { x86_cpuid(); } #else -inline void loadLoadFence() { compilerFence(); } -inline void loadStoreFence() { compilerFence(); } -inline void storeLoadFence() { compilerFence(); } -inline void storeStoreFence() { compilerFence(); } -inline void memoryBarrierAfterLock() { compilerFence(); } -inline void memoryBarrierBeforeUnlock() { compilerFence(); } +inline void loadLoadFence() { std::atomic_thread_fence(std::memory_order_seq_cst); } +inline void loadStoreFence() { std::atomic_thread_fence(std::memory_order_seq_cst); } +inline void storeLoadFence() { std::atomic_thread_fence(std::memory_order_seq_cst); } +inline void storeStoreFence() { std::atomic_thread_fence(std::memory_order_seq_cst); } +inline void memoryBarrierAfterLock() { std::atomic_thread_fence(std::memory_order_seq_cst); } +inline void memoryBarrierBeforeUnlock() { std::atomic_thread_fence(std::memory_order_seq_cst); } +inline void crossModifyingCodeFence() { std::atomic_thread_fence(std::memory_order_seq_cst); } // Probably not strong enough. #endif -inline bool weakCompareAndSwap(uint8_t* location, uint8_t expected, uint8_t newValue) -{ -#if ENABLE(COMPARE_AND_SWAP) -#if !COMPILER(MSVC) && (CPU(X86) || CPU(X86_64)) - // !COMPILER(MSVC) here means "ASM_SYNTAX(AT_AND_T)" - unsigned char result; - asm volatile( - "lock; cmpxchgb %3, %2\n\t" - "sete %1" - : "+a"(expected), "=q"(result), "+m"(*location) - : "q"(newValue) - : "memory" - ); - return result; -#elif COMPILER(MSVC) && CPU(X86) - // COMPILER(MSVC) here means "ASM_SYNTAX(INTEL)" - // FIXME: We need a 64-bit ASM implementation, but this cannot be inline due to - // Microsoft's decision to exclude it from the compiler. - bool result = false; - - __asm { - mov al, expected - mov edx, location - mov cl, newValue - lock cmpxchg byte ptr[edx], cl - setz result - } +typedef size_t ConsumeDependency; - return result; +template ::type* = nullptr> +ALWAYS_INLINE ConsumeDependency zeroWithConsumeDependency(T value) +{ + uint64_t dependency; + uint64_t copy = bitwise_cast(value); +#if CPU(ARM64) + // Create a magical zero value through inline assembly, whose computation + // isn't visible to the optimizer. This zero is then usable as an offset in + // further address computations: adding zero does nothing, but the compiler + // doesn't know it. It's magical because it creates an address dependency + // from the load of `location` to the uses of the dependency, which triggers + // the ARM ISA's address dependency rule, a.k.a. the mythical C++ consume + // ordering. This forces weak memory order CPUs to observe `location` and + // dependent loads in their store order without the reader using a barrier + // or an acquire load. + asm volatile("eor %x[dependency], %x[in], %x[in]" + : [dependency] "=r"(dependency) + : [in] "r"(copy) + // Lie about touching memory. Not strictly needed, but is + // likely to avoid unwanted load/store motion. + : "memory"); +#elif CPU(ARM) + asm volatile("eor %[dependency], %[in], %[in]" + : [dependency] "=r"(dependency) + : [in] "r"(copy) + : "memory"); #else - uintptr_t locationValue = bitwise_cast(location); - uintptr_t alignedLocationValue = locationValue & ~(sizeof(unsigned) - 1); - uintptr_t locationOffset = locationValue - alignedLocationValue; - ASSERT(locationOffset < sizeof(unsigned)); - unsigned* alignedLocation = bitwise_cast(alignedLocationValue); - // Make sure that this load is always issued and never optimized away. - unsigned oldAlignedValue = *const_cast(alignedLocation); - - struct Splicer { - static unsigned splice(unsigned value, uint8_t byte, uintptr_t byteIndex) - { - union { - unsigned word; - uint8_t bytes[sizeof(unsigned)]; - } u; - u.word = value; - u.bytes[byteIndex] = byte; - return u.word; - } - }; - - unsigned expectedAlignedValue = Splicer::splice(oldAlignedValue, expected, locationOffset); - unsigned newAlignedValue = Splicer::splice(oldAlignedValue, newValue, locationOffset); - - return weakCompareAndSwap(alignedLocation, expectedAlignedValue, newAlignedValue); + // No dependency is needed for this architecture. + loadLoadFence(); + dependency = 0; + (void)copy; #endif + return static_cast(dependency); +} + +template ::type* = nullptr> +ALWAYS_INLINE ConsumeDependency zeroWithConsumeDependency(T value) +{ + uint32_t dependency; + uint32_t copy = bitwise_cast(value); +#if CPU(ARM64) + asm volatile("eor %w[dependency], %w[in], %w[in]" + : [dependency] "=r"(dependency) + : [in] "r"(copy) + : "memory"); +#elif CPU(ARM) + asm volatile("eor %[dependency], %[in], %[in]" + : [dependency] "=r"(dependency) + : [in] "r"(copy) + : "memory"); #else - UNUSED_PARAM(location); - UNUSED_PARAM(expected); - UNUSED_PARAM(newValue); - CRASH(); - return false; + loadLoadFence(); + dependency = 0; + (void)copy; #endif + return static_cast(dependency); +} + +template ::type* = nullptr> +ALWAYS_INLINE ConsumeDependency zeroWithConsumeDependency(T value) +{ + uint16_t copy = bitwise_cast(value); + return zeroWithConsumeDependency(static_cast(copy)); +} + +template ::type* = nullptr> +ALWAYS_INLINE ConsumeDependency zeroWithConsumeDependency(T value) +{ + uint8_t copy = bitwise_cast(value); + return zeroWithConsumeDependency(static_cast(copy)); +} + +template +struct Consumed { + T value; + ConsumeDependency dependency; +}; + +// Consume load, returning the loaded `value` at `location` and a dependent-zero +// which creates an address dependency from the `location`. +// +// Usage notes: +// +// * Regarding control dependencies: merely branching based on `value` or +// `dependency` isn't sufficient to impose a dependency ordering: you must +// use `dependency` in the address computation of subsequent loads which +// should observe the store order w.r.t. `location`. +// * Regarding memory ordering: consume load orders the `location` load with +// susequent dependent loads *only*. It says nothing about ordering of other +// loads! +// +// Caveat emptor. +template +ALWAYS_INLINE auto consumeLoad(const T* location) +{ + typedef typename std::remove_cv::type Returned; + Consumed ret { }; + // Force the read of `location` to occur exactly once and without fusing or + // forwarding using volatile. This is important because the compiler could + // otherwise rematerialize or find equivalent loads, or simply forward from + // a previous one, and lose the dependency we're trying so hard to + // create. Prevent tearing by using an atomic, but let it move around by + // using relaxed. We have at least a memory fence after this which prevents + // the load from moving too much. + ret.value = reinterpret_cast*>(location)->load(std::memory_order_relaxed); + ret.dependency = zeroWithConsumeDependency(ret.value); + return ret; } } // namespace WTF +using WTF::Atomic; +using WTF::ConsumeDependency; +using WTF::consumeLoad; + #endif // Atomics_h diff --git a/Source/WTF/wtf/AutodrainedPool.h b/Source/WTF/wtf/AutodrainedPool.h index 6fb0893a5..6f02c5df4 100644 --- a/Source/WTF/wtf/AutodrainedPool.h +++ b/Source/WTF/wtf/AutodrainedPool.h @@ -10,7 +10,7 @@ * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. - * 3. Neither the name of Apple Computer, Inc. ("Apple") nor the names of + * 3. Neither the name of Apple Inc. ("Apple") nor the names of * its contributors may be used to endorse or promote products derived * from this software without specific prior written permission. * @@ -31,7 +31,7 @@ #include -#if PLATFORM(MAC) && !defined(__OBJC__) +#if USE(FOUNDATION) && !defined(__OBJC__) typedef struct objc_object *id; #endif @@ -40,7 +40,7 @@ namespace WTF { class AutodrainedPool { WTF_MAKE_NONCOPYABLE(AutodrainedPool); public: -#if PLATFORM(MAC) +#if USE(FOUNDATION) WTF_EXPORT_PRIVATE AutodrainedPool(); WTF_EXPORT_PRIVATE ~AutodrainedPool(); #else @@ -49,7 +49,7 @@ public: #endif private: -#if PLATFORM(MAC) +#if USE(FOUNDATION) id m_pool; #endif }; diff --git a/Source/WTF/wtf/AutomaticThread.cpp b/Source/WTF/wtf/AutomaticThread.cpp new file mode 100644 index 000000000..387c6e25d --- /dev/null +++ b/Source/WTF/wtf/AutomaticThread.cpp @@ -0,0 +1,235 @@ +/* + * Copyright (C) 2016-2017 Apple Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY + * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY + * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include "config.h" +#include "AutomaticThread.h" + +#include "DataLog.h" + +namespace WTF { + +static const bool verbose = false; + +RefPtr AutomaticThreadCondition::create() +{ + return adoptRef(new AutomaticThreadCondition()); +} + +AutomaticThreadCondition::AutomaticThreadCondition() +{ +} + +AutomaticThreadCondition::~AutomaticThreadCondition() +{ +} + +void AutomaticThreadCondition::notifyOne(const AbstractLocker& locker) +{ + for (AutomaticThread* thread : m_threads) { + if (thread->isWaiting(locker)) { + thread->notify(locker); + return; + } + } + + for (AutomaticThread* thread : m_threads) { + if (!thread->hasUnderlyingThread(locker)) { + thread->start(locker); + return; + } + } + + m_condition.notifyOne(); +} + +void AutomaticThreadCondition::notifyAll(const AbstractLocker& locker) +{ + m_condition.notifyAll(); + + for (AutomaticThread* thread : m_threads) { + if (thread->isWaiting(locker)) + thread->notify(locker); + else if (!thread->hasUnderlyingThread(locker)) + thread->start(locker); + } +} + +void AutomaticThreadCondition::wait(Lock& lock) +{ + m_condition.wait(lock); +} + +void AutomaticThreadCondition::add(const AbstractLocker&, AutomaticThread* thread) +{ + ASSERT(!m_threads.contains(thread)); + m_threads.append(thread); +} + +void AutomaticThreadCondition::remove(const AbstractLocker&, AutomaticThread* thread) +{ + m_threads.removeFirst(thread); + ASSERT(!m_threads.contains(thread)); +} + +bool AutomaticThreadCondition::contains(const AbstractLocker&, AutomaticThread* thread) +{ + return m_threads.contains(thread); +} + +AutomaticThread::AutomaticThread(const AbstractLocker& locker, Box lock, RefPtr condition) + : m_lock(lock) + , m_condition(condition) +{ + if (verbose) + dataLog(RawPointer(this), ": Allocated AutomaticThread.\n"); + m_condition->add(locker, this); +} + +AutomaticThread::~AutomaticThread() +{ + if (verbose) + dataLog(RawPointer(this), ": Deleting AutomaticThread.\n"); + LockHolder locker(*m_lock); + + // It's possible that we're in a waiting state with the thread shut down. This is a goofy way to + // die, but it could happen. + m_condition->remove(locker, this); +} + +bool AutomaticThread::tryStop(const AbstractLocker&) +{ + if (!m_isRunning) + return true; + if (m_hasUnderlyingThread) + return false; + m_isRunning = false; + return true; +} + +bool AutomaticThread::isWaiting(const AbstractLocker& locker) +{ + return hasUnderlyingThread(locker) && m_isWaiting; +} + +bool AutomaticThread::notify(const AbstractLocker& locker) +{ + ASSERT_UNUSED(locker, hasUnderlyingThread(locker)); + m_isWaiting = false; + return m_waitCondition.notifyOne(); +} + +void AutomaticThread::join() +{ + LockHolder locker(*m_lock); + while (m_isRunning) + m_isRunningCondition.wait(*m_lock); +} + +void AutomaticThread::start(const AbstractLocker&) +{ + RELEASE_ASSERT(m_isRunning); + + RefPtr preserveThisForThread = this; + + m_hasUnderlyingThread = true; + + ThreadIdentifier thread = createThread( + "WTF::AutomaticThread", + [=] () { + if (verbose) + dataLog(RawPointer(this), ": Running automatic thread!\n"); + + RefPtr thread = preserveThisForThread; + thread->threadDidStart(); + + if (!ASSERT_DISABLED) { + LockHolder locker(*m_lock); + ASSERT(m_condition->contains(locker, this)); + } + + auto stopImpl = [&] (const AbstractLocker& locker) { + thread->threadIsStopping(locker); + thread->m_hasUnderlyingThread = false; + }; + + auto stopPermanently = [&] (const AbstractLocker& locker) { + m_isRunning = false; + m_isRunningCondition.notifyAll(); + stopImpl(locker); + }; + + auto stopForTimeout = [&] (const AbstractLocker& locker) { + stopImpl(locker); + }; + + for (;;) { + { + LockHolder locker(*m_lock); + for (;;) { + PollResult result = poll(locker); + if (result == PollResult::Work) + break; + if (result == PollResult::Stop) + return stopPermanently(locker); + RELEASE_ASSERT(result == PollResult::Wait); + // Shut the thread down after one second. + m_isWaiting = true; + bool awokenByNotify = + m_waitCondition.waitFor(*m_lock, 1_s); + if (verbose && !awokenByNotify && !m_isWaiting) + dataLog(RawPointer(this), ": waitFor timed out, but notified via m_isWaiting flag!\n"); + if (m_isWaiting) { + m_isWaiting = false; + if (verbose) + dataLog(RawPointer(this), ": Going to sleep!\n"); + // It's important that we don't release the lock until we have completely + // indicated that the thread is kaput. Otherwise we'll have a a notify + // race that manifests as a deadlock on VM shutdown. + return stopForTimeout(locker); + } + } + } + + WorkResult result = work(); + if (result == WorkResult::Stop) { + LockHolder locker(*m_lock); + return stopPermanently(locker); + } + RELEASE_ASSERT(result == WorkResult::Continue); + } + }); + detachThread(thread); +} + +void AutomaticThread::threadDidStart() +{ +} + +void AutomaticThread::threadIsStopping(const AbstractLocker&) +{ +} + +} // namespace WTF + diff --git a/Source/WTF/wtf/AutomaticThread.h b/Source/WTF/wtf/AutomaticThread.h new file mode 100644 index 000000000..ec6ba438f --- /dev/null +++ b/Source/WTF/wtf/AutomaticThread.h @@ -0,0 +1,193 @@ +/* + * Copyright (C) 2016-2017 Apple Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY + * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY + * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef WTF_AutomaticThread_h +#define WTF_AutomaticThread_h + +#include +#include +#include +#include +#include +#include +#include + +namespace WTF { + +// Often, we create threads that have this as their body: +// +// for (;;) { +// { +// LockHolder locker(m_lock); +// for (;;) { +// [1] stuff that could break, return, or fall through; +// m_condition.wait(m_lock); +// } +// } +// +// [2] do work; +// } +// +// When we do this, we don't always do a good job of managing this thread's lifetime, which may lead +// to this thread sitting around even when it is not needed. +// +// AutomaticThread is here to help you in these situations. It encapsulates a lock, a condition +// variable, and a thread. It will automatically shut the thread down after 1 second of inactivity. +// You use AutomaticThread by subclassing it, and put any state that is needed between [1] and [2] +// in the subclass. +// +// The terminology we use is: +// +// [1] PollResult AutomaticThread::poll() +// [2] WordResult AutomaticThread::work() +// +// Note that poll() and work() may not be called on the same thread every time, since this will shut +// down the thread as necessary. This is legal since m_condition.wait(m_lock) can drop the lock, and +// so there is no reason to keep the thread around. + +class AutomaticThread; + +class AutomaticThreadCondition : public ThreadSafeRefCounted { +public: + static WTF_EXPORT_PRIVATE RefPtr create(); + + WTF_EXPORT_PRIVATE ~AutomaticThreadCondition(); + + WTF_EXPORT_PRIVATE void notifyOne(const AbstractLocker&); + WTF_EXPORT_PRIVATE void notifyAll(const AbstractLocker&); + + // You can reuse this condition for other things, just as you would any other condition. + // However, since conflating conditions could lead to thundering herd, it's best to avoid it. + // One known-good case for one-true-condition is when the communication involves just two + // threads. In such cases, the thread doing the notifyAll() can wake up at most one thread - + // its partner. + WTF_EXPORT_PRIVATE void wait(Lock&); + +private: + friend class AutomaticThread; + + WTF_EXPORT_PRIVATE AutomaticThreadCondition(); + + void add(const AbstractLocker&, AutomaticThread*); + void remove(const AbstractLocker&, AutomaticThread*); + bool contains(const AbstractLocker&, AutomaticThread*); + + Condition m_condition; + Vector m_threads; +}; + +class WTF_EXPORT_PRIVATE AutomaticThread : public ThreadSafeRefCounted { +public: + // Note that if you drop all of your references to an AutomaticThread then as soon as there is a + // second during which it doesn't get woken up, it will simply die on its own. This is a + // permanent kind of death where the AutomaticThread object goes away, rather than the temporary + // kind of death where AutomaticThread lives but its underlying thread dies. All you have to do + // to prevent permanent death is keep a ref to AutomaticThread. At time of writing, every user of + // AutomaticThread keeps a ref to it and does join() as part of the shutdown process, so only the + // temporary kind of automatic death happens in practice. We keep the permanent death feature + // because it leads to an easy-to-understand reference counting discipline (AutomaticThread holds + // strong ref to AutomaticThreadCondition and the underlying thread holds a strong ref to + // AutomaticThread). + virtual ~AutomaticThread(); + + // Sometimes it's possible to optimize for the case that there is no underlying thread. + bool hasUnderlyingThread(const AbstractLocker&) const { return m_hasUnderlyingThread; } + + // This attempts to quickly stop the thread. This will succeed if the thread happens to not be + // running. Returns true if the thread has been stopped. A good idiom for stopping your automatic + // thread is to first try this, and if that doesn't work, to tell the thread using your own + // mechanism (set some flag and then notify the condition). + bool tryStop(const AbstractLocker&); + + bool isWaiting(const AbstractLocker&); + + bool notify(const AbstractLocker&); + + void join(); + +protected: + // This logically creates the thread, but in reality the thread won't be created until someone + // calls AutomaticThreadCondition::notifyOne() or notifyAll(). + AutomaticThread(const AbstractLocker&, Box, RefPtr); + + // To understand PollResult and WorkResult, imagine that poll() and work() are being called like + // so: + // + // void AutomaticThread::runThread() + // { + // for (;;) { + // { + // LockHolder locker(m_lock); + // for (;;) { + // PollResult result = poll(); + // if (result == PollResult::Work) + // break; + // if (result == PollResult::Stop) + // return; + // RELEASE_ASSERT(result == PollResult::Wait); + // m_condition.wait(m_lock); + // } + // } + // + // WorkResult result = work(); + // if (result == WorkResult::Stop) + // return; + // RELEASE_ASSERT(result == WorkResult::Continue); + // } + // } + + enum class PollResult { Work, Stop, Wait }; + virtual PollResult poll(const AbstractLocker&) = 0; + + enum class WorkResult { Continue, Stop }; + virtual WorkResult work() = 0; + + // It's sometimes useful to allocate resources while the thread is running, and to destroy them + // when the thread dies. These methods let you do this. You can override these methods, and you + // can be sure that the default ones don't do anything (so you don't need a super call). + virtual void threadDidStart(); + virtual void threadIsStopping(const AbstractLocker&); + +private: + friend class AutomaticThreadCondition; + + void start(const AbstractLocker&); + + Box m_lock; + RefPtr m_condition; + bool m_isRunning { true }; + bool m_isWaiting { false }; + bool m_hasUnderlyingThread { false }; + Condition m_waitCondition; + Condition m_isRunningCondition; +}; + +} // namespace WTF + +using WTF::AutomaticThread; +using WTF::AutomaticThreadCondition; + +#endif // WTF_AutomaticThread_h + diff --git a/Source/WTF/wtf/BackwardsGraph.h b/Source/WTF/wtf/BackwardsGraph.h new file mode 100644 index 000000000..65337baf1 --- /dev/null +++ b/Source/WTF/wtf/BackwardsGraph.h @@ -0,0 +1,295 @@ +/* + * Copyright (C) 2016 Apple Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY + * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY + * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef WTF_BackwardsGraph_h +#define WTF_BackwardsGraph_h + +#include +#include +#include +#include + +namespace WTF { + +template +class BackwardsGraph { + WTF_MAKE_NONCOPYABLE(BackwardsGraph); + WTF_MAKE_FAST_ALLOCATED; +public: + // We use "#end" to refer to the synthetic root we have created. + static const char* rootName() { return "#end"; }; + + class Node { + public: + Node(typename Graph::Node node = typename Graph::Node()) + : m_node(node) + { + } + + static Node root() + { + Node result; + result.m_node = 0; + result.m_isRoot = true; + return result; + } + + bool operator==(const Node& other) const + { + return m_node == other.m_node + && m_isRoot == other.m_isRoot; + } + + bool operator!=(const Node& other) const + { + return !(*this == other); + } + + explicit operator bool() const { return *this != Node(); } + + bool isRoot() const + { + return m_isRoot; + } + + typename Graph::Node node() const { return m_node; } + + private: + typename Graph::Node m_node; + bool m_isRoot { false }; + }; + + class Set { + public: + Set() + { + } + + bool add(const Node& node) + { + if (node.isRoot()) + return checkAndSet(m_hasRoot, true); + return m_set.add(node.node()); + } + + bool remove(const Node& node) + { + if (node.isRoot()) + return checkAndSet(m_hasRoot, false); + return m_set.remove(node.node()); + } + + bool contains(const Node& node) + { + if (node.isRoot()) + return m_hasRoot; + return m_set.contains(node.node()); + } + + void dump(PrintStream& out) const + { + if (m_hasRoot) + out.print(rootName(), " "); + out.print(m_set); + } + + private: + typename Graph::Set m_set; + bool m_hasRoot { false }; + }; + + template + class Map { + public: + Map(Graph& graph) + : m_map(graph.template newMap()) + { + } + + void clear() + { + m_map.clear(); + m_root = T(); + } + + size_t size() const { return m_map.size() + 1; } + + T& operator[](size_t index) + { + if (!index) + return m_root; + return m_map[index - 1]; + } + + const T& operator[](size_t index) const + { + return (*const_cast(this))[index]; + } + + T& operator[](const Node& node) + { + if (node.isRoot()) + return m_root; + return m_map[node.node()]; + } + + const T& operator[](const Node& node) const + { + return (*const_cast(this))[node]; + } + + private: + typename Graph::template Map m_map; + T m_root; + }; + + typedef Vector List; + + BackwardsGraph(Graph& graph) + : m_graph(graph) + { + GraphNodeWorklist worklist; + + auto addRootSuccessor = [&] (typename Graph::Node node) { + if (worklist.push(node)) { + m_rootSuccessorList.append(node); + m_rootSuccessorSet.add(node); + while (typename Graph::Node node = worklist.pop()) + worklist.pushAll(graph.predecessors(node)); + } + }; + + for (unsigned i = 0; i < graph.numNodes(); ++i) { + if (typename Graph::Node node = graph.node(i)) { + if (!graph.successors(node).size()) + addRootSuccessor(node); + } + } + + // At this point there will be some nodes in the graph that aren't known to the worklist. We + // could add any or all of them to the root successors list. Adding all of them would be a bad + // pessimisation. Ideally we would pick the ones that have backward edges but no forward + // edges. That would require thinking, so we just use a rough heuristic: add the highest + // numbered nodes first, which is totally fine if the input program is already sorted nicely. + for (unsigned i = graph.numNodes(); i--;) { + if (typename Graph::Node node = graph.node(i)) + addRootSuccessor(node); + } + } + + Node root() { return Node::root(); } + + template + Map newMap() { return Map(m_graph); } + + List successors(const Node& node) const + { + if (node.isRoot()) + return m_rootSuccessorList; + List result; + for (typename Graph::Node predecessor : m_graph.predecessors(node.node())) + result.append(predecessor); + return result; + } + + List predecessors(const Node& node) const + { + if (node.isRoot()) + return { }; + + List result; + + if (m_rootSuccessorSet.contains(node.node())) + result.append(Node::root()); + + for (typename Graph::Node successor : m_graph.successors(node.node())) + result.append(successor); + + return result; + } + + unsigned index(const Node& node) const + { + if (node.isRoot()) + return 0; + return m_graph.index(node.node()) + 1; + } + + Node node(unsigned index) const + { + if (!index) + return Node::root(); + return m_graph.node(index - 1); + } + + unsigned numNodes() const + { + return m_graph.numNodes() + 1; + } + + CString dump(Node node) const + { + StringPrintStream out; + if (!node) + out.print(""); + else if (node.isRoot()) + out.print(rootName()); + else + out.print(m_graph.dump(node.node())); + return out.toCString(); + } + + void dump(PrintStream& out) const + { + for (unsigned i = 0; i < numNodes(); ++i) { + Node node = this->node(i); + if (!node) + continue; + out.print(dump(node), ":\n"); + out.print(" Preds: "); + CommaPrinter comma; + for (Node predecessor : predecessors(node)) + out.print(comma, dump(predecessor)); + out.print("\n"); + out.print(" Succs: "); + comma = CommaPrinter(); + for (Node successor : successors(node)) + out.print(comma, dump(successor)); + out.print("\n"); + } + } + +private: + Graph& m_graph; + List m_rootSuccessorList; + typename Graph::Set m_rootSuccessorSet; +}; + +} // namespace WTF + +using WTF::BackwardsGraph; + +#endif // WTF_BackwardsGraph_h + diff --git a/Source/WTF/wtf/Bag.h b/Source/WTF/wtf/Bag.h index 417402bca..01eca7472 100644 --- a/Source/WTF/wtf/Bag.h +++ b/Source/WTF/wtf/Bag.h @@ -30,30 +30,60 @@ namespace WTF { template class Bag { + WTF_MAKE_NONCOPYABLE(Bag); + WTF_MAKE_FAST_ALLOCATED; private: - struct Node { + class Node { + WTF_MAKE_FAST_ALLOCATED; + public: + template + Node(Args&&... args) + : m_item(std::forward(args)...) + { + } + T m_item; Node* m_next; }; public: Bag() - : m_head(0) { } + + Bag(Bag&& other) + { + ASSERT(!m_head); + m_head = other.m_head; + other.m_head = nullptr; + } + + Bag& operator=(Bag&& other) + { + m_head = other.m_head; + other.m_head = nullptr; + return *this; + } ~Bag() + { + clear(); + } + + void clear() { while (m_head) { Node* current = m_head; m_head = current->m_next; delete current; } + m_head = nullptr; } - T* add() + template + T* add(Args&&... args) { - Node* newNode = new Node; + Node* newNode = new Node(std::forward(args)...); newNode->m_next = m_head; m_head = newNode; return &newNode->m_item; @@ -81,6 +111,12 @@ public: { return m_node == other.m_node; } + + bool operator!=(const iterator& other) const + { + return !(*this == other); + } + private: template friend class WTF::Bag; Node* m_node; @@ -98,7 +134,7 @@ public: bool isEmpty() const { return !m_head; } private: - Node* m_head; + Node* m_head { nullptr }; }; } // namespace WTF diff --git a/Source/WTF/wtf/BagToHashMap.h b/Source/WTF/wtf/BagToHashMap.h index c1be7ff95..539795fde 100644 --- a/Source/WTF/wtf/BagToHashMap.h +++ b/Source/WTF/wtf/BagToHashMap.h @@ -1,5 +1,5 @@ /* - * Copyright (C) 2013 Apple Inc. All rights reserved. + * Copyright (C) 2013, 2014 Apple Inc. All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions @@ -32,8 +32,8 @@ namespace WTF { -template -void toHashMap(Bag& bag, KeyGetterFunctor& getKey, HashMap& result) +template +void toHashMap(Bag& bag, KeyGetterFunctor& getKey, HashMap& result) { for (typename Bag::iterator iter = bag.begin(); !!iter; ++iter) { ElementType* element = *iter; diff --git a/Source/WTF/wtf/BitVector.cpp b/Source/WTF/wtf/BitVector.cpp index f60856c39..736ff7d28 100644 --- a/Source/WTF/wtf/BitVector.cpp +++ b/Source/WTF/wtf/BitVector.cpp @@ -182,6 +182,50 @@ size_t BitVector::bitCountSlow() const } bool BitVector::equalsSlowCase(const BitVector& other) const +{ + bool result = equalsSlowCaseFast(other); + ASSERT(result == equalsSlowCaseSimple(other)); + return result; +} + +bool BitVector::equalsSlowCaseFast(const BitVector& other) const +{ + if (isInline() != other.isInline()) + return equalsSlowCaseSimple(other); + + const OutOfLineBits* myBits = outOfLineBits(); + const OutOfLineBits* otherBits = other.outOfLineBits(); + + size_t myNumWords = myBits->numWords(); + size_t otherNumWords = otherBits->numWords(); + size_t minNumWords; + size_t maxNumWords; + + const OutOfLineBits* longerBits; + if (myNumWords < otherNumWords) { + minNumWords = myNumWords; + maxNumWords = otherNumWords; + longerBits = otherBits; + } else { + minNumWords = otherNumWords; + maxNumWords = myNumWords; + longerBits = myBits; + } + + for (size_t i = minNumWords; i < maxNumWords; ++i) { + if (longerBits->bits()[i]) + return false; + } + + for (size_t i = minNumWords; i--;) { + if (myBits->bits()[i] != otherBits->bits()[i]) + return false; + } + + return true; +} + +bool BitVector::equalsSlowCaseSimple(const BitVector& other) const { // This is really cheesy, but probably good enough for now. for (unsigned i = std::max(size(), other.size()); i--;) { diff --git a/Source/WTF/wtf/BitVector.h b/Source/WTF/wtf/BitVector.h index 77d95f6df..762cc0460 100644 --- a/Source/WTF/wtf/BitVector.h +++ b/Source/WTF/wtf/BitVector.h @@ -1,5 +1,5 @@ /* - * Copyright (C) 2011 Apple Inc. All rights reserved. + * Copyright (C) 2011, 2014, 2016 Apple Inc. All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions @@ -28,6 +28,7 @@ #include #include +#include #include #include #include @@ -117,24 +118,31 @@ public: return !!(bits()[bit / bitsInPointer()] & (static_cast(1) << (bit & (bitsInPointer() - 1)))); } - void quickSet(size_t bit) + bool quickSet(size_t bit) { ASSERT_WITH_SECURITY_IMPLICATION(bit < size()); - bits()[bit / bitsInPointer()] |= (static_cast(1) << (bit & (bitsInPointer() - 1))); + uintptr_t& word = bits()[bit / bitsInPointer()]; + uintptr_t mask = static_cast(1) << (bit & (bitsInPointer() - 1)); + bool result = !!(word & mask); + word |= mask; + return result; } - void quickClear(size_t bit) + bool quickClear(size_t bit) { ASSERT_WITH_SECURITY_IMPLICATION(bit < size()); - bits()[bit / bitsInPointer()] &= ~(static_cast(1) << (bit & (bitsInPointer() - 1))); + uintptr_t& word = bits()[bit / bitsInPointer()]; + uintptr_t mask = static_cast(1) << (bit & (bitsInPointer() - 1)); + bool result = !!(word & mask); + word &= ~mask; + return result; } - void quickSet(size_t bit, bool value) + bool quickSet(size_t bit, bool value) { if (value) - quickSet(bit); - else - quickClear(bit); + return quickSet(bit); + return quickClear(bit); } bool get(size_t bit) const @@ -143,32 +151,48 @@ public: return false; return quickGet(bit); } + + bool contains(size_t bit) const + { + return get(bit); + } - void set(size_t bit) + bool set(size_t bit) { ensureSize(bit + 1); - quickSet(bit); + return quickSet(bit); + } + + // This works like the add methods of sets. Instead of returning the previous value, like set(), + // it returns whether the bit transitioned from false to true. + bool add(size_t bit) + { + return !set(bit); } - void ensureSizeAndSet(size_t bit, size_t size) + bool ensureSizeAndSet(size_t bit, size_t size) { ensureSize(size); - quickSet(bit); + return quickSet(bit); } - void clear(size_t bit) + bool clear(size_t bit) { if (bit >= size()) - return; - quickClear(bit); + return false; + return quickClear(bit); + } + + bool remove(size_t bit) + { + return clear(bit); } - void set(size_t bit, bool value) + bool set(size_t bit, bool value) { if (value) - set(bit); - else - clear(bit); + return set(bit); + return clear(bit); } void merge(const BitVector& other) @@ -209,6 +233,19 @@ public: return bitCountSlow(); } + size_t findBit(size_t index, bool value) const + { + size_t result = findBitFast(index, value); + if (!ASSERT_DISABLED) { + size_t expectedResult = findBitSimple(index, value); + if (result != expectedResult) { + dataLog("findBit(", index, ", ", value, ") on ", *this, " should have gotten ", expectedResult, " but got ", result, "\n"); + ASSERT_NOT_REACHED(); + } + } + return result; + } + WTF_EXPORT_PRIVATE void dump(PrintStream& out) const; enum EmptyValueTag { EmptyValue }; @@ -249,6 +286,46 @@ public: return IntHash::hash(value); } + class iterator { + public: + iterator() + : m_bitVector(nullptr) + , m_index(0) + { + } + + iterator(const BitVector& bitVector, size_t index) + : m_bitVector(&bitVector) + , m_index(index) + { + } + + size_t operator*() const { return m_index; } + + iterator& operator++() + { + m_index = m_bitVector->findBit(m_index + 1, true); + return *this; + } + + bool operator==(const iterator& other) const + { + return m_index == other.m_index; + } + + bool operator!=(const iterator& other) const + { + return !(*this == other); + } + private: + const BitVector* m_bitVector; + size_t m_index; + }; + + // Use this to iterate over set bits. + iterator begin() const { return iterator(*this, findBit(0, true)); } + iterator end() const { return iterator(*this, size()); } + private: static unsigned bitsInPointer() { @@ -283,6 +360,49 @@ private: return WTF::bitCount(static_cast(bits)); } + size_t findBitFast(size_t startIndex, bool value) const + { + if (isInline()) { + size_t index = startIndex; + findBitInWord(m_bitsOrPointer, index, maxInlineBits(), value); + return index; + } + + const OutOfLineBits* bits = outOfLineBits(); + + // value = true: casts to 1, then xors to 0, then negates to 0. + // value = false: casts to 0, then xors to 1, then negates to -1 (i.e. all one bits). + uintptr_t skipValue = -(static_cast(value) ^ 1); + size_t numWords = bits->numWords(); + + size_t wordIndex = startIndex / bitsInPointer(); + size_t startIndexInWord = startIndex - wordIndex * bitsInPointer(); + + while (wordIndex < numWords) { + uintptr_t word = bits->bits()[wordIndex]; + if (word != skipValue) { + size_t index = startIndexInWord; + if (findBitInWord(word, index, bitsInPointer(), value)) + return wordIndex * bitsInPointer() + index; + } + + wordIndex++; + startIndexInWord = 0; + } + + return bits->numBits(); + } + + size_t findBitSimple(size_t index, bool value) const + { + while (index < size()) { + if (get(index) == value) + return index; + index++; + } + return size(); + } + class OutOfLineBits { public: size_t numBits() const { return m_numBits; } @@ -318,6 +438,8 @@ private: WTF_EXPORT_PRIVATE size_t bitCountSlow() const; WTF_EXPORT_PRIVATE bool equalsSlowCase(const BitVector& other) const; + bool equalsSlowCaseFast(const BitVector& other) const; + bool equalsSlowCaseSimple(const BitVector& other) const; WTF_EXPORT_PRIVATE uintptr_t hashSlowCase() const; uintptr_t* bits() diff --git a/Source/WTF/wtf/Bitmap.h b/Source/WTF/wtf/Bitmap.h index 7b288f9ed..89b2c9da8 100644 --- a/Source/WTF/wtf/Bitmap.h +++ b/Source/WTF/wtf/Bitmap.h @@ -1,5 +1,5 @@ /* - * Copyright (C) 2010 Apple Inc. All rights reserved. + * Copyright (C) 2010, 2016 Apple Inc. All rights reserved. * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Lesser General Public @@ -27,22 +27,22 @@ namespace WTF { -enum BitmapAtomicMode { - // This makes concurrentTestAndSet behave just like testAndSet. - BitmapNotAtomic, - - // This makes concurrentTestAndSet use compareAndSwap, so that it's - // atomic even when used concurrently. - BitmapAtomic -}; - -template +template class Bitmap { + WTF_MAKE_FAST_ALLOCATED; + + static_assert(sizeof(WordType) <= sizeof(unsigned), "WordType must not be bigger than unsigned"); public: Bitmap(); + static constexpr size_t size() + { + return bitmapSize; + } + bool get(size_t) const; void set(size_t); + void set(size_t, bool); bool testAndSet(size_t); bool testAndClear(size_t); bool concurrentTestAndSet(size_t); @@ -50,14 +50,29 @@ public: size_t nextPossiblyUnset(size_t) const; void clear(size_t); void clearAll(); - int64_t findRunOfZeros(size_t) const; - size_t count(size_t = 0) const; + int64_t findRunOfZeros(size_t runLength) const; + size_t count(size_t start = 0) const; size_t isEmpty() const; size_t isFull() const; + + void merge(const Bitmap&); + void filter(const Bitmap&); + void exclude(const Bitmap&); + + template + void forEachSetBit(const Func&) const; + + void mergeAndClear(Bitmap&); + void setAndClear(Bitmap&); + + bool operator==(const Bitmap&) const; + bool operator!=(const Bitmap&) const; + + unsigned hash() const; private: static const unsigned wordSize = sizeof(WordType) * 8; - static const unsigned words = (size + wordSize - 1) / wordSize; + static const unsigned words = (bitmapSize + wordSize - 1) / wordSize; // the literal '1' is of type signed int. We want to use an unsigned // version of the correct size when doing the calculations because if @@ -69,26 +84,35 @@ private: std::array bits; }; -template -inline Bitmap::Bitmap() +template +inline Bitmap::Bitmap() { clearAll(); } -template -inline bool Bitmap::get(size_t n) const +template +inline bool Bitmap::get(size_t n) const { return !!(bits[n / wordSize] & (one << (n % wordSize))); } -template -inline void Bitmap::set(size_t n) +template +inline void Bitmap::set(size_t n) { bits[n / wordSize] |= (one << (n % wordSize)); } -template -inline bool Bitmap::testAndSet(size_t n) +template +inline void Bitmap::set(size_t n, bool value) +{ + if (value) + set(n); + else + clear(n); +} + +template +inline bool Bitmap::testAndSet(size_t n) { WordType mask = one << (n % wordSize); size_t index = n / wordSize; @@ -97,8 +121,8 @@ inline bool Bitmap::testAndSet(size_t n) return result; } -template -inline bool Bitmap::testAndClear(size_t n) +template +inline bool Bitmap::testAndClear(size_t n) { WordType mask = one << (n % wordSize); size_t index = n / wordSize; @@ -107,14 +131,9 @@ inline bool Bitmap::testAndClear(size_t n) return result; } -template -inline bool Bitmap::concurrentTestAndSet(size_t n) +template +inline bool Bitmap::concurrentTestAndSet(size_t n) { - if (atomicMode == BitmapNotAtomic) - return testAndSet(n); - - ASSERT(atomicMode == BitmapAtomic); - WordType mask = one << (n % wordSize); size_t index = n / wordSize; WordType* wordPtr = bits.data() + index; @@ -123,18 +142,13 @@ inline bool Bitmap::concurrentTestAndSet(size_t n) oldValue = *wordPtr; if (oldValue & mask) return true; - } while (!weakCompareAndSwap(wordPtr, oldValue, oldValue | mask)); + } while (!atomicCompareExchangeWeakRelaxed(wordPtr, oldValue, static_cast(oldValue | mask))); return false; } -template -inline bool Bitmap::concurrentTestAndClear(size_t n) +template +inline bool Bitmap::concurrentTestAndClear(size_t n) { - if (atomicMode == BitmapNotAtomic) - return testAndClear(n); - - ASSERT(atomicMode == BitmapAtomic); - WordType mask = one << (n % wordSize); size_t index = n / wordSize; WordType* wordPtr = bits.data() + index; @@ -143,37 +157,37 @@ inline bool Bitmap::concurrentTestAndClear(size_t n) oldValue = *wordPtr; if (!(oldValue & mask)) return false; - } while (!weakCompareAndSwap(wordPtr, oldValue, oldValue & ~mask)); + } while (!atomicCompareExchangeWeakRelaxed(wordPtr, oldValue, static_cast(oldValue & ~mask))); return true; } -template -inline void Bitmap::clear(size_t n) +template +inline void Bitmap::clear(size_t n) { bits[n / wordSize] &= ~(one << (n % wordSize)); } -template -inline void Bitmap::clearAll() +template +inline void Bitmap::clearAll() { memset(bits.data(), 0, sizeof(bits)); } -template -inline size_t Bitmap::nextPossiblyUnset(size_t start) const +template +inline size_t Bitmap::nextPossiblyUnset(size_t start) const { if (!~bits[start / wordSize]) return ((start / wordSize) + 1) * wordSize; return start + 1; } -template -inline int64_t Bitmap::findRunOfZeros(size_t runLength) const +template +inline int64_t Bitmap::findRunOfZeros(size_t runLength) const { if (!runLength) runLength = 1; - for (size_t i = 0; i <= (size - runLength) ; i++) { + for (size_t i = 0; i <= (bitmapSize - runLength) ; i++) { bool found = true; for (size_t j = i; j <= (i + runLength - 1) ; j++) { if (get(j)) { @@ -187,8 +201,8 @@ inline int64_t Bitmap::findRunOfZeros(size_t runLeng return -1; } -template -inline size_t Bitmap::count(size_t start) const +template +inline size_t Bitmap::count(size_t start) const { size_t result = 0; for ( ; (start % wordSize); ++start) { @@ -200,8 +214,8 @@ inline size_t Bitmap::count(size_t start) const return result; } -template -inline size_t Bitmap::isEmpty() const +template +inline size_t Bitmap::isEmpty() const { for (size_t i = 0; i < words; ++i) if (bits[i]) @@ -209,8 +223,8 @@ inline size_t Bitmap::isEmpty() const return true; } -template -inline size_t Bitmap::isFull() const +template +inline size_t Bitmap::isFull() const { for (size_t i = 0; i < words; ++i) if (~bits[i]) @@ -218,5 +232,89 @@ inline size_t Bitmap::isFull() const return true; } +template +inline void Bitmap::merge(const Bitmap& other) +{ + for (size_t i = 0; i < words; ++i) + bits[i] |= other.bits[i]; +} + +template +inline void Bitmap::filter(const Bitmap& other) +{ + for (size_t i = 0; i < words; ++i) + bits[i] &= other.bits[i]; +} + +template +inline void Bitmap::exclude(const Bitmap& other) +{ + for (size_t i = 0; i < words; ++i) + bits[i] &= ~other.bits[i]; +} + +template +template +inline void Bitmap::forEachSetBit(const Func& func) const +{ + for (size_t i = 0; i < words; ++i) { + WordType word = bits[i]; + if (!word) + continue; + size_t base = i * wordSize; + for (size_t j = 0; j < wordSize; ++j) { + if (word & 1) + func(base + j); + word >>= 1; + } + } +} + +template +inline void Bitmap::mergeAndClear(Bitmap& other) +{ + for (size_t i = 0; i < words; ++i) { + bits[i] |= other.bits[i]; + other.bits[i] = 0; + } +} + +template +inline void Bitmap::setAndClear(Bitmap& other) +{ + for (size_t i = 0; i < words; ++i) { + bits[i] = other.bits[i]; + other.bits[i] = 0; + } +} + +template +inline bool Bitmap::operator==(const Bitmap& other) const +{ + for (size_t i = 0; i < words; ++i) { + if (bits[i] != other.bits[i]) + return false; + } + return true; +} + +template +inline bool Bitmap::operator!=(const Bitmap& other) const +{ + return !(*this == other); +} + +template +inline unsigned Bitmap::hash() const +{ + unsigned result = 0; + for (size_t i = 0; i < words; ++i) + result ^= IntHash::hash(bits[i]); + return result; } + +} // namespace WTF + +using WTF::Bitmap; + #endif diff --git a/Source/WTF/wtf/BlockObjCExceptions.h b/Source/WTF/wtf/BlockObjCExceptions.h new file mode 100644 index 000000000..271bf6d79 --- /dev/null +++ b/Source/WTF/wtf/BlockObjCExceptions.h @@ -0,0 +1,32 @@ +/* + * Copyright (C) 2003, 2016 Apple Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY + * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY + * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#import + +WTF_EXPORT_PRIVATE NO_RETURN_DUE_TO_ASSERT void ReportBlockedObjCException(NSException *); + +#define BEGIN_BLOCK_OBJC_EXCEPTIONS @try { +#define END_BLOCK_OBJC_EXCEPTIONS } @catch(NSException *localException) { ReportBlockedObjCException(localException); } + diff --git a/Source/WTF/wtf/BlockPtr.h b/Source/WTF/wtf/BlockPtr.h new file mode 100644 index 000000000..1b79d4178 --- /dev/null +++ b/Source/WTF/wtf/BlockPtr.h @@ -0,0 +1,169 @@ +/* + * Copyright (C) 2016 Apple Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS'' + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, + * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS + * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF + * THE POSSIBILITY OF SUCH DAMAGE. + */ + +#pragma once + +#include +#include + +namespace WTF { + +extern "C" void* _NSConcreteMallocBlock[32]; + +template class BlockPtr; + +template +class BlockPtr { +public: + using BlockType = R (^)(Args...); + + template + static BlockPtr fromCallable(F function) + { + struct Descriptor { + uintptr_t reserved; + uintptr_t size; + void (*copy)(void *dst, const void *src); + void (*dispose)(const void *); + }; + + struct Block { + void* isa; + int32_t flags; + int32_t reserved; + R (*invoke)(void *, Args...); + const struct Descriptor* descriptor; + F f; + }; + + static const Descriptor descriptor { + 0, + sizeof(Block), + + // We keep the copy function null - the block is already on the heap + // so it should never be copied. + nullptr, + + [](const void* ptr) { + static_cast(const_cast(ptr))->f.~F(); + } + }; + + Block* block = static_cast(malloc(sizeof(Block))); + block->isa = _NSConcreteMallocBlock; + + enum { + BLOCK_NEEDS_FREE = (1 << 24), + BLOCK_HAS_COPY_DISPOSE = (1 << 25), + }; + const unsigned retainCount = 1; + + block->flags = BLOCK_HAS_COPY_DISPOSE | BLOCK_NEEDS_FREE | (retainCount << 1); + block->reserved = 0; + block->invoke = [](void *ptr, Args... args) -> R { + return static_cast(ptr)->f(std::forward(args)...); + }; + block->descriptor = &descriptor; + + new (&block->f) F { std::move(function) }; + + BlockPtr blockPtr; + blockPtr.m_block = reinterpret_cast(block); + + return blockPtr; + } + + BlockPtr() + : m_block(nullptr) + { + } + + BlockPtr(BlockType block) + : m_block(Block_copy(block)) + { + } + + BlockPtr(const BlockPtr& other) + : m_block(Block_copy(other.m_block)) + { + } + + BlockPtr(BlockPtr&& other) + : m_block(std::exchange(other.m_block, nullptr)) + { + } + + ~BlockPtr() + { + Block_release(m_block); + } + + BlockPtr& operator=(const BlockPtr& other) + { + if (this != &other) { + Block_release(m_block); + m_block = Block_copy(other.m_block); + } + + return *this; + } + + BlockPtr& operator=(BlockPtr&& other) + { + ASSERT(this != &other); + + Block_release(m_block); + m_block = std::exchange(other.m_block, nullptr); + + return *this; + } + + BlockType get() const { return m_block; } + + explicit operator bool() const { return m_block; } + bool operator!() const { return !m_block; } + + R operator()(Args... arguments) const + { + ASSERT(m_block); + + return m_block(std::forward(arguments)...); + } + +private: + BlockType m_block; +}; + +template +inline BlockPtr makeBlockPtr(R (^block)(Args...)) +{ + return BlockPtr(block); +} + +} + +using WTF::BlockPtr; +using WTF::makeBlockPtr; + diff --git a/Source/WTF/wtf/BloomFilter.h b/Source/WTF/wtf/BloomFilter.h index e14cb280e..afb17b4d6 100644 --- a/Source/WTF/wtf/BloomFilter.h +++ b/Source/WTF/wtf/BloomFilter.h @@ -1,5 +1,5 @@ /* - * Copyright (C) 2011 Apple Inc. All rights reserved. + * Copyright (C) 2011, 2015 Apple Inc. All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions @@ -26,31 +26,150 @@ #ifndef BloomFilter_h #define BloomFilter_h +#include #include namespace WTF { -// Counting bloom filter with k=2 and 8 bit counters. Uses 2^keyBits bytes of memory. +// Bloom filter with k=2. Uses 2^keyBits/8 bytes of memory. // False positive rate is approximately (1-e^(-2n/m))^2, where n is the number of unique // keys and m is the table size (==2^keyBits). +// See http://en.wikipedia.org/wiki/Bloom_filter template class BloomFilter { WTF_MAKE_FAST_ALLOCATED; public: - static_assert(keyBits <= 16, "BloomFilter key size must be less than or equal to 16!"); - static const size_t tableSize = 1 << keyBits; + + BloomFilter(); + + void add(unsigned hash); + // For example SHA1::Digest. + template void add(const std::array&); + + void add(const BloomFilter&); + + // The filter may give false positives (claim it may contain a key it doesn't) + // but never false negatives (claim it doesn't contain a key it does). + bool mayContain(unsigned hash) const; + template bool mayContain(const std::array&) const; + + void clear(); + + void add(const AtomicString& string) { add(string.impl()->existingHash()); } + void add(const String& string) { add(string.impl()->hash()); } + bool mayContain(const AtomicString& string) const { return mayContain(string.impl()->existingHash()); } + bool mayContain(const String& string) const { return mayContain(string.impl()->hash()); } + +private: + static const unsigned bitsPerPosition = 8 * sizeof(unsigned); static const unsigned keyMask = (1 << keyBits) - 1; - static uint8_t maximumCount() { return std::numeric_limits::max(); } + static unsigned arrayIndex(unsigned key) { return key / bitsPerPosition; } + static unsigned bitMask(unsigned key) { return 1 << (key % bitsPerPosition); } + template static std::pair keysFromHash(const std::array&); + + bool isBitSet(unsigned key) const; + void setBit(unsigned key); + + std::array m_bitArray; +}; + +template +inline BloomFilter::BloomFilter() + : m_bitArray() +{ +} + +template +inline bool BloomFilter::mayContain(unsigned hash) const +{ + // The top and bottom bits of the incoming hash are treated as independent bloom filter hash functions. + // This works well as long as the filter size is not much above 2^16. + return isBitSet(hash) && isBitSet(hash >> 16); +} + +template +inline void BloomFilter::add(unsigned hash) +{ + setBit(hash); + setBit(hash >> 16); +} + +template +template +inline std::pair BloomFilter::keysFromHash(const std::array& hash) +{ + // We could use larger k value than 2 for long hashes. + static_assert(hashSize >= 2 * sizeof(unsigned), "Hash array too short"); + return { + *reinterpret_cast(hash.data()), + *reinterpret_cast(hash.data() + sizeof(unsigned)) + }; +} + +template +template +inline bool BloomFilter::mayContain(const std::array& hash) const +{ + auto keys = keysFromHash(hash); + return isBitSet(keys.first) && isBitSet(keys.second); +} + +template +template +inline void BloomFilter::add(const std::array& hash) +{ + auto keys = keysFromHash(hash); + setBit(keys.first); + setBit(keys.second); +} + +template +inline void BloomFilter::add(const BloomFilter& other) +{ + for (size_t i = 0; i < m_bitArray.size(); ++i) + m_bitArray[i] |= other.m_bitArray[i]; +} + +template +bool BloomFilter::isBitSet(unsigned key) const +{ + unsigned maskedKey = key & keyMask; + ASSERT(arrayIndex(maskedKey) < m_bitArray.size()); + return m_bitArray[arrayIndex(maskedKey)] & bitMask(maskedKey); +} + +template +void BloomFilter::setBit(unsigned key) +{ + unsigned maskedKey = key & keyMask; + ASSERT(arrayIndex(maskedKey) < m_bitArray.size()); + m_bitArray[arrayIndex(maskedKey)] |= bitMask(maskedKey); +} + +template +inline void BloomFilter::clear() +{ + m_bitArray.fill(0); +} + +// Counting bloom filter with 8 bit counters. Uses 2^keyBits bytes of memory. Error rates as above. +// See http://en.wikipedia.org/wiki/Bloom_filter#Counting_filters +template +class CountingBloomFilter { + WTF_MAKE_FAST_ALLOCATED; +public: + static const size_t tableSize = 1 << keyBits; + static unsigned maximumCount() { return std::numeric_limits::max(); } - BloomFilter() { clear(); } + CountingBloomFilter(); void add(unsigned hash); void remove(unsigned hash); // The filter may give false positives (claim it may contain a key it doesn't) // but never false negatives (claim it doesn't contain a key it does). - bool mayContain(unsigned hash) const { return firstSlot(hash) && secondSlot(hash); } + bool mayContain(unsigned hash) const { return firstBucket(hash) && secondBucket(hash); } // The filter must be cleared before reuse even if all keys are removed. // Otherwise overflowed keys will stick around. @@ -71,19 +190,27 @@ public: #endif private: - uint8_t& firstSlot(unsigned hash) { return m_table[hash & keyMask]; } - uint8_t& secondSlot(unsigned hash) { return m_table[(hash >> 16) & keyMask]; } - const uint8_t& firstSlot(unsigned hash) const { return m_table[hash & keyMask]; } - const uint8_t& secondSlot(unsigned hash) const { return m_table[(hash >> 16) & keyMask]; } + static const unsigned keyMask = (1 << keyBits) - 1; - uint8_t m_table[tableSize]; + uint8_t& firstBucket(unsigned hash) { return m_buckets[hash & keyMask]; } + uint8_t& secondBucket(unsigned hash) { return m_buckets[(hash >> 16) & keyMask]; } + const uint8_t& firstBucket(unsigned hash) const { return m_buckets[hash & keyMask]; } + const uint8_t& secondBucket(unsigned hash) const { return m_buckets[(hash >> 16) & keyMask]; } + + std::array m_buckets; }; - + template -inline void BloomFilter::add(unsigned hash) +inline CountingBloomFilter::CountingBloomFilter() + : m_buckets() { - uint8_t& first = firstSlot(hash); - uint8_t& second = secondSlot(hash); +} + +template +inline void CountingBloomFilter::add(unsigned hash) +{ + auto& first = firstBucket(hash); + auto& second = secondBucket(hash); if (LIKELY(first < maximumCount())) ++first; if (LIKELY(second < maximumCount())) @@ -91,13 +218,13 @@ inline void BloomFilter::add(unsigned hash) } template -inline void BloomFilter::remove(unsigned hash) +inline void CountingBloomFilter::remove(unsigned hash) { - uint8_t& first = firstSlot(hash); - uint8_t& second = secondSlot(hash); + auto& first = firstBucket(hash); + auto& second = secondBucket(hash); ASSERT(first); ASSERT(second); - // In case of an overflow, the slot sticks in the table until clear(). + // In case of an overflow, the bucket sticks in the table until clear(). if (LIKELY(first < maximumCount())) --first; if (LIKELY(second < maximumCount())) @@ -105,27 +232,27 @@ inline void BloomFilter::remove(unsigned hash) } template -inline void BloomFilter::clear() +inline void CountingBloomFilter::clear() { - memset(m_table, 0, tableSize); + m_buckets.fill(0); } #if !ASSERT_DISABLED template -bool BloomFilter::likelyEmpty() const +bool CountingBloomFilter::likelyEmpty() const { - for (size_t n = 0; n < tableSize; ++n) { - if (m_table[n] && m_table[n] != maximumCount()) + for (auto& bucket : m_buckets) { + if (bucket && bucket != maximumCount()) return false; } return true; } template -bool BloomFilter::isClear() const +bool CountingBloomFilter::isClear() const { - for (size_t n = 0; n < tableSize; ++n) { - if (m_table[n]) + for (auto& bucket : m_buckets) { + if (bucket) return false; } return true; @@ -135,5 +262,6 @@ bool BloomFilter::isClear() const } using WTF::BloomFilter; +using WTF::CountingBloomFilter; #endif diff --git a/Source/WTF/wtf/BoundsCheckedPointer.h b/Source/WTF/wtf/BoundsCheckedPointer.h deleted file mode 100644 index be0d21a2c..000000000 --- a/Source/WTF/wtf/BoundsCheckedPointer.h +++ /dev/null @@ -1,286 +0,0 @@ -/* - * Copyright (C) 2011 Apple Inc. All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * - * 1. Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * 2. Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * 3. Neither the name of Apple Computer, Inc. ("Apple") nor the names of - * its contributors may be used to endorse or promote products derived - * from this software without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY - * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED - * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE - * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY - * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES - * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; - * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND - * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT - * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF - * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - */ - -#ifndef WTF_BoundsCheckedPointer_h -#define WTF_BoundsCheckedPointer_h - -#include - -namespace WTF { - -// Useful for when you'd like to do pointer arithmetic on a buffer, but -// you'd also like to get some ASSERT()'s that prevent you from overflowing. -// This should be performance-neutral in release builds, while providing -// you with strong assertions in debug builds. Note that all of the -// asserting happens when you actually access the pointer. You are allowed -// to overflow or underflow with arithmetic so long as no accesses are -// performed. - -template -class BoundsCheckedPointer { -public: - BoundsCheckedPointer() - : m_pointer(0) -#if !ASSERT_DISABLED - , m_begin(0) - , m_end(0) -#endif - { - } - - BoundsCheckedPointer(T* pointer, size_t numElements) - : m_pointer(pointer) -#if !ASSERT_DISABLED - , m_begin(pointer) - , m_end(pointer + numElements) -#endif - { - UNUSED_PARAM(numElements); - } - - BoundsCheckedPointer(T* pointer, T* end) - : m_pointer(pointer) -#if !ASSERT_DISABLED - , m_begin(pointer) - , m_end(end) -#endif - { - UNUSED_PARAM(end); - } - - BoundsCheckedPointer(T* pointer, T* begin, size_t numElements) - : m_pointer(pointer) -#if !ASSERT_DISABLED - , m_begin(begin) - , m_end(begin + numElements) -#endif - { - UNUSED_PARAM(begin); - UNUSED_PARAM(numElements); - } - - BoundsCheckedPointer(T* pointer, T* begin, T* end) - : m_pointer(pointer) -#if !ASSERT_DISABLED - , m_begin(begin) - , m_end(end) -#endif - { - UNUSED_PARAM(begin); - UNUSED_PARAM(end); - } - - BoundsCheckedPointer& operator=(T* value) - { - m_pointer = value; - return *this; - } - - BoundsCheckedPointer& operator+=(ptrdiff_t amount) - { - m_pointer += amount; - return *this; - } - - BoundsCheckedPointer& operator-=(ptrdiff_t amount) - { - m_pointer -= amount; - return *this; - } - - BoundsCheckedPointer operator+(ptrdiff_t amount) const - { - BoundsCheckedPointer result = *this; - result.m_pointer += amount; - return result; - } - - BoundsCheckedPointer operator-(ptrdiff_t amount) const - { - BoundsCheckedPointer result = *this; - result.m_pointer -= amount; - return result; - } - - BoundsCheckedPointer operator++() // prefix - { - m_pointer++; - return *this; - } - - BoundsCheckedPointer operator--() // prefix - { - m_pointer--; - return *this; - } - - BoundsCheckedPointer operator++(int) // postfix - { - BoundsCheckedPointer result = *this; - m_pointer++; - return result; - } - - BoundsCheckedPointer operator--(int) // postfix - { - BoundsCheckedPointer result = *this; - m_pointer--; - return result; - } - - bool operator<(T* other) const - { - return m_pointer < other; - } - - bool operator<=(T* other) const - { - return m_pointer <= other; - } - - bool operator>(T* other) const - { - return m_pointer > other; - } - - bool operator>=(T* other) const - { - return m_pointer >= other; - } - - bool operator==(T* other) const - { - return m_pointer == other; - } - - bool operator!=(T* other) const - { - return m_pointer != other; - } - - bool operator<(BoundsCheckedPointer other) const - { - return m_pointer < other.m_pointer; - } - - bool operator<=(BoundsCheckedPointer other) const - { - return m_pointer <= other.m_pointer; - } - - bool operator>(BoundsCheckedPointer other) const - { - return m_pointer > other.m_pointer; - } - - bool operator>=(BoundsCheckedPointer other) const - { - return m_pointer >= other.m_pointer; - } - - bool operator==(BoundsCheckedPointer other) const - { - return m_pointer == other.m_pointer; - } - - bool operator!=(BoundsCheckedPointer other) const - { - return m_pointer != other.m_pointer; - } - - BoundsCheckedPointer operator!() - { - return !m_pointer; - } - - T* get() - { - return m_pointer; - } - - T& operator*() - { - validate(); - return *m_pointer; - } - - const T& operator*() const - { - validate(); - return *m_pointer; - } - - T& operator[](ptrdiff_t index) - { - validate(m_pointer + index); - return m_pointer[index]; - } - - const T& operator[](ptrdiff_t index) const - { - validate(m_pointer + index); - return m_pointer[index]; - } - - // The only thing this has in common with strcat() is that it - // keeps appending from the given pointer until reaching 0. - BoundsCheckedPointer& strcat(const T* source) - { - while (*source) - *(*this)++ = *source++; - return *this; - } - -private: - void validate(T* pointer) const - { - ASSERT_UNUSED(pointer, pointer >= m_begin); - - // This guard is designed to protect against the misaligned case. - // A simple pointer < m_end would miss the case if, for example, - // T = int16_t and pointer is 1 byte less than m_end. - ASSERT_UNUSED(pointer, pointer + 1 <= m_end); - } - - void validate() const - { - validate(m_pointer); - } - - T* m_pointer; -#if !ASSERT_DISABLED - T* m_begin; - T* m_end; -#endif -}; - -} // namespace WTF - -using WTF::BoundsCheckedPointer; - -#endif // WTF_BoundsCheckedPointer_h diff --git a/Source/WTF/wtf/Box.h b/Source/WTF/wtf/Box.h new file mode 100644 index 000000000..b66132191 --- /dev/null +++ b/Source/WTF/wtf/Box.h @@ -0,0 +1,81 @@ +/* + * Copyright (C) 2015 Apple Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY + * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY + * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef WTF_Box_h +#define WTF_Box_h + +#include +#include + +namespace WTF { + +// Box is a reference-counted pointer to T that allocates T using FastMalloc and prepends a reference +// count to it. +template +class Box { +public: + Box() + { + } + + Box(std::nullptr_t) + { + } + + template + static Box create(Arguments&&... arguments) + { + Box result; + result.m_data = adoptRef(new Data(std::forward(arguments)...)); + return result; + } + + T* get() const { return &m_data->value; } + + T& operator*() const { return m_data->value; } + T* operator->() const { return &m_data->value; } + + explicit operator bool() { return m_data; } + +private: + struct Data : ThreadSafeRefCounted { + template + Data(Arguments&&... arguments) + : value(std::forward(arguments)...) + { + } + + T value; + }; + + RefPtr m_data; +}; + +} // namespace WTF + +using WTF::Box; + +#endif // WTF_Box_h + diff --git a/Source/WTF/wtf/Brigand.h b/Source/WTF/wtf/Brigand.h new file mode 100644 index 000000000..2000a8250 --- /dev/null +++ b/Source/WTF/wtf/Brigand.h @@ -0,0 +1,2489 @@ +// Brigand library +// +// Copyright (c) 2015 Edouard Alligand and Joel Falcou +// +// Boost Software License - Version 1.0 - August 17th, 2003 +// +// Permission is hereby granted, free of charge, to any person or organization +// obtaining a copy of the software and accompanying documentation covered by +// this license (the "Software") to use, reproduce, display, distribute, +// execute, and transmit the Software, and to prepare derivative works of the +// Software, and to permit third-parties to whom the Software is furnished to +// do so, all subject to the following: +// +// The copyright notices in the Software and this entire statement, including +// the above license grant, this restriction and the following disclaimer, +// must be included in all copies of the Software, in whole or in part, and +// all derivative works of the Software, unless such copies or derivative +// works are solely in the form of machine-executable object code generated by +// a source language processor. +// +// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +// FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT +// SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE +// FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE, +// ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER +// DEALINGS IN THE SOFTWARE. + +// This file contains a standalone version of Edouard Alligand and Joel Falcou's +// Brigand library, which can be found at https://github.com/edouarda/brigand + +#pragma once + +#if defined(_MSC_VER) && !defined(__GNUC__) && !defined(__clang__) +#define BRIGAND_COMP_MSVC +#if _MSC_VER == 1900 +#define BRIGAND_COMP_MSVC_2015 +#elif _MSC_VER == 1800 +#define BRIGAND_COMP_MSVC_2013 +#endif +#elif __GNUC__ +#ifndef __clang__ +#define BRIGAND_COMP_GCC +#else +#define BRIGAND_COMP_CLANG +#endif +#endif + +#define BRIGAND_NO_BOOST_SUPPORT 1 + +#include +#include +#include +#include +#include +#include +#include +#include + +#if !defined(BRIGAND_NO_BOOST_SUPPORT) +#include +#include +#include +#include +#include +#endif + +namespace brigand +{ + template struct list {}; + template + using integral_list = brigand::list< std::integral_constant...>; + using empty_sequence = brigand::list<>; +} +namespace brigand +{ + namespace lazy + { + template class B> struct wrap; + template class A, class... T, template class B> + struct wrap, B> + { + using type = B; + }; + } + template class B> + using wrap = typename lazy::wrap::type; +} +namespace brigand +{ +namespace detail +{ + template + struct append_impl + { + using type = brigand::empty_sequence; + }; + template + struct append_impl + { + using type = T; + }; + template