[apple/javascriptcore.git] / wtf / RefPtrHashMap.h

// -*- mode: c++; c-basic-offset: 4 -*-
/*
 * Copyright (C) 2005, 2006, 2007 Apple Inc. All rights reserved.
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Library General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public License
 * along with this library; see the file COPYING.LIB.  If not, write to
 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
 * Boston, MA 02110-1301, USA.
 *
 */

namespace WTF {

    // This specialization is a direct copy of HashMap, with overloaded functions
    // to allow for lookup by pointer instead of RefPtr, avoiding ref-count churn.
    
    // FIXME: Is there a better way to do this that doesn't just copy HashMap?
    
    template<typename T, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg>
    class HashMap<RefPtr<T>, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg> {
    private:
        typedef KeyTraitsArg KeyTraits;
        typedef MappedTraitsArg MappedTraits;
        typedef PairBaseHashTraits<KeyTraits, MappedTraits> ValueTraits;

    public:
        typedef typename KeyTraits::TraitType KeyType;
        typedef T* RawKeyType;
        typedef typename MappedTraits::TraitType MappedType;
        typedef typename ValueTraits::TraitType ValueType;

    private:
        typedef HashArg HashFunctions;

        typedef typename HashKeyStorageTraits<HashFunctions, KeyTraits>::Hash StorageHashFunctions;

        typedef typename HashKeyStorageTraits<HashFunctions, KeyTraits>::Traits KeyStorageTraits;
        typedef typename MappedTraits::StorageTraits MappedStorageTraits;
        typedef PairHashTraits<KeyStorageTraits, MappedStorageTraits> ValueStorageTraits;

        typedef typename KeyStorageTraits::TraitType KeyStorageType;
        typedef typename MappedStorageTraits::TraitType MappedStorageType;
        typedef typename ValueStorageTraits::TraitType ValueStorageType;

        typedef HashTable<KeyStorageType, ValueStorageType, PairFirstExtractor<ValueStorageType>,
            StorageHashFunctions, ValueStorageTraits, KeyStorageTraits> HashTableType;

    public:
        typedef HashTableIteratorAdapter<HashTableType, ValueType> iterator;
        typedef HashTableConstIteratorAdapter<HashTableType, ValueType> const_iterator;

        HashMap();
        HashMap(const HashMap&);
        HashMap& operator=(const HashMap&);
        ~HashMap();

        void swap(HashMap&);

        int size() const;
        int capacity() const;
        bool isEmpty() const;

        // iterators iterate over pairs of keys and values
        iterator begin();
        iterator end();
        const_iterator begin() const;
        const_iterator end() const;

        iterator find(const KeyType&);
        iterator find(RawKeyType);
        const_iterator find(const KeyType&) const;
        const_iterator find(RawKeyType) const;
        bool contains(const KeyType&) const;
        bool contains(RawKeyType) const;
        MappedType get(const KeyType&) const;
        MappedType get(RawKeyType) const;

        // replaces value but not key if key is already present
        // return value is a pair of the iterator to the key location, 
        // and a boolean that's true if a new value was actually added
        pair<iterator, bool> set(const KeyType&, const MappedType&); 
        pair<iterator, bool> set(RawKeyType, const MappedType&); 

        // does nothing if key is already present
        // return value is a pair of the iterator to the key location, 
        // and a boolean that's true if a new value was actually added
        pair<iterator, bool> add(const KeyType&, const MappedType&); 
        pair<iterator, bool> add(RawKeyType, const MappedType&); 

        void remove(const KeyType&);
        void remove(RawKeyType);
        void remove(iterator);
        void clear();

        MappedType take(const KeyType&); // efficient combination of get with remove
        MappedType take(RawKeyType); // efficient combination of get with remove

    private:
        pair<iterator, bool> inlineAdd(const KeyType&, const MappedType&);
        pair<iterator, bool> inlineAdd(RawKeyType, const MappedType&);
        void refAll();
        void derefAll();

        HashTableType m_impl;
    };
    
    template<typename T, typename U, typename V, typename W, typename X>
    inline void HashMap<RefPtr<T>, U, V, W, X>::refAll()
    {
        HashTableRefCounter<HashTableType, ValueTraits>::refAll(m_impl);
    }

