ConcurrentHashMapTest.cpp File Reference

#include <folly/concurrency/ConcurrentHashMap.h>
#include <atomic>
#include <memory>
#include <thread>
#include <folly/hash/Hash.h>
#include <folly/portability/GTest.h>
#include <folly/test/DeterministicSchedule.h>

Go to the source code of this file.

Classes
struct	foo
struct	Wrapper

Macros
#define	Atom   std::atomic
#define	Mutex   std::mutex
#define	lib   std
#define	join   t.join()

Functions
	DEFINE_int64 (seed, 0,"Seed for random number generators")
	TEST (ConcurrentHashMap, MapTest)
	TEST (ConcurrentHashMap, MaxSizeTest)
	TEST (ConcurrentHashMap, MoveTest)
	TEST (ConcurrentHashMap, EmplaceTest)
	TEST (ConcurrentHashMap, MapResizeTest)
	TEST (ConcurrentHashMap, MapNoCopiesTest)
	TEST (ConcurrentHashMap, MapMovableKeysTest)
	TEST (ConcurrentHashMap, MapUpdateTest)
	TEST (ConcurrentHashMap, MapIterateTest2)
	TEST (ConcurrentHashMap, MapIterateTest)
	TEST (ConcurrentHashMap, MoveIterateAssignIterate)
	TEST (ConcurrentHashMap, EraseTest)
	TEST (ConcurrentHashMap, CopyIterator)
	TEST (ConcurrentHashMap, EraseInIterateTest)
	TEST (ConcurrentHashMap, UpdateStressTest)
	TEST (ConcurrentHashMap, EraseStressTest)
	TEST (ConcurrentHashMap, IterateStressTest)
	TEST (ConcurrentHashMap, insertStressTest)
	TEST (ConcurrentHashMap, assignStressTest)
	TEST (ConcurrentHashMap, RefcountTest)
	TEST (ConcurrentHashMap, Deletion)
	TEST (ConcurrentHashMap, DeletionWithErase)
	TEST (ConcurrentHashMap, DeletionWithIterator)
	TEST (ConcurrentHashMap, DeletionWithForLoop)
	TEST (ConcurrentHashMap, DeletionMultiple)
	TEST (ConcurrentHashMap, DeletionAssigned)
	TEST (ConcurrentHashMap, DeletionMultipleMaps)
	TEST (ConcurrentHashMap, ForEachLoop)
	TEST (ConcurrentHashMap, IteratorMove)

Macro Definition Documentation

#define Atom   std::atomic

Definition at line 301 of file ConcurrentHashMapTest.cpp.

Referenced by folly::hazptr_domain< DeterministicAtomic >::acquire_new_hprec(), array_dtor_full_tc_test(), array_test(), folly::detail::atomic_notification::atomic_notify_all_impl(), folly::test::atomic_notify_one(), folly::detail::atomic_notification::atomic_notify_one_impl(), folly::detail::atomic_notification::atomic_wait_impl(), folly::detail::atomic_notification::atomic_wait_until_impl(), auto_retire_test(), basic_holders_test(), basic_objects_test(), basic_protection_test(), burn(), cleanup_test(), copy_and_move_test(), folly::detail::LifoSemBase< BatonType, Atom >::decrOrPush(), folly::default_hazptr_domain(), folly::hazptr_deleter< T, std::default_delete< T > >::delete_obj(), destruction_test(), deterministicAtomicWaitUntilTests(), folly::hazptr_obj_linked< Atom >::downgrade_link(), folly::test::doWork(), free_function_retire_test(), folly::hazptr_default_domain_helper< std::atomic >::get(), counted_ptr_base< Atom >::getRef(), folly::detail::LifoSemNode< Handoff, Atom >::handoff(), folly::hazptr_domain_push_retired(), folly::detail::hazptr_domain_rcount_threshold(), folly::hazptr_retire(), folly::AccessSpreader< Atom >::initialize(), non_atomic< T >::is_lock_free(), lifo_test(), linked_test(), local_test(), make_counted(), folly::MPMCQueue< T, Atom, true >::maybeUpdateFromClosed(), move_test(), mt_linked_test(), folly::detail::LifoSemHead::operator!=(), folly::hazptr_root< Node, Atom >::operator()(), folly::DefaultWeightFn< T >::operator()(), counted_ptr< T, Atom >::operator==(), folly::hazptr_array< 3, Atom >::operator[](), folly::hazptr_obj< Atom >::pre_retire_check_fail(), priv_dtor_test(), List< T, Atom >::protect_all(), pthrd_mutex_(), pthrd_rwlock_reads(), Node< Atom >::ptr_next(), NodeRC< Mutable, Atom >::push_links(), NodeAuto< Atom >::push_links(), folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::Segment::push_links(), run_basic_test(), folly::test::run_basic_test(), run_basic_tests(), run_basic_thread(), folly::test::run_basic_timed_wait_tests(), run_mt_sequencer_thread(), folly::test::run_pingpong_test(), run_pingpong_test(), run_steady_clock_test(), folly::test::run_timed_wait_tmo_tests(), runNeverFailTest(), runNeverFailThread(), runNeverFailUntilThread(), folly::runReader(), runRemoteUnlock(), runTryEnqDeqThread(), folly::hazptr_holder< Atom >::set_hprec(), folly::swap(), swmr_test(), folly::TEST(), TEST(), folly::detail::atomic_notification::toCvStatus(), folly::SharedMutexImpl< ReaderPriority, Tag_, Atom, BlockImmediately, AnnotateForThreadSanitizer >::tryUnlockTokenlessSharedDeferred(), folly::LockFreeRingBuffer< T, Atom >::turn(), PosixMutex::unlock_shared(), folly::value(), virtual_test(), and folly::AtomicUnorderedInsertMap< Key, Value, Hash, KeyEqual, SkipKeyValueDeletion, Atom, IndexType, Allocator >::zeroFillSlots().

