<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
"http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head><meta http-equiv="content-type" content="text/html; charset=utf-8" />
<title>[185324] trunk/Source</title>
</head>
<body>
<style type="text/css"><!--
#msg dl.meta { border: 1px #006 solid; background: #369; padding: 6px; color: #fff; }
#msg dl.meta dt { float: left; width: 6em; font-weight: bold; }
#msg dt:after { content:':';}
#msg dl, #msg dt, #msg ul, #msg li, #header, #footer, #logmsg { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; }
#msg dl a { font-weight: bold}
#msg dl a:link { color:#fc3; }
#msg dl a:active { color:#ff0; }
#msg dl a:visited { color:#cc6; }
h3 { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; font-weight: bold; }
#msg pre { overflow: auto; background: #ffc; border: 1px #fa0 solid; padding: 6px; }
#logmsg { background: #ffc; border: 1px #fa0 solid; padding: 1em 1em 0 1em; }
#logmsg p, #logmsg pre, #logmsg blockquote { margin: 0 0 1em 0; }
#logmsg p, #logmsg li, #logmsg dt, #logmsg dd { line-height: 14pt; }
#logmsg h1, #logmsg h2, #logmsg h3, #logmsg h4, #logmsg h5, #logmsg h6 { margin: .5em 0; }
#logmsg h1:first-child, #logmsg h2:first-child, #logmsg h3:first-child, #logmsg h4:first-child, #logmsg h5:first-child, #logmsg h6:first-child { margin-top: 0; }
#logmsg ul, #logmsg ol { padding: 0; list-style-position: inside; margin: 0 0 0 1em; }
#logmsg ul { text-indent: -1em; padding-left: 1em; }#logmsg ol { text-indent: -1.5em; padding-left: 1.5em; }
#logmsg > ul, #logmsg > ol { margin: 0 0 1em 0; }
#logmsg pre { background: #eee; padding: 1em; }
#logmsg blockquote { border: 1px solid #fa0; border-left-width: 10px; padding: 1em 1em 0 1em; background: white;}
#logmsg dl { margin: 0; }
#logmsg dt { font-weight: bold; }
#logmsg dd { margin: 0; padding: 0 0 0.5em 0; }
#logmsg dd:before { content:'\00bb';}
#logmsg table { border-spacing: 0px; border-collapse: collapse; border-top: 4px solid #fa0; border-bottom: 1px solid #fa0; background: #fff; }
#logmsg table th { text-align: left; font-weight: normal; padding: 0.2em 0.5em; border-top: 1px dotted #fa0; }
#logmsg table td { text-align: right; border-top: 1px dotted #fa0; padding: 0.2em 0.5em; }
#logmsg table thead th { text-align: center; border-bottom: 1px solid #fa0; }
#logmsg table th.Corner { text-align: left; }
#logmsg hr { border: none 0; border-top: 2px dashed #fa0; height: 1px; }
#header, #footer { color: #fff; background: #636; border: 1px #300 solid; padding: 6px; }
#patch { width: 100%; }
#patch h4 {font-family: verdana,arial,helvetica,sans-serif;font-size:10pt;padding:8px;background:#369;color:#fff;margin:0;}
#patch .propset h4, #patch .binary h4 {margin:0;}
#patch pre {padding:0;line-height:1.2em;margin:0;}
#patch .diff {width:100%;background:#eee;padding: 0 0 10px 0;overflow:auto;}
#patch .propset .diff, #patch .binary .diff {padding:10px 0;}
#patch span {display:block;padding:0 10px;}
#patch .modfile, #patch .addfile, #patch .delfile, #patch .propset, #patch .binary, #patch .copfile {border:1px solid #ccc;margin:10px 0;}
#patch ins {background:#dfd;text-decoration:none;display:block;padding:0 10px;}
#patch del {background:#fdd;text-decoration:none;display:block;padding:0 10px;}
#patch .lines, .info {color:#888;background:#fff;}
--></style>
<div id="msg">
<dl class="meta">
<dt>Revision</dt> <dd><a href="http://trac.webkit.org/projects/webkit/changeset/185324">185324</a></dd>
<dt>Author</dt> <dd>fpizlo@apple.com</dd>
<dt>Date</dt> <dd>2015-06-08 12:41:47 -0700 (Mon, 08 Jun 2015)</dd>
</dl>
<h3>Log Message</h3>
<pre>The tiny set magic in StructureSet should be available in WTF
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):</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourceJavaScriptCoreChangeLog">trunk/Source/JavaScriptCore/ChangeLog</a></li>
<li><a href="#trunkSourceJavaScriptCorebytecodeStructureSetcpp">trunk/Source/JavaScriptCore/bytecode/StructureSet.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCorebytecodeStructureSeth">trunk/Source/JavaScriptCore/bytecode/StructureSet.h</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGStructureAbstractValuecpp">trunk/Source/JavaScriptCore/dfg/DFGStructureAbstractValue.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGStructureAbstractValueh">trunk/Source/JavaScriptCore/dfg/DFGStructureAbstractValue.h</a></li>
<li><a href="#trunkSourceWTFChangeLog">trunk/Source/WTF/ChangeLog</a></li>
<li><a href="#trunkSourceWTFWTFvcxprojWTFvcxproj">trunk/Source/WTF/WTF.vcxproj/WTF.vcxproj</a></li>
<li><a href="#trunkSourceWTFWTFxcodeprojprojectpbxproj">trunk/Source/WTF/WTF.xcodeproj/project.pbxproj</a></li>
<li><a href="#trunkSourceWTFwtfCMakeListstxt">trunk/Source/WTF/wtf/CMakeLists.txt</a></li>
</ul>
<h3>Added Paths</h3>
<ul>
<li><a href="#trunkSourceWTFwtfTinyPtrSeth">trunk/Source/WTF/wtf/TinyPtrSet.h</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceJavaScriptCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ChangeLog (185323 => 185324)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ChangeLog 2015-06-08 18:21:59 UTC (rev 185323)
+++ trunk/Source/JavaScriptCore/ChangeLog 2015-06-08 19:41:47 UTC (rev 185324)
</span><span class="lines">@@ -1,3 +1,76 @@
</span><ins>+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):
+
</ins><span class="cx"> 2015-06-08 Csaba Osztrogonác <ossy@webkit.org>
</span><span class="cx">
</span><span class="cx"> [ARM] Add the missing setupArgumentsWithExecState functions after r185240
</span></span></pre></div>
<a id="trunkSourceJavaScriptCorebytecodeStructureSetcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/bytecode/StructureSet.cpp (185323 => 185324)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/bytecode/StructureSet.cpp 2015-06-08 18:21:59 UTC (rev 185323)
+++ trunk/Source/JavaScriptCore/bytecode/StructureSet.cpp 2015-06-08 19:41:47 UTC (rev 185324)
</span><span class="lines">@@ -1,5 +1,5 @@
</span><span class="cx"> /*
</span><del>- * Copyright (C) 2014 Apple Inc. All rights reserved.
</del><ins>+ * Copyright (C) 2014, 2015 Apple Inc. All rights reserved.
</ins><span class="cx"> *
</span><span class="cx"> * Redistribution and use in source and binary forms, with or without
</span><span class="cx"> * modification, are permitted provided that the following conditions
</span><span class="lines">@@ -31,203 +31,27 @@
</span><span class="cx">
</span><span class="cx"> namespace JSC {
</span><span class="cx">
</span><del>-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();
-}
-
</del><span class="cx"> #if ENABLE(DFG_JIT)
</span><span class="cx">
</span><del>-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
-
</del><span class="cx"> void StructureSet::filter(const DFG::StructureAbstractValue& other)
</span><span class="cx"> {
</span><del>- StructureAbstractValueContains functor(other);
- genericFilter(functor);
</del><ins>+ genericFilter([&] (Structure* structure) -> bool { return other.contains(structure); });
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> void StructureSet::filter(SpeculatedType type)
</span><span class="cx"> {
</span><del>- SpeculatedTypeContains functor(type);
- genericFilter(functor);
</del><ins>+ genericFilter(
+ [&] (Structure* structure) -> bool {
+ return type & speculationFromStructure(structure);
+ });
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> void StructureSet::filterArrayModes(ArrayModes arrayModes)
</span><span class="cx"> {
</span><del>- ArrayModesContains functor(arrayModes);
- genericFilter(functor);
</del><ins>+ genericFilter(
+ [&] (Structure* structure) -> bool {
+ return arrayModes & arrayModeFromStructure(structure);
+ });
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> void StructureSet::filter(const DFG::AbstractValue& other)
</span><span class="lines">@@ -239,89 +63,23 @@
</span><span class="cx">
</span><span class="cx"> #endif // ENABLE(DFG_JIT)
</span><span class="cx">
</span><del>-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);
-}
-
</del><span class="cx"> SpeculatedType StructureSet::speculationFromStructures() const
</span><span class="cx"> {
</span><del>- if (isThin()) {
- if (!singleStructure())
- return SpecNone;
- return speculationFromStructure(singleStructure());
- }
-
</del><span class="cx"> SpeculatedType result = SpecNone;
</span><del>- OutOfLineList* list = structureList();
- for (unsigned i = 0; i < list->m_length; ++i)
- mergeSpeculation(result, speculationFromStructure(list->list()[i]));
</del><ins>+ forEach(
+ [&] (Structure* structure) {
+ mergeSpeculation(result, speculationFromStructure(structure));
+ });
</ins><span class="cx"> return result;
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> ArrayModes StructureSet::arrayModesFromStructures() const
</span><span class="cx"> {
</span><del>- if (isThin()) {
- if (!singleStructure())
- return 0;
- return asArrayModes(singleStructure()->indexingType());
- }
-
</del><span class="cx"> ArrayModes result = 0;
</span><del>- OutOfLineList* list = structureList();
- for (unsigned i = 0; i < list->m_length; ++i)
- mergeArrayModes(result, asArrayModes(list->list()[i]->indexingType()));
</del><ins>+ forEach(
+ [&] (Structure* structure) {
+ mergeArrayModes(result, asArrayModes(structure->indexingType()));
+ });
</ins><span class="cx"> return result;
</span><span class="cx"> }
</span><span class="cx">
</span><span class="lines">@@ -329,8 +87,7 @@
</span><span class="cx"> {
</span><span class="cx"> CommaPrinter comma;
</span><span class="cx"> out.print("[");
</span><del>- for (size_t i = 0; i < size(); ++i)
- out.print(comma, inContext(*at(i), context));
</del><ins>+ forEach([&] (Structure* structure) { out.print(comma, inContext(*structure, context)); });
</ins><span class="cx"> out.print("]");
</span><span class="cx"> }
</span><span class="cx">
</span><span class="lines">@@ -339,59 +96,5 @@
</span><span class="cx"> dumpInContext(out, nullptr);
</span><span class="cx"> }
</span><span class="cx">
</span><del>-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);
-}
-
</del><span class="cx"> } // namespace JSC
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceJavaScriptCorebytecodeStructureSeth"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/bytecode/StructureSet.h (185323 => 185324)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/bytecode/StructureSet.h 2015-06-08 18:21:59 UTC (rev 185323)
+++ trunk/Source/JavaScriptCore/bytecode/StructureSet.h 2015-06-08 19:41:47 UTC (rev 185324)
</span><span class="lines">@@ -1,5 +1,5 @@
</span><span class="cx"> /*
</span><del>- * Copyright (C) 2011, 2013, 2014 Apple Inc. All rights reserved.
</del><ins>+ * Copyright (C) 2011, 2013-2015 Apple Inc. All rights reserved.
</ins><span class="cx"> *
</span><span class="cx"> * Redistribution and use in source and binary forms, with or without
</span><span class="cx"> * modification, are permitted provided that the following conditions
</span><span class="lines">@@ -30,6 +30,7 @@
</span><span class="cx"> #include "SpeculatedType.h"
</span><span class="cx"> #include "Structure.h"
</span><span class="cx"> #include "DumpContext.h"
</span><ins>+#include <wtf/TinyPtrSet.h>
</ins><span class="cx">
</span><span class="cx"> namespace JSC {
</span><span class="cx">
</span><span class="lines">@@ -38,68 +39,32 @@
</span><span class="cx"> struct AbstractValue;
</span><span class="cx"> }
</span><span class="cx">
</span><del>-class StructureSet {
</del><ins>+class StructureSet : public TinyPtrSet<Structure*> {
</ins><span class="cx"> public:
</span><ins>+ // I really want to do this:
+ // using TinyPtrSet::TinyPtrSet;
+ //
+ // But I can't because Windows.
+
</ins><span class="cx"> StructureSet()
</span><del>- : m_pointer(0)
</del><span class="cx"> {
</span><del>- setEmpty();
</del><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> StructureSet(Structure* structure)
</span><del>- : m_pointer(0)
</del><ins>+ : TinyPtrSet(structure)
</ins><span class="cx"> {
</span><del>- set(structure);
</del><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> ALWAYS_INLINE StructureSet(const StructureSet& other)
</span><del>- : m_pointer(0)
</del><ins>+ : TinyPtrSet(other)
</ins><span class="cx"> {
</span><del>- copyFrom(other);
</del><span class="cx"> }
</span><span class="cx">
</span><del>- ALWAYS_INLINE StructureSet& operator=(const StructureSet& other)
- {
- if (this == &other)
- return *this;
- deleteStructureListIfNecessary();
- copyFrom(other);
- return *this;
- }
-
- ~StructureSet()
- {
- deleteStructureListIfNecessary();
- }
-
- void clear();
-
</del><span class="cx"> Structure* onlyStructure() const
</span><span class="cx"> {
</span><del>- if (isThin())
- return singleStructure();
- OutOfLineList* list = structureList();
- if (list->m_length != 1)
- return nullptr;
- return list->list()[0];
</del><ins>+ return onlyEntry();
</ins><span class="cx"> }
</span><span class="cx">
</span><del>- 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&);
-
</del><span class="cx"> #if ENABLE(DFG_JIT)
</span><span class="cx"> void filter(const DFG::StructureAbstractValue&);
</span><span class="cx"> void filter(SpeculatedType);
</span><span class="lines">@@ -107,212 +72,11 @@
</span><span class="cx"> void filter(const DFG::AbstractValue&);
</span><span class="cx"> #endif // ENABLE(DFG_JIT)
</span><span class="cx">
</span><del>- 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;
-
</del><span class="cx"> SpeculatedType speculationFromStructures() const;
</span><span class="cx"> ArrayModes arrayModesFromStructures() const;
</span><span class="cx">
</span><span class="cx"> void dumpInContext(PrintStream&, DumpContext*) const;
</span><span class="cx"> void dump(PrintStream&) const;
</span><del>-
-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;
</del><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> } // namespace JSC
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGStructureAbstractValuecpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGStructureAbstractValue.cpp (185323 => 185324)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGStructureAbstractValue.cpp 2015-06-08 18:21:59 UTC (rev 185323)
+++ trunk/Source/JavaScriptCore/dfg/DFGStructureAbstractValue.cpp 2015-06-08 19:41:47 UTC (rev 185324)
</span><span class="lines">@@ -1,5 +1,5 @@
</span><span class="cx"> /*
</span><del>- * Copyright (C) 2014 Apple Inc. All rights reserved.
</del><ins>+ * Copyright (C) 2014, 2015 Apple Inc. All rights reserved.
</ins><span class="cx"> *
</span><span class="cx"> * Redistribution and use in source and binary forms, with or without
</span><span class="cx"> * modification, are permitted provided that the following conditions
</span><span class="lines">@@ -64,14 +64,14 @@
</span><span class="cx"> setClobbered(true);
</span><span class="cx">
</span><span class="cx"> if (m_set.isThin()) {
</span><del>- if (!m_set.singleStructure())
</del><ins>+ if (!m_set.singleEntry())
</ins><span class="cx"> return;
</span><del>- if (!m_set.singleStructure()->dfgShouldWatch())
</del><ins>+ if (!m_set.singleEntry()->dfgShouldWatch())
</ins><span class="cx"> makeTopWhenThin();
</span><span class="cx"> return;
</span><span class="cx"> }
</span><del>-
- StructureSet::OutOfLineList* list = m_set.structureList();
</del><ins>+
+ StructureSet::OutOfLineList* list = m_set.list();
</ins><span class="cx"> for (unsigned i = list->m_length; i--;) {
</span><span class="cx"> if (!list->list()[i]->dfgShouldWatch()) {
</span><span class="cx"> makeTop();
</span><span class="lines">@@ -268,25 +268,6 @@
</span><span class="cx"> filter(other.m_set);
</span><span class="cx"> }
</span><span class="cx">
</span><del>-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
-
</del><span class="cx"> void StructureAbstractValue::filterSlow(SpeculatedType type)
</span><span class="cx"> {
</span><span class="cx"> SAMPLE("StructureAbstractValue filter type slow");
</span><span class="lines">@@ -298,8 +279,10 @@
</span><span class="cx">
</span><span class="cx"> ASSERT(!isTop());
</span><span class="cx">
</span><del>- ConformsToType conformsToType(type);
- m_set.genericFilter(conformsToType);
</del><ins>+ m_set.genericFilter(
+ [&] (Structure* structure) {
+ return !!(speculationFromStructure(structure) & type);
+ });
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> bool StructureAbstractValue::contains(Structure* structure) const
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGStructureAbstractValueh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGStructureAbstractValue.h (185323 => 185324)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGStructureAbstractValue.h 2015-06-08 18:21:59 UTC (rev 185323)
+++ trunk/Source/JavaScriptCore/dfg/DFGStructureAbstractValue.h 2015-06-08 19:41:47 UTC (rev 185324)
</span><span class="lines">@@ -1,5 +1,5 @@
</span><span class="cx"> /*
</span><del>- * Copyright (C) 2011, 2012, 2013, 2014 Apple Inc. All rights reserved.
</del><ins>+ * Copyright (C) 2011-2015 Apple Inc. All rights reserved.
</ins><span class="cx"> *
</span><span class="cx"> * Redistribution and use in source and binary forms, with or without
</span><span class="cx"> * modification, are permitted provided that the following conditions
</span><span class="lines">@@ -40,7 +40,7 @@
</span><span class="cx"> public:
</span><span class="cx"> StructureAbstractValue() { }
</span><span class="cx"> StructureAbstractValue(Structure* structure)
</span><del>- : m_set(structure)
</del><ins>+ : m_set(StructureSet(structure))
</ins><span class="cx"> {
</span><span class="cx"> setClobbered(false);
</span><span class="cx"> }
</span><span class="lines">@@ -57,7 +57,7 @@
</span><span class="cx">
</span><span class="cx"> ALWAYS_INLINE StructureAbstractValue& operator=(Structure* structure)
</span><span class="cx"> {
</span><del>- m_set = structure;
</del><ins>+ m_set = StructureSet(structure);
</ins><span class="cx"> setClobbered(false);
</span><span class="cx"> return *this;
</span><span class="cx"> }
</span><span class="lines">@@ -82,7 +82,7 @@
</span><span class="cx">
</span><span class="cx"> void makeTop()
</span><span class="cx"> {
</span><del>- m_set.deleteStructureListIfNecessary();
</del><ins>+ m_set.deleteListIfNecessary();
</ins><span class="cx"> m_set.m_pointer = topValue;
</span><span class="cx"> }
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceWTFChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/ChangeLog (185323 => 185324)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/ChangeLog 2015-06-08 18:21:59 UTC (rev 185323)
+++ trunk/Source/WTF/ChangeLog 2015-06-08 19:41:47 UTC (rev 185324)
</span><span class="lines">@@ -1,3 +1,66 @@
</span><ins>+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):
+
</ins><span class="cx"> 2015-06-08 Michael Catanzaro <mcatanzaro@igalia.com>
</span><span class="cx">
</span><span class="cx"> [SOUP] Performs DNS prefetch when a proxy is configured (information leak)
</span></span></pre></div>
<a id="trunkSourceWTFWTFvcxprojWTFvcxproj"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/WTF.vcxproj/WTF.vcxproj (185323 => 185324)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/WTF.vcxproj/WTF.vcxproj 2015-06-08 18:21:59 UTC (rev 185323)
+++ trunk/Source/WTF/WTF.vcxproj/WTF.vcxproj 2015-06-08 19:41:47 UTC (rev 185324)
</span><span class="lines">@@ -300,6 +300,7 @@
</span><span class="cx"> <ClInclude Include="..\wtf\threadsafeRefCounted.h" />
</span><span class="cx"> <ClInclude Include="..\wtf\threadspecific.h" />
</span><span class="cx"> <ClInclude Include="..\wtf\threads\BinarySemaphore.h" />
</span><ins>+ <ClInclude Include="..\wtf\TinyPtrSet.h" />
</ins><span class="cx"> <ClInclude Include="..\wtf\unicode\CharacterNames.h" />
</span><span class="cx"> <ClInclude Include="..\wtf\unicode\Collator.h" />
</span><span class="cx"> <ClInclude Include="..\wtf\unicode\UTF8.h" />
</span></span></pre></div>
<a id="trunkSourceWTFWTFxcodeprojprojectpbxproj"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/WTF.xcodeproj/project.pbxproj (185323 => 185324)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/WTF.xcodeproj/project.pbxproj 2015-06-08 18:21:59 UTC (rev 185323)
+++ trunk/Source/WTF/WTF.xcodeproj/project.pbxproj 2015-06-08 19:41:47 UTC (rev 185324)
</span><span class="lines">@@ -40,6 +40,7 @@
</span><span class="cx"> 0FD81AC5154FB22E00983E72 /* FastBitVector.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FD81AC4154FB22E00983E72 /* FastBitVector.h */; settings = {ATTRIBUTES = (); }; };
</span><span class="cx"> 0FDDBFA71666DFA300C55FEF /* StringPrintStream.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FDDBFA51666DFA300C55FEF /* StringPrintStream.cpp */; };
</span><span class="cx"> 0FDDBFA81666DFA300C55FEF /* StringPrintStream.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FDDBFA61666DFA300C55FEF /* StringPrintStream.h */; };
</span><ins>+ 0FED67B61B22D4D80066CE15 /* TinyPtrSet.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FED67B51B22D4D80066CE15 /* TinyPtrSet.h */; };
</ins><span class="cx"> 14022F4118F5C3FC007FF0EB /* libbmalloc.a in Frameworks */ = {isa = PBXBuildFile; fileRef = 14022F4018F5C3FC007FF0EB /* libbmalloc.a */; };
</span><span class="cx"> 143F611F1565F0F900DB514A /* RAMSize.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 143F611D1565F0F900DB514A /* RAMSize.cpp */; };
</span><span class="cx"> 143F61201565F0F900DB514A /* RAMSize.h in Headers */ = {isa = PBXBuildFile; fileRef = 143F611E1565F0F900DB514A /* RAMSize.h */; settings = {ATTRIBUTES = (); }; };
</span><span class="lines">@@ -320,6 +321,7 @@
</span><span class="cx"> 0FDDBFA51666DFA300C55FEF /* StringPrintStream.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = StringPrintStream.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 0FDDBFA61666DFA300C55FEF /* StringPrintStream.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = StringPrintStream.h; sourceTree = "<group>"; };
</span><span class="cx"> 0FEC3EE4171B834700FDAC8D /* ByteSpinLock.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = ByteSpinLock.h; sourceTree = "<group>"; };
</span><ins>+ 0FED67B51B22D4D80066CE15 /* TinyPtrSet.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = TinyPtrSet.h; sourceTree = "<group>"; };
</ins><span class="cx"> 14022F4018F5C3FC007FF0EB /* libbmalloc.a */ = {isa = PBXFileReference; lastKnownFileType = archive.ar; path = libbmalloc.a; sourceTree = BUILT_PRODUCTS_DIR; };
</span><span class="cx"> 143F611D1565F0F900DB514A /* RAMSize.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = RAMSize.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 143F611E1565F0F900DB514A /* RAMSize.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = RAMSize.h; sourceTree = "<group>"; };
</span><span class="lines">@@ -862,6 +864,7 @@
</span><span class="cx"> A8A47336151A825B004123FF /* ThreadingPthreads.cpp */,
</span><span class="cx"> A8A4733E151A825B004123FF /* ThreadSafeRefCounted.h */,
</span><span class="cx"> A8A4733F151A825B004123FF /* ThreadSpecific.h */,
</span><ins>+ 0FED67B51B22D4D80066CE15 /* TinyPtrSet.h */,
</ins><span class="cx"> 149EF16216BBFE0D000A4331 /* TriState.h */,
</span><span class="cx"> 83FBA93119DF459700F30ADB /* TypeCasts.h */,
</span><span class="cx"> A8A4735C151A825B004123FF /* UnionFind.h */,
</span><span class="lines">@@ -1201,6 +1204,7 @@
</span><span class="cx"> A8A4747D151A825B004123FF /* ValueCheck.h in Headers */,
</span><span class="cx"> A8A4747E151A825B004123FF /* Vector.h in Headers */,
</span><span class="cx"> A8A4747F151A825B004123FF /* VectorTraits.h in Headers */,
</span><ins>+ 0FED67B61B22D4D80066CE15 /* TinyPtrSet.h in Headers */,
</ins><span class="cx"> A8A47480151A825B004123FF /* VMTags.h in Headers */,
</span><span class="cx"> 974CFC8E16A4F327006D5404 /* WeakPtr.h in Headers */,
</span><span class="cx"> E4A0AD3A1A96245500536DF6 /* WorkQueue.h in Headers */,
</span></span></pre></div>
<a id="trunkSourceWTFwtfCMakeListstxt"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/wtf/CMakeLists.txt (185323 => 185324)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/wtf/CMakeLists.txt 2015-06-08 18:21:59 UTC (rev 185323)
+++ trunk/Source/WTF/wtf/CMakeLists.txt 2015-06-08 19:41:47 UTC (rev 185324)
</span><span class="lines">@@ -94,6 +94,7 @@
</span><span class="cx"> ThreadSpecific.h
</span><span class="cx"> Threading.h
</span><span class="cx"> ThreadingPrimitives.h
</span><ins>+ TinyPtrSet.h
</ins><span class="cx"> VMTags.h
</span><span class="cx"> ValueCheck.h
</span><span class="cx"> Vector.h
</span></span></pre></div>
<a id="trunkSourceWTFwtfTinyPtrSeth"></a>
<div class="addfile"><h4>Added: trunk/Source/WTF/wtf/TinyPtrSet.h (0 => 185324)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/wtf/TinyPtrSet.h (rev 0)
+++ trunk/Source/WTF/wtf/TinyPtrSet.h 2015-06-08 19:41:47 UTC (rev 185324)
</span><span class="lines">@@ -0,0 +1,517 @@
</span><ins>+/*
+ * 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
+
</ins></span></pre>
</div>
</div>
</body>
</html>