/* * Copyright (C) 2005, 2006, 2007, 2008 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: Find a better way that doesn't require an entire copy of the HashMap template. template struct RefPtrHashMapRawKeyTranslator { typedef typename ValueType::first_type KeyType; typedef typename ValueType::second_type MappedType; typedef typename ValueTraits::FirstTraits KeyTraits; typedef typename ValueTraits::SecondTraits MappedTraits; static unsigned hash(RawKeyType key) { return HashFunctions::hash(key); } static bool equal(const KeyType& a, RawKeyType b) { return HashFunctions::equal(a, b); } static void translate(ValueType& location, RawKeyType key, const MappedType& mapped) { location.first = key; location.second = mapped; } }; template class HashMap, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg> : public FastAllocBase { private: typedef KeyTraitsArg KeyTraits; typedef MappedTraitsArg MappedTraits; typedef PairHashTraits 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 HashTable, HashFunctions, ValueTraits, KeyTraits> HashTableType; typedef RefPtrHashMapRawKeyTranslator RawKeyTranslator; public: typedef HashTableIteratorAdapter iterator; typedef HashTableConstIteratorAdapter const_iterator; 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; MappedType inlineGet(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 set(const KeyType&, const MappedType&); pair 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 add(const KeyType&, const MappedType&); pair 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 inlineAdd(const KeyType&, const MappedType&); pair inlineAdd(RawKeyType, const MappedType&); HashTableType m_impl; }; template inline void HashMap, U, V, W, X>::swap(HashMap& other) { m_impl.swap(other.m_impl); } template inline int HashMap, U, V, W, X>::size() const { return m_impl.size(); } template inline int HashMap, U, V, W, X>::capacity() const { return m_impl.capacity(); } template inline bool HashMap, U, V, W, X>::isEmpty() const { return m_impl.isEmpty(); } template inline typename HashMap, U, V, W, X>::iterator HashMap, U, V, W, X>::begin() { return m_impl.begin(); } template inline typename HashMap, U, V, W, X>::iterator HashMap, U, V, W, X>::end() { return m_impl.end(); } template inline typename HashMap, U, V, W, X>::const_iterator HashMap, U, V, W, X>::begin() const { return m_impl.begin(); } template inline typename HashMap, U, V, W, X>::const_iterator HashMap, U, V, W, X>::end() const { return m_impl.end(); } template inline typename HashMap, U, V, W, X>::iterator HashMap, U, V, W, X>::find(const KeyType& key) { return m_impl.find(key); } template inline typename HashMap, U, V, W, X>::iterator HashMap, U, V, W, X>::find(RawKeyType key) { return m_impl.template find(key); } template inline typename HashMap, U, V, W, X>::const_iterator HashMap, U, V, W, X>::find(const KeyType& key) const { return m_impl.find(key); } template inline typename HashMap, U, V, W, X>::const_iterator HashMap, U, V, W, X>::find(RawKeyType key) const { return m_impl.template find(key); } template inline bool HashMap, U, V, W, X>::contains(const KeyType& key) const { return m_impl.contains(key); } template inline bool HashMap, U, V, W, X>::contains(RawKeyType key) const { return m_impl.template contains(key); } template inline pair, U, V, W, X>::iterator, bool> HashMap, U, V, W, X>::inlineAdd(const KeyType& key, const MappedType& mapped) { typedef HashMapTranslator TranslatorType; return m_impl.template add(key, mapped); } template inline pair, U, V, W, X>::iterator, bool> HashMap, U, V, W, X>::inlineAdd(RawKeyType key, const MappedType& mapped) { return m_impl.template add(key, mapped); } template pair, U, V, W, X>::iterator, bool> HashMap, U, V, W, X>::set(const KeyType& key, const MappedType& mapped) { pair 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 pair, U, V, W, X>::iterator, bool> HashMap, U, V, W, X>::set(RawKeyType key, const MappedType& mapped) { pair 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 pair, U, V, W, X>::iterator, bool> HashMap, U, V, W, X>::add(const KeyType& key, const MappedType& mapped) { return inlineAdd(key, mapped); } template pair, U, V, W, X>::iterator, bool> HashMap, U, V, W, X>::add(RawKeyType key, const MappedType& mapped) { return inlineAdd(key, mapped); } template typename HashMap, U, V, W, MappedTraits>::MappedType HashMap, U, V, W, MappedTraits>::get(const KeyType& key) const { ValueType* entry = const_cast(m_impl).lookup(key); if (!entry) return MappedTraits::emptyValue(); return entry->second; } template typename HashMap, U, V, W, MappedTraits>::MappedType inline HashMap, U, V, W, MappedTraits>::inlineGet(RawKeyType key) const { ValueType* entry = const_cast(m_impl).template lookup(key); if (!entry) return MappedTraits::emptyValue(); return entry->second; } template typename HashMap, U, V, W, MappedTraits>::MappedType HashMap, U, V, W, MappedTraits>::get(RawKeyType key) const { return inlineGet(key); } template inline void HashMap, U, V, W, X>::remove(iterator it) { if (it.m_impl == m_impl.end()) return; m_impl.checkTableConsistency(); m_impl.removeWithoutEntryConsistencyCheck(it.m_impl); } template inline void HashMap, U, V, W, X>::remove(const KeyType& key) { remove(find(key)); } template inline void HashMap, U, V, W, X>::remove(RawKeyType key) { remove(find(key)); } template inline void HashMap, U, V, W, X>::clear() { m_impl.clear(); } template typename HashMap, U, V, W, MappedTraits>::MappedType HashMap, 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, U, V, W, MappedTraits>::MappedType result = it->second; remove(it); return result; } template typename HashMap, U, V, W, MappedTraits>::MappedType HashMap, 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, U, V, W, MappedTraits>::MappedType result = it->second; remove(it); return result; } } // namespace WTF