Use glyph-ids for lookups of SVG font kerning-pairs

Source/core/svg/SVGFontElement.cpp

 /*
  * Copyright (C) 2007 Eric Seidel <eric@webkit.org>
  * Copyright (C) 2007 Nikolas Zimmermann <zimmermann@kde.org>
  * Copyright (C) Research In Motion Limited 2010. All rights reserved.
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Library General Public
  * License as published by the Free Software Foundation; either
  * version 2 of the License, or (at your option) any later version.
  *
@@ skipping 41 matching lines @@
 
 PassRefPtr<SVGFontElement> SVGFontElement::create(Document& document)
 {
     return adoptRef(new SVGFontElement(document));
 }
 
 void SVGFontElement::invalidateGlyphCache()
 {
     if (m_isGlyphCacheValid) {
         m_glyphMap.clear();
-        m_horizontalKerningPairs.clear();
-        m_verticalKerningPairs.clear();
+        m_horizontalKerningTable.clear();
+        m_verticalKerningTable.clear();
     }
     m_isGlyphCacheValid = false;
 }
 
 SVGMissingGlyphElement* SVGFontElement::firstMissingGlyphElement() const
 {
     for (Node* child = firstChild(); child; child = child->nextSibling()) {
         if (child->hasTagName(SVGNames::missing_glyphTag))
             return toSVGMissingGlyphElement(child);
     }
@@ skipping 30 matching lines @@
             }
 
             // This glyph is never meant to be used for rendering, only as identifier as a part of a ligature.
             SVGGlyph newGlyphPart;
             newGlyphPart.isPartOfLigature = true;
             m_glyphMap.addGlyph(String(), lookupString, newGlyphPart);
         }
     }
 }
 
+static inline KerningPairKey makeKerningPairKey(Glyph glyphId1, Glyph glyphId2)
+{
+    return glyphId1 << 16 | glyphId2;
+}
+
+Vector<SVGGlyph> SVGFontElement::buildGlyphList(const UnicodeRanges& unicodeRanges, const HashSet<String>& unicodeNames, const HashSet<String>& glyphNames) const
+{
+    Vector<SVGGlyph> glyphs;
+    if (!unicodeRanges.isEmpty()) {
+        const UnicodeRanges::const_iterator end = unicodeRanges.end();
+        for (UnicodeRanges::const_iterator it = unicodeRanges.begin(); it != end; ++it)
+            m_glyphMap.collectGlyphsForUnicodeRange(*it, glyphs);
+    }
+    if (!unicodeNames.isEmpty()) {
+        const HashSet<String>::const_iterator end = unicodeNames.end();
+        for (HashSet<String>::const_iterator it = unicodeNames.begin(); it != end; ++it)
+            m_glyphMap.collectGlyphsForStringExact(*it, glyphs);
+    }
+    if (!glyphNames.isEmpty()) {
+        const HashSet<String>::const_iterator end = glyphNames.end();
+        for (HashSet<String>::const_iterator it = glyphNames.begin(); it != end; ++it) {
+            const SVGGlyph& glyph = m_glyphMap.glyphIdentifierForGlyphName(*it);
+            if (glyph.tableEntry)
+                glyphs.append(glyph);
+        }
+    }
+    return glyphs;
+}
+
+void SVGFontElement::addPairsToKerningTable(const SVGKerningPair& kerningPair, KerningTable& kerningTable)
+{
+    Vector<SVGGlyph> glyphsLhs = buildGlyphList(kerningPair.unicodeRange1, kerningPair.unicodeName1, kerningPair.glyphName1);
+    Vector<SVGGlyph> glyphsRhs = buildGlyphList(kerningPair.unicodeRange2, kerningPair.unicodeName2, kerningPair.glyphName2);
+    if (glyphsLhs.isEmpty() || glyphsRhs.isEmpty())
+        return;
+    size_t glyphsLhsSize = glyphsLhs.size();
+    size_t glyphsRhsSize = glyphsRhs.size();
+    // Enumerate all the valid kerning pairs, and add them to the table.
+    for (size_t lhsIndex = 0; lhsIndex < glyphsLhsSize; ++lhsIndex) {
+        for (size_t rhsIndex = 0; rhsIndex < glyphsRhsSize; ++rhsIndex) {
+            Glyph glyph1 = glyphsLhs[lhsIndex].tableEntry;
+            Glyph glyph2 = glyphsRhs[rhsIndex].tableEntry;
+            ASSERT(glyph1 && glyph2);
+            kerningTable.add(makeKerningPairKey(glyph1, glyph2), kerningPair.kerning);
+        }
+    }
+}
+
+void SVGFontElement::buildKerningTable(const KerningPairVector& kerningPairs, KerningTable& kerningTable)
+{
+    size_t kerningPairsSize = kerningPairs.size();
+    for (size_t i = 0; i < kerningPairsSize; ++i)
+        addPairsToKerningTable(kerningPairs[i], kerningTable);
+}
+
 void SVGFontElement::ensureGlyphCache()
 {
     if (m_isGlyphCacheValid)
         return;
 
+    KerningPairVector horizontalKerningPairs;
+    KerningPairVector verticalKerningPairs;
+
     SVGMissingGlyphElement* firstMissingGlyphElement = 0;
     Vector<String> ligatures;
     for (Node* child = firstChild(); child; child = child->nextSibling()) {
         if (child->hasTagName(SVGNames::glyphTag)) {
             SVGGlyphElement* glyph = toSVGGlyphElement(child);
             AtomicString unicode = glyph->fastGetAttribute(SVGNames::unicodeAttr);
             AtomicString glyphId = glyph->getIdAttribute();
             if (glyphId.isEmpty() && unicode.isEmpty())
                 continue;
 
             m_glyphMap.addGlyph(glyphId, unicode, glyph->buildGlyphIdentifier());
 
             // Register ligatures, if needed, don't mix up with surrogate pairs though!
             if (unicode.length() > 1 && !U16_IS_SURROGATE(unicode[0]))
                 ligatures.append(unicode.string());
         } else if (child->hasTagName(SVGNames::hkernTag)) {
-            toSVGHKernElement(child)->buildHorizontalKerningPair(m_horizontalKerningPairs);
+            toSVGHKernElement(child)->buildHorizontalKerningPair(horizontalKerningPairs);
         } else if (child->hasTagName(SVGNames::vkernTag)) {
-            toSVGVKernElement(child)->buildVerticalKerningPair(m_verticalKerningPairs);
+            toSVGVKernElement(child)->buildVerticalKerningPair(verticalKerningPairs);
         } else if (child->hasTagName(SVGNames::missing_glyphTag) && !firstMissingGlyphElement) {
             firstMissingGlyphElement = toSVGMissingGlyphElement(child);
         }
     }
 
+    // Build the kerning tables.
+    buildKerningTable(horizontalKerningPairs, m_horizontalKerningTable);
+    buildKerningTable(verticalKerningPairs, m_verticalKerningTable);
+
+    // The glyph-name->glyph-id map won't be needed/used after having built the kerning table(s).
+    m_glyphMap.dropNamedGlyphMap();
+
     // Register each character of each ligature, if needed.
     if (!ligatures.isEmpty())
         registerLigaturesInGlyphCache(ligatures);
 
     // Register missing-glyph element, if present.
     if (firstMissingGlyphElement) {
         SVGGlyph svgGlyph = SVGGlyphElement::buildGenericGlyphIdentifier(firstMissingGlyphElement);
         m_glyphMap.appendToGlyphTable(svgGlyph);
         m_missingGlyph = svgGlyph.tableEntry;
         ASSERT(m_missingGlyph > 0);
     }
 
     m_isGlyphCacheValid = true;
 }
 
-static bool stringMatchesUnicodeRange(const String& unicodeString, const UnicodeRanges& ranges, const HashSet<String>& unicodeValues)
+static float kerningForPairOfGlyphs(const KerningTable& kerningTable, Glyph glyphId1, Glyph glyphId2)
 {
-    if (unicodeString.isEmpty())
-        return false;
-
-    if (!ranges.isEmpty()) {
-        UChar firstChar = unicodeString[0];
-        const UnicodeRanges::const_iterator end = ranges.end();
-        for (UnicodeRanges::const_iterator it = ranges.begin(); it != end; ++it) {
-            if (firstChar >= it->first && firstChar <= it->second)
-                return true;
-        }
-    }
-
-    if (!unicodeValues.isEmpty())
-        return unicodeValues.contains(unicodeString);
-
-    return false;
-}
-
-static bool stringMatchesGlyphName(const String& glyphName, const HashSet<String>& glyphValues)
-{
-    if (glyphName.isEmpty())
-        return false;
-
-    if (!glyphValues.isEmpty())
-        return glyphValues.contains(glyphName);
-
-    return false;
-}
-
-static bool matches(const String& u1, const String& g1, const String& u2, const String& g2, const SVGKerningPair& kerningPair)
-{
-    if (!stringMatchesUnicodeRange(u1, kerningPair.unicodeRange1, kerningPair.unicodeName1)
-        && !stringMatchesGlyphName(g1, kerningPair.glyphName1))
-        return false;
-
-    if (!stringMatchesUnicodeRange(u2, kerningPair.unicodeRange2, kerningPair.unicodeName2)
-        && !stringMatchesGlyphName(g2, kerningPair.glyphName2))
-        return false;
-
-    return true;
-}
-
-static float kerningForPairOfStringsAndGlyphs(const KerningPairVector& kerningPairs, const String& u1, const String& g1, const String& u2, const String& g2)
-{
-    KerningPairVector::const_iterator it = kerningPairs.end() - 1;
-    const KerningPairVector::const_iterator begin = kerningPairs.begin() - 1;
-    for (; it != begin; --it) {
-        if (matches(u1, g1, u2, g2, *it))
-            return it->kerning;
-    }
+    KerningTable::const_iterator result = kerningTable.find(makeKerningPairKey(glyphId1, glyphId2));
+    if (result != kerningTable.end())
+        return result->value;
 
     return 0;
 }
 
-float SVGFontElement::horizontalKerningForPairOfStringsAndGlyphs(const String& u1, const String& g1, const String& u2, const String& g2) const
+float SVGFontElement::horizontalKerningForPairOfGlyphs(Glyph glyphId1, Glyph glyphId2) const
 {
-    if (m_horizontalKerningPairs.isEmpty())
+    if (m_horizontalKerningTable.isEmpty())
         return 0;
 
-    return kerningForPairOfStringsAndGlyphs(m_horizontalKerningPairs, u1, g1, u2, g2);
+    return kerningForPairOfGlyphs(m_horizontalKerningTable, glyphId1, glyphId2);
 }
 
-float SVGFontElement::verticalKerningForPairOfStringsAndGlyphs(const String& u1, const String& g1, const String& u2, const String& g2) const
+float SVGFontElement::verticalKerningForPairOfGlyphs(Glyph glyphId1, Glyph glyphId2) const
 {
-    if (m_verticalKerningPairs.isEmpty())
+    if (m_verticalKerningTable.isEmpty())
         return 0;
 
-    return kerningForPairOfStringsAndGlyphs(m_verticalKerningPairs, u1, g1, u2, g2);
+    return kerningForPairOfGlyphs(m_verticalKerningTable, glyphId1, glyphId2);
 }
 
 void SVGFontElement::collectGlyphsForString(const String& string, Vector<SVGGlyph>& glyphs)
 {
     ensureGlyphCache();
     m_glyphMap.collectGlyphsForString(string, glyphs);
 }
 
-void SVGFontElement::collectGlyphsForGlyphName(const String& glyphName, Vector<SVGGlyph>& glyphs)
+void SVGFontElement::collectGlyphsForAltGlyphReference(const String& glyphIdentifier, Vector<SVGGlyph>& glyphs)
 {
     ensureGlyphCache();
     // FIXME: We only support glyphName -> single glyph mapping so far.
-    glyphs.append(m_glyphMap.glyphIdentifierForGlyphName(glyphName));
+    glyphs.append(m_glyphMap.glyphIdentifierForAltGlyphReference(glyphIdentifier));
 }
 
 SVGGlyph SVGFontElement::svgGlyphForGlyph(Glyph glyph)
 {
     ensureGlyphCache();
     return m_glyphMap.svgGlyphForGlyph(glyph);
 }
 
 Glyph SVGFontElement::missingGlyph()
 {
     ensureGlyphCache();
     return m_missingGlyph;
 }
 
 }
 
 #endif // ENABLE(SVG_FONTS)