1 /* 2 * Copyright (C) 2005, 2006, 2007, 2008 Apple Inc. All rights reserved. 3 * 4 * This library is free software; you can redistribute it and/or 5 * modify it under the terms of the GNU Library General Public 6 * License as published by the Free Software Foundation; either 7 * version 2 of the License, or (at your option) any later version. 8 * 9 * This library is distributed in the hope that it will be useful, 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 12 * Library General Public License for more details. 13 * 14 * You should have received a copy of the GNU Library General Public License 15 * along with this library; see the file COPYING.LIB. If not, write to 16 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, 17 * Boston, MA 02110-1301, USA. 18 * 19 */ 20 21 #ifndef WTF_HashMap_h 22 #define WTF_HashMap_h 23 24 #include "HashTable.h" 25 26 namespace WTF { 27 28 template<typename PairType> struct PairFirstExtractor; 29 30 template<typename KeyArg, typename MappedArg, typename HashArg = typename DefaultHash<KeyArg>::Hash, 31 typename KeyTraitsArg = HashTraits<KeyArg>, typename MappedTraitsArg = HashTraits<MappedArg> > 32 class HashMap : public FastAllocBase { 33 private: 34 typedef KeyTraitsArg KeyTraits; 35 typedef MappedTraitsArg MappedTraits; 36 typedef PairHashTraits<KeyTraits, MappedTraits> ValueTraits; 37 38 public: 39 typedef typename KeyTraits::TraitType KeyType; 40 typedef typename MappedTraits::TraitType MappedType; 41 typedef typename ValueTraits::TraitType ValueType; 42 43 private: 44 typedef HashArg HashFunctions; 45 46 typedef HashTable<KeyType, ValueType, PairFirstExtractor<ValueType>, 47 HashFunctions, ValueTraits, KeyTraits> HashTableType; 48 49 public: 50 typedef HashTableIteratorAdapter<HashTableType, ValueType> iterator; 51 typedef HashTableConstIteratorAdapter<HashTableType, ValueType> const_iterator; 52 53 void swap(HashMap&); 54 55 int size() const; 56 int capacity() const; 57 bool isEmpty() const; 58 59 // iterators iterate over pairs of keys and values 60 iterator begin(); 61 iterator end(); 62 const_iterator begin() const; 63 const_iterator end() const; 64 65 iterator find(const KeyType&); 66 const_iterator find(const KeyType&) const; 67 bool contains(const KeyType&) const; 68 MappedType get(const KeyType&) const; 69 70 // replaces value but not key if key is already present 71 // return value is a pair of the iterator to the key location, 72 // and a boolean that's true if a new value was actually added 73 pair<iterator, bool> set(const KeyType&, const MappedType&); 74 75 // does nothing if key is already present 76 // return value is a pair of the iterator to the key location, 77 // and a boolean that's true if a new value was actually added 78 pair<iterator, bool> add(const KeyType&, const MappedType&); 79 80 void remove(const KeyType&); 81 void remove(iterator); 82 void clear(); 83 84 MappedType take(const KeyType&); // efficient combination of get with remove 85 86 // An alternate version of find() that finds the object by hashing and comparing 87 // with some other type, to avoid the cost of type conversion. HashTranslator 88 // must have the following function members: 89 // static unsigned hash(const T&); 90 // static bool equal(const ValueType&, const T&); 91 template<typename T, typename HashTranslator> iterator find(const T&); 92 template<typename T, typename HashTranslator> const_iterator find(const T&) const; 93 template<typename T, typename HashTranslator> bool contains(const T&) const; 94 95 // An alternate version of add() that finds the object by hashing and comparing 96 // with some other type, to avoid the cost of type conversion if the object is already 97 // in the table. HashTranslator must have the following function members: 98 // static unsigned hash(const T&); 99 // static bool equal(const ValueType&, const T&); 100 // static translate(ValueType&, const T&, unsigned hashCode); 101 template<typename T, typename HashTranslator> pair<iterator, bool> add(const T&, const MappedType&); 102 103 void checkConsistency() const; 104 105 private: 106 pair<iterator, bool> inlineAdd(const KeyType&, const MappedType&); 107 108 HashTableType m_impl; 109 }; 110 111 template<typename PairType> struct PairFirstExtractor { 112 static const typename PairType::first_type& extract(const PairType& p) { return p.first; } 113 }; 114 115 template<typename ValueType, typename ValueTraits, typename HashFunctions> 116 struct HashMapTranslator { 117 typedef typename ValueType::first_type KeyType; 118 typedef typename ValueType::second_type MappedType; 119 120 static unsigned hash(const KeyType& key) { return HashFunctions::hash(key); } 121 static bool equal(const KeyType& a, const KeyType& b) { return HashFunctions::equal(a, b); } 122 static void translate(ValueType& location, const KeyType& key, const MappedType& mapped) 123 { 124 location.first = key; 125 location.second = mapped; 126 } 127 }; 128 129 template<typename ValueType, typename ValueTraits, typename T, typename Translator> 130 struct HashMapTranslatorAdapter { 131 typedef typename ValueType::first_type KeyType; 132 typedef typename ValueType::second_type MappedType; 133 134 static unsigned hash(const T& key) { return Translator::hash(key); } 135 static bool equal(const KeyType& a, const T& b) { return Translator::equal(a, b); } 136 static void translate(ValueType& location, const T& key, const MappedType&, unsigned hashCode) 137 { 138 Translator::translate(location.first, key, hashCode); 139 } 140 }; 141 142 template<typename T, typename U, typename V, typename W, typename X> 143 inline void HashMap<T, U, V, W, X>::swap(HashMap& other) 144 { 145 m_impl.swap(other.m_impl); 146 } 147 148 template<typename T, typename U, typename V, typename W, typename X> 149 inline int HashMap<T, U, V, W, X>::size() const 150 { 151 return m_impl.size(); 152 } 153 154 template<typename T, typename U, typename V, typename W, typename X> 155 inline int HashMap<T, U, V, W, X>::capacity() const 156 { 157 return m_impl.capacity(); 158 } 159 160 template<typename T, typename U, typename V, typename W, typename X> 161 inline bool HashMap<T, U, V, W, X>::isEmpty() const 162 { 163 return m_impl.isEmpty(); 164 } 165 166 template<typename T, typename U, typename V, typename W, typename X> 167 inline typename HashMap<T, U, V, W, X>::iterator HashMap<T, U, V, W, X>::begin() 168 { 169 return m_impl.begin(); 170 } 171 172 template<typename T, typename U, typename V, typename W, typename X> 173 inline typename HashMap<T, U, V, W, X>::iterator HashMap<T, U, V, W, X>::end() 174 { 175 return m_impl.end(); 176 } 177 178 template<typename T, typename U, typename V, typename W, typename X> 179 inline typename HashMap<T, U, V, W, X>::const_iterator HashMap<T, U, V, W, X>::begin() const 180 { 181 return m_impl.begin(); 182 } 183 184 template<typename T, typename U, typename V, typename W, typename X> 185 inline typename HashMap<T, U, V, W, X>::const_iterator HashMap<T, U, V, W, X>::end() const 186 { 187 return m_impl.end(); 188 } 189 190 template<typename T, typename U, typename V, typename W, typename X> 191 inline typename HashMap<T, U, V, W, X>::iterator HashMap<T, U, V, W, X>::find(const KeyType& key) 192 { 193 return m_impl.find(key); 194 } 195 196 template<typename T, typename U, typename V, typename W, typename X> 197 inline typename HashMap<T, U, V, W, X>::const_iterator HashMap<T, U, V, W, X>::find(const KeyType& key) const 198 { 199 return m_impl.find(key); 200 } 201 202 template<typename T, typename U, typename V, typename W, typename X> 203 inline bool HashMap<T, U, V, W, X>::contains(const KeyType& key) const 204 { 205 return m_impl.contains(key); 206 } 207 208 template<typename T, typename U, typename V, typename W, typename X> 209 template<typename TYPE, typename HashTranslator> 210 inline typename HashMap<T, U, V, W, X>::iterator 211 HashMap<T, U, V, W, X>::find(const TYPE& value) 212 { 213 typedef HashMapTranslatorAdapter<ValueType, ValueTraits, TYPE, HashTranslator> Adapter; 214 return m_impl.template find<TYPE, Adapter>(value); 215 } 216 217 template<typename T, typename U, typename V, typename W, typename X> 218 template<typename TYPE, typename HashTranslator> 219 inline typename HashMap<T, U, V, W, X>::const_iterator 220 HashMap<T, U, V, W, X>::find(const TYPE& value) const 221 { 222 typedef HashMapTranslatorAdapter<ValueType, ValueTraits, TYPE, HashTranslator> Adapter; 223 return m_impl.template find<TYPE, Adapter>(value); 224 } 225 226 template<typename T, typename U, typename V, typename W, typename X> 227 template<typename TYPE, typename HashTranslator> 228 inline bool 229 HashMap<T, U, V, W, X>::contains(const TYPE& value) const 230 { 231 typedef HashMapTranslatorAdapter<ValueType, ValueTraits, TYPE, HashTranslator> Adapter; 232 return m_impl.template contains<TYPE, Adapter>(value); 233 } 234 235 template<typename T, typename U, typename V, typename W, typename X> 236 inline pair<typename HashMap<T, U, V, W, X>::iterator, bool> 237 HashMap<T, U, V, W, X>::inlineAdd(const KeyType& key, const MappedType& mapped) 238 { 239 typedef HashMapTranslator<ValueType, ValueTraits, HashFunctions> TranslatorType; 240 return m_impl.template add<KeyType, MappedType, TranslatorType>(key, mapped); 241 } 242 243 template<typename T, typename U, typename V, typename W, typename X> 244 pair<typename HashMap<T, U, V, W, X>::iterator, bool> 245 HashMap<T, U, V, W, X>::set(const KeyType& key, const MappedType& mapped) 246 { 247 pair<iterator, bool> result = inlineAdd(key, mapped); 248 if (!result.second) { 249 // add call above didn't change anything, so set the mapped value 250 result.first->second = mapped; 251 } 252 return result; 253 } 254 255 template<typename T, typename U, typename V, typename W, typename X> 256 template<typename TYPE, typename HashTranslator> 257 pair<typename HashMap<T, U, V, W, X>::iterator, bool> 258 HashMap<T, U, V, W, X>::add(const TYPE& key, const MappedType& value) 259 { 260 typedef HashMapTranslatorAdapter<ValueType, ValueTraits, TYPE, HashTranslator> Adapter; 261 return m_impl.template addPassingHashCode<TYPE, MappedType, Adapter>(key, value); 262 } 263 264 template<typename T, typename U, typename V, typename W, typename X> 265 pair<typename HashMap<T, U, V, W, X>::iterator, bool> 266 HashMap<T, U, V, W, X>::add(const KeyType& key, const MappedType& mapped) 267 { 268 return inlineAdd(key, mapped); 269 } 270 271 template<typename T, typename U, typename V, typename W, typename MappedTraits> 272 typename HashMap<T, U, V, W, MappedTraits>::MappedType 273 HashMap<T, U, V, W, MappedTraits>::get(const KeyType& key) const 274 { 275 ValueType* entry = const_cast<HashTableType&>(m_impl).lookup(key); 276 if (!entry) 277 return MappedTraits::emptyValue(); 278 return entry->second; 279 } 280 281 template<typename T, typename U, typename V, typename W, typename X> 282 inline void HashMap<T, U, V, W, X>::remove(iterator it) 283 { 284 if (it.m_impl == m_impl.end()) 285 return; 286 m_impl.internalCheckTableConsistency(); 287 m_impl.removeWithoutEntryConsistencyCheck(it.m_impl); 288 } 289 290 template<typename T, typename U, typename V, typename W, typename X> 291 inline void HashMap<T, U, V, W, X>::remove(const KeyType& key) 292 { 293 remove(find(key)); 294 } 295 296 template<typename T, typename U, typename V, typename W, typename X> 297 inline void HashMap<T, U, V, W, X>::clear() 298 { 299 m_impl.clear(); 300 } 301 302 template<typename T, typename U, typename V, typename W, typename MappedTraits> 303 typename HashMap<T, U, V, W, MappedTraits>::MappedType 304 HashMap<T, U, V, W, MappedTraits>::take(const KeyType& key) 305 { 306 // This can probably be made more efficient to avoid ref/deref churn. 307 iterator it = find(key); 308 if (it == end()) 309 return MappedTraits::emptyValue(); 310 typename HashMap<T, U, V, W, MappedTraits>::MappedType result = it->second; 311 remove(it); 312 return result; 313 } 314 315 template<typename T, typename U, typename V, typename W, typename X> 316 inline void HashMap<T, U, V, W, X>::checkConsistency() const 317 { 318 m_impl.checkTableConsistency(); 319 } 320 321 322 template<typename T, typename U, typename V, typename W, typename X> 323 bool operator==(const HashMap<T, U, V, W, X>& a, const HashMap<T, U, V, W, X>& b) 324 { 325 if (a.size() != b.size()) 326 return false; 327 328 typedef typename HashMap<T, U, V, W, X>::const_iterator const_iterator; 329 330 const_iterator end = a.end(); 331 const_iterator notFound = b.end(); 332 for (const_iterator it = a.begin(); it != end; ++it) { 333 const_iterator bPos = b.find(it->first); 334 if (bPos == notFound || it->second != bPos->second) 335 return false; 336 } 337 338 return true; 339 } 340 341 template<typename T, typename U, typename V, typename W, typename X> 342 inline bool operator!=(const HashMap<T, U, V, W, X>& a, const HashMap<T, U, V, W, X>& b) 343 { 344 return !(a == b); 345 } 346 347 template<typename MappedType, typename HashTableType> 348 void deleteAllPairSeconds(HashTableType& collection) 349 { 350 typedef typename HashTableType::const_iterator iterator; 351 iterator end = collection.end(); 352 for (iterator it = collection.begin(); it != end; ++it) 353 delete it->second; 354 } 355 356 template<typename T, typename U, typename V, typename W, typename X> 357 inline void deleteAllValues(const HashMap<T, U, V, W, X>& collection) 358 { 359 deleteAllPairSeconds<typename HashMap<T, U, V, W, X>::MappedType>(collection); 360 } 361 362 template<typename KeyType, typename HashTableType> 363 void deleteAllPairFirsts(HashTableType& collection) 364 { 365 typedef typename HashTableType::const_iterator iterator; 366 iterator end = collection.end(); 367 for (iterator it = collection.begin(); it != end; ++it) 368 delete it->first; 369 } 370 371 template<typename T, typename U, typename V, typename W, typename X> 372 inline void deleteAllKeys(const HashMap<T, U, V, W, X>& collection) 373 { 374 deleteAllPairFirsts<typename HashMap<T, U, V, W, X>::KeyType>(collection); 375 } 376 377 template<typename T, typename U, typename V, typename W, typename X, typename Y> 378 inline void copyKeysToVector(const HashMap<T, U, V, W, X>& collection, Y& vector) 379 { 380 typedef typename HashMap<T, U, V, W, X>::const_iterator::Keys iterator; 381 382 vector.resize(collection.size()); 383 384 iterator it = collection.begin().keys(); 385 iterator end = collection.end().keys(); 386 for (unsigned i = 0; it != end; ++it, ++i) 387 vector[i] = *it; 388 } 389 390 template<typename T, typename U, typename V, typename W, typename X, typename Y> 391 inline void copyValuesToVector(const HashMap<T, U, V, W, X>& collection, Y& vector) 392 { 393 typedef typename HashMap<T, U, V, W, X>::const_iterator::Values iterator; 394 395 vector.resize(collection.size()); 396 397 iterator it = collection.begin().values(); 398 iterator end = collection.end().values(); 399 for (unsigned i = 0; it != end; ++it, ++i) 400 vector[i] = *it; 401 } 402 403 } // namespace WTF 404 405 using WTF::HashMap; 406 407 #include "RefPtrHashMap.h" 408 409 #endif /* WTF_HashMap_h */ 410
