folly::detail::ConcurrentHashMapSegment< KeyType, ValueType, ShardBits, HashFn, KeyEqual, Allocator, Atom, Mutex > Class Template Reference

#include <ConcurrentHashMap-detail.h>

Classes
class	Buckets
class	Iterator

Public Types
typedef KeyType	key_type
typedef ValueType	mapped_type
typedef std::pair< const KeyType, ValueType >	value_type
typedef std::size_t	size_type
using	Node = concurrenthashmap::NodeT< KeyType, ValueType, Allocator, Atom >

Public Member Functions
	ConcurrentHashMapSegment (size_t initial_buckets, float load_factor, size_t max_size)
	~ConcurrentHashMapSegment ()
size_t	size ()
bool	empty ()
bool	insert (Iterator &it, std::pair< key_type, mapped_type > &&foo)
template<typename Key , typename Value >
bool	insert (Iterator &it, Key &&k, Value &&v)
template<typename Key , typename... Args>
bool	try_emplace (Iterator &it, Key &&k, Args &&...args)
template<typename... Args>
bool	emplace (Iterator &it, const KeyType &k, Node *node)
template<typename Key , typename Value >
bool	insert_or_assign (Iterator &it, Key &&k, Value &&v)
template<typename Key , typename Value >
bool	assign (Iterator &it, Key &&k, Value &&v)
template<typename Key , typename Value >
bool	assign_if_equal (Iterator &it, Key &&k, const ValueType &expected, Value &&desired)
template<typename MatchFunc , typename... Args>
bool	insert_internal (Iterator &it, const KeyType &k, InsertType type, MatchFunc match, Node *cur, Args &&...args)
void	rehash (size_t bucket_count)
bool	find (Iterator &res, const KeyType &k)
size_type	erase (const key_type &key)
size_type	erase_internal (const key_type &key, Iterator *iter)
void	erase (Iterator &res, Iterator &pos)
void	clear ()
void	max_load_factor (float factor)
Iterator	cbegin ()
Iterator	cend ()

Private Types
enum	InsertType { InsertType::DOES_NOT_EXIST, InsertType::MUST_EXIST, InsertType::ANY, InsertType::MATCH }

Private Member Functions
uint64_t	getIdx (size_t bucket_count, size_t hash)
void	getBucketsAndCount (size_t &bcount, Buckets *&buckets, hazptr_holder< Atom > &hazptr)

Private Attributes
Mutex	m_
float	load_factor_
size_t	load_factor_nodes_
size_t	size_ {0}
size_t const	max_size_
Atom< Buckets * >	buckets_ {nullptr}
std::atomic< uint64_t >	seqlock_ {0}
Atom< size_t >	bucket_count_

Detailed Description

template<typename KeyType, typename ValueType, uint8_t ShardBits = 0, typename HashFn = std::hash<KeyType>, typename KeyEqual = std::equal_to<KeyType>, typename Allocator = std::allocator<uint8_t>, template< typename > class Atom = std::atomic, class Mutex = std::mutex>
class folly::detail::ConcurrentHashMapSegment< KeyType, ValueType, ShardBits, HashFn, KeyEqual, Allocator, Atom, Mutex >

Definition at line 208 of file ConcurrentHashMap-detail.h.

Member Typedef Documentation

template<typename KeyType , typename ValueType , uint8_t ShardBits = 0, typename HashFn = std::hash<KeyType>, typename KeyEqual = std::equal_to<KeyType>, typename Allocator = std::allocator<uint8_t>, template< typename > class Atom = std::atomic, class Mutex = std::mutex>

typedef KeyType folly::detail::ConcurrentHashMapSegment< KeyType, ValueType, ShardBits, HashFn, KeyEqual, Allocator, Atom, Mutex >::key_type

Definition at line 219 of file ConcurrentHashMap-detail.h.

template<typename KeyType , typename ValueType , uint8_t ShardBits = 0, typename HashFn = std::hash<KeyType>, typename KeyEqual = std::equal_to<KeyType>, typename Allocator = std::allocator<uint8_t>, template< typename > class Atom = std::atomic, class Mutex = std::mutex>

typedef ValueType folly::detail::ConcurrentHashMapSegment< KeyType, ValueType, ShardBits, HashFn, KeyEqual, Allocator, Atom, Mutex >::mapped_type

Definition at line 220 of file ConcurrentHashMap-detail.h.

template<typename KeyType , typename ValueType , uint8_t ShardBits = 0, typename HashFn = std::hash<KeyType>, typename KeyEqual = std::equal_to<KeyType>, typename Allocator = std::allocator<uint8_t>, template< typename > class Atom = std::atomic, class Mutex = std::mutex>

using folly::detail::ConcurrentHashMapSegment< KeyType, ValueType, ShardBits, HashFn, KeyEqual, Allocator, Atom, Mutex >::Node = concurrenthashmap::NodeT<KeyType, ValueType, Allocator, Atom>

Definition at line 224 of file ConcurrentHashMap-detail.h.

template<typename KeyType , typename ValueType , uint8_t ShardBits = 0, typename HashFn = std::hash<KeyType>, typename KeyEqual = std::equal_to<KeyType>, typename Allocator = std::allocator<uint8_t>, template< typename > class Atom = std::atomic, class Mutex = std::mutex>

