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