proxygen: folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn

#include <AtomicHashArray.h>

Inheritance diagram for folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >:

Classes
struct	ahm_iterator

struct	SimpleRetT

Public Types
typedef KeyT	key_type

typedef ValueT	mapped_type

typedef std::pair< const KeyT, ValueT >	value_type

typedef HashFcn	hasher

typedef EqualFcn	key_equal

typedef KeyConvertFcn	key_convert

typedef value_type *	pointer

typedef value_type &	reference

typedef const value_type &	const_reference

typedef std::ptrdiff_t	difference_type

typedef std::size_t	size_type

typedef SubMap::Config	Config

typedef ahm_iterator< const AtomicHashMap, const value_type, typename SubMap::const_iterator >	const_iterator

typedef ahm_iterator< AtomicHashMap, value_type, typename SubMap::iterator >	iterator

Public Member Functions
	AtomicHashMap (size_t finalSizeEst, const Config &c=Config())

	~AtomicHashMap ()

key_equal	key_eq () const

hasher	hash_function () const

std::pair< iterator, bool >	insert (const value_type &r)

std::pair< iterator, bool >	insert (key_type k, const mapped_type &v)

std::pair< iterator, bool >	insert (value_type &&r)

std::pair< iterator, bool >	insert (key_type k, mapped_type &&v)

template<typename LookupKeyT = key_type, typename LookupHashFcn = hasher, typename LookupEqualFcn = key_equal, typename LookupKeyToKeyFcn = key_convert, typename... ArgTs>
std::pair< iterator, bool >	emplace (LookupKeyT k, ArgTs &&...vCtorArg)

template<typename LookupKeyT = key_type, typename LookupHashFcn = hasher, typename LookupEqualFcn = key_equal>
iterator	find (LookupKeyT k)

template<typename LookupKeyT = key_type, typename LookupHashFcn = hasher, typename LookupEqualFcn = key_equal>
const_iterator	find (LookupKeyT k) const

size_type	erase (key_type k)

void	clear ()

size_t	size () const

bool	empty () const

size_type	count (key_type k) const

iterator	findAt (uint32_t idx)

const_iterator	findAt (uint32_t idx) const

size_t	capacity () const

size_t	spaceRemaining () const

void	setEntryCountThreadCacheSize (int32_t newSize)

int	numSubMaps () const

iterator	begin ()

const_iterator	begin () const

iterator	end ()

const_iterator	end () const

uint32_t	recToIdx (const value_type &r, bool mayInsert=true)

uint32_t	recToIdx (value_type &&r, bool mayInsert=true)

uint32_t	recToIdx (key_type k, const mapped_type &v, bool mayInsert=true)

uint32_t	recToIdx (key_type k, mapped_type &&v, bool mayInsert=true)

uint32_t	keyToIdx (const KeyT k, bool mayInsert=false)

const value_type &	idxToRec (uint32_t idx) const

template<typename LookupKeyT , typename LookupHashFcn , typename LookupEqualFcn , typename LookupKeyToKeyFcn , typename... ArgTs>
std::pair< typename AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::iterator, bool >	emplace (LookupKeyT k, ArgTs &&...vCtorArgs)

Public Attributes
const float	kGrowthFrac_

Private Types
typedef AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >	SubMap

Private Member Functions
template<typename LookupKeyT = key_type, typename LookupHashFcn = hasher, typename LookupEqualFcn = key_equal, typename LookupKeyToKeyFcn = key_convert, typename... ArgTs>
SimpleRetT	insertInternal (LookupKeyT key, ArgTs &&...value)

template<typename LookupKeyT = key_type, typename LookupHashFcn = hasher, typename LookupEqualFcn = key_equal>
SimpleRetT	findInternal (const LookupKeyT k) const

SimpleRetT	findAtInternal (uint32_t idx) const

bool	tryLockMap (unsigned int idx)

Static Private Member Functions
static uint32_t	encodeIndex (uint32_t subMap, uint32_t subMapIdx)

Private Attributes
std::atomic< SubMap * >	subMaps_ [kNumSubMaps_]

std::atomic< uint32_t >	numMapsAllocated_

Static Private Attributes
static const uint32_t	kNumSubMapBits_ = 4

static const uint32_t	kSecondaryMapBit_ = 1u << 31

static const uint32_t	kSubMapIndexShift_ = 32 - kNumSubMapBits_ - 1

static const uint32_t	kSubMapIndexMask_ = (1 << kSubMapIndexShift_) - 1

static const uint32_t	kNumSubMaps_ = 1 << kNumSubMapBits_

static const uintptr_t	kLockedPtr_ = 0x88ULL << 48

Detailed Description

template<class KeyT, class ValueT, class HashFcn, class EqualFcn, class Allocator, class ProbeFcn, class KeyConvertFcn>
class folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >

