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