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