llvm/llvm/include/llvm/ADT/DenseMap.h

//===- llvm/ADT/DenseMap.h - Dense probed hash table ------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
///
/// \file
/// This file defines the DenseMap class.
///
//===----------------------------------------------------------------------===//

#ifndef LLVM_ADT_DENSEMAP_H
#define LLVM_ADT_DENSEMAP_H

#include "llvm/ADT/DenseMapInfo.h"
#include "llvm/ADT/EpochTracker.h"
#include "llvm/Support/AlignOf.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/MemAlloc.h"
#include "llvm/Support/ReverseIteration.h"
#include "llvm/Support/type_traits.h"
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstring>
#include <initializer_list>
#include <iterator>
#include <new>
#include <type_traits>
#include <utility>

namespace llvm {

namespace detail {

// We extend a pair to allow users to override the bucket type with their own
// implementation without requiring two members.
template <typename KeyT, typename ValueT>
struct DenseMapPair : public std::pair<KeyT, ValueT> { … };

} // end namespace detail

template <typename KeyT, typename ValueT,
          typename KeyInfoT = DenseMapInfo<KeyT>,
          typename Bucket = llvm::detail::DenseMapPair<KeyT, ValueT>,
          bool IsConst = false>
class DenseMapIterator;

template <typename DerivedT, typename KeyT, typename ValueT, typename KeyInfoT,
          typename BucketT>
class DenseMapBase : public DebugEpochBase { … };

/// Equality comparison for DenseMap.
///
/// Iterates over elements of LHS confirming that each (key, value) pair in LHS
/// is also in RHS, and that no additional pairs are in RHS.
/// Equivalent to N calls to RHS.find and N value comparisons. Amortized
/// complexity is linear, worst case is O(N^2) (if every hash collides).
template <typename DerivedT, typename KeyT, typename ValueT, typename KeyInfoT,
          typename BucketT>
bool operator==(
    const DenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT> &LHS,
    const DenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT> &RHS) { … }

/// Inequality comparison for DenseMap.
///
/// Equivalent to !(LHS == RHS). See operator== for performance notes.
template <typename DerivedT, typename KeyT, typename ValueT, typename KeyInfoT,
          typename BucketT>
bool operator!=(
    const DenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT> &LHS,
    const DenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT> &RHS) { … }

template <typename KeyT, typename ValueT,
          typename KeyInfoT = DenseMapInfo<KeyT>,
          typename BucketT = llvm::detail::DenseMapPair<KeyT, ValueT>>
class DenseMap : public DenseMapBase<DenseMap<KeyT, ValueT, KeyInfoT, BucketT>,
                                     KeyT, ValueT, KeyInfoT, BucketT> {
  friend class DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT, BucketT>;

  // Lift some types from the dependent base class into this class for
  // simplicity of referring to them.
  using BaseT = DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT, BucketT>;

  BucketT *Buckets;
  unsigned NumEntries;
  unsigned NumTombstones;
  unsigned NumBuckets;

public:
  /// Create a DenseMap with an optional \p InitialReserve that guarantee that
  /// this number of elements can be inserted in the map without grow()
  explicit DenseMap(unsigned InitialReserve = 0) { … }

  DenseMap(const DenseMap &other) : … { … }

  DenseMap(DenseMap &&other) : … { … }

  template <typename InputIt> DenseMap(const InputIt &I, const InputIt &E) { … }

  DenseMap(std::initializer_list<typename BaseT::value_type> Vals) { … }

  ~DenseMap() { … }

  void swap(DenseMap &RHS) { … }

  DenseMap &operator=(const DenseMap &other) { … }

  DenseMap &operator=(DenseMap &&other) { … }

  void copyFrom(const DenseMap &other) { … }

  void init(unsigned InitNumEntries) { … }

  void grow(unsigned AtLeast) { … }

  void shrink_and_clear() { … }

private:
  unsigned getNumEntries() const { … }

  void setNumEntries(unsigned Num) { … }

  unsigned getNumTombstones() const { … }

  void setNumTombstones(unsigned Num) { … }

  BucketT *getBuckets() const { … }

  unsigned getNumBuckets() const { … }

  bool allocateBuckets(unsigned Num) { … }
};

template <typename KeyT, typename ValueT, unsigned InlineBuckets = 4,
          typename KeyInfoT = DenseMapInfo<KeyT>,
          typename BucketT = llvm::detail::DenseMapPair<KeyT, ValueT>>
class SmallDenseMap
    : public DenseMapBase<
          SmallDenseMap<KeyT, ValueT, InlineBuckets, KeyInfoT, BucketT>, KeyT,
          ValueT, KeyInfoT, BucketT> {
  friend class DenseMapBase<SmallDenseMap, KeyT, ValueT, KeyInfoT, BucketT>;

  // Lift some types from the dependent base class into this class for
  // simplicity of referring to them.
  using BaseT = DenseMapBase<SmallDenseMap, KeyT, ValueT, KeyInfoT, BucketT>;

  static_assert(isPowerOf2_64(InlineBuckets),
                "InlineBuckets must be a power of 2.");

  unsigned Small : 1;
  unsigned NumEntries : 31;
  unsigned NumTombstones;

  struct LargeRep {
    BucketT *Buckets;
    unsigned NumBuckets;
  };

  /// A "union" of an inline bucket array and the struct representing
  /// a large bucket. This union will be discriminated by the 'Small' bit.
  AlignedCharArrayUnion<BucketT[InlineBuckets], LargeRep> storage;

public:
  explicit SmallDenseMap(unsigned NumInitBuckets = 0) { … }

  SmallDenseMap(const SmallDenseMap &other) : … { … }

  SmallDenseMap(SmallDenseMap &&other) : … { … }

  template <typename InputIt>
  SmallDenseMap(const InputIt &I, const InputIt &E) { … }

  SmallDenseMap(std::initializer_list<typename BaseT::value_type> Vals)
      : … { … }

  ~SmallDenseMap() { … }

  void swap(SmallDenseMap &RHS) { … }

  SmallDenseMap &operator=(const SmallDenseMap &other) { … }

  SmallDenseMap &operator=(SmallDenseMap &&other) { … }

  void copyFrom(const SmallDenseMap &other) { … }

  void init(unsigned InitBuckets) { … }

  void grow(unsigned AtLeast) { … }

  void shrink_and_clear() { … }

private:
  unsigned getNumEntries() const { … }

  void setNumEntries(unsigned Num) { … }

  unsigned getNumTombstones() const { … }

  void setNumTombstones(unsigned Num) { … }

  const BucketT *getInlineBuckets() const { … }

  BucketT *getInlineBuckets() { … }

  const LargeRep *getLargeRep() const { … }

  LargeRep *getLargeRep() { … }

  const BucketT *getBuckets() const { … }

  BucketT *getBuckets() { … }

  unsigned getNumBuckets() const { … }

  void deallocateBuckets() { … }

  LargeRep allocateBuckets(unsigned Num) { … }
};

template <typename KeyT, typename ValueT, typename KeyInfoT, typename Bucket,
          bool IsConst>
class DenseMapIterator : DebugEpochBase::HandleBase { … };

template <typename KeyT, typename ValueT, typename KeyInfoT>
inline size_t capacity_in_bytes(const DenseMap<KeyT, ValueT, KeyInfoT> &X) { … }

} // end namespace llvm

#endif // LLVM_ADT_DENSEMAP_H