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 "TextRun.h"
30#include <wtf/Forward.h>
31#include <wtf/HashFunctions.h>
32#include <wtf/HashSet.h>
33#include <wtf/RefPtr.h>
34#include <wtf/StringHasher.h>
35
36namespace WebCore {
37
38struct GlyphOverflow;
39
40class WidthCache {
41private:
42    // Used to optimize small strings as hash table keys. Avoids malloc'ing an out-of-line StringImpl.
43    class SmallStringKey {
44    public:
45        static unsigned capacity() { return s_capacity; }
46
47        SmallStringKey()
48            : m_length(s_emptyValueLength)
49        {
50        }
51
52        SmallStringKey(WTF::HashTableDeletedValueType)
53            : m_length(s_deletedValueLength)
54        {
55        }
56
57        template<typename CharacterType> SmallStringKey(CharacterType* characters, unsigned short length)
58            : m_length(length)
59        {
60            ASSERT(length <= s_capacity);
61
62            StringHasher hasher;
63
64            bool remainder = length & 1;
65            length >>= 1;
66
67            unsigned i = 0;
68            while (length--) {
69                m_characters[i] = characters[i];
70                m_characters[i + 1] = characters[i + 1];
71                hasher.addCharactersAssumingAligned(characters[i], characters[i + 1]);
72                i += 2;
73            }
74
75            if (remainder) {
76                m_characters[i] = characters[i];
77                hasher.addCharacter(characters[i]);
78            }
79
80            m_hash = hasher.hash();
81        }
82
83        const UChar* characters() const { return m_characters; }
84        unsigned short length() const { return m_length; }
85        unsigned hash() const { return m_hash; }
86
87        bool isHashTableDeletedValue() const { return m_length == s_deletedValueLength; }
88        bool isHashTableEmptyValue() const { return m_length == s_emptyValueLength; }
89
90    private:
91        static const unsigned s_capacity = 15;
92        static const unsigned s_emptyValueLength = s_capacity + 1;
93        static const unsigned s_deletedValueLength = s_capacity + 2;
94
95        unsigned m_hash;
96        unsigned short m_length;
97        UChar m_characters[s_capacity];
98    };
99
100    struct SmallStringKeyHash {
101        static unsigned hash(const SmallStringKey& key) { return key.hash(); }
102        static bool equal(const SmallStringKey& a, const SmallStringKey& b) { return a == b; }
103        static const bool safeToCompareToEmptyOrDeleted = true; // Empty and deleted values have lengths that are not equal to any valid length.
104    };
105
106    struct SmallStringKeyHashTraits : WTF::SimpleClassHashTraits<SmallStringKey> {
107        static const bool hasIsEmptyValueFunction = true;
108        static bool isEmptyValue(const SmallStringKey& key) { return key.isHashTableEmptyValue(); }
109        static const bool needsDestruction = false;
110        static const int minimumTableSize = 16;
111    };
112
113    friend bool operator==(const SmallStringKey&, const SmallStringKey&);
114
115public:
116    WidthCache()
117        : m_interval(s_maxInterval)
118        , m_countdown(m_interval)
119    {
120    }
121
122    float* add(const TextRun& run, float entry, bool hasKerningOrLigatures, bool hasWordSpacingOrLetterSpacing, GlyphOverflow* glyphOverflow)
123    {
124        // The width cache is not really profitable unless we're doing expensive glyph transformations.
125        if (!hasKerningOrLigatures)
126            return 0;
127        // Word spacing and letter spacing can change the width of a word.
128        if (hasWordSpacingOrLetterSpacing)
129            return 0;
130        // Since this is just a width cache, we don't have enough information to satisfy glyph queries.
131        if (glyphOverflow)
132            return 0;
133        // If we allow tabs and a tab occurs inside a word, the width of the word varies based on its position on the line.
134        if (run.allowTabs())
135            return 0;
136        if (static_cast<unsigned>(run.length()) > SmallStringKey::capacity())
137            return 0;
138
139        if (m_countdown > 0) {
140            --m_countdown;
141            return 0;
142        }
143
144        return addSlowCase(run, entry);
145    }
146
147    void clear()
148    {
149        m_singleCharMap.clear();
150        m_map.clear();
151    }
152
153private:
154    float* addSlowCase(const TextRun& run, float entry)
155    {
156        int length = run.length();
157        bool isNewEntry;
158        float *value;
159        if (length == 1) {
160            SingleCharMap::AddResult addResult = m_singleCharMap.add(run[0], entry);
161            isNewEntry = addResult.isNewEntry;
162            value = &addResult.iterator->value;
163        } else {
164            SmallStringKey smallStringKey;
165            if (run.is8Bit())
166                smallStringKey = SmallStringKey(run.characters8(), length);
167            else
168                smallStringKey = SmallStringKey(run.characters16(), length);
169
170            Map::AddResult addResult = m_map.add(smallStringKey, entry);
171            isNewEntry = addResult.isNewEntry;
172            value = &addResult.iterator->value;
173        }
174
175        // Cache hit: ramp up by sampling the next few words.
176        if (!isNewEntry) {
177            m_interval = s_minInterval;
178            return value;
179        }
180
181        // Cache miss: ramp down by increasing our sampling interval.
182        if (m_interval < s_maxInterval)
183            ++m_interval;
184        m_countdown = m_interval;
185
186        if ((m_singleCharMap.size() + m_map.size()) < s_maxSize)
187            return value;
188
189        // No need to be fancy: we're just trying to avoid pathological growth.
190        m_singleCharMap.clear();
191        m_map.clear();
192        return 0;
193    }
194
195    typedef HashMap<SmallStringKey, float, SmallStringKeyHash, SmallStringKeyHashTraits> Map;
196    typedef HashMap<uint32_t, float, DefaultHash<uint32_t>::Hash, WTF::UnsignedWithZeroKeyHashTraits<uint32_t>> SingleCharMap;
197    static const int s_minInterval = -3; // A cache hit pays for about 3 cache misses.
198    static const int s_maxInterval = 20; // Sampling at this interval has almost no overhead.
199    static const int s_maxSize = 500000; // Just enough to guard against pathological growth.
200
201    int m_interval;
202    int m_countdown;
203    SingleCharMap m_singleCharMap;
204    Map m_map;
205};
206
207inline bool operator==(const WidthCache::SmallStringKey& a, const WidthCache::SmallStringKey& b)
208{
209    if (a.length() != b.length())
210        return false;
211    return WTF::equal(a.characters(), b.characters(), a.length());
212}
213
214} // namespace WebCore
215
216#endif // WidthCache_h
217