Introduce fxcrt::RetainedTreeNode
Builds trees the way they were intended, almost. Similar to
what Blink did prior to the Oilpan garbage collector.
Change-Id: I24b0523bb6585d280e458254c3303ce9162b4654
Reviewed-on: https://pdfium-review.googlesource.com/c/pdfium/+/52331
Commit-Queue: Tom Sepez <tsepez@chromium.org>
Reviewed-by: Lei Zhang <thestig@chromium.org>
diff --git a/core/fxcrt/BUILD.gn b/core/fxcrt/BUILD.gn
index d395e4d..2221af1 100644
--- a/core/fxcrt/BUILD.gn
+++ b/core/fxcrt/BUILD.gn
@@ -56,6 +56,7 @@
"observable.h",
"pauseindicator_iface.h",
"retain_ptr.h",
+ "retained_tree_node.h",
"shared_copy_on_write.h",
"string_data_template.h",
"string_pool_template.h",
@@ -156,6 +157,7 @@
"observable_unittest.cpp",
"pdfium_span_unittest.cpp",
"retain_ptr_unittest.cpp",
+ "retained_tree_node_unittest.cpp",
"shared_copy_on_write_unittest.cpp",
"string_pool_template_unittest.cpp",
"unowned_ptr_unittest.cpp",
diff --git a/core/fxcrt/retained_tree_node.h b/core/fxcrt/retained_tree_node.h
new file mode 100644
index 0000000..8b29e69
--- /dev/null
+++ b/core/fxcrt/retained_tree_node.h
@@ -0,0 +1,146 @@
+// Copyright 2019 PDFium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef CORE_FXCRT_RETAINED_TREE_NODE_H_
+#define CORE_FXCRT_RETAINED_TREE_NODE_H_
+
+#include "core/fxcrt/retain_ptr.h"
+#include "third_party/base/logging.h"
+
+namespace fxcrt {
+
+// For DOM/XML-ish trees, where references outside the tree are RetainPtr<T>,
+// and the parent node also "retains" its children but doesn't always have
+// a direct pointer to them.
+template <typename T>
+class RetainedTreeNode {
+ public:
+ template <typename U, typename... Args>
+ friend RetainPtr<U> pdfium::MakeRetain(Args&&... args);
+
+ T* GetParent() const { return m_pParent; }
+ T* GetFirstChild() const { return m_pFirstChild; }
+ T* GetLastChild() const { return m_pLastChild; }
+ T* GetNextSibling() const { return m_pNextSibling; }
+ T* GetPrevSibling() const { return m_pPrevSibling; }
+
+ void AppendFirstChild(const RetainPtr<T>& child) {
+ BecomeParent(child);
+ if (m_pFirstChild) {
+ m_pFirstChild->m_pPrevSibling = child.Get();
+ child->m_pNextSibling = m_pFirstChild;
+ m_pFirstChild = child.Get();
+ } else {
+ m_pFirstChild = child.Get();
+ m_pLastChild = child.Get();
+ }
+ }
+
+ void AppendLastChild(const RetainPtr<T>& child) {
+ BecomeParent(child);
+ if (m_pLastChild) {
+ m_pLastChild->m_pNextSibling = child.Get();
+ child->m_pPrevSibling = m_pLastChild;
+ m_pLastChild = child.Get();
+ } else {
+ m_pFirstChild = child.Get();
+ m_pLastChild = child.Get();
+ }
+ }
+
+ void InsertBefore(const RetainPtr<T>& child, T* other) {
+ if (!other) {
+ AppendLastChild(child);
+ return;
+ }
+ CHECK(other->m_pParent == this);
+ BecomeParent(child);
+ child->m_pNextSibling = other;
+ child->m_pPrevSibling = other->m_pPrevSibling;
+ if (other->m_pPrevSibling)
+ other->m_pPrevSibling->m_pNextSibling = child.Get();
+ else
+ m_pFirstChild = child.Get();
+ other->m_pPrevSibling = child.Get();
+ }
+
+ void InsertAfter(const RetainPtr<T>& child, T* other) {
+ if (!other) {
+ AppendFirstChild(child);
+ return;
+ }
+ CHECK(other->m_pParent == this);
+ BecomeParent(child);
+ child->m_pNextSibling = other->m_pNextSibling;
+ child->m_pPrevSibling = other;
+ if (other->m_pNextSibling)
+ other->m_pNextSibling->m_pPrevSibling = child.Get();
+ else
+ m_pLastChild = child.Get();
+ other->m_pNextSibling = child.Get();
+ }
+
+ void RemoveChild(const RetainPtr<T>& child) {
+ CHECK(child->m_pParent == this);
+ if (child->m_pNextSibling)
+ child->m_pNextSibling->m_pPrevSibling = child->m_pPrevSibling;
+ else
+ m_pLastChild = child->m_pPrevSibling;
+
+ if (child->m_pPrevSibling)
+ child->m_pPrevSibling->m_pNextSibling = child->m_pNextSibling;
+ else
+ m_pFirstChild = child->m_pNextSibling;
+
+ child->m_pParent = nullptr;
+ child->m_pPrevSibling = nullptr;
+ child->m_pNextSibling = nullptr;
+ }
+
+ protected:
+ RetainedTreeNode() = default;
+ virtual ~RetainedTreeNode() {
+ while (m_pFirstChild)
+ RemoveChild(pdfium::WrapRetain(m_pFirstChild));
+ }
+
+ private:
+ template <typename U>
+ friend struct ReleaseDeleter;
+
+ template <typename U>
+ friend class RetainPtr;
+
+ RetainedTreeNode(const RetainedTreeNode& that) = delete;
+ RetainedTreeNode& operator=(const RetainedTreeNode& that) = delete;
+
+ void Retain() { ++m_nRefCount; }
+ void Release() {
+ ASSERT(m_nRefCount > 0);
+ if (--m_nRefCount == 0 && !m_pParent)
+ delete this;
+ }
+
+ // Child left in state where sibling members need subsequent adjustment.
+ void BecomeParent(const RetainPtr<T>& child) {
+ if (child->m_pParent)
+ child->m_pParent->RemoveChild(child);
+ child->m_pParent = static_cast<T*>(this);
+ ASSERT(!child->m_pNextSibling);
+ ASSERT(!child->m_pPrevSibling);
+ }
+
+ intptr_t m_nRefCount = 0;
+ T* m_pParent = nullptr; // Raw, intra-tree pointer.
+ T* m_pFirstChild = nullptr; // Raw, intra-tree pointer.
+ T* m_pLastChild = nullptr; // Raw, intra-tree pointer.
+ T* m_pNextSibling = nullptr; // Raw, intra-tree pointer
+ T* m_pPrevSibling = nullptr; // Raw, intra-tree pointer
+};
+
+} // namespace fxcrt
+
+using fxcrt::RetainedTreeNode;
+
+#endif // CORE_FXCRT_RETAINED_TREE_NODE_H_
diff --git a/core/fxcrt/retained_tree_node_unittest.cpp b/core/fxcrt/retained_tree_node_unittest.cpp
new file mode 100644
index 0000000..c41b5ef
--- /dev/null
+++ b/core/fxcrt/retained_tree_node_unittest.cpp
@@ -0,0 +1,170 @@
+// Copyright 2019 PDFium 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 "core/fxcrt/retained_tree_node.h"
+
+#include "core/fxcrt/observable.h"
+#include "core/fxcrt/retain_ptr.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace fxcrt {
+namespace {
+
+class ObservableRetainedTreeNodeForTest
+ : public RetainedTreeNode<ObservableRetainedTreeNodeForTest>,
+ public Observable<ObservableRetainedTreeNodeForTest> {
+ public:
+ template <typename T, typename... Args>
+ friend RetainPtr<T> pdfium::MakeRetain(Args&&... args);
+
+ private:
+ ObservableRetainedTreeNodeForTest() = default;
+};
+
+void AddClutterToFront(
+ const RetainPtr<ObservableRetainedTreeNodeForTest>& parent) {
+ for (int i = 0; i < 4; ++i) {
+ parent->AppendFirstChild(
+ pdfium::MakeRetain<ObservableRetainedTreeNodeForTest>());
+ }
+}
+
+void AddClutterToBack(
+ const RetainPtr<ObservableRetainedTreeNodeForTest>& parent) {
+ for (int i = 0; i < 4; ++i) {
+ parent->AppendLastChild(
+ pdfium::MakeRetain<ObservableRetainedTreeNodeForTest>());
+ }
+}
+
+} // namespace
+
+TEST(RetainedTreeNode, NoParent) {
+ ObservableRetainedTreeNodeForTest::ObservedPtr watcher;
+ {
+ RetainPtr<ObservableRetainedTreeNodeForTest> ptr =
+ pdfium::MakeRetain<ObservableRetainedTreeNodeForTest>();
+ watcher = ObservableRetainedTreeNodeForTest::ObservedPtr(ptr.Get());
+ EXPECT_TRUE(watcher.Get());
+ }
+ EXPECT_FALSE(watcher.Get());
+}
+
+TEST(RetainedTreeNode, FirstHasParent) {
+ ObservableRetainedTreeNodeForTest::ObservedPtr watcher;
+ RetainPtr<ObservableRetainedTreeNodeForTest> parent =
+ pdfium::MakeRetain<ObservableRetainedTreeNodeForTest>();
+ {
+ RetainPtr<ObservableRetainedTreeNodeForTest> ptr =
+ pdfium::MakeRetain<ObservableRetainedTreeNodeForTest>();
+ watcher = ObservableRetainedTreeNodeForTest::ObservedPtr(ptr.Get());
+ parent->AppendFirstChild(ptr);
+ EXPECT_TRUE(watcher.Get());
+ }
+ EXPECT_TRUE(watcher.Get());
+ parent->RemoveChild(pdfium::WrapRetain(watcher.Get()));
+ EXPECT_FALSE(watcher.Get());
+ // Now add some clutter.
+ {
+ RetainPtr<ObservableRetainedTreeNodeForTest> ptr =
+ pdfium::MakeRetain<ObservableRetainedTreeNodeForTest>();
+ watcher = ObservableRetainedTreeNodeForTest::ObservedPtr(ptr.Get());
+ parent->AppendFirstChild(ptr);
+ AddClutterToFront(parent);
+ AddClutterToBack(parent);
+ EXPECT_TRUE(watcher.Get());
+ }
+ EXPECT_TRUE(watcher.Get());
+ parent->RemoveChild(pdfium::WrapRetain(watcher.Get()));
+ EXPECT_FALSE(watcher.Get());
+}
+
+TEST(RetainedTreeNode, LastHasParent) {
+ ObservableRetainedTreeNodeForTest::ObservedPtr watcher;
+ RetainPtr<ObservableRetainedTreeNodeForTest> parent =
+ pdfium::MakeRetain<ObservableRetainedTreeNodeForTest>();
+ {
+ RetainPtr<ObservableRetainedTreeNodeForTest> ptr =
+ pdfium::MakeRetain<ObservableRetainedTreeNodeForTest>();
+ watcher = ObservableRetainedTreeNodeForTest::ObservedPtr(ptr.Get());
+ parent->AppendLastChild(ptr);
+ EXPECT_TRUE(watcher.Get());
+ }
+ {
+ // Now add some clutter.
+ RetainPtr<ObservableRetainedTreeNodeForTest> ptr =
+ pdfium::MakeRetain<ObservableRetainedTreeNodeForTest>();
+ watcher = ObservableRetainedTreeNodeForTest::ObservedPtr(ptr.Get());
+ parent->AppendLastChild(ptr);
+ AddClutterToFront(parent);
+ AddClutterToBack(parent);
+ EXPECT_TRUE(watcher.Get());
+ }
+ EXPECT_TRUE(watcher.Get());
+ parent->RemoveChild(pdfium::WrapRetain(watcher.Get()));
+ EXPECT_FALSE(watcher.Get());
+}
+
+TEST(RetainedTreeNode, GrandChildCleanedUp) {
+ ObservableRetainedTreeNodeForTest::ObservedPtr watcher;
+ RetainPtr<ObservableRetainedTreeNodeForTest> grandparent =
+ pdfium::MakeRetain<ObservableRetainedTreeNodeForTest>();
+ {
+ RetainPtr<ObservableRetainedTreeNodeForTest> parent =
+ pdfium::MakeRetain<ObservableRetainedTreeNodeForTest>();
+ grandparent->AppendFirstChild(parent);
+ {
+ RetainPtr<ObservableRetainedTreeNodeForTest> ptr =
+ pdfium::MakeRetain<ObservableRetainedTreeNodeForTest>();
+ watcher = ObservableRetainedTreeNodeForTest::ObservedPtr(ptr.Get());
+ parent->AppendFirstChild(ptr);
+ EXPECT_TRUE(watcher.Get());
+ }
+ grandparent->RemoveChild(parent);
+ EXPECT_TRUE(watcher.Get());
+ }
+ EXPECT_FALSE(watcher.Get());
+}
+
+TEST(RetainedTreeNode, InsertBeforeAfter) {
+ ObservableRetainedTreeNodeForTest::ObservedPtr watcher;
+ RetainPtr<ObservableRetainedTreeNodeForTest> parent =
+ pdfium::MakeRetain<ObservableRetainedTreeNodeForTest>();
+
+ AddClutterToFront(parent);
+ {
+ RetainPtr<ObservableRetainedTreeNodeForTest> ptr =
+ pdfium::MakeRetain<ObservableRetainedTreeNodeForTest>();
+ watcher = ObservableRetainedTreeNodeForTest::ObservedPtr(ptr.Get());
+ parent->AppendFirstChild(ptr);
+ parent->InsertBefore(pdfium::WrapRetain(parent->GetFirstChild()),
+ parent->GetLastChild());
+ parent->InsertAfter(pdfium::WrapRetain(parent->GetLastChild()),
+ parent->GetFirstChild());
+ EXPECT_TRUE(watcher.Get());
+ }
+ parent->RemoveChild(pdfium::WrapRetain(watcher.Get()));
+ EXPECT_FALSE(watcher.Get());
+}
+
+TEST(RetainedTreeNode, Traversal) {
+ RetainPtr<ObservableRetainedTreeNodeForTest> parent =
+ pdfium::MakeRetain<ObservableRetainedTreeNodeForTest>();
+
+ AddClutterToFront(parent);
+ int count = 0;
+ for (ObservableRetainedTreeNodeForTest* pNode = parent->GetFirstChild();
+ pNode; pNode = pNode->GetNextSibling()) {
+ ++count;
+ }
+ EXPECT_EQ(4, count);
+ count = 0;
+ for (ObservableRetainedTreeNodeForTest* pNode = parent->GetLastChild(); pNode;
+ pNode = pNode->GetPrevSibling()) {
+ ++count;
+ }
+ EXPECT_EQ(4, count);
+}
+
+} // namespace fxcrt
