1/*
2 * Copyright (C) 2006, 2007, 2008 Apple Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 *
8 * 1.  Redistributions of source code must retain the above copyright
9 *     notice, this list of conditions and the following disclaimer.
10 * 2.  Redistributions in binary form must reproduce the above copyright
11 *     notice, this list of conditions and the following disclaimer in the
12 *     documentation and/or other materials provided with the distribution.
13 * 3.  Neither the name of Apple Computer, Inc. ("Apple") nor the names of
14 *     its contributors may be used to endorse or promote products derived
15 *     from this software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
18 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
19 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
20 * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
21 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
22 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
23 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
24 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28
29#ifndef GlyphPageTreeNode_h
30#define GlyphPageTreeNode_h
31
32#include <string.h>
33#include <wtf/HashMap.h>
34#include <wtf/PassRefPtr.h>
35#include <wtf/RefCounted.h>
36#include <wtf/unicode/Unicode.h>
37
38#ifndef NDEBUG
39void showGlyphPageTrees();
40void showGlyphPageTree(unsigned pageNumber);
41#endif
42
43namespace WebCore {
44
45class FontData;
46class GlyphPageTreeNode;
47class SimpleFontData;
48
49typedef unsigned short Glyph;
50
51// Holds the glyph index and the corresponding SimpleFontData information for a given
52// character.
53struct GlyphData {
54    GlyphData(Glyph g = 0, const SimpleFontData* f = 0)
55        : glyph(g)
56        , fontData(f)
57    {
58    }
59    Glyph glyph;
60    const SimpleFontData* fontData;
61};
62
63// A GlyphPage contains a fixed-size set of GlyphData mappings for a contiguous
64// range of characters in the Unicode code space. GlyphPages are indexed
65// starting from 0 and incrementing for each 256 glyphs.
66//
67// One page may actually include glyphs from other fonts if the characters are
68// missing in the primary font. It is owned by exactly one GlyphPageTreeNode,
69// although multiple nodes may reference it as their "page" if they are supposed
70// to be overriding the parent's node, but provide no additional information.
71class GlyphPage : public RefCounted<GlyphPage> {
72public:
73    static PassRefPtr<GlyphPage> create(GlyphPageTreeNode* owner)
74    {
75        return adoptRef(new GlyphPage(owner));
76    }
77
78    static const size_t size = 256; // Covers Latin-1 in a single page.
79
80    unsigned indexForCharacter(UChar32 c) const { return c % size; }
81    GlyphData glyphDataForCharacter(UChar32 c) const
82    {
83        unsigned index = indexForCharacter(c);
84        return GlyphData(m_glyphs[index], m_glyphFontData[index]);
85    }
86
87    GlyphData glyphDataForIndex(unsigned index) const
88    {
89        ASSERT(index < size);
90        return GlyphData(m_glyphs[index], m_glyphFontData[index]);
91    }
92
93    Glyph glyphAt(unsigned index) const
94    {
95        ASSERT(index < size);
96        return m_glyphs[index];
97    }
98
99    const SimpleFontData* fontDataForCharacter(UChar32 c) const
100    {
101        return m_glyphFontData[indexForCharacter(c)];
102    }
103
104    void setGlyphDataForCharacter(UChar32 c, Glyph g, const SimpleFontData* f)
105    {
106        setGlyphDataForIndex(indexForCharacter(c), g, f);
107    }
108    void setGlyphDataForIndex(unsigned index, Glyph g, const SimpleFontData* f)
109    {
110        ASSERT(index < size);
111        m_glyphs[index] = g;
112        m_glyphFontData[index] = f;
113    }
114    void setGlyphDataForIndex(unsigned index, const GlyphData& glyphData)
115    {
116        setGlyphDataForIndex(index, glyphData.glyph, glyphData.fontData);
117    }
118
119    void copyFrom(const GlyphPage& other)
120    {
121        memcpy(m_glyphs, other.m_glyphs, sizeof(m_glyphs));
122        memcpy(m_glyphFontData, other.m_glyphFontData, sizeof(m_glyphFontData));
123    }
124
125    void clear()
126    {
127        memset(m_glyphs, 0, sizeof(m_glyphs));
128        memset(m_glyphFontData, 0, sizeof(m_glyphFontData));
129    }
130
131    GlyphPageTreeNode* owner() const { return m_owner; }
132
133    // Implemented by the platform.
134    bool fill(unsigned offset, unsigned length, UChar* characterBuffer, unsigned bufferLength, const SimpleFontData*);
135
136private:
137    GlyphPage(GlyphPageTreeNode* owner)
138        : m_owner(owner)
139    {
140    }
141
142    // Separate arrays, rather than array of GlyphData, to save space.
143    Glyph m_glyphs[size];
144    const SimpleFontData* m_glyphFontData[size];
145
146    GlyphPageTreeNode* m_owner;
147};
148
149// The glyph page tree is a data structure that maps (FontData, glyph page number)
150// to a GlyphPage.  Level 0 (the "root") is special. There is one root
151// GlyphPageTreeNode for each glyph page number.  The roots do not have a
152// GlyphPage associated with them, and their initializePage() function is never
153// called to fill the glyphs.
154//
155// Each root node maps a FontData pointer to another GlyphPageTreeNode at
156// level 1 (the "root child") that stores the actual glyphs for a specific font data.
157// These nodes will only have a GlyphPage if they have glyphs for that range.
158//
159// Levels greater than one correspond to subsequent levels of the fallback list
160// for that font. These levels override their parent's page of glyphs by
161// filling in holes with the new font (thus making a more complete page).
162//
163// A NULL FontData pointer corresponds to the system fallback
164// font. It is tracked separately from the regular pages and overrides so that
165// the glyph pages do not get polluted with these last-resort glyphs. The
166// system fallback page is not populated at construction like the other pages,
167// but on demand for each glyph, because the system may need to use different
168// fallback fonts for each. This lazy population is done by the Font.
169class GlyphPageTreeNode {
170public:
171    GlyphPageTreeNode()
172        : m_parent(0)
173        , m_level(0)
174        , m_isSystemFallback(false)
175        , m_systemFallbackChild(0)
176        , m_customFontCount(0)
177#ifndef NDEBUG
178        , m_pageNumber(0)
179#endif
180    {
181    }
182
183    ~GlyphPageTreeNode();
184
185    static HashMap<int, GlyphPageTreeNode*>* roots;
186    static GlyphPageTreeNode* pageZeroRoot;
187
188    static GlyphPageTreeNode* getRootChild(const FontData* fontData, unsigned pageNumber)
189    {
190        return getRoot(pageNumber)->getChild(fontData, pageNumber);
191    }
192
193    static void pruneTreeCustomFontData(const FontData*);
194    static void pruneTreeFontData(const SimpleFontData*);
195
196    void pruneCustomFontData(const FontData*);
197    void pruneFontData(const SimpleFontData*, unsigned level = 0);
198
199    GlyphPageTreeNode* parent() const { return m_parent; }
200    GlyphPageTreeNode* getChild(const FontData*, unsigned pageNumber);
201
202    // Returns a page of glyphs (or NULL if there are no glyphs in this page's character range).
203    GlyphPage* page() const { return m_page.get(); }
204
205    // Returns the level of this node. See class-level comment.
206    unsigned level() const { return m_level; }
207
208    // The system fallback font has special rules (see above).
209    bool isSystemFallback() const { return m_isSystemFallback; }
210
211    static size_t treeGlyphPageCount();
212    size_t pageCount() const;
213
214private:
215    static GlyphPageTreeNode* getRoot(unsigned pageNumber);
216    void initializePage(const FontData*, unsigned pageNumber);
217
218#ifndef NDEBUG
219    void showSubtree();
220#endif
221
222    GlyphPageTreeNode* m_parent;
223    RefPtr<GlyphPage> m_page;
224    unsigned m_level;
225    bool m_isSystemFallback;
226    HashMap<const FontData*, GlyphPageTreeNode*> m_children;
227    GlyphPageTreeNode* m_systemFallbackChild;
228    unsigned m_customFontCount;
229
230#ifndef NDEBUG
231    unsigned m_pageNumber;
232
233    friend void ::showGlyphPageTree(unsigned pageNumber);
234#endif
235};
236
237} // namespace WebCore
238
239#endif // GlyphPageTreeNode_h
240