chromium/v8/src/base/small-map.h

// 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 { … };

// 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 { … };
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 { … };

// Partial template specialization handles case where M::key_equal exists, e.g.,
// unordered_map<>.
select_equal_key<M, true>;

}  // 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() : … { … }

  explicit SmallMap(const MapInit& functor) : … { … }

  // Allow copy-constructor and assignment, since STL allows them too.
  SmallMap(const SmallMap& src) V8_NOEXCEPT { … }

  void operator=(const SmallMap& src) V8_NOEXCEPT { … }

  ~SmallMap() { … }

  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) { … }

  const_iterator find(const key_type& key) const { … }

  // Invalidates iterators.
  data_type& operator[](const key_type& key) { … }

  // Invalidates iterators.
  std::pair<iterator, bool> insert(const value_type& x) { … }

  // Invalidates iterators.
  template <class InputIterator>
  void insert(InputIterator f, InputIterator l) { … }

  // Invalidates iterators.
  template <typename... Args>
  std::pair<iterator, bool> emplace(Args&&... args) { … }

  // Invalidates iterators.
  template <typename... Args>
  std::pair<iterator, bool> try_emplace(const key_type& key, Args&&... args) { … }

  iterator begin() { … }

  const_iterator begin() const { … }

  iterator end() { … }

  const_iterator end() const { … }

  void clear() { … }

  // Invalidates iterators. Returns iterator following the last removed element.
  iterator erase(const iterator& position) { … }

  size_t erase(const key_type& key) { … }

  size_t count(const key_type& key) const { … }

  size_t size() const { … }

  bool empty() const { … }

  // Returns true if we have fallen back to using the underlying map
  // representation.
  bool UsingFullMap() const { … }

  V8_INLINE NormalMap* map() { … }

  V8_INLINE const NormalMap* map() const { … }

 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() { … }

  // Helpers for constructors and destructors.
  void InitFrom(const SmallMap& src) { … }

  void Destroy() { … }
};

}  // namespace v8::base

#endif  // V8_BASE_SMALL_MAP_H_