zircon/system/ulib/fbl/test/intrusive_singly_linked_list_tests.cc

// Copyright 2016 The Fuchsia Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include <fbl/intrusive_single_list.h>
#include <fbl/tests/intrusive_containers/intrusive_singly_linked_list_checker.h>
#include <fbl/tests/intrusive_containers/sequence_container_test_environment.h>
#include <fbl/tests/intrusive_containers/test_thunks.h>
#include <zxtest/zxtest.h>

namespace fbl {
namespace tests {
namespace intrusive_containers {

template <typename ContainerStateType>
struct OtherListTraits {
  using PtrTraits = typename ContainerStateType::PtrTraits;
  static ContainerStateType& node_state(typename PtrTraits::RefType obj) {
    return obj.other_container_state_;
  }
};

template <typename PtrType, NodeOptions kNodeOptions = NodeOptions::None>
class SLLTraits {
 public:
  // clang-format off
  using TestObjBaseType         = TestObjBase;

  using ContainerType           = SinglyLinkedList<PtrType>;
  using ContainableBaseClass    = SinglyLinkedListable<PtrType, kNodeOptions>;
  using ContainerStateType      = SinglyLinkedListNodeState<PtrType, kNodeOptions>;

  using OtherContainerStateType = ContainerStateType;
  using OtherContainerTraits    = OtherListTraits<OtherContainerStateType>;
  using OtherContainerType      = SinglyLinkedListCustomTraits<PtrType, OtherContainerTraits>;
  // clang-format on

  struct Tag1 {};
  struct Tag2 {};
  struct Tag3 {};

  using TaggedContainableBaseClasses =
      fbl::ContainableBaseClasses<TaggedSinglyLinkedListable<PtrType, Tag1>,
                                  TaggedSinglyLinkedListable<PtrType, Tag2>,
                                  TaggedSinglyLinkedListable<PtrType, Tag3>>;

