// 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/throw_delegate.h"

#include "absl/container/internal/common_policy_traits.h"

#include "absl/container/internal/container_memory.h"

#include "absl/container/internal/raw_hash_set.h"  // IWYU pragma: export

#include "absl/meta/type_traits.h"

namespace absl {

ABSL_NAMESPACE_BEGIN

namespace container_internal {

template <class Policy, class... Params>

class raw_hash_map;

template <typename Policy, typename Hash, typename Eq, typename Alloc>

struct InstantiateRawHashMap {

  using type = typename ApplyWithoutDefaultSuffix<

      raw_hash_map,

      TypeList<int, typename Policy::DefaultHash, typename Policy::DefaultEq,

               typename Policy::DefaultAlloc>,

      TypeList<Policy, Hash, Eq, Alloc>>::type;

};

template <class Policy, class... Params>

class raw_hash_map : public raw_hash_set<Policy, Params...> {

  // 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 Hash = typename raw_hash_map::raw_hash_set::hasher;

  using Eq = typename raw_hash_map::raw_hash_set::key_equal;

  using Alloc = typename raw_hash_map::raw_hash_set::allocator_type;

  template <class K>

  using key_arg =

      typename KeyArg<IsTransparent<Eq>::value && IsTransparent<Hash>::value>::

          template type<K, typename Policy::key_type>;

  // NOTE: The mess here is to shorten the code for the (very repetitive)

  // function overloads, and to allow the lifetime-bound overloads to dispatch

  // to the non-lifetime-bound overloads, to ensure there is a single source of

  // truth for each overload set.

  //

  // Enabled if an assignment from the given type would require the

  // source object to remain alive for the life of the element.

  //

  // TODO(b/402804213): Remove these traits and simplify the overloads whenever

  // we have a better mechanism available to handle lifetime analysis.

  template <class K, bool Value, typename = void>

  using LifetimeBoundK = HasValue<

      Value, std::conditional_t<policy_trait_element_is_owner<Policy>::value,

                                std::false_type,

                                type_traits_internal::IsLifetimeBoundAssignment<

                                    typename Policy::key_type, K>>>;

  template <class V, bool Value, typename = void>

  using LifetimeBoundV =

      HasValue<Value, type_traits_internal::IsLifetimeBoundAssignment<

                          typename Policy::mapped_type, V>>;

  template <class K, bool KValue, class V, bool VValue, typename... Dummy>

  using LifetimeBoundKV =

      std::conjunction<LifetimeBoundK<K, KValue, std::void_t<Dummy...>>,

                       LifetimeBoundV<V, VValue>>;

 public:

  using key_type = typename Policy::key_type;

  using mapped_type = typename Policy::mapped_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);

  //

  // TODO(b/402804213): Remove these macros whenever we have a better mechanism

  // available to handle lifetime analysis.

#define ABSL_INTERNAL_X(Func, Callee, KQual, VQual, KValue, VValue, Tail, ...) \

  template <                                                                   \

      typename K = key_type, class V = mapped_type,                            \

      ABSL_INTERNAL_IF_##KValue##_NOR_##VValue(                                \

          int = (EnableIf<LifetimeBoundKV<K, KValue, V, VValue,                \

                                          IfRRef<int KQual>::AddPtr<K>,        \

                                          IfRRef<int VQual>::AddPtr<V>>>()),   \

          ABSL_INTERNAL_SINGLE_ARG(                                            \

              int&...,                                                         \

              decltype(EnableIf<LifetimeBoundKV<K, KValue, V, VValue>>()) =    \

                  0))>                                                         \

  decltype(auto) Func(                                                         \

      __VA_ARGS__ key_arg<K> KQual k ABSL_INTERNAL_IF_##KValue(                \

          ABSL_INTERNAL_ATTRIBUTE_CAPTURED_BY(this)),                          \

      V VQual v ABSL_INTERNAL_IF_##VValue(ABSL_INTERNAL_ATTRIBUTE_CAPTURED_BY( \

