Residency 1: Add Chromium's LinkedList to /common/
A Chromium's LinkedList class to Dawn. Implementation and header are
a direct copy/paste. This is to be used to implement an LRU Cache
for the ResidencyManager class.
Bug: dawn:193
Change-Id: I7cb02649590be4db0fe54c9d80557ac49efc34de
Reviewed-on: https://dawn-review.googlesource.com/c/dawn/+/16380
Commit-Queue: Corentin Wallez <cwallez@chromium.org>
Reviewed-by: Corentin Wallez <cwallez@chromium.org>
Reviewed-by: Austin Eng <enga@chromium.org>
diff --git a/BUILD.gn b/BUILD.gn
index 3de92a4..f09523e 100644
--- a/BUILD.gn
+++ b/BUILD.gn
@@ -830,6 +830,7 @@
"src/tests/unittests/ErrorTests.cpp",
"src/tests/unittests/ExtensionTests.cpp",
"src/tests/unittests/GetProcAddressTests.cpp",
+ "src/tests/unittests/LinkedListTests.cpp",
"src/tests/unittests/MathTests.cpp",
"src/tests/unittests/ObjectBaseTests.cpp",
"src/tests/unittests/PerStageTests.cpp",
diff --git a/src/common/BUILD.gn b/src/common/BUILD.gn
index c036f62..321fa30 100644
--- a/src/common/BUILD.gn
+++ b/src/common/BUILD.gn
@@ -108,6 +108,7 @@
"GPUInfo.cpp",
"GPUInfo.h",
"HashUtils.h",
+ "LinkedList.h",
"Log.cpp",
"Log.h",
"Math.cpp",
diff --git a/src/common/CMakeLists.txt b/src/common/CMakeLists.txt
index f36a9d0..be9bd84 100644
--- a/src/common/CMakeLists.txt
+++ b/src/common/CMakeLists.txt
@@ -24,6 +24,7 @@
"GPUInfo.cpp"
"GPUInfo.h"
"HashUtils.h"
+ "LinkedList.h"
"Log.cpp"
"Log.h"
"Math.cpp"
diff --git a/src/common/LinkedList.h b/src/common/LinkedList.h
new file mode 100644
index 0000000..c67c986
--- /dev/null
+++ b/src/common/LinkedList.h
@@ -0,0 +1,185 @@
+// Copyright (c) 2009 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+// This file is a copy of Chromium's /src/base/containers/linked_list.h
+
+#ifndef COMMON_LINKED_LIST_H
+#define COMMON_LINKED_LIST_H
+
+// Simple LinkedList type. (See the Q&A section to understand how this
+// differs from std::list).
+//
+// To use, start by declaring the class which will be contained in the linked
+// list, as extending LinkNode (this gives it next/previous pointers).
+//
+// class MyNodeType : public LinkNode<MyNodeType> {
+// ...
+// };
+//
+// Next, to keep track of the list's head/tail, use a LinkedList instance:
+//
+// LinkedList<MyNodeType> list;
+//
+// To add elements to the list, use any of LinkedList::Append,
+// LinkNode::InsertBefore, or LinkNode::InsertAfter:
+//
+// LinkNode<MyNodeType>* n1 = ...;
+// LinkNode<MyNodeType>* n2 = ...;
+// LinkNode<MyNodeType>* n3 = ...;
+//
+// list.Append(n1);
+// list.Append(n3);
+// n3->InsertBefore(n3);
+//
+// Lastly, to iterate through the linked list forwards:
+//
+// for (LinkNode<MyNodeType>* node = list.head();
+// node != list.end();
+// node = node->next()) {
+// MyNodeType* value = node->value();
+// ...
+// }
+//
+// Or to iterate the linked list backwards:
+//
+// for (LinkNode<MyNodeType>* node = list.tail();
+// node != list.end();
+// node = node->previous()) {
+// MyNodeType* value = node->value();
+// ...
+// }
+//
+// Questions and Answers:
+//
+// Q. Should I use std::list or base::LinkedList?
+//
+// A. The main reason to use base::LinkedList over std::list is
+// performance. If you don't care about the performance differences
+// then use an STL container, as it makes for better code readability.
+//
+// Comparing the performance of base::LinkedList<T> to std::list<T*>:
+//
+// * Erasing an element of type T* from base::LinkedList<T> is
+// an O(1) operation. Whereas for std::list<T*> it is O(n).
+// That is because with std::list<T*> you must obtain an
+// iterator to the T* element before you can call erase(iterator).
+//
+// * Insertion operations with base::LinkedList<T> never require
+// heap allocations.
+//
+// Q. How does base::LinkedList implementation differ from std::list?
+//
+// A. Doubly-linked lists are made up of nodes that contain "next" and
+// "previous" pointers that reference other nodes in the list.
+//
+// With base::LinkedList<T>, the type being inserted already reserves
+// space for the "next" and "previous" pointers (base::LinkNode<T>*).
+// Whereas with std::list<T> the type can be anything, so the implementation
+// needs to glue on the "next" and "previous" pointers using
+// some internal node type.
+
+template <typename T>
+class LinkNode {
+ public:
+ LinkNode() : previous_(nullptr), next_(nullptr) {
+ }
+ LinkNode(LinkNode<T>* previous, LinkNode<T>* next) : previous_(previous), next_(next) {
+ }
+
+ LinkNode(LinkNode<T>&& rhs) {
+ next_ = rhs.next_;
+ rhs.next_ = nullptr;
+ previous_ = rhs.previous_;
+ rhs.previous_ = nullptr;
+
+ // If the node belongs to a list, next_ and previous_ are both non-null.
+ // Otherwise, they are both null.
+ if (next_) {
+ next_->previous_ = this;
+ previous_->next_ = this;
+ }
+ }
+
+ // Insert |this| into the linked list, before |e|.
+ void InsertBefore(LinkNode<T>* e) {
+ this->next_ = e;
+ this->previous_ = e->previous_;
+ e->previous_->next_ = this;
+ e->previous_ = this;
+ }
+
+ // Insert |this| into the linked list, after |e|.
+ void InsertAfter(LinkNode<T>* e) {
+ this->next_ = e->next_;
+ this->previous_ = e;
+ e->next_->previous_ = this;
+ e->next_ = this;
+ }
+
+ // Remove |this| from the linked list.
+ void RemoveFromList() {
+ this->previous_->next_ = this->next_;
+ this->next_->previous_ = this->previous_;
+ // next() and previous() return non-null if and only this node is not in any
+ // list.
+ this->next_ = nullptr;
+ this->previous_ = nullptr;
+ }
+
+ LinkNode<T>* previous() const {
+ return previous_;
+ }
+
+ LinkNode<T>* next() const {
+ return next_;
+ }
+
+ // Cast from the node-type to the value type.
+ const T* value() const {
+ return static_cast<const T*>(this);
+ }
+
+ T* value() {
+ return static_cast<T*>(this);
+ }
+
+ private:
+ LinkNode<T>* previous_;
+ LinkNode<T>* next_;
+};
+
+template <typename T>
+class LinkedList {
+ public:
+ // The "root" node is self-referential, and forms the basis of a circular
+ // list (root_.next() will point back to the start of the list,
+ // and root_->previous() wraps around to the end of the list).
+ LinkedList() : root_(&root_, &root_) {
+ }
+
+ // Appends |e| to the end of the linked list.
+ void Append(LinkNode<T>* e) {
+ e->InsertBefore(&root_);
+ }
+
+ LinkNode<T>* head() const {
+ return root_.next();
+ }
+
+ LinkNode<T>* tail() const {
+ return root_.previous();
+ }
+
+ const LinkNode<T>* end() const {
+ return &root_;
+ }
+
+ bool empty() const {
+ return head() == end();
+ }
+
+ private:
+ LinkNode<T> root_;
+};
+#endif // COMMON_LINKED_LIST_H
\ No newline at end of file
diff --git a/src/tests/unittests/LinkedListTests.cpp b/src/tests/unittests/LinkedListTests.cpp
new file mode 100644
index 0000000..ee298b0
--- /dev/null
+++ b/src/tests/unittests/LinkedListTests.cpp
@@ -0,0 +1,353 @@
+// Copyright (c) 2009 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+// This file is a copy of Chromium's /src/base/containers/linked_list_unittest.cc
+
+#include <gtest/gtest.h>
+
+#include "common/LinkedList.h"
+
+#include <list>
+
+class Node : public LinkNode<Node> {
+ public:
+ explicit Node(int id) : id_(id) {
+ }
+
+ int id() const {
+ return id_;
+ }
+
+ private:
+ int id_;
+};
+
+class MultipleInheritanceNodeBase {
+ public:
+ MultipleInheritanceNodeBase() : field_taking_up_space_(0) {
+ }
+ int field_taking_up_space_;
+};
+
+class MultipleInheritanceNode : public MultipleInheritanceNodeBase,
+ public LinkNode<MultipleInheritanceNode> {
+ public:
+ MultipleInheritanceNode() = default;
+};
+
+class MovableNode : public LinkNode<MovableNode> {
+ public:
+ explicit MovableNode(int id) : id_(id) {
+ }
+
+ MovableNode(MovableNode&&) = default;
+
+ int id() const {
+ return id_;
+ }
+
+ private:
+ int id_;
+};
+
+// Checks that when iterating |list| (either from head to tail, or from
+// tail to head, as determined by |forward|), we get back |node_ids|,
+// which is an array of size |num_nodes|.
+void ExpectListContentsForDirection(const LinkedList<Node>& list,
+ int num_nodes,
+ const int* node_ids,
+ bool forward) {
+ int i = 0;
+ for (const LinkNode<Node>* node = (forward ? list.head() : list.tail()); node != list.end();
+ node = (forward ? node->next() : node->previous())) {
+ ASSERT_LT(i, num_nodes);
+ int index_of_id = forward ? i : num_nodes - i - 1;
+ EXPECT_EQ(node_ids[index_of_id], node->value()->id());
+ ++i;
+ }
+ EXPECT_EQ(num_nodes, i);
+}
+
+void ExpectListContents(const LinkedList<Node>& list, int num_nodes, const int* node_ids) {
+ {
+ SCOPED_TRACE("Iterating forward (from head to tail)");
+ ExpectListContentsForDirection(list, num_nodes, node_ids, true);
+ }
+ {
+ SCOPED_TRACE("Iterating backward (from tail to head)");
+ ExpectListContentsForDirection(list, num_nodes, node_ids, false);
+ }
+}
+
+TEST(LinkedList, Empty) {
+ LinkedList<Node> list;
+ EXPECT_EQ(list.end(), list.head());
+ EXPECT_EQ(list.end(), list.tail());
+ ExpectListContents(list, 0, nullptr);
+}
+
+TEST(LinkedList, Append) {
+ LinkedList<Node> list;
+ ExpectListContents(list, 0, nullptr);
+
+ Node n1(1);
+ list.Append(&n1);
+
+ EXPECT_EQ(&n1, list.head());
+ EXPECT_EQ(&n1, list.tail());
+ {
+ const int expected[] = {1};
+ ExpectListContents(list, 1, expected);
+ }
+
+ Node n2(2);
+ list.Append(&n2);
+
+ EXPECT_EQ(&n1, list.head());
+ EXPECT_EQ(&n2, list.tail());
+ {
+ const int expected[] = {1, 2};
+ ExpectListContents(list, 2, expected);
+ }
+
+ Node n3(3);
+ list.Append(&n3);
+
+ EXPECT_EQ(&n1, list.head());
+ EXPECT_EQ(&n3, list.tail());
+ {
+ const int expected[] = {1, 2, 3};
+ ExpectListContents(list, 3, expected);
+ }
+}
+
+TEST(LinkedList, RemoveFromList) {
+ LinkedList<Node> list;
+
+ Node n1(1);
+ Node n2(2);
+ Node n3(3);
+ Node n4(4);
+ Node n5(5);
+
+ list.Append(&n1);
+ list.Append(&n2);
+ list.Append(&n3);
+ list.Append(&n4);
+ list.Append(&n5);
+
+ EXPECT_EQ(&n1, list.head());
+ EXPECT_EQ(&n5, list.tail());
+ {
+ const int expected[] = {1, 2, 3, 4, 5};
+ ExpectListContents(list, 5, expected);
+ }
+
+ // Remove from the middle.
+ n3.RemoveFromList();
+
+ EXPECT_EQ(&n1, list.head());
+ EXPECT_EQ(&n5, list.tail());
+ {
+ const int expected[] = {1, 2, 4, 5};
+ ExpectListContents(list, 4, expected);
+ }
+
+ // Remove from the tail.
+ n5.RemoveFromList();
+
+ EXPECT_EQ(&n1, list.head());
+ EXPECT_EQ(&n4, list.tail());
+ {
+ const int expected[] = {1, 2, 4};
+ ExpectListContents(list, 3, expected);
+ }
+
+ // Remove from the head.
+ n1.RemoveFromList();
+
+ EXPECT_EQ(&n2, list.head());
+ EXPECT_EQ(&n4, list.tail());
+ {
+ const int expected[] = {2, 4};
+ ExpectListContents(list, 2, expected);
+ }
+
+ // Empty the list.
+ n2.RemoveFromList();
+ n4.RemoveFromList();
+
+ ExpectListContents(list, 0, nullptr);
+ EXPECT_EQ(list.end(), list.head());
+ EXPECT_EQ(list.end(), list.tail());
+
+ // Fill the list once again.
+ list.Append(&n1);
+ list.Append(&n2);
+ list.Append(&n3);
+ list.Append(&n4);
+ list.Append(&n5);
+
+ EXPECT_EQ(&n1, list.head());
+ EXPECT_EQ(&n5, list.tail());
+ {
+ const int expected[] = {1, 2, 3, 4, 5};
+ ExpectListContents(list, 5, expected);
+ }
+}
+
+TEST(LinkedList, InsertBefore) {
+ LinkedList<Node> list;
+
+ Node n1(1);
+ Node n2(2);
+ Node n3(3);
+ Node n4(4);
+
+ list.Append(&n1);
+ list.Append(&n2);
+
+ EXPECT_EQ(&n1, list.head());
+ EXPECT_EQ(&n2, list.tail());
+ {
+ const int expected[] = {1, 2};
+ ExpectListContents(list, 2, expected);
+ }
+
+ n3.InsertBefore(&n2);
+
+ EXPECT_EQ(&n1, list.head());
+ EXPECT_EQ(&n2, list.tail());
+ {
+ const int expected[] = {1, 3, 2};
+ ExpectListContents(list, 3, expected);
+ }
+
+ n4.InsertBefore(&n1);
+
+ EXPECT_EQ(&n4, list.head());
+ EXPECT_EQ(&n2, list.tail());
+ {
+ const int expected[] = {4, 1, 3, 2};
+ ExpectListContents(list, 4, expected);
+ }
+}
+
+TEST(LinkedList, InsertAfter) {
+ LinkedList<Node> list;
+
+ Node n1(1);
+ Node n2(2);
+ Node n3(3);
+ Node n4(4);
+
+ list.Append(&n1);
+ list.Append(&n2);
+
+ EXPECT_EQ(&n1, list.head());
+ EXPECT_EQ(&n2, list.tail());
+ {
+ const int expected[] = {1, 2};
+ ExpectListContents(list, 2, expected);
+ }
+
+ n3.InsertAfter(&n2);
+
+ EXPECT_EQ(&n1, list.head());
+ EXPECT_EQ(&n3, list.tail());
+ {
+ const int expected[] = {1, 2, 3};
+ ExpectListContents(list, 3, expected);
+ }
+
+ n4.InsertAfter(&n1);
+
+ EXPECT_EQ(&n1, list.head());
+ EXPECT_EQ(&n3, list.tail());
+ {
+ const int expected[] = {1, 4, 2, 3};
+ ExpectListContents(list, 4, expected);
+ }
+}
+
+TEST(LinkedList, MultipleInheritanceNode) {
+ MultipleInheritanceNode node;
+ EXPECT_EQ(&node, node.value());
+}
+
+TEST(LinkedList, EmptyListIsEmpty) {
+ LinkedList<Node> list;
+ EXPECT_TRUE(list.empty());
+}
+
+TEST(LinkedList, NonEmptyListIsNotEmpty) {
+ LinkedList<Node> list;
+
+ Node n(1);
+ list.Append(&n);
+
+ EXPECT_FALSE(list.empty());
+}
+
+TEST(LinkedList, EmptiedListIsEmptyAgain) {
+ LinkedList<Node> list;
+
+ Node n(1);
+ list.Append(&n);
+ n.RemoveFromList();
+
+ EXPECT_TRUE(list.empty());
+}
+
+TEST(LinkedList, NodesCanBeReused) {
+ LinkedList<Node> list1;
+ LinkedList<Node> list2;
+
+ Node n(1);
+ list1.Append(&n);
+ n.RemoveFromList();
+ list2.Append(&n);
+
+ EXPECT_EQ(list2.head()->value(), &n);
+}
+
+TEST(LinkedList, RemovedNodeHasNullNextPrevious) {
+ LinkedList<Node> list;
+
+ Node n(1);
+ list.Append(&n);
+ n.RemoveFromList();
+
+ EXPECT_EQ(nullptr, n.next());
+ EXPECT_EQ(nullptr, n.previous());
+}
+
+TEST(LinkedList, NodeMoveConstructor) {
+ LinkedList<MovableNode> list;
+
+ MovableNode n1(1);
+ MovableNode n2(2);
+ MovableNode n3(3);
+
+ list.Append(&n1);
+ list.Append(&n2);
+ list.Append(&n3);
+
+ EXPECT_EQ(&n1, n2.previous());
+ EXPECT_EQ(&n2, n1.next());
+ EXPECT_EQ(&n3, n2.next());
+ EXPECT_EQ(&n2, n3.previous());
+ EXPECT_EQ(2, n2.id());
+
+ MovableNode n2_new(std::move(n2));
+
+ EXPECT_EQ(nullptr, n2.next());
+ EXPECT_EQ(nullptr, n2.previous());
+
+ EXPECT_EQ(&n1, n2_new.previous());
+ EXPECT_EQ(&n2_new, n1.next());
+ EXPECT_EQ(&n3, n2_new.next());
+ EXPECT_EQ(&n2_new, n3.previous());
+ EXPECT_EQ(2, n2_new.id());
+}
\ No newline at end of file
