From cad810f21b803229eb11403f9209855525a25d57 Mon Sep 17 00:00:00 2001 From: Steve Block Date: Fri, 6 May 2011 11:45:16 +0100 Subject: Merge WebKit at r75315: Initial merge by git. Change-Id: I570314b346ce101c935ed22a626b48c2af266b84 --- Source/JavaScriptCore/wtf/ListHashSet.h | 617 ++++++++++++++++++++++++++++++++ 1 file changed, 617 insertions(+) create mode 100644 Source/JavaScriptCore/wtf/ListHashSet.h (limited to 'Source/JavaScriptCore/wtf/ListHashSet.h') 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 class ListHashSet; + + template struct IdentityExtractor; + + template + void deleteAllValues(const ListHashSet&); + + template class ListHashSetIterator; + template class ListHashSetConstIterator; + + template struct ListHashSetNode; + template struct ListHashSetNodeAllocator; + template struct ListHashSetNodeHashFunctions; + + template::Hash> class ListHashSet : public FastAllocBase { + private: + typedef ListHashSetNode Node; + typedef ListHashSetNodeAllocator NodeAllocator; + + typedef HashTraits NodeTraits; + typedef ListHashSetNodeHashFunctions NodeHash; + + typedef HashTable, NodeHash, NodeTraits, NodeTraits> ImplType; + typedef HashTableIterator, NodeHash, NodeTraits, NodeTraits> ImplTypeIterator; + typedef HashTableConstIterator, NodeHash, NodeTraits, NodeTraits> ImplTypeConstIterator; + + typedef HashArg HashFunctions; + + public: + typedef ValueArg ValueType; + typedef ListHashSetIterator iterator; + typedef ListHashSetConstIterator const_iterator; + + friend class ListHashSetConstIterator; + + 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 add(const ValueType&); + + pair insertBefore(const ValueType& beforeValue, const ValueType& newValue); + pair 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 m_allocator; + }; + + template struct ListHashSetNodeAllocator { + typedef ListHashSetNode Node; + typedef ListHashSetNodeAllocator 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(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(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 struct ListHashSetNode { + typedef ListHashSetNodeAllocator 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 struct ListHashSetNodeHashFunctions { + typedef ListHashSetNode 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 class ListHashSetIterator { + private: + typedef ListHashSet ListHashSetType; + typedef ListHashSetIterator iterator; + typedef ListHashSetConstIterator const_iterator; + typedef ListHashSetNode Node; + typedef ValueArg ValueType; + typedef ValueType& ReferenceType; + typedef ValueType* PointerType; + + friend class ListHashSet; + + 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(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 class ListHashSetConstIterator { + private: + typedef ListHashSet ListHashSetType; + typedef ListHashSetIterator iterator; + typedef ListHashSetConstIterator const_iterator; + typedef ListHashSetNode Node; + typedef ValueArg ValueType; + typedef const ValueType& ReferenceType; + typedef const ValueType* PointerType; + + friend class ListHashSet; + friend class ListHashSetIterator; + + 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 + struct ListHashSetTranslator { + private: + typedef ListHashSetNode Node; + typedef ListHashSetNodeAllocator 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 + inline ListHashSet::ListHashSet() + : m_head(0) + , m_tail(0) + , m_allocator(new NodeAllocator) + { + } + + template + inline ListHashSet::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 + inline ListHashSet& ListHashSet::operator=(const ListHashSet& other) + { + ListHashSet tmp(other); + swap(tmp); + return *this; + } + + template + inline void ListHashSet::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 + inline ListHashSet::~ListHashSet() + { + deleteAllNodes(); + } + + template + inline int ListHashSet::size() const + { + return m_impl.size(); + } + + template + inline int ListHashSet::capacity() const + { + return m_impl.capacity(); + } + + template + inline bool ListHashSet::isEmpty() const + { + return m_impl.isEmpty(); + } + + template + inline typename ListHashSet::iterator ListHashSet::begin() + { + return makeIterator(m_head); + } + + template + inline typename ListHashSet::iterator ListHashSet::end() + { + return makeIterator(0); + } + + template + inline typename ListHashSet::const_iterator ListHashSet::begin() const + { + return makeConstIterator(m_head); + } + + template + inline typename ListHashSet::const_iterator ListHashSet::end() const + { + return makeConstIterator(0); + } + + template + inline typename ListHashSet::iterator ListHashSet::find(const ValueType& value) + { + typedef ListHashSetTranslator Translator; + ImplTypeIterator it = m_impl.template find(value); + if (it == m_impl.end()) + return end(); + return makeIterator(*it); + } + + template + inline typename ListHashSet::const_iterator ListHashSet::find(const ValueType& value) const + { + typedef ListHashSetTranslator Translator; + ImplTypeConstIterator it = m_impl.template find(value); + if (it == m_impl.end()) + return end(); + return makeConstIterator(*it); + } + + template + inline bool ListHashSet::contains(const ValueType& value) const + { + typedef ListHashSetTranslator Translator; + return m_impl.template contains(value); + } + + template + pair::iterator, bool> ListHashSet::add(const ValueType &value) + { + typedef ListHashSetTranslator Translator; + pair result = m_impl.template add(value, m_allocator.get()); + if (result.second) + appendNode(*result.first); + return std::make_pair(makeIterator(*result.first), result.second); + } + + template + pair::iterator, bool> ListHashSet::insertBefore(iterator it, const ValueType& newValue) + { + typedef ListHashSetTranslator Translator; + pair result = m_impl.template add(newValue, m_allocator.get()); + if (result.second) + insertNodeBefore(it.node(), *result.first); + return std::make_pair(makeIterator(*result.first), result.second); + + } + + template + pair::iterator, bool> ListHashSet::insertBefore(const ValueType& beforeValue, const ValueType& newValue) + { + return insertBefore(find(beforeValue), newValue); + } + + template + inline void ListHashSet::remove(iterator it) + { + if (it == end()) + return; + m_impl.remove(it.node()); + unlinkAndDelete(it.node()); + } + + template + inline void ListHashSet::remove(const ValueType& value) + { + remove(find(value)); + } + + template + inline void ListHashSet::clear() + { + deleteAllNodes(); + m_impl.clear(); + m_head = 0; + m_tail = 0; + } + + template + void ListHashSet::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 + void ListHashSet::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 + void ListHashSet::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 + void ListHashSet::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 + inline ListHashSetIterator ListHashSet::makeIterator(Node* position) + { + return ListHashSetIterator(this, position); + } + + template + inline ListHashSetConstIterator ListHashSet::makeConstIterator(Node* position) const + { + return ListHashSetConstIterator(this, position); + } + + template + 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 + inline void deleteAllValues(const ListHashSet& collection) + { + deleteAllValues::ValueType>(collection.m_impl); + } + +} // namespace WTF + +using WTF::ListHashSet; + +#endif /* WTF_ListHashSet_h */ -- cgit v1.1