Changeset 195356 in webkit


Ignore:
Timestamp:
Jan 20, 2016 9:59:02 AM (8 years ago)
Author:
commit-queue@webkit.org
Message:

Refactor AtomicStringKeyedMRUCache to be a generic LRU cache
​https://bugs.webkit.org/show_bug.cgi?id=153109

Patch by Said Abou-Hallawa <​sabouhallawa@apple.com> on 2016-01-20
Reviewed by Darin Adler.

Source/WebCore:

Replace the template specialization of AtomicStringKeyedMRUCache with
template derived from TinyLRUCachePolicy. Override the functions which
are needed for creating the values and the null value. Also replace the
static function which was returning a NeverDestroyed AtomicStringKeyedMRUCache
with a singleton function 'cache' inside the derived template.

  • WebCore.xcodeproj/project.pbxproj:
  • platform/text/AtomicStringKeyedMRUCache.h: Removed.
  • platform/text/cf/HyphenationCF.cpp:

(WebCore::canHyphenate):
(WebCore::lastHyphenLocation):
(WebCore::AtomicStringKeyedMRUCache<RetainPtr<CFLocaleRef>>::createValueForNullKey): Deleted.
(WebCore::AtomicStringKeyedMRUCache<RetainPtr<CFLocaleRef>>::createValueForKey): Deleted.
(WebCore::cfLocaleCache): Deleted.

  • platform/text/hyphen/HyphenationLibHyphen.cpp:

(WebCore::countLeadingSpaces):
(WebCore::lastHyphenLocation):
(WebCore::AtomicStringKeyedMRUCache<RefPtr<HyphenationDictionary>>::createValueForNullKey): Deleted.
(WebCore::AtomicStringKeyedMRUCache<RefPtr<HyphenationDictionary>>::createValueForKey): Deleted.
(WebCore::hyphenDictionaryCache): Deleted.

Source/WTF:

Refactor AtomicStringKeyedMRUCache, move it to WTF project and rename it
to be TinyLRUCache. Define another template and call it TinyLRUCachePolicy.
This one can be overridden for different keys and values. Its function is
creating the cached values.

  • WTF.xcodeproj/project.pbxproj:
  • wtf/TinyLRUCache.h: Added.

(WebCore::TinyLRUCachePolicy::isKeyNull):
(WebCore::TinyLRUCachePolicy::createValueForNullKey):
(WebCore::TinyLRUCachePolicy::createValueForKey):
(WebCore::TinyLRUCache::get):

Location:
trunk/Source
Files:
6 edited
1 moved

Legend:

