small_map.h 18 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605
  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. #ifndef BASE_CONTAINERS_SMALL_MAP_H_
  5. #define BASE_CONTAINERS_SMALL_MAP_H_
  6. #include <stddef.h>
  7. #include <limits>
  8. #include <map>
  9. #include <new>
  10. #include <utility>
  11. #include "base/check.h"
  12. #include "base/check_op.h"
  13. #include "base/memory/raw_ptr.h"
  14. inline constexpr size_t kUsingFullMapSentinel =
  15. std::numeric_limits<size_t>::max();
  16. namespace base {
  17. // small_map is a container with a std::map-like interface. It starts out backed
  18. // by an unsorted array but switches to some other container type if it grows
  19. // beyond this fixed size.
  20. //
  21. // Please see //base/containers/README.md for an overview of which container
  22. // to select.
  23. //
  24. // PROS
  25. //
  26. // - Good memory locality and low overhead for smaller maps.
  27. // - Handles large maps without the degenerate performance of flat_map.
  28. //
  29. // CONS
  30. //
  31. // - Larger code size than the alternatives.
  32. //
  33. // IMPORTANT NOTES
  34. //
  35. // - Iterators are invalidated across mutations.
  36. //
  37. // DETAILS
  38. //
  39. // base::small_map will pick up the comparator from the underlying map type. In
  40. // std::map only a "less" operator is defined, which requires us to do two
  41. // comparisons per element when doing the brute-force search in the simple
  42. // array. std::unordered_map has a key_equal function which will be used.
  43. //
  44. // We define default overrides for the common map types to avoid this
  45. // double-compare, but you should be aware of this if you use your own operator<
  46. // for your map and supply your own version of == to the small_map. You can use
  47. // regular operator== by just doing:
  48. //
  49. // base::small_map<std::map<MyKey, MyValue>, 4, std::equal_to<KyKey>>
  50. //
  51. //
  52. // USAGE
  53. // -----
  54. //
  55. // NormalMap: The map type to fall back to. This also defines the key and value
  56. // types for the small_map.
  57. // kArraySize: The size of the initial array of results. This will be allocated
  58. // with the small_map object rather than separately on the heap.
  59. // Once the map grows beyond this size, the map type will be used
  60. // instead.
  61. // EqualKey: A functor which tests two keys for equality. If the wrapped map
  62. // type has a "key_equal" member (unordered_map does), then that will
  63. // be used by default. If the wrapped map type has a strict weak
  64. // ordering "key_compare" (std::map does), that will be used to
  65. // implement equality by default.
  66. // MapInit: A functor that takes a NormalMap* and uses it to initialize the map.
  67. // This functor will be called at most once per small_map, when the map
  68. // exceeds the threshold of kArraySize and we are about to copy values
  69. // from the array to the map. The functor *must* initialize the
  70. // NormalMap* argument with placement new, since after it runs we
  71. // assume that the NormalMap has been initialized.
  72. //
  73. // Example:
  74. // base::small_map<std::map<string, int>> days;
  75. // days["sunday" ] = 0;
  76. // days["monday" ] = 1;
  77. // days["tuesday" ] = 2;
  78. // days["wednesday"] = 3;
  79. // days["thursday" ] = 4;
  80. // days["friday" ] = 5;
  81. // days["saturday" ] = 6;
  82. namespace internal {
  83. template <typename NormalMap>
  84. class small_map_default_init {
  85. public:
  86. void operator()(NormalMap* map) const { new (map) NormalMap(); }
  87. };
  88. // has_key_equal<M>::value is true iff there exists a type M::key_equal. This is
  89. // used to dispatch to one of the select_equal_key<> metafunctions below.
  90. template <typename M>
  91. struct has_key_equal {
  92. typedef char sml; // "small" is sometimes #defined so we use an abbreviation.
  93. typedef struct { char dummy[2]; } big;
  94. // Two functions, one accepts types that have a key_equal member, and one that
  95. // accepts anything. They each return a value of a different size, so we can
  96. // determine at compile-time which function would have been called.
  97. template <typename U> static big test(typename U::key_equal*);
  98. template <typename> static sml test(...);
  99. // Determines if M::key_equal exists by looking at the size of the return
  100. // type of the compiler-chosen test() function.
  101. static const bool value = (sizeof(test<M>(0)) == sizeof(big));
  102. };
  103. template <typename M> const bool has_key_equal<M>::value;
  104. // Base template used for map types that do NOT have an M::key_equal member,
  105. // e.g., std::map<>. These maps have a strict weak ordering comparator rather
  106. // than an equality functor, so equality will be implemented in terms of that
  107. // comparator.
  108. //
  109. // There's a partial specialization of this template below for map types that do
  110. // have an M::key_equal member.
  111. template <typename M, bool has_key_equal_value>
  112. struct select_equal_key {
  113. struct equal_key {
  114. bool operator()(const typename M::key_type& left,
  115. const typename M::key_type& right) {
  116. // Implements equality in terms of a strict weak ordering comparator.
  117. typename M::key_compare comp;
  118. return !comp(left, right) && !comp(right, left);
  119. }
  120. };
  121. };
  122. // Partial template specialization handles case where M::key_equal exists, e.g.,
  123. // unordered_map<>.
  124. template <typename M>
  125. struct select_equal_key<M, true> {
  126. typedef typename M::key_equal equal_key;
  127. };
  128. } // namespace internal
  129. template <typename NormalMap,
  130. size_t kArraySize = 4,
  131. typename EqualKey = typename internal::select_equal_key<
  132. NormalMap,
  133. internal::has_key_equal<NormalMap>::value>::equal_key,
  134. typename MapInit = internal::small_map_default_init<NormalMap>>
  135. class small_map {
  136. static_assert(kArraySize > 0, "Initial size must be greater than 0");
  137. static_assert(kArraySize != kUsingFullMapSentinel,
  138. "Initial size out of range");
  139. public:
  140. typedef typename NormalMap::key_type key_type;
  141. typedef typename NormalMap::mapped_type data_type;
  142. typedef typename NormalMap::mapped_type mapped_type;
  143. typedef typename NormalMap::value_type value_type;
  144. typedef EqualKey key_equal;
  145. small_map() : size_(0), functor_(MapInit()) {}
  146. explicit small_map(const MapInit& functor) : size_(0), functor_(functor) {}
  147. // Allow copy-constructor and assignment, since STL allows them too.
  148. small_map(const small_map& src) {
  149. // size_ and functor_ are initted in InitFrom()
  150. InitFrom(src);
  151. }
  152. void operator=(const small_map& src) {
  153. if (&src == this) return;
  154. // This is not optimal. If src and dest are both using the small array, we
  155. // could skip the teardown and reconstruct. One problem to be resolved is
  156. // that the value_type itself is pair<const K, V>, and const K is not
  157. // assignable.
  158. Destroy();
  159. InitFrom(src);
  160. }
  161. ~small_map() { Destroy(); }
  162. class const_iterator;
  163. class iterator {
  164. public:
  165. typedef typename NormalMap::iterator::iterator_category iterator_category;
  166. typedef typename NormalMap::iterator::value_type value_type;
  167. typedef typename NormalMap::iterator::difference_type difference_type;
  168. typedef typename NormalMap::iterator::pointer pointer;
  169. typedef typename NormalMap::iterator::reference reference;
  170. inline iterator() : array_iter_(nullptr) {}
  171. inline iterator& operator++() {
  172. if (array_iter_ != nullptr) {
  173. ++array_iter_;
  174. } else {
  175. ++map_iter_;
  176. }
  177. return *this;
  178. }
  179. inline iterator operator++(int /*unused*/) {
  180. iterator result(*this);
  181. ++(*this);
  182. return result;
  183. }
  184. inline iterator& operator--() {
  185. if (array_iter_ != nullptr) {
  186. --array_iter_;
  187. } else {
  188. --map_iter_;
  189. }
  190. return *this;
  191. }
  192. inline iterator operator--(int /*unused*/) {
  193. iterator result(*this);
  194. --(*this);
  195. return result;
  196. }
  197. inline value_type* operator->() const {
  198. return array_iter_ ? array_iter_.get() : map_iter_.operator->();
  199. }
  200. inline value_type& operator*() const {
  201. return array_iter_ ? *array_iter_ : *map_iter_;
  202. }
  203. inline bool operator==(const iterator& other) const {
  204. if (array_iter_ != nullptr) {
  205. return array_iter_ == other.array_iter_;
  206. } else {
  207. return other.array_iter_ == nullptr && map_iter_ == other.map_iter_;
  208. }
  209. }
  210. inline bool operator!=(const iterator& other) const {
  211. return !(*this == other);
  212. }
  213. private:
  214. friend class small_map;
  215. friend class const_iterator;
  216. inline explicit iterator(value_type* init) : array_iter_(init) {}
  217. inline explicit iterator(const typename NormalMap::iterator& init)
  218. : array_iter_(nullptr), map_iter_(init) {}
  219. raw_ptr<value_type> array_iter_;
  220. typename NormalMap::iterator map_iter_;
  221. };
  222. class const_iterator {
  223. public:
  224. typedef typename NormalMap::const_iterator::iterator_category
  225. iterator_category;
  226. typedef typename NormalMap::const_iterator::value_type value_type;
  227. typedef typename NormalMap::const_iterator::difference_type difference_type;
  228. typedef typename NormalMap::const_iterator::pointer pointer;
  229. typedef typename NormalMap::const_iterator::reference reference;
  230. inline const_iterator() : array_iter_(nullptr) {}
  231. // Non-explicit constructor lets us convert regular iterators to const
  232. // iterators.
  233. inline const_iterator(const iterator& other)
  234. : array_iter_(other.array_iter_), map_iter_(other.map_iter_) {}
  235. inline const_iterator& operator++() {
  236. if (array_iter_ != nullptr) {
  237. ++array_iter_;
  238. } else {
  239. ++map_iter_;
  240. }
  241. return *this;
  242. }
  243. inline const_iterator operator++(int /*unused*/) {
  244. const_iterator result(*this);
  245. ++(*this);
  246. return result;
  247. }
  248. inline const_iterator& operator--() {
  249. if (array_iter_ != nullptr) {
  250. --array_iter_;
  251. } else {
  252. --map_iter_;
  253. }
  254. return *this;
  255. }
  256. inline const_iterator operator--(int /*unused*/) {
  257. const_iterator result(*this);
  258. --(*this);
  259. return result;
  260. }
  261. inline const value_type* operator->() const {
  262. return array_iter_ ? array_iter_.get() : map_iter_.operator->();
  263. }
  264. inline const value_type& operator*() const {
  265. return array_iter_ ? *array_iter_ : *map_iter_;
  266. }
  267. inline bool operator==(const const_iterator& other) const {
  268. if (array_iter_ != nullptr) {
  269. return array_iter_ == other.array_iter_;
  270. }
  271. return other.array_iter_ == nullptr && map_iter_ == other.map_iter_;
  272. }
  273. inline bool operator!=(const const_iterator& other) const {
  274. return !(*this == other);
  275. }
  276. private:
  277. friend class small_map;
  278. inline explicit const_iterator(const value_type* init)
  279. : array_iter_(init) {}
  280. inline explicit const_iterator(
  281. const typename NormalMap::const_iterator& init)
  282. : array_iter_(nullptr), map_iter_(init) {}
  283. raw_ptr<const value_type> array_iter_;
  284. typename NormalMap::const_iterator map_iter_;
  285. };
  286. iterator find(const key_type& key) {
  287. key_equal compare;
  288. if (UsingFullMap()) {
  289. return iterator(map()->find(key));
  290. }
  291. for (size_t i = 0; i < size_; ++i) {
  292. if (compare(array_[i].first, key)) {
  293. return iterator(array_ + i);
  294. }
  295. }
  296. return iterator(array_ + size_);
  297. }
  298. const_iterator find(const key_type& key) const {
  299. key_equal compare;
  300. if (UsingFullMap()) {
  301. return const_iterator(map()->find(key));
  302. }
  303. for (size_t i = 0; i < size_; ++i) {
  304. if (compare(array_[i].first, key)) {
  305. return const_iterator(array_ + i);
  306. }
  307. }
  308. return const_iterator(array_ + size_);
  309. }
  310. // Invalidates iterators.
  311. data_type& operator[](const key_type& key) {
  312. key_equal compare;
  313. if (UsingFullMap()) {
  314. return map_[key];
  315. }
  316. // Search backwards to favor recently-added elements.
  317. for (size_t i = size_; i > 0; --i) {
  318. const size_t index = i - 1;
  319. if (compare(array_[index].first, key)) {
  320. return array_[index].second;
  321. }
  322. }
  323. if (size_ == kArraySize) {
  324. ConvertToRealMap();
  325. return map_[key];
  326. }
  327. DCHECK(size_ < kArraySize);
  328. new (&array_[size_]) value_type(key, data_type());
  329. return array_[size_++].second;
  330. }
  331. // Invalidates iterators.
  332. std::pair<iterator, bool> insert(const value_type& x) {
  333. key_equal compare;
  334. if (UsingFullMap()) {
  335. std::pair<typename NormalMap::iterator, bool> ret = map_.insert(x);
  336. return std::make_pair(iterator(ret.first), ret.second);
  337. }
  338. for (size_t i = 0; i < size_; ++i) {
  339. if (compare(array_[i].first, x.first)) {
  340. return std::make_pair(iterator(array_ + i), false);
  341. }
  342. }
  343. if (size_ == kArraySize) {
  344. ConvertToRealMap(); // Invalidates all iterators!
  345. std::pair<typename NormalMap::iterator, bool> ret = map_.insert(x);
  346. return std::make_pair(iterator(ret.first), ret.second);
  347. }
  348. DCHECK(size_ < kArraySize);
  349. new (&array_[size_]) value_type(x);
  350. return std::make_pair(iterator(array_ + size_++), true);
  351. }
  352. // Invalidates iterators.
  353. template <class InputIterator>
  354. void insert(InputIterator f, InputIterator l) {
  355. while (f != l) {
  356. insert(*f);
  357. ++f;
  358. }
  359. }
  360. // Invalidates iterators.
  361. template <typename... Args>
  362. std::pair<iterator, bool> emplace(Args&&... args) {
  363. key_equal compare;
  364. if (UsingFullMap()) {
  365. std::pair<typename NormalMap::iterator, bool> ret =
  366. map_.emplace(std::forward<Args>(args)...);
  367. return std::make_pair(iterator(ret.first), ret.second);
  368. }
  369. value_type x(std::forward<Args>(args)...);
  370. for (size_t i = 0; i < size_; ++i) {
  371. if (compare(array_[i].first, x.first)) {
  372. return std::make_pair(iterator(array_ + i), false);
  373. }
  374. }
  375. if (size_ == kArraySize) {
  376. ConvertToRealMap(); // Invalidates all iterators!
  377. std::pair<typename NormalMap::iterator, bool> ret =
  378. map_.emplace(std::move(x));
  379. return std::make_pair(iterator(ret.first), ret.second);
  380. }
  381. DCHECK(size_ < kArraySize);
  382. new (&array_[size_]) value_type(std::move(x));
  383. return std::make_pair(iterator(array_ + size_++), true);
  384. }
  385. iterator begin() {
  386. return UsingFullMap() ? iterator(map_.begin()) : iterator(array_);
  387. }
  388. const_iterator begin() const {
  389. return UsingFullMap() ? const_iterator(map_.begin())
  390. : const_iterator(array_);
  391. }
  392. iterator end() {
  393. return UsingFullMap() ? iterator(map_.end()) : iterator(array_ + size_);
  394. }
  395. const_iterator end() const {
  396. return UsingFullMap() ? const_iterator(map_.end())
  397. : const_iterator(array_ + size_);
  398. }
  399. void clear() {
  400. if (UsingFullMap()) {
  401. map_.~NormalMap();
  402. } else {
  403. for (size_t i = 0; i < size_; ++i) {
  404. array_[i].~value_type();
  405. }
  406. }
  407. size_ = 0;
  408. }
  409. // Invalidates iterators. Returns iterator following the last removed element.
  410. iterator erase(const iterator& position) {
  411. if (UsingFullMap()) {
  412. return iterator(map_.erase(position.map_iter_));
  413. }
  414. size_t i = static_cast<size_t>(position.array_iter_ - array_);
  415. // TODO(crbug.com/817982): When we have a checked iterator, this CHECK might
  416. // not be necessary.
  417. CHECK_LE(i, size_);
  418. array_[i].~value_type();
  419. --size_;
  420. if (i != size_) {
  421. new (&array_[i]) value_type(std::move(array_[size_]));
  422. array_[size_].~value_type();
  423. return iterator(array_ + i);
  424. }
  425. return end();
  426. }
  427. size_t erase(const key_type& key) {
  428. iterator iter = find(key);
  429. if (iter == end()) {
  430. return 0;
  431. }
  432. erase(iter);
  433. return 1;
  434. }
  435. size_t count(const key_type& key) const {
  436. return (find(key) == end()) ? 0 : 1;
  437. }
  438. size_t size() const { return UsingFullMap() ? map_.size() : size_; }
  439. bool empty() const { return UsingFullMap() ? map_.empty() : size_ == 0; }
  440. // Returns true if we have fallen back to using the underlying map
  441. // representation.
  442. bool UsingFullMap() const { return size_ == kUsingFullMapSentinel; }
  443. inline NormalMap* map() {
  444. CHECK(UsingFullMap());
  445. return &map_;
  446. }
  447. inline const NormalMap* map() const {
  448. CHECK(UsingFullMap());
  449. return &map_;
  450. }
  451. private:
  452. // When `size_ == kUsingFullMapSentinel`, we have switched storage strategies
  453. // from `array_[kArraySize] to `NormalMap map_`. See ConvertToRealMap and
  454. // UsingFullMap.
  455. size_t size_;
  456. MapInit functor_;
  457. // We want to call constructors and destructors manually, but we don't want
  458. // to allocate and deallocate the memory used for them separately. Since
  459. // array_ and map_ are mutually exclusive, we'll put them in a union.
  460. union {
  461. value_type array_[kArraySize];
  462. NormalMap map_;
  463. };
  464. void ConvertToRealMap() {
  465. // Storage for the elements in the temporary array. This is intentionally
  466. // declared as a union to avoid having to default-construct |kArraySize|
  467. // elements, only to move construct over them in the initial loop.
  468. union Storage {
  469. Storage() {}
  470. ~Storage() {}
  471. value_type array[kArraySize];
  472. } temp;
  473. // Move the current elements into a temporary array.
  474. for (size_t i = 0; i < kArraySize; ++i) {
  475. new (&temp.array[i]) value_type(std::move(array_[i]));
  476. array_[i].~value_type();
  477. }
  478. // Initialize the map.
  479. size_ = kUsingFullMapSentinel;
  480. functor_(&map_);
  481. // Insert elements into it.
  482. for (size_t i = 0; i < kArraySize; ++i) {
  483. map_.insert(std::move(temp.array[i]));
  484. temp.array[i].~value_type();
  485. }
  486. }
  487. // Helpers for constructors and destructors.
  488. void InitFrom(const small_map& src) {
  489. functor_ = src.functor_;
  490. size_ = src.size_;
  491. if (src.UsingFullMap()) {
  492. functor_(&map_);
  493. map_ = src.map_;
  494. } else {
  495. for (size_t i = 0; i < size_; ++i) {
  496. new (&array_[i]) value_type(src.array_[i]);
  497. }
  498. }
  499. }
  500. void Destroy() {
  501. if (UsingFullMap()) {
  502. map_.~NormalMap();
  503. } else {
  504. for (size_t i = 0; i < size_; ++i) {
  505. array_[i].~value_type();
  506. }
  507. }
  508. }
  509. };
  510. } // namespace base
  511. #endif // BASE_CONTAINERS_SMALL_MAP_H_