15c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/* 25c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Copyright (C) 2012 Apple Inc. All rights reserved. 35c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 45c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Redistribution and use in source and binary forms, with or without 55c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * modification, are permitted provided that the following conditions 65c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * are met: 75c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 1. Redistributions of source code must retain the above copyright 85c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * notice, this list of conditions and the following disclaimer. 95c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 2. Redistributions in binary form must reproduce the above copyright 105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * notice, this list of conditions and the following disclaimer in the 115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * documentation and/or other materials provided with the distribution. 125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY 145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR 175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY 215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2302772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#ifndef WidthCache_h 275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#define WidthCache_h 285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 29d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles)#include "platform/geometry/IntRectExtent.h" 30a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)#include "platform/text/TextRun.h" 310019e4eead4d990e4304c54a9028aca9122fb256Ben Murdoch#include "wtf/Forward.h" 320019e4eead4d990e4304c54a9028aca9122fb256Ben Murdoch#include "wtf/HashFunctions.h" 330019e4eead4d990e4304c54a9028aca9122fb256Ben Murdoch#include "wtf/HashSet.h" 340019e4eead4d990e4304c54a9028aca9122fb256Ben Murdoch#include "wtf/HashTableDeletedValueType.h" 350019e4eead4d990e4304c54a9028aca9122fb256Ben Murdoch#include "wtf/StringHasher.h" 365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 37c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)namespace blink { 385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 39d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles)struct WidthCacheEntry { 40d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles) WidthCacheEntry() 41d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles) { 42d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles) width = std::numeric_limits<float>::quiet_NaN(); 43d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles) } 44d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles) bool isValid() const { return !std::isnan(width); } 45d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles) float width; 46d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles) IntRectExtent glyphBounds; 47d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles)}; 48d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles) 495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)class WidthCache { 505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)private: 515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Used to optimize small strings as hash table keys. Avoids malloc'ing an out-of-line StringImpl. 525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) class SmallStringKey { 535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) public: 545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static unsigned capacity() { return s_capacity; } 555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) SmallStringKey() 575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) : m_length(s_emptyValueLength) 585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) SmallStringKey(WTF::HashTableDeletedValueType) 625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) : m_length(s_deletedValueLength) 635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename CharacterType> SmallStringKey(CharacterType* characters, unsigned short length) 675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) : m_length(length) 685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(length <= s_capacity); 70926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) StringHasher hasher; 725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool remainder = length & 1; 745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) length >>= 1; 755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) unsigned i = 0; 775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (length--) { 785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_characters[i] = characters[i]; 795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_characters[i + 1] = characters[i + 1]; 80926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) hasher.addCharactersAssumingAligned(characters[i], characters[i + 1]); 815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) i += 2; 825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (remainder) { 855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_characters[i] = characters[i]; 865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) hasher.addCharacter(characters[i]); 875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_hash = hasher.hash(); 905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const UChar* characters() const { return m_characters; } 935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) unsigned short length() const { return m_length; } 945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) unsigned hash() const { return m_hash; } 955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool isHashTableDeletedValue() const { return m_length == s_deletedValueLength; } 975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool isHashTableEmptyValue() const { return m_length == s_emptyValueLength; } 985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) private: 1005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const unsigned s_capacity = 15; 1015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const unsigned s_emptyValueLength = s_capacity + 1; 1025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const unsigned s_deletedValueLength = s_capacity + 2; 1035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) unsigned m_hash; 1055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) unsigned short m_length; 1065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) UChar m_characters[s_capacity]; 1075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 1085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) struct SmallStringKeyHash { 1105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static unsigned hash(const SmallStringKey& key) { return key.hash(); } 1115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static bool equal(const SmallStringKey& a, const SmallStringKey& b) { return a == b; } 1125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const bool safeToCompareToEmptyOrDeleted = true; // Empty and deleted values have lengths that are not equal to any valid length. 1135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 1145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) struct SmallStringKeyHashTraits : WTF::SimpleClassHashTraits<SmallStringKey> { 1165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const bool hasIsEmptyValueFunction = true; 1175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static bool isEmptyValue(const SmallStringKey& key) { return key.isHashTableEmptyValue(); } 1185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const bool needsDestruction = false; 119f79f16f17ddc4f842d7b7a38603e280e94be826aTorne (Richard Coles) static const unsigned minimumTableSize = 16; 1205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 1215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) friend bool operator==(const SmallStringKey&, const SmallStringKey&); 1235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)public: 1255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) WidthCache() 1265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) : m_interval(s_maxInterval) 1275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) , m_countdown(m_interval) 1285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 131d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles) WidthCacheEntry* add(const TextRun& run, WidthCacheEntry entry) 1325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (static_cast<unsigned>(run.length()) > SmallStringKey::capacity()) 1345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return 0; 1355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (m_countdown > 0) { 1375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) --m_countdown; 1385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return 0; 1395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return addSlowCase(run, entry); 1425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 144926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) void clear() 1455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 146926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) m_singleCharMap.clear(); 147926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) m_map.clear(); 148926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) } 1495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 150926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)private: 151d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles) WidthCacheEntry* addSlowCase(const TextRun& run, WidthCacheEntry entry) 152926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) { 153926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) int length = run.length(); 154926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) bool isNewEntry; 155d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles) WidthCacheEntry *value; 156926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) if (length == 1) { 157926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) SingleCharMap::AddResult addResult = m_singleCharMap.add(run[0], entry); 158926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) isNewEntry = addResult.isNewEntry; 15909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) value = &addResult.storedValue->value; 160926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) } else { 161926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) SmallStringKey smallStringKey; 162926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) if (run.is8Bit()) 163926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) smallStringKey = SmallStringKey(run.characters8(), length); 164926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) else 165926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) smallStringKey = SmallStringKey(run.characters16(), length); 166926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 167926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) Map::AddResult addResult = m_map.add(smallStringKey, entry); 168926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) isNewEntry = addResult.isNewEntry; 16909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) value = &addResult.storedValue->value; 170926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) } 1715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Cache hit: ramp up by sampling the next few words. 173926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) if (!isNewEntry) { 1745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_interval = s_minInterval; 175926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) return value; 1765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Cache miss: ramp down by increasing our sampling interval. 1795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (m_interval < s_maxInterval) 1805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ++m_interval; 1815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_countdown = m_interval; 1825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 183926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) if ((m_singleCharMap.size() + m_map.size()) < s_maxSize) 184926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) return value; 1855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 186926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) // No need to be fancy: we're just trying to avoid pathological growth. 187926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) m_singleCharMap.clear(); 188926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) m_map.clear(); 1895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return 0; 1905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 192d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles) typedef HashMap<SmallStringKey, WidthCacheEntry, SmallStringKeyHash, SmallStringKeyHashTraits> Map; 193d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles) typedef HashMap<uint32_t, WidthCacheEntry, DefaultHash<uint32_t>::Hash, WTF::UnsignedWithZeroKeyHashTraits<uint32_t> > SingleCharMap; 1945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const int s_minInterval = -3; // A cache hit pays for about 3 cache misses. 1955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const int s_maxInterval = 20; // Sampling at this interval has almost no overhead. 19651b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) static const unsigned s_maxSize = 500000; // Just enough to guard against pathological growth. 1975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int m_interval; 1995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int m_countdown; 200926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) SingleCharMap m_singleCharMap; 2015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Map m_map; 2025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}; 2035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)inline bool operator==(const WidthCache::SmallStringKey& a, const WidthCache::SmallStringKey& b) 2055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 2065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (a.length() != b.length()) 2075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return false; 2085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return WTF::equal(a.characters(), b.characters(), a.length()); 2095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 2105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 211c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)} // namespace blink 2125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif // WidthCache_h 214