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
30namespace 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
143        ListHashSetNodeAllocator()
144            : m_freeList(pool())
145            , m_isDoneWithInitialFreeList(false)
146        {
147            memset(m_pool.pool, 0, sizeof(m_pool.pool));
148        }
149
150        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
176        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:
191        Node* pool() { return reinterpret_cast_ptr<Node*>(m_pool.pool); }
192        Node* pastPool() { return pool() + m_poolSize; }
193
194        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
211        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
221        void* operator new(size_t, NodeAllocator* allocator)
222        {
223            return allocator->allocate();
224        }
225        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
243        static unsigned hash(Node* const& key) { return HashArg::hash(key->m_value); }
244        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
260        ListHashSetIterator(const ListHashSetType* set, Node* position) : m_iterator(set, position) { }
261
262    public:
263        ListHashSetIterator() { }
264
265        // default copy, assignment and destructor are OK
266
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
283        operator const_iterator() const { return m_iterator; }
284
285    private:
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
304        ListHashSetConstIterator(const ListHashSetType* set, Node* position)
305            : m_set(set)
306            , m_position(position)
307        {
308        }
309
310    public:
311        ListHashSetConstIterator()
312        {
313        }
314
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:
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:
367        static unsigned hash(const ValueType& key) { return HashFunctions::hash(key); }
368        static bool equal(Node* const& a, const ValueType& b) { return HashFunctions::equal(a->m_value, b); }
369        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>
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>
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>
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>
412    inline ListHashSet<T, inlineCapacity, U>::~ListHashSet()
413    {
414        deleteAllNodes();
415    }
416
417    template<typename T, size_t inlineCapacity, typename U>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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:
520        static unsigned hash(const T& key) { return Translator::hash(key); }
521        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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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
706using WTF::ListHashSet;
707
708#endif /* WTF_ListHashSet_h */
709