Home | History | Annotate | Download | only in fonts 
      1 /*
      2  * Copyright (C) 2012 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  * 1. Redistributions of source code must retain the above copyright
      8  *    notice, this list of conditions and the following disclaimer.
      9  * 2. Redistributions in binary form must reproduce the above copyright
     10  *    notice, this list of conditions and the following disclaimer in the
     11  *    documentation and/or other materials provided with the distribution.
     12  *
     13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
     14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
     15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
     16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
     17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
     18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
     19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
     20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
     21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
     22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
     23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     24  */
     25 
     26 #ifndef WidthCache_h
     27 #define WidthCache_h
     28 
     29 #include "platform/geometry/IntRectExtent.h"
     30 #include "platform/text/TextRun.h"
     31 #include "wtf/Forward.h"
     32 #include "wtf/HashFunctions.h"
     33 #include "wtf/HashSet.h"
     34 #include "wtf/HashTableDeletedValueType.h"
     35 #include "wtf/StringHasher.h"
     36 
     37 namespace blink {
     38 
     39 struct WidthCacheEntry {
     40     WidthCacheEntry()
     41     {
     42         width = std::numeric_limits<float>::quiet_NaN();
     43     }
     44     bool isValid() const { return !std::isnan(width); }
     45     float width;
     46     IntRectExtent glyphBounds;
     47 };
     48 
     49 class WidthCache {
     50 private:
     51     // Used to optimize small strings as hash table keys. Avoids malloc'ing an out-of-line StringImpl.
     52     class SmallStringKey {
     53     public:
     54         static unsigned capacity() { return s_capacity; }
     55 
     56         SmallStringKey()
     57             : m_length(s_emptyValueLength)
     58         {
     59         }
     60 
     61         SmallStringKey(WTF::HashTableDeletedValueType)
     62             : m_length(s_deletedValueLength)
     63         {
     64         }
     65 
     66         template<typename CharacterType> SmallStringKey(CharacterType* characters, unsigned short length)
     67             : m_length(length)
     68         {
     69             ASSERT(length <= s_capacity);
     70 
     71             StringHasher hasher;
     72 
     73             bool remainder = length & 1;
     74             length >>= 1;
     75 
     76             unsigned i = 0;
     77             while (length--) {
     78                 m_characters[i] = characters[i];
     79                 m_characters[i + 1] = characters[i + 1];
     80                 hasher.addCharactersAssumingAligned(characters[i], characters[i + 1]);
     81                 i += 2;
     82             }
     83 
     84             if (remainder) {
     85                 m_characters[i] = characters[i];
     86                 hasher.addCharacter(characters[i]);
     87             }
     88 
     89             m_hash = hasher.hash();
     90         }
     91 
     92         const UChar* characters() const { return m_characters; }
     93         unsigned short length() const { return m_length; }
     94         unsigned hash() const { return m_hash; }
     95 
     96         bool isHashTableDeletedValue() const { return m_length == s_deletedValueLength; }
     97         bool isHashTableEmptyValue() const { return m_length == s_emptyValueLength; }
     98 
     99     private:
    100         static const unsigned s_capacity = 15;
    101         static const unsigned s_emptyValueLength = s_capacity + 1;
    102         static const unsigned s_deletedValueLength = s_capacity + 2;
    103 
    104         unsigned m_hash;
    105         unsigned short m_length;
    106         UChar m_characters[s_capacity];
    107     };
    108 
    109     struct SmallStringKeyHash {
    110         static unsigned hash(const SmallStringKey& key) { return key.hash(); }
    111         static bool equal(const SmallStringKey& a, const SmallStringKey& b) { return a == b; }
    112         static const bool safeToCompareToEmptyOrDeleted = true; // Empty and deleted values have lengths that are not equal to any valid length.
    113     };
    114 
    115     struct SmallStringKeyHashTraits : WTF::SimpleClassHashTraits<SmallStringKey> {
    116         static const bool hasIsEmptyValueFunction = true;
    117         static bool isEmptyValue(const SmallStringKey& key) { return key.isHashTableEmptyValue(); }
    118         static const bool needsDestruction = false;
    119         static const unsigned minimumTableSize = 16;
    120     };
    121 
    122     friend bool operator==(const SmallStringKey&, const SmallStringKey&);
    123 
    124 public:
    125     WidthCache()
    126         : m_interval(s_maxInterval)
    127         , m_countdown(m_interval)
    128     {
    129     }
    130 
    131     WidthCacheEntry* add(const TextRun& run, WidthCacheEntry entry)
    132     {
    133         if (static_cast<unsigned>(run.length()) > SmallStringKey::capacity())
    134             return 0;
    135 
    136         if (m_countdown > 0) {
    137             --m_countdown;
    138             return 0;
    139         }
    140 
    141         return addSlowCase(run, entry);
    142     }
    143 
    144     void clear()
    145     {
    146         m_singleCharMap.clear();
    147         m_map.clear();
    148     }
    149 
    150 private:
    151     WidthCacheEntry* addSlowCase(const TextRun& run, WidthCacheEntry entry)
    152     {
    153         int length = run.length();
    154         bool isNewEntry;
    155         WidthCacheEntry *value;
    156         if (length == 1) {
    157             SingleCharMap::AddResult addResult = m_singleCharMap.add(run[0], entry);
    158             isNewEntry = addResult.isNewEntry;
    159             value = &addResult.storedValue->value;
    160         } else {
    161             SmallStringKey smallStringKey;
    162             if (run.is8Bit())
    163                 smallStringKey = SmallStringKey(run.characters8(), length);
    164             else
    165                 smallStringKey = SmallStringKey(run.characters16(), length);
    166 
    167             Map::AddResult addResult = m_map.add(smallStringKey, entry);
    168             isNewEntry = addResult.isNewEntry;
    169             value = &addResult.storedValue->value;
    170         }
    171 
    172         // Cache hit: ramp up by sampling the next few words.
    173         if (!isNewEntry) {
    174             m_interval = s_minInterval;
    175             return value;
    176         }
    177 
    178         // Cache miss: ramp down by increasing our sampling interval.
    179         if (m_interval < s_maxInterval)
    180             ++m_interval;
    181         m_countdown = m_interval;
    182 
    183         if ((m_singleCharMap.size() + m_map.size()) < s_maxSize)
    184             return value;
    185 
    186         // No need to be fancy: we're just trying to avoid pathological growth.
    187         m_singleCharMap.clear();
    188         m_map.clear();
    189         return 0;
    190     }
    191 
    192     typedef HashMap<SmallStringKey, WidthCacheEntry, SmallStringKeyHash, SmallStringKeyHashTraits> Map;
    193     typedef HashMap<uint32_t, WidthCacheEntry, DefaultHash<uint32_t>::Hash, WTF::UnsignedWithZeroKeyHashTraits<uint32_t> > SingleCharMap;
    194     static const int s_minInterval = -3; // A cache hit pays for about 3 cache misses.
    195     static const int s_maxInterval = 20; // Sampling at this interval has almost no overhead.
    196     static const unsigned s_maxSize = 500000; // Just enough to guard against pathological growth.
    197 
    198     int m_interval;
    199     int m_countdown;
    200     SingleCharMap m_singleCharMap;
    201     Map m_map;
    202 };
    203 
    204 inline bool operator==(const WidthCache::SmallStringKey& a, const WidthCache::SmallStringKey& b)
    205 {
    206     if (a.length() != b.length())
    207         return false;
    208     return WTF::equal(a.characters(), b.characters(), a.length());
    209 }
    210 
    211 } // namespace blink
    212 
    213 #endif // WidthCache_h
    214