          this))) ABSL_ATTRIBUTE_LIFETIME_BOUND {                              \

    return ABSL_INTERNAL_IF_##KValue##_OR_##VValue(                            \

        (this->template Func<K, V, 0>), Callee)(                               \

        std::forward<decltype(k)>(k), std::forward<decltype(v)>(v)) Tail;      \

  }                                                                            \

  static_assert(true, "This is to force a semicolon.")

  ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, const&, const&,

                  false, false, ABSL_INTERNAL_SINGLE_ARG());

  ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, const&, const&,

                  false, true, ABSL_INTERNAL_SINGLE_ARG());

  ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, const&, const&, true,

                  false, ABSL_INTERNAL_SINGLE_ARG());

  ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, const&, const&, true,

                  true, ABSL_INTERNAL_SINGLE_ARG());

  ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, const&, &&, false,

                  false, ABSL_INTERNAL_SINGLE_ARG());

  ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, const&, &&, false,

                  true, ABSL_INTERNAL_SINGLE_ARG());

  ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, const&, &&, true,

                  false, ABSL_INTERNAL_SINGLE_ARG());

  ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, const&, &&, true,

                  true, ABSL_INTERNAL_SINGLE_ARG());

  ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, &&, const&, false,

                  false, ABSL_INTERNAL_SINGLE_ARG());

  ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, &&, const&, false,

                  true, ABSL_INTERNAL_SINGLE_ARG());

  ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, &&, const&, true,

                  false, ABSL_INTERNAL_SINGLE_ARG());

  ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, &&, const&, true,

                  true, ABSL_INTERNAL_SINGLE_ARG());

  ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, &&, &&, false, false,

                  ABSL_INTERNAL_SINGLE_ARG());

  ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, &&, &&, false, true,

                  ABSL_INTERNAL_SINGLE_ARG());

  ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, &&, &&, true, false,

                  ABSL_INTERNAL_SINGLE_ARG());

  ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, &&, &&, true, true,

                  ABSL_INTERNAL_SINGLE_ARG());

  ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, const&, const&,

                  false, false, .first, const_iterator ABSL_INTERNAL_COMMA);

  ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, const&, const&,

                  false, true, .first, const_iterator ABSL_INTERNAL_COMMA);

  ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, const&, const&, true,

                  false, .first, const_iterator ABSL_INTERNAL_COMMA);

  ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, const&, const&, true,

                  true, .first, const_iterator ABSL_INTERNAL_COMMA);

  ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, const&, &&, false,

                  false, .first, const_iterator ABSL_INTERNAL_COMMA);

  ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, const&, &&, false,

                  true, .first, const_iterator ABSL_INTERNAL_COMMA);

  ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, const&, &&, true,

                  false, .first, const_iterator ABSL_INTERNAL_COMMA);

  ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, const&, &&, true,

                  true, .first, const_iterator ABSL_INTERNAL_COMMA);

  ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, &&, const&, false,

                  false, .first, const_iterator ABSL_INTERNAL_COMMA);

  ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, &&, const&, false,

                  true, .first, const_iterator ABSL_INTERNAL_COMMA);

  ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, &&, const&, true,

                  false, .first, const_iterator ABSL_INTERNAL_COMMA);

  ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, &&, const&, true,

                  true, .first, const_iterator ABSL_INTERNAL_COMMA);

  ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, &&, &&, false, false,

                  .first, const_iterator ABSL_INTERNAL_COMMA);

  ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, &&, &&, false, true,

                  .first, const_iterator ABSL_INTERNAL_COMMA);

  ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, &&, &&, true, false,

                  .first, const_iterator ABSL_INTERNAL_COMMA);

  ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, &&, &&, true, true,

                  .first, const_iterator ABSL_INTERNAL_COMMA);