Definition at line 95 of file AtomicHashArray.h.

Member Typedef Documentation

template<class KeyT, class ValueT, class HashFcn, class EqualFcn, class Allocator, class ProbeFcn, class KeyConvertFcn>

typedef SubMap::Config folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::Config

Definition at line 188 of file AtomicHashMap.h.

template<class KeyT, class ValueT, class HashFcn, class EqualFcn, class Allocator, class ProbeFcn, class KeyConvertFcn>

typedef ahm_iterator< const AtomicHashMap, const value_type, typename SubMap::const_iterator> folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::const_iterator

Definition at line 191 of file AtomicHashMap.h.

template<class KeyT, class ValueT, class HashFcn, class EqualFcn, class Allocator, class ProbeFcn, class KeyConvertFcn>

typedef const value_type& folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::const_reference

Definition at line 185 of file AtomicHashMap.h.

template<class KeyT, class ValueT, class HashFcn, class EqualFcn, class Allocator, class ProbeFcn, class KeyConvertFcn>

typedef std::ptrdiff_t folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::difference_type

Definition at line 186 of file AtomicHashMap.h.

template<class KeyT, class ValueT, class HashFcn, class EqualFcn, class Allocator, class ProbeFcn, class KeyConvertFcn>

typedef HashFcn folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::hasher

Definition at line 180 of file AtomicHashMap.h.

template<class KeyT, class ValueT, class HashFcn, class EqualFcn, class Allocator, class ProbeFcn, class KeyConvertFcn>

typedef ahm_iterator<AtomicHashMap, value_type, typename SubMap::iterator> folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::iterator

Definition at line 199 of file AtomicHashMap.h.

template<class KeyT, class ValueT, class HashFcn, class EqualFcn, class Allocator, class ProbeFcn, class KeyConvertFcn>

typedef KeyConvertFcn folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::key_convert

Definition at line 182 of file AtomicHashMap.h.

template<class KeyT, class ValueT, class HashFcn, class EqualFcn, class Allocator, class ProbeFcn, class KeyConvertFcn>

typedef EqualFcn folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::key_equal

Definition at line 181 of file AtomicHashMap.h.

template<class KeyT, class ValueT, class HashFcn, class EqualFcn, class Allocator, class ProbeFcn, class KeyConvertFcn>

typedef KeyT folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::key_type

Definition at line 177 of file AtomicHashMap.h.

template<class KeyT, class ValueT, class HashFcn, class EqualFcn, class Allocator, class ProbeFcn, class KeyConvertFcn>

typedef ValueT folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::mapped_type

Definition at line 178 of file AtomicHashMap.h.

template<class KeyT, class ValueT, class HashFcn, class EqualFcn, class Allocator, class ProbeFcn, class KeyConvertFcn>

typedef value_type* folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::pointer

Definition at line 183 of file AtomicHashMap.h.

template<class KeyT, class ValueT, class HashFcn, class EqualFcn, class Allocator, class ProbeFcn, class KeyConvertFcn>

typedef value_type& folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::reference

Definition at line 184 of file AtomicHashMap.h.

template<class KeyT, class ValueT, class HashFcn, class EqualFcn, class Allocator, class ProbeFcn, class KeyConvertFcn>

typedef std::size_t folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::size_type

Definition at line 187 of file AtomicHashMap.h.

template<class KeyT, class ValueT, class HashFcn, class EqualFcn, class Allocator, class ProbeFcn, class KeyConvertFcn>

typedef AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn> folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::SubMap

private

Definition at line 174 of file AtomicHashMap.h.

template<class KeyT, class ValueT, class HashFcn, class EqualFcn, class Allocator, class ProbeFcn, class KeyConvertFcn>

typedef std::pair<const KeyT, ValueT> folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::value_type

Definition at line 179 of file AtomicHashMap.h.

Constructor & Destructor Documentation

template<typename KeyT , typename ValueT , typename HashFcn , typename EqualFcn , typename Allocator , typename ProbeFcn , typename KeyConvertFcn >

folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::AtomicHashMap	(	size_t	finalSizeEst,
		const Config &	c = `Config()`
	)

explicit

Definition at line 42 of file AtomicHashMap-inl.h.

References folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::create(), FOR_EACH_RANGE, i, folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::kNumSubMaps_, folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::Config::maxLoadFactor, folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::numMapsAllocated_, and folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::subMaps_.

     : kGrowthFrac_(
           config.growthFactor < 0 ? 1.0f - config.maxLoadFactor
                                   : config.growthFactor) {
   CHECK(config.maxLoadFactor > 0.0f && config.maxLoadFactor < 1.0f);
   subMaps_[0].store(
       SubMap::create(finalSizeEst, config).release(),
       std::memory_order_relaxed);
   auto subMapCount = kNumSubMaps_;
   FOR_EACH_RANGE (i, 1, subMapCount) {
     subMaps_[i].store(nullptr, std::memory_order_relaxed);
   }
   numMapsAllocated_.store(1, std::memory_order_relaxed);
 }

