1 /* 2 * Copyright (C) 2005, 2006, 2007, 2008, 2011 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 "wtf/FastAllocBase.h" 25 #include "wtf/HashTable.h" 26 27 namespace WTF { 28 29 template<typename KeyTraits, typename MappedTraits> struct HashMapValueTraits; 30 31 template<typename T> struct ReferenceTypeMaker { 32 typedef T& ReferenceType; 33 }; 34 template<typename T> struct ReferenceTypeMaker<T&> { 35 typedef T& ReferenceType; 36 }; 37 38 template<typename T> struct KeyValuePairKeyExtractor { 39 static const typename T::KeyType& extract(const T& p) { return p.key; } 40 }; 41 42 template<typename KeyArg, typename MappedArg, typename HashArg = typename DefaultHash<KeyArg>::Hash, 43 typename KeyTraitsArg = HashTraits<KeyArg>, typename MappedTraitsArg = HashTraits<MappedArg> > 44 class HashMap { 45 WTF_MAKE_FAST_ALLOCATED; 46 private: 47 typedef KeyTraitsArg KeyTraits; 48 typedef MappedTraitsArg MappedTraits; 49 typedef HashMapValueTraits<KeyTraits, MappedTraits> ValueTraits; 50 51 public: 52 typedef typename KeyTraits::TraitType KeyType; 53 typedef typename MappedTraits::TraitType MappedType; 54 typedef typename ValueTraits::TraitType ValueType; 55 56 private: 57 typedef typename MappedTraits::PassInType MappedPassInType; 58 typedef typename MappedTraits::PassOutType MappedPassOutType; 59 typedef typename MappedTraits::PeekType MappedPeekType; 60 61 typedef typename ReferenceTypeMaker<MappedPassInType>::ReferenceType MappedPassInReferenceType; 62 63 typedef HashArg HashFunctions; 64 65 typedef HashTable<KeyType, ValueType, KeyValuePairKeyExtractor<ValueType>, 66 HashFunctions, ValueTraits, KeyTraits> HashTableType; 67 68 class HashMapKeysProxy; 69 class HashMapValuesProxy; 70 71 public: 72 typedef HashTableIteratorAdapter<HashTableType, ValueType> iterator; 73 typedef HashTableConstIteratorAdapter<HashTableType, ValueType> const_iterator; 74 typedef typename HashTableType::AddResult AddResult; 75 76 public: 77 void swap(HashMap&); 78 79 unsigned size() const; 80 unsigned capacity() const; 81 bool isEmpty() const; 82 83 // iterators iterate over pairs of keys and values 84 iterator begin(); 85 iterator end(); 86 const_iterator begin() const; 87 const_iterator end() const; 88 89 HashMapKeysProxy& keys() { return static_cast<HashMapKeysProxy&>(*this); } 90 const HashMapKeysProxy& keys() const { return static_cast<const HashMapKeysProxy&>(*this); } 91 92 HashMapValuesProxy& values() { return static_cast<HashMapValuesProxy&>(*this); } 93 const HashMapValuesProxy& values() const { return static_cast<const HashMapValuesProxy&>(*this); } 94 95 iterator find(const KeyType&); 96 const_iterator find(const KeyType&) const; 97 bool contains(const KeyType&) const; 98 MappedPeekType get(const KeyType&) const; 99 100 // replaces value but not key if key is already present 101 // return value is a pair of the iterator to the key location, 102 // and a boolean that's true if a new value was actually added 103 AddResult set(const KeyType&, MappedPassInType); 104 105 // does nothing if key is already present 106 // return value is a pair of the iterator to the key location, 107 // and a boolean that's true if a new value was actually added 108 AddResult add(const KeyType&, MappedPassInType); 109 110 void remove(const KeyType&); 111 void remove(iterator); 112 void clear(); 113 114 MappedPassOutType take(const KeyType&); // efficient combination of get with remove 115 116 // An alternate version of find() that finds the object by hashing and comparing 117 // with some other type, to avoid the cost of type conversion. HashTranslator 118 // must have the following function members: 119 // static unsigned hash(const T&); 120 // static bool equal(const ValueType&, const T&); 121 template<typename HashTranslator, typename T> iterator find(const T&); 122 template<typename HashTranslator, typename T> const_iterator find(const T&) const; 123 template<typename HashTranslator, typename T> bool contains(const T&) const; 124 125 // An alternate version of add() that finds the object by hashing and comparing 126 // with some other type, to avoid the cost of type conversion if the object is already 127 // in the table. HashTranslator must have the following function members: 128 // static unsigned hash(const T&); 129 // static bool equal(const ValueType&, const T&); 130 // static translate(ValueType&, const T&, unsigned hashCode); 131 template<typename HashTranslator, typename T> AddResult add(const T&, MappedPassInType); 132 133 static bool isValidKey(const KeyType&); 134 135 private: 136 AddResult inlineAdd(const KeyType&, MappedPassInReferenceType); 137 138 HashTableType m_impl; 139 }; 140 141 template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg> 142 class HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg>::HashMapKeysProxy : 143 private HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg> { 144 public: 145 typedef HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg> HashMapType; 146 typedef typename HashMapType::iterator::Keys iterator; 147 typedef typename HashMapType::const_iterator::Keys const_iterator; 148 149 iterator begin() 150 { 151 return HashMapType::begin().keys(); 152 } 153 154 iterator end() 155 { 156 return HashMapType::end().keys(); 157 } 158 159 const_iterator begin() const 160 { 161 return HashMapType::begin().keys(); 162 } 163 164 const_iterator end() const 165 { 166 return HashMapType::end().keys(); 167 } 168 169 private: 170 friend class HashMap; 171 172 // These are intentionally not implemented. 173 HashMapKeysProxy(); 174 HashMapKeysProxy(const HashMapKeysProxy&); 175 HashMapKeysProxy& operator=(const HashMapKeysProxy&); 176 ~HashMapKeysProxy(); 177 }; 178 179 template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg> 180 class HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg>::HashMapValuesProxy : 181 private HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg> { 182 public: 183 typedef HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg> HashMapType; 184 typedef typename HashMapType::iterator::Values iterator; 185 typedef typename HashMapType::const_iterator::Values const_iterator; 186 187 iterator begin() 188 { 189 return HashMapType::begin().values(); 190 } 191 192 iterator end() 193 { 194 return HashMapType::end().values(); 195 } 196 197 const_iterator begin() const 198 { 199 return HashMapType::begin().values(); 200 } 201 202 const_iterator end() const 203 { 204 return HashMapType::end().values(); 205 } 206 207 private: 208 friend class HashMap; 209 210 // These are intentionally not implemented. 211 HashMapValuesProxy(); 212 HashMapValuesProxy(const HashMapValuesProxy&); 213 HashMapValuesProxy& operator=(const HashMapValuesProxy&); 214 ~HashMapValuesProxy(); 215 }; 216 217 template<typename KeyTraits, typename MappedTraits> struct HashMapValueTraits : KeyValuePairHashTraits<KeyTraits, MappedTraits> { 218 static const bool hasIsEmptyValueFunction = true; 219 static bool isEmptyValue(const typename KeyValuePairHashTraits<KeyTraits, MappedTraits>::TraitType& value) 220 { 221 return isHashTraitsEmptyValue<KeyTraits>(value.key); 222 } 223 }; 224 225 template<typename ValueTraits, typename HashFunctions> 226 struct HashMapTranslator { 227 template<typename T> static unsigned hash(const T& key) { return HashFunctions::hash(key); } 228 template<typename T, typename U> static bool equal(const T& a, const U& b) { return HashFunctions::equal(a, b); } 229 template<typename T, typename U, typename V> static void translate(T& location, const U& key, const V& mapped) 230 { 231 location.key = key; 232 ValueTraits::ValueTraits::store(mapped, location.value); 233 } 234 }; 235 236 template<typename ValueTraits, typename Translator> 237 struct HashMapTranslatorAdapter { 238 template<typename T> static unsigned hash(const T& key) { return Translator::hash(key); } 239 template<typename T, typename U> static bool equal(const T& a, const U& b) { return Translator::equal(a, b); } 240 template<typename T, typename U, typename V> static void translate(T& location, const U& key, const V& mapped, unsigned hashCode) 241 { 242 Translator::translate(location.key, key, hashCode); 243 ValueTraits::ValueTraits::store(mapped, location.value); 244 } 245 }; 246 247 template<typename T, typename U, typename V, typename W, typename X> 248 inline void HashMap<T, U, V, W, X>::swap(HashMap& other) 249 { 250 m_impl.swap(other.m_impl); 251 } 252 253 template<typename T, typename U, typename V, typename W, typename X> 254 inline unsigned HashMap<T, U, V, W, X>::size() const 255 { 256 return m_impl.size(); 257 } 258 259 template<typename T, typename U, typename V, typename W, typename X> 260 inline unsigned HashMap<T, U, V, W, X>::capacity() const 261 { 262 return m_impl.capacity(); 263 } 264 265 template<typename T, typename U, typename V, typename W, typename X> 266 inline bool HashMap<T, U, V, W, X>::isEmpty() const 267 { 268 return m_impl.isEmpty(); 269 } 270 271 template<typename T, typename U, typename V, typename W, typename X> 272 inline typename HashMap<T, U, V, W, X>::iterator HashMap<T, U, V, W, X>::begin() 273 { 274 return m_impl.begin(); 275 } 276 277 template<typename T, typename U, typename V, typename W, typename X> 278 inline typename HashMap<T, U, V, W, X>::iterator HashMap<T, U, V, W, X>::end() 279 { 280 return m_impl.end(); 281 } 282 283 template<typename T, typename U, typename V, typename W, typename X> 284 inline typename HashMap<T, U, V, W, X>::const_iterator HashMap<T, U, V, W, X>::begin() const 285 { 286 return m_impl.begin(); 287 } 288 289 template<typename T, typename U, typename V, typename W, typename X> 290 inline typename HashMap<T, U, V, W, X>::const_iterator HashMap<T, U, V, W, X>::end() const 291 { 292 return m_impl.end(); 293 } 294 295 template<typename T, typename U, typename V, typename W, typename X> 296 inline typename HashMap<T, U, V, W, X>::iterator HashMap<T, U, V, W, X>::find(const KeyType& key) 297 { 298 return m_impl.find(key); 299 } 300 301 template<typename T, typename U, typename V, typename W, typename X> 302 inline typename HashMap<T, U, V, W, X>::const_iterator HashMap<T, U, V, W, X>::find(const KeyType& key) const 303 { 304 return m_impl.find(key); 305 } 306 307 template<typename T, typename U, typename V, typename W, typename X> 308 inline bool HashMap<T, U, V, W, X>::contains(const KeyType& key) const 309 { 310 return m_impl.contains(key); 311 } 312 313 template<typename T, typename U, typename V, typename W, typename X> 314 template<typename HashTranslator, typename TYPE> 315 inline typename HashMap<T, U, V, W, X>::iterator 316 HashMap<T, U, V, W, X>::find(const TYPE& value) 317 { 318 return m_impl.template find<HashMapTranslatorAdapter<ValueTraits, HashTranslator> >(value); 319 } 320 321 template<typename T, typename U, typename V, typename W, typename X> 322 template<typename HashTranslator, typename TYPE> 323 inline typename HashMap<T, U, V, W, X>::const_iterator 324 HashMap<T, U, V, W, X>::find(const TYPE& value) const 325 { 326 return m_impl.template find<HashMapTranslatorAdapter<ValueTraits, HashTranslator> >(value); 327 } 328 329 template<typename T, typename U, typename V, typename W, typename X> 330 template<typename HashTranslator, typename TYPE> 331 inline bool 332 HashMap<T, U, V, W, X>::contains(const TYPE& value) const 333 { 334 return m_impl.template contains<HashMapTranslatorAdapter<ValueTraits, HashTranslator> >(value); 335 } 336 337 template<typename T, typename U, typename V, typename W, typename X> 338 typename HashMap<T, U, V, W, X>::AddResult 339 HashMap<T, U, V, W, X>::inlineAdd(const KeyType& key, MappedPassInReferenceType mapped) 340 { 341 return m_impl.template add<HashMapTranslator<ValueTraits, HashFunctions> >(key, mapped); 342 } 343 344 template<typename T, typename U, typename V, typename W, typename X> 345 typename HashMap<T, U, V, W, X>::AddResult 346 HashMap<T, U, V, W, X>::set(const KeyType& key, MappedPassInType mapped) 347 { 348 AddResult result = inlineAdd(key, mapped); 349 if (!result.isNewEntry) { 350 // The inlineAdd call above found an existing hash table entry; we need to set the mapped value. 351 MappedTraits::store(mapped, result.iterator->value); 352 } 353 return result; 354 } 355 356 template<typename T, typename U, typename V, typename W, typename X> 357 template<typename HashTranslator, typename TYPE> 358 typename HashMap<T, U, V, W, X>::AddResult 359 HashMap<T, U, V, W, X>::add(const TYPE& key, MappedPassInType value) 360 { 361 return m_impl.template addPassingHashCode<HashMapTranslatorAdapter<ValueTraits, HashTranslator> >(key, value); 362 } 363 364 template<typename T, typename U, typename V, typename W, typename X> 365 typename HashMap<T, U, V, W, X>::AddResult 366 HashMap<T, U, V, W, X>::add(const KeyType& key, MappedPassInType mapped) 367 { 368 return inlineAdd(key, mapped); 369 } 370 371 template<typename T, typename U, typename V, typename W, typename MappedTraits> 372 typename HashMap<T, U, V, W, MappedTraits>::MappedPeekType 373 HashMap<T, U, V, W, MappedTraits>::get(const KeyType& key) const 374 { 375 ValueType* entry = const_cast<HashTableType&>(m_impl).lookup(key); 376 if (!entry) 377 return MappedTraits::peek(MappedTraits::emptyValue()); 378 return MappedTraits::peek(entry->value); 379 } 380 381 template<typename T, typename U, typename V, typename W, typename X> 382 inline void HashMap<T, U, V, W, X>::remove(iterator it) 383 { 384 m_impl.remove(it.m_impl); 385 } 386 387 template<typename T, typename U, typename V, typename W, typename X> 388 inline void HashMap<T, U, V, W, X>::remove(const KeyType& key) 389 { 390 remove(find(key)); 391 } 392 393 template<typename T, typename U, typename V, typename W, typename X> 394 inline void HashMap<T, U, V, W, X>::clear() 395 { 396 m_impl.clear(); 397 } 398 399 template<typename T, typename U, typename V, typename W, typename MappedTraits> 400 typename HashMap<T, U, V, W, MappedTraits>::MappedPassOutType 401 HashMap<T, U, V, W, MappedTraits>::take(const KeyType& key) 402 { 403 iterator it = find(key); 404 if (it == end()) 405 return MappedTraits::passOut(MappedTraits::emptyValue()); 406 MappedPassOutType result = MappedTraits::passOut(it->value); 407 remove(it); 408 return result; 409 } 410 411 template<typename T, typename U, typename V, typename W, typename X> 412 inline bool HashMap<T, U, V, W, X>::isValidKey(const KeyType& key) 413 { 414 if (KeyTraits::isDeletedValue(key)) 415 return false; 416 417 if (HashFunctions::safeToCompareToEmptyOrDeleted) { 418 if (key == KeyTraits::emptyValue()) 419 return false; 420 } else { 421 if (isHashTraitsEmptyValue<KeyTraits>(key)) 422 return false; 423 } 424 425 return true; 426 } 427 428 template<typename T, typename U, typename V, typename W, typename X> 429 bool operator==(const HashMap<T, U, V, W, X>& a, const HashMap<T, U, V, W, X>& b) 430 { 431 if (a.size() != b.size()) 432 return false; 433 434 typedef typename HashMap<T, U, V, W, X>::const_iterator const_iterator; 435 436 const_iterator aEnd = a.end(); 437 const_iterator bEnd = b.end(); 438 for (const_iterator it = a.begin(); it != aEnd; ++it) { 439 const_iterator bPos = b.find(it->key); 440 if (bPos == bEnd || it->value != bPos->value) 441 return false; 442 } 443 444 return true; 445 } 446 447 template<typename T, typename U, typename V, typename W, typename X> 448 inline bool operator!=(const HashMap<T, U, V, W, X>& a, const HashMap<T, U, V, W, X>& b) 449 { 450 return !(a == b); 451 } 452 453 template<typename T, typename U, typename V, typename W, typename X> 454 inline void deleteAllValues(const HashMap<T, U, V, W, X>& collection) 455 { 456 typedef typename HashMap<T, U, V, W, X>::const_iterator iterator; 457 iterator end = collection.end(); 458 for (iterator it = collection.begin(); it != end; ++it) 459 delete it->value; 460 } 461 462 template<typename T, typename U, typename V, typename W, typename X> 463 inline void deleteAllKeys(const HashMap<T, U, V, W, X>& collection) 464 { 465 typedef typename HashMap<T, U, V, W, X>::const_iterator iterator; 466 iterator end = collection.end(); 467 for (iterator it = collection.begin(); it != end; ++it) 468 delete it->key; 469 } 470 471 template<typename T, typename U, typename V, typename W, typename X, typename Y> 472 inline void copyKeysToVector(const HashMap<T, U, V, W, X>& collection, Y& vector) 473 { 474 typedef typename HashMap<T, U, V, W, X>::const_iterator::Keys iterator; 475 476 vector.resize(collection.size()); 477 478 iterator it = collection.begin().keys(); 479 iterator end = collection.end().keys(); 480 for (unsigned i = 0; it != end; ++it, ++i) 481 vector[i] = *it; 482 } 483 484 template<typename T, typename U, typename V, typename W, typename X, typename Y> 485 inline void copyValuesToVector(const HashMap<T, U, V, W, X>& collection, Y& vector) 486 { 487 typedef typename HashMap<T, U, V, W, X>::const_iterator::Values iterator; 488 489 vector.resize(collection.size()); 490 491 iterator it = collection.begin().values(); 492 iterator end = collection.end().values(); 493 for (unsigned i = 0; it != end; ++it, ++i) 494 vector[i] = *it; 495 } 496 497 } // namespace WTF 498 499 using WTF::HashMap; 500 501 #include "wtf/RefPtrHashMap.h" 502 503 #endif /* WTF_HashMap_h */ 504
