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