typedef std::size_t folly::detail::ConcurrentHashMapSegment< KeyType, ValueType, ShardBits, HashFn, KeyEqual, Allocator, Atom, Mutex >::size_type

Definition at line 222 of file ConcurrentHashMap-detail.h.

template<typename KeyType , typename ValueType , uint8_t ShardBits = 0, typename HashFn = std::hash<KeyType>, typename KeyEqual = std::equal_to<KeyType>, typename Allocator = std::allocator<uint8_t>, template< typename > class Atom = std::atomic, class Mutex = std::mutex>

typedef std::pair<const KeyType, ValueType> folly::detail::ConcurrentHashMapSegment< KeyType, ValueType, ShardBits, HashFn, KeyEqual, Allocator, Atom, Mutex >::value_type

Definition at line 221 of file ConcurrentHashMap-detail.h.

Member Enumeration Documentation

template<typename KeyType , typename ValueType , uint8_t ShardBits = 0, typename HashFn = std::hash<KeyType>, typename KeyEqual = std::equal_to<KeyType>, typename Allocator = std::allocator<uint8_t>, template< typename > class Atom = std::atomic, class Mutex = std::mutex>

enum folly::detail::ConcurrentHashMapSegment::InsertType

strongprivate

Enumerator
DOES_NOT_EXIST
MUST_EXIST
ANY
MATCH

Definition at line 209 of file ConcurrentHashMap-detail.h.

                        {
    DOES_NOT_EXIST, // insert/emplace operations.  If key exists, return false.
    MUST_EXIST, // assign operations.  If key does not exist, return false.
    ANY, // insert_or_assign.
    MATCH, // assign_if_equal (not in std).  For concurrent maps, a
           // way to atomically change a value if equal to some other
           // value.
  };

Constructor & Destructor Documentation

template<typename KeyType , typename ValueType , uint8_t ShardBits = 0, typename HashFn = std::hash<KeyType>, typename KeyEqual = std::equal_to<KeyType>, typename Allocator = std::allocator<uint8_t>, template< typename > class Atom = std::atomic, class Mutex = std::mutex>

folly::detail::ConcurrentHashMapSegment< KeyType, ValueType, ShardBits, HashFn, KeyEqual, Allocator, Atom, Mutex >::ConcurrentHashMapSegment ( size_t  initial_buckets, float  load_factor, size_t  max_size  )

inline

Definition at line 227 of file ConcurrentHashMap-detail.h.

References folly::isPowTwo(), folly::nextPowTwo(), and folly::popcount().

      : load_factor_(load_factor), max_size_(max_size) {
    initial_buckets = folly::nextPowTwo(initial_buckets);
    DCHECK(
        max_size_ == 0 ||
        (isPowTwo(max_size_) &&
         (folly::popcount(max_size_ - 1) + ShardBits <= 32)));
    auto buckets = Buckets::create(initial_buckets);
    buckets_.store(buckets, std::memory_order_release);
    load_factor_nodes_ = initial_buckets * load_factor_;
    bucket_count_.store(initial_buckets, std::memory_order_relaxed);
  }

template<typename KeyType , typename ValueType , uint8_t ShardBits = 0, typename HashFn = std::hash<KeyType>, typename KeyEqual = std::equal_to<KeyType>, typename Allocator = std::allocator<uint8_t>, template< typename > class Atom = std::atomic, class Mutex = std::mutex>

folly::detail::ConcurrentHashMapSegment< KeyType, ValueType, ShardBits, HashFn, KeyEqual, Allocator, Atom, Mutex >::~ConcurrentHashMapSegment ( )

inline

Definition at line 243 of file ConcurrentHashMap-detail.h.

References count.

                              {
    auto buckets = buckets_.load(std::memory_order_relaxed);
    // We can delete and not retire() here, since users must have
    // their own synchronization around destruction.
    auto count = bucket_count_.load(std::memory_order_relaxed);
    buckets->unlink_and_reclaim_nodes(count);
    buckets->destroy(count);
  }

Member Function Documentation

template<typename KeyType , typename ValueType , uint8_t ShardBits = 0, typename HashFn = std::hash<KeyType>, typename KeyEqual = std::equal_to<KeyType>, typename Allocator = std::allocator<uint8_t>, template< typename > class Atom = std::atomic, class Mutex = std::mutex>

template<typename Key , typename Value >

bool folly::detail::ConcurrentHashMapSegment< KeyType, ValueType, ShardBits, HashFn, KeyEqual, Allocator, Atom, Mutex >::assign ( Iterator &  it, Key &&  k, Value &&  v  )

inline

Definition at line 326 of file ConcurrentHashMap-detail.h.

References k, uint8_t, and v.

                                                {
    auto node = (Node*)Allocator().allocate(sizeof(Node));
    new (node) Node(std::forward<Key>(k), std::forward<Value>(v));
    auto res = insert_internal(
        it,
        node->getItem().first,
        InsertType::MUST_EXIST,
        [](const ValueType&) { return false; },
        node,
        node);
    if (!res) {
      node->~Node();
      Allocator().deallocate((uint8_t*)node, sizeof(Node));
    }
    return res;
  }

