From 3c62d20a385d31315a392206de53c9fe72a08db1 Mon Sep 17 00:00:00 2001 From: dsinclair Date: Thu, 8 Feb 2018 20:55:41 +0000 Subject: Revert "Convert CXFA_Node to store a vector of children" This reverts commit f0e386de64e030f6d692acfa27e2bc0a50018710. Reason for revert: After chatting with tsepez@, we've got a better direction to take these changes. Original change's description: > Convert CXFA_Node to store a vector of children > > This CL changes CXFA_Node to use a vector of nodes as children instead > of a singly linked list of siblings and child pointers. > > Change-Id: Ica8219f63d783a07d90b9541ae62a35c49166e44 > Reviewed-on: https://pdfium-review.googlesource.com/26030 > Reviewed-by: Ryan Harrison > Commit-Queue: dsinclair TBR=dsinclair@chromium.org,hnakashima@chromium.org,rharrison@chromium.org Change-Id: I115779a292d39694ad5faf0b748a617c491b40f0 No-Presubmit: true No-Tree-Checks: true No-Try: true Reviewed-on: https://pdfium-review.googlesource.com/26070 Reviewed-by: dsinclair Commit-Queue: dsinclair --- xfa/fxfa/parser/cxfa_node.cpp | 262 ++++++++++++++++++++++-------------------- xfa/fxfa/parser/cxfa_node.h | 14 +-- 2 files changed, 143 insertions(+), 133 deletions(-) diff --git a/xfa/fxfa/parser/cxfa_node.cpp b/xfa/fxfa/parser/cxfa_node.cpp index 2d50ec48a3..9af2b2e75a 100644 --- a/xfa/fxfa/parser/cxfa_node.cpp +++ b/xfa/fxfa/parser/cxfa_node.cpp @@ -421,7 +421,6 @@ void ReorderDataNodes(const std::set& sSet1, pNodeSetPair->second.insert(pNode); } } - for (const auto& iter1 : rgMap) { CXFA_NodeSetPairMap* pNodeSetPairMap = iter1.second.get(); if (!pNodeSetPairMap) @@ -506,6 +505,9 @@ CXFA_Node::CXFA_Node(CXFA_Document* pDoc, m_Properties(properties), m_Attributes(attributes), m_ValidPackets(validPackets), + m_pNext(nullptr), + m_pChild(nullptr), + m_pLastChild(nullptr), m_pXMLNode(nullptr), m_ePacket(ePacket), m_uNodeFlags(XFA_NodeFlag_None), @@ -535,12 +537,13 @@ CXFA_Node::CXFA_Node(CXFA_Document* pDoc, CXFA_Node::~CXFA_Node() { ASSERT(!parent_); - for (auto* child : children_) { - child->parent_ = nullptr; - delete child; + CXFA_Node* pNode = m_pChild; + while (pNode) { + CXFA_Node* pNext = pNode->m_pNext; + pNode->parent_ = nullptr; + delete pNode; + pNode = pNext; } - children_.clear(); - if (m_pXMLNode && IsOwnXMLNode()) delete m_pXMLNode; } @@ -583,84 +586,43 @@ CXFA_Node* CXFA_Node::Clone(bool bRecursive) { return pClone; } -CXFA_Node* CXFA_Node::GetFirstChild() const { - if (children_.empty()) - return nullptr; - return children_[0]; -} - -CXFA_Node* CXFA_Node::GetNextSibling() const { - return parent_ ? parent_->GetNodeAfter(this) : nullptr; -} - CXFA_Node* CXFA_Node::GetPrevSibling() const { - return parent_ ? parent_->GetNodeBefore(this) : nullptr; -} - -CXFA_Node* CXFA_Node::GetNodeAfter(const CXFA_Node* node) const { - if (children_.empty() || children_.back() == node) + if (!parent_ || parent_->m_pChild == this) return nullptr; - for (size_t i = 0; i < (children_.size() - 1); ++i) { - if (children_[i] == node) - return children_[i + 1]; - } - return nullptr; -} - -CXFA_Node* CXFA_Node::GetNodeBefore(const CXFA_Node* node) const { - if (children_.empty() || children_[0] == node) - return nullptr; - - for (size_t i = 1; i < children_.size(); ++i) { - if (children_[i] == node) - return children_[i - 1]; + for (CXFA_Node* pNode = parent_->m_pChild; pNode; pNode = pNode->m_pNext) { + if (pNode->m_pNext == this) + return pNode; } return nullptr; } CXFA_Node* CXFA_Node::GetNextContainerSibling() const { - return parent_ ? parent_->GetContainerAfter(this) : nullptr; + CXFA_Node* pNode = m_pNext; + while (pNode && pNode->GetObjectType() != XFA_ObjectType::ContainerNode) + pNode = pNode->m_pNext; + return pNode; } CXFA_Node* CXFA_Node::GetPrevContainerSibling() const { - return parent_ ? parent_->GetContainerBefore(this) : nullptr; -} - -CXFA_Node* CXFA_Node::GetContainerAfter(const CXFA_Node* node) const { - bool found = false; - for (size_t i = 0; i < children_.size(); ++i) { - if (children_[i] == node) { - found = true; - continue; - } - if (!found) - continue; - - if (children_[i]->GetObjectType() == XFA_ObjectType::ContainerNode) - return children_[i]; - } - return nullptr; -} + if (!parent_ || parent_->m_pChild == this) + return nullptr; -CXFA_Node* CXFA_Node::GetContainerBefore(const CXFA_Node* node) const { CXFA_Node* container = nullptr; - for (size_t i = 0; i < children_.size(); ++i) { - if (children_[i] == node) - break; - - if (children_[i]->GetObjectType() == XFA_ObjectType::ContainerNode) - container = children_[i]; + for (CXFA_Node* pNode = parent_->m_pChild; pNode; pNode = pNode->m_pNext) { + if (pNode->GetObjectType() == XFA_ObjectType::ContainerNode) + container = pNode; + if (pNode->m_pNext == this) + return container; } - return container; + return nullptr; } CXFA_Node* CXFA_Node::GetFirstContainerChild() const { - for (auto* child : children_) { - if (child->GetObjectType() == XFA_ObjectType::ContainerNode) - return child; - } - return nullptr; + CXFA_Node* pNode = m_pChild; + while (pNode && pNode->GetObjectType() != XFA_ObjectType::ContainerNode) + pNode = pNode->m_pNext; + return pNode; } CXFA_Node* CXFA_Node::GetContainerParent() const { @@ -752,17 +714,17 @@ std::vector CXFA_Node::GetNodeList(uint32_t dwTypeFilter, XFA_Element eTypeFilter) { if (eTypeFilter != XFA_Element::Unknown) { std::vector nodes; - for (auto* child : children_) { - if (child->GetElementType() == eTypeFilter) - nodes.push_back(child); + for (CXFA_Node* pChild = m_pChild; pChild; pChild = pChild->m_pNext) { + if (pChild->GetElementType() == eTypeFilter) + nodes.push_back(pChild); } return nodes; } if (dwTypeFilter == (XFA_NODEFILTER_Children | XFA_NODEFILTER_Properties)) { std::vector nodes; - for (auto* child : children_) - nodes.push_back(child); + for (CXFA_Node* pChild = m_pChild; pChild; pChild = pChild->m_pNext) + nodes.push_back(pChild); return nodes; } @@ -773,22 +735,21 @@ std::vector CXFA_Node::GetNodeList(uint32_t dwTypeFilter, bool bFilterProperties = !!(dwTypeFilter & XFA_NODEFILTER_Properties); bool bFilterOneOfProperties = !!(dwTypeFilter & XFA_NODEFILTER_OneOfProperty); std::vector nodes; - for (auto* child : children_) { - if (HasProperty(child->GetElementType())) { - nodes.push_back(child); - continue; - } - - if (bFilterProperties) { - nodes.push_back(child); - } else if (bFilterOneOfProperties && - HasPropertyFlags(child->GetElementType(), - XFA_PROPERTYFLAG_OneOf)) { - nodes.push_back(child); - } else if (bFilterChildren && - (child->GetElementType() == XFA_Element::Variables || - child->GetElementType() == XFA_Element::PageSet)) { - nodes.push_back(child); + for (CXFA_Node* pChild = m_pChild; pChild; pChild = pChild->m_pNext) { + if (!HasProperty(pChild->GetElementType())) { + if (bFilterProperties) { + nodes.push_back(pChild); + } else if (bFilterOneOfProperties && + HasPropertyFlags(pChild->GetElementType(), + XFA_PROPERTYFLAG_OneOf)) { + nodes.push_back(pChild); + } else if (bFilterChildren && + (pChild->GetElementType() == XFA_Element::Variables || + pChild->GetElementType() == XFA_Element::PageSet)) { + nodes.push_back(pChild); + } + } else if (bFilterChildren) { + nodes.push_back(pChild); } } @@ -1130,10 +1091,10 @@ CXFA_Node* CXFA_Node::GetModelNode() { size_t CXFA_Node::CountChildren(XFA_Element eType, bool bOnlyChild) { size_t count = 0; - for (auto* child : children_) { - if (child->GetElementType() != eType && eType != XFA_Element::Unknown) + for (CXFA_Node* pNode = m_pChild; pNode; pNode = pNode->GetNextSibling()) { + if (pNode->GetElementType() != eType && eType != XFA_Element::Unknown) continue; - if (bOnlyChild && HasProperty(child->GetElementType())) + if (bOnlyChild && HasProperty(pNode->GetElementType())) continue; ++count; } @@ -1144,13 +1105,13 @@ CXFA_Node* CXFA_Node::GetChildInternal(size_t index, XFA_Element eType, bool bOnlyChild) { size_t count = 0; - for (auto* child : children_) { - if (child->GetElementType() != eType && eType != XFA_Element::Unknown) + for (CXFA_Node* pNode = m_pChild; pNode; pNode = pNode->GetNextSibling()) { + if (pNode->GetElementType() != eType && eType != XFA_Element::Unknown) continue; - if (bOnlyChild && HasProperty(child->GetElementType())) + if (bOnlyChild && HasProperty(pNode->GetElementType())) continue; if (count == index) - return child; + return pNode; ++count; } @@ -1158,7 +1119,6 @@ CXFA_Node* CXFA_Node::GetChildInternal(size_t index, } void CXFA_Node::InsertChild(int32_t index, CXFA_Node* pNode) { - ASSERT(pNode); ASSERT(!pNode->parent_); pNode->parent_ = this; @@ -1166,14 +1126,33 @@ void CXFA_Node::InsertChild(int32_t index, CXFA_Node* pNode) { ASSERT(ret); (void)ret; // Avoid unused variable warning. - if (children_.empty() || index < 0 || - static_cast(index) >= children_.size()) { - children_.push_back(pNode); - if (index >= 0) - index = children_.size() - 1; + if (!m_pChild || index == 0) { + if (index > 0) + return; + + pNode->m_pNext = m_pChild; + m_pChild = pNode; + index = 0; + } else if (index < 0) { + m_pLastChild->m_pNext = pNode; } else { - children_.insert(children_.begin() + index, pNode); + CXFA_Node* pPrev = m_pChild; + int32_t iCount = 0; + while (++iCount != index && pPrev->m_pNext) + pPrev = pPrev->m_pNext; + + if (index > 0 && index != iCount) + return; + + pNode->m_pNext = pPrev->m_pNext; + pPrev->m_pNext = pNode; + index = iCount; } + if (!pNode->m_pNext) + m_pLastChild = pNode; + + ASSERT(m_pLastChild); + ASSERT(!m_pLastChild->m_pNext); pNode->ClearFlag(XFA_NodeFlag_HasRemovedChildren); CXFA_FFNotify* pNotify = m_pDocument->GetNotify(); @@ -1189,11 +1168,8 @@ void CXFA_Node::InsertChild(int32_t index, CXFA_Node* pNode) { } void CXFA_Node::InsertChild(CXFA_Node* pNode, CXFA_Node* pBeforeNode) { - ASSERT(pNode); - ASSERT(!pNode->parent_); - pNode->parent_ = this; - - if (pBeforeNode && pBeforeNode->parent_ != this) { + if (!pNode || pNode->parent_ || + (pBeforeNode && pBeforeNode->parent_ != this)) { NOTREACHED(); return; } @@ -1202,17 +1178,31 @@ void CXFA_Node::InsertChild(CXFA_Node* pNode, CXFA_Node* pBeforeNode) { ASSERT(ret); (void)ret; // Avoid unused variable warning. - int32_t nIndex = 0; - if (children_.empty() || !pBeforeNode) { - children_.push_back(pNode); + int32_t nIndex = -1; + pNode->parent_ = this; + if (!m_pChild || pBeforeNode == m_pChild) { + pNode->m_pNext = m_pChild; + m_pChild = pNode; + nIndex = 0; + } else if (!pBeforeNode) { + pNode->m_pNext = m_pLastChild->m_pNext; + m_pLastChild->m_pNext = pNode; } else { - for (auto* child : children_) { - if (child == pBeforeNode) - break; - ++nIndex; + nIndex = 1; + CXFA_Node* pPrev = m_pChild; + while (pPrev->m_pNext != pBeforeNode) { + pPrev = pPrev->m_pNext; + nIndex++; } - children_.insert(children_.begin() + nIndex, pNode); + pNode->m_pNext = pPrev->m_pNext; + pPrev->m_pNext = pNode; } + if (!pNode->m_pNext) { + m_pLastChild = pNode; + } + + ASSERT(m_pLastChild); + ASSERT(!m_pLastChild->m_pNext); pNode->ClearFlag(XFA_NodeFlag_HasRemovedChildren); CXFA_FFNotify* pNotify = m_pDocument->GetNotify(); @@ -1226,21 +1216,43 @@ void CXFA_Node::InsertChild(CXFA_Node* pNode, CXFA_Node* pBeforeNode) { } } -void CXFA_Node::RemoveChild(CXFA_Node* pNode, bool bNotify) { - ASSERT(pNode); - ASSERT(pNode->parent_ == this); +CXFA_Node* CXFA_Node::Deprecated_GetPrevSibling() { + if (!parent_) + return nullptr; + + for (CXFA_Node* pSibling = parent_->m_pChild; pSibling; + pSibling = pSibling->m_pNext) { + if (pSibling->m_pNext == this) { + return pSibling; + } + } + return nullptr; +} - auto it = std::find(children_.begin(), children_.end(), pNode); - ASSERT(it != children_.end()); +void CXFA_Node::RemoveChild(CXFA_Node* pNode, bool bNotify) { + if (!pNode || pNode->parent_ != this) { + NOTREACHED(); + return; + } - children_.erase(it); + if (m_pChild == pNode) { + m_pChild = pNode->m_pNext; + if (m_pLastChild == pNode) + m_pLastChild = pNode->m_pNext; + } else { + CXFA_Node* pPrev = pNode->Deprecated_GetPrevSibling(); + pPrev->m_pNext = pNode->m_pNext; + if (m_pLastChild == pNode) + m_pLastChild = pNode->m_pNext ? pNode->m_pNext : pPrev; + } + pNode->m_pNext = nullptr; pNode->parent_ = nullptr; - OnRemoved(bNotify); + ASSERT(!m_pLastChild || !m_pLastChild->m_pNext); + OnRemoved(bNotify); pNode->SetFlag(XFA_NodeFlag_HasRemovedChildren, true); m_pDocument->AddPurgeNode(pNode); - if (IsNeedSavingXMLNode() && pNode->m_pXMLNode) { if (pNode->IsAttributeInXML()) { ASSERT(pNode->m_pXMLNode == m_pXMLNode && @@ -1381,8 +1393,8 @@ void CXFA_Node::ReleaseBindingNodes() { for (auto& node : binding_nodes_) node.Release(); - for (auto* child : children_) - child->ReleaseBindingNodes(); + for (CXFA_Node* pNode = m_pChild; pNode; pNode = pNode->m_pNext) + pNode->ReleaseBindingNodes(); } bool CXFA_Node::IsAttributeInXML() { diff --git a/xfa/fxfa/parser/cxfa_node.h b/xfa/fxfa/parser/cxfa_node.h index c849b19248..c3b2fd1b84 100644 --- a/xfa/fxfa/parser/cxfa_node.h +++ b/xfa/fxfa/parser/cxfa_node.h @@ -178,9 +178,9 @@ class CXFA_Node : public CXFA_Object { CXFA_Node* Clone(bool bRecursive); - CXFA_Node* GetNextSibling() const; + CXFA_Node* GetNextSibling() const { return m_pNext; } CXFA_Node* GetPrevSibling() const; - CXFA_Node* GetFirstChild() const; + CXFA_Node* GetFirstChild() const { return m_pChild; } CXFA_Node* GetParent() const { return parent_.Get(); } CXFA_Node* GetNextContainerSibling() const; @@ -420,6 +420,7 @@ class CXFA_Node : public CXFA_Object { WideString GetValidateMessage(bool bError, bool bVersionFlag); bool HasFlag(XFA_NodeFlag dwFlag) const; + CXFA_Node* Deprecated_GetPrevSibling(); const PropertyData* GetPropertyData(XFA_Element property) const; const AttributeData* GetAttributeData(XFA_Attribute attr) const; Optional GetFirstPropertyWithFlag(uint8_t flag); @@ -488,15 +489,12 @@ class CXFA_Node : public CXFA_Object { CXFA_Event* event, CXFA_EventParam* pEventParam); - CXFA_Node* GetNodeBefore(const CXFA_Node* node) const; - CXFA_Node* GetNodeAfter(const CXFA_Node* node) const; - CXFA_Node* GetContainerBefore(const CXFA_Node* node) const; - CXFA_Node* GetContainerAfter(const CXFA_Node* node) const; - const PropertyData* const m_Properties; const AttributeData* const m_Attributes; const uint32_t m_ValidPackets; - std::vector children_; + CXFA_Node* m_pNext; + CXFA_Node* m_pChild; + CXFA_Node* m_pLastChild; UnownedPtr parent_; CFX_XMLNode* m_pXMLNode; const XFA_PacketType m_ePacket; -- cgit v1.2.3