Adds iterators and a check to avoid segfault when removing node in LinkedList.
Bug: dawn:628
Change-Id: I1250ffe303155004572c2476ec357daa78b7bb3b
Reviewed-on: https://dawn-review.googlesource.com/c/dawn/+/65860
Commit-Queue: Loko Kung <lokokung@google.com>
Reviewed-by: Austin Eng <enga@chromium.org>
diff --git a/src/common/LinkedList.h b/src/common/LinkedList.h
index 47ca1eb..9b89ad5 100644
--- a/src/common/LinkedList.h
+++ b/src/common/LinkedList.h
@@ -2,7 +2,10 @@
// 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
+// This file is a copy of Chromium's /src/base/containers/linked_list.h with the following
+// modifications:
+// - Added iterators for ranged based iterations
+// - Added in list check before removing node to prevent segfault, now returns true iff removed
#ifndef COMMON_LINKED_LIST_H
#define COMMON_LINKED_LIST_H
@@ -43,6 +46,11 @@
// ...
// }
//
+// for (LinkNode<MyNodeType*> node : list) {
+// MyNodeType* value = node->value();
+// ...
+// }
+//
// Or to iterate the linked list backwards:
//
// for (LinkNode<MyNodeType>* node = list.tail();
@@ -125,14 +133,18 @@
return this->next_ != nullptr;
}
- // Remove |this| from the linked list.
- void RemoveFromList() {
+ // Remove |this| from the linked list. Returns true iff removed from a list.
+ bool RemoveFromList() {
+ if (!IsInList()) {
+ return false;
+ }
+
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.
+ // next() and previous() return non-null if and only this node is not in any list.
this->next_ = nullptr;
this->previous_ = nullptr;
+ return true;
}
LinkNode<T>* previous() const {
@@ -197,4 +209,44 @@
private:
LinkNode<T> root_;
};
+
+template <typename T>
+class LinkedListIterator {
+ public:
+ LinkedListIterator(LinkNode<T>* node) : current_(node), next_(node->next()) {
+ }
+
+ // We keep an early reference to the next node in the list so that even if the current element
+ // is modified or removed from the list, we have a valid next node.
+ LinkedListIterator<T> const& operator++() {
+ current_ = next_;
+ next_ = current_->next();
+ return *this;
+ }
+
+ bool operator!=(const LinkedListIterator<T>& other) const {
+ return current_ != other.current_;
+ }
+
+ LinkNode<T>* operator*() const {
+ return current_;
+ }
+
+ private:
+ LinkNode<T>* current_;
+ LinkNode<T>* next_;
+};
+
+template <typename T>
+LinkedListIterator<T> begin(LinkedList<T>& l) {
+ return LinkedListIterator<T>(l.head());
+}
+
+// Free end function does't use LinkedList<T>::end because of it's const nature. Instead we wrap
+// around from tail.
+template <typename T>
+LinkedListIterator<T> end(LinkedList<T>& l) {
+ return LinkedListIterator<T>(l.tail()->next());
+}
+
#endif // COMMON_LINKED_LIST_H
diff --git a/src/tests/unittests/LinkedListTests.cpp b/src/tests/unittests/LinkedListTests.cpp
index 7dcb37f..1a06d8c 100644
--- a/src/tests/unittests/LinkedListTests.cpp
+++ b/src/tests/unittests/LinkedListTests.cpp
@@ -19,6 +19,10 @@
return id_;
}
+ void set_id(int id) {
+ id_ = id;
+ }
+
private:
int id_;
};
@@ -360,6 +364,27 @@
EXPECT_FALSE(n.IsInList());
list.Append(&n);
EXPECT_TRUE(n.IsInList());
- n.RemoveFromList();
+ EXPECT_TRUE(n.RemoveFromList());
EXPECT_FALSE(n.IsInList());
+ EXPECT_FALSE(n.RemoveFromList());
+}
+
+TEST(LinkedList, RangeBasedModify) {
+ LinkedList<Node> list;
+
+ Node n1(1);
+ Node n2(2);
+ list.Append(&n1);
+ list.Append(&n2);
+
+ for (LinkNode<Node>* node : list) {
+ node->value()->set_id(node->value()->id() + 1);
+ }
+ const int expected[] = {2, 3};
+ ExpectListContents(list, 2, expected);
+}
+
+TEST(LinkedList, RangeBasedEndIsEnd) {
+ LinkedList<Node> list;
+ EXPECT_EQ(list.end(), *end(list));
}
