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