Home | History | Annotate | Download | only in wtf
      1 /*
      2  * Copyright (C) 2005, 2006, 2007, 2008, 2011, 2012 Apple Inc. All rights reserved.
      3  * Copyright (C) 2011, Benjamin Poulain <ikipou (at) gmail.com>
      4  *
      5  * This library is free software; you can redistribute it and/or
      6  * modify it under the terms of the GNU Library General Public
      7  * License as published by the Free Software Foundation; either
      8  * version 2 of the License, or (at your option) any later version.
      9  *
     10  * This library is distributed in the hope that it will be useful,
     11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
     12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
     13  * Library General Public License for more details.
     14  *
     15  * You should have received a copy of the GNU Library General Public License
     16  * along with this library; see the file COPYING.LIB.  If not, write to
     17  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
     18  * Boston, MA 02110-1301, USA.
     19  *
     20  */
     21 
     22 #ifndef WTF_ListHashSet_h
     23 #define WTF_ListHashSet_h
     24 
     25 #include "wtf/DefaultAllocator.h"
     26 #include "wtf/HashSet.h"
     27 #include "wtf/OwnPtr.h"
     28 #include "wtf/PassOwnPtr.h"
     29 
     30 namespace WTF {
     31 
     32     // ListHashSet: Just like HashSet, this class provides a Set
     33     // interface - a collection of unique objects with O(1) insertion,
     34     // removal and test for containership. However, it also has an
     35     // order - iterating it will always give back values in the order
     36     // in which they are added.
     37 
     38     // Unlike iteration of most WTF Hash data structures, iteration is
     39     // guaranteed safe against mutation of the ListHashSet, except for
     40     // removal of the item currently pointed to by a given iterator.
     41 
     42     template<typename Value, size_t inlineCapacity, typename HashFunctions, typename Allocator> class ListHashSet;
     43 
     44     template<typename Set> class ListHashSetIterator;
     45     template<typename Set> class ListHashSetConstIterator;
     46     template<typename Set> class ListHashSetReverseIterator;
     47     template<typename Set> class ListHashSetConstReverseIterator;
     48 
     49     template<typename ValueArg> class ListHashSetNodeBase;
     50     template<typename ValueArg, typename Allocator> class ListHashSetNode;
     51     template<typename ValueArg, size_t inlineCapacity> struct ListHashSetAllocator;
     52 
     53     template<typename HashArg> struct ListHashSetNodeHashFunctions;
     54     template<typename HashArg> struct ListHashSetTranslator;
     55 
     56     // Don't declare a destructor for HeapAllocated ListHashSet.
     57     template<typename Derived, typename Allocator, bool isGarbageCollected>
     58     class ListHashSetDestructorBase;
     59 
     60     template<typename Derived, typename Allocator>
     61     class ListHashSetDestructorBase<Derived, Allocator, true> {
     62     protected:
     63         typename Allocator::AllocatorProvider m_allocatorProvider;
     64     };
     65 
     66     template<typename Derived, typename Allocator>
     67     class ListHashSetDestructorBase<Derived, Allocator, false> {
     68     public:
     69         ~ListHashSetDestructorBase() { static_cast<Derived*>(this)->finalize(); }
     70     protected:
     71         typename Allocator::AllocatorProvider m_allocatorProvider;
     72     };
     73 
     74     // Note that for a ListHashSet you cannot specify the HashTraits as a
     75     // template argument. It uses the default hash traits for the ValueArg
     76     // type.
     77     template<typename ValueArg, size_t inlineCapacity = 256, typename HashArg = typename DefaultHash<ValueArg>::Hash, typename AllocatorArg = ListHashSetAllocator<ValueArg, inlineCapacity> > class ListHashSet
     78         : public ListHashSetDestructorBase<ListHashSet<ValueArg, inlineCapacity, HashArg, AllocatorArg>, AllocatorArg, AllocatorArg::isGarbageCollected> {
     79         typedef AllocatorArg Allocator;
     80         WTF_USE_ALLOCATOR(ListHashSet, Allocator);
     81 
     82         typedef ListHashSetNode<ValueArg, Allocator> Node;
     83         typedef HashTraits<Node*> NodeTraits;
     84         typedef ListHashSetNodeHashFunctions<HashArg> NodeHash;
     85         typedef ListHashSetTranslator<HashArg> BaseTranslator;
     86 
     87         typedef HashTable<Node*, Node*, IdentityExtractor, NodeHash, NodeTraits, NodeTraits, typename Allocator::TableAllocator> ImplType;
     88         typedef HashTableIterator<Node*, Node*, IdentityExtractor, NodeHash, NodeTraits, NodeTraits, typename Allocator::TableAllocator> ImplTypeIterator;
     89         typedef HashTableConstIterator<Node*, Node*, IdentityExtractor, NodeHash, NodeTraits, NodeTraits, typename Allocator::TableAllocator> ImplTypeConstIterator;
     90 
     91         typedef HashArg HashFunctions;
     92 
     93     public:
     94         typedef ValueArg ValueType;
     95         typedef HashTraits<ValueType> ValueTraits;
     96         typedef typename ValueTraits::PeekInType ValuePeekInType;
     97         typedef typename ValueTraits::PassInType ValuePassInType;
     98         typedef typename ValueTraits::PassOutType ValuePassOutType;
     99 
    100         typedef ListHashSetIterator<ListHashSet> iterator;
    101         typedef ListHashSetConstIterator<ListHashSet> const_iterator;
    102         friend class ListHashSetIterator<ListHashSet>;
    103         friend class ListHashSetConstIterator<ListHashSet>;
    104 
    105         typedef ListHashSetReverseIterator<ListHashSet> reverse_iterator;
    106         typedef ListHashSetConstReverseIterator<ListHashSet> const_reverse_iterator;
    107         friend class ListHashSetReverseIterator<ListHashSet>;
    108         friend class ListHashSetConstReverseIterator<ListHashSet>;
    109 
    110         template<typename ValueType> struct HashTableAddResult {
    111         HashTableAddResult(Node* storedValue, bool isNewEntry) : storedValue(storedValue), isNewEntry(isNewEntry) { }
    112             Node* storedValue;
    113             bool isNewEntry;
    114         };
    115         typedef HashTableAddResult<ValueType> AddResult;
    116 
    117         ListHashSet();
    118         ListHashSet(const ListHashSet&);
    119         ListHashSet& operator=(const ListHashSet&);
    120         void finalize();
    121 
    122         void swap(ListHashSet&);
    123 
    124         unsigned size() const { return m_impl.size(); }
    125         unsigned capacity() const { return m_impl.capacity(); }
    126         bool isEmpty() const { return m_impl.isEmpty(); }
    127 
    128         iterator begin() { return makeIterator(m_head); }
    129         iterator end() { return makeIterator(0); }
    130         const_iterator begin() const { return makeConstIterator(m_head); }
    131         const_iterator end() const { return makeConstIterator(0); }
    132 
    133         reverse_iterator rbegin() { return makeReverseIterator(m_tail); }
    134         reverse_iterator rend() { return makeReverseIterator(0); }
    135         const_reverse_iterator rbegin() const { return makeConstReverseIterator(m_tail); }
    136         const_reverse_iterator rend() const { return makeConstReverseIterator(0); }
    137 
    138         ValueType& first();
    139         const ValueType& first() const;
    140         void removeFirst();
    141 
    142         ValueType& last();
    143         const ValueType& last() const;
    144         void removeLast();
    145 
    146         iterator find(ValuePeekInType);
    147         const_iterator find(ValuePeekInType) const;
    148         bool contains(ValuePeekInType) const;
    149 
    150         // An alternate version of find() that finds the object by hashing and comparing
    151         // with some other type, to avoid the cost of type conversion.
    152         // The HashTranslator interface is defined in HashSet.
    153         template<typename HashTranslator, typename T> iterator find(const T&);
    154         template<typename HashTranslator, typename T> const_iterator find(const T&) const;
    155         template<typename HashTranslator, typename T> bool contains(const T&) const;
    156 
    157         // The return value of add is a pair of a pointer to the stored value,
    158         // and a bool that is true if an new entry was added.
    159         AddResult add(ValuePassInType);
    160 
    161         // Same as add() except that the return value is an
    162         // iterator. Useful in cases where it's needed to have the
    163         // same return value as find() and where it's not possible to
    164         // use a pointer to the storedValue.
    165         iterator addReturnIterator(ValuePassInType);
    166 
    167         // Add the value to the end of the collection. If the value was already in
    168         // the list, it is moved to the end.
    169         AddResult appendOrMoveToLast(ValuePassInType);
    170 
    171         // Add the value to the beginning of the collection. If the value was already in
    172         // the list, it is moved to the beginning.
    173         AddResult prependOrMoveToFirst(ValuePassInType);
    174 
    175         AddResult insertBefore(ValuePeekInType beforeValue, ValuePassInType newValue);
    176         AddResult insertBefore(iterator, ValuePassInType);
    177 
    178         void remove(ValuePeekInType value) { return remove(find(value)); }
    179         void remove(iterator);
    180         void clear();
    181         template<typename Collection>
    182         void removeAll(const Collection& other) { WTF::removeAll(*this, other); }
    183 
    184         ValuePassOutType take(iterator);
    185         ValuePassOutType take(ValuePeekInType);
    186         ValuePassOutType takeFirst();
    187 
    188         void trace(typename Allocator::Visitor*);
    189 
    190     private:
    191         void unlink(Node*);
    192         void unlinkAndDelete(Node*);
    193         void appendNode(Node*);
    194         void prependNode(Node*);
    195         void insertNodeBefore(Node* beforeNode, Node* newNode);
    196         void deleteAllNodes();
    197         Allocator* allocator() const { return this->m_allocatorProvider.get(); }
    198         void createAllocatorIfNeeded() { this->m_allocatorProvider.createAllocatorIfNeeded(); }
    199         void deallocate(Node* node) const { this->m_allocatorProvider.deallocate(node); }
    200 
    201         iterator makeIterator(Node* position) { return iterator(this, position); }
    202         const_iterator makeConstIterator(Node* position) const { return const_iterator(this, position); }
    203         reverse_iterator makeReverseIterator(Node* position) { return reverse_iterator(this, position); }
    204         const_reverse_iterator makeConstReverseIterator(Node* position) const { return const_reverse_iterator(this, position); }
    205 
    206         ImplType m_impl;
    207         Node* m_head;
    208         Node* m_tail;
    209     };
    210 
    211     // ListHashSetNode has this base class to hold the members because the MSVC
    212     // compiler otherwise gets into circular template dependencies when trying
    213     // to do sizeof on a node.
    214     template<typename ValueArg> class ListHashSetNodeBase {
    215     protected:
    216         ListHashSetNodeBase(const ValueArg& value)
    217             : m_value(value)
    218             , m_prev(0)
    219             , m_next(0)
    220 #ifndef NDEBUG
    221             , m_isAllocated(true)
    222 #endif
    223         {
    224         }
    225 
    226         template <typename U>
    227         ListHashSetNodeBase(const U& value)
    228             : m_value(value)
    229             , m_prev(0)
    230             , m_next(0)
    231 #ifndef NDEBUG
    232             , m_isAllocated(true)
    233 #endif
    234         {
    235         }
    236 
    237     public:
    238         ValueArg m_value;
    239         ListHashSetNodeBase* m_prev;
    240         ListHashSetNodeBase* m_next;
    241 #ifndef NDEBUG
    242         bool m_isAllocated;
    243 #endif
    244     };
    245 
    246     // This allocator is only used for non-Heap ListHashSets.
    247     template<typename ValueArg, size_t inlineCapacity>
    248     struct ListHashSetAllocator : public DefaultAllocator {
    249         typedef DefaultAllocator TableAllocator;
    250         typedef ListHashSetNode<ValueArg, ListHashSetAllocator> Node;
    251         typedef ListHashSetNodeBase<ValueArg> NodeBase;
    252         class AllocatorProvider {
    253         public:
    254             void createAllocatorIfNeeded()
    255             {
    256                 if (!m_allocator)
    257                     m_allocator = adoptPtr(new ListHashSetAllocator);
    258             }
    259 
    260             void swap(AllocatorProvider& other)
    261             {
    262                 m_allocator.swap(other.m_allocator);
    263             }
    264 
    265             void deallocate(Node* node) const
    266             {
    267                 ASSERT(m_allocator);
    268                 m_allocator->deallocate(node);
    269             }
    270 
    271             ListHashSetAllocator* get() const
    272             {
    273                 ASSERT(m_allocator);
    274                 return m_allocator.get();
    275             }
    276 
    277         private:
    278             OwnPtr<ListHashSetAllocator> m_allocator;
    279         };
    280 
    281         ListHashSetAllocator()
    282             : m_freeList(pool())
    283             , m_isDoneWithInitialFreeList(false)
    284         {
    285             memset(m_pool.buffer, 0, sizeof(m_pool.buffer));
    286         }
    287 
    288         Node* allocateNode()
    289         {
    290             Node* result = m_freeList;
    291 
    292             if (!result)
    293                 return static_cast<Node*>(fastMalloc(sizeof(NodeBase)));
    294 
    295             ASSERT(!result->m_isAllocated);
    296 
    297             Node* next = result->next();
    298             ASSERT(!next || !next->m_isAllocated);
    299             if (!next && !m_isDoneWithInitialFreeList) {
    300                 next = result + 1;
    301                 if (next == pastPool()) {
    302                     m_isDoneWithInitialFreeList = true;
    303                     next = 0;
    304                 } else {
    305                     ASSERT(inPool(next));
    306                     ASSERT(!next->m_isAllocated);
    307                 }
    308             }
    309             m_freeList = next;
    310 
    311             return result;
    312         }
    313 
    314         void deallocate(Node* node)
    315         {
    316             if (inPool(node)) {
    317 #ifndef NDEBUG
    318                 node->m_isAllocated = false;
    319 #endif
    320                 node->m_next = m_freeList;
    321                 m_freeList = node;
    322                 return;
    323             }
    324 
    325             fastFree(node);
    326         }
    327 
    328         bool inPool(Node* node)
    329         {
    330             return node >= pool() && node < pastPool();
    331         }
    332 
    333         static void traceValue(typename DefaultAllocator::Visitor* visitor, Node* node) { }
    334 
    335     private:
    336         Node* pool() { return reinterpret_cast_ptr<Node*>(m_pool.buffer); }
    337         Node* pastPool() { return pool() + m_poolSize; }
    338 
    339         Node* m_freeList;
    340         bool m_isDoneWithInitialFreeList;
    341 #if defined(MEMORY_TOOL_REPLACES_ALLOCATOR)
    342         // The allocation pool for nodes is one big chunk that ASAN has no
    343         // insight into, so it can cloak errors. Make it as small as possible
    344         // to force nodes to be allocated individually where ASAN can see them.
    345         static const size_t m_poolSize = 1;
    346 #else
    347         static const size_t m_poolSize = inlineCapacity;
    348 #endif
    349         AlignedBuffer<sizeof(NodeBase) * m_poolSize, WTF_ALIGN_OF(NodeBase)> m_pool;
    350     };
    351 
    352     template<typename ValueArg, typename AllocatorArg> class ListHashSetNode : public ListHashSetNodeBase<ValueArg> {
    353     public:
    354         typedef AllocatorArg NodeAllocator;
    355         typedef ValueArg Value;
    356 
    357         template <typename U>
    358         ListHashSetNode(U value)
    359             : ListHashSetNodeBase<ValueArg>(value) { }
    360 
    361         void* operator new(size_t, NodeAllocator* allocator)
    362         {
    363             COMPILE_ASSERT(sizeof(ListHashSetNode) == sizeof(ListHashSetNodeBase<ValueArg>), PleaseAddAnyFieldsToTheBase);
    364             return allocator->allocateNode();
    365         }
    366 
    367         void setWasAlreadyDestructed()
    368         {
    369             if (NodeAllocator::isGarbageCollected && HashTraits<ValueArg>::needsDestruction)
    370                 this->m_prev = unlinkedNodePointer();
    371         }
    372 
    373         bool wasAlreadyDestructed() const
    374         {
    375             ASSERT(NodeAllocator::isGarbageCollected);
    376             return this->m_prev == unlinkedNodePointer();
    377         }
    378 
    379         static void finalize(void* pointer)
    380         {
    381             ASSERT(HashTraits<ValueArg>::needsDestruction); // No need to waste time calling finalize if it's not needed.
    382             ListHashSetNode* self = reinterpret_cast_ptr<ListHashSetNode*>(pointer);
    383 
    384             // Check whether this node was already destructed before being
    385             // unlinked from the collection.
    386             if (self->wasAlreadyDestructed())
    387                 return;
    388 
    389             self->m_value.~ValueArg();
    390         }
    391 
    392         void destroy(NodeAllocator* allocator)
    393         {
    394             this->~ListHashSetNode();
    395             setWasAlreadyDestructed();
    396             allocator->deallocate(this);
    397         }
    398 
    399         // This is not called in normal tracing, but it is called if we find a
    400         // pointer to a node on the stack using conservative scanning. Since
    401         // the original ListHashSet may no longer exist we make sure to mark
    402         // the neighbours in the chain too.
    403         void trace(typename NodeAllocator::Visitor* visitor)
    404         {
    405             // The conservative stack scan can find nodes that have been
    406             // removed from the set and destructed. We don't need to trace
    407             // these, and it would be wrong to do so, because the class will
    408             // not expect the trace method to be called after the destructor.
    409             // It's an error to remove a node from the ListHashSet while an
    410             // iterator is positioned at that node, so there should be no valid
    411             // pointers from the stack to a destructed node.
    412             if (wasAlreadyDestructed())
    413                 return;
    414             NodeAllocator::traceValue(visitor, this);
    415             visitor->mark(next());
    416             visitor->mark(prev());
    417         }
    418 
    419         ListHashSetNode* next() const { return reinterpret_cast<ListHashSetNode*>(this->m_next); }
    420         ListHashSetNode* prev() const { return reinterpret_cast<ListHashSetNode*>(this->m_prev); }
    421 
    422         // Don't add fields here, the ListHashSetNodeBase and this should have
    423         // the same size.
    424 
    425         static ListHashSetNode* unlinkedNodePointer() { return reinterpret_cast<ListHashSetNode*>(-1); }
    426 
    427         template<typename HashArg>
    428         friend struct ListHashSetNodeHashFunctions;
    429     };
    430 
    431     template<typename HashArg> struct ListHashSetNodeHashFunctions {
    432         template<typename T> static unsigned hash(const T& key) { return HashArg::hash(key->m_value); }
    433         template<typename T> static bool equal(const T& a, const T& b) { return HashArg::equal(a->m_value, b->m_value); }
    434         static const bool safeToCompareToEmptyOrDeleted = false;
    435     };
    436 
    437     template<typename Set> class ListHashSetIterator {
    438     private:
    439         typedef typename Set::const_iterator const_iterator;
    440         typedef typename Set::Node Node;
    441         typedef typename Set::ValueType ValueType;
    442         typedef ValueType& ReferenceType;
    443         typedef ValueType* PointerType;
    444 
    445         ListHashSetIterator(const Set* set, Node* position) : m_iterator(set, position) { }
    446 
    447     public:
    448         ListHashSetIterator() { }
    449 
    450         // default copy, assignment and destructor are OK
    451 
    452         PointerType get() const { return const_cast<PointerType>(m_iterator.get()); }
    453         ReferenceType operator*() const { return *get(); }
    454         PointerType operator->() const { return get(); }
    455 
    456         ListHashSetIterator& operator++() { ++m_iterator; return *this; }
    457         ListHashSetIterator& operator--() { --m_iterator; return *this; }
    458 
    459         // Postfix ++ and -- intentionally omitted.
    460 
    461         // Comparison.
    462         bool operator==(const ListHashSetIterator& other) const { return m_iterator == other.m_iterator; }
    463         bool operator!=(const ListHashSetIterator& other) const { return m_iterator != other.m_iterator; }
    464 
    465         operator const_iterator() const { return m_iterator; }
    466 
    467     private:
    468         Node* node() { return m_iterator.node(); }
    469 
    470         const_iterator m_iterator;
    471 
    472         template<typename T, size_t inlineCapacity, typename U, typename V>
    473         friend class ListHashSet;
    474     };
    475 
    476     template<typename Set>
    477     class ListHashSetConstIterator {
    478     private:
    479         typedef typename Set::const_iterator const_iterator;
    480         typedef typename Set::Node Node;
    481         typedef typename Set::ValueType ValueType;
    482         typedef const ValueType& ReferenceType;
    483         typedef const ValueType* PointerType;
    484 
    485         friend class ListHashSetIterator<Set>;
    486 
    487         ListHashSetConstIterator(const Set* set, Node* position)
    488             : m_set(set)
    489             , m_position(position)
    490         {
    491         }
    492 
    493     public:
    494         ListHashSetConstIterator()
    495         {
    496         }
    497 
    498         PointerType get() const
    499         {
    500             return &m_position->m_value;
    501         }
    502         ReferenceType operator*() const { return *get(); }
    503         PointerType operator->() const { return get(); }
    504 
    505         ListHashSetConstIterator& operator++()
    506         {
    507             ASSERT(m_position != 0);
    508             m_position = m_position->next();
    509             return *this;
    510         }
    511 
    512         ListHashSetConstIterator& operator--()
    513         {
    514             ASSERT(m_position != m_set->m_head);
    515             if (!m_position)
    516                 m_position = m_set->m_tail;
    517             else
    518                 m_position = m_position->prev();
    519             return *this;
    520         }
    521 
    522         // Postfix ++ and -- intentionally omitted.
    523 
    524         // Comparison.
    525         bool operator==(const ListHashSetConstIterator& other) const
    526         {
    527             return m_position == other.m_position;
    528         }
    529         bool operator!=(const ListHashSetConstIterator& other) const
    530         {
    531             return m_position != other.m_position;
    532         }
    533 
    534     private:
    535         Node* node() { return m_position; }
    536 
    537         const Set* m_set;
    538         Node* m_position;
    539 
    540         template<typename T, size_t inlineCapacity, typename U, typename V>
    541         friend class ListHashSet;
    542     };
    543 
    544     template<typename Set>
    545     class ListHashSetReverseIterator {
    546     private:
    547         typedef typename Set::const_reverse_iterator const_reverse_iterator;
    548         typedef typename Set::Node Node;
    549         typedef typename Set::ValueType ValueType;
    550         typedef ValueType& ReferenceType;
    551         typedef ValueType* PointerType;
    552 
    553         ListHashSetReverseIterator(const Set* set, Node* position) : m_iterator(set, position) { }
    554 
    555     public:
    556         ListHashSetReverseIterator() { }
    557 
    558         // default copy, assignment and destructor are OK
    559 
    560         PointerType get() const { return const_cast<PointerType>(m_iterator.get()); }
    561         ReferenceType operator*() const { return *get(); }
    562         PointerType operator->() const { return get(); }
    563 
    564         ListHashSetReverseIterator& operator++() { ++m_iterator; return *this; }
    565         ListHashSetReverseIterator& operator--() { --m_iterator; return *this; }
    566 
    567         // Postfix ++ and -- intentionally omitted.
    568 
    569         // Comparison.
    570         bool operator==(const ListHashSetReverseIterator& other) const { return m_iterator == other.m_iterator; }
    571         bool operator!=(const ListHashSetReverseIterator& other) const { return m_iterator != other.m_iterator; }
    572 
    573         operator const_reverse_iterator() const { return m_iterator; }
    574 
    575     private:
    576         Node* node() { return m_iterator.node(); }
    577 
    578         const_reverse_iterator m_iterator;
    579 
    580         template<typename T, size_t inlineCapacity, typename U, typename V>
    581         friend class ListHashSet;
    582     };
    583 
    584     template<typename Set> class ListHashSetConstReverseIterator {
    585     private:
    586         typedef typename Set::reverse_iterator reverse_iterator;
    587         typedef typename Set::Node Node;
    588         typedef typename Set::ValueType ValueType;
    589         typedef const ValueType& ReferenceType;
    590         typedef const ValueType* PointerType;
    591 
    592         friend class ListHashSetReverseIterator<Set>;
    593 
    594         ListHashSetConstReverseIterator(const Set* set, Node* position)
    595             : m_set(set)
    596             , m_position(position)
    597         {
    598         }
    599 
    600     public:
    601         ListHashSetConstReverseIterator()
    602         {
    603         }
    604 
    605         PointerType get() const
    606         {
    607             return &m_position->m_value;
    608         }
    609         ReferenceType operator*() const { return *get(); }
    610         PointerType operator->() const { return get(); }
    611 
    612         ListHashSetConstReverseIterator& operator++()
    613         {
    614             ASSERT(m_position != 0);
    615             m_position = m_position->prev();
    616             return *this;
    617         }
    618 
    619         ListHashSetConstReverseIterator& operator--()
    620         {
    621             ASSERT(m_position != m_set->m_tail);
    622             if (!m_position)
    623                 m_position = m_set->m_head;
    624             else
    625                 m_position = m_position->next();
    626             return *this;
    627         }
    628 
    629         // Postfix ++ and -- intentionally omitted.
    630 
    631         // Comparison.
    632         bool operator==(const ListHashSetConstReverseIterator& other) const
    633         {
    634             return m_position == other.m_position;
    635         }
    636         bool operator!=(const ListHashSetConstReverseIterator& other) const
    637         {
    638             return m_position != other.m_position;
    639         }
    640 
    641     private:
    642         Node* node() { return m_position; }
    643 
    644         const Set* m_set;
    645         Node* m_position;
    646 
    647         template<typename T, size_t inlineCapacity, typename U, typename V>
    648         friend class ListHashSet;
    649     };
    650 
    651     template<typename HashFunctions>
    652     struct ListHashSetTranslator {
    653         template<typename T> static unsigned hash(const T& key) { return HashFunctions::hash(key); }
    654         template<typename T, typename U> static bool equal(const T& a, const U& b) { return HashFunctions::equal(a->m_value, b); }
    655         template<typename T, typename U, typename V> static void translate(T*& location, const U& key, const V& allocator)
    656         {
    657             location = new (const_cast<V*>(&allocator)) T(key);
    658         }
    659     };
    660 
    661     template<typename T, size_t inlineCapacity, typename U, typename V>
    662     inline ListHashSet<T, inlineCapacity, U, V>::ListHashSet()
    663         : m_head(0)
    664         , m_tail(0)
    665     {
    666     }
    667 
    668     template<typename T, size_t inlineCapacity, typename U, typename V>
    669     inline ListHashSet<T, inlineCapacity, U, V>::ListHashSet(const ListHashSet& other)
    670         : m_head(0)
    671         , m_tail(0)
    672     {
    673         const_iterator end = other.end();
    674         for (const_iterator it = other.begin(); it != end; ++it)
    675             add(*it);
    676     }
    677 
    678     template<typename T, size_t inlineCapacity, typename U, typename V>
    679     inline ListHashSet<T, inlineCapacity, U, V>& ListHashSet<T, inlineCapacity, U, V>::operator=(const ListHashSet& other)
    680     {
    681         ListHashSet tmp(other);
    682         swap(tmp);
    683         return *this;
    684     }
    685 
    686     template<typename T, size_t inlineCapacity, typename U, typename V>
    687     inline void ListHashSet<T, inlineCapacity, U, V>::swap(ListHashSet& other)
    688     {
    689         m_impl.swap(other.m_impl);
    690         std::swap(m_head, other.m_head);
    691         std::swap(m_tail, other.m_tail);
    692         this->m_allocatorProvider.swap(other.m_allocatorProvider);
    693     }
    694 
    695     template<typename T, size_t inlineCapacity, typename U, typename V>
    696     inline void ListHashSet<T, inlineCapacity, U, V>::finalize()
    697     {
    698         COMPILE_ASSERT(!Allocator::isGarbageCollected, FinalizeOnHeapAllocatedListHashSetShouldNeverBeCalled);
    699         deleteAllNodes();
    700     }
    701 
    702     template<typename T, size_t inlineCapacity, typename U, typename V>
    703     inline T& ListHashSet<T, inlineCapacity, U, V>::first()
    704     {
    705         ASSERT(!isEmpty());
    706         return m_head->m_value;
    707     }
    708 
    709     template<typename T, size_t inlineCapacity, typename U, typename V>
    710     inline void ListHashSet<T, inlineCapacity, U, V>::removeFirst()
    711     {
    712         ASSERT(!isEmpty());
    713         m_impl.remove(m_head);
    714         unlinkAndDelete(m_head);
    715     }
    716 
    717     template<typename T, size_t inlineCapacity, typename U, typename V>
    718     inline const T& ListHashSet<T, inlineCapacity, U, V>::first() const
    719     {
    720         ASSERT(!isEmpty());
    721         return m_head->m_value;
    722     }
    723 
    724     template<typename T, size_t inlineCapacity, typename U, typename V>
    725     inline T& ListHashSet<T, inlineCapacity, U, V>::last()
    726     {
    727         ASSERT(!isEmpty());
    728         return m_tail->m_value;
    729     }
    730 
    731     template<typename T, size_t inlineCapacity, typename U, typename V>
    732     inline const T& ListHashSet<T, inlineCapacity, U, V>::last() const
    733     {
    734         ASSERT(!isEmpty());
    735         return m_tail->m_value;
    736     }
    737 
    738     template<typename T, size_t inlineCapacity, typename U, typename V>
    739     inline void ListHashSet<T, inlineCapacity, U, V>::removeLast()
    740     {
    741         ASSERT(!isEmpty());
    742         m_impl.remove(m_tail);
    743         unlinkAndDelete(m_tail);
    744     }
    745 
    746     template<typename T, size_t inlineCapacity, typename U, typename V>
    747     inline typename ListHashSet<T, inlineCapacity, U, V>::iterator ListHashSet<T, inlineCapacity, U, V>::find(ValuePeekInType value)
    748     {
    749         ImplTypeIterator it = m_impl.template find<BaseTranslator>(value);
    750         if (it == m_impl.end())
    751             return end();
    752         return makeIterator(*it);
    753     }
    754 
    755     template<typename T, size_t inlineCapacity, typename U, typename V>
    756     inline typename ListHashSet<T, inlineCapacity, U, V>::const_iterator ListHashSet<T, inlineCapacity, U, V>::find(ValuePeekInType value) const
    757     {
    758         ImplTypeConstIterator it = m_impl.template find<BaseTranslator>(value);
    759         if (it == m_impl.end())
    760             return end();
    761         return makeConstIterator(*it);
    762     }
    763 
    764     template<typename Translator>
    765     struct ListHashSetTranslatorAdapter {
    766         template<typename T> static unsigned hash(const T& key) { return Translator::hash(key); }
    767         template<typename T, typename U> static bool equal(const T& a, const U& b) { return Translator::equal(a->m_value, b); }
    768     };
    769 
    770     template<typename ValueType, size_t inlineCapacity, typename U, typename V>
    771     template<typename HashTranslator, typename T>
    772     inline typename ListHashSet<ValueType, inlineCapacity, U, V>::iterator ListHashSet<ValueType, inlineCapacity, U, V>::find(const T& value)
    773     {
    774         ImplTypeConstIterator it = m_impl.template find<ListHashSetTranslatorAdapter<HashTranslator> >(value);
    775         if (it == m_impl.end())
    776             return end();
    777         return makeIterator(*it);
    778     }
    779 
    780     template<typename ValueType, size_t inlineCapacity, typename U, typename V>
    781     template<typename HashTranslator, typename T>
    782     inline typename ListHashSet<ValueType, inlineCapacity, U, V>::const_iterator ListHashSet<ValueType, inlineCapacity, U, V>::find(const T& value) const
    783     {
    784         ImplTypeConstIterator it = m_impl.template find<ListHashSetTranslatorAdapter<HashTranslator> >(value);
    785         if (it == m_impl.end())
    786             return end();
    787         return makeConstIterator(*it);
    788     }
    789 
    790     template<typename ValueType, size_t inlineCapacity, typename U, typename V>
    791     template<typename HashTranslator, typename T>
    792     inline bool ListHashSet<ValueType, inlineCapacity, U, V>::contains(const T& value) const
    793     {
    794         return m_impl.template contains<ListHashSetTranslatorAdapter<HashTranslator> >(value);
    795     }
    796 
    797     template<typename T, size_t inlineCapacity, typename U, typename V>
    798     inline bool ListHashSet<T, inlineCapacity, U, V>::contains(ValuePeekInType value) const
    799     {
    800         return m_impl.template contains<BaseTranslator>(value);
    801     }
    802 
    803     template<typename T, size_t inlineCapacity, typename U, typename V>
    804     typename ListHashSet<T, inlineCapacity, U, V>::AddResult ListHashSet<T, inlineCapacity, U, V>::add(ValuePassInType value)
    805     {
    806         createAllocatorIfNeeded();
    807         // The second argument is a const ref. This is useful for the HashTable
    808         // because it lets it take lvalues by reference, but for our purposes
    809         // it's inconvenient, since it constrains us to be const, whereas the
    810         // allocator actually changes when it does allocations.
    811         typename ImplType::AddResult result = m_impl.template add<BaseTranslator>(value, *this->allocator());
    812         if (result.isNewEntry)
    813             appendNode(*result.storedValue);
    814         return AddResult(*result.storedValue, result.isNewEntry);
    815     }
    816 
    817     template<typename T, size_t inlineCapacity, typename U, typename V>
    818     typename ListHashSet<T, inlineCapacity, U, V>::iterator ListHashSet<T, inlineCapacity, U, V>::addReturnIterator(ValuePassInType value)
    819     {
    820         return makeIterator(add(value).storedValue);
    821     }
    822 
    823     template<typename T, size_t inlineCapacity, typename U, typename V>
    824     typename ListHashSet<T, inlineCapacity, U, V>::AddResult ListHashSet<T, inlineCapacity, U, V>::appendOrMoveToLast(ValuePassInType value)
    825     {
    826         createAllocatorIfNeeded();
    827         typename ImplType::AddResult result = m_impl.template add<BaseTranslator>(value, *this->allocator());
    828         Node* node = *result.storedValue;
    829         if (!result.isNewEntry)
    830             unlink(node);
    831         appendNode(node);
    832         return AddResult(*result.storedValue, result.isNewEntry);
    833     }
    834 
    835     template<typename T, size_t inlineCapacity, typename U, typename V>
    836     typename ListHashSet<T, inlineCapacity, U, V>::AddResult ListHashSet<T, inlineCapacity, U, V>::prependOrMoveToFirst(ValuePassInType value)
    837     {
    838         createAllocatorIfNeeded();
    839         typename ImplType::AddResult result = m_impl.template add<BaseTranslator>(value, *this->allocator());
    840         Node* node = *result.storedValue;
    841         if (!result.isNewEntry)
    842             unlink(node);
    843         prependNode(node);
    844         return AddResult(*result.storedValue, result.isNewEntry);
    845     }
    846 
    847     template<typename T, size_t inlineCapacity, typename U, typename V>
    848     typename ListHashSet<T, inlineCapacity, U, V>::AddResult ListHashSet<T, inlineCapacity, U, V>::insertBefore(iterator it, ValuePassInType newValue)
    849     {
    850         createAllocatorIfNeeded();
    851         typename ImplType::AddResult result = m_impl.template add<BaseTranslator>(newValue, *this->allocator());
    852         if (result.isNewEntry)
    853             insertNodeBefore(it.node(), *result.storedValue);
    854         return AddResult(*result.storedValue, result.isNewEntry);
    855     }
    856 
    857     template<typename T, size_t inlineCapacity, typename U, typename V>
    858     typename ListHashSet<T, inlineCapacity, U, V>::AddResult ListHashSet<T, inlineCapacity, U, V>::insertBefore(ValuePeekInType beforeValue, ValuePassInType newValue)
    859     {
    860         createAllocatorIfNeeded();
    861         return insertBefore(find(beforeValue), newValue);
    862     }
    863 
    864     template<typename T, size_t inlineCapacity, typename U, typename V>
    865     inline void ListHashSet<T, inlineCapacity, U, V>::remove(iterator it)
    866     {
    867         if (it == end())
    868             return;
    869         m_impl.remove(it.node());
    870         unlinkAndDelete(it.node());
    871     }
    872 
    873     template<typename T, size_t inlineCapacity, typename U, typename V>
    874     inline void ListHashSet<T, inlineCapacity, U, V>::clear()
    875     {
    876         deleteAllNodes();
    877         m_impl.clear();
    878         m_head = 0;
    879         m_tail = 0;
    880     }
    881 
    882     template<typename T, size_t inlineCapacity, typename U, typename V>
    883     typename ListHashSet<T, inlineCapacity, U, V>::ValuePassOutType ListHashSet<T, inlineCapacity, U, V>::take(iterator it)
    884     {
    885         if (it == end())
    886             return ValueTraits::emptyValue();
    887 
    888         m_impl.remove(it.node());
    889         ValuePassOutType result = ValueTraits::passOut(it.node()->m_value);
    890         unlinkAndDelete(it.node());
    891 
    892         return result;
    893     }
    894 
    895     template<typename T, size_t inlineCapacity, typename U, typename V>
    896     typename ListHashSet<T, inlineCapacity, U, V>::ValuePassOutType ListHashSet<T, inlineCapacity, U, V>::take(ValuePeekInType value)
    897     {
    898         return take(find(value));
    899     }
    900 
    901     template<typename T, size_t inlineCapacity, typename U, typename V>
    902     typename ListHashSet<T, inlineCapacity, U, V>::ValuePassOutType ListHashSet<T, inlineCapacity, U, V>::takeFirst()
    903     {
    904         ASSERT(!isEmpty());
    905         m_impl.remove(m_head);
    906         ValuePassOutType result = ValueTraits::passOut(m_head->m_value);
    907         unlinkAndDelete(m_head);
    908 
    909         return result;
    910     }
    911 
    912     template<typename T, size_t inlineCapacity, typename U, typename Allocator>
    913     void ListHashSet<T, inlineCapacity, U, Allocator>::unlink(Node* node)
    914     {
    915         if (!node->m_prev) {
    916             ASSERT(node == m_head);
    917             m_head = node->next();
    918         } else {
    919             ASSERT(node != m_head);
    920             node->m_prev->m_next = node->m_next;
    921         }
    922 
    923         if (!node->m_next) {
    924             ASSERT(node == m_tail);
    925             m_tail = node->prev();
    926         } else {
    927             ASSERT(node != m_tail);
    928             node->m_next->m_prev = node->m_prev;
    929         }
    930     }
    931 
    932     template<typename T, size_t inlineCapacity, typename U, typename V>
    933     void ListHashSet<T, inlineCapacity, U, V>::unlinkAndDelete(Node* node)
    934     {
    935         unlink(node);
    936         node->destroy(this->allocator());
    937     }
    938 
    939     template<typename T, size_t inlineCapacity, typename U, typename V>
    940     void ListHashSet<T, inlineCapacity, U, V>::appendNode(Node* node)
    941     {
    942         node->m_prev = m_tail;
    943         node->m_next = 0;
    944 
    945         if (m_tail) {
    946             ASSERT(m_head);
    947             m_tail->m_next = node;
    948         } else {
    949             ASSERT(!m_head);
    950             m_head = node;
    951         }
    952 
    953         m_tail = node;
    954     }
    955 
    956     template<typename T, size_t inlineCapacity, typename U, typename V>
    957     void ListHashSet<T, inlineCapacity, U, V>::prependNode(Node* node)
    958     {
    959         node->m_prev = 0;
    960         node->m_next = m_head;
    961 
    962         if (m_head)
    963             m_head->m_prev = node;
    964         else
    965             m_tail = node;
    966 
    967         m_head = node;
    968     }
    969 
    970     template<typename T, size_t inlineCapacity, typename U, typename V>
    971     void ListHashSet<T, inlineCapacity, U, V>::insertNodeBefore(Node* beforeNode, Node* newNode)
    972     {
    973         if (!beforeNode)
    974             return appendNode(newNode);
    975 
    976         newNode->m_next = beforeNode;
    977         newNode->m_prev = beforeNode->m_prev;
    978         if (beforeNode->m_prev)
    979             beforeNode->m_prev->m_next = newNode;
    980         beforeNode->m_prev = newNode;
    981 
    982         if (!newNode->m_prev)
    983             m_head = newNode;
    984     }
    985 
    986     template<typename T, size_t inlineCapacity, typename U, typename V>
    987     void ListHashSet<T, inlineCapacity, U, V>::deleteAllNodes()
    988     {
    989         if (!m_head)
    990             return;
    991 
    992         for (Node* node = m_head, *next = m_head->next(); node; node = next, next = node ? node->next() : 0)
    993             node->destroy(this->allocator());
    994     }
    995 
    996     template<typename T, size_t inlineCapacity, typename U, typename V>
    997     void ListHashSet<T, inlineCapacity, U, V>::trace(typename Allocator::Visitor* visitor)
    998     {
    999         COMPILE_ASSERT(HashTraits<T>::weakHandlingFlag == NoWeakHandlingInCollections, ListHashSetDoesNotSupportWeakness);
   1000         // This marks all the nodes and their contents live that can be
   1001         // accessed through the HashTable. That includes m_head and m_tail
   1002         // so we do not have to explicitly trace them here.
   1003         m_impl.trace(visitor);
   1004     }
   1005 
   1006 } // namespace WTF
   1007 
   1008 using WTF::ListHashSet;
   1009 
   1010 #endif /* WTF_ListHashSet_h */
   1011