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 .
diff --git a/core/include/fxcrt/fx_basic.h b/core/include/fxcrt/fx_basic.h
index 230d3db..bc3d812 100644
--- a/core/include/fxcrt/fx_basic.h
+++ b/core/include/fxcrt/fx_basic.h
@@ -635,21 +635,6 @@
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 30223ad..59acfcb 100644
--- a/core/src/fpdfapi/fpdf_font/font_int.h
+++ b/core/src/fpdfapi/fpdf_font/font_int.h
@@ -172,7 +172,7 @@
FX_DWORD ReverseLookup(FX_WCHAR unicode);
protected:
- CFX_CMapDWordToDWord m_Map;
+ std::map<FX_DWORD, FX_DWORD> 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 8eae7cf..7f593c7 100644
--- a/core/src/fpdfapi/fpdf_font/fpdf_font.cpp
+++ b/core/src/fpdfapi/fpdf_font/fpdf_font.cpp
@@ -473,8 +473,9 @@
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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
} 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 a1717a9..81383fa 100644
--- a/core/src/fpdfapi/fpdf_font/ttgsubtable.cpp
+++ b/core/src/fpdfapi/fpdf_font/ttgsubtable.cpp
@@ -85,33 +85,26 @@
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 67cda37..5cf0e24 100644
--- a/core/src/fpdfapi/fpdf_font/ttgsubtable.h
+++ b/core/src/fpdfapi/fpdf_font/ttgsubtable.h
@@ -341,7 +341,7 @@
p += 4;
return ret;
}
- CFX_CMapDWordToDWord m_featureMap;
+ std::map<FX_DWORD, FX_DWORD> 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 a12a289..4f81be1 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 <set>
#include <utility>
#include <vector>
@@ -3003,9 +3004,8 @@
CPDF_PageNode m_pageNodes;
- CFX_CMapDWordToDWord* m_pageMapCheckState;
-
- CFX_CMapDWordToDWord* m_pagesLoadState;
+ std::set<FX_DWORD> m_pageMapCheckState;
+ std::set<FX_DWORD> m_pagesLoadState;
};
IPDF_DataAvail::IPDF_DataAvail(IFX_FileAvail* pFileAvail,
@@ -3063,13 +3063,11 @@
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 @@
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 @@
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 @@
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 @@
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 6bcb915..380beb6 100644
--- a/core/src/fxcrt/fx_basic_maps.cpp
+++ b/core/src/fxcrt/fx_basic_maps.cpp
@@ -348,71 +348,3 @@
}
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);
-}
