folly::AtomicUnorderedInsertMap< Key, Value, Hash, KeyEqual, SkipKeyValueDeletion, Atom, IndexType, Allocator > Struct Template Reference

#include <AtomicUnorderedMap.h>

Classes
struct	ConstIterator
struct	Slot

Public Types
typedef Key	key_type
typedef Value	mapped_type
typedef std::pair< Key, Value >	value_type
typedef std::size_t	size_type
typedef std::ptrdiff_t	difference_type
typedef Hash	hasher
typedef KeyEqual	key_equal
typedef const value_type &	const_reference
typedef struct folly::AtomicUnorderedInsertMap::ConstIterator	const_iterator

Public Member Functions
	AtomicUnorderedInsertMap (size_t maxSize, float maxLoadFactor=0.8f, const Allocator &alloc=Allocator())
	~AtomicUnorderedInsertMap ()
template<typename Func >
std::pair< const_iterator, bool >	findOrConstruct (const Key &key, Func &&func)
template<class K , class V >
std::pair< const_iterator, bool >	emplace (const K &key, V &&value)
const_iterator	find (const Key &key) const
const_iterator	cbegin () const
const_iterator	cend () const

Public Attributes
friend	ConstIterator

Private Types
enum	: IndexType { kMaxAllocationTries = 1000 }
enum	BucketState : IndexType { EMPTY = 0, CONSTRUCTING = 1, LINKED = 2 }

Private Member Functions
IndexType	keyToSlotIdx (const Key &key) const
IndexType	find (const Key &key, IndexType slot) const
IndexType	allocateNear (IndexType start)
IndexType	allocationAttempt (IndexType start, IndexType tries) const
void	zeroFillSlots ()

Private Attributes
size_t	mmapRequested_
size_t	numSlots_
size_t	slotMask_
	tricky, see keyToSlodIdx More...
Allocator	allocator_
Slot *	slots_

Detailed Description

template<typename Key, typename Value, typename Hash = std::hash<Key>, typename KeyEqual = std::equal_to<Key>, bool SkipKeyValueDeletion = (boost::has_trivial_destructor<Key>::value && boost::has_trivial_destructor<Value>::value), template< typename > class Atom = std::atomic, typename IndexType = uint32_t, typename Allocator = folly::detail::MMapAlloc>
struct folly::AtomicUnorderedInsertMap< Key, Value, Hash, KeyEqual, SkipKeyValueDeletion, Atom, IndexType, Allocator >

You're probably reading this because you are looking for an AtomicUnorderedMap<K,V> that is fully general, highly concurrent (for reads, writes, and iteration), and makes no performance compromises. We haven't figured that one out yet. What you will find here is a hash table implementation that sacrifices generality so that it can give you all of the other things.

LIMITATIONS:

• Insert only (*) - the only write operation supported directly by AtomicUnorderedInsertMap is findOrConstruct. There is a (*) because values aren't moved, so you can roll your own concurrency control for in-place updates of values (see MutableData and MutableAtom below), but the hash table itself doesn't help you.
• No resizing - you must specify the capacity up front, and once the hash map gets full you won't be able to insert. Insert performance will degrade once the load factor is high. Insert is O(1/(1-actual_load_factor)). Note that this is a pretty strong limitation, because you can't remove existing keys.
• 2^30 maximum default capacity - by default AtomicUnorderedInsertMap uses uint32_t internal indexes (and steals 2 bits), limiting you to about a billion entries. If you need more you can fill in all of the template params so you change IndexType to uint64_t, or you can use AtomicUnorderedInsertMap64. 64-bit indexes will increase the space over of the map, of course.

WHAT YOU GET IN EXCHANGE:

• Arbitrary key and value types - any K and V that can be used in a std::unordered_map can be used here. In fact, the key and value types don't even have to be copyable or moveable!
• Keys and values in the map won't be moved - it is safe to keep pointers or references to the keys and values in the map, because they are never moved or destroyed (until the map itself is destroyed).
• Iterators are never invalidated - writes don't invalidate iterators, so you can scan and insert in parallel.
• Fast wait-free reads - reads are usually only a single cache miss, even when the hash table is very large. Wait-freedom means that you won't see latency outliers even in the face of concurrent writes.
• Lock-free insert - writes proceed in parallel. If a thread in the middle of a write is unlucky and gets suspended, it doesn't block anybody else.

