hash_traits.h | Explore in Territory

/*
 * Copyright (C) 2005, 2006, 2007, 2008, 2011, 2012 Apple Inc. All rights
 * reserved.
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Library General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public License
 * along with this library; see the file COPYING.LIB.  If not, write to
 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
 * Boston, MA 02110-1301, USA.
 *
 */

#ifndef THIRD_PARTY_BLINK_RENDERER_PLATFORM_WTF_HASH_TRAITS_H_
#define THIRD_PARTY_BLINK_RENDERER_PLATFORM_WTF_HASH_TRAITS_H_

#include <string.h>

#include <concepts>
#include <limits>
#include <memory>
#include <type_traits>
#include <utility>

#include "third_party/blink/renderer/platform/wtf/allocator/allocator.h"
#include "third_party/blink/renderer/platform/wtf/hash_functions.h"
#include "third_party/blink/renderer/platform/wtf/hash_table_deleted_value_type.h"
#include "third_party/blink/renderer/platform/wtf/std_lib_extras.h"
#include "third_party/blink/renderer/platform/wtf/type_traits.h"

namespace WTF {

// A hash traits type is required for a type when the type is used as the key
// or value of a HashTable-based classes. See documentation in
// GenericHashTraitsBase for the HashTraits API.
//
// A hash traits type can be defined as
// - a specialization of the HashTraits template, which will be automatically
//   used, or
// - a standalone hash traits type, which should be passed as the *Traits
//   template parameters of HashTable-based classes.
// The former is preferred if the hash traits defines the default hash behavior
// of the type. The latter is suitable when a type has multiple hash behaviors,
// e.g. CaseFoldingHashTraits defines an alternative hash behavior of strings.
//
// This file contains definitions of hash traits for integral types,
// floating-point types, enums, raw and smart pointers, std::pair, etc.
// These types can be used as hash key or value directly.
//
// This file also contains hash traits types that can be used as the base class
// of hash traits of other types.
//
// A simple hash traits type for a key type can be like:
//   template <>
//   HashTraits<KeyType> : GenericHashTraits<KeyType> {
//     static unsigned GetHash(const KeyType& key) { ...; }
//     static KeyType EmptyValue() { ...; }
//     static KeyType DeletedValue() { ...; }
//   };
//
// A hash traits type for a value type can be even simpler. See documentation
// in GenericHashTraitsBase for which functions/flags are for key types only
// (i.e. not needed for a value type).
//
template <typename T>
struct HashTraits;

class String;

namespace internal {

template <typename T>
struct GenericHashTraitsBase { … };

template <typename T, auto empty_value, auto deleted_value>
struct IntOrEnumHashTraits : internal::GenericHashTraitsBase<T> { … };

}  // namespace internal

// Default integer traits disallow both 0 and -1 as keys (max value instead of
// -1 for unsigned).
template <typename T, T empty_value = 0, T deleted_value = static_cast<T>(-1)>
struct IntHashTraits
    : internal::IntOrEnumHashTraits<T, empty_value, deleted_value> { … };

// Default traits for an enum type.  0 is very popular, and -1 is also popular.
// So we use -128 and -127.
template <typename T>
struct EnumHashTraits : internal::IntOrEnumHashTraits<T, -128, -127> { … };

template <typename T>
struct GenericHashTraits : internal::GenericHashTraitsBase<T> { … };

GenericHashTraits<T>;

GenericHashTraits<T>;

GenericHashTraits<T>;

// Default integral traits disallow both 0 and max as keys -- use these traits
// to allow zero and disallow max - 1.
template <typename T>
struct IntWithZeroKeyHashTraits
    : IntHashTraits<T,
                    std::numeric_limits<T>::max(),
                    std::numeric_limits<T>::max() - 1> { … };

// This hash traits can be used in cases where the key is already a good hash.
struct AlreadyHashedTraits : GenericHashTraits<unsigned> { … };
struct AlreadyHashedWithZeroKeyTraits : IntWithZeroKeyHashTraits<unsigned> { … };

GenericHashTraits<P *>;

GenericHashTraits<scoped_refptr<P>>;

GenericHashTraits<std::unique_ptr<T>>;

// HashTraits<T> is defined as GenericHashTraits<T> by default.
// The separation of HashTraits<T> and GenericHashTraits<T> is to allow
// a specialized HashTraits<T> to inherit GenericHashTraits<T>.
template <typename T>
struct HashTraits : GenericHashTraits<T> { … };

// This hash traits type requires the following methods in class T, unless
// the corresponding hash traits method is overridden:
//   // Computes the hash code, for GetHash().
//   unsigned GetHash() const;
//   // Creates the deleted value, for ConstructDeletedValue().
//   T(HashTableDeletedValueType);
//   // Checks if `this` is a deleted value, for IsDeletedValue().
//   bool IsHashTableDeletedValue() const;
// Also requires T() and operator== if EmptyValue() and Equal() are not
// overridden, respectively, which is the same as GenericHashTraits<T>.
template <typename T>
struct SimpleClassHashTraits : GenericHashTraits<T> { … };

// Defined in string_hash.h.
template <>
struct HashTraits<String>;

namespace internal {

template <typename Traits, typename Enabled = void>
struct HashTraitsEmptyValueChecker { … };
HashTraitsEmptyValueChecker<Traits, std::enable_if_t<std::is_same_v<decltype(Traits::IsEmptyValue(std::declval<typename Traits::TraitType>())), bool>>>;

template <typename Traits, typename Enabled = void>
struct HashTraitsDeletedValueHelper { … };
HashTraitsDeletedValueHelper<Traits, std::enable_if_t<std::is_same_v<decltype(Traits::IsDeletedValue(std::declval<typename Traits::TraitType>())), bool>>>;

}  // namespace internal

// This function selects either the EmptyValue() function or the IsEmptyValue()
// function to check for empty values.
template <typename Traits, typename T>
inline bool IsHashTraitsEmptyValue(const T& value) { … }

// This function selects either the DeletedValue() function or the
// IsDeletedValue() function to check for deleted values.
template <typename Traits, typename T>
inline bool IsHashTraitsDeletedValue(const T& value) { … }

// This function selects either the DeletedValue() function or the
// ConstructDeletedValue() function to construct a deleted value.
template <typename Traits, typename T>
inline void ConstructHashTraitsDeletedValue(T& slot) { … }

template <typename Traits, typename T>
inline bool IsHashTraitsEmptyOrDeletedValue(const T& value) { … }

// A HashTraits type for T to delegate all HashTraits API to a field.
template <typename T,
          auto field,
          typename FieldTraits = HashTraits<
              std::remove_reference_t<decltype(std::declval<T>().*field)>>>
struct OneFieldHashTraits : GenericHashTraits<T> {
  using TraitType = T;
  static unsigned GetHash(const T& p) { … }
  static bool Equal(const T& a, const T& b) { … }
  static constexpr bool kSafeToCompareToEmptyOrDeleted =
      FieldTraits::kSafeToCompareToEmptyOrDeleted;

