The tiny set magic in StructureSet should be available in WTF
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 8 Jun 2015 19:41:47 +0000 (19:41 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 8 Jun 2015 19:41:47 +0000 (19:41 +0000)
https://bugs.webkit.org/show_bug.cgi?id=145722

Reviewed by Geoffrey Garen.

Source/JavaScriptCore:

I moved the generic logic of small sets of pointers and moved it into WTF. Now,
StructureSet is a subclass of TinyPtrSet<Structure*>. There shouldn't be any functional
change.

* bytecode/StructureSet.cpp:
(JSC::StructureSet::filter):
(JSC::StructureSet::filterArrayModes):
(JSC::StructureSet::speculationFromStructures):
(JSC::StructureSet::arrayModesFromStructures):
(JSC::StructureSet::dumpInContext):
(JSC::StructureSet::dump):
(JSC::StructureSet::clear): Deleted.
(JSC::StructureSet::add): Deleted.
(JSC::StructureSet::remove): Deleted.
(JSC::StructureSet::contains): Deleted.
(JSC::StructureSet::merge): Deleted.
(JSC::StructureSet::exclude): Deleted.
(JSC::StructureSet::isSubsetOf): Deleted.
(JSC::StructureSet::overlaps): Deleted.
(JSC::StructureSet::operator==): Deleted.
(JSC::StructureSet::addOutOfLine): Deleted.
(JSC::StructureSet::containsOutOfLine): Deleted.
(JSC::StructureSet::copyFromOutOfLine): Deleted.
(JSC::StructureSet::OutOfLineList::create): Deleted.
(JSC::StructureSet::OutOfLineList::destroy): Deleted.
* bytecode/StructureSet.h:
(JSC::StructureSet::onlyStructure):
(JSC::StructureSet::StructureSet): Deleted.
(JSC::StructureSet::operator=): Deleted.
(JSC::StructureSet::~StructureSet): Deleted.
(JSC::StructureSet::isEmpty): Deleted.
(JSC::StructureSet::genericFilter): Deleted.
(JSC::StructureSet::isSupersetOf): Deleted.
(JSC::StructureSet::size): Deleted.
(JSC::StructureSet::at): Deleted.
(JSC::StructureSet::operator[]): Deleted.
(JSC::StructureSet::last): Deleted.
(JSC::StructureSet::iterator::iterator): Deleted.
(JSC::StructureSet::iterator::operator*): Deleted.
(JSC::StructureSet::iterator::operator++): Deleted.
(JSC::StructureSet::iterator::operator==): Deleted.
(JSC::StructureSet::iterator::operator!=): Deleted.
(JSC::StructureSet::begin): Deleted.
(JSC::StructureSet::end): Deleted.
(JSC::StructureSet::ContainsOutOfLine::ContainsOutOfLine): Deleted.
(JSC::StructureSet::ContainsOutOfLine::operator()): Deleted.
(JSC::StructureSet::copyFrom): Deleted.
(JSC::StructureSet::OutOfLineList::list): Deleted.
(JSC::StructureSet::OutOfLineList::OutOfLineList): Deleted.
(JSC::StructureSet::deleteStructureListIfNecessary): Deleted.
(JSC::StructureSet::isThin): Deleted.
(JSC::StructureSet::pointer): Deleted.
(JSC::StructureSet::singleStructure): Deleted.
(JSC::StructureSet::structureList): Deleted.
(JSC::StructureSet::set): Deleted.
(JSC::StructureSet::setEmpty): Deleted.
(JSC::StructureSet::getReservedFlag): Deleted.
(JSC::StructureSet::setReservedFlag): Deleted.
* dfg/DFGStructureAbstractValue.cpp:
(JSC::DFG::StructureAbstractValue::clobber):
(JSC::DFG::StructureAbstractValue::filter):
(JSC::DFG::StructureAbstractValue::filterSlow):
(JSC::DFG::StructureAbstractValue::contains):
* dfg/DFGStructureAbstractValue.h:
(JSC::DFG::StructureAbstractValue::makeTop):

Source/WTF:

As the management of structure sets evolved in JSC, the StructureSet data structure grew
increasingly smart. It's got some smart stuff for managing small sets of pointers. I
wanted to take the generic logic out of JSC and put it into a reusable templatized class
in WTF.

* WTF.vcxproj/WTF.vcxproj:
* WTF.xcodeproj/project.pbxproj:
* wtf/CMakeLists.txt:
* wtf/TinyPtrSet.h: Added.
(WTF::TinyPtrSet::TinyPtrSet):
(WTF::TinyPtrSet::operator=):
(WTF::TinyPtrSet::~TinyPtrSet):
(WTF::TinyPtrSet::clear):
(WTF::TinyPtrSet::onlyEntry):
(WTF::TinyPtrSet::isEmpty):
(WTF::TinyPtrSet::add):
(WTF::TinyPtrSet::remove):
(WTF::TinyPtrSet::contains):
(WTF::TinyPtrSet::merge):
(WTF::TinyPtrSet::forEach):
(WTF::TinyPtrSet::genericFilter):
(WTF::TinyPtrSet::filter):
(WTF::TinyPtrSet::exclude):
(WTF::TinyPtrSet::isSubsetOf):
(WTF::TinyPtrSet::isSupersetOf):
(WTF::TinyPtrSet::overlaps):
(WTF::TinyPtrSet::size):
(WTF::TinyPtrSet::at):
(WTF::TinyPtrSet::operator[]):
(WTF::TinyPtrSet::last):
(WTF::TinyPtrSet::iterator::iterator):
(WTF::TinyPtrSet::iterator::operator*):
(WTF::TinyPtrSet::iterator::operator++):
(WTF::TinyPtrSet::iterator::operator==):
(WTF::TinyPtrSet::iterator::operator!=):
(WTF::TinyPtrSet::begin):
(WTF::TinyPtrSet::end):
(WTF::TinyPtrSet::operator==):
(WTF::TinyPtrSet::addOutOfLine):
(WTF::TinyPtrSet::containsOutOfLine):
(WTF::TinyPtrSet::copyFrom):
(WTF::TinyPtrSet::copyFromOutOfLine):
(WTF::TinyPtrSet::OutOfLineList::create):
(WTF::TinyPtrSet::OutOfLineList::destroy):
(WTF::TinyPtrSet::OutOfLineList::list):
(WTF::TinyPtrSet::OutOfLineList::OutOfLineList):
(WTF::TinyPtrSet::deleteListIfNecessary):
(WTF::TinyPtrSet::isThin):
(WTF::TinyPtrSet::pointer):
(WTF::TinyPtrSet::singleEntry):
(WTF::TinyPtrSet::list):
(WTF::TinyPtrSet::set):
(WTF::TinyPtrSet::setEmpty):
(WTF::TinyPtrSet::getReservedFlag):
(WTF::TinyPtrSet::setReservedFlag):

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@185324 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/bytecode/StructureSet.cpp
Source/JavaScriptCore/bytecode/StructureSet.h
Source/JavaScriptCore/dfg/DFGStructureAbstractValue.cpp
Source/JavaScriptCore/dfg/DFGStructureAbstractValue.h
Source/WTF/ChangeLog
Source/WTF/WTF.vcxproj/WTF.vcxproj
Source/WTF/WTF.xcodeproj/project.pbxproj
Source/WTF/wtf/CMakeLists.txt
Source/WTF/wtf/TinyPtrSet.h [new file with mode: 0644]

index 55e07da..ed7b1ae 100644 (file)
@@ -1,3 +1,76 @@
+2015-06-07  Filip Pizlo  <fpizlo@apple.com>
+
+        The tiny set magic in StructureSet should be available in WTF
+        https://bugs.webkit.org/show_bug.cgi?id=145722
+
+        Reviewed by Geoffrey Garen.
+        
+        I moved the generic logic of small sets of pointers and moved it into WTF. Now,
+        StructureSet is a subclass of TinyPtrSet<Structure*>. There shouldn't be any functional
+        change.
+
+        * bytecode/StructureSet.cpp:
+        (JSC::StructureSet::filter):
+        (JSC::StructureSet::filterArrayModes):
+        (JSC::StructureSet::speculationFromStructures):
+        (JSC::StructureSet::arrayModesFromStructures):
+        (JSC::StructureSet::dumpInContext):
+        (JSC::StructureSet::dump):
+        (JSC::StructureSet::clear): Deleted.
+        (JSC::StructureSet::add): Deleted.
+        (JSC::StructureSet::remove): Deleted.
+        (JSC::StructureSet::contains): Deleted.
+        (JSC::StructureSet::merge): Deleted.
+        (JSC::StructureSet::exclude): Deleted.
+        (JSC::StructureSet::isSubsetOf): Deleted.
+        (JSC::StructureSet::overlaps): Deleted.
+        (JSC::StructureSet::operator==): Deleted.
+        (JSC::StructureSet::addOutOfLine): Deleted.
+        (JSC::StructureSet::containsOutOfLine): Deleted.
+        (JSC::StructureSet::copyFromOutOfLine): Deleted.
+        (JSC::StructureSet::OutOfLineList::create): Deleted.
+        (JSC::StructureSet::OutOfLineList::destroy): Deleted.
+        * bytecode/StructureSet.h:
+        (JSC::StructureSet::onlyStructure):
+        (JSC::StructureSet::StructureSet): Deleted.
+        (JSC::StructureSet::operator=): Deleted.
+        (JSC::StructureSet::~StructureSet): Deleted.
+        (JSC::StructureSet::isEmpty): Deleted.
+        (JSC::StructureSet::genericFilter): Deleted.
+        (JSC::StructureSet::isSupersetOf): Deleted.
+        (JSC::StructureSet::size): Deleted.
+        (JSC::StructureSet::at): Deleted.
+        (JSC::StructureSet::operator[]): Deleted.
+        (JSC::StructureSet::last): Deleted.
+        (JSC::StructureSet::iterator::iterator): Deleted.
+        (JSC::StructureSet::iterator::operator*): Deleted.
+        (JSC::StructureSet::iterator::operator++): Deleted.
+        (JSC::StructureSet::iterator::operator==): Deleted.
+        (JSC::StructureSet::iterator::operator!=): Deleted.
+        (JSC::StructureSet::begin): Deleted.
+        (JSC::StructureSet::end): Deleted.
+        (JSC::StructureSet::ContainsOutOfLine::ContainsOutOfLine): Deleted.
+        (JSC::StructureSet::ContainsOutOfLine::operator()): Deleted.
+        (JSC::StructureSet::copyFrom): Deleted.
+        (JSC::StructureSet::OutOfLineList::list): Deleted.
+        (JSC::StructureSet::OutOfLineList::OutOfLineList): Deleted.
+        (JSC::StructureSet::deleteStructureListIfNecessary): Deleted.
+        (JSC::StructureSet::isThin): Deleted.
+        (JSC::StructureSet::pointer): Deleted.
+        (JSC::StructureSet::singleStructure): Deleted.
+        (JSC::StructureSet::structureList): Deleted.
+        (JSC::StructureSet::set): Deleted.
+        (JSC::StructureSet::setEmpty): Deleted.
+        (JSC::StructureSet::getReservedFlag): Deleted.
+        (JSC::StructureSet::setReservedFlag): Deleted.
+        * dfg/DFGStructureAbstractValue.cpp:
+        (JSC::DFG::StructureAbstractValue::clobber):
+        (JSC::DFG::StructureAbstractValue::filter):
+        (JSC::DFG::StructureAbstractValue::filterSlow):
+        (JSC::DFG::StructureAbstractValue::contains):
+        * dfg/DFGStructureAbstractValue.h:
+        (JSC::DFG::StructureAbstractValue::makeTop):
+
 2015-06-08  Csaba Osztrogon√°c  <ossy@webkit.org>
 
         [ARM] Add the missing setupArgumentsWithExecState functions after r185240
index 3d2c109..55fdb7d 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2014 Apple Inc. All rights reserved.
+ * Copyright (C) 2014, 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
 
 namespace JSC {
 
-void StructureSet::clear()
-{
-    deleteStructureListIfNecessary();
-    setEmpty();
-}
-
-bool StructureSet::add(Structure* structure)
-{
-    ASSERT(structure);
-    if (isThin()) {
-        if (singleStructure() == structure)
-            return false;
-        if (!singleStructure()) {
-            set(structure);
-            return true;
-        }
-        OutOfLineList* list = OutOfLineList::create(defaultStartingSize);
-        list->m_length = 2;
-        list->list()[0] = singleStructure();
-        list->list()[1] = structure;
-        set(list);
-        return true;
-    }
-    
-    return addOutOfLine(structure);
-}
-
-bool StructureSet::remove(Structure* structure)
-{
-    if (isThin()) {
-        if (singleStructure() == structure) {
-            setEmpty();
-            return true;
-        }
-        return false;
-    }
-    
-    OutOfLineList* list = structureList();
-    for (unsigned i = 0; i < list->m_length; ++i) {
-        if (list->list()[i] != structure)
-            continue;
-        list->list()[i] = list->list()[--list->m_length];
-        if (!list->m_length) {
-            OutOfLineList::destroy(list);
-            setEmpty();
-        }
-        return true;
-    }
-    return false;
-}
-
-bool StructureSet::contains(Structure* structure) const
-{
-    if (isThin())
-        return singleStructure() == structure;
-
-    return containsOutOfLine(structure);
-}
-
-bool StructureSet::merge(const StructureSet& other)
-{
-    if (other.isThin()) {
-        if (other.singleStructure())
-            return add(other.singleStructure());
-        return false;
-    }
-    
-    OutOfLineList* list = other.structureList();
-    if (list->m_length >= 2) {
-        if (isThin()) {
-            OutOfLineList* myNewList = OutOfLineList::create(
-                list->m_length + !!singleStructure());
-            if (singleStructure()) {
-                myNewList->m_length = 1;
-                myNewList->list()[0] = singleStructure();
-            }
-            set(myNewList);
-        }
-        bool changed = false;
-        for (unsigned i = 0; i < list->m_length; ++i)
-            changed |= addOutOfLine(list->list()[i]);
-        return changed;
-    }
-    
-    ASSERT(list->m_length);
-    return add(list->list()[0]);
-}
-
-void StructureSet::filter(const StructureSet& other)
-{
-    if (other.isThin()) {
-        if (!other.singleStructure() || !contains(other.singleStructure()))
-            clear();
-        else {
-            clear();
-            set(other.singleStructure());
-        }
-        return;
-    }
-    
-    ContainsOutOfLine containsOutOfLine(other);
-    genericFilter(containsOutOfLine);
-}
-
-void StructureSet::exclude(const StructureSet& other)
-{
-    if (other.isThin()) {
-        if (other.singleStructure())
-            remove(other.singleStructure());
-        return;
-    }
-    
-    if (isThin()) {
-        if (!singleStructure())
-            return;
-        if (other.contains(singleStructure()))
-            clear();
-        return;
-    }
-    
-    OutOfLineList* list = structureList();
-    for (unsigned i = 0; i < list->m_length; ++i) {
-        if (!other.containsOutOfLine(list->list()[i]))
-            continue;
-        list->list()[i--] = list->list()[--list->m_length];
-    }
-    if (!list->m_length)
-        clear();
-}
-
 #if ENABLE(DFG_JIT)
 
-namespace {
-
-class StructureAbstractValueContains {
-public:
-    StructureAbstractValueContains(const DFG::StructureAbstractValue& value)
-        : m_value(value)
-    {
-    }
-    
-    bool operator()(Structure* structure)
-    {
-        return m_value.contains(structure);
-    }
-private:
-    const DFG::StructureAbstractValue& m_value;
-};
-
-class SpeculatedTypeContains {
-public:
-    SpeculatedTypeContains(SpeculatedType type)
-        : m_type(type)
-    {
-    }
-    
-    bool operator()(Structure* structure)
-    {
-        return m_type & speculationFromStructure(structure);
-    }
-private:
-    SpeculatedType m_type;
-};
-
-class ArrayModesContains {
-public:
-    ArrayModesContains(ArrayModes arrayModes)
-        : m_arrayModes(arrayModes)
-    {
-    }
-    
-    bool operator()(Structure* structure)
-    {
-        return m_arrayModes & arrayModeFromStructure(structure);
-    }
-private:
-    ArrayModes m_arrayModes;
-};
-
-} // anonymous namespace
-
 void StructureSet::filter(const DFG::StructureAbstractValue& other)
 {
-    StructureAbstractValueContains functor(other);
-    genericFilter(functor);
+    genericFilter([&] (Structure* structure) -> bool { return other.contains(structure); });
 }
 
 void StructureSet::filter(SpeculatedType type)
 {
-    SpeculatedTypeContains functor(type);
-    genericFilter(functor);
+    genericFilter(
+        [&] (Structure* structure) -> bool {
+            return type & speculationFromStructure(structure);
+        });
 }
 
 void StructureSet::filterArrayModes(ArrayModes arrayModes)
 {
-    ArrayModesContains functor(arrayModes);
-    genericFilter(functor);
+    genericFilter(
+        [&] (Structure* structure) -> bool {
+            return arrayModes & arrayModeFromStructure(structure);
+        });
 }
 
 void StructureSet::filter(const DFG::AbstractValue& other)
@@ -239,89 +63,23 @@ void StructureSet::filter(const DFG::AbstractValue& other)
 
 #endif // ENABLE(DFG_JIT)
 
-bool StructureSet::isSubsetOf(const StructureSet& other) const
-{
-    if (isThin()) {
-        if (!singleStructure())
-            return true;
-        return other.contains(singleStructure());
-    }
-    
-    if (other.isThin()) {
-        if (!other.singleStructure())
-            return false;
-        OutOfLineList* list = structureList();
-        if (list->m_length >= 2)
-            return false;
-        if (list->list()[0] == other.singleStructure())
-            return true;
-        return false;
-    }
-    
-    OutOfLineList* list = structureList();
-    for (unsigned i = 0; i < list->m_length; ++i) {
-        if (!other.containsOutOfLine(list->list()[i]))
-            return false;
-    }
-    return true;
-}
-
-bool StructureSet::overlaps(const StructureSet& other) const
-{
-    if (isThin()) {
-        if (!singleStructure())
-            return false;
-        return other.contains(singleStructure());
-    }
-    
-    if (other.isThin()) {
-        if (!other.singleStructure())
-            return false;
-        return containsOutOfLine(other.singleStructure());
-    }
-    
-    OutOfLineList* list = structureList();
-    for (unsigned i = 0; i < list->m_length; ++i) {
-        if (other.containsOutOfLine(list->list()[i]))
-            return true;
-    }
-    return false;
-}
-
-bool StructureSet::operator==(const StructureSet& other) const
-{
-    if (size() != other.size())
-        return false;
-    return isSubsetOf(other);
-}
-
 SpeculatedType StructureSet::speculationFromStructures() const
 {
-    if (isThin()) {
-        if (!singleStructure())
-            return SpecNone;
-        return speculationFromStructure(singleStructure());
-    }
-    
     SpeculatedType result = SpecNone;
-    OutOfLineList* list = structureList();
-    for (unsigned i = 0; i < list->m_length; ++i)
-        mergeSpeculation(result, speculationFromStructure(list->list()[i]));
+    forEach(
+        [&] (Structure* structure) {
+            mergeSpeculation(result, speculationFromStructure(structure));
+        });
     return result;
 }
 
 ArrayModes StructureSet::arrayModesFromStructures() const
 {
-    if (isThin()) {
-        if (!singleStructure())
-            return 0;
-        return asArrayModes(singleStructure()->indexingType());
-    }
-    
     ArrayModes result = 0;
-    OutOfLineList* list = structureList();
-    for (unsigned i = 0; i < list->m_length; ++i)
-        mergeArrayModes(result, asArrayModes(list->list()[i]->indexingType()));
+    forEach(
+        [&] (Structure* structure) {
+            mergeArrayModes(result, asArrayModes(structure->indexingType()));
+        });
     return result;
 }
 
@@ -329,8 +87,7 @@ void StructureSet::dumpInContext(PrintStream& out, DumpContext* context) const
 {
     CommaPrinter comma;
     out.print("[");
-    for (size_t i = 0; i < size(); ++i)
-        out.print(comma, inContext(*at(i), context));
+    forEach([&] (Structure* structure) { out.print(comma, inContext(*structure, context)); });
     out.print("]");
 }
 
@@ -339,59 +96,5 @@ void StructureSet::dump(PrintStream& out) const
     dumpInContext(out, nullptr);
 }
 
-bool StructureSet::addOutOfLine(Structure* structure)
-{
-    OutOfLineList* list = structureList();
-    for (unsigned i = 0; i < list->m_length; ++i) {
-        if (list->list()[i] == structure)
-            return false;
-    }
-    
-    if (list->m_length < list->m_capacity) {
-        list->list()[list->m_length++] = structure;
-        return true;
-    }
-    
-    OutOfLineList* newList = OutOfLineList::create(list->m_capacity * 2);
-    newList->m_length = list->m_length + 1;
-    for (unsigned i = list->m_length; i--;)
-        newList->list()[i] = list->list()[i];
-    newList->list()[list->m_length] = structure;
-    OutOfLineList::destroy(list);
-    set(newList);
-    return true;
-}
-
-bool StructureSet::containsOutOfLine(Structure* structure) const
-{
-    OutOfLineList* list = structureList();
-    for (unsigned i = 0; i < list->m_length; ++i) {
-        if (list->list()[i] == structure)
-            return true;
-    }
-    return false;
-}
-
-void StructureSet::copyFromOutOfLine(const StructureSet& other)
-{
-    ASSERT(!other.isThin() && other.m_pointer != reservedValue);
-    OutOfLineList* otherList = other.structureList();
-    OutOfLineList* myList = OutOfLineList::create(otherList->m_length);
-    myList->m_length = otherList->m_length;
-    for (unsigned i = otherList->m_length; i--;)
-        myList->list()[i] = otherList->list()[i];
-    set(myList);
-}
-
-StructureSet::OutOfLineList* StructureSet::OutOfLineList::create(unsigned capacity)
-{
-    return new (NotNull, fastMalloc(sizeof(OutOfLineList) + capacity * sizeof(Structure*))) OutOfLineList(0, capacity);
-}
-
-void StructureSet::OutOfLineList::destroy(OutOfLineList* list)
-{
-    fastFree(list);
-}
-
 } // namespace JSC
 
