File indexing completed on 2024-05-12 15:43:38
0001 /* 0002 * Copyright (C) 2005, 2006, 2007, 2008 Apple Inc. All rights reserved. 0003 * 0004 * This library is free software; you can redistribute it and/or 0005 * modify it under the terms of the GNU Library General Public 0006 * License as published by the Free Software Foundation; either 0007 * version 2 of the License, or (at your option) any later version. 0008 * 0009 * This library is distributed in the hope that it will be useful, 0010 * but WITHOUT ANY WARRANTY; without even the implied warranty of 0011 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 0012 * Library General Public License for more details. 0013 * 0014 * You should have received a copy of the GNU Library General Public License 0015 * along with this library; see the file COPYING.LIB. If not, write to 0016 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, 0017 * Boston, MA 02110-1301, USA. 0018 * 0019 */ 0020 0021 #ifndef WTF_HashMap_h 0022 #define WTF_HashMap_h 0023 0024 #include <wtf/HashTable.h> 0025 0026 namespace WTF 0027 { 0028 0029 template<typename PairType> struct PairFirstExtractor; 0030 0031 template<typename KeyArg, typename MappedArg, typename HashArg = typename DefaultHash<KeyArg>::Hash, 0032 typename KeyTraitsArg = HashTraits<KeyArg>, typename MappedTraitsArg = HashTraits<MappedArg> > 0033 class HashMap 0034 { 0035 private: 0036 typedef KeyTraitsArg KeyTraits; 0037 typedef MappedTraitsArg MappedTraits; 0038 typedef PairHashTraits<KeyTraits, MappedTraits> ValueTraits; 0039 0040 public: 0041 typedef typename KeyTraits::TraitType KeyType; 0042 typedef typename MappedTraits::TraitType MappedType; 0043 typedef typename ValueTraits::TraitType ValueType; 0044 0045 private: 0046 typedef HashArg HashFunctions; 0047 0048 typedef HashTable<KeyType, ValueType, PairFirstExtractor<ValueType>, 0049 HashFunctions, ValueTraits, KeyTraits> HashTableType; 0050 0051 public: 0052 typedef HashTableIteratorAdapter<HashTableType, ValueType> iterator; 0053 typedef HashTableConstIteratorAdapter<HashTableType, ValueType> const_iterator; 0054 0055 void swap(HashMap &); 0056 0057 int size() const; 0058 int capacity() const; 0059 bool isEmpty() const; 0060 0061 // iterators iterate over pairs of keys and values 0062 iterator begin(); 0063 iterator end(); 0064 const_iterator begin() const; 0065 const_iterator end() const; 0066 0067 iterator find(const KeyType &); 0068 const_iterator find(const KeyType &) const; 0069 bool contains(const KeyType &) const; 0070 MappedType get(const KeyType &) const; 0071 0072 // replaces value but not key if key is already present 0073 // return value is a pair of the iterator to the key location, 0074 // and a boolean that's true if a new value was actually added 0075 pair<iterator, bool> set(const KeyType &, const MappedType &); 0076 0077 // does nothing if key is already present 0078 // return value is a pair of the iterator to the key location, 0079 // and a boolean that's true if a new value was actually added 0080 pair<iterator, bool> add(const KeyType &, const MappedType &); 0081 0082 void remove(const KeyType &); 0083 void remove(iterator); 0084 void clear(); 0085 0086 MappedType take(const KeyType &); // efficient combination of get with remove 0087 0088 private: 0089 pair<iterator, bool> inlineAdd(const KeyType &, const MappedType &); 0090 0091 HashTableType m_impl; 0092 }; 0093 0094 template<typename PairType> struct PairFirstExtractor { 0095 static const typename PairType::first_type &extract(const PairType &p) 0096 { 0097 return p.first; 0098 } 0099 }; 0100 0101 template<typename ValueType, typename ValueTraits, typename HashFunctions> 0102 struct HashMapTranslator { 0103 typedef typename ValueType::first_type KeyType; 0104 typedef typename ValueType::second_type MappedType; 0105 0106 static unsigned hash(const KeyType &key) 0107 { 0108 return HashFunctions::hash(key); 0109 } 0110 static bool equal(const KeyType &a, const KeyType &b) 0111 { 0112 return HashFunctions::equal(a, b); 0113 } 0114 static void translate(ValueType &location, const KeyType &key, const MappedType &mapped) 0115 { 0116 location.first = key; 0117 location.second = mapped; 0118 } 0119 }; 0120 0121 template<typename T, typename U, typename V, typename W, typename X> 0122 inline void HashMap<T, U, V, W, X>::swap(HashMap &other) 0123 { 0124 m_impl.swap(other.m_impl); 0125 } 0126 0127 template<typename T, typename U, typename V, typename W, typename X> 0128 inline int HashMap<T, U, V, W, X>::size() const 0129 { 0130 return m_impl.size(); 0131 } 0132 0133 template<typename T, typename U, typename V, typename W, typename X> 0134 inline int HashMap<T, U, V, W, X>::capacity() const 0135 { 0136 return m_impl.capacity(); 0137 } 0138 0139 template<typename T, typename U, typename V, typename W, typename X> 0140 inline bool HashMap<T, U, V, W, X>::isEmpty() const 0141 { 0142 return m_impl.isEmpty(); 0143 } 0144 0145 template<typename T, typename U, typename V, typename W, typename X> 0146 inline typename HashMap<T, U, V, W, X>::iterator HashMap<T, U, V, W, X>::begin() 0147 { 0148 return m_impl.begin(); 0149 } 0150 0151 template<typename T, typename U, typename V, typename W, typename X> 0152 inline typename HashMap<T, U, V, W, X>::iterator HashMap<T, U, V, W, X>::end() 0153 { 0154 return m_impl.end(); 0155 } 0156 0157 template<typename T, typename U, typename V, typename W, typename X> 0158 inline typename HashMap<T, U, V, W, X>::const_iterator HashMap<T, U, V, W, X>::begin() const 0159 { 0160 return m_impl.begin(); 0161 } 0162 0163 template<typename T, typename U, typename V, typename W, typename X> 0164 inline typename HashMap<T, U, V, W, X>::const_iterator HashMap<T, U, V, W, X>::end() const 0165 { 0166 return m_impl.end(); 0167 } 0168 0169 template<typename T, typename U, typename V, typename W, typename X> 0170 inline typename HashMap<T, U, V, W, X>::iterator HashMap<T, U, V, W, X>::find(const KeyType &key) 0171 { 0172 return m_impl.find(key); 0173 } 0174 0175 template<typename T, typename U, typename V, typename W, typename X> 0176 inline typename HashMap<T, U, V, W, X>::const_iterator HashMap<T, U, V, W, X>::find(const KeyType &key) const 0177 { 0178 return m_impl.find(key); 0179 } 0180 0181 template<typename T, typename U, typename V, typename W, typename X> 0182 inline bool HashMap<T, U, V, W, X>::contains(const KeyType &key) const 0183 { 0184 return m_impl.contains(key); 0185 } 0186 0187 template<typename T, typename U, typename V, typename W, typename X> 0188 inline pair<typename HashMap<T, U, V, W, X>::iterator, bool> 0189 HashMap<T, U, V, W, X>::inlineAdd(const KeyType &key, const MappedType &mapped) 0190 { 0191 typedef HashMapTranslator<ValueType, ValueTraits, HashFunctions> TranslatorType; 0192 return m_impl.template add<KeyType, MappedType, TranslatorType>(key, mapped); 0193 } 0194 0195 template<typename T, typename U, typename V, typename W, typename X> 0196 pair<typename HashMap<T, U, V, W, X>::iterator, bool> 0197 HashMap<T, U, V, W, X>::set(const KeyType &key, const MappedType &mapped) 0198 { 0199 pair<iterator, bool> result = inlineAdd(key, mapped); 0200 if (!result.second) { 0201 // add call above didn't change anything, so set the mapped value 0202 result.first->second = mapped; 0203 } 0204 return result; 0205 } 0206 0207 template<typename T, typename U, typename V, typename W, typename X> 0208 pair<typename HashMap<T, U, V, W, X>::iterator, bool> 0209 HashMap<T, U, V, W, X>::add(const KeyType &key, const MappedType &mapped) 0210 { 0211 return inlineAdd(key, mapped); 0212 } 0213 0214 template<typename T, typename U, typename V, typename W, typename MappedTraits> 0215 typename HashMap<T, U, V, W, MappedTraits>::MappedType 0216 HashMap<T, U, V, W, MappedTraits>::get(const KeyType &key) const 0217 { 0218 ValueType *entry = const_cast<HashTableType &>(m_impl).lookup(key); 0219 if (!entry) { 0220 return MappedTraits::emptyValue(); 0221 } 0222 return entry->second; 0223 } 0224 0225 template<typename T, typename U, typename V, typename W, typename X> 0226 inline void HashMap<T, U, V, W, X>::remove(iterator it) 0227 { 0228 if (it.m_impl == m_impl.end()) { 0229 return; 0230 } 0231 m_impl.checkTableConsistency(); 0232 m_impl.removeWithoutEntryConsistencyCheck(it.m_impl); 0233 } 0234 0235 template<typename T, typename U, typename V, typename W, typename X> 0236 inline void HashMap<T, U, V, W, X>::remove(const KeyType &key) 0237 { 0238 remove(find(key)); 0239 } 0240 0241 template<typename T, typename U, typename V, typename W, typename X> 0242 inline void HashMap<T, U, V, W, X>::clear() 0243 { 0244 m_impl.clear(); 0245 } 0246 0247 template<typename T, typename U, typename V, typename W, typename MappedTraits> 0248 typename HashMap<T, U, V, W, MappedTraits>::MappedType 0249 HashMap<T, U, V, W, MappedTraits>::take(const KeyType &key) 0250 { 0251 // This can probably be made more efficient to avoid ref/deref churn. 0252 iterator it = find(key); 0253 if (it == end()) { 0254 return MappedTraits::emptyValue(); 0255 } 0256 typename HashMap<T, U, V, W, MappedTraits>::MappedType result = it->second; 0257 remove(it); 0258 return result; 0259 } 0260 0261 template<typename T, typename U, typename V, typename W, typename X> 0262 bool operator==(const HashMap<T, U, V, W, X> &a, const HashMap<T, U, V, W, X> &b) 0263 { 0264 if (a.size() != b.size()) { 0265 return false; 0266 } 0267 0268 typedef typename HashMap<T, U, V, W, X>::const_iterator const_iterator; 0269 0270 const_iterator end = a.end(); 0271 const_iterator notFound = b.end(); 0272 for (const_iterator it = a.begin(); it != end; ++it) { 0273 const_iterator bPos = b.find(it->first); 0274 if (bPos == notFound || it->second != bPos->second) { 0275 return false; 0276 } 0277 } 0278 0279 return true; 0280 } 0281 0282 template<typename T, typename U, typename V, typename W, typename X> 0283 inline bool operator!=(const HashMap<T, U, V, W, X> &a, const HashMap<T, U, V, W, X> &b) 0284 { 0285 return !(a == b); 0286 } 0287 0288 template<typename MappedType, typename HashTableType> 0289 void deleteAllPairSeconds(HashTableType &collection) 0290 { 0291 typedef typename HashTableType::const_iterator iterator; 0292 iterator end = collection.end(); 0293 for (iterator it = collection.begin(); it != end; ++it) { 0294 delete it->second; 0295 } 0296 } 0297 0298 template<typename T, typename U, typename V, typename W, typename X> 0299 inline void deleteAllValues(const HashMap<T, U, V, W, X> &collection) 0300 { 0301 deleteAllPairSeconds<typename HashMap<T, U, V, W, X>::MappedType>(collection); 0302 } 0303 0304 template<typename KeyType, typename HashTableType> 0305 void deleteAllPairFirsts(HashTableType &collection) 0306 { 0307 typedef typename HashTableType::const_iterator iterator; 0308 iterator end = collection.end(); 0309 for (iterator it = collection.begin(); it != end; ++it) { 0310 delete it->first; 0311 } 0312 } 0313 0314 template<typename T, typename U, typename V, typename W, typename X> 0315 inline void deleteAllKeys(const HashMap<T, U, V, W, X> &collection) 0316 { 0317 deleteAllPairFirsts<typename HashMap<T, U, V, W, X>::KeyType>(collection); 0318 } 0319 0320 template<typename T, typename U, typename V, typename W, typename X, typename Y> 0321 inline void copyKeysToVector(const HashMap<T, U, V, W, X> &collection, Y &vector) 0322 { 0323 typedef typename HashMap<T, U, V, W, X>::const_iterator::Keys iterator; 0324 0325 vector.resize(collection.size()); 0326 0327 iterator it = collection.begin().keys(); 0328 iterator end = collection.end().keys(); 0329 for (unsigned i = 0; it != end; ++it, ++i) { 0330 vector[i] = *it; 0331 } 0332 } 0333 0334 template<typename T, typename U, typename V, typename W, typename X, typename Y> 0335 inline void copyValuesToVector(const HashMap<T, U, V, W, X> &collection, Y &vector) 0336 { 0337 typedef typename HashMap<T, U, V, W, X>::const_iterator::Values iterator; 0338 0339 vector.resize(collection.size()); 0340 0341 iterator it = collection.begin().values(); 0342 iterator end = collection.end().values(); 0343 for (unsigned i = 0; it != end; ++it, ++i) { 0344 vector[i] = *it; 0345 } 0346 } 0347 0348 } // namespace WTF 0349 0350 using WTF::HashMap; 0351 0352 #include <wtf/RefPtrHashMap.h> 0353 0354 #endif /* WTF_HashMap_h */