15c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/* 2926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) * Copyright (C) 2005, 2006, 2007, 2008, 2011, 2012 Apple Inc. All rights reserved. 35c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Copyright (C) 2011, Benjamin Poulain <ikipou@gmail.com> 45c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 55c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * This library is free software; you can redistribute it and/or 65c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * modify it under the terms of the GNU Library General Public 75c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * License as published by the Free Software Foundation; either 85c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * version 2 of the License, or (at your option) any later version. 95c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * This library is distributed in the hope that it will be useful, 115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * but WITHOUT ANY WARRANTY; without even the implied warranty of 125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Library General Public License for more details. 145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * You should have received a copy of the GNU Library General Public License 165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * along with this library; see the file COPYING.LIB. If not, write to 175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, 185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Boston, MA 02110-1301, USA. 195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#ifndef WTF_ListHashSet_h 235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#define WTF_ListHashSet_h 245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 25591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch#include "wtf/HashSet.h" 26591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch#include "wtf/OwnPtr.h" 27591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch#include "wtf/PassOwnPtr.h" 285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)namespace WTF { 305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // ListHashSet: Just like HashSet, this class provides a Set 325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // interface - a collection of unique objects with O(1) insertion, 335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // removal and test for containership. However, it also has an 345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // order - iterating it will always give back values in the order 355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // in which they are added. 365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Unlike iteration of most WTF Hash data structures, iteration is 385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // guaranteed safe against mutation of the ListHashSet, except for 395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // removal of the item currently pointed to by a given iterator. 405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename Value, size_t inlineCapacity, typename HashFunctions> class ListHashSet; 425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename Value, size_t inlineCapacity, typename HashFunctions> 445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void deleteAllValues(const ListHashSet<Value, inlineCapacity, HashFunctions>&); 455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename ValueArg, size_t inlineCapacity, typename HashArg> class ListHashSetIterator; 475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename ValueArg, size_t inlineCapacity, typename HashArg> class ListHashSetConstIterator; 485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename ValueArg, size_t inlineCapacity, typename HashArg> class ListHashSetReverseIterator; 495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename ValueArg, size_t inlineCapacity, typename HashArg> class ListHashSetConstReverseIterator; 505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename ValueArg, size_t inlineCapacity> struct ListHashSetNode; 525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename ValueArg, size_t inlineCapacity> struct ListHashSetNodeAllocator; 535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename HashArg> struct ListHashSetNodeHashFunctions; 555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename HashArg> struct ListHashSetTranslator; 565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename ValueArg, size_t inlineCapacity = 256, typename HashArg = typename DefaultHash<ValueArg>::Hash> class ListHashSet { 585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) WTF_MAKE_FAST_ALLOCATED; 595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) private: 605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef ListHashSetNode<ValueArg, inlineCapacity> Node; 615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef ListHashSetNodeAllocator<ValueArg, inlineCapacity> NodeAllocator; 625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef HashTraits<Node*> NodeTraits; 645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef ListHashSetNodeHashFunctions<HashArg> NodeHash; 655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef ListHashSetTranslator<HashArg> BaseTranslator; 665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef HashTable<Node*, Node*, IdentityExtractor, NodeHash, NodeTraits, NodeTraits> ImplType; 685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef HashTableIterator<Node*, Node*, IdentityExtractor, NodeHash, NodeTraits, NodeTraits> ImplTypeIterator; 695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef HashTableConstIterator<Node*, Node*, IdentityExtractor, NodeHash, NodeTraits, NodeTraits> ImplTypeConstIterator; 705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef HashArg HashFunctions; 725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) public: 745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef ValueArg ValueType; 755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef ListHashSetIterator<ValueType, inlineCapacity, HashArg> iterator; 775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef ListHashSetConstIterator<ValueType, inlineCapacity, HashArg> const_iterator; 785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) friend class ListHashSetConstIterator<ValueType, inlineCapacity, HashArg>; 795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef ListHashSetReverseIterator<ValueType, inlineCapacity, HashArg> reverse_iterator; 815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef ListHashSetConstReverseIterator<ValueType, inlineCapacity, HashArg> const_reverse_iterator; 825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) friend class ListHashSetConstReverseIterator<ValueType, inlineCapacity, HashArg>; 835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef HashTableAddResult<iterator> AddResult; 855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ListHashSet(); 875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ListHashSet(const ListHashSet&); 885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ListHashSet& operator=(const ListHashSet&); 895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ~ListHashSet(); 905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void swap(ListHashSet&); 925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 9351b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) unsigned size() const; 9451b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) unsigned capacity() const; 955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool isEmpty() const; 965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) size_t sizeInBytes() const; 985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) iterator begin(); 1005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) iterator end(); 1015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const_iterator begin() const; 1025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const_iterator end() const; 1035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) reverse_iterator rbegin(); 1055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) reverse_iterator rend(); 1065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const_reverse_iterator rbegin() const; 1075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const_reverse_iterator rend() const; 1085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ValueType& first(); 1105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const ValueType& first() const; 111926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) void removeFirst(); 1125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ValueType& last(); 1145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const ValueType& last() const; 1155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void removeLast(); 1165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) iterator find(const ValueType&); 1185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const_iterator find(const ValueType&) const; 1195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool contains(const ValueType&) const; 1205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // An alternate version of find() that finds the object by hashing and comparing 1225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // with some other type, to avoid the cost of type conversion. 1235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // The HashTranslator interface is defined in HashSet. 12451b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) template<typename HashTranslator, typename T> iterator find(const T&); 12551b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) template<typename HashTranslator, typename T> const_iterator find(const T&) const; 12651b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) template<typename HashTranslator, typename T> bool contains(const T&) const; 1275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 12802772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch // The return value of add is a pair of an iterator to the new value's location, 1295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // and a bool that is true if an new entry was added. 1305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) AddResult add(const ValueType&); 1315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 132926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) // Add the value to the end of the collection. If the value was already in 133926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) // the list, it is moved to the end. 134926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) AddResult appendOrMoveToLast(const ValueType&); 135926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 136926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) // Add the value to the beginning of the collection. If the value was already in 137926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) // the list, it is moved to the beginning. 138926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) AddResult prependOrMoveToFirst(const ValueType&); 139926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 1405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) AddResult insertBefore(const ValueType& beforeValue, const ValueType& newValue); 1415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) AddResult insertBefore(iterator, const ValueType&); 1425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void remove(const ValueType&); 1445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void remove(iterator); 1455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void clear(); 1465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) private: 148926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) void unlink(Node*); 1495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void unlinkAndDelete(Node*); 1505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void appendNode(Node*); 151926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) void prependNode(Node*); 1525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void insertNodeBefore(Node* beforeNode, Node* newNode); 1535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void deleteAllNodes(); 154a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) void createAllocatorIfNeeded(); 15502772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 1565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) iterator makeIterator(Node*); 1575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const_iterator makeConstIterator(Node*) const; 1585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) reverse_iterator makeReverseIterator(Node*); 1595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const_reverse_iterator makeConstReverseIterator(Node*) const; 1605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) friend void deleteAllValues<>(const ListHashSet&); 1625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ImplType m_impl; 1645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Node* m_head; 1655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Node* m_tail; 1665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) OwnPtr<NodeAllocator> m_allocator; 1675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 1685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename ValueArg, size_t inlineCapacity> struct ListHashSetNodeAllocator { 1705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef ListHashSetNode<ValueArg, inlineCapacity> Node; 1715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef ListHashSetNodeAllocator<ValueArg, inlineCapacity> NodeAllocator; 1725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 17302772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch ListHashSetNodeAllocator() 1745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) : m_freeList(pool()) 1755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) , m_isDoneWithInitialFreeList(false) 17602772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch { 1775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) memset(m_pool.pool, 0, sizeof(m_pool.pool)); 1785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Node* allocate() 18102772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch { 1825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Node* result = m_freeList; 1835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!result) 1855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return static_cast<Node*>(fastMalloc(sizeof(Node))); 1865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(!result->m_isAllocated); 1885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Node* next = result->m_next; 1905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(!next || !next->m_isAllocated); 1915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!next && !m_isDoneWithInitialFreeList) { 1925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) next = result + 1; 1935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (next == pastPool()) { 1945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_isDoneWithInitialFreeList = true; 1955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) next = 0; 1965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else { 1975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(inPool(next)); 1985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(!next->m_isAllocated); 1995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_freeList = next; 2025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return result; 2045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 20602772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch void deallocate(Node* node) 2075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 2085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (inPool(node)) { 2095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#ifndef NDEBUG 2105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) node->m_isAllocated = false; 2115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 2125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) node->m_next = m_freeList; 2135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_freeList = node; 2145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 2155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) fastFree(node); 2185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool inPool(Node* node) 2215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 2225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return node >= pool() && node < pastPool(); 2235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) private: 2265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Node* pool() { return reinterpret_cast_ptr<Node*>(m_pool.pool); } 2275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Node* pastPool() { return pool() + m_poolSize; } 2285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Node* m_freeList; 2305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool m_isDoneWithInitialFreeList; 2315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const size_t m_poolSize = inlineCapacity; 2325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) union { 2335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) char pool[sizeof(Node) * m_poolSize]; 2345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) double forAlignment; 2355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } m_pool; 2365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 2375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename ValueArg, size_t inlineCapacity> struct ListHashSetNode { 2395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef ListHashSetNodeAllocator<ValueArg, inlineCapacity> NodeAllocator; 2405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ListHashSetNode(ValueArg value) 2425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) : m_value(value) 2435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) , m_prev(0) 2445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) , m_next(0) 2455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#ifndef NDEBUG 2465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) , m_isAllocated(true) 2475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 2485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 2495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void* operator new(size_t, NodeAllocator* allocator) 2525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 2535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return allocator->allocate(); 2545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void destroy(NodeAllocator* allocator) 2565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 2575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this->~ListHashSetNode(); 2585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) allocator->deallocate(this); 2595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ValueArg m_value; 2625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ListHashSetNode* m_prev; 2635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ListHashSetNode* m_next; 2645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#ifndef NDEBUG 2665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool m_isAllocated; 2675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 2685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 2695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename HashArg> struct ListHashSetNodeHashFunctions { 2715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T> static unsigned hash(const T& key) { return HashArg::hash(key->m_value); } 2725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T> static bool equal(const T& a, const T& b) { return HashArg::equal(a->m_value, b->m_value); } 2735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const bool safeToCompareToEmptyOrDeleted = false; 2745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 2755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename ValueArg, size_t inlineCapacity, typename HashArg> class ListHashSetIterator { 2775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) private: 2785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef ListHashSet<ValueArg, inlineCapacity, HashArg> ListHashSetType; 2795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef ListHashSetIterator<ValueArg, inlineCapacity, HashArg> iterator; 2805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef ListHashSetConstIterator<ValueArg, inlineCapacity, HashArg> const_iterator; 2815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef ListHashSetNode<ValueArg, inlineCapacity> Node; 2825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef ValueArg ValueType; 2835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef ValueType& ReferenceType; 2845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef ValueType* PointerType; 2855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) friend class ListHashSet<ValueArg, inlineCapacity, HashArg>; 2875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ListHashSetIterator(const ListHashSetType* set, Node* position) : m_iterator(set, position) { } 2895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) public: 2915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ListHashSetIterator() { } 2925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // default copy, assignment and destructor are OK 2945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) PointerType get() const { return const_cast<PointerType>(m_iterator.get()); } 2965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ReferenceType operator*() const { return *get(); } 2975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) PointerType operator->() const { return get(); } 2985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) iterator& operator++() { ++m_iterator; return *this; } 3005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // postfix ++ intentionally omitted 3025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) iterator& operator--() { --m_iterator; return *this; } 3045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // postfix -- intentionally omitted 3065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Comparison. 3085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool operator==(const iterator& other) const { return m_iterator == other.m_iterator; } 3095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool operator!=(const iterator& other) const { return m_iterator != other.m_iterator; } 3105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) operator const_iterator() const { return m_iterator; } 3125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) private: 3145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Node* node() { return m_iterator.node(); } 3155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const_iterator m_iterator; 3175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 3185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename ValueArg, size_t inlineCapacity, typename HashArg> class ListHashSetConstIterator { 3205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) private: 3215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef ListHashSet<ValueArg, inlineCapacity, HashArg> ListHashSetType; 3225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef ListHashSetIterator<ValueArg, inlineCapacity, HashArg> iterator; 3235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef ListHashSetConstIterator<ValueArg, inlineCapacity, HashArg> const_iterator; 3245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef ListHashSetNode<ValueArg, inlineCapacity> Node; 3255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef ValueArg ValueType; 3265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef const ValueType& ReferenceType; 3275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef const ValueType* PointerType; 3285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) friend class ListHashSet<ValueArg, inlineCapacity, HashArg>; 3305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) friend class ListHashSetIterator<ValueArg, inlineCapacity, HashArg>; 3315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ListHashSetConstIterator(const ListHashSetType* set, Node* position) 3335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) : m_set(set) 3345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) , m_position(position) 3355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 3365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) public: 3395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ListHashSetConstIterator() 3405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 3415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) PointerType get() const 3445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 3455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return &m_position->m_value; 3465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ReferenceType operator*() const { return *get(); } 3485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) PointerType operator->() const { return get(); } 3495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const_iterator& operator++() 3515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 3525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(m_position != 0); 3535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_position = m_position->m_next; 3545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return *this; 3555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // postfix ++ intentionally omitted 3585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const_iterator& operator--() 3605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 3615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(m_position != m_set->m_head); 3625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!m_position) 3635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_position = m_set->m_tail; 3645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) else 3655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_position = m_position->m_prev; 3665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return *this; 3675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // postfix -- intentionally omitted 3705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Comparison. 3725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool operator==(const const_iterator& other) const 3735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 3745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return m_position == other.m_position; 3755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool operator!=(const const_iterator& other) const 3775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 3785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return m_position != other.m_position; 3795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) private: 3825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Node* node() { return m_position; } 3835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const ListHashSetType* m_set; 3855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Node* m_position; 3865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 3875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename ValueArg, size_t inlineCapacity, typename HashArg> class ListHashSetReverseIterator { 3895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) private: 3905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef ListHashSet<ValueArg, inlineCapacity, HashArg> ListHashSetType; 3915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef ListHashSetReverseIterator<ValueArg, inlineCapacity, HashArg> reverse_iterator; 3925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef ListHashSetConstReverseIterator<ValueArg, inlineCapacity, HashArg> const_reverse_iterator; 3935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef ListHashSetNode<ValueArg, inlineCapacity> Node; 3945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef ValueArg ValueType; 3955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef ValueType& ReferenceType; 3965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef ValueType* PointerType; 3975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) friend class ListHashSet<ValueArg, inlineCapacity, HashArg>; 3995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ListHashSetReverseIterator(const ListHashSetType* set, Node* position) : m_iterator(set, position) { } 4015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) public: 4035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ListHashSetReverseIterator() { } 4045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // default copy, assignment and destructor are OK 4065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) PointerType get() const { return const_cast<PointerType>(m_iterator.get()); } 4085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ReferenceType operator*() const { return *get(); } 4095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) PointerType operator->() const { return get(); } 4105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) reverse_iterator& operator++() { ++m_iterator; return *this; } 4125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // postfix ++ intentionally omitted 4145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) reverse_iterator& operator--() { --m_iterator; return *this; } 4165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // postfix -- intentionally omitted 4185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Comparison. 4205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool operator==(const reverse_iterator& other) const { return m_iterator == other.m_iterator; } 4215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool operator!=(const reverse_iterator& other) const { return m_iterator != other.m_iterator; } 4225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) operator const_reverse_iterator() const { return m_iterator; } 4245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) private: 4265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Node* node() { return m_iterator.node(); } 4275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const_reverse_iterator m_iterator; 4295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 4305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename ValueArg, size_t inlineCapacity, typename HashArg> class ListHashSetConstReverseIterator { 4325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) private: 4335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef ListHashSet<ValueArg, inlineCapacity, HashArg> ListHashSetType; 4345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef ListHashSetReverseIterator<ValueArg, inlineCapacity, HashArg> reverse_iterator; 4355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef ListHashSetConstReverseIterator<ValueArg, inlineCapacity, HashArg> const_reverse_iterator; 4365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef ListHashSetNode<ValueArg, inlineCapacity> Node; 4375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef ValueArg ValueType; 4385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef const ValueType& ReferenceType; 4395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef const ValueType* PointerType; 4405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) friend class ListHashSet<ValueArg, inlineCapacity, HashArg>; 4425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) friend class ListHashSetReverseIterator<ValueArg, inlineCapacity, HashArg>; 4435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ListHashSetConstReverseIterator(const ListHashSetType* set, Node* position) 4455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) : m_set(set) 4465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) , m_position(position) 4475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 4485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) public: 4515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ListHashSetConstReverseIterator() 4525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 4535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) PointerType get() const 4565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 4575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return &m_position->m_value; 4585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ReferenceType operator*() const { return *get(); } 4605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) PointerType operator->() const { return get(); } 4615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const_reverse_iterator& operator++() 4635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 4645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(m_position != 0); 4655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_position = m_position->m_prev; 4665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return *this; 4675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // postfix ++ intentionally omitted 4705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const_reverse_iterator& operator--() 4725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 4735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(m_position != m_set->m_tail); 4745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!m_position) 4755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_position = m_set->m_head; 4765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) else 4775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_position = m_position->m_next; 4785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return *this; 4795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // postfix -- intentionally omitted 4825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Comparison. 4845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool operator==(const const_reverse_iterator& other) const 4855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 4865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return m_position == other.m_position; 4875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool operator!=(const const_reverse_iterator& other) const 4895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 4905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return m_position != other.m_position; 4915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) private: 4945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Node* node() { return m_position; } 4955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const ListHashSetType* m_set; 4975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Node* m_position; 4985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 4995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename HashFunctions> 5015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) struct ListHashSetTranslator { 5025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T> static unsigned hash(const T& key) { return HashFunctions::hash(key); } 5035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T, typename U> static bool equal(const T& a, const U& b) { return HashFunctions::equal(a->m_value, b); } 5045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T, typename U, typename V> static void translate(T*& location, const U& key, const V& allocator) 5055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 5065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) location = new (allocator) T(key); 5075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 5085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 5095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename U> 5115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline ListHashSet<T, inlineCapacity, U>::ListHashSet() 5125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) : m_head(0) 5135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) , m_tail(0) 5145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 5155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 5165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename U> 5185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline ListHashSet<T, inlineCapacity, U>::ListHashSet(const ListHashSet& other) 5195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) : m_head(0) 5205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) , m_tail(0) 5215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 5225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const_iterator end = other.end(); 5235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (const_iterator it = other.begin(); it != end; ++it) 5245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) add(*it); 5255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 5265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename U> 5285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline ListHashSet<T, inlineCapacity, U>& ListHashSet<T, inlineCapacity, U>::operator=(const ListHashSet& other) 5295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 5305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ListHashSet tmp(other); 5315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) swap(tmp); 5325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return *this; 5335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 5345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename U> 5365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline void ListHashSet<T, inlineCapacity, U>::swap(ListHashSet& other) 5375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 5385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_impl.swap(other.m_impl); 5395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) std::swap(m_head, other.m_head); 5405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) std::swap(m_tail, other.m_tail); 5415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_allocator.swap(other.m_allocator); 5425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 5435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename U> 5455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline ListHashSet<T, inlineCapacity, U>::~ListHashSet() 5465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 5475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) deleteAllNodes(); 5485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 5495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename U> 55151b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) inline unsigned ListHashSet<T, inlineCapacity, U>::size() const 5525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 55302772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch return m_impl.size(); 5545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 5555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename U> 55751b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) inline unsigned ListHashSet<T, inlineCapacity, U>::capacity() const 5585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 55902772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch return m_impl.capacity(); 5605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 5615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename U> 5635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline bool ListHashSet<T, inlineCapacity, U>::isEmpty() const 5645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 56502772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch return m_impl.isEmpty(); 5665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 5675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename U> 5695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) size_t ListHashSet<T, inlineCapacity, U>::sizeInBytes() const 5705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 571a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) size_t result = sizeof(*this); 572a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) if (!m_allocator) 573a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) return result; 574a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) result += sizeof(*m_allocator) + (sizeof(typename ImplType::ValueType) * m_impl.capacity()); 5755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (Node* node = m_head; node; node = node->m_next) { 5765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!m_allocator->inPool(node)) 5775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) result += sizeof(Node); 5785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 5795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return result; 5805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 5815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename U> 5835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline typename ListHashSet<T, inlineCapacity, U>::iterator ListHashSet<T, inlineCapacity, U>::begin() 5845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 58502772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch return makeIterator(m_head); 5865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 5875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename U> 5895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline typename ListHashSet<T, inlineCapacity, U>::iterator ListHashSet<T, inlineCapacity, U>::end() 5905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 5915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return makeIterator(0); 5925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 5935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename U> 5955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline typename ListHashSet<T, inlineCapacity, U>::const_iterator ListHashSet<T, inlineCapacity, U>::begin() const 5965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 59702772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch return makeConstIterator(m_head); 5985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 5995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename U> 6015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline typename ListHashSet<T, inlineCapacity, U>::const_iterator ListHashSet<T, inlineCapacity, U>::end() const 6025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 60302772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch return makeConstIterator(0); 6045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 6055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename U> 6075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline typename ListHashSet<T, inlineCapacity, U>::reverse_iterator ListHashSet<T, inlineCapacity, U>::rbegin() 6085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 60902772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch return makeReverseIterator(m_tail); 6105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 6115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename U> 6135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline typename ListHashSet<T, inlineCapacity, U>::reverse_iterator ListHashSet<T, inlineCapacity, U>::rend() 6145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 6155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return makeReverseIterator(0); 6165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 6175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename U> 6195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline typename ListHashSet<T, inlineCapacity, U>::const_reverse_iterator ListHashSet<T, inlineCapacity, U>::rbegin() const 6205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 62102772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch return makeConstReverseIterator(m_tail); 6225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 6235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename U> 6255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline typename ListHashSet<T, inlineCapacity, U>::const_reverse_iterator ListHashSet<T, inlineCapacity, U>::rend() const 6265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 62702772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch return makeConstReverseIterator(0); 6285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 6295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename U> 6315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline T& ListHashSet<T, inlineCapacity, U>::first() 6325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 6335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(!isEmpty()); 6345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return m_head->m_value; 6355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 6365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename U> 638926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) inline void ListHashSet<T, inlineCapacity, U>::removeFirst() 639926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) { 640926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) ASSERT(!isEmpty()); 641926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) m_impl.remove(m_head); 642926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) unlinkAndDelete(m_head); 643926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) } 644926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 645926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) template<typename T, size_t inlineCapacity, typename U> 6465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline const T& ListHashSet<T, inlineCapacity, U>::first() const 6475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 6485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(!isEmpty()); 6495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return m_head->m_value; 6505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 6515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename U> 6535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline T& ListHashSet<T, inlineCapacity, U>::last() 6545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 6555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(!isEmpty()); 6565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return m_tail->m_value; 6575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 6585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename U> 6605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline const T& ListHashSet<T, inlineCapacity, U>::last() const 6615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 6625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(!isEmpty()); 6635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return m_tail->m_value; 6645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 6655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename U> 6675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline void ListHashSet<T, inlineCapacity, U>::removeLast() 6685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 6695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(!isEmpty()); 6705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_impl.remove(m_tail); 6715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) unlinkAndDelete(m_tail); 6725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 6735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename U> 6755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline typename ListHashSet<T, inlineCapacity, U>::iterator ListHashSet<T, inlineCapacity, U>::find(const ValueType& value) 6765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 6775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ImplTypeIterator it = m_impl.template find<BaseTranslator>(value); 6785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (it == m_impl.end()) 6795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return end(); 68002772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch return makeIterator(*it); 6815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 6825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename U> 6845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline typename ListHashSet<T, inlineCapacity, U>::const_iterator ListHashSet<T, inlineCapacity, U>::find(const ValueType& value) const 6855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 6865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ImplTypeConstIterator it = m_impl.template find<BaseTranslator>(value); 6875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (it == m_impl.end()) 6885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return end(); 6895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return makeConstIterator(*it); 6905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 6915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename Translator> 6935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) struct ListHashSetTranslatorAdapter { 6945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T> static unsigned hash(const T& key) { return Translator::hash(key); } 6955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T, typename U> static bool equal(const T& a, const U& b) { return Translator::equal(a->m_value, b); } 6965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 6975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename ValueType, size_t inlineCapacity, typename U> 69951b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) template<typename HashTranslator, typename T> 7005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline typename ListHashSet<ValueType, inlineCapacity, U>::iterator ListHashSet<ValueType, inlineCapacity, U>::find(const T& value) 7015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 7025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ImplTypeConstIterator it = m_impl.template find<ListHashSetTranslatorAdapter<HashTranslator> >(value); 7035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (it == m_impl.end()) 7045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return end(); 7055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return makeIterator(*it); 7065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 7075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename ValueType, size_t inlineCapacity, typename U> 70951b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) template<typename HashTranslator, typename T> 7105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline typename ListHashSet<ValueType, inlineCapacity, U>::const_iterator ListHashSet<ValueType, inlineCapacity, U>::find(const T& value) const 7115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 7125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ImplTypeConstIterator it = m_impl.template find<ListHashSetTranslatorAdapter<HashTranslator> >(value); 7135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (it == m_impl.end()) 7145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return end(); 7155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return makeConstIterator(*it); 7165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 7175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename ValueType, size_t inlineCapacity, typename U> 71951b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) template<typename HashTranslator, typename T> 7205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline bool ListHashSet<ValueType, inlineCapacity, U>::contains(const T& value) const 7215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 7225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return m_impl.template contains<ListHashSetTranslatorAdapter<HashTranslator> >(value); 7235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 7245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename U> 7265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline bool ListHashSet<T, inlineCapacity, U>::contains(const ValueType& value) const 7275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 7285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return m_impl.template contains<BaseTranslator>(value); 7295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 7305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename U> 7325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typename ListHashSet<T, inlineCapacity, U>::AddResult ListHashSet<T, inlineCapacity, U>::add(const ValueType &value) 7335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 734a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) createAllocatorIfNeeded(); 7355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typename ImplType::AddResult result = m_impl.template add<BaseTranslator>(value, m_allocator.get()); 7365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (result.isNewEntry) 7375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) appendNode(*result.iterator); 7385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return AddResult(makeIterator(*result.iterator), result.isNewEntry); 7395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 7405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename U> 742926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) typename ListHashSet<T, inlineCapacity, U>::AddResult ListHashSet<T, inlineCapacity, U>::appendOrMoveToLast(const ValueType &value) 743926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) { 744a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) createAllocatorIfNeeded(); 745926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) typename ImplType::AddResult result = m_impl.template add<BaseTranslator>(value, m_allocator.get()); 746926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) Node* node = *result.iterator; 747926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) if (!result.isNewEntry) 748926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) unlink(node); 749926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) appendNode(node); 750926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) return AddResult(makeIterator(*result.iterator), result.isNewEntry); 751926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) } 752926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 753926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) template<typename T, size_t inlineCapacity, typename U> 754926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) typename ListHashSet<T, inlineCapacity, U>::AddResult ListHashSet<T, inlineCapacity, U>::prependOrMoveToFirst(const ValueType &value) 755926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) { 756a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) createAllocatorIfNeeded(); 757926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) typename ImplType::AddResult result = m_impl.template add<BaseTranslator>(value, m_allocator.get()); 758926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) Node* node = *result.iterator; 759926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) if (!result.isNewEntry) 760926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) unlink(node); 761926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) prependNode(node); 762926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) return AddResult(makeIterator(*result.iterator), result.isNewEntry); 763926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) } 764926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 765926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) template<typename T, size_t inlineCapacity, typename U> 7665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typename ListHashSet<T, inlineCapacity, U>::AddResult ListHashSet<T, inlineCapacity, U>::insertBefore(iterator it, const ValueType& newValue) 7675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 768a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) createAllocatorIfNeeded(); 7695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typename ImplType::AddResult result = m_impl.template add<BaseTranslator>(newValue, m_allocator.get()); 7705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (result.isNewEntry) 7715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) insertNodeBefore(it.node(), *result.iterator); 7725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return AddResult(makeIterator(*result.iterator), result.isNewEntry); 7735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 7745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename U> 7765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typename ListHashSet<T, inlineCapacity, U>::AddResult ListHashSet<T, inlineCapacity, U>::insertBefore(const ValueType& beforeValue, const ValueType& newValue) 7775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 778a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) createAllocatorIfNeeded(); 77902772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch return insertBefore(find(beforeValue), newValue); 7805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 7815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename U> 7835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline void ListHashSet<T, inlineCapacity, U>::remove(iterator it) 7845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 7855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (it == end()) 7865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 7875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_impl.remove(it.node()); 7885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) unlinkAndDelete(it.node()); 7895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 7905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename U> 7925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline void ListHashSet<T, inlineCapacity, U>::remove(const ValueType& value) 7935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 7945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) remove(find(value)); 7955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 7965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename U> 7985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline void ListHashSet<T, inlineCapacity, U>::clear() 7995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 8005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) deleteAllNodes(); 80102772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch m_impl.clear(); 8025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_head = 0; 8035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_tail = 0; 8045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 8055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 8065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename U> 807926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) void ListHashSet<T, inlineCapacity, U>::unlink(Node* node) 8085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 8095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!node->m_prev) { 8105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(node == m_head); 8115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_head = node->m_next; 8125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else { 8135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(node != m_head); 8145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) node->m_prev->m_next = node->m_next; 8155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 8165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 8175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!node->m_next) { 8185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(node == m_tail); 8195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_tail = node->m_prev; 8205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else { 8215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(node != m_tail); 8225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) node->m_next->m_prev = node->m_prev; 8235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 824926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) } 8255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 826926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) template<typename T, size_t inlineCapacity, typename U> 827926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) void ListHashSet<T, inlineCapacity, U>::unlinkAndDelete(Node* node) 828926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) { 829926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) unlink(node); 8305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) node->destroy(m_allocator.get()); 8315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 8325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 8335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename U> 8345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void ListHashSet<T, inlineCapacity, U>::appendNode(Node* node) 8355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 8365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) node->m_prev = m_tail; 8375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) node->m_next = 0; 8385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 8395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (m_tail) { 8405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(m_head); 8415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_tail->m_next = node; 8425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else { 8435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(!m_head); 8445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_head = node; 8455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 8465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 8475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_tail = node; 8485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 8495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 8505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename U> 851926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) void ListHashSet<T, inlineCapacity, U>::prependNode(Node* node) 852926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) { 853926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) node->m_prev = 0; 854926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) node->m_next = m_head; 855926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 856926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) if (m_head) 857926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) m_head->m_prev = node; 858926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) else 859926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) m_tail = node; 860926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 861926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) m_head = node; 862926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) } 863926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 864926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) template<typename T, size_t inlineCapacity, typename U> 8655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void ListHashSet<T, inlineCapacity, U>::insertNodeBefore(Node* beforeNode, Node* newNode) 8665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 8675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!beforeNode) 8685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return appendNode(newNode); 86902772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 8705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) newNode->m_next = beforeNode; 8715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) newNode->m_prev = beforeNode->m_prev; 8725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (beforeNode->m_prev) 8735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) beforeNode->m_prev->m_next = newNode; 8745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) beforeNode->m_prev = newNode; 8755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 8765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!newNode->m_prev) 8775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_head = newNode; 8785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 8795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 8805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename U> 8815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void ListHashSet<T, inlineCapacity, U>::deleteAllNodes() 8825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 8835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!m_head) 8845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 8855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 8865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (Node* node = m_head, *next = m_head->m_next; node; node = next, next = node ? node->m_next : 0) 8875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) node->destroy(m_allocator.get()); 8885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 8895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 8905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename U> 891a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) void ListHashSet<T, inlineCapacity, U>::createAllocatorIfNeeded() 892a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) { 893a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) if (!m_allocator) 894a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) m_allocator = adoptPtr(new NodeAllocator); 895a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) } 896a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) 897a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename U> 89802772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch inline ListHashSetReverseIterator<T, inlineCapacity, U> ListHashSet<T, inlineCapacity, U>::makeReverseIterator(Node* position) 8995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 90002772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch return ListHashSetReverseIterator<T, inlineCapacity, U>(this, position); 9015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 9025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 9035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename U> 9045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline ListHashSetConstReverseIterator<T, inlineCapacity, U> ListHashSet<T, inlineCapacity, U>::makeConstReverseIterator(Node* position) const 90502772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch { 90602772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch return ListHashSetConstReverseIterator<T, inlineCapacity, U>(this, position); 9075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 90802772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 9095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename U> 91002772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch inline ListHashSetIterator<T, inlineCapacity, U> ListHashSet<T, inlineCapacity, U>::makeIterator(Node* position) 9115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 91202772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch return ListHashSetIterator<T, inlineCapacity, U>(this, position); 9135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 9145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 9155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename U> 9165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline ListHashSetConstIterator<T, inlineCapacity, U> ListHashSet<T, inlineCapacity, U>::makeConstIterator(Node* position) const 91702772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch { 91802772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch return ListHashSetConstIterator<T, inlineCapacity, U>(this, position); 9195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 9205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<bool, typename ValueType, typename HashTableType> 9215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void deleteAllValues(HashTableType& collection) 9225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 9235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef typename HashTableType::const_iterator iterator; 9245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) iterator end = collection.end(); 9255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (iterator it = collection.begin(); it != end; ++it) 9265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) delete (*it)->m_value; 9275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 9285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 9295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T, size_t inlineCapacity, typename U> 9305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline void deleteAllValues(const ListHashSet<T, inlineCapacity, U>& collection) 9315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 9325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) deleteAllValues<true, typename ListHashSet<T, inlineCapacity, U>::ValueType>(collection.m_impl); 9335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 9345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 9355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} // namespace WTF 9365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 9375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)using WTF::ListHashSet; 9385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 9395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif /* WTF_ListHashSet_h */ 940