Quelle TestDoublyLinkedList.cpp Sprache: C

/* -*- 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/DoublyLinkedList.h"

using mozilla::DoublyLinkedList;
using mozilla::DoublyLinkedListElement;

struct SomeClass : public DoublyLinkedListElement<SomeClass> {
  unsigned int mValue;
  explicit SomeClass(int aValue) : mValue(aValue) {}
  void incr() { ++mValue; }
  bool operator==(const SomeClass& other) const {
    return mValue == other.mValue;
  }
};

template <typename ListType, size_t N>
static void CheckListValues(ListType& list, unsigned int (&values)[N]) {
  size_t count = 0;
  for (auto& x : list) {
    MOZ_RELEASE_ASSERT(x.mValue == values[count]);
    ++count;
  }
  MOZ_RELEASE_ASSERT(count == N);
}

static void TestDoublyLinkedList() {
  DoublyLinkedList<SomeClass> list;

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

  MOZ_RELEASE_ASSERT(list.isEmpty());
  MOZ_RELEASE_ASSERT(!list.begin());
  MOZ_RELEASE_ASSERT(!list.end());

  for (SomeClass& x : list) {
    MOZ_RELEASE_ASSERT(x.mValue);
    MOZ_RELEASE_ASSERT(false);
  }

  list.pushFront(&one);
  {
    unsigned int check[]{1};
    CheckListValues(list, check);
  }

  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.begin()->mValue == 1);
  MOZ_RELEASE_ASSERT(!list.end());

  list.pushFront(&two);
  {
    unsigned int check[]{2, 1};
    CheckListValues(list, check);
  }

  MOZ_RELEASE_ASSERT(list.begin()->mValue == 2);
  MOZ_RELEASE_ASSERT(!list.end());
  MOZ_RELEASE_ASSERT(!list.contains(three));

  list.pushBack(&three);
  {
    unsigned int check[]{2, 1, 3};
    CheckListValues(list, check);
  }

  MOZ_RELEASE_ASSERT(list.begin()->mValue == 2);
  MOZ_RELEASE_ASSERT(!list.end());

  list.remove(&one);
  {
    unsigned int check[]{2, 3};
    CheckListValues(list, check);
  }

  list.insertBefore(list.find(three), &one);
  {
    unsigned int check[]{2, 1, 3};
    CheckListValues(list, check);
  }

  list.remove(&three);
  {
    unsigned int check[]{2, 1};
    CheckListValues(list, check);
  }

  list.insertBefore(list.find(two), &three);
  {
    unsigned int check[]{3, 2, 1};
    CheckListValues(list, check);
  }

  list.remove(&three);
  {
    unsigned int check[]{2, 1};
    CheckListValues(list, check);
  }

  list.insertBefore(++list.find(two), &three);
  {
    unsigned int check[]{2, 3, 1};
    CheckListValues(list, check);
  }

  list.remove(&one);
  {
    unsigned int check[]{2, 3};
    CheckListValues(list, check);
  }

  list.remove(&two);
  {
    unsigned int check[]{3};
    CheckListValues(list, check);
  }

  list.insertBefore(list.find(three), &two);
  {
    unsigned int check[]{2, 3};
    CheckListValues(list, check);
  }

  list.remove(&three);
  {
    unsigned int check[]{2};
    CheckListValues(list, check);
  }

  list.remove(&two);
  MOZ_RELEASE_ASSERT(list.isEmpty());

  list.pushBack(&three);
  {
    unsigned int check[]{3};
    CheckListValues(list, check);
  }

  list.pushFront(&two);
  {
    unsigned int check[]{2, 3};
    CheckListValues(list, check);
  }

  // This should modify the values of |two| and |three| as pointers to them are
  // stored in the list, not copies.
  for (SomeClass& x : list) {
    x.incr();
  }

  MOZ_RELEASE_ASSERT(*list.begin() == two);
  MOZ_RELEASE_ASSERT(*++list.begin() == three);

  SomeClass four(4);
  MOZ_RELEASE_ASSERT(++list.begin() == list.find(four));
}

struct InTwoLists {
  explicit InTwoLists(unsigned int aValue) : mValue(aValue) {}
  DoublyLinkedListElement<InTwoLists> mListOne;
  DoublyLinkedListElement<InTwoLists> mListTwo;
  unsigned int mValue;

  struct GetListOneTrait {
    static DoublyLinkedListElement<InTwoLists>& Get(InTwoLists* aThis) {
      return aThis->mListOne;
    }
  };
};

namespace mozilla {

template <>
struct GetDoublyLinkedListElement<InTwoLists> {
  static DoublyLinkedListElement<InTwoLists>& Get(InTwoLists* aThis) {
    return aThis->mListTwo;
  }
};

}  // namespace mozilla

static void TestCustomAccessor() {
  DoublyLinkedList<InTwoLists, InTwoLists::GetListOneTrait> listOne;
  DoublyLinkedList<InTwoLists> listTwo;

  InTwoLists one(1);
  InTwoLists two(2);

  listOne.pushBack(&one);
  listOne.pushBack(&two);
  {
    unsigned int check[]{1, 2};
    CheckListValues(listOne, check);
  }

  listTwo.pushBack(&one);
  listTwo.pushBack(&two);
  {
    unsigned int check[]{1, 2};
    CheckListValues(listOne, check);
  }
  {
    unsigned int check[]{1, 2};
    CheckListValues(listTwo, check);
  }

  (void)listTwo.popBack();
  {
    unsigned int check[]{1, 2};
    CheckListValues(listOne, check);
  }
  {
    unsigned int check[]{1};
    CheckListValues(listTwo, check);
  }

  (void)listOne.popBack();
  {
    unsigned int check[]{1};
    CheckListValues(listOne, check);
  }
  {
    unsigned int check[]{1};
    CheckListValues(listTwo, check);
  }
}

static void TestSafeDoubleLinkedList() {
  mozilla::SafeDoublyLinkedList<SomeClass> list;
  auto* elt1 = new SomeClass(0);
  auto* elt2 = new SomeClass(0);
  auto* elt3 = new SomeClass(0);
  auto* elt4 = new SomeClass(0);
  list.pushBack(elt1);
  list.pushBack(elt2);
  list.pushBack(elt3);
  auto iter = list.begin();

  // basic tests for iterator validity
  MOZ_RELEASE_ASSERT(
      &*iter == elt1,
      "iterator returned by begin() must point to the first element!");
  MOZ_RELEASE_ASSERT(
      &*(iter.next()) == elt2,
      "iterator returned by begin() must have the second element as 'next'!");
  list.remove(elt2);
  MOZ_RELEASE_ASSERT(
      &*(iter.next()) == elt3,
      "After removal of the 2nd element 'next' must point to the 3rd element!");
  ++iter;
  MOZ_RELEASE_ASSERT(
      &*iter == elt3,
      "After advancing one step the current element must be the 3rd one!");
  MOZ_RELEASE_ASSERT(!iter.next(), "This is the last element of the list!");
  list.pushBack(elt4);
  MOZ_RELEASE_ASSERT(&*(iter.next()) == elt4,
                     "After adding an element at the end of the list the "
                     "iterator must be updated!");

  // advance to last element, then remove last element
  ++iter;
  list.popBack();
  MOZ_RELEASE_ASSERT(bool(iter) == false,
                     "After removing the last element, the iterator pointing "
                     "to the last element must be empty!");

  // iterate the whole remaining list, increment values
  for (auto& el : list) {
    el.incr();
  }
  MOZ_RELEASE_ASSERT(elt1->mValue == 1);
  MOZ_RELEASE_ASSERT(elt2->mValue == 0);
  MOZ_RELEASE_ASSERT(elt3->mValue == 1);
  MOZ_RELEASE_ASSERT(elt4->mValue == 0);

  // Removing the first element of the list while iterating must empty the
  // iterator
  for (auto it = list.begin(); it != list.end(); ++it) {
    MOZ_RELEASE_ASSERT(bool(it) == true, "The iterator must contain a value!");
    list.popFront();
    MOZ_RELEASE_ASSERT(
        bool(it) == false,
        "After removing the first element, the iterator must be empty!");
  }

  delete elt1;
  delete elt2;
  delete elt3;
  delete elt4;
}

int main() {
  TestDoublyLinkedList();
  TestCustomAccessor();
  TestSafeDoubleLinkedList();
  return 0;
}

quality92%

¤ Dauer der Verarbeitung: 0.13 Sekunden (vorverarbeitet) ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.