WebCore/GlyphPageTreeNode.h

   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> {
  61     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
  70     const GlyphData& glyphDataForCharacter(UChar32 c) const { return m_glyphs[c % size]; }
  71     void setGlyphDataForCharacter(UChar32 c, Glyph g, const SimpleFontData* f)
  72     {
  73         setGlyphDataForIndex(c % size, g, f);
  74     }
  75     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     }
  81     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:
  87     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:
 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
 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
 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).
 147     GlyphPage* page() const { return m_page.get(); }
 148
 149     // Returns the level of this node. See class-level comment.
 150     unsigned level() const { return m_level; }
 151
 152     // The system fallback font has special rules (see above).
 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