OLD | NEW |
1 /* | 1 /* |
2 * Copyright (C) 2005, 2006, 2007, 2008, 2011, 2012 Apple Inc. All rights reserv
ed. | 2 * Copyright (C) 2005, 2006, 2007, 2008, 2011, 2012 Apple Inc. All rights reserv
ed. |
3 * Copyright (C) 2011, Benjamin Poulain <ikipou@gmail.com> | 3 * Copyright (C) 2011, Benjamin Poulain <ikipou@gmail.com> |
4 * | 4 * |
5 * This library is free software; you can redistribute it and/or | 5 * This library is free software; you can redistribute it and/or |
6 * modify it under the terms of the GNU Library General Public | 6 * modify it under the terms of the GNU Library General Public |
7 * License as published by the Free Software Foundation; either | 7 * License as published by the Free Software Foundation; either |
8 * version 2 of the License, or (at your option) any later version. | 8 * version 2 of the License, or (at your option) any later version. |
9 * | 9 * |
10 * This library is distributed in the hope that it will be useful, | 10 * This library is distributed in the hope that it will be useful, |
(...skipping 38 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
49 template<typename Set> class ListHashSetReverseIterator; | 49 template<typename Set> class ListHashSetReverseIterator; |
50 template<typename Set> class ListHashSetConstReverseIterator; | 50 template<typename Set> class ListHashSetConstReverseIterator; |
51 | 51 |
52 template<typename ValueArg> class ListHashSetNodeBase; | 52 template<typename ValueArg> class ListHashSetNodeBase; |
53 template<typename ValueArg, typename Allocator> class ListHashSetNode; | 53 template<typename ValueArg, typename Allocator> class ListHashSetNode; |
54 template<typename ValueArg, size_t inlineCapacity> struct ListHashSetAllocat
or; | 54 template<typename ValueArg, size_t inlineCapacity> struct ListHashSetAllocat
or; |
55 | 55 |
56 template<typename HashArg> struct ListHashSetNodeHashFunctions; | 56 template<typename HashArg> struct ListHashSetNodeHashFunctions; |
57 template<typename HashArg> struct ListHashSetTranslator; | 57 template<typename HashArg> struct ListHashSetTranslator; |
58 | 58 |
| 59 // Don't declare a destructor for HeapAllocated ListHashSet. |
| 60 template<typename Derived, typename Allocator, bool isGarbageCollected> |
| 61 class ListHashSetDestructorBase; |
| 62 |
| 63 template<typename Derived, typename Allocator> |
| 64 class ListHashSetDestructorBase<Derived, Allocator, true> { |
| 65 protected: |
| 66 typename Allocator::AllocatorProvider m_allocatorProvider; |
| 67 }; |
| 68 |
| 69 template<typename Derived, typename Allocator> |
| 70 class ListHashSetDestructorBase<Derived, Allocator, false> { |
| 71 public: |
| 72 ~ListHashSetDestructorBase() { static_cast<Derived*>(this)->finalize();
} |
| 73 protected: |
| 74 typename Allocator::AllocatorProvider m_allocatorProvider; |
| 75 }; |
| 76 |
59 // Note that for a ListHashSet you cannot specify the HashTraits as a | 77 // Note that for a ListHashSet you cannot specify the HashTraits as a |
60 // template argument. It uses the default hash traits for the ValueArg | 78 // template argument. It uses the default hash traits for the ValueArg |
61 // type. | 79 // type. |
62 template<typename ValueArg, size_t inlineCapacity = 256, typename HashArg =
typename DefaultHash<ValueArg>::Hash, typename AllocatorArg = ListHashSetAllocat
or<ValueArg, inlineCapacity> > class ListHashSet { | 80 template<typename ValueArg, size_t inlineCapacity = 256, typename HashArg =
typename DefaultHash<ValueArg>::Hash, typename AllocatorArg = ListHashSetAllocat
or<ValueArg, inlineCapacity> > class ListHashSet |
| 81 : public ListHashSetDestructorBase<ListHashSet<ValueArg, inlineCapacity,
HashArg, AllocatorArg>, AllocatorArg, AllocatorArg::isGarbageCollected> { |
63 typedef AllocatorArg Allocator; | 82 typedef AllocatorArg Allocator; |
64 WTF_USE_ALLOCATOR(ListHashSet, Allocator); | 83 WTF_USE_ALLOCATOR(ListHashSet, Allocator); |
65 | 84 |
66 typedef ListHashSetNode<ValueArg, Allocator> Node; | 85 typedef ListHashSetNode<ValueArg, Allocator> Node; |
67 typedef HashTraits<Node*> NodeTraits; | 86 typedef HashTraits<Node*> NodeTraits; |
68 typedef ListHashSetNodeHashFunctions<HashArg> NodeHash; | 87 typedef ListHashSetNodeHashFunctions<HashArg> NodeHash; |
69 typedef ListHashSetTranslator<HashArg> BaseTranslator; | 88 typedef ListHashSetTranslator<HashArg> BaseTranslator; |
70 | 89 |
71 typedef HashTable<Node*, Node*, IdentityExtractor, NodeHash, NodeTraits,
NodeTraits, typename Allocator::TableAllocator> ImplType; | 90 typedef HashTable<Node*, Node*, IdentityExtractor, NodeHash, NodeTraits,
NodeTraits, typename Allocator::TableAllocator> ImplType; |
72 typedef HashTableIterator<Node*, Node*, IdentityExtractor, NodeHash, Nod
eTraits, NodeTraits, typename Allocator::TableAllocator> ImplTypeIterator; | 91 typedef HashTableIterator<Node*, Node*, IdentityExtractor, NodeHash, Nod
eTraits, NodeTraits, typename Allocator::TableAllocator> ImplTypeIterator; |
(...skipping 18 matching lines...) Expand all Loading... |
91 template<typename ValueType> struct HashTableAddResult { | 110 template<typename ValueType> struct HashTableAddResult { |
92 HashTableAddResult(Node* storedValue, bool isNewEntry) : storedValue(sto
redValue), isNewEntry(isNewEntry) { } | 111 HashTableAddResult(Node* storedValue, bool isNewEntry) : storedValue(sto
redValue), isNewEntry(isNewEntry) { } |
93 Node* storedValue; | 112 Node* storedValue; |
94 bool isNewEntry; | 113 bool isNewEntry; |
95 }; | 114 }; |
96 typedef HashTableAddResult<ValueType> AddResult; | 115 typedef HashTableAddResult<ValueType> AddResult; |
97 | 116 |
98 ListHashSet(); | 117 ListHashSet(); |
99 ListHashSet(const ListHashSet&); | 118 ListHashSet(const ListHashSet&); |
100 ListHashSet& operator=(const ListHashSet&); | 119 ListHashSet& operator=(const ListHashSet&); |
101 ~ListHashSet(); | 120 void finalize(); |
102 | 121 |
103 void swap(ListHashSet&); | 122 void swap(ListHashSet&); |
104 | 123 |
105 unsigned size() const { return m_impl.size(); } | 124 unsigned size() const { return m_impl.size(); } |
106 unsigned capacity() const { return m_impl.capacity(); } | 125 unsigned capacity() const { return m_impl.capacity(); } |
107 bool isEmpty() const { return m_impl.isEmpty(); } | 126 bool isEmpty() const { return m_impl.isEmpty(); } |
108 | 127 |
109 iterator begin() { return makeIterator(m_head); } | 128 iterator begin() { return makeIterator(m_head); } |
110 iterator end() { return makeIterator(0); } | 129 iterator end() { return makeIterator(0); } |
111 const_iterator begin() const { return makeConstIterator(m_head); } | 130 const_iterator begin() const { return makeConstIterator(m_head); } |
(...skipping 52 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
164 | 183 |
165 void trace(typename Allocator::Visitor*); | 184 void trace(typename Allocator::Visitor*); |
166 | 185 |
167 private: | 186 private: |
168 void unlink(Node*); | 187 void unlink(Node*); |
169 void unlinkAndDelete(Node*); | 188 void unlinkAndDelete(Node*); |
170 void appendNode(Node*); | 189 void appendNode(Node*); |
171 void prependNode(Node*); | 190 void prependNode(Node*); |
172 void insertNodeBefore(Node* beforeNode, Node* newNode); | 191 void insertNodeBefore(Node* beforeNode, Node* newNode); |
173 void deleteAllNodes(); | 192 void deleteAllNodes(); |
174 Allocator* allocator() const { return m_allocatorProvider.get(); } | 193 Allocator* allocator() const { return this->m_allocatorProvider.get(); } |
175 void createAllocatorIfNeeded() { m_allocatorProvider.createAllocatorIfNe
eded(); } | 194 void createAllocatorIfNeeded() { this->m_allocatorProvider.createAllocat
orIfNeeded(); } |
176 void deallocate(Node* node) const { m_allocatorProvider.deallocate(node)
; } | 195 void deallocate(Node* node) const { this->m_allocatorProvider.deallocate
(node); } |
177 | 196 |
178 iterator makeIterator(Node* position) { return iterator(this, position);
} | 197 iterator makeIterator(Node* position) { return iterator(this, position);
} |
179 const_iterator makeConstIterator(Node* position) const { return const_it
erator(this, position); } | 198 const_iterator makeConstIterator(Node* position) const { return const_it
erator(this, position); } |
180 reverse_iterator makeReverseIterator(Node* position) { return reverse_it
erator(this, position); } | 199 reverse_iterator makeReverseIterator(Node* position) { return reverse_it
erator(this, position); } |
181 const_reverse_iterator makeConstReverseIterator(Node* position) const {
return const_reverse_iterator(this, position); } | 200 const_reverse_iterator makeConstReverseIterator(Node* position) const {
return const_reverse_iterator(this, position); } |
182 | 201 |
183 friend void deleteAllValues<>(const ListHashSet&); | 202 friend void deleteAllValues<>(const ListHashSet&); |
184 | 203 |
185 ImplType m_impl; | 204 ImplType m_impl; |
186 Node* m_head; | 205 Node* m_head; |
187 Node* m_tail; | 206 Node* m_tail; |
188 typename Allocator::AllocatorProvider m_allocatorProvider; | |
189 }; | 207 }; |
190 | 208 |
191 // ListHashSetNode has this base class to hold the members because the MSVC | 209 // ListHashSetNode has this base class to hold the members because the MSVC |
192 // compiler otherwise gets into circular template dependencies when trying | 210 // compiler otherwise gets into circular template dependencies when trying |
193 // to do sizeof on a node. | 211 // to do sizeof on a node. |
194 template<typename ValueArg> class ListHashSetNodeBase { | 212 template<typename ValueArg> class ListHashSetNodeBase { |
195 protected: | 213 protected: |
196 ListHashSetNodeBase(const ValueArg& value) | 214 ListHashSetNodeBase(const ValueArg& value) |
197 : m_value(value) | 215 : m_value(value) |
198 , m_prev(0) | 216 , m_prev(0) |
(...skipping 463 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
662 swap(tmp); | 680 swap(tmp); |
663 return *this; | 681 return *this; |
664 } | 682 } |
665 | 683 |
666 template<typename T, size_t inlineCapacity, typename U, typename V> | 684 template<typename T, size_t inlineCapacity, typename U, typename V> |
667 inline void ListHashSet<T, inlineCapacity, U, V>::swap(ListHashSet& other) | 685 inline void ListHashSet<T, inlineCapacity, U, V>::swap(ListHashSet& other) |
668 { | 686 { |
669 m_impl.swap(other.m_impl); | 687 m_impl.swap(other.m_impl); |
670 std::swap(m_head, other.m_head); | 688 std::swap(m_head, other.m_head); |
671 std::swap(m_tail, other.m_tail); | 689 std::swap(m_tail, other.m_tail); |
672 m_allocatorProvider.swap(other.m_allocatorProvider); | 690 this->m_allocatorProvider.swap(other.m_allocatorProvider); |
673 } | 691 } |
674 | 692 |
675 template<typename T, size_t inlineCapacity, typename U, typename V> | 693 template<typename T, size_t inlineCapacity, typename U, typename V> |
676 inline ListHashSet<T, inlineCapacity, U, V>::~ListHashSet() | 694 inline void ListHashSet<T, inlineCapacity, U, V>::finalize() |
677 { | 695 { |
678 if (!Allocator::isGarbageCollected) | 696 COMPILE_ASSERT(!Allocator::isGarbageCollected, FinalizeOnHeapAllocatedLi
stHashSetShouldNeverBeCalled); |
679 deleteAllNodes(); | 697 deleteAllNodes(); |
680 } | 698 } |
681 | 699 |
682 template<typename T, size_t inlineCapacity, typename U, typename V> | 700 template<typename T, size_t inlineCapacity, typename U, typename V> |
683 inline T& ListHashSet<T, inlineCapacity, U, V>::first() | 701 inline T& ListHashSet<T, inlineCapacity, U, V>::first() |
684 { | 702 { |
685 ASSERT(!isEmpty()); | 703 ASSERT(!isEmpty()); |
686 return m_head->m_value; | 704 return m_head->m_value; |
687 } | 705 } |
688 | 706 |
689 template<typename T, size_t inlineCapacity, typename U, typename V> | 707 template<typename T, size_t inlineCapacity, typename U, typename V> |
(...skipping 282 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
972 inline void deleteAllValues(const ListHashSet<T, inlineCapacity, U, V>& coll
ection) | 990 inline void deleteAllValues(const ListHashSet<T, inlineCapacity, U, V>& coll
ection) |
973 { | 991 { |
974 deleteAllValues<true, typename ListHashSet<T, inlineCapacity, U, V>::Val
ueType>(collection.m_impl); | 992 deleteAllValues<true, typename ListHashSet<T, inlineCapacity, U, V>::Val
ueType>(collection.m_impl); |
975 } | 993 } |
976 | 994 |
977 } // namespace WTF | 995 } // namespace WTF |
978 | 996 |
979 using WTF::ListHashSet; | 997 using WTF::ListHashSet; |
980 | 998 |
981 #endif /* WTF_ListHashSet_h */ | 999 #endif /* WTF_ListHashSet_h */ |
OLD | NEW |