← Back to branch summary

~ubuntu-branches/ubuntu/maverick/webkit/maverick

« back to all changes in this revision

Viewing changes to JavaScriptCore/wtf/ListHashSet.h

  • Committer: Bazaar Package Importer
  • Author(s): Mike Hommey
  • Date: 2007-08-19 15:54:12 UTC
  • Revision ID: james.westby@ubuntu.com-20070819155412-uxxg1h9plpghmtbi
Tags: upstream-0~svn25144
Import upstream version 0~svn25144

Show diffs side-by-side

added added

removed removed

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