COMMENTS ON INSERT-ONLY

This map provides wait-free linearizable reads and lock-free linearizable inserts. Inserted values won't be moved, but no concurrency control is provided for safely updating them. To remind you of that fact they are only provided in const form. This is the only simple safe thing to do while preserving something like the normal std::map iteration form, which requires that iteration be exposed via std::pair (and prevents encapsulation of access to the value).

There are a couple of reasonable policies for doing in-place concurrency control on the values. I am hoping that the policy can be injected via the value type or an extra template param, to keep the core AtomicUnorderedInsertMap insert-only:

CONST: this is the currently implemented strategy, which is simple, performant, and not that expressive. You can always put in a value with a mutable field (see MutableAtom below), but that doesn't look as pretty as it should.

ATOMIC: for integers and integer-size trivially copyable structs (via an adapter like tao/queues/AtomicStruct) the value can be a std::atomic and read and written atomically.

SEQ-LOCK: attach a counter incremented before and after write. Writers serialize by using CAS to make an even->odd transition, then odd->even after the write. Readers grab the value with memcpy, checking sequence value before and after. Readers retry until they see an even sequence number that doesn't change. This works for larger structs, but still requires memcpy to be equivalent to copy assignment, and it is no longer lock-free. It scales very well, because the readers are still invisible (no cache line writes).

LOCK: folly's SharedMutex would be a good choice here.

MEMORY ALLOCATION

Underlying memory is allocated as a big anonymous mmap chunk, which might be cheaper than calloc() and is certainly not more expensive for large maps. If the SkipKeyValueDeletion template param is true then deletion of the map consists of unmapping the backing memory, which is much faster than destructing all of the keys and values. Feel free to override if std::is_trivial_destructor isn't recognizing the triviality of your destructors.

Definition at line 144 of file AtomicUnorderedMap.h.

Member Typedef Documentation

template<typename Key, typename Value, typename Hash = std::hash<Key>, typename KeyEqual = std::equal_to<Key>, bool SkipKeyValueDeletion = (boost::has_trivial_destructor<Key>::value && boost::has_trivial_destructor<Value>::value), template< typename > class Atom = std::atomic, typename IndexType = uint32_t, typename Allocator = folly::detail::MMapAlloc>

typedef struct folly::AtomicUnorderedInsertMap::ConstIterator folly::AtomicUnorderedInsertMap< Key, Value, Hash, KeyEqual, SkipKeyValueDeletion, Atom, IndexType, Allocator >::const_iterator

template<typename Key, typename Value, typename Hash = std::hash<Key>, typename KeyEqual = std::equal_to<Key>, bool SkipKeyValueDeletion = (boost::has_trivial_destructor<Key>::value && boost::has_trivial_destructor<Value>::value), template< typename > class Atom = std::atomic, typename IndexType = uint32_t, typename Allocator = folly::detail::MMapAlloc>

typedef const value_type& folly::AtomicUnorderedInsertMap< Key, Value, Hash, KeyEqual, SkipKeyValueDeletion, Atom, IndexType, Allocator >::const_reference

Definition at line 152 of file AtomicUnorderedMap.h.

template<typename Key, typename Value, typename Hash = std::hash<Key>, typename KeyEqual = std::equal_to<Key>, bool SkipKeyValueDeletion = (boost::has_trivial_destructor<Key>::value && boost::has_trivial_destructor<Value>::value), template< typename > class Atom = std::atomic, typename IndexType = uint32_t, typename Allocator = folly::detail::MMapAlloc>

typedef std::ptrdiff_t folly::AtomicUnorderedInsertMap< Key, Value, Hash, KeyEqual, SkipKeyValueDeletion, Atom, IndexType, Allocator >::difference_type

Definition at line 149 of file AtomicUnorderedMap.h.