  static constexpr bool kEmptyValueIsZero = FieldTraits::kEmptyValueIsZero;
  static T EmptyValue() { … }

  static bool IsEmptyValue(const T& value) { … }

  static void ConstructDeletedValue(T& slot) { … }
  static bool IsDeletedValue(const T& value) { … }

  static constexpr unsigned kMinimumTableSize = FieldTraits::kMinimumTableSize;

  template <typename U = void>
  struct NeedsToForbidGCOnMove {
    static const bool value =
        FieldTraits::template NeedsToForbidGCOnMove<>::value;
  };
};

// A HashTraits type for T to delegate all HashTraits API to two fields.
template <
    typename T,
    auto first_field,
    auto second_field,
    typename FirstTraits = HashTraits<
        std::remove_reference_t<decltype(std::declval<T>().*first_field)>>,
    typename SecondTraits = HashTraits<
        std::remove_reference_t<decltype(std::declval<T>().*second_field)>>>
struct TwoFieldsHashTraits : OneFieldHashTraits<T, first_field, FirstTraits> {
  using TraitType = T;
  static unsigned GetHash(const T& p) { … }
  static bool Equal(const T& a, const T& b) { … }
  static constexpr bool kSafeToCompareToEmptyOrDeleted =
      FirstTraits::kSafeToCompareToEmptyOrDeleted &&
      SecondTraits::kSafeToCompareToEmptyOrDeleted;

  static constexpr bool kEmptyValueIsZero =
      FirstTraits::kEmptyValueIsZero && SecondTraits::kEmptyValueIsZero;
  static T EmptyValue() { … }

  static bool IsEmptyValue(const T& value) { … }

  // ConstructDeletedValue(), IsDeletedValue(), kMinimumTableSize delegate to
  // the first field, inherited from OneFieldHashTraits.

  template <typename U = void>
  struct NeedsToForbidGCOnMove {
    static const bool value =
        FirstTraits::template NeedsToForbidGCOnMove<>::value ||
        SecondTraits::template NeedsToForbidGCOnMove<>::value;
  };
};

template <typename FirstTraitsArg,
          typename SecondTraitsArg,
          typename P = std::pair<typename FirstTraitsArg::TraitType,
                                 typename SecondTraitsArg::TraitType>>
struct PairHashTraits : TwoFieldsHashTraits<P,
                                            &P::first,
                                            &P::second,
                                            FirstTraitsArg,
                                            SecondTraitsArg> {
  using TraitType = P;
  using FirstTraits = FirstTraitsArg;
  using SecondTraits = SecondTraitsArg;
};

HashTraits<std::pair<First, Second>>;

// Shortcut of HashTraits<T>::GetHash(), which can deduct T automatically.
template <typename T>
unsigned GetHash(const T& key) { … }

}  // namespace WTF

AlreadyHashedTraits;
AlreadyHashedWithZeroKeyTraits;
EnumHashTraits;
GenericHashTraits;
HashTraits;
IntHashTraits;
IntWithZeroKeyHashTraits;
OneFieldHashTraits;
PairHashTraits;
SimpleClassHashTraits;
TwoFieldsHashTraits;

#endif  // THIRD_PARTY_BLINK_RENDERER_PLATFORM_WTF_HASH_TRAITS_H_
chromium/third_party/blink/renderer/platform/wtf/hash_traits.h