#undef ABSL_INTERNAL_X

  // 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, int = EnableIf<LifetimeBoundK<K, false, K*>>(),

            class... Args,

            typename std::enable_if<

                !std::is_convertible<K, const_iterator>::value, int>::type = 0>

  std::pair<iterator, bool> try_emplace(key_arg<K>&& k, Args&&... args)

      ABSL_ATTRIBUTE_LIFETIME_BOUND {

    return try_emplace_impl(std::forward<key_arg<K>>(k),

                            std::forward<Args>(args)...);

  }

  template <class K = key_type, class... Args,

            EnableIf<LifetimeBoundK<K, true, K*>> = 0,

            typename std::enable_if<

                !std::is_convertible<K, const_iterator>::value, int>::type = 0>

  std::pair<iterator, bool> try_emplace(

      key_arg<K>&& k ABSL_INTERNAL_ATTRIBUTE_CAPTURED_BY(this),

      Args&&... args) ABSL_ATTRIBUTE_LIFETIME_BOUND {

    return this->template try_emplace<K, 0>(std::forward<key_arg<K>>(k),

                                            std::forward<Args>(args)...);

  }

  template <class K = key_type, int = EnableIf<LifetimeBoundK<K, false>>(),

            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,

            EnableIf<LifetimeBoundK<K, true>> = 0,

            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 ABSL_INTERNAL_ATTRIBUTE_CAPTURED_BY(this),

      Args&&... args) ABSL_ATTRIBUTE_LIFETIME_BOUND {

    return this->template try_emplace<K, 0>(k, std::forward<Args>(args)...);

  }

  template <class K = key_type, int = EnableIf<LifetimeBoundK<K, false, K*>>(),

            class... Args>

  iterator try_emplace(const_iterator, key_arg<K>&& k,

                       Args&&... args) ABSL_ATTRIBUTE_LIFETIME_BOUND {

    return try_emplace(std::forward<key_arg<K>>(k), std::forward<Args>(args)...)

        .first;

  }

  template <class K = key_type, class... Args,

            EnableIf<LifetimeBoundK<K, true, K*>> = 0>

  iterator try_emplace(const_iterator hint,

                       key_arg<K>&& k ABSL_INTERNAL_ATTRIBUTE_CAPTURED_BY(this),

                       Args&&... args) ABSL_ATTRIBUTE_LIFETIME_BOUND {

    return this->template try_emplace<K, 0>(hint, std::forward<key_arg<K>>(k),

                                            std::forward<Args>(args)...);

  }

  template <class K = key_type, int = EnableIf<LifetimeBoundK<K, false>>(),

            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... Args,

            EnableIf<LifetimeBoundK<K, true>> = 0>

  iterator try_emplace(const_iterator hint,

                       const key_arg<K>& k

                           ABSL_INTERNAL_ATTRIBUTE_CAPTURED_BY(this),

                       Args&&... args) ABSL_ATTRIBUTE_LIFETIME_BOUND {

    return this->template try_emplace<K, 0>(hint, k,

                                            std::forward<Args>(args)...);

  }

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

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

      ThrowStdOutOfRange("absl::container_internal::raw_hash_map<>::at");

    }

    return Policy::value(&*it);

  }

  template <class K = key_type, class P = Policy,

            int = EnableIf<LifetimeBoundK<K, false, K*>>()>

  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<key_arg<K>>(key)).first));

  }

  template <class K = key_type, class P = Policy, int&...,

            EnableIf<LifetimeBoundK<K, true, K*>> = 0>

  MappedReference<P> operator[](

      key_arg<K>&& key ABSL_INTERNAL_ATTRIBUTE_CAPTURED_BY(this))

      ABSL_ATTRIBUTE_LIFETIME_BOUND {

    return this->template operator[]<K, P, 0>(std::forward<key_arg<K>>(key));

  }

  template <class K = key_type, class P = Policy,

            int = EnableIf<LifetimeBoundK<K, false>>()>

  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));

  }

  template <class K = key_type, class P = Policy, int&...,

            EnableIf<LifetimeBoundK<K, true>> = 0>

  MappedReference<P> operator[](

      const key_arg<K>& key ABSL_INTERNAL_ATTRIBUTE_CAPTURED_BY(this))

      ABSL_ATTRIBUTE_LIFETIME_BOUND {

    return this->template operator[]<K, P, 0>(key);

  }

 private:

  static_assert(

      std::is_same_v<

          typename InstantiateRawHashMap<Policy, Hash, Eq, Alloc>::type,

          raw_hash_map>,

      "Redundant template parameters were passed. Use InstantiateRawHashMap<> "

      "instead");

  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_