template<typename Key, typename Value, typename Hash = std::hash<Key>, typename KeyEqual = std::equal_to<Key>, bool SkipKeyValueDeletion = (boost::has_trivial_destructor<Key>::value && boost::has_trivial_destructor<Value>::value), template< typename > class Atom = std::atomic, typename IndexType = uint32_t, typename Allocator = folly::detail::MMapAlloc>

typedef Hash folly::AtomicUnorderedInsertMap< Key, Value, Hash, KeyEqual, SkipKeyValueDeletion, Atom, IndexType, Allocator >::hasher

Definition at line 150 of file AtomicUnorderedMap.h.

template<typename Key, typename Value, typename Hash = std::hash<Key>, typename KeyEqual = std::equal_to<Key>, bool SkipKeyValueDeletion = (boost::has_trivial_destructor<Key>::value && boost::has_trivial_destructor<Value>::value), template< typename > class Atom = std::atomic, typename IndexType = uint32_t, typename Allocator = folly::detail::MMapAlloc>

typedef KeyEqual folly::AtomicUnorderedInsertMap< Key, Value, Hash, KeyEqual, SkipKeyValueDeletion, Atom, IndexType, Allocator >::key_equal

Definition at line 151 of file AtomicUnorderedMap.h.

template<typename Key, typename Value, typename Hash = std::hash<Key>, typename KeyEqual = std::equal_to<Key>, bool SkipKeyValueDeletion = (boost::has_trivial_destructor<Key>::value && boost::has_trivial_destructor<Value>::value), template< typename > class Atom = std::atomic, typename IndexType = uint32_t, typename Allocator = folly::detail::MMapAlloc>

typedef Key folly::AtomicUnorderedInsertMap< Key, Value, Hash, KeyEqual, SkipKeyValueDeletion, Atom, IndexType, Allocator >::key_type

Definition at line 145 of file AtomicUnorderedMap.h.

template<typename Key, typename Value, typename Hash = std::hash<Key>, typename KeyEqual = std::equal_to<Key>, bool SkipKeyValueDeletion = (boost::has_trivial_destructor<Key>::value && boost::has_trivial_destructor<Value>::value), template< typename > class Atom = std::atomic, typename IndexType = uint32_t, typename Allocator = folly::detail::MMapAlloc>

typedef Value folly::AtomicUnorderedInsertMap< Key, Value, Hash, KeyEqual, SkipKeyValueDeletion, Atom, IndexType, Allocator >::mapped_type

Definition at line 146 of file AtomicUnorderedMap.h.

template<typename Key, typename Value, typename Hash = std::hash<Key>, typename KeyEqual = std::equal_to<Key>, bool SkipKeyValueDeletion = (boost::has_trivial_destructor<Key>::value && boost::has_trivial_destructor<Value>::value), template< typename > class Atom = std::atomic, typename IndexType = uint32_t, typename Allocator = folly::detail::MMapAlloc>

typedef std::size_t folly::AtomicUnorderedInsertMap< Key, Value, Hash, KeyEqual, SkipKeyValueDeletion, Atom, IndexType, Allocator >::size_type

Definition at line 148 of file AtomicUnorderedMap.h.

template<typename Key, typename Value, typename Hash = std::hash<Key>, typename KeyEqual = std::equal_to<Key>, bool SkipKeyValueDeletion = (boost::has_trivial_destructor<Key>::value && boost::has_trivial_destructor<Value>::value), template< typename > class Atom = std::atomic, typename IndexType = uint32_t, typename Allocator = folly::detail::MMapAlloc>

typedef std::pair<Key, Value> folly::AtomicUnorderedInsertMap< Key, Value, Hash, KeyEqual, SkipKeyValueDeletion, Atom, IndexType, Allocator >::value_type

Definition at line 147 of file AtomicUnorderedMap.h.

Member Enumeration Documentation

template<typename Key, typename Value, typename Hash = std::hash<Key>, typename KeyEqual = std::equal_to<Key>, bool SkipKeyValueDeletion = (boost::has_trivial_destructor<Key>::value && boost::has_trivial_destructor<Value>::value), template< typename > class Atom = std::atomic, typename IndexType = uint32_t, typename Allocator = folly::detail::MMapAlloc>

