Source/WTF/wtf/ListHashSet.h - Issue 14238015: Move Source/WTF/wtf to Source/wtf

Unified Diff: Source/WTF/wtf/ListHashSet.h

Issue 14238015: Move Source/WTF/wtf to Source/wtf (Closed) Base URL: svn://svn.chromium.org/blink/trunk

Patch Set: Created 7 years, 8 months ago

Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.

Jump to:

View side-by-side diff with in-line comments

Index: Source/WTF/wtf/ListHashSet.h

diff --git a/Source/WTF/wtf/ListHashSet.h b/Source/WTF/wtf/ListHashSet.h

deleted file mode 100644

index 557cad1a494c3d6489acef621276048efdf609ef..0000000000000000000000000000000000000000

--- a/Source/WTF/wtf/ListHashSet.h

+++ /dev/null

@@ -1,928 +0,0 @@

-/*

- *

- * This library is free software; you can redistribute it and/or

- * modify it under the terms of the GNU Library General Public

- * License as published by the Free Software Foundation; either

- * version 2 of the License, or (at your option) any later version.

- *

- * This library is distributed in the hope that it will be useful,

- * but WITHOUT ANY WARRANTY; without even the implied warranty of

- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU

- * Library General Public License for more details.

- *

- * You should have received a copy of the GNU Library General Public License

- * along with this library; see the file COPYING.LIB. If not, write to

- * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,

- * Boston, MA 02110-1301, USA.

- *

- */

-#ifndef WTF_ListHashSet_h

-#define WTF_ListHashSet_h

-#include <wtf/HashSet.h>

-#include <wtf/OwnPtr.h>

-#include <wtf/PassOwnPtr.h>

-namespace WTF {

- // ListHashSet: Just like HashSet, this class provides a Set

- // interface - a collection of unique objects with O(1) insertion,

- // removal and test for containership. However, it also has an

- // order - iterating it will always give back values in the order

- // in which they are added.

- // Unlike iteration of most WTF Hash data structures, iteration is

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

- void deleteAllValues(const ListHashSet<Value, inlineCapacity, HashFunctions>&);

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

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

- ListHashSet();

- ListHashSet(const ListHashSet&);

- ListHashSet& operator=(const ListHashSet&);

- ~ListHashSet();

- void swap(ListHashSet&);

- int size() const;

- int capacity() const;

- bool isEmpty() const;

- size_t sizeInBytes() const;

- iterator begin();

- iterator end();

- const_iterator begin() const;

- const_iterator end() const;

- reverse_iterator rbegin();

- reverse_iterator rend();

- const_reverse_iterator rbegin() const;

- const_reverse_iterator rend() const;

- ValueType& first();

- const ValueType& first() const;

- void removeFirst();

- ValueType& last();

- const ValueType& last() const;

- void removeLast();

- iterator find(const ValueType&);

- const_iterator find(const ValueType&) const;

- bool contains(const ValueType&) 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.

- // The HashTranslator interface is defined in HashSet.

- // FIXME: We should reverse the order of the template arguments so that callers

- // can just pass the translator let the compiler deduce T.

- template<typename T, typename HashTranslator> iterator find(const T&);

- template<typename T, typename HashTranslator> const_iterator find(const T&) const;

- template<typename T, typename HashTranslator> bool contains(const T&) const;

- // The return value of add is a pair of an iterator to the new value's location,

- // and a bool that is true if an new entry was added.

- AddResult add(const ValueType&);

- // 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&);

- // 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 insertBefore(const ValueType& beforeValue, const ValueType& newValue);

- AddResult insertBefore(iterator, const ValueType&);

- void remove(const ValueType&);

- void remove(iterator);

- void clear();

- private:

- void unlink(Node*);

- void unlinkAndDelete(Node*);

- void appendNode(Node*);

- void prependNode(Node*);

- void insertNodeBefore(Node* beforeNode, Node* newNode);

- void deleteAllNodes();

- iterator makeIterator(Node*);

- const_iterator makeConstIterator(Node*) const;

- reverse_iterator makeReverseIterator(Node*);

- const_reverse_iterator makeConstReverseIterator(Node*) const;

- friend void deleteAllValues<>(const ListHashSet&);

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

- ListHashSetNodeAllocator()

- : m_freeList(pool())

- , m_isDoneWithInitialFreeList(false)

- {

- memset(m_pool.pool, 0, sizeof(m_pool.pool));

- }

- Node* allocate()

- {

- Node* result = m_freeList;

- if (!result)

- return static_cast<Node*>(fastMalloc(sizeof(Node)));

- ASSERT(!result->m_isAllocated);

- Node* next = result->m_next;

- ASSERT(!next || !next->m_isAllocated);

- if (!next && !m_isDoneWithInitialFreeList) {

- next = result + 1;

- if (next == pastPool()) {

- m_isDoneWithInitialFreeList = true;

- next = 0;

- } else {

- ASSERT(inPool(next));

- ASSERT(!next->m_isAllocated);

- }

- m_freeList = next;

- return result;

- }

- void deallocate(Node* node)

- {

- if (inPool(node)) {

-#ifndef NDEBUG

- node->m_isAllocated = false;

-#endif

- node->m_next = m_freeList;

- m_freeList = node;

- return;

- }

- fastFree(node);

- }

- bool inPool(Node* node)

- {

- return node >= pool() && node < pastPool();

- }

- private:

- Node* pool() { return reinterpret_cast_ptr<Node*>(m_pool.pool); }

- Node* pastPool() { return pool() + m_poolSize; }

- Node* m_freeList;

- bool m_isDoneWithInitialFreeList;

- static const size_t m_poolSize = inlineCapacity;

- union {

- char pool[sizeof(Node) * m_poolSize];

- double forAlignment;

- } m_pool;

- };

- template<typename ValueArg, size_t inlineCapacity> struct ListHashSetNode {

- typedef ListHashSetNodeAllocator<ValueArg, inlineCapacity> NodeAllocator;

- ListHashSetNode(ValueArg value)

- : m_value(value)

- , m_prev(0)

- , m_next(0)

-#ifndef NDEBUG

- , m_isAllocated(true)

-#endif

- {

- }

- void* operator new(size_t, NodeAllocator* allocator)

- {

- return allocator->allocate();

- }

- void destroy(NodeAllocator* allocator)

- {

- this->~ListHashSetNode();

- allocator->deallocate(this);

- }

- ValueArg m_value;

- ListHashSetNode* m_prev;

- ListHashSetNode* m_next;

-#ifndef NDEBUG

- bool m_isAllocated;

-#endif

- };

- template<typename HashArg> struct ListHashSetNodeHashFunctions {

- template<typename T> static unsigned hash(const T& key) { return HashArg::hash(key->m_value); }

- template<typename T> static bool equal(const T& a, const T& b) { return HashArg::equal(a->m_value, b->m_value); }

- static const bool safeToCompareToEmptyOrDeleted = false;

- };

- template<typename ValueArg, size_t inlineCapacity, typename HashArg> 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 ValueType& ReferenceType;

- typedef ValueType* PointerType;

- friend class ListHashSet<ValueArg, inlineCapacity, HashArg>;

- ListHashSetIterator(const ListHashSetType* set, Node* position) : m_iterator(set, position) { }

- public:

- ListHashSetIterator() { }

- // default copy, assignment and destructor are OK

- PointerType get() const { return const_cast<PointerType>(m_iterator.get()); }

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

- // postfix -- 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; }

- operator const_iterator() const { return m_iterator; }

- private:

- Node* node() { return m_iterator.node(); }

- const_iterator m_iterator;

- };

