AtomicLinkedListTest.cpp File Reference

#include <algorithm>
#include <thread>
#include <folly/AtomicLinkedList.h>
#include <folly/portability/GTest.h>

Go to the source code of this file.

Classes
class	TestIntrusiveObject
class	TestObject

Functions
	TEST (AtomicIntrusiveLinkedList, Basic)
	TEST (AtomicIntrusiveLinkedList, ReverseSweep)
	TEST (AtomicIntrusiveLinkedList, Move)
	TEST (AtomicIntrusiveLinkedList, Stress)
	TEST (AtomicLinkedList, Basic)

Function Documentation

TEST	(	AtomicIntrusiveLinkedList	,
		Basic
	)

Definition at line 40 of file AtomicLinkedListTest.cpp.

References a, b, c, folly::AtomicIntrusiveLinkedList< T, HookMember >::empty(), EXPECT_EQ, EXPECT_FALSE, EXPECT_TRUE, TestIntrusiveObject::id(), folly::AtomicIntrusiveLinkedList< T, HookMember >::insertHead(), bm::list, folly::gen::move, and folly::AtomicIntrusiveLinkedList< T, HookMember >::sweep().

                                       {
  TestIntrusiveObject a(1), b(2), c(3);

  TestIntrusiveObject::List list;

  EXPECT_TRUE(list.empty());

  {
    EXPECT_TRUE(list.insertHead(&a));
    EXPECT_FALSE(list.insertHead(&b));

    EXPECT_FALSE(list.empty());

    size_t id = 0;
    list.sweep([&](TestIntrusiveObject* obj) mutable {
      ++id;
      EXPECT_EQ(id, obj->id());
    });

    EXPECT_TRUE(list.empty());
  }

  // Try re-inserting the same item (b) and a new item (c)
  {
    EXPECT_TRUE(list.insertHead(&b));
    EXPECT_FALSE(list.insertHead(&c));

    EXPECT_FALSE(list.empty());

    size_t id = 1;
    list.sweep([&](TestIntrusiveObject* obj) mutable {
      ++id;
      EXPECT_EQ(id, obj->id());
    });

    EXPECT_TRUE(list.empty());
  }

  TestIntrusiveObject::List movedList = std::move(list);
}

TEST	(	AtomicIntrusiveLinkedList	,
		ReverseSweep
	)

Definition at line 81 of file AtomicLinkedListTest.cpp.

References a, b, c, folly::AtomicIntrusiveLinkedList< T, HookMember >::empty(), EXPECT_EQ, EXPECT_FALSE, EXPECT_TRUE, TestIntrusiveObject::id(), folly::AtomicIntrusiveLinkedList< T, HookMember >::insertHead(), bm::list, and folly::AtomicIntrusiveLinkedList< T, HookMember >::reverseSweep().

                                              {
  TestIntrusiveObject a(1), b(2), c(3);
  TestIntrusiveObject::List list;
  list.insertHead(&a);
  list.insertHead(&b);
  list.insertHead(&c);
  size_t next_expected_id = 3;
  list.reverseSweep([&](TestIntrusiveObject* obj) {
    auto const expected = next_expected_id--;
    EXPECT_EQ(expected, obj->id());
  });
  EXPECT_TRUE(list.empty());
  // Test that we can still insert
  list.insertHead(&a);
  EXPECT_FALSE(list.empty());
  list.reverseSweep([](TestIntrusiveObject*) {});
}

TEST	(	AtomicIntrusiveLinkedList	,
		Move
	)

Definition at line 99 of file AtomicLinkedListTest.cpp.

References a, b, folly::AtomicIntrusiveLinkedList< T, HookMember >::empty(), EXPECT_EQ, EXPECT_FALSE, EXPECT_TRUE, TestIntrusiveObject::id(), folly::AtomicIntrusiveLinkedList< T, HookMember >::insertHead(), and folly::gen::move.

                                      {
  TestIntrusiveObject a(1), b(2);

  TestIntrusiveObject::List list1;

  EXPECT_TRUE(list1.insertHead(&a));
  EXPECT_FALSE(list1.insertHead(&b));

  EXPECT_FALSE(list1.empty());

  TestIntrusiveObject::List list2(std::move(list1));

  EXPECT_TRUE(list1.empty());
  EXPECT_FALSE(list2.empty());

  TestIntrusiveObject::List list3;

  EXPECT_TRUE(list3.empty());

  list3 = std::move(list2);

  EXPECT_TRUE(list2.empty());
  EXPECT_FALSE(list3.empty());

  size_t id = 0;
  list3.sweep([&](TestIntrusiveObject* obj) mutable {
    ++id;
    EXPECT_EQ(id, obj->id());
  });
}

TEST	(	AtomicIntrusiveLinkedList	,
		Stress
	)

Definition at line 130 of file AtomicLinkedListTest.cpp.

References current, EXPECT_EQ, i, TestIntrusiveObject::id(), folly::AtomicIntrusiveLinkedList< T, HookMember >::insertHead(), kNumThreads, bm::list, folly::AtomicIntrusiveLinkedList< T, HookMember >::sweep(), and threads.

                                        {
  static constexpr size_t kNumThreads = 32;
  static constexpr size_t kNumElements = 100000;

  std::vector<TestIntrusiveObject> elements;
  for (size_t i = 0; i < kNumThreads * kNumElements; ++i) {
    elements.emplace_back(i);
  }

  TestIntrusiveObject::List list;

  std::vector<std::thread> threads;
  for (size_t threadId = 0; threadId < kNumThreads; ++threadId) {
    threads.emplace_back([threadId, &list, &elements] {
      for (size_t id = 0; id < kNumElements; ++id) {
        list.insertHead(&elements[threadId + kNumThreads * id]);
      }
    });
  }

  std::vector<size_t> ids;
  TestIntrusiveObject* prev{nullptr};

  while (ids.size() < kNumThreads * kNumElements) {
    list.sweep([&](TestIntrusiveObject* current) {
      ids.push_back(current->id());

      if (prev && prev->id() % kNumThreads == current->id() % kNumThreads) {
        EXPECT_EQ(prev->id() + kNumThreads, current->id());
      }

      prev = current;
    });
  }

  std::sort(ids.begin(), ids.end());

  for (size_t i = 0; i < kNumThreads * kNumElements; ++i) {
    EXPECT_EQ(i, ids[i]);
  }

  for (auto& thread : threads) {
    thread.join();
  }
}

TEST	(	AtomicLinkedList	,
		Basic
	)

Definition at line 190 of file AtomicLinkedListTest.cpp.

References counter, EXPECT_EQ, EXPECT_TRUE, TestIntrusiveObject::id(), bm::list, and ptr.

                              {
  constexpr size_t kNumElements = 10;

  using List = folly::AtomicLinkedList<TestObject>;
  List list;

  std::shared_ptr<void> ptr = std::make_shared<int>(42);

  for (size_t id = 0; id < kNumElements; ++id) {
    list.insertHead({id, ptr});
  }

  size_t counter = 0;

  list.sweep([&](TestObject object) {
    EXPECT_EQ(counter, object.id());

    EXPECT_EQ(1 + kNumElements - counter, ptr.use_count());

    ++counter;
  });

  EXPECT_TRUE(ptr.unique());
}