1// Copyright (c) 2012 The Chromium Authors. All rights reserved. 2// Use of this source code is governed by a BSD-style license that can be 3// found in the LICENSE file. 4 5#ifndef BASE_CONTAINERS_SMALL_MAP_H_ 6#define BASE_CONTAINERS_SMALL_MAP_H_ 7 8#include <stddef.h> 9 10#include <map> 11#include <string> 12#include <utility> 13 14#include "base/containers/hash_tables.h" 15#include "base/logging.h" 16#include "base/memory/manual_constructor.h" 17 18namespace base { 19 20// An STL-like associative container which starts out backed by a simple 21// array but switches to some other container type if it grows beyond a 22// fixed size. 23// 24// WHAT TYPE OF MAP SHOULD YOU USE? 25// -------------------------------- 26// 27// - std::map should be the default if you're not sure, since it's the most 28// difficult to mess up. Generally this is backed by a red-black tree. It 29// will generate a lot of code (if you use a common key type like int or 30// string the linker will probably emiminate the duplicates). It will 31// do heap allocations for each element. 32// 33// - If you only ever keep a couple of items and have very simple usage, 34// consider whether a using a vector and brute-force searching it will be 35// the most efficient. It's not a lot of generated code (less then a 36// red-black tree if your key is "weird" and not eliminated as duplicate of 37// something else) and will probably be faster and do fewer heap allocations 38// than std::map if you have just a couple of items. 39// 40// - base::hash_map should be used if you need O(1) lookups. It may waste 41// space in the hash table, and it can be easy to write correct-looking 42// code with the default hash function being wrong or poorly-behaving. 43// 44// - SmallMap combines the performance benefits of the brute-force-searched 45// vector for small cases (no extra heap allocations), but can efficiently 46// fall back if you end up adding many items. It will generate more code 47// than std::map (at least 160 bytes for operator[]) which is bad if you 48// have a "weird" key where map functions can't be 49// duplicate-code-eliminated. If you have a one-off key and aren't in 50// performance-critical code, this bloat may negate some of the benefits and 51// you should consider on of the other options. 52// 53// SmallMap will pick up the comparator from the underlying map type. In 54// std::map (and in MSVC additionally hash_map) only a "less" operator is 55// defined, which requires us to do two comparisons per element when doing the 56// brute-force search in the simple array. 57// 58// We define default overrides for the common map types to avoid this 59// double-compare, but you should be aware of this if you use your own 60// operator< for your map and supply yor own version of == to the SmallMap. 61// You can use regular operator== by just doing: 62// 63// base::SmallMap<std::map<MyKey, MyValue>, 4, std::equal_to<KyKey> > 64// 65// 66// USAGE 67// ----- 68// 69// NormalMap: The map type to fall back to. This also defines the key 70// and value types for the SmallMap. 71// kArraySize: The size of the initial array of results. This will be 72// allocated with the SmallMap object rather than separately on 73// the heap. Once the map grows beyond this size, the map type 74// will be used instead. 75// EqualKey: A functor which tests two keys for equality. If the wrapped 76// map type has a "key_equal" member (hash_map does), then that will 77// be used by default. If the wrapped map type has a strict weak 78// ordering "key_compare" (std::map does), that will be used to 79// implement equality by default. 80// MapInit: A functor that takes a ManualConstructor<NormalMap>* and uses it to 81// initialize the map. This functor will be called at most once per 82// SmallMap, when the map exceeds the threshold of kArraySize and we 83// are about to copy values from the array to the map. The functor 84// *must* call one of the Init() methods provided by 85// ManualConstructor, since after it runs we assume that the NormalMap 86// has been initialized. 87// 88// example: 89// base::SmallMap< std::map<string, int> > days; 90// days["sunday" ] = 0; 91// days["monday" ] = 1; 92// days["tuesday" ] = 2; 93// days["wednesday"] = 3; 94// days["thursday" ] = 4; 95// days["friday" ] = 5; 96// days["saturday" ] = 6; 97// 98// You should assume that SmallMap might invalidate all the iterators 99// on any call to erase(), insert() and operator[]. 100 101namespace internal { 102 103template <typename NormalMap> 104class SmallMapDefaultInit { 105 public: 106 void operator()(ManualConstructor<NormalMap>* map) const { 107 map->Init(); 108 } 109}; 110 111// has_key_equal<M>::value is true iff there exists a type M::key_equal. This is 112// used to dispatch to one of the select_equal_key<> metafunctions below. 113template <typename M> 114struct has_key_equal { 115 typedef char sml; // "small" is sometimes #defined so we use an abbreviation. 116 typedef struct { char dummy[2]; } big; 117 // Two functions, one accepts types that have a key_equal member, and one that 118 // accepts anything. They each return a value of a different size, so we can 119 // determine at compile-time which function would have been called. 120 template <typename U> static big test(typename U::key_equal*); 121 template <typename> static sml test(...); 122 // Determines if M::key_equal exists by looking at the size of the return 123 // type of the compiler-chosen test() function. 124 static const bool value = (sizeof(test<M>(0)) == sizeof(big)); 125}; 126template <typename M> const bool has_key_equal<M>::value; 127 128// Base template used for map types that do NOT have an M::key_equal member, 129// e.g., std::map<>. These maps have a strict weak ordering comparator rather 130// than an equality functor, so equality will be implemented in terms of that 131// comparator. 132// 133// There's a partial specialization of this template below for map types that do 134// have an M::key_equal member. 135template <typename M, bool has_key_equal_value> 136struct select_equal_key { 137 struct equal_key { 138 bool operator()(const typename M::key_type& left, 139 const typename M::key_type& right) { 140 // Implements equality in terms of a strict weak ordering comparator. 141 typename M::key_compare comp; 142 return !comp(left, right) && !comp(right, left); 143 } 144 }; 145}; 146 147// Provide overrides to use operator== for key compare for the "normal" map and 148// hash map types. If you override the default comparator or allocator for a 149// map or hash_map, or use another type of map, this won't get used. 150// 151// If we switch to using std::unordered_map for base::hash_map, then the 152// hash_map specialization can be removed. 153template <typename KeyType, typename ValueType> 154struct select_equal_key< std::map<KeyType, ValueType>, false> { 155 struct equal_key { 156 bool operator()(const KeyType& left, const KeyType& right) { 157 return left == right; 158 } 159 }; 160}; 161template <typename KeyType, typename ValueType> 162struct select_equal_key< base::hash_map<KeyType, ValueType>, false> { 163 struct equal_key { 164 bool operator()(const KeyType& left, const KeyType& right) { 165 return left == right; 166 } 167 }; 168}; 169 170// Partial template specialization handles case where M::key_equal exists, e.g., 171// hash_map<>. 172template <typename M> 173struct select_equal_key<M, true> { 174 typedef typename M::key_equal equal_key; 175}; 176 177} // namespace internal 178 179template <typename NormalMap, 180 int kArraySize = 4, 181 typename EqualKey = 182 typename internal::select_equal_key< 183 NormalMap, 184 internal::has_key_equal<NormalMap>::value>::equal_key, 185 typename MapInit = internal::SmallMapDefaultInit<NormalMap> > 186class SmallMap { 187 // We cannot rely on the compiler to reject array of size 0. In 188 // particular, gcc 2.95.3 does it but later versions allow 0-length 189 // arrays. Therefore, we explicitly reject non-positive kArraySize 190 // here. 191 static_assert(kArraySize > 0, "default initial size should be positive"); 192 193 public: 194 typedef typename NormalMap::key_type key_type; 195 typedef typename NormalMap::mapped_type data_type; 196 typedef typename NormalMap::mapped_type mapped_type; 197 typedef typename NormalMap::value_type value_type; 198 typedef EqualKey key_equal; 199 200 SmallMap() : size_(0), functor_(MapInit()) {} 201 202 explicit SmallMap(const MapInit& functor) : size_(0), functor_(functor) {} 203 204 // Allow copy-constructor and assignment, since STL allows them too. 205 SmallMap(const SmallMap& src) { 206 // size_ and functor_ are initted in InitFrom() 207 InitFrom(src); 208 } 209 void operator=(const SmallMap& src) { 210 if (&src == this) return; 211 212 // This is not optimal. If src and dest are both using the small 213 // array, we could skip the teardown and reconstruct. One problem 214 // to be resolved is that the value_type itself is pair<const K, 215 // V>, and const K is not assignable. 216 Destroy(); 217 InitFrom(src); 218 } 219 ~SmallMap() { 220 Destroy(); 221 } 222 223 class const_iterator; 224 225 class iterator { 226 public: 227 typedef typename NormalMap::iterator::iterator_category iterator_category; 228 typedef typename NormalMap::iterator::value_type value_type; 229 typedef typename NormalMap::iterator::difference_type difference_type; 230 typedef typename NormalMap::iterator::pointer pointer; 231 typedef typename NormalMap::iterator::reference reference; 232 233 inline iterator(): array_iter_(NULL) {} 234 235 inline iterator& operator++() { 236 if (array_iter_ != NULL) { 237 ++array_iter_; 238 } else { 239 ++hash_iter_; 240 } 241 return *this; 242 } 243 inline iterator operator++(int /*unused*/) { 244 iterator result(*this); 245 ++(*this); 246 return result; 247 } 248 inline iterator& operator--() { 249 if (array_iter_ != NULL) { 250 --array_iter_; 251 } else { 252 --hash_iter_; 253 } 254 return *this; 255 } 256 inline iterator operator--(int /*unused*/) { 257 iterator result(*this); 258 --(*this); 259 return result; 260 } 261 inline value_type* operator->() const { 262 if (array_iter_ != NULL) { 263 return array_iter_->get(); 264 } else { 265 return hash_iter_.operator->(); 266 } 267 } 268 269 inline value_type& operator*() const { 270 if (array_iter_ != NULL) { 271 return *array_iter_->get(); 272 } else { 273 return *hash_iter_; 274 } 275 } 276 277 inline bool operator==(const iterator& other) const { 278 if (array_iter_ != NULL) { 279 return array_iter_ == other.array_iter_; 280 } else { 281 return other.array_iter_ == NULL && hash_iter_ == other.hash_iter_; 282 } 283 } 284 285 inline bool operator!=(const iterator& other) const { 286 return !(*this == other); 287 } 288 289 bool operator==(const const_iterator& other) const; 290 bool operator!=(const const_iterator& other) const; 291 292 private: 293 friend class SmallMap; 294 friend class const_iterator; 295 inline explicit iterator(ManualConstructor<value_type>* init) 296 : array_iter_(init) {} 297 inline explicit iterator(const typename NormalMap::iterator& init) 298 : array_iter_(NULL), hash_iter_(init) {} 299 300 ManualConstructor<value_type>* array_iter_; 301 typename NormalMap::iterator hash_iter_; 302 }; 303 304 class const_iterator { 305 public: 306 typedef typename NormalMap::const_iterator::iterator_category 307 iterator_category; 308 typedef typename NormalMap::const_iterator::value_type value_type; 309 typedef typename NormalMap::const_iterator::difference_type difference_type; 310 typedef typename NormalMap::const_iterator::pointer pointer; 311 typedef typename NormalMap::const_iterator::reference reference; 312 313 inline const_iterator(): array_iter_(NULL) {} 314 // Non-explicit ctor lets us convert regular iterators to const iterators 315 inline const_iterator(const iterator& other) 316 : array_iter_(other.array_iter_), hash_iter_(other.hash_iter_) {} 317 318 inline const_iterator& operator++() { 319 if (array_iter_ != NULL) { 320 ++array_iter_; 321 } else { 322 ++hash_iter_; 323 } 324 return *this; 325 } 326 inline const_iterator operator++(int /*unused*/) { 327 const_iterator result(*this); 328 ++(*this); 329 return result; 330 } 331 332 inline const_iterator& operator--() { 333 if (array_iter_ != NULL) { 334 --array_iter_; 335 } else { 336 --hash_iter_; 337 } 338 return *this; 339 } 340 inline const_iterator operator--(int /*unused*/) { 341 const_iterator result(*this); 342 --(*this); 343 return result; 344 } 345 346 inline const value_type* operator->() const { 347 if (array_iter_ != NULL) { 348 return array_iter_->get(); 349 } else { 350 return hash_iter_.operator->(); 351 } 352 } 353 354 inline const value_type& operator*() const { 355 if (array_iter_ != NULL) { 356 return *array_iter_->get(); 357 } else { 358 return *hash_iter_; 359 } 360 } 361 362 inline bool operator==(const const_iterator& other) const { 363 if (array_iter_ != NULL) { 364 return array_iter_ == other.array_iter_; 365 } else { 366 return other.array_iter_ == NULL && hash_iter_ == other.hash_iter_; 367 } 368 } 369 370 inline bool operator!=(const const_iterator& other) const { 371 return !(*this == other); 372 } 373 374 private: 375 friend class SmallMap; 376 inline explicit const_iterator( 377 const ManualConstructor<value_type>* init) 378 : array_iter_(init) {} 379 inline explicit const_iterator( 380 const typename NormalMap::const_iterator& init) 381 : array_iter_(NULL), hash_iter_(init) {} 382 383 const ManualConstructor<value_type>* array_iter_; 384 typename NormalMap::const_iterator hash_iter_; 385 }; 386 387 iterator find(const key_type& key) { 388 key_equal compare; 389 if (size_ >= 0) { 390 for (int i = 0; i < size_; i++) { 391 if (compare(array_[i]->first, key)) { 392 return iterator(array_ + i); 393 } 394 } 395 return iterator(array_ + size_); 396 } else { 397 return iterator(map()->find(key)); 398 } 399 } 400 401 const_iterator find(const key_type& key) const { 402 key_equal compare; 403 if (size_ >= 0) { 404 for (int i = 0; i < size_; i++) { 405 if (compare(array_[i]->first, key)) { 406 return const_iterator(array_ + i); 407 } 408 } 409 return const_iterator(array_ + size_); 410 } else { 411 return const_iterator(map()->find(key)); 412 } 413 } 414 415 // Invalidates iterators. 416 data_type& operator[](const key_type& key) { 417 key_equal compare; 418 419 if (size_ >= 0) { 420 // operator[] searches backwards, favoring recently-added 421 // elements. 422 for (int i = size_-1; i >= 0; --i) { 423 if (compare(array_[i]->first, key)) { 424 return array_[i]->second; 425 } 426 } 427 if (size_ == kArraySize) { 428 ConvertToRealMap(); 429 return (*map_)[key]; 430 } else { 431 array_[size_].Init(key, data_type()); 432 return array_[size_++]->second; 433 } 434 } else { 435 return (*map_)[key]; 436 } 437 } 438 439 // Invalidates iterators. 440 std::pair<iterator, bool> insert(const value_type& x) { 441 key_equal compare; 442 443 if (size_ >= 0) { 444 for (int i = 0; i < size_; i++) { 445 if (compare(array_[i]->first, x.first)) { 446 return std::make_pair(iterator(array_ + i), false); 447 } 448 } 449 if (size_ == kArraySize) { 450 ConvertToRealMap(); // Invalidates all iterators! 451 std::pair<typename NormalMap::iterator, bool> ret = map_->insert(x); 452 return std::make_pair(iterator(ret.first), ret.second); 453 } else { 454 array_[size_].Init(x); 455 return std::make_pair(iterator(array_ + size_++), true); 456 } 457 } else { 458 std::pair<typename NormalMap::iterator, bool> ret = map_->insert(x); 459 return std::make_pair(iterator(ret.first), ret.second); 460 } 461 } 462 463 // Invalidates iterators. 464 template <class InputIterator> 465 void insert(InputIterator f, InputIterator l) { 466 while (f != l) { 467 insert(*f); 468 ++f; 469 } 470 } 471 472 iterator begin() { 473 if (size_ >= 0) { 474 return iterator(array_); 475 } else { 476 return iterator(map_->begin()); 477 } 478 } 479 const_iterator begin() const { 480 if (size_ >= 0) { 481 return const_iterator(array_); 482 } else { 483 return const_iterator(map_->begin()); 484 } 485 } 486 487 iterator end() { 488 if (size_ >= 0) { 489 return iterator(array_ + size_); 490 } else { 491 return iterator(map_->end()); 492 } 493 } 494 const_iterator end() const { 495 if (size_ >= 0) { 496 return const_iterator(array_ + size_); 497 } else { 498 return const_iterator(map_->end()); 499 } 500 } 501 502 void clear() { 503 if (size_ >= 0) { 504 for (int i = 0; i < size_; i++) { 505 array_[i].Destroy(); 506 } 507 } else { 508 map_.Destroy(); 509 } 510 size_ = 0; 511 } 512 513 // Invalidates iterators. 514 void erase(const iterator& position) { 515 if (size_ >= 0) { 516 int i = position.array_iter_ - array_; 517 array_[i].Destroy(); 518 --size_; 519 if (i != size_) { 520 array_[i].InitFromMove(std::move(array_[size_])); 521 array_[size_].Destroy(); 522 } 523 } else { 524 map_->erase(position.hash_iter_); 525 } 526 } 527 528 size_t erase(const key_type& key) { 529 iterator iter = find(key); 530 if (iter == end()) return 0u; 531 erase(iter); 532 return 1u; 533 } 534 535 size_t count(const key_type& key) const { 536 return (find(key) == end()) ? 0 : 1; 537 } 538 539 size_t size() const { 540 if (size_ >= 0) { 541 return static_cast<size_t>(size_); 542 } else { 543 return map_->size(); 544 } 545 } 546 547 bool empty() const { 548 if (size_ >= 0) { 549 return (size_ == 0); 550 } else { 551 return map_->empty(); 552 } 553 } 554 555 // Returns true if we have fallen back to using the underlying map 556 // representation. 557 bool UsingFullMap() const { 558 return size_ < 0; 559 } 560 561 inline NormalMap* map() { 562 CHECK(UsingFullMap()); 563 return map_.get(); 564 } 565 inline const NormalMap* map() const { 566 CHECK(UsingFullMap()); 567 return map_.get(); 568 } 569 570 private: 571 int size_; // negative = using hash_map 572 573 MapInit functor_; 574 575 // We want to call constructors and destructors manually, but we don't 576 // want to allocate and deallocate the memory used for them separately. 577 // So, we use this crazy ManualConstructor class. 578 // 579 // Since array_ and map_ are mutually exclusive, we'll put them in a 580 // union, too. We add in a dummy_ value which quiets MSVC from otherwise 581 // giving an erroneous "union member has copy constructor" error message 582 // (C2621). This dummy member has to come before array_ to quiet the 583 // compiler. 584 // 585 // TODO(brettw) remove this and use C++11 unions when we require C++11. 586 union { 587 ManualConstructor<value_type> dummy_; 588 ManualConstructor<value_type> array_[kArraySize]; 589 ManualConstructor<NormalMap> map_; 590 }; 591 592 void ConvertToRealMap() { 593 // Move the current elements into a temporary array. 594 ManualConstructor<value_type> temp_array[kArraySize]; 595 596 for (int i = 0; i < kArraySize; i++) { 597 temp_array[i].InitFromMove(std::move(array_[i])); 598 array_[i].Destroy(); 599 } 600 601 // Initialize the map. 602 size_ = -1; 603 functor_(&map_); 604 605 // Insert elements into it. 606 for (int i = 0; i < kArraySize; i++) { 607 map_->insert(std::move(*temp_array[i])); 608 temp_array[i].Destroy(); 609 } 610 } 611 612 // Helpers for constructors and destructors. 613 void InitFrom(const SmallMap& src) { 614 functor_ = src.functor_; 615 size_ = src.size_; 616 if (src.size_ >= 0) { 617 for (int i = 0; i < size_; i++) { 618 array_[i].Init(*src.array_[i]); 619 } 620 } else { 621 functor_(&map_); 622 (*map_.get()) = (*src.map_.get()); 623 } 624 } 625 void Destroy() { 626 if (size_ >= 0) { 627 for (int i = 0; i < size_; i++) { 628 array_[i].Destroy(); 629 } 630 } else { 631 map_.Destroy(); 632 } 633 } 634}; 635 636template <typename NormalMap, int kArraySize, typename EqualKey, 637 typename Functor> 638inline bool SmallMap<NormalMap, kArraySize, EqualKey, 639 Functor>::iterator::operator==( 640 const const_iterator& other) const { 641 return other == *this; 642} 643template <typename NormalMap, int kArraySize, typename EqualKey, 644 typename Functor> 645inline bool SmallMap<NormalMap, kArraySize, EqualKey, 646 Functor>::iterator::operator!=( 647 const const_iterator& other) const { 648 return other != *this; 649} 650 651} // namespace base 652 653#endif // BASE_CONTAINERS_SMALL_MAP_H_ 654