  using TaggedType1 = TaggedSinglyLinkedList<PtrType, Tag1>;
  using TaggedType2 = TaggedSinglyLinkedList<PtrType, Tag2>;
  using TaggedType3 = TaggedSinglyLinkedList<PtrType, Tag3>;
};

// Just a sanity check so we know our metaprogramming nonsense is
// doing what we expect:
static_assert(
    std::is_same_v<typename SLLTraits<int*>::TaggedContainableBaseClasses::TagTypes,
                   std::tuple<typename SLLTraits<int*>::Tag1, typename SLLTraits<int*>::Tag2,
                              typename SLLTraits<int*>::Tag3>>);

// Negative compilation tests which make sure that we don't accidentally
// mismatch pointer types between the node and the container.
TEST(SinglyLinkedListTest, MismatchedPointerType) {
  struct Obj {
    fbl::SinglyLinkedListNodeState<Obj*> sll_node_state_;
  };
#if TEST_WILL_NOT_COMPILE || 0
  [[maybe_unused]] fbl::SinglyLinkedList<std::unique_ptr<Obj>> list;
#endif
}

// Negative compilation test which make sure that we cannot try to use a node
// flagged with AllowRemoveFromContainer with a sized list.
TEST(SinglyLinkedListTest, NoRemoveFromContainer) {
  struct Obj : public SinglyLinkedListable<Obj*, NodeOptions::AllowRemoveFromContainer> {};
#if TEST_WILL_NOT_COMPILE || 0
  [[maybe_unused]] fbl::SinglyLinkedList<Obj*> list;
#endif
}

// clang-format off
DEFINE_TEST_OBJECTS(SLL);
using UMTE   = DEFINE_TEST_THUNK(Sequence, SLL, Unmanaged);
using UPDDTE = DEFINE_TEST_THUNK(Sequence, SLL, UniquePtrDefaultDeleter);
using UPCDTE = DEFINE_TEST_THUNK(Sequence, SLL, UniquePtrCustomDeleter);
using RPTE   = DEFINE_TEST_THUNK(Sequence, SLL, RefPtr);
VERIFY_CONTAINER_SIZES(SLL, sizeof(void*));

// Versions of the test objects which support clear_unsafe.
template <typename PtrType>
using CU_SLLTraits = SLLTraits<PtrType, fbl::NodeOptions::AllowClearUnsafe>;
DEFINE_TEST_OBJECTS(CU_SLL);
using CU_UMTE   = DEFINE_TEST_THUNK(Sequence, CU_SLL, Unmanaged);
using CU_UPDDTE = DEFINE_TEST_THUNK(Sequence, CU_SLL, UniquePtrDefaultDeleter);
VERIFY_CONTAINER_SIZES(CU_SLL, sizeof(void*));

//////////////////////////////////////////
// General container specific tests.
//////////////////////////////////////////
RUN_ZXTEST(SinglyLinkedListTest, UMTE,    Clear)
RUN_ZXTEST(SinglyLinkedListTest, UPDDTE,  Clear)
RUN_ZXTEST(SinglyLinkedListTest, UPCDTE,  Clear)
RUN_ZXTEST(SinglyLinkedListTest, RPTE,    Clear)

#if TEST_WILL_NOT_COMPILE || 0
// Won't compile because node lacks AllowClearUnsafe option.
RUN_ZXTEST(SinglyLinkedListTest, UMTE,    ClearUnsafe)
RUN_ZXTEST(SinglyLinkedListTest, UPDDTE,  ClearUnsafe)
RUN_ZXTEST(SinglyLinkedListTest, UPCDTE,  ClearUnsafe)
RUN_ZXTEST(SinglyLinkedListTest, RPTE,    ClearUnsafe)
#endif

#if TEST_WILL_NOT_COMPILE || 0
// Won't compile because pointer type is managed.
RUN_ZXTEST(SinglyLinkedListTest, CU_UPDDTE,  ClearUnsafe)
#endif

RUN_ZXTEST(SinglyLinkedListTest, CU_UMTE, ClearUnsafe)

RUN_ZXTEST(SinglyLinkedListTest, UMTE,    IsEmpty)
RUN_ZXTEST(SinglyLinkedListTest, UPDDTE,  IsEmpty)
RUN_ZXTEST(SinglyLinkedListTest, UPCDTE,  IsEmpty)
RUN_ZXTEST(SinglyLinkedListTest, RPTE,    IsEmpty)

RUN_ZXTEST(SinglyLinkedListTest, UMTE,    Iterate)
RUN_ZXTEST(SinglyLinkedListTest, UPDDTE,  Iterate)
RUN_ZXTEST(SinglyLinkedListTest, UPCDTE,  Iterate)
RUN_ZXTEST(SinglyLinkedListTest, RPTE,    Iterate)

// SinglyLinkedLists cannot perform direct erase operations, nor can they erase
// using an iterator.
#if TEST_WILL_NOT_COMPILE || 0
RUN_ZXTEST(SinglyLinkedListTest, UMTE,    IterErase)
RUN_ZXTEST(SinglyLinkedListTest, UPDDTE,  IterErase)
RUN_ZXTEST(SinglyLinkedListTest, UPCDTE,  IterErase)
RUN_ZXTEST(SinglyLinkedListTest, RPTE,    IterErase)

RUN_ZXTEST(SinglyLinkedListTest, UMTE,    DirectErase)
RUN_ZXTEST(SinglyLinkedListTest, UPDDTE,  DirectErase)
RUN_ZXTEST(SinglyLinkedListTest, UPCDTE,  DirectErase)
RUN_ZXTEST(SinglyLinkedListTest, RPTE,    DirectErase)
#endif

RUN_ZXTEST(SinglyLinkedListTest, UMTE,    MakeIterator)
RUN_ZXTEST(SinglyLinkedListTest, UPDDTE,  MakeIterator)
RUN_ZXTEST(SinglyLinkedListTest, UPCDTE,  MakeIterator)
RUN_ZXTEST(SinglyLinkedListTest, RPTE,    MakeIterator)

// SinglyLinkedLists cannot iterate backwards.
#if TEST_WILL_NOT_COMPILE || 0
RUN_ZXTEST(SinglyLinkedListTest, UMTE,    ReverseIterErase)
RUN_ZXTEST(SinglyLinkedListTest, UPDDTE,  ReverseIterErase)
RUN_ZXTEST(SinglyLinkedListTest, UPCDTE,  ReverseIterErase)
RUN_ZXTEST(SinglyLinkedListTest, RPTE,    ReverseIterErase)

RUN_ZXTEST(SinglyLinkedListTest, UMTE,    ReverseIterate)
RUN_ZXTEST(SinglyLinkedListTest, UPDDTE,  ReverseIterate)
RUN_ZXTEST(SinglyLinkedListTest, UPCDTE,  ReverseIterate)
RUN_ZXTEST(SinglyLinkedListTest, RPTE,    ReverseIterate)
#endif

RUN_ZXTEST(SinglyLinkedListTest, UMTE,    Swap)
RUN_ZXTEST(SinglyLinkedListTest, UPDDTE,  Swap)
RUN_ZXTEST(SinglyLinkedListTest, UPCDTE,  Swap)
RUN_ZXTEST(SinglyLinkedListTest, RPTE,    Swap)

RUN_ZXTEST(SinglyLinkedListTest, UMTE,    RvalueOps)
RUN_ZXTEST(SinglyLinkedListTest, UPDDTE,  RvalueOps)
RUN_ZXTEST(SinglyLinkedListTest, UPCDTE,  RvalueOps)
RUN_ZXTEST(SinglyLinkedListTest, RPTE,    RvalueOps)

RUN_ZXTEST(SinglyLinkedListTest, UPDDTE,  Scope)
RUN_ZXTEST(SinglyLinkedListTest, UPCDTE,  Scope)
RUN_ZXTEST(SinglyLinkedListTest, RPTE,    Scope)

RUN_ZXTEST(SinglyLinkedListTest, UMTE,    TwoContainer)
#if TEST_WILL_NOT_COMPILE || 0
RUN_ZXTEST(SinglyLinkedListTest, UPDDTE,  TwoContainer)
RUN_ZXTEST(SinglyLinkedListTest, UPCDTE,  TwoContainer)
#endif
RUN_ZXTEST(SinglyLinkedListTest, RPTE,    TwoContainer)

RUN_ZXTEST(SinglyLinkedListTest, UMTE,    ThreeContainerHelper)
#if TEST_WILL_NOT_COMPILE || 0
RUN_ZXTEST(SinglyLinkedListTest, UPDDTE,  ThreeContainerHelper)
RUN_ZXTEST(SinglyLinkedListTest, UPCDTE,  ThreeContainerHelper)
#endif
RUN_ZXTEST(SinglyLinkedListTest, RPTE,    ThreeContainerHelper)

RUN_ZXTEST(SinglyLinkedListTest, UMTE,    IterCopyPointer)
#if TEST_WILL_NOT_COMPILE || 0
RUN_ZXTEST(SinglyLinkedListTest, UPDDTE,  IterCopyPointer)
RUN_ZXTEST(SinglyLinkedListTest, UPCDTE,  IterCopyPointer)
#endif
RUN_ZXTEST(SinglyLinkedListTest, RPTE,    IterCopyPointer)

RUN_ZXTEST(SinglyLinkedListTest, UMTE,    EraseIf)
RUN_ZXTEST(SinglyLinkedListTest, UPDDTE,  EraseIf)
RUN_ZXTEST(SinglyLinkedListTest, UPCDTE,  EraseIf)
RUN_ZXTEST(SinglyLinkedListTest, RPTE,    EraseIf)

RUN_ZXTEST(SinglyLinkedListTest, UMTE,    FindIf)
RUN_ZXTEST(SinglyLinkedListTest, UPDDTE,  FindIf)
RUN_ZXTEST(SinglyLinkedListTest, UPCDTE,  FindIf)
RUN_ZXTEST(SinglyLinkedListTest, RPTE,    FindIf)

//////////////////////////////////////////
// Sequence container specific tests.
//////////////////////////////////////////
RUN_ZXTEST(SinglyLinkedListTest, UMTE,    PushFront)
RUN_ZXTEST(SinglyLinkedListTest, UPDDTE,  PushFront)
RUN_ZXTEST(SinglyLinkedListTest, UPCDTE,  PushFront)
RUN_ZXTEST(SinglyLinkedListTest, RPTE,    PushFront)

RUN_ZXTEST(SinglyLinkedListTest, UMTE,    PopFront)
RUN_ZXTEST(SinglyLinkedListTest, UPDDTE,  PopFront)
RUN_ZXTEST(SinglyLinkedListTest, UPCDTE,  PopFront)
RUN_ZXTEST(SinglyLinkedListTest, RPTE,    PopFront)

// Singly linked lists cannot push/pop to/from the back
#if TEST_WILL_NOT_COMPILE || 0
RUN_ZXTEST(SinglyLinkedListTest, UMTE,    PushBack)
RUN_ZXTEST(SinglyLinkedListTest, UPDDTE,  PushBack)
RUN_ZXTEST(SinglyLinkedListTest, UPCDTE,  PushBack)
RUN_ZXTEST(SinglyLinkedListTest, RPTE,    PushBack)

RUN_ZXTEST(SinglyLinkedListTest, UMTE,    PopBack)
RUN_ZXTEST(SinglyLinkedListTest, UPDDTE,  PopBack)
RUN_ZXTEST(SinglyLinkedListTest, UPCDTE,  PopBack)
RUN_ZXTEST(SinglyLinkedListTest, RPTE,    PopBack)
#endif

RUN_ZXTEST(SinglyLinkedListTest, UMTE,    SeqIterate)
RUN_ZXTEST(SinglyLinkedListTest, UPDDTE,  SeqIterate)
RUN_ZXTEST(SinglyLinkedListTest, UPCDTE,  SeqIterate)
RUN_ZXTEST(SinglyLinkedListTest, RPTE,    SeqIterate)

// SinglyLinkedLists cannot iterate backwards.
#if TEST_WILL_NOT_COMPILE || 0
RUN_ZXTEST(SinglyLinkedListTest, UMTE,    SeqReverseIterate)
RUN_ZXTEST(SinglyLinkedListTest, UPDDTE,  SeqReverseIterate)
RUN_ZXTEST(SinglyLinkedListTest, UPCDTE,  SeqReverseIterate)
RUN_ZXTEST(SinglyLinkedListTest, RPTE,    SeqReverseIterate)
#endif

RUN_ZXTEST(SinglyLinkedListTest, UMTE,    EraseNext)
RUN_ZXTEST(SinglyLinkedListTest, UPDDTE,  EraseNext)
RUN_ZXTEST(SinglyLinkedListTest, UPCDTE,  EraseNext)
RUN_ZXTEST(SinglyLinkedListTest, RPTE,    EraseNext)

RUN_ZXTEST(SinglyLinkedListTest, UMTE,    InsertAfter)
RUN_ZXTEST(SinglyLinkedListTest, UPDDTE,  InsertAfter)
RUN_ZXTEST(SinglyLinkedListTest, UPCDTE,  InsertAfter)
RUN_ZXTEST(SinglyLinkedListTest, RPTE,    InsertAfter)

// SinglyLinkedLists cannot perform inserts-before operations, either with an
// iterator or with a direct object reference.
#if TEST_WILL_NOT_COMPILE || 0
RUN_ZXTEST(SinglyLinkedListTest, UMTE,    Insert)
RUN_ZXTEST(SinglyLinkedListTest, UPDDTE,  Insert)
RUN_ZXTEST(SinglyLinkedListTest, UPCDTE,  Insert)
RUN_ZXTEST(SinglyLinkedListTest, RPTE,    Insert)

RUN_ZXTEST(SinglyLinkedListTest, UMTE,    DirectInsert)
RUN_ZXTEST(SinglyLinkedListTest, UPDDTE,  DirectInsert)
RUN_ZXTEST(SinglyLinkedListTest, UPCDTE,  DirectInsert)
RUN_ZXTEST(SinglyLinkedListTest, RPTE,    DirectInsert)
#endif

// SinglyLinkedLists cannot perform splice operations.
#if TEST_WILL_NOT_COMPILE || 0
RUN_ZXTEST(SinglyLinkedListTest, UMTE,    Splice)
RUN_ZXTEST(SinglyLinkedListTest, UPDDTE,  Splice)
RUN_ZXTEST(SinglyLinkedListTest, UPCDTE,  Splice)
RUN_ZXTEST(SinglyLinkedListTest, RPTE,    Splice)
#endif

RUN_ZXTEST(SinglyLinkedListTest, UMTE,    SplitAfter)
RUN_ZXTEST(SinglyLinkedListTest, UPDDTE,  SplitAfter)
RUN_ZXTEST(SinglyLinkedListTest, UPCDTE,  SplitAfter)
RUN_ZXTEST(SinglyLinkedListTest, RPTE,    SplitAfter)

RUN_ZXTEST(SinglyLinkedListTest, UMTE,    ReplaceIfCopy)
#if TEST_WILL_NOT_COMPILE || 0
RUN_ZXTEST(SinglyLinkedListTest, UPDDTE,  ReplaceIfCopy)
RUN_ZXTEST(SinglyLinkedListTest, UPCDTE,  ReplaceIfCopy)
#endif
RUN_ZXTEST(SinglyLinkedListTest, RPTE,    ReplaceIfCopy)

RUN_ZXTEST(SinglyLinkedListTest, UMTE,    ReplaceIfMove)
RUN_ZXTEST(SinglyLinkedListTest, UPDDTE,  ReplaceIfMove)
RUN_ZXTEST(SinglyLinkedListTest, UPCDTE,  ReplaceIfMove)
RUN_ZXTEST(SinglyLinkedListTest, RPTE,    ReplaceIfMove)
// clang-format on

}  // namespace intrusive_containers
}  // namespace tests
}  // namespace fbl