Merge to XFA: Remove CGW_ArrayTemplate and its O(n^2 log n) sort.
Original Review URL: https://codereview.chromium.org/1652613002 .
(cherry picked from commit 0841b0f37678ba4962247f5636e9390718fc027e)
TBR=thestig@chromium.org
Review URL: https://codereview.chromium.org/1657663003 .
diff --git a/fpdfsdk/include/fsdk_baseform.h b/fpdfsdk/include/fsdk_baseform.h
index 023ea74..0d72639 100644
--- a/fpdfsdk/include/fsdk_baseform.h
+++ b/fpdfsdk/include/fsdk_baseform.h
@@ -14,12 +14,13 @@
#endif
#include <map>
+#include <vector>
#include "core/include/fpdfapi/fpdf_parser.h"
#include "core/include/fpdfdoc/fpdf_doc.h"
#include "core/include/fxcrt/fx_basic.h"
#include "core/include/fxge/fx_dib.h"
-#include "fsdk_baseannot.h"
+#include "fpdfsdk/include/fsdk_baseannot.h"
class CFFL_FormFiller;
class CPDFSDK_Annot;
@@ -373,14 +374,10 @@
FX_BOOL m_bNeedHightlight[kNumFieldTypes];
};
-#define BAI_STRUCTURE 0
-#define BAI_ROW 1
-#define BAI_COLUMN 2
-
-#define CPDFSDK_Annots CFX_ArrayTemplate<CPDFSDK_Annot*>
-#define CPDFSDK_SortAnnots CGW_ArrayTemplate<CPDFSDK_Annot*>
class CBA_AnnotIterator {
public:
+ enum TabOrder { STRUCTURE = 0, ROW, COLUMN };
+
CBA_AnnotIterator(CPDFSDK_PageView* pPageView,
const CFX_ByteString& sType,
const CFX_ByteString& sSubType);
@@ -393,15 +390,19 @@
private:
void GenerateResults();
- static int CompareByLeft(CPDFSDK_Annot* p1, CPDFSDK_Annot* p2);
- static int CompareByTop(CPDFSDK_Annot* p1, CPDFSDK_Annot* p2);
- static CPDF_Rect GetAnnotRect(CPDFSDK_Annot* pAnnot);
+ static CPDF_Rect GetAnnotRect(const CPDFSDK_Annot* pAnnot);
+ // Function signature compatible with std::sort().
+ static bool CompareByLeftAscending(const CPDFSDK_Annot* p1,
+ const CPDFSDK_Annot* p2);
+ static bool CompareByTopDescending(const CPDFSDK_Annot* p1,
+ const CPDFSDK_Annot* p2);
+
+ TabOrder m_eTabOrder;
CPDFSDK_PageView* m_pPageView;
CFX_ByteString m_sType;
CFX_ByteString m_sSubType;
- int m_nTabs;
- CPDFSDK_Annots m_Annots;
+ std::vector<CPDFSDK_Annot*> m_Annots;
};
#endif // FPDFSDK_INCLUDE_FSDK_BASEFORM_H_
diff --git a/fpdfsdk/include/fsdk_mgr.h b/fpdfsdk/include/fsdk_mgr.h
index e53be1b..042ba38 100644
--- a/fpdfsdk/include/fsdk_mgr.h
+++ b/fpdfsdk/include/fsdk_mgr.h
@@ -561,6 +561,7 @@
FX_BOOL m_bChangeMask;
FX_BOOL m_bBeingDestroyed;
};
+
class CPDFSDK_PageView final {
public:
CPDFSDK_PageView(CPDFSDK_Document* pSDKDoc, UnderlyingPageType* page);
@@ -667,77 +668,4 @@
FX_BOOL m_bLocked;
};
-template <class TYPE>
-class CGW_ArrayTemplate : public CFX_ArrayTemplate<TYPE> {
- public:
- CGW_ArrayTemplate() {}
- ~CGW_ArrayTemplate() {}
-
- typedef int (*LP_COMPARE)(TYPE p1, TYPE p2);
-
- void Sort(LP_COMPARE pCompare, FX_BOOL bAscent = TRUE) {
- int nSize = this->GetSize();
- QuickSort(0, nSize - 1, bAscent, pCompare);
- }
-
- private:
- void QuickSort(FX_UINT nStartPos,
- FX_UINT nStopPos,
- FX_BOOL bAscend,
- LP_COMPARE pCompare) {
- if (nStartPos >= nStopPos)
- return;
-
- if ((nStopPos - nStartPos) == 1) {
- TYPE Value1 = this->GetAt(nStartPos);
- TYPE Value2 = this->GetAt(nStopPos);
-
- int iGreate = (*pCompare)(Value1, Value2);
- if ((bAscend && iGreate > 0) || (!bAscend && iGreate < 0)) {
- this->SetAt(nStartPos, Value2);
- this->SetAt(nStopPos, Value1);
- }
- return;
- }
-
- FX_UINT m = nStartPos + (nStopPos - nStartPos) / 2;
- FX_UINT i = nStartPos;
-
- TYPE Value = this->GetAt(m);
-
- while (i < m) {
- TYPE temp = this->GetAt(i);
-
- int iGreate = (*pCompare)(temp, Value);
- if ((bAscend && iGreate > 0) || (!bAscend && iGreate < 0)) {
- this->InsertAt(m + 1, temp);
- this->RemoveAt(i);
- m--;
- } else {
- i++;
- }
- }
-
- FX_UINT j = nStopPos;
-
- while (j > m) {
- TYPE temp = this->GetAt(j);
-
- int iGreate = (*pCompare)(temp, Value);
- if ((bAscend && iGreate < 0) || (!bAscend && iGreate > 0)) {
- this->RemoveAt(j);
- this->InsertAt(m, temp);
- m++;
- } else {
- j--;
- }
- }
-
- if (nStartPos < m)
- QuickSort(nStartPos, m, bAscend, pCompare);
- if (nStopPos > m)
- QuickSort(m, nStopPos, bAscend, pCompare);
- }
-};
-
#endif // FPDFSDK_INCLUDE_FSDK_MGR_H_
diff --git a/fpdfsdk/src/fsdk_baseform.cpp b/fpdfsdk/src/fsdk_baseform.cpp
index b248094..72c192a 100644
--- a/fpdfsdk/src/fsdk_baseform.cpp
+++ b/fpdfsdk/src/fsdk_baseform.cpp
@@ -6,6 +6,7 @@
#include "fpdfsdk/include/fsdk_baseform.h"
+#include <algorithm>
#include <memory>
#include "fpdfsdk/include/formfiller/FFL_FormFiller.h"
@@ -2741,177 +2742,125 @@
CBA_AnnotIterator::CBA_AnnotIterator(CPDFSDK_PageView* pPageView,
const CFX_ByteString& sType,
const CFX_ByteString& sSubType)
- : m_pPageView(pPageView),
+ : m_eTabOrder(STRUCTURE),
+ m_pPageView(pPageView),
m_sType(sType),
- m_sSubType(sSubType),
- m_nTabs(BAI_STRUCTURE) {
+ m_sSubType(sSubType) {
CPDF_Page* pPDFPage = m_pPageView->GetPDFPage();
CFX_ByteString sTabs = pPDFPage->m_pFormDict->GetStringBy("Tabs");
-
- if (sTabs == "R") {
- m_nTabs = BAI_ROW;
- } else if (sTabs == "C") {
- m_nTabs = BAI_COLUMN;
- } else {
- m_nTabs = BAI_STRUCTURE;
- }
+ if (sTabs == "R")
+ m_eTabOrder = ROW;
+ else if (sTabs == "C")
+ m_eTabOrder = COLUMN;
GenerateResults();
}
CBA_AnnotIterator::~CBA_AnnotIterator() {
- m_Annots.RemoveAll();
}
CPDFSDK_Annot* CBA_AnnotIterator::GetFirstAnnot() {
- if (m_Annots.GetSize() > 0)
- return m_Annots[0];
-
- return NULL;
+ return m_Annots.empty() ? nullptr : m_Annots.front();
}
CPDFSDK_Annot* CBA_AnnotIterator::GetLastAnnot() {
- if (m_Annots.GetSize() > 0)
- return m_Annots[m_Annots.GetSize() - 1];
-
- return NULL;
+ return m_Annots.empty() ? nullptr : m_Annots.back();
}
CPDFSDK_Annot* CBA_AnnotIterator::GetNextAnnot(CPDFSDK_Annot* pAnnot) {
- for (int i = 0, sz = m_Annots.GetSize(); i < sz; ++i) {
- if (m_Annots[i] == pAnnot)
- return (i + 1 < sz) ? m_Annots[i + 1] : m_Annots[0];
- }
- return NULL;
+ auto iter = std::find(m_Annots.begin(), m_Annots.end(), pAnnot);
+ if (iter == m_Annots.end())
+ return nullptr;
+ ++iter;
+ if (iter == m_Annots.end())
+ iter = m_Annots.begin();
+ return *iter;
}
CPDFSDK_Annot* CBA_AnnotIterator::GetPrevAnnot(CPDFSDK_Annot* pAnnot) {
- for (int i = 0, sz = m_Annots.GetSize(); i < sz; ++i) {
- if (m_Annots[i] == pAnnot)
- return (i - 1 >= 0) ? m_Annots[i - 1] : m_Annots[sz - 1];
- }
- return NULL;
+ auto iter = std::find(m_Annots.begin(), m_Annots.end(), pAnnot);
+ if (iter == m_Annots.end())
+ return nullptr;
+ if (iter == m_Annots.begin())
+ iter = m_Annots.end();
+ return *(--iter);
}
-int CBA_AnnotIterator::CompareByLeft(CPDFSDK_Annot* p1, CPDFSDK_Annot* p2) {
- ASSERT(p1);
- ASSERT(p2);
-
- CPDF_Rect rcAnnot1 = GetAnnotRect(p1);
- CPDF_Rect rcAnnot2 = GetAnnotRect(p2);
-
- if (rcAnnot1.left < rcAnnot2.left)
- return -1;
- if (rcAnnot1.left > rcAnnot2.left)
- return 1;
- return 0;
+// static
+bool CBA_AnnotIterator::CompareByLeftAscending(const CPDFSDK_Annot* p1,
+ const CPDFSDK_Annot* p2) {
+ return GetAnnotRect(p1).left < GetAnnotRect(p2).left;
}
-int CBA_AnnotIterator::CompareByTop(CPDFSDK_Annot* p1, CPDFSDK_Annot* p2) {
- ASSERT(p1);
- ASSERT(p2);
-
- CPDF_Rect rcAnnot1 = GetAnnotRect(p1);
- CPDF_Rect rcAnnot2 = GetAnnotRect(p2);
-
- if (rcAnnot1.top < rcAnnot2.top)
- return -1;
- if (rcAnnot1.top > rcAnnot2.top)
- return 1;
- return 0;
+// static
+bool CBA_AnnotIterator::CompareByTopDescending(const CPDFSDK_Annot* p1,
+ const CPDFSDK_Annot* p2) {
+ return GetAnnotRect(p1).top > GetAnnotRect(p2).top;
}
void CBA_AnnotIterator::GenerateResults() {
- switch (m_nTabs) {
- case BAI_STRUCTURE: {
+ switch (m_eTabOrder) {
+ case STRUCTURE: {
for (size_t i = 0; i < m_pPageView->CountAnnots(); ++i) {
CPDFSDK_Annot* pAnnot = m_pPageView->GetAnnot(i);
if (pAnnot->GetType() == m_sType && pAnnot->GetSubType() == m_sSubType)
- m_Annots.Add(pAnnot);
+ m_Annots.push_back(pAnnot);
}
- break;
- }
- case BAI_ROW: {
- CPDFSDK_SortAnnots sa;
+ } break;
+ case ROW: {
+ std::vector<CPDFSDK_Annot*> sa;
for (size_t i = 0; i < m_pPageView->CountAnnots(); ++i) {
CPDFSDK_Annot* pAnnot = m_pPageView->GetAnnot(i);
if (pAnnot->GetType() == m_sType && pAnnot->GetSubType() == m_sSubType)
- sa.Add(pAnnot);
+ sa.push_back(pAnnot);
}
- if (sa.GetSize() > 0)
- sa.Sort(CBA_AnnotIterator::CompareByLeft);
-
- while (sa.GetSize() > 0) {
+ std::sort(sa.begin(), sa.end(), CompareByLeftAscending);
+ while (!sa.empty()) {
int nLeftTopIndex = -1;
FX_FLOAT fTop = 0.0f;
-
- for (int i = sa.GetSize() - 1; i >= 0; i--) {
- CPDFSDK_Annot* pAnnot = sa.GetAt(i);
- ASSERT(pAnnot);
-
- CPDF_Rect rcAnnot = GetAnnotRect(pAnnot);
-
+ for (int i = sa.size() - 1; i >= 0; i--) {
+ CPDF_Rect rcAnnot = GetAnnotRect(sa[i]);
if (rcAnnot.top > fTop) {
nLeftTopIndex = i;
fTop = rcAnnot.top;
}
}
-
if (nLeftTopIndex >= 0) {
- CPDFSDK_Annot* pLeftTopAnnot = sa.GetAt(nLeftTopIndex);
- ASSERT(pLeftTopAnnot);
-
+ CPDFSDK_Annot* pLeftTopAnnot = sa[nLeftTopIndex];
CPDF_Rect rcLeftTop = GetAnnotRect(pLeftTopAnnot);
+ m_Annots.push_back(pLeftTopAnnot);
+ sa.erase(sa.begin() + nLeftTopIndex);
- m_Annots.Add(pLeftTopAnnot);
- sa.RemoveAt(nLeftTopIndex);
-
- CFX_ArrayTemplate<int> aSelect;
-
- for (int i = 0, sz = sa.GetSize(); i < sz; ++i) {
- CPDFSDK_Annot* pAnnot = sa.GetAt(i);
- ASSERT(pAnnot);
-
- CPDF_Rect rcAnnot = GetAnnotRect(pAnnot);
+ std::vector<int> aSelect;
+ for (int i = 0; i < sa.size(); ++i) {
+ CPDF_Rect rcAnnot = GetAnnotRect(sa[i]);
FX_FLOAT fCenterY = (rcAnnot.top + rcAnnot.bottom) / 2.0f;
if (fCenterY > rcLeftTop.bottom && fCenterY < rcLeftTop.top)
- aSelect.Add(i);
+ aSelect.push_back(i);
}
+ for (int i = 0; i < aSelect.size(); ++i)
+ m_Annots.push_back(sa[aSelect[i]]);
- for (int i = 0, sz = aSelect.GetSize(); i < sz; ++i)
- m_Annots.Add(sa[aSelect[i]]);
-
- for (int i = aSelect.GetSize() - 1; i >= 0; --i)
- sa.RemoveAt(aSelect[i]);
-
- aSelect.RemoveAll();
+ for (int i = aSelect.size() - 1; i >= 0; --i)
+ sa.erase(sa.begin() + aSelect[i]);
}
}
- sa.RemoveAll();
- break;
- }
- case BAI_COLUMN: {
- CPDFSDK_SortAnnots sa;
+ } break;
+ case COLUMN: {
+ std::vector<CPDFSDK_Annot*> sa;
for (size_t i = 0; i < m_pPageView->CountAnnots(); ++i) {
CPDFSDK_Annot* pAnnot = m_pPageView->GetAnnot(i);
if (pAnnot->GetType() == m_sType && pAnnot->GetSubType() == m_sSubType)
- sa.Add(pAnnot);
+ sa.push_back(pAnnot);
}
- if (sa.GetSize() > 0)
- sa.Sort(CBA_AnnotIterator::CompareByTop, FALSE);
-
- while (sa.GetSize() > 0) {
+ std::sort(sa.begin(), sa.end(), CompareByTopDescending);
+ while (!sa.empty()) {
int nLeftTopIndex = -1;
FX_FLOAT fLeft = -1.0f;
-
- for (int i = sa.GetSize() - 1; i >= 0; --i) {
- CPDFSDK_Annot* pAnnot = sa.GetAt(i);
- ASSERT(pAnnot);
-
- CPDF_Rect rcAnnot = GetAnnotRect(pAnnot);
-
+ for (int i = sa.size() - 1; i >= 0; --i) {
+ CPDF_Rect rcAnnot = GetAnnotRect(sa[i]);
if (fLeft < 0) {
nLeftTopIndex = 0;
fLeft = rcAnnot.left;
@@ -2922,41 +2871,31 @@
}
if (nLeftTopIndex >= 0) {
- CPDFSDK_Annot* pLeftTopAnnot = sa.GetAt(nLeftTopIndex);
- ASSERT(pLeftTopAnnot);
-
+ CPDFSDK_Annot* pLeftTopAnnot = sa[nLeftTopIndex];
CPDF_Rect rcLeftTop = GetAnnotRect(pLeftTopAnnot);
+ m_Annots.push_back(pLeftTopAnnot);
+ sa.erase(sa.begin() + nLeftTopIndex);
- m_Annots.Add(pLeftTopAnnot);
- sa.RemoveAt(nLeftTopIndex);
-
- CFX_ArrayTemplate<int> aSelect;
- for (int i = 0, sz = sa.GetSize(); i < sz; ++i) {
- CPDFSDK_Annot* pAnnot = sa.GetAt(i);
- ASSERT(pAnnot);
-
- CPDF_Rect rcAnnot = GetAnnotRect(pAnnot);
+ std::vector<int> aSelect;
+ for (int i = 0; i < sa.size(); ++i) {
+ CPDF_Rect rcAnnot = GetAnnotRect(sa[i]);
FX_FLOAT fCenterX = (rcAnnot.left + rcAnnot.right) / 2.0f;
if (fCenterX > rcLeftTop.left && fCenterX < rcLeftTop.right)
- aSelect.Add(i);
+ aSelect.push_back(i);
}
+ for (int i = 0; i < aSelect.size(); ++i)
+ m_Annots.push_back(sa[aSelect[i]]);
- for (int i = 0, sz = aSelect.GetSize(); i < sz; ++i)
- m_Annots.Add(sa[aSelect[i]]);
-
- for (int i = aSelect.GetSize() - 1; i >= 0; --i)
- sa.RemoveAt(aSelect[i]);
-
- aSelect.RemoveAll();
+ for (int i = aSelect.size() - 1; i >= 0; --i)
+ sa.erase(sa.begin() + aSelect[i]);
}
}
- sa.RemoveAll();
break;
}
}
}
-CPDF_Rect CBA_AnnotIterator::GetAnnotRect(CPDFSDK_Annot* pAnnot) {
+CPDF_Rect CBA_AnnotIterator::GetAnnotRect(const CPDFSDK_Annot* pAnnot) {
CPDF_Rect rcAnnot;
pAnnot->GetPDFAnnot()->GetRect(rcAnnot);
return rcAnnot;
diff --git a/fpdfsdk/src/javascript/Field.cpp b/fpdfsdk/src/javascript/Field.cpp
index 1b55515..24acd60 100644
--- a/fpdfsdk/src/javascript/Field.cpp
+++ b/fpdfsdk/src/javascript/Field.cpp
@@ -6,6 +6,10 @@
#include "Field.h"
+#include <algorithm>
+#include <memory>
+#include <vector>
+
#include "Document.h"
#include "Icon.h"
#include "JS_Context.h"
@@ -3082,10 +3086,6 @@
return TRUE;
}
-int JS_COMPARESTRING(CFX_WideString* ps1, CFX_WideString* ps2) {
- return ps1->Compare(*ps2);
-}
-
FX_BOOL Field::getArray(IJS_Context* cc,
const std::vector<CJS_Value>& params,
CJS_Value& vRet,
@@ -3094,35 +3094,38 @@
if (FieldArray.empty())
return FALSE;
- CGW_ArrayTemplate<CFX_WideString*> swSort;
+ std::vector<std::unique_ptr<CFX_WideString>> swSort;
+ for (CPDF_FormField* pFormField : FieldArray) {
+ swSort.push_back(std::unique_ptr<CFX_WideString>(
+ new CFX_WideString(pFormField->GetFullName())));
+ }
- for (CPDF_FormField* pFormField : FieldArray)
- swSort.Add(new CFX_WideString(pFormField->GetFullName()));
- swSort.Sort(JS_COMPARESTRING);
+ std::sort(
+ swSort.begin(), swSort.end(),
+ [](const std::unique_ptr<CFX_WideString>& p1,
+ const std::unique_ptr<CFX_WideString>& p2) { return *p1 < *p2; });
CJS_Context* pContext = (CJS_Context*)cc;
CJS_Runtime* pRuntime = pContext->GetJSRuntime();
- ASSERT(pRuntime);
-
CJS_Array FormFieldArray(pRuntime);
- for (int j = 0, jsz = swSort.GetSize(); j < jsz; j++) {
- std::unique_ptr<CFX_WideString> pStr(swSort.GetAt(j));
+
+ int j = 0;
+ for (const auto& pStr : swSort) {
v8::Local<v8::Object> pObj = FXJS_NewFxDynamicObj(
pRuntime->GetIsolate(), pRuntime, CJS_Field::g_nObjDefnID);
ASSERT(!pObj.IsEmpty());
CJS_Field* pJSField =
- (CJS_Field*)FXJS_GetPrivate(pRuntime->GetIsolate(), pObj);
- Field* pField = (Field*)pJSField->GetEmbedObject();
+ static_cast<CJS_Field*>(FXJS_GetPrivate(pRuntime->GetIsolate(), pObj));
+ Field* pField = static_cast<Field*>(pJSField->GetEmbedObject());
pField->AttachField(m_pJSDoc, *pStr);
CJS_Value FormFieldValue(pRuntime);
FormFieldValue = pJSField;
- FormFieldArray.SetElement(j, FormFieldValue);
+ FormFieldArray.SetElement(j++, FormFieldValue);
}
vRet = FormFieldArray;
- swSort.RemoveAll();
return TRUE;
}