    template<typename T, typename U, typename V, typename W, typename X>
    inline void HashMap<RefPtr<T>, U, V, W, X>::derefAll()
    {
        HashTableRefCounter<HashTableType, ValueTraits>::derefAll(m_impl);
    }

    template<typename T, typename U, typename V, typename W, typename X>
    inline HashMap<RefPtr<T>, U, V, W, X>::HashMap()
    {
    }

    template<typename T, typename U, typename V, typename W, typename X>
    inline HashMap<RefPtr<T>, U, V, W, X>::HashMap(const HashMap& other)
        : m_impl(other.m_impl)
    {
        refAll();
    }

    template<typename T, typename U, typename V, typename W, typename X>
    inline HashMap<RefPtr<T>, U, V, W, X>& HashMap<RefPtr<T>, U, V, W, X>::operator=(const HashMap& other)
    {
        HashMap tmp(other);
        swap(tmp); 
        return *this;
    }

    template<typename T, typename U, typename V, typename W, typename X>
    inline void HashMap<RefPtr<T>, U, V, W, X>::swap(HashMap& other)
    {
        m_impl.swap(other.m_impl); 
    }

    template<typename T, typename U, typename V, typename W, typename X>
    inline HashMap<RefPtr<T>, U, V, W, X>::~HashMap()
    {
        derefAll();
    }

    template<typename T, typename U, typename V, typename W, typename X>
    inline int HashMap<RefPtr<T>, U, V, W, X>::size() const
    {
        return m_impl.size(); 
    }

    template<typename T, typename U, typename V, typename W, typename X>
    inline int HashMap<RefPtr<T>, U, V, W, X>::capacity() const
    { 
        return m_impl.capacity(); 
    }

    template<typename T, typename U, typename V, typename W, typename X>
    inline bool HashMap<RefPtr<T>, U, V, W, X>::isEmpty() const
    {
        return m_impl.isEmpty();
    }

    template<typename T, typename U, typename V, typename W, typename X>
    inline typename HashMap<RefPtr<T>, U, V, W, X>::iterator HashMap<RefPtr<T>, U, V, W, X>::begin()
    {
        return m_impl.begin();
    }

    template<typename T, typename U, typename V, typename W, typename X>
    inline typename HashMap<RefPtr<T>, U, V, W, X>::iterator HashMap<RefPtr<T>, U, V, W, X>::end()
    {
        return m_impl.end();
    }

    template<typename T, typename U, typename V, typename W, typename X>
    inline typename HashMap<RefPtr<T>, U, V, W, X>::const_iterator HashMap<RefPtr<T>, U, V, W, X>::begin() const
    {
        return m_impl.begin();
    }

    template<typename T, typename U, typename V, typename W, typename X>
    inline typename HashMap<RefPtr<T>, U, V, W, X>::const_iterator HashMap<RefPtr<T>, U, V, W, X>::end() const
    {
        return m_impl.end();
    }

    template<typename T, typename U, typename V, typename W, typename X>
    inline typename HashMap<RefPtr<T>, U, V, W, X>::iterator HashMap<RefPtr<T>, U, V, W, X>::find(const KeyType& key)
    {
        return m_impl.find(*(const KeyStorageType*)&key);
    }

    template<typename T, typename U, typename V, typename W, typename X>
    inline typename HashMap<RefPtr<T>, U, V, W, X>::iterator HashMap<RefPtr<T>, U, V, W, X>::find(RawKeyType key)
    {
        return m_impl.find(*(const KeyStorageType*)&key);
    }

    template<typename T, typename U, typename V, typename W, typename X>
    inline typename HashMap<RefPtr<T>, U, V, W, X>::const_iterator HashMap<RefPtr<T>, U, V, W, X>::find(const KeyType& key) const
    {
        return m_impl.find(*(const KeyStorageType*)&key);
    }

    template<typename T, typename U, typename V, typename W, typename X>
    inline typename HashMap<RefPtr<T>, U, V, W, X>::const_iterator HashMap<RefPtr<T>, U, V, W, X>::find(RawKeyType key) const
    {
        return m_impl.find(*(const KeyStorageType*)&key);
    }