template<class KeyT, class ValueT, class HashFcn, class EqualFcn, class Allocator, class ProbeFcn, class KeyConvertFcn>

folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::~AtomicHashMap ( )

inline

Definition at line 209 of file AtomicHashMap.h.

                    {
     const unsigned int numMaps =
         numMapsAllocated_.load(std::memory_order_relaxed);
     FOR_EACH_RANGE (i, 0, numMaps) {
       SubMap* thisMap = subMaps_[i].load(std::memory_order_relaxed);
       DCHECK(thisMap);
       SubMap::destroy(thisMap);
     }
   }

Member Function Documentation

template<class KeyT, class ValueT, class HashFcn, class EqualFcn, class Allocator, class ProbeFcn, class KeyConvertFcn>

iterator folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::begin ( )

inline

Definition at line 379 of file AtomicHashMap.h.

Referenced by TEST().

                    {
     iterator it(this, 0, subMaps_[0].load(std::memory_order_relaxed)->begin());
     it.checkAdvanceToNextSubmap();
     return it;
   }

template<class KeyT, class ValueT, class HashFcn, class EqualFcn, class Allocator, class ProbeFcn, class KeyConvertFcn>

const_iterator folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::begin ( ) const

inline

Definition at line 385 of file AtomicHashMap.h.

                                {
     const_iterator it(
         this, 0, subMaps_[0].load(std::memory_order_relaxed)->begin());
     it.checkAdvanceToNextSubmap();
     return it;
   }

template<typename KeyT , typename ValueT , typename HashFcn , typename EqualFcn , typename Allocator , typename ProbeFcn , typename KeyConvertFcn >

size_t folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::capacity ( ) const

Definition at line 412 of file AtomicHashMap-inl.h.

References FOR_EACH_RANGE, i, folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::numMapsAllocated_, and folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::subMaps_.

Referenced by TEST().

                                    {
   size_t totalCap(0);
   int const numMaps = numMapsAllocated_.load(std::memory_order_acquire);
   FOR_EACH_RANGE (i, 0, numMaps) {
     totalCap += subMaps_[i].load(std::memory_order_relaxed)->capacity_;
   }
   return totalCap;
 }

template<typename KeyT , typename ValueT , typename HashFcn , typename EqualFcn , typename Allocator , typename ProbeFcn , typename KeyConvertFcn >

void folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::clear ( )

Definition at line 466 of file AtomicHashMap-inl.h.

References folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::destroy(), FOR_EACH_RANGE, i, folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::numMapsAllocated_, and folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::subMaps_.

Referenced by TEST().

                           {
   subMaps_[0].load(std::memory_order_relaxed)->clear();
   int const numMaps = numMapsAllocated_.load(std::memory_order_relaxed);
   FOR_EACH_RANGE (i, 1, numMaps) {
     SubMap* thisMap = subMaps_[i].load(std::memory_order_relaxed);
     DCHECK(thisMap);
     SubMap::destroy(thisMap);
     subMaps_[i].store(nullptr, std::memory_order_relaxed);
   }
   numMapsAllocated_.store(1, std::memory_order_relaxed);
 }

template<class KeyT, class ValueT, class HashFcn, class EqualFcn, class Allocator, class ProbeFcn, class KeyConvertFcn>

size_type folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::count ( key_type k ) const

inline

Definition at line 334 of file AtomicHashMap.h.

Referenced by TEST().

                                     {
     return find(k) == end() ? 0 : 1;
   }

template<class KeyT, class ValueT, class HashFcn, class EqualFcn, class Allocator, class ProbeFcn, class KeyConvertFcn>

template<typename LookupKeyT , typename LookupHashFcn , typename LookupEqualFcn , typename LookupKeyToKeyFcn , typename... ArgTs>

std::pair< typename AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn>::iterator, bool> folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::emplace	(	LookupKeyT	k,
		ArgTs &&...	vCtorArgs
	)

Definition at line 89 of file AtomicHashMap-inl.h.

References folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::SimpleRetT::i, folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::insertInternal(), folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::SimpleRetT::j, k, folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::makeIter(), folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::subMaps_, and folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::SimpleRetT::success.

                                                               {
   SimpleRetT ret = insertInternal<
       LookupKeyT,
       LookupHashFcn,
       LookupEqualFcn,
       LookupKeyToKeyFcn>(k, std::forward<ArgTs>(vCtorArgs)...);
   SubMap* subMap = subMaps_[ret.i].load(std::memory_order_relaxed);
   return std::make_pair(
       iterator(this, ret.i, subMap->makeIter(ret.j)), ret.success);
 }