anonymous enum : IndexType

private

Enumerator
kMaxAllocationTries

Definition at line 337 of file AtomicUnorderedMap.h.

       : IndexType {
    kMaxAllocationTries = 1000, // after this we throw
  };

template<typename Key, typename Value, typename Hash = std::hash<Key>, typename KeyEqual = std::equal_to<Key>, bool SkipKeyValueDeletion = (boost::has_trivial_destructor<Key>::value && boost::has_trivial_destructor<Value>::value), template< typename > class Atom = std::atomic, typename IndexType = uint32_t, typename Allocator = folly::detail::MMapAlloc>

enum folly::AtomicUnorderedInsertMap::BucketState : IndexType

private

Enumerator
EMPTY
CONSTRUCTING
LINKED

Definition at line 341 of file AtomicUnorderedMap.h.

                   : IndexType {
    EMPTY = 0,
    CONSTRUCTING = 1,
    LINKED = 2,
  };

Constructor & Destructor Documentation

template<typename Key, typename Value, typename Hash = std::hash<Key>, typename KeyEqual = std::equal_to<Key>, bool SkipKeyValueDeletion = (boost::has_trivial_destructor<Key>::value && boost::has_trivial_destructor<Value>::value), template< typename > class Atom = std::atomic, typename IndexType = uint32_t, typename Allocator = folly::detail::MMapAlloc>

folly::AtomicUnorderedInsertMap< Key, Value, Hash, KeyEqual, SkipKeyValueDeletion, Atom, IndexType, Allocator >::AtomicUnorderedInsertMap ( size_t  maxSize, float  maxLoadFactor = 0.8f, const Allocator &  alloc = Allocator()  )

inlineexplicit

Constructs a map that will support the insertion of maxSize key-value pairs without exceeding the max load factor. Load factors of greater than 1 are not supported, and once the actual load factor of the map approaches 1 the insert performance will suffer. The capacity is limited to 2^30 (about a billion) for the default IndexType, beyond which we will throw invalid_argument.

Definition at line 207 of file AtomicUnorderedMap.h.

References f, min, and folly::nextPowTwo().

      : allocator_(alloc) {
    size_t capacity = size_t(maxSize / std::min(1.0f, maxLoadFactor) + 128);
    size_t avail = size_t{1} << (8 * sizeof(IndexType) - 2);
    if (capacity > avail && maxSize < avail) {
      // we'll do our best
      capacity = avail;
    }
    if (capacity < maxSize || capacity > avail) {
      throw std::invalid_argument(
          "AtomicUnorderedInsertMap capacity must fit in IndexType with 2 bits "
          "left over");
    }

    numSlots_ = capacity;
    slotMask_ = folly::nextPowTwo(capacity * 4) - 1;
    mmapRequested_ = sizeof(Slot) * capacity;
    slots_ = reinterpret_cast<Slot*>(allocator_.allocate(mmapRequested_));
    zeroFillSlots();
    // mark the zero-th slot as in-use but not valid, since that happens
    // to be our nil value
    slots_[0].stateUpdate(EMPTY, CONSTRUCTING);
  }

template<typename Key, typename Value, typename Hash = std::hash<Key>, typename KeyEqual = std::equal_to<Key>, bool SkipKeyValueDeletion = (boost::has_trivial_destructor<Key>::value && boost::has_trivial_destructor<Value>::value), template< typename > class Atom = std::atomic, typename IndexType = uint32_t, typename Allocator = folly::detail::MMapAlloc>

folly::AtomicUnorderedInsertMap< Key, Value, Hash, KeyEqual, SkipKeyValueDeletion, Atom, IndexType, Allocator >::~AtomicUnorderedInsertMap ( )

inline

Definition at line 234 of file AtomicUnorderedMap.h.

References i.

                              {
    if (!SkipKeyValueDeletion) {
      for (size_t i = 1; i < numSlots_; ++i) {
        slots_[i].~Slot();
      }
    }
    allocator_.deallocate(reinterpret_cast<char*>(slots_), mmapRequested_);
  }

Member Function Documentation