index 04c1dca..da67045 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2011, 2013, 2014 Apple Inc. All rights reserved.
+ * Copyright (C) 2011, 2013-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
@@ -30,6 +30,7 @@
 #include "SpeculatedType.h"
 #include "Structure.h"
 #include "DumpContext.h"
+#include <wtf/TinyPtrSet.h>
 
 namespace JSC {
 
@@ -38,68 +39,32 @@ class StructureAbstractValue;
 struct AbstractValue;
 }
 
-class StructureSet {
+class StructureSet : public TinyPtrSet<Structure*> {
 public:
+    // I really want to do this:
+    // using TinyPtrSet::TinyPtrSet;
+    //
+    // But I can't because Windows.
+    
     StructureSet()
-        : m_pointer(0)
     {
-        setEmpty();
     }
     
     StructureSet(Structure* structure)
-        : m_pointer(0)
+        : TinyPtrSet(structure)
     {
-        set(structure);
     }
     
     ALWAYS_INLINE StructureSet(const StructureSet& other)
-        : m_pointer(0)
+        : TinyPtrSet(other)
     {
-        copyFrom(other);
     }
     
-    ALWAYS_INLINE StructureSet& operator=(const StructureSet& other)
-    {
-        if (this == &other)
-            return *this;
-        deleteStructureListIfNecessary();
-        copyFrom(other);
-        return *this;
-    }
-    
-    ~StructureSet()
-    {
-        deleteStructureListIfNecessary();
-    }
-    
-    void clear();
-    
     Structure* onlyStructure() const
     {
-        if (isThin())
-            return singleStructure();
-        OutOfLineList* list = structureList();
-        if (list->m_length != 1)
-            return nullptr;
-        return list->list()[0];
+        return onlyEntry();
     }
     
-    bool isEmpty() const
-    {
-        bool result = isThin() && !singleStructure();
-        if (result)
-            ASSERT(m_pointer != reservedValue);
-        return result;
-    }
-    
-    bool add(Structure*);
-    bool remove(Structure*);
-    bool contains(Structure*) const;
-    
-    bool merge(const StructureSet&);
-    void filter(const StructureSet&);
-    void exclude(const StructureSet&);
-    
 #if ENABLE(DFG_JIT)
     void filter(const DFG::StructureAbstractValue&);
     void filter(SpeculatedType);
@@ -107,212 +72,11 @@ public:
     void filter(const DFG::AbstractValue&);
 #endif // ENABLE(DFG_JIT)
     
-    template<typename Functor>
-    void genericFilter(Functor& functor)
-    {
-        if (isThin()) {
-            if (!singleStructure())
-                return;
-            if (functor(singleStructure()))
-                return;
-            clear();
-            return;
-        }
-        
-        OutOfLineList* list = structureList();
-        for (unsigned i = 0; i < list->m_length; ++i) {
-            if (functor(list->list()[i]))
-                continue;
-            list->list()[i--] = list->list()[--list->m_length];
-        }
-        if (!list->m_length)
-            clear();
-    }
-    
-    bool isSubsetOf(const StructureSet&) const;
-    bool isSupersetOf(const StructureSet& other) const
-    {
-        return other.isSubsetOf(*this);
-    }
-    
-    bool overlaps(const StructureSet&) const;
-    
-    size_t size() const
-    {
-        if (isThin())
-            return !!singleStructure();
-        return structureList()->m_length;
-    }
-    
-    Structure* at(size_t i) const
-    {
-        if (isThin()) {
-            ASSERT(!i);
-            ASSERT(singleStructure());
-            return singleStructure();
-        }
-        ASSERT(i < structureList()->m_length);
-        return structureList()->list()[i];
-    }
-    
-    Structure* operator[](size_t i) const { return at(i); }
-    
-    Structure* last() const
-    {
-        if (isThin()) {
-            ASSERT(singleStructure());
-            return singleStructure();
-        }
-        return structureList()->list()[structureList()->m_length - 1];
-    }
-    
-    class iterator {
-    public:
-        iterator()
-            : m_set(nullptr)
-            , m_index(0)
-        {
-        }
-        
-        iterator(const StructureSet* set, size_t index)
-            : m_set(set)
-            , m_index(index)
-        {
-        }
-        
-        Structure* operator*() const { return m_set->at(m_index); }
-        iterator& operator++()
-        {
-            m_index++;
-            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 StructureSet* m_set;
-        size_t m_index;
-    };
-    
-    iterator begin() const { return iterator(this, 0); }
-    iterator end() const { return iterator(this, size()); }
-    
-    bool operator==(const StructureSet& other) const;
-    
     SpeculatedType speculationFromStructures() const;
     ArrayModes arrayModesFromStructures() const;
     
     void dumpInContext(PrintStream&, DumpContext*) const;
     void dump(PrintStream&) const;
-    
-private:
-    friend class DFG::StructureAbstractValue;
-    
-    static const uintptr_t thinFlag = 1;
-    static const uintptr_t reservedFlag = 2;
-    static const uintptr_t flags = thinFlag | reservedFlag;
-    static const uintptr_t reservedValue = 4;
-
-    static const unsigned defaultStartingSize = 4;
-    
-    bool addOutOfLine(Structure*);
-    bool containsOutOfLine(Structure*) const;
-    
-    class ContainsOutOfLine {
-    public:
-        ContainsOutOfLine(const StructureSet& set)
-            : m_set(set)
-        {
-        }
-        
-        bool operator()(Structure* structure)
-        {
-            return m_set.containsOutOfLine(structure);
-        }
-    private:
-        const StructureSet& m_set;
-    };
-
-    ALWAYS_INLINE void copyFrom(const StructureSet& other)
-    {
-        if (other.isThin() || other.m_pointer == reservedValue) {
-            bool value = getReservedFlag();
-            m_pointer = other.m_pointer;
-            setReservedFlag(value);
-            return;
-        }
-        copyFromOutOfLine(other);
-    }
-    void copyFromOutOfLine(const StructureSet& other);
-    
-    class OutOfLineList {
-    public:
-        static OutOfLineList* create(unsigned capacity);
-        static void destroy(OutOfLineList*);
-        
-        Structure** list() { return bitwise_cast<Structure**>(this + 1); }
-        
-        OutOfLineList(unsigned length, unsigned capacity)
-            : m_length(length)
-            , m_capacity(capacity)
-        {
-        }
-
-        unsigned m_length;
-        unsigned m_capacity;
-    };
-    
-    ALWAYS_INLINE void deleteStructureListIfNecessary()
-    {
-        if (!isThin() && m_pointer != reservedValue)
-            OutOfLineList::destroy(structureList());
-    }
-    
-    bool isThin() const { return m_pointer & thinFlag; }
-    
-    void* pointer() const
-    {
-        return bitwise_cast<void*>(m_pointer & ~flags);
-    }
-    
-    Structure* singleStructure() const
-    {
-        ASSERT(isThin());
-        return static_cast<Structure*>(pointer());
-    }
-    
-    OutOfLineList* structureList() const
-    {
-        ASSERT(!isThin());
-        return static_cast<OutOfLineList*>(pointer());
-    }
-    
-    void set(Structure* structure)
-    {
-        set(bitwise_cast<uintptr_t>(structure), true);
-    }
-    void set(OutOfLineList* structures)
-    {
-        set(bitwise_cast<uintptr_t>(structures), false);
-    }
-    void setEmpty()
-    {
-        set(0, true);
-    }
-    void set(uintptr_t pointer, bool singleStructure)
-    {
-        m_pointer = pointer | (singleStructure ? thinFlag : 0) | (m_pointer & reservedFlag);
-    }
-    bool getReservedFlag() const { return m_pointer & reservedFlag; }
-    void setReservedFlag(bool value)
-    {
-        if (value)
-            m_pointer |= reservedFlag;
-        else
-            m_pointer &= ~reservedFlag;
-    }
-
-    uintptr_t m_pointer;
 };
 
 } // namespace JSC
index b96e781..a3fbb89 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2014 Apple Inc. All rights reserved.
+ * Copyright (C) 2014, 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
@@ -64,14 +64,14 @@ void StructureAbstractValue::clobber()
     setClobbered(true);
         
     if (m_set.isThin()) {
-        if (!m_set.singleStructure())
+        if (!m_set.singleEntry())
             return;
-        if (!m_set.singleStructure()->dfgShouldWatch())
+        if (!m_set.singleEntry()->dfgShouldWatch())
             makeTopWhenThin();
         return;
     }
-        
-    StructureSet::OutOfLineList* list = m_set.structureList();
+    
+    StructureSet::OutOfLineList* list = m_set.list();
     for (unsigned i = list->m_length; i--;) {
         if (!list->list()[i]->dfgShouldWatch()) {
             makeTop();
@@ -268,25 +268,6 @@ void StructureAbstractValue::filter(const StructureAbstractValue& other)
     filter(other.m_set);
 }
 
-namespace {
-
-class ConformsToType {
-public:
-    ConformsToType(SpeculatedType type)
-        : m_type(type)
-    {
-    }
-    
-    bool operator()(Structure* structure)
-    {
-        return !!(speculationFromStructure(structure) & m_type);
-    }
-private:
-    SpeculatedType m_type;
-};
-
-} // anonymous namespace
-
 void StructureAbstractValue::filterSlow(SpeculatedType type)
 {
     SAMPLE("StructureAbstractValue filter type slow");
@@ -298,8 +279,10 @@ void StructureAbstractValue::filterSlow(SpeculatedType type)
     
     ASSERT(!isTop());
     
-    ConformsToType conformsToType(type);
-    m_set.genericFilter(conformsToType);
+    m_set.genericFilter(
+        [&] (Structure* structure) {
+            return !!(speculationFromStructure(structure) & type);
+        });
 }
 
 bool StructureAbstractValue::contains(Structure* structure) const
index dc22186..a22eab1 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2011, 2012, 2013, 2014 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
@@ -40,7 +40,7 @@ class StructureAbstractValue {
 public:
     StructureAbstractValue() { }
     StructureAbstractValue(Structure* structure)
-        : m_set(structure)
+        : m_set(StructureSet(structure))
     {
         setClobbered(false);
     }
@@ -57,7 +57,7 @@ public:
     
     ALWAYS_INLINE StructureAbstractValue& operator=(Structure* structure)
     {
-        m_set = structure;
+        m_set = StructureSet(structure);
         setClobbered(false);
         return *this;
     }
@@ -82,7 +82,7 @@ public:
     
     void makeTop()
     {
-        m_set.deleteStructureListIfNecessary();
+        m_set.deleteListIfNecessary();
         m_set.m_pointer = topValue;
     }
     
index b2f7a4f..852c172 100644 (file)
@@ -1,3 +1,66 @@
+2015-06-07  Filip Pizlo  <fpizlo@apple.com>
+
+        The tiny set magic in StructureSet should be available in WTF
+        https://bugs.webkit.org/show_bug.cgi?id=145722
+
+        Reviewed by Geoffrey Garen.
+        
+        As the management of structure sets evolved in JSC, the StructureSet data structure grew
+        increasingly smart. It's got some smart stuff for managing small sets of pointers. I
+        wanted to take the generic logic out of JSC and put it into a reusable templatized class
+        in WTF.
+        
+        * WTF.vcxproj/WTF.vcxproj:
+        * WTF.xcodeproj/project.pbxproj:
+        * wtf/CMakeLists.txt:
+        * wtf/TinyPtrSet.h: Added.
+        (WTF::TinyPtrSet::TinyPtrSet):
+        (WTF::TinyPtrSet::operator=):
+        (WTF::TinyPtrSet::~TinyPtrSet):
+        (WTF::TinyPtrSet::clear):
+        (WTF::TinyPtrSet::onlyEntry):
+        (WTF::TinyPtrSet::isEmpty):
+        (WTF::TinyPtrSet::add):
+        (WTF::TinyPtrSet::remove):
+        (WTF::TinyPtrSet::contains):
+        (WTF::TinyPtrSet::merge):
+        (WTF::TinyPtrSet::forEach):
+        (WTF::TinyPtrSet::genericFilter):
+        (WTF::TinyPtrSet::filter):
+        (WTF::TinyPtrSet::exclude):
+        (WTF::TinyPtrSet::isSubsetOf):
+        (WTF::TinyPtrSet::isSupersetOf):
+        (WTF::TinyPtrSet::overlaps):
+        (WTF::TinyPtrSet::size):
+        (WTF::TinyPtrSet::at):
+        (WTF::TinyPtrSet::operator[]):
+        (WTF::TinyPtrSet::last):
+        (WTF::TinyPtrSet::iterator::iterator):
+        (WTF::TinyPtrSet::iterator::operator*):
+        (WTF::TinyPtrSet::iterator::operator++):
+        (WTF::TinyPtrSet::iterator::operator==):
+        (WTF::TinyPtrSet::iterator::operator!=):
+        (WTF::TinyPtrSet::begin):
+        (WTF::TinyPtrSet::end):
+        (WTF::TinyPtrSet::operator==):
+        (WTF::TinyPtrSet::addOutOfLine):
+        (WTF::TinyPtrSet::containsOutOfLine):
+        (WTF::TinyPtrSet::copyFrom):
+        (WTF::TinyPtrSet::copyFromOutOfLine):
+        (WTF::TinyPtrSet::OutOfLineList::create):
+        (WTF::TinyPtrSet::OutOfLineList::destroy):
+        (WTF::TinyPtrSet::OutOfLineList::list):
+        (WTF::TinyPtrSet::OutOfLineList::OutOfLineList):
+        (WTF::TinyPtrSet::deleteListIfNecessary):
+        (WTF::TinyPtrSet::isThin):
+        (WTF::TinyPtrSet::pointer):
+        (WTF::TinyPtrSet::singleEntry):
+        (WTF::TinyPtrSet::list):
+        (WTF::TinyPtrSet::set):
+        (WTF::TinyPtrSet::setEmpty):
+        (WTF::TinyPtrSet::getReservedFlag):
+        (WTF::TinyPtrSet::setReservedFlag):
+
 2015-06-08  Michael Catanzaro  <mcatanzaro@igalia.com>
 
         [SOUP] Performs DNS prefetch when a proxy is configured (information leak)
index 989713e..407eb31 100644 (file)
     <ClInclude Include="..\wtf\threadsafeRefCounted.h" />
     <ClInclude Include="..\wtf\threadspecific.h" />
     <ClInclude Include="..\wtf\threads\BinarySemaphore.h" />
+    <ClInclude Include="..\wtf\TinyPtrSet.h" />
     <ClInclude Include="..\wtf\unicode\CharacterNames.h" />
     <ClInclude Include="..\wtf\unicode\Collator.h" />
     <ClInclude Include="..\wtf\unicode\UTF8.h" />
index bf4ce98..7dfd971 100644 (file)
@@ -40,6 +40,7 @@
                0FD81AC5154FB22E00983E72 /* FastBitVector.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FD81AC4154FB22E00983E72 /* FastBitVector.h */; settings = {ATTRIBUTES = (); }; };
                0FDDBFA71666DFA300C55FEF /* StringPrintStream.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FDDBFA51666DFA300C55FEF /* StringPrintStream.cpp */; };
                0FDDBFA81666DFA300C55FEF /* StringPrintStream.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FDDBFA61666DFA300C55FEF /* StringPrintStream.h */; };
