proxygen
Public Member Functions | Public Attributes | List of all members
folly::AtomicUnorderedInsertMap< Key, Value, Hash, KeyEqual, SkipKeyValueDeletion, Atom, IndexType, Allocator >::Slot Struct Reference

Public Member Functions

 ~Slot ()
 
BucketState state () const
 
void stateUpdate (BucketState before, BucketState after)
 
value_type & keyValue ()
 
const value_type & keyValue () const
 

Public Attributes

Atom< IndexType > headAndState_
 
IndexType next_
 The next bucket in the chain. More...
 
std::aligned_storage< sizeof(value_type), alignof(value_type)>::type raw_
 Key and Value. More...
 

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 >::Slot

Lock-free insertion is easiest by prepending to collision chains. A large chaining hash table takes two cache misses instead of one, however. Our solution is to colocate the bucket storage and the head storage, so that even though we are traversing chains we are likely to stay within the same cache line. Just make sure to traverse head before looking at any keys. This strategy gives us 32 bit pointers and fast iteration.

Definition at line 354 of file AtomicUnorderedMap.h.

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 >::Slot::~Slot ( )
inline

Definition at line 368 of file AtomicUnorderedMap.h.

References s.

368  {
369  auto s = state();
370  assert(s == EMPTY || s == LINKED);
371  if (s == LINKED) {
372  keyValue().first.~Key();
373  keyValue().second.~Value();
374  }
375  }
s
static set< string > s
Definition: StringKeyedBenchmark.cpp:48

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>
value_type& folly::AtomicUnorderedInsertMap< Key, Value, Hash, KeyEqual, SkipKeyValueDeletion, Atom, IndexType, Allocator >::Slot::keyValue ( )
inline

Definition at line 386 of file AtomicUnorderedMap.h.

386  {
387  assert(state() != EMPTY);
388  return *static_cast<value_type*>(static_cast<void*>(&raw_));
389  }
folly::AtomicUnorderedInsertMap::Slot::raw_
std::aligned_storage< sizeof(value_type), alignof(value_type)>::type raw_
Key and Value.
Definition: AtomicUnorderedMap.h:366
folly::AtomicUnorderedInsertMap::value_type
std::pair< Key, Value > value_type
Definition: AtomicUnorderedMap.h:147
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 value_type& folly::AtomicUnorderedInsertMap< Key, Value, Hash, KeyEqual, SkipKeyValueDeletion, Atom, IndexType, Allocator >::Slot::keyValue ( ) const
inline

Definition at line 391 of file AtomicUnorderedMap.h.

391  {
392  assert(state() != EMPTY);
393  return *static_cast<const value_type*>(static_cast<const void*>(&raw_));
394  }
folly::AtomicUnorderedInsertMap::Slot::raw_
std::aligned_storage< sizeof(value_type), alignof(value_type)>::type raw_
Key and Value.
Definition: AtomicUnorderedMap.h:366
folly::AtomicUnorderedInsertMap::value_type
std::pair< Key, Value > value_type
Definition: AtomicUnorderedMap.h:147
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>
BucketState folly::AtomicUnorderedInsertMap< Key, Value, Hash, KeyEqual, SkipKeyValueDeletion, Atom, IndexType, Allocator >::Slot::state ( ) const
inline

Definition at line 377 of file AtomicUnorderedMap.h.

377  {
378  return BucketState(headAndState_.load(std::memory_order_acquire) & 3);
379  }
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 >::Slot::stateUpdate ( BucketState  before,
BucketState  after 
)
inline

Definition at line 381 of file AtomicUnorderedMap.h.

381  {
382  assert(state() == before);
383  headAndState_ += (after - before);
384  }

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>
Atom<IndexType> folly::AtomicUnorderedInsertMap< Key, Value, Hash, KeyEqual, SkipKeyValueDeletion, Atom, IndexType, Allocator >::Slot::headAndState_

The bottom two bits are the BucketState, the rest is the index of the first bucket for the chain whose keys map to this slot. When things are going well the head usually links to this slot, but that doesn't always have to happen.

Definition at line 359 of file AtomicUnorderedMap.h.

Referenced by folly::AtomicUnorderedInsertMap< Key, Value, Hash, KeyEqual, SkipKeyValueDeletion, Atom, IndexType, Allocator >::allocateNear(), and folly::AtomicUnorderedInsertMap< Key, Value, Hash, KeyEqual, SkipKeyValueDeletion, Atom, IndexType, Allocator >::find().

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 >::Slot::next_

The next bucket in the chain.

Definition at line 362 of file AtomicUnorderedMap.h.

Referenced by folly::AtomicUnorderedInsertMap< Key, Value, Hash, KeyEqual, SkipKeyValueDeletion, Atom, IndexType, Allocator >::find().

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>
std::aligned_storage<sizeof(value_type), alignof(value_type)>::type folly::AtomicUnorderedInsertMap< Key, Value, Hash, KeyEqual, SkipKeyValueDeletion, Atom, IndexType, Allocator >::Slot::raw_

Key and Value.

Definition at line 366 of file AtomicUnorderedMap.h.

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