Add WTF::move()
[WebKit-https.git] / Source / WTF / wtf / ListHashSet.h
1 /*
2  * Copyright (C) 2005, 2006, 2007, 2008, 2011, 2012, 2013 Apple Inc. All rights reserved.
3  * Copyright (C) 2011, Benjamin Poulain <ikipou@gmail.com>
4  *
5  * This library is free software; you can redistribute it and/or
6  * modify it under the terms of the GNU Library General Public
7  * License as published by the Free Software Foundation; either
8  * version 2 of the License, or (at your option) any later version.
9  *
10  * This library is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13  * Library General Public License for more details.
14  *
15  * You should have received a copy of the GNU Library General Public License
16  * along with this library; see the file COPYING.LIB.  If not, write to
17  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
18  * Boston, MA 02110-1301, USA.
19  *
20  */
21
22 #ifndef WTF_ListHashSet_h
23 #define WTF_ListHashSet_h
24
25 #include <wtf/HashSet.h>
26 #include <wtf/OwnPtr.h>
27 #include <wtf/PassOwnPtr.h>
28
29 namespace WTF {
30
31 // ListHashSet: Just like HashSet, this class provides a Set
32 // interface - a collection of unique objects with O(1) insertion,
33 // removal and test for containership. However, it also has an
34 // order - iterating it will always give back values in the order
35 // in which they are added.
36
37 // Unlike iteration of most WTF Hash data structures, iteration is
38 // guaranteed safe against mutation of the ListHashSet, except for
39 // removal of the item currently pointed to by a given iterator.
40
41 template<typename Value, size_t inlineCapacity, typename HashFunctions> class ListHashSet;
42
43 template<typename ValueArg, size_t inlineCapacity, typename HashArg> class ListHashSetIterator;
44 template<typename ValueArg, size_t inlineCapacity, typename HashArg> class ListHashSetConstIterator;
45
46 template<typename ValueArg, size_t inlineCapacity> struct ListHashSetNode;
47 template<typename ValueArg, size_t inlineCapacity> class ListHashSetNodeAllocator;
48
49 template<typename HashArg> struct ListHashSetNodeHashFunctions;
50 template<typename HashArg> struct ListHashSetTranslator;
51
52 template<typename ValueArg, size_t inlineCapacity = 256, typename HashArg = typename DefaultHash<ValueArg>::Hash> class ListHashSet {
53     WTF_MAKE_FAST_ALLOCATED;
54 private:
55     typedef ListHashSetNode<ValueArg, inlineCapacity> Node;
56     typedef ListHashSetNodeAllocator<ValueArg, inlineCapacity> NodeAllocator;
57
58     typedef HashTraits<Node*> NodeTraits;
59     typedef ListHashSetNodeHashFunctions<HashArg> NodeHash;
60     typedef ListHashSetTranslator<HashArg> BaseTranslator;
61
62     typedef HashArg HashFunctions;
63
64 public:
65     typedef ValueArg ValueType;
66
67     typedef ListHashSetIterator<ValueType, inlineCapacity, HashArg> iterator;
68     typedef ListHashSetConstIterator<ValueType, inlineCapacity, HashArg> const_iterator;
69     friend class ListHashSetConstIterator<ValueType, inlineCapacity, HashArg>;
70
71     typedef std::reverse_iterator<iterator> reverse_iterator;
72     typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
73
74     typedef HashTableAddResult<iterator> AddResult;
75
76     ListHashSet();
77     ListHashSet(const ListHashSet&);
78     ListHashSet& operator=(const ListHashSet&);
79     ~ListHashSet();
80
81     void swap(ListHashSet&);
82
83     int size() const;
84     int capacity() const;
85     bool isEmpty() const;
86
87     iterator begin() { return makeIterator(m_head); }
88     iterator end() { return makeIterator(nullptr); }
89     const_iterator begin() const { return makeConstIterator(m_head); }
90     const_iterator end() const { return makeConstIterator(nullptr); }
91
92     reverse_iterator rbegin() { return reverse_iterator(end()); }
93     reverse_iterator rend() { return reverse_iterator(begin()); }
94     const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
95     const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }
96
97     ValueType& first();
98     const ValueType& first() const;
99     void removeFirst();
100     ValueType takeFirst();
101
102     ValueType& last();
103     const ValueType& last() const;
104     void removeLast();
105     ValueType takeLast();
106
107     iterator find(const ValueType&);
108     const_iterator find(const ValueType&) const;
109     bool contains(const ValueType&) const;
110
111     // An alternate version of find() that finds the object by hashing and comparing
112     // with some other type, to avoid the cost of type conversion.
113     // The HashTranslator interface is defined in HashSet.
114     // FIXME: We should reverse the order of the template arguments so that callers
115     // can just pass the translator let the compiler deduce T.
116     template<typename T, typename HashTranslator> iterator find(const T&);
117     template<typename T, typename HashTranslator> const_iterator find(const T&) const;
118     template<typename T, typename HashTranslator> bool contains(const T&) const;
119
120     // The return value of add is a pair of an iterator to the new value's location, 
121     // and a bool that is true if an new entry was added.
122     AddResult add(const ValueType&);
123     AddResult add(ValueType&&);
124
125     // Add the value to the end of the collection. If the value was already in
126     // the list, it is moved to the end.
127     AddResult appendOrMoveToLast(const ValueType&);
128     AddResult appendOrMoveToLast(ValueType&&);
129
130     // Add the value to the beginning of the collection. If the value was already in
131     // the list, it is moved to the beginning.
132     AddResult prependOrMoveToFirst(const ValueType&);
133     AddResult prependOrMoveToFirst(ValueType&&);
134
135     AddResult insertBefore(const ValueType& beforeValue, const ValueType& newValue);
136     AddResult insertBefore(const ValueType& beforeValue, ValueType&& newValue);
137     AddResult insertBefore(iterator, const ValueType&);
138     AddResult insertBefore(iterator, ValueType&&);
139
140     bool remove(const ValueType&);
141     bool remove(iterator);
142     void clear();
143
144 private:
145     void unlink(Node*);
146     void unlinkAndDelete(Node*);
147     void appendNode(Node*);
148     void prependNode(Node*);
149     void insertNodeBefore(Node* beforeNode, Node* newNode);
150     void deleteAllNodes();
151     
152     iterator makeIterator(Node*);
153     const_iterator makeConstIterator(Node*) const;
154
155     HashTable<Node*, Node*, IdentityExtractor, NodeHash, NodeTraits, NodeTraits> m_impl;
156     Node* m_head;
157     Node* m_tail;
158     std::unique_ptr<NodeAllocator> m_allocator;
159 };
160
161 template<typename ValueArg, size_t inlineCapacity> class ListHashSetNodeAllocator {
162     WTF_MAKE_FAST_ALLOCATED;
163
164 public:
165     typedef ListHashSetNode<ValueArg, inlineCapacity> Node;
166     typedef ListHashSetNodeAllocator<ValueArg, inlineCapacity> NodeAllocator;
167
168     ListHashSetNodeAllocator() 
169         : m_freeList(pool())
170         , m_isDoneWithInitialFreeList(false)
171     { 
172         memset(m_pool.pool, 0, sizeof(m_pool.pool));
173     }
174
175     Node* allocate()
176     { 
177         Node* result = m_freeList;
178
179         if (!result)
180             return static_cast<Node*>(fastMalloc(sizeof(Node)));
181
182         ASSERT(!result->m_isAllocated);
183
184         Node* next = result->m_next;
185         ASSERT(!next || !next->m_isAllocated);
186         if (!next && !m_isDoneWithInitialFreeList) {
187             next = result + 1;
188             if (next == pastPool()) {
189                 m_isDoneWithInitialFreeList = true;
190                 next = 0;
191             } else {
192                 ASSERT(inPool(next));
193                 ASSERT(!next->m_isAllocated);
194             }
195         }
196         m_freeList = next;
197
198         return result;
199     }
200
201     void deallocate(Node* node) 
202     {
203         if (inPool(node)) {
204 #ifndef NDEBUG
205             node->m_isAllocated = false;
206 #endif
207             node->m_next = m_freeList;
208             m_freeList = node;
209             return;
210         }
211
212         fastFree(node);
213     }
214
215 private:
216     Node* pool() { return reinterpret_cast_ptr<Node*>(m_pool.pool); }
217     Node* pastPool() { return pool() + m_poolSize; }
218     bool inPool(Node* node)
219     {
220         return node >= pool() && node < pastPool();
221     }
222
223     Node* m_freeList;
224     bool m_isDoneWithInitialFreeList;
225     static const size_t m_poolSize = inlineCapacity;
226     union {
227         char pool[sizeof(Node) * m_poolSize];
228         double forAlignment;
229     } m_pool;
230 };
231
232 template<typename ValueArg, size_t inlineCapacity> struct ListHashSetNode {
233     typedef ListHashSetNodeAllocator<ValueArg, inlineCapacity> NodeAllocator;
234
235     template<typename T>
236     ListHashSetNode(T&& value)
237         : m_value(std::forward<T>(value))
238         , m_prev(0)
239         , m_next(0)
240 #ifndef NDEBUG
241         , m_isAllocated(true)
242 #endif
243     {
244     }
245
246     void* operator new(size_t, NodeAllocator* allocator)
247     {
248         return allocator->allocate();
249     }
250     void destroy(NodeAllocator* allocator)
251     {
252         this->~ListHashSetNode();
253         allocator->deallocate(this);
254     }
255
256     ValueArg m_value;
257     ListHashSetNode* m_prev;
258     ListHashSetNode* m_next;
259
260 #ifndef NDEBUG
261     bool m_isAllocated;
262 #endif
263 };
264
265 template<typename HashArg> struct ListHashSetNodeHashFunctions {
266     template<typename T> static unsigned hash(const T& key) { return HashArg::hash(key->m_value); }
267     template<typename T> static bool equal(const T& a, const T& b) { return HashArg::equal(a->m_value, b->m_value); }
268     static const bool safeToCompareToEmptyOrDeleted = false;
269 };
270
271 template<typename ValueArg, size_t inlineCapacity, typename HashArg> class ListHashSetIterator {
272 private:
273     typedef ListHashSet<ValueArg, inlineCapacity, HashArg> ListHashSetType;
274     typedef ListHashSetIterator<ValueArg, inlineCapacity, HashArg> iterator;
275     typedef ListHashSetConstIterator<ValueArg, inlineCapacity, HashArg> const_iterator;
276     typedef ListHashSetNode<ValueArg, inlineCapacity> Node;
277     typedef ValueArg ValueType;
278
279     friend class ListHashSet<ValueArg, inlineCapacity, HashArg>;
280
281     ListHashSetIterator(const ListHashSetType* set, Node* position) : m_iterator(set, position) { }
282
283 public:
284     typedef ptrdiff_t difference_type;
285     typedef ValueType value_type;
286     typedef ValueType* pointer;
287     typedef ValueType& reference;
288     typedef std::bidirectional_iterator_tag iterator_category;
289
290     ListHashSetIterator() { }
291
292     // default copy, assignment and destructor are OK
293
294     ValueType* get() const { return const_cast<ValueType*>(m_iterator.get()); }
295     ValueType& operator*() const { return *get(); }
296     ValueType* operator->() const { return get(); }
297
298     iterator& operator++() { ++m_iterator; return *this; }
299
300     // postfix ++ intentionally omitted
301
302     iterator& operator--() { --m_iterator; return *this; }
303
304     // postfix -- intentionally omitted
305
306     // Comparison.
307     bool operator==(const iterator& other) const { return m_iterator == other.m_iterator; }
308     bool operator!=(const iterator& other) const { return m_iterator != other.m_iterator; }
309
310     operator const_iterator() const { return m_iterator; }
311
312 private:
313     Node* node() { return m_iterator.node(); }
314
315     const_iterator m_iterator;
316 };
317
318 template<typename ValueArg, size_t inlineCapacity, typename HashArg> class ListHashSetConstIterator {
319 private:
320     typedef ListHashSet<ValueArg, inlineCapacity, HashArg> ListHashSetType;
321     typedef ListHashSetIterator<ValueArg, inlineCapacity, HashArg> iterator;
322     typedef ListHashSetConstIterator<ValueArg, inlineCapacity, HashArg> const_iterator;
323     typedef ListHashSetNode<ValueArg, inlineCapacity> Node;
324     typedef ValueArg ValueType;
325
326     friend class ListHashSet<ValueArg, inlineCapacity, HashArg>;
327     friend class ListHashSetIterator<ValueArg, inlineCapacity, HashArg>;
328
329     ListHashSetConstIterator(const ListHashSetType* set, Node* position)
330         : m_set(set)
331         , m_position(position)
332     {
333     }
334
335 public:
336     typedef ptrdiff_t difference_type;
337     typedef const ValueType value_type;
338     typedef const ValueType* pointer;
339     typedef const ValueType& reference;
340     typedef std::bidirectional_iterator_tag iterator_category;
341
342     ListHashSetConstIterator()
343     {
344     }
345
346     const ValueType* get() const
347     {
348         return &m_position->m_value;
349     }
350
351     const ValueType& operator*() const { return *get(); }
352     const ValueType* operator->() const { return get(); }
353
354     const_iterator& operator++()
355     {
356         ASSERT(m_position != 0);
357         m_position = m_position->m_next;
358         return *this;
359     }
360
361     // postfix ++ intentionally omitted
362
363     const_iterator& operator--()
364     {
365         ASSERT(m_position != m_set->m_head);
366         if (!m_position)
367             m_position = m_set->m_tail;
368         else
369             m_position = m_position->m_prev;
370         return *this;
371     }
372
373     // postfix -- intentionally omitted
374
375     // Comparison.
376     bool operator==(const const_iterator& other) const
377     {
378         return m_position == other.m_position;
379     }
380     bool operator!=(const const_iterator& other) const
381     {
382         return m_position != other.m_position;
383     }
384
385 private:
386     Node* node() { return m_position; }
387
388     const ListHashSetType* m_set;
389     Node* m_position;
390 };
391
392 template<typename HashFunctions>
393 struct ListHashSetTranslator {
394     template<typename T> static unsigned hash(const T& key) { return HashFunctions::hash(key); }
395     template<typename T, typename U> static bool equal(const T& a, const U& b) { return HashFunctions::equal(a->m_value, b); }
396     template<typename T, typename U, typename V> static void translate(T*& location, U&& key, const V& allocator)
397     {
398         location = new (allocator) T(std::forward<U>(key));
399     }
400 };
401
402 template<typename T, size_t inlineCapacity, typename U>
403 inline ListHashSet<T, inlineCapacity, U>::ListHashSet()
404     : m_head(0)
405     , m_tail(0)
406     , m_allocator(std::make_unique<NodeAllocator>())
407 {
408 }
409
410 template<typename T, size_t inlineCapacity, typename U>
411 inline ListHashSet<T, inlineCapacity, U>::ListHashSet(const ListHashSet& other)
412     : m_head(0)
413     , m_tail(0)
414     , m_allocator(std::make_unique<NodeAllocator>())
415 {
416     for (auto it = other.begin(), end = other.end(); it != end; ++it)
417         add(*it);
418 }
419
420 template<typename T, size_t inlineCapacity, typename U>
421 inline ListHashSet<T, inlineCapacity, U>& ListHashSet<T, inlineCapacity, U>::operator=(const ListHashSet& other)
422 {
423     ListHashSet tmp(other);
424     swap(tmp);
425     return *this;
426 }
427
428 template<typename T, size_t inlineCapacity, typename U>
429 inline void ListHashSet<T, inlineCapacity, U>::swap(ListHashSet& other)
430 {
431     m_impl.swap(other.m_impl);
432     std::swap(m_head, other.m_head);
433     std::swap(m_tail, other.m_tail);
434     m_allocator.swap(other.m_allocator);
435 }
436
437 template<typename T, size_t inlineCapacity, typename U>
438 inline ListHashSet<T, inlineCapacity, U>::~ListHashSet()
439 {
440     deleteAllNodes();
441 }
442
443 template<typename T, size_t inlineCapacity, typename U>
444 inline int ListHashSet<T, inlineCapacity, U>::size() const
445 {
446     return m_impl.size(); 
447 }
448
449 template<typename T, size_t inlineCapacity, typename U>
450 inline int ListHashSet<T, inlineCapacity, U>::capacity() const
451 {
452     return m_impl.capacity(); 
453 }
454
455 template<typename T, size_t inlineCapacity, typename U>
456 inline bool ListHashSet<T, inlineCapacity, U>::isEmpty() const
457 {
458     return m_impl.isEmpty(); 
459 }
460
461 template<typename T, size_t inlineCapacity, typename U>
462 inline T& ListHashSet<T, inlineCapacity, U>::first()
463 {
464     ASSERT(!isEmpty());
465     return m_head->m_value;
466 }
467
468 template<typename T, size_t inlineCapacity, typename U>
469 inline void ListHashSet<T, inlineCapacity, U>::removeFirst()
470 {
471     takeFirst();
472 }
473
474 template<typename T, size_t inlineCapacity, typename U>
475 inline T ListHashSet<T, inlineCapacity, U>::takeFirst()
476 {
477     ASSERT(!isEmpty());
478     auto it = m_impl.find(m_head);
479
480     T result = WTF::move((*it)->m_value);
481     m_impl.remove(it);
482     unlinkAndDelete(m_head);
483
484     return result;
485 }
486
487 template<typename T, size_t inlineCapacity, typename U>
488 inline const T& ListHashSet<T, inlineCapacity, U>::first() const
489 {
490     ASSERT(!isEmpty());
491     return m_head->m_value;
492 }
493
494 template<typename T, size_t inlineCapacity, typename U>
495 inline T& ListHashSet<T, inlineCapacity, U>::last()
496 {
497     ASSERT(!isEmpty());
498     return m_tail->m_value;
499 }
500
501 template<typename T, size_t inlineCapacity, typename U>
502 inline const T& ListHashSet<T, inlineCapacity, U>::last() const
503 {
504     ASSERT(!isEmpty());
505     return m_tail->m_value;
506 }
507
508 template<typename T, size_t inlineCapacity, typename U>
509 inline void ListHashSet<T, inlineCapacity, U>::removeLast()
510 {
511     takeLast();
512 }
513
514 template<typename T, size_t inlineCapacity, typename U>
515 inline T ListHashSet<T, inlineCapacity, U>::takeLast()
516 {
517     ASSERT(!isEmpty());
518     auto it = m_impl.find(m_tail);
519
520     T result = WTF::move((*it)->m_value);
521     m_impl.remove(it);
522     unlinkAndDelete(m_tail);
523
524     return result;
525 }
526
527 template<typename T, size_t inlineCapacity, typename U>
528 inline auto ListHashSet<T, inlineCapacity, U>::find(const ValueType& value) -> iterator
529 {
530     auto it = m_impl.template find<BaseTranslator>(value);
531     if (it == m_impl.end())
532         return end();
533     return makeIterator(*it); 
534 }
535
536 template<typename T, size_t inlineCapacity, typename U>
537 inline auto ListHashSet<T, inlineCapacity, U>::find(const ValueType& value) const -> const_iterator
538 {
539     auto it = m_impl.template find<BaseTranslator>(value);
540     if (it == m_impl.end())
541         return end();
542     return makeConstIterator(*it);
543 }
544
545 template<typename Translator>
546 struct ListHashSetTranslatorAdapter {
547     template<typename T> static unsigned hash(const T& key) { return Translator::hash(key); }
548     template<typename T, typename U> static bool equal(const T& a, const U& b) { return Translator::equal(a->m_value, b); }
549 };
550
551 template<typename ValueType, size_t inlineCapacity, typename U>
552 template<typename T, typename HashTranslator>
553 inline auto ListHashSet<ValueType, inlineCapacity, U>::find(const T& value) -> iterator
554 {
555     auto it = m_impl.template find<ListHashSetTranslatorAdapter<HashTranslator>>(value);
556     if (it == m_impl.end())
557         return end();
558     return makeIterator(*it);
559 }
560
561 template<typename ValueType, size_t inlineCapacity, typename U>
562 template<typename T, typename HashTranslator>
563 inline auto ListHashSet<ValueType, inlineCapacity, U>::find(const T& value) const -> const_iterator
564 {
565     auto it = m_impl.template find<ListHashSetTranslatorAdapter<HashTranslator>>(value);
566     if (it == m_impl.end())
567         return end();
568     return makeConstIterator(*it);
569 }
570
571 template<typename ValueType, size_t inlineCapacity, typename U>
572 template<typename T, typename HashTranslator>
573 inline bool ListHashSet<ValueType, inlineCapacity, U>::contains(const T& value) const
574 {
575     return m_impl.template contains<ListHashSetTranslatorAdapter<HashTranslator>>(value);
576 }
577
578 template<typename T, size_t inlineCapacity, typename U>
579 inline bool ListHashSet<T, inlineCapacity, U>::contains(const ValueType& value) const
580 {
581     return m_impl.template contains<BaseTranslator>(value);
582 }
583
584 template<typename T, size_t inlineCapacity, typename U>
585 auto ListHashSet<T, inlineCapacity, U>::add(const ValueType& value) -> AddResult
586 {
587     auto result = m_impl.template add<BaseTranslator>(value, m_allocator.get());
588     if (result.isNewEntry)
589         appendNode(*result.iterator);
590     return AddResult(makeIterator(*result.iterator), result.isNewEntry);
591 }
592
593 template<typename T, size_t inlineCapacity, typename U>
594 auto ListHashSet<T, inlineCapacity, U>::add(ValueType&& value) -> AddResult
595 {
596     auto result = m_impl.template add<BaseTranslator>(WTF::move(value), m_allocator.get());
597     if (result.isNewEntry)
598         appendNode(*result.iterator);
599     return AddResult(makeIterator(*result.iterator), result.isNewEntry);
600 }
601
602 template<typename T, size_t inlineCapacity, typename U>
603 auto ListHashSet<T, inlineCapacity, U>::appendOrMoveToLast(const ValueType& value) -> AddResult
604 {
605     auto result = m_impl.template add<BaseTranslator>(value, m_allocator.get());
606     Node* node = *result.iterator;
607     if (!result.isNewEntry)
608         unlink(node);
609     appendNode(node);
610
611     return AddResult(makeIterator(*result.iterator), result.isNewEntry);
612 }
613
614 template<typename T, size_t inlineCapacity, typename U>
615 auto ListHashSet<T, inlineCapacity, U>::appendOrMoveToLast(ValueType&& value) -> AddResult
616 {
617     auto result = m_impl.template add<BaseTranslator>(WTF::move(value), m_allocator.get());
618     Node* node = *result.iterator;
619     if (!result.isNewEntry)
620         unlink(node);
621     appendNode(node);
622
623     return AddResult(makeIterator(*result.iterator), result.isNewEntry);
624 }
625
626 template<typename T, size_t inlineCapacity, typename U>
627 auto ListHashSet<T, inlineCapacity, U>::prependOrMoveToFirst(const ValueType& value) -> AddResult
628 {
629     auto result = m_impl.template add<BaseTranslator>(value, m_allocator.get());
630     Node* node = *result.iterator;
631     if (!result.isNewEntry)
632         unlink(node);
633     prependNode(node);
634
635     return AddResult(makeIterator(*result.iterator), result.isNewEntry);
636 }
637
638 template<typename T, size_t inlineCapacity, typename U>
639 auto ListHashSet<T, inlineCapacity, U>::prependOrMoveToFirst(ValueType&& value) -> AddResult
640 {
641     auto result = m_impl.template add<BaseTranslator>(WTF::move(value), m_allocator.get());
642     Node* node = *result.iterator;
643     if (!result.isNewEntry)
644         unlink(node);
645     prependNode(node);
646
647     return AddResult(makeIterator(*result.iterator), result.isNewEntry);
648 }
649
650 template<typename T, size_t inlineCapacity, typename U>
651 auto ListHashSet<T, inlineCapacity, U>::insertBefore(const ValueType& beforeValue, const ValueType& newValue) -> AddResult
652 {
653     return insertBefore(find(beforeValue), newValue);
654 }
655
656 template<typename T, size_t inlineCapacity, typename U>
657 auto ListHashSet<T, inlineCapacity, U>::insertBefore(const ValueType& beforeValue, ValueType&& newValue) -> AddResult
658 {
659     return insertBefore(find(beforeValue), WTF::move(newValue));
660 }
661
662 template<typename T, size_t inlineCapacity, typename U>
663 auto ListHashSet<T, inlineCapacity, U>::insertBefore(iterator it, const ValueType& newValue) -> AddResult
664 {
665     auto result = m_impl.template add<BaseTranslator>(newValue, m_allocator.get());
666     if (result.isNewEntry)
667         insertNodeBefore(it.node(), *result.iterator);
668     return AddResult(makeIterator(*result.iterator), result.isNewEntry);
669 }
670
671 template<typename T, size_t inlineCapacity, typename U>
672 auto ListHashSet<T, inlineCapacity, U>::insertBefore(iterator it, ValueType&& newValue) -> AddResult
673 {
674     auto result = m_impl.template add<BaseTranslator>(WTF::move(newValue), m_allocator.get());
675     if (result.isNewEntry)
676         insertNodeBefore(it.node(), *result.iterator);
677     return AddResult(makeIterator(*result.iterator), result.isNewEntry);
678 }
679
680 template<typename T, size_t inlineCapacity, typename U>
681 inline bool ListHashSet<T, inlineCapacity, U>::remove(iterator it)
682 {
683     if (it == end())
684         return false;
685     m_impl.remove(it.node());
686     unlinkAndDelete(it.node());
687     return true;
688 }
689
690 template<typename T, size_t inlineCapacity, typename U>
691 inline bool ListHashSet<T, inlineCapacity, U>::remove(const ValueType& value)
692 {
693     return remove(find(value));
694 }
695
696 template<typename T, size_t inlineCapacity, typename U>
697 inline void ListHashSet<T, inlineCapacity, U>::clear()
698 {
699     deleteAllNodes();
700     m_impl.clear(); 
701     m_head = 0;
702     m_tail = 0;
703 }
704
705 template<typename T, size_t inlineCapacity, typename U>
706 void ListHashSet<T, inlineCapacity, U>::unlink(Node* node)
707 {
708     if (!node->m_prev) {
709         ASSERT(node == m_head);
710         m_head = node->m_next;
711     } else {
712         ASSERT(node != m_head);
713         node->m_prev->m_next = node->m_next;
714     }
715
716     if (!node->m_next) {
717         ASSERT(node == m_tail);
718         m_tail = node->m_prev;
719     } else {
720         ASSERT(node != m_tail);
721         node->m_next->m_prev = node->m_prev;
722     }
723 }
724
725 template<typename T, size_t inlineCapacity, typename U>
726 void ListHashSet<T, inlineCapacity, U>::unlinkAndDelete(Node* node)
727 {
728     unlink(node);
729     node->destroy(m_allocator.get());
730 }
731
732 template<typename T, size_t inlineCapacity, typename U>
733 void ListHashSet<T, inlineCapacity, U>::appendNode(Node* node)
734 {
735     node->m_prev = m_tail;
736     node->m_next = 0;
737
738     if (m_tail) {
739         ASSERT(m_head);
740         m_tail->m_next = node;
741     } else {
742         ASSERT(!m_head);
743         m_head = node;
744     }
745
746     m_tail = node;
747 }
748
749 template<typename T, size_t inlineCapacity, typename U>
750 void ListHashSet<T, inlineCapacity, U>::prependNode(Node* node)
751 {
752     node->m_prev = 0;
753     node->m_next = m_head;
754
755     if (m_head)
756         m_head->m_prev = node;
757     else
758         m_tail = node;
759
760     m_head = node;
761 }
762
763 template<typename T, size_t inlineCapacity, typename U>
764 void ListHashSet<T, inlineCapacity, U>::insertNodeBefore(Node* beforeNode, Node* newNode)
765 {
766     if (!beforeNode)
767         return appendNode(newNode);
768     
769     newNode->m_next = beforeNode;
770     newNode->m_prev = beforeNode->m_prev;
771     if (beforeNode->m_prev)
772         beforeNode->m_prev->m_next = newNode;
773     beforeNode->m_prev = newNode;
774
775     if (!newNode->m_prev)
776         m_head = newNode;
777 }
778
779 template<typename T, size_t inlineCapacity, typename U>
780 void ListHashSet<T, inlineCapacity, U>::deleteAllNodes()
781 {
782     if (!m_head)
783         return;
784
785     for (Node* node = m_head, *next = m_head->m_next; node; node = next, next = node ? node->m_next : 0)
786         node->destroy(m_allocator.get());
787 }
788
789 template<typename T, size_t inlineCapacity, typename U>
790 inline auto ListHashSet<T, inlineCapacity, U>::makeIterator(Node* position) -> iterator
791 {
792     return iterator(this, position);
793 }
794
795 template<typename T, size_t inlineCapacity, typename U>
796 inline auto ListHashSet<T, inlineCapacity, U>::makeConstIterator(Node* position) const -> const_iterator
797
798     return const_iterator(this, position);
799 }
800
801 } // namespace WTF
802
803 using WTF::ListHashSet;
804
805 #endif /* WTF_ListHashSet_h */