1 /////////////////////////////////////////////////////////////////////////////// 2 // Copyright (c) Electronic Arts Inc. All rights reserved. 3 /////////////////////////////////////////////////////////////////////////////// 4 5 /////////////////////////////////////////////////////////////////////////////// 6 // This file is based on the TR1 (technical report 1) reference implementation 7 // of the unordered_set/unordered_map C++ classes as of about 4/2005. Most likely 8 // many or all C++ library vendors' implementations of this classes will be 9 // based off of the reference version and so will look pretty similar to this 10 // file as well as other vendors' versions. 11 /////////////////////////////////////////////////////////////////////////////// 12 13 14 #ifndef EASTL_HASH_MAP_H 15 #define EASTL_HASH_MAP_H 16 17 18 #include <EASTL/internal/config.h> 19 #include <EASTL/internal/hashtable.h> 20 #include <EASTL/functional.h> 21 #include <EASTL/utility.h> 22 23 #if defined(EA_PRAGMA_ONCE_SUPPORTED) 24 #pragma once // Some compilers (e.g. VC++) benefit significantly from using this. We've measured 3-4% build speed improvements in apps as a result. 25 #endif 26 27 28 29 namespace eastl 30 { 31 32 /// EASTL_HASH_MAP_DEFAULT_NAME 33 /// 34 /// Defines a default container name in the absence of a user-provided name. 35 /// 36 #ifndef EASTL_HASH_MAP_DEFAULT_NAME 37 #define EASTL_HASH_MAP_DEFAULT_NAME EASTL_DEFAULT_NAME_PREFIX " hash_map" // Unless the user overrides something, this is "EASTL hash_map". 38 #endif 39 40 41 /// EASTL_HASH_MULTIMAP_DEFAULT_NAME 42 /// 43 /// Defines a default container name in the absence of a user-provided name. 44 /// 45 #ifndef EASTL_HASH_MULTIMAP_DEFAULT_NAME 46 #define EASTL_HASH_MULTIMAP_DEFAULT_NAME EASTL_DEFAULT_NAME_PREFIX " hash_multimap" // Unless the user overrides something, this is "EASTL hash_multimap". 47 #endif 48 49 50 /// EASTL_HASH_MAP_DEFAULT_ALLOCATOR 51 /// 52 #ifndef EASTL_HASH_MAP_DEFAULT_ALLOCATOR 53 #define EASTL_HASH_MAP_DEFAULT_ALLOCATOR allocator_type(EASTL_HASH_MAP_DEFAULT_NAME) 54 #endif 55 56 /// EASTL_HASH_MULTIMAP_DEFAULT_ALLOCATOR 57 /// 58 #ifndef EASTL_HASH_MULTIMAP_DEFAULT_ALLOCATOR 59 #define EASTL_HASH_MULTIMAP_DEFAULT_ALLOCATOR allocator_type(EASTL_HASH_MULTIMAP_DEFAULT_NAME) 60 #endif 61 62 63 64 /// hash_map 65 /// 66 /// Implements a hash_map, which is a hashed associative container. 67 /// Lookups are O(1) (that is, they are fast) but the container is 68 /// not sorted. Note that lookups are only O(1) if the hash table 69 /// is well-distributed (non-colliding). The lookup approaches 70 /// O(n) behavior as the table becomes increasingly poorly distributed. 71 /// 72 /// set_max_load_factor 73 /// If you want to make a hashtable never increase its bucket usage, 74 /// call set_max_load_factor with a very high value such as 100000.f. 75 /// 76 /// bCacheHashCode 77 /// We provide the boolean bCacheHashCode template parameter in order 78 /// to allow the storing of the hash code of the key within the map. 79 /// When this option is disabled, the rehashing of the table will 80 /// call the hash function on the key. Setting bCacheHashCode to true 81 /// is useful for cases whereby the calculation of the hash value for 82 /// a contained object is very expensive. 83 /// 84 /// find_as 85 /// In order to support the ability to have a hashtable of strings but 86 /// be able to do efficiently lookups via char pointers (i.e. so they 87 /// aren't converted to string objects), we provide the find_as 88 /// function. This function allows you to do a find with a key of a 89 /// type other than the hashtable key type. 90 /// 91 /// Example find_as usage: 92 /// hash_map<string, int> hashMap; 93 /// i = hashMap.find_as("hello"); // Use default hash and compare. 94 /// 95 /// Example find_as usage (namespaces omitted for brevity): 96 /// hash_map<string, int> hashMap; 97 /// i = hashMap.find_as("hello", hash<char*>(), equal_to_2<string, char*>()); 98 /// 99 template <typename Key, typename T, typename Hash = eastl::hash<Key>, typename Predicate = eastl::equal_to<Key>, 100 typename Allocator = EASTLAllocatorType, bool bCacheHashCode = false> 101 class hash_map 102 : public hashtable<Key, eastl::pair<const Key, T>, Allocator, eastl::use_first<eastl::pair<const Key, T> >, Predicate, 103 Hash, mod_range_hashing, default_ranged_hash, prime_rehash_policy, bCacheHashCode, true, true> 104 { 105 public: 106 typedef hashtable<Key, eastl::pair<const Key, T>, Allocator, 107 eastl::use_first<eastl::pair<const Key, T> >, 108 Predicate, Hash, mod_range_hashing, default_ranged_hash, 109 prime_rehash_policy, bCacheHashCode, true, true> base_type; 110 typedef hash_map<Key, T, Hash, Predicate, Allocator, bCacheHashCode> this_type; 111 typedef typename base_type::size_type size_type; 112 typedef typename base_type::key_type key_type; 113 typedef T mapped_type; 114 typedef typename base_type::value_type value_type; // NOTE: 'value_type = pair<const key_type, mapped_type>'. 115 typedef typename base_type::allocator_type allocator_type; 116 typedef typename base_type::node_type node_type; 117 typedef typename base_type::insert_return_type insert_return_type; 118 typedef typename base_type::iterator iterator; 119 typedef typename base_type::const_iterator const_iterator; 120 121 using base_type::insert; 122 123 public: 124 /// hash_map 125 /// 126 /// Default constructor. 127 /// 128 explicit hash_map(const allocator_type& allocator = EASTL_HASH_MAP_DEFAULT_ALLOCATOR) Hash()129 : base_type(0, Hash(), mod_range_hashing(), default_ranged_hash(), 130 Predicate(), eastl::use_first<eastl::pair<const Key, T> >(), allocator) 131 { 132 // Empty 133 } 134 135 136 /// hash_map 137 /// 138 /// Constructor which creates an empty container, but start with nBucketCount buckets. 139 /// We default to a small nBucketCount value, though the user really should manually 140 /// specify an appropriate value in order to prevent memory from being reallocated. 141 /// 142 explicit hash_map(size_type nBucketCount, const Hash& hashFunction = Hash(), 143 const Predicate& predicate = Predicate(), const allocator_type& allocator = EASTL_HASH_MAP_DEFAULT_ALLOCATOR) base_type(nBucketCount,hashFunction,mod_range_hashing (),default_ranged_hash (),predicate,eastl::use_first<eastl::pair<const Key,T>> (),allocator)144 : base_type(nBucketCount, hashFunction, mod_range_hashing(), default_ranged_hash(), 145 predicate, eastl::use_first<eastl::pair<const Key, T> >(), allocator) 146 { 147 // Empty 148 } 149 150 hash_map(const this_type & x)151 hash_map(const this_type& x) 152 : base_type(x) 153 { 154 } 155 156 hash_map(this_type && x)157 hash_map(this_type&& x) 158 : base_type(eastl::move(x)) 159 { 160 } 161 162 hash_map(this_type && x,const allocator_type & allocator)163 hash_map(this_type&& x, const allocator_type& allocator) 164 : base_type(eastl::move(x), allocator) 165 { 166 } 167 168 169 /// hash_map 170 /// 171 /// initializer_list-based constructor. 172 /// Allows for initializing with brace values (e.g. hash_map<int, char*> hm = { {3,"c"}, {4,"d"}, {5,"e"} }; ) 173 /// 174 hash_map(std::initializer_list<value_type> ilist, size_type nBucketCount = 0, const Hash& hashFunction = Hash(), 175 const Predicate& predicate = Predicate(), const allocator_type& allocator = EASTL_HASH_MAP_DEFAULT_ALLOCATOR) 176 : base_type(ilist.begin(), ilist.end(), nBucketCount, hashFunction, mod_range_hashing(), default_ranged_hash(), 177 predicate, eastl::use_first<eastl::pair<const Key, T> >(), allocator) 178 { 179 // Empty 180 } 181 182 183 /// hash_map 184 /// 185 /// An input bucket count of <= 1 causes the bucket count to be equal to the number of 186 /// elements in the input range. 187 /// 188 template <typename ForwardIterator> 189 hash_map(ForwardIterator first, ForwardIterator last, size_type nBucketCount = 0, const Hash& hashFunction = Hash(), 190 const Predicate& predicate = Predicate(), const allocator_type& allocator = EASTL_HASH_MAP_DEFAULT_ALLOCATOR) base_type(first,last,nBucketCount,hashFunction,mod_range_hashing (),default_ranged_hash (),predicate,eastl::use_first<eastl::pair<const Key,T>> (),allocator)191 : base_type(first, last, nBucketCount, hashFunction, mod_range_hashing(), default_ranged_hash(), 192 predicate, eastl::use_first<eastl::pair<const Key, T> >(), allocator) 193 { 194 // Empty 195 } 196 197 198 this_type& operator=(const this_type& x) 199 { 200 return static_cast<this_type&>(base_type::operator=(x)); 201 } 202 203 204 this_type& operator=(std::initializer_list<value_type> ilist) 205 { 206 return static_cast<this_type&>(base_type::operator=(ilist)); 207 } 208 209 210 this_type& operator=(this_type&& x) 211 { 212 return static_cast<this_type&>(base_type::operator=(eastl::move(x))); 213 } 214 215 216 /// insert 217 /// 218 /// This is an extension to the C++ standard. We insert a default-constructed 219 /// element with the given key. The reason for this is that we can avoid the 220 /// potentially expensive operation of creating and/or copying a mapped_type 221 /// object on the stack. insert(const key_type & key)222 insert_return_type insert(const key_type& key) 223 { 224 return base_type::DoInsertKey(true_type(), key); 225 } 226 at(const key_type & k)227 T& at(const key_type& k) 228 { 229 iterator it = base_type::find(k); 230 231 if (it == base_type::end()) 232 { 233 #if EASTL_EXCEPTIONS_ENABLED 234 // throw exeption if exceptions enabled 235 throw std::out_of_range("invalid hash_map<K, T> key"); 236 #else 237 // assert false if asserts enabled 238 EASTL_ASSERT_MSG(false, "invalid hash_map<K, T> key"); 239 #endif 240 } 241 // undefined behaviour if exceptions and asserts are disabled and it == end() 242 return it->second; 243 } 244 245 at(const key_type & k)246 const T& at(const key_type& k) const 247 { 248 const_iterator it = base_type::find(k); 249 250 if (it == base_type::end()) 251 { 252 #if EASTL_EXCEPTIONS_ENABLED 253 // throw exeption if exceptions enabled 254 throw std::out_of_range("invalid hash_map<K, T> key"); 255 #else 256 // assert false if asserts enabled 257 EASTL_ASSERT_MSG(false, "invalid hash_map<K, T> key"); 258 #endif 259 } 260 // undefined behaviour if exceptions and asserts are disabled and it == end() 261 return it->second; 262 } 263 264 insert(key_type && key)265 insert_return_type insert(key_type&& key) 266 { 267 return base_type::DoInsertKey(true_type(), eastl::move(key)); 268 } 269 270 271 mapped_type& operator[](const key_type& key) 272 { 273 return (*base_type::DoInsertKey(true_type(), key).first).second; 274 275 // Slower reference version: 276 //const typename base_type::iterator it = base_type::find(key); 277 //if(it != base_type::end()) 278 // return (*it).second; 279 //return (*base_type::insert(value_type(key, mapped_type())).first).second; 280 } 281 282 mapped_type& operator[](key_type&& key) 283 { 284 // The Standard states that this function "inserts the value value_type(std::move(key), mapped_type())" 285 return (*base_type::DoInsertKey(true_type(), eastl::move(key)).first).second; 286 } 287 288 289 }; // hash_map 290 291 292 293 294 295 296 /// hash_multimap 297 /// 298 /// Implements a hash_multimap, which is the same thing as a hash_map 299 /// except that contained elements need not be unique. See the 300 /// documentation for hash_set for details. 301 /// 302 template <typename Key, typename T, typename Hash = eastl::hash<Key>, typename Predicate = eastl::equal_to<Key>, 303 typename Allocator = EASTLAllocatorType, bool bCacheHashCode = false> 304 class hash_multimap 305 : public hashtable<Key, eastl::pair<const Key, T>, Allocator, eastl::use_first<eastl::pair<const Key, T> >, Predicate, 306 Hash, mod_range_hashing, default_ranged_hash, prime_rehash_policy, bCacheHashCode, true, false> 307 { 308 public: 309 typedef hashtable<Key, eastl::pair<const Key, T>, Allocator, 310 eastl::use_first<eastl::pair<const Key, T> >, 311 Predicate, Hash, mod_range_hashing, default_ranged_hash, 312 prime_rehash_policy, bCacheHashCode, true, false> base_type; 313 typedef hash_multimap<Key, T, Hash, Predicate, Allocator, bCacheHashCode> this_type; 314 typedef typename base_type::size_type size_type; 315 typedef typename base_type::key_type key_type; 316 typedef T mapped_type; 317 typedef typename base_type::value_type value_type; // Note that this is pair<const key_type, mapped_type>. 318 typedef typename base_type::allocator_type allocator_type; 319 typedef typename base_type::node_type node_type; 320 typedef typename base_type::insert_return_type insert_return_type; 321 typedef typename base_type::iterator iterator; 322 323 using base_type::insert; 324 325 private: 326 using base_type::try_emplace; 327 using base_type::insert_or_assign; 328 329 public: 330 /// hash_multimap 331 /// 332 /// Default constructor. 333 /// 334 explicit hash_multimap(const allocator_type& allocator = EASTL_HASH_MULTIMAP_DEFAULT_ALLOCATOR) Hash()335 : base_type(0, Hash(), mod_range_hashing(), default_ranged_hash(), 336 Predicate(), eastl::use_first<eastl::pair<const Key, T> >(), allocator) 337 { 338 // Empty 339 } 340 341 342 /// hash_multimap 343 /// 344 /// Constructor which creates an empty container, but start with nBucketCount buckets. 345 /// We default to a small nBucketCount value, though the user really should manually 346 /// specify an appropriate value in order to prevent memory from being reallocated. 347 /// 348 explicit hash_multimap(size_type nBucketCount, const Hash& hashFunction = Hash(), 349 const Predicate& predicate = Predicate(), const allocator_type& allocator = EASTL_HASH_MULTIMAP_DEFAULT_ALLOCATOR) base_type(nBucketCount,hashFunction,mod_range_hashing (),default_ranged_hash (),predicate,eastl::use_first<eastl::pair<const Key,T>> (),allocator)350 : base_type(nBucketCount, hashFunction, mod_range_hashing(), default_ranged_hash(), 351 predicate, eastl::use_first<eastl::pair<const Key, T> >(), allocator) 352 { 353 // Empty 354 } 355 356 hash_multimap(const this_type & x)357 hash_multimap(const this_type& x) 358 : base_type(x) 359 { 360 } 361 362 hash_multimap(this_type && x)363 hash_multimap(this_type&& x) 364 : base_type(eastl::move(x)) 365 { 366 } 367 368 hash_multimap(this_type && x,const allocator_type & allocator)369 hash_multimap(this_type&& x, const allocator_type& allocator) 370 : base_type(eastl::move(x), allocator) 371 { 372 } 373 374 375 /// hash_multimap 376 /// 377 /// initializer_list-based constructor. 378 /// Allows for initializing with brace values (e.g. hash_multimap<int, char*> hm = { {3,"c"}, {3,"C"}, {4,"d"} }; ) 379 /// 380 hash_multimap(std::initializer_list<value_type> ilist, size_type nBucketCount = 0, const Hash& hashFunction = Hash(), 381 const Predicate& predicate = Predicate(), const allocator_type& allocator = EASTL_HASH_MULTIMAP_DEFAULT_ALLOCATOR) 382 : base_type(ilist.begin(), ilist.end(), nBucketCount, hashFunction, mod_range_hashing(), default_ranged_hash(), 383 predicate, eastl::use_first<eastl::pair<const Key, T> >(), allocator) 384 { 385 // Empty 386 } 387 388 389 /// hash_multimap 390 /// 391 /// An input bucket count of <= 1 causes the bucket count to be equal to the number of 392 /// elements in the input range. 393 /// 394 template <typename ForwardIterator> 395 hash_multimap(ForwardIterator first, ForwardIterator last, size_type nBucketCount = 0, const Hash& hashFunction = Hash(), 396 const Predicate& predicate = Predicate(), const allocator_type& allocator = EASTL_HASH_MULTIMAP_DEFAULT_ALLOCATOR) base_type(first,last,nBucketCount,hashFunction,mod_range_hashing (),default_ranged_hash (),predicate,eastl::use_first<eastl::pair<const Key,T>> (),allocator)397 : base_type(first, last, nBucketCount, hashFunction, mod_range_hashing(), default_ranged_hash(), 398 predicate, eastl::use_first<eastl::pair<const Key, T> >(), allocator) 399 { 400 // Empty 401 } 402 403 404 this_type& operator=(const this_type& x) 405 { 406 return static_cast<this_type&>(base_type::operator=(x)); 407 } 408 409 410 this_type& operator=(std::initializer_list<value_type> ilist) 411 { 412 return static_cast<this_type&>(base_type::operator=(ilist)); 413 } 414 415 416 this_type& operator=(this_type&& x) 417 { 418 return static_cast<this_type&>(base_type::operator=(eastl::move(x))); 419 } 420 421 422 /// insert 423 /// 424 /// This is an extension to the C++ standard. We insert a default-constructed 425 /// element with the given key. The reason for this is that we can avoid the 426 /// potentially expensive operation of creating and/or copying a mapped_type 427 /// object on the stack. insert(const key_type & key)428 insert_return_type insert(const key_type& key) 429 { 430 return base_type::DoInsertKey(false_type(), key); 431 } 432 433 insert(key_type && key)434 insert_return_type insert(key_type&& key) 435 { 436 return base_type::DoInsertKey(false_type(), eastl::move(key)); 437 } 438 439 440 }; // hash_multimap 441 442 443 444 /////////////////////////////////////////////////////////////////////// 445 // global operators 446 /////////////////////////////////////////////////////////////////////// 447 448 template <typename Key, typename T, typename Hash, typename Predicate, typename Allocator, bool bCacheHashCode> 449 inline bool operator==(const hash_map<Key, T, Hash, Predicate, Allocator, bCacheHashCode>& a, 450 const hash_map<Key, T, Hash, Predicate, Allocator, bCacheHashCode>& b) 451 { 452 typedef typename hash_map<Key, T, Hash, Predicate, Allocator, bCacheHashCode>::const_iterator const_iterator; 453 454 // We implement branching with the assumption that the return value is usually false. 455 if(a.size() != b.size()) 456 return false; 457 458 // For map (with its unique keys), we need only test that each element in a can be found in b, 459 // as there can be only one such pairing per element. multimap needs to do a something more elaborate. 460 for(const_iterator ai = a.begin(), aiEnd = a.end(), biEnd = b.end(); ai != aiEnd; ++ai) 461 { 462 const_iterator bi = b.find(ai->first); 463 464 if((bi == biEnd) || !(*ai == *bi)) // We have to compare the values, because lookups are done by keys alone but the full value_type of a map is a key/value pair. 465 return false; // It's possible that two elements in the two containers have identical keys but different values. 466 } 467 468 return true; 469 } 470 471 template <typename Key, typename T, typename Hash, typename Predicate, typename Allocator, bool bCacheHashCode> 472 inline bool operator!=(const hash_map<Key, T, Hash, Predicate, Allocator, bCacheHashCode>& a, 473 const hash_map<Key, T, Hash, Predicate, Allocator, bCacheHashCode>& b) 474 { 475 return !(a == b); 476 } 477 478 479 template <typename Key, typename T, typename Hash, typename Predicate, typename Allocator, bool bCacheHashCode> 480 inline bool operator==(const hash_multimap<Key, T, Hash, Predicate, Allocator, bCacheHashCode>& a, 481 const hash_multimap<Key, T, Hash, Predicate, Allocator, bCacheHashCode>& b) 482 { 483 typedef typename hash_multimap<Key, T, Hash, Predicate, Allocator, bCacheHashCode>::const_iterator const_iterator; 484 typedef typename eastl::iterator_traits<const_iterator>::difference_type difference_type; 485 486 // We implement branching with the assumption that the return value is usually false. 487 if(a.size() != b.size()) 488 return false; 489 490 // We can't simply search for each element of a in b, as it may be that the bucket for 491 // two elements in a has those same two elements in b but in different order (which should 492 // still result in equality). Also it's possible that one bucket in a has two elements which 493 // both match a solitary element in the equivalent bucket in b (which shouldn't result in equality). 494 eastl::pair<const_iterator, const_iterator> aRange; 495 eastl::pair<const_iterator, const_iterator> bRange; 496 497 for(const_iterator ai = a.begin(), aiEnd = a.end(); ai != aiEnd; ai = aRange.second) // For each element in a... 498 { 499 aRange = a.equal_range(ai->first); // Get the range of elements in a that are equal to ai. 500 bRange = b.equal_range(ai->first); // Get the range of elements in b that are equal to ai. 501 502 // We need to verify that aRange == bRange. First make sure the range sizes are equivalent... 503 const difference_type aDistance = eastl::distance(aRange.first, aRange.second); 504 const difference_type bDistance = eastl::distance(bRange.first, bRange.second); 505 506 if(aDistance != bDistance) 507 return false; 508 509 // At this point, aDistance > 0 and aDistance == bDistance. 510 // Implement a fast pathway for the case that there's just a single element. 511 if(aDistance == 1) 512 { 513 if(!(*aRange.first == *bRange.first)) // We have to compare the values, because lookups are done by keys alone but the full value_type of a map is a key/value pair. 514 return false; // It's possible that two elements in the two containers have identical keys but different values. Ditto for the permutation case below. 515 } 516 else 517 { 518 // Check to see if these aRange and bRange are any permutation of each other. 519 // This check gets slower as there are more elements in the range. 520 if(!eastl::is_permutation(aRange.first, aRange.second, bRange.first)) 521 return false; 522 } 523 } 524 525 return true; 526 } 527 528 template <typename Key, typename T, typename Hash, typename Predicate, typename Allocator, bool bCacheHashCode> 529 inline bool operator!=(const hash_multimap<Key, T, Hash, Predicate, Allocator, bCacheHashCode>& a, 530 const hash_multimap<Key, T, Hash, Predicate, Allocator, bCacheHashCode>& b) 531 { 532 return !(a == b); 533 } 534 535 536 } // namespace eastl 537 538 539 #endif // Header include guard 540 541 542 543 544 545 546