folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn > Class Template Reference

#include <AtomicHashArray.h>

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

Classes
struct	aha_iterator
struct	Config
struct	Deleter
struct	SimpleRetT

Public Types
typedef KeyT	key_type
typedef ValueT	mapped_type
typedef HashFcn	hasher
typedef EqualFcn	key_equal
typedef KeyConvertFcn	key_convert
typedef std::pair< const KeyT, ValueT >	value_type
typedef std::size_t	size_type
typedef std::ptrdiff_t	difference_type
typedef value_type &	reference
typedef const value_type &	const_reference
typedef value_type *	pointer
typedef const value_type *	const_pointer
typedef aha_iterator< const AtomicHashArray, const value_type >	const_iterator
typedef aha_iterator< AtomicHashArray, value_type >	iterator
typedef std::unique_ptr< AtomicHashArray, Deleter >	SmartPtr

Public Member Functions
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
std::pair< iterator, bool >	insert (const value_type &r)
std::pair< iterator, bool >	insert (value_type &&r)
template<typename LookupKeyT = key_type, typename LookupHashFcn = hasher, typename LookupEqualFcn = key_equal, typename LookupKeyToKeyFcn = key_convert, typename... ArgTs>
std::pair< iterator, bool >	emplace (LookupKeyT key_in, ArgTs &&...vCtorArgs)
size_t	erase (KeyT k)
void	clear ()
size_t	size () const
bool	empty () const
iterator	begin ()
const_iterator	begin () const
iterator	end ()
const_iterator	end () const
iterator	findAt (uint32_t idx)
const_iterator	findAt (uint32_t idx) const
iterator	makeIter (size_t idx)
const_iterator	makeIter (size_t idx) const
double	maxLoadFactor () const
void	setEntryCountThreadCacheSize (uint32_t newSize)
uint32_t	getEntryCountThreadCacheSize () const

Static Public Member Functions
static void	destroy (AtomicHashArray *)
static SmartPtr	create (size_t maxSize, const Config &c=Config())

Public Attributes
const size_t	capacity_
const size_t	maxEntries_
const KeyT	kEmptyKey_
const KeyT	kLockedKey_
const KeyT	kErasedKey_

Private Member Functions
template<typename LookupKeyT = key_type, typename LookupHashFcn = hasher, typename LookupEqualFcn = key_equal, typename LookupKeyToKeyFcn = Identity, typename... ArgTs>
SimpleRetT	insertInternal (LookupKeyT key, ArgTs &&...vCtorArgs)
template<typename LookupKeyT = key_type, typename LookupHashFcn = hasher, typename LookupEqualFcn = key_equal>
SimpleRetT	findInternal (const LookupKeyT key)
template<typename MaybeKeyT >
void	checkLegalKeyIfKey (MaybeKeyT key)
	AtomicHashArray (size_t capacity, KeyT emptyKey, KeyT lockedKey, KeyT erasedKey, double maxLoadFactor, uint32_t cacheSize)
	~AtomicHashArray ()=default
void	unlockCell (value_type *const cell, KeyT newKey)
bool	tryLockCell (value_type *const cell)
template<class LookupKeyT = key_type, class LookupHashFcn = hasher>
size_t	keyToAnchorIdx (const LookupKeyT k) const

Static Private Member Functions
static std::atomic< KeyT > *	cellKeyPtr (const value_type &r)
static KeyT	relaxedLoadKey (const value_type &r)
static KeyT	acquireLoadKey (const value_type &r)

Private Attributes
const size_t	kAnchorMask_
ThreadCachedInt< uint64_t >	numEntries_
ThreadCachedInt< uint64_t >	numPendingEntries_
std::atomic< int64_t >	isFull_
std::atomic< int64_t >	numErases_
value_type	cells_ [0]

Friends
class	AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn >

Detailed Description

template<class KeyT, class ValueT, class HashFcn = std::hash<KeyT>, class EqualFcn = std::equal_to<KeyT>, class Allocator = std::allocator<char>, class ProbeFcn = AtomicHashArrayLinearProbeFcn, class KeyConvertFcn = Identity>
class folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >

Definition at line 105 of file AtomicHashArray.h.

Member Typedef Documentation

template<class KeyT , class ValueT , class HashFcn = std::hash<KeyT>, class EqualFcn = std::equal_to<KeyT>, class Allocator = std::allocator<char>, class ProbeFcn = AtomicHashArrayLinearProbeFcn, class KeyConvertFcn = Identity>

typedef aha_iterator<const AtomicHashArray, const value_type> folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::const_iterator

Definition at line 135 of file AtomicHashArray.h.

template<class KeyT , class ValueT , class HashFcn = std::hash<KeyT>, class EqualFcn = std::equal_to<KeyT>, class Allocator = std::allocator<char>, class ProbeFcn = AtomicHashArrayLinearProbeFcn, class KeyConvertFcn = Identity>

typedef const value_type* folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::const_pointer

Definition at line 126 of file AtomicHashArray.h.

template<class KeyT , class ValueT , class HashFcn = std::hash<KeyT>, class EqualFcn = std::equal_to<KeyT>, class Allocator = std::allocator<char>, class ProbeFcn = AtomicHashArrayLinearProbeFcn, class KeyConvertFcn = Identity>

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