template<typename Key, typename Value, typename Hash = std::hash<Key>, typename KeyEqual = std::equal_to<Key>, bool SkipKeyValueDeletion = (boost::has_trivial_destructor<Key>::value && boost::has_trivial_destructor<Value>::value), template< typename > class Atom = std::atomic, typename IndexType = uint32_t, typename Allocator = folly::detail::MMapAlloc>

IndexType folly::AtomicUnorderedInsertMap< Key, Value, Hash, KeyEqual, SkipKeyValueDeletion, Atom, IndexType, Allocator >::allocateNear ( IndexType  start )

inlineprivate

Allocates a slot and returns its index. Tries to put it near slots_[start].

Definition at line 432 of file AtomicUnorderedMap.h.

References folly::AtomicUnorderedInsertMap< Key, Value, Hash, KeyEqual, SkipKeyValueDeletion, Atom, IndexType, Allocator >::Slot::headAndState_.

                                          {
    for (IndexType tries = 0; tries < kMaxAllocationTries; ++tries) {
      auto slot = allocationAttempt(start, tries);
      auto prev = slots_[slot].headAndState_.load(std::memory_order_acquire);
      if ((prev & 3) == EMPTY &&
          slots_[slot].headAndState_.compare_exchange_strong(
              prev, prev + CONSTRUCTING - EMPTY)) {
        return slot;
      }
    }
    throw std::bad_alloc();
  }

template<typename Key, typename Value, typename Hash = std::hash<Key>, typename KeyEqual = std::equal_to<Key>, bool SkipKeyValueDeletion = (boost::has_trivial_destructor<Key>::value && boost::has_trivial_destructor<Value>::value), template< typename > class Atom = std::atomic, typename IndexType = uint32_t, typename Allocator = folly::detail::MMapAlloc>

IndexType folly::AtomicUnorderedInsertMap< Key, Value, Hash, KeyEqual, SkipKeyValueDeletion, Atom, IndexType, Allocator >::allocationAttempt ( IndexType  start, IndexType  tries  ) const

inlineprivate

Returns the slot we should attempt to allocate after tries failed tries, starting from the specified slot. This is pulled out so we can specialize it differently during deterministic testing

Definition at line 448 of file AtomicUnorderedMap.h.

References LIKELY, folly::Random::rand32(), and folly::Random::rand64().

                                                                      {
    if (LIKELY(tries < 8 && start + tries < numSlots_)) {
      return IndexType(start + tries);
    } else {
      IndexType rv;
      if (sizeof(IndexType) <= 4) {
        rv = IndexType(folly::Random::rand32(numSlots_));
      } else {
        rv = IndexType(folly::Random::rand64(numSlots_));
      }
      assert(rv < numSlots_);
      return rv;
    }
  }

template<typename Key, typename Value, typename Hash = std::hash<Key>, typename KeyEqual = std::equal_to<Key>, bool SkipKeyValueDeletion = (boost::has_trivial_destructor<Key>::value && boost::has_trivial_destructor<Value>::value), template< typename > class Atom = std::atomic, typename IndexType = uint32_t, typename Allocator = folly::detail::MMapAlloc>

const_iterator folly::AtomicUnorderedInsertMap< Key, Value, Hash, KeyEqual, SkipKeyValueDeletion, Atom, IndexType, Allocator >::cbegin ( ) const

inline

Definition at line 324 of file AtomicUnorderedMap.h.

                                {
    IndexType slot = numSlots_ - 1;
    while (slot > 0 && slots_[slot].state() != LINKED) {
      --slot;
    }
    return ConstIterator(*this, slot);
  }

template<typename Key, typename Value, typename Hash = std::hash<Key>, typename KeyEqual = std::equal_to<Key>, bool SkipKeyValueDeletion = (boost::has_trivial_destructor<Key>::value && boost::has_trivial_destructor<Value>::value), template< typename > class Atom = std::atomic, typename IndexType = uint32_t, typename Allocator = folly::detail::MMapAlloc>

const_iterator folly::AtomicUnorderedInsertMap< Key, Value, Hash, KeyEqual, SkipKeyValueDeletion, Atom, IndexType, Allocator >::cend ( ) const