+               0FED67B61B22D4D80066CE15 /* TinyPtrSet.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FED67B51B22D4D80066CE15 /* TinyPtrSet.h */; };
                14022F4118F5C3FC007FF0EB /* libbmalloc.a in Frameworks */ = {isa = PBXBuildFile; fileRef = 14022F4018F5C3FC007FF0EB /* libbmalloc.a */; };
                143F611F1565F0F900DB514A /* RAMSize.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 143F611D1565F0F900DB514A /* RAMSize.cpp */; };
                143F61201565F0F900DB514A /* RAMSize.h in Headers */ = {isa = PBXBuildFile; fileRef = 143F611E1565F0F900DB514A /* RAMSize.h */; settings = {ATTRIBUTES = (); }; };
                0FDDBFA51666DFA300C55FEF /* StringPrintStream.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = StringPrintStream.cpp; sourceTree = "<group>"; };
                0FDDBFA61666DFA300C55FEF /* StringPrintStream.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = StringPrintStream.h; sourceTree = "<group>"; };
                0FEC3EE4171B834700FDAC8D /* ByteSpinLock.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = ByteSpinLock.h; sourceTree = "<group>"; };
+               0FED67B51B22D4D80066CE15 /* TinyPtrSet.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = TinyPtrSet.h; sourceTree = "<group>"; };
                14022F4018F5C3FC007FF0EB /* libbmalloc.a */ = {isa = PBXFileReference; lastKnownFileType = archive.ar; path = libbmalloc.a; sourceTree = BUILT_PRODUCTS_DIR; };
                143F611D1565F0F900DB514A /* RAMSize.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = RAMSize.cpp; sourceTree = "<group>"; };
                143F611E1565F0F900DB514A /* RAMSize.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = RAMSize.h; sourceTree = "<group>"; };
                                A8A47336151A825B004123FF /* ThreadingPthreads.cpp */,
                                A8A4733E151A825B004123FF /* ThreadSafeRefCounted.h */,
                                A8A4733F151A825B004123FF /* ThreadSpecific.h */,
