⚠ Archived content — this site is no longer maintained.   Current WebKit documentation is at docs.webkit.org.

Changeset 176290 in webkit


Ignore:
Timestamp:
Nov 18, 2014, 3:06:00 PM (12 years ago)
Author:
ggaren@apple.com
Message:

Removed the custom allocator for ListHashSet nodes
​https://bugs.webkit.org/show_bug.cgi?id=138841

Reviewed by Andreas Kling.

Source/WebCore:

Uses of ListHashSet no longer need to declare an inline capacity,
since that was only used to specify the capacity of the custom allocator.

  • dom/DOMNamedFlowCollection.h:
  • dom/DocumentEventQueue.h:
  • dom/DocumentStyleSheetCollection.h:
  • dom/NamedFlowCollection.h:
  • html/FormController.h:
  • rendering/FloatingObjects.h:
  • rendering/RenderBlock.h:

Source/WebKit2:

Uses of ListHashSet no longer need to declare an inline capacity,
since that was only used to specify the capacity of the custom allocator.

  • UIProcess/Plugins/PluginInfoStore.cpp:

(WebKit::PluginInfoStore::loadPluginsIfNecessary):

Source/WTF:

bmalloc is fast, so we don't need a custom allocator.

The MallocBench test for linked list node allocation (list_allocate) is
4.09X faster in bmalloc than TCMalloc. Also, I wrote a stress test to
add/remove link elements, which modify a ListHashSet on insertion and
removal, and it was 1% faster / in the noise with bmalloc enabled.

  • wtf/ListHashSet.h:

(WTF::ListHashSetNode::ListHashSetNode):
(WTF::ListHashSetTranslator::translate):
(WTF::U>::ListHashSet):
(WTF::=):
(WTF::U>::swap):
(WTF::U>::~ListHashSet):
(WTF::U>::size):
(WTF::U>::capacity):
(WTF::U>::isEmpty):
(WTF::U>::first):
(WTF::U>::removeFirst):
(WTF::U>::takeFirst):
(WTF::U>::last):
(WTF::U>::removeLast):
(WTF::U>::takeLast):
(WTF::U>::contains):
(WTF::U>::remove):
(WTF::U>::clear):
(WTF::U>::unlink):
(WTF::U>::unlinkAndDelete):
(WTF::U>::appendNode):
(WTF::U>::prependNode):
(WTF::U>::insertNodeBefore):
(WTF::U>::deleteAllNodes):
(WTF::ListHashSetNodeAllocator::ListHashSetNodeAllocator): Deleted.
(WTF::ListHashSetNodeAllocator::allocate): Deleted.
(WTF::ListHashSetNodeAllocator::deallocate): Deleted.
(WTF::ListHashSetNodeAllocator::pool): Deleted.
(WTF::ListHashSetNodeAllocator::pastPool): Deleted.
(WTF::ListHashSetNodeAllocator::inPool): Deleted.
(WTF::ListHashSetNode::operator new): Deleted.
(WTF::ListHashSetNode::destroy): Deleted.