    template<typename T, typename U, typename V, typename W, typename X>
    inline bool HashMap<RefPtr<T>, U, V, W, X>::contains(const KeyType& key) const
    {
        return m_impl.contains(*(const KeyStorageType*)&key);
    }

    template<typename T, typename U, typename V, typename W, typename X>
    inline bool HashMap<RefPtr<T>, U, V, W, X>::contains(RawKeyType key) const
    {
        return m_impl.contains(*(const KeyStorageType*)&key);
    }

    template<typename T, typename U, typename V, typename W, typename X>
    inline pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool>
    HashMap<RefPtr<T>, U, V, W, X>::inlineAdd(const KeyType& key, const MappedType& mapped) 
    {
        const bool canReplaceDeletedKey = !KeyTraits::needsDestruction || KeyStorageTraits::needsDestruction;
        typedef HashMapTranslator<canReplaceDeletedKey, ValueType, ValueTraits, ValueStorageTraits, HashFunctions> TranslatorType;
        return m_impl.template add<KeyType, MappedType, TranslatorType>(key, mapped);
    }

    template<typename T, typename U, typename V, typename W, typename X>
    inline pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool>
    HashMap<RefPtr<T>, U, V, W, X>::inlineAdd(RawKeyType key, const MappedType& mapped) 
    {
        return inlineAdd(*(const KeyType*)&key, mapped);
    }

    template<typename T, typename U, typename V, typename W, typename X>
    pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool>
    HashMap<RefPtr<T>, U, V, W, X>::set(const KeyType& key, const MappedType& mapped) 
    {
        pair<iterator, bool> result = inlineAdd(key, mapped);
        if (!result.second)
            // add call above didn't change anything, so set the mapped value
            result.first->second = mapped;
        return result;
    }

    template<typename T, typename U, typename V, typename W, typename X>
    pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool>
    HashMap<RefPtr<T>, U, V, W, X>::set(RawKeyType key, const MappedType& mapped) 
    {
        pair<iterator, bool> result = inlineAdd(key, mapped);
        if (!result.second)
            // add call above didn't change anything, so set the mapped value
            result.first->second = mapped;
        return result;
    }

    template<typename T, typename U, typename V, typename W, typename X>
    pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool>
    HashMap<RefPtr<T>, U, V, W, X>::add(const KeyType& key, const MappedType& mapped)
    {
        return inlineAdd(key, mapped);
    }

    template<typename T, typename U, typename V, typename W, typename X>
    pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool>
    HashMap<RefPtr<T>, U, V, W, X>::add(RawKeyType key, const MappedType& mapped)
    {
        return inlineAdd(key, mapped);
    }

    template<typename T, typename U, typename V, typename W, typename MappedTraits>
    typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType
    HashMap<RefPtr<T>, U, V, W, MappedTraits>::get(const KeyType& key) const
    {
        if (m_impl.isEmpty())
            return MappedTraits::emptyValue();
        ValueStorageType* entry = const_cast<HashTableType&>(m_impl).lookup(*(const KeyStorageType*)&key);
        if (!entry)
            return MappedTraits::emptyValue();
        return ((ValueType *)entry)->second;
    }

    template<typename T, typename U, typename V, typename W, typename MappedTraits>
    typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType
    HashMap<RefPtr<T>, U, V, W, MappedTraits>::get(RawKeyType key) const
    {
        if (m_impl.isEmpty())
            return MappedTraits::emptyValue();
        ValueStorageType* entry = const_cast<HashTableType&>(m_impl).lookup(*(const KeyStorageType*)&key);
        if (!entry)
            return MappedTraits::emptyValue();
        return ((ValueType *)entry)->second;
    }

    template<typename T, typename U, typename V, typename W, typename X>
    inline void HashMap<RefPtr<T>, U, V, W, X>::remove(iterator it)
    {
        if (it.m_impl == m_impl.end())
            return;
        m_impl.checkTableConsistency();
        RefCounter<ValueTraits, ValueStorageTraits>::deref(*it.m_impl);
        m_impl.removeWithoutEntryConsistencyCheck(it.m_impl);
    }

    template<typename T, typename U, typename V, typename W, typename X>
    inline void HashMap<RefPtr<T>, U, V, W, X>::remove(const KeyType& key)
    {
        remove(find(key));
    }