Definition at line 124 of file AtomicHashArray.h.

template<class KeyT , class ValueT , class HashFcn = std::hash<KeyT>, class EqualFcn = std::equal_to<KeyT>, class Allocator = std::allocator<char>, class ProbeFcn = AtomicHashArrayLinearProbeFcn, class KeyConvertFcn = Identity>

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

Definition at line 122 of file AtomicHashArray.h.

template<class KeyT , class ValueT , class HashFcn = std::hash<KeyT>, class EqualFcn = std::equal_to<KeyT>, class Allocator = std::allocator<char>, class ProbeFcn = AtomicHashArrayLinearProbeFcn, class KeyConvertFcn = Identity>

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

Definition at line 117 of file AtomicHashArray.h.

template<class KeyT , class ValueT , class HashFcn = std::hash<KeyT>, class EqualFcn = std::equal_to<KeyT>, class Allocator = std::allocator<char>, class ProbeFcn = AtomicHashArrayLinearProbeFcn, class KeyConvertFcn = Identity>

typedef aha_iterator<AtomicHashArray, value_type> folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::iterator

Definition at line 138 of file AtomicHashArray.h.

template<class KeyT , class ValueT , class HashFcn = std::hash<KeyT>, class EqualFcn = std::equal_to<KeyT>, class Allocator = std::allocator<char>, class ProbeFcn = AtomicHashArrayLinearProbeFcn, class KeyConvertFcn = Identity>

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

Definition at line 119 of file AtomicHashArray.h.

template<class KeyT , class ValueT , class HashFcn = std::hash<KeyT>, class EqualFcn = std::equal_to<KeyT>, class Allocator = std::allocator<char>, class ProbeFcn = AtomicHashArrayLinearProbeFcn, class KeyConvertFcn = Identity>

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

Definition at line 118 of file AtomicHashArray.h.

template<class KeyT , class ValueT , class HashFcn = std::hash<KeyT>, class EqualFcn = std::equal_to<KeyT>, class Allocator = std::allocator<char>, class ProbeFcn = AtomicHashArrayLinearProbeFcn, class KeyConvertFcn = Identity>

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

Definition at line 112 of file AtomicHashArray.h.

template<class KeyT , class ValueT , class HashFcn = std::hash<KeyT>, class EqualFcn = std::equal_to<KeyT>, class Allocator = std::allocator<char>, class ProbeFcn = AtomicHashArrayLinearProbeFcn, class KeyConvertFcn = Identity>

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

Definition at line 116 of file AtomicHashArray.h.

template<class KeyT , class ValueT , class HashFcn = std::hash<KeyT>, class EqualFcn = std::equal_to<KeyT>, class Allocator = std::allocator<char>, class ProbeFcn = AtomicHashArrayLinearProbeFcn, class KeyConvertFcn = Identity>

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

Definition at line 125 of file AtomicHashArray.h.

template<class KeyT , class ValueT , class HashFcn = std::hash<KeyT>, class EqualFcn = std::equal_to<KeyT>, class Allocator = std::allocator<char>, class ProbeFcn = AtomicHashArrayLinearProbeFcn, class KeyConvertFcn = Identity>

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

Definition at line 123 of file AtomicHashArray.h.

template<class KeyT , class ValueT , class HashFcn = std::hash<KeyT>, class EqualFcn = std::equal_to<KeyT>, class Allocator = std::allocator<char>, class ProbeFcn = AtomicHashArrayLinearProbeFcn, class KeyConvertFcn = Identity>

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

Definition at line 121 of file AtomicHashArray.h.

template<class KeyT , class ValueT , class HashFcn = std::hash<KeyT>, class EqualFcn = std::equal_to<KeyT>, class Allocator = std::allocator<char>, class ProbeFcn = AtomicHashArrayLinearProbeFcn, class KeyConvertFcn = Identity>

typedef std::unique_ptr<AtomicHashArray, Deleter> folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::SmartPtr

Definition at line 156 of file AtomicHashArray.h.

template<class KeyT , class ValueT , class HashFcn = std::hash<KeyT>, class EqualFcn = std::equal_to<KeyT>, class Allocator = std::allocator<char>, class ProbeFcn = AtomicHashArrayLinearProbeFcn, class KeyConvertFcn = Identity>

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

Definition at line 120 of file AtomicHashArray.h.

Constructor & Destructor Documentation

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

folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::AtomicHashArray ( size_t  capacity, KeyT  emptyKey, KeyT  lockedKey, KeyT  erasedKey, double  maxLoadFactor, uint32_t  cacheSize  )

private

Definition at line 45 of file AtomicHashArray-inl.h.

Referenced by folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::create(), and folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::destroy().

    : capacity_(capacity),
      maxEntries_(size_t(_maxLoadFactor * capacity_ + 0.5)),
      kEmptyKey_(emptyKey),
      kLockedKey_(lockedKey),
      kErasedKey_(erasedKey),
      kAnchorMask_(nextPowTwo(capacity_) - 1),
      numEntries_(0, cacheSize),
      numPendingEntries_(0, cacheSize),
      isFull_(0),
      numErases_(0) {}

