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
29namespace 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
41template<typename Value, size_t inlineCapacity, typename HashFunctions> class ListHashSet;
42
43template<typename ValueArg, size_t inlineCapacity, typename HashArg> class ListHashSetIterator;
44template<typename ValueArg, size_t inlineCapacity, typename HashArg> class ListHashSetConstIterator;
45
46template<typename ValueArg, size_t inlineCapacity> struct ListHashSetNode;
47template<typename ValueArg, size_t inlineCapacity> class ListHashSetNodeAllocator;
48
49template<typename HashArg> struct ListHashSetNodeHashFunctions;
50template<typename HashArg> struct ListHashSetTranslator;
51
52template<typename ValueArg, size_t inlineCapacity = 256, typename HashArg = typename DefaultHash<ValueArg>::Hash> class ListHashSet {
53    WTF_MAKE_FAST_ALLOCATED;
54private:
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
64public:
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
144private:
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
161template<typename ValueArg, size_t inlineCapacity> class ListHashSetNodeAllocator {
162    WTF_MAKE_FAST_ALLOCATED;
163
164public:
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
215private:
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
232template<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
265template<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
271template<typename ValueArg, size_t inlineCapacity, typename HashArg> class ListHashSetIterator {
272private:
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
283public:
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
312private:
313    Node* node() { return m_iterator.node(); }
314
315    const_iterator m_iterator;
316};
317
318template<typename ValueArg, size_t inlineCapacity, typename HashArg> class ListHashSetConstIterator {
319private:
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
335public:
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
385private:
386    Node* node() { return m_position; }
387
388    const ListHashSetType* m_set;
389    Node* m_position;
390};
391
392template<typename HashFunctions>
393struct 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
402template<typename T, size_t inlineCapacity, typename U>
403inline ListHashSet<T, inlineCapacity, U>::ListHashSet()
404    : m_head(0)
405    , m_tail(0)
406    , m_allocator(std::make_unique<NodeAllocator>())
407{
408}
409
410template<typename T, size_t inlineCapacity, typename U>
411inline 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
420template<typename T, size_t inlineCapacity, typename U>
421inline 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
428template<typename T, size_t inlineCapacity, typename U>
429inline 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
437template<typename T, size_t inlineCapacity, typename U>
438inline ListHashSet<T, inlineCapacity, U>::~ListHashSet()
439{
440    deleteAllNodes();
441}
442
443template<typename T, size_t inlineCapacity, typename U>
444inline int ListHashSet<T, inlineCapacity, U>::size() const
445{
446    return m_impl.size();
447}
448
449template<typename T, size_t inlineCapacity, typename U>
450inline int ListHashSet<T, inlineCapacity, U>::capacity() const
451{
452    return m_impl.capacity();
453}
454
455template<typename T, size_t inlineCapacity, typename U>
456inline bool ListHashSet<T, inlineCapacity, U>::isEmpty() const
457{
458    return m_impl.isEmpty();
459}
460
461template<typename T, size_t inlineCapacity, typename U>
462inline T& ListHashSet<T, inlineCapacity, U>::first()
463{
464    ASSERT(!isEmpty());
465    return m_head->m_value;
466}
467
468template<typename T, size_t inlineCapacity, typename U>
469inline void ListHashSet<T, inlineCapacity, U>::removeFirst()
470{
471    takeFirst();
472}
473
474template<typename T, size_t inlineCapacity, typename U>
475inline 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
487template<typename T, size_t inlineCapacity, typename U>
488inline const T& ListHashSet<T, inlineCapacity, U>::first() const
489{
490    ASSERT(!isEmpty());
491    return m_head->m_value;
492}
493
494template<typename T, size_t inlineCapacity, typename U>
495inline T& ListHashSet<T, inlineCapacity, U>::last()
496{
497    ASSERT(!isEmpty());
498    return m_tail->m_value;
499}
500
501template<typename T, size_t inlineCapacity, typename U>
502inline const T& ListHashSet<T, inlineCapacity, U>::last() const
503{
504    ASSERT(!isEmpty());
505    return m_tail->m_value;
506}
507
508template<typename T, size_t inlineCapacity, typename U>
509inline void ListHashSet<T, inlineCapacity, U>::removeLast()
510{
511    takeLast();
512}
513
514template<typename T, size_t inlineCapacity, typename U>
515inline 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
527template<typename T, size_t inlineCapacity, typename U>
528inline 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
536template<typename T, size_t inlineCapacity, typename U>
537inline 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
545template<typename Translator>
546struct 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
551template<typename ValueType, size_t inlineCapacity, typename U>
552template<typename T, typename HashTranslator>
553inline 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
561template<typename ValueType, size_t inlineCapacity, typename U>
562template<typename T, typename HashTranslator>
563inline 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
571template<typename ValueType, size_t inlineCapacity, typename U>
572template<typename T, typename HashTranslator>
573inline bool ListHashSet<ValueType, inlineCapacity, U>::contains(const T& value) const
574{
575    return m_impl.template contains<ListHashSetTranslatorAdapter<HashTranslator>>(value);
576}
577
578template<typename T, size_t inlineCapacity, typename U>
579inline bool ListHashSet<T, inlineCapacity, U>::contains(const ValueType& value) const
580{
581    return m_impl.template contains<BaseTranslator>(value);
582}
583
584template<typename T, size_t inlineCapacity, typename U>
585auto 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
593template<typename T, size_t inlineCapacity, typename U>
594auto 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
602template<typename T, size_t inlineCapacity, typename U>
603auto 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
614template<typename T, size_t inlineCapacity, typename U>
615auto 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
626template<typename T, size_t inlineCapacity, typename U>
627auto 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
638template<typename T, size_t inlineCapacity, typename U>
639auto 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
650template<typename T, size_t inlineCapacity, typename U>
651auto ListHashSet<T, inlineCapacity, U>::insertBefore(const ValueType& beforeValue, const ValueType& newValue) -> AddResult
652{
653    return insertBefore(find(beforeValue), newValue);
654}
655
656template<typename T, size_t inlineCapacity, typename U>
657auto ListHashSet<T, inlineCapacity, U>::insertBefore(const ValueType& beforeValue, ValueType&& newValue) -> AddResult
658{
659    return insertBefore(find(beforeValue), WTF::move(newValue));
660}
661
662template<typename T, size_t inlineCapacity, typename U>
663auto 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
671template<typename T, size_t inlineCapacity, typename U>
672auto 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
680template<typename T, size_t inlineCapacity, typename U>
681inline 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
690template<typename T, size_t inlineCapacity, typename U>
691inline bool ListHashSet<T, inlineCapacity, U>::remove(const ValueType& value)
692{
693    return remove(find(value));
694}
695
696template<typename T, size_t inlineCapacity, typename U>
697inline void ListHashSet<T, inlineCapacity, U>::clear()
698{
699    deleteAllNodes();
700    m_impl.clear();
701    m_head = 0;
702    m_tail = 0;
703}
704
705template<typename T, size_t inlineCapacity, typename U>
706void 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
725template<typename T, size_t inlineCapacity, typename U>
726void ListHashSet<T, inlineCapacity, U>::unlinkAndDelete(Node* node)
727{
728    unlink(node);
729    node->destroy(m_allocator.get());
730}
731
732template<typename T, size_t inlineCapacity, typename U>
733void 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
749template<typename T, size_t inlineCapacity, typename U>
750void 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
763template<typename T, size_t inlineCapacity, typename U>
764void 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
779template<typename T, size_t inlineCapacity, typename U>
780void 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
789template<typename T, size_t inlineCapacity, typename U>
790inline auto ListHashSet<T, inlineCapacity, U>::makeIterator(Node* position) -> iterator
791{
792    return iterator(this, position);
793}
794
795template<typename T, size_t inlineCapacity, typename U>
796inline auto ListHashSet<T, inlineCapacity, U>::makeConstIterator(Node* position) const -> const_iterator
797{
798    return const_iterator(this, position);
799}
800
801} // namespace WTF
802
803using WTF::ListHashSet;
804
805#endif /* WTF_ListHashSet_h */
806