From 0841b0f37678ba4962247f5636e9390718fc027e Mon Sep 17 00:00:00 2001 From: Tom Sepez Date: Mon, 1 Feb 2016 13:37:38 -0800 Subject: Remove CGW_ArrayTemplate and its O(n^2 log n) sort. R=thestig@chromium.org Review URL: https://codereview.chromium.org/1652613002 . --- fpdfsdk/include/fsdk_baseform.h | 25 ++--- fpdfsdk/include/fsdk_mgr.h | 74 +------------- fpdfsdk/src/fsdk_baseform.cpp | 207 ++++++++++++++------------------------- fpdfsdk/src/javascript/Field.cpp | 35 ++++--- 4 files changed, 106 insertions(+), 235 deletions(-) diff --git a/fpdfsdk/include/fsdk_baseform.h b/fpdfsdk/include/fsdk_baseform.h index f553bd8848..0290ef021d 100644 --- a/fpdfsdk/include/fsdk_baseform.h +++ b/fpdfsdk/include/fsdk_baseform.h @@ -14,12 +14,13 @@ #endif #include +#include #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; @@ -273,14 +274,10 @@ class CPDFSDK_InterForm : public CPDF_FormNotify { FX_BOOL m_bNeedHightlight[kNumFieldTypes]; }; -#define BAI_STRUCTURE 0 -#define BAI_ROW 1 -#define BAI_COLUMN 2 - -#define CPDFSDK_Annots CFX_ArrayTemplate -#define CPDFSDK_SortAnnots CGW_ArrayTemplate class CBA_AnnotIterator { public: + enum TabOrder { STRUCTURE = 0, ROW, COLUMN }; + CBA_AnnotIterator(CPDFSDK_PageView* pPageView, const CFX_ByteString& sType, const CFX_ByteString& sSubType); @@ -293,15 +290,19 @@ class CBA_AnnotIterator { 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 m_Annots; }; #endif // FPDFSDK_INCLUDE_FSDK_BASEFORM_H_ diff --git a/fpdfsdk/include/fsdk_mgr.h b/fpdfsdk/include/fsdk_mgr.h index 4b07cc3127..323b07a46d 100644 --- a/fpdfsdk/include/fsdk_mgr.h +++ b/fpdfsdk/include/fsdk_mgr.h @@ -292,6 +292,7 @@ class CPDFSDK_Document { FX_BOOL m_bChangeMask; FX_BOOL m_bBeingDestroyed; }; + class CPDFSDK_PageView final { public: CPDFSDK_PageView(CPDFSDK_Document* pSDKDoc, UnderlyingPageType* page); @@ -368,77 +369,4 @@ class CPDFSDK_PageView final { FX_BOOL m_bTakeOverPage; }; -template -class CGW_ArrayTemplate : public CFX_ArrayTemplate { - 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 218ee1d83a..46aa1f3d85 100644 --- a/fpdfsdk/src/fsdk_baseform.cpp +++ b/fpdfsdk/src/fsdk_baseform.cpp @@ -6,6 +6,7 @@ #include "fpdfsdk/include/fsdk_baseform.h" +#include #include #include "fpdfsdk/include/formfiller/FFL_FormFiller.h" @@ -2079,177 +2080,125 @@ FX_COLORREF CPDFSDK_InterForm::GetHighlightColor(int nFieldType) { 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 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 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 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 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; @@ -2260,41 +2209,31 @@ void CBA_AnnotIterator::GenerateResults() { } 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 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 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 d97001aae2..0b78ba24a6 100644 --- a/fpdfsdk/src/javascript/Field.cpp +++ b/fpdfsdk/src/javascript/Field.cpp @@ -6,6 +6,10 @@ #include "Field.h" +#include +#include +#include + #include "Document.h" #include "Icon.h" #include "JS_Context.h" @@ -3083,10 +3087,6 @@ FX_BOOL Field::deleteItemAt(IJS_Context* cc, 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& params, CJS_Value& vRet, @@ -3095,35 +3095,38 @@ FX_BOOL Field::getArray(IJS_Context* cc, if (FieldArray.empty()) return FALSE; - CGW_ArrayTemplate swSort; + std::vector> swSort; + for (CPDF_FormField* pFormField : FieldArray) { + swSort.push_back(std::unique_ptr( + 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& p1, + const std::unique_ptr& 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 pStr(swSort.GetAt(j)); + + int j = 0; + for (const auto& pStr : swSort) { v8::Local 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(FXJS_GetPrivate(pRuntime->GetIsolate(), pObj)); + Field* pField = static_cast(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; } -- cgit v1.2.3