wtf/ListHashSet.h

   1 /*
   2  * Copyright (C) 2005, 2006, 2007, 2008 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 "Assertions.h"
  26 #include "HashSet.h"
  27 #include "OwnPtr.h"
  28 #include "PassOwnPtr.h"
  29 #include "StdLibExtras.h"
  30
  31 namespace WTF {
  32
  33     // ListHashSet: Just like HashSet, this class provides a Set
  34     // interface - a collection of unique objects with O(1) insertion,
  35     // removal and test for containership. However, it also has an
  36     // order - iterating it will always give back values in the order
  37     // in which they are added.
  38
  39     // In theory it would be possible to add prepend, insertAfter
  40     // and an append that moves the element to the end even if already present,
  41     // but unclear yet if these are needed.
  42
  43     template<typename Value, size_t inlineCapacity, typename HashFunctions> class ListHashSet;
  44
  45     template<typename T> struct IdentityExtractor;
  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
  53     template<typename ValueArg, size_t inlineCapacity> struct ListHashSetNode;
  54     template<typename ValueArg, size_t inlineCapacity> struct ListHashSetNodeAllocator;
  55     template<typename ValueArg, size_t inlineCapacity, typename HashArg> struct ListHashSetNodeHashFunctions;
  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<ValueArg, inlineCapacity, HashArg> NodeHash;
  65
  66         typedef HashTable<Node*, Node*, IdentityExtractor<Node*>, NodeHash, NodeTraits, NodeTraits> ImplType;
  67         typedef HashTableIterator<Node*, Node*, IdentityExtractor<Node*>, NodeHash, NodeTraits, NodeTraits> ImplTypeIterator;
  68         typedef HashTableConstIterator<Node*, Node*, IdentityExtractor<Node*>, NodeHash, NodeTraits, NodeTraits> ImplTypeConstIterator;
  69
  70         typedef HashArg HashFunctions;
  71
  72     public:
  73         typedef ValueArg ValueType;
  74         typedef ListHashSetIterator<ValueType, inlineCapacity, HashArg> iterator;
  75         typedef ListHashSetConstIterator<ValueType, inlineCapacity, HashArg> const_iterator;
  76
  77         friend class ListHashSetConstIterator<ValueType, inlineCapacity, HashArg>;
  78
  79         ListHashSet();
  80         ListHashSet(const ListHashSet&);
  81         ListHashSet& operator=(const ListHashSet&);
  82         ~ListHashSet();
  83
  84         void swap(ListHashSet&);
  85
  86         int size() const;
  87         int capacity() const;
  88         bool isEmpty() const;
  89
  90         iterator begin();
  91         iterator end();
  92         const_iterator begin() const;
  93         const_iterator end() const;
  94
  95         ValueType& first();
  96         const ValueType& first() const;
  97
  98         ValueType& last();
  99         const ValueType& last() const;
 100         void removeLast();
 101
 102         iterator find(const ValueType&);
 103         const_iterator find(const ValueType&) const;
 104         bool contains(const ValueType&) const;
 105
 106         // An alternate version of find() that finds the object by hashing and comparing
 107         // with some other type, to avoid the cost of type conversion.
 108         // The HashTranslator interface is defined in HashSet.
 109         template<typename T, typename HashTranslator> iterator find(const T&);
 110         template<typename T, typename HashTranslator> const_iterator find(const T&) const;
 111         template<typename T, typename HashTranslator> bool contains(const T&) const;
 112
 113         // the return value is a pair of an iterator to the new value's location,
 114         // and a bool that is true if an new entry was added
 115         pair<iterator, bool> add(const ValueType&);
 116
 117         pair<iterator, bool> insertBefore(const ValueType& beforeValue, const ValueType& newValue);
 118         pair<iterator, bool> insertBefore(iterator it, const ValueType&);
 119
 120         void remove(const ValueType&);
 121         void remove(iterator);
 122         void clear();
 123
 124     private:
 125         void unlinkAndDelete(Node*);
 126         void appendNode(Node*);
 127         void insertNodeBefore(Node* beforeNode, Node* newNode);
 128         void deleteAllNodes();
 129         iterator makeIterator(Node*);
 130         const_iterator makeConstIterator(Node*) const;
 131
 132         friend void deleteAllValues<>(const ListHashSet&);
 133
 134         ImplType m_impl;
 135         Node* m_head;
 136         Node* m_tail;
 137         OwnPtr<NodeAllocator> m_allocator;
 138     };
 139
 140     template<typename ValueArg, size_t inlineCapacity> struct ListHashSetNodeAllocator {
 141         typedef ListHashSetNode<ValueArg, inlineCapacity> Node;
 142         typedef ListHashSetNodeAllocator<ValueArg, inlineCapacity> NodeAllocator;
 143
 144         ListHashSetNodeAllocator()
 145             : m_freeList(pool())
 146             , m_isDoneWithInitialFreeList(false)
 147         {
 148             memset(m_pool.pool, 0, sizeof(m_pool.pool));
 149         }
 150
 151         Node* allocate()
 152         {
 153             Node* result = m_freeList;
 154
 155             if (!result)
 156                 return static_cast<Node*>(fastMalloc(sizeof(Node)));
 157
 158             ASSERT(!result->m_isAllocated);
 159
 160             Node* next = result->m_next;
 161             ASSERT(!next || !next->m_isAllocated);
 162             if (!next && !m_isDoneWithInitialFreeList) {
 163                 next = result + 1;
 164                 if (next == pastPool()) {
 165                     m_isDoneWithInitialFreeList = true;
 166                     next = 0;
 167                 } else {
 168                     ASSERT(inPool(next));
 169                     ASSERT(!next->m_isAllocated);
 170                 }
 171             }
 172             m_freeList = next;
 173
 174             return result;
 175         }
 176
 177         void deallocate(Node* node)
 178         {
 179             if (inPool(node)) {
 180 #ifndef NDEBUG
 181                 node->m_isAllocated = false;
 182 #endif
 183                 node->m_next = m_freeList;
 184                 m_freeList = node;
 185                 return;
 186             }
 187
 188             fastFree(node);
 189         }
 190
 191     private:
 192         Node* pool() { return reinterpret_cast_ptr<Node*>(m_pool.pool); }
 193         Node* pastPool() { return pool() + m_poolSize; }
 194
 195         bool inPool(Node* node)
 196         {
 197             return node >= pool() && node < pastPool();
 198         }
 199
 200         Node* m_freeList;
 201         bool m_isDoneWithInitialFreeList;
 202         static const size_t m_poolSize = inlineCapacity;
 203         union {
 204             char pool[sizeof(Node) * m_poolSize];
 205             double forAlignment;
 206         } m_pool;
 207     };
 208
 209     template<typename ValueArg, size_t inlineCapacity> struct ListHashSetNode {
 210         typedef ListHashSetNodeAllocator<ValueArg, inlineCapacity> NodeAllocator;
 211
 212         ListHashSetNode(ValueArg value)
 213             : m_value(value)
 214             , m_prev(0)
 215             , m_next(0)
 216 #ifndef NDEBUG
 217             , m_isAllocated(true)
 218 #endif
 219         {
 220         }
 221
 222         void* operator new(size_t, NodeAllocator* allocator)
 223         {
 224             return allocator->allocate();
 225         }
 226         void destroy(NodeAllocator* allocator)
 227         {
 228             this->~ListHashSetNode();
 229             allocator->deallocate(this);
 230         }
 231
 232         ValueArg m_value;
 233         ListHashSetNode* m_prev;
 234         ListHashSetNode* m_next;
 235
 236 #ifndef NDEBUG
 237         bool m_isAllocated;
 238 #endif
 239     };
 240
 241     template<typename ValueArg, size_t inlineCapacity, typename HashArg> struct ListHashSetNodeHashFunctions {
 242         typedef ListHashSetNode<ValueArg, inlineCapacity> Node;
 243
 244         static unsigned hash(Node* const& key) { return HashArg::hash(key->m_value); }
 245         static bool equal(Node* const& a, Node* const& b) { return HashArg::equal(a->m_value, b->m_value); }
 246         static const bool safeToCompareToEmptyOrDeleted = false;
 247     };
 248
 249     template<typename ValueArg, size_t inlineCapacity, typename HashArg> class ListHashSetIterator {
 250     private:
 251         typedef ListHashSet<ValueArg, inlineCapacity, HashArg> ListHashSetType;
 252         typedef ListHashSetIterator<ValueArg, inlineCapacity, HashArg> iterator;
 253         typedef ListHashSetConstIterator<ValueArg, inlineCapacity, HashArg> const_iterator;
 254         typedef ListHashSetNode<ValueArg, inlineCapacity> Node;
 255         typedef ValueArg ValueType;
 256         typedef ValueType& ReferenceType;
 257         typedef ValueType* PointerType;
 258
 259         friend class ListHashSet<ValueArg, inlineCapacity, HashArg>;
 260
 261         ListHashSetIterator(const ListHashSetType* set, Node* position) : m_iterator(set, position) { }
 262
 263     public:
 264         ListHashSetIterator() { }
 265
 266         // default copy, assignment and destructor are OK
 267
 268         PointerType get() const { return const_cast<PointerType>(m_iterator.get()); }
 269         ReferenceType operator*() const { return *get(); }
 270         PointerType operator->() const { return get(); }
 271
 272         iterator& operator++() { ++m_iterator; return *this; }
 273
 274         // postfix ++ intentionally omitted
 275
 276         iterator& operator--() { --m_iterator; return *this; }
 277
 278         // postfix -- intentionally omitted
 279
 280         // Comparison.
 281         bool operator==(const iterator& other) const { return m_iterator == other.m_iterator; }
 282         bool operator!=(const iterator& other) const { return m_iterator != other.m_iterator; }
 283
 284         operator const_iterator() const { return m_iterator; }
 285
 286     private:
 287         Node* node() { return m_iterator.node(); }
 288
 289         const_iterator m_iterator;
 290     };
 291
 292     template<typename ValueArg, size_t inlineCapacity, typename HashArg> class ListHashSetConstIterator {
 293     private:
 294         typedef ListHashSet<ValueArg, inlineCapacity, HashArg> ListHashSetType;
 295         typedef ListHashSetIterator<ValueArg, inlineCapacity, HashArg> iterator;
 296         typedef ListHashSetConstIterator<ValueArg, inlineCapacity, HashArg> const_iterator;
 297         typedef ListHashSetNode<ValueArg, inlineCapacity> Node;
 298         typedef ValueArg ValueType;
 299         typedef const ValueType& ReferenceType;
 300         typedef const ValueType* PointerType;
 301
 302         friend class ListHashSet<ValueArg, inlineCapacity, HashArg>;
 303         friend class ListHashSetIterator<ValueArg, inlineCapacity, HashArg>;
 304
 305         ListHashSetConstIterator(const ListHashSetType* set, Node* position)
 306             : m_set(set)
 307             , m_position(position)
 308         {
 309         }
 310
 311     public:
 312         ListHashSetConstIterator()
 313         {
 314         }
 315
 316         PointerType get() const
 317         {
 318             return &m_position->m_value;
 319         }
 320         ReferenceType operator*() const { return *get(); }
 321         PointerType operator->() const { return get(); }
 322
 323         const_iterator& operator++()
 324         {
 325             ASSERT(m_position != 0);
 326             m_position = m_position->m_next;
 327             return *this;
 328         }
 329
 330         // postfix ++ intentionally omitted
 331
 332         const_iterator& operator--()
 333         {
 334             ASSERT(m_position != m_set->m_head);
 335             if (!m_position)
 336                 m_position = m_set->m_tail;
 337             else
 338                 m_position = m_position->m_prev;
 339             return *this;
 340         }
 341
 342         // postfix -- intentionally omitted
 343
 344         // Comparison.
 345         bool operator==(const const_iterator& other) const
 346         {
 347             return m_position == other.m_position;
 348         }
 349         bool operator!=(const const_iterator& other) const
 350         {
 351             return m_position != other.m_position;
 352         }
 353
 354     private:
 355         Node* node() { return m_position; }
 356
 357         const ListHashSetType* m_set;
 358         Node* m_position;
 359     };
 360
 361
 362     template<typename ValueType, size_t inlineCapacity, typename HashFunctions>
 363     struct ListHashSetTranslator {
 364     private:
 365         typedef ListHashSetNode<ValueType, inlineCapacity> Node;
 366         typedef ListHashSetNodeAllocator<ValueType, inlineCapacity> NodeAllocator;
 367     public:
 368         static unsigned hash(const ValueType& key) { return HashFunctions::hash(key); }
 369         static bool equal(Node* const& a, const ValueType& b) { return HashFunctions::equal(a->m_value, b); }
 370         static void translate(Node*& location, const ValueType& key, NodeAllocator* allocator)
 371         {
 372             location = new (allocator) Node(key);
 373         }
 374     };
 375
 376     template<typename T, size_t inlineCapacity, typename U>
 377     inline ListHashSet<T, inlineCapacity, U>::ListHashSet()
 378         : m_head(0)
 379         , m_tail(0)
 380         , m_allocator(adoptPtr(new NodeAllocator))
 381     {
 382     }
 383
 384     template<typename T, size_t inlineCapacity, typename U>
 385     inline ListHashSet<T, inlineCapacity, U>::ListHashSet(const ListHashSet& other)
 386         : m_head(0)
 387         , m_tail(0)
 388         , m_allocator(adoptPtr(new NodeAllocator))
 389     {
 390         const_iterator end = other.end();
 391         for (const_iterator it = other.begin(); it != end; ++it)
 392             add(*it);
 393     }
 394
 395     template<typename T, size_t inlineCapacity, typename U>
 396     inline ListHashSet<T, inlineCapacity, U>& ListHashSet<T, inlineCapacity, U>::operator=(const ListHashSet& other)
 397     {
 398         ListHashSet tmp(other);
 399         swap(tmp);
 400         return *this;
 401     }
 402
 403     template<typename T, size_t inlineCapacity, typename U>
 404     inline void ListHashSet<T, inlineCapacity, U>::swap(ListHashSet& other)
 405     {
 406         m_impl.swap(other.m_impl);
 407         std::swap(m_head, other.m_head);
 408         std::swap(m_tail, other.m_tail);
 409         m_allocator.swap(other.m_allocator);
 410     }
 411
 412     template<typename T, size_t inlineCapacity, typename U>
 413     inline ListHashSet<T, inlineCapacity, U>::~ListHashSet()
 414     {
 415         deleteAllNodes();
 416     }
 417
 418     template<typename T, size_t inlineCapacity, typename U>
 419     inline int ListHashSet<T, inlineCapacity, U>::size() const
 420     {
 421         return m_impl.size();
 422     }
 423
 424     template<typename T, size_t inlineCapacity, typename U>
 425     inline int ListHashSet<T, inlineCapacity, U>::capacity() const
 426     {
 427         return m_impl.capacity();
 428     }
 429
 430     template<typename T, size_t inlineCapacity, typename U>
 431     inline bool ListHashSet<T, inlineCapacity, U>::isEmpty() const
 432     {
 433         return m_impl.isEmpty();
 434     }
 435
 436     template<typename T, size_t inlineCapacity, typename U>
 437     inline typename ListHashSet<T, inlineCapacity, U>::iterator ListHashSet<T, inlineCapacity, U>::begin()
 438     {
 439         return makeIterator(m_head);
 440     }
 441
 442     template<typename T, size_t inlineCapacity, typename U>
 443     inline typename ListHashSet<T, inlineCapacity, U>::iterator ListHashSet<T, inlineCapacity, U>::end()
 444     {
 445         return makeIterator(0);
 446     }
 447
 448     template<typename T, size_t inlineCapacity, typename U>
 449     inline typename ListHashSet<T, inlineCapacity, U>::const_iterator ListHashSet<T, inlineCapacity, U>::begin() const
 450     {
 451         return makeConstIterator(m_head);
 452     }
 453
 454     template<typename T, size_t inlineCapacity, typename U>
 455     inline typename ListHashSet<T, inlineCapacity, U>::const_iterator ListHashSet<T, inlineCapacity, U>::end() const
 456     {
 457         return makeConstIterator(0);
 458     }
 459
 460     template<typename T, size_t inlineCapacity, typename U>
 461     inline T& ListHashSet<T, inlineCapacity, U>::first()
 462     {
 463         ASSERT(!isEmpty());
 464         return m_head->m_value;
 465     }
 466
 467     template<typename T, size_t inlineCapacity, typename U>
 468     inline const T& ListHashSet<T, inlineCapacity, U>::first() const
 469     {
 470         ASSERT(!isEmpty());
 471         return m_head->m_value;
 472     }
 473
 474     template<typename T, size_t inlineCapacity, typename U>
 475     inline T& ListHashSet<T, inlineCapacity, U>::last()
 476     {
 477         ASSERT(!isEmpty());
 478         return m_tail->m_value;
 479     }
 480
 481     template<typename T, size_t inlineCapacity, typename U>
 482     inline const T& ListHashSet<T, inlineCapacity, U>::last() const
 483     {
 484         ASSERT(!isEmpty());
 485         return m_tail->m_value;
 486     }
 487
 488     template<typename T, size_t inlineCapacity, typename U>
 489     inline void ListHashSet<T, inlineCapacity, U>::removeLast()
 490     {
 491         ASSERT(!isEmpty());
 492         m_impl.remove(m_tail);
 493         unlinkAndDelete(m_tail);
 494     }
 495
 496     template<typename T, size_t inlineCapacity, typename U>
 497     inline typename ListHashSet<T, inlineCapacity, U>::iterator ListHashSet<T, inlineCapacity, U>::find(const ValueType& value)
 498     {
 499         typedef ListHashSetTranslator<ValueType, inlineCapacity, HashFunctions> Translator;
 500         ImplTypeIterator it = m_impl.template find<ValueType, Translator>(value);
 501         if (it == m_impl.end())
 502             return end();
 503         return makeIterator(*it);
 504     }
 505
 506     template<typename T, size_t inlineCapacity, typename U>
 507     inline typename ListHashSet<T, inlineCapacity, U>::const_iterator ListHashSet<T, inlineCapacity, U>::find(const ValueType& value) const
 508     {
 509         typedef ListHashSetTranslator<ValueType, inlineCapacity, HashFunctions> Translator;
 510         ImplTypeConstIterator it = m_impl.template find<ValueType, Translator>(value);
 511         if (it == m_impl.end())
 512             return end();
 513         return makeConstIterator(*it);
 514     }
 515
 516     template<typename ValueType, size_t inlineCapacity, typename T, typename Translator>
 517     struct ListHashSetTranslatorAdapter {
 518     private:
 519         typedef ListHashSetNode<ValueType, inlineCapacity> Node;
 520     public:
 521         static unsigned hash(const T& key) { return Translator::hash(key); }
 522         static bool equal(Node* const& a, const T& b) { return Translator::equal(a->m_value, b); }
 523     };
 524
 525     template<typename ValueType, size_t inlineCapacity, typename U>
 526     template<typename T, typename HashTranslator>
 527     inline typename ListHashSet<ValueType, inlineCapacity, U>::iterator ListHashSet<ValueType, inlineCapacity, U>::find(const T& value)
 528     {
 529         typedef ListHashSetTranslatorAdapter<ValueType, inlineCapacity, T, HashTranslator> Adapter;
 530         ImplTypeConstIterator it = m_impl.template find<T, Adapter>(value);
 531         if (it == m_impl.end())
 532             return end();
 533         return makeIterator(*it);
 534     }
 535
 536     template<typename ValueType, size_t inlineCapacity, typename U>
 537     template<typename T, typename HashTranslator>
 538     inline typename ListHashSet<ValueType, inlineCapacity, U>::const_iterator ListHashSet<ValueType, inlineCapacity, U>::find(const T& value) const
 539     {
 540         typedef ListHashSetTranslatorAdapter<ValueType, inlineCapacity, T, HashTranslator> Adapter;
 541         ImplTypeConstIterator it = m_impl.template find<T, Adapter>(value);
 542         if (it == m_impl.end())
 543             return end();
 544         return makeConstIterator(*it);
 545     }
 546
 547     template<typename ValueType, size_t inlineCapacity, typename U>
 548     template<typename T, typename HashTranslator>
 549     inline bool ListHashSet<ValueType, inlineCapacity, U>::contains(const T& value) const
 550     {
 551         typedef ListHashSetTranslatorAdapter<ValueType, inlineCapacity, T, HashTranslator> Adapter;
 552         return m_impl.template contains<T, Adapter>(value);
 553     }
 554
 555     template<typename T, size_t inlineCapacity, typename U>
 556     inline bool ListHashSet<T, inlineCapacity, U>::contains(const ValueType& value) const
 557     {
 558         typedef ListHashSetTranslator<ValueType, inlineCapacity, HashFunctions> Translator;
 559         return m_impl.template contains<ValueType, Translator>(value);
 560     }
 561
 562     template<typename T, size_t inlineCapacity, typename U>
 563     pair<typename ListHashSet<T, inlineCapacity, U>::iterator, bool> ListHashSet<T, inlineCapacity, U>::add(const ValueType &value)
 564     {
 565         typedef ListHashSetTranslator<ValueType, inlineCapacity, HashFunctions> Translator;
 566         pair<typename ImplType::iterator, bool> result = m_impl.template add<ValueType, NodeAllocator*, Translator>(value, m_allocator.get());
 567         if (result.second)
 568             appendNode(*result.first);
 569         return std::make_pair(makeIterator(*result.first), result.second);
 570     }
 571
 572     template<typename T, size_t inlineCapacity, typename U>
 573     pair<typename ListHashSet<T, inlineCapacity, U>::iterator, bool> ListHashSet<T, inlineCapacity, U>::insertBefore(iterator it, const ValueType& newValue)
 574     {
 575         typedef ListHashSetTranslator<ValueType, inlineCapacity, HashFunctions> Translator;
 576         pair<typename ImplType::iterator, bool> result = m_impl.template add<ValueType, NodeAllocator*, Translator>(newValue, m_allocator.get());
 577         if (result.second)
 578             insertNodeBefore(it.node(), *result.first);
 579         return std::make_pair(makeIterator(*result.first), result.second);
 580
 581     }
 582
 583     template<typename T, size_t inlineCapacity, typename U>
 584     pair<typename ListHashSet<T, inlineCapacity, U>::iterator, bool> ListHashSet<T, inlineCapacity, U>::insertBefore(const ValueType& beforeValue, const ValueType& newValue)
 585     {
 586         return insertBefore(find(beforeValue), newValue);
 587     }
 588
 589     template<typename T, size_t inlineCapacity, typename U>
 590     inline void ListHashSet<T, inlineCapacity, U>::remove(iterator it)
 591     {
 592         if (it == end())
 593             return;
 594         m_impl.remove(it.node());
 595         unlinkAndDelete(it.node());
 596     }
 597
 598     template<typename T, size_t inlineCapacity, typename U>
 599     inline void ListHashSet<T, inlineCapacity, U>::remove(const ValueType& value)
 600     {
 601         remove(find(value));
 602     }
 603
 604     template<typename T, size_t inlineCapacity, typename U>
 605     inline void ListHashSet<T, inlineCapacity, U>::clear()
 606     {
 607         deleteAllNodes();
 608         m_impl.clear();
 609         m_head = 0;
 610         m_tail = 0;
 611     }
 612
 613     template<typename T, size_t inlineCapacity, typename U>
 614     void ListHashSet<T, inlineCapacity, U>::unlinkAndDelete(Node* node)
 615     {
 616         if (!node->m_prev) {
 617             ASSERT(node == m_head);
 618             m_head = node->m_next;
 619         } else {
 620             ASSERT(node != m_head);
 621             node->m_prev->m_next = node->m_next;
 622         }
 623
 624         if (!node->m_next) {
 625             ASSERT(node == m_tail);
 626             m_tail = node->m_prev;
 627         } else {
 628             ASSERT(node != m_tail);
 629             node->m_next->m_prev = node->m_prev;
 630         }
 631
 632         node->destroy(m_allocator.get());
 633     }
 634
 635     template<typename T, size_t inlineCapacity, typename U>
 636     void ListHashSet<T, inlineCapacity, U>::appendNode(Node* node)
 637     {
 638         node->m_prev = m_tail;
 639         node->m_next = 0;
 640
 641         if (m_tail) {
 642             ASSERT(m_head);
 643             m_tail->m_next = node;
 644         } else {
 645             ASSERT(!m_head);
 646             m_head = node;
 647         }
 648
 649         m_tail = node;
 650     }
 651
 652     template<typename T, size_t inlineCapacity, typename U>
 653     void ListHashSet<T, inlineCapacity, U>::insertNodeBefore(Node* beforeNode, Node* newNode)
 654     {
 655         if (!beforeNode)
 656             return appendNode(newNode);
 657
 658         newNode->m_next = beforeNode;
 659         newNode->m_prev = beforeNode->m_prev;
 660         if (beforeNode->m_prev)
 661             beforeNode->m_prev->m_next = newNode;
 662         beforeNode->m_prev = newNode;
 663
 664         if (!newNode->m_prev)
 665             m_head = newNode;
 666     }
 667
 668     template<typename T, size_t inlineCapacity, typename U>
 669     void ListHashSet<T, inlineCapacity, U>::deleteAllNodes()
 670     {
 671         if (!m_head)
 672             return;
 673
 674         for (Node* node = m_head, *next = m_head->m_next; node; node = next, next = node ? node->m_next : 0)
 675             node->destroy(m_allocator.get());
 676     }
 677
 678     template<typename T, size_t inlineCapacity, typename U>
 679     inline ListHashSetIterator<T, inlineCapacity, U> ListHashSet<T, inlineCapacity, U>::makeIterator(Node* position)
 680     {
 681         return ListHashSetIterator<T, inlineCapacity, U>(this, position);
 682     }
 683
 684     template<typename T, size_t inlineCapacity, typename U>
 685     inline ListHashSetConstIterator<T, inlineCapacity, U> ListHashSet<T, inlineCapacity, U>::makeConstIterator(Node* position) const
 686     {
 687         return ListHashSetConstIterator<T, inlineCapacity, U>(this, position);
 688     }
 689
 690     template<bool, typename ValueType, typename HashTableType>
 691     void deleteAllValues(HashTableType& collection)
 692     {
 693         typedef typename HashTableType::const_iterator iterator;
 694         iterator end = collection.end();
 695         for (iterator it = collection.begin(); it != end; ++it)
 696             delete (*it)->m_value;
 697     }
 698
 699     template<typename T, size_t inlineCapacity, typename U>
 700     inline void deleteAllValues(const ListHashSet<T, inlineCapacity, U>& collection)
 701     {
 702         deleteAllValues<true, typename ListHashSet<T, inlineCapacity, U>::ValueType>(collection.m_impl);
 703     }
 704
 705 } // namespace WTF
 706
 707 using WTF::ListHashSet;
 708
 709 #endif /* WTF_ListHashSet_h */