From 85d5c4af4a9546970b34dd413c473d10fef8534b Mon Sep 17 00:00:00 2001 From: Tom Sepez Date: Tue, 18 Aug 2015 09:20:29 -0700 Subject: FX_CMapDwordToDword considered harmful. Lookups are log(n), but random insertions could result in n^2 behaviour. Replace with maps and sets. R=thestig@chromium.org Review URL: https://codereview.chromium.org/1289703003 . --- core/include/fxcrt/fx_basic.h | 15 ----- core/src/fpdfapi/fpdf_font/font_int.h | 2 +- core/src/fpdfapi/fpdf_font/fpdf_font.cpp | 28 ++++----- core/src/fpdfapi/fpdf_font/ttgsubtable.cpp | 19 ++---- core/src/fpdfapi/fpdf_font/ttgsubtable.h | 2 +- .../src/fpdfapi/fpdf_parser/fpdf_parser_parser.cpp | 43 ++++---------- core/src/fxcrt/fx_basic_maps.cpp | 68 ---------------------- 7 files changed, 30 insertions(+), 147 deletions(-) diff --git a/core/include/fxcrt/fx_basic.h b/core/include/fxcrt/fx_basic.h index 230d3db0f0..bc3d81200f 100644 --- a/core/include/fxcrt/fx_basic.h +++ b/core/include/fxcrt/fx_basic.h @@ -635,21 +635,6 @@ class CFX_MapPtrToPtr { CAssoc* GetAssocAt(void* key, FX_DWORD& hash) const; }; -class CFX_CMapDWordToDWord { - public: - FX_BOOL Lookup(FX_DWORD key, FX_DWORD& value) const; - - void SetAt(FX_DWORD key, FX_DWORD value); - - void EstimateSize(FX_DWORD size, FX_DWORD grow_by); - - FX_POSITION GetStartPosition() const; - - void GetNextAssoc(FX_POSITION& pos, FX_DWORD& key, FX_DWORD& value) const; - - protected: - CFX_BinaryBuf m_Buffer; -}; class CFX_CMapByteStringToPtr { public: CFX_CMapByteStringToPtr(); diff --git a/core/src/fpdfapi/fpdf_font/font_int.h b/core/src/fpdfapi/fpdf_font/font_int.h index 30223ad63a..59acfcbd35 100644 --- a/core/src/fpdfapi/fpdf_font/font_int.h +++ b/core/src/fpdfapi/fpdf_font/font_int.h @@ -172,7 +172,7 @@ class CPDF_ToUnicodeMap { FX_DWORD ReverseLookup(FX_WCHAR unicode); protected: - CFX_CMapDWordToDWord m_Map; + std::map m_Map; CPDF_CID2UnicodeMap* m_pBaseMap; CFX_WideTextBuf m_MultiCharBuf; }; diff --git a/core/src/fpdfapi/fpdf_font/fpdf_font.cpp b/core/src/fpdfapi/fpdf_font/fpdf_font.cpp index 8eae7cf3f8..7f593c7be3 100644 --- a/core/src/fpdfapi/fpdf_font/fpdf_font.cpp +++ b/core/src/fpdfapi/fpdf_font/fpdf_font.cpp @@ -473,8 +473,9 @@ CPDF_FontCharMap::CPDF_FontCharMap(CPDF_Font* pFont) { m_pFont = pFont; } CFX_WideString CPDF_ToUnicodeMap::Lookup(FX_DWORD charcode) { - FX_DWORD value; - if (m_Map.Lookup(charcode, value)) { + auto it = m_Map.find(charcode); + if (it != m_Map.end()) { + FX_DWORD value = it->second; FX_WCHAR unicode = (FX_WCHAR)(value & 0xffff); if (unicode != 0xffff) { return unicode; @@ -500,13 +501,9 @@ CFX_WideString CPDF_ToUnicodeMap::Lookup(FX_DWORD charcode) { return CFX_WideString(); } FX_DWORD CPDF_ToUnicodeMap::ReverseLookup(FX_WCHAR unicode) { - FX_POSITION pos = m_Map.GetStartPosition(); - while (pos) { - FX_DWORD key, value; - m_Map.GetNextAssoc(pos, key, value); - if ((FX_WCHAR)value == unicode) { - return key; - } + for (const auto& pair : m_Map) { + if (pair.second == unicode) + return pair.first; } return 0; } @@ -599,7 +596,6 @@ void CPDF_ToUnicodeMap::Load(CPDF_Stream* pStream) { CPDF_StreamAcc stream; stream.LoadAllData(pStream, FALSE); CPDF_SimpleParser parser(stream.GetData(), stream.GetSize()); - m_Map.EstimateSize(stream.GetSize() / 8, 1024); while (1) { CFX_ByteStringC word = parser.GetWord(); if (word.IsEmpty()) { @@ -619,9 +615,9 @@ void CPDF_ToUnicodeMap::Load(CPDF_Stream* pStream) { continue; } if (len == 1) { - m_Map.SetAt(srccode, destcode.GetAt(0)); + m_Map[srccode] = destcode.GetAt(0); } else { - m_Map.SetAt(srccode, m_MultiCharBuf.GetLength() * 0x10000 + 0xffff); + m_Map[srccode] = m_MultiCharBuf.GetLength() * 0x10000 + 0xffff; m_MultiCharBuf.AppendChar(destcode.GetLength()); m_MultiCharBuf << destcode; } @@ -650,9 +646,9 @@ void CPDF_ToUnicodeMap::Load(CPDF_Stream* pStream) { continue; } if (len == 1) { - m_Map.SetAt(code, destcode.GetAt(0)); + m_Map[code] = destcode.GetAt(0); } else { - m_Map.SetAt(code, m_MultiCharBuf.GetLength() * 0x10000 + 0xffff); + m_Map[code] = m_MultiCharBuf.GetLength() * 0x10000 + 0xffff; m_MultiCharBuf.AppendChar(destcode.GetLength()); m_MultiCharBuf << destcode; } @@ -665,7 +661,7 @@ void CPDF_ToUnicodeMap::Load(CPDF_Stream* pStream) { if (len == 1) { value = _StringToCode(start); for (FX_DWORD code = lowcode; code <= highcode; code++) { - m_Map.SetAt(code, value++); + m_Map[code] = value++; } } else { for (FX_DWORD code = lowcode; code <= highcode; code++) { @@ -675,7 +671,7 @@ void CPDF_ToUnicodeMap::Load(CPDF_Stream* pStream) { } else { retcode = _StringDataAdd(destcode); } - m_Map.SetAt(code, m_MultiCharBuf.GetLength() * 0x10000 + 0xffff); + m_Map[code] = m_MultiCharBuf.GetLength() * 0x10000 + 0xffff; m_MultiCharBuf.AppendChar(retcode.GetLength()); m_MultiCharBuf << retcode; destcode = retcode; diff --git a/core/src/fpdfapi/fpdf_font/ttgsubtable.cpp b/core/src/fpdfapi/fpdf_font/ttgsubtable.cpp index a1717a9fd4..81383fa869 100644 --- a/core/src/fpdfapi/fpdf_font/ttgsubtable.cpp +++ b/core/src/fpdfapi/fpdf_font/ttgsubtable.cpp @@ -85,33 +85,26 @@ bool CFX_CTTGSUBTable::GetVerticalGlyph(TT_uint32_t glyphnum, k); if (FeatureList.FeatureRecord[index].FeatureTag == tag[0] || FeatureList.FeatureRecord[index].FeatureTag == tag[1]) { - FX_DWORD value; - if (!m_featureMap.Lookup(index, value)) { - m_featureMap.SetAt(index, index); + if (m_featureMap.find(index) == m_featureMap.end()) { + m_featureMap[index] = index; } } } } } - if (!m_featureMap.GetStartPosition()) { + if (m_featureMap.empty()) { for (int i = 0; i < FeatureList.FeatureCount; i++) { if (FeatureList.FeatureRecord[i].FeatureTag == tag[0] || FeatureList.FeatureRecord[i].FeatureTag == tag[1]) { - FX_DWORD value; - if (!m_featureMap.Lookup(i, value)) { - m_featureMap.SetAt(i, i); - } + m_featureMap[i] = i; } } } m_bFeautureMapLoad = TRUE; } - FX_POSITION pos = m_featureMap.GetStartPosition(); - while (pos) { - FX_DWORD index, value; - m_featureMap.GetNextAssoc(pos, index, value); + for (const auto& pair : m_featureMap) { if (GetVerticalGlyphSub(glyphnum, vglyphnum, - &FeatureList.FeatureRecord[value].Feature)) { + &FeatureList.FeatureRecord[pair.second].Feature)) { return true; } } diff --git a/core/src/fpdfapi/fpdf_font/ttgsubtable.h b/core/src/fpdfapi/fpdf_font/ttgsubtable.h index 67cda371c1..5cf0e2413f 100644 --- a/core/src/fpdfapi/fpdf_font/ttgsubtable.h +++ b/core/src/fpdfapi/fpdf_font/ttgsubtable.h @@ -341,7 +341,7 @@ class CFX_CTTGSUBTable { p += 4; return ret; } - CFX_CMapDWordToDWord m_featureMap; + std::map m_featureMap; FX_BOOL m_bFeautureMapLoad; bool loaded; struct tt_gsub_header header; diff --git a/core/src/fpdfapi/fpdf_parser/fpdf_parser_parser.cpp b/core/src/fpdfapi/fpdf_parser/fpdf_parser_parser.cpp index a12a2894a5..4f81be1d3f 100644 --- a/core/src/fpdfapi/fpdf_parser/fpdf_parser_parser.cpp +++ b/core/src/fpdfapi/fpdf_parser/fpdf_parser_parser.cpp @@ -4,6 +4,7 @@ // Original code copyright 2014 Foxit Software Inc. http://www.foxitsoftware.com +#include #include #include @@ -3003,9 +3004,8 @@ class CPDF_DataAvail final : public IPDF_DataAvail { CPDF_PageNode m_pageNodes; - CFX_CMapDWordToDWord* m_pageMapCheckState; - - CFX_CMapDWordToDWord* m_pagesLoadState; + std::set m_pageMapCheckState; + std::set m_pagesLoadState; }; IPDF_DataAvail::IPDF_DataAvail(IFX_FileAvail* pFileAvail, @@ -3063,13 +3063,11 @@ CPDF_DataAvail::CPDF_DataAvail(IFX_FileAvail* pFileAvail, m_pAcroForm = NULL; m_pPageDict = NULL; m_pPageResource = NULL; - m_pageMapCheckState = NULL; m_docStatus = PDF_DATAAVAIL_HEADER; m_parser.m_bOwnFileRead = FALSE; m_bTotalLoadPageTree = FALSE; m_bCurPageDictLoadOK = FALSE; m_bLinearedDataOK = FALSE; - m_pagesLoadState = NULL; } CPDF_DataAvail::~CPDF_DataAvail() { if (m_pLinearized) { @@ -3081,8 +3079,6 @@ CPDF_DataAvail::~CPDF_DataAvail() { if (m_pTrailer) { m_pTrailer->Release(); } - delete m_pageMapCheckState; - delete m_pagesLoadState; int32_t i = 0; int32_t iSize = m_arrayAcroforms.GetSize(); for (i = 0; i < iSize; ++i) { @@ -3517,29 +3513,14 @@ FX_BOOL CPDF_DataAvail::PreparePageItem() { return TRUE; } FX_BOOL CPDF_DataAvail::IsFirstCheck(int iPage) { - if (NULL == m_pageMapCheckState) { - m_pageMapCheckState = new CFX_CMapDWordToDWord(); - } - FX_DWORD dwValue = 0; - if (!m_pageMapCheckState->Lookup(iPage, dwValue)) { - m_pageMapCheckState->SetAt(iPage, 1); - return TRUE; - } - if (dwValue != 0) { + if (m_pageMapCheckState.find(iPage) != m_pageMapCheckState.end()) return FALSE; - } - m_pageMapCheckState->SetAt(iPage, 1); + + m_pageMapCheckState.insert(iPage); return TRUE; } void CPDF_DataAvail::ResetFirstCheck(int iPage) { - if (NULL == m_pageMapCheckState) { - m_pageMapCheckState = new CFX_CMapDWordToDWord(); - } - FX_DWORD dwValue = 1; - if (!m_pageMapCheckState->Lookup(iPage, dwValue)) { - return; - } - m_pageMapCheckState->SetAt(iPage, 0); + m_pageMapCheckState.erase(iPage); } FX_BOOL CPDF_DataAvail::CheckPage(IFX_DownloadHints* pHints) { FX_DWORD iPageObjs = m_PageObjList.GetSize(); @@ -4513,16 +4494,12 @@ FX_BOOL CPDF_DataAvail::IsPageAvail(int32_t iPage, IFX_DownloadHints* pHints) { m_objs_array.RemoveAll(); m_objnum_array.RemoveAll(); } - if (m_pagesLoadState == NULL) { - m_pagesLoadState = new CFX_CMapDWordToDWord(); - } - FX_DWORD dwPageLoad = 0; - if (m_pagesLoadState->Lookup(iPage, dwPageLoad) && dwPageLoad != 0) { + if (m_pagesLoadState.find(iPage) != m_pagesLoadState.end()) { return TRUE; } if (m_bLinearized) { if ((FX_DWORD)iPage == m_dwFirstPageNo) { - m_pagesLoadState->SetAt(iPage, TRUE); + m_pagesLoadState.insert(iPage); return TRUE; } if (!CheckLinearizedData(pHints)) { @@ -4617,7 +4594,7 @@ FX_BOOL CPDF_DataAvail::IsPageAvail(int32_t iPage, IFX_DownloadHints* pHints) { m_bAnnotsLoad = FALSE; m_bCurPageDictLoadOK = FALSE; ResetFirstCheck(iPage); - m_pagesLoadState->SetAt(iPage, TRUE); + m_pagesLoadState.insert(iPage); return TRUE; } FX_BOOL CPDF_DataAvail::CheckResources(IFX_DownloadHints* pHints) { diff --git a/core/src/fxcrt/fx_basic_maps.cpp b/core/src/fxcrt/fx_basic_maps.cpp index 6bcb91546a..380beb6f89 100644 --- a/core/src/fxcrt/fx_basic_maps.cpp +++ b/core/src/fxcrt/fx_basic_maps.cpp @@ -348,71 +348,3 @@ int CFX_CMapByteStringToPtr::GetCount() const { } return count; } -extern "C" { -static int _CompareDWord(const void* p1, const void* p2) { - return (*(FX_DWORD*)p1) - (*(FX_DWORD*)p2); -} -}; -struct _DWordPair { - FX_DWORD key; - FX_DWORD value; -}; -FX_BOOL CFX_CMapDWordToDWord::Lookup(FX_DWORD key, FX_DWORD& value) const { - void* pResult = FXSYS_bsearch(&key, m_Buffer.GetBuffer(), - m_Buffer.GetSize() / sizeof(_DWordPair), - sizeof(_DWordPair), _CompareDWord); - if (pResult == NULL) { - return FALSE; - } - value = ((FX_DWORD*)pResult)[1]; - return TRUE; -} -FX_POSITION CFX_CMapDWordToDWord::GetStartPosition() const { - FX_DWORD count = m_Buffer.GetSize() / sizeof(_DWordPair); - if (count == 0) { - return NULL; - } - return (FX_POSITION)1; -} -void CFX_CMapDWordToDWord::GetNextAssoc(FX_POSITION& pos, - FX_DWORD& key, - FX_DWORD& value) const { - if (pos == 0) { - return; - } - FX_DWORD index = ((FX_DWORD)(uintptr_t)pos) - 1; - FX_DWORD count = m_Buffer.GetSize() / sizeof(_DWordPair); - _DWordPair* buf = (_DWordPair*)m_Buffer.GetBuffer(); - key = buf[index].key; - value = buf[index].value; - if (index == count - 1) { - pos = 0; - } else { - pos = (FX_POSITION)((uintptr_t)pos + 1); - } -} -void CFX_CMapDWordToDWord::SetAt(FX_DWORD key, FX_DWORD value) { - FX_DWORD count = m_Buffer.GetSize() / sizeof(_DWordPair); - _DWordPair* buf = (_DWordPair*)m_Buffer.GetBuffer(); - _DWordPair pair = {key, value}; - if (count == 0 || key > buf[count - 1].key) { - m_Buffer.AppendBlock(&pair, sizeof(_DWordPair)); - return; - } - int low = 0, high = count - 1; - while (low <= high) { - int mid = (low + high) / 2; - if (buf[mid].key < key) { - low = mid + 1; - } else if (buf[mid].key > key) { - high = mid - 1; - } else { - buf[mid].value = value; - return; - } - } - m_Buffer.InsertBlock(low * sizeof(_DWordPair), &pair, sizeof(_DWordPair)); -} -void CFX_CMapDWordToDWord::EstimateSize(FX_DWORD size, FX_DWORD grow_by) { - m_Buffer.EstimateSize(size, grow_by); -} -- cgit v1.2.3