template<class KeyT , class ValueT , class HashFcn = std::hash<KeyT>, class EqualFcn = std::equal_to<KeyT>, class Allocator = std::allocator<char>, class ProbeFcn = AtomicHashArrayLinearProbeFcn, class KeyConvertFcn = Identity>

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

privatedefault

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

Member Function Documentation

template<class KeyT , class ValueT , class HashFcn = std::hash<KeyT>, class EqualFcn = std::equal_to<KeyT>, class Allocator = std::allocator<char>, class ProbeFcn = AtomicHashArrayLinearProbeFcn, class KeyConvertFcn = Identity>

static KeyT folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::acquireLoadKey ( const value_type &  r )

inlinestaticprivate

Definition at line 398 of file AtomicHashArray.h.

Referenced by folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::erase(), folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::findInternal(), folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::insertInternal(), and folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::aha_iterator< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::isValid().

                                                  {
    return cellKeyPtr(r)->load(std::memory_order_acquire);
  }

template<class KeyT , class ValueT , class HashFcn = std::hash<KeyT>, class EqualFcn = std::equal_to<KeyT>, class Allocator = std::allocator<char>, class ProbeFcn = AtomicHashArrayLinearProbeFcn, class KeyConvertFcn = Identity>

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

inline

Definition at line 296 of file AtomicHashArray.h.

References folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::aha_iterator< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::advancePastEmpty().

Referenced by folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::ahm_iterator< ContT, IterVal, SubIt >::checkAdvanceToNextSubmap().

                   {
    iterator it(this, 0);
    it.advancePastEmpty();
    return it;
  }

template<class KeyT , class ValueT , class HashFcn = std::hash<KeyT>, class EqualFcn = std::equal_to<KeyT>, class Allocator = std::allocator<char>, class ProbeFcn = AtomicHashArrayLinearProbeFcn, class KeyConvertFcn = Identity>

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

inline

Definition at line 301 of file AtomicHashArray.h.

References folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::aha_iterator< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::advancePastEmpty().

                               {
    const_iterator it(this, 0);
    it.advancePastEmpty();
    return it;
  }

template<class KeyT , class ValueT , class HashFcn = std::hash<KeyT>, class EqualFcn = std::equal_to<KeyT>, class Allocator = std::allocator<char>, class ProbeFcn = AtomicHashArrayLinearProbeFcn, class KeyConvertFcn = Identity>

static std::atomic<KeyT>* folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::cellKeyPtr ( const value_type &  r )

inlinestaticprivate

Definition at line 383 of file AtomicHashArray.h.

References upload::const.

Referenced by folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::create(), and folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::erase().

                                                          {
    // We need some illegal casting here in order to actually store
    // our value_type as a std::pair<const,>.  But a little bit of
    // undefined behavior never hurt anyone ...
    static_assert(
        sizeof(std::atomic<KeyT>) == sizeof(KeyT),
        "std::atomic is implemented in an unexpected way for AHM");
    return const_cast<std::atomic<KeyT>*>(
        reinterpret_cast<std::atomic<KeyT> const*>(&r.first));
  }

template<class KeyT , class ValueT , class HashFcn = std::hash<KeyT>, class EqualFcn = std::equal_to<KeyT>, class Allocator = std::allocator<char>, class ProbeFcn = AtomicHashArrayLinearProbeFcn, class KeyConvertFcn = Identity>

template<typename MaybeKeyT >

void folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::checkLegalKeyIfKey ( MaybeKeyT  key )

inlineprivate

Definition at line 379 of file AtomicHashArray.h.

References folly::detail::checkLegalKeyIfKeyTImpl().

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

                                         {
    detail::checkLegalKeyIfKeyTImpl(key, kEmptyKey_, kLockedKey_, kErasedKey_);
  }

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

void folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::clear

(

)

Definition at line 450 of file AtomicHashArray-inl.h.

References folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::capacity_, folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::cells_, folly::gen::first, FOR_EACH_RANGE, i, folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::isFull_, folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::kEmptyKey_, folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::numEntries_, folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::numErases_, folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::numPendingEntries_, and folly::ThreadCachedInt< IntT, Tag >::set().

Referenced by TEST().

                          {
  FOR_EACH_RANGE (i, 0, capacity_) {
    if (cells_[i].first != kEmptyKey_) {
      cells_[i].~value_type();
      *const_cast<KeyT*>(&cells_[i].first) = kEmptyKey_;
    }
    CHECK(cells_[i].first == kEmptyKey_);
  }
  numEntries_.set(0);
  numPendingEntries_.set(0);
  isFull_.store(0, std::memory_order_relaxed);
  numErases_.store(0, std::memory_order_relaxed);
}

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

AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::SmartPtr folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::create ( size_t  maxSize, const Config &  c = Config()  )

static

Definition at line 362 of file AtomicHashArray-inl.h.

References folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::AtomicHashArray(), folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::cellKeyPtr(), folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::Config::emptyKey, folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::Config::entryCountThreadCacheSize, folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::Config::erasedKey, FOR_EACH_RANGE, i, folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::Config::lockedKey, map(), and folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::Config::maxLoadFactor.

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

                                                          {
  CHECK_LE(c.maxLoadFactor, 1.0);
  CHECK_GT(c.maxLoadFactor, 0.0);
  CHECK_NE(c.emptyKey, c.lockedKey);
  size_t capacity = size_t(maxSize / c.maxLoadFactor);
  size_t sz = sizeof(AtomicHashArray) + sizeof(value_type) * capacity;

  auto const mem = Allocator().allocate(sz);
  try {
    new (mem) AtomicHashArray(
        capacity,
        c.emptyKey,
        c.lockedKey,
        c.erasedKey,
        c.maxLoadFactor,
        c.entryCountThreadCacheSize);
  } catch (...) {
    Allocator().deallocate(mem, sz);
    throw;
  }

  SmartPtr map(static_cast<AtomicHashArray*>((void*)mem));

  /*
   * Mark all cells as empty.
   *
   * Note: we're bending the rules a little here accessing the key
   * element in our cells even though the cell object has not been
   * constructed, and casting them to atomic objects (see cellKeyPtr).
   * (Also, in fact we never actually invoke the value_type
   * constructor.)  This is in order to avoid needing to default
   * construct a bunch of value_type when we first start up: if you
   * have an expensive default constructor for the value type this can
   * noticeably speed construction time for an AHA.
   */
  FOR_EACH_RANGE (i, 0, map->capacity_) {
    cellKeyPtr(map->cells_[i])
        ->store(map->kEmptyKey_, std::memory_order_relaxed);
  }
  return map;
}

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

void folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::destroy ( AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn > *  p )

static

Definition at line 419 of file AtomicHashArray-inl.h.

References folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::AtomicHashArray(), folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::capacity_, folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::cells_, FOR_EACH_RANGE, i, folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::kEmptyKey_, and folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::~AtomicHashArray().

Referenced by folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::clear(), and folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::Deleter::operator()().

                                              {
  assert(p);

  size_t sz = sizeof(AtomicHashArray) + sizeof(value_type) * p->capacity_;

  FOR_EACH_RANGE (i, 0, p->capacity_) {
    if (p->cells_[i].first != p->kEmptyKey_) {
      p->cells_[i].~value_type();
    }
  }
  p->~AtomicHashArray();

  Allocator().deallocate((char*)p, sz);
}

template<class KeyT , class ValueT , class HashFcn = std::hash<KeyT>, class EqualFcn = std::equal_to<KeyT>, class Allocator = std::allocator<char>, class ProbeFcn = AtomicHashArrayLinearProbeFcn, class KeyConvertFcn = Identity>

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

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

inline

Definition at line 270 of file AtomicHashArray.h.

References folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::SimpleRetT::idx, k, and folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::SimpleRetT::success.

                                                                           {
    SimpleRetT ret = insertInternal<
        LookupKeyT,
        LookupHashFcn,
        LookupEqualFcn,
        LookupKeyToKeyFcn>(key_in, std::forward<ArgTs>(vCtorArgs)...);
    return std::make_pair(iterator(this, ret.idx), ret.success);
  }

template<class KeyT , class ValueT , class HashFcn = std::hash<KeyT>, class EqualFcn = std::equal_to<KeyT>, class Allocator = std::allocator<char>, class ProbeFcn = AtomicHashArrayLinearProbeFcn, class KeyConvertFcn = Identity>

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

inline

Definition at line 292 of file AtomicHashArray.h.

References folly::size().

                     {
    return size() == 0;
  }

template<class KeyT , class ValueT , class HashFcn = std::hash<KeyT>, class EqualFcn = std::equal_to<KeyT>, class Allocator = std::allocator<char>, class ProbeFcn = AtomicHashArrayLinearProbeFcn, class KeyConvertFcn = Identity>

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

inline

Definition at line 307 of file AtomicHashArray.h.

Referenced by atomicHashArrayInsertRaceThread(), and folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::ahm_iterator< ContT, IterVal, SubIt >::checkAdvanceToNextSubmap().

                 {
    return iterator(this, capacity_);
  }

template<class KeyT , class ValueT , class HashFcn = std::hash<KeyT>, class EqualFcn = std::equal_to<KeyT>, class Allocator = std::allocator<char>, class ProbeFcn = AtomicHashArrayLinearProbeFcn, class KeyConvertFcn = Identity>

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

inline

Definition at line 310 of file AtomicHashArray.h.

                             {
    return const_iterator(this, capacity_);
  }

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

size_t folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::erase

(

KeyT

k

)

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

References folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::acquireLoadKey(), folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::capacity_, folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::cellKeyPtr(), folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::cells_, folly::symbolizer::test::expect(), folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::kEmptyKey_, folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::kErasedKey_, folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::keyToAnchorIdx(), folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::kLockedKey_, folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::numErases_, and UNLIKELY.

                                     {
  CHECK_NE(key_in, kEmptyKey_);
  CHECK_NE(key_in, kLockedKey_);
  CHECK_NE(key_in, kErasedKey_);

  for (size_t idx = keyToAnchorIdx(key_in), numProbes = 0;;
       idx = ProbeFcn()(idx, numProbes, capacity_)) {
    DCHECK_LT(idx, capacity_);
    value_type* cell = &cells_[idx];
    KeyT currentKey = acquireLoadKey(*cell);
    if (currentKey == kEmptyKey_ || currentKey == kLockedKey_) {
      // If we hit an empty (or locked) element, this key does not exist. This
      // is similar to how it's handled in find().
      return 0;
    }
    if (EqualFcn()(currentKey, key_in)) {
      // Found an existing entry for our key, attempt to mark it erased.
      // Some other thread may have erased our key, but this is ok.
      KeyT expect = currentKey;
      if (cellKeyPtr(*cell)->compare_exchange_strong(expect, kErasedKey_)) {
        numErases_.fetch_add(1, std::memory_order_relaxed);

        // Even if there's a value in the cell, we won't delete (or even
        // default construct) it because some other thread may be accessing it.
        // Locking it meanwhile won't work either since another thread may be
        // holding a pointer to it.

        // We found the key and successfully erased it.
        return 1;
      }
      // If another thread succeeds in erasing our key, we'll stop our search.
      return 0;
    }

    // NOTE: the way we count numProbes must be same in find(), insert(),
    // and erase(). Otherwise it may break probing.
    ++numProbes;
    if (UNLIKELY(numProbes >= capacity_)) {
      // probed every cell...fail
      return 0;
    }
  }
}

template<class KeyT , class ValueT , class HashFcn = std::hash<KeyT>, class EqualFcn = std::equal_to<KeyT>, class Allocator = std::allocator<char>, class ProbeFcn = AtomicHashArrayLinearProbeFcn, class KeyConvertFcn = Identity>

template<typename LookupKeyT = key_type, typename LookupHashFcn = hasher, typename LookupEqualFcn = key_equal>

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

inline

Definition at line 221 of file AtomicHashArray.h.

                              {
    return iterator(
        this, findInternal<LookupKeyT, LookupHashFcn, LookupEqualFcn>(k).idx);
  }

template<class KeyT , class ValueT , class HashFcn = std::hash<KeyT>, class EqualFcn = std::equal_to<KeyT>, class Allocator = std::allocator<char>, class ProbeFcn = AtomicHashArrayLinearProbeFcn, class KeyConvertFcn = Identity>

template<typename LookupKeyT = key_type, typename LookupHashFcn = hasher, typename LookupEqualFcn = key_equal>

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

inline

Definition at line 230 of file AtomicHashArray.h.

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

template<class KeyT , class ValueT , class HashFcn = std::hash<KeyT>, class EqualFcn = std::equal_to<KeyT>, class Allocator = std::allocator<char>, class ProbeFcn = AtomicHashArrayLinearProbeFcn, class KeyConvertFcn = Identity>

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

inline

Definition at line 317 of file AtomicHashArray.h.

                                {
    DCHECK_LT(idx, capacity_);
    return iterator(this, idx);
  }

template<class KeyT , class ValueT , class HashFcn = std::hash<KeyT>, class EqualFcn = std::equal_to<KeyT>, class Allocator = std::allocator<char>, class ProbeFcn = AtomicHashArrayLinearProbeFcn, class KeyConvertFcn = Identity>

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

inline

Definition at line 321 of file AtomicHashArray.h.

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

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

template<class LookupKeyT , class LookupHashFcn , class LookupEqualFcn >

AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::SimpleRetT folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::findInternal ( const LookupKeyT  key )

private

Definition at line 94 of file AtomicHashArray-inl.h.

References folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::acquireLoadKey(), folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::capacity_, folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::cells_, folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::kEmptyKey_, LIKELY, and UNLIKELY.

                                                        {
  checkLegalKeyIfKey<LookupKeyT>(key_in);

  for (size_t idx = keyToAnchorIdx<LookupKeyT, LookupHashFcn>(key_in),
              numProbes = 0;
       ;
       idx = ProbeFcn()(idx, numProbes, capacity_)) {
    const KeyT key = acquireLoadKey(cells_[idx]);
    if (LIKELY(LookupEqualFcn()(key, key_in))) {
      return SimpleRetT(idx, true);
    }
    if (UNLIKELY(key == kEmptyKey_)) {
      // if we hit an empty element, this key does not exist
      return SimpleRetT(capacity_, false);
    }
    // NOTE: the way we count numProbes must be same in find(), insert(),
    // and erase(). Otherwise it may break probing.
    ++numProbes;
    if (UNLIKELY(numProbes >= capacity_)) {
      // probed every cell...fail
      return SimpleRetT(capacity_, false);
    }
  }
}

template<class KeyT , class ValueT , class HashFcn = std::hash<KeyT>, class EqualFcn = std::equal_to<KeyT>, class Allocator = std::allocator<char>, class ProbeFcn = AtomicHashArrayLinearProbeFcn, class KeyConvertFcn = Identity>

uint32_t folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::getEntryCountThreadCacheSize ( ) const

inline

Definition at line 342 of file AtomicHashArray.h.

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

                                                {
    return numEntries_.getCacheSize();
  }

template<class KeyT , class ValueT , class HashFcn = std::hash<KeyT>, class EqualFcn = std::equal_to<KeyT>, class Allocator = std::allocator<char>, class ProbeFcn = AtomicHashArrayLinearProbeFcn, class KeyConvertFcn = Identity>

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

inline

Definition at line 246 of file AtomicHashArray.h.

Referenced by atomicHashArrayInsertRaceThread().

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

