Replace CXFA_PtrSetTemplate with std::unordered_set.

Building a set on top of a map and ignoring the mapped
value seems wasteful.

Review-Url: https://codereview.chromium.org/1942903003

5 files changed, 108 insertions, 161 deletions

diff --git a/xfa/fxfa/parser/xfa_document.h b/xfa/fxfa/parser/xfa_document.h
index dc50646868..16428ea781 100644
--- a/xfa/fxfa/parser/xfa_document.h
+++ b/xfa/fxfa/parser/xfa_document.h
@@ -115,7 +115,7 @@ class CXFA_Document {
   CScript_LogPseudoModel* m_pScriptLog;
   CScript_LayoutPseudoModel* m_pScriptLayout;
   CScript_SignaturePseudoModel* m_pScriptSignature;
-  CXFA_NodeSet m_rgPurgeNodes;
+  CXFA_NodeSet m_PurgeNodes;
   XFA_VERSION m_eCurVersionMode;
   uint32_t m_dwDocFlags;
   friend class CXFA_SimpleParser;
diff --git a/xfa/fxfa/parser/xfa_document_imp.cpp b/xfa/fxfa/parser/xfa_document_imp.cpp
index 3601c5b621..0421683e07 100644
--- a/xfa/fxfa/parser/xfa_document_imp.cpp
+++ b/xfa/fxfa/parser/xfa_document_imp.cpp
@@ -159,36 +159,37 @@ CXFA_Object* CXFA_Document::GetXFAObject(uint32_t dwNodeNameHash) {
 CXFA_Node* CXFA_Document::CreateNode(uint32_t dwPacket, XFA_ELEMENT eElement) {
   return CreateNode(XFA_GetPacketByID(dwPacket), eElement);
 }
+
 CXFA_Node* CXFA_Document::CreateNode(const XFA_PACKETINFO* pPacket,
                                      XFA_ELEMENT eElement) {
-  if (pPacket == NULL) {
-    return NULL;
-  }
+  if (!pPacket)
+    return nullptr;
+
   const XFA_ELEMENTINFO* pElement = XFA_GetElementByID(eElement);
   if (pElement && (pElement->dwPackets & pPacket->eName)) {
     CXFA_Node* pNode = new CXFA_Node(this, pPacket->eName, pElement->eName);
-    if (pNode) {
-      AddPurgeNode(pNode);
-    }
+    AddPurgeNode(pNode);
     return pNode;
   }
-  return NULL;
+
+  return nullptr;
 }
+
 void CXFA_Document::AddPurgeNode(CXFA_Node* pNode) {
-  m_rgPurgeNodes.Add(pNode);
+  m_PurgeNodes.insert(pNode);
 }
+
 FX_BOOL CXFA_Document::RemovePurgeNode(CXFA_Node* pNode) {
-  return m_rgPurgeNodes.RemoveKey(pNode);
+  return !!m_PurgeNodes.erase(pNode);
 }
+
 void CXFA_Document::PurgeNodes() {
-  FX_POSITION psNode = m_rgPurgeNodes.GetStartPosition();
-  while (psNode) {
-    CXFA_Node* pNode;
-    m_rgPurgeNodes.GetNextAssoc(psNode, pNode);
+  for (CXFA_Node* pNode : m_PurgeNodes)
     delete pNode;
-  }
-  m_rgPurgeNodes.RemoveAll();
+
+  m_PurgeNodes.clear();
 }
+
 void CXFA_Document::SetFlag(uint32_t dwFlag, FX_BOOL bOn) {
   if (bOn) {
     m_dwDocFlags |= dwFlag;
@@ -357,16 +358,13 @@ void CXFA_Document::DoProtoMerge() {
     }
     CFX_WideStringC wsUseVal;
     if (pNode->TryCData(XFA_ATTRIBUTE_Use, wsUseVal) && !wsUseVal.IsEmpty()) {
-      sUseNodes.Add(pNode);
+      sUseNodes.insert(pNode);
     } else if (pNode->TryCData(XFA_ATTRIBUTE_Usehref, wsUseVal) &&
                !wsUseVal.IsEmpty()) {
-      sUseNodes.Add(pNode);
+      sUseNodes.insert(pNode);
     }
   }
-  FX_POSITION pos = sUseNodes.GetStartPosition();
-  while (pos) {
-    CXFA_Node* pUseHrefNode = NULL;
-    sUseNodes.GetNextAssoc(pos, pUseHrefNode);
+  for (CXFA_Node* pUseHrefNode : sUseNodes) {
     CFX_WideString wsUseVal;
     CFX_WideStringC wsURI, wsID, wsSOM;
     if (pUseHrefNode->TryCData(XFA_ATTRIBUTE_Usehref, wsUseVal) &&
diff --git a/xfa/fxfa/parser/xfa_object.h b/xfa/fxfa/parser/xfa_object.h
index 0779cbf2b3..f6267b5998 100644
--- a/xfa/fxfa/parser/xfa_object.h
+++ b/xfa/fxfa/parser/xfa_object.h
@@ -7,6 +7,8 @@
 #ifndef XFA_FXFA_PARSER_XFA_OBJECT_H_
 #define XFA_FXFA_PARSER_XFA_OBJECT_H_
 
+#include <unordered_set>
+
 #include "xfa/fde/xml/fde_xml.h"
 #include "xfa/fxfa/parser/xfa_utils.h"
 #include "xfa/fxjse/cfxjse_arguments.h"
@@ -105,9 +107,9 @@ enum XFA_SOM_MESSAGETYPE {
   XFA_SOM_MandatoryMessage
 };
 
-typedef CFX_ArrayTemplate<CXFA_Node*> CXFA_NodeArray;
-typedef CFX_StackTemplate<CXFA_Node*> CXFA_NodeStack;
-typedef CXFA_PtrSetTemplate<CXFA_Node*> CXFA_NodeSet;
+using CXFA_NodeArray = CFX_ArrayTemplate<CXFA_Node*>;
+using CXFA_NodeStack = CFX_StackTemplate<CXFA_Node*>;
+using CXFA_NodeSet = std::unordered_set<CXFA_Node*>;
 typedef void (*PD_CALLBACK_DUPLICATEDATA)(void*& pData);
 
 struct XFA_MAPDATABLOCKCALLBACKINFO {
diff --git a/xfa/fxfa/parser/xfa_object_imp.cpp b/xfa/fxfa/parser/xfa_object_imp.cpp
index dd5e1b4591..e3631c60f2 100644
--- a/xfa/fxfa/parser/xfa_object_imp.cpp
+++ b/xfa/fxfa/parser/xfa_object_imp.cpp
@@ -6,7 +6,10 @@
 
 #include "xfa/fxfa/parser/xfa_object.h"
 
+#include <memory>
+
 #include "core/fxcrt/include/fx_ext.h"
+#include "third_party/base/stl_util.h"
 #include "xfa/fde/xml/fde_xml_imp.h"
 #include "xfa/fgas/crt/fgas_codepage.h"
 #include "xfa/fgas/crt/fgas_system.h"
@@ -2843,112 +2846,91 @@ XFA_ScriptInstanceManager_ReorderDataNodes_SortNodeArrayByDocumentIdx(
     const CXFA_NodeSet& rgNodeSet,
     CXFA_NodeArray& rgNodeArray,
     CFX_ArrayTemplate<int32_t>& rgIdxArray) {
-  int32_t iCount = rgNodeSet.GetCount();
+  int32_t iCount = pdfium::CollectionSize<int32_t>(rgNodeSet);
   rgNodeArray.SetSize(iCount);
   rgIdxArray.SetSize(iCount);
-  if (iCount == 0) {
+  if (iCount == 0)
     return;
-  }
-  int32_t iIndex = -1, iTotalIndex = -1;
-  CXFA_Node* pNode = NULL;
-  FX_POSITION pos = rgNodeSet.GetStartPosition();
-  rgNodeSet.GetNextAssoc(pos, pNode);
-  for (pNode = pNode->GetNodeItem(XFA_NODEITEM_Parent)
-                   ->GetNodeItem(XFA_NODEITEM_FirstChild);
+
+  int32_t iIndex = -1;
+  int32_t iTotalIndex = -1;
+  CXFA_Node* pCommonParent =
+      (*rgNodeSet.begin())->GetNodeItem(XFA_NODEITEM_Parent);
+  for (CXFA_Node* pNode = pCommonParent->GetNodeItem(XFA_NODEITEM_FirstChild);
        pNode && iIndex < iCount;
        pNode = pNode->GetNodeItem(XFA_NODEITEM_NextSibling)) {
     iTotalIndex++;
-    if (rgNodeSet.Lookup(pNode)) {
+    if (pdfium::ContainsValue(rgNodeSet, pNode)) {
       iIndex++;
       rgNodeArray[iIndex] = pNode;
       rgIdxArray[iIndex] = iTotalIndex;
     }
   }
 }
-struct CXFA_DualNodeArray {
-  CXFA_NodeSet firstNodeList;
-  CXFA_NodeSet secondNodeList;
-};
-static void XFA_ScriptInstanceManager_ReorderDataNodes(CXFA_NodeSet& sSet1,
-                                                       CXFA_NodeSet& sSet2,
-                                                       FX_BOOL bInsertBefore) {
-  CFX_MapPtrTemplate<CXFA_Node*,
-                     CFX_MapPtrTemplate<uint32_t, CXFA_DualNodeArray*>*>
-      rgNodeListMap;
-  FX_POSITION pos;
-  pos = sSet1.GetStartPosition();
-  while (pos) {
-    CXFA_Node* pNode = NULL;
-    sSet1.GetNextAssoc(pos, pNode);
-    CXFA_Node* pParentNode = pNode->GetNodeItem(XFA_NODEITEM_Parent);
-    uint32_t dwNameHash = pNode->GetNameHash();
-    if (!pParentNode || !dwNameHash) {
-      continue;
-    }
-    CFX_MapPtrTemplate<uint32_t, CXFA_DualNodeArray*>* pNodeListChildMap =
-        rgNodeListMap[pParentNode];
-    if (!pNodeListChildMap) {
-      rgNodeListMap[pParentNode] = pNodeListChildMap =
-          new CFX_MapPtrTemplate<uint32_t, CXFA_DualNodeArray*>;
-    }
-    CXFA_DualNodeArray* pDualNodeArray = (*pNodeListChildMap)[dwNameHash];
-    if (!pDualNodeArray) {
-      (*pNodeListChildMap)[dwNameHash] = pDualNodeArray =
-          new CXFA_DualNodeArray;
-    }
-    pDualNodeArray->firstNodeList.Add(pNode);
-  }
-  pos = sSet2.GetStartPosition();
-  while (pos) {
-    CXFA_Node* pNode = NULL;
-    sSet2.GetNextAssoc(pos, pNode);
-    CXFA_Node* pParentNode = pNode->GetNodeItem(XFA_NODEITEM_Parent);
-    uint32_t dwNameHash = pNode->GetNameHash();
-    if (!pParentNode || !dwNameHash) {
-      continue;
-    }
-    CFX_MapPtrTemplate<uint32_t, CXFA_DualNodeArray*>* pNodeListChildMap =
-        rgNodeListMap[pParentNode];
-    if (!pNodeListChildMap) {
-      rgNodeListMap[pParentNode] = pNodeListChildMap =
-          new CFX_MapPtrTemplate<uint32_t, CXFA_DualNodeArray*>;
-    }
-    CXFA_DualNodeArray* pDualNodeArray = (*pNodeListChildMap)[dwNameHash];
-    if (!pDualNodeArray) {
-      (*pNodeListChildMap)[dwNameHash] = pDualNodeArray =
-          new CXFA_DualNodeArray;
-    }
-    if (pDualNodeArray->firstNodeList.Lookup(pNode)) {
-      pDualNodeArray->firstNodeList.RemoveKey(pNode);
-    } else {
-      pDualNodeArray->secondNodeList.Add(pNode);
-    }
-  }
-  pos = rgNodeListMap.GetStartPosition();
-  while (pos) {
-    CXFA_Node* pParentNode = NULL;
-    CFX_MapPtrTemplate<uint32_t, CXFA_DualNodeArray*>* pNodeListChildMap = NULL;
-    rgNodeListMap.GetNextAssoc(pos, pParentNode, pNodeListChildMap);
-    if (!pNodeListChildMap) {
+
+using CXFA_NodeSetPair = std::pair<CXFA_NodeSet, CXFA_NodeSet>;
+using CXFA_NodeSetPairMap =
+    std::map<uint32_t, std::unique_ptr<CXFA_NodeSetPair>>;
+using CXFA_NodeSetPairMapMap =
+    std::map<CXFA_Node*, std::unique_ptr<CXFA_NodeSetPairMap>>;
+
+static CXFA_NodeSetPair* NodeSetPairForNode(CXFA_Node* pNode,
+                                            CXFA_NodeSetPairMapMap* pMap) {
+  CXFA_Node* pParentNode = pNode->GetNodeItem(XFA_NODEITEM_Parent);
+  uint32_t dwNameHash = pNode->GetNameHash();
+  if (!pParentNode || !dwNameHash)
+    return nullptr;
+
+  if (!(*pMap)[pParentNode])
+    (*pMap)[pParentNode].reset(new CXFA_NodeSetPairMap);
+
+  CXFA_NodeSetPairMap* pNodeSetPairMap = (*pMap)[pParentNode].get();
+  if (!(*pNodeSetPairMap)[dwNameHash])
+    (*pNodeSetPairMap)[dwNameHash].reset(new CXFA_NodeSetPair);
+
+  return (*pNodeSetPairMap)[dwNameHash].get();
+}
+
+static void XFA_ScriptInstanceManager_ReorderDataNodes(
+    const CXFA_NodeSet& sSet1,
+    const CXFA_NodeSet& sSet2,
+    FX_BOOL bInsertBefore) {
+  CXFA_NodeSetPairMapMap rgMap;
+  for (CXFA_Node* pNode : sSet1) {
+    CXFA_NodeSetPair* pNodeSetPair = NodeSetPairForNode(pNode, &rgMap);
+    if (pNodeSetPair)
+      pNodeSetPair->first.insert(pNode);
+  }
+  for (CXFA_Node* pNode : sSet2) {
+    CXFA_NodeSetPair* pNodeSetPair = NodeSetPairForNode(pNode, &rgMap);
+    if (pNodeSetPair) {
+      if (pdfium::ContainsValue(pNodeSetPair->first, pNode))
+        pNodeSetPair->first.erase(pNode);
+      else
+        pNodeSetPair->second.insert(pNode);
+    }
+  }
+  for (const auto& iter1 : rgMap) {
+    CXFA_NodeSetPairMap* pNodeSetPairMap = iter1.second.get();
+    if (!pNodeSetPairMap) {
       continue;
     }
-    FX_POSITION childpos = pNodeListChildMap->GetStartPosition();
-    while (childpos) {
-      uint32_t dwNameHash = 0;
-      CXFA_DualNodeArray* pDualNodeArray = NULL;
-      pNodeListChildMap->GetNextAssoc(childpos, dwNameHash, pDualNodeArray);
-      if (!pDualNodeArray) {
+    for (const auto& iter2 : *pNodeSetPairMap) {
+      CXFA_NodeSetPair* pNodeSetPair = iter2.second.get();
+      if (!pNodeSetPair) {
         continue;
       }
-      if (pDualNodeArray->firstNodeList.GetCount() != 0 &&
-          pDualNodeArray->secondNodeList.GetCount() != 0) {
-        CXFA_NodeArray rgNodeArray1, rgNodeArray2;
-        CFX_ArrayTemplate<int32_t> rgIdxArray1, rgIdxArray2;
+      if (!pNodeSetPair->first.empty() && !pNodeSetPair->second.empty()) {
+        CXFA_NodeArray rgNodeArray1;
+        CXFA_NodeArray rgNodeArray2;
+        CFX_ArrayTemplate<int32_t> rgIdxArray1;
+        CFX_ArrayTemplate<int32_t> rgIdxArray2;
         XFA_ScriptInstanceManager_ReorderDataNodes_SortNodeArrayByDocumentIdx(
-            pDualNodeArray->firstNodeList, rgNodeArray1, rgIdxArray1);
+            pNodeSetPair->first, rgNodeArray1, rgIdxArray1);
         XFA_ScriptInstanceManager_ReorderDataNodes_SortNodeArrayByDocumentIdx(
-            pDualNodeArray->secondNodeList, rgNodeArray2, rgIdxArray2);
-        CXFA_Node *pParentNode = NULL, *pBeforeNode = NULL;
+            pNodeSetPair->second, rgNodeArray2, rgIdxArray2);
+        CXFA_Node* pParentNode = nullptr;
+        CXFA_Node* pBeforeNode = nullptr;
         if (bInsertBefore) {
           pBeforeNode = rgNodeArray2[0];
           pParentNode = pBeforeNode->GetNodeItem(XFA_NODEITEM_Parent);
@@ -2957,19 +2939,17 @@ static void XFA_ScriptInstanceManager_ReorderDataNodes(CXFA_NodeSet& sSet1,
           pParentNode = pLastNode->GetNodeItem(XFA_NODEITEM_Parent);
           pBeforeNode = pLastNode->GetNodeItem(XFA_NODEITEM_NextSibling);
         }
-        for (int32_t iIdx = 0, iCount = rgIdxArray1.GetSize(); iIdx < iCount;
-             iIdx++) {
+        for (int32_t iIdx = 0; iIdx < rgIdxArray1.GetSize(); iIdx++) {
           CXFA_Node* pCurNode = rgNodeArray1[iIdx];
           pParentNode->RemoveChild(pCurNode);
           pParentNode->InsertChild(pCurNode, pBeforeNode);
         }
       }
-      delete pDualNodeArray;
     }
-    pNodeListChildMap->RemoveAll();
+    pNodeSetPairMap->clear();
   }
-  rgNodeListMap.RemoveAll();
 }
+
 static void XFA_ScriptInstanceManager_InsertItem(
     CXFA_Node* pInstMgrNode,
     CXFA_Node* pNewInstance,
@@ -2991,7 +2971,8 @@ static void XFA_ScriptInstanceManager_InsertItem(
     pInstMgrNode->GetNodeItem(XFA_NODEITEM_Parent)
         ->InsertChild(pNewInstance, pNextSibling);
     if (bMoveDataBindingNodes) {
-      CXFA_NodeSet sNew, sAfter;
+      CXFA_NodeSet sNew;
+      CXFA_NodeSet sAfter;
       CXFA_NodeIteratorTemplate<CXFA_Node,
                                 CXFA_TraverseStrategy_XFAContainerNode>
           sIteratorNew(pNewInstance);
@@ -3001,7 +2982,7 @@ static void XFA_ScriptInstanceManager_InsertItem(
         if (!pDataNode) {
           continue;
         }
-        sNew.Add(pDataNode);
+        sNew.insert(pDataNode);
       }
       CXFA_NodeIteratorTemplate<CXFA_Node,
                                 CXFA_TraverseStrategy_XFAContainerNode>
@@ -3012,7 +2993,7 @@ static void XFA_ScriptInstanceManager_InsertItem(
         if (!pDataNode) {
           continue;
         }
-        sAfter.Add(pDataNode);
+        sAfter.insert(pDataNode);
       }
       XFA_ScriptInstanceManager_ReorderDataNodes(sNew, sAfter, FALSE);
     }
@@ -3022,7 +3003,8 @@ static void XFA_ScriptInstanceManager_InsertItem(
     pInstMgrNode->GetNodeItem(XFA_NODEITEM_Parent)
         ->InsertChild(pNewInstance, pBeforeInstance);
     if (bMoveDataBindingNodes) {
-      CXFA_NodeSet sNew, sBefore;
+      CXFA_NodeSet sNew;
+      CXFA_NodeSet sBefore;
       CXFA_NodeIteratorTemplate<CXFA_Node,
                                 CXFA_TraverseStrategy_XFAContainerNode>
           sIteratorNew(pNewInstance);
@@ -3032,7 +3014,7 @@ static void XFA_ScriptInstanceManager_InsertItem(
         if (!pDataNode) {
           continue;
         }
-        sNew.Add(pDataNode);
+        sNew.insert(pDataNode);
       }
       CXFA_NodeIteratorTemplate<CXFA_Node,
                                 CXFA_TraverseStrategy_XFAContainerNode>
@@ -3043,7 +3025,7 @@ static void XFA_ScriptInstanceManager_InsertItem(
         if (!pDataNode) {
           continue;
         }
-        sBefore.Add(pDataNode);
+        sBefore.insert(pDataNode);
       }
       XFA_ScriptInstanceManager_ReorderDataNodes(sNew, sBefore, TRUE);
     }
diff --git a/xfa/fxfa/parser/xfa_utils.h b/xfa/fxfa/parser/xfa_utils.h
index c2a0fbbb82..821e485e25 100644
--- a/xfa/fxfa/parser/xfa_utils.h
+++ b/xfa/fxfa/parser/xfa_utils.h
@@ -13,6 +13,8 @@
 class CFDE_XMLElement;
 class CFDE_XMLNode;
 class CXFA_LocaleValue;
+class CXFA_Node;
+class CXFA_WidgetData;
 
 inline FX_BOOL XFA_IsSpace(FX_WCHAR c) {
   return (c == 0x20) || (c == 0x0d) || (c == 0x0a) || (c == 0x09);
@@ -162,43 +164,6 @@ class CXFA_NodeIteratorTemplate {
   NodeType* m_pRoot;
   CFX_StackTemplate<NodeType*> m_NodeStack;
 };
-template <class KeyType>
-class CXFA_PtrSetTemplate : private CFX_MapPtrToPtr {
- public:
-  CXFA_PtrSetTemplate() : CFX_MapPtrToPtr(10) {}
-
-  int GetCount() const { return CFX_MapPtrToPtr::GetCount(); }
-
-  FX_BOOL IsEmpty() const { return CFX_MapPtrToPtr::IsEmpty(); }
-
-  FX_BOOL Lookup(KeyType key) const {
-    void* pValue = NULL;
-    return CFX_MapPtrToPtr::Lookup((void*)key, pValue);
-  }
-
-  FX_BOOL operator[](KeyType key) { return Lookup(key); }
-
-  void Add(KeyType key) { CFX_MapPtrToPtr::SetAt((void*)key, (void*)key); }
-
-  FX_BOOL RemoveKey(KeyType key) {
-    return CFX_MapPtrToPtr::RemoveKey((void*)key);
-  }
-
-  void RemoveAll() { CFX_MapPtrToPtr::RemoveAll(); }
-
-  FX_POSITION GetStartPosition() const {
-    return CFX_MapPtrToPtr::GetStartPosition();
-  }
-
-  void GetNextAssoc(FX_POSITION& rNextPosition, KeyType& rKey) const {
-    void* pKey = NULL;
-    void* pValue = NULL;
-    CFX_MapPtrToPtr::GetNextAssoc(rNextPosition, pKey, pValue);
-    rKey = (KeyType)(uintptr_t)pKey;
-  }
-};
-class CXFA_Node;
-class CXFA_WidgetData;
 
 CXFA_Node* XFA_CreateUIChild(CXFA_Node* pNode, XFA_ELEMENT& eWidgetType);
 CXFA_LocaleValue XFA_GetLocaleValue(CXFA_WidgetData* pWidgetData);