| 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 |