template<typename KeyType , typename ValueType , uint8_t ShardBits = 0, typename HashFn = std::hash<KeyType>, typename KeyEqual = std::equal_to<KeyType>, typename Allocator = std::allocator<uint8_t>, template< typename > class Atom = std::atomic, class Mutex = std::mutex>

template<typename Key , typename Value >

bool folly::detail::ConcurrentHashMapSegment< KeyType, ValueType, ShardBits, HashFn, KeyEqual, Allocator, Atom, Mutex >::assign_if_equal ( Iterator &  it, Key &&  k, const ValueType &  expected, Value &&  desired  )

inline

Definition at line 344 of file ConcurrentHashMap-detail.h.

References testing::Args(), k, uint8_t, and v.

                       {
    auto node = (Node*)Allocator().allocate(sizeof(Node));
    new (node) Node(std::forward<Key>(k), std::forward<Value>(desired));
    auto res = insert_internal(
        it,
        node->getItem().first,
        InsertType::MATCH,
        [&expected](const ValueType& v) { return v == expected; },
        node,
        node);
    if (!res) {
      node->~Node();
      Allocator().deallocate((uint8_t*)node, sizeof(Node));
    }
    return res;
  }

template<typename KeyType , typename ValueType , uint8_t ShardBits = 0, typename HashFn = std::hash<KeyType>, typename KeyEqual = std::equal_to<KeyType>, typename Allocator = std::allocator<uint8_t>, template< typename > class Atom = std::atomic, class Mutex = std::mutex>

Iterator folly::detail::ConcurrentHashMapSegment< KeyType, ValueType, ShardBits, HashFn, KeyEqual, Allocator, Atom, Mutex >::cbegin ( )

inline

Definition at line 634 of file ConcurrentHashMap-detail.h.

References folly::detail::ConcurrentHashMapSegment< KeyType, ValueType, ShardBits, HashFn, KeyEqual, Allocator, Atom, Mutex >::Iterator::hazptrs_, folly::detail::ConcurrentHashMapSegment< KeyType, ValueType, ShardBits, HashFn, KeyEqual, Allocator, Atom, Mutex >::Iterator::next(), and folly::detail::ConcurrentHashMapSegment< KeyType, ValueType, ShardBits, HashFn, KeyEqual, Allocator, Atom, Mutex >::Iterator::setNode().

                    {
    Iterator res;
    size_t bcount;
    Buckets* buckets;
    getBucketsAndCount(bcount, buckets, res.hazptrs_[0]);
    res.setNode(nullptr, buckets, bcount, 0);
    res.next();
    return res;
  }

template<typename KeyType , typename ValueType , uint8_t ShardBits = 0, typename HashFn = std::hash<KeyType>, typename KeyEqual = std::equal_to<KeyType>, typename Allocator = std::allocator<uint8_t>, template< typename > class Atom = std::atomic, class Mutex = std::mutex>

Iterator folly::detail::ConcurrentHashMapSegment< KeyType, ValueType, ShardBits, HashFn, KeyEqual, Allocator, Atom, Mutex >::cend ( )

inline

Definition at line 644 of file ConcurrentHashMap-detail.h.

Referenced by folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::ConstIterator::next().

                  {
    return Iterator(nullptr);
  }

template<typename KeyType , typename ValueType , uint8_t ShardBits = 0, typename HashFn = std::hash<KeyType>, typename KeyEqual = std::equal_to<KeyType>, typename Allocator = std::allocator<uint8_t>, template< typename > class Atom = std::atomic, class Mutex = std::mutex>

void folly::detail::ConcurrentHashMapSegment< KeyType, ValueType, ShardBits, HashFn, KeyEqual, Allocator, Atom, Mutex >::clear ( )

inline

Definition at line 614 of file ConcurrentHashMap-detail.h.

References g(), and folly::hazptr_obj_base< T, Atom, D >::retire().

               {
    size_t bcount = bucket_count_.load(std::memory_order_relaxed);
    Buckets* buckets;
    auto newbuckets = Buckets::create(bcount);
    {
      std::lock_guard<Mutex> g(m_);
      buckets = buckets_.load(std::memory_order_relaxed);
      buckets_.store(newbuckets, std::memory_order_release);
      size_ = 0;
    }
    buckets->retire(concurrenthashmap::HazptrBucketDeleter<Allocator>(bcount));
  }

template<typename KeyType , typename ValueType , uint8_t ShardBits = 0, typename HashFn = std::hash<KeyType>, typename KeyEqual = std::equal_to<KeyType>, typename Allocator = std::allocator<uint8_t>, template< typename > class Atom = std::atomic, class Mutex = std::mutex>

template<typename... Args>

bool folly::detail::ConcurrentHashMapSegment< KeyType, ValueType, ShardBits, HashFn, KeyEqual, Allocator, Atom, Mutex >::emplace ( Iterator &  it, const KeyType &  k, Node *  node  )

inline

Definition at line 297 of file ConcurrentHashMap-detail.h.

Referenced by folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::emplace().

                                                           {
    return insert_internal(
        it,
        k,
        InsertType::DOES_NOT_EXIST,
        [](const ValueType&) { return false; },
        node,
        node);
  }