Location:
trunk/Source
Files:
13 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/WTF/ChangeLog

    r176275 r176290  
     12014-11-18  Geoffrey Garen  <ggaren@apple.com>
     2
     3        Removed the custom allocator for ListHashSet nodes
     4        https://bugs.webkit.org/show_bug.cgi?id=138841
     5
     6        Reviewed by Andreas Kling.
     7
     8        bmalloc is fast, so we don't need a custom allocator.
     9
     10        The MallocBench test for linked list node allocation (list_allocate) is
     11        4.09X faster in bmalloc than TCMalloc. Also, I wrote a stress test to
     12        add/remove link elements, which modify a ListHashSet on insertion and
     13        removal, and it was 1% faster / in the noise with bmalloc enabled.
     14
     15        * wtf/ListHashSet.h:
     16        (WTF::ListHashSetNode::ListHashSetNode):
     17        (WTF::ListHashSetTranslator::translate):
     18        (WTF::U>::ListHashSet):
     19        (WTF::=):
     20        (WTF::U>::swap):
     21        (WTF::U>::~ListHashSet):
     22        (WTF::U>::size):
     23        (WTF::U>::capacity):
     24        (WTF::U>::isEmpty):
     25        (WTF::U>::first):
     26        (WTF::U>::removeFirst):
     27        (WTF::U>::takeFirst):
     28        (WTF::U>::last):
     29        (WTF::U>::removeLast):
     30        (WTF::U>::takeLast):
     31        (WTF::U>::contains):
     32        (WTF::U>::remove):
     33        (WTF::U>::clear):
     34        (WTF::U>::unlink):
     35        (WTF::U>::unlinkAndDelete):
     36        (WTF::U>::appendNode):
     37        (WTF::U>::prependNode):
     38        (WTF::U>::insertNodeBefore):
     39        (WTF::U>::deleteAllNodes):
     40        (WTF::ListHashSetNodeAllocator::ListHashSetNodeAllocator): Deleted.
     41        (WTF::ListHashSetNodeAllocator::allocate): Deleted.
     42        (WTF::ListHashSetNodeAllocator::deallocate): Deleted.
     43        (WTF::ListHashSetNodeAllocator::pool): Deleted.
     44        (WTF::ListHashSetNodeAllocator::pastPool): Deleted.
     45        (WTF::ListHashSetNodeAllocator::inPool): Deleted.
     46        (WTF::ListHashSetNode::operator new): Deleted.
     47        (WTF::ListHashSetNode::destroy): Deleted.
     48
    1492014-11-18  Chris Dumez  <cdumez@apple.com>
    250

  • trunk/Source/WTF/wtf/ListHashSet.h

    r170774 r176290  
    3939// removal of the item currently pointed to by a given iterator.
    4040
    41 template<typename Value, size_t inlineCapacity, typename HashFunctions> class ListHashSet;
    42 
    43 template<typename ValueArg, size_t inlineCapacity, typename HashArg> class ListHashSetIterator;
    44 template<typename ValueArg, size_t inlineCapacity, typename HashArg> class ListHashSetConstIterator;
    45 
    46 template<typename ValueArg, size_t inlineCapacity> struct ListHashSetNode;
    47 template<typename ValueArg, size_t inlineCapacity> class ListHashSetNodeAllocator;
     41template<typename Value, typename HashFunctions> class ListHashSet;
     42
     43template<typename ValueArg, typename HashArg> class ListHashSetIterator;
     44template<typename ValueArg, typename HashArg> class ListHashSetConstIterator;
     45
     46template<typename ValueArg> struct ListHashSetNode;
    4847
    4948template<typename HashArg> struct ListHashSetNodeHashFunctions;
    5049template<typename HashArg> struct ListHashSetTranslator;
    5150
    52 template<typename ValueArg, size_t inlineCapacity = 256, typename HashArg = typename DefaultHash<ValueArg>::Hash> class ListHashSet {
     51template<typename ValueArg, typename HashArg = typename DefaultHash<ValueArg>::Hash> class ListHashSet {
    5352    WTF_MAKE_FAST_ALLOCATED;
    5453private:
    55     typedef ListHashSetNode<ValueArg, inlineCapacity> Node;
    56     typedef ListHashSetNodeAllocator<ValueArg, inlineCapacity> NodeAllocator;
     54    typedef ListHashSetNode<ValueArg> Node;
    5755
    5856    typedef HashTraits<Node*> NodeTraits;
    … …  
    6563    typedef ValueArg ValueType;
    6664
    67     typedef ListHashSetIterator<ValueType, inlineCapacity, HashArg> iterator;
    68     typedef ListHashSetConstIterator<ValueType, inlineCapacity, HashArg> const_iterator;
    69     friend class ListHashSetConstIterator<ValueType, inlineCapacity, HashArg>;
     65    typedef ListHashSetIterator<ValueType, HashArg> iterator;
     66    typedef ListHashSetConstIterator<ValueType, HashArg> const_iterator;
     67    friend class ListHashSetConstIterator<ValueType, HashArg>;
    7068
    7169    typedef std::reverse_iterator<iterator> reverse_iterator;
    … …  
    156154    Node* m_head;
    157155    Node* m_tail;
    158     std::unique_ptr<NodeAllocator> m_allocator;
    159156};
    160157
    161 template<typename ValueArg, size_t inlineCapacity> class ListHashSetNodeAllocator {
     158template<typename ValueArg> struct ListHashSetNode {
    162159    WTF_MAKE_FAST_ALLOCATED;
    163 
    164160public:
    165     typedef ListHashSetNode<ValueArg, inlineCapacity> Node;
    166     typedef ListHashSetNodeAllocator<ValueArg, inlineCapacity> NodeAllocator;
    167 
    168     ListHashSetNodeAllocator()
    169         : m_freeList(pool())
    170         , m_isDoneWithInitialFreeList(false)
    171     {
    172         memset(m_pool.pool, 0, sizeof(m_pool.pool));
    173     }
    174 
    175     Node* allocate()
    176     {
    177         Node* result = m_freeList;
    178 
    179         if (!result)
    180             return static_cast<Node*>(fastMalloc(sizeof(Node)));
    181 
    182         ASSERT(!result->m_isAllocated);
    183 
    184         Node* next = result->m_next;
    185         ASSERT(!next || !next->m_isAllocated);
    186         if (!next && !m_isDoneWithInitialFreeList) {
    187             next = result + 1;
    188             if (next == pastPool()) {
    189                 m_isDoneWithInitialFreeList = true;
    190                 next = 0;
    191             } else {
    192                 ASSERT(inPool(next));
    193                 ASSERT(!next->m_isAllocated);
    194             }
    195         }
    196         m_freeList = next;
    197 
    198         return result;
    199     }
    200 
    201     void deallocate(Node* node)
    202     {
    203         if (inPool(node)) {
    204 #ifndef NDEBUG
    205             node->m_isAllocated = false;
    206 #endif
    207             node->m_next = m_freeList;
    208             m_freeList = node;
    209             return;
    210         }
    211 
    212         fastFree(node);
    213     }
    214 
    215 private:
    216     Node* pool() { return reinterpret_cast_ptr<Node*>(m_pool.pool); }
    217     Node* pastPool() { return pool() + m_poolSize; }
    218     bool inPool(Node* node)
    219     {
    220         return node >= pool() && node < pastPool();
    221     }
    222 
    223     Node* m_freeList;
    224     bool m_isDoneWithInitialFreeList;
    225     static const size_t m_poolSize = inlineCapacity;
    226     union {
    227         char pool[sizeof(Node) * m_poolSize];
    228         double forAlignment;
    229     } m_pool;
    230 };
    231 
    232 template<typename ValueArg, size_t inlineCapacity> struct ListHashSetNode {
    233     typedef ListHashSetNodeAllocator<ValueArg, inlineCapacity> NodeAllocator;
    234 
    235161    template<typename T>
    236162    ListHashSetNode(T&& value)
    … …  
    238164        , m_prev(0)
    239165        , m_next(0)
    240 #ifndef NDEBUG
    241         , m_isAllocated(true)
    242 #endif
    243     {
    244     }
    245 
    246     void* operator new(size_t, NodeAllocator* allocator)
    247     {
    248         return allocator->allocate();
    249     }
    250     void destroy(NodeAllocator* allocator)
    251     {
    252         this->~ListHashSetNode();
    253         allocator->deallocate(this);
     166    {
    254167    }
    255168
    … …  
    257170    ListHashSetNode* m_prev;
    258171    ListHashSetNode* m_next;
    259 
    260 #ifndef NDEBUG
    261     bool m_isAllocated;
    262 #endif
    263172};
    264173
    … …  
    269178};
    270179
    271 template<typename ValueArg, size_t inlineCapacity, typename HashArg> class ListHashSetIterator {
     180template<typename ValueArg, typename HashArg> class ListHashSetIterator {
    272181private:
    273     typedef ListHashSet<ValueArg, inlineCapacity, HashArg> ListHashSetType;
    274     typedef ListHashSetIterator<ValueArg, inlineCapacity, HashArg> iterator;
    275     typedef ListHashSetConstIterator<ValueArg, inlineCapacity, HashArg> const_iterator;
    276     typedef ListHashSetNode<ValueArg, inlineCapacity> Node;
     182    typedef ListHashSet<ValueArg, HashArg> ListHashSetType;
     183    typedef ListHashSetIterator<ValueArg, HashArg> iterator;
     184    typedef ListHashSetConstIterator<ValueArg, HashArg> const_iterator;
     185    typedef ListHashSetNode<ValueArg> Node;
    277186    typedef ValueArg ValueType;
    278187
    279     friend class ListHashSet<ValueArg, inlineCapacity, HashArg>;
     188    friend class ListHashSet<ValueArg, HashArg>;
    280189
    281190    ListHashSetIterator(const ListHashSetType* set, Node* position) : m_iterator(set, position) { }
    … …  
    316225};
    317226
    318 template<typename ValueArg, size_t inlineCapacity, typename HashArg> class ListHashSetConstIterator {
     227template<typename ValueArg, typename HashArg> class ListHashSetConstIterator {
    319228private:
    320     typedef ListHashSet<ValueArg, inlineCapacity, HashArg> ListHashSetType;
    321     typedef ListHashSetIterator<ValueArg, inlineCapacity, HashArg> iterator;
    322     typedef ListHashSetConstIterator<ValueArg, inlineCapacity, HashArg> const_iterator;
    323     typedef ListHashSetNode<ValueArg, inlineCapacity> Node;
     229    typedef ListHashSet<ValueArg, HashArg> ListHashSetType;
     230    typedef ListHashSetIterator<ValueArg, HashArg> iterator;
     231    typedef ListHashSetConstIterator<ValueArg, HashArg> const_iterator;
     232    typedef ListHashSetNode<ValueArg> Node;
    324233    typedef ValueArg ValueType;
    325234
    326     friend class ListHashSet<ValueArg, inlineCapacity, HashArg>;
    327     friend class ListHashSetIterator<ValueArg, inlineCapacity, HashArg>;
     235    friend class ListHashSet<ValueArg, HashArg>;
     236    friend class ListHashSetIterator<ValueArg, HashArg>;
    328237
    329238    ListHashSetConstIterator(const ListHashSetType* set, Node* position)
    … …  
    394303    template<typename T> static unsigned hash(const T& key) { return HashFunctions::hash(key); }
    395304    template<typename T, typename U> static bool equal(const T& a, const U& b) { return HashFunctions::equal(a->m_value, b); }
    396     template<typename T, typename U, typename V> static void translate(T*& location, U&& key, const V& allocator)
    397     {
    398         location = new (allocator) T(std::forward<U>(key));
     305    template<typename T, typename U, typename V> static void translate(T*& location, U&& key, V&&)
     306    {
     307        location = new T(std::forward<U>(key));
    399308    }
    400309};
    401310
    402 template<typename T, size_t inlineCapacity, typename U>
    403 inline ListHashSet<T, inlineCapacity, U>::ListHashSet()
     311template<typename T, typename U>
     312inline ListHashSet<T, U>::ListHashSet()
    404313    : m_head(0)
    405314    , m_tail(0)
    406     , m_allocator(std::make_unique<NodeAllocator>())
    407 {
    408 }
    409 
    410 template<typename T, size_t inlineCapacity, typename U>
    411 inline ListHashSet<T, inlineCapacity, U>::ListHashSet(const ListHashSet& other)
     315{
     316}
     317
     318template<typename T, typename U>
     319inline ListHashSet<T, U>::ListHashSet(const ListHashSet& other)
    412320    : m_head(0)
    413321    , m_tail(0)
    414     , m_allocator(std::make_unique<NodeAllocator>())
    415322{
    416323    for (auto it = other.begin(), end = other.end(); it != end; ++it)
    … …  
    418325}
    419326
    420 template<typename T, size_t inlineCapacity, typename U>
    421 inline ListHashSet<T, inlineCapacity, U>& ListHashSet<T, inlineCapacity, U>::operator=(const ListHashSet& other)
     327template<typename T, typename U>
     328inline ListHashSet<T, U>& ListHashSet<T, U>::operator=(const ListHashSet& other)
    422329{
    423330    ListHashSet tmp(other);
    … …  
    426333}
    427334
    428 template<typename T, size_t inlineCapacity, typename U>
    429 inline void ListHashSet<T, inlineCapacity, U>::swap(ListHashSet& other)
     335template<typename T, typename U>
     336inline void ListHashSet<T, U>::swap(ListHashSet& other)
    430337{
    431338    m_impl.swap(other.m_impl);
    432339    std::swap(m_head, other.m_head);
    433340    std::swap(m_tail, other.m_tail);
    434     m_allocator.swap(other.m_allocator);
    435 }
    436 
    437 template<typename T, size_t inlineCapacity, typename U>
    438 inline ListHashSet<T, inlineCapacity, U>::~ListHashSet()
     341}
     342
     343template<typename T, typename U>
     344inline ListHashSet<T, U>::~ListHashSet()
    439345{
    440346    deleteAllNodes();
    441347}
    442348
    443 template<typename T, size_t inlineCapacity, typename U>
    444 inline int ListHashSet<T, inlineCapacity, U>::size() const
     349template<typename T, typename U>
     350inline int ListHashSet<T, U>::size() const
    445351{
    446352    return m_impl.size();
    447353}
    448354
    449 template<typename T, size_t inlineCapacity, typename U>
    450 inline int ListHashSet<T, inlineCapacity, U>::capacity() const
     355template<typename T, typename U>
     356inline int ListHashSet<T, U>::capacity() const
    451357{
    452358    return m_impl.capacity();
    453359}
    454360
    455 template<typename T, size_t inlineCapacity, typename U>
    456 inline bool ListHashSet<T, inlineCapacity, U>::isEmpty() const
     361template<typename T, typename U>
     362inline bool ListHashSet<T, U>::isEmpty() const
    457363{
    458364    return m_impl.isEmpty();
    459365}
    460366
    461 template<typename T, size_t inlineCapacity, typename U>
    462 inline T& ListHashSet<T, inlineCapacity, U>::first()
     367template<typename T, typename U>
     368inline T& ListHashSet<T, U>::first()
    463369{
    464370    ASSERT(!isEmpty());
    … …  
    466372}
    467373
    468 template<typename T, size_t inlineCapacity, typename U>
    469 inline void ListHashSet<T, inlineCapacity, U>::removeFirst()
     374template<typename T, typename U>
     375inline void ListHashSet<T, U>::removeFirst()
    470376{
    471377    takeFirst();
    472378}
    473379
    474 template<typename T, size_t inlineCapacity, typename U>
    475 inline T ListHashSet<T, inlineCapacity, U>::takeFirst()
     380template<typename T, typename U>
     381inline T ListHashSet<T, U>::takeFirst()
    476382{
    477383    ASSERT(!isEmpty());
    … …  
    485391}
    486392
    487 template<typename T, size_t inlineCapacity, typename U>
    488 inline const T& ListHashSet<T, inlineCapacity, U>::first() const
     393template<typename T, typename U>
     394inline const T& ListHashSet<T, U>::first() const
    489395{
    490396    ASSERT(!isEmpty());
    … …  
    492398}
    493399
    494 template<typename T, size_t inlineCapacity, typename U>
    495 inline T& ListHashSet<T, inlineCapacity, U>::last()
     400template<typename T, typename U>
     401inline T& ListHashSet<T, U>::last()
    496402{
    497403    ASSERT(!isEmpty());
    … …  
    499405}
    500406
    501 template<typename T, size_t inlineCapacity, typename U>
    502 inline const T& ListHashSet<T, inlineCapacity, U>::last() const
     407template<typename T, typename U>
     408inline const T& ListHashSet<T, U>::last() const
    503409{
    504410    ASSERT(!isEmpty());
    … …  
    506412}
    507413
    508 template<typename T, size_t inlineCapacity, typename U>
    509 inline void ListHashSet<T, inlineCapacity, U>::removeLast()
     414template<typename T, typename U>
     415inline void ListHashSet<T, U>::removeLast()
    510416{
    511417    takeLast();
    512418}
    513419
    514 template<typename T, size_t inlineCapacity, typename U>
    515 inline T ListHashSet<T, inlineCapacity, U>::takeLast()
     420template<typename T, typename U>
     421inline T ListHashSet<T, U>::takeLast()
    516422{
    517423    ASSERT(!isEmpty());
    … …  
    525431}
    526432
    527 template<typename T, size_t inlineCapacity, typename U>
    528 inline auto ListHashSet<T, inlineCapacity, U>::find(const ValueType& value) -> iterator
     433template<typename T, typename U>
     434inline auto ListHashSet<T, U>::find(const ValueType& value) -> iterator
    529435{
    530436    auto it = m_impl.template find<BaseTranslator>(value);
    … …  
    534440}
    535441
    536 template<typename T, size_t inlineCapacity, typename U>
    537 inline auto ListHashSet<T, inlineCapacity, U>::find(const ValueType& value) const -> const_iterator
     442template<typename T, typename U>
     443inline auto ListHashSet<T, U>::find(const ValueType& value) const -> const_iterator
    538444{
    539445    auto it = m_impl.template find<BaseTranslator>(value);
    … …  
    549455};
    550456
    551 template<typename ValueType, size_t inlineCapacity, typename U>
     457template<typename ValueType, typename U>
    552458template<typename T, typename HashTranslator>
    553 inline auto ListHashSet<ValueType, inlineCapacity, U>::find(const T& value) -> iterator
     459inline auto ListHashSet<ValueType, U>::find(const T& value) -> iterator
    554460{
    555461    auto it = m_impl.template find<ListHashSetTranslatorAdapter<HashTranslator>>(value);
    … …  
    559465}
    560466
    561 template<typename ValueType, size_t inlineCapacity, typename U>
     467template<typename ValueType, typename U>
    562468template<typename T, typename HashTranslator>
    563 inline auto ListHashSet<ValueType, inlineCapacity, U>::find(const T& value) const -> const_iterator
     469inline auto ListHashSet<ValueType, U>::find(const T& value) const -> const_iterator
    564470{
    565471    auto it = m_impl.template find<ListHashSetTranslatorAdapter<HashTranslator>>(value);
    … …  
    569475}
    570476
    571 template<typename ValueType, size_t inlineCapacity, typename U>
     477template<typename ValueType, typename U>
    572478template<typename T, typename HashTranslator>
    573 inline bool ListHashSet<ValueType, inlineCapacity, U>::contains(const T& value) const
     479inline bool ListHashSet<ValueType, U>::contains(const T& value) const
    574480{
    575481    return m_impl.template contains<ListHashSetTranslatorAdapter<HashTranslator>>(value);
    576482}
    577483
    578 template<typename T, size_t inlineCapacity, typename U>
    579 inline bool ListHashSet<T, inlineCapacity, U>::contains(const ValueType& value) const
     484template<typename T, typename U>
     485inline bool ListHashSet<T, U>::contains(const ValueType& value) const
    580486{
    581487    return m_impl.template contains<BaseTranslator>(value);
    582488}
    583489
    584 template<typename T, size_t inlineCapacity, typename U>
    585 auto ListHashSet<T, inlineCapacity, U>::add(const ValueType& value) -> AddResult
    586 {
    587     auto result = m_impl.template add<BaseTranslator>(value, m_allocator.get());
     490template<typename T, typename U>
     491auto ListHashSet<T, U>::add(const ValueType& value) -> AddResult
     492{
     493    auto result = m_impl.template add<BaseTranslator>(value, nullptr);
    588494    if (result.isNewEntry)
    589495        appendNode(*result.iterator);
    … …  
    591497}
    592498
    593 template<typename T, size_t inlineCapacity, typename U>
    594 auto ListHashSet<T, inlineCapacity, U>::add(ValueType&& value) -> AddResult
    595 {
    596     auto result = m_impl.template add<BaseTranslator>(WTF::move(value), m_allocator.get());
     499template<typename T, typename U>
     500auto ListHashSet<T, U>::add(ValueType&& value) -> AddResult
     501{
     502    auto result = m_impl.template add<BaseTranslator>(WTF::move(value), nullptr);
    597503    if (result.isNewEntry)
    598504        appendNode(*result.iterator);
    … …  
    600506}
    601507
    602 template<typename T, size_t inlineCapacity, typename U>
    603 auto ListHashSet<T, inlineCapacity, U>::appendOrMoveToLast(const ValueType& value) -> AddResult
    604 {
    605     auto result = m_impl.template add<BaseTranslator>(value, m_allocator.get());
     508template<typename T, typename U>
     509auto ListHashSet<T, U>::appendOrMoveToLast(const ValueType& value) -> AddResult
     510{
     511    auto result = m_impl.template add<BaseTranslator>(value, nullptr);
    606512    Node* node = *result.iterator;
    607513    if (!result.isNewEntry)
    … …  
    612518}
    613519
    614 template<typename T, size_t inlineCapacity, typename U>
    615 auto ListHashSet<T, inlineCapacity, U>::appendOrMoveToLast(ValueType&& value) -> AddResult
    616 {
    617     auto result = m_impl.template add<BaseTranslator>(WTF::move(value), m_allocator.get());
     520template<typename T, typename U>
     521auto ListHashSet<T, U>::appendOrMoveToLast(ValueType&& value) -> AddResult
     522{
     523    auto result = m_impl.template add<BaseTranslator>(WTF::move(value), nullptr);
    618524    Node* node = *result.iterator;
    619525    if (!result.isNewEntry)
    … …  
    624530}
    625531
    626 template<typename T, size_t inlineCapacity, typename U>
    627 auto ListHashSet<T, inlineCapacity, U>::prependOrMoveToFirst(const ValueType& value) -> AddResult
    628 {
    629     auto result = m_impl.template add<BaseTranslator>(value, m_allocator.get());
     532template<typename T, typename U>
     533auto ListHashSet<T, U>::prependOrMoveToFirst(const ValueType& value) -> AddResult
     534{
     535    auto result = m_impl.template add<BaseTranslator>(value, nullptr);
    630536    Node* node = *result.iterator;
    631537    if (!result.isNewEntry)
    … …  
    636542}
    637543
    638 template<typename T, size_t inlineCapacity, typename U>
    639 auto ListHashSet<T, inlineCapacity, U>::prependOrMoveToFirst(ValueType&& value) -> AddResult
    640 {
    641     auto result = m_impl.template add<BaseTranslator>(WTF::move(value), m_allocator.get());
     544template<typename T, typename U>
     545auto ListHashSet<T, U>::prependOrMoveToFirst(ValueType&& value) -> AddResult
     546{
     547    auto result = m_impl.template add<BaseTranslator>(WTF::move(value), nullptr);
    642548    Node* node = *result.iterator;
    643549    if (!result.isNewEntry)
    … …  
    648554}
    649555
    650 template<typename T, size_t inlineCapacity, typename U>
    651 auto ListHashSet<T, inlineCapacity, U>::insertBefore(const ValueType& beforeValue, const ValueType& newValue) -> AddResult
     556template<typename T, typename U>
     557auto ListHashSet<T, U>::insertBefore(const ValueType& beforeValue, const ValueType& newValue) -> AddResult
    652558{
    653559    return insertBefore(find(beforeValue), newValue);
    654560}
    655561
    656 template<typename T, size_t inlineCapacity, typename U>
    657 auto ListHashSet<T, inlineCapacity, U>::insertBefore(const ValueType& beforeValue, ValueType&& newValue) -> AddResult
     562template<typename T, typename U>
     563auto ListHashSet<T, U>::insertBefore(const ValueType& beforeValue, ValueType&& newValue) -> AddResult
    658564{
    659565    return insertBefore(find(beforeValue), WTF::move(newValue));
    660566}
    661567
    662 template<typename T, size_t inlineCapacity, typename U>
    663 auto ListHashSet<T, inlineCapacity, U>::insertBefore(iterator it, const ValueType& newValue) -> AddResult
    664 {
    665     auto result = m_impl.template add<BaseTranslator>(newValue, m_allocator.get());
     568template<typename T, typename U>
     569auto ListHashSet<T, U>::insertBefore(iterator it, const ValueType& newValue) -> AddResult
     570{
     571    auto result = m_impl.template add<BaseTranslator>(newValue, nullptr);
    666572    if (result.isNewEntry)
    667573        insertNodeBefore(it.node(), *result.iterator);
    … …  
    669575}
    670576
    671 template<typename T, size_t inlineCapacity, typename U>
    672 auto ListHashSet<T, inlineCapacity, U>::insertBefore(iterator it, ValueType&& newValue) -> AddResult
    673 {
    674     auto result = m_impl.template add<BaseTranslator>(WTF::move(newValue), m_allocator.get());
     577template<typename T, typename U>
     578auto ListHashSet<T, U>::insertBefore(iterator it, ValueType&& newValue) -> AddResult
     579{
     580    auto result = m_impl.template add<BaseTranslator>(WTF::move(newValue), nullptr);
    675581    if (result.isNewEntry)
    676582        insertNodeBefore(it.node(), *result.iterator);
    … …  
    678584}
    679585
    680 template<typename T, size_t inlineCapacity, typename U>
    681 inline bool ListHashSet<T, inlineCapacity, U>::remove(iterator it)
     586template<typename T, typename U>
     587inline bool ListHashSet<T, U>::remove(iterator it)
    682588{
    683589    if (it == end())
    … …  
    688594}
    689595
    690 template<typename T, size_t inlineCapacity, typename U>
    691 inline bool ListHashSet<T, inlineCapacity, U>::remove(const ValueType& value)
     596template<typename T, typename U>
     597inline bool ListHashSet<T, U>::remove(const ValueType& value)
    692598{
    693599    return remove(find(value));
    694600}
    695601
    696 template<typename T, size_t inlineCapacity, typename U>
    697 inline void ListHashSet<T, inlineCapacity, U>::clear()
     602template<typename T, typename U>
     603inline void ListHashSet<T, U>::clear()
    698604{
    699605    deleteAllNodes();
    … …  
    703609}
    704610
    705 template<typename T, size_t inlineCapacity, typename U>
    706 void ListHashSet<T, inlineCapacity, U>::unlink(Node* node)
     611template<typename T, typename U>
     612void ListHashSet<T, U>::unlink(Node* node)
    707613{
    708614    if (!node->m_prev) {
    … …  
    723629}
    724630
    725 template<typename T, size_t inlineCapacity, typename U>
    726 void ListHashSet<T, inlineCapacity, U>::unlinkAndDelete(Node* node)
     631template<typename T, typename U>
     632void ListHashSet<T, U>::unlinkAndDelete(Node* node)
    727633{
    728634    unlink(node);
    729     node->destroy(m_allocator.get());
    730 }
    731 
    732 template<typename T, size_t inlineCapacity, typename U>
    733 void ListHashSet<T, inlineCapacity, U>::appendNode(Node* node)
     635    delete node;
     636}
     637
     638template<typename T, typename U>
     639void ListHashSet<T, U>::appendNode(Node* node)
    734640{
    735641    node->m_prev = m_tail;
    … …  
    747653}
    748654
    749 template<typename T, size_t inlineCapacity, typename U>
    750 void ListHashSet<T, inlineCapacity, U>::prependNode(Node* node)
     655template<typename T, typename U>
     656void ListHashSet<T, U>::prependNode(Node* node)
    751657{
    752658    node->m_prev = 0;
    … …  
    761667}
    762668
    763 template<typename T, size_t inlineCapacity, typename U>
    764 void ListHashSet<T, inlineCapacity, U>::insertNodeBefore(Node* beforeNode, Node* newNode)
     669template<typename T, typename U>
     670void ListHashSet<T, U>::insertNodeBefore(Node* beforeNode, Node* newNode)
    765671{
    766672    if (!beforeNode)
    … …  
    777683}
    778684
    779 template<typename T, size_t inlineCapacity, typename U>
    780 void ListHashSet<T, inlineCapacity, U>::deleteAllNodes()
     685template<typename T, typename U>
     686void ListHashSet<T, U>::deleteAllNodes()
    781687{
    782688    if (!m_head)
    … …  
    784690
    785691    for (Node* node = m_head, *next = m_head->m_next; node; node = next, next = node ? node->m_next : 0)
    786         node->destroy(m_allocator.get());
    787 }
    788 
    789 template<typename T, size_t inlineCapacity, typename U>
    790 inline auto ListHashSet<T, inlineCapacity, U>::makeIterator(Node* position) -> iterator
     692        delete node;
     693}
     694
     695template<typename T, typename U>
     696inline auto ListHashSet<T, U>::makeIterator(Node* position) -> iterator
    791697{
    792698    return iterator(this, position);
    793699}
    794700
    795 template<typename T, size_t inlineCapacity, typename U>
    796 inline auto ListHashSet<T, inlineCapacity, U>::makeConstIterator(Node* position) const -> const_iterator
     701template<typename T, typename U>
     702inline auto ListHashSet<T, U>::makeConstIterator(Node* position) const -> const_iterator
    797703{
    798704    return const_iterator(this, position);

  • trunk/Source/WebCore/ChangeLog

    r176287 r176290  
     12014-11-18  Geoffrey Garen  <ggaren@apple.com>
     2
     3        Removed the custom allocator for ListHashSet nodes
     4        https://bugs.webkit.org/show_bug.cgi?id=138841
     5
     6        Reviewed by Andreas Kling.
     7
     8        Uses of ListHashSet no longer need to declare an inline capacity,
     9        since that was only used to specify the capacity of the custom allocator.
     10
     11        * dom/DOMNamedFlowCollection.h:
     12        * dom/DocumentEventQueue.h:
     13        * dom/DocumentStyleSheetCollection.h:
     14        * dom/NamedFlowCollection.h:
     15        * html/FormController.h:
     16        * rendering/FloatingObjects.h:
     17        * rendering/RenderBlock.h:
     18
    1192014-11-18  David Hyatt  <hyatt@apple.com>
    220

  • trunk/Source/WebCore/dom/DOMNamedFlowCollection.h

    r128325 r176290  
    5858    struct DOMNamedFlowHashTranslator;
    5959
    60     typedef ListHashSet<RefPtr<WebKitNamedFlow>, 1, DOMNamedFlowHashFunctions> DOMNamedFlowSet;
     60    typedef ListHashSet<RefPtr<WebKitNamedFlow>, DOMNamedFlowHashFunctions> DOMNamedFlowSet;
    6161    explicit DOMNamedFlowCollection(const Vector<WebKitNamedFlow*>&);
    6262    DOMNamedFlowSet m_namedFlows;

  • trunk/Source/WebCore/dom/DocumentEventQueue.h

    r165676 r176290  
    5959    Document& m_document;
    6060    std::unique_ptr<Timer> m_pendingEventTimer;
    61     ListHashSet<RefPtr<Event>, 16> m_queuedEvents;
     61    ListHashSet<RefPtr<Event>> m_queuedEvents;
    6262    HashSet<Node*> m_nodesWithQueuedScrollEvents;
    6363    bool m_isClosed;

  • trunk/Source/WebCore/dom/DocumentStyleSheetCollection.h

    r172814 r176290  
    153153    UpdateFlag m_pendingUpdateType;
    154154
    155     typedef ListHashSet<Node*, 32> StyleSheetCandidateListHashSet;
     155    typedef ListHashSet<Node*> StyleSheetCandidateListHashSet;
    156156    StyleSheetCandidateListHashSet m_styleSheetCandidateNodes;
    157157

  • trunk/Source/WebCore/dom/NamedFlowCollection.h

    r175148 r176290  
    6464    struct NamedFlowHashTranslator;
    6565
    66     typedef ListHashSet<WebKitNamedFlow*, 1, NamedFlowHashFunctions> NamedFlowSet;
     66    typedef ListHashSet<WebKitNamedFlow*, NamedFlowHashFunctions> NamedFlowSet;
    6767
    6868    explicit NamedFlowCollection(Document*);

  • trunk/Source/WebCore/html/FormController.h

    r172862 r176290  
    9696
    9797private:
    98     typedef ListHashSet<RefPtr<HTMLFormControlElementWithState>, 64> FormElementListHashSet;
     98    typedef ListHashSet<RefPtr<HTMLFormControlElementWithState>> FormElementListHashSet;
    9999    typedef HashMap<RefPtr<AtomicStringImpl>, std::unique_ptr<SavedFormState>> SavedFormStateMap;
    100100

  • trunk/Source/WebCore/rendering/FloatingObjects.h

    r163631 r176290  
    112112};
    113113
    114 typedef ListHashSet<std::unique_ptr<FloatingObject>, 4, FloatingObjectHashFunctions> FloatingObjectSet;
     114typedef ListHashSet<std::unique_ptr<FloatingObject>, FloatingObjectHashFunctions> FloatingObjectSet;
    115115
    116116typedef PODInterval<LayoutUnit, FloatingObject*> FloatingObjectInterval;

  • trunk/Source/WebCore/rendering/RenderBlock.h

    r175640 r176290  
    4141struct PaintInfo;
    4242
    43 typedef WTF::ListHashSet<RenderBox*, 16> TrackedRendererListHashSet;
     43typedef WTF::ListHashSet<RenderBox*> TrackedRendererListHashSet;
    4444typedef WTF::HashMap<const RenderBlock*, std::unique_ptr<TrackedRendererListHashSet>> TrackedDescendantsMap;
    4545typedef WTF::HashMap<const RenderBox*, std::unique_ptr<HashSet<RenderBlock*>>> TrackedContainerMap;

  • trunk/Source/WebKit/WebKit.vcxproj/WebKitExportGenerator/WebKitExports.def.in

    r176001 r176290  
    260260        symbolWithPointer(?paintControlTints@FrameView@WebCore@@AAEXXZ, ?paintControlTints@FrameView@WebCore@@AEAAXXZ)
    261261        symbolWithPointer(?rangeFromLocationAndLength@TextIterator@WebCore@@SA?AV?$PassRefPtr@VRange@WebCore@@@WTF@@PAVContainerNode@2@HH_N@Z, ?rangeFromLocationAndLength@TextIterator@WebCore@@SA?AV?$PassRefPtr@VRange@WebCore@@@WTF@@PEAVContainerNode@2@HH_N@Z)
    262         symbolWithPointer(?rectBasedTestResult@HitTestResult@WebCore@@QBEABV?$ListHashSet@V?$RefPtr@VNode@WebCore@@@WTF@@$0BAA@U?$PtrHash@V?$RefPtr@VNode@WebCore@@@WTF@@@2@@WTF@@XZ, ?rectBasedTestResult@HitTestResult@WebCore@@QEBAAEBV?$ListHashSet@V?$RefPtr@VNode@WebCore@@@WTF@@$0BAA@U?$PtrHash@V?$RefPtr@VNode@WebCore@@@WTF@@@2@@WTF@@XZ)
     262        symbolWithPointer(?rectBasedTestResult@HitTestResult@WebCore@@QBEABV?$ListHashSet@V?$RefPtr@VNode@WebCore@@@WTF@@U?$PtrHash@V?$RefPtr@VNode@WebCore@@@WTF@@@2@@WTF@@XZ, )
    263263        symbolWithPointer(?rectForPoint@HitTestLocation@WebCore@@SA?AVIntRect@2@ABVLayoutPoint@2@IIII@Z, ?rectForPoint@HitTestLocation@WebCore@@SA?AVIntRect@2@AEBVLayoutPoint@2@IIII@Z)
    264264        symbolWithPointer(?reload@FrameLoader@WebCore@@QAEX_N@Z, ?reload@FrameLoader@WebCore@@QEAAX_N@Z)

  • trunk/Source/WebKit2/ChangeLog

    r176289 r176290  
     12014-11-18  Geoffrey Garen  <ggaren@apple.com>
     2
     3        Removed the custom allocator for ListHashSet nodes
     4        https://bugs.webkit.org/show_bug.cgi?id=138841
     5
     6        Reviewed by Andreas Kling.
     7
     8        Uses of ListHashSet no longer need to declare an inline capacity,
     9        since that was only used to specify the capacity of the custom allocator.
     10
     11        * UIProcess/Plugins/PluginInfoStore.cpp:
     12        (WebKit::PluginInfoStore::loadPluginsIfNecessary):
     13
    1142014-11-18  Eric Carlson  <eric.carlson@apple.com>
    215

  • trunk/Source/WebKit2/UIProcess/Plugins/PluginInfoStore.cpp

    r173364 r176290  
    6969        return;
    7070
    71     ListHashSet<String, 32> uniquePluginPaths;
     71    ListHashSet<String> uniquePluginPaths;
    7272
    7373    // First, load plug-ins from the additional plug-ins directories specified.
Note: See TracChangeset for help on using the changeset viewer.