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 <wtf/HashMap.h> 33 #include <wtf/PassRefPtr.h> 34 #include <wtf/RefCounted.h> 35 #include <wtf/unicode/Unicode.h> 36 37 namespace WebCore { 38 39 class FontData; 40 class GlyphPageTreeNode; 41 class SimpleFontData; 42 43 typedef unsigned short Glyph; 44 45 // Holds the glyph index and the corresponding SimpleFontData information for a given 46 // character. 47 struct GlyphData { 48 Glyph glyph; 49 const SimpleFontData* fontData; 50 }; 51 52 // A GlyphPage contains a fixed-size set of GlyphData mappings for a contiguous 53 // range of characters in the Unicode code space. GlyphPages are indexed 54 // starting from 0 and incrementing for each 256 glyphs. 55 // 56 // One page may actually include glyphs from other fonts if the characters are 57 // missing in the parimary font. It is owned by exactly one GlyphPageTreeNode, 58 // although multiple nodes may reference it as their "page" if they are supposed 59 // to be overriding the parent's node, but provide no additional information. 60 struct GlyphPage : public RefCounted<GlyphPage> { createGlyphPage61 static PassRefPtr<GlyphPage> create(GlyphPageTreeNode* owner) 62 { 63 return adoptRef(new GlyphPage(owner)); 64 } 65 66 static const size_t size = 256; // Covers Latin-1 in a single page. 67 GlyphData m_glyphs[size]; 68 GlyphPageTreeNode* m_owner; 69 glyphDataForCharacterGlyphPage70 const GlyphData& glyphDataForCharacter(UChar32 c) const { return m_glyphs[c % size]; } setGlyphDataForCharacterGlyphPage71 void setGlyphDataForCharacter(UChar32 c, Glyph g, const SimpleFontData* f) 72 { 73 setGlyphDataForIndex(c % size, g, f); 74 } setGlyphDataForIndexGlyphPage75 void setGlyphDataForIndex(unsigned index, Glyph g, const SimpleFontData* f) 76 { 77 ASSERT(index < size); 78 m_glyphs[index].glyph = g; 79 m_glyphs[index].fontData = f; 80 } ownerGlyphPage81 GlyphPageTreeNode* owner() const { return m_owner; } 82 83 // Implemented by the platform. 84 bool fill(unsigned offset, unsigned length, UChar* characterBuffer, unsigned bufferLength, const SimpleFontData*); 85 86 private: GlyphPageGlyphPage87 GlyphPage(GlyphPageTreeNode* owner) 88 : m_owner(owner) 89 { 90 } 91 }; 92 93 // The glyph page tree is a data structure that maps (FontData, glyph page number) 94 // to a GlyphPage. Level 0 (the "root") is special. There is one root 95 // GlyphPageTreeNode for each glyph page number. The roots do not have a 96 // GlyphPage associated with them, and their initializePage() function is never 97 // called to fill the glyphs. 98 // 99 // Each root node maps a FontData pointer to another GlyphPageTreeNode at 100 // level 1 (the "root child") that stores the actual glyphs for a specific font data. 101 // These nodes will only have a GlyphPage if they have glyphs for that range. 102 // 103 // Levels greater than one correspond to subsequent levels of the fallback list 104 // for that font. These levels override their parent's page of glyphs by 105 // filling in holes with the new font (thus making a more complete page). 106 // 107 // A NULL FontData pointer corresponds to the system fallback 108 // font. It is tracked separately from the regular pages and overrides so that 109 // the glyph pages do not get polluted with these last-resort glyphs. The 110 // system fallback page is not populated at construction like the other pages, 111 // but on demand for each glyph, because the system may need to use different 112 // fallback fonts for each. This lazy population is done by the Font. 113 class GlyphPageTreeNode { 114 public: GlyphPageTreeNode()115 GlyphPageTreeNode() 116 : m_parent(0) 117 , m_level(0) 118 , m_isSystemFallback(false) 119 , m_systemFallbackChild(0) 120 , m_customFontCount(0) 121 #ifndef NDEBUG 122 , m_pageNumber(0) 123 #endif 124 { 125 } 126 127 ~GlyphPageTreeNode(); 128 129 static HashMap<int, GlyphPageTreeNode*>* roots; 130 static GlyphPageTreeNode* pageZeroRoot; 131 getRootChild(const FontData * fontData,unsigned pageNumber)132 static GlyphPageTreeNode* getRootChild(const FontData* fontData, unsigned pageNumber) 133 { 134 return getRoot(pageNumber)->getChild(fontData, pageNumber); 135 } 136 137 static void pruneTreeCustomFontData(const FontData*); 138 static void pruneTreeFontData(const SimpleFontData*); 139 140 void pruneCustomFontData(const FontData*); 141 void pruneFontData(const SimpleFontData*, unsigned level = 0); 142 parent()143 GlyphPageTreeNode* parent() const { return m_parent; } 144 GlyphPageTreeNode* getChild(const FontData*, unsigned pageNumber); 145 146 // Returns a page of glyphs (or NULL if there are no glyphs in this page's character range). page()147 GlyphPage* page() const { return m_page.get(); } 148 149 // Returns the level of this node. See class-level comment. level()150 unsigned level() const { return m_level; } 151 152 // The system fallback font has special rules (see above). isSystemFallback()153 bool isSystemFallback() const { return m_isSystemFallback; } 154 155 static size_t treeGlyphPageCount(); 156 size_t pageCount() const; 157 158 private: 159 static GlyphPageTreeNode* getRoot(unsigned pageNumber); 160 void initializePage(const FontData*, unsigned pageNumber); 161 162 GlyphPageTreeNode* m_parent; 163 RefPtr<GlyphPage> m_page; 164 unsigned m_level; 165 bool m_isSystemFallback; 166 HashMap<const FontData*, GlyphPageTreeNode*> m_children; 167 GlyphPageTreeNode* m_systemFallbackChild; 168 unsigned m_customFontCount; 169 170 #ifndef NDEBUG 171 unsigned m_pageNumber; 172 #endif 173 }; 174 175 } // namespace WebCore 176 177 #endif // GlyphPageTreeNode_h 178