llvm/compiler-rt/lib/sanitizer_common/sanitizer_dense_map.h

//===- sanitizer_dense_map.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
//
//===----------------------------------------------------------------------===//
//
// This is fork of llvm/ADT/DenseMap.h class with the following changes:
//  * Use mmap to allocate.
//  * No iterators.
//  * Does not shrink.
//
//===----------------------------------------------------------------------===//

#ifndef SANITIZER_DENSE_MAP_H
#define SANITIZER_DENSE_MAP_H

#include "sanitizer_common.h"
#include "sanitizer_dense_map_info.h"
#include "sanitizer_internal_defs.h"
#include "sanitizer_type_traits.h"

namespace __sanitizer {

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

/// 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 = 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 = nullptr;
  unsigned NumEntries = 0;
  unsigned NumTombstones = 0;
  unsigned NumBuckets = 0;

 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) { … }
  constexpr DenseMap() = default;

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

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

  ~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) { … }

 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) { … }

  static void *allocate_buffer(uptr Size) { … }

  static void deallocate_buffer(void *Ptr, uptr Size) { … }
};

}  // namespace __sanitizer

#endif  // SANITIZER_DENSE_MAP_H