template<class KeyT , class ValueT , class HashFcn = std::hash<KeyT>, class EqualFcn = std::equal_to<KeyT>, class Allocator = std::allocator<char>, class ProbeFcn = AtomicHashArrayLinearProbeFcn, class KeyConvertFcn = Identity>

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

inline

Definition at line 249 of file AtomicHashArray.h.

References folly::gen::move.

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

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>

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

private

Definition at line 158 of file AtomicHashArray-inl.h.

References folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::acquireLoadKey(), folly::detail::atomic_hash_spin_wait(), folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::capacity_, folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::cells_, folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::checkLegalKeyIfKey(), folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::isFull_, folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::kEmptyKey_, folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::kErasedKey_, folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::kLockedKey_, folly::gen::mapped(), folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::maxEntries_, folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::numEntries_, folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::numPendingEntries_, folly::ThreadCachedInt< IntT, Tag >::readFast(), folly::ThreadCachedInt< IntT, Tag >::readFull(), folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::relaxedLoadKey(), folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::tryLockCell(), type, UNLIKELY, folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::unlockCell(), and value.

                                                                          {
  const short NO_NEW_INSERTS = 1;
  const short NO_PENDING_INSERTS = 2;
  checkLegalKeyIfKey<LookupKeyT>(key_in);

  size_t idx = keyToAnchorIdx<LookupKeyT, LookupHashFcn>(key_in);
  size_t numProbes = 0;
  for (;;) {
    DCHECK_LT(idx, capacity_);
    value_type* cell = &cells_[idx];
    if (relaxedLoadKey(*cell) == kEmptyKey_) {
      // NOTE: isFull_ is set based on numEntries_.readFast(), so it's
      // possible to insert more than maxEntries_ entries. However, it's not
      // possible to insert past capacity_.
      ++numPendingEntries_;
      if (isFull_.load(std::memory_order_acquire)) {
        --numPendingEntries_;

        // Before deciding whether this insert succeeded, this thread needs to
        // wait until no other thread can add a new entry.

        // Correctness assumes isFull_ is true at this point. If
        // another thread now does ++numPendingEntries_, we expect it
        // to pass the isFull_.load() test above. (It shouldn't insert
        // a new entry.)
        detail::atomic_hash_spin_wait([&] {
          return (isFull_.load(std::memory_order_acquire) !=
                  NO_PENDING_INSERTS) &&
              (numPendingEntries_.readFull() != 0);
        });
        isFull_.store(NO_PENDING_INSERTS, std::memory_order_release);

        if (relaxedLoadKey(*cell) == kEmptyKey_) {
          // Don't insert past max load factor
          return SimpleRetT(capacity_, false);
        }
      } else {
        // An unallocated cell. Try once to lock it. If we succeed, insert here.
        // If we fail, fall through to comparison below; maybe the insert that
        // just beat us was for this very key....
        if (tryLockCell(cell)) {
          KeyT key_new;
          // Write the value - done before unlocking
          try {
            key_new = LookupKeyToKeyFcn()(key_in);
            typedef
                typename std::remove_const<LookupKeyT>::type LookupKeyTNoConst;
            constexpr bool kAlreadyChecked =
                std::is_same<KeyT, LookupKeyTNoConst>::value;
            if (!kAlreadyChecked) {
              checkLegalKeyIfKey(key_new);
            }
            DCHECK(relaxedLoadKey(*cell) == kLockedKey_);
            // A const mapped_type is only constant once constructed, so cast
            // away any const for the placement new here.
            using mapped = typename std::remove_const<mapped_type>::type;
            new (const_cast<mapped*>(&cell->second))
                ValueT(std::forward<ArgTs>(vCtorArgs)...);
            unlockCell(cell, key_new); // Sets the new key
          } catch (...) {
            // Transition back to empty key---requires handling
            // locked->empty below.
            unlockCell(cell, kEmptyKey_);
            --numPendingEntries_;
            throw;
          }
          // An erase() can race here and delete right after our insertion
          // Direct comparison rather than EqualFcn ok here
          // (we just inserted it)
          DCHECK(
              relaxedLoadKey(*cell) == key_new ||
              relaxedLoadKey(*cell) == kErasedKey_);
          --numPendingEntries_;
          ++numEntries_; // This is a thread cached atomic increment :)
          if (numEntries_.readFast() >= maxEntries_) {
            isFull_.store(NO_NEW_INSERTS, std::memory_order_relaxed);
          }
          return SimpleRetT(idx, true);
        }
        --numPendingEntries_;
      }
    }
    DCHECK(relaxedLoadKey(*cell) != kEmptyKey_);
    if (kLockedKey_ == acquireLoadKey(*cell)) {
      detail::atomic_hash_spin_wait(
          [&] { return kLockedKey_ == acquireLoadKey(*cell); });
    }

    const KeyT thisKey = acquireLoadKey(*cell);
    if (LookupEqualFcn()(thisKey, key_in)) {
      // Found an existing entry for our key, but we don't overwrite the
      // previous value.
      return SimpleRetT(idx, false);
    } else if (thisKey == kEmptyKey_ || thisKey == kLockedKey_) {
      // We need to try again (i.e., don't increment numProbes or
      // advance idx): this case can happen if the constructor for
      // ValueT threw for this very cell (the rethrow block above).
      continue;
    }

    // NOTE: the way we count numProbes must be same in find(),
    // insert(), and erase(). Otherwise it may break probing.
    ++numProbes;
    if (UNLIKELY(numProbes >= capacity_)) {
      // probed every cell...fail
      return SimpleRetT(capacity_, false);
    }

    idx = ProbeFcn()(idx, numProbes, capacity_);
  }
}

