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/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 <cstdint>
#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 >
class	llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >
struct	llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::ExactBucketCount
struct	llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::Rep
class	llvm::DenseMap< KeyT, ValueT, KeyInfoT, BucketT >
class	llvm::SmallDenseMap< KeyT, ValueT, InlineBuckets, KeyInfoT, BucketT >
class	llvm::DenseMapIterator< KeyT, ValueT, KeyInfoT, Bucket, IsConst >

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

Functions
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)
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 ()
template<typename BucketT>
size_t	llvm::densemap::detail::allocBytes (unsigned Num)
template<typename DerivedT, typename KeyT, typename ValueT, typename KeyInfoT, typename BucketT>
bool	llvm::operator== (const DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT > &LHS, const DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT > &RHS)
	Equality comparison for DenseMap.
template<typename DerivedT, typename KeyT, typename ValueT, typename KeyInfoT, typename BucketT>
bool	llvm::operator!= (const DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT > &LHS, const DenseMapBase< DerivedT, 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)

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.