template<class KeyT, class ValueT, class HashFcn, class EqualFcn, class Allocator, class ProbeFcn, class KeyConvertFcn>

template<typename LookupKeyT = key_type, typename LookupHashFcn = hasher, typename LookupEqualFcn = key_equal, typename LookupKeyToKeyFcn = key_convert, typename... ArgTs>

std::pair<iterator, bool> folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::emplace	(	LookupKeyT	k,
		ArgTs &&...	vCtorArg
	)

template<class KeyT, class ValueT, class HashFcn, class EqualFcn, class Allocator, class ProbeFcn, class KeyConvertFcn>

bool folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::empty ( ) const

inline

Definition at line 330 of file AtomicHashMap.h.

Referenced by TEST().

                      {
     return size() == 0;
   }

template<typename KeyT , typename ValueT , typename HashFcn , typename EqualFcn , typename Allocator , typename ProbeFcn , typename KeyConvertFcn >

uint32_t folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::encodeIndex	(	uint32_t	subMap,
		uint32_t	subMapIdx
	)

inlinestaticprivate

Definition at line 536 of file AtomicHashMap-inl.h.

References folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::kNumSubMapBits_, folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::kSecondaryMapBit_, folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::kSubMapIndexMask_, and folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::kSubMapIndexShift_.

                                                                 {
   DCHECK_EQ(offset & kSecondaryMapBit_, 0); // offset can't be too big
   if (subMap == 0) {
     return offset;
   }
   // Make sure subMap isn't too big
   DCHECK_EQ(subMap >> kNumSubMapBits_, 0);
   // Make sure subMap bits of offset are clear
   DCHECK_EQ(offset & (~kSubMapIndexMask_ | kSecondaryMapBit_), 0);
 
   // Set high-order bits to encode which submap this index belongs to
   return offset | (subMap << kSubMapIndexShift_) | kSecondaryMapBit_;
 }

template<class KeyT, class ValueT, class HashFcn, class EqualFcn, class Allocator, class ProbeFcn, class KeyConvertFcn>

iterator folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::end ( )

inline

Definition at line 392 of file AtomicHashMap.h.

Referenced by BENCHMARK(), folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::find(), Counters::getValue(), and TEST().

                  {
     return iterator();
   }

template<class KeyT, class ValueT, class HashFcn, class EqualFcn, class Allocator, class ProbeFcn, class KeyConvertFcn>

const_iterator folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::end ( ) const

inline

Definition at line 396 of file AtomicHashMap.h.

                              {
     return const_iterator();
   }

template<typename KeyT , typename ValueT , typename HashFcn , typename EqualFcn , typename Allocator , typename ProbeFcn , typename KeyConvertFcn >

AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::size_type folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::erase ( key_type k )

Definition at line 384 of file AtomicHashMap-inl.h.

References FOR_EACH_RANGE, i, deadlock::load(), folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::numMapsAllocated_, and folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::subMaps_.

Referenced by TEST().

                                       {
   int const numMaps = numMapsAllocated_.load(std::memory_order_acquire);
   FOR_EACH_RANGE (i, 0, numMaps) {
     // Check each map successively.  If one succeeds, we're done!
     if (subMaps_[i].load(std::memory_order_relaxed)->erase(k)) {
       return 1;
     }
   }
   // Didn't find our key...
   return 0;
 }

template<typename KeyT , typename ValueT , typename HashFcn , typename EqualFcn , typename Allocator , typename ProbeFcn , typename KeyConvertFcn >

template<class LookupKeyT , class LookupHashFcn , class LookupEqualFcn >

AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::iterator folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::find ( LookupKeyT k )

Definition at line 232 of file AtomicHashMap-inl.h.

References folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::end(), folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::SimpleRetT::i, folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::SimpleRetT::j, k, folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::makeIter(), folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::subMaps_, and folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::SimpleRetT::success.

Referenced by BENCHMARK(), Counters::getValue(), and TEST().

                                      {
   SimpleRetT ret = findInternal<LookupKeyT, LookupHashFcn, LookupEqualFcn>(k);
   if (!ret.success) {
     return end();
   }
   SubMap* subMap = subMaps_[ret.i].load(std::memory_order_relaxed);
   return iterator(this, ret.i, subMap->makeIter(ret.j));
 }

template<typename KeyT , typename ValueT , typename HashFcn , typename EqualFcn , typename Allocator , typename ProbeFcn , typename KeyConvertFcn >

template<class LookupKeyT , class LookupHashFcn , class LookupEqualFcn >

AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::const_iterator folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::find ( LookupKeyT k ) const

Definition at line 265 of file AtomicHashMap-inl.h.

                                            {
   return const_cast<AtomicHashMap*>(this)
       ->find<LookupKeyT, LookupHashFcn, LookupEqualFcn>(k);
 }

