| OLD | NEW |
|---|
| (Empty) |
| 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_ | |
| OLD | NEW |
|---|
Chromium Code Reviews