    template<typename T, typename U, typename V, typename W, typename X>
    inline void HashMap<RefPtr<T>, U, V, W, X>::remove(RawKeyType key)
    {
        remove(find(key));
    }

    template<typename T, typename U, typename V, typename W, typename X>
    inline void HashMap<RefPtr<T>, U, V, W, X>::clear()
    {
        derefAll();
        m_impl.clear();
    }

    template<typename T, typename U, typename V, typename W, typename MappedTraits>
    typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType
    HashMap<RefPtr<T>, U, V, W, MappedTraits>::take(const KeyType& key)
    {
        // This can probably be made more efficient to avoid ref/deref churn.
        iterator it = find(key);
        if (it == end())
            return MappedTraits::emptyValue();
        typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType result = it->second;
        remove(it);
        return result;
    }

    template<typename T, typename U, typename V, typename W, typename MappedTraits>
    typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType
    HashMap<RefPtr<T>, U, V, W, MappedTraits>::take(RawKeyType key)
    {
        // This can probably be made more efficient to avoid ref/deref churn.
        iterator it = find(key);
        if (it == end())
            return MappedTraits::emptyValue();
        typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType result = it->second;
        remove(it);
        return result;
    }

} // namespace WTF
Commit	Line	Data
b37bf2e1 A	1	// -- mode: c++; c-basic-offset: 4 --
	2	/*
	3	* Copyright (C) 2005, 2006, 2007 Apple Inc. All rights reserved.
	4	*
	5	* This library is free software; you can redistribute it and/or
	6	* modify it under the terms of the GNU Library General Public
	7	* License as published by the Free Software Foundation; either
	8	* version 2 of the License, or (at your option) any later version.
	9	*
	10	* This library is distributed in the hope that it will be useful,
	11	* but WITHOUT ANY WARRANTY; without even the implied warranty of
	12	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
	13	* Library General Public License for more details.
	14	*
	15	* You should have received a copy of the GNU Library General Public License
	16	* along with this library; see the file COPYING.LIB. If not, write to
	17	* the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
	18	* Boston, MA 02110-1301, USA.
	19	*
	20	*/
	21
	22	namespace WTF {
	23
	24	// This specialization is a direct copy of HashMap, with overloaded functions
	25	// to allow for lookup by pointer instead of RefPtr, avoiding ref-count churn.
	26
	27	// FIXME: Is there a better way to do this that doesn't just copy HashMap?
	28
	29	template<typename T, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg>
	30	class HashMap<RefPtr<T>, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg> {
	31	private:
	32	typedef KeyTraitsArg KeyTraits;
	33	typedef MappedTraitsArg MappedTraits;
	34	typedef PairBaseHashTraits<KeyTraits, MappedTraits> ValueTraits;
	35
	36	public:
	37	typedef typename KeyTraits::TraitType KeyType;
	38	typedef T* RawKeyType;
	39	typedef typename MappedTraits::TraitType MappedType;
	40	typedef typename ValueTraits::TraitType ValueType;
	41
	42	private:
	43	typedef HashArg HashFunctions;
	44
	45	typedef typename HashKeyStorageTraits<HashFunctions, KeyTraits>::Hash StorageHashFunctions;
	46
	47	typedef typename HashKeyStorageTraits<HashFunctions, KeyTraits>::Traits KeyStorageTraits;
	48	typedef typename MappedTraits::StorageTraits MappedStorageTraits;
	49	typedef PairHashTraits<KeyStorageTraits, MappedStorageTraits> ValueStorageTraits;
	50
	51	typedef typename KeyStorageTraits::TraitType KeyStorageType;
	52	typedef typename MappedStorageTraits::TraitType MappedStorageType;
	53	typedef typename ValueStorageTraits::TraitType ValueStorageType;
	54
	55	typedef HashTable<KeyStorageType, ValueStorageType, PairFirstExtractor<ValueStorageType>,
	56	StorageHashFunctions, ValueStorageTraits, KeyStorageTraits> HashTableType;
	57
	58	public:
	59	typedef HashTableIteratorAdapter<HashTableType, ValueType> iterator;
	60	typedef HashTableConstIteratorAdapter<HashTableType, ValueType> const_iterator;
	61
	62	HashMap();
	63	HashMap(const HashMap&);
	64	HashMap& operator=(const HashMap&);
65	~HashMap();
66
67	void swap(HashMap&);
68
69	int size() const;
70	int capacity() const;
71	bool isEmpty() const;
72
73	// iterators iterate over pairs of keys and values
74	iterator begin();
75	iterator end();
76	const_iterator begin() const;
77	const_iterator end() const;
78
79	iterator find(const KeyType&);
80	iterator find(RawKeyType);
81	const_iterator find(const KeyType&) const;
82	const_iterator find(RawKeyType) const;
83	bool contains(const KeyType&) const;
84	bool contains(RawKeyType) const;
85	MappedType get(const KeyType&) const;
86	MappedType get(RawKeyType) const;
87
88	// replaces value but not key if key is already present
89	// return value is a pair of the iterator to the key location,
90	// and a boolean that's true if a new value was actually added
91	pair<iterator, bool> set(const KeyType&, const MappedType&);
92	pair<iterator, bool> set(RawKeyType, const MappedType&);
93
94	// does nothing if key is already present
95	// return value is a pair of the iterator to the key location,
96	// and a boolean that's true if a new value was actually added
97	pair<iterator, bool> add(const KeyType&, const MappedType&);
98	pair<iterator, bool> add(RawKeyType, const MappedType&);
99
100	void remove(const KeyType&);
101	void remove(RawKeyType);
102	void remove(iterator);
103	void clear();
104
105	MappedType take(const KeyType&); // efficient combination of get with remove
106	MappedType take(RawKeyType); // efficient combination of get with remove
107
108	private:
109	pair<iterator, bool> inlineAdd(const KeyType&, const MappedType&);
110	pair<iterator, bool> inlineAdd(RawKeyType, const MappedType&);
111	void refAll();
112	void derefAll();
113
114	HashTableType m_impl;
115	};
116
117	template<typename T, typename U, typename V, typename W, typename X>
118	inline void HashMap<RefPtr<T>, U, V, W, X>::refAll()
119	{
120	HashTableRefCounter<HashTableType, ValueTraits>::refAll(m_impl);
121	}
122
123	template<typename T, typename U, typename V, typename W, typename X>
124	inline void HashMap<RefPtr<T>, U, V, W, X>::derefAll()
125	{
126	HashTableRefCounter<HashTableType, ValueTraits>::derefAll(m_impl);
127	}
128
129	template<typename T, typename U, typename V, typename W, typename X>
130	inline HashMap<RefPtr<T>, U, V, W, X>::HashMap()
131	{
132	}
133
134	template<typename T, typename U, typename V, typename W, typename X>
135	inline HashMap<RefPtr<T>, U, V, W, X>::HashMap(const HashMap& other)
136	: m_impl(other.m_impl)
137	{
138	refAll();
139	}
140
141	template<typename T, typename U, typename V, typename W, typename X>
142	inline HashMap<RefPtr<T>, U, V, W, X>& HashMap<RefPtr<T>, U, V, W, X>::operator=(const HashMap& other)
143	{
144	HashMap tmp(other);
145	swap(tmp);
146	return *this;
147	}
148
149	template<typename T, typename U, typename V, typename W, typename X>
150	inline void HashMap<RefPtr<T>, U, V, W, X>::swap(HashMap& other)
151	{
152	m_impl.swap(other.m_impl);
153	}
154
155	template<typename T, typename U, typename V, typename W, typename X>
156	inline HashMap<RefPtr<T>, U, V, W, X>::~HashMap()
157	{
158	derefAll();
159	}
160
161	template<typename T, typename U, typename V, typename W, typename X>
162	inline int HashMap<RefPtr<T>, U, V, W, X>::size() const
163	{
164	return m_impl.size();
165	}
166
167	template<typename T, typename U, typename V, typename W, typename X>
168	inline int HashMap<RefPtr<T>, U, V, W, X>::capacity() const
169	{
170	return m_impl.capacity();
171	}
172
173	template<typename T, typename U, typename V, typename W, typename X>
174	inline bool HashMap<RefPtr<T>, U, V, W, X>::isEmpty() const
175	{
176	return m_impl.isEmpty();
177	}
178
179	template<typename T, typename U, typename V, typename W, typename X>
180	inline typename HashMap<RefPtr<T>, U, V, W, X>::iterator HashMap<RefPtr<T>, U, V, W, X>::begin()
181	{
182	return m_impl.begin();
183	}
184
185	template<typename T, typename U, typename V, typename W, typename X>
186	inline typename HashMap<RefPtr<T>, U, V, W, X>::iterator HashMap<RefPtr<T>, U, V, W, X>::end()
187	{
188	return m_impl.end();
189	}
190
191	template<typename T, typename U, typename V, typename W, typename X>
192	inline typename HashMap<RefPtr<T>, U, V, W, X>::const_iterator HashMap<RefPtr<T>, U, V, W, X>::begin() const
193	{
194	return m_impl.begin();
195	}
196
197	template<typename T, typename U, typename V, typename W, typename X>
198	inline typename HashMap<RefPtr<T>, U, V, W, X>::const_iterator HashMap<RefPtr<T>, U, V, W, X>::end() const
199	{
200	return m_impl.end();
201	}
202
203	template<typename T, typename U, typename V, typename W, typename X>
204	inline typename HashMap<RefPtr<T>, U, V, W, X>::iterator HashMap<RefPtr<T>, U, V, W, X>::find(const KeyType& key)
205	{
206	return m_impl.find((const KeyStorageType)&key);
207	}
208
209	template<typename T, typename U, typename V, typename W, typename X>
210	inline typename HashMap<RefPtr<T>, U, V, W, X>::iterator HashMap<RefPtr<T>, U, V, W, X>::find(RawKeyType key)
211	{
212	return m_impl.find((const KeyStorageType)&key);
213	}
214
215	template<typename T, typename U, typename V, typename W, typename X>
216	inline typename HashMap<RefPtr<T>, U, V, W, X>::const_iterator HashMap<RefPtr<T>, U, V, W, X>::find(const KeyType& key) const
217	{
218	return m_impl.find((const KeyStorageType)&key);
219	}
220
221	template<typename T, typename U, typename V, typename W, typename X>
222	inline typename HashMap<RefPtr<T>, U, V, W, X>::const_iterator HashMap<RefPtr<T>, U, V, W, X>::find(RawKeyType key) const
223	{
224	return m_impl.find((const KeyStorageType)&key);
225	}
226
227	template<typename T, typename U, typename V, typename W, typename X>
228	inline bool HashMap<RefPtr<T>, U, V, W, X>::contains(const KeyType& key) const
229	{
230	return m_impl.contains((const KeyStorageType)&key);
231	}
232
233	template<typename T, typename U, typename V, typename W, typename X>
234	inline bool HashMap<RefPtr<T>, U, V, W, X>::contains(RawKeyType key) const
235	{
236	return m_impl.contains((const KeyStorageType)&key);
237	}
238
239	template<typename T, typename U, typename V, typename W, typename X>
240	inline pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool>
241	HashMap<RefPtr<T>, U, V, W, X>::inlineAdd(const KeyType& key, const MappedType& mapped)
242	{
243	const bool canReplaceDeletedKey = !KeyTraits::needsDestruction \|\| KeyStorageTraits::needsDestruction;
244	typedef HashMapTranslator<canReplaceDeletedKey, ValueType, ValueTraits, ValueStorageTraits, HashFunctions> TranslatorType;
245	return m_impl.template add<KeyType, MappedType, TranslatorType>(key, mapped);
246	}
247
248	template<typename T, typename U, typename V, typename W, typename X>
249	inline pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool>
250	HashMap<RefPtr<T>, U, V, W, X>::inlineAdd(RawKeyType key, const MappedType& mapped)
251	{
252	return inlineAdd((const KeyType)&key, mapped);
253	}
254
255	template<typename T, typename U, typename V, typename W, typename X>
256	pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool>
257	HashMap<RefPtr<T>, U, V, W, X>::set(const KeyType& key, const MappedType& mapped)
258	{
259	pair<iterator, bool> result = inlineAdd(key, mapped);
260	if (!result.second)
261	// add call above didn't change anything, so set the mapped value
262	result.first->second = mapped;
263	return result;
264	}
265
266	template<typename T, typename U, typename V, typename W, typename X>
267	pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool>
268	HashMap<RefPtr<T>, U, V, W, X>::set(RawKeyType key, const MappedType& mapped)
269	{
270	pair<iterator, bool> result = inlineAdd(key, mapped);
271	if (!result.second)
272	// add call above didn't change anything, so set the mapped value
273	result.first->second = mapped;
274	return result;
275	}
276
277	template<typename T, typename U, typename V, typename W, typename X>
278	pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool>
279	HashMap<RefPtr<T>, U, V, W, X>::add(const KeyType& key, const MappedType& mapped)
280	{
281	return inlineAdd(key, mapped);
282	}
283
284	template<typename T, typename U, typename V, typename W, typename X>
285	pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool>
286	HashMap<RefPtr<T>, U, V, W, X>::add(RawKeyType key, const MappedType& mapped)
287	{
288	return inlineAdd(key, mapped);
289	}
290
291	template<typename T, typename U, typename V, typename W, typename MappedTraits>
292	typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType
293	HashMap<RefPtr<T>, U, V, W, MappedTraits>::get(const KeyType& key) const
294	{
295	if (m_impl.isEmpty())
296	return MappedTraits::emptyValue();
297	ValueStorageType* entry = const_cast<HashTableType&>(m_impl).lookup((const KeyStorageType)&key);
298	if (!entry)
299	return MappedTraits::emptyValue();
300	return ((ValueType *)entry)->second;
301	}
302
303	template<typename T, typename U, typename V, typename W, typename MappedTraits>
304	typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType
305	HashMap<RefPtr<T>, U, V, W, MappedTraits>::get(RawKeyType key) const
306	{
307	if (m_impl.isEmpty())
308	return MappedTraits::emptyValue();
309	ValueStorageType* entry = const_cast<HashTableType&>(m_impl).lookup((const KeyStorageType)&key);
310	if (!entry)
311	return MappedTraits::emptyValue();
312	return ((ValueType *)entry)->second;
313	}
314
315	template<typename T, typename U, typename V, typename W, typename X>
316	inline void HashMap<RefPtr<T>, U, V, W, X>::remove(iterator it)
317	{
318	if (it.m_impl == m_impl.end())
319	return;
320	m_impl.checkTableConsistency();
321	RefCounter<ValueTraits, ValueStorageTraits>::deref(*it.m_impl);
322	m_impl.removeWithoutEntryConsistencyCheck(it.m_impl);
323	}
324
325	template<typename T, typename U, typename V, typename W, typename X>
326	inline void HashMap<RefPtr<T>, U, V, W, X>::remove(const KeyType& key)
327	{
328	remove(find(key));
329	}
330
331	template<typename T, typename U, typename V, typename W, typename X>
332	inline void HashMap<RefPtr<T>, U, V, W, X>::remove(RawKeyType key)
333	{
334	remove(find(key));
335	}
336
337	template<typename T, typename U, typename V, typename W, typename X>
338	inline void HashMap<RefPtr<T>, U, V, W, X>::clear()
339	{
340	derefAll();
341	m_impl.clear();
342	}
343
344	template<typename T, typename U, typename V, typename W, typename MappedTraits>
345	typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType
346	HashMap<RefPtr<T>, U, V, W, MappedTraits>::take(const KeyType& key)
347	{
348	// This can probably be made more efficient to avoid ref/deref churn.
349	iterator it = find(key);
350	if (it == end())
351	return MappedTraits::emptyValue();
352	typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType result = it->second;
353	remove(it);
354	return result;
355	}
356
357	template<typename T, typename U, typename V, typename W, typename MappedTraits>
358	typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType
359	HashMap<RefPtr<T>, U, V, W, MappedTraits>::take(RawKeyType key)
360	{
361	// This can probably be made more efficient to avoid ref/deref churn.
362	iterator it = find(key);
363	if (it == end())
364	return MappedTraits::emptyValue();
365	typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType result = it->second;
366	remove(it);
367	return result;
368	}
369
370	} // namespace WTF