template<class KeyT, class ValueT, class HashFcn, class EqualFcn, class Allocator, class ProbeFcn, class KeyConvertFcn>

iterator folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::findAt ( uint32_t idx )

inline

Definition at line 347 of file AtomicHashMap.h.

Referenced by TEST().

                                 {
     SimpleRetT ret = findAtInternal(idx);
     DCHECK_LT(ret.i, numSubMaps());
     return iterator(
         this,
         ret.i,
         subMaps_[ret.i].load(std::memory_order_relaxed)->makeIter(ret.j));
   }

template<class KeyT, class ValueT, class HashFcn, class EqualFcn, class Allocator, class ProbeFcn, class KeyConvertFcn>

const_iterator folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::findAt ( uint32_t idx ) const

inline

Definition at line 355 of file AtomicHashMap.h.

                                             {
     return const_cast<AtomicHashMap*>(this)->findAt(idx);
   }

template<typename KeyT , typename ValueT , typename HashFcn , typename EqualFcn , typename Allocator , typename ProbeFcn , typename KeyConvertFcn >

AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::SimpleRetT folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::findAtInternal ( uint32_t idx ) const

private

Definition at line 344 of file AtomicHashMap-inl.h.

References folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::kSecondaryMapBit_, folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::kSubMapIndexMask_, folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::kSubMapIndexShift_, folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::numMapsAllocated_, and uint32_t.

                                                      {
   uint32_t subMapIdx, subMapOffset;
   if (idx & kSecondaryMapBit_) {
     // idx falls in a secondary map
     idx &= ~kSecondaryMapBit_; // unset secondary bit
     subMapIdx = idx >> kSubMapIndexShift_;
     DCHECK_LT(subMapIdx, numMapsAllocated_.load(std::memory_order_relaxed));
     subMapOffset = idx & kSubMapIndexMask_;
   } else {
     // idx falls in primary map
     subMapIdx = 0;
     subMapOffset = idx;
   }
   return SimpleRetT(subMapIdx, subMapOffset, true);
 }

template<typename KeyT , typename ValueT , typename HashFcn , typename EqualFcn , typename Allocator , typename ProbeFcn , typename KeyConvertFcn >

template<class LookupKeyT , class LookupHashFcn , class LookupEqualFcn >

private

Definition at line 295 of file AtomicHashMap-inl.h.

References folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::capacity_, FOR_EACH_RANGE, i, folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::SimpleRetT::idx, k, LIKELY, folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::numMapsAllocated_, folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::subMaps_, and folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::SimpleRetT::success.

                                                          {
   SubMap* const primaryMap = subMaps_[0].load(std::memory_order_relaxed);
   typename SubMap::SimpleRetT ret =
       primaryMap
           ->template findInternal<LookupKeyT, LookupHashFcn, LookupEqualFcn>(k);
   if (LIKELY(ret.idx != primaryMap->capacity_)) {
     return SimpleRetT(0, ret.idx, ret.success);
   }
   const unsigned int numMaps =
       numMapsAllocated_.load(std::memory_order_acquire);
   FOR_EACH_RANGE (i, 1, numMaps) {
     // Check each map successively.  If one succeeds, we're done!
     SubMap* thisMap = subMaps_[i].load(std::memory_order_relaxed);
     ret =
         thisMap
             ->template findInternal<LookupKeyT, LookupHashFcn, LookupEqualFcn>(
                 k);
     if (LIKELY(ret.idx != thisMap->capacity_)) {
       return SimpleRetT(i, ret.idx, ret.success);
     }
   }
   // Didn't find our key...
   return SimpleRetT(numMaps, 0, false);
 }

template<class KeyT, class ValueT, class HashFcn, class EqualFcn, class Allocator, class ProbeFcn, class KeyConvertFcn>

hasher folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::hash_function ( ) const

inline

Definition at line 222 of file AtomicHashMap.h.

                                {
     return hasher();
   }

template<class KeyT, class ValueT, class HashFcn, class EqualFcn, class Allocator, class ProbeFcn, class KeyConvertFcn>

const value_type& folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::idxToRec ( uint32_t idx ) const

inline

Definition at line 430 of file AtomicHashMap.h.

                                                         {
     SimpleRetT ret = findAtInternal(idx);
     return subMaps_[ret.i].load(std::memory_order_relaxed)->idxToRec(ret.j);
   }

template<class KeyT, class ValueT, class HashFcn, class EqualFcn, class Allocator, class ProbeFcn, class KeyConvertFcn>

std::pair<iterator, bool> folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::insert ( const value_type & r )

inline

Definition at line 241 of file AtomicHashMap.h.

Referenced by BENCHMARK(), Counters::increment(), and TEST().

                                                       {
     return emplace(r.first, r.second);
   }