- template<typename ValueArg, size_t inlineCapacity, typename HashArg> 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 const ValueType& ReferenceType;

- typedef const ValueType* PointerType;

- friend class ListHashSet<ValueArg, inlineCapacity, HashArg>;

- friend class ListHashSetIterator<ValueArg, inlineCapacity, HashArg>;

- ListHashSetConstIterator(const ListHashSetType* set, Node* position)

- : m_set(set)

- , m_position(position)

- {

- }

- public:

- ListHashSetConstIterator()

- {

- }

- PointerType get() const

- {

- return &m_position->m_value;

- }

- ReferenceType operator*() const { return *get(); }

- PointerType operator->() const { return get(); }

- const_iterator& operator++()

- {

- ASSERT(m_position != 0);

- m_position = m_position->m_next;

- return *this;

- }

- // postfix ++ intentionally omitted

- const_iterator& operator--()

- {

- ASSERT(m_position != m_set->m_head);

- if (!m_position)

- m_position = m_set->m_tail;

- else

- m_position = m_position->m_prev;

- return *this;

- }

- // postfix -- intentionally omitted

- // Comparison.

- bool operator==(const const_iterator& other) const

- {

- return m_position == other.m_position;

- }

- bool operator!=(const const_iterator& other) const

- {

- return m_position != other.m_position;

- }

- private:

- Node* node() { return m_position; }

- const ListHashSetType* m_set;

- Node* m_position;

- };

- template<typename ValueArg, size_t inlineCapacity, typename HashArg> 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 ValueType& ReferenceType;

- typedef ValueType* PointerType;

- friend class ListHashSet<ValueArg, inlineCapacity, HashArg>;

- ListHashSetReverseIterator(const ListHashSetType* set, Node* position) : m_iterator(set, position) { }

- public:

- ListHashSetReverseIterator() { }

- // default copy, assignment and destructor are OK