template<class KeyT , class ValueT , class HashFcn = std::hash<KeyT>, class EqualFcn = std::equal_to<KeyT>, class Allocator = std::allocator<char>, class ProbeFcn = AtomicHashArrayLinearProbeFcn, class KeyConvertFcn = Identity>

template<class LookupKeyT = key_type, class LookupHashFcn = hasher>

size_t folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::keyToAnchorIdx ( const LookupKeyT  k ) const

inlineprivate

Definition at line 438 of file AtomicHashArray.h.

References k, and LIKELY.

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

                                                         {
    const size_t hashVal = LookupHashFcn()(k);
    const size_t probe = hashVal & kAnchorMask_;
    return LIKELY(probe < capacity_) ? probe : hashVal % capacity_;
  }

template<class KeyT , class ValueT , class HashFcn = std::hash<KeyT>, class EqualFcn = std::equal_to<KeyT>, class Allocator = std::allocator<char>, class ProbeFcn = AtomicHashArrayLinearProbeFcn, class KeyConvertFcn = Identity>

iterator folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::makeIter ( size_t  idx )

inline

Definition at line 325 of file AtomicHashArray.h.

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

                                {
    return iterator(this, idx);
  }

template<class KeyT , class ValueT , class HashFcn = std::hash<KeyT>, class EqualFcn = std::equal_to<KeyT>, class Allocator = std::allocator<char>, class ProbeFcn = AtomicHashArrayLinearProbeFcn, class KeyConvertFcn = Identity>

const_iterator folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::makeIter ( size_t  idx ) const

inline

Definition at line 328 of file AtomicHashArray.h.

                                            {
    return const_iterator(this, idx);
  }

template<class KeyT , class ValueT , class HashFcn = std::hash<KeyT>, class EqualFcn = std::equal_to<KeyT>, class Allocator = std::allocator<char>, class ProbeFcn = AtomicHashArrayLinearProbeFcn, class KeyConvertFcn = Identity>

double folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::maxLoadFactor ( ) const

inline

Definition at line 333 of file AtomicHashArray.h.

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

                               {
    return ((double)maxEntries_) / capacity_;
  }

template<class KeyT , class ValueT , class HashFcn = std::hash<KeyT>, class EqualFcn = std::equal_to<KeyT>, class Allocator = std::allocator<char>, class ProbeFcn = AtomicHashArrayLinearProbeFcn, class KeyConvertFcn = Identity>

static KeyT folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::relaxedLoadKey ( const value_type &  r )

inlinestaticprivate

Definition at line 394 of file AtomicHashArray.h.

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

                                                  {
    return cellKeyPtr(r)->load(std::memory_order_relaxed);
  }

template<class KeyT , class ValueT , class HashFcn = std::hash<KeyT>, class EqualFcn = std::equal_to<KeyT>, class Allocator = std::allocator<char>, class ProbeFcn = AtomicHashArrayLinearProbeFcn, class KeyConvertFcn = Identity>

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

inline

Definition at line 337 of file AtomicHashArray.h.

Referenced by folly::AtomicHashMap< int64_t, int64_t >::setEntryCountThreadCacheSize().

                                                      {
    numEntries_.setCacheSize(newSize);
    numPendingEntries_.setCacheSize(newSize);
  }

template<class KeyT , class ValueT , class HashFcn = std::hash<KeyT>, class EqualFcn = std::equal_to<KeyT>, class Allocator = std::allocator<char>, class ProbeFcn = AtomicHashArrayLinearProbeFcn, class KeyConvertFcn = Identity>

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

inline

Definition at line 288 of file AtomicHashArray.h.

Referenced by TEST().

                      {
    return numEntries_.readFull() - numErases_.load(std::memory_order_relaxed);
  }

template<class KeyT , class ValueT , class HashFcn = std::hash<KeyT>, class EqualFcn = std::equal_to<KeyT>, class Allocator = std::allocator<char>, class ProbeFcn = AtomicHashArrayLinearProbeFcn, class KeyConvertFcn = Identity>

bool folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::tryLockCell ( value_type *const  cell )

inlineprivate

Definition at line 431 of file AtomicHashArray.h.

References folly::symbolizer::test::expect().

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

                                                  {
    KeyT expect = kEmptyKey_;
    return cellKeyPtr(*cell)->compare_exchange_strong(
        expect, kLockedKey_, std::memory_order_acq_rel);
  }

template<class KeyT , class ValueT , class HashFcn = std::hash<KeyT>, class EqualFcn = std::equal_to<KeyT>, class Allocator = std::allocator<char>, class ProbeFcn = AtomicHashArrayLinearProbeFcn, class KeyConvertFcn = Identity>

void folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::unlockCell ( value_type *const  cell, KeyT  newKey  )

inlineprivate

Definition at line 427 of file AtomicHashArray.h.

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

                                                              {
    cellKeyPtr(*cell)->store(newKey, std::memory_order_release);
  }

