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/HashSet.h"
     26 #include "wtf/OwnPtr.h"
     27 #include "wtf/PassOwnPtr.h"
     28 
     29 namespace WTF {
     30 
     31     // ListHashSet: Just like HashSet, this class provides a Set
     32     // interface - a collection of unique objects with O(1) insertion,
     33     // removal and test for containership. However, it also has an
     34     // order - iterating it will always give back values in the order
     35     // in which they are added.
     36 
     37     // Unlike iteration of most WTF Hash data structures, iteration is
     38     // guaranteed safe against mutation of the ListHashSet, except for
     39     // removal of the item currently pointed to by a given iterator.
     40 
     41     template<typename Value, size_t inlineCapacity, typename HashFunctions> class ListHashSet;
     42 
     43     template<typename Value, size_t inlineCapacity, typename HashFunctions>
     44     void deleteAllValues(const ListHashSet<Value, inlineCapacity, HashFunctions>&);
     45 
     46     template<typename ValueArg, size_t inlineCapacity, typename HashArg> class ListHashSetIterator;
     47     template<typename ValueArg, size_t inlineCapacity, typename HashArg> class ListHashSetConstIterator;
     48     template<typename ValueArg, size_t inlineCapacity, typename HashArg> class ListHashSetReverseIterator;
     49     template<typename ValueArg, size_t inlineCapacity, typename HashArg> class ListHashSetConstReverseIterator;
     50 
     51     template<typename ValueArg, size_t inlineCapacity> struct ListHashSetNode;
     52     template<typename ValueArg, size_t inlineCapacity> struct ListHashSetNodeAllocator;
     53 
     54     template<typename HashArg> struct ListHashSetNodeHashFunctions;
     55     template<typename HashArg> struct ListHashSetTranslator;
     56 
     57     template<typename ValueArg, size_t inlineCapacity = 256, typename HashArg = typename DefaultHash<ValueArg>::Hash> class ListHashSet {
     58         WTF_MAKE_FAST_ALLOCATED;
     59     private:
     60         typedef ListHashSetNode<ValueArg, inlineCapacity> Node;
     61         typedef ListHashSetNodeAllocator<ValueArg, inlineCapacity> NodeAllocator;
     62 
     63         typedef HashTraits<Node*> NodeTraits;
     64         typedef ListHashSetNodeHashFunctions<HashArg> NodeHash;
     65         typedef ListHashSetTranslator<HashArg> BaseTranslator;
     66 
     67         typedef HashTable<Node*, Node*, IdentityExtractor, NodeHash, NodeTraits, NodeTraits> ImplType;
     68         typedef HashTableIterator<Node*, Node*, IdentityExtractor, NodeHash, NodeTraits, NodeTraits> ImplTypeIterator;
     69         typedef HashTableConstIterator<Node*, Node*, IdentityExtractor, NodeHash, NodeTraits, NodeTraits> ImplTypeConstIterator;
     70 
     71         typedef HashArg HashFunctions;
     72 
     73     public:
     74         typedef ValueArg ValueType;
     75 
     76         typedef ListHashSetIterator<ValueType, inlineCapacity, HashArg> iterator;
     77         typedef ListHashSetConstIterator<ValueType, inlineCapacity, HashArg> const_iterator;
     78         friend class ListHashSetConstIterator<ValueType, inlineCapacity, HashArg>;
     79 
     80         typedef ListHashSetReverseIterator<ValueType, inlineCapacity, HashArg> reverse_iterator;
     81         typedef ListHashSetConstReverseIterator<ValueType, inlineCapacity, HashArg> const_reverse_iterator;
     82         friend class ListHashSetConstReverseIterator<ValueType, inlineCapacity, HashArg>;
     83 
     84         typedef HashTableAddResult<iterator> AddResult;
     85 
     86         ListHashSet();
     87         ListHashSet(const ListHashSet&);
     88         ListHashSet& operator=(const ListHashSet&);
     89         ~ListHashSet();
     90 
     91         void swap(ListHashSet&);
     92 
     93         unsigned size() const;
     94         unsigned capacity() const;
     95         bool isEmpty() const;
     96 
     97         size_t sizeInBytes() const;
     98 
     99         iterator begin();
    100         iterator end();
    101         const_iterator begin() const;
    102         const_iterator end() const;
    103 
    104         reverse_iterator rbegin();
    105         reverse_iterator rend();
    106         const_reverse_iterator rbegin() const;
    107         const_reverse_iterator rend() const;
    108 
    109         ValueType& first();
    110         const ValueType& first() const;
    111         void removeFirst();
    112 
    113         ValueType& last();
    114         const ValueType& last() const;
    115         void removeLast();
    116 
    117         iterator find(const ValueType&);
    118         const_iterator find(const ValueType&) const;
    119         bool contains(const ValueType&) const;
    120 
    121         // An alternate version of find() that finds the object by hashing and comparing
    122         // with some other type, to avoid the cost of type conversion.
    123         // The HashTranslator interface is defined in HashSet.
    124         template<typename HashTranslator, typename T> iterator find(const T&);
    125         template<typename HashTranslator, typename T> const_iterator find(const T&) const;
    126         template<typename HashTranslator, typename T> bool contains(const T&) const;
    127 
    128         // The return value of add is a pair of an iterator to the new value's location,
    129         // and a bool that is true if an new entry was added.
    130         AddResult add(const ValueType&);
    131 
    132         // Add the value to the end of the collection. If the value was already in
    133         // the list, it is moved to the end.
    134         AddResult appendOrMoveToLast(const ValueType&);
    135 
    136         // Add the value to the beginning of the collection. If the value was already in
    137         // the list, it is moved to the beginning.
    138         AddResult prependOrMoveToFirst(const ValueType&);
    139 
    140         AddResult insertBefore(const ValueType& beforeValue, const ValueType& newValue);
    141         AddResult insertBefore(iterator, const ValueType&);
    142 
    143         void remove(const ValueType&);
    144         void remove(iterator);
    145         void clear();
    146 
    147     private:
    148         void unlink(Node*);
    149         void unlinkAndDelete(Node*);
    150         void appendNode(Node*);
    151         void prependNode(Node*);
    152         void insertNodeBefore(Node* beforeNode, Node* newNode);
    153         void deleteAllNodes();
    154         void createAllocatorIfNeeded();
    155 
    156         iterator makeIterator(Node*);
    157         const_iterator makeConstIterator(Node*) const;
    158         reverse_iterator makeReverseIterator(Node*);
    159         const_reverse_iterator makeConstReverseIterator(Node*) const;
    160 
    161         friend void deleteAllValues<>(const ListHashSet&);
    162 
    163         ImplType m_impl;
    164         Node* m_head;
    165         Node* m_tail;
    166         OwnPtr<NodeAllocator> m_allocator;
    167     };
    168 
    169     template<typename ValueArg, size_t inlineCapacity> struct ListHashSetNodeAllocator {
    170         typedef ListHashSetNode<ValueArg, inlineCapacity> Node;
    171         typedef ListHashSetNodeAllocator<ValueArg, inlineCapacity> NodeAllocator;
    172 
    173         ListHashSetNodeAllocator()
    174             : m_freeList(pool())
    175             , m_isDoneWithInitialFreeList(false)
    176         {
    177             memset(m_pool.pool, 0, sizeof(m_pool.pool));
    178         }
    179 
    180         Node* allocate()
    181         {
    182             Node* result = m_freeList;
    183 
    184             if (!result)
    185                 return static_cast<Node*>(fastMalloc(sizeof(Node)));
    186 
    187             ASSERT(!result->m_isAllocated);
    188 
    189             Node* next = result->m_next;
    190             ASSERT(!next || !next->m_isAllocated);
    191             if (!next && !m_isDoneWithInitialFreeList) {
    192                 next = result + 1;
    193                 if (next == pastPool()) {
    194                     m_isDoneWithInitialFreeList = true;
    195                     next = 0;
    196                 } else {
    197                     ASSERT(inPool(next));
    198                     ASSERT(!next->m_isAllocated);
    199                 }
    200             }
    201             m_freeList = next;
    202 
    203             return result;
    204         }
    205 
    206         void deallocate(Node* node)
    207         {
    208             if (inPool(node)) {
    209 #ifndef NDEBUG
    210                 node->m_isAllocated = false;
    211 #endif
    212                 node->m_next = m_freeList;
    213                 m_freeList = node;
    214                 return;
    215             }
    216 
    217             fastFree(node);
    218         }
    219 
    220         bool inPool(Node* node)
    221         {
    222             return node >= pool() && node < pastPool();
    223         }
    224 
    225     private:
    226         Node* pool() { return reinterpret_cast_ptr<Node*>(m_pool.pool); }
    227         Node* pastPool() { return pool() + m_poolSize; }
    228 
    229         Node* m_freeList;
    230         bool m_isDoneWithInitialFreeList;
    231         static const size_t m_poolSize = inlineCapacity;
    232         union {
    233             char pool[sizeof(Node) * m_poolSize];
    234             double forAlignment;
    235         } m_pool;
    236     };
    237 
    238     template<typename ValueArg, size_t inlineCapacity> struct ListHashSetNode {
    239         typedef ListHashSetNodeAllocator<ValueArg, inlineCapacity> NodeAllocator;
    240 
    241         ListHashSetNode(ValueArg value)
    242             : m_value(value)
    243             , m_prev(0)
    244             , m_next(0)
    245 #ifndef NDEBUG
    246             , m_isAllocated(true)
    247 #endif
    248         {
    249         }
    250 
    251         void* operator new(size_t, NodeAllocator* allocator)
    252         {
    253             return allocator->allocate();
    254         }
    255         void destroy(NodeAllocator* allocator)
    256         {
    257             this->~ListHashSetNode();
    258             allocator->deallocate(this);
    259         }
    260 
    261         ValueArg m_value;
    262         ListHashSetNode* m_prev;
    263         ListHashSetNode* m_next;
    264 
    265 #ifndef NDEBUG
    266         bool m_isAllocated;
    267 #endif
    268     };
    269 
    270     template<typename HashArg> struct ListHashSetNodeHashFunctions {
    271         template<typename T> static unsigned hash(const T& key) { return HashArg::hash(key->m_value); }
    272         template<typename T> static bool equal(const T& a, const T& b) { return HashArg::equal(a->m_value, b->m_value); }
    273         static const bool safeToCompareToEmptyOrDeleted = false;
    274     };
    275 
    276     template<typename ValueArg, size_t inlineCapacity, typename HashArg> class ListHashSetIterator {
    277     private:
    278         typedef ListHashSet<ValueArg, inlineCapacity, HashArg> ListHashSetType;
    279         typedef ListHashSetIterator<ValueArg, inlineCapacity, HashArg> iterator;
    280         typedef ListHashSetConstIterator<ValueArg, inlineCapacity, HashArg> const_iterator;
    281         typedef ListHashSetNode<ValueArg, inlineCapacity> Node;
    282         typedef ValueArg ValueType;
    283         typedef ValueType& ReferenceType;
    284         typedef ValueType* PointerType;
    285 
    286         friend class ListHashSet<ValueArg, inlineCapacity, HashArg>;
    287 
    288         ListHashSetIterator(const ListHashSetType* set, Node* position) : m_iterator(set, position) { }
    289 
    290     public:
    291         ListHashSetIterator() { }
    292 
    293         // default copy, assignment and destructor are OK
    294 
    295         PointerType get() const { return const_cast<PointerType>(m_iterator.get()); }
    296         ReferenceType operator*() const { return *get(); }
    297         PointerType operator->() const { return get(); }
    298 
    299         iterator& operator++() { ++m_iterator; return *this; }
    300 
    301         // postfix ++ intentionally omitted
    302 
    303         iterator& operator--() { --m_iterator; return *this; }
    304 
    305         // postfix -- intentionally omitted
    306 
    307         // Comparison.
    308         bool operator==(const iterator& other) const { return m_iterator == other.m_iterator; }
    309         bool operator!=(const iterator& other) const { return m_iterator != other.m_iterator; }
    310 
    311         operator const_iterator() const { return m_iterator; }
    312 
    313     private:
    314         Node* node() { return m_iterator.node(); }
    315 
    316         const_iterator m_iterator;
    317     };
    318 
    319     template<typename ValueArg, size_t inlineCapacity, typename HashArg> class ListHashSetConstIterator {
    320     private:
    321         typedef ListHashSet<ValueArg, inlineCapacity, HashArg> ListHashSetType;
    322         typedef ListHashSetIterator<ValueArg, inlineCapacity, HashArg> iterator;
    323         typedef ListHashSetConstIterator<ValueArg, inlineCapacity, HashArg> const_iterator;
    324         typedef ListHashSetNode<ValueArg, inlineCapacity> Node;
    325         typedef ValueArg ValueType;
    326         typedef const ValueType& ReferenceType;
    327         typedef const ValueType* PointerType;
    328 
    329         friend class ListHashSet<ValueArg, inlineCapacity, HashArg>;
    330         friend class ListHashSetIterator<ValueArg, inlineCapacity, HashArg>;
    331 
    332         ListHashSetConstIterator(const ListHashSetType* set, Node* position)
    333             : m_set(set)
    334             , m_position(position)
    335         {
    336         }
    337 
    338     public:
    339         ListHashSetConstIterator()
    340         {
    341         }
    342 
    343         PointerType get() const
    344         {
    345             return &m_position->m_value;
    346         }
    347         ReferenceType operator*() const { return *get(); }
    348         PointerType operator->() const { return get(); }
    349 
    350         const_iterator& operator++()
    351         {
    352             ASSERT(m_position != 0);
    353             m_position = m_position->m_next;
    354             return *this;
    355         }
    356 
    357         // postfix ++ intentionally omitted
    358 
    359         const_iterator& operator--()
    360         {
    361             ASSERT(m_position != m_set->m_head);
    362             if (!m_position)
    363                 m_position = m_set->m_tail;
    364             else
    365                 m_position = m_position->m_prev;
    366             return *this;
    367         }
    368 
    369         // postfix -- intentionally omitted
    370 
    371         // Comparison.
    372         bool operator==(const const_iterator& other) const
    373         {
    374             return m_position == other.m_position;
    375         }
    376         bool operator!=(const const_iterator& other) const
    377         {
    378             return m_position != other.m_position;
    379         }
    380 
    381     private:
    382         Node* node() { return m_position; }
    383 
    384         const ListHashSetType* m_set;
    385         Node* m_position;
    386     };
    387 
    388     template<typename ValueArg, size_t inlineCapacity, typename HashArg> class ListHashSetReverseIterator {
    389     private:
    390         typedef ListHashSet<ValueArg, inlineCapacity, HashArg> ListHashSetType;
    391         typedef ListHashSetReverseIterator<ValueArg, inlineCapacity, HashArg> reverse_iterator;
    392         typedef ListHashSetConstReverseIterator<ValueArg, inlineCapacity, HashArg> const_reverse_iterator;
    393         typedef ListHashSetNode<ValueArg, inlineCapacity> Node;
    394         typedef ValueArg ValueType;
    395         typedef ValueType& ReferenceType;
    396         typedef ValueType* PointerType;
    397 
    398         friend class ListHashSet<ValueArg, inlineCapacity, HashArg>;
    399 
    400         ListHashSetReverseIterator(const ListHashSetType* set, Node* position) : m_iterator(set, position) { }
    401 
    402     public:
    403         ListHashSetReverseIterator() { }
    404 
    405         // default copy, assignment and destructor are OK
    406 
    407         PointerType get() const { return const_cast<PointerType>(m_iterator.get()); }
    408         ReferenceType operator*() const { return *get(); }
    409         PointerType operator->() const { return get(); }
    410 
    411         reverse_iterator& operator++() { ++m_iterator; return *this; }
    412 
    413         // postfix ++ intentionally omitted
    414 
    415         reverse_iterator& operator--() { --m_iterator; return *this; }
    416 
    417         // postfix -- intentionally omitted
    418 
    419         // Comparison.
    420         bool operator==(const reverse_iterator& other) const { return m_iterator == other.m_iterator; }
    421         bool operator!=(const reverse_iterator& other) const { return m_iterator != other.m_iterator; }
    422 
    423         operator const_reverse_iterator() const { return m_iterator; }
    424 
    425     private:
    426         Node* node() { return m_iterator.node(); }
    427 
    428         const_reverse_iterator m_iterator;
    429     };
    430 
    431     template<typename ValueArg, size_t inlineCapacity, typename HashArg> class ListHashSetConstReverseIterator {
    432     private:
    433         typedef ListHashSet<ValueArg, inlineCapacity, HashArg> ListHashSetType;
    434         typedef ListHashSetReverseIterator<ValueArg, inlineCapacity, HashArg> reverse_iterator;
    435         typedef ListHashSetConstReverseIterator<ValueArg, inlineCapacity, HashArg> const_reverse_iterator;
    436         typedef ListHashSetNode<ValueArg, inlineCapacity> Node;
    437         typedef ValueArg ValueType;
    438         typedef const ValueType& ReferenceType;
    439         typedef const ValueType* PointerType;
    440 
    441         friend class ListHashSet<ValueArg, inlineCapacity, HashArg>;
    442         friend class ListHashSetReverseIterator<ValueArg, inlineCapacity, HashArg>;
    443 
    444         ListHashSetConstReverseIterator(const ListHashSetType* set, Node* position)
    445             : m_set(set)
    446             , m_position(position)
    447         {
    448         }
    449 
    450     public:
    451         ListHashSetConstReverseIterator()
    452         {
    453         }
    454 
    455         PointerType get() const
    456         {
    457             return &m_position->m_value;
    458         }
    459         ReferenceType operator*() const { return *get(); }
    460         PointerType operator->() const { return get(); }
    461 
    462         const_reverse_iterator& operator++()
    463         {
    464             ASSERT(m_position != 0);
    465             m_position = m_position->m_prev;
    466             return *this;
    467         }
    468 
    469         // postfix ++ intentionally omitted
    470 
    471         const_reverse_iterator& operator--()
    472         {
    473             ASSERT(m_position != m_set->m_tail);
    474             if (!m_position)
    475                 m_position = m_set->m_head;
    476             else
    477                 m_position = m_position->m_next;
    478             return *this;
    479         }
    480 
    481         // postfix -- intentionally omitted
    482 
    483         // Comparison.
    484         bool operator==(const const_reverse_iterator& other) const
    485         {
    486             return m_position == other.m_position;
    487         }
    488         bool operator!=(const const_reverse_iterator& other) const
    489         {
    490             return m_position != other.m_position;
    491         }
    492 
    493     private:
    494         Node* node() { return m_position; }
    495 
    496         const ListHashSetType* m_set;
    497         Node* m_position;
    498     };
    499 
    500     template<typename HashFunctions>
    501     struct ListHashSetTranslator {
    502         template<typename T> static unsigned hash(const T& key) { return HashFunctions::hash(key); }
    503         template<typename T, typename U> static bool equal(const T& a, const U& b) { return HashFunctions::equal(a->m_value, b); }
    504         template<typename T, typename U, typename V> static void translate(T*& location, const U& key, const V& allocator)
    505         {
    506             location = new (allocator) T(key);
    507         }
    508     };
    509 
    510     template<typename T, size_t inlineCapacity, typename U>
    511     inline ListHashSet<T, inlineCapacity, U>::ListHashSet()
    512         : m_head(0)
    513         , m_tail(0)
    514     {
    515     }
    516 
    517     template<typename T, size_t inlineCapacity, typename U>
    518     inline ListHashSet<T, inlineCapacity, U>::ListHashSet(const ListHashSet& other)
    519         : m_head(0)
    520         , m_tail(0)
    521     {
    522         const_iterator end = other.end();
    523         for (const_iterator it = other.begin(); it != end; ++it)
    524             add(*it);
    525     }
    526 
    527     template<typename T, size_t inlineCapacity, typename U>
    528     inline ListHashSet<T, inlineCapacity, U>& ListHashSet<T, inlineCapacity, U>::operator=(const ListHashSet& other)
    529     {
    530         ListHashSet tmp(other);
    531         swap(tmp);
    532         return *this;
    533     }
    534 
    535     template<typename T, size_t inlineCapacity, typename U>
    536     inline void ListHashSet<T, inlineCapacity, U>::swap(ListHashSet& other)
    537     {
    538         m_impl.swap(other.m_impl);
    539         std::swap(m_head, other.m_head);
    540         std::swap(m_tail, other.m_tail);
    541         m_allocator.swap(other.m_allocator);
    542     }
    543 
    544     template<typename T, size_t inlineCapacity, typename U>
    545     inline ListHashSet<T, inlineCapacity, U>::~ListHashSet()
    546     {
    547         deleteAllNodes();
    548     }
    549 
    550     template<typename T, size_t inlineCapacity, typename U>
    551     inline unsigned ListHashSet<T, inlineCapacity, U>::size() const
    552     {
    553         return m_impl.size();
    554     }
    555 
    556     template<typename T, size_t inlineCapacity, typename U>
    557     inline unsigned ListHashSet<T, inlineCapacity, U>::capacity() const
    558     {
    559         return m_impl.capacity();
    560     }
    561 
    562     template<typename T, size_t inlineCapacity, typename U>
    563     inline bool ListHashSet<T, inlineCapacity, U>::isEmpty() const
    564     {
    565         return m_impl.isEmpty();
    566     }
    567 
    568     template<typename T, size_t inlineCapacity, typename U>
    569     size_t ListHashSet<T, inlineCapacity, U>::sizeInBytes() const
    570     {
    571         size_t result = sizeof(*this);
    572         if (!m_allocator)
    573             return result;
    574         result += sizeof(*m_allocator) + (sizeof(typename ImplType::ValueType) * m_impl.capacity());
    575         for (Node* node = m_head; node; node = node->m_next) {
    576             if (!m_allocator->inPool(node))
    577                 result += sizeof(Node);
    578         }
    579         return result;
    580     }
    581 
    582     template<typename T, size_t inlineCapacity, typename U>
    583     inline typename ListHashSet<T, inlineCapacity, U>::iterator ListHashSet<T, inlineCapacity, U>::begin()
    584     {
    585         return makeIterator(m_head);
    586     }
    587 
    588     template<typename T, size_t inlineCapacity, typename U>
    589     inline typename ListHashSet<T, inlineCapacity, U>::iterator ListHashSet<T, inlineCapacity, U>::end()
    590     {
    591         return makeIterator(0);
    592     }
    593 
    594     template<typename T, size_t inlineCapacity, typename U>
    595     inline typename ListHashSet<T, inlineCapacity, U>::const_iterator ListHashSet<T, inlineCapacity, U>::begin() const
    596     {
    597         return makeConstIterator(m_head);
    598     }
    599 
    600     template<typename T, size_t inlineCapacity, typename U>
    601     inline typename ListHashSet<T, inlineCapacity, U>::const_iterator ListHashSet<T, inlineCapacity, U>::end() const
    602     {
    603         return makeConstIterator(0);
    604     }
    605 
    606     template<typename T, size_t inlineCapacity, typename U>
    607     inline typename ListHashSet<T, inlineCapacity, U>::reverse_iterator ListHashSet<T, inlineCapacity, U>::rbegin()
    608     {
    609         return makeReverseIterator(m_tail);
    610     }
    611 
    612     template<typename T, size_t inlineCapacity, typename U>
    613     inline typename ListHashSet<T, inlineCapacity, U>::reverse_iterator ListHashSet<T, inlineCapacity, U>::rend()
    614     {
    615         return makeReverseIterator(0);
    616     }
    617 
    618     template<typename T, size_t inlineCapacity, typename U>
    619     inline typename ListHashSet<T, inlineCapacity, U>::const_reverse_iterator ListHashSet<T, inlineCapacity, U>::rbegin() const
    620     {
    621         return makeConstReverseIterator(m_tail);
    622     }
    623 
    624     template<typename T, size_t inlineCapacity, typename U>
    625     inline typename ListHashSet<T, inlineCapacity, U>::const_reverse_iterator ListHashSet<T, inlineCapacity, U>::rend() const
    626     {
    627         return makeConstReverseIterator(0);
    628     }
    629 
    630     template<typename T, size_t inlineCapacity, typename U>
    631     inline T& ListHashSet<T, inlineCapacity, U>::first()
    632     {
    633         ASSERT(!isEmpty());
    634         return m_head->m_value;
    635     }
    636 
    637     template<typename T, size_t inlineCapacity, typename U>
    638     inline void ListHashSet<T, inlineCapacity, U>::removeFirst()
    639     {
    640         ASSERT(!isEmpty());
    641         m_impl.remove(m_head);
    642         unlinkAndDelete(m_head);
    643     }
    644 
    645     template<typename T, size_t inlineCapacity, typename U>
    646     inline const T& ListHashSet<T, inlineCapacity, U>::first() const
    647     {
    648         ASSERT(!isEmpty());
    649         return m_head->m_value;
    650     }
    651 
    652     template<typename T, size_t inlineCapacity, typename U>
    653     inline T& ListHashSet<T, inlineCapacity, U>::last()
    654     {
    655         ASSERT(!isEmpty());
    656         return m_tail->m_value;
    657     }
    658 
    659     template<typename T, size_t inlineCapacity, typename U>
    660     inline const T& ListHashSet<T, inlineCapacity, U>::last() const
    661     {
    662         ASSERT(!isEmpty());
    663         return m_tail->m_value;
    664     }
    665 
    666     template<typename T, size_t inlineCapacity, typename U>
    667     inline void ListHashSet<T, inlineCapacity, U>::removeLast()
    668     {
    669         ASSERT(!isEmpty());
    670         m_impl.remove(m_tail);
    671         unlinkAndDelete(m_tail);
    672     }
    673 
    674     template<typename T, size_t inlineCapacity, typename U>
    675     inline typename ListHashSet<T, inlineCapacity, U>::iterator ListHashSet<T, inlineCapacity, U>::find(const ValueType& value)
    676     {
    677         ImplTypeIterator it = m_impl.template find<BaseTranslator>(value);
    678         if (it == m_impl.end())
    679             return end();
    680         return makeIterator(*it);
    681     }
    682 
    683     template<typename T, size_t inlineCapacity, typename U>
    684     inline typename ListHashSet<T, inlineCapacity, U>::const_iterator ListHashSet<T, inlineCapacity, U>::find(const ValueType& value) const
    685     {
    686         ImplTypeConstIterator it = m_impl.template find<BaseTranslator>(value);
    687         if (it == m_impl.end())
    688             return end();
    689         return makeConstIterator(*it);
    690     }
    691 
    692     template<typename Translator>
    693     struct ListHashSetTranslatorAdapter {
    694         template<typename T> static unsigned hash(const T& key) { return Translator::hash(key); }
    695         template<typename T, typename U> static bool equal(const T& a, const U& b) { return Translator::equal(a->m_value, b); }
    696     };
    697 
    698     template<typename ValueType, size_t inlineCapacity, typename U>
    699     template<typename HashTranslator, typename T>
    700     inline typename ListHashSet<ValueType, inlineCapacity, U>::iterator ListHashSet<ValueType, inlineCapacity, U>::find(const T& value)
    701     {
    702         ImplTypeConstIterator it = m_impl.template find<ListHashSetTranslatorAdapter<HashTranslator> >(value);
    703         if (it == m_impl.end())
    704             return end();
    705         return makeIterator(*it);
    706     }
    707 
    708     template<typename ValueType, size_t inlineCapacity, typename U>
    709     template<typename HashTranslator, typename T>
    710     inline typename ListHashSet<ValueType, inlineCapacity, U>::const_iterator ListHashSet<ValueType, inlineCapacity, U>::find(const T& value) const
    711     {
    712         ImplTypeConstIterator it = m_impl.template find<ListHashSetTranslatorAdapter<HashTranslator> >(value);
    713         if (it == m_impl.end())
    714             return end();
    715         return makeConstIterator(*it);
    716     }
    717 
    718     template<typename ValueType, size_t inlineCapacity, typename U>
    719     template<typename HashTranslator, typename T>
    720     inline bool ListHashSet<ValueType, inlineCapacity, U>::contains(const T& value) const
    721     {
    722         return m_impl.template contains<ListHashSetTranslatorAdapter<HashTranslator> >(value);
    723     }
    724 
    725     template<typename T, size_t inlineCapacity, typename U>
    726     inline bool ListHashSet<T, inlineCapacity, U>::contains(const ValueType& value) const
    727     {
    728         return m_impl.template contains<BaseTranslator>(value);
    729     }
    730 
    731     template<typename T, size_t inlineCapacity, typename U>
    732     typename ListHashSet<T, inlineCapacity, U>::AddResult ListHashSet<T, inlineCapacity, U>::add(const ValueType &value)
    733     {
    734         createAllocatorIfNeeded();
    735         typename ImplType::AddResult result = m_impl.template add<BaseTranslator>(value, m_allocator.get());
    736         if (result.isNewEntry)
    737             appendNode(*result.iterator);
    738         return AddResult(makeIterator(*result.iterator), result.isNewEntry);
    739     }
    740 
    741     template<typename T, size_t inlineCapacity, typename U>
    742     typename ListHashSet<T, inlineCapacity, U>::AddResult ListHashSet<T, inlineCapacity, U>::appendOrMoveToLast(const ValueType &value)
    743     {
    744         createAllocatorIfNeeded();
    745         typename ImplType::AddResult result = m_impl.template add<BaseTranslator>(value, m_allocator.get());
    746         Node* node = *result.iterator;
    747         if (!result.isNewEntry)
    748             unlink(node);
    749         appendNode(node);
    750         return AddResult(makeIterator(*result.iterator), result.isNewEntry);
    751     }
    752 
    753     template<typename T, size_t inlineCapacity, typename U>
    754     typename ListHashSet<T, inlineCapacity, U>::AddResult ListHashSet<T, inlineCapacity, U>::prependOrMoveToFirst(const ValueType &value)
    755     {
    756         createAllocatorIfNeeded();
    757         typename ImplType::AddResult result = m_impl.template add<BaseTranslator>(value, m_allocator.get());
    758         Node* node = *result.iterator;
    759         if (!result.isNewEntry)
    760             unlink(node);
    761         prependNode(node);
    762         return AddResult(makeIterator(*result.iterator), result.isNewEntry);
    763     }
    764 
    765     template<typename T, size_t inlineCapacity, typename U>
    766     typename ListHashSet<T, inlineCapacity, U>::AddResult ListHashSet<T, inlineCapacity, U>::insertBefore(iterator it, const ValueType& newValue)
    767     {
    768         createAllocatorIfNeeded();
    769         typename ImplType::AddResult result = m_impl.template add<BaseTranslator>(newValue, m_allocator.get());
    770         if (result.isNewEntry)
    771             insertNodeBefore(it.node(), *result.iterator);
    772         return AddResult(makeIterator(*result.iterator), result.isNewEntry);
    773     }
    774 
    775     template<typename T, size_t inlineCapacity, typename U>
    776     typename ListHashSet<T, inlineCapacity, U>::AddResult ListHashSet<T, inlineCapacity, U>::insertBefore(const ValueType& beforeValue, const ValueType& newValue)
    777     {
    778         createAllocatorIfNeeded();
    779         return insertBefore(find(beforeValue), newValue);
    780     }
    781 
    782     template<typename T, size_t inlineCapacity, typename U>
    783     inline void ListHashSet<T, inlineCapacity, U>::remove(iterator it)
    784     {
    785         if (it == end())
    786             return;
    787         m_impl.remove(it.node());
    788         unlinkAndDelete(it.node());
    789     }
    790 
    791     template<typename T, size_t inlineCapacity, typename U>
    792     inline void ListHashSet<T, inlineCapacity, U>::remove(const ValueType& value)
    793     {
    794         remove(find(value));
    795     }
    796 
    797     template<typename T, size_t inlineCapacity, typename U>
    798     inline void ListHashSet<T, inlineCapacity, U>::clear()
    799     {
    800         deleteAllNodes();
    801         m_impl.clear();
    802         m_head = 0;
    803         m_tail = 0;
    804     }
    805 
    806     template<typename T, size_t inlineCapacity, typename U>
    807     void ListHashSet<T, inlineCapacity, U>::unlink(Node* node)
    808     {
    809         if (!node->m_prev) {
    810             ASSERT(node == m_head);
    811             m_head = node->m_next;
    812         } else {
    813             ASSERT(node != m_head);
    814             node->m_prev->m_next = node->m_next;
    815         }
    816 
    817         if (!node->m_next) {
    818             ASSERT(node == m_tail);
    819             m_tail = node->m_prev;
    820         } else {
    821             ASSERT(node != m_tail);
    822             node->m_next->m_prev = node->m_prev;
    823         }
    824     }
    825 
    826     template<typename T, size_t inlineCapacity, typename U>
    827     void ListHashSet<T, inlineCapacity, U>::unlinkAndDelete(Node* node)
    828     {
    829         unlink(node);
    830         node->destroy(m_allocator.get());
    831     }
    832 
    833     template<typename T, size_t inlineCapacity, typename U>
    834     void ListHashSet<T, inlineCapacity, U>::appendNode(Node* node)
    835     {
    836         node->m_prev = m_tail;
    837         node->m_next = 0;
    838 
    839         if (m_tail) {
    840             ASSERT(m_head);
    841             m_tail->m_next = node;
    842         } else {
    843             ASSERT(!m_head);
    844             m_head = node;
    845         }
    846 
    847         m_tail = node;
    848     }
    849 
    850     template<typename T, size_t inlineCapacity, typename U>
    851     void ListHashSet<T, inlineCapacity, U>::prependNode(Node* node)
    852     {
    853         node->m_prev = 0;
    854         node->m_next = m_head;
    855 
    856         if (m_head)
    857             m_head->m_prev = node;
    858         else
    859             m_tail = node;
    860 
    861         m_head = node;
    862     }
    863 
    864     template<typename T, size_t inlineCapacity, typename U>
    865     void ListHashSet<T, inlineCapacity, U>::insertNodeBefore(Node* beforeNode, Node* newNode)
    866     {
    867         if (!beforeNode)
    868             return appendNode(newNode);
    869 
    870         newNode->m_next = beforeNode;
    871         newNode->m_prev = beforeNode->m_prev;
    872         if (beforeNode->m_prev)
    873             beforeNode->m_prev->m_next = newNode;
    874         beforeNode->m_prev = newNode;
    875 
    876         if (!newNode->m_prev)
    877             m_head = newNode;
    878     }
    879 
    880     template<typename T, size_t inlineCapacity, typename U>
    881     void ListHashSet<T, inlineCapacity, U>::deleteAllNodes()
    882     {
    883         if (!m_head)
    884             return;
    885 
    886         for (Node* node = m_head, *next = m_head->m_next; node; node = next, next = node ? node->m_next : 0)
    887             node->destroy(m_allocator.get());
    888     }
    889 
    890     template<typename T, size_t inlineCapacity, typename U>
    891     void ListHashSet<T, inlineCapacity, U>::createAllocatorIfNeeded()
    892     {
    893         if (!m_allocator)
    894             m_allocator = adoptPtr(new NodeAllocator);
    895     }
    896 
    897     template<typename T, size_t inlineCapacity, typename U>
    898     inline ListHashSetReverseIterator<T, inlineCapacity, U> ListHashSet<T, inlineCapacity, U>::makeReverseIterator(Node* position)
    899     {
    900         return ListHashSetReverseIterator<T, inlineCapacity, U>(this, position);
    901     }
    902 
    903     template<typename T, size_t inlineCapacity, typename U>
    904     inline ListHashSetConstReverseIterator<T, inlineCapacity, U> ListHashSet<T, inlineCapacity, U>::makeConstReverseIterator(Node* position) const
    905     {
    906         return ListHashSetConstReverseIterator<T, inlineCapacity, U>(this, position);
    907     }
    908 
    909     template<typename T, size_t inlineCapacity, typename U>
    910     inline ListHashSetIterator<T, inlineCapacity, U> ListHashSet<T, inlineCapacity, U>::makeIterator(Node* position)
    911     {
    912         return ListHashSetIterator<T, inlineCapacity, U>(this, position);
    913     }
    914 
    915     template<typename T, size_t inlineCapacity, typename U>
    916     inline ListHashSetConstIterator<T, inlineCapacity, U> ListHashSet<T, inlineCapacity, U>::makeConstIterator(Node* position) const
    917     {
    918         return ListHashSetConstIterator<T, inlineCapacity, U>(this, position);
    919     }
    920     template<bool, typename ValueType, typename HashTableType>
    921     void deleteAllValues(HashTableType& collection)
    922     {
    923         typedef typename HashTableType::const_iterator iterator;
    924         iterator end = collection.end();
    925         for (iterator it = collection.begin(); it != end; ++it)
    926             delete (*it)->m_value;
    927     }
    928 
    929     template<typename T, size_t inlineCapacity, typename U>
    930     inline void deleteAllValues(const ListHashSet<T, inlineCapacity, U>& collection)
    931     {
    932         deleteAllValues<true, typename ListHashSet<T, inlineCapacity, U>::ValueType>(collection.m_impl);
    933     }
    934 
    935 } // namespace WTF
    936 
    937 using WTF::ListHashSet;
    938 
    939 #endif /* WTF_ListHashSet_h */
    940