chromium/third_party/blink/renderer/platform/wtf/hash_map.h

/*
 * Copyright (C) 2005, 2006, 2007, 2008, 2011 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_MAP_H_
#define THIRD_PARTY_BLINK_RENDERER_PLATFORM_WTF_HASH_MAP_H_

#include <initializer_list>

#include "base/numerics/safe_conversions.h"
#include "third_party/blink/renderer/platform/wtf/allocator/allocator.h"
#include "third_party/blink/renderer/platform/wtf/allocator/partition_allocator.h"
#include "third_party/blink/renderer/platform/wtf/atomic_operations.h"
#include "third_party/blink/renderer/platform/wtf/construct_traits.h"
#include "third_party/blink/renderer/platform/wtf/hash_table.h"
#include "third_party/blink/renderer/platform/wtf/key_value_pair.h"
#include "third_party/blink/renderer/platform/wtf/type_traits.h"
#include "third_party/blink/renderer/platform/wtf/wtf_size_t.h"

namespace WTF {

template <typename KeyTraits, typename MappedTraits>
struct HashMapValueTraits;

template <typename Value, typename Traits, typename Allocator>
class HashCountedSet;

struct KeyValuePairExtractor { … };

// Note: empty or deleted key values are not allowed, using them may lead to
// undefined behavior. For pointer keys this means that null pointers are not
// allowed; for integer keys 0 or -1 can't be used as a key. You can change
// the restriction with a custom key hash traits. See hash_traits.h for how to
// define hash traits.
// Commonly used key types define their key hash traits separately from the
// class itself, so e.g if you want a `WTF::HashMap<WTF::String, ...>` you must
// include `string_hash.h`.
template <typename KeyArg,
          typename MappedArg,
          typename KeyTraitsArg = HashTraits<KeyArg>,
          typename MappedTraitsArg = HashTraits<MappedArg>,
          typename Allocator = PartitionAllocator>
class HashMap { … };

template <typename KeyArg,
          typename MappedArg,
          typename KeyTraitsArg,
          typename MappedTraitsArg,
          typename Allocator>
class HashMap<KeyArg, MappedArg, KeyTraitsArg, MappedTraitsArg, Allocator>::
    HashMapKeysProxy : private HashMap<KeyArg,
                                       MappedArg,
                                       KeyTraitsArg,
                                       MappedTraitsArg,
                                       Allocator> { … };

template <typename KeyArg,
          typename MappedArg,
          typename KeyTraitsArg,
          typename MappedTraitsArg,
          typename Allocator>
class HashMap<KeyArg, MappedArg, KeyTraitsArg, MappedTraitsArg, Allocator>::
    HashMapValuesProxy : private HashMap<KeyArg,
                                         MappedArg,
                                         KeyTraitsArg,
                                         MappedTraitsArg,
                                         Allocator> { … };

template <typename KeyTraits, typename ValueTraits>
struct HashMapValueTraits : KeyValuePairHashTraits<KeyTraits, ValueTraits> { … };

template <typename KeyTraits, typename ValueTraits>
struct HashMapTranslator { … };

template <typename KeyArg,
          typename MappedArg,
          typename KeyTraitsArg,
          typename MappedTraitsArg,
          typename Allocator>
HashMap<KeyArg, MappedArg, KeyTraitsArg, MappedTraitsArg, Allocator>::HashMap(
    std::initializer_list<ValueType> elements) { … }

template <typename T, typename U, typename V, typename W, typename X>
auto HashMap<T, U, V, W, X>::operator=(
    std::initializer_list<ValueType> elements) -> HashMap& { … }

template <typename T, typename U, typename V, typename W, typename X>
inline unsigned HashMap<T, U, V, W, X>::size() const { … }

template <typename T, typename U, typename V, typename W, typename X>
inline unsigned HashMap<T, U, V, W, X>::Capacity() const { … }

template <typename T, typename U, typename V, typename W, typename X>
inline bool HashMap<T, U, V, W, X>::empty() const { … }

template <typename T, typename U, typename V, typename W, typename X>
inline typename HashMap<T, U, V, W, X>::iterator
HashMap<T, U, V, W, X>::begin() { … }

template <typename T, typename U, typename V, typename W, typename X>
inline typename HashMap<T, U, V, W, X>::iterator HashMap<T, U, V, W, X>::end() { … }

template <typename T, typename U, typename V, typename W, typename X>
inline typename HashMap<T, U, V, W, X>::const_iterator
HashMap<T, U, V, W, X>::begin() const { … }

template <typename T, typename U, typename V, typename W, typename X>
inline typename HashMap<T, U, V, W, X>::const_iterator
HashMap<T, U, V, W, X>::end() const { … }

template <typename T, typename U, typename V, typename W, typename X>
inline typename HashMap<T, U, V, W, X>::iterator HashMap<T, U, V, W, X>::find(
    KeyPeekInType key) { … }

template <typename T, typename U, typename V, typename W, typename X>
inline typename HashMap<T, U, V, W, X>::const_iterator
HashMap<T, U, V, W, X>::find(KeyPeekInType key) const { … }

template <typename T, typename U, typename V, typename W, typename X>
inline bool HashMap<T, U, V, W, X>::Contains(KeyPeekInType key) const { … }

template <typename T, typename U, typename V, typename W, typename X>
template <typename HashTranslator, typename TYPE>
inline typename HashMap<T, U, V, W, X>::iterator HashMap<T, U, V, W, X>::Find(
    const TYPE& value) { … }

template <typename T, typename U, typename V, typename W, typename X>
template <typename HashTranslator, typename TYPE>
inline typename HashMap<T, U, V, W, X>::const_iterator
HashMap<T, U, V, W, X>::Find(const TYPE& value) const { … }

template <typename T, typename U, typename V, typename W, typename X>
template <typename HashTranslator, typename TYPE>
inline bool HashMap<T, U, V, W, X>::Contains(const TYPE& value) const { … }

template <typename T, typename U, typename V, typename W, typename X>
template <typename IncomingKeyType, typename IncomingMappedType>
typename HashMap<T, U, V, W, X>::AddResult HashMap<T, U, V, W, X>::InlineAdd(
    IncomingKeyType&& key,
    IncomingMappedType&& mapped) { … }

template <typename T, typename U, typename V, typename W, typename X>
template <typename IncomingKeyType, typename IncomingMappedType>
typename HashMap<T, U, V, W, X>::AddResult HashMap<T, U, V, W, X>::Set(
    IncomingKeyType&& key,
    IncomingMappedType&& mapped) { … }

template <typename T, typename U, typename V, typename W, typename X>
template <typename IncomingKeyType, typename IncomingMappedType>
typename HashMap<T, U, V, W, X>::AddResult HashMap<T, U, V, W, X>::insert(
    IncomingKeyType&& key,
    IncomingMappedType&& mapped) { … }

template <typename T, typename U, typename V, typename W, typename X>
typename HashMap<T, U, V, W, X>::MappedPeekType HashMap<T, U, V, W, X>::at(
    KeyPeekInType key) const { … }

template <typename T, typename U, typename V, typename W, typename X>
inline void HashMap<T, U, V, W, X>::erase(iterator it) { … }

template <typename T, typename U, typename V, typename W, typename X>
inline void HashMap<T, U, V, W, X>::erase(KeyPeekInType key) { … }

template <typename T, typename U, typename V, typename W, typename X>
inline void HashMap<T, U, V, W, X>::clear() { … }

template <typename T, typename U, typename V, typename W, typename X>
auto HashMap<T, U, V, W, X>::Take(KeyPeekInType key) -> MappedType { … }

template <typename T, typename U, typename V, typename W, typename X>
template <typename IncomingKeyType>
inline bool HashMap<T, U, V, W, X>::IsValidKey(const IncomingKeyType& key) { … }

template <typename T, typename U, typename V, typename W, typename X>
bool operator==(const HashMap<T, U, V, W, X>& a,
                const HashMap<T, U, V, W, X>& b) { … }

template <typename T, typename U, typename V, typename W, typename X>
inline bool operator!=(const HashMap<T, U, V, W, X>& a,
                       const HashMap<T, U, V, W, X>& b) { … }

template <typename T,
          typename U,
          typename V,
          typename W,
          typename X,
          typename Z>
inline void CopyKeysToVector(const HashMap<T, U, V, W, X>& collection,
                             Z& vector) { … }

template <typename T,
          typename U,
          typename V,
          typename W,
          typename X,
          typename Z>
inline void CopyValuesToVector(const HashMap<T, U, V, W, X>& collection,
                               Z& vector) { … }

}  // namespace WTF

HashMap;

#endif  // THIRD_PARTY_BLINK_RENDERER_PLATFORM_WTF_HASH_MAP_H_