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 .

4 files changed, 20 insertions, 31 deletions

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;