- PointerType get() const { return const_cast<PointerType>(m_iterator.get()); }

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

- // postfix -- 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; }

- operator const_reverse_iterator() const { return m_iterator; }

- private:

- Node* node() { return m_iterator.node(); }

- const_reverse_iterator m_iterator;

- };

- template<typename ValueArg, size_t inlineCapacity, typename HashArg> 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 const ValueType& ReferenceType;

- typedef const ValueType* PointerType;

- friend class ListHashSet<ValueArg, inlineCapacity, HashArg>;

- friend class ListHashSetReverseIterator<ValueArg, inlineCapacity, HashArg>;

- ListHashSetConstReverseIterator(const ListHashSetType* set, Node* position)

- : m_set(set)

- , m_position(position)

- {

- }

- public:

- ListHashSetConstReverseIterator()

- {

- }

- PointerType get() const

- {

- return &m_position->m_value;

- }

- ReferenceType operator*() const { return *get(); }

- PointerType operator->() const { return get(); }

- const_reverse_iterator& operator++()

- {

- ASSERT(m_position != 0);

- m_position = m_position->m_prev;

- return *this;

- }

- // postfix ++ intentionally omitted

- const_reverse_iterator& operator--()

- {

- ASSERT(m_position != m_set->m_tail);

- if (!m_position)

- m_position = m_set->m_head;

- else

- m_position = m_position->m_next;

- return *this;

- }

- // postfix -- intentionally omitted

- // Comparison.

- bool operator==(const const_reverse_iterator& other) const

- {

- return m_position == other.m_position;

- }

- bool operator!=(const const_reverse_iterator& other) const

- {

- return m_position != other.m_position;

- }

- private:

- Node* node() { return m_position; }

- const ListHashSetType* m_set;

- Node* m_position;

- };

- template<typename HashFunctions>

- struct ListHashSetTranslator {

- template<typename T> static unsigned hash(const T& key) { return HashFunctions::hash(key); }

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

- }

- };

- template<typename T, size_t inlineCapacity, typename U>

- inline ListHashSet<T, inlineCapacity, U>::ListHashSet()

- : m_head(0)

- , m_tail(0)

- , m_allocator(adoptPtr(new NodeAllocator))

- {

- }

- template<typename T, size_t inlineCapacity, typename U>

- inline ListHashSet<T, inlineCapacity, U>::ListHashSet(const ListHashSet& other)

- : m_head(0)

- , m_tail(0)

- , m_allocator(adoptPtr(new NodeAllocator))

- {

- const_iterator end = other.end();

- for (const_iterator it = other.begin(); it != end; ++it)

- add(*it);

- }

- template<typename T, size_t inlineCapacity, typename U>

- inline ListHashSet<T, inlineCapacity, U>& ListHashSet<T, inlineCapacity, U>::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)

- {

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

- }

- template<typename T, size_t inlineCapacity, typename U>

- inline ListHashSet<T, inlineCapacity, U>::~ListHashSet()

- {

- deleteAllNodes();

- }

- template<typename T, size_t inlineCapacity, typename U>

- inline int ListHashSet<T, inlineCapacity, U>::size() const

- {

- return m_impl.size();

- }

- template<typename T, size_t inlineCapacity, typename U>

- inline int 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) + sizeof(*m_allocator);

- result += 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()

- {

- ASSERT(!isEmpty());

- return m_head->m_value;

- }

- template<typename T, size_t inlineCapacity, typename U>

- inline void ListHashSet<T, inlineCapacity, U>::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

- {

- ASSERT(!isEmpty());

- return m_head->m_value;

- }

- template<typename T, size_t inlineCapacity, typename U>

- inline T& ListHashSet<T, inlineCapacity, U>::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

- {

- ASSERT(!isEmpty());

- return m_tail->m_value;

- }

- template<typename T, size_t inlineCapacity, typename U>

- inline void ListHashSet<T, inlineCapacity, U>::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)

