diff options
Diffstat (limited to 'chromium/third_party/WebKit/Source/wtf/ListHashSet.h')
| -rw-r--r-- | chromium/third_party/WebKit/Source/wtf/ListHashSet.h | 809 |
1 files changed, 440 insertions, 369 deletions
diff --git a/chromium/third_party/WebKit/Source/wtf/ListHashSet.h b/chromium/third_party/WebKit/Source/wtf/ListHashSet.h index 44d649259b6..7e26077e8d3 100644 --- a/chromium/third_party/WebKit/Source/wtf/ListHashSet.h +++ b/chromium/third_party/WebKit/Source/wtf/ListHashSet.h @@ -22,6 +22,7 @@ #ifndef WTF_ListHashSet_h #define WTF_ListHashSet_h +#include "wtf/DefaultAllocator.h" #include "wtf/HashSet.h" #include "wtf/OwnPtr.h" #include "wtf/PassOwnPtr.h" @@ -38,73 +39,101 @@ namespace WTF { // guaranteed safe against mutation of the ListHashSet, except for // removal of the item currently pointed to by a given iterator. - template<typename Value, size_t inlineCapacity, typename HashFunctions> class ListHashSet; + template<typename Value, size_t inlineCapacity, typename HashFunctions, typename Allocator> class ListHashSet; - template<typename Value, size_t inlineCapacity, typename HashFunctions> - void deleteAllValues(const ListHashSet<Value, inlineCapacity, HashFunctions>&); + template<typename Set> class ListHashSetIterator; + template<typename Set> class ListHashSetConstIterator; + template<typename Set> class ListHashSetReverseIterator; + template<typename Set> class ListHashSetConstReverseIterator; - template<typename ValueArg, size_t inlineCapacity, typename HashArg> class ListHashSetIterator; - template<typename ValueArg, size_t inlineCapacity, typename HashArg> class ListHashSetConstIterator; - template<typename ValueArg, size_t inlineCapacity, typename HashArg> class ListHashSetReverseIterator; - template<typename ValueArg, size_t inlineCapacity, typename HashArg> class ListHashSetConstReverseIterator; - - template<typename ValueArg, size_t inlineCapacity> struct ListHashSetNode; - template<typename ValueArg, size_t inlineCapacity> struct ListHashSetNodeAllocator; + template<typename ValueArg> class ListHashSetNodeBase; + template<typename ValueArg, typename Allocator> class ListHashSetNode; + template<typename ValueArg, size_t inlineCapacity> struct ListHashSetAllocator; template<typename HashArg> struct ListHashSetNodeHashFunctions; template<typename HashArg> struct ListHashSetTranslator; - template<typename ValueArg, size_t inlineCapacity = 256, typename HashArg = typename DefaultHash<ValueArg>::Hash> class ListHashSet { - WTF_MAKE_FAST_ALLOCATED; - private: - typedef ListHashSetNode<ValueArg, inlineCapacity> Node; - typedef ListHashSetNodeAllocator<ValueArg, inlineCapacity> NodeAllocator; + // Don't declare a destructor for HeapAllocated ListHashSet. + template<typename Derived, typename Allocator, bool isGarbageCollected> + class ListHashSetDestructorBase; + + template<typename Derived, typename Allocator> + class ListHashSetDestructorBase<Derived, Allocator, true> { + protected: + typename Allocator::AllocatorProvider m_allocatorProvider; + }; + + template<typename Derived, typename Allocator> + class ListHashSetDestructorBase<Derived, Allocator, false> { + public: + ~ListHashSetDestructorBase() { static_cast<Derived*>(this)->finalize(); } + protected: + typename Allocator::AllocatorProvider m_allocatorProvider; + }; + + // Note that for a ListHashSet you cannot specify the HashTraits as a + // template argument. It uses the default hash traits for the ValueArg + // type. + template<typename ValueArg, size_t inlineCapacity = 256, typename HashArg = typename DefaultHash<ValueArg>::Hash, typename AllocatorArg = ListHashSetAllocator<ValueArg, inlineCapacity> > class ListHashSet + : public ListHashSetDestructorBase<ListHashSet<ValueArg, inlineCapacity, HashArg, AllocatorArg>, AllocatorArg, AllocatorArg::isGarbageCollected> { + typedef AllocatorArg Allocator; + WTF_USE_ALLOCATOR(ListHashSet, Allocator); + typedef ListHashSetNode<ValueArg, Allocator> Node; typedef HashTraits<Node*> NodeTraits; typedef ListHashSetNodeHashFunctions<HashArg> NodeHash; typedef ListHashSetTranslator<HashArg> BaseTranslator; - typedef HashTable<Node*, Node*, IdentityExtractor, NodeHash, NodeTraits, NodeTraits> ImplType; - typedef HashTableIterator<Node*, Node*, IdentityExtractor, NodeHash, NodeTraits, NodeTraits> ImplTypeIterator; - typedef HashTableConstIterator<Node*, Node*, IdentityExtractor, NodeHash, NodeTraits, NodeTraits> ImplTypeConstIterator; + typedef HashTable<Node*, Node*, IdentityExtractor, NodeHash, NodeTraits, NodeTraits, typename Allocator::TableAllocator> ImplType; + typedef HashTableIterator<Node*, Node*, IdentityExtractor, NodeHash, NodeTraits, NodeTraits, typename Allocator::TableAllocator> ImplTypeIterator; + typedef HashTableConstIterator<Node*, Node*, IdentityExtractor, NodeHash, NodeTraits, NodeTraits, typename Allocator::TableAllocator> ImplTypeConstIterator; typedef HashArg HashFunctions; public: typedef ValueArg ValueType; - - typedef ListHashSetIterator<ValueType, inlineCapacity, HashArg> iterator; - typedef ListHashSetConstIterator<ValueType, inlineCapacity, HashArg> const_iterator; - friend class ListHashSetConstIterator<ValueType, inlineCapacity, HashArg>; - - typedef ListHashSetReverseIterator<ValueType, inlineCapacity, HashArg> reverse_iterator; - typedef ListHashSetConstReverseIterator<ValueType, inlineCapacity, HashArg> const_reverse_iterator; - friend class ListHashSetConstReverseIterator<ValueType, inlineCapacity, HashArg>; - - typedef HashTableAddResult<iterator> AddResult; + typedef HashTraits<ValueType> ValueTraits; + typedef typename ValueTraits::PeekInType ValuePeekInType; + typedef typename ValueTraits::PassInType ValuePassInType; + typedef typename ValueTraits::PassOutType ValuePassOutType; + + typedef ListHashSetIterator<ListHashSet> iterator; + typedef ListHashSetConstIterator<ListHashSet> const_iterator; + friend class ListHashSetIterator<ListHashSet>; + friend class ListHashSetConstIterator<ListHashSet>; + + typedef ListHashSetReverseIterator<ListHashSet> reverse_iterator; + typedef ListHashSetConstReverseIterator<ListHashSet> const_reverse_iterator; + friend class ListHashSetReverseIterator<ListHashSet>; + friend class ListHashSetConstReverseIterator<ListHashSet>; + + template<typename ValueType> struct HashTableAddResult { + HashTableAddResult(Node* storedValue, bool isNewEntry) : storedValue(storedValue), isNewEntry(isNewEntry) { } + Node* storedValue; + bool isNewEntry; + }; + typedef HashTableAddResult<ValueType> AddResult; ListHashSet(); ListHashSet(const ListHashSet&); ListHashSet& operator=(const ListHashSet&); - ~ListHashSet(); + void finalize(); void swap(ListHashSet&); - unsigned size() const; - unsigned capacity() const; - bool isEmpty() const; - - size_t sizeInBytes() const; + unsigned size() const { return m_impl.size(); } + unsigned capacity() const { return m_impl.capacity(); } + bool isEmpty() const { return m_impl.isEmpty(); } - iterator begin(); - iterator end(); - const_iterator begin() const; - const_iterator end() const; + iterator begin() { return makeIterator(m_head); } + iterator end() { return makeIterator(0); } + const_iterator begin() const { return makeConstIterator(m_head); } + const_iterator end() const { return makeConstIterator(0); } - reverse_iterator rbegin(); - reverse_iterator rend(); - const_reverse_iterator rbegin() const; - const_reverse_iterator rend() const; + reverse_iterator rbegin() { return makeReverseIterator(m_tail); } + reverse_iterator rend() { return makeReverseIterator(0); } + const_reverse_iterator rbegin() const { return makeConstReverseIterator(m_tail); } + const_reverse_iterator rend() const { return makeConstReverseIterator(0); } ValueType& first(); const ValueType& first() const; @@ -114,9 +143,9 @@ namespace WTF { const ValueType& last() const; void removeLast(); - iterator find(const ValueType&); - const_iterator find(const ValueType&) const; - bool contains(const ValueType&) const; + iterator find(ValuePeekInType); + const_iterator find(ValuePeekInType) const; + bool contains(ValuePeekInType) const; // An alternate version of find() that finds the object by hashing and comparing // with some other type, to avoid the cost of type conversion. @@ -125,24 +154,38 @@ namespace WTF { template<typename HashTranslator, typename T> const_iterator find(const T&) const; template<typename HashTranslator, typename T> bool contains(const T&) const; - // The return value of add is a pair of an iterator to the new value's location, + // The return value of add is a pair of a pointer to the stored value, // and a bool that is true if an new entry was added. - AddResult add(const ValueType&); + AddResult add(ValuePassInType); + + // Same as add() except that the return value is an + // iterator. Useful in cases where it's needed to have the + // same return value as find() and where it's not possible to + // use a pointer to the storedValue. + iterator addReturnIterator(ValuePassInType); // Add the value to the end of the collection. If the value was already in // the list, it is moved to the end. - AddResult appendOrMoveToLast(const ValueType&); + AddResult appendOrMoveToLast(ValuePassInType); // Add the value to the beginning of the collection. If the value was already in // the list, it is moved to the beginning. - AddResult prependOrMoveToFirst(const ValueType&); + AddResult prependOrMoveToFirst(ValuePassInType); - AddResult insertBefore(const ValueType& beforeValue, const ValueType& newValue); - AddResult insertBefore(iterator, const ValueType&); + AddResult insertBefore(ValuePeekInType beforeValue, ValuePassInType newValue); + AddResult insertBefore(iterator, ValuePassInType); - void remove(const ValueType&); + void remove(ValuePeekInType value) { return remove(find(value)); } void remove(iterator); void clear(); + template<typename Collection> + void removeAll(const Collection& other) { WTF::removeAll(*this, other); } + + ValuePassOutType take(iterator); + ValuePassOutType take(ValuePeekInType); + ValuePassOutType takeFirst(); + + void trace(typename Allocator::Visitor*); private: void unlink(Node*); @@ -151,42 +194,107 @@ namespace WTF { void prependNode(Node*); void insertNodeBefore(Node* beforeNode, Node* newNode); void deleteAllNodes(); - void createAllocatorIfNeeded(); + Allocator* allocator() const { return this->m_allocatorProvider.get(); } + void createAllocatorIfNeeded() { this->m_allocatorProvider.createAllocatorIfNeeded(); } + void deallocate(Node* node) const { this->m_allocatorProvider.deallocate(node); } - iterator makeIterator(Node*); - const_iterator makeConstIterator(Node*) const; - reverse_iterator makeReverseIterator(Node*); - const_reverse_iterator makeConstReverseIterator(Node*) const; - - friend void deleteAllValues<>(const ListHashSet&); + iterator makeIterator(Node* position) { return iterator(this, position); } + const_iterator makeConstIterator(Node* position) const { return const_iterator(this, position); } + reverse_iterator makeReverseIterator(Node* position) { return reverse_iterator(this, position); } + const_reverse_iterator makeConstReverseIterator(Node* position) const { return const_reverse_iterator(this, position); } ImplType m_impl; Node* m_head; Node* m_tail; - OwnPtr<NodeAllocator> m_allocator; }; - template<typename ValueArg, size_t inlineCapacity> struct ListHashSetNodeAllocator { - typedef ListHashSetNode<ValueArg, inlineCapacity> Node; - typedef ListHashSetNodeAllocator<ValueArg, inlineCapacity> NodeAllocator; + // ListHashSetNode has this base class to hold the members because the MSVC + // compiler otherwise gets into circular template dependencies when trying + // to do sizeof on a node. + template<typename ValueArg> class ListHashSetNodeBase { + protected: + ListHashSetNodeBase(const ValueArg& value) + : m_value(value) + , m_prev(0) + , m_next(0) +#ifndef NDEBUG + , m_isAllocated(true) +#endif + { + } + + template <typename U> + ListHashSetNodeBase(const U& value) + : m_value(value) + , m_prev(0) + , m_next(0) +#ifndef NDEBUG + , m_isAllocated(true) +#endif + { + } + + public: + ValueArg m_value; + ListHashSetNodeBase* m_prev; + ListHashSetNodeBase* m_next; +#ifndef NDEBUG + bool m_isAllocated; +#endif + }; + + // This allocator is only used for non-Heap ListHashSets. + template<typename ValueArg, size_t inlineCapacity> + struct ListHashSetAllocator : public DefaultAllocator { + typedef DefaultAllocator TableAllocator; + typedef ListHashSetNode<ValueArg, ListHashSetAllocator> Node; + typedef ListHashSetNodeBase<ValueArg> NodeBase; + class AllocatorProvider { + public: + void createAllocatorIfNeeded() + { + if (!m_allocator) + m_allocator = adoptPtr(new ListHashSetAllocator); + } + + void swap(AllocatorProvider& other) + { + m_allocator.swap(other.m_allocator); + } + + void deallocate(Node* node) const + { + ASSERT(m_allocator); + m_allocator->deallocate(node); + } + + ListHashSetAllocator* get() const + { + ASSERT(m_allocator); + return m_allocator.get(); + } - ListHashSetNodeAllocator() + private: + OwnPtr<ListHashSetAllocator> m_allocator; + }; + + ListHashSetAllocator() : m_freeList(pool()) , m_isDoneWithInitialFreeList(false) { - memset(m_pool.pool, 0, sizeof(m_pool.pool)); + memset(m_pool.buffer, 0, sizeof(m_pool.buffer)); } - Node* allocate() + Node* allocateNode() { Node* result = m_freeList; if (!result) - return static_cast<Node*>(fastMalloc(sizeof(Node))); + return static_cast<Node*>(fastMalloc(sizeof(NodeBase))); ASSERT(!result->m_isAllocated); - Node* next = result->m_next; + Node* next = result->next(); ASSERT(!next || !next->m_isAllocated); if (!next && !m_isDoneWithInitialFreeList) { next = result + 1; @@ -222,49 +330,102 @@ namespace WTF { return node >= pool() && node < pastPool(); } + static void traceValue(typename DefaultAllocator::Visitor* visitor, Node* node) { } + private: - Node* pool() { return reinterpret_cast_ptr<Node*>(m_pool.pool); } + Node* pool() { return reinterpret_cast_ptr<Node*>(m_pool.buffer); } Node* pastPool() { return pool() + m_poolSize; } Node* m_freeList; bool m_isDoneWithInitialFreeList; +#if defined(MEMORY_TOOL_REPLACES_ALLOCATOR) + // The allocation pool for nodes is one big chunk that ASAN has no + // insight into, so it can cloak errors. Make it as small as possible + // to force nodes to be allocated individually where ASAN can see them. + static const size_t m_poolSize = 1; +#else static const size_t m_poolSize = inlineCapacity; - union { - char pool[sizeof(Node) * m_poolSize]; - double forAlignment; - } m_pool; +#endif + AlignedBuffer<sizeof(NodeBase) * m_poolSize, WTF_ALIGN_OF(NodeBase)> m_pool; }; - template<typename ValueArg, size_t inlineCapacity> struct ListHashSetNode { - typedef ListHashSetNodeAllocator<ValueArg, inlineCapacity> NodeAllocator; + template<typename ValueArg, typename AllocatorArg> class ListHashSetNode : public ListHashSetNodeBase<ValueArg> { + public: + typedef AllocatorArg NodeAllocator; + typedef ValueArg Value; - ListHashSetNode(ValueArg value) - : m_value(value) - , m_prev(0) - , m_next(0) -#ifndef NDEBUG - , m_isAllocated(true) -#endif + template <typename U> + ListHashSetNode(U value) + : ListHashSetNodeBase<ValueArg>(value) { } + + void* operator new(size_t, NodeAllocator* allocator) { + COMPILE_ASSERT(sizeof(ListHashSetNode) == sizeof(ListHashSetNodeBase<ValueArg>), PleaseAddAnyFieldsToTheBase); + return allocator->allocateNode(); } - void* operator new(size_t, NodeAllocator* allocator) + void setWasAlreadyDestructed() { - return allocator->allocate(); + if (NodeAllocator::isGarbageCollected && HashTraits<ValueArg>::needsDestruction) + this->m_prev = unlinkedNodePointer(); } + + bool wasAlreadyDestructed() const + { + ASSERT(NodeAllocator::isGarbageCollected); + return this->m_prev == unlinkedNodePointer(); + } + + static void finalize(void* pointer) + { + ASSERT(HashTraits<ValueArg>::needsDestruction); // No need to waste time calling finalize if it's not needed. + ListHashSetNode* self = reinterpret_cast_ptr<ListHashSetNode*>(pointer); + + // Check whether this node was already destructed before being + // unlinked from the collection. + if (self->wasAlreadyDestructed()) + return; + + self->m_value.~ValueArg(); + } + void destroy(NodeAllocator* allocator) { this->~ListHashSetNode(); + setWasAlreadyDestructed(); allocator->deallocate(this); } - ValueArg m_value; - ListHashSetNode* m_prev; - ListHashSetNode* m_next; + // This is not called in normal tracing, but it is called if we find a + // pointer to a node on the stack using conservative scanning. Since + // the original ListHashSet may no longer exist we make sure to mark + // the neighbours in the chain too. + void trace(typename NodeAllocator::Visitor* visitor) + { + // The conservative stack scan can find nodes that have been + // removed from the set and destructed. We don't need to trace + // these, and it would be wrong to do so, because the class will + // not expect the trace method to be called after the destructor. + // It's an error to remove a node from the ListHashSet while an + // iterator is positioned at that node, so there should be no valid + // pointers from the stack to a destructed node. + if (wasAlreadyDestructed()) + return; + NodeAllocator::traceValue(visitor, this); + visitor->mark(next()); + visitor->mark(prev()); + } -#ifndef NDEBUG - bool m_isAllocated; -#endif + ListHashSetNode* next() const { return reinterpret_cast<ListHashSetNode*>(this->m_next); } + ListHashSetNode* prev() const { return reinterpret_cast<ListHashSetNode*>(this->m_prev); } + + // Don't add fields here, the ListHashSetNodeBase and this should have + // the same size. + + static ListHashSetNode* unlinkedNodePointer() { return reinterpret_cast<ListHashSetNode*>(-1); } + + template<typename HashArg> + friend struct ListHashSetNodeHashFunctions; }; template<typename HashArg> struct ListHashSetNodeHashFunctions { @@ -273,19 +434,15 @@ namespace WTF { static const bool safeToCompareToEmptyOrDeleted = false; }; - template<typename ValueArg, size_t inlineCapacity, typename HashArg> class ListHashSetIterator { + template<typename Set> class ListHashSetIterator { private: - typedef ListHashSet<ValueArg, inlineCapacity, HashArg> ListHashSetType; - typedef ListHashSetIterator<ValueArg, inlineCapacity, HashArg> iterator; - typedef ListHashSetConstIterator<ValueArg, inlineCapacity, HashArg> const_iterator; - typedef ListHashSetNode<ValueArg, inlineCapacity> Node; - typedef ValueArg ValueType; + typedef typename Set::const_iterator const_iterator; + typedef typename Set::Node Node; + typedef typename Set::ValueType ValueType; typedef ValueType& ReferenceType; typedef ValueType* PointerType; - friend class ListHashSet<ValueArg, inlineCapacity, HashArg>; - - ListHashSetIterator(const ListHashSetType* set, Node* position) : m_iterator(set, position) { } + ListHashSetIterator(const Set* set, Node* position) : m_iterator(set, position) { } public: ListHashSetIterator() { } @@ -296,17 +453,14 @@ namespace WTF { ReferenceType operator*() const { return *get(); } PointerType operator->() const { return get(); } - iterator& operator++() { ++m_iterator; return *this; } - - // postfix ++ intentionally omitted - - iterator& operator--() { --m_iterator; return *this; } + ListHashSetIterator& operator++() { ++m_iterator; return *this; } + ListHashSetIterator& operator--() { --m_iterator; return *this; } - // postfix -- intentionally omitted + // Postfix ++ and -- intentionally omitted. // Comparison. - bool operator==(const iterator& other) const { return m_iterator == other.m_iterator; } - bool operator!=(const iterator& other) const { return m_iterator != other.m_iterator; } + bool operator==(const ListHashSetIterator& other) const { return m_iterator == other.m_iterator; } + bool operator!=(const ListHashSetIterator& other) const { return m_iterator != other.m_iterator; } operator const_iterator() const { return m_iterator; } @@ -314,22 +468,23 @@ namespace WTF { Node* node() { return m_iterator.node(); } const_iterator m_iterator; + + template<typename T, size_t inlineCapacity, typename U, typename V> + friend class ListHashSet; }; - template<typename ValueArg, size_t inlineCapacity, typename HashArg> class ListHashSetConstIterator { + template<typename Set> + class ListHashSetConstIterator { private: - typedef ListHashSet<ValueArg, inlineCapacity, HashArg> ListHashSetType; - typedef ListHashSetIterator<ValueArg, inlineCapacity, HashArg> iterator; - typedef ListHashSetConstIterator<ValueArg, inlineCapacity, HashArg> const_iterator; - typedef ListHashSetNode<ValueArg, inlineCapacity> Node; - typedef ValueArg ValueType; + typedef typename Set::const_iterator const_iterator; + typedef typename Set::Node Node; + typedef typename Set::ValueType ValueType; typedef const ValueType& ReferenceType; typedef const ValueType* PointerType; - friend class ListHashSet<ValueArg, inlineCapacity, HashArg>; - friend class ListHashSetIterator<ValueArg, inlineCapacity, HashArg>; + friend class ListHashSetIterator<Set>; - ListHashSetConstIterator(const ListHashSetType* set, Node* position) + ListHashSetConstIterator(const Set* set, Node* position) : m_set(set) , m_position(position) { @@ -347,33 +502,31 @@ namespace WTF { ReferenceType operator*() const { return *get(); } PointerType operator->() const { return get(); } - const_iterator& operator++() + ListHashSetConstIterator& operator++() { ASSERT(m_position != 0); - m_position = m_position->m_next; + m_position = m_position->next(); return *this; } - // postfix ++ intentionally omitted - - const_iterator& operator--() + ListHashSetConstIterator& operator--() { ASSERT(m_position != m_set->m_head); if (!m_position) m_position = m_set->m_tail; else - m_position = m_position->m_prev; + m_position = m_position->prev(); return *this; } - // postfix -- intentionally omitted + // Postfix ++ and -- intentionally omitted. // Comparison. - bool operator==(const const_iterator& other) const + bool operator==(const ListHashSetConstIterator& other) const { return m_position == other.m_position; } - bool operator!=(const const_iterator& other) const + bool operator!=(const ListHashSetConstIterator& other) const { return m_position != other.m_position; } @@ -381,23 +534,23 @@ namespace WTF { private: Node* node() { return m_position; } - const ListHashSetType* m_set; + const Set* m_set; Node* m_position; + + template<typename T, size_t inlineCapacity, typename U, typename V> + friend class ListHashSet; }; - template<typename ValueArg, size_t inlineCapacity, typename HashArg> class ListHashSetReverseIterator { + template<typename Set> + class ListHashSetReverseIterator { private: - typedef ListHashSet<ValueArg, inlineCapacity, HashArg> ListHashSetType; - typedef ListHashSetReverseIterator<ValueArg, inlineCapacity, HashArg> reverse_iterator; - typedef ListHashSetConstReverseIterator<ValueArg, inlineCapacity, HashArg> const_reverse_iterator; - typedef ListHashSetNode<ValueArg, inlineCapacity> Node; - typedef ValueArg ValueType; + typedef typename Set::const_reverse_iterator const_reverse_iterator; + typedef typename Set::Node Node; + typedef typename Set::ValueType ValueType; typedef ValueType& ReferenceType; typedef ValueType* PointerType; - friend class ListHashSet<ValueArg, inlineCapacity, HashArg>; - - ListHashSetReverseIterator(const ListHashSetType* set, Node* position) : m_iterator(set, position) { } + ListHashSetReverseIterator(const Set* set, Node* position) : m_iterator(set, position) { } public: ListHashSetReverseIterator() { } @@ -408,17 +561,14 @@ namespace WTF { ReferenceType operator*() const { return *get(); } PointerType operator->() const { return get(); } - reverse_iterator& operator++() { ++m_iterator; return *this; } - - // postfix ++ intentionally omitted - - reverse_iterator& operator--() { --m_iterator; return *this; } + ListHashSetReverseIterator& operator++() { ++m_iterator; return *this; } + ListHashSetReverseIterator& operator--() { --m_iterator; return *this; } - // postfix -- intentionally omitted + // Postfix ++ and -- intentionally omitted. // Comparison. - bool operator==(const reverse_iterator& other) const { return m_iterator == other.m_iterator; } - bool operator!=(const reverse_iterator& other) const { return m_iterator != other.m_iterator; } + bool operator==(const ListHashSetReverseIterator& other) const { return m_iterator == other.m_iterator; } + bool operator!=(const ListHashSetReverseIterator& other) const { return m_iterator != other.m_iterator; } operator const_reverse_iterator() const { return m_iterator; } @@ -426,22 +576,22 @@ namespace WTF { Node* node() { return m_iterator.node(); } const_reverse_iterator m_iterator; + + template<typename T, size_t inlineCapacity, typename U, typename V> + friend class ListHashSet; }; - template<typename ValueArg, size_t inlineCapacity, typename HashArg> class ListHashSetConstReverseIterator { + template<typename Set> class ListHashSetConstReverseIterator { private: - typedef ListHashSet<ValueArg, inlineCapacity, HashArg> ListHashSetType; - typedef ListHashSetReverseIterator<ValueArg, inlineCapacity, HashArg> reverse_iterator; - typedef ListHashSetConstReverseIterator<ValueArg, inlineCapacity, HashArg> const_reverse_iterator; - typedef ListHashSetNode<ValueArg, inlineCapacity> Node; - typedef ValueArg ValueType; + typedef typename Set::reverse_iterator reverse_iterator; + typedef typename Set::Node Node; + typedef typename Set::ValueType ValueType; typedef const ValueType& ReferenceType; typedef const ValueType* PointerType; - friend class ListHashSet<ValueArg, inlineCapacity, HashArg>; - friend class ListHashSetReverseIterator<ValueArg, inlineCapacity, HashArg>; + friend class ListHashSetReverseIterator<Set>; - ListHashSetConstReverseIterator(const ListHashSetType* set, Node* position) + ListHashSetConstReverseIterator(const Set* set, Node* position) : m_set(set) , m_position(position) { @@ -459,33 +609,31 @@ namespace WTF { ReferenceType operator*() const { return *get(); } PointerType operator->() const { return get(); } - const_reverse_iterator& operator++() + ListHashSetConstReverseIterator& operator++() { ASSERT(m_position != 0); - m_position = m_position->m_prev; + m_position = m_position->prev(); return *this; } - // postfix ++ intentionally omitted - - const_reverse_iterator& operator--() + ListHashSetConstReverseIterator& operator--() { ASSERT(m_position != m_set->m_tail); if (!m_position) m_position = m_set->m_head; else - m_position = m_position->m_next; + m_position = m_position->next(); return *this; } - // postfix -- intentionally omitted + // Postfix ++ and -- intentionally omitted. // Comparison. - bool operator==(const const_reverse_iterator& other) const + bool operator==(const ListHashSetConstReverseIterator& other) const { return m_position == other.m_position; } - bool operator!=(const const_reverse_iterator& other) const + bool operator!=(const ListHashSetConstReverseIterator& other) const { return m_position != other.m_position; } @@ -493,8 +641,11 @@ namespace WTF { private: Node* node() { return m_position; } - const ListHashSetType* m_set; + const Set* m_set; Node* m_position; + + template<typename T, size_t inlineCapacity, typename U, typename V> + friend class ListHashSet; }; template<typename HashFunctions> @@ -503,19 +654,19 @@ namespace WTF { template<typename T, typename U> static bool equal(const T& a, const U& b) { return HashFunctions::equal(a->m_value, b); } template<typename T, typename U, typename V> static void translate(T*& location, const U& key, const V& allocator) { - location = new (allocator) T(key); + location = new (const_cast<V*>(&allocator)) T(key); } }; - template<typename T, size_t inlineCapacity, typename U> - inline ListHashSet<T, inlineCapacity, U>::ListHashSet() + template<typename T, size_t inlineCapacity, typename U, typename V> + inline ListHashSet<T, inlineCapacity, U, V>::ListHashSet() : m_head(0) , m_tail(0) { } - template<typename T, size_t inlineCapacity, typename U> - inline ListHashSet<T, inlineCapacity, U>::ListHashSet(const ListHashSet& other) + template<typename T, size_t inlineCapacity, typename U, typename V> + inline ListHashSet<T, inlineCapacity, U, V>::ListHashSet(const ListHashSet& other) : m_head(0) , m_tail(0) { @@ -524,155 +675,76 @@ namespace WTF { add(*it); } - template<typename T, size_t inlineCapacity, typename U> - inline ListHashSet<T, inlineCapacity, U>& ListHashSet<T, inlineCapacity, U>::operator=(const ListHashSet& other) + template<typename T, size_t inlineCapacity, typename U, typename V> + inline ListHashSet<T, inlineCapacity, U, V>& ListHashSet<T, inlineCapacity, U, V>::operator=(const ListHashSet& other) { ListHashSet tmp(other); swap(tmp); return *this; } - template<typename T, size_t inlineCapacity, typename U> - inline void ListHashSet<T, inlineCapacity, U>::swap(ListHashSet& other) + template<typename T, size_t inlineCapacity, typename U, typename V> + inline void ListHashSet<T, inlineCapacity, U, V>::swap(ListHashSet& other) { m_impl.swap(other.m_impl); std::swap(m_head, other.m_head); std::swap(m_tail, other.m_tail); - m_allocator.swap(other.m_allocator); + this->m_allocatorProvider.swap(other.m_allocatorProvider); } - template<typename T, size_t inlineCapacity, typename U> - inline ListHashSet<T, inlineCapacity, U>::~ListHashSet() + template<typename T, size_t inlineCapacity, typename U, typename V> + inline void ListHashSet<T, inlineCapacity, U, V>::finalize() { + COMPILE_ASSERT(!Allocator::isGarbageCollected, FinalizeOnHeapAllocatedListHashSetShouldNeverBeCalled); deleteAllNodes(); } - template<typename T, size_t inlineCapacity, typename U> - inline unsigned ListHashSet<T, inlineCapacity, U>::size() const - { - return m_impl.size(); - } - - template<typename T, size_t inlineCapacity, typename U> - inline unsigned ListHashSet<T, inlineCapacity, U>::capacity() const - { - return m_impl.capacity(); - } - - template<typename T, size_t inlineCapacity, typename U> - inline bool ListHashSet<T, inlineCapacity, U>::isEmpty() const - { - return m_impl.isEmpty(); - } - - template<typename T, size_t inlineCapacity, typename U> - size_t ListHashSet<T, inlineCapacity, U>::sizeInBytes() const - { - size_t result = sizeof(*this); - if (!m_allocator) - return result; - result += sizeof(*m_allocator) + (sizeof(typename ImplType::ValueType) * m_impl.capacity()); - for (Node* node = m_head; node; node = node->m_next) { - if (!m_allocator->inPool(node)) - result += sizeof(Node); - } - return result; - } - - template<typename T, size_t inlineCapacity, typename U> - inline typename ListHashSet<T, inlineCapacity, U>::iterator ListHashSet<T, inlineCapacity, U>::begin() - { - return makeIterator(m_head); - } - - template<typename T, size_t inlineCapacity, typename U> - inline typename ListHashSet<T, inlineCapacity, U>::iterator ListHashSet<T, inlineCapacity, U>::end() - { - return makeIterator(0); - } - - template<typename T, size_t inlineCapacity, typename U> - inline typename ListHashSet<T, inlineCapacity, U>::const_iterator ListHashSet<T, inlineCapacity, U>::begin() const - { - return makeConstIterator(m_head); - } - - template<typename T, size_t inlineCapacity, typename U> - inline typename ListHashSet<T, inlineCapacity, U>::const_iterator ListHashSet<T, inlineCapacity, U>::end() const - { - return makeConstIterator(0); - } - - template<typename T, size_t inlineCapacity, typename U> - inline typename ListHashSet<T, inlineCapacity, U>::reverse_iterator ListHashSet<T, inlineCapacity, U>::rbegin() - { - return makeReverseIterator(m_tail); - } - - template<typename T, size_t inlineCapacity, typename U> - inline typename ListHashSet<T, inlineCapacity, U>::reverse_iterator ListHashSet<T, inlineCapacity, U>::rend() - { - return makeReverseIterator(0); - } - - template<typename T, size_t inlineCapacity, typename U> - inline typename ListHashSet<T, inlineCapacity, U>::const_reverse_iterator ListHashSet<T, inlineCapacity, U>::rbegin() const - { - return makeConstReverseIterator(m_tail); - } - - template<typename T, size_t inlineCapacity, typename U> - inline typename ListHashSet<T, inlineCapacity, U>::const_reverse_iterator ListHashSet<T, inlineCapacity, U>::rend() const - { - return makeConstReverseIterator(0); - } - - template<typename T, size_t inlineCapacity, typename U> - inline T& ListHashSet<T, inlineCapacity, U>::first() + template<typename T, size_t inlineCapacity, typename U, typename V> + inline T& ListHashSet<T, inlineCapacity, U, V>::first() { ASSERT(!isEmpty()); return m_head->m_value; } - template<typename T, size_t inlineCapacity, typename U> - inline void ListHashSet<T, inlineCapacity, U>::removeFirst() + template<typename T, size_t inlineCapacity, typename U, typename V> + inline void ListHashSet<T, inlineCapacity, U, V>::removeFirst() { ASSERT(!isEmpty()); m_impl.remove(m_head); unlinkAndDelete(m_head); } - template<typename T, size_t inlineCapacity, typename U> - inline const T& ListHashSet<T, inlineCapacity, U>::first() const + template<typename T, size_t inlineCapacity, typename U, typename V> + inline const T& ListHashSet<T, inlineCapacity, U, V>::first() const { ASSERT(!isEmpty()); return m_head->m_value; } - template<typename T, size_t inlineCapacity, typename U> - inline T& ListHashSet<T, inlineCapacity, U>::last() + template<typename T, size_t inlineCapacity, typename U, typename V> + inline T& ListHashSet<T, inlineCapacity, U, V>::last() { ASSERT(!isEmpty()); return m_tail->m_value; } - template<typename T, size_t inlineCapacity, typename U> - inline const T& ListHashSet<T, inlineCapacity, U>::last() const + template<typename T, size_t inlineCapacity, typename U, typename V> + inline const T& ListHashSet<T, inlineCapacity, U, V>::last() const { ASSERT(!isEmpty()); return m_tail->m_value; } - template<typename T, size_t inlineCapacity, typename U> - inline void ListHashSet<T, inlineCapacity, U>::removeLast() + template<typename T, size_t inlineCapacity, typename U, typename V> + inline void ListHashSet<T, inlineCapacity, U, V>::removeLast() { ASSERT(!isEmpty()); m_impl.remove(m_tail); unlinkAndDelete(m_tail); } - template<typename T, size_t inlineCapacity, typename U> - inline typename ListHashSet<T, inlineCapacity, U>::iterator ListHashSet<T, inlineCapacity, U>::find(const ValueType& value) + template<typename T, size_t inlineCapacity, typename U, typename V> + inline typename ListHashSet<T, inlineCapacity, U, V>::iterator ListHashSet<T, inlineCapacity, U, V>::find(ValuePeekInType value) { ImplTypeIterator it = m_impl.template find<BaseTranslator>(value); if (it == m_impl.end()) @@ -680,8 +752,8 @@ namespace WTF { return makeIterator(*it); } - template<typename T, size_t inlineCapacity, typename U> - inline typename ListHashSet<T, inlineCapacity, U>::const_iterator ListHashSet<T, inlineCapacity, U>::find(const ValueType& value) const + template<typename T, size_t inlineCapacity, typename U, typename V> + inline typename ListHashSet<T, inlineCapacity, U, V>::const_iterator ListHashSet<T, inlineCapacity, U, V>::find(ValuePeekInType value) const { ImplTypeConstIterator it = m_impl.template find<BaseTranslator>(value); if (it == m_impl.end()) @@ -695,9 +767,9 @@ namespace WTF { template<typename T, typename U> static bool equal(const T& a, const U& b) { return Translator::equal(a->m_value, b); } }; - template<typename ValueType, size_t inlineCapacity, typename U> + template<typename ValueType, size_t inlineCapacity, typename U, typename V> template<typename HashTranslator, typename T> - inline typename ListHashSet<ValueType, inlineCapacity, U>::iterator ListHashSet<ValueType, inlineCapacity, U>::find(const T& value) + inline typename ListHashSet<ValueType, inlineCapacity, U, V>::iterator ListHashSet<ValueType, inlineCapacity, U, V>::find(const T& value) { ImplTypeConstIterator it = m_impl.template find<ListHashSetTranslatorAdapter<HashTranslator> >(value); if (it == m_impl.end()) @@ -705,9 +777,9 @@ namespace WTF { return makeIterator(*it); } - template<typename ValueType, size_t inlineCapacity, typename U> + template<typename ValueType, size_t inlineCapacity, typename U, typename V> template<typename HashTranslator, typename T> - inline typename ListHashSet<ValueType, inlineCapacity, U>::const_iterator ListHashSet<ValueType, inlineCapacity, U>::find(const T& value) const + inline typename ListHashSet<ValueType, inlineCapacity, U, V>::const_iterator ListHashSet<ValueType, inlineCapacity, U, V>::find(const T& value) const { ImplTypeConstIterator it = m_impl.template find<ListHashSetTranslatorAdapter<HashTranslator> >(value); if (it == m_impl.end()) @@ -715,72 +787,82 @@ namespace WTF { return makeConstIterator(*it); } - template<typename ValueType, size_t inlineCapacity, typename U> + template<typename ValueType, size_t inlineCapacity, typename U, typename V> template<typename HashTranslator, typename T> - inline bool ListHashSet<ValueType, inlineCapacity, U>::contains(const T& value) const + inline bool ListHashSet<ValueType, inlineCapacity, U, V>::contains(const T& value) const { return m_impl.template contains<ListHashSetTranslatorAdapter<HashTranslator> >(value); } - template<typename T, size_t inlineCapacity, typename U> - inline bool ListHashSet<T, inlineCapacity, U>::contains(const ValueType& value) const + template<typename T, size_t inlineCapacity, typename U, typename V> + inline bool ListHashSet<T, inlineCapacity, U, V>::contains(ValuePeekInType value) const { return m_impl.template contains<BaseTranslator>(value); } - template<typename T, size_t inlineCapacity, typename U> - typename ListHashSet<T, inlineCapacity, U>::AddResult ListHashSet<T, inlineCapacity, U>::add(const ValueType &value) + template<typename T, size_t inlineCapacity, typename U, typename V> + typename ListHashSet<T, inlineCapacity, U, V>::AddResult ListHashSet<T, inlineCapacity, U, V>::add(ValuePassInType value) { createAllocatorIfNeeded(); - typename ImplType::AddResult result = m_impl.template add<BaseTranslator>(value, m_allocator.get()); + // The second argument is a const ref. This is useful for the HashTable + // because it lets it take lvalues by reference, but for our purposes + // it's inconvenient, since it constrains us to be const, whereas the + // allocator actually changes when it does allocations. + typename ImplType::AddResult result = m_impl.template add<BaseTranslator>(value, *this->allocator()); if (result.isNewEntry) - appendNode(*result.iterator); - return AddResult(makeIterator(*result.iterator), result.isNewEntry); + appendNode(*result.storedValue); + return AddResult(*result.storedValue, result.isNewEntry); + } + + template<typename T, size_t inlineCapacity, typename U, typename V> + typename ListHashSet<T, inlineCapacity, U, V>::iterator ListHashSet<T, inlineCapacity, U, V>::addReturnIterator(ValuePassInType value) + { + return makeIterator(add(value).storedValue); } - template<typename T, size_t inlineCapacity, typename U> - typename ListHashSet<T, inlineCapacity, U>::AddResult ListHashSet<T, inlineCapacity, U>::appendOrMoveToLast(const ValueType &value) + template<typename T, size_t inlineCapacity, typename U, typename V> + typename ListHashSet<T, inlineCapacity, U, V>::AddResult ListHashSet<T, inlineCapacity, U, V>::appendOrMoveToLast(ValuePassInType value) { createAllocatorIfNeeded(); - typename ImplType::AddResult result = m_impl.template add<BaseTranslator>(value, m_allocator.get()); - Node* node = *result.iterator; + typename ImplType::AddResult result = m_impl.template add<BaseTranslator>(value, *this->allocator()); + Node* node = *result.storedValue; if (!result.isNewEntry) unlink(node); appendNode(node); - return AddResult(makeIterator(*result.iterator), result.isNewEntry); + return AddResult(*result.storedValue, result.isNewEntry); } - template<typename T, size_t inlineCapacity, typename U> - typename ListHashSet<T, inlineCapacity, U>::AddResult ListHashSet<T, inlineCapacity, U>::prependOrMoveToFirst(const ValueType &value) + template<typename T, size_t inlineCapacity, typename U, typename V> + typename ListHashSet<T, inlineCapacity, U, V>::AddResult ListHashSet<T, inlineCapacity, U, V>::prependOrMoveToFirst(ValuePassInType value) { createAllocatorIfNeeded(); - typename ImplType::AddResult result = m_impl.template add<BaseTranslator>(value, m_allocator.get()); - Node* node = *result.iterator; + typename ImplType::AddResult result = m_impl.template add<BaseTranslator>(value, *this->allocator()); + Node* node = *result.storedValue; if (!result.isNewEntry) unlink(node); prependNode(node); - return AddResult(makeIterator(*result.iterator), result.isNewEntry); + return AddResult(*result.storedValue, result.isNewEntry); } - template<typename T, size_t inlineCapacity, typename U> - typename ListHashSet<T, inlineCapacity, U>::AddResult ListHashSet<T, inlineCapacity, U>::insertBefore(iterator it, const ValueType& newValue) + template<typename T, size_t inlineCapacity, typename U, typename V> + typename ListHashSet<T, inlineCapacity, U, V>::AddResult ListHashSet<T, inlineCapacity, U, V>::insertBefore(iterator it, ValuePassInType newValue) { createAllocatorIfNeeded(); - typename ImplType::AddResult result = m_impl.template add<BaseTranslator>(newValue, m_allocator.get()); + typename ImplType::AddResult result = m_impl.template add<BaseTranslator>(newValue, *this->allocator()); if (result.isNewEntry) - insertNodeBefore(it.node(), *result.iterator); - return AddResult(makeIterator(*result.iterator), result.isNewEntry); + insertNodeBefore(it.node(), *result.storedValue); + return AddResult(*result.storedValue, result.isNewEntry); } - template<typename T, size_t inlineCapacity, typename U> - typename ListHashSet<T, inlineCapacity, U>::AddResult ListHashSet<T, inlineCapacity, U>::insertBefore(const ValueType& beforeValue, const ValueType& newValue) + template<typename T, size_t inlineCapacity, typename U, typename V> + typename ListHashSet<T, inlineCapacity, U, V>::AddResult ListHashSet<T, inlineCapacity, U, V>::insertBefore(ValuePeekInType beforeValue, ValuePassInType newValue) { createAllocatorIfNeeded(); return insertBefore(find(beforeValue), newValue); } - template<typename T, size_t inlineCapacity, typename U> - inline void ListHashSet<T, inlineCapacity, U>::remove(iterator it) + template<typename T, size_t inlineCapacity, typename U, typename V> + inline void ListHashSet<T, inlineCapacity, U, V>::remove(iterator it) { if (it == end()) return; @@ -788,14 +870,8 @@ namespace WTF { unlinkAndDelete(it.node()); } - template<typename T, size_t inlineCapacity, typename U> - inline void ListHashSet<T, inlineCapacity, U>::remove(const ValueType& value) - { - remove(find(value)); - } - - template<typename T, size_t inlineCapacity, typename U> - inline void ListHashSet<T, inlineCapacity, U>::clear() + template<typename T, size_t inlineCapacity, typename U, typename V> + inline void ListHashSet<T, inlineCapacity, U, V>::clear() { deleteAllNodes(); m_impl.clear(); @@ -803,12 +879,42 @@ namespace WTF { m_tail = 0; } - template<typename T, size_t inlineCapacity, typename U> - void ListHashSet<T, inlineCapacity, U>::unlink(Node* node) + template<typename T, size_t inlineCapacity, typename U, typename V> + typename ListHashSet<T, inlineCapacity, U, V>::ValuePassOutType ListHashSet<T, inlineCapacity, U, V>::take(iterator it) + { + if (it == end()) + return ValueTraits::emptyValue(); + + m_impl.remove(it.node()); + ValuePassOutType result = ValueTraits::passOut(it.node()->m_value); + unlinkAndDelete(it.node()); + + return result; + } + + template<typename T, size_t inlineCapacity, typename U, typename V> + typename ListHashSet<T, inlineCapacity, U, V>::ValuePassOutType ListHashSet<T, inlineCapacity, U, V>::take(ValuePeekInType value) + { + return take(find(value)); + } + + template<typename T, size_t inlineCapacity, typename U, typename V> + typename ListHashSet<T, inlineCapacity, U, V>::ValuePassOutType ListHashSet<T, inlineCapacity, U, V>::takeFirst() + { + ASSERT(!isEmpty()); + m_impl.remove(m_head); + ValuePassOutType result = ValueTraits::passOut(m_head->m_value); + unlinkAndDelete(m_head); + + return result; + } + + template<typename T, size_t inlineCapacity, typename U, typename Allocator> + void ListHashSet<T, inlineCapacity, U, Allocator>::unlink(Node* node) { if (!node->m_prev) { ASSERT(node == m_head); - m_head = node->m_next; + m_head = node->next(); } else { ASSERT(node != m_head); node->m_prev->m_next = node->m_next; @@ -816,22 +922,22 @@ namespace WTF { if (!node->m_next) { ASSERT(node == m_tail); - m_tail = node->m_prev; + m_tail = node->prev(); } else { ASSERT(node != m_tail); node->m_next->m_prev = node->m_prev; } } - template<typename T, size_t inlineCapacity, typename U> - void ListHashSet<T, inlineCapacity, U>::unlinkAndDelete(Node* node) + template<typename T, size_t inlineCapacity, typename U, typename V> + void ListHashSet<T, inlineCapacity, U, V>::unlinkAndDelete(Node* node) { unlink(node); - node->destroy(m_allocator.get()); + node->destroy(this->allocator()); } - template<typename T, size_t inlineCapacity, typename U> - void ListHashSet<T, inlineCapacity, U>::appendNode(Node* node) + template<typename T, size_t inlineCapacity, typename U, typename V> + void ListHashSet<T, inlineCapacity, U, V>::appendNode(Node* node) { node->m_prev = m_tail; node->m_next = 0; @@ -847,8 +953,8 @@ namespace WTF { m_tail = node; } - template<typename T, size_t inlineCapacity, typename U> - void ListHashSet<T, inlineCapacity, U>::prependNode(Node* node) + template<typename T, size_t inlineCapacity, typename U, typename V> + void ListHashSet<T, inlineCapacity, U, V>::prependNode(Node* node) { node->m_prev = 0; node->m_next = m_head; @@ -861,8 +967,8 @@ namespace WTF { m_head = node; } - template<typename T, size_t inlineCapacity, typename U> - void ListHashSet<T, inlineCapacity, U>::insertNodeBefore(Node* beforeNode, Node* newNode) + template<typename T, size_t inlineCapacity, typename U, typename V> + void ListHashSet<T, inlineCapacity, U, V>::insertNodeBefore(Node* beforeNode, Node* newNode) { if (!beforeNode) return appendNode(newNode); @@ -877,59 +983,24 @@ namespace WTF { m_head = newNode; } - template<typename T, size_t inlineCapacity, typename U> - void ListHashSet<T, inlineCapacity, U>::deleteAllNodes() + template<typename T, size_t inlineCapacity, typename U, typename V> + void ListHashSet<T, inlineCapacity, U, V>::deleteAllNodes() { if (!m_head) return; - for (Node* node = m_head, *next = m_head->m_next; node; node = next, next = node ? node->m_next : 0) - node->destroy(m_allocator.get()); - } - - template<typename T, size_t inlineCapacity, typename U> - void ListHashSet<T, inlineCapacity, U>::createAllocatorIfNeeded() - { - if (!m_allocator) - m_allocator = adoptPtr(new NodeAllocator); - } - - template<typename T, size_t inlineCapacity, typename U> - inline ListHashSetReverseIterator<T, inlineCapacity, U> ListHashSet<T, inlineCapacity, U>::makeReverseIterator(Node* position) - { - return ListHashSetReverseIterator<T, inlineCapacity, U>(this, position); - } - - template<typename T, size_t inlineCapacity, typename U> - inline ListHashSetConstReverseIterator<T, inlineCapacity, U> ListHashSet<T, inlineCapacity, U>::makeConstReverseIterator(Node* position) const - { - return ListHashSetConstReverseIterator<T, inlineCapacity, U>(this, position); - } - - template<typename T, size_t inlineCapacity, typename U> - inline ListHashSetIterator<T, inlineCapacity, U> ListHashSet<T, inlineCapacity, U>::makeIterator(Node* position) - { - return ListHashSetIterator<T, inlineCapacity, U>(this, position); - } - - template<typename T, size_t inlineCapacity, typename U> - inline ListHashSetConstIterator<T, inlineCapacity, U> ListHashSet<T, inlineCapacity, U>::makeConstIterator(Node* position) const - { - return ListHashSetConstIterator<T, inlineCapacity, U>(this, position); - } - template<bool, typename ValueType, typename HashTableType> - void deleteAllValues(HashTableType& collection) - { - typedef typename HashTableType::const_iterator iterator; - iterator end = collection.end(); - for (iterator it = collection.begin(); it != end; ++it) - delete (*it)->m_value; + for (Node* node = m_head, *next = m_head->next(); node; node = next, next = node ? node->next() : 0) + node->destroy(this->allocator()); } - template<typename T, size_t inlineCapacity, typename U> - inline void deleteAllValues(const ListHashSet<T, inlineCapacity, U>& collection) + template<typename T, size_t inlineCapacity, typename U, typename V> + void ListHashSet<T, inlineCapacity, U, V>::trace(typename Allocator::Visitor* visitor) { - deleteAllValues<true, typename ListHashSet<T, inlineCapacity, U>::ValueType>(collection.m_impl); + COMPILE_ASSERT(HashTraits<T>::weakHandlingFlag == NoWeakHandlingInCollections, ListHashSetDoesNotSupportWeakness); + // This marks all the nodes and their contents live that can be + // accessed through the HashTable. That includes m_head and m_tail + // so we do not have to explicitly trace them here. + m_impl.trace(visitor); } } // namespace WTF |