Unmodified
Added
Removed

  • trunk/Source/WTF/ChangeLog

    r195339 r195356  
     12016-01-20  Said Abou-Hallawa  <sabouhallawa@apple.com>
     2
     3        Refactor AtomicStringKeyedMRUCache to be a generic LRU cache
     4        https://bugs.webkit.org/show_bug.cgi?id=153109
     5
     6        Reviewed by Darin Adler.
     7
     8        Refactor AtomicStringKeyedMRUCache, move it to WTF project and rename it
     9        to be TinyLRUCache. Define another template and call it TinyLRUCachePolicy.
     10        This one can be overridden for different keys and values. Its function is
     11        creating the cached values.
     12
     13        * WTF.xcodeproj/project.pbxproj:
     14        * wtf/TinyLRUCache.h: Added.
     15        (WebCore::TinyLRUCachePolicy::isKeyNull):
     16        (WebCore::TinyLRUCachePolicy::createValueForNullKey):
     17        (WebCore::TinyLRUCachePolicy::createValueForKey):
     18        (WebCore::TinyLRUCache::get):
     19
    1202016-01-19  Saam barati  <sbarati@apple.com>
    221

  • trunk/Source/WTF/WTF.xcodeproj/project.pbxproj

    r195304 r195356  
    9797                2CDED0F418115C85004DBA70 /* RunLoop.h in Headers */ = {isa = PBXBuildFile; fileRef = 2CDED0F218115C85004DBA70 /* RunLoop.h */; };
    9898                430B47891AAAAC1A001223DA /* StringCommon.h in Headers */ = {isa = PBXBuildFile; fileRef = 430B47871AAAAC1A001223DA /* StringCommon.h */; };
     99                553071CA1C40427200384898 /* TinyLRUCache.h in Headers */ = {isa = PBXBuildFile; fileRef = 553071C91C40427200384898 /* TinyLRUCache.h */; };
    99100                70A993FE1AD7151300FA615B /* SymbolRegistry.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 70A993FC1AD7151300FA615B /* SymbolRegistry.cpp */; };
    100101                70A993FF1AD7151300FA615B /* SymbolRegistry.h in Headers */ = {isa = PBXBuildFile; fileRef = 70A993FD1AD7151300FA615B /* SymbolRegistry.h */; };
    … …  
    403404                2CDED0F218115C85004DBA70 /* RunLoop.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = RunLoop.h; sourceTree = "<group>"; };
    404405                430B47871AAAAC1A001223DA /* StringCommon.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = StringCommon.h; sourceTree = "<group>"; };
     406                553071C91C40427200384898 /* TinyLRUCache.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = TinyLRUCache.h; sourceTree = "<group>"; };
    405407                5D247B6214689B8600E78B76 /* libWTF.a */ = {isa = PBXFileReference; explicitFileType = archive.ar; includeInIndex = 0; path = libWTF.a; sourceTree = BUILT_PRODUCTS_DIR; };
    406408                5D247B6E14689C4700E78B76 /* Base.xcconfig */ = {isa = PBXFileReference; lastKnownFileType = text.xcconfig; path = Base.xcconfig; sourceTree = "<group>"; };
    … …  
    929931                                A8A4733E151A825B004123FF /* ThreadSafeRefCounted.h */,
    930932                                A8A4733F151A825B004123FF /* ThreadSpecific.h */,
     933                                553071C91C40427200384898 /* TinyLRUCache.h */,
    931934                                0FED67B51B22D4D80066CE15 /* TinyPtrSet.h */,
    932935                                149EF16216BBFE0D000A4331 /* TriState.h */,
    … …  
    12311234                                0F87105A16643F190090B0AD /* RawPointer.h in Headers */,
    12321235                                A8A47417151A825B004123FF /* RedBlackTree.h in Headers */,
     1236                                553071CA1C40427200384898 /* TinyLRUCache.h in Headers */,
    12331237                                26299B6E17A9E5B800ADEBE5 /* Ref.h in Headers */,
    12341238                                A8A47418151A825B004123FF /* RefCounted.h in Headers */,

  • trunk/Source/WTF/wtf/TinyLRUCache.h

    r195355 r195356  
    11/*
    2  * Copyright (C) 2010 Apple Inc. All rights reserved.
     2 * Copyright (C) 2010, 2016 Apple Inc. All rights reserved.
    33 *
    44 * Redistribution and use in source and binary forms, with or without
    … …  
    2424 */
    2525
    26 #ifndef AtomicStringKeyedMRUCache_h
    27 #define AtomicStringKeyedMRUCache_h
     26#ifndef TinyLRUCache_h
     27#define TinyLRUCache_h
    2828
    2929#include <wtf/NeverDestroyed.h>
    30 #include <wtf/text/AtomicString.h>
     30#include <wtf/Vector.h>
    3131
    3232namespace WebCore {
    3333
    34 template<typename T, size_t capacity = 4>
    35 class AtomicStringKeyedMRUCache {
     34template<typename KeyType, typename ValueType>
     35struct TinyLRUCachePolicy {
     36    static bool isKeyNull(const KeyType&) { return false; }
     37    static ValueType createValueForNullKey() { return { }; }
     38    static ValueType createValueForKey(const KeyType&) { return { }; }
     39};
     40
     41template<typename KeyType, typename ValueType, size_t capacity = 4>
     42class TinyLRUCache {
    3643public:
    37     T get(const AtomicString& key)
     44    const ValueType& get(const KeyType& key)
    3845    {
    39         if (key.isNull()) {
    40             static NeverDestroyed<T> valueForNull(createValueForNullKey());
     46        if (TinyLRUCachePolicy<KeyType, ValueType>::isKeyNull(key)) {
     47            static NeverDestroyed<ValueType> valueForNull = TinyLRUCachePolicy<KeyType, ValueType>::createValueForNullKey();
    4148            return valueForNull;
    4249        }
    4350
    4451        for (size_t i = 0; i < m_cache.size(); ++i) {
    45             if (m_cache[i].first == key) {
    46                 size_t foundIndex = i;
    47                 if (foundIndex + 1 < m_cache.size()) {
    48                     Entry entry = m_cache[foundIndex];
    49                     m_cache.remove(foundIndex);
    50                     foundIndex = m_cache.size();
    51                     m_cache.append(entry);
    52                 }
    53                 return m_cache[foundIndex].second;
    54             }
     52            if (m_cache[i].first != key)
     53                continue;
     54
     55            if (i == m_cache.size() - 1)
     56                return m_cache[i].second;
     57
     58            // If the entry is not the last one, move it to the end of the cache.
     59            Entry entry = WTFMove(m_cache[i]);
     60            m_cache.remove(i);
     61            m_cache.append(WTFMove(entry));
     62            return m_cache[m_cache.size() - 1].second;
    5563        }
     64
     65        // m_cache[0] is the LRU entry, so remove it.
    5666        if (m_cache.size() == capacity)
    5767            m_cache.remove(0);
    5868
    59         m_cache.append(std::make_pair(key, createValueForKey(key)));
     69        m_cache.append(std::make_pair(key, TinyLRUCachePolicy<KeyType, ValueType>::createValueForKey(key)));
    6070        return m_cache.last().second;
    6171    }
    6272
    6373private:
    64     T createValueForNullKey();
    65     T createValueForKey(const AtomicString&);
    66 
    67     typedef std::pair<AtomicString, T> Entry;
     74    typedef std::pair<KeyType, ValueType> Entry;
    6875    typedef Vector<Entry, capacity> Cache;
    6976    Cache m_cache;
    … …  
    7279}
    7380
    74 #endif // AtomicStringKeyedMRUCache_h
     81#endif // TinyLRUCache_h

  • trunk/Source/WebCore/ChangeLog

    r195355 r195356  
     12016-01-20  Said Abou-Hallawa  <sabouhallawa@apple.com>
     2
     3        Refactor AtomicStringKeyedMRUCache to be a generic LRU cache
     4        https://bugs.webkit.org/show_bug.cgi?id=153109
     5
     6        Reviewed by Darin Adler.
     7
     8        Replace the template specialization of AtomicStringKeyedMRUCache with
     9        template derived from TinyLRUCachePolicy. Override the functions which
     10        are needed for creating the values and the null value. Also replace the
     11        static function which was returning a NeverDestroyed AtomicStringKeyedMRUCache
     12        with a singleton function 'cache' inside the derived template.
     13
     14        * WebCore.xcodeproj/project.pbxproj:
     15        * platform/text/AtomicStringKeyedMRUCache.h: Removed.
     16        * platform/text/cf/HyphenationCF.cpp:
     17        (WebCore::canHyphenate):
     18        (WebCore::lastHyphenLocation):
     19        (WebCore::AtomicStringKeyedMRUCache<RetainPtr<CFLocaleRef>>::createValueForNullKey): Deleted.
     20        (WebCore::AtomicStringKeyedMRUCache<RetainPtr<CFLocaleRef>>::createValueForKey): Deleted.
     21        (WebCore::cfLocaleCache): Deleted.
     22        * platform/text/hyphen/HyphenationLibHyphen.cpp:
     23        (WebCore::countLeadingSpaces):
     24        (WebCore::lastHyphenLocation):
     25        (WebCore::AtomicStringKeyedMRUCache<RefPtr<HyphenationDictionary>>::createValueForNullKey): Deleted.
     26        (WebCore::AtomicStringKeyedMRUCache<RefPtr<HyphenationDictionary>>::createValueForKey): Deleted.
     27        (WebCore::hyphenDictionaryCache): Deleted.
     28
    1292016-01-20  Chris Dumez  <cdumez@apple.com>
    230

  • trunk/Source/WebCore/WebCore.xcodeproj/project.pbxproj

    r195335 r195356  
    14261426                37C236111097EE7700EF9F72 /* ComplexTextController.h in Headers */ = {isa = PBXBuildFile; fileRef = 37C2360F1097EE7700EF9F72 /* ComplexTextController.h */; };
    14271427                37C238221098C84200EF9F72 /* ComplexTextControllerCoreText.mm in Sources */ = {isa = PBXBuildFile; fileRef = 37C238201098C84200EF9F72 /* ComplexTextControllerCoreText.mm */; };
    1428                 37C61F0112095C87007A3C67 /* AtomicStringKeyedMRUCache.h in Headers */ = {isa = PBXBuildFile; fileRef = 37C61F0012095C87007A3C67 /* AtomicStringKeyedMRUCache.h */; };
    14291428                37D456FD1A9A50D8003330A1 /* LocalizableStrings.pm in Copy Scripts */ = {isa = PBXBuildFile; fileRef = 37D456FB1A9A50B6003330A1 /* LocalizableStrings.pm */; };
    14301429                37DDCD9413844FD50008B793 /* MIMEHeader.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 37DDCD9213844FD50008B793 /* MIMEHeader.cpp */; };
    … …  
    88218820                37C2360F1097EE7700EF9F72 /* ComplexTextController.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ComplexTextController.h; sourceTree = "<group>"; };
    88228821                37C238201098C84200EF9F72 /* ComplexTextControllerCoreText.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; path = ComplexTextControllerCoreText.mm; sourceTree = "<group>"; xcLanguageSpecificationIdentifier = xcode.lang.objcpp; };
    8823                 37C61F0012095C87007A3C67 /* AtomicStringKeyedMRUCache.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = AtomicStringKeyedMRUCache.h; sourceTree = "<group>"; };
    88248822                37D456FB1A9A50B6003330A1 /* LocalizableStrings.pm */ = {isa = PBXFileReference; lastKnownFileType = text.script.perl; path = LocalizableStrings.pm; sourceTree = "<group>"; };
    88258823                37DDCD9213844FD50008B793 /* MIMEHeader.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = MIMEHeader.cpp; sourceTree = "<group>"; };
    … …  
    2177921777                                A516E8B2136E04C00076C3C0 /* ios */,
    2178021778                                B2C3D9F90D006C1D00EF6F26 /* mac */,
    21781                                 37C61F0012095C87007A3C67 /* AtomicStringKeyedMRUCache.h */,
    2178221779                                B2C3D9F20D006C1D00EF6F26 /* BidiContext.cpp */,
    2178321780                                B2C3D9F30D006C1D00EF6F26 /* BidiContext.h */,
    … …  
    2465124648                                E1CDE9221501916900862CC5 /* AsyncFileStream.h in Headers */,
    2465224649                                0FFD4D6118651FA300512F6E /* AsyncScrollingCoordinator.h in Headers */,
    24653                                 37C61F0112095C87007A3C67 /* AtomicStringKeyedMRUCache.h in Headers */,
    2465424650                                A8C4A80D09D563270003AC8D /* Attr.h in Headers */,
    2465524651                                A8C4A80B09D563270003AC8D /* Attribute.h in Headers */,

  • trunk/Source/WebCore/platform/text/cf/HyphenationCF.cpp

    r194819 r195356  
    2727#include "Hyphenation.h"
    2828
    29 #include "AtomicStringKeyedMRUCache.h"
    3029#include "Language.h"
    3130#include "TextBreakIteratorInternalICU.h"
    3231#include <wtf/ListHashSet.h>
    3332#include <wtf/RetainPtr.h>
     33#include <wtf/TinyLRUCache.h>
    3434#include <wtf/text/StringView.h>
    3535
    … …  
    3737
    3838template<>
    39 RetainPtr<CFLocaleRef> AtomicStringKeyedMRUCache<RetainPtr<CFLocaleRef>>::createValueForNullKey()
     39class TinyLRUCachePolicy<AtomicString, RetainPtr<CFLocaleRef>>
    4040{
    41     // CF hyphenation functions use locale (regional formats) language, which doesn't necessarily match primary UI language,
    42     // so we can't use default locale here. See <rdar://problem/14897664>.
    43     RetainPtr<CFLocaleRef> locale = adoptCF(CFLocaleCreate(kCFAllocatorDefault, defaultLanguage().createCFString().get()));
     41public:
     42    static TinyLRUCache<AtomicString, RetainPtr<CFLocaleRef>>& cache()
     43    {
     44        static NeverDestroyed<TinyLRUCache<AtomicString, RetainPtr<CFLocaleRef>>> cache;
     45        return cache;
     46    }
    4447
    45     return CFStringIsHyphenationAvailableForLocale(locale.get()) ? locale : 0;
    46 }
     48    static bool isKeyNull(const AtomicString& localeIdentifier)
     49    {
     50        return localeIdentifier.isNull();
     51    }
    4752
    48 template<>
    49 RetainPtr<CFLocaleRef> AtomicStringKeyedMRUCache<RetainPtr<CFLocaleRef>>::createValueForKey(const AtomicString& localeIdentifier)
    50 {
    51     RetainPtr<CFLocaleRef> locale = adoptCF(CFLocaleCreate(kCFAllocatorDefault, localeIdentifier.string().createCFString().get()));
     53    static RetainPtr<CFLocaleRef> createValueForNullKey()
     54    {
     55        // CF hyphenation functions use locale (regional formats) language, which doesn't necessarily match primary UI language,
     56        // so we can't use default locale here. See <rdar://problem/14897664>.
     57        RetainPtr<CFLocaleRef> locale = adoptCF(CFLocaleCreate(kCFAllocatorDefault, defaultLanguage().createCFString().get()));
     58        return CFStringIsHyphenationAvailableForLocale(locale.get()) ? locale : nullptr;
     59    }
    5260
    53     return CFStringIsHyphenationAvailableForLocale(locale.get()) ? locale : 0;
    54 }
     61    static RetainPtr<CFLocaleRef> createValueForKey(const AtomicString& localeIdentifier)
     62    {
     63        RetainPtr<CFLocaleRef> locale = adoptCF(CFLocaleCreate(kCFAllocatorDefault, localeIdentifier.string().createCFString().get()));
    5564
    56 static AtomicStringKeyedMRUCache<RetainPtr<CFLocaleRef>>& cfLocaleCache()
    57 {
    58     static NeverDestroyed<AtomicStringKeyedMRUCache<RetainPtr<CFLocaleRef>>> cache;
    59     return cache;
    60 }
     65        return CFStringIsHyphenationAvailableForLocale(locale.get()) ? locale : nullptr;
     66    }
     67};
    6168
    6269bool canHyphenate(const AtomicString& localeIdentifier)
    6370{
    64     return cfLocaleCache().get(localeIdentifier);
     71    return TinyLRUCachePolicy<AtomicString, RetainPtr<CFLocaleRef>>::cache().get(localeIdentifier);
    6572}
    6673
    6774size_t lastHyphenLocation(StringView text, size_t beforeIndex, const AtomicString& localeIdentifier)
    6875{
    69     RetainPtr<CFLocaleRef> locale = cfLocaleCache().get(localeIdentifier);
     76    RetainPtr<CFLocaleRef> locale = TinyLRUCachePolicy<AtomicString, RetainPtr<CFLocaleRef>>::cache().get(localeIdentifier);
    7077    ASSERT(locale);
    7178

  • trunk/Source/WebCore/platform/text/hyphen/HyphenationLibHyphen.cpp

    r195058 r195356  
    3030#if USE(LIBHYPHEN)
    3131
    32 #include "AtomicStringKeyedMRUCache.h"
    3332#include "FileSystem.h"
    3433#include <hyphen.h>
    3534#include <wtf/HashMap.h>
    3635#include <wtf/NeverDestroyed.h>
     36#include <wtf/TinyLRUCache.h>
    3737#include <wtf/text/AtomicStringHash.h>
    3838#include <wtf/text/CString.h>
    … …  
    168168
    169169template<>
    170 RefPtr<HyphenationDictionary> AtomicStringKeyedMRUCache<RefPtr<HyphenationDictionary>>::createValueForNullKey()
    171 {
    172     return HyphenationDictionary::createNull();
    173 }
    174 
    175 template<>
    176 RefPtr<HyphenationDictionary> AtomicStringKeyedMRUCache<RefPtr<HyphenationDictionary>>::createValueForKey(const AtomicString& dictionaryPath)
    177 {
    178     return HyphenationDictionary::create(fileSystemRepresentation(dictionaryPath.string()));
    179 }
    180 
    181 static AtomicStringKeyedMRUCache<RefPtr<HyphenationDictionary>>& hyphenDictionaryCache()
    182 {
    183     static NeverDestroyed<AtomicStringKeyedMRUCache<RefPtr<HyphenationDictionary>>> cache;
    184     return cache;
    185 }
     170class TinyLRUCachePolicy<AtomicString, RefPtr<HyphenationDictionary>>
     171{
     172public:
     173    static TinyLRUCache<AtomicString, RefPtr<HyphenationDictionary>>& cache()
     174    {
     175        static NeverDestroyed<TinyLRUCache<AtomicString, RefPtr<HyphenationDictionary>>> cache;
     176        return cache;
     177    }
     178
     179    static bool isKeyNull(const AtomicString& localeIdentifier)
     180    {
     181        return localeIdentifier.isNull();
     182    }
     183
     184    static RefPtr<HyphenationDictionary> createValueForNullKey()
     185    {
     186        return HyphenationDictionary::createNull();
     187    }
     188
     189    static RefPtr<HyphenationDictionary> createValueForKey(const AtomicString& dictionaryPath)
     190    {
     191        return HyphenationDictionary::create(fileSystemRepresentation(dictionaryPath.string()));
     192    }
     193};
    186194
    187195static void countLeadingSpaces(const CString& utf8String, int32_t& pointerOffset, int32_t& characterOffset)
    … …  
    226234    ASSERT(availableLocales().contains(lowercaseLocaleIdentifier));
    227235    for (const auto& dictionaryPath : availableLocales().get(lowercaseLocaleIdentifier)) {
    228         RefPtr<HyphenationDictionary> dictionary = hyphenDictionaryCache().get(AtomicString(dictionaryPath));
     236        RefPtr<HyphenationDictionary> dictionary = TinyLRUCachePolicy<AtomicString, RefPtr<HyphenationDictionary>>::cache().get(AtomicString(dictionaryPath));
    229237
    230238        char** replacements = nullptr;
Note: See TracChangeset for help on using the changeset viewer.