Friends And Related Function Documentation

template<class KeyT , class ValueT , class HashFcn = std::hash<KeyT>, class EqualFcn = std::equal_to<KeyT>, class Allocator = std::allocator<char>, class ProbeFcn = AtomicHashArrayLinearProbeFcn, class KeyConvertFcn = Identity>

friend class AtomicHashMap< KeyT,ValueT,HashFcn,EqualFcn,Allocator,ProbeFcn >

friend

Definition at line 355 of file AtomicHashArray.h.

Member Data Documentation

template<class KeyT , class ValueT , class HashFcn = std::hash<KeyT>, class EqualFcn = std::equal_to<KeyT>, class Allocator = std::allocator<char>, class ProbeFcn = AtomicHashArrayLinearProbeFcn, class KeyConvertFcn = Identity>

const size_t folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::capacity_

Definition at line 128 of file AtomicHashArray.h.

Referenced by folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::aha_iterator< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::advancePastEmpty(), folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::clear(), folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::destroy(), folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::erase(), folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::findInternal(), folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::findInternal(), folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::insertInternal(), and folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::insertInternal().

template<class KeyT , class ValueT , class HashFcn = std::hash<KeyT>, class EqualFcn = std::equal_to<KeyT>, class Allocator = std::allocator<char>, class ProbeFcn = AtomicHashArrayLinearProbeFcn, class KeyConvertFcn = Identity>

value_type folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::cells_[0]

private

Definition at line 413 of file AtomicHashArray.h.

Referenced by folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::clear(), folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::destroy(), folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::erase(), folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::findInternal(), and folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::insertInternal().

template<class KeyT , class ValueT , class HashFcn = std::hash<KeyT>, class EqualFcn = std::equal_to<KeyT>, class Allocator = std::allocator<char>, class ProbeFcn = AtomicHashArrayLinearProbeFcn, class KeyConvertFcn = Identity>

std::atomic<int64_t> folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::isFull_

private

Definition at line 410 of file AtomicHashArray.h.

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

template<class KeyT , class ValueT , class HashFcn = std::hash<KeyT>, class EqualFcn = std::equal_to<KeyT>, class Allocator = std::allocator<char>, class ProbeFcn = AtomicHashArrayLinearProbeFcn, class KeyConvertFcn = Identity>

const size_t folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::kAnchorMask_

private

Definition at line 147 of file AtomicHashArray.h.

template<class KeyT , class ValueT , class HashFcn = std::hash<KeyT>, class EqualFcn = std::equal_to<KeyT>, class Allocator = std::allocator<char>, class ProbeFcn = AtomicHashArrayLinearProbeFcn, class KeyConvertFcn = Identity>

const KeyT folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::kEmptyKey_

Definition at line 130 of file AtomicHashArray.h.

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

template<class KeyT , class ValueT , class HashFcn = std::hash<KeyT>, class EqualFcn = std::equal_to<KeyT>, class Allocator = std::allocator<char>, class ProbeFcn = AtomicHashArrayLinearProbeFcn, class KeyConvertFcn = Identity>

const KeyT folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::kErasedKey_

Definition at line 132 of file AtomicHashArray.h.

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

template<class KeyT , class ValueT , class HashFcn = std::hash<KeyT>, class EqualFcn = std::equal_to<KeyT>, class Allocator = std::allocator<char>, class ProbeFcn = AtomicHashArrayLinearProbeFcn, class KeyConvertFcn = Identity>

const KeyT folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::kLockedKey_

Definition at line 131 of file AtomicHashArray.h.

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

template<class KeyT , class ValueT , class HashFcn = std::hash<KeyT>, class EqualFcn = std::equal_to<KeyT>, class Allocator = std::allocator<char>, class ProbeFcn = AtomicHashArrayLinearProbeFcn, class KeyConvertFcn = Identity>

const size_t folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::maxEntries_

Definition at line 129 of file AtomicHashArray.h.

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

template<class KeyT , class ValueT , class HashFcn = std::hash<KeyT>, class EqualFcn = std::equal_to<KeyT>, class Allocator = std::allocator<char>, class ProbeFcn = AtomicHashArrayLinearProbeFcn, class KeyConvertFcn = Identity>

ThreadCachedInt<uint64_t> folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::numEntries_

private

Definition at line 408 of file AtomicHashArray.h.

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

template<class KeyT , class ValueT , class HashFcn = std::hash<KeyT>, class EqualFcn = std::equal_to<KeyT>, class Allocator = std::allocator<char>, class ProbeFcn = AtomicHashArrayLinearProbeFcn, class KeyConvertFcn = Identity>

std::atomic<int64_t> folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::numErases_

private

Definition at line 411 of file AtomicHashArray.h.

Referenced by folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::clear(), and folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::erase().

template<class KeyT , class ValueT , class HashFcn = std::hash<KeyT>, class EqualFcn = std::equal_to<KeyT>, class Allocator = std::allocator<char>, class ProbeFcn = AtomicHashArrayLinearProbeFcn, class KeyConvertFcn = Identity>

ThreadCachedInt<uint64_t> folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::numPendingEntries_

private

Definition at line 409 of file AtomicHashArray.h.

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

---

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

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