Source/WTF/wtf/ListHashSet.h

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