18e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project/* 28e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * Copyright (C) 2005, 2006, 2007, 2008 Apple Inc. All rights reserved. 38e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * 48e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * This library is free software; you can redistribute it and/or 58e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * modify it under the terms of the GNU Library General Public 68e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * License as published by the Free Software Foundation; either 78e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * version 2 of the License, or (at your option) any later version. 88e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * 98e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * This library is distributed in the hope that it will be useful, 108e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * but WITHOUT ANY WARRANTY; without even the implied warranty of 118e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 128e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * Library General Public License for more details. 138e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * 148e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * You should have received a copy of the GNU Library General Public License 158e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * along with this library; see the file COPYING.LIB. If not, write to 168e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, 178e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * Boston, MA 02110-1301, USA. 188e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * 198e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project */ 208e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 218e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#ifndef WTF_HashSet_h 228e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#define WTF_HashSet_h 238e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 240bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch#include "FastAllocBase.h" 258e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#include "HashTable.h" 268e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 278e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projectnamespace WTF { 288e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 298e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename Value, typename HashFunctions, typename Traits> class HashSet; 308e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename Value, typename HashFunctions, typename Traits> 318e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void deleteAllValues(const HashSet<Value, HashFunctions, Traits>&); 32231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block template<typename Value, typename HashFunctions, typename Traits> 33231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block void fastDeleteAllValues(const HashSet<Value, HashFunctions, Traits>&); 348e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 358e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename T> struct IdentityExtractor; 368e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 378e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename ValueArg, typename HashArg = typename DefaultHash<ValueArg>::Hash, 38ab9e7a118cf1ea2e3a93dce683b2ded3e7291ddbBen Murdoch typename TraitsArg = HashTraits<ValueArg> > class HashSet { 39ab9e7a118cf1ea2e3a93dce683b2ded3e7291ddbBen Murdoch WTF_MAKE_FAST_ALLOCATED; 408e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project private: 418e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project typedef HashArg HashFunctions; 428e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project typedef TraitsArg ValueTraits; 438e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 448e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project public: 458e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project typedef typename ValueTraits::TraitType ValueType; 468e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 478e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project private: 488e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project typedef HashTable<ValueType, ValueType, IdentityExtractor<ValueType>, 498e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project HashFunctions, ValueTraits, ValueTraits> HashTableType; 508e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 518e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project public: 52ca9cb53ed1119a3fd98fafa0972ffeb56dee1c24Steve Block typedef HashTableConstIteratorAdapter<HashTableType, ValueType> iterator; 538e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project typedef HashTableConstIteratorAdapter<HashTableType, ValueType> const_iterator; 548e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 558e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void swap(HashSet&); 568e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 578e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project int size() const; 588e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project int capacity() const; 598e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project bool isEmpty() const; 608e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 61ca9cb53ed1119a3fd98fafa0972ffeb56dee1c24Steve Block iterator begin() const; 62ca9cb53ed1119a3fd98fafa0972ffeb56dee1c24Steve Block iterator end() const; 638e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 64ca9cb53ed1119a3fd98fafa0972ffeb56dee1c24Steve Block iterator find(const ValueType&) const; 658e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project bool contains(const ValueType&) const; 668e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 678e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // An alternate version of find() that finds the object by hashing and comparing 688e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // with some other type, to avoid the cost of type conversion. HashTranslator 698e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // must have the following function members: 708e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // static unsigned hash(const T&); 718e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // static bool equal(const ValueType&, const T&); 72ca9cb53ed1119a3fd98fafa0972ffeb56dee1c24Steve Block template<typename T, typename HashTranslator> iterator find(const T&) const; 738e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename T, typename HashTranslator> bool contains(const T&) const; 748e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 758e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // The return value is a pair of an interator to the new value's location, 768e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // and a bool that is true if an new entry was added. 778e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project pair<iterator, bool> add(const ValueType&); 788e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 798e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // An alternate version of add() that finds the object by hashing and comparing 808e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // with some other type, to avoid the cost of type conversion if the object is already 81643ca7872b450ea4efacab6188849e5aac2ba161Steve Block // in the table. HashTranslator must have the following function members: 828e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // static unsigned hash(const T&); 838e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // static bool equal(const ValueType&, const T&); 848e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // static translate(ValueType&, const T&, unsigned hashCode); 858e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename T, typename HashTranslator> pair<iterator, bool> add(const T&); 868e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 878e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void remove(const ValueType&); 888e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void remove(iterator); 898e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void clear(); 908e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 918e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project private: 928e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project friend void deleteAllValues<>(const HashSet&); 93231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block friend void fastDeleteAllValues<>(const HashSet&); 948e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 958e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project HashTableType m_impl; 968e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project }; 978e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 988e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename T> struct IdentityExtractor { 998e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project static const T& extract(const T& t) { return t; } 1008e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project }; 1018e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1028e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename ValueType, typename ValueTraits, typename T, typename Translator> 1038e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project struct HashSetTranslatorAdapter { 1048e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project static unsigned hash(const T& key) { return Translator::hash(key); } 1058e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project static bool equal(const ValueType& a, const T& b) { return Translator::equal(a, b); } 1068e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project static void translate(ValueType& location, const T& key, const T&, unsigned hashCode) 1078e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 1088e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project Translator::translate(location, key, hashCode); 1098e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1108e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project }; 1118e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1128e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename T, typename U, typename V> 1138e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project inline void HashSet<T, U, V>::swap(HashSet& other) 1148e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 1158e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_impl.swap(other.m_impl); 1168e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1178e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1188e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename T, typename U, typename V> 1198e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project inline int HashSet<T, U, V>::size() const 1208e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 1218e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return m_impl.size(); 1228e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1238e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1248e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename T, typename U, typename V> 1258e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project inline int HashSet<T, U, V>::capacity() const 1268e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 1278e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return m_impl.capacity(); 1288e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1298e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1308e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename T, typename U, typename V> 1318e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project inline bool HashSet<T, U, V>::isEmpty() const 1328e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 1338e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return m_impl.isEmpty(); 1348e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1358e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1368e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename T, typename U, typename V> 137ca9cb53ed1119a3fd98fafa0972ffeb56dee1c24Steve Block inline typename HashSet<T, U, V>::iterator HashSet<T, U, V>::begin() const 1388e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 1398e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return m_impl.begin(); 1408e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1418e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1428e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename T, typename U, typename V> 143ca9cb53ed1119a3fd98fafa0972ffeb56dee1c24Steve Block inline typename HashSet<T, U, V>::iterator HashSet<T, U, V>::end() const 1448e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 1458e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return m_impl.end(); 1468e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1478e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1488e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename T, typename U, typename V> 149ca9cb53ed1119a3fd98fafa0972ffeb56dee1c24Steve Block inline typename HashSet<T, U, V>::iterator HashSet<T, U, V>::find(const ValueType& value) const 1508e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 1518e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return m_impl.find(value); 1528e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1538e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1548e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename T, typename U, typename V> 1558e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project inline bool HashSet<T, U, V>::contains(const ValueType& value) const 1568e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 1578e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return m_impl.contains(value); 1588e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1598e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1608e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename Value, typename HashFunctions, typename Traits> 1610bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch template<typename T, typename HashTranslator> 1628e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project typename HashSet<Value, HashFunctions, Traits>::iterator 1638e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project inline HashSet<Value, HashFunctions, Traits>::find(const T& value) const 1648e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 1650bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch typedef HashSetTranslatorAdapter<ValueType, ValueTraits, T, HashTranslator> Adapter; 1668e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return m_impl.template find<T, Adapter>(value); 1678e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1688e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1698e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename Value, typename HashFunctions, typename Traits> 1700bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch template<typename T, typename HashTranslator> 1718e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project inline bool HashSet<Value, HashFunctions, Traits>::contains(const T& value) const 1728e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 1730bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch typedef HashSetTranslatorAdapter<ValueType, ValueTraits, T, HashTranslator> Adapter; 1748e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return m_impl.template contains<T, Adapter>(value); 1758e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1768e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1778e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename T, typename U, typename V> 1782fc2651226baac27029e38c9d6ef883fa32084dbSteve Block inline pair<typename HashSet<T, U, V>::iterator, bool> HashSet<T, U, V>::add(const ValueType& value) 1798e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 1808e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return m_impl.add(value); 1818e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1828e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1838e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename Value, typename HashFunctions, typename Traits> 1840bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch template<typename T, typename HashTranslator> 1852fc2651226baac27029e38c9d6ef883fa32084dbSteve Block inline pair<typename HashSet<Value, HashFunctions, Traits>::iterator, bool> 1868e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project HashSet<Value, HashFunctions, Traits>::add(const T& value) 1878e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 1880bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch typedef HashSetTranslatorAdapter<ValueType, ValueTraits, T, HashTranslator> Adapter; 1898e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return m_impl.template addPassingHashCode<T, T, Adapter>(value, value); 1908e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1918e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1928e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename T, typename U, typename V> 1938e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project inline void HashSet<T, U, V>::remove(iterator it) 1948e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 1958e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (it.m_impl == m_impl.end()) 1968e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return; 197d0825bca7fe65beaee391d30da42e937db621564Steve Block m_impl.internalCheckTableConsistency(); 1988e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_impl.removeWithoutEntryConsistencyCheck(it.m_impl); 1998e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 2008e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2018e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename T, typename U, typename V> 2028e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project inline void HashSet<T, U, V>::remove(const ValueType& value) 2038e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 2048e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project remove(find(value)); 2058e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 2068e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2078e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename T, typename U, typename V> 2088e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project inline void HashSet<T, U, V>::clear() 2098e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 2108e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project m_impl.clear(); 2118e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 2128e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2138e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename ValueType, typename HashTableType> 2148e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void deleteAllValues(HashTableType& collection) 2158e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 2168e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project typedef typename HashTableType::const_iterator iterator; 2178e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project iterator end = collection.end(); 2188e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project for (iterator it = collection.begin(); it != end; ++it) 2198e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project delete *it; 2208e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 2218e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2228e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename T, typename U, typename V> 2238e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project inline void deleteAllValues(const HashSet<T, U, V>& collection) 2248e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 2258e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project deleteAllValues<typename HashSet<T, U, V>::ValueType>(collection.m_impl); 2268e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 227231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block 228231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block template<typename ValueType, typename HashTableType> 229231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block void fastDeleteAllValues(HashTableType& collection) 230231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block { 231231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block typedef typename HashTableType::const_iterator iterator; 232231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block iterator end = collection.end(); 233231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block for (iterator it = collection.begin(); it != end; ++it) 234231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block fastDelete(*it); 235231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block } 236231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block 237231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block template<typename T, typename U, typename V> 238231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block inline void fastDeleteAllValues(const HashSet<T, U, V>& collection) 239231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block { 240231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block fastDeleteAllValues<typename HashSet<T, U, V>::ValueType>(collection.m_impl); 241231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Block } 2428e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2438e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename T, typename U, typename V, typename W> 2448e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project inline void copyToVector(const HashSet<T, U, V>& collection, W& vector) 2458e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 2468e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project typedef typename HashSet<T, U, V>::const_iterator iterator; 2478e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2488e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project vector.resize(collection.size()); 2498e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2508e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project iterator it = collection.begin(); 2518e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project iterator end = collection.end(); 2528e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project for (unsigned i = 0; it != end; ++it, ++i) 2538e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project vector[i] = *it; 2548e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 2558e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2568e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project} // namespace WTF 2578e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2588e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projectusing WTF::HashSet; 2598e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2608e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif /* WTF_HashSet_h */ 261