template<typename KeyType , typename ValueType , uint8_t ShardBits = 0, typename HashFn = std::hash<KeyType>, typename KeyEqual = std::equal_to<KeyType>, typename Allocator = std::allocator<uint8_t>, template< typename > class Atom = std::atomic, class Mutex = std::mutex>

bool folly::detail::ConcurrentHashMapSegment< KeyType, ValueType, ShardBits, HashFn, KeyEqual, Allocator, Atom, Mutex >::empty ( )

inline

Definition at line 256 of file ConcurrentHashMap-detail.h.

References folly::size().

               {
    return size() == 0;
  }

template<typename KeyType , typename ValueType , uint8_t ShardBits = 0, typename HashFn = std::hash<KeyType>, typename KeyEqual = std::equal_to<KeyType>, typename Allocator = std::allocator<uint8_t>, template< typename > class Atom = std::atomic, class Mutex = std::mutex>

size_type folly::detail::ConcurrentHashMapSegment< KeyType, ValueType, ShardBits, HashFn, KeyEqual, Allocator, Atom, Mutex >::erase ( const key_type &  key )

inline

Definition at line 548 of file ConcurrentHashMap-detail.h.

Referenced by folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::erase().

                                       {
    return erase_internal(key, nullptr);
  }

template<typename KeyType , typename ValueType , uint8_t ShardBits = 0, typename HashFn = std::hash<KeyType>, typename KeyEqual = std::equal_to<KeyType>, typename Allocator = std::allocator<uint8_t>, template< typename > class Atom = std::atomic, class Mutex = std::mutex>

void folly::detail::ConcurrentHashMapSegment< KeyType, ValueType, ShardBits, HashFn, KeyEqual, Allocator, Atom, Mutex >::erase ( Iterator &  res, Iterator &  pos  )

inline

Definition at line 608 of file ConcurrentHashMap-detail.h.

References folly::padded::cend().

                                           {
    erase_internal(pos->first, &res);
    // Invalidate the iterator.
    pos = cend();
  }

template<typename KeyType , typename ValueType , uint8_t ShardBits = 0, typename HashFn = std::hash<KeyType>, typename KeyEqual = std::equal_to<KeyType>, typename Allocator = std::allocator<uint8_t>, template< typename > class Atom = std::atomic, class Mutex = std::mutex>

size_type folly::detail::ConcurrentHashMapSegment< KeyType, ValueType, ShardBits, HashFn, KeyEqual, Allocator, Atom, Mutex >::erase_internal ( const key_type &  key, Iterator *  iter  )

inline

Definition at line 552 of file ConcurrentHashMap-detail.h.

References g(), h, folly::detail::ConcurrentHashMapSegment< KeyType, ValueType, ShardBits, HashFn, KeyEqual, Allocator, Atom, Mutex >::Iterator::hazptrs_, cpp.ast::next(), folly::detail::ConcurrentHashMapSegment< KeyType, ValueType, ShardBits, HashFn, KeyEqual, Allocator, Atom, Mutex >::Iterator::next(), folly::detail::concurrenthashmap::NodeT< KeyType, ValueType, Allocator, Atom >::next_, and folly::detail::ConcurrentHashMapSegment< KeyType, ValueType, ShardBits, HashFn, KeyEqual, Allocator, Atom, Mutex >::Iterator::setNode().

                                                                {
    Node* node{nullptr};
    auto h = HashFn()(key);
    {
      std::lock_guard<Mutex> g(m_);

      size_t bcount = bucket_count_.load(std::memory_order_relaxed);
      auto buckets = buckets_.load(std::memory_order_relaxed);
      auto idx = getIdx(bcount, h);
      auto head = &buckets->buckets_[idx]();
      node = head->load(std::memory_order_relaxed);
      Node* prev = nullptr;
      while (node) {
        if (KeyEqual()(key, node->getItem().first)) {
          auto next = node->next_.load(std::memory_order_relaxed);
          if (next) {
            next->acquire_link(); // defined in hazptr_obj_base_linked
          }
          if (prev) {
            prev->next_.store(next, std::memory_order_release);
          } else {
            // Must be head of list.
            head->store(next, std::memory_order_release);
          }

          if (iter) {
            iter->hazptrs_[0].reset(buckets);
            iter->setNode(
                node->next_.load(std::memory_order_acquire),
                buckets,
                bcount,
                idx);
            iter->next();
          }
          size_--;
          break;
        }
        prev = node;
        node = node->next_.load(std::memory_order_relaxed);
      }
    }
    // Delete the node while not under the lock.
    if (node) {
      node->release();
      return 1;
    }

    return 0;
  }

template<typename KeyType , typename ValueType , uint8_t ShardBits = 0, typename HashFn = std::hash<KeyType>, typename KeyEqual = std::equal_to<KeyType>, typename Allocator = std::allocator<uint8_t>, template< typename > class Atom = std::atomic, class Mutex = std::mutex>

bool folly::detail::ConcurrentHashMapSegment< KeyType, ValueType, ShardBits, HashFn, KeyEqual, Allocator, Atom, Mutex >::find ( Iterator &  res, const KeyType &  k  )

inline

Definition at line 525 of file ConcurrentHashMap-detail.h.

