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 .

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<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 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<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 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 <set>
 #include <utility>
 #include <vector>
 
@@ -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<FX_DWORD> m_pageMapCheckState;
+  std::set<FX_DWORD> 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);
-}