#define join   t.join()

Definition at line 304 of file ConcurrentHashMapTest.cpp.

Referenced by release_docs.WikiBrancher::__init__(), fbcode_builder.FBCodeBuilder::__repr__(), cpp.ast.Parameter::__str__(), cpp.ast.Type::__str__(), upload.SubversionVCS::_CollapseKeywords(), cpp.gmock_class::_GenerateMethods(), cpp.gmock_class::_GenerateMocks(), cpp.ast.AstBuilder::_GenerateOne(), cpp.ast.AstBuilder::_GetClass(), upload.HttpRpcServer::_GetOpener(), cpp.ast._GenericDeclaration::_TypeStringHelper(), pump.Output::Append(), pump::BeautifyCode(), pump.Token::Clone(), cpp.ast.TypeConverter::DeclarationToParts(), cpp.ast._GenericDeclaration::FullName(), gen_trace_event_constants::gen_java(), upload.GitVCS::GenerateDiff(), upload.MercurialVCS::GenerateDiff(), gen_gtest_pred_impl::GenerateHeader(), cpp.gmock_class_test.GenerateMethodsTest::GenerateMethodSource(), cpp.gmock_class_test.GenerateMocksTest::GenerateMocks(), gen_gtest_pred_impl::GenerateUnitTest(), upload.MercurialVCS::GetBaseFile(), cpp.ast.AstBuilder::handle_struct(), upload_gtest::main(), upload_gmock::main(), cpp.gmock_class::main(), make_docker_context::make_docker_context(), wangle::MultiFilePoller::registerFiles(), gtest_throw_on_failure_test::Run(), gtest_throw_on_failure_test.ThrowOnFailureTest::RunAndVerify(), gtest_break_on_failure_unittest.GTestBreakOnFailureUnitTest::RunAndVerify(), gtest_list_tests_unittest.GTestListTestsUnitTest::RunAndVerify(), upload::RunShellWithReturnCode(), folly::runWritesNeverFail(), upload::SplitPatch(), cpp.gmock_class_test.TestCase::StripLeadingWhitespace(), pump::SubString(), TEST(), TEST_F(), gtest_output_test.GTestOutputTest::testOutput(), gen_gtest_pred_impl::TestsForArity(), and cpp.ast.TypeConverter::ToType().

#define lib   std

Definition at line 303 of file ConcurrentHashMapTest.cpp.

Referenced by cmake_minimum_required(), option(), and TEST().

#define Mutex   std::mutex

Definition at line 302 of file ConcurrentHashMapTest.cpp.

Referenced by burn(), testing::internal::CheckedDowncastToActualType(), folly::test::doWork(), doWork(), runUncontended(), TEST(), folly::sync_tests::testAcquireLocked(), folly::sync_tests::testAcquireLockedWithConst(), folly::sync_tests::testBasicImpl(), folly::sync_tests::testConcurrency(), folly::sync_tests::testConstCopy(), folly::sync_tests::testDeprecated(), folly::sync_tests::testDualLocking(), folly::sync_tests::testDualLockingWithConst(), folly::sync_tests::testExchange(), folly::sync_tests::testTimed(), folly::sync_tests::testTimedShared(), folly::sync_tests::testTimedSynchronized(), folly::sync_tests::testTimedSynchronizedWithConst(), folly::sync_tests::testWithLock(), and folly::wlock().

Function Documentation

DEFINE_int64	(	seed	,
		0	,
		"Seed for random number generators"
	)

TEST	(	ConcurrentHashMap	,
		MapTest
	)

Definition at line 33 of file ConcurrentHashMapTest.cpp.

References folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::assign_if_equal(), folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::at(), folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::cend(), folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::clear(), folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::empty(), folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::erase(), EXPECT_EQ, EXPECT_FALSE, EXPECT_NE, EXPECT_TRUE, folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::find(), folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::insert(), folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::insert_or_assign(), and folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::max_load_factor().

                                 {
  ConcurrentHashMap<uint64_t, uint64_t> foomap(3);
  foomap.max_load_factor(1.05);
  EXPECT_TRUE(foomap.empty());
  EXPECT_EQ(foomap.find(1), foomap.cend());
  auto r = foomap.insert(1, 0);
  EXPECT_TRUE(r.second);
  auto r2 = foomap.insert(1, 0);
  EXPECT_EQ(r.first->second, 0);
  EXPECT_EQ(r.first->first, 1);
  EXPECT_EQ(r2.first->second, 0);
  EXPECT_EQ(r2.first->first, 1);
  EXPECT_EQ(r.first, r2.first);
  EXPECT_TRUE(r.second);
  EXPECT_FALSE(r2.second);
  EXPECT_FALSE(foomap.empty());
  EXPECT_TRUE(foomap.insert(std::make_pair(2, 0)).second);
  EXPECT_TRUE(foomap.insert_or_assign(2, 0).second);
  EXPECT_TRUE(foomap.assign_if_equal(2, 0, 3));
  EXPECT_TRUE(foomap.insert(3, 0).second);
  EXPECT_NE(foomap.find(1), foomap.cend());
  EXPECT_NE(foomap.find(2), foomap.cend());
  EXPECT_EQ(foomap.find(2)->second, 3);
  EXPECT_EQ(foomap[2], 3);
  EXPECT_EQ(foomap[20], 0);
  EXPECT_EQ(foomap.at(20), 0);
  EXPECT_FALSE(foomap.insert(1, 0).second);
  auto l = foomap.find(1);
  foomap.erase(l);
  EXPECT_FALSE(foomap.erase(1));
  EXPECT_EQ(foomap.find(1), foomap.cend());
  auto res = foomap.find(2);
  EXPECT_NE(res, foomap.cend());
  EXPECT_EQ(3, res->second);
  EXPECT_FALSE(foomap.empty());
  foomap.clear();
  EXPECT_TRUE(foomap.empty());
}

TEST	(	ConcurrentHashMap	,
		MaxSizeTest
	)

Definition at line 72 of file ConcurrentHashMapTest.cpp.

References EXPECT_TRUE, i, and folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::insert().

                                     {
  ConcurrentHashMap<uint64_t, uint64_t> foomap(2, 16);
  bool insert_failed = false;
  for (int i = 0; i < 32; i++) {
    auto res = foomap.insert(0, 0);
    if (!res.second) {
      insert_failed = true;
    }
  }
  EXPECT_TRUE(insert_failed);
}

TEST	(	ConcurrentHashMap	,
		MoveTest
	)

Definition at line 84 of file ConcurrentHashMapTest.cpp.

References folly::gen::move.

                                  {
  ConcurrentHashMap<uint64_t, uint64_t> foomap(2, 16);
  auto other = std::move(foomap);
  auto other2 = std::move(other);
  other = std::move(other2);
}

TEST	(	ConcurrentHashMap	,
		EmplaceTest
	)

Definition at line 113 of file ConcurrentHashMapTest.cpp.

References bar, foo::copied, folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::emplace(), EXPECT_EQ, folly::foo, folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::insert(), foo::moved, and folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::try_emplace().

                                     {
  ConcurrentHashMap<uint64_t, foo> foomap(200);
  foo bar; // Make sure to test copy
  foomap.insert(1, bar);
  EXPECT_EQ(foo::moved, 0);
  EXPECT_EQ(foo::copied, 1);
  foo::copied = 0;
  // The difference between emplace and try_emplace:
  // If insertion fails, try_emplace does not move its argument
  foomap.try_emplace(1, foo());
  EXPECT_EQ(foo::moved, 0);
  EXPECT_EQ(foo::copied, 0);
  foomap.emplace(1, foo());
  EXPECT_EQ(foo::moved, 1);
  EXPECT_EQ(foo::copied, 0);
}

TEST	(	ConcurrentHashMap	,
		MapResizeTest
	)

Definition at line 130 of file ConcurrentHashMapTest.cpp.

References folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::cend(), folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::erase(), EXPECT_EQ, EXPECT_FALSE, EXPECT_NE, EXPECT_TRUE, folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::find(), folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::insert(), and folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::reserve().

                                       {
  ConcurrentHashMap<uint64_t, uint64_t> foomap(2);
  EXPECT_EQ(foomap.find(1), foomap.cend());
  EXPECT_TRUE(foomap.insert(1, 0).second);
  EXPECT_TRUE(foomap.insert(2, 0).second);
  EXPECT_TRUE(foomap.insert(3, 0).second);
  EXPECT_TRUE(foomap.insert(4, 0).second);
  foomap.reserve(512);
  EXPECT_NE(foomap.find(1), foomap.cend());
  EXPECT_NE(foomap.find(2), foomap.cend());
  EXPECT_FALSE(foomap.insert(1, 0).second);
  EXPECT_TRUE(foomap.erase(1));
  EXPECT_EQ(foomap.find(1), foomap.cend());
  auto res = foomap.find(2);
  EXPECT_NE(res, foomap.cend());
  if (res != foomap.cend()) {
    EXPECT_EQ(0, res->second);
  }
}

