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