References folly::detail::ConcurrentHashMapSegment< KeyType, ValueType, ShardBits, HashFn, KeyEqual, Allocator, Atom, Mutex >::Buckets::buckets_, h, folly::detail::ConcurrentHashMapSegment< KeyType, ValueType, ShardBits, HashFn, KeyEqual, Allocator, Atom, Mutex >::Iterator::hazptrs_, k, and folly::detail::ConcurrentHashMapSegment< KeyType, ValueType, ShardBits, HashFn, KeyEqual, Allocator, Atom, Mutex >::Iterator::setNode().

                                             {
    auto& hazcurr = res.hazptrs_[1];
    auto& haznext = res.hazptrs_[2];
    auto h = HashFn()(k);
    size_t bcount;
    Buckets* buckets;
    getBucketsAndCount(bcount, buckets, res.hazptrs_[0]);

    auto idx = getIdx(bcount, h);
    auto prev = &buckets->buckets_[idx]();
    auto node = hazcurr.get_protected(*prev);
    while (node) {
      if (KeyEqual()(k, node->getItem().first)) {
        res.setNode(node, buckets, bcount, idx);
        return true;
      }
      node = haznext.get_protected(node->next_);
      hazcurr.swap(haznext);
    }
    return false;
  }

template<typename KeyType , typename ValueType , uint8_t ShardBits = 0, typename HashFn = std::hash<KeyType>, typename KeyEqual = std::equal_to<KeyType>, typename Allocator = std::allocator<uint8_t>, template< typename > class Atom = std::atomic, class Mutex = std::mutex>

void folly::detail::ConcurrentHashMapSegment< KeyType, ValueType, ShardBits, HashFn, KeyEqual, Allocator, Atom, Mutex >::getBucketsAndCount ( size_t &  bcount, Buckets *&  buckets, hazptr_holder< Atom > &  hazptr  )

inlineprivate

Definition at line 795 of file ConcurrentHashMap-detail.h.

References folly::hazptr_holder< Atom >::get_protected().

                                   {
    while (true) {
      auto seqlock = seqlock_.load(std::memory_order_acquire);
      bcount = bucket_count_.load(std::memory_order_acquire);
      buckets = hazptr.get_protected(buckets_);
      auto seqlock2 = seqlock_.load(std::memory_order_acquire);
      if (!(seqlock & 1) && (seqlock == seqlock2)) {
        break;
      }
    }
    DCHECK(buckets);
  }

template<typename KeyType , typename ValueType , uint8_t ShardBits = 0, typename HashFn = std::hash<KeyType>, typename KeyEqual = std::equal_to<KeyType>, typename Allocator = std::allocator<uint8_t>, template< typename > class Atom = std::atomic, class Mutex = std::mutex>

uint64_t folly::detail::ConcurrentHashMapSegment< KeyType, ValueType, ShardBits, HashFn, KeyEqual, Allocator, Atom, Mutex >::getIdx ( size_t  bucket_count, size_t  hash  )

inlineprivate

Definition at line 792 of file ConcurrentHashMap-detail.h.

                                                    {
    return (hash >> ShardBits) & (bucket_count - 1);
  }

template<typename KeyType , typename ValueType , uint8_t ShardBits = 0, typename HashFn = std::hash<KeyType>, typename KeyEqual = std::equal_to<KeyType>, typename Allocator = std::allocator<uint8_t>, template< typename > class Atom = std::atomic, class Mutex = std::mutex>

bool folly::detail::ConcurrentHashMapSegment< KeyType, ValueType, ShardBits, HashFn, KeyEqual, Allocator, Atom, Mutex >::insert ( Iterator &  it, std::pair< key_type, mapped_type > &&  foo  )

inline

Definition at line 260 of file ConcurrentHashMap-detail.h.

References folly::gen::move.

Referenced by folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::insert().

                                                                  {
    return insert(it, std::move(foo.first), std::move(foo.second));
  }

template<typename KeyType , typename ValueType , uint8_t ShardBits = 0, typename HashFn = std::hash<KeyType>, typename KeyEqual = std::equal_to<KeyType>, typename Allocator = std::allocator<uint8_t>, template< typename > class Atom = std::atomic, class Mutex = std::mutex>

template<typename Key , typename Value >

bool folly::detail::ConcurrentHashMapSegment< KeyType, ValueType, ShardBits, HashFn, KeyEqual, Allocator, Atom, Mutex >::insert ( Iterator &  it, Key &&  k, Value &&  v  )

inline

Definition at line 265 of file ConcurrentHashMap-detail.h.

References testing::Args(), k, testing::Key(), uint8_t, and v.

                                                {
    auto node = (Node*)Allocator().allocate(sizeof(Node));
    new (node) Node(std::forward<Key>(k), std::forward<Value>(v));
    auto res = insert_internal(
        it,
        node->getItem().first,
        InsertType::DOES_NOT_EXIST,
        [](const ValueType&) { return false; },
        node,
        node);
    if (!res) {
      node->~Node();
      Allocator().deallocate((uint8_t*)node, sizeof(Node));
    }
    return res;
  }

template<typename KeyType , typename ValueType , uint8_t ShardBits = 0, typename HashFn = std::hash<KeyType>, typename KeyEqual = std::equal_to<KeyType>, typename Allocator = std::allocator<uint8_t>, template< typename > class Atom = std::atomic, class Mutex = std::mutex>

