absl/container/internal/raw_hash_map.h

// Copyright 2018 The Abseil Authors.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      https://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

#ifndef ABSL_CONTAINER_INTERNAL_RAW_HASH_MAP_H_
#define ABSL_CONTAINER_INTERNAL_RAW_HASH_MAP_H_

#include <tuple>
#include <type_traits>
#include <utility>

#include "absl/base/attributes.h"
#include "absl/base/config.h"
#include "absl/base/internal/throw_delegate.h"
#include "absl/container/internal/container_memory.h"
#include "absl/container/internal/raw_hash_set.h"  // IWYU pragma: export

namespace absl {
ABSL_NAMESPACE_BEGIN
namespace container_internal {

template <class Policy, class Hash, class Eq, class Alloc>
class raw_hash_map : public raw_hash_set<Policy, Hash, Eq, Alloc> {
  // P is Policy. It's passed as a template argument to support maps that have
  // incomplete types as values, as in unordered_map<K, IncompleteType>.
  // MappedReference<> may be a non-reference type.
  template <class P>
  using MappedReference = decltype(P::value(
      std::addressof(std::declval<typename raw_hash_map::reference>())));

  // MappedConstReference<> may be a non-reference type.
  template <class P>
  using MappedConstReference = decltype(P::value(
      std::addressof(std::declval<typename raw_hash_map::const_reference>())));

  using KeyArgImpl =
      KeyArg<IsTransparent<Eq>::value && IsTransparent<Hash>::value>;

 public:
  using key_type = typename Policy::key_type;
  using mapped_type = typename Policy::mapped_type;
  template <class K>
  using key_arg = typename KeyArgImpl::template type<K, key_type>;

  static_assert(!std::is_reference<key_type>::value, "");

  // TODO(b/187807849): Evaluate whether to support reference mapped_type and
  // remove this assertion if/when it is supported.
  static_assert(!std::is_reference<mapped_type>::value, "");

  using iterator = typename raw_hash_map::raw_hash_set::iterator;
  using const_iterator = typename raw_hash_map::raw_hash_set::const_iterator;

  raw_hash_map() {}
  using raw_hash_map::raw_hash_set::raw_hash_set;

  // The last two template parameters ensure that both arguments are rvalues
  // (lvalue arguments are handled by the overloads below). This is necessary
  // for supporting bitfield arguments.
  //
  //   union { int n : 1; };
  //   flat_hash_map<int, int> m;
  //   m.insert_or_assign(n, n);
  template <class K = key_type, class V = mapped_type, K* = nullptr,
            V* = nullptr>
  std::pair<iterator, bool> insert_or_assign(key_arg<K>&& k, V&& v)
      ABSL_ATTRIBUTE_LIFETIME_BOUND {
    return insert_or_assign_impl(std::forward<K>(k), std::forward<V>(v));
  }

  template <class K = key_type, class V = mapped_type, K* = nullptr>
  std::pair<iterator, bool> insert_or_assign(key_arg<K>&& k, const V& v)
      ABSL_ATTRIBUTE_LIFETIME_BOUND {
    return insert_or_assign_impl(std::forward<K>(k), v);
  }

  template <class K = key_type, class V = mapped_type, V* = nullptr>
  std::pair<iterator, bool> insert_or_assign(const key_arg<K>& k, V&& v)
      ABSL_ATTRIBUTE_LIFETIME_BOUND {
    return insert_or_assign_impl(k, std::forward<V>(v));
  }

  template <class K = key_type, class V = mapped_type>
  std::pair<iterator, bool> insert_or_assign(const key_arg<K>& k, const V& v)
      ABSL_ATTRIBUTE_LIFETIME_BOUND {
    return insert_or_assign_impl(k, v);
  }

  template <class K = key_type, class V = mapped_type, K* = nullptr,
            V* = nullptr>
  iterator insert_or_assign(const_iterator, key_arg<K>&& k,
                            V&& v) ABSL_ATTRIBUTE_LIFETIME_BOUND {
    return insert_or_assign(std::forward<K>(k), std::forward<V>(v)).first;
  }

  template <class K = key_type, class V = mapped_type, K* = nullptr>
  iterator insert_or_assign(const_iterator, key_arg<K>&& k,
                            const V& v) ABSL_ATTRIBUTE_LIFETIME_BOUND {
    return insert_or_assign(std::forward<K>(k), v).first;
  }

  template <class K = key_type, class V = mapped_type, V* = nullptr>
  iterator insert_or_assign(const_iterator, const key_arg<K>& k,
                            V&& v) ABSL_ATTRIBUTE_LIFETIME_BOUND {
    return insert_or_assign(k, std::forward<V>(v)).first;
  }