template<class KeyT, class ValueT, class HashFcn, class EqualFcn, class Allocator, class ProbeFcn, class KeyConvertFcn>

std::pair<iterator, bool> folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::insert	(	key_type	k,
		const mapped_type &	v
	)

inline

Definition at line 244 of file AtomicHashMap.h.

                                                                    {
     return emplace(k, v);
   }

template<class KeyT, class ValueT, class HashFcn, class EqualFcn, class Allocator, class ProbeFcn, class KeyConvertFcn>

std::pair<iterator, bool> folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::insert ( value_type && r )

inline

Definition at line 247 of file AtomicHashMap.h.

                                                  {
     return emplace(r.first, std::move(r.second));
   }

template<class KeyT, class ValueT, class HashFcn, class EqualFcn, class Allocator, class ProbeFcn, class KeyConvertFcn>

std::pair<iterator, bool> folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::insert	(	key_type	k,
		mapped_type &&	v
	)

inline

Definition at line 250 of file AtomicHashMap.h.

                                                               {
     return emplace(k, std::move(v));
   }

template<typename KeyT , typename ValueT , typename HashFcn , typename EqualFcn , typename Allocator , typename ProbeFcn , typename KeyConvertFcn >

template<typename LookupKeyT , typename LookupHashFcn , typename LookupEqualFcn , typename LookupKeyToKeyFcn , typename... ArgTs>

AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::SimpleRetT folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::insertInternal	(	LookupKeyT	key,
		ArgTs &&...	value
	)

private

Definition at line 130 of file AtomicHashMap-inl.h.

Referenced by folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::emplace().

                                                                        {
 beginInsertInternal:
   auto nextMapIdx = // this maintains our state
       numMapsAllocated_.load(std::memory_order_acquire);
   typename SubMap::SimpleRetT ret;
   FOR_EACH_RANGE (i, 0, nextMapIdx) {
     // insert in each map successively.  If one succeeds, we're done!
     SubMap* subMap = subMaps_[i].load(std::memory_order_relaxed);
     ret = subMap->template insertInternal<
         LookupKeyT,
         LookupHashFcn,
         LookupEqualFcn,
         LookupKeyToKeyFcn>(key, std::forward<ArgTs>(vCtorArgs)...);
     if (ret.idx == subMap->capacity_) {
       continue; // map is full, so try the next one
     }
     // Either collision or success - insert in either case
     return SimpleRetT(i, ret.idx, ret.success);
   }
 
   // If we made it this far, all maps are full and we need to try to allocate
   // the next one.
 
   SubMap* primarySubMap = subMaps_[0].load(std::memory_order_relaxed);
   if (nextMapIdx >= kNumSubMaps_ ||
       primarySubMap->capacity_ * kGrowthFrac_ < 1.0) {
     // Can't allocate any more sub maps.
     throw AtomicHashMapFullError();
   }
 
   if (tryLockMap(nextMapIdx)) {
     // Alloc a new map and shove it in.  We can change whatever
     // we want because other threads are waiting on us...
     size_t numCellsAllocated = (size_t)(
         primarySubMap->capacity_ *
         std::pow(1.0 + kGrowthFrac_, nextMapIdx - 1));
     size_t newSize = size_t(numCellsAllocated * kGrowthFrac_);
     DCHECK(
         subMaps_[nextMapIdx].load(std::memory_order_relaxed) ==
         (SubMap*)kLockedPtr_);
     // create a new map using the settings stored in the first map
 
     Config config;
     config.emptyKey = primarySubMap->kEmptyKey_;
     config.lockedKey = primarySubMap->kLockedKey_;
     config.erasedKey = primarySubMap->kErasedKey_;
     config.maxLoadFactor = primarySubMap->maxLoadFactor();
     config.entryCountThreadCacheSize =
         primarySubMap->getEntryCountThreadCacheSize();
     subMaps_[nextMapIdx].store(
         SubMap::create(newSize, config).release(), std::memory_order_relaxed);
 
     // Publish the map to other threads.
     numMapsAllocated_.fetch_add(1, std::memory_order_release);
     DCHECK_EQ(
         nextMapIdx + 1, numMapsAllocated_.load(std::memory_order_relaxed));
   } else {
     // If we lost the race, we'll have to wait for the next map to get
     // allocated before doing any insertion here.
     detail::atomic_hash_spin_wait([&] {
       return nextMapIdx >= numMapsAllocated_.load(std::memory_order_acquire);
     });
   }
 
   // Relaxed is ok here because either we just created this map, or we
   // just did a spin wait with an acquire load on numMapsAllocated_.
   SubMap* loadedMap = subMaps_[nextMapIdx].load(std::memory_order_relaxed);
   DCHECK(loadedMap && loadedMap != (SubMap*)kLockedPtr_);
   ret = loadedMap->insertInternal(key, std::forward<ArgTs>(vCtorArgs)...);
   if (ret.idx != loadedMap->capacity_) {
     return SimpleRetT(nextMapIdx, ret.idx, ret.success);
   }
   // We took way too long and the new map is already full...try again from
   // the top (this should pretty much never happen).
   goto beginInsertInternal;
 }

