src/third_party/WebKit/Source/wtf/ListHashSet.h

   1 /*
   2  * Copyright (C) 2005, 2006, 2007, 2008, 2011, 2012 Apple Inc. All rights reserved.
   3  * Copyright (C) 2011, Benjamin Poulain <ikipou@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 #if ENABLE(ASSERT)
 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 #if ENABLE(ASSERT)
 232             , m_isAllocated(true)
 233 #endif
 234         {
 235         }
 236
 237     public:
 238         ValueArg m_value;
 239         ListHashSetNodeBase* m_prev;
 240         ListHashSetNodeBase* m_next;
 241 #if ENABLE(ASSERT)
 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 #if ENABLE(ASSERT)
 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_SANITIZER_INITIAL_SIZE)
 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 #if !ENABLE(OILPAN)
1007     template<typename T, size_t U, typename V>
1008     struct NeedsTracing<ListHashSet<T, U, V> > {
1009         static const bool value = false;
1010     };
1011 #endif
1012
1013 } // namespace WTF
1014
1015 using WTF::ListHashSet;
1016
1017 #endif /* WTF_ListHashSet_h */