ListHashSet.h revision ab9e7a118cf1ea2e3a93dce683b2ded3e7291ddb 
1/*
2 * Copyright (C) 2005, 2006, 2007, 2008 Apple Inc. All rights reserved.
3 *
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Library General Public
6 * License as published by the Free Software Foundation; either
7 * version 2 of the License, or (at your option) any later version.
8 *
9 * This library is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12 * Library General Public License for more details.
13 *
14 * You should have received a copy of the GNU Library General Public License
15 * along with this library; see the file COPYING.LIB.  If not, write to
16 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
17 * Boston, MA 02110-1301, USA.
18 *
19 */
20
21#ifndef WTF_ListHashSet_h
22#define WTF_ListHashSet_h
23
24#include "Assertions.h"
25#include "HashSet.h"
26#include "OwnPtr.h"
27#include "StdLibExtras.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    // In theory it would be possible to add prepend, insertAfter
38    // and an append that moves the element to the end even if already present,
39    // but unclear yet if these are needed.
40
41    template<typename Value, size_t inlineCapacity, typename HashFunctions> class ListHashSet;
42
43    template<typename T> struct IdentityExtractor;
44
45    template<typename Value, size_t inlineCapacity, typename HashFunctions>
46    void deleteAllValues(const ListHashSet<Value, inlineCapacity, HashFunctions>&);
47
48    template<typename ValueArg, size_t inlineCapacity, typename HashArg> class ListHashSetIterator;
49    template<typename ValueArg, size_t inlineCapacity, typename HashArg> class ListHashSetConstIterator;
50
51    template<typename ValueArg, size_t inlineCapacity> struct ListHashSetNode;
52    template<typename ValueArg, size_t inlineCapacity> struct ListHashSetNodeAllocator;
53    template<typename ValueArg, size_t inlineCapacity, typename HashArg> struct ListHashSetNodeHashFunctions;
54
55    template<typename ValueArg, size_t inlineCapacity = 256, typename HashArg = typename DefaultHash<ValueArg>::Hash> class ListHashSet {
56        WTF_MAKE_FAST_ALLOCATED;
57    private:
58        typedef ListHashSetNode<ValueArg, inlineCapacity> Node;
59        typedef ListHashSetNodeAllocator<ValueArg, inlineCapacity> NodeAllocator;
60
61        typedef HashTraits<Node*> NodeTraits;
62        typedef ListHashSetNodeHashFunctions<ValueArg, inlineCapacity, HashArg> NodeHash;
63
64        typedef HashTable<Node*, Node*, IdentityExtractor<Node*>, NodeHash, NodeTraits, NodeTraits> ImplType;
65        typedef HashTableIterator<Node*, Node*, IdentityExtractor<Node*>, NodeHash, NodeTraits, NodeTraits> ImplTypeIterator;
66        typedef HashTableConstIterator<Node*, Node*, IdentityExtractor<Node*>, NodeHash, NodeTraits, NodeTraits> ImplTypeConstIterator;
67
68        typedef HashArg HashFunctions;
69
70    public:
71        typedef ValueArg ValueType;
72        typedef ListHashSetIterator<ValueType, inlineCapacity, HashArg> iterator;
73        typedef ListHashSetConstIterator<ValueType, inlineCapacity, HashArg> const_iterator;
74
75        friend class ListHashSetConstIterator<ValueType, inlineCapacity, HashArg>;
76
77        ListHashSet();
78        ListHashSet(const ListHashSet&);
79        ListHashSet& operator=(const ListHashSet&);
80        ~ListHashSet();
81
82        void swap(ListHashSet&);
83
84        int size() const;
85        int capacity() const;
86        bool isEmpty() const;
87
88        iterator begin();
89        iterator end();
90        const_iterator begin() const;
91        const_iterator end() const;
92
93        iterator find(const ValueType&);
94        const_iterator find(const ValueType&) const;
95        bool contains(const ValueType&) const;
96
97        // the return value is a pair of an iterator to the new value's location,
98        // and a bool that is true if an new entry was added
99        pair<iterator, bool> add(const ValueType&);
100
101        pair<iterator, bool> insertBefore(const ValueType& beforeValue, const ValueType& newValue);
102        pair<iterator, bool> insertBefore(iterator it, const ValueType&);
103
104        void remove(const ValueType&);
105        void remove(iterator);
106        void clear();
107
108    private:
109        void unlinkAndDelete(Node*);
110        void appendNode(Node*);
111        void insertNodeBefore(Node* beforeNode, Node* newNode);
112        void deleteAllNodes();
113        iterator makeIterator(Node*);
114        const_iterator makeConstIterator(Node*) const;
115
116        friend void deleteAllValues<>(const ListHashSet&);
117
118        ImplType m_impl;
119        Node* m_head;
120        Node* m_tail;
121        OwnPtr<NodeAllocator> m_allocator;
122    };
123
124    template<typename ValueArg, size_t inlineCapacity> struct ListHashSetNodeAllocator {
125        typedef ListHashSetNode<ValueArg, inlineCapacity> Node;
126        typedef ListHashSetNodeAllocator<ValueArg, inlineCapacity> NodeAllocator;
127
128        ListHashSetNodeAllocator()
129            : m_freeList(pool())
130            , m_isDoneWithInitialFreeList(false)
131        {
132            memset(m_pool.pool, 0, sizeof(m_pool.pool));
133        }
134
135        Node* allocate()
136        {
137            Node* result = m_freeList;
138
139            if (!result)
140                return static_cast<Node*>(fastMalloc(sizeof(Node)));
141
142            ASSERT(!result->m_isAllocated);
143
144            Node* next = result->m_next;
145            ASSERT(!next || !next->m_isAllocated);
146            if (!next && !m_isDoneWithInitialFreeList) {
147                next = result + 1;
148                if (next == pastPool()) {
149                    m_isDoneWithInitialFreeList = true;
150                    next = 0;
151                } else {
152                    ASSERT(inPool(next));
153                    ASSERT(!next->m_isAllocated);
154                }
155            }
156            m_freeList = next;
157
158            return result;
159        }
160
161        void deallocate(Node* node)
162        {
163            if (inPool(node)) {
164#ifndef NDEBUG
165                node->m_isAllocated = false;
166#endif
167                node->m_next = m_freeList;
168                m_freeList = node;
169                return;
170            }
171
172            fastFree(node);
173        }
174
175    private:
176        Node* pool() { return reinterpret_cast_ptr<Node*>(m_pool.pool); }
177        Node* pastPool() { return pool() + m_poolSize; }
178
179        bool inPool(Node* node)
180        {
181            return node >= pool() && node < pastPool();
182        }
183
184        Node* m_freeList;
185        bool m_isDoneWithInitialFreeList;
186        static const size_t m_poolSize = inlineCapacity;
187        union {
188            char pool[sizeof(Node) * m_poolSize];
189            double forAlignment;
190        } m_pool;
191    };
192
193    template<typename ValueArg, size_t inlineCapacity> struct ListHashSetNode {
194        typedef ListHashSetNodeAllocator<ValueArg, inlineCapacity> NodeAllocator;
195
196        ListHashSetNode(ValueArg value)
197            : m_value(value)
198            , m_prev(0)
199            , m_next(0)
200#ifndef NDEBUG
201            , m_isAllocated(true)
202#endif
203        {
204        }
205
206        void* operator new(size_t, NodeAllocator* allocator)
207        {
208            return allocator->allocate();
209        }
210        void destroy(NodeAllocator* allocator)
211        {
212            this->~ListHashSetNode();
213            allocator->deallocate(this);
214        }
215
216        ValueArg m_value;
217        ListHashSetNode* m_prev;
218        ListHashSetNode* m_next;
219
220#ifndef NDEBUG
221        bool m_isAllocated;
222#endif
223    };
224
225    template<typename ValueArg, size_t inlineCapacity, typename HashArg> struct ListHashSetNodeHashFunctions {
226        typedef ListHashSetNode<ValueArg, inlineCapacity> Node;
227
228        static unsigned hash(Node* const& key) { return HashArg::hash(key->m_value); }
229        static bool equal(Node* const& a, Node* const& b) { return HashArg::equal(a->m_value, b->m_value); }
230        static const bool safeToCompareToEmptyOrDeleted = false;
231    };
232
233    template<typename ValueArg, size_t inlineCapacity, typename HashArg> class ListHashSetIterator {
234    private:
235        typedef ListHashSet<ValueArg, inlineCapacity, HashArg> ListHashSetType;
236        typedef ListHashSetIterator<ValueArg, inlineCapacity, HashArg> iterator;
237        typedef ListHashSetConstIterator<ValueArg, inlineCapacity, HashArg> const_iterator;
238        typedef ListHashSetNode<ValueArg, inlineCapacity> Node;
239        typedef ValueArg ValueType;
240        typedef ValueType& ReferenceType;
241        typedef ValueType* PointerType;
242
243        friend class ListHashSet<ValueArg, inlineCapacity, HashArg>;
244
245        ListHashSetIterator(const ListHashSetType* set, Node* position) : m_iterator(set, position) { }
246
247    public:
248        ListHashSetIterator() { }
249
250        // default copy, assignment and destructor are OK
251
252        PointerType get() const { return const_cast<PointerType>(m_iterator.get()); }
253        ReferenceType operator*() const { return *get(); }
254        PointerType operator->() const { return get(); }
255
256        iterator& operator++() { ++m_iterator; return *this; }
257
258        // postfix ++ intentionally omitted
259
260        iterator& operator--() { --m_iterator; return *this; }
261
262        // postfix -- intentionally omitted
263
264        // Comparison.
265        bool operator==(const iterator& other) const { return m_iterator == other.m_iterator; }
266        bool operator!=(const iterator& other) const { return m_iterator != other.m_iterator; }
267
268        operator const_iterator() const { return m_iterator; }
269
270    private:
271        Node* node() { return m_iterator.node(); }
272
273        const_iterator m_iterator;
274    };
275
276    template<typename ValueArg, size_t inlineCapacity, typename HashArg> class ListHashSetConstIterator {
277    private:
278        typedef ListHashSet<ValueArg, inlineCapacity, HashArg> ListHashSetType;
279        typedef ListHashSetIterator<ValueArg, inlineCapacity, HashArg> iterator;
280        typedef ListHashSetConstIterator<ValueArg, inlineCapacity, HashArg> const_iterator;
281        typedef ListHashSetNode<ValueArg, inlineCapacity> Node;
282        typedef ValueArg ValueType;
283        typedef const ValueType& ReferenceType;
284        typedef const ValueType* PointerType;
285
286        friend class ListHashSet<ValueArg, inlineCapacity, HashArg>;
287        friend class ListHashSetIterator<ValueArg, inlineCapacity, HashArg>;
288
289        ListHashSetConstIterator(const ListHashSetType* set, Node* position)
290            : m_set(set)
291            , m_position(position)
292        {
293        }
294
295    public:
296        ListHashSetConstIterator()
297        {
298        }
299
300        PointerType get() const
301        {
302            return &m_position->m_value;
303        }
304        ReferenceType operator*() const { return *get(); }
305        PointerType operator->() const { return get(); }
306
307        const_iterator& operator++()
308        {
309            ASSERT(m_position != 0);
310            m_position = m_position->m_next;
311            return *this;
312        }
313
314        // postfix ++ intentionally omitted
315
316        const_iterator& operator--()
317        {
318            ASSERT(m_position != m_set->m_head);
319            if (!m_position)
320                m_position = m_set->m_tail;
321            else
322                m_position = m_position->m_prev;
323            return *this;
324        }
325
326        // postfix -- intentionally omitted
327
328        // Comparison.
329        bool operator==(const const_iterator& other) const
330        {
331            return m_position == other.m_position;
332        }
333        bool operator!=(const const_iterator& other) const
334        {
335            return m_position != other.m_position;
336        }
337
338    private:
339        Node* node() { return m_position; }
340
341        const ListHashSetType* m_set;
342        Node* m_position;
343    };
344
345
346    template<typename ValueType, size_t inlineCapacity, typename HashFunctions>
347    struct ListHashSetTranslator {
348    private:
349        typedef ListHashSetNode<ValueType, inlineCapacity> Node;
350        typedef ListHashSetNodeAllocator<ValueType, inlineCapacity> NodeAllocator;
351    public:
352        static unsigned hash(const ValueType& key) { return HashFunctions::hash(key); }
353        static bool equal(Node* const& a, const ValueType& b) { return HashFunctions::equal(a->m_value, b); }
354        static void translate(Node*& location, const ValueType& key, NodeAllocator* allocator)
355        {
356            location = new (allocator) Node(key);
357        }
358    };
359
360    template<typename T, size_t inlineCapacity, typename U>
361    inline ListHashSet<T, inlineCapacity, U>::ListHashSet()
362        : m_head(0)
363        , m_tail(0)
364        , m_allocator(new NodeAllocator)
365    {
366    }
367
368    template<typename T, size_t inlineCapacity, typename U>
369    inline ListHashSet<T, inlineCapacity, U>::ListHashSet(const ListHashSet& other)
370        : m_head(0)
371        , m_tail(0)
372        , m_allocator(new NodeAllocator)
373    {
374        const_iterator end = other.end();
375        for (const_iterator it = other.begin(); it != end; ++it)
376            add(*it);
377    }
378
379    template<typename T, size_t inlineCapacity, typename U>
380    inline ListHashSet<T, inlineCapacity, U>& ListHashSet<T, inlineCapacity, U>::operator=(const ListHashSet& other)
381    {
382        ListHashSet tmp(other);
383        swap(tmp);
384        return *this;
385    }
386
387    template<typename T, size_t inlineCapacity, typename U>
388    inline void ListHashSet<T, inlineCapacity, U>::swap(ListHashSet& other)
389    {
390        m_impl.swap(other.m_impl);
391        std::swap(m_head, other.m_head);
392        std::swap(m_tail, other.m_tail);
393        m_allocator.swap(other.m_allocator);
394    }
395
396    template<typename T, size_t inlineCapacity, typename U>
397    inline ListHashSet<T, inlineCapacity, U>::~ListHashSet()
398    {
399        deleteAllNodes();
400    }
401
402    template<typename T, size_t inlineCapacity, typename U>
403    inline int ListHashSet<T, inlineCapacity, U>::size() const
404    {
405        return m_impl.size();
406    }
407
408    template<typename T, size_t inlineCapacity, typename U>
409    inline int ListHashSet<T, inlineCapacity, U>::capacity() const
410    {
411        return m_impl.capacity();
412    }
413
414    template<typename T, size_t inlineCapacity, typename U>
415    inline bool ListHashSet<T, inlineCapacity, U>::isEmpty() const
416    {
417        return m_impl.isEmpty();
418    }
419
420    template<typename T, size_t inlineCapacity, typename U>
421    inline typename ListHashSet<T, inlineCapacity, U>::iterator ListHashSet<T, inlineCapacity, U>::begin()
422    {
423        return makeIterator(m_head);
424    }
425
426    template<typename T, size_t inlineCapacity, typename U>
427    inline typename ListHashSet<T, inlineCapacity, U>::iterator ListHashSet<T, inlineCapacity, U>::end()
428    {
429        return makeIterator(0);
430    }
431
432    template<typename T, size_t inlineCapacity, typename U>
433    inline typename ListHashSet<T, inlineCapacity, U>::const_iterator ListHashSet<T, inlineCapacity, U>::begin() const
434    {
435        return makeConstIterator(m_head);
436    }
437
438    template<typename T, size_t inlineCapacity, typename U>
439    inline typename ListHashSet<T, inlineCapacity, U>::const_iterator ListHashSet<T, inlineCapacity, U>::end() const
440    {
441        return makeConstIterator(0);
442    }
443
444    template<typename T, size_t inlineCapacity, typename U>
445    inline typename ListHashSet<T, inlineCapacity, U>::iterator ListHashSet<T, inlineCapacity, U>::find(const ValueType& value)
446    {
447        typedef ListHashSetTranslator<ValueType, inlineCapacity, HashFunctions> Translator;
448        ImplTypeIterator it = m_impl.template find<ValueType, Translator>(value);
449        if (it == m_impl.end())
450            return end();
451        return makeIterator(*it);
452    }
453
454    template<typename T, size_t inlineCapacity, typename U>
455    inline typename ListHashSet<T, inlineCapacity, U>::const_iterator ListHashSet<T, inlineCapacity, U>::find(const ValueType& value) const
456    {
457        typedef ListHashSetTranslator<ValueType, inlineCapacity, HashFunctions> Translator;
458        ImplTypeConstIterator it = m_impl.template find<ValueType, Translator>(value);
459        if (it == m_impl.end())
460            return end();
461        return makeConstIterator(*it);
462    }
463
464    template<typename T, size_t inlineCapacity, typename U>
465    inline bool ListHashSet<T, inlineCapacity, U>::contains(const ValueType& value) const
466    {
467        typedef ListHashSetTranslator<ValueType, inlineCapacity, HashFunctions> Translator;
468        return m_impl.template contains<ValueType, Translator>(value);
469    }
470
471    template<typename T, size_t inlineCapacity, typename U>
472    pair<typename ListHashSet<T, inlineCapacity, U>::iterator, bool> ListHashSet<T, inlineCapacity, U>::add(const ValueType &value)
473    {
474        typedef ListHashSetTranslator<ValueType, inlineCapacity, HashFunctions> Translator;
475        pair<typename ImplType::iterator, bool> result = m_impl.template add<ValueType, NodeAllocator*, Translator>(value, m_allocator.get());
476        if (result.second)
477            appendNode(*result.first);
478        return std::make_pair(makeIterator(*result.first), result.second);
479    }
480
481    template<typename T, size_t inlineCapacity, typename U>
482    pair<typename ListHashSet<T, inlineCapacity, U>::iterator, bool> ListHashSet<T, inlineCapacity, U>::insertBefore(iterator it, const ValueType& newValue)
483    {
484        typedef ListHashSetTranslator<ValueType, inlineCapacity, HashFunctions> Translator;
485        pair<typename ImplType::iterator, bool> result = m_impl.template add<ValueType, NodeAllocator*, Translator>(newValue, m_allocator.get());
486        if (result.second)
487            insertNodeBefore(it.node(), *result.first);
488        return std::make_pair(makeIterator(*result.first), result.second);
489
490    }
491
492    template<typename T, size_t inlineCapacity, typename U>
493    pair<typename ListHashSet<T, inlineCapacity, U>::iterator, bool> ListHashSet<T, inlineCapacity, U>::insertBefore(const ValueType& beforeValue, const ValueType& newValue)
494    {
495        return insertBefore(find(beforeValue), newValue);
496    }
497
498    template<typename T, size_t inlineCapacity, typename U>
499    inline void ListHashSet<T, inlineCapacity, U>::remove(iterator it)
500    {
501        if (it == end())
502            return;
503        m_impl.remove(it.node());
504        unlinkAndDelete(it.node());
505    }
506
507    template<typename T, size_t inlineCapacity, typename U>
508    inline void ListHashSet<T, inlineCapacity, U>::remove(const ValueType& value)
509    {
510        remove(find(value));
511    }
512
513    template<typename T, size_t inlineCapacity, typename U>
514    inline void ListHashSet<T, inlineCapacity, U>::clear()
515    {
516        deleteAllNodes();
517        m_impl.clear();
518        m_head = 0;
519        m_tail = 0;
520    }
521
522    template<typename T, size_t inlineCapacity, typename U>
523    void ListHashSet<T, inlineCapacity, U>::unlinkAndDelete(Node* node)
524    {
525        if (!node->m_prev) {
526            ASSERT(node == m_head);
527            m_head = node->m_next;
528        } else {
529            ASSERT(node != m_head);
530            node->m_prev->m_next = node->m_next;
531        }
532
533        if (!node->m_next) {
534            ASSERT(node == m_tail);
535            m_tail = node->m_prev;
536        } else {
537            ASSERT(node != m_tail);
538            node->m_next->m_prev = node->m_prev;
539        }
540
541        node->destroy(m_allocator.get());
542    }
543
544    template<typename T, size_t inlineCapacity, typename U>
545    void ListHashSet<T, inlineCapacity, U>::appendNode(Node* node)
546    {
547        node->m_prev = m_tail;
548        node->m_next = 0;
549
550        if (m_tail) {
551            ASSERT(m_head);
552            m_tail->m_next = node;
553        } else {
554            ASSERT(!m_head);
555            m_head = node;
556        }
557
558        m_tail = node;
559    }
560
561    template<typename T, size_t inlineCapacity, typename U>
562    void ListHashSet<T, inlineCapacity, U>::insertNodeBefore(Node* beforeNode, Node* newNode)
563    {
564        if (!beforeNode)
565            return appendNode(newNode);
566
567        newNode->m_next = beforeNode;
568        newNode->m_prev = beforeNode->m_prev;
569        if (beforeNode->m_prev)
570            beforeNode->m_prev->m_next = newNode;
571        beforeNode->m_prev = newNode;
572
573        if (!newNode->m_prev)
574            m_head = newNode;
575    }
576
577    template<typename T, size_t inlineCapacity, typename U>
578    void ListHashSet<T, inlineCapacity, U>::deleteAllNodes()
579    {
580        if (!m_head)
581            return;
582
583        for (Node* node = m_head, *next = m_head->m_next; node; node = next, next = node ? node->m_next : 0)
584            node->destroy(m_allocator.get());
585    }
586
587    template<typename T, size_t inlineCapacity, typename U>
588    inline ListHashSetIterator<T, inlineCapacity, U> ListHashSet<T, inlineCapacity, U>::makeIterator(Node* position)
589    {
590        return ListHashSetIterator<T, inlineCapacity, U>(this, position);
591    }
592
593    template<typename T, size_t inlineCapacity, typename U>
594    inline ListHashSetConstIterator<T, inlineCapacity, U> ListHashSet<T, inlineCapacity, U>::makeConstIterator(Node* position) const
595    {
596        return ListHashSetConstIterator<T, inlineCapacity, U>(this, position);
597    }
598
599    template<bool, typename ValueType, typename HashTableType>
600    void deleteAllValues(HashTableType& collection)
601    {
602        typedef typename HashTableType::const_iterator iterator;
603        iterator end = collection.end();
604        for (iterator it = collection.begin(); it != end; ++it)
605            delete (*it)->m_value;
606    }
607
608    template<typename T, size_t inlineCapacity, typename U>
609    inline void deleteAllValues(const ListHashSet<T, inlineCapacity, U>& collection)
610    {
611        deleteAllValues<true, typename ListHashSet<T, inlineCapacity, U>::ValueType>(collection.m_impl);
612    }
613
614} // namespace WTF
615
616using WTF::ListHashSet;
617
618#endif /* WTF_ListHashSet_h */
619