TEST	(	ConcurrentHashMap	,
		MapNoCopiesTest
	)

Definition at line 151 of file ConcurrentHashMapTest.cpp.

References folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::cend(), EXPECT_EQ, EXPECT_NE, EXPECT_TRUE, folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::find(), i, folly::test::operator==(), and folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::try_emplace().

                                         {
  struct Uncopyable {
    int i_;
    Uncopyable(int i) {
      i_ = i;
    }
    Uncopyable(const Uncopyable& that) = delete;
    bool operator==(const Uncopyable& o) const {
      return i_ == o.i_;
    }
  };
  struct Hasher {
    size_t operator()(const Uncopyable&) const {
      return 0;
    }
  };
  ConcurrentHashMap<Uncopyable, Uncopyable, Hasher> foomap(2);
  EXPECT_TRUE(foomap.try_emplace(1, 1).second);
  EXPECT_TRUE(foomap.try_emplace(2, 2).second);
  auto res = foomap.find(2);
  EXPECT_NE(res, foomap.cend());

  EXPECT_TRUE(foomap.try_emplace(3, 3).second);

  auto res2 = foomap.find(2);
  EXPECT_NE(res2, foomap.cend());
  EXPECT_EQ(&(res->second), &(res2->second));
}

TEST	(	ConcurrentHashMap	,
		MapMovableKeysTest
	)

Definition at line 180 of file ConcurrentHashMapTest.cpp.

References folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::assign(), folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::assign_if_equal(), folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::emplace(), EXPECT_FALSE, EXPECT_TRUE, i, folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::insert(), folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::insert_or_assign(), folly::test::operator==(), and folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::try_emplace().

                                            {
  struct Movable {
    int i_;
    Movable(int i) {
      i_ = i;
    }
    Movable(const Movable&) = delete;
    Movable(Movable&& o) {
      i_ = o.i_;
      o.i_ = 0;
    }
    bool operator==(const Movable& o) const {
      return i_ == o.i_;
    }
  };
  struct Hasher {
    size_t operator()(const Movable&) const {
      return 0;
    }
  };
  ConcurrentHashMap<Movable, Movable, Hasher> foomap(2);
  EXPECT_TRUE(foomap.insert(std::make_pair(Movable(10), Movable(1))).second);
  EXPECT_TRUE(foomap.assign(Movable(10), Movable(2)));
  EXPECT_TRUE(foomap.insert(Movable(11), Movable(1)).second);
  EXPECT_TRUE(foomap.emplace(Movable(12), Movable(1)).second);
  EXPECT_TRUE(foomap.insert_or_assign(Movable(10), Movable(3)).second);
  EXPECT_TRUE(foomap.assign_if_equal(Movable(10), Movable(3), Movable(4)));
  EXPECT_FALSE(foomap.try_emplace(Movable(10), Movable(3)).second);
  EXPECT_TRUE(foomap.try_emplace(Movable(13), Movable(3)).second);
}

TEST	(	ConcurrentHashMap	,
		MapUpdateTest
	)

Definition at line 211 of file ConcurrentHashMapTest.cpp.

References folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::assign(), folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::cend(), EXPECT_EQ, EXPECT_NE, EXPECT_TRUE, folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::find(), and folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::insert().

                                       {
  ConcurrentHashMap<uint64_t, uint64_t> foomap(2);
  EXPECT_TRUE(foomap.insert(1, 10).second);
  EXPECT_TRUE(bool(foomap.assign(1, 11)));
  auto res = foomap.find(1);
  EXPECT_NE(res, foomap.cend());
  EXPECT_EQ(11, res->second);
}

TEST	(	ConcurrentHashMap	,
		MapIterateTest2
	)

Definition at line 220 of file ConcurrentHashMapTest.cpp.

References folly::test::begin(), folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::cbegin(), folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::cend(), folly::test::end(), and EXPECT_EQ.

                                         {
  ConcurrentHashMap<uint64_t, uint64_t> foomap(2);
  auto begin = foomap.cbegin();
  auto end = foomap.cend();
  EXPECT_EQ(begin, end);
}

TEST	(	ConcurrentHashMap	,
		MapIterateTest
	)

Definition at line 227 of file ConcurrentHashMapTest.cpp.

References folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::cbegin(), folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::cend(), count, EXPECT_EQ, EXPECT_NE, EXPECT_TRUE, and folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::insert().

                                        {
  ConcurrentHashMap<uint64_t, uint64_t> foomap(2);
  EXPECT_EQ(foomap.cbegin(), foomap.cend());
  EXPECT_TRUE(foomap.insert(1, 1).second);
  EXPECT_TRUE(foomap.insert(2, 2).second);
  auto iter = foomap.cbegin();
  EXPECT_NE(iter, foomap.cend());
  EXPECT_EQ(iter->first, 1);
  EXPECT_EQ(iter->second, 1);
  ++iter;
  EXPECT_NE(iter, foomap.cend());
  EXPECT_EQ(iter->first, 2);
  EXPECT_EQ(iter->second, 2);
  ++iter;
  EXPECT_EQ(iter, foomap.cend());

  int count = 0;
  for (auto it = foomap.cbegin(); it != foomap.cend(); ++it) {
    count++;
  }
  EXPECT_EQ(count, 2);
}

TEST	(	ConcurrentHashMap	,
		MoveIterateAssignIterate
	)

Definition at line 250 of file ConcurrentHashMapTest.cpp.

References folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::insert(), map(), and folly::gen::move.

                                                  {
  using Map = ConcurrentHashMap<int, int>;
  Map tmp;
  Map map{std::move(tmp)};

  map.insert(0, 0);
  ++map.cbegin();
  ConcurrentHashMap<int, int> other;
  other.insert(0, 0);
  map = std::move(other);
  ++map.cbegin();
}

TEST	(	ConcurrentHashMap	,
		EraseTest
	)

Definition at line 263 of file ConcurrentHashMapTest.cpp.

References folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::erase(), EXPECT_EQ, folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::find(), and folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::insert().

                                   {
  ConcurrentHashMap<uint64_t, uint64_t> foomap(3);
  foomap.insert(1, 0);
  auto f1 = foomap.find(1);
  EXPECT_EQ(1, foomap.erase(1));
  foomap.erase(f1);
}

TEST	(	ConcurrentHashMap	,
		CopyIterator
	)

Definition at line 271 of file ConcurrentHashMapTest.cpp.

References folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::cbegin(), folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::cend(), EXPECT_EQ, folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::insert(), and map().

                                      {
  ConcurrentHashMap<int, int> map;
  map.insert(0, 0);
  for (auto cit = map.cbegin(); cit != map.cend(); ++cit) {
    std::pair<int const, int> const ckv{0, 0};
    EXPECT_EQ(*cit, ckv);
  }
}

TEST	(	ConcurrentHashMap	,
		EraseInIterateTest
	)

Definition at line 280 of file ConcurrentHashMapTest.cpp.

References folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::cbegin(), folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::cend(), folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::erase(), EXPECT_EQ, EXPECT_GE, folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::insert(), k, folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::size(), and uint64_t.

                                            {
  ConcurrentHashMap<uint64_t, uint64_t> foomap(3);
  for (uint64_t k = 0; k < 10; ++k) {
    foomap.insert(k, k);
  }
  EXPECT_EQ(10, foomap.size());
  for (auto it = foomap.cbegin(); it != foomap.cend();) {
    if (it->second > 3) {
      it = foomap.erase(it);
    } else {
      ++it;
    }
  }
  EXPECT_EQ(4, foomap.size());
  for (auto it = foomap.cbegin(); it != foomap.cend(); ++it) {
    EXPECT_GE(3, it->second);
  }
}

TEST	(	ConcurrentHashMap	,
		UpdateStressTest
	)

Definition at line 310 of file ConcurrentHashMapTest.cpp.

References Atom, EXPECT_EQ, EXPECT_NE, EXPECT_TRUE, i, folly::hash::jenkins_rev_mix32(), folly::join(), k, m, Mutex, folly::size(), folly::pushmi::detail::t, threads, uint32_t, folly::test::DeterministicSchedule::uniform(), and val.

                                          {
  DeterministicSchedule sched(DeterministicSchedule::uniform(FLAGS_seed));

  // size must match iters for this test.
  unsigned size = 128 * 128;
  unsigned iters = size;
  ConcurrentHashMap<
      unsigned long,
      unsigned long,
      std::hash<unsigned long>,
      std::equal_to<unsigned long>,
      std::allocator<uint8_t>,
      8,
      Atom,
      Mutex>
      m(2);

  for (uint32_t i = 0; i < size; i++) {
    m.insert(i, i);
  }
  std::vector<std::thread> threads;
  unsigned int num_threads = 32;
  for (uint32_t t = 0; t < num_threads; t++) {
    threads.push_back(lib::thread([&, t]() {
      int offset = (iters * t / num_threads);
      for (uint32_t i = 0; i < iters / num_threads; i++) {
        unsigned long k = folly::hash::jenkins_rev_mix32((i + offset));
        k = k % (iters / num_threads) + offset;
        unsigned long val = 3;
        {
          auto res = m.find(k);
          EXPECT_NE(res, m.cend());
          EXPECT_EQ(k, res->second);
          auto r = m.assign(k, res->second);
          EXPECT_TRUE(r);
        }
        {
          auto res = m.find(k);
          EXPECT_NE(res, m.cend());
          EXPECT_EQ(k, res->second);
        }
        // Another random insertion to force table resizes
        val = size + i + offset;
        EXPECT_TRUE(m.insert(val, val).second);
      }
    }));
  }
  for (auto& t : threads) {
    join;
  }
}