- {

- ImplTypeIterator it = m_impl.template find<BaseTranslator>(value);

- if (it == m_impl.end())

- return 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(const ValueType& value) const

- {

- ImplTypeConstIterator it = m_impl.template find<BaseTranslator>(value);

- if (it == m_impl.end())

- return end();

- return makeConstIterator(*it);

- }

- template<typename Translator>

- struct ListHashSetTranslatorAdapter {

- template<typename T> static unsigned hash(const T& key) { return Translator::hash(key); }

- 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 T, typename HashTranslator>

- inline typename ListHashSet<ValueType, inlineCapacity, U>::iterator ListHashSet<ValueType, inlineCapacity, U>::find(const T& value)

- {

- ImplTypeConstIterator it = m_impl.template find<ListHashSetTranslatorAdapter<HashTranslator> >(value);

- if (it == m_impl.end())

- return end();

- return makeIterator(*it);

- }

- template<typename ValueType, size_t inlineCapacity, typename U>

- template<typename T, typename HashTranslator>

- inline typename ListHashSet<ValueType, inlineCapacity, U>::const_iterator ListHashSet<ValueType, inlineCapacity, U>::find(const T& value) const

- {

- ImplTypeConstIterator it = m_impl.template find<ListHashSetTranslatorAdapter<HashTranslator> >(value);

- if (it == m_impl.end())

- return end();

- return makeConstIterator(*it);

- }

- template<typename ValueType, size_t inlineCapacity, typename U>

- template<typename T, typename HashTranslator>

- inline bool ListHashSet<ValueType, inlineCapacity, U>::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

- {

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

- {

- typename ImplType::AddResult result = m_impl.template add<BaseTranslator>(value, m_allocator.get());

- if (result.isNewEntry)

- appendNode(*result.iterator);

- return AddResult(makeIterator(*result.iterator), result.isNewEntry);

- }

- template<typename T, size_t inlineCapacity, typename U>

- typename ListHashSet<T, inlineCapacity, U>::AddResult ListHashSet<T, inlineCapacity, U>::appendOrMoveToLast(const ValueType &value)

- {

- typename ImplType::AddResult result = m_impl.template add<BaseTranslator>(value, m_allocator.get());

- Node* node = *result.iterator;

- if (!result.isNewEntry)

- unlink(node);

- appendNode(node);

- return AddResult(makeIterator(*result.iterator), result.isNewEntry);

- }

- template<typename T, size_t inlineCapacity, typename U>

- typename ListHashSet<T, inlineCapacity, U>::AddResult ListHashSet<T, inlineCapacity, U>::prependOrMoveToFirst(const ValueType &value)

- {

- typename ImplType::AddResult result = m_impl.template add<BaseTranslator>(value, m_allocator.get());

- Node* node = *result.iterator;

- if (!result.isNewEntry)

- unlink(node);

- prependNode(node);

- return AddResult(makeIterator(*result.iterator), 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)

- {

- typename ImplType::AddResult result = m_impl.template add<BaseTranslator>(newValue, m_allocator.get());

- if (result.isNewEntry)

- insertNodeBefore(it.node(), *result.iterator);

- return AddResult(makeIterator(*result.iterator), 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)

- {

- return insertBefore(find(beforeValue), newValue);

- }

- template<typename T, size_t inlineCapacity, typename U>

- inline void ListHashSet<T, inlineCapacity, U>::remove(iterator it)

- {

- if (it == end())

- return;

- m_impl.remove(it.node());

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

- {

- deleteAllNodes();

- m_impl.clear();

- m_head = 0;

- m_tail = 0;

- }

- template<typename T, size_t inlineCapacity, typename U>

- void ListHashSet<T, inlineCapacity, U>::unlink(Node* node)

- {

- if (!node->m_prev) {

- ASSERT(node == m_head);

- m_head = node->m_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;

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

- {

- unlink(node);

- node->destroy(m_allocator.get());

- }

- template<typename T, size_t inlineCapacity, typename U>

- void ListHashSet<T, inlineCapacity, U>::appendNode(Node* node)

- {

- node->m_prev = m_tail;

- node->m_next = 0;

- if (m_tail) {

- ASSERT(m_head);

- m_tail->m_next = node;

- } else {

- ASSERT(!m_head);

- m_head = node;

- }

- m_tail = node;

- }

- template<typename T, size_t inlineCapacity, typename U>

- void ListHashSet<T, inlineCapacity, U>::prependNode(Node* node)

- {

- node->m_prev = 0;

- node->m_next = m_head;

- if (m_head)

- m_head->m_prev = node;

- else

- m_tail = node;

- m_head = node;

- }

- template<typename T, size_t inlineCapacity, typename U>

- void ListHashSet<T, inlineCapacity, U>::insertNodeBefore(Node* beforeNode, Node* newNode)

- {

- if (!beforeNode)

- return appendNode(newNode);

- newNode->m_next = beforeNode;

- newNode->m_prev = beforeNode->m_prev;

- if (beforeNode->m_prev)

- beforeNode->m_prev->m_next = newNode;

- beforeNode->m_prev = newNode;

- if (!newNode->m_prev)

- m_head = newNode;

- }

- template<typename T, size_t inlineCapacity, typename U>

- void ListHashSet<T, inlineCapacity, U>::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>

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

- }

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

- }

-} // namespace WTF

-using WTF::ListHashSet;

-#endif /* WTF_ListHashSet_h */

« no previous file with comments | « Source/WTF/wtf/IntegralTypedArrayBase.h ('k') | Source/WTF/wtf/ListRefPtr.h » ('j') | Source/config.h » ('J')