15c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/* 25c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Copyright (C) 2005, 2006, 2007, 2008, 2011 Apple Inc. All rights reserved. 35c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 45c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * This library is free software; you can redistribute it and/or 55c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * modify it under the terms of the GNU Library General Public 65c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * License as published by the Free Software Foundation; either 75c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * version 2 of the License, or (at your option) any later version. 85c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 95c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * This library is distributed in the hope that it will be useful, 105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * but WITHOUT ANY WARRANTY; without even the implied warranty of 115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Library General Public License for more details. 135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * You should have received a copy of the GNU Library General Public License 155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * along with this library; see the file COPYING.LIB. If not, write to 165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, 175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Boston, MA 02110-1301, USA. 185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#ifndef WTF_HashMap_h 225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#define WTF_HashMap_h 235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)#include "wtf/DefaultAllocator.h" 25591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch#include "wtf/HashTable.h" 265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)namespace WTF { 285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename KeyTraits, typename MappedTraits> struct HashMapValueTraits; 305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T> struct ReferenceTypeMaker { 325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef T& ReferenceType; 335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T> struct ReferenceTypeMaker<T&> { 355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef T& ReferenceType; 365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) struct KeyValuePairKeyExtractor { 3909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T> 405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const typename T::KeyType& extract(const T& p) { return p.key; } 415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 43323480423219ecd77329f8326dc5e0e3b50926d4Torne (Richard Coles) // Note: empty or deleted key values are not allowed, using them may lead to undefined behavior. 44323480423219ecd77329f8326dc5e0e3b50926d4Torne (Richard Coles) // For pointer keys this means that null pointers are not allowed unless you supply custom key traits. 4509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template< 4609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) typename KeyArg, 4709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) typename MappedArg, 4809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) typename HashArg = typename DefaultHash<KeyArg>::Hash, 4909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) typename KeyTraitsArg = HashTraits<KeyArg>, 5009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) typename MappedTraitsArg = HashTraits<MappedArg>, 5109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) typename Allocator = DefaultAllocator> 525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) class HashMap { 53f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu WTF_USE_ALLOCATOR(HashMap, Allocator); 545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) private: 555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef KeyTraitsArg KeyTraits; 565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef MappedTraitsArg MappedTraits; 575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef HashMapValueTraits<KeyTraits, MappedTraits> ValueTraits; 585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) public: 605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef typename KeyTraits::TraitType KeyType; 6109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) typedef const typename KeyTraits::PeekInType& KeyPeekInType; 625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef typename MappedTraits::TraitType MappedType; 635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef typename ValueTraits::TraitType ValueType; 645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) private: 665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef typename MappedTraits::PassInType MappedPassInType; 675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef typename MappedTraits::PassOutType MappedPassOutType; 6809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) typedef typename MappedTraits::PeekOutType MappedPeekType; 695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef typename ReferenceTypeMaker<MappedPassInType>::ReferenceType MappedPassInReferenceType; 715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef HashArg HashFunctions; 735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) typedef HashTable<KeyType, ValueType, KeyValuePairKeyExtractor, 7509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) HashFunctions, ValueTraits, KeyTraits, Allocator> HashTableType; 765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) class HashMapKeysProxy; 785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) class HashMapValuesProxy; 795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) public: 815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef HashTableIteratorAdapter<HashTableType, ValueType> iterator; 825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef HashTableConstIteratorAdapter<HashTableType, ValueType> const_iterator; 835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef typename HashTableType::AddResult AddResult; 845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) public: 8609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) void swap(HashMap& ref) 8709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) { 8809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) m_impl.swap(ref.m_impl); 8909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) } 9009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 9109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) void swap(typename Allocator::template OtherType<HashMap>::Type other) 9209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) { 9309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) HashMap& ref = Allocator::getOther(other); 9409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) m_impl.swap(ref.m_impl); 9509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) } 965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 9751b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) unsigned size() const; 9851b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) unsigned capacity() const; 995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool isEmpty() const; 1005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // iterators iterate over pairs of keys and values 1025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) iterator begin(); 1035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) iterator end(); 1045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const_iterator begin() const; 1055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const_iterator end() const; 1065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) HashMapKeysProxy& keys() { return static_cast<HashMapKeysProxy&>(*this); } 1085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const HashMapKeysProxy& keys() const { return static_cast<const HashMapKeysProxy&>(*this); } 1095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) HashMapValuesProxy& values() { return static_cast<HashMapValuesProxy&>(*this); } 1115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const HashMapValuesProxy& values() const { return static_cast<const HashMapValuesProxy&>(*this); } 1125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 11309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) iterator find(KeyPeekInType); 11409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) const_iterator find(KeyPeekInType) const; 11509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) bool contains(KeyPeekInType) const; 11609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) MappedPeekType get(KeyPeekInType) const; 1175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // replaces value but not key if key is already present 11902772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch // return value is a pair of the iterator to the key location, 1205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // and a boolean that's true if a new value was actually added 12109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) AddResult set(KeyPeekInType, MappedPassInType); 1225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // does nothing if key is already present 12402772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch // return value is a pair of the iterator to the key location, 1255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // and a boolean that's true if a new value was actually added 12609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) AddResult add(KeyPeekInType, MappedPassInType); 1275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 12809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) void remove(KeyPeekInType); 1295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void remove(iterator); 1305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void clear(); 131f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu template<typename Collection> 132f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu void removeAll(const Collection& toBeRemoved) { WTF::removeAll(*this, toBeRemoved); } 1335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 13409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) MappedPassOutType take(KeyPeekInType); // efficient combination of get with remove 1355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // An alternate version of find() that finds the object by hashing and comparing 1375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // with some other type, to avoid the cost of type conversion. HashTranslator 1385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // must have the following function members: 1395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // static unsigned hash(const T&); 1405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // static bool equal(const ValueType&, const T&); 141591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch template<typename HashTranslator, typename T> iterator find(const T&); 142591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch template<typename HashTranslator, typename T> const_iterator find(const T&) const; 143591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch template<typename HashTranslator, typename T> bool contains(const T&) const; 1445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // An alternate version of add() that finds the object by hashing and comparing 1465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // with some other type, to avoid the cost of type conversion if the object is already 1475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // in the table. HashTranslator must have the following function members: 1485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // static unsigned hash(const T&); 1495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // static bool equal(const ValueType&, const T&); 1505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // static translate(ValueType&, const T&, unsigned hashCode); 151591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch template<typename HashTranslator, typename T> AddResult add(const T&, MappedPassInType); 1525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 15309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) static bool isValidKey(KeyPeekInType); 15409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 155f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu void trace(typename Allocator::Visitor* visitor) { m_impl.trace(visitor); } 156926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 1575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) private: 15809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) AddResult inlineAdd(KeyPeekInType, MappedPassInReferenceType); 1595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 16053e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) HashTableType m_impl; 16153e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) }; 16253e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) 16309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg, typename Allocator> 16409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) class HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg, Allocator>::HashMapKeysProxy : 16509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) private HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg, Allocator> { 1665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) public: 16709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) typedef HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg, Allocator> HashMapType; 16853e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) typedef typename HashMapType::iterator::Keys iterator; 16953e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) typedef typename HashMapType::const_iterator::Keys const_iterator; 17053e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) 1715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) iterator begin() 1725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 17353e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) return HashMapType::begin().keys(); 1745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 17553e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) 1765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) iterator end() 1775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 17853e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) return HashMapType::end().keys(); 1795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const_iterator begin() const 1825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 18353e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) return HashMapType::begin().keys(); 1845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 18553e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) 1865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const_iterator end() const 1875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 18853e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) return HashMapType::end().keys(); 1895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) private: 1925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) friend class HashMap; 1935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // These are intentionally not implemented. 1955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) HashMapKeysProxy(); 1965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) HashMapKeysProxy(const HashMapKeysProxy&); 1975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) HashMapKeysProxy& operator=(const HashMapKeysProxy&); 1985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ~HashMapKeysProxy(); 19953e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) }; 2005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 20109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg, typename Allocator> 20209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) class HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg, Allocator>::HashMapValuesProxy : 20309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) private HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg, Allocator> { 2045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) public: 20509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) typedef HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg, Allocator> HashMapType; 20653e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) typedef typename HashMapType::iterator::Values iterator; 20753e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) typedef typename HashMapType::const_iterator::Values const_iterator; 20853e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) 2095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) iterator begin() 2105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 21153e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) return HashMapType::begin().values(); 2125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 21353e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) 2145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) iterator end() 2155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 21653e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) return HashMapType::end().values(); 2175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const_iterator begin() const 2205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 22153e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) return HashMapType::begin().values(); 2225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 22353e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) 2245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const_iterator end() const 2255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 22653e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) return HashMapType::end().values(); 2275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) private: 2305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) friend class HashMap; 2315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // These are intentionally not implemented. 2335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) HashMapValuesProxy(); 2345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) HashMapValuesProxy(const HashMapValuesProxy&); 2355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) HashMapValuesProxy& operator=(const HashMapValuesProxy&); 2365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ~HashMapValuesProxy(); 2375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 2385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename KeyTraits, typename MappedTraits> struct HashMapValueTraits : KeyValuePairHashTraits<KeyTraits, MappedTraits> { 2405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const bool hasIsEmptyValueFunction = true; 2415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static bool isEmptyValue(const typename KeyValuePairHashTraits<KeyTraits, MappedTraits>::TraitType& value) 2425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 2435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return isHashTraitsEmptyValue<KeyTraits>(value.key); 2445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 2465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename ValueTraits, typename HashFunctions> 2485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) struct HashMapTranslator { 2495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T> static unsigned hash(const T& key) { return HashFunctions::hash(key); } 2505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T, typename U> static bool equal(const T& a, const U& b) { return HashFunctions::equal(a, b); } 2515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T, typename U, typename V> static void translate(T& location, const U& key, const V& mapped) 2525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 2535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) location.key = key; 2545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ValueTraits::ValueTraits::store(mapped, location.value); 2555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 2575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename ValueTraits, typename Translator> 2595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) struct HashMapTranslatorAdapter { 2605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T> static unsigned hash(const T& key) { return Translator::hash(key); } 2615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T, typename U> static bool equal(const T& a, const U& b) { return Translator::equal(a, b); } 2625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T, typename U, typename V> static void translate(T& location, const U& key, const V& mapped, unsigned hashCode) 2635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 2645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Translator::translate(location.key, key, hashCode); 2655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ValueTraits::ValueTraits::store(mapped, location.value); 2665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 2685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 26909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, typename U, typename V, typename W, typename X, typename Y> 27009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) inline unsigned HashMap<T, U, V, W, X, Y>::size() const 2715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 27202772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch return m_impl.size(); 2735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 27509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, typename U, typename V, typename W, typename X, typename Y> 27609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) inline unsigned HashMap<T, U, V, W, X, Y>::capacity() const 27702772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch { 27802772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch return m_impl.capacity(); 2795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 28109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, typename U, typename V, typename W, typename X, typename Y> 28209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) inline bool HashMap<T, U, V, W, X, Y>::isEmpty() const 2835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 2845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return m_impl.isEmpty(); 2855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 28709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, typename U, typename V, typename W, typename X, typename Y> 28809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) inline typename HashMap<T, U, V, W, X, Y>::iterator HashMap<T, U, V, W, X, Y>::begin() 2895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 2905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return m_impl.begin(); 2915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 29309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, typename U, typename V, typename W, typename X, typename Y> 29409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) inline typename HashMap<T, U, V, W, X, Y>::iterator HashMap<T, U, V, W, X, Y>::end() 2955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 2965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return m_impl.end(); 2975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 29909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, typename U, typename V, typename W, typename X, typename Y> 30009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) inline typename HashMap<T, U, V, W, X, Y>::const_iterator HashMap<T, U, V, W, X, Y>::begin() const 3015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 3025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return m_impl.begin(); 3035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 30509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, typename U, typename V, typename W, typename X, typename Y> 30609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) inline typename HashMap<T, U, V, W, X, Y>::const_iterator HashMap<T, U, V, W, X, Y>::end() const 3075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 3085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return m_impl.end(); 3095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 31109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, typename U, typename V, typename W, typename X, typename Y> 31209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) inline typename HashMap<T, U, V, W, X, Y>::iterator HashMap<T, U, V, W, X, Y>::find(KeyPeekInType key) 3135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 3145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return m_impl.find(key); 3155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 31709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, typename U, typename V, typename W, typename X, typename Y> 31809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) inline typename HashMap<T, U, V, W, X, Y>::const_iterator HashMap<T, U, V, W, X, Y>::find(KeyPeekInType key) const 3195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 3205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return m_impl.find(key); 3215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 32309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, typename U, typename V, typename W, typename X, typename Y> 32409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) inline bool HashMap<T, U, V, W, X, Y>::contains(KeyPeekInType key) const 3255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 3265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return m_impl.contains(key); 3275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 32909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, typename U, typename V, typename W, typename X, typename Y> 330591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch template<typename HashTranslator, typename TYPE> 33109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) inline typename HashMap<T, U, V, W, X, Y>::iterator 33209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) HashMap<T, U, V, W, X, Y>::find(const TYPE& value) 3335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 3345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return m_impl.template find<HashMapTranslatorAdapter<ValueTraits, HashTranslator> >(value); 3355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 33709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, typename U, typename V, typename W, typename X, typename Y> 338591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch template<typename HashTranslator, typename TYPE> 33909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) inline typename HashMap<T, U, V, W, X, Y>::const_iterator 34009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) HashMap<T, U, V, W, X, Y>::find(const TYPE& value) const 3415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 3425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return m_impl.template find<HashMapTranslatorAdapter<ValueTraits, HashTranslator> >(value); 3435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 34509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, typename U, typename V, typename W, typename X, typename Y> 346591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch template<typename HashTranslator, typename TYPE> 3475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline bool 34809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) HashMap<T, U, V, W, X, Y>::contains(const TYPE& value) const 3495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 3505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return m_impl.template contains<HashMapTranslatorAdapter<ValueTraits, HashTranslator> >(value); 3515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 35309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, typename U, typename V, typename W, typename X, typename Y> 35409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) typename HashMap<T, U, V, W, X, Y>::AddResult 35509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) HashMap<T, U, V, W, X, Y>::inlineAdd(KeyPeekInType key, MappedPassInReferenceType mapped) 3565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 3575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return m_impl.template add<HashMapTranslator<ValueTraits, HashFunctions> >(key, mapped); 3585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 36009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, typename U, typename V, typename W, typename X, typename Y> 36109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) typename HashMap<T, U, V, W, X, Y>::AddResult 36209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) HashMap<T, U, V, W, X, Y>::set(KeyPeekInType key, MappedPassInType mapped) 3635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 3645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) AddResult result = inlineAdd(key, mapped); 3655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!result.isNewEntry) { 3665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // The inlineAdd call above found an existing hash table entry; we need to set the mapped value. 36709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) MappedTraits::store(mapped, result.storedValue->value); 3685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return result; 3705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 37209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, typename U, typename V, typename W, typename X, typename Y> 373591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch template<typename HashTranslator, typename TYPE> 37409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) typename HashMap<T, U, V, W, X, Y>::AddResult 37509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) HashMap<T, U, V, W, X, Y>::add(const TYPE& key, MappedPassInType value) 3765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 3775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return m_impl.template addPassingHashCode<HashMapTranslatorAdapter<ValueTraits, HashTranslator> >(key, value); 3785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 38009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, typename U, typename V, typename W, typename X, typename Y> 38109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) typename HashMap<T, U, V, W, X, Y>::AddResult 38209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) HashMap<T, U, V, W, X, Y>::add(KeyPeekInType key, MappedPassInType mapped) 3835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 3845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return inlineAdd(key, mapped); 3855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 38709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, typename U, typename V, typename W, typename X, typename Y> 38809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) typename HashMap<T, U, V, W, X, Y>::MappedPeekType 38909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) HashMap<T, U, V, W, X, Y>::get(KeyPeekInType key) const 3905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 3915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ValueType* entry = const_cast<HashTableType&>(m_impl).lookup(key); 3925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!entry) 3935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return MappedTraits::peek(MappedTraits::emptyValue()); 3945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return MappedTraits::peek(entry->value); 3955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 39709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, typename U, typename V, typename W, typename X, typename Y> 39809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) inline void HashMap<T, U, V, W, X, Y>::remove(iterator it) 3995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 4003c9e4aeaee9f9b0a9a814da07bcb33319c7ea363Ben Murdoch m_impl.remove(it.m_impl); 4015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 40309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, typename U, typename V, typename W, typename X, typename Y> 40409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) inline void HashMap<T, U, V, W, X, Y>::remove(KeyPeekInType key) 4055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 4065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) remove(find(key)); 4075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 40909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, typename U, typename V, typename W, typename X, typename Y> 41009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) inline void HashMap<T, U, V, W, X, Y>::clear() 4115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 4125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_impl.clear(); 4135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 41509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, typename U, typename V, typename W, typename X, typename Y> 41609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) typename HashMap<T, U, V, W, X, Y>::MappedPassOutType 41709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) HashMap<T, U, V, W, X, Y>::take(KeyPeekInType key) 4185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 4195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) iterator it = find(key); 4205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (it == end()) 4215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return MappedTraits::passOut(MappedTraits::emptyValue()); 4225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) MappedPassOutType result = MappedTraits::passOut(it->value); 4235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) remove(it); 4245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return result; 4255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 42709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, typename U, typename V, typename W, typename X, typename Y> 42809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) inline bool HashMap<T, U, V, W, X, Y>::isValidKey(KeyPeekInType key) 429926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) { 430926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) if (KeyTraits::isDeletedValue(key)) 431926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) return false; 432926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 433926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) if (HashFunctions::safeToCompareToEmptyOrDeleted) { 434926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) if (key == KeyTraits::emptyValue()) 435926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) return false; 436926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) } else { 437926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) if (isHashTraitsEmptyValue<KeyTraits>(key)) 438926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) return false; 439926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) } 440926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 441926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) return true; 442926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) } 443926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 44409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, typename U, typename V, typename W, typename X, typename Y> 44509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) bool operator==(const HashMap<T, U, V, W, X, Y>& a, const HashMap<T, U, V, W, X, Y>& b) 4465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 4475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (a.size() != b.size()) 4485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return false; 4495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 45009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) typedef typename HashMap<T, U, V, W, X, Y>::const_iterator const_iterator; 4515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 45206f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles) const_iterator aEnd = a.end(); 45306f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles) const_iterator bEnd = b.end(); 45406f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles) for (const_iterator it = a.begin(); it != aEnd; ++it) { 4555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const_iterator bPos = b.find(it->key); 45606f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles) if (bPos == bEnd || it->value != bPos->value) 4575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return false; 4585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return true; 4615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 46309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, typename U, typename V, typename W, typename X, typename Y> 46409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) inline bool operator!=(const HashMap<T, U, V, W, X, Y>& a, const HashMap<T, U, V, W, X, Y>& b) 4655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 4665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return !(a == b); 4675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 46909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, typename U, typename V, typename W, typename X, typename Y, typename Z> 47009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) inline void copyKeysToVector(const HashMap<T, U, V, W, X, Y>& collection, Z& vector) 4715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 47209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) typedef typename HashMap<T, U, V, W, X, Y>::const_iterator::Keys iterator; 47302772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 4745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) vector.resize(collection.size()); 47502772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 4765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) iterator it = collection.begin().keys(); 4775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) iterator end = collection.end().keys(); 4785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (unsigned i = 0; it != end; ++it, ++i) 4795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) vector[i] = *it; 48002772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch } 4815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 48209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) template<typename T, typename U, typename V, typename W, typename X, typename Y, typename Z> 48309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) inline void copyValuesToVector(const HashMap<T, U, V, W, X, Y>& collection, Z& vector) 4845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 48509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) typedef typename HashMap<T, U, V, W, X, Y>::const_iterator::Values iterator; 48602772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 4875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) vector.resize(collection.size()); 48802772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 4895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) iterator it = collection.begin().values(); 4905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) iterator end = collection.end().values(); 4915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (unsigned i = 0; it != end; ++it, ++i) 4925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) vector[i] = *it; 49302772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch } 4945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 495197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch#if !ENABLE(OILPAN) 496197021e6b966cfb06891637935ef33fff06433d1Ben Murdochtemplate<typename T, typename U, typename V, typename W, typename X> 497197021e6b966cfb06891637935ef33fff06433d1Ben Murdochstruct NeedsTracing<HashMap<T, U, V, W, X> > { 498197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch static const bool value = false; 499197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch}; 500197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch#endif 501197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch 5025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} // namespace WTF 5035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)using WTF::HashMap; 5055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif /* WTF_HashMap_h */ 507