llvm/llvm/include/llvm/IR/ValueMap.h

//===- ValueMap.h - Safe map from Values to data ----------------*- 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 file defines the ValueMap class.  ValueMap maps Value* or any subclass
// to an arbitrary other type.  It provides the DenseMap interface but updates
// itself to remain safe when keys are RAUWed or deleted.  By default, when a
// key is RAUWed from V1 to V2, the old mapping V1->target is removed, and a new
// mapping V2->target is added.  If V2 already existed, its old target is
// overwritten.  When a key is deleted, its mapping is removed.
//
// You can override a ValueMap's Config parameter to control exactly what
// happens on RAUW and destruction and to get called back on each event.  It's
// legal to call back into the ValueMap from a Config's callbacks.  Config
// parameters should inherit from ValueMapConfig<KeyT> to get default
// implementations of all the methods ValueMap uses.  See ValueMapConfig for
// documentation of the functions you can override.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_IR_VALUEMAP_H
#define LLVM_IR_VALUEMAP_H

#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DenseMapInfo.h"
#include "llvm/IR/TrackingMDRef.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/Mutex.h"
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <iterator>
#include <mutex>
#include <optional>
#include <type_traits>
#include <utility>

namespace llvm {

template<typename KeyT, typename ValueT, typename Config>
class ValueMapCallbackVH;
template<typename DenseMapT, typename KeyT>
class ValueMapIterator;
template<typename DenseMapT, typename KeyT>
class ValueMapConstIterator;

/// This class defines the default behavior for configurable aspects of
/// ValueMap<>.  User Configs should inherit from this class to be as compatible
/// as possible with future versions of ValueMap.
template<typename KeyT, typename MutexT = sys::Mutex>
struct ValueMapConfig { … };

/// See the file comment.
template<typename KeyT, typename ValueT, typename Config =ValueMapConfig<KeyT>>
class ValueMap {
  friend class ValueMapCallbackVH<KeyT, ValueT, Config>;

  using ValueMapCVH = ValueMapCallbackVH<KeyT, ValueT, Config>;
  using MapT = DenseMap<ValueMapCVH, ValueT, DenseMapInfo<ValueMapCVH>>;
  using MDMapT = DenseMap<const Metadata *, TrackingMDRef>;
  using ExtraData = typename Config::ExtraData;

  MapT Map;
  std::optional<MDMapT> MDMap;
  ExtraData Data;

public:
  using key_type = KeyT;
  using mapped_type = ValueT;
  using value_type = std::pair<KeyT, ValueT>;
  using size_type = unsigned;

  explicit ValueMap(unsigned NumInitBuckets = 64)
      : … { … }
  explicit ValueMap(const ExtraData &Data, unsigned NumInitBuckets = 64)
      : … { … }
  // ValueMap can't be copied nor moved, because the callbacks store pointer to
  // it.
  ValueMap(const ValueMap &) = delete;
  ValueMap(ValueMap &&) = delete;
  ValueMap &operator=(const ValueMap &) = delete;
  ValueMap &operator=(ValueMap &&) = delete;

  bool hasMD() const { … }
  MDMapT &MD() { … }
  std::optional<MDMapT> &getMDMap() { … }

  /// Get the mapped metadata, if it's in the map.
  std::optional<Metadata *> getMappedMD(const Metadata *MD) const { … }

  using iterator = ValueMapIterator<MapT, KeyT>;
  using const_iterator = ValueMapConstIterator<MapT, KeyT>;

  inline iterator begin() { … }
  inline iterator end() { … }
  inline const_iterator begin() const { … }
  inline const_iterator end() const { … }

  bool empty() const { … }
  size_type size() const { … }

  /// Grow the map so that it has at least Size buckets. Does not shrink
  void reserve(size_t Size) { … }

  void clear() { … }

  /// Return 1 if the specified key is in the map, 0 otherwise.
  size_type count(const KeyT &Val) const { … }

  iterator find(const KeyT &Val) { … }
  const_iterator find(const KeyT &Val) const { … }

  /// lookup - Return the entry for the specified key, or a default
  /// constructed value if no such entry exists.
  ValueT lookup(const KeyT &Val) const { … }

  // Inserts key,value pair into the map if the key isn't already in the map.
  // If the key is already in the map, it returns false and doesn't update the
  // value.
  std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) { … }

  std::pair<iterator, bool> insert(std::pair<KeyT, ValueT> &&KV) { … }

  /// insert - Range insertion of pairs.
  template<typename InputIt>
  void insert(InputIt I, InputIt E) { … }

  bool erase(const KeyT &Val) { … }
  void erase(iterator I) { … }

  value_type& FindAndConstruct(const KeyT &Key) { … }

  ValueT &operator[](const KeyT &Key) { … }

  /// isPointerIntoBucketsArray - Return true if the specified pointer points
  /// somewhere into the ValueMap's array of buckets (i.e. either to a key or
  /// value in the ValueMap).
  bool isPointerIntoBucketsArray(const void *Ptr) const { … }

  /// getPointerIntoBucketsArray() - Return an opaque pointer into the buckets
  /// array.  In conjunction with the previous method, this can be used to
  /// determine whether an insertion caused the ValueMap to reallocate.
  const void *getPointerIntoBucketsArray() const { … }

private:
  // Takes a key being looked up in the map and wraps it into a
  // ValueMapCallbackVH, the actual key type of the map.  We use a helper
  // function because ValueMapCVH is constructed with a second parameter.
  ValueMapCVH Wrap(KeyT key) const { … }
};

// This CallbackVH updates its ValueMap when the contained Value changes,
// according to the user's preferences expressed through the Config object.
template <typename KeyT, typename ValueT, typename Config>
class ValueMapCallbackVH final : public CallbackVH { … };

DenseMapInfo<ValueMapCallbackVH<KeyT, ValueT, Config>>;

template <typename DenseMapT, typename KeyT> class ValueMapIterator { … };

template <typename DenseMapT, typename KeyT> class ValueMapConstIterator { … };

} // end namespace llvm

#endif // LLVM_IR_VALUEMAP_H