inline

Definition at line 332 of file AtomicUnorderedMap.h.

Referenced by TEST().

                              {
    return ConstIterator(*this, 0);
  }

template<typename Key, typename Value, typename Hash = std::hash<Key>, typename KeyEqual = std::equal_to<Key>, bool SkipKeyValueDeletion = (boost::has_trivial_destructor<Key>::value && boost::has_trivial_destructor<Value>::value), template< typename > class Atom = std::atomic, typename IndexType = uint32_t, typename Allocator = folly::detail::MMapAlloc>

template<class K , class V >

std::pair<const_iterator, bool> folly::AtomicUnorderedInsertMap< Key, Value, Hash, KeyEqual, SkipKeyValueDeletion, Atom, IndexType, Allocator >::emplace ( const K &  key, V &&  value  )

inline

This isn't really emplace, but it is what we need to test. Eventually we can duplicate all of the std::pair constructor forms, including a recursive tuple forwarding template http://functionalcpp.wordpress.com/2013/08/28/tuple-forwarding/).

Definition at line 315 of file AtomicUnorderedMap.h.

References folly::value(), and testing::Value().

Referenced by BENCHMARK(), TEST(), and TYPED_TEST().

                                                                 {
    return findOrConstruct(
        key, [&](void* raw) { new (raw) Value(std::forward<V>(value)); });
  }

template<typename Key, typename Value, typename Hash = std::hash<Key>, typename KeyEqual = std::equal_to<Key>, bool SkipKeyValueDeletion = (boost::has_trivial_destructor<Key>::value && boost::has_trivial_destructor<Value>::value), template< typename > class Atom = std::atomic, typename IndexType = uint32_t, typename Allocator = folly::detail::MMapAlloc>

const_iterator folly::AtomicUnorderedInsertMap< Key, Value, Hash, KeyEqual, SkipKeyValueDeletion, Atom, IndexType, Allocator >::find ( const Key &  key ) const

inline

Definition at line 320 of file AtomicUnorderedMap.h.

Referenced by BENCHMARK(), TEST(), and TYPED_TEST().

                                            {
    return ConstIterator(*this, find(key, keyToSlotIdx(key)));
  }

template<typename Key, typename Value, typename Hash = std::hash<Key>, typename KeyEqual = std::equal_to<Key>, bool SkipKeyValueDeletion = (boost::has_trivial_destructor<Key>::value && boost::has_trivial_destructor<Value>::value), template< typename > class Atom = std::atomic, typename IndexType = uint32_t, typename Allocator = folly::detail::MMapAlloc>

IndexType folly::AtomicUnorderedInsertMap< Key, Value, Hash, KeyEqual, SkipKeyValueDeletion, Atom, IndexType, Allocator >::find ( const Key &  key, IndexType  slot  ) const

inlineprivate

Definition at line 419 of file AtomicUnorderedMap.h.

References folly::gen::first, folly::AtomicUnorderedInsertMap< Key, Value, Hash, KeyEqual, SkipKeyValueDeletion, Atom, IndexType, Allocator >::Slot::headAndState_, and folly::AtomicUnorderedInsertMap< Key, Value, Hash, KeyEqual, SkipKeyValueDeletion, Atom, IndexType, Allocator >::Slot::next_.

                                                       {
    KeyEqual ke = {};
    auto hs = slots_[slot].headAndState_.load(std::memory_order_acquire);
    for (slot = hs >> 2; slot != 0; slot = slots_[slot].next_) {
      if (ke(key, slots_[slot].keyValue().first)) {
        return slot;
      }
    }
    return 0;
  }

template<typename Key, typename Value, typename Hash = std::hash<Key>, typename KeyEqual = std::equal_to<Key>, bool SkipKeyValueDeletion = (boost::has_trivial_destructor<Key>::value && boost::has_trivial_destructor<Value>::value), template< typename > class Atom = std::atomic, typename IndexType = uint32_t, typename Allocator = folly::detail::MMapAlloc>

template<typename Func >