TEST	(	ConcurrentHashMap	,
		EraseStressTest
	)

Definition at line 362 of file ConcurrentHashMapTest.cpp.

References Atom, EXPECT_EQ, EXPECT_TRUE, i, folly::hash::jenkins_rev_mix32(), folly::join(), k, m, Mutex, folly::size(), folly::pushmi::detail::t, threads, uint32_t, and folly::test::DeterministicSchedule::uniform().

                                         {
  DeterministicSchedule sched(DeterministicSchedule::uniform(FLAGS_seed));

  unsigned size = 2;
  unsigned iters = size * 128 * 2;
  ConcurrentHashMap<
      unsigned long,
      unsigned long,
      std::hash<unsigned long>,
      std::equal_to<unsigned long>,
      std::allocator<uint8_t>,
      8,
      Atom,
      Mutex>
      m(2);

  for (uint32_t i = 0; i < size; i++) {
    unsigned long k = folly::hash::jenkins_rev_mix32(i);
    m.insert(k, k);
  }
  std::vector<std::thread> threads;
  unsigned int num_threads = 32;
  for (uint32_t t = 0; t < num_threads; t++) {
    threads.push_back(lib::thread([&, t]() {
      int offset = (iters * t / num_threads);
      for (uint32_t i = 0; i < iters / num_threads; i++) {
        unsigned long k = folly::hash::jenkins_rev_mix32((i + offset));
        auto res = m.insert(k, k).second;
        if (res) {
          res = m.erase(k);
          if (!res) {
            printf("Faulre to erase thread %i val %li\n", t, k);
            exit(0);
          }
          EXPECT_TRUE(res);
        }
        res = m.insert(k, k).second;
        if (res) {
          res = bool(m.assign(k, k));
          if (!res) {
            printf("Thread %i update fail %li res%i\n", t, k, res);
            exit(0);
          }
          EXPECT_TRUE(res);
          auto result = m.find(k);
          if (result == m.cend()) {
            printf("Thread %i lookup fail %li\n", t, k);
            exit(0);
          }
          EXPECT_EQ(k, result->second);
        }
      }
    }));
  }
  for (auto& t : threads) {
    join;
  }
}

TEST	(	ConcurrentHashMap	,
		IterateStressTest
	)

Definition at line 421 of file ConcurrentHashMapTest.cpp.

References Atom, count, EXPECT_EQ, EXPECT_TRUE, i, folly::hash::jenkins_rev_mix32(), folly::join(), k, m, Mutex, folly::size(), folly::pushmi::detail::t, threads, uint32_t, and folly::test::DeterministicSchedule::uniform().

                                           {
  DeterministicSchedule sched(DeterministicSchedule::uniform(FLAGS_seed));

  unsigned size = 2;
  unsigned iters = size * 128 * 2;
  ConcurrentHashMap<
      unsigned long,
      unsigned long,
      std::hash<unsigned long>,
      std::equal_to<unsigned long>,
      std::allocator<uint8_t>,
      8,
      Atom,
      Mutex>
      m(2);

  for (uint32_t i = 0; i < size; i++) {
    unsigned long k = folly::hash::jenkins_rev_mix32(i);
    m.insert(k, k);
  }
  for (uint32_t i = 0; i < 10; i++) {
    m.insert(i, i);
  }
  std::vector<std::thread> threads;
  unsigned int num_threads = 32;
  for (uint32_t t = 0; t < num_threads; t++) {
    threads.push_back(lib::thread([&, t]() {
      int offset = (iters * t / num_threads);
      for (uint32_t i = 0; i < iters / num_threads; i++) {
        unsigned long k = folly::hash::jenkins_rev_mix32((i + offset));
        auto res = m.insert(k, k).second;
        if (res) {
          res = m.erase(k);
          if (!res) {
            printf("Faulre to erase thread %i val %li\n", t, k);
            exit(0);
          }
          EXPECT_TRUE(res);
        }
        int count = 0;
        for (auto it = m.cbegin(); it != m.cend(); ++it) {
          printf("Item is %li\n", it->first);
          if (it->first < 10) {
            count++;
          }
        }
        EXPECT_EQ(count, 10);
      }
    }));
  }
  for (auto& t : threads) {
    join;
  }
}

TEST	(	ConcurrentHashMap	,
		insertStressTest
	)

Definition at line 476 of file ConcurrentHashMapTest.cpp.