+                               0FED67B51B22D4D80066CE15 /* TinyPtrSet.h */,
                                149EF16216BBFE0D000A4331 /* TriState.h */,
                                83FBA93119DF459700F30ADB /* TypeCasts.h */,
                                A8A4735C151A825B004123FF /* UnionFind.h */,
                                A8A4747D151A825B004123FF /* ValueCheck.h in Headers */,
                                A8A4747E151A825B004123FF /* Vector.h in Headers */,
                                A8A4747F151A825B004123FF /* VectorTraits.h in Headers */,
+                               0FED67B61B22D4D80066CE15 /* TinyPtrSet.h in Headers */,
                                A8A47480151A825B004123FF /* VMTags.h in Headers */,
                                974CFC8E16A4F327006D5404 /* WeakPtr.h in Headers */,
                                E4A0AD3A1A96245500536DF6 /* WorkQueue.h in Headers */,
index e5fc7e3..b15bdf7 100644 (file)
@@ -94,6 +94,7 @@ set(WTF_HEADERS
     ThreadSpecific.h
     Threading.h
     ThreadingPrimitives.h
+    TinyPtrSet.h
     VMTags.h
     ValueCheck.h
     Vector.h
diff --git a/Source/WTF/wtf/TinyPtrSet.h b/Source/WTF/wtf/TinyPtrSet.h
new file mode 100644 (file)
index 0000000..4d527a3
--- /dev/null
@@ -0,0 +1,517 @@
+/*
+ * 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 TinyPtrSet_h
+#define TinyPtrSet_h
+
+#include <wtf/Assertions.h>
+#include <wtf/FastMalloc.h>
+
+namespace JSC { namespace DFG {
+class StructureAbstractValue;
+} } // namespace JSC::DFG
+
+namespace WTF {
+
+// FIXME: This currently only works for types that are pointer-like: they should have the size
+// of a pointer and like a pointer they should not have assignment operators, copy constructors,
+// non-trivial default constructors, and non-trivial destructors. It may be possible to lift all
+// of these restrictions. If we succeeded then this should be renamed to just TinySet.
+// https://bugs.webkit.org/show_bug.cgi?id=145741
+
+template<typename T>
+class TinyPtrSet {
+public:
+    TinyPtrSet()
+        : m_pointer(0)
+    {
+        setEmpty();
+    }
+    
+    TinyPtrSet(T element)
+        : m_pointer(0)
+    {
+        set(element);
+    }
+    
+    ALWAYS_INLINE TinyPtrSet(const TinyPtrSet& other)
+        : m_pointer(0)
+    {
+        copyFrom(other);
+    }
+    
+    ALWAYS_INLINE TinyPtrSet& operator=(const TinyPtrSet& other)
+    {
+        if (this == &other)
+            return *this;
+        deleteListIfNecessary();
+        copyFrom(other);
+        return *this;
+    }
+    
+    ~TinyPtrSet()
+    {
+        deleteListIfNecessary();
+    }
+    
+    void clear()
+    {
+        deleteListIfNecessary();
+        setEmpty();
+    }
+    
+    // Returns the only entry if the array has exactly one entry.
+    T onlyEntry() const
+    {
+        if (isThin())
+            return singleEntry();
+        OutOfLineList* list = this->list();
+        if (list->m_length != 1)
+            return T();
+        return list->list()[0];
+    }
+    
+    bool isEmpty() const
+    {
+        bool result = isThin() && !singleEntry();
+        if (result)
+            ASSERT(m_poointer != reservedValue);
+        return result;
+    }
+    
+    bool add(T value)
+    {
+        ASSERT(value);
+        if (isThin()) {
+            if (singleEntry() == value)
+                return false;
+            if (!singleEntry()) {
+                set(value);
+                return true;
+            }
+            
+            OutOfLineList* list = OutOfLineList::create(defaultStartingSize);
+            list->m_length = 2;
+            list->list()[0] = singleEntry();
+            list->list()[1] = value;
+            set(list);
+            return true;
+        }
+        
+        return addOutOfLine(value);
+    }
+    
+    bool remove(T value)
+    {
+        if (isThin()) {
+            if (singleEntry() == value) {
+                setEmpty();
+                return true;
+            }
+            return false;
+        }
+        
+        OutOfLineList* list = this->list();
+        for (unsigned i = 0; i < list->m_length; ++i) {
+            if (list->list()[i] != value)
+                continue;
+            list->list()[i] = list->list()[--list->m_length];
+            if (!list->m_length) {
+                OutOfLineList::destroy(list);
+                setEmpty();
+            }
+            return true;
+        }
+        return false;
+    }
+    
+    bool contains(T value) const
+    {
+        if (isThin())
+            return singleEntry() == value;
+        return containsOutOfLine(value);
+    }
+    
+    bool merge(const TinyPtrSet& other)
+    {
+        if (other.isThin()) {
+            if (other.singleEntry())
+                return add(other.singleEntry());
+            return false;
+        }
+        
+        OutOfLineList* list = other.list();
+        if (list->m_length >= 2) {
+            if (isThin()) {
+                OutOfLineList* myNewList = OutOfLineList::create(
+                    list->m_length + !!singleEntry());
+                if (singleEntry()) {
+                    myNewList->m_length = 1;
+                    myNewList->list()[0] = singleEntry();
+                }
+                set(myNewList);
+            }
+            bool changed = false;
+            for (unsigned i = 0; i < list->m_length; ++i)
+                changed |= addOutOfLine(list->list()[i]);
+            return changed;
+        }
+        
+        ASSERT(list->m_length);
+        return add(list->list()[0]);
+    }
+    
+    template<typename Functor>
+    void forEach(const Functor& functor) const
+    {
+        if (isThin()) {
+            if (!singleEntry())
+                return;
+            functor(singleEntry());
+            return;
+        }
+        
+        OutOfLineList* list = this->list();
+        for (unsigned i = 0; i < list->m_length; ++i)
+            functor(list->list()[i]);
+    }
+        
+    template<typename Functor>
+    void genericFilter(const Functor& functor)
+    {
+        if (isThin()) {
+            if (!singleEntry())
+                return;
+            if (functor(singleEntry()))
+                return;
+            clear();
+            return;
+        }
+        
+        OutOfLineList* list = this->list();
+        for (unsigned i = 0; i < list->m_length; ++i) {
+            if (functor(list->list()[i]))
+                continue;
+            list->list()[i--] = list->list()[--list->m_length];
+        }
+        if (!list->m_length)
+            clear();
+    }
+        
+    void filter(const TinyPtrSet& other)
+    {
+        if (other.isThin()) {
+            if (!other.singleEntry() || !contains(other.singleEntry()))
+                clear();
+            else {
+                clear();
+                set(other.singleEntry());
+            }
+            return;
+        }
+        
+        genericFilter([&] (T value) { return other.containsOutOfLine(value); });
+    }
+    
+    void exclude(const TinyPtrSet& other)
+    {
+        if (other.isThin()) {
+            if (other.singleEntry())
+                remove(other.singleEntry());
+            return;
+        }
+        
+        genericFilter([&] (T value) { return !other.containsOutOfLine(value); });
+    }
+    
+    bool isSubsetOf(const TinyPtrSet& other) const
+    {
+        if (isThin()) {
+            if (!singleEntry())
+                return true;
+            return other.contains(singleEntry());
+        }
+        
+        if (other.isThin()) {
+            if (!other.singleEntry())
+                return false;
+            OutOfLineList* list = this->list();
+            if (list->m_length >= 2)
+                return false;
+            if (list->list()[0] == other.singleEntry())
+                return true;
+            return false;
+        }
+        
+        OutOfLineList* list = this->list();
+        for (unsigned i = 0; i < list->m_length; ++i) {
+            if (!other.containsOutOfLine(list->list()[i]))
+                return false;
+        }
+        return true;
+    }
+    
+    bool isSupersetOf(const TinyPtrSet& other) const
+    {
+        return other.isSubsetOf(*this);
+    }
+    
+    bool overlaps(const TinyPtrSet& other) const
+    {
+        if (isThin()) {
+            if (!singleEntry())
+                return false;
+            return other.contains(singleEntry());
+        }
+        
+        if (other.isThin()) {
+            if (!other.singleEntry())
+                return false;
+            return containsOutOfLine(other.singleEntry());
+        }
+        
+        OutOfLineList* list = this->list();
+        for (unsigned i = 0; i < list->m_length; ++i) {
+            if (other.containsOutOfLine(list->list()[i]))
+                return true;
+        }
+        return false;
+    }
+    
+    size_t size() const
+    {
+        if (isThin())
+            return !!singleEntry();
+        return list()->m_length;
+    }
+    
+    T at(size_t i) const
+    {
+        if (isThin()) {
+            ASSERT(!i);
+            ASSERT(singleEntry());
+            return singleEntry();
+        }
+        ASSERT(i < list()->m_length);
+        return list()->list()[i];
+    }
+    
+    T operator[](size_t i) const { return at(i); }
+    
+    T last() const
+    {
+        if (isThin()) {
+            ASSERT(singleEntry());
+            return singleEntry();
+        }
+        return list()->list()[list()->m_length - 1];
+    }
+    
+    class iterator {
+    public:
+        iterator()
+            : m_set(nullptr)
+            , m_index(0)
+        {
+        }
+        
+        iterator(const TinyPtrSet* set, size_t index)
+            : m_set(set)
+            , m_index(index)
+        {
+        }
+        
+        T operator*() const { return m_set->at(index); }
+        iterator& operator++()
+        {
+            m_index++;
+            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 TinyPtrSet* m_set;
+        size_t m_index;
+    };
+    
+    iterator begin() const { return iterator(this, 0); }
+    iterator end() const { return iterator(this, size()); }
+    
+    bool operator==(const TinyPtrSet& other) const
+    {
+        if (size() != other.size())
+            return false;
+        return isSubsetOf(other);
+    }
+    
+private:
+    friend class JSC::DFG::StructureAbstractValue;
+
+    static const uintptr_t thinFlag = 1;
+    static const uintptr_t reservedFlag = 2;
+    static const uintptr_t flags = thinFlag | reservedFlag;
+    static const uintptr_t reservedValue = 4;
+
+    static const unsigned defaultStartingSize = 4;
+    
+    bool addOutOfLine(T value)
+    {
+        OutOfLineList* list = this->list();
+        for (unsigned i = 0; i < list->m_length; ++i) {
+            if (list->list()[i] == value)
+                return false;
+        }
+        
+        if (list->m_length < list->m_capacity) {
+            list->list()[list->m_length++] = value;
+            return true;
+        }
+        
+        OutOfLineList* newList = OutOfLineList::create(list->m_capacity * 2);
+        newList->m_length = list->m_length + 1;
+        for (unsigned i = list->m_length; i--;)
+            newList->list()[i] = list->list()[i];
+        newList->list()[list->m_length] = value;
+        OutOfLineList::destroy(list);
+        set(newList);
+        return true;
+    }
+    
+    bool containsOutOfLine(T value) const
+    {
+        OutOfLineList* list = this->list();
+        for (unsigned i = 0; i < list->m_length; ++i) {
+            if (list->list()[i] == value)
+                return true;
+        }
+        return false;
+    }
+    
+    ALWAYS_INLINE void copyFrom(const TinyPtrSet& other)
+    {
+        if (other.isThin() || other.m_pointer == reservedValue) {
+            bool value = getReservedFlag();
+            m_pointer = other.m_pointer;
+            setReservedFlag(value);
+            return;
+        }
+        copyFromOutOfLine(other);
+    }
+    
+    NEVER_INLINE void copyFromOutOfLine(const TinyPtrSet& other)
+    {
+        ASSERT(!other.isThin() && other.m_pointer != reservedValue);
+        OutOfLineList* otherList = other.list();
+        OutOfLineList* myList = OutOfLineList::create(otherList->m_length);
+        myList->m_length = otherList->m_length;
+        for (unsigned i = otherList->m_length; i--;)
+            myList->list()[i] = otherList->list()[i];
+        set(myList);
+    }
+    
+    class OutOfLineList {
+    public:
+        static OutOfLineList* create(unsigned capacity)
+        {
+            return new (NotNull, fastMalloc(sizeof(OutOfLineList) + capacity * sizeof(T))) OutOfLineList(0, capacity);
+        }
+        
+        static void destroy(OutOfLineList* list)
+        {
+            fastFree(list);
+        }
+        
+        T* list() { return bitwise_cast<T*>(this + 1); }
+        
+        OutOfLineList(unsigned length, unsigned capacity)
+            : m_length(length)
+            , m_capacity(capacity)
+        {
+        }
+
+        unsigned m_length;
+        unsigned m_capacity;
+    };
+    
+    ALWAYS_INLINE void deleteListIfNecessary()
+    {
+        if (!isThin() && m_pointer != reservedValue)
+            OutOfLineList::destroy(list());
+    }
+    
+    bool isThin() const { return m_pointer & thinFlag; }
+    
+    void* pointer() const
+    {
+        return bitwise_cast<void*>(m_pointer & ~flags);
+    }
+    
+    T singleEntry() const
+    {
+        ASSERT(isThin());
+        return static_cast<T>(pointer());
+    }
+    
+    OutOfLineList* list() const
+    {
+        ASSERT(!isThin());
+        return static_cast<OutOfLineList*>(pointer());
+    }
+    
+    void set(T value)
+    {
+        set(bitwise_cast<uintptr_t>(value), true);
+    }
+    void set(OutOfLineList* list)
+    {
+        set(bitwise_cast<uintptr_t>(list), false);
+    }
+    void setEmpty()
+    {
+        set(0, true);
+    }
+    void set(uintptr_t pointer, bool singleEntry)
+    {
+        m_pointer = pointer | (singleEntry ? thinFlag : 0) | (m_pointer & reservedFlag);
+    }
+    bool getReservedFlag() const { return m_pointer & reservedFlag; }
+    void setReservedFlag(bool value)
+    {
+        if (value)
+            m_pointer |= reservedFlag;
+        else
+            m_pointer &= ~reservedFlag;
+    }
+    
+    uintptr_t m_pointer;
+};
+
+} // namespace WTF
+
+using WTF::TinyPtrSet;
+
+#endif // TinyPtrSet_h
+