template<class KeyT, class ValueT, class HashFcn, class EqualFcn, class Allocator, class ProbeFcn, class KeyConvertFcn>

key_equal folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::key_eq ( ) const

inline

Definition at line 219 of file AtomicHashMap.h.

                            {
     return key_equal();
   }

template<class KeyT, class ValueT, class HashFcn, class EqualFcn, class Allocator, class ProbeFcn, class KeyConvertFcn>

uint32_t folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::keyToIdx	(	const KeyT	k,
		bool	mayInsert = `false`
	)

inline

Definition at line 426 of file AtomicHashMap.h.

                                                                  {
     return recToIdx(value_type(k), mayInsert);
   }

template<class KeyT, class ValueT, class HashFcn, class EqualFcn, class Allocator, class ProbeFcn, class KeyConvertFcn>

int folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::numSubMaps ( ) const

inline

Definition at line 375 of file AtomicHashMap.h.

Referenced by TEST().

                          {
     return numMapsAllocated_.load(std::memory_order_acquire);
   }

template<class KeyT, class ValueT, class HashFcn, class EqualFcn, class Allocator, class ProbeFcn, class KeyConvertFcn>

uint32_t folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::recToIdx	(	const value_type &	r,
		bool	mayInsert = `true`
	)

inline

Definition at line 402 of file AtomicHashMap.h.

                                                                        {
     SimpleRetT ret =
         mayInsert ? insertInternal(r.first, r.second) : findInternal(r.first);
     return encodeIndex(ret.i, ret.j);
   }

template<class KeyT, class ValueT, class HashFcn, class EqualFcn, class Allocator, class ProbeFcn, class KeyConvertFcn>

uint32_t folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::recToIdx	(	value_type &&	r,
		bool	mayInsert = `true`
	)

inline

Definition at line 408 of file AtomicHashMap.h.

                                                                   {
     SimpleRetT ret = mayInsert ? insertInternal(r.first, std::move(r.second))
                                : findInternal(r.first);
     return encodeIndex(ret.i, ret.j);
   }

template<class KeyT, class ValueT, class HashFcn, class EqualFcn, class Allocator, class ProbeFcn, class KeyConvertFcn>

uint32_t folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::recToIdx	(	key_type	k,
		const mapped_type &	v,
		bool	mayInsert = `true`
	)

inline

Definition at line 415 of file AtomicHashMap.h.

                                                                     {
     SimpleRetT ret = mayInsert ? insertInternal(k, v) : findInternal(k);
     return encodeIndex(ret.i, ret.j);
   }

template<class KeyT, class ValueT, class HashFcn, class EqualFcn, class Allocator, class ProbeFcn, class KeyConvertFcn>

uint32_t folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::recToIdx	(	key_type	k,
		mapped_type &&	v,
		bool	mayInsert = `true`
	)

inline

Definition at line 420 of file AtomicHashMap.h.

                                                                                {
     SimpleRetT ret =
         mayInsert ? insertInternal(k, std::move(v)) : findInternal(k);
     return encodeIndex(ret.i, ret.j);
   }

template<class KeyT, class ValueT, class HashFcn, class EqualFcn, class Allocator, class ProbeFcn, class KeyConvertFcn>

void folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::setEntryCountThreadCacheSize ( int32_t newSize )

inline

Definition at line 365 of file AtomicHashMap.h.

                                                      {
     const int numMaps = numMapsAllocated_.load(std::memory_order_acquire);
     for (int i = 0; i < numMaps; ++i) {
       SubMap* map = subMaps_[i].load(std::memory_order_relaxed);
       map->setEntryCountThreadCacheSize(newSize);
     }
   }

template<typename KeyT , typename ValueT , typename HashFcn , typename EqualFcn , typename Allocator , typename ProbeFcn , typename KeyConvertFcn >

size_t folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::size ( ) const

Definition at line 494 of file AtomicHashMap-inl.h.

References FOR_EACH_RANGE, i, folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::numMapsAllocated_, folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::subMaps_, and uint32_t.

Referenced by TEST(), and Counters::toString().

                                {
   size_t totalSize(0);
   int const numMaps = numMapsAllocated_.load(std::memory_order_acquire);
   FOR_EACH_RANGE (i, 0, numMaps) {
     totalSize += subMaps_[i].load(std::memory_order_relaxed)->size();
   }
   return totalSize;
 }

template<typename KeyT , typename ValueT , typename HashFcn , typename EqualFcn , typename Allocator , typename ProbeFcn , typename KeyConvertFcn >