References Atom, EXPECT_FALSE, EXPECT_TRUE, i, folly::join(), m, Mutex, folly::size(), folly::pushmi::detail::t, threads, uint32_t, and folly::test::DeterministicSchedule::uniform().

                                          {
  DeterministicSchedule sched(DeterministicSchedule::uniform(FLAGS_seed));

  unsigned size = 2;
  unsigned iters = size * 64 * 4;
  ConcurrentHashMap<
      unsigned long,
      unsigned long,
      std::hash<unsigned long>,
      std::equal_to<unsigned long>,
      std::allocator<uint8_t>,
      8,
      Atom,
      Mutex>
      m(2);

  EXPECT_TRUE(m.insert(0, 0).second);
  EXPECT_FALSE(m.insert(0, 0).second);
  std::vector<std::thread> threads;
  unsigned int num_threads = 32;
  for (uint32_t t = 0; t < num_threads; t++) {
    threads.push_back(lib::thread([&, t]() {
      int offset = (iters * t / num_threads);
      for (uint32_t i = 0; i < iters / num_threads; i++) {
        auto var = offset + i + 1;
        EXPECT_TRUE(m.insert(var, var).second);
        EXPECT_FALSE(m.insert(0, 0).second);
      }
    }));
  }
  for (auto& t : threads) {
    join;
  }
}

TEST	(	ConcurrentHashMap	,
		assignStressTest
	)

Definition at line 511 of file ConcurrentHashMapTest.cpp.

References a, Atom, b, check(), EXPECT_EQ, EXPECT_NE, i, folly::join(), m, Mutex, folly::size(), folly::pushmi::detail::t, threads, uint32_t, uint64_t, folly::test::DeterministicSchedule::uniform(), and v.

                                          {
  DeterministicSchedule sched(DeterministicSchedule::uniform(FLAGS_seed));

  unsigned size = 2;
  unsigned iters = size * 64 * 4;
  struct big_value {
    uint64_t v1;
    uint64_t v2;
    uint64_t v3;
    uint64_t v4;
    uint64_t v5;
    uint64_t v6;
    uint64_t v7;
    uint64_t v8;
    void set(uint64_t v) {
      v1 = v2 = v3 = v4 = v5 = v6 = v7 = v8 = v;
    }
    void check() const {
      auto v = v1;
      EXPECT_EQ(v, v8);
      EXPECT_EQ(v, v7);
      EXPECT_EQ(v, v6);
      EXPECT_EQ(v, v5);
      EXPECT_EQ(v, v4);
      EXPECT_EQ(v, v3);
      EXPECT_EQ(v, v2);
    }
  };
  ConcurrentHashMap<
      unsigned long,
      big_value,
      std::hash<unsigned long>,
      std::equal_to<unsigned long>,
      std::allocator<uint8_t>,
      8,
      Atom,
      Mutex>
      m(2);

  for (uint32_t i = 0; i < iters; i++) {
    big_value a;
    a.set(i);
    m.insert(i, a);
  }

  std::vector<std::thread> threads;
  unsigned int num_threads = 32;
  for (uint32_t t = 0; t < num_threads; t++) {
    threads.push_back(lib::thread([&]() {
      for (uint32_t i = 0; i < iters; i++) {
        auto res = m.find(i);
        EXPECT_NE(res, m.cend());
        res->second.check();
        big_value b;
        b.set(res->second.v1 + 1);
        m.assign(i, b);
      }
    }));
  }
  for (auto& t : threads) {
    join;
  }
}

TEST	(	ConcurrentHashMap	,
		RefcountTest
	)

Definition at line 575 of file ConcurrentHashMapTest.cpp.

References i, folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::insert(), folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::insert_or_assign(), int32_t, and uint64_t.

                                      {
  struct badhash {
    size_t operator()(uint64_t) const {
      return 0;
    }
  };
  ConcurrentHashMap<
      uint64_t,
      uint64_t,
      badhash,
      std::equal_to<uint64_t>,
      std::allocator<uint8_t>,
      0>
      foomap(3);
  foomap.insert(0, 0);
  foomap.insert(1, 1);
  foomap.insert(2, 2);
  for (int32_t i = 0; i < 300; ++i) {
    foomap.insert_or_assign(1, i);
  }
}

TEST	(	ConcurrentHashMap	,
		Deletion
	)

Definition at line 606 of file ConcurrentHashMapTest.cpp.

References EXPECT_TRUE, folly::hazptr_cleanup(), folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::insert(), and map().

                                  {
  bool del{false};

  {
    ConcurrentHashMap<int, std::shared_ptr<Wrapper>> map;

    map.insert(0, std::make_shared<Wrapper>(del));
  }

  folly::hazptr_cleanup();

  EXPECT_TRUE(del);
}

TEST	(	ConcurrentHashMap	,
		DeletionWithErase
	)

Definition at line 620 of file ConcurrentHashMapTest.cpp.

References folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::erase(), EXPECT_TRUE, folly::hazptr_cleanup(), folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::insert(), and map().

                                           {
  bool del{false};

  {
    ConcurrentHashMap<int, std::shared_ptr<Wrapper>> map;

    map.insert(0, std::make_shared<Wrapper>(del));
    map.erase(0);
  }

  folly::hazptr_cleanup();

  EXPECT_TRUE(del);
}