std::pair<const_iterator, bool> folly::AtomicUnorderedInsertMap< Key, Value, Hash, KeyEqual, SkipKeyValueDeletion, Atom, IndexType, Allocator >::findOrConstruct ( const Key &  key, Func &&  func  )

inline

Searches for the key, returning (iter,false) if it is found. If it is not found calls the functor Func with a void* argument that is raw storage suitable for placement construction of a Value (see raw_value_type), then returns (iter,true). May call Func and then return (iter,false) if there are other concurrent writes, in which case the newly constructed value will be immediately destroyed.

This function does not block other readers or writers. If there are other concurrent writes, many parallel calls to func may happen and only the first one to complete will win. The values constructed by the other calls to func will be destroyed.

Usage:

AtomicUnorderedInsertMap<std::string,std::string> memo;

auto value = memo.findOrConstruct(key, [=](void* raw) { new (raw) std::string(computation(key)); })->first;

Definition at line 263 of file AtomicUnorderedMap.h.

References testing::Key().

                                                                             {
    auto const slot = keyToSlotIdx(key);
    auto prev = slots_[slot].headAndState_.load(std::memory_order_acquire);

    auto existing = find(key, slot);
    if (existing != 0) {
      return std::make_pair(ConstIterator(*this, existing), false);
    }

    auto idx = allocateNear(slot);
    new (&slots_[idx].keyValue().first) Key(key);
    func(static_cast<void*>(&slots_[idx].keyValue().second));

    while (true) {
      slots_[idx].next_ = prev >> 2;

      // we can merge the head update and the CONSTRUCTING -> LINKED update
      // into a single CAS if slot == idx (which should happen often)
      auto after = idx << 2;
      if (slot == idx) {
        after += LINKED;
      } else {
        after += (prev & 3);
      }

      if (slots_[slot].headAndState_.compare_exchange_strong(prev, after)) {
        // success
        if (idx != slot) {
          slots_[idx].stateUpdate(CONSTRUCTING, LINKED);
        }
        return std::make_pair(ConstIterator(*this, idx), true);
      }
      // compare_exchange_strong updates its first arg on failure, so
      // there is no need to reread prev

      existing = find(key, slot);
      if (existing != 0) {
        // our allocated key and value are no longer needed
        slots_[idx].keyValue().first.~Key();
        slots_[idx].keyValue().second.~Value();
        slots_[idx].stateUpdate(CONSTRUCTING, EMPTY);

        return std::make_pair(ConstIterator(*this, existing), false);
      }
    }
  }

template<typename Key, typename Value, typename Hash = std::hash<Key>, typename KeyEqual = std::equal_to<Key>, bool SkipKeyValueDeletion = (boost::has_trivial_destructor<Key>::value && boost::has_trivial_destructor<Value>::value), template< typename > class Atom = std::atomic, typename IndexType = uint32_t, typename Allocator = folly::detail::MMapAlloc>

IndexType folly::AtomicUnorderedInsertMap< Key, Value, Hash, KeyEqual, SkipKeyValueDeletion, Atom, IndexType, Allocator >::keyToSlotIdx ( const Key &  key ) const

inlineprivate

Definition at line 410 of file AtomicUnorderedMap.h.

References h.

                                               {
    size_t h = hasher()(key);
    h &= slotMask_;
    while (h >= numSlots_) {
      h -= numSlots_;
    }
    return h;
  }

template<typename Key, typename Value, typename Hash = std::hash<Key>, typename KeyEqual = std::equal_to<Key>, bool SkipKeyValueDeletion = (boost::has_trivial_destructor<Key>::value && boost::has_trivial_destructor<Value>::value), template< typename > class Atom = std::atomic, typename IndexType = uint32_t, typename Allocator = folly::detail::MMapAlloc>

void folly::AtomicUnorderedInsertMap< Key, Value, Hash, KeyEqual, SkipKeyValueDeletion, Atom, IndexType, Allocator >::zeroFillSlots ( )

inlineprivate

Definition at line 463 of file AtomicUnorderedMap.h.

