src/base/containers/small_map.h

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