// 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, DefaultAllocator> ImplType;
- typedef HashTableIterator<Node*, Node*, IdentityExtractor, NodeHash, NodeTraits, NodeTraits, DefaultAllocator> ImplTypeIterator;
- typedef HashTableConstIterator<Node*, Node*, IdentityExtractor, NodeHash, NodeTraits, NodeTraits, DefaultAllocator> 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 typename HashTraits<ValueType>::PeekInType ValuePeekInType;
+ typedef HashTraits<ValueType> ValueTraits;
+ typedef typename ValueTraits::PeekInType ValuePeekInType;
+ typedef typename ValueTraits::PassInType ValuePassInType;
+ typedef typename ValueTraits::PassOutType ValuePassOutType;
- typedef ListHashSetIterator<ValueType, inlineCapacity, HashArg> iterator;
- typedef ListHashSetConstIterator<ValueType, inlineCapacity, HashArg> const_iterator;
- friend class ListHashSetConstIterator<ValueType, inlineCapacity, HashArg>;
+ typedef ListHashSetIterator<ListHashSet> iterator;
+ typedef ListHashSetConstIterator<ListHashSet> const_iterator;
+ friend class ListHashSetIterator<ListHashSet>;
+ friend class ListHashSetConstIterator<ListHashSet>;
- typedef ListHashSetReverseIterator<ValueType, inlineCapacity, HashArg> reverse_iterator;
- typedef ListHashSetConstReverseIterator<ValueType, inlineCapacity, HashArg> const_reverse_iterator;
- friend class ListHashSetConstReverseIterator<ValueType, inlineCapacity, HashArg>;
+ 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) { }
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;
// 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(ValuePeekInType);
+ 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(ValuePeekInType);
+ 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(ValuePeekInType);
+ 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(ValuePeekInType);
+ AddResult prependOrMoveToFirst(ValuePassInType);
- AddResult insertBefore(ValuePeekInType beforeValue, ValuePeekInType newValue);
- AddResult insertBefore(iterator, ValuePeekInType);
+ AddResult insertBefore(ValuePeekInType beforeValue, ValuePassInType newValue);
+ AddResult insertBefore(iterator, ValuePassInType);
- void remove(ValuePeekInType);
+ 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*);
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)
+#if ENABLE(ASSERT)
+ , m_isAllocated(true)
+#endif
+ {
+ }
+
+ template <typename U>
+ ListHashSetNodeBase(const U& value)
+ : m_value(value)
+ , m_prev(0)
+ , m_next(0)
+#if ENABLE(ASSERT)
+ , m_isAllocated(true)
+#endif
+ {
+ }
+
+ public:
+ ValueArg m_value;
+ ListHashSetNodeBase* m_prev;
+ ListHashSetNodeBase* m_next;
+#if ENABLE(ASSERT)
+ 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();
+ }
+
+ private:
+ OwnPtr<ListHashSetAllocator> m_allocator;
+ };
- ListHashSetNodeAllocator()
+ 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;
void deallocate(Node* node)
{
if (inPool(node)) {
-#ifndef NDEBUG
+#if ENABLE(ASSERT)
node->m_isAllocated = false;
#endif
node->m_next = m_freeList;
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_SANITIZER_INITIAL_SIZE)
+ // 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(const 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();
}
- template <typename U>
- ListHashSetNode(const U& value)
- : m_value(value)
- , m_prev(0)
- , m_next(0)
-#ifndef NDEBUG
- , m_isAllocated(true)
-#endif
+ void setWasAlreadyDestructed()
{
+ if (NodeAllocator::isGarbageCollected && HashTraits<ValueArg>::needsDestruction)
+ this->m_prev = unlinkedNodePointer();
}
- void* operator new(size_t, NodeAllocator* allocator)
+ bool wasAlreadyDestructed() const
{
- return allocator->allocate();
+ 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 {
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() { }
ReferenceType operator*() const { return *get(); }
PointerType operator->() const { return get(); }
- iterator& operator++() { ++m_iterator; return *this; }
+ ListHashSetIterator& operator++() { ++m_iterator; return *this; }
+ ListHashSetIterator& operator--() { --m_iterator; return *this; }
- // postfix ++ intentionally omitted
-
- iterator& 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; }
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)
{
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;
}
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() { }
ReferenceType operator*() const { return *get(); }
PointerType operator->() const { return get(); }
- reverse_iterator& operator++() { ++m_iterator; return *this; }
+ ListHashSetReverseIterator& operator++() { ++m_iterator; return *this; }
+ ListHashSetReverseIterator& operator--() { --m_iterator; return *this; }
- // postfix ++ intentionally omitted
-
- reverse_iterator& 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; }
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)
{
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;
}
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>
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)
{
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(ValuePeekInType 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())
return makeIterator(*it);
}
- template<typename T, size_t inlineCapacity, typename U>
- inline typename ListHashSet<T, inlineCapacity, U>::const_iterator ListHashSet<T, inlineCapacity, U>::find(ValuePeekInType 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())
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())
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())
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(ValuePeekInType 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(ValuePeekInType 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.storedValue);
return AddResult(*result.storedValue, result.isNewEntry);
}
- template<typename T, size_t inlineCapacity, typename U>
- typename ListHashSet<T, inlineCapacity, U>::iterator ListHashSet<T, inlineCapacity, U>::addReturnIterator(ValuePeekInType value)
+ 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(ValuePeekInType 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());
+ typename ImplType::AddResult result = m_impl.template add<BaseTranslator>(value, *this->allocator());
Node* node = *result.storedValue;
if (!result.isNewEntry)
unlink(node);
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(ValuePeekInType 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());
+ typename ImplType::AddResult result = m_impl.template add<BaseTranslator>(value, *this->allocator());
Node* node = *result.storedValue;
if (!result.isNewEntry)
unlink(node);
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, ValuePeekInType 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.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(ValuePeekInType beforeValue, ValuePeekInType 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;
unlinkAndDelete(it.node());
}
- template<typename T, size_t inlineCapacity, typename U>
- inline void ListHashSet<T, inlineCapacity, U>::remove(ValuePeekInType 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();
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;
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;
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;
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);
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);
+ 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 ListHashSetReverseIterator<T, inlineCapacity, U> ListHashSet<T, inlineCapacity, U>::makeReverseIterator(Node* position)
+ template<typename T, size_t inlineCapacity, typename U, typename V>
+ void ListHashSet<T, inlineCapacity, U, V>::trace(typename Allocator::Visitor* visitor)
{
- return ListHashSetReverseIterator<T, inlineCapacity, U>(this, position);
+ 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);
}
- 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;
- }
-
- template<typename T, size_t inlineCapacity, typename U>
- inline void deleteAllValues(const ListHashSet<T, inlineCapacity, U>& collection)
- {
- deleteAllValues<true, typename ListHashSet<T, inlineCapacity, U>::ValueType>(collection.m_impl);
- }
+#if !ENABLE(OILPAN)
+ template<typename T, size_t U, typename V>
+ struct NeedsTracing<ListHashSet<T, U, V> > {
+ static const bool value = false;
+ };
+#endif
} // namespace WTF
projects / platform / framework / web / crosswalk.git / blobdiff