References Atom, testing::Key(), uint64_t, value, and testing::Value().

                       {
    using folly::detail::GivesZeroFilledMemory;
    if (!GivesZeroFilledMemory<Allocator>::value) {
      memset(slots_, 0, mmapRequested_);
    }
  }

Member Data Documentation

template<typename Key, typename Value, typename Hash = std::hash<Key>, typename KeyEqual = std::equal_to<Key>, bool SkipKeyValueDeletion = (boost::has_trivial_destructor<Key>::value && boost::has_trivial_destructor<Value>::value), template< typename > class Atom = std::atomic, typename IndexType = uint32_t, typename Allocator = folly::detail::MMapAlloc>

Allocator folly::AtomicUnorderedInsertMap< Key, Value, Hash, KeyEqual, SkipKeyValueDeletion, Atom, IndexType, Allocator >::allocator_

private

Definition at line 407 of file AtomicUnorderedMap.h.

template<typename Key, typename Value, typename Hash = std::hash<Key>, typename KeyEqual = std::equal_to<Key>, bool SkipKeyValueDeletion = (boost::has_trivial_destructor<Key>::value && boost::has_trivial_destructor<Value>::value), template< typename > class Atom = std::atomic, typename IndexType = uint32_t, typename Allocator = folly::detail::MMapAlloc>

friend folly::AtomicUnorderedInsertMap< Key, Value, Hash, KeyEqual, SkipKeyValueDeletion, Atom, IndexType, Allocator >::ConstIterator

Definition at line 199 of file AtomicUnorderedMap.h.

template<typename Key, typename Value, typename Hash = std::hash<Key>, typename KeyEqual = std::equal_to<Key>, bool SkipKeyValueDeletion = (boost::has_trivial_destructor<Key>::value && boost::has_trivial_destructor<Value>::value), template< typename > class Atom = std::atomic, typename IndexType = uint32_t, typename Allocator = folly::detail::MMapAlloc>

size_t folly::AtomicUnorderedInsertMap< Key, Value, Hash, KeyEqual, SkipKeyValueDeletion, Atom, IndexType, Allocator >::mmapRequested_

private

Definition at line 401 of file AtomicUnorderedMap.h.

template<typename Key, typename Value, typename Hash = std::hash<Key>, typename KeyEqual = std::equal_to<Key>, bool SkipKeyValueDeletion = (boost::has_trivial_destructor<Key>::value && boost::has_trivial_destructor<Value>::value), template< typename > class Atom = std::atomic, typename IndexType = uint32_t, typename Allocator = folly::detail::MMapAlloc>

size_t folly::AtomicUnorderedInsertMap< Key, Value, Hash, KeyEqual, SkipKeyValueDeletion, Atom, IndexType, Allocator >::numSlots_

private

Definition at line 402 of file AtomicUnorderedMap.h.

template<typename Key, typename Value, typename Hash = std::hash<Key>, typename KeyEqual = std::equal_to<Key>, bool SkipKeyValueDeletion = (boost::has_trivial_destructor<Key>::value && boost::has_trivial_destructor<Value>::value), template< typename > class Atom = std::atomic, typename IndexType = uint32_t, typename Allocator = folly::detail::MMapAlloc>

size_t folly::AtomicUnorderedInsertMap< Key, Value, Hash, KeyEqual, SkipKeyValueDeletion, Atom, IndexType, Allocator >::slotMask_

private

tricky, see keyToSlodIdx

Definition at line 405 of file AtomicUnorderedMap.h.

template<typename Key, typename Value, typename Hash = std::hash<Key>, typename KeyEqual = std::equal_to<Key>, bool SkipKeyValueDeletion = (boost::has_trivial_destructor<Key>::value && boost::has_trivial_destructor<Value>::value), template< typename > class Atom = std::atomic, typename IndexType = uint32_t, typename Allocator = folly::detail::MMapAlloc>

Slot* folly::AtomicUnorderedInsertMap< Key, Value, Hash, KeyEqual, SkipKeyValueDeletion, Atom, IndexType, Allocator >::slots_

private

Definition at line 408 of file AtomicUnorderedMap.h.

---

The documentation for this struct was generated from the following file:

• proxygen/folly/folly/AtomicUnorderedMap.h