DenseMap.h File Reference

This file defines the DenseMap class. More...

#include "llvm/ADT/ADL.h"
#include "llvm/ADT/DenseMapInfo.h"
#include "llvm/ADT/EpochTracker.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/STLForwardCompat.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>

Go to the source code of this file.

Classes
struct	llvm::detail::DenseMapPair< KeyT, ValueT >
struct	llvm::densemap::detail::StorageRep< BucketT >
class	llvm::densemap::detail::DenseMapStorage< BucketT >
class	llvm::densemap::detail::SmallDenseMapStorage< BucketT, InlineBuckets >
class	llvm::DenseMapIterator< KeyT, ValueT, KeyInfoT, Bucket, IsConst >
class	llvm::DenseMapBase< StorageT, KeyT, ValueT, KeyInfoT, BucketT >
class	llvm::DenseMap< KeyT, ValueT, KeyInfoT, BucketT >
class	llvm::SmallDenseMap< KeyT, ValueT, InlineBuckets, KeyInfoT, BucketT >

Namespaces
namespace	llvm
	This is an optimization pass for GlobalISel generic memory operations.
namespace	llvm::detail
	A self-contained host- and target-independent arbitrary-precision floating-point software implementation.
namespace	llvm::densemap
namespace	llvm::densemap::detail

Typedefs
using	llvm::densemap::detail::UsedT = uint32_t
using	llvm::densemap::detail::BucketHasher = unsigned (*)(const void *Key)
	Hashes the key, at offset 0 in a bucket.

Functions
template<typename BucketT>
void	llvm::densemap::detail::relocateBucket (BucketT *Dst, BucketT *Src)
constexpr size_t	llvm::densemap::detail::usedWords (size_t N)
bool	llvm::densemap::detail::used (const UsedT *U, size_t I)
void	llvm::densemap::detail::setUsed (UsedT *U, size_t I)
void	llvm::densemap::detail::unsetUsed (UsedT *U, size_t I)
void	llvm::densemap::detail::clearUsed (UsedT *U, unsigned Num)
template<typename Fn>
LLVM_ATTRIBUTE_ALWAYS_INLINE void	llvm::densemap::detail::forEachUsed (const UsedT *U, unsigned N, Fn Func)
template<typename BucketT>
constexpr size_t	llvm::densemap::detail::allocAlign ()
size_t	llvm::densemap::detail::allocBytes (size_t BucketSize, unsigned Num)
template<typename BucketT>
size_t	llvm::densemap::detail::allocBytes (unsigned Num)
UsedT *	llvm::densemap::detail::usedFor (void *Buckets, size_t BucketSize, unsigned Num)
template<typename KeyT, typename KeyInfoT>
constexpr BucketHasher	llvm::densemap::detail::hasherFor ()
LLVM_ABI void	llvm::densemap::detail::rehashRelocatable (void *Dst, UsedT *DstUsed, unsigned DstNumBuckets, const void *Src, const UsedT *SrcUsed, unsigned SrcNumBuckets, size_t BucketSize, BucketHasher Hasher)
	Rehash the live buckets of Src into the empty Dst, which must have room for all of them.
LLVM_ABI void *	llvm::densemap::detail::growRelocatable (void *OldBuckets, const UsedT *OldUsed, unsigned OldNumBuckets, unsigned NewNumBuckets, size_t BucketSize, size_t Align, BucketHasher Hasher, bool FreeOld)
	Allocate a table of NewNumBuckets buckets and rehash the OldNumBuckets buckets at OldBuckets into it, freeing them if FreeOld.
template<typename Storage1T, typename Storage2T, typename KeyT, typename ValueT, typename KeyInfoT, typename BucketT>
bool	llvm::operator== (const DenseMapBase< Storage1T, KeyT, ValueT, KeyInfoT, BucketT > &LHS, const DenseMapBase< Storage2T, KeyT, ValueT, KeyInfoT, BucketT > &RHS)
	Equality comparison for DenseMap.
template<typename Storage1T, typename Storage2T, typename KeyT, typename ValueT, typename KeyInfoT, typename BucketT>
bool	llvm::operator!= (const DenseMapBase< Storage1T, KeyT, ValueT, KeyInfoT, BucketT > &LHS, const DenseMapBase< Storage2T, KeyT, ValueT, KeyInfoT, BucketT > &RHS)
	Inequality comparison for DenseMap.
template<typename KeyT, typename ValueT, typename KeyInfoT>
size_t	llvm::capacity_in_bytes (const DenseMap< KeyT, ValueT, KeyInfoT > &X)

Variables
template<typename BucketT>
constexpr bool	llvm::densemap::detail::isRelocatableBucket
template<typename KeyT, typename KeyInfoT, typename = void>
constexpr bool	llvm::densemap::detail::hashesPointerValue = false
template<typename T>
constexpr bool	llvm::densemap::detail::hashesPointerValue< T *, DenseMapInfo< T * >, std::enable_if_t< std::is_same_v< typename DenseMapInfo< T * >::PointerValueHash, DenseMapInfo< T * > > > >

Detailed Description

This file defines the DenseMap class.

The hash table is linear-probing open addressing with tombstone-free deletion (Knuth TAOCP 6.4 Algorithm R), power-of-two capacity, and a 0.75 maximum load factor. No sentinel key. Occupancy is stored in a packed 1-bit-per-bucket "used" array.

SmallDenseMap adds an inline small buffer optimization.

Definition in file DenseMap.h.