Diff
Modified: trunk/Source/_javascript_Core/ChangeLog (198374 => 198375)
--- trunk/Source/_javascript_Core/ChangeLog 2016-03-18 01:53:58 UTC (rev 198374)
+++ trunk/Source/_javascript_Core/ChangeLog 2016-03-18 02:11:31 UTC (rev 198375)
@@ -1,3 +1,35 @@
+2016-03-17 Saam barati <[email protected]>
+
+ Implement SmallPtrSet and integrate it into the Parser
+ https://bugs.webkit.org/show_bug.cgi?id=155552
+
+ Reviewed by Filip Pizlo.
+
+ Using SmallPtrSet instead of HashSet really helps speed
+ up the parser. What saves us most is not needing to always
+ malloc/free memory in the HashSet.
+
+ * parser/Parser.cpp:
+ (JSC::Parser<LexerType>::parseInner):
+ * parser/Parser.h:
+ (JSC::Scope::Scope):
+ (JSC::Scope::startSwitch):
+ (JSC::Scope::endSwitch):
+ (JSC::Scope::startLoop):
+ (JSC::Scope::hasDeclaredParameter):
+ (JSC::Scope::declareWrite):
+ (JSC::Scope::declareParameter):
+ (JSC::Scope::usedVariablesContains):
+ (JSC::Scope::useVariable):
+ (JSC::Scope::collectFreeVariables):
+ (JSC::Scope::getCapturedVars):
+ (JSC::Scope::isValidStrictMode):
+ (JSC::Scope::shadowsArguments):
+ (JSC::Scope::copyCapturedVariablesToVector):
+ (JSC::Scope::setIsModule):
+ (JSC::Parser::pushScope):
+ (JSC::Scope::getUsedVariables): Deleted.
+
2016-03-17 Brian Burg <[email protected]>
Web Inspector: protocol generator shouldn't generate enums for parameters with non-anonymous enum types
Modified: trunk/Source/_javascript_Core/parser/Parser.cpp (198374 => 198375)
--- trunk/Source/_javascript_Core/parser/Parser.cpp 2016-03-18 01:53:58 UTC (rev 198374)
+++ trunk/Source/_javascript_Core/parser/Parser.cpp 2016-03-18 02:11:31 UTC (rev 198375)
@@ -311,10 +311,8 @@
for (auto& entry : capturedVariables)
varDeclarations.markVariableAsCaptured(entry);
- IdentifierSet usedVariables;
- scope->getUsedVariables(usedVariables);
if (parseMode == SourceParseMode::GeneratorWrapperFunctionMode) {
- if (usedVariables.contains(m_vm->propertyNames->arguments.impl()))
+ if (scope->usedVariablesContains(m_vm->propertyNames->arguments.impl()))
context.propagateArgumentsUse();
}
Modified: trunk/Source/_javascript_Core/parser/Parser.h (198374 => 198375)
--- trunk/Source/_javascript_Core/parser/Parser.h 2016-03-18 01:53:58 UTC (rev 198374)
+++ trunk/Source/_javascript_Core/parser/Parser.h 2016-03-18 02:11:31 UTC (rev 198375)
@@ -40,13 +40,15 @@
#include <wtf/Forward.h>
#include <wtf/Noncopyable.h>
#include <wtf/RefPtr.h>
+#include <wtf/SmallPtrSet.h>
+
namespace JSC {
struct Scope;
}
namespace WTF {
-template <> struct VectorTraits<JSC::Scope> : SimpleClassVectorTraits {
- static const bool canInitializeWithMemset = false; // Not all Scope data members initialize to 0.
+template <> struct VectorTraits<JSC::Scope> : VectorTraitsBase</* is pod */ false, void> {
+ static const bool canMoveWithMemcpy = true;
};
}
@@ -60,6 +62,8 @@
class ProgramNode;
class SourceCode;
+typedef SmallPtrSet<UniquedStringImpl*> UniquedStringImplPtrSet;
+
// Macros to make the more common TreeBuilder types a little less verbose
#define TreeStatement typename TreeBuilder::Statement
#define TreeExpression typename TreeBuilder::_expression_
@@ -158,6 +162,9 @@
};
struct Scope {
+ WTF_MAKE_NONCOPYABLE(Scope);
+
+public:
Scope(const VM* vm, bool isFunction, bool isGenerator, bool strictMode, bool isArrowFunction)
: m_vm(vm)
, m_shadowsArguments(false)
@@ -186,43 +193,6 @@
{
}
- Scope(const Scope& rhs)
- : m_vm(rhs.m_vm)
- , m_shadowsArguments(rhs.m_shadowsArguments)
- , m_usesEval(rhs.m_usesEval)
- , m_needsFullActivation(rhs.m_needsFullActivation)
- , m_hasDirectSuper(rhs.m_hasDirectSuper)
- , m_needsSuperBinding(rhs.m_needsSuperBinding)
- , m_allowsVarDeclarations(rhs.m_allowsVarDeclarations)
- , m_allowsLexicalDeclarations(rhs.m_allowsLexicalDeclarations)
- , m_strictMode(rhs.m_strictMode)
- , m_isFunction(rhs.m_isFunction)
- , m_isGenerator(rhs.m_isGenerator)
- , m_isGeneratorBoundary(rhs.m_isGeneratorBoundary)
- , m_isArrowFunction(rhs.m_isArrowFunction)
- , m_isArrowFunctionBoundary(rhs.m_isArrowFunctionBoundary)
- , m_isLexicalScope(rhs.m_isLexicalScope)
- , m_isFunctionBoundary(rhs.m_isFunctionBoundary)
- , m_isValidStrictMode(rhs.m_isValidStrictMode)
- , m_hasArguments(rhs.m_hasArguments)
- , m_isEvalContext(rhs.m_isEvalContext)
- , m_constructorKind(rhs.m_constructorKind)
- , m_expectedSuperBinding(rhs.m_expectedSuperBinding)
- , m_loopDepth(rhs.m_loopDepth)
- , m_switchDepth(rhs.m_switchDepth)
- , m_innerArrowFunctionFeatures(rhs.m_innerArrowFunctionFeatures)
- , m_moduleScopeData(rhs.m_moduleScopeData)
- {
- if (rhs.m_labels) {
- m_labels = std::make_unique<LabelStack>();
-
- typedef LabelStack::const_iterator iterator;
- iterator end = rhs.m_labels->end();
- for (iterator it = rhs.m_labels->begin(); it != end; ++it)
- m_labels->append(ScopeLabelInfo { it->uid, it->isLoop });
- }
- }
-
void startSwitch() { m_switchDepth++; }
void endSwitch() { m_switchDepth--; }
void startLoop() { m_loopDepth++; }
@@ -454,7 +424,7 @@
bool hasDeclaredParameter(const RefPtr<UniquedStringImpl>& ident)
{
- return m_declaredParameters.contains(ident) || hasDeclaredVariable(ident);
+ return m_declaredParameters.contains(ident.get()) || hasDeclaredVariable(ident);
}
void declareWrite(const Identifier* ident)
@@ -492,11 +462,7 @@
return result;
}
- void getUsedVariables(IdentifierSet& usedVariables)
- {
- usedVariables.swap(m_usedVariables);
- }
-
+ bool usedVariablesContains(UniquedStringImpl* impl) const { return m_usedVariables.contains(impl); }
void useVariable(const Identifier* ident, bool isEval)
{
m_usesEval |= isEval;
@@ -548,7 +514,7 @@
m_usesEval = true;
{
- for (const RefPtr<UniquedStringImpl>& impl : nestedScope->m_usedVariables) {
+ for (UniquedStringImpl* impl : nestedScope->m_usedVariables) {
if (nestedScope->m_declaredVariables.contains(impl) || nestedScope->m_lexicalVariables.contains(impl))
continue;
@@ -573,11 +539,10 @@
}
if (nestedScope->m_writtenVariables.size()) {
- IdentifierSet::iterator end = nestedScope->m_writtenVariables.end();
- for (IdentifierSet::iterator ptr = nestedScope->m_writtenVariables.begin(); ptr != end; ++ptr) {
- if (nestedScope->m_declaredVariables.contains(*ptr) || nestedScope->m_lexicalVariables.contains(*ptr))
+ for (UniquedStringImpl* impl : nestedScope->m_writtenVariables) {
+ if (nestedScope->m_declaredVariables.contains(impl) || nestedScope->m_lexicalVariables.contains(impl))
continue;
- m_writtenVariables.add(*ptr);
+ m_writtenVariables.add(impl);
}
}
}
@@ -605,11 +570,10 @@
if (shadowsArguments())
modifiedArguments = true;
if (m_declaredParameters.size()) {
- IdentifierSet::iterator end = m_writtenVariables.end();
- for (IdentifierSet::iterator ptr = m_writtenVariables.begin(); ptr != end; ++ptr) {
- if (*ptr == m_vm->propertyNames->arguments.impl())
+ for (UniquedStringImpl* impl : m_writtenVariables) {
+ if (impl == m_vm->propertyNames->arguments.impl())
modifiedArguments = true;
- if (!m_declaredParameters.contains(*ptr))
+ if (!m_declaredParameters.contains(impl))
continue;
modifiedParameter = true;
break;
@@ -621,13 +585,12 @@
bool isValidStrictMode() const { return m_isValidStrictMode; }
bool shadowsArguments() const { return m_shadowsArguments; }
- void copyCapturedVariablesToVector(const IdentifierSet& capturedVariables, Vector<RefPtr<UniquedStringImpl>>& vector)
+ void copyCapturedVariablesToVector(const UniquedStringImplPtrSet& capturedVariables, Vector<RefPtr<UniquedStringImpl>>& vector)
{
- IdentifierSet::iterator end = capturedVariables.end();
- for (IdentifierSet::iterator it = capturedVariables.begin(); it != end; ++it) {
- if (m_declaredVariables.contains(*it) || m_lexicalVariables.contains(*it))
+ for (UniquedStringImpl* impl : capturedVariables) {
+ if (m_declaredVariables.contains(impl) || m_lexicalVariables.contains(impl))
continue;
- vector.append(*it);
+ vector.append(impl);
}
}
@@ -694,40 +657,43 @@
m_moduleScopeData = ModuleScopeData::create();
}
+ // All the fields in Scope must be able to use memcpy as their
+ // move operation. If you add a field that violates this, make sure
+ // to remove this comment and update WTF::VectorTraits<JSC::Scope>.
const VM* m_vm;
- bool m_shadowsArguments : 1;
- bool m_usesEval : 1;
- bool m_needsFullActivation : 1;
- bool m_hasDirectSuper : 1;
- bool m_needsSuperBinding : 1;
- bool m_allowsVarDeclarations : 1;
- bool m_allowsLexicalDeclarations : 1;
- bool m_strictMode : 1;
- bool m_isFunction : 1;
- bool m_isGenerator : 1;
- bool m_isGeneratorBoundary : 1;
- bool m_isArrowFunction : 1;
- bool m_isArrowFunctionBoundary : 1;
- bool m_isLexicalScope : 1;
- bool m_isFunctionBoundary : 1;
- bool m_isValidStrictMode : 1;
- bool m_hasArguments : 1;
- bool m_isEvalContext : 1;
- unsigned m_constructorKind : 2;
- unsigned m_expectedSuperBinding : 2;
+ bool m_shadowsArguments;
+ bool m_usesEval;
+ bool m_needsFullActivation;
+ bool m_hasDirectSuper;
+ bool m_needsSuperBinding;
+ bool m_allowsVarDeclarations;
+ bool m_allowsLexicalDeclarations;
+ bool m_strictMode;
+ bool m_isFunction;
+ bool m_isGenerator;
+ bool m_isGeneratorBoundary;
+ bool m_isArrowFunction;
+ bool m_isArrowFunctionBoundary;
+ bool m_isLexicalScope;
+ bool m_isFunctionBoundary;
+ bool m_isValidStrictMode;
+ bool m_hasArguments;
+ bool m_isEvalContext;
+ unsigned m_constructorKind;
+ unsigned m_expectedSuperBinding;
int m_loopDepth;
int m_switchDepth;
InnerArrowFunctionCodeFeatures m_innerArrowFunctionFeatures;
typedef Vector<ScopeLabelInfo, 2> LabelStack;
std::unique_ptr<LabelStack> m_labels;
- IdentifierSet m_declaredParameters;
+ UniquedStringImplPtrSet m_declaredParameters;
VariableEnvironment m_declaredVariables;
VariableEnvironment m_lexicalVariables;
- IdentifierSet m_usedVariables;
+ UniquedStringImplPtrSet m_usedVariables;
IdentifierSet m_closedVariableCandidates;
- IdentifierSet m_writtenVariables;
- RefPtr<ModuleScopeData> m_moduleScopeData { };
+ UniquedStringImplPtrSet m_writtenVariables;
+ RefPtr<ModuleScopeData> m_moduleScopeData;
DeclarationStacks::FunctionStack m_functionDeclarations;
};
@@ -1004,7 +970,7 @@
isGenerator = m_scopeStack.last().isGenerator();
isArrowFunction = m_scopeStack.last().isArrowFunction();
}
- m_scopeStack.append(Scope(m_vm, isFunction, isGenerator, isStrict, isArrowFunction));
+ m_scopeStack.constructAndAppend(m_vm, isFunction, isGenerator, isStrict, isArrowFunction);
return currentScope();
}
Modified: trunk/Source/WTF/ChangeLog (198374 => 198375)
--- trunk/Source/WTF/ChangeLog 2016-03-18 01:53:58 UTC (rev 198374)
+++ trunk/Source/WTF/ChangeLog 2016-03-18 02:11:31 UTC (rev 198375)
@@ -1,3 +1,66 @@
+2016-03-17 Saam barati <[email protected]>
+
+ Implement SmallPtrSet and integrate it into the Parser
+ https://bugs.webkit.org/show_bug.cgi?id=155552
+
+ Reviewed by Filip Pizlo.
+
+ This patch implements the SmallPtrSet data struture.
+ Inspired by the implementation in llvm:
+ http://llvm.org/docs/doxygen/html/SmallPtrSet_8h_source.html
+
+ The data structure uses an inline array for storage up until
+ a fixed limit (8 entries in our implementation). If that storage
+ fills up, we fall back to a simple hash table implementation.
+ Crucially, this implementation doesn't support the remove
+ operation. This is on purpose. The hash table will only ever
+ grow.
+
+ Also, the implementation allows for it to be memcopied around.
+ I.e, we can put SmallPtrSet inside a Vector and allow that
+ Vector to use memcpy as its move operation (of course this
+ is only valid if the SmallPtrSet in the old memory doesn't have
+ its destructor called unless it is set back to its initial state.)
+
+ For now, SmallPtrSet only supports pointer types that are trivially
+ destructible. It's probably not too difficult to extend this to
+ smart pointers, but it's not part of this original implementation.
+
+ I've also implemented a pure forwarding varargs constructAndAppend
+ method on Vector. This allows you to do:
+ Vector<T> v;
+ v.constructAndAppend(a1, a2, ...)
+ as long as T has a constructor that accepts arguments (a1, a2, ...).
+
+ * WTF.xcodeproj/project.pbxproj:
+ * wtf/CMakeLists.txt:
+ * wtf/SmallPtrSet.h: Added.
+ (WTF::SmallPtrSet::SmallPtrSet):
+ (WTF::SmallPtrSet::operator=):
+ (WTF::SmallPtrSet::~SmallPtrSet):
+ (WTF::SmallPtrSet::add):
+ (WTF::SmallPtrSet::contains):
+ (WTF::SmallPtrSet::iterator::operator++):
+ (WTF::SmallPtrSet::iterator::operator*):
+ (WTF::SmallPtrSet::iterator::operator==):
+ (WTF::SmallPtrSet::iterator::operator!=):
+ (WTF::SmallPtrSet::begin):
+ (WTF::SmallPtrSet::end):
+ (WTF::SmallPtrSet::size):
+ (WTF::SmallPtrSet::emptyValue):
+ (WTF::SmallPtrSet::isValidEntry):
+ (WTF::SmallPtrSet::isSmall):
+ (WTF::SmallPtrSet::initialize):
+ (WTF::SmallPtrSet::grow):
+ (WTF::SmallPtrSet::bucket):
+ * wtf/Vector.h:
+ (WTF::Vector::append):
+ (WTF::Vector::uncheckedAppend):
+ (WTF::minCapacity>::append):
+ (WTF::minCapacity>::constructAndAppend):
+ (WTF::minCapacity>::appendSlowCase):
+ (WTF::minCapacity>::constructAndAppendSlowCase):
+
2016-03-16 Filip Pizlo <[email protected]>
Replace all of the various non-working and non-compiling sampling profiler hacks with a single super hack
Modified: trunk/Source/WTF/WTF.xcodeproj/project.pbxproj (198374 => 198375)
--- trunk/Source/WTF/WTF.xcodeproj/project.pbxproj 2016-03-18 01:53:58 UTC (rev 198374)
+++ trunk/Source/WTF/WTF.xcodeproj/project.pbxproj 2016-03-18 02:11:31 UTC (rev 198375)
@@ -106,6 +106,7 @@
70ECA60D1B02426800449739 /* AtomicStringImpl.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 70ECA60A1B02426800449739 /* AtomicStringImpl.cpp */; };
70ECA60E1B02426800449739 /* SymbolImpl.h in Headers */ = {isa = PBXBuildFile; fileRef = 70ECA60B1B02426800449739 /* SymbolImpl.h */; };
70ECA60F1B02426800449739 /* UniquedStringImpl.h in Headers */ = {isa = PBXBuildFile; fileRef = 70ECA60C1B02426800449739 /* UniquedStringImpl.h */; };
+ 79EC70611C99F9BC003A3AE2 /* SmallPtrSet.h in Headers */ = {isa = PBXBuildFile; fileRef = 7936D6A91C99F8AE000D1AED /* SmallPtrSet.h */; };
7CBBA07419BB7FDC00BBF025 /* OSObjectPtr.h in Headers */ = {isa = PBXBuildFile; fileRef = 7CBBA07319BB7FDC00BBF025 /* OSObjectPtr.h */; };
7CDD7FF8186D291E007433CD /* IteratorAdaptors.h in Headers */ = {isa = PBXBuildFile; fileRef = 7CDD7FF7186D291E007433CD /* IteratorAdaptors.h */; };
7CDD7FFA186D2A54007433CD /* IteratorRange.h in Headers */ = {isa = PBXBuildFile; fileRef = 7CDD7FF9186D2A54007433CD /* IteratorRange.h */; };
@@ -421,6 +422,7 @@
70ECA60A1B02426800449739 /* AtomicStringImpl.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = AtomicStringImpl.cpp; sourceTree = "<group>"; };
70ECA60B1B02426800449739 /* SymbolImpl.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SymbolImpl.h; sourceTree = "<group>"; };
70ECA60C1B02426800449739 /* UniquedStringImpl.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = UniquedStringImpl.h; sourceTree = "<group>"; };
+ 7936D6A91C99F8AE000D1AED /* SmallPtrSet.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SmallPtrSet.h; sourceTree = "<group>"; };
7CBBA07319BB7FDC00BBF025 /* OSObjectPtr.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = OSObjectPtr.h; sourceTree = "<group>"; };
7CDD7FF7186D291E007433CD /* IteratorAdaptors.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = IteratorAdaptors.h; sourceTree = "<group>"; };
7CDD7FF9186D2A54007433CD /* IteratorRange.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = IteratorRange.h; sourceTree = "<group>"; };
@@ -914,6 +916,7 @@
A748744F17A0BDAE00FA04CB /* SixCharacterHash.cpp */,
A748745017A0BDAE00FA04CB /* SixCharacterHash.h */,
A8A4730C151A825B004123FF /* SizeLimits.cpp */,
+ 7936D6A91C99F8AE000D1AED /* SmallPtrSet.h */,
A8A4730D151A825B004123FF /* Spectrum.h */,
A8A4730E151A825B004123FF /* StackBounds.cpp */,
A8A4730F151A825B004123FF /* StackBounds.h */,
@@ -1150,6 +1153,7 @@
A8A47395151A825B004123FF /* CheckedBoolean.h in Headers */,
A8A4745F151A825B004123FF /* Collator.h in Headers */,
0FC4EDE61696149600F65041 /* CommaPrinter.h in Headers */,
+ 79EC70611C99F9BC003A3AE2 /* SmallPtrSet.h in Headers */,
DE5A09FC1BA36992003D4424 /* CommonCryptoSPI.h in Headers */,
0F8F2B91172E00FC007DBDA5 /* CompilationThread.h in Headers */,
A8A47398151A825B004123FF /* Compiler.h in Headers */,
Modified: trunk/Source/WTF/wtf/CMakeLists.txt (198374 => 198375)
--- trunk/Source/WTF/wtf/CMakeLists.txt 2016-03-18 01:53:58 UTC (rev 198374)
+++ trunk/Source/WTF/wtf/CMakeLists.txt 2016-03-18 02:11:31 UTC (rev 198375)
@@ -94,6 +94,7 @@
SaturatedArithmetic.h
ScopedLambda.h
SegmentedVector.h
+ SmallPtrSet.h
StackBounds.h
StackStats.h
StaticConstructors.h
Added: trunk/Source/WTF/wtf/SmallPtrSet.h (0 => 198375)
--- trunk/Source/WTF/wtf/SmallPtrSet.h (rev 0)
+++ trunk/Source/WTF/wtf/SmallPtrSet.h 2016-03-18 02:11:31 UTC (rev 198375)
@@ -0,0 +1,253 @@
+/*
+ * 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 SmallPtrSet_h
+#define SmallPtrSet_h
+
+#include <wtf/Assertions.h>
+#include <wtf/FastMalloc.h>
+#include <wtf/HashFunctions.h>
+#include <wtf/Noncopyable.h>
+
+namespace WTF {
+
+template<typename PtrType>
+class SmallPtrSet {
+ WTF_MAKE_NONCOPYABLE(SmallPtrSet);
+ static_assert(std::is_trivially_destructible<PtrType>::value, "We currently don't support non-trivially destructible pointer types.");
+ static_assert(sizeof(PtrType) == sizeof(void*), "Only support pointer sized things.");
+
+public:
+ SmallPtrSet()
+ {
+ initialize();
+ }
+
+ // We take care to have SmallPtrSet have partial move semantics allowable through
+ // memcpy. It's partial move semantics because our destructor should not be called
+ // on the SmallPtrObject in the old memory we were moved from (otherwise, we might free m_buffer twice)
+ // unless that old memory is reset to be isSmall(). See move constructor below.
+ // To maintain these semantics, we determine if we're small by checking our size
+ // and not our m_buffer pointer. And when we're small, we don't do operations on
+ // m_buffer, instead, we perform operations on m_smallStorage directly. The reason we want
+ // these semantics is that it's beneficial to have a Vector that contains SmallPtrSet
+ // (or an object with SmallPtrSet as a field) be allowed to use memcpy for its move operation.
+
+ SmallPtrSet(SmallPtrSet&& other)
+ {
+ *this = WTFMove(other);
+ }
+
+ SmallPtrSet& operator=(SmallPtrSet&& other)
+ {
+ memcpy(this, &other, sizeof(SmallPtrSet));
+ other.initialize();
+ return *this;
+ }
+
+ ~SmallPtrSet()
+ {
+ if (!isSmall())
+ fastFree(m_buffer);
+ }
+
+ inline void add(PtrType ptr)
+ {
+ ASSERT(isValidEntry(ptr));
+
+ if (isSmall()) {
+ for (unsigned i = 0; i < m_size; i++) {
+ if (m_smallStorage[i] == ptr)
+ return;
+ }
+
+ if (m_size < SmallArraySize) {
+ m_smallStorage[m_size] = ptr;
+ ++m_size;
+ return;
+ }
+
+ grow(64);
+ // Fall through. We're no longer small :(
+ }
+
+ // If we're more than 3/4ths full we grow.
+ if (UNLIKELY(m_size * 4 >= m_capacity * 3)) {
+ grow(m_capacity * 2);
+ ASSERT(!(m_capacity & (m_capacity - 1)));
+ }
+
+ void** bucket = this->bucket(ptr);
+ if (*bucket != ptr) {
+ *bucket = ptr;
+ ++m_size;
+ }
+ }
+
+ inline bool contains(PtrType ptr) const
+ {
+ ASSERT(isValidEntry(ptr));
+ if (isSmall()) {
+ for (unsigned i = 0; i < m_size; i++) { // We only need to search up to m_size because we store things linearly inside m_smallStorage.
+ if (m_smallStorage[i] == ptr)
+ return true;
+ }
+ return false;
+ }
+
+ void** bucket = this->bucket(ptr);
+ return *bucket == ptr;
+ }
+
+ class iterator {
+ public:
+ iterator& operator++()
+ {
+ m_index++;
+ ASSERT(m_index <= m_capacity);
+ while (m_index < m_capacity && m_buffer[m_index] == emptyValue())
+ m_index++;
+ return *this;
+ }
+
+ PtrType operator*() const { ASSERT(m_index < m_capacity); return static_cast<PtrType>(m_buffer[m_index]); }
+ bool operator==(const iterator& other) const { ASSERT(m_buffer == other.m_buffer); return m_index == other.m_index; }
+ bool operator!=(const iterator& other) const { ASSERT(m_buffer == other.m_buffer); return !(*this == other); }
+
+ private:
+ template<typename U> friend class WTF::SmallPtrSet;
+ unsigned m_index;
+ unsigned m_capacity;
+ void** m_buffer;
+ };
+
+ iterator begin() const
+ {
+ iterator it;
+ it.m_index = -1;
+ it.m_capacity = m_capacity;
+ if (isSmall())
+ it.m_buffer = const_cast<void**>(m_smallStorage);
+ else
+ it.m_buffer = m_buffer;
+
+ ++it;
+
+ return it;
+ }
+
+ iterator end() const
+ {
+ iterator it;
+ it.m_index = m_capacity;
+ it.m_capacity = m_capacity;
+ if (isSmall())
+ it.m_buffer = const_cast<void**>(m_smallStorage);
+ else
+ it.m_buffer = m_buffer;
+
+ return it;
+ }
+
+ inline unsigned size() const { return m_size; }
+
+private:
+ constexpr static void* emptyValue()
+ {
+ return bitwise_cast<void*>(std::numeric_limits<uintptr_t>::max());
+ }
+
+ bool isValidEntry(const PtrType ptr) const
+ {
+ return ptr != emptyValue();
+ }
+
+ inline bool isSmall() const
+ {
+ return m_capacity == SmallArraySize;
+ }
+
+ inline void initialize()
+ {
+ m_size = 0;
+ m_buffer = nullptr;
+ m_capacity = SmallArraySize;
+ memset(m_smallStorage, -1, sizeof(void*) * SmallArraySize);
+ ASSERT(isSmall());
+ }
+
+ inline void grow(unsigned size)
+ {
+ ASSERT(static_cast<int32_t>(bitwise_cast<intptr_t>(emptyValue())) == -1);
+
+ size_t allocationSize = sizeof(void*) * size;
+ bool wasSmall = isSmall();
+ void** oldBuffer = wasSmall ? m_smallStorage : m_buffer;
+ unsigned oldCapacity = m_capacity;
+ m_buffer = static_cast<void**>(fastMalloc(allocationSize));
+ memset(m_buffer, -1, allocationSize);
+ m_capacity = size;
+
+ for (unsigned i = 0; i < oldCapacity; i++) {
+ if (oldBuffer[i] != emptyValue()) {
+ void** ptr = this->bucket(static_cast<PtrType>(oldBuffer[i]));
+ *ptr = oldBuffer[i];
+ }
+ }
+
+ if (!wasSmall)
+ fastFree(oldBuffer);
+ }
+
+
+ inline void** bucket(PtrType target) const
+ {
+ ASSERT(!(m_capacity & (m_capacity - 1)));
+ unsigned bucket = PtrHashBase<PtrType, false /* isSmartPtr */>::hash(target) & (m_capacity - 1);
+ unsigned index = 0;
+ while (true) {
+ void** ptr = m_buffer + bucket;
+ if (*ptr == emptyValue())
+ return ptr;
+ if (*ptr == target)
+ return ptr;
+ index++;
+ bucket = (bucket + index) & (m_capacity - 1);
+ }
+ }
+
+ static const unsigned SmallArraySize = 8;
+
+ unsigned m_size;
+ unsigned m_capacity;
+ void** m_buffer;
+ void* m_smallStorage[SmallArraySize];
+};
+
+} // namespace WTF
+
+using WTF::SmallPtrSet;
+
+#endif // SmallPtrSet_h
Modified: trunk/Source/WTF/wtf/Vector.h (198374 => 198375)
--- trunk/Source/WTF/wtf/Vector.h 2016-03-18 01:53:58 UTC (rev 198374)
+++ trunk/Source/WTF/wtf/Vector.h 2016-03-18 02:11:31 UTC (rev 198375)
@@ -725,6 +725,7 @@
void append(ValueType&& value) { append<ValueType>(std::forward<ValueType>(value)); }
template<typename U> void append(U&&);
+ template<typename... Args> void constructAndAppend(Args&&...);
void uncheckedAppend(ValueType&& value) { uncheckedAppend<ValueType>(std::forward<ValueType>(value)); }
template<typename U> void uncheckedAppend(U&&);
@@ -787,6 +788,7 @@
const T* tryExpandCapacity(size_t newMinCapacity, const T*);
template<typename U> U* expandCapacity(size_t newMinCapacity, U*);
template<typename U> void appendSlowCase(U&&);
+ template<typename... Args> void constructAndAppendSlowCase(Args&&...);
void asanSetInitialBufferSizeTo(size_t);
void asanSetBufferSizeToFullCapacity();
@@ -1214,6 +1216,19 @@
appendSlowCase(std::forward<U>(value));
}
+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename... Args>
+ALWAYS_INLINE void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::constructAndAppend(Args&&... args)
+{
+ if (size() != capacity()) {
+ asanBufferSizeWillChangeTo(m_size + 1);
+ new (NotNull, end()) T(std::forward<Args>(args)...);
+ ++m_size;
+ return;
+ }
+
+ constructAndAppendSlowCase(std::forward<Args>(args)...);
+}
+
template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename U>
void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::appendSlowCase(U&& value)
{
@@ -1228,6 +1243,19 @@
++m_size;
}
+template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename... Args>
+void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::constructAndAppendSlowCase(Args&&... args)
+{
+ ASSERT(size() == capacity());
+
+ expandCapacity(size() + 1);
+ ASSERT(begin());
+
+ asanBufferSizeWillChangeTo(m_size + 1);
+ new (NotNull, end()) T(std::forward<Args>(args)...);
+ ++m_size;
+}
+
// This version of append saves a branch in the case where you know that the
// vector's capacity is large enough for the append to succeed.
