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