size_t folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::spaceRemaining ( ) const

Definition at line 438 of file AtomicHashMap-inl.h.

References FOR_EACH_RANGE, i, max, folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::maxEntries_, folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::numEntries_, folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::numMapsAllocated_, folly::ThreadCachedInt< IntT, Tag >::readFull(), and folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::subMaps_.

                                          {
   size_t spaceRem(0);
   int const numMaps = numMapsAllocated_.load(std::memory_order_acquire);
   FOR_EACH_RANGE (i, 0, numMaps) {
     SubMap* thisMap = subMaps_[i].load(std::memory_order_relaxed);
     spaceRem +=
         std::max(0, thisMap->maxEntries_ - &thisMap->numEntries_.readFull());
   }
   return spaceRem;
 }

template<class KeyT, class ValueT, class HashFcn, class EqualFcn, class Allocator, class ProbeFcn, class KeyConvertFcn>

bool folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::tryLockMap ( unsigned int idx )

inlineprivate

Definition at line 475 of file AtomicHashMap.h.

Referenced by folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::insertInternal().

                                            {
     SubMap* val = nullptr;
     return subMaps_[idx].compare_exchange_strong(
         val, (SubMap*)kLockedPtr_, std::memory_order_acquire);
   }

Member Data Documentation

template<class KeyT, class ValueT, class HashFcn, class EqualFcn, class Allocator, class ProbeFcn, class KeyConvertFcn>

const float folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::kGrowthFrac_

Definition at line 202 of file AtomicHashMap.h.

Referenced by folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::insertInternal().

template<class KeyT, class ValueT, class HashFcn, class EqualFcn, class Allocator, class ProbeFcn, class KeyConvertFcn>

const uintptr_t folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::kLockedPtr_ = 0x88ULL << 48

staticprivate

Definition at line 446 of file AtomicHashMap.h.

Referenced by folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::insertInternal().

template<class KeyT, class ValueT, class HashFcn, class EqualFcn, class Allocator, class ProbeFcn, class KeyConvertFcn>

const uint32_t folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::kNumSubMapBits_ = 4

staticprivate

Definition at line 441 of file AtomicHashMap.h.

Referenced by folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::encodeIndex().

template<class KeyT, class ValueT, class HashFcn, class EqualFcn, class Allocator, class ProbeFcn, class KeyConvertFcn>

const uint32_t folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::kNumSubMaps_ = 1 << kNumSubMapBits_

staticprivate

Definition at line 445 of file AtomicHashMap.h.

Referenced by folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::AtomicHashMap(), and folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::insertInternal().

template<class KeyT, class ValueT, class HashFcn, class EqualFcn, class Allocator, class ProbeFcn, class KeyConvertFcn>

const uint32_t folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::kSecondaryMapBit_ = 1u << 31

staticprivate

Definition at line 442 of file AtomicHashMap.h.

Referenced by folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::encodeIndex(), and folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::findAtInternal().

template<class KeyT, class ValueT, class HashFcn, class EqualFcn, class Allocator, class ProbeFcn, class KeyConvertFcn>

const uint32_t folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::kSubMapIndexMask_ = (1 << kSubMapIndexShift_) - 1

staticprivate

Definition at line 444 of file AtomicHashMap.h.

template<class KeyT, class ValueT, class HashFcn, class EqualFcn, class Allocator, class ProbeFcn, class KeyConvertFcn>

const uint32_t folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::kSubMapIndexShift_ = 32 - kNumSubMapBits_ - 1

staticprivate

Definition at line 443 of file AtomicHashMap.h.

template<class KeyT, class ValueT, class HashFcn, class EqualFcn, class Allocator, class ProbeFcn, class KeyConvertFcn>

std::atomic<uint32_t> folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::numMapsAllocated_

private

Definition at line 473 of file AtomicHashMap.h.

template<class KeyT, class ValueT, class HashFcn, class EqualFcn, class Allocator, class ProbeFcn, class KeyConvertFcn>

std::atomic<SubMap*> folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::subMaps_[kNumSubMaps_]

private

Definition at line 472 of file AtomicHashMap.h.

The documentation for this class was generated from the following files:

proxygen/folly/folly/AtomicHashArray.h
proxygen/folly/folly/AtomicHashMap.h
proxygen/folly/folly/AtomicHashMap-inl.h

Classes

Public Types

Public Member Functions

Public Attributes

Private Types

Private Member Functions

Static Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

template<class KeyT, class ValueT, class HashFcn, class EqualFcn, class Allocator, class ProbeFcn, class KeyConvertFcn> class folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<class KeyT, class ValueT, class HashFcn, class EqualFcn, class Allocator, class ProbeFcn, class KeyConvertFcn>
class folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >