Changeset 196716 in webkit


Ignore:
Timestamp:
Feb 17, 2016, 1:17:00 PM (10 years ago)
Author:
weinig@apple.com
Message:

Add an ensure function on HashMap that takes a key and a function to make the lazy value initialization idiom easier
​https://bugs.webkit.org/show_bug.cgi?id=134857

Reviewed by Geoffrey Garen.

Source/WTF:

The current idiom for adding a value to a HashMap if the key is not already present, to allow for not
unnecessarily constructing the new value if it won't be used, is:

{

auto result = map.add(key, Value());
if (!result.isNewEntry)

return result.iterator->value;

result.iterator->value = createNewValue();
return result.iterator->value;

}

or sometimes

{

auto& value = map.add(key, Value()).iterator->value;
if (!value)

value = createNewValue();

return value;

}

With this patch, you can now use the new function HashMap::ensure(key, functor). This will allow us to
change to using the following idiom:

{

return map.ensure(key, [] { return createNewValue(); });

}

The passed in functor will only be called if the key is not already present in the HashMap.

  • wtf/HashMap.h:

(WTF::HashMapTranslator::translate):
(WTF::HashMapEnsureTranslator::hash):
(WTF::HashMapEnsureTranslator::equal):
(WTF::HashMapEnsureTranslator::translate):
(WTF::HashMapTranslatorAdapter::hash):

Tools:

  • TestWebKitAPI/Tests/WTF/HashMap.cpp:

Add tests for HashMap::ensure.

Location:
trunk
Files:
4 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/WTF/ChangeLog

    r196686 r196716  
     12016-02-16  Sam Weinig  <sam@webkit.org>
     2
     3        Add an ensure function on HashMap that takes a key and a function to make the lazy value initialization idiom easier
     4        https://bugs.webkit.org/show_bug.cgi?id=134857
     5
     6        Reviewed by Geoffrey Garen.
     7
     8        The current idiom for adding a value to a HashMap if the key is not already present, to allow for not
     9        unnecessarily constructing the new value if it won't be used, is:
     10       
     11        {
     12            auto result = map.add(key, Value());
     13            if (!result.isNewEntry)
     14                return result.iterator->value;
     15
     16            result.iterator->value = createNewValue();
     17            return result.iterator->value;
     18        }
     19
     20        or sometimes
     21
     22        {
     23            auto& value = map.add(key, Value()).iterator->value;
     24            if (!value)
     25                value = createNewValue();
     26            return value;
     27        }
     28
     29        With this patch, you can now use the new function HashMap::ensure(key, functor). This will allow us to
     30        change to using the following idiom:
     31
     32        {
     33            return map.ensure(key, [] { return createNewValue(); });
     34        }
     35
     36        The passed in functor will only be called if the key is not already present in the HashMap.
     37
     38        * wtf/HashMap.h:
     39        (WTF::HashMapTranslator::translate):
     40        (WTF::HashMapEnsureTranslator::hash):
     41        (WTF::HashMapEnsureTranslator::equal):
     42        (WTF::HashMapEnsureTranslator::translate):
     43        (WTF::HashMapTranslatorAdapter::hash):
     44
    1452016-02-16  Filip Pizlo  <fpizlo@apple.com>
    246

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

    r194496 r196716  
    119119    template<typename V> AddResult fastAdd(KeyType&&, V&&);
    120120
     121    template<typename Functor> MappedType& ensure(const KeyType&, const Functor&);
     122    template<typename Functor> MappedType& ensure(KeyType&&, const Functor&);
     123
    121124    bool remove(const KeyType&);
    122125    bool remove(iterator);
    … …  
    164167    AddResult inlineAdd(K&&, V&&);
    165168
     169    template<typename K, typename F>
     170    MappedType& inlineEnsure(K&&, const F&);
     171
    166172    HashTableType m_impl;
    167173};
    … …  
    178184};
    179185
     186template<typename ValueTraits, typename HashFunctions>
     187struct HashMapEnsureTranslator {
     188    template<typename T> static unsigned hash(const T& key) { return HashFunctions::hash(key); }
     189    template<typename T, typename U> static bool equal(const T& a, const U& b) { return HashFunctions::equal(a, b); }
     190    template<typename T, typename U, typename Functor> static void translate(T& location, U&& key, const Functor& functor)
     191    {
     192        location.key = std::forward<U>(key);
     193        location.value = functor();
     194    }
     195};
     196
    180197template<typename ValueTraits, typename Translator>
    181198struct HashMapTranslatorAdapter {
    … …  
    298315
    299316template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg>
     317template<typename K, typename F>
     318ALWAYS_INLINE auto HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg>::inlineEnsure(K&& key, const F& functor) -> MappedType&
     319{
     320    return m_impl.template add<HashMapEnsureTranslator<KeyValuePairTraits, HashFunctions>>(std::forward<K>(key), functor).iterator->value;
     321}
     322
     323template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg>
    300324template<typename T>
    301325auto HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg>::set(const KeyType& key, T&& mapped) -> AddResult
    … …  
    346370}
    347371
     372template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg>
     373template<typename Functor>
     374auto HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg>::ensure(const KeyType& key, const Functor& functor) -> MappedType&
     375{
     376    return inlineEnsure(key, functor);
     377}
     378
     379template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg>
     380template<typename Functor>
     381auto HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg>::ensure(KeyType&& key, const Functor& functor) -> MappedType&
     382{
     383    return inlineEnsure(WTFMove(key), functor);
     384}
     385   
    348386template<typename T, typename U, typename V, typename W, typename MappedTraits>
    349387auto HashMap<T, U, V, W, MappedTraits>::get(const KeyType& key) const -> MappedPeekType

  • trunk/Tools/ChangeLog

    r196699 r196716  
     12016-02-16  Sam Weinig  <sam@webkit.org>
     2
     3        Add an ensure function on HashMap that takes a key and a function to make the lazy value initialization idiom easier
     4        https://bugs.webkit.org/show_bug.cgi?id=134857
     5
     6        Reviewed by Geoffrey Garen.
     7
     8        * TestWebKitAPI/Tests/WTF/HashMap.cpp:
     9        Add tests for HashMap::ensure.
     10
    1112016-02-17  Nan Wang  <n_wang@apple.com>
    212

  • trunk/Tools/TestWebKitAPI/Tests/WTF/HashMap.cpp

    r194496 r196716  
    509509}
    510510
     511TEST(WTF_HashMap, Ensure)
     512{
     513    HashMap<unsigned, unsigned> map;
     514    {
     515        auto value = map.ensure(1, [] { return 1; });
     516        EXPECT_EQ(1u, value);
     517        value = map.ensure(1, [] { return 2; });
     518        EXPECT_EQ(1u, value);
     519    }
     520}
     521
     522TEST(WTF_HashMap, Ensure_MoveOnlyValues)
     523{
     524    HashMap<unsigned, MoveOnly> moveOnlyValues;
     525    {
     526        auto& value = moveOnlyValues.ensure(1, [] { return MoveOnly(1); });
     527        EXPECT_EQ(1u, value.value());
     528        auto& value2 = moveOnlyValues.ensure(1, [] { return MoveOnly(2); });
     529        EXPECT_EQ(1u, value2.value());
     530    }
     531}
     532
     533TEST(WTF_HashMap, Ensure_UniquePointer)
     534{
     535    HashMap<unsigned, std::unique_ptr<unsigned>> map;
     536    {
     537        auto& value = map.ensure(1, [] { return std::make_unique<unsigned>(1); });
     538        EXPECT_EQ(1u, *map.get(1));
     539        EXPECT_EQ(1u, *value.get());
     540        auto& value2 = map.ensure(1, [] { return std::make_unique<unsigned>(2); });
     541        EXPECT_EQ(1u, *map.get(1));
     542        EXPECT_EQ(1u, *value2.get());
     543    }
     544}
     545
     546TEST(WTF_HashMap, Ensure_RefPtr)
     547{
     548    HashMap<unsigned, RefPtr<RefLogger>> map;
     549
     550    {
     551        DerivedRefLogger a("a");
     552
     553        map.ensure(1, [&] { return RefPtr<RefLogger>(&a); });
     554        EXPECT_STREQ("ref(a) ", takeLogStr().c_str());
     555
     556        map.ensure(1, [&] { return RefPtr<RefLogger>(&a); });
     557        EXPECT_STREQ("", takeLogStr().c_str());
     558    }
     559}
     560
    511561} // namespace TestWebKitAPI
Note: See TracChangeset for help on using the changeset viewer.