TestLinkedList.cpp

mozilla-central/mfbt/tests/TestLinkedList.cpp (file symbol)

Enable keyboard shortcuts

Source code

File a bug in Core :: MFBT

Revision control

Copy as Markdown

Other Tools

/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */

/* vim: set ts=8 sts=2 et sw=2 tw=80: */

/* This Source Code Form is subject to the terms of the Mozilla Public

 * License, v. 2.0. If a copy of the MPL was not distributed with this file,

 * You can obtain one at http://mozilla.org/MPL/2.0/. */

#include "mozilla/Assertions.h"

#include "mozilla/LinkedList.h"

using mozilla::AutoCleanLinkedList;

using mozilla::LinkedList;

using mozilla::LinkedListElement;

struct SomeClass : public LinkedListElement<SomeClass> {

  unsigned int mValue;

  explicit SomeClass(int aValue = 0) : mValue(aValue) {}

  SomeClass(SomeClass&&) = default;

  SomeClass& operator=(SomeClass&&) = default;

  void incr() { ++mValue; }

};

template <size_t N>

static void CheckListValues(LinkedList<SomeClass>& list,

                            unsigned int (&values)[N]) {

  size_t count = 0;

  for (SomeClass* x : list) {

    MOZ_RELEASE_ASSERT(x->mValue == values[count]);

    ++count;

  MOZ_RELEASE_ASSERT(count == N);

static void TestList() {

  LinkedList<SomeClass> list;

  SomeClass one(1), two(2), three(3);

  MOZ_RELEASE_ASSERT(list.isEmpty());

  MOZ_RELEASE_ASSERT(list.length() == 0);

  MOZ_RELEASE_ASSERT(!list.getFirst());

  MOZ_RELEASE_ASSERT(!list.getLast());

  MOZ_RELEASE_ASSERT(!list.popFirst());

  MOZ_RELEASE_ASSERT(!list.popLast());

  for (SomeClass* x : list) {

    MOZ_RELEASE_ASSERT(x);

    MOZ_RELEASE_ASSERT(false);

  list.insertFront(&one);

    unsigned int check[]{1};

    CheckListValues(list, check);

  MOZ_RELEASE_ASSERT(one.isInList());

  MOZ_RELEASE_ASSERT(!two.isInList());

  MOZ_RELEASE_ASSERT(!three.isInList());

  MOZ_RELEASE_ASSERT(list.contains(&one));

  MOZ_RELEASE_ASSERT(!list.contains(&two));

  MOZ_RELEASE_ASSERT(!list.contains(&three));

  MOZ_RELEASE_ASSERT(!list.isEmpty());

  MOZ_RELEASE_ASSERT(list.length() == 1);

  MOZ_RELEASE_ASSERT(list.getFirst()->mValue == 1);

  MOZ_RELEASE_ASSERT(list.getLast()->mValue == 1);

  list.insertFront(&two);

    unsigned int check[]{2, 1};

    CheckListValues(list, check);

  MOZ_RELEASE_ASSERT(list.length() == 2);

  MOZ_RELEASE_ASSERT(list.getFirst()->mValue == 2);

  MOZ_RELEASE_ASSERT(list.getLast()->mValue == 1);

  list.insertBack(&three);

    unsigned int check[]{2, 1, 3};

    CheckListValues(list, check);

  MOZ_RELEASE_ASSERT(list.length() == 3);

  MOZ_RELEASE_ASSERT(list.getFirst()->mValue == 2);

  MOZ_RELEASE_ASSERT(list.getLast()->mValue == 3);

  one.removeFrom(list);

    unsigned int check[]{2, 3};

    CheckListValues(list, check);

  three.setPrevious(&one);

    unsigned int check[]{2, 1, 3};

    CheckListValues(list, check);

  three.removeFrom(list);

    unsigned int check[]{2, 1};

    CheckListValues(list, check);

  two.setPrevious(&three);

    unsigned int check[]{3, 2, 1};

    CheckListValues(list, check);

  three.removeFrom(list);

    unsigned int check[]{2, 1};

    CheckListValues(list, check);

  two.setNext(&three);

    unsigned int check[]{2, 3, 1};

    CheckListValues(list, check);

  one.remove();

    unsigned int check[]{2, 3};

    CheckListValues(list, check);

  two.remove();

    unsigned int check[]{3};

    CheckListValues(list, check);

  three.setPrevious(&two);

    unsigned int check[]{2, 3};

    CheckListValues(list, check);

  three.remove();

    unsigned int check[]{2};

    CheckListValues(list, check);

  two.remove();

  list.insertBack(&three);

    unsigned int check[]{3};

    CheckListValues(list, check);

  list.insertFront(&two);

    unsigned int check[]{2, 3};

    CheckListValues(list, check);

  for (SomeClass* x : list) {

    x->incr();

  MOZ_RELEASE_ASSERT(list.length() == 2);

  MOZ_RELEASE_ASSERT(list.getFirst() == &two);

  MOZ_RELEASE_ASSERT(list.getLast() == &three);

  MOZ_RELEASE_ASSERT(list.getFirst()->mValue == 3);

  MOZ_RELEASE_ASSERT(list.getLast()->mValue == 4);

  const LinkedList<SomeClass>& constList = list;

  for (const SomeClass* x : constList) {

    MOZ_RELEASE_ASSERT(x);

static void TestExtendLists() {

  AutoCleanLinkedList<SomeClass> list1, list2;

  constexpr unsigned int N = 5;

  for (unsigned int i = 0; i < N; ++i) {

    list1.insertBack(new SomeClass(static_cast<int>(i)));

    AutoCleanLinkedList<SomeClass> singleItemList;

    singleItemList.insertFront(new SomeClass(static_cast<int>(i + N)));

    list2.extendBack(std::move(singleItemList));

  // list1 = { 0, 1, 2, 3, 4 }

  // list2 = { 5, 6, 7, 8, 9 }

  list1.extendBack(AutoCleanLinkedList<SomeClass>());

  list1.extendBack(std::move(list2));

  // Make sure the line above has properly emptied |list2|.

  MOZ_RELEASE_ASSERT(list2.isEmpty());  // NOLINT(bugprone-use-after-move)

  size_t i = 0;

  for (SomeClass* x : list1) {

    MOZ_RELEASE_ASSERT(x->mValue == i++);

  MOZ_RELEASE_ASSERT(i == N * 2);

void TestSplice() {

  AutoCleanLinkedList<SomeClass> list1, list2;

  for (unsigned int i = 1; i <= 5; ++i) {

    list1.insertBack(new SomeClass(static_cast<int>(i)));

    AutoCleanLinkedList<SomeClass> singleItemList;

    singleItemList.insertFront(new SomeClass(static_cast<int>(i * 10)));

    list2.extendBack(std::move(singleItemList));

  // list1 = { 1, 2, 3, 4, 5 }

  // list2 = { 10, 20, 30, 40, 50 }

  list1.splice(2, list2, 0, 5);

  MOZ_RELEASE_ASSERT(list2.isEmpty());

  unsigned int kExpected1[]{1, 2, 10, 20, 30, 40, 50, 3, 4, 5};

  CheckListValues(list1, kExpected1);

  // Since aSourceLen=100 exceeds list1's end, the function transfers

  // three items [3, 4, 5].

  list2.splice(0, list1, 7, 100);

  unsigned int kExpected2[]{1, 2, 10, 20, 30, 40, 50};

  unsigned int kExpected3[]{3, 4, 5};

  CheckListValues(list1, kExpected2);

  CheckListValues(list2, kExpected3);

  // Since aDestinationPos=100 exceeds list2's end, the function transfers

  // items to list2's end.

  list2.splice(100, list1, 1, 1);

  unsigned int kExpected4[]{1, 10, 20, 30, 40, 50};

  unsigned int kExpected5[]{3, 4, 5, 2};

  CheckListValues(list1, kExpected4);

  CheckListValues(list2, kExpected5);

static void TestMove() {

  auto MakeSomeClass = [](unsigned int aValue) -> SomeClass {

    return SomeClass(aValue);

};

  LinkedList<SomeClass> list1;

  // Test move constructor for LinkedListElement.

  SomeClass c1(MakeSomeClass(1));

  list1.insertBack(&c1);

  // Test move assignment for LinkedListElement from an element not in a

  // list.

  SomeClass c2;

  c2 = MakeSomeClass(2);

  list1.insertBack(&c2);

  // Test move assignment of LinkedListElement from an element already in a

  // list.

  SomeClass c3;

  c3 = std::move(c2);

  MOZ_RELEASE_ASSERT(!c2.isInList());

  MOZ_RELEASE_ASSERT(c3.isInList());

  // Test move constructor for LinkedList.

  LinkedList<SomeClass> list2(std::move(list1));

    unsigned int check[]{1, 2};

    CheckListValues(list2, check);

  MOZ_RELEASE_ASSERT(list1.isEmpty());

  // Test move assignment for LinkedList.

  LinkedList<SomeClass> list3;

  list3 = std::move(list2);

    unsigned int check[]{1, 2};

    CheckListValues(list3, check);

  MOZ_RELEASE_ASSERT(list2.isEmpty());

  list3.clear();

static void TestRemoveAndGet() {

  LinkedList<SomeClass> list;

  SomeClass one(1), two(2), three(3);

  list.insertBack(&one);

  list.insertBack(&two);

  list.insertBack(&three);

    unsigned int check[]{1, 2, 3};

    CheckListValues(list, check);

  MOZ_RELEASE_ASSERT(two.removeAndGetNext() == &three);

    unsigned int check[]{1, 3};

    CheckListValues(list, check);

  MOZ_RELEASE_ASSERT(three.removeAndGetPrevious() == &one);

    unsigned int check[]{1};

    CheckListValues(list, check);

struct PrivateClass : private LinkedListElement<PrivateClass> {

  friend class mozilla::LinkedList<PrivateClass>;

  friend class mozilla::LinkedListElement<PrivateClass>;

};

static void TestPrivate() {

  LinkedList<PrivateClass> list;

  PrivateClass one, two;

  list.insertBack(&one);

  list.insertBack(&two);

  size_t count = 0;

  for (PrivateClass* p : list) {

    MOZ_RELEASE_ASSERT(p, "cannot have null elements in list");

    count++;

  MOZ_RELEASE_ASSERT(count == 2);

struct CountedClass : public LinkedListElement<RefPtr<CountedClass>> {

  int mCount;

  void AddRef() { mCount++; }

  void Release() { mCount--; }

  CountedClass() : mCount(0) {}

  ~CountedClass() { MOZ_RELEASE_ASSERT(mCount == 0); }

};

static void TestRefPtrList() {

  LinkedList<RefPtr<CountedClass>> list;

  CountedClass* elt1 = new CountedClass;

  CountedClass* elt2 = new CountedClass;

  list.insertBack(elt1);

  list.insertBack(elt2);

  MOZ_RELEASE_ASSERT(elt1->mCount == 1);

  MOZ_RELEASE_ASSERT(elt2->mCount == 1);

  for (RefPtr<CountedClass> p : list) {

    MOZ_RELEASE_ASSERT(p->mCount == 2);

  RefPtr<CountedClass> ptr = list.getFirst();

  while (ptr) {

    MOZ_RELEASE_ASSERT(ptr->mCount == 2);

    RefPtr<CountedClass> next = ptr->getNext();

    ptr->remove();

    ptr = std::move(next);

  ptr = nullptr;

  MOZ_RELEASE_ASSERT(elt1->mCount == 0);

  MOZ_RELEASE_ASSERT(elt2->mCount == 0);

  list.insertBack(elt1);

  elt1->setNext(elt2);

  MOZ_RELEASE_ASSERT(elt1->mCount == 1);

  MOZ_RELEASE_ASSERT(elt2->mCount == 1);

  RefPtr<CountedClass> first = list.popFirst();

  MOZ_RELEASE_ASSERT(elt1->mCount == 1);

  MOZ_RELEASE_ASSERT(elt2->mCount == 1);

  RefPtr<CountedClass> second = list.popFirst();

  MOZ_RELEASE_ASSERT(elt1->mCount == 1);

  MOZ_RELEASE_ASSERT(elt2->mCount == 1);

  first = second = nullptr;

  delete elt1;

  delete elt2;

int main() {

  TestList();

  TestExtendLists();

  TestSplice();

  TestPrivate();

  TestMove();

  TestRemoveAndGet();

  TestRefPtrList();

  return 0;