18e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project/* 28e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * Copyright (C) 2005, 2006, 2007, 2008 Apple Inc. All rights reserved. 381bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch * Copyright (C) 2011, Benjamin Poulain <ikipou@gmail.com> 48e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * 58e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * This library is free software; you can redistribute it and/or 68e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * modify it under the terms of the GNU Library General Public 78e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * License as published by the Free Software Foundation; either 88e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * version 2 of the License, or (at your option) any later version. 98e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * 108e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * This library is distributed in the hope that it will be useful, 118e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * but WITHOUT ANY WARRANTY; without even the implied warranty of 128e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 138e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * Library General Public License for more details. 148e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * 158e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * You should have received a copy of the GNU Library General Public License 168e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * along with this library; see the file COPYING.LIB. If not, write to 178e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, 188e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * Boston, MA 02110-1301, USA. 198e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * 208e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project */ 218e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 228e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#ifndef WTF_ListHashSet_h 238e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#define WTF_ListHashSet_h 248e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 258e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#include "Assertions.h" 268e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#include "HashSet.h" 278e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#include "OwnPtr.h" 28e8b154fd68f9b33be40a3590e58347f353835f5cSteve Block#include "StdLibExtras.h" 298e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 308e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projectnamespace WTF { 318e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 328e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // ListHashSet: Just like HashSet, this class provides a Set 338e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // interface - a collection of unique objects with O(1) insertion, 348e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // removal and test for containership. However, it also has an 358e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // order - iterating it will always give back values in the order 368e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // in which they are added. 378e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 388e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // In theory it would be possible to add prepend, insertAfter 398e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // and an append that moves the element to the end even if already present, 408e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // but unclear yet if these are needed. 418e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 42e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block template<typename Value, size_t inlineCapacity, typename HashFunctions> class ListHashSet; 438e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 448e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename T> struct IdentityExtractor; 458e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 46e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block template<typename Value, size_t inlineCapacity, typename HashFunctions> 47e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block void deleteAllValues(const ListHashSet<Value, inlineCapacity, HashFunctions>&); 488e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 49e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block template<typename ValueArg, size_t inlineCapacity, typename HashArg> class ListHashSetIterator; 50e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block template<typename ValueArg, size_t inlineCapacity, typename HashArg> class ListHashSetConstIterator; 518e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 52e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block template<typename ValueArg, size_t inlineCapacity> struct ListHashSetNode; 53e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block template<typename ValueArg, size_t inlineCapacity> struct ListHashSetNodeAllocator; 54e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block template<typename ValueArg, size_t inlineCapacity, typename HashArg> struct ListHashSetNodeHashFunctions; 558e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 56ab9e7a118cf1ea2e3a93dce683b2ded3e7291ddbBen Murdoch template<typename ValueArg, size_t inlineCapacity = 256, typename HashArg = typename DefaultHash<ValueArg>::Hash> class ListHashSet { 57ab9e7a118cf1ea2e3a93dce683b2ded3e7291ddbBen Murdoch WTF_MAKE_FAST_ALLOCATED; 588e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project private: 59e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block typedef ListHashSetNode<ValueArg, inlineCapacity> Node; 60e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block typedef ListHashSetNodeAllocator<ValueArg, inlineCapacity> NodeAllocator; 618e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 628e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project typedef HashTraits<Node*> NodeTraits; 63e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block typedef ListHashSetNodeHashFunctions<ValueArg, inlineCapacity, HashArg> NodeHash; 648e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 658e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project typedef HashTable<Node*, Node*, IdentityExtractor<Node*>, NodeHash, NodeTraits, NodeTraits> ImplType; 66635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project typedef HashTableIterator<Node*, Node*, IdentityExtractor<Node*>, NodeHash, NodeTraits, NodeTraits> ImplTypeIterator; 67635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project typedef HashTableConstIterator<Node*, Node*, IdentityExtractor<Node*>, NodeHash, NodeTraits, NodeTraits> ImplTypeConstIterator; 688e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 698e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project typedef HashArg HashFunctions; 708e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 718e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project public: 728e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project typedef ValueArg ValueType; 73e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block typedef ListHashSetIterator<ValueType, inlineCapacity, HashArg> iterator; 74e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block typedef ListHashSetConstIterator<ValueType, inlineCapacity, HashArg> const_iterator; 758e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 76e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block friend class ListHashSetConstIterator<ValueType, inlineCapacity, HashArg>; 778e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 788e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ListHashSet(); 798e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ListHashSet(const ListHashSet&); 808e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ListHashSet& operator=(const ListHashSet&); 818e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ~ListHashSet(); 828e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 838e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void swap(ListHashSet&); 848e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 858e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project int size() const; 868e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project int capacity() const; 878e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project bool isEmpty() const; 888e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 898e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project iterator begin(); 908e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project iterator end(); 918e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project const_iterator begin() const; 928e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project const_iterator end() const; 938e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 9481bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch ValueType& first(); 9581bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch const ValueType& first() const; 9681bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 9781bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch ValueType& last(); 9881bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch const ValueType& last() const; 9981bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch void removeLast(); 10081bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 1018e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project iterator find(const ValueType&); 1028e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project const_iterator find(const ValueType&) const; 1038e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project bool contains(const ValueType&) const; 1048e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 10581bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch // An alternate version of find() that finds the object by hashing and comparing 10681bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch // with some other type, to avoid the cost of type conversion. 10781bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch // The HashTranslator interface is defined in HashSet. 10881bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, typename HashTranslator> iterator find(const T&); 10981bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, typename HashTranslator> const_iterator find(const T&) const; 11081bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, typename HashTranslator> bool contains(const T&) const; 11181bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 1128e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // the return value is a pair of an iterator to the new value's location, 1138e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // and a bool that is true if an new entry was added 1148e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project pair<iterator, bool> add(const ValueType&); 1158e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1168e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project pair<iterator, bool> insertBefore(const ValueType& beforeValue, const ValueType& newValue); 1178e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project pair<iterator, bool> insertBefore(iterator it, const ValueType&); 1188e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1198e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void remove(const ValueType&); 1208e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void remove(iterator); 1218e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void clear(); 1228e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1238e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project private: 1248e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void unlinkAndDelete(Node*); 1258e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void appendNode(Node*); 1268e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void insertNodeBefore(Node* beforeNode, Node* newNode); 1278e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void deleteAllNodes(); 1288e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project iterator makeIterator(Node*); 1298e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project const_iterator makeConstIterator(Node*) const; 1308e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1318e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project friend void deleteAllValues<>(const ListHashSet&); 1328e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1338e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ImplType m_impl; 1348e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project Node* m_head; 1358e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project Node* m_tail; 1368e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project OwnPtr<NodeAllocator> m_allocator; 1378e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project }; 1388e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 139e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block template<typename ValueArg, size_t inlineCapacity> struct ListHashSetNodeAllocator { 140e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block typedef ListHashSetNode<ValueArg, inlineCapacity> Node; 141e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block typedef ListHashSetNodeAllocator<ValueArg, inlineCapacity> NodeAllocator; 1428e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1438e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ListHashSetNodeAllocator() 1448e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project : m_freeList(pool()) 1458e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project , m_isDoneWithInitialFreeList(false) 1468e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 1478e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project memset(m_pool.pool, 0, sizeof(m_pool.pool)); 1488e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1498e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1508e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project Node* allocate() 1518e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 1528e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project Node* result = m_freeList; 1538e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1548e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (!result) 1558e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return static_cast<Node*>(fastMalloc(sizeof(Node))); 1568e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1578e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(!result->m_isAllocated); 1588e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1598e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project Node* next = result->m_next; 1608e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(!next || !next->m_isAllocated); 1618e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (!next && !m_isDoneWithInitialFreeList) { 1628e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project next = result + 1; 1638e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (next == pastPool()) { 1648e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_isDoneWithInitialFreeList = true; 1658e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project next = 0; 1668e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } else { 1678e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(inPool(next)); 1688e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(!next->m_isAllocated); 1698e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1708e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1718e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_freeList = next; 1728e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1738e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return result; 1748e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1758e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1768e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void deallocate(Node* node) 1778e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 1788e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (inPool(node)) { 1798e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#ifndef NDEBUG 1808e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project node->m_isAllocated = false; 1818e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif 1828e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project node->m_next = m_freeList; 1838e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_freeList = node; 1848e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return; 1858e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1868e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1878e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project fastFree(node); 1888e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1898e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1908e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project private: 191e8b154fd68f9b33be40a3590e58347f353835f5cSteve Block Node* pool() { return reinterpret_cast_ptr<Node*>(m_pool.pool); } 1928e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project Node* pastPool() { return pool() + m_poolSize; } 1938e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1948e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project bool inPool(Node* node) 1958e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 1968e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return node >= pool() && node < pastPool(); 1978e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1988e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1998e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project Node* m_freeList; 2008e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project bool m_isDoneWithInitialFreeList; 201e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block static const size_t m_poolSize = inlineCapacity; 2028e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project union { 2038e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project char pool[sizeof(Node) * m_poolSize]; 2048e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project double forAlignment; 2058e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } m_pool; 2068e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project }; 2078e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 208e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block template<typename ValueArg, size_t inlineCapacity> struct ListHashSetNode { 209e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block typedef ListHashSetNodeAllocator<ValueArg, inlineCapacity> NodeAllocator; 2108e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2118e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ListHashSetNode(ValueArg value) 2128e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project : m_value(value) 2138e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project , m_prev(0) 2148e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project , m_next(0) 2158e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#ifndef NDEBUG 2168e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project , m_isAllocated(true) 2178e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif 2188e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 2198e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 2208e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2218e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void* operator new(size_t, NodeAllocator* allocator) 2228e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 2238e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return allocator->allocate(); 2248e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 2258e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void destroy(NodeAllocator* allocator) 2268e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 2278e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project this->~ListHashSetNode(); 2288e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project allocator->deallocate(this); 2298e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 2308e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2318e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ValueArg m_value; 2328e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ListHashSetNode* m_prev; 2338e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ListHashSetNode* m_next; 2348e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2358e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#ifndef NDEBUG 2368e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project bool m_isAllocated; 2378e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif 2388e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project }; 2398e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 240e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block template<typename ValueArg, size_t inlineCapacity, typename HashArg> struct ListHashSetNodeHashFunctions { 241e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block typedef ListHashSetNode<ValueArg, inlineCapacity> Node; 2428e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2438e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project static unsigned hash(Node* const& key) { return HashArg::hash(key->m_value); } 2448e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project static bool equal(Node* const& a, Node* const& b) { return HashArg::equal(a->m_value, b->m_value); } 2458e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project static const bool safeToCompareToEmptyOrDeleted = false; 2468e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project }; 2478e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 248e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block template<typename ValueArg, size_t inlineCapacity, typename HashArg> class ListHashSetIterator { 2498e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project private: 250e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block typedef ListHashSet<ValueArg, inlineCapacity, HashArg> ListHashSetType; 251e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block typedef ListHashSetIterator<ValueArg, inlineCapacity, HashArg> iterator; 252e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block typedef ListHashSetConstIterator<ValueArg, inlineCapacity, HashArg> const_iterator; 253e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block typedef ListHashSetNode<ValueArg, inlineCapacity> Node; 2548e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project typedef ValueArg ValueType; 2558e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project typedef ValueType& ReferenceType; 2568e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project typedef ValueType* PointerType; 2578e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 258e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block friend class ListHashSet<ValueArg, inlineCapacity, HashArg>; 2598e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2608e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ListHashSetIterator(const ListHashSetType* set, Node* position) : m_iterator(set, position) { } 2618e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2628e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project public: 2638e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ListHashSetIterator() { } 2648e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2658e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // default copy, assignment and destructor are OK 2668e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2678e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project PointerType get() const { return const_cast<PointerType>(m_iterator.get()); } 2688e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ReferenceType operator*() const { return *get(); } 2698e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project PointerType operator->() const { return get(); } 2708e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2718e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project iterator& operator++() { ++m_iterator; return *this; } 2728e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2738e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // postfix ++ intentionally omitted 2748e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2758e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project iterator& operator--() { --m_iterator; return *this; } 2768e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2778e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // postfix -- intentionally omitted 2788e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2798e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Comparison. 2808e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project bool operator==(const iterator& other) const { return m_iterator == other.m_iterator; } 2818e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project bool operator!=(const iterator& other) const { return m_iterator != other.m_iterator; } 2828e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2838e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project operator const_iterator() const { return m_iterator; } 2848e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2858e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project private: 2868e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project Node* node() { return m_iterator.node(); } 2878e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2888e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project const_iterator m_iterator; 2898e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project }; 2908e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 291e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block template<typename ValueArg, size_t inlineCapacity, typename HashArg> class ListHashSetConstIterator { 2928e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project private: 293e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block typedef ListHashSet<ValueArg, inlineCapacity, HashArg> ListHashSetType; 294e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block typedef ListHashSetIterator<ValueArg, inlineCapacity, HashArg> iterator; 295e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block typedef ListHashSetConstIterator<ValueArg, inlineCapacity, HashArg> const_iterator; 296e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block typedef ListHashSetNode<ValueArg, inlineCapacity> Node; 2978e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project typedef ValueArg ValueType; 2988e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project typedef const ValueType& ReferenceType; 2998e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project typedef const ValueType* PointerType; 3008e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 301e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block friend class ListHashSet<ValueArg, inlineCapacity, HashArg>; 302e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block friend class ListHashSetIterator<ValueArg, inlineCapacity, HashArg>; 3038e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 3048e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ListHashSetConstIterator(const ListHashSetType* set, Node* position) 3058e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project : m_set(set) 3068e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project , m_position(position) 3078e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 3088e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 3098e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 3108e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project public: 3118e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ListHashSetConstIterator() 3128e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 3138e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 3148e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 3158e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project PointerType get() const 3168e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 3178e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return &m_position->m_value; 3188e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 3198e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ReferenceType operator*() const { return *get(); } 3208e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project PointerType operator->() const { return get(); } 3218e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 3228e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project const_iterator& operator++() 3238e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 3248e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(m_position != 0); 3258e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_position = m_position->m_next; 3268e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return *this; 3278e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 3288e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 3298e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // postfix ++ intentionally omitted 3308e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 3318e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project const_iterator& operator--() 3328e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 3338e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(m_position != m_set->m_head); 3348e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (!m_position) 3358e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_position = m_set->m_tail; 3368e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project else 3378e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_position = m_position->m_prev; 3388e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return *this; 3398e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 3408e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 3418e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // postfix -- intentionally omitted 3428e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 3438e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Comparison. 3448e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project bool operator==(const const_iterator& other) const 3458e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 3468e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return m_position == other.m_position; 3478e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 3488e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project bool operator!=(const const_iterator& other) const 3498e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 3508e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return m_position != other.m_position; 3518e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 3528e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 3538e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project private: 3548e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project Node* node() { return m_position; } 3558e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 3568e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project const ListHashSetType* m_set; 3578e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project Node* m_position; 3588e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project }; 3598e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 3608e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 361e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block template<typename ValueType, size_t inlineCapacity, typename HashFunctions> 3628e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project struct ListHashSetTranslator { 3638e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project private: 364e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block typedef ListHashSetNode<ValueType, inlineCapacity> Node; 365e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block typedef ListHashSetNodeAllocator<ValueType, inlineCapacity> NodeAllocator; 3668e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project public: 3678e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project static unsigned hash(const ValueType& key) { return HashFunctions::hash(key); } 3688e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project static bool equal(Node* const& a, const ValueType& b) { return HashFunctions::equal(a->m_value, b); } 3698e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project static void translate(Node*& location, const ValueType& key, NodeAllocator* allocator) 3708e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 3718e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project location = new (allocator) Node(key); 3728e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 3738e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project }; 3748e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 375e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block template<typename T, size_t inlineCapacity, typename U> 376e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block inline ListHashSet<T, inlineCapacity, U>::ListHashSet() 3778e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project : m_head(0) 3788e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project , m_tail(0) 3798e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project , m_allocator(new NodeAllocator) 3808e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 3818e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 3828e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 383e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block template<typename T, size_t inlineCapacity, typename U> 384e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block inline ListHashSet<T, inlineCapacity, U>::ListHashSet(const ListHashSet& other) 3858e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project : m_head(0) 3868e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project , m_tail(0) 3878e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project , m_allocator(new NodeAllocator) 3888e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 3898e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project const_iterator end = other.end(); 3908e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project for (const_iterator it = other.begin(); it != end; ++it) 3918e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project add(*it); 3928e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 3938e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 394e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block template<typename T, size_t inlineCapacity, typename U> 395e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block inline ListHashSet<T, inlineCapacity, U>& ListHashSet<T, inlineCapacity, U>::operator=(const ListHashSet& other) 3968e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 3978e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ListHashSet tmp(other); 3988e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project swap(tmp); 3998e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return *this; 4008e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 4018e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 402e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block template<typename T, size_t inlineCapacity, typename U> 403e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block inline void ListHashSet<T, inlineCapacity, U>::swap(ListHashSet& other) 4048e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 4058e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_impl.swap(other.m_impl); 4068e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project std::swap(m_head, other.m_head); 4078e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project std::swap(m_tail, other.m_tail); 4088e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_allocator.swap(other.m_allocator); 4098e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 4108e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 411e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block template<typename T, size_t inlineCapacity, typename U> 412e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block inline ListHashSet<T, inlineCapacity, U>::~ListHashSet() 4138e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 4148e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project deleteAllNodes(); 4158e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 4168e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 417e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block template<typename T, size_t inlineCapacity, typename U> 418e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block inline int ListHashSet<T, inlineCapacity, U>::size() const 4198e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 4208e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return m_impl.size(); 4218e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 4228e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 423e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block template<typename T, size_t inlineCapacity, typename U> 424e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block inline int ListHashSet<T, inlineCapacity, U>::capacity() const 4258e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 4268e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return m_impl.capacity(); 4278e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 4288e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 429e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block template<typename T, size_t inlineCapacity, typename U> 430e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block inline bool ListHashSet<T, inlineCapacity, U>::isEmpty() const 4318e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 4328e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return m_impl.isEmpty(); 4338e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 4348e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 435e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block template<typename T, size_t inlineCapacity, typename U> 436e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block inline typename ListHashSet<T, inlineCapacity, U>::iterator ListHashSet<T, inlineCapacity, U>::begin() 4378e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 4388e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return makeIterator(m_head); 4398e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 4408e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 441e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block template<typename T, size_t inlineCapacity, typename U> 442e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block inline typename ListHashSet<T, inlineCapacity, U>::iterator ListHashSet<T, inlineCapacity, U>::end() 4438e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 4448e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return makeIterator(0); 4458e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 4468e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 447e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block template<typename T, size_t inlineCapacity, typename U> 448e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block inline typename ListHashSet<T, inlineCapacity, U>::const_iterator ListHashSet<T, inlineCapacity, U>::begin() const 4498e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 4508e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return makeConstIterator(m_head); 4518e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 4528e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 453e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block template<typename T, size_t inlineCapacity, typename U> 454e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block inline typename ListHashSet<T, inlineCapacity, U>::const_iterator ListHashSet<T, inlineCapacity, U>::end() const 4558e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 4568e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return makeConstIterator(0); 4578e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 4588e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 459e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block template<typename T, size_t inlineCapacity, typename U> 46081bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch inline T& ListHashSet<T, inlineCapacity, U>::first() 46181bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch { 46281bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch ASSERT(!isEmpty()); 46381bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch return m_head->m_value; 46481bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch } 46581bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 46681bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, size_t inlineCapacity, typename U> 46781bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch inline const T& ListHashSet<T, inlineCapacity, U>::first() const 46881bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch { 46981bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch ASSERT(!isEmpty()); 47081bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch return m_head->m_value; 47181bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch } 47281bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 47381bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, size_t inlineCapacity, typename U> 47481bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch inline T& ListHashSet<T, inlineCapacity, U>::last() 47581bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch { 47681bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch ASSERT(!isEmpty()); 47781bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch return m_tail->m_value; 47881bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch } 47981bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 48081bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, size_t inlineCapacity, typename U> 48181bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch inline const T& ListHashSet<T, inlineCapacity, U>::last() const 48281bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch { 48381bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch ASSERT(!isEmpty()); 48481bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch return m_tail->m_value; 48581bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch } 48681bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 48781bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, size_t inlineCapacity, typename U> 48881bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch inline void ListHashSet<T, inlineCapacity, U>::removeLast() 48981bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch { 49081bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch ASSERT(!isEmpty()); 49181bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch m_impl.remove(m_tail); 49281bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch unlinkAndDelete(m_tail); 49381bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch } 49481bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 49581bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, size_t inlineCapacity, typename U> 496e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block inline typename ListHashSet<T, inlineCapacity, U>::iterator ListHashSet<T, inlineCapacity, U>::find(const ValueType& value) 4978e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 498e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block typedef ListHashSetTranslator<ValueType, inlineCapacity, HashFunctions> Translator; 499635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project ImplTypeIterator it = m_impl.template find<ValueType, Translator>(value); 5008e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (it == m_impl.end()) 5018e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return end(); 5028e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return makeIterator(*it); 5038e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 5048e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 505e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block template<typename T, size_t inlineCapacity, typename U> 506e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block inline typename ListHashSet<T, inlineCapacity, U>::const_iterator ListHashSet<T, inlineCapacity, U>::find(const ValueType& value) const 5078e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 508e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block typedef ListHashSetTranslator<ValueType, inlineCapacity, HashFunctions> Translator; 509635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project ImplTypeConstIterator it = m_impl.template find<ValueType, Translator>(value); 5108e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (it == m_impl.end()) 5118e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return end(); 5128e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return makeConstIterator(*it); 5138e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 5148e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 51581bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename ValueType, size_t inlineCapacity, typename T, typename Translator> 51681bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch struct ListHashSetTranslatorAdapter { 51781bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch private: 51881bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch typedef ListHashSetNode<ValueType, inlineCapacity> Node; 51981bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch public: 52081bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch static unsigned hash(const T& key) { return Translator::hash(key); } 52181bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch static bool equal(Node* const& a, const T& b) { return Translator::equal(a->m_value, b); } 52281bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch }; 52381bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 52481bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename ValueType, size_t inlineCapacity, typename U> 52581bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, typename HashTranslator> 52681bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch inline typename ListHashSet<ValueType, inlineCapacity, U>::iterator ListHashSet<ValueType, inlineCapacity, U>::find(const T& value) 52781bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch { 52881bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch typedef ListHashSetTranslatorAdapter<ValueType, inlineCapacity, T, HashTranslator> Adapter; 52981bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch ImplTypeConstIterator it = m_impl.template find<T, Adapter>(value); 53081bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch if (it == m_impl.end()) 53181bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch return end(); 53281bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch return makeIterator(*it); 53381bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch } 53481bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 53581bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename ValueType, size_t inlineCapacity, typename U> 53681bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, typename HashTranslator> 53781bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch inline typename ListHashSet<ValueType, inlineCapacity, U>::const_iterator ListHashSet<ValueType, inlineCapacity, U>::find(const T& value) const 53881bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch { 53981bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch typedef ListHashSetTranslatorAdapter<ValueType, inlineCapacity, T, HashTranslator> Adapter; 54081bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch ImplTypeConstIterator it = m_impl.template find<T, Adapter>(value); 54181bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch if (it == m_impl.end()) 54281bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch return end(); 54381bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch return makeConstIterator(*it); 54481bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch } 54581bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 54681bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename ValueType, size_t inlineCapacity, typename U> 54781bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch template<typename T, typename HashTranslator> 54881bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch inline bool ListHashSet<ValueType, inlineCapacity, U>::contains(const T& value) const 54981bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch { 55081bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch typedef ListHashSetTranslatorAdapter<ValueType, inlineCapacity, T, HashTranslator> Adapter; 55181bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch return m_impl.template contains<T, Adapter>(value); 55281bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch } 55381bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 554e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block template<typename T, size_t inlineCapacity, typename U> 555e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block inline bool ListHashSet<T, inlineCapacity, U>::contains(const ValueType& value) const 5568e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 557e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block typedef ListHashSetTranslator<ValueType, inlineCapacity, HashFunctions> Translator; 5588e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return m_impl.template contains<ValueType, Translator>(value); 5598e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 5608e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 561e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block template<typename T, size_t inlineCapacity, typename U> 562e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block pair<typename ListHashSet<T, inlineCapacity, U>::iterator, bool> ListHashSet<T, inlineCapacity, U>::add(const ValueType &value) 5638e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 564e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block typedef ListHashSetTranslator<ValueType, inlineCapacity, HashFunctions> Translator; 5658e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project pair<typename ImplType::iterator, bool> result = m_impl.template add<ValueType, NodeAllocator*, Translator>(value, m_allocator.get()); 5668e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (result.second) 5678e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project appendNode(*result.first); 5688e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return std::make_pair(makeIterator(*result.first), result.second); 5698e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 5708e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 571e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block template<typename T, size_t inlineCapacity, typename U> 572e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block pair<typename ListHashSet<T, inlineCapacity, U>::iterator, bool> ListHashSet<T, inlineCapacity, U>::insertBefore(iterator it, const ValueType& newValue) 5738e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 574e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block typedef ListHashSetTranslator<ValueType, inlineCapacity, HashFunctions> Translator; 5758e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project pair<typename ImplType::iterator, bool> result = m_impl.template add<ValueType, NodeAllocator*, Translator>(newValue, m_allocator.get()); 5768e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (result.second) 5778e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project insertNodeBefore(it.node(), *result.first); 5788e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return std::make_pair(makeIterator(*result.first), result.second); 5798e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 5808e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 5818e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 582e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block template<typename T, size_t inlineCapacity, typename U> 583e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block pair<typename ListHashSet<T, inlineCapacity, U>::iterator, bool> ListHashSet<T, inlineCapacity, U>::insertBefore(const ValueType& beforeValue, const ValueType& newValue) 5848e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 5858e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return insertBefore(find(beforeValue), newValue); 5868e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 5878e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 588e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block template<typename T, size_t inlineCapacity, typename U> 589e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block inline void ListHashSet<T, inlineCapacity, U>::remove(iterator it) 5908e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 5918e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (it == end()) 5928e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return; 5938e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_impl.remove(it.node()); 5948e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project unlinkAndDelete(it.node()); 5958e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 5968e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 597e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block template<typename T, size_t inlineCapacity, typename U> 598e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block inline void ListHashSet<T, inlineCapacity, U>::remove(const ValueType& value) 5998e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 6008e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project remove(find(value)); 6018e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 6028e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 603e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block template<typename T, size_t inlineCapacity, typename U> 604e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block inline void ListHashSet<T, inlineCapacity, U>::clear() 6058e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 6068e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project deleteAllNodes(); 6078e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_impl.clear(); 6088e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_head = 0; 6098e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_tail = 0; 6108e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 6118e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 612e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block template<typename T, size_t inlineCapacity, typename U> 613e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block void ListHashSet<T, inlineCapacity, U>::unlinkAndDelete(Node* node) 6148e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 6158e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (!node->m_prev) { 6168e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(node == m_head); 6178e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_head = node->m_next; 6188e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } else { 6198e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(node != m_head); 6208e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project node->m_prev->m_next = node->m_next; 6218e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 6228e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 6238e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (!node->m_next) { 6248e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(node == m_tail); 6258e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_tail = node->m_prev; 6268e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } else { 6278e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(node != m_tail); 6288e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project node->m_next->m_prev = node->m_prev; 6298e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 6308e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 6318e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project node->destroy(m_allocator.get()); 6328e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 6338e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 634e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block template<typename T, size_t inlineCapacity, typename U> 635e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block void ListHashSet<T, inlineCapacity, U>::appendNode(Node* node) 6368e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 6378e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project node->m_prev = m_tail; 6388e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project node->m_next = 0; 6398e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 6408e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (m_tail) { 6418e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(m_head); 6428e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_tail->m_next = node; 6438e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } else { 6448e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(!m_head); 6458e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_head = node; 6468e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 6478e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 6488e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_tail = node; 6498e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 6508e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 651e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block template<typename T, size_t inlineCapacity, typename U> 652e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block void ListHashSet<T, inlineCapacity, U>::insertNodeBefore(Node* beforeNode, Node* newNode) 6538e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 6548e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (!beforeNode) 6558e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return appendNode(newNode); 6568e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 6578e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project newNode->m_next = beforeNode; 6588e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project newNode->m_prev = beforeNode->m_prev; 6598e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (beforeNode->m_prev) 6608e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project beforeNode->m_prev->m_next = newNode; 6618e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project beforeNode->m_prev = newNode; 6628e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 6638e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (!newNode->m_prev) 6648e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_head = newNode; 6658e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 6668e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 667e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block template<typename T, size_t inlineCapacity, typename U> 668e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block void ListHashSet<T, inlineCapacity, U>::deleteAllNodes() 6698e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 6708e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (!m_head) 6718e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return; 6728e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 6738e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project for (Node* node = m_head, *next = m_head->m_next; node; node = next, next = node ? node->m_next : 0) 6748e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project node->destroy(m_allocator.get()); 6758e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 6768e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 677e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block template<typename T, size_t inlineCapacity, typename U> 678e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block inline ListHashSetIterator<T, inlineCapacity, U> ListHashSet<T, inlineCapacity, U>::makeIterator(Node* position) 6798e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 680e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block return ListHashSetIterator<T, inlineCapacity, U>(this, position); 6818e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 6828e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 683e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block template<typename T, size_t inlineCapacity, typename U> 684e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block inline ListHashSetConstIterator<T, inlineCapacity, U> ListHashSet<T, inlineCapacity, U>::makeConstIterator(Node* position) const 6858e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 686e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block return ListHashSetConstIterator<T, inlineCapacity, U>(this, position); 6878e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 6888e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 6898e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<bool, typename ValueType, typename HashTableType> 6908e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void deleteAllValues(HashTableType& collection) 6918e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 6928e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project typedef typename HashTableType::const_iterator iterator; 6938e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project iterator end = collection.end(); 6948e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project for (iterator it = collection.begin(); it != end; ++it) 6958e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project delete (*it)->m_value; 6968e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 6978e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 698e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block template<typename T, size_t inlineCapacity, typename U> 699e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block inline void deleteAllValues(const ListHashSet<T, inlineCapacity, U>& collection) 7008e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 701e78cbe89e6f337f2f1fe40315be88f742b547151Steve Block deleteAllValues<true, typename ListHashSet<T, inlineCapacity, U>::ValueType>(collection.m_impl); 7028e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 7038e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 7048e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project} // namespace WTF 7058e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 7068e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projectusing WTF::ListHashSet; 7078e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 7088e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif /* WTF_ListHashSet_h */ 709