diff options
Diffstat (limited to 'Source/JavaScriptCore/wtf/ListHashSet.h')
| -rw-r--r-- | Source/JavaScriptCore/wtf/ListHashSet.h | 617 |
1 files changed, 617 insertions, 0 deletions
diff --git a/Source/JavaScriptCore/wtf/ListHashSet.h b/Source/JavaScriptCore/wtf/ListHashSet.h new file mode 100644 index 0000000..e14ac45 --- /dev/null +++ b/Source/JavaScriptCore/wtf/ListHashSet.h @@ -0,0 +1,617 @@ +/* + * Copyright (C) 2005, 2006, 2007, 2008 Apple Inc. All rights reserved. + * + * 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 "Assertions.h" +#include "HashSet.h" +#include "OwnPtr.h" +#include "StdLibExtras.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. + + // In theory it would be possible to add prepend, insertAfter + // and an append that moves the element to the end even if already present, + // but unclear yet if these are needed. + + template<typename Value, size_t inlineCapacity, typename HashFunctions> class ListHashSet; + + template<typename T> struct IdentityExtractor; + + 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> struct ListHashSetNode; + template<typename ValueArg, size_t inlineCapacity> struct ListHashSetNodeAllocator; + template<typename ValueArg, size_t inlineCapacity, typename HashArg> struct ListHashSetNodeHashFunctions; + + template<typename ValueArg, size_t inlineCapacity = 256, typename HashArg = typename DefaultHash<ValueArg>::Hash> class ListHashSet : public FastAllocBase { + private: + typedef ListHashSetNode<ValueArg, inlineCapacity> Node; + typedef ListHashSetNodeAllocator<ValueArg, inlineCapacity> NodeAllocator; + + typedef HashTraits<Node*> NodeTraits; + typedef ListHashSetNodeHashFunctions<ValueArg, inlineCapacity, HashArg> NodeHash; + + typedef HashTable<Node*, Node*, IdentityExtractor<Node*>, NodeHash, NodeTraits, NodeTraits> ImplType; + typedef HashTableIterator<Node*, Node*, IdentityExtractor<Node*>, NodeHash, NodeTraits, NodeTraits> ImplTypeIterator; + typedef HashTableConstIterator<Node*, Node*, IdentityExtractor<Node*>, 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>; + + ListHashSet(); + ListHashSet(const ListHashSet&); + ListHashSet& operator=(const ListHashSet&); + ~ListHashSet(); + + void swap(ListHashSet&); + + int size() const; + int capacity() const; + bool isEmpty() const; + + iterator begin(); + iterator end(); + const_iterator begin() const; + const_iterator end() const; + + iterator find(const ValueType&); + const_iterator find(const ValueType&) const; + bool contains(const ValueType&) const; + + // the return value is a pair of an iterator to the new value's location, + // and a bool that is true if an new entry was added + pair<iterator, bool> add(const ValueType&); + + pair<iterator, bool> insertBefore(const ValueType& beforeValue, const ValueType& newValue); + pair<iterator, bool> insertBefore(iterator it, const ValueType&); + + void remove(const ValueType&); + void remove(iterator); + void clear(); + + private: + void unlinkAndDelete(Node*); + void appendNode(Node*); + void insertNodeBefore(Node* beforeNode, Node* newNode); + void deleteAllNodes(); + iterator makeIterator(Node*); + const_iterator makeConstIterator(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); + } + + private: + Node* pool() { return reinterpret_cast_ptr<Node*>(m_pool.pool); } + Node* pastPool() { return pool() + m_poolSize; } + + bool inPool(Node* node) + { + return node >= pool() && node < pastPool(); + } + + 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 ValueArg, size_t inlineCapacity, typename HashArg> struct ListHashSetNodeHashFunctions { + typedef ListHashSetNode<ValueArg, inlineCapacity> Node; + + static unsigned hash(Node* const& key) { return HashArg::hash(key->m_value); } + static bool equal(Node* const& a, Node* const& 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 ValueType, size_t inlineCapacity, typename HashFunctions> + struct ListHashSetTranslator { + private: + typedef ListHashSetNode<ValueType, inlineCapacity> Node; + typedef ListHashSetNodeAllocator<ValueType, inlineCapacity> NodeAllocator; + public: + static unsigned hash(const ValueType& key) { return HashFunctions::hash(key); } + static bool equal(Node* const& a, const ValueType& b) { return HashFunctions::equal(a->m_value, b); } + static void translate(Node*& location, const ValueType& key, NodeAllocator* allocator) + { + location = new (allocator) Node(key); + } + }; + + template<typename T, size_t inlineCapacity, typename U> + inline ListHashSet<T, inlineCapacity, U>::ListHashSet() + : m_head(0) + , m_tail(0) + , m_allocator(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(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> + 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>::iterator ListHashSet<T, inlineCapacity, U>::find(const ValueType& value) + { + typedef ListHashSetTranslator<ValueType, inlineCapacity, HashFunctions> Translator; + ImplTypeIterator it = m_impl.template find<ValueType, Translator>(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 + { + typedef ListHashSetTranslator<ValueType, inlineCapacity, HashFunctions> Translator; + ImplTypeConstIterator it = m_impl.template find<ValueType, Translator>(value); + if (it == m_impl.end()) + return end(); + return makeConstIterator(*it); + } + + template<typename T, size_t inlineCapacity, typename U> + inline bool ListHashSet<T, inlineCapacity, U>::contains(const ValueType& value) const + { + typedef ListHashSetTranslator<ValueType, inlineCapacity, HashFunctions> Translator; + return m_impl.template contains<ValueType, Translator>(value); + } + + template<typename T, size_t inlineCapacity, typename U> + pair<typename ListHashSet<T, inlineCapacity, U>::iterator, bool> ListHashSet<T, inlineCapacity, U>::add(const ValueType &value) + { + typedef ListHashSetTranslator<ValueType, inlineCapacity, HashFunctions> Translator; + pair<typename ImplType::iterator, bool> result = m_impl.template add<ValueType, NodeAllocator*, Translator>(value, m_allocator.get()); + if (result.second) + appendNode(*result.first); + return std::make_pair(makeIterator(*result.first), result.second); + } + + template<typename T, size_t inlineCapacity, typename U> + pair<typename ListHashSet<T, inlineCapacity, U>::iterator, bool> ListHashSet<T, inlineCapacity, U>::insertBefore(iterator it, const ValueType& newValue) + { + typedef ListHashSetTranslator<ValueType, inlineCapacity, HashFunctions> Translator; + pair<typename ImplType::iterator, bool> result = m_impl.template add<ValueType, NodeAllocator*, Translator>(newValue, m_allocator.get()); + if (result.second) + insertNodeBefore(it.node(), *result.first); + return std::make_pair(makeIterator(*result.first), result.second); + + } + + template<typename T, size_t inlineCapacity, typename U> + pair<typename ListHashSet<T, inlineCapacity, U>::iterator, bool> 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>::unlinkAndDelete(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; + } + + 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>::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 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 */ |