TEST	(	ConcurrentHashMap	,
		DeletionWithIterator
	)

Definition at line 635 of file ConcurrentHashMapTest.cpp.

References folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::erase(), EXPECT_TRUE, folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::find(), folly::hazptr_cleanup(), folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::insert(), and map().

                                              {
  bool del{false};

  {
    ConcurrentHashMap<int, std::shared_ptr<Wrapper>> map;

    map.insert(0, std::make_shared<Wrapper>(del));
    auto it = map.find(0);
    map.erase(it);
  }

  folly::hazptr_cleanup();

  EXPECT_TRUE(del);
}

TEST	(	ConcurrentHashMap	,
		DeletionWithForLoop
	)

Definition at line 651 of file ConcurrentHashMapTest.cpp.

References folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::cbegin(), folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::cend(), EXPECT_EQ, EXPECT_TRUE, folly::hazptr_cleanup(), folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::insert(), and map().

                                             {
  bool del{false};

  {
    ConcurrentHashMap<int, std::shared_ptr<Wrapper>> map;

    map.insert(0, std::make_shared<Wrapper>(del));
    for (auto it = map.cbegin(); it != map.cend(); ++it) {
      EXPECT_EQ(it->first, 0);
    }
  }

  folly::hazptr_cleanup();

  EXPECT_TRUE(del);
}

TEST	(	ConcurrentHashMap	,
		DeletionMultiple
	)

Definition at line 668 of file ConcurrentHashMapTest.cpp.

References EXPECT_TRUE, folly::hazptr_cleanup(), folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::insert(), and map().

                                          {
  bool del1{false}, del2{false};

  {
    ConcurrentHashMap<int, std::shared_ptr<Wrapper>> map;

    map.insert(0, std::make_shared<Wrapper>(del1));
    map.insert(1, std::make_shared<Wrapper>(del2));
  }

  folly::hazptr_cleanup();

  EXPECT_TRUE(del1);
  EXPECT_TRUE(del2);
}

TEST	(	ConcurrentHashMap	,
		DeletionAssigned
	)

Definition at line 684 of file ConcurrentHashMapTest.cpp.

References EXPECT_TRUE, folly::hazptr_cleanup(), folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::insert(), folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::insert_or_assign(), and map().

                                          {
  bool del1{false}, del2{false};

  {
    ConcurrentHashMap<int, std::shared_ptr<Wrapper>> map;

    map.insert(0, std::make_shared<Wrapper>(del1));
    map.insert_or_assign(0, std::make_shared<Wrapper>(del2));
  }

  folly::hazptr_cleanup();

  EXPECT_TRUE(del1);
  EXPECT_TRUE(del2);
}

TEST	(	ConcurrentHashMap	,
		DeletionMultipleMaps
	)

Definition at line 700 of file ConcurrentHashMapTest.cpp.

References EXPECT_TRUE, folly::hazptr_cleanup(), and folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::insert().

                                              {
  bool del1{false}, del2{false};

  {
    ConcurrentHashMap<int, std::shared_ptr<Wrapper>> map1;
    ConcurrentHashMap<int, std::shared_ptr<Wrapper>> map2;

    map1.insert(0, std::make_shared<Wrapper>(del1));
    map2.insert(0, std::make_shared<Wrapper>(del2));
  }

  folly::hazptr_cleanup();

  EXPECT_TRUE(del1);
  EXPECT_TRUE(del2);
}

TEST	(	ConcurrentHashMap	,
		ForEachLoop
	)

Definition at line 717 of file ConcurrentHashMapTest.cpp.

References EXPECT_EQ, folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::insert(), and map().

                                     {
  ConcurrentHashMap<int, int> map;
  map.insert(1, 2);
  size_t iters = 0;
  for (const auto& kv : map) {
    EXPECT_EQ(kv.first, 1);
    EXPECT_EQ(kv.second, 2);
    ++iters;
  }
  EXPECT_EQ(iters, 1);
}

TEST	(	ConcurrentHashMap	,
		IteratorMove
	)

Definition at line 729 of file ConcurrentHashMapTest.cpp.

References ASSERT_EQ, folly::foo, foo2(), gen_gtest_pred_impl::Iter(), k, map(), and folly::gen::move.

                                      {
  using CHM = ConcurrentHashMap<int, int>;
  using Iter = CHM::ConstIterator;
  struct Foo {
    Iter it;
    explicit Foo(Iter&& it_) : it(std::move(it_)) {}
    Foo(Foo&&) = default;
    Foo& operator=(Foo&&) = default;
  };
  CHM map;
  int k = 111;
  int v = 999999;
  map.insert(k, v);
  Foo foo(map.find(k));
  ASSERT_EQ(foo.it->second, v);
  Foo foo2(map.find(0));
  foo2 = std::move(foo);
  ASSERT_EQ(foo2.it->second, v);
}