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
37namespace blink {
38
39struct 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
49class WidthCache {
50private:
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
124public:
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
150private:
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
204inline 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