| // Copyright 2012 The Chromium Authors. All rights reserved. | |
| // Use of this source code is governed by a BSD-style license that can be | |
| // found in the LICENSE file. | |
| // Copyright 2023 the V8 project authors. All rights reserved. | |
| // This file is a clone of "base/containers/small_map.h" in chromium. | |
| // Keep in sync, especially when fixing bugs. | |
| #ifndef V8_BASE_SMALL_MAP_H_ | |
| #define V8_BASE_SMALL_MAP_H_ | |
| #include "src/base/macros.h" | |
| namespace v8::base { | |
| // SmallMap is a container with a std::map-like interface. It starts out backed | |
| // by an unsorted array but switches to some other container type if it grows | |
| // beyond this fixed size. | |
| // | |
| // PROS | |
| // | |
| // - Good memory locality and low overhead for smaller maps. | |
| // - Handles large maps without the degenerate performance of an array. | |
| // | |
| // CONS | |
| // | |
| // - Larger code size than the alternatives. | |
| // | |
| // IMPORTANT NOTES | |
| // | |
| // - Iterators are invalidated across mutations. | |
| // | |
| // DETAILS | |
| // | |
| // SmallMap will pick up the comparator from the underlying map type. In | |
| // std::map only a "less" operator is defined, which requires us to do two | |
| // comparisons per element when doing the brute-force search in the simple | |
| // array. std::unordered_map has a key_equal function which will be used. | |
| // | |
| // We define default overrides for the common map types to avoid this | |
| // double-compare, but you should be aware of this if you use your own operator< | |
| // for your map and supply your own version of == to the SmallMap. You can use | |
| // regular operator== by just doing: | |
| // | |
| // SmallMap<std::map<MyKey, MyValue>, 4, std::equal_to<MyKey>> | |
| // | |
| // | |
| // USAGE | |
| // ----- | |
| // | |
| // NormalMap: The map type to fall back to. This also defines the key and value | |
| // types for the SmallMap. | |
| // kArraySize: The size of the initial array of results. This will be allocated | |
| // with the SmallMap object rather than separately on the heap. | |
| // Once the map grows beyond this size, the map type will be used | |
| // instead. | |
| // EqualKey: A functor which tests two keys for equality. If the wrapped map | |
| // type has a "key_equal" member (unordered_map does), then that will | |
| // be used by default. If the wrapped map type has a strict weak | |
| // ordering "key_compare" (std::map does), that will be used to | |
| // implement equality by default. | |
| // MapInit: A functor that takes a NormalMap* and uses it to initialize the map. | |
| // This functor will be called at most once per SmallMap, when the map | |
| // exceeds the threshold of kArraySize and we are about to copy values | |
| // from the array to the map. The functor *must* initialize the | |
| // NormalMap* argument with placement new, since after it runs we | |
| // assume that the NormalMap has been initialized. | |
| // | |
| // Example: | |
| // SmallMap<std::map<string, int>> days; | |
| // days["sunday" ] = 0; | |
| // days["monday" ] = 1; | |
| // days["tuesday" ] = 2; | |
| // days["wednesday"] = 3; | |
| // days["thursday" ] = 4; | |
| // days["friday" ] = 5; | |
| // days["saturday" ] = 6; | |
| namespace internal { | |
| template <typename NormalMap> | |
| class SmallMapDefaultInit { | |
| public: | |
| void operator()(NormalMap* map) const { new (map) NormalMap(); } | |
| }; | |
| // has_key_equal<M>::value is true iff there exists a type M::key_equal. This is | |
| // used to dispatch to one of the select_equal_key<> metafunctions below. | |
| template <typename M> | |
| struct has_key_equal { | |
| typedef char sml; // "small" is sometimes #defined so we use an abbreviation. | |
| typedef struct { | |
| char dummy[2]; | |
| } big; | |
| // Two functions, one accepts types that have a key_equal member, and one that | |
| // accepts anything. They each return a value of a different size, so we can | |
| // determine at compile-time which function would have been called. | |
| template <typename U> | |
| static big test(typename U::key_equal*); | |
| template <typename> | |
| static sml test(...); | |
| // Determines if M::key_equal exists by looking at the size of the return | |
| // type of the compiler-chosen test() function. | |
| static const bool value = (sizeof(test<M>(0)) == sizeof(big)); | |
| }; | |
| template <typename M> | |
| const bool has_key_equal<M>::value; | |
| // Base template used for map types that do NOT have an M::key_equal member, | |
| // e.g., std::map<>. These maps have a strict weak ordering comparator rather | |
| // than an equality functor, so equality will be implemented in terms of that | |
| // comparator. | |
| // | |
| // There's a partial specialization of this template below for map types that do | |
| // have an M::key_equal member. | |
| template <typename M, bool has_key_equal_value> | |
| struct select_equal_key { | |
| struct equal_key { | |
| bool operator()(const typename M::key_type& left, | |
| const typename M::key_type& right) { | |
| // Implements equality in terms of a strict weak ordering comparator. | |
| typename M::key_compare comp; | |
| return !comp(left, right) && !comp(right, left); | |
| } | |
| }; | |
| }; | |
| // Partial template specialization handles case where M::key_equal exists, e.g., | |
| // unordered_map<>. | |
| template <typename M> | |
| struct select_equal_key<M, true> { | |
| typedef typename M::key_equal equal_key; | |
| }; | |
| } // namespace internal | |
| template <typename NormalMap, size_t kArraySize = 4, | |
| typename EqualKey = typename internal::select_equal_key< | |
| NormalMap, internal::has_key_equal<NormalMap>::value>::equal_key, | |
| typename MapInit = internal::SmallMapDefaultInit<NormalMap>> | |
| class SmallMap { | |
| static constexpr size_t kUsingFullMapSentinel = | |
| std::numeric_limits<size_t>::max(); | |
| static_assert(kArraySize > 0, "Initial size must be greater than 0"); | |
| static_assert(kArraySize != kUsingFullMapSentinel, | |
| "Initial size out of range"); | |
| public: | |
| typedef typename NormalMap::key_type key_type; | |
| typedef typename NormalMap::mapped_type data_type; | |
| typedef typename NormalMap::mapped_type mapped_type; | |
| typedef typename NormalMap::value_type value_type; | |
| typedef EqualKey key_equal; | |
| SmallMap() : size_(0), functor_(MapInit()) {} | |
| explicit SmallMap(const MapInit& functor) : size_(0), functor_(functor) {} | |
| // Allow copy-constructor and assignment, since STL allows them too. | |
| SmallMap(const SmallMap& src) V8_NOEXCEPT { | |
| // size_ and functor_ are initted in InitFrom() | |
| InitFrom(src); | |
| } | |
| void operator=(const SmallMap& src) V8_NOEXCEPT { | |
| if (&src == this) return; | |
| // This is not optimal. If src and dest are both using the small array, we | |
| // could skip the teardown and reconstruct. One problem to be resolved is | |
| // that the value_type itself is pair<const K, V>, and const K is not | |
| // assignable. | |
| Destroy(); | |
| InitFrom(src); | |
| } | |
| ~SmallMap() { Destroy(); } | |
| class const_iterator; | |
| class iterator { | |
| public: | |
| typedef typename NormalMap::iterator::iterator_category iterator_category; | |
| typedef typename NormalMap::iterator::value_type value_type; | |
| typedef typename NormalMap::iterator::difference_type difference_type; | |
| typedef typename NormalMap::iterator::pointer pointer; | |
| typedef typename NormalMap::iterator::reference reference; | |
| V8_INLINE iterator() : array_iter_(nullptr) {} | |
| V8_INLINE iterator& operator++() { | |
| if (array_iter_ != nullptr) { | |
| ++array_iter_; | |
| } else { | |
| ++map_iter_; | |
| } | |
| return *this; | |
| } | |
| V8_INLINE iterator operator++(int /*unused*/) { | |
| iterator result(*this); | |
| ++(*this); | |
| return result; | |
| } | |
| V8_INLINE iterator& operator--() { | |
| if (array_iter_ != nullptr) { | |
| --array_iter_; | |
| } else { | |
| --map_iter_; | |
| } | |
| return *this; | |
| } | |
| V8_INLINE iterator operator--(int /*unused*/) { | |
| iterator result(*this); | |
| --(*this); | |
| return result; | |
| } | |
| V8_INLINE value_type* operator->() const { | |
| return array_iter_ ? array_iter_ : map_iter_.operator->(); | |
| } | |
| V8_INLINE value_type& operator*() const { | |
| return array_iter_ ? *array_iter_ : *map_iter_; | |
| } | |
| V8_INLINE bool operator==(const iterator& other) const { | |
| if (array_iter_ != nullptr) { | |
| return array_iter_ == other.array_iter_; | |
| } else { | |
| return other.array_iter_ == nullptr && map_iter_ == other.map_iter_; | |
| } | |
| } | |
| V8_INLINE bool operator!=(const iterator& other) const { | |
| return !(*this == other); | |
| } | |
| private: | |
| friend class SmallMap; | |
| friend class const_iterator; | |
| V8_INLINE explicit iterator(value_type* init) : array_iter_(init) {} | |
| V8_INLINE explicit iterator(const typename NormalMap::iterator& init) | |
| : array_iter_(nullptr), map_iter_(init) {} | |
| value_type* array_iter_; | |
| typename NormalMap::iterator map_iter_; | |
| }; | |
| class const_iterator { | |
| public: | |
| typedef | |
| typename NormalMap::const_iterator::iterator_category iterator_category; | |
| typedef typename NormalMap::const_iterator::value_type value_type; | |
| typedef typename NormalMap::const_iterator::difference_type difference_type; | |
| typedef typename NormalMap::const_iterator::pointer pointer; | |
| typedef typename NormalMap::const_iterator::reference reference; | |
| V8_INLINE const_iterator() : array_iter_(nullptr) {} | |
| // Non-explicit constructor lets us convert regular iterators to const | |
| // iterators. | |
| V8_INLINE const_iterator(const iterator& other) | |
| : array_iter_(other.array_iter_), map_iter_(other.map_iter_) {} | |
| V8_INLINE const_iterator& operator++() { | |
| if (array_iter_ != nullptr) { | |
| ++array_iter_; | |
| } else { | |
| ++map_iter_; | |
| } | |
| return *this; | |
| } | |
| V8_INLINE const_iterator operator++(int /*unused*/) { | |
| const_iterator result(*this); | |
| ++(*this); | |
| return result; | |
| } | |
| V8_INLINE const_iterator& operator--() { | |
| if (array_iter_ != nullptr) { | |
| --array_iter_; | |
| } else { | |
| --map_iter_; | |
| } | |
| return *this; | |
| } | |
| V8_INLINE const_iterator operator--(int /*unused*/) { | |
| const_iterator result(*this); | |
| --(*this); | |
| return result; | |
| } | |
| V8_INLINE const value_type* operator->() const { | |
| return array_iter_ ? array_iter_ : map_iter_.operator->(); | |
| } | |
| V8_INLINE const value_type& operator*() const { | |
| return array_iter_ ? *array_iter_ : *map_iter_; | |
| } | |
| V8_INLINE bool operator==(const const_iterator& other) const { | |
| if (array_iter_ != nullptr) { | |
| return array_iter_ == other.array_iter_; | |
| } | |
| return other.array_iter_ == nullptr && map_iter_ == other.map_iter_; | |
| } | |
| V8_INLINE bool operator!=(const const_iterator& other) const { | |
| return !(*this == other); | |
| } | |
| private: | |
| friend class SmallMap; | |
| V8_INLINE explicit const_iterator(const value_type* init) | |
| : array_iter_(init) {} | |
| V8_INLINE explicit const_iterator( | |
| const typename NormalMap::const_iterator& init) | |
| : array_iter_(nullptr), map_iter_(init) {} | |
| const value_type* array_iter_; | |
| typename NormalMap::const_iterator map_iter_; | |
| }; | |
| iterator find(const key_type& key) { | |
| key_equal compare; | |
| if (UsingFullMap()) { | |
| return iterator(map()->find(key)); | |
| } | |
| for (size_t i = 0; i < size_; ++i) { | |
| if (compare(array_[i].first, key)) { | |
| return iterator(array_ + i); | |
| } | |
| } | |
| return iterator(array_ + size_); | |
| } | |
| const_iterator find(const key_type& key) const { | |
| key_equal compare; | |
| if (UsingFullMap()) { | |
| return const_iterator(map()->find(key)); | |
| } | |
| for (size_t i = 0; i < size_; ++i) { | |
| if (compare(array_[i].first, key)) { | |
| return const_iterator(array_ + i); | |
| } | |
| } | |
| return const_iterator(array_ + size_); | |
| } | |
| // Invalidates iterators. | |
| data_type& operator[](const key_type& key) { | |
| key_equal compare; | |
| if (UsingFullMap()) { | |
| return map_[key]; | |
| } | |
| // Search backwards to favor recently-added elements. | |
| for (size_t i = size_; i > 0; --i) { | |
| const size_t index = i - 1; | |
| if (compare(array_[index].first, key)) { | |
| return array_[index].second; | |
| } | |
| } | |
| if (V8_UNLIKELY(size_ == kArraySize)) { | |
| ConvertToRealMap(); | |
| return map_[key]; | |
| } | |
| DCHECK(size_ < kArraySize); | |
| new (&array_[size_]) value_type(key, data_type()); | |
| return array_[size_++].second; | |
| } | |
| // Invalidates iterators. | |
| std::pair<iterator, bool> insert(const value_type& x) { | |
| key_equal compare; | |
| if (UsingFullMap()) { | |
| std::pair<typename NormalMap::iterator, bool> ret = map_.insert(x); | |
| return std::make_pair(iterator(ret.first), ret.second); | |
| } | |
| for (size_t i = 0; i < size_; ++i) { | |
| if (compare(array_[i].first, x.first)) { | |
| return std::make_pair(iterator(array_ + i), false); | |
| } | |
| } | |
| if (V8_UNLIKELY(size_ == kArraySize)) { | |
| ConvertToRealMap(); // Invalidates all iterators! | |
| std::pair<typename NormalMap::iterator, bool> ret = map_.insert(x); | |
| return std::make_pair(iterator(ret.first), ret.second); | |
| } | |
| DCHECK(size_ < kArraySize); | |
| new (&array_[size_]) value_type(x); | |
| return std::make_pair(iterator(array_ + size_++), true); | |
| } | |
| // Invalidates iterators. | |
| template <class InputIterator> | |
| void insert(InputIterator f, InputIterator l) { | |
| while (f != l) { | |
| insert(*f); | |
| ++f; | |
| } | |
| } | |
| // Invalidates iterators. | |
| template <typename... Args> | |
| std::pair<iterator, bool> emplace(Args&&... args) { | |
| key_equal compare; | |
| if (UsingFullMap()) { | |
| std::pair<typename NormalMap::iterator, bool> ret = | |
| map_.emplace(std::forward<Args>(args)...); | |
| return std::make_pair(iterator(ret.first), ret.second); | |
| } | |
| value_type x(std::forward<Args>(args)...); | |
| for (size_t i = 0; i < size_; ++i) { | |
| if (compare(array_[i].first, x.first)) { | |
| return std::make_pair(iterator(array_ + i), false); | |
| } | |
| } | |
| if (V8_UNLIKELY(size_ == kArraySize)) { | |
| ConvertToRealMap(); // Invalidates all iterators! | |
| std::pair<typename NormalMap::iterator, bool> ret = | |
| map_.emplace(std::move(x)); | |
| return std::make_pair(iterator(ret.first), ret.second); | |
| } | |
| DCHECK(size_ < kArraySize); | |
| new (&array_[size_]) value_type(std::move(x)); | |
| return std::make_pair(iterator(array_ + size_++), true); | |
| } | |
| // Invalidates iterators. | |
| template <typename... Args> | |
| std::pair<iterator, bool> try_emplace(const key_type& key, Args&&... args) { | |
| key_equal compare; | |
| if (UsingFullMap()) { | |
| std::pair<typename NormalMap::iterator, bool> ret = | |
| map_.try_emplace(key, std::forward<Args>(args)...); | |
| return std::make_pair(iterator(ret.first), ret.second); | |
| } | |
| for (size_t i = 0; i < size_; ++i) { | |
| if (compare(array_[i].first, key)) { | |
| return std::make_pair(iterator(array_ + i), false); | |
| } | |
| } | |
| if (V8_UNLIKELY(size_ == kArraySize)) { | |
| ConvertToRealMap(); // Invalidates all iterators! | |
| std::pair<typename NormalMap::iterator, bool> ret = | |
| map_.try_emplace(key, std::forward<Args>(args)...); | |
| return std::make_pair(iterator(ret.first), ret.second); | |
| } | |
| DCHECK(size_ < kArraySize); | |
| new (&array_[size_]) value_type(key, std::forward<Args>(args)...); | |
| return std::make_pair(iterator(array_ + size_++), true); | |
| } | |
| iterator begin() { | |
| return UsingFullMap() ? iterator(map_.begin()) : iterator(array_); | |
| } | |
| const_iterator begin() const { | |
| return UsingFullMap() ? const_iterator(map_.begin()) | |
| : const_iterator(array_); | |
| } | |
| iterator end() { | |
| return UsingFullMap() ? iterator(map_.end()) : iterator(array_ + size_); | |
| } | |
| const_iterator end() const { | |
| return UsingFullMap() ? const_iterator(map_.end()) | |
| : const_iterator(array_ + size_); | |
| } | |
| void clear() { | |
| if (UsingFullMap()) { | |
| map_.~NormalMap(); | |
| } else { | |
| for (size_t i = 0; i < size_; ++i) { | |
| array_[i].~value_type(); | |
| } | |
| } | |
| size_ = 0; | |
| } | |
| // Invalidates iterators. Returns iterator following the last removed element. | |
| iterator erase(const iterator& position) { | |
| if (UsingFullMap()) { | |
| return iterator(map_.erase(position.map_iter_)); | |
| } | |
| size_t i = static_cast<size_t>(position.array_iter_ - array_); | |
| // TODO(crbug.com/817982): When we have a checked iterator, this CHECK might | |
| // not be necessary. | |
| CHECK_LE(i, size_); | |
| array_[i].~value_type(); | |
| --size_; | |
| if (i != size_) { | |
| new (&array_[i]) value_type(std::move(array_[size_])); | |
| array_[size_].~value_type(); | |
| return iterator(array_ + i); | |
| } | |
| return end(); | |
| } | |
| size_t erase(const key_type& key) { | |
| iterator iter = find(key); | |
| if (iter == end()) { | |
| return 0; | |
| } | |
| erase(iter); | |
| return 1; | |
| } | |
| size_t count(const key_type& key) const { | |
| return (find(key) == end()) ? 0 : 1; | |
| } | |
| size_t size() const { return UsingFullMap() ? map_.size() : size_; } | |
| bool empty() const { return UsingFullMap() ? map_.empty() : size_ == 0; } | |
| // Returns true if we have fallen back to using the underlying map | |
| // representation. | |
| bool UsingFullMap() const { return size_ == kUsingFullMapSentinel; } | |
| V8_INLINE NormalMap* map() { | |
| CHECK(UsingFullMap()); | |
| return &map_; | |
| } | |
| V8_INLINE const NormalMap* map() const { | |
| CHECK(UsingFullMap()); | |
| return &map_; | |
| } | |
| private: | |
| // When `size_ == kUsingFullMapSentinel`, we have switched storage strategies | |
| // from `array_[kArraySize] to `NormalMap map_`. See ConvertToRealMap and | |
| // UsingFullMap. | |
| size_t size_; | |
| MapInit functor_; | |
| // We want to call constructors and destructors manually, but we don't want | |
| // to allocate and deallocate the memory used for them separately. Since | |
| // array_ and map_ are mutually exclusive, we'll put them in a union. | |
| union { | |
| value_type array_[kArraySize]; | |
| NormalMap map_; | |
| }; | |
| V8_NOINLINE V8_PRESERVE_MOST void ConvertToRealMap() { | |
| // Storage for the elements in the temporary array. This is intentionally | |
| // declared as a union to avoid having to default-construct |kArraySize| | |
| // elements, only to move construct over them in the initial loop. | |
| union Storage { | |
| Storage() {} | |
| ~Storage() {} | |
| value_type array[kArraySize]; | |
| } temp; | |
| // Move the current elements into a temporary array. | |
| for (size_t i = 0; i < kArraySize; ++i) { | |
| new (&temp.array[i]) value_type(std::move(array_[i])); | |
| array_[i].~value_type(); | |
| } | |
| // Initialize the map. | |
| size_ = kUsingFullMapSentinel; | |
| functor_(&map_); | |
| // Insert elements into it. | |
| for (size_t i = 0; i < kArraySize; ++i) { | |
| map_.insert(std::move(temp.array[i])); | |
| temp.array[i].~value_type(); | |
| } | |
| } | |
| // Helpers for constructors and destructors. | |
| void InitFrom(const SmallMap& src) { | |
| functor_ = src.functor_; | |
| size_ = src.size_; | |
| if (src.UsingFullMap()) { | |
| functor_(&map_); | |
| map_ = src.map_; | |
| } else { | |
| for (size_t i = 0; i < size_; ++i) { | |
| new (&array_[i]) value_type(src.array_[i]); | |
| } | |
| } | |
| } | |
| void Destroy() { | |
| if (UsingFullMap()) { | |
| map_.~NormalMap(); | |
| } else { | |
| for (size_t i = 0; i < size_; ++i) { | |
| array_[i].~value_type(); | |
| } | |
| } | |
| } | |
| }; | |
| } // namespace v8::base | |
| #endif // V8_BASE_SMALL_MAP_H_ |