1/*
2 * Copyright (C) 2008 Apple Inc. All rights reserved.
3 *
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Library General Public
6 * License as published by the Free Software Foundation; either
7 * version 2 of the License, or (at your option) any later version.
8 *
9 * This library is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12 * Library General Public License for more details.
13 *
14 * You should have received a copy of the GNU Library General Public License
15 * along with this library; see the file COPYING.LIB.  If not, write to
16 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
17 * Boston, MA 02110-1301, USA.
18 */
19
20#ifndef SVGGlyphMap_h
21#define SVGGlyphMap_h
22
23#if ENABLE(SVG_FONTS)
24#include "core/svg/SVGParserUtilities.h"
25#include "platform/fonts/Latin1TextIterator.h"
26#include "platform/fonts/SVGGlyph.h"
27#include "platform/text/SurrogatePairAwareTextIterator.h"
28#include "wtf/HashMap.h"
29#include "wtf/Vector.h"
30
31namespace blink {
32
33struct GlyphMapNode;
34
35typedef HashMap<UChar32, RefPtr<GlyphMapNode> > GlyphMapLayer;
36
37struct GlyphMapNode : public RefCounted<GlyphMapNode> {
38private:
39    GlyphMapNode() { }
40public:
41    static PassRefPtr<GlyphMapNode> create() { return adoptRef(new GlyphMapNode); }
42
43    Vector<SVGGlyph> glyphs;
44
45    GlyphMapLayer children;
46};
47
48class SVGGlyphMap {
49public:
50    SVGGlyphMap() : m_currentPriority(0) { }
51
52    void addGlyph(const String& glyphIdentifier, const String& unicodeString, SVGGlyph glyph)
53    {
54        ASSERT(!glyphIdentifier.isEmpty() || !unicodeString.isEmpty());
55
56        bool hasGlyphIdentifier = !glyphIdentifier.isEmpty();
57        if (unicodeString.isEmpty()) {
58            // Register glyphs with 'id's in the id glyph map and in the glyph table.
59            ASSERT(hasGlyphIdentifier);
60            appendToGlyphTable(glyph);
61            m_idGlyphs.add(glyphIdentifier, glyph.tableEntry);
62            return;
63        }
64
65        unsigned length = unicodeString.length();
66
67        RefPtr<GlyphMapNode> node;
68        if (unicodeString.is8Bit()) {
69            Latin1TextIterator textIterator(unicodeString.characters8(), 0, length, length);
70            node = findOrCreateNode(textIterator);
71        } else {
72            SurrogatePairAwareTextIterator textIterator(unicodeString.characters16(), 0, length, length);
73            node = findOrCreateNode(textIterator);
74        }
75        if (!node)
76            return;
77
78        // Register glyph associated with an unicode string into the glyph map.
79        node->glyphs.append(glyph);
80        SVGGlyph& lastGlyph = node->glyphs.last();
81        lastGlyph.priority = m_currentPriority++;
82        lastGlyph.unicodeStringLength = length;
83
84        // If the glyph is named, also add it to the named glyph name, and to the glyph table in both cases.
85        appendToGlyphTable(lastGlyph);
86        if (!lastGlyph.glyphName.isEmpty())
87            m_namedGlyphs.add(lastGlyph.glyphName, lastGlyph.tableEntry);
88        if (hasGlyphIdentifier)
89            m_idGlyphs.add(glyphIdentifier, lastGlyph.tableEntry);
90    }
91
92    void appendToGlyphTable(SVGGlyph& glyph)
93    {
94        size_t tableEntry = m_glyphTable.size();
95        ASSERT(tableEntry < std::numeric_limits<unsigned short>::max());
96
97        // The first table entry starts with 1. 0 denotes an unknown glyph.
98        glyph.tableEntry = tableEntry + 1;
99        m_glyphTable.append(glyph);
100    }
101
102    static inline bool compareGlyphPriority(const SVGGlyph& first, const SVGGlyph& second)
103    {
104        return first.priority < second.priority;
105    }
106
107    void collectGlyphsForString(const String& string, Vector<SVGGlyph>& glyphs)
108    {
109        unsigned length = string.length();
110
111        if (!length)
112            return;
113
114        if (string.is8Bit()) {
115            Latin1TextIterator textIterator(string.characters8(), 0, length, length);
116            collectGlyphsForIterator(textIterator, glyphs);
117        } else {
118            SurrogatePairAwareTextIterator textIterator(string.characters16(), 0, length, length);
119            collectGlyphsForIterator(textIterator, glyphs);
120        }
121
122        std::sort(glyphs.begin(), glyphs.end(), compareGlyphPriority);
123    }
124
125    void collectGlyphsForStringExact(const String& string, Vector<SVGGlyph>& glyphs) const
126    {
127        unsigned length = string.length();
128
129        if (!length)
130            return;
131
132        RefPtr<GlyphMapNode> node;
133        if (string.is8Bit()) {
134            Latin1TextIterator textIterator(string.characters8(), 0, length, length);
135            node = findNode(textIterator);
136        } else {
137            SurrogatePairAwareTextIterator textIterator(string.characters16(), 0, length, length);
138            node = findNode(textIterator);
139        }
140
141        if (node)
142            glyphs.appendVector(node->glyphs);
143    }
144
145    void collectGlyphsForUnicodeRange(const UnicodeRange& unicodeRange, Vector<SVGGlyph>& glyphs) const
146    {
147        for (unsigned character = unicodeRange.first; character <= unicodeRange.second; ++character) {
148            if (RefPtr<GlyphMapNode> node = m_rootLayer.get(character))
149                glyphs.appendVector(node->glyphs);
150        }
151    }
152
153    void clear()
154    {
155        m_rootLayer.clear();
156        m_glyphTable.clear();
157        m_idGlyphs.clear();
158        m_namedGlyphs.clear();
159        m_currentPriority = 0;
160    }
161
162    void dropNamedGlyphMap()
163    {
164        m_namedGlyphs.clear();
165    }
166
167    const SVGGlyph& svgGlyphForGlyph(Glyph glyph) const
168    {
169        if (!glyph || glyph > m_glyphTable.size()) {
170            DEFINE_STATIC_LOCAL(SVGGlyph, defaultGlyph, ());
171            return defaultGlyph;
172        }
173        return m_glyphTable[glyph - 1];
174    }
175
176    const SVGGlyph& glyphIdentifierForAltGlyphReference(const String& glyphIdentifier) const
177    {
178        return svgGlyphForGlyph(m_idGlyphs.get(glyphIdentifier));
179    }
180
181    const SVGGlyph& glyphIdentifierForGlyphName(const String& glyphName) const
182    {
183        return svgGlyphForGlyph(m_namedGlyphs.get(glyphName));
184    }
185
186private:
187    template<typename Iterator>
188    PassRefPtr<GlyphMapNode> findOrCreateNode(Iterator& textIterator)
189    {
190        GlyphMapLayer* currentLayer = &m_rootLayer;
191
192        RefPtr<GlyphMapNode> node;
193        UChar32 character = 0;
194        unsigned clusterLength = 0;
195        while (textIterator.consume(character, clusterLength)) {
196            node = currentLayer->get(character);
197            if (!node) {
198                node = GlyphMapNode::create();
199                currentLayer->set(character, node);
200            }
201            currentLayer = &node->children;
202            textIterator.advance(clusterLength);
203        }
204
205        return node.release();
206    }
207
208    template<typename Iterator>
209    PassRefPtr<GlyphMapNode> findNode(Iterator& textIterator) const
210    {
211        const GlyphMapLayer* currentLayer = &m_rootLayer;
212
213        RefPtr<GlyphMapNode> node;
214        UChar32 character = 0;
215        unsigned clusterLength = 0;
216        while (textIterator.consume(character, clusterLength)) {
217            node = currentLayer->get(character);
218            if (!node)
219                break;
220            currentLayer = &node->children;
221            textIterator.advance(clusterLength);
222        }
223
224        return node.release();
225    }
226
227    template<typename Iterator>
228    void collectGlyphsForIterator(Iterator& textIterator, Vector<SVGGlyph>& glyphs)
229    {
230        GlyphMapLayer* currentLayer = &m_rootLayer;
231
232        UChar32 character = 0;
233        unsigned clusterLength = 0;
234        while (textIterator.consume(character, clusterLength)) {
235            RefPtr<GlyphMapNode> node = currentLayer->get(character);
236            if (!node)
237                break;
238            glyphs.appendVector(node->glyphs);
239            currentLayer = &node->children;
240            textIterator.advance(clusterLength);
241        }
242    }
243
244    GlyphMapLayer m_rootLayer;
245    Vector<SVGGlyph> m_glyphTable;
246    HashMap<String, Glyph> m_namedGlyphs;
247    HashMap<String, Glyph> m_idGlyphs;
248    int m_currentPriority;
249};
250
251}
252
253#endif // ENABLE(SVG_FONTS)
254#endif // SVGGlyphMap_h
255