  template <class K = key_type, class V = mapped_type>
  iterator insert_or_assign(const_iterator, const key_arg<K>& k,
                            const V& v) ABSL_ATTRIBUTE_LIFETIME_BOUND {
    return insert_or_assign(k, v).first;
  }

  // All `try_emplace()` overloads make the same guarantees regarding rvalue
  // arguments as `std::unordered_map::try_emplace()`, namely that these
  // functions will not move from rvalue arguments if insertions do not happen.
  template <class K = key_type, class... Args,
            typename std::enable_if<
                !std::is_convertible<K, const_iterator>::value, int>::type = 0,
            K* = nullptr>
  std::pair<iterator, bool> try_emplace(key_arg<K>&& k, Args&&... args)
      ABSL_ATTRIBUTE_LIFETIME_BOUND {
    return try_emplace_impl(std::forward<K>(k), std::forward<Args>(args)...);
  }

  template <class K = key_type, class... Args,
            typename std::enable_if<
                !std::is_convertible<K, const_iterator>::value, int>::type = 0>
  std::pair<iterator, bool> try_emplace(const key_arg<K>& k, Args&&... args)
      ABSL_ATTRIBUTE_LIFETIME_BOUND {
    return try_emplace_impl(k, std::forward<Args>(args)...);
  }

  template <class K = key_type, class... Args, K* = nullptr>
  iterator try_emplace(const_iterator, key_arg<K>&& k,
                       Args&&... args) ABSL_ATTRIBUTE_LIFETIME_BOUND {
    return try_emplace(std::forward<K>(k), std::forward<Args>(args)...).first;
  }

  template <class K = key_type, class... Args>
  iterator try_emplace(const_iterator, const key_arg<K>& k,
                       Args&&... args) ABSL_ATTRIBUTE_LIFETIME_BOUND {
    return try_emplace(k, std::forward<Args>(args)...).first;
  }

  template <class K = key_type, class P = Policy>
  MappedReference<P> at(const key_arg<K>& key) ABSL_ATTRIBUTE_LIFETIME_BOUND {
    auto it = this->find(key);
    if (it == this->end()) {
      base_internal::ThrowStdOutOfRange(
          "absl::container_internal::raw_hash_map<>::at");
    }
    return Policy::value(&*it);
  }

  template <class K = key_type, class P = Policy>
  MappedConstReference<P> at(const key_arg<K>& key) const
      ABSL_ATTRIBUTE_LIFETIME_BOUND {
    auto it = this->find(key);
    if (it == this->end()) {
      base_internal::ThrowStdOutOfRange(
          "absl::container_internal::raw_hash_map<>::at");
    }
    return Policy::value(&*it);
  }

  template <class K = key_type, class P = Policy, K* = nullptr>
  MappedReference<P> operator[](key_arg<K>&& key)
      ABSL_ATTRIBUTE_LIFETIME_BOUND {
    // It is safe to use unchecked_deref here because try_emplace
    // will always return an iterator pointing to a valid item in the table,
    // since it inserts if nothing is found for the given key.
    return Policy::value(
        &this->unchecked_deref(try_emplace(std::forward<K>(key)).first));
  }

  template <class K = key_type, class P = Policy>
  MappedReference<P> operator[](const key_arg<K>& key)
      ABSL_ATTRIBUTE_LIFETIME_BOUND {
    // It is safe to use unchecked_deref here because try_emplace
    // will always return an iterator pointing to a valid item in the table,
    // since it inserts if nothing is found for the given key.
    return Policy::value(&this->unchecked_deref(try_emplace(key).first));
  }

 private:
  template <class K, class V>
  std::pair<iterator, bool> insert_or_assign_impl(K&& k, V&& v)
      ABSL_ATTRIBUTE_LIFETIME_BOUND {
    auto res = this->find_or_prepare_insert(k);
    if (res.second) {
      this->emplace_at(res.first, std::forward<K>(k), std::forward<V>(v));
    } else {
      Policy::value(&*res.first) = std::forward<V>(v);
    }
    return res;
  }

  template <class K = key_type, class... Args>
  std::pair<iterator, bool> try_emplace_impl(K&& k, Args&&... args)
      ABSL_ATTRIBUTE_LIFETIME_BOUND {
    auto res = this->find_or_prepare_insert(k);
    if (res.second) {
      this->emplace_at(res.first, std::piecewise_construct,
                       std::forward_as_tuple(std::forward<K>(k)),
                       std::forward_as_tuple(std::forward<Args>(args)...));
    }
    return res;
  }
};

}  // namespace container_internal
ABSL_NAMESPACE_END
}  // namespace absl

#endif  // ABSL_CONTAINER_INTERNAL_RAW_HASH_MAP_H_