template<typename MatchFunc , typename... Args>

bool folly::detail::ConcurrentHashMapSegment< KeyType, ValueType, ShardBits, HashFn, KeyEqual, Allocator, Atom, Mutex >::insert_internal ( Iterator &  it, const KeyType &  k, InsertType  type, MatchFunc  match, Node *  cur, Args &&...  args  )

inline

Definition at line 366 of file ConcurrentHashMap-detail.h.

References g(), h, folly::detail::ConcurrentHashMapSegment< KeyType, ValueType, ShardBits, HashFn, KeyEqual, Allocator, Atom, Mutex >::Iterator::hazptrs_, k, cpp.ast::next(), folly::detail::concurrenthashmap::NodeT< KeyType, ValueType, Allocator, Atom >::next_, and folly::detail::ConcurrentHashMapSegment< KeyType, ValueType, ShardBits, HashFn, KeyEqual, Allocator, Atom, Mutex >::Iterator::setNode().

                      {
    auto h = HashFn()(k);
    std::unique_lock<Mutex> g(m_);

    size_t bcount = bucket_count_.load(std::memory_order_relaxed);
    auto buckets = buckets_.load(std::memory_order_relaxed);
    // Check for rehash needed for DOES_NOT_EXIST
    if (size_ >= load_factor_nodes_ && type == InsertType::DOES_NOT_EXIST) {
      if (max_size_ && size_ << 1 > max_size_) {
        // Would exceed max size.
        throw std::bad_alloc();
      }
      rehash(bcount << 1);
      buckets = buckets_.load(std::memory_order_relaxed);
      bcount = bucket_count_.load(std::memory_order_relaxed);
    }

    auto idx = getIdx(bcount, h);
    auto head = &buckets->buckets_[idx]();
    auto node = head->load(std::memory_order_relaxed);
    auto headnode = node;
    auto prev = head;
    auto& hazbuckets = it.hazptrs_[0];
    auto& haznode = it.hazptrs_[1];
    hazbuckets.reset(buckets);
    while (node) {
      // Is the key found?
      if (KeyEqual()(k, node->getItem().first)) {
        it.setNode(node, buckets, bcount, idx);
        haznode.reset(node);
        if (type == InsertType::MATCH) {
          if (!match(node->getItem().second)) {
            return false;
          }
        }
        if (type == InsertType::DOES_NOT_EXIST) {
          return false;
        } else {
          if (!cur) {
            cur = (Node*)Allocator().allocate(sizeof(Node));
            new (cur) Node(std::forward<Args>(args)...);
          }
          auto next = node->next_.load(std::memory_order_relaxed);
          cur->next_.store(next, std::memory_order_relaxed);
          if (next) {
            next->acquire_link(); // defined in hazptr_obj_base_linked
          }
          prev->store(cur, std::memory_order_release);
          g.unlock();
          // Release not under lock.
          node->release();
          return true;
        }
      }

      prev = &node->next_;
      node = node->next_.load(std::memory_order_relaxed);
    }
    if (type != InsertType::DOES_NOT_EXIST && type != InsertType::ANY) {
      haznode.reset();
      hazbuckets.reset();
      return false;
    }
    // Node not found, check for rehash on ANY
    if (size_ >= load_factor_nodes_ && type == InsertType::ANY) {
      if (max_size_ && size_ << 1 > max_size_) {
        // Would exceed max size.
        throw std::bad_alloc();
      }
      rehash(bcount << 1);

      // Reload correct bucket.
      buckets = buckets_.load(std::memory_order_relaxed);
      bcount <<= 1;
      hazbuckets.reset(buckets);
      idx = getIdx(bcount, h);
      head = &buckets->buckets_[idx]();
      headnode = head->load(std::memory_order_relaxed);
    }

    // We found a slot to put the node.
    size_++;
    if (!cur) {
      // InsertType::ANY
      // OR DOES_NOT_EXIST, but only in the try_emplace case
      DCHECK(type == InsertType::ANY || type == InsertType::DOES_NOT_EXIST);
      cur = (Node*)Allocator().allocate(sizeof(Node));
      new (cur) Node(std::forward<Args>(args)...);
    }
    cur->next_.store(headnode, std::memory_order_relaxed);
    head->store(cur, std::memory_order_release);
    it.setNode(cur, buckets, bcount, idx);
    return true;
  }

template<typename KeyType , typename ValueType , uint8_t ShardBits = 0, typename HashFn = std::hash<KeyType>, typename KeyEqual = std::equal_to<KeyType>, typename Allocator = std::allocator<uint8_t>, template< typename > class Atom = std::atomic, class Mutex = std::mutex>

template<typename Key , typename Value >

bool folly::detail::ConcurrentHashMapSegment< KeyType, ValueType, ShardBits, HashFn, KeyEqual, Allocator, Atom, Mutex >::insert_or_assign ( Iterator &  it, Key &&  k, Value &&  v  )

inline

Definition at line 308 of file ConcurrentHashMap-detail.h.

References k, uint8_t, and v.

Referenced by folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::insert_or_assign().

                                                          {
    auto node = (Node*)Allocator().allocate(sizeof(Node));
    new (node) Node(std::forward<Key>(k), std::forward<Value>(v));
    auto res = insert_internal(
        it,
        node->getItem().first,
        InsertType::ANY,
        [](const ValueType&) { return false; },
        node,
        node);
    if (!res) {
      node->~Node();
      Allocator().deallocate((uint8_t*)node, sizeof(Node));
    }
    return res;
  }

template<typename KeyType , typename ValueType , uint8_t ShardBits = 0, typename HashFn = std::hash<KeyType>, typename KeyEqual = std::equal_to<KeyType>, typename Allocator = std::allocator<uint8_t>, template< typename > class Atom = std::atomic, class Mutex = std::mutex>

void folly::detail::ConcurrentHashMapSegment< KeyType, ValueType, ShardBits, HashFn, KeyEqual, Allocator, Atom, Mutex >::max_load_factor ( float  factor )

inline

Definition at line 627 of file ConcurrentHashMap-detail.h.

References g().

                                     {
    std::lock_guard<Mutex> g(m_);
    load_factor_ = factor;
    load_factor_nodes_ =
        bucket_count_.load(std::memory_order_relaxed) * load_factor_;
  }

template<typename KeyType , typename ValueType , uint8_t ShardBits = 0, typename HashFn = std::hash<KeyType>, typename KeyEqual = std::equal_to<KeyType>, typename Allocator = std::allocator<uint8_t>, template< typename > class Atom = std::atomic, class Mutex = std::mutex>

void folly::detail::ConcurrentHashMapSegment< KeyType, ValueType, ShardBits, HashFn, KeyEqual, Allocator, Atom, Mutex >::rehash ( size_t  bucket_count )

inline

Definition at line 468 of file ConcurrentHashMap-detail.h.

References count, h, i, and k.

                                   {
    auto buckets = buckets_.load(std::memory_order_relaxed);
    auto newbuckets = Buckets::create(bucket_count);

    load_factor_nodes_ = bucket_count * load_factor_;

    auto oldcount = bucket_count_.load(std::memory_order_relaxed);
    for (size_t i = 0; i < oldcount; i++) {
      auto bucket = &buckets->buckets_[i]();
      auto node = bucket->load(std::memory_order_relaxed);
      if (!node) {
        continue;
      }
      auto h = HashFn()(node->getItem().first);
      auto idx = getIdx(bucket_count, h);
      // Reuse as long a chain as possible from the end.  Since the
      // nodes don't have previous pointers, the longest last chain
      // will be the same for both the previous hashmap and the new one,
      // assuming all the nodes hash to the same bucket.
      auto lastrun = node;
      auto lastidx = idx;
      auto count = 0;
      auto last = node->next_.load(std::memory_order_relaxed);
      for (; last != nullptr;
           last = last->next_.load(std::memory_order_relaxed)) {
        auto k = getIdx(bucket_count, HashFn()(last->getItem().first));
        if (k != lastidx) {
          lastidx = k;
          lastrun = last;
          count = 0;
        }
        count++;
      }
      // Set longest last run in new bucket, incrementing the refcount.
      lastrun->acquire_link(); // defined in hazptr_obj_base_linked
      newbuckets->buckets_[lastidx]().store(lastrun, std::memory_order_relaxed);
      // Clone remaining nodes
      for (; node != lastrun;
           node = node->next_.load(std::memory_order_relaxed)) {
        auto newnode = (Node*)Allocator().allocate(sizeof(Node));
        new (newnode) Node(node);
        auto k = getIdx(bucket_count, HashFn()(node->getItem().first));
        auto prevhead = &newbuckets->buckets_[k]();
        newnode->next_.store(prevhead->load(std::memory_order_relaxed));
        prevhead->store(newnode, std::memory_order_relaxed);
      }
    }

    auto oldbuckets = buckets_.load(std::memory_order_relaxed);
    seqlock_.fetch_add(1, std::memory_order_release);
    bucket_count_.store(bucket_count, std::memory_order_release);
    buckets_.store(newbuckets, std::memory_order_release);
    seqlock_.fetch_add(1, std::memory_order_release);
    oldbuckets->retire(
        concurrenthashmap::HazptrBucketDeleter<Allocator>(oldcount));
  }

template<typename KeyType , typename ValueType , uint8_t ShardBits = 0, typename HashFn = std::hash<KeyType>, typename KeyEqual = std::equal_to<KeyType>, typename Allocator = std::allocator<uint8_t>, template< typename > class Atom = std::atomic, class Mutex = std::mutex>

size_t folly::detail::ConcurrentHashMapSegment< KeyType, ValueType, ShardBits, HashFn, KeyEqual, Allocator, Atom, Mutex >::size ( )

inline

Definition at line 252 of file ConcurrentHashMap-detail.h.

                {
    return size_;
  }

template<typename KeyType , typename ValueType , uint8_t ShardBits = 0, typename HashFn = std::hash<KeyType>, typename KeyEqual = std::equal_to<KeyType>, typename Allocator = std::allocator<uint8_t>, template< typename > class Atom = std::atomic, class Mutex = std::mutex>

template<typename Key , typename... Args>

bool folly::detail::ConcurrentHashMapSegment< KeyType, ValueType, ShardBits, HashFn, KeyEqual, Allocator, Atom, Mutex >::try_emplace ( Iterator &  it, Key &&  k, Args &&...  args  )

inline

Definition at line 283 of file ConcurrentHashMap-detail.h.

References testing::Args(), and k.

Referenced by folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::try_emplace().

                                                          {
    // Note: first key is only ever compared.  Second is moved in to
    // create the node, and the first key is never touched again.
    return insert_internal(
        it,
        std::forward<Key>(k),
        InsertType::DOES_NOT_EXIST,
        [](const ValueType&) { return false; },
        nullptr,
        std::forward<Key>(k),
        std::forward<Args>(args)...);
  }

Member Data Documentation

template<typename KeyType , typename ValueType , uint8_t ShardBits = 0, typename HashFn = std::hash<KeyType>, typename KeyEqual = std::equal_to<KeyType>, typename Allocator = std::allocator<uint8_t>, template< typename > class Atom = std::atomic, class Mutex = std::mutex>

Atom<size_t> folly::detail::ConcurrentHashMapSegment< KeyType, ValueType, ShardBits, HashFn, KeyEqual, Allocator, Atom, Mutex >::bucket_count_

private

Definition at line 820 of file ConcurrentHashMap-detail.h.

template<typename KeyType , typename ValueType , uint8_t ShardBits = 0, typename HashFn = std::hash<KeyType>, typename KeyEqual = std::equal_to<KeyType>, typename Allocator = std::allocator<uint8_t>, template< typename > class Atom = std::atomic, class Mutex = std::mutex>

Atom<Buckets*> folly::detail::ConcurrentHashMapSegment< KeyType, ValueType, ShardBits, HashFn, KeyEqual, Allocator, Atom, Mutex >::buckets_ {nullptr}

private

Definition at line 818 of file ConcurrentHashMap-detail.h.

template<typename KeyType , typename ValueType , uint8_t ShardBits = 0, typename HashFn = std::hash<KeyType>, typename KeyEqual = std::equal_to<KeyType>, typename Allocator = std::allocator<uint8_t>, template< typename > class Atom = std::atomic, class Mutex = std::mutex>

float folly::detail::ConcurrentHashMapSegment< KeyType, ValueType, ShardBits, HashFn, KeyEqual, Allocator, Atom, Mutex >::load_factor_

private

Definition at line 812 of file ConcurrentHashMap-detail.h.

template<typename KeyType , typename ValueType , uint8_t ShardBits = 0, typename HashFn = std::hash<KeyType>, typename KeyEqual = std::equal_to<KeyType>, typename Allocator = std::allocator<uint8_t>, template< typename > class Atom = std::atomic, class Mutex = std::mutex>

size_t folly::detail::ConcurrentHashMapSegment< KeyType, ValueType, ShardBits, HashFn, KeyEqual, Allocator, Atom, Mutex >::load_factor_nodes_

private

Definition at line 813 of file ConcurrentHashMap-detail.h.

template<typename KeyType , typename ValueType , uint8_t ShardBits = 0, typename HashFn = std::hash<KeyType>, typename KeyEqual = std::equal_to<KeyType>, typename Allocator = std::allocator<uint8_t>, template< typename > class Atom = std::atomic, class Mutex = std::mutex>

Mutex folly::detail::ConcurrentHashMapSegment< KeyType, ValueType, ShardBits, HashFn, KeyEqual, Allocator, Atom, Mutex >::m_

private

Definition at line 811 of file ConcurrentHashMap-detail.h.

template<typename KeyType , typename ValueType , uint8_t ShardBits = 0, typename HashFn = std::hash<KeyType>, typename KeyEqual = std::equal_to<KeyType>, typename Allocator = std::allocator<uint8_t>, template< typename > class Atom = std::atomic, class Mutex = std::mutex>

size_t const folly::detail::ConcurrentHashMapSegment< KeyType, ValueType, ShardBits, HashFn, KeyEqual, Allocator, Atom, Mutex >::max_size_

private

Definition at line 815 of file ConcurrentHashMap-detail.h.

template<typename KeyType , typename ValueType , uint8_t ShardBits = 0, typename HashFn = std::hash<KeyType>, typename KeyEqual = std::equal_to<KeyType>, typename Allocator = std::allocator<uint8_t>, template< typename > class Atom = std::atomic, class Mutex = std::mutex>

std::atomic<uint64_t> folly::detail::ConcurrentHashMapSegment< KeyType, ValueType, ShardBits, HashFn, KeyEqual, Allocator, Atom, Mutex >::seqlock_ {0}

private

Definition at line 819 of file ConcurrentHashMap-detail.h.

template<typename KeyType , typename ValueType , uint8_t ShardBits = 0, typename HashFn = std::hash<KeyType>, typename KeyEqual = std::equal_to<KeyType>, typename Allocator = std::allocator<uint8_t>, template< typename > class Atom = std::atomic, class Mutex = std::mutex>

size_t folly::detail::ConcurrentHashMapSegment< KeyType, ValueType, ShardBits, HashFn, KeyEqual, Allocator, Atom, Mutex >::size_ {0}

private

Definition at line 814 of file ConcurrentHashMap-detail.h.

---

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

• proxygen/folly/folly/concurrency/detail/ConcurrentHashMap-detail.h