add TThreadSafeLRUCacheWithSizeProvider wrapper

На данный момент никак нельзя создать thread-safe кэш с произвольным SizeProvider, из-за того, что это не позволяет сделать шаблон `TThreadSafeCache`, при этом отредактировтаь его тоже не удастся, так как для этого нужно передать дополнительный параметр `typename TSizeProvider`, что сломает обратную совместимость, так как шаблон принимает далее переменное число аргументов (см. [TThreadSafeCache](https://a.yandex-team.ru/arcadia/library/cpp/cache/thread_safe_cache.h?rev=rXXXXXX#L15))
В связи с этим добавлен еще один хелпер, для создания LRUCache с TSizeProvider
293511a33b45f23d8afc9ff217a817481401932c

2 files changed, 308 insertions, 0 deletions

diff --git a/library/cpp/cache/thread_safe_cache.h b/library/cpp/cache/thread_safe_cache.h
index 2699c8f7b7..08c899ad3d 100644
--- a/library/cpp/cache/thread_safe_cache.h
+++ b/library/cpp/cache/thread_safe_cache.h
@@ -201,6 +201,44 @@ namespace NPrivate {
         using TCache = TThreadSafeCache<TKey, TValue, TListType, EGettersPromotionPolicy::Promoted, TArgs...>;
     };
 
+    struct TLFUHelper {
+        template <class TKey, class TValue>
+        using TListType = TLFUList<TKey, TValue>;
+
+        template <class TKey, class TValue, class... TArgs>
+        using TCache = TThreadSafeCache<TKey, TValue, TListType, EGettersPromotionPolicy::Promoted, TArgs...>;
+    };
+
+    template <class TSizeProvider, class TValue>
+    struct TSizeProviderRemoveAtomic : TSizeProvider {
+        // TValue in this signature is TCache::TPtr, using this wrapper user don't need
+        // to handle TPtr (which is TAtomicSharedPtr<TValue>) and can just accept TValue
+        // in custom size provider. See example in unittests
+        size_t operator()(const TValue& value) const {
+            // We can pass reference to value without synchronization, because TSizeProvider::operator()
+            // is always called from methods secured by a guard
+            return TSizeProvider::operator()(*value);
+        }
+    };
+
+    template <template <class, class, class> class TTemplateListType, EGettersPromotionPolicy GettersPromotionPolicy>
+    struct TCacheWithSizeProviderHelper {
+    private:
+        template <class TSizeProvider>
+        struct TListWithProvider {
+            template <class TKey, class TValue>
+            using TListType = TTemplateListType<TKey, TValue, TSizeProviderRemoveAtomic<TSizeProvider, TValue>>;
+        };
+
+    public:
+        template <class TKey, class TValue, class TSizeProvider, class... TArgs>
+        using TCache = TThreadSafeCache<TKey, TValue, TListWithProvider<TSizeProvider>::template TListType, GettersPromotionPolicy, TArgs...>;
+    };
+
+    using TLRUWithSizeProviderHelper = TCacheWithSizeProviderHelper<TLRUList, EGettersPromotionPolicy::Promoted>;
+
+    using TLFUWithSizeProviderHelper = TCacheWithSizeProviderHelper<TLFUList, EGettersPromotionPolicy::Promoted>;
+
 }
 
 template <class TKey, class TValue, class... TArgs>
@@ -209,3 +247,11 @@ using TThreadSafeCache = typename NPrivate::TLWHelper::template TCache<TKey, TVa
 template <class TKey, class TValue, class... TArgs>
 using TThreadSafeLRUCache = typename NPrivate::TLRUHelper::template TCache<TKey, TValue, TArgs...>;
 
+template <class TKey, class TValue, class... TArgs>
+using TThreadSafeLFUCache = typename NPrivate::TLFUHelper::template TCache<TKey, TValue, TArgs...>;
+
+template <class TKey, class TValue, class TSizeProvider, class... TArgs>
+using TThreadSafeLRUCacheWithSizeProvider = typename NPrivate::TLRUWithSizeProviderHelper::template TCache<TKey, TValue, TSizeProvider, TArgs...>;
+
+template <class TKey, class TValue, class TSizeProvider, class... TArgs>
+using TThreadSafeLFUCacheWithSizeProvider = typename NPrivate::TLFUWithSizeProviderHelper::template TCache<TKey, TValue, TSizeProvider, TArgs...>;
diff --git a/library/cpp/cache/ut/cache_ut.cpp b/library/cpp/cache/ut/cache_ut.cpp
index 36a3eff094..8546bc166c 100644
--- a/library/cpp/cache/ut/cache_ut.cpp
+++ b/library/cpp/cache/ut/cache_ut.cpp
@@ -735,3 +735,265 @@ Y_UNIT_TEST_SUITE(TThreadSafeLRUCacheTest) {
         UNIT_ASSERT(cache.Contains(0));
     }
 }
+
+Y_UNIT_TEST_SUITE(TThreadSafeLFUCacheTest) {
+    using TCache = TThreadSafeLFUCache<size_t, TString, size_t>;
+
+    TVector<TString> Values = {"a", "bb", "ccc", "dddd", "eeeee"};
+
+    class TCallbacks: public TCache::ICallbacks {
+    public:
+        TKey GetKey(size_t i) const override {
+            return i;
+        }
+
+        TValue* CreateObject(size_t i) const override {
+            UNIT_ASSERT(i < Values.size());
+            ++Creations;
+            return new TString(Values[i]);
+        }
+
+        mutable size_t Creations = 0;
+    };
+
+    Y_UNIT_TEST(SimpleTest) {
+        for (size_t i = 0; i < Values.size(); ++i) {
+            const TString data = *TCache::Get<TCallbacks>(i);
+            UNIT_ASSERT_EQUAL(data, Values[i]);
+        }
+    }
+
+    Y_UNIT_TEST(InsertUpdateTest) {
+        TCallbacks callbacks;
+        TCache cache(callbacks, 10);
+
+        cache.Insert(2, MakeAtomicShared<TString>("hj"));
+        TAtomicSharedPtr<TString> item = cache.Get(2);
+
+        UNIT_ASSERT(callbacks.Creations == 0);
+        UNIT_ASSERT(*item == "hj");
+
+        cache.Insert(2, MakeAtomicShared<TString>("hjk"));
+        item = cache.Get(2);
+
+        UNIT_ASSERT(callbacks.Creations == 0);
+        UNIT_ASSERT(*item == "hj");
+
+        cache.Update(2, MakeAtomicShared<TString>("hjk"));
+        item = cache.Get(2);
+
+        UNIT_ASSERT_EQUAL(cache.TotalSize(), 1);
+        UNIT_ASSERT_EQUAL(cache.Size(), 1);
+        UNIT_ASSERT(callbacks.Creations == 0);
+        UNIT_ASSERT(*item == "hjk");
+    }
+
+    Y_UNIT_TEST(LFUTest) {
+        TCallbacks callbacks;
+        TCache cache(callbacks, 3);
+        size_t expectedCreations = 0;
+
+        UNIT_ASSERT_EQUAL(cache.GetMaxSize(), 3);
+        auto item = cache.Get(0);
+        UNIT_ASSERT(*item == "a");
+        UNIT_ASSERT(cache.TotalSize() == 1);
+        UNIT_ASSERT(callbacks.Creations == ++expectedCreations);
+
+        item = cache.Get(1);
+        UNIT_ASSERT(*item == "bb");
+        UNIT_ASSERT(cache.TotalSize() == 2);
+        UNIT_ASSERT(callbacks.Creations == ++expectedCreations);
+
+        item = cache.Get(2);
+        UNIT_ASSERT(*item == "ccc");
+        UNIT_ASSERT(cache.TotalSize() == 3);
+        UNIT_ASSERT(callbacks.Creations == ++expectedCreations);
+
+        cache.Get(0);
+        cache.Get(0);
+        cache.Get(0);
+
+        cache.Get(1);
+
+        cache.Get(2);
+        cache.Get(2);
+
+        // evict 1
+        item = cache.Get(3);
+        UNIT_ASSERT(*item == "dddd");
+        UNIT_ASSERT(cache.TotalSize() == 3);
+        UNIT_ASSERT(callbacks.Creations == ++expectedCreations);
+
+        // check that 0 was evicted and left only 1 2 3
+        item = cache.Get(0);
+        UNIT_ASSERT(*item == "a");
+
+        item = cache.Get(2);
+        UNIT_ASSERT(*item == "ccc");
+
+        item = cache.Get(3);
+        UNIT_ASSERT(*item == "dddd");
+        UNIT_ASSERT(callbacks.Creations == expectedCreations);
+
+        cache.Get(0);
+        cache.Get(2);
+        cache.Get(3);
+
+        // evict 3
+        item = cache.Get(4);
+        UNIT_ASSERT(*item == "eeeee");
+        UNIT_ASSERT(cache.TotalSize() == 3);
+        UNIT_ASSERT(callbacks.Creations == ++expectedCreations);
+
+        // check that 1 was evicted and left only 2 3 4
+        item = cache.Get(0);
+        UNIT_ASSERT(*item == "a");
+
+        item = cache.Get(2);
+        UNIT_ASSERT(*item == "ccc");
+
+        item = cache.Get(4);
+        UNIT_ASSERT(*item == "eeeee");
+        UNIT_ASSERT(callbacks.Creations == expectedCreations);
+    }
+}
+
+Y_UNIT_TEST_SUITE(TThreadSafeLRUCacheWithSizeProviderTest) {
+    struct TStringLengthSizeProvider {
+        size_t operator()(const TString& s) const {
+            return s.size();
+        }
+    };
+    using TCache = TThreadSafeLRUCacheWithSizeProvider<size_t, TString, TStringLengthSizeProvider, size_t>;
+
+    TVector<TString> Values = {"a", "bb", "ccc", "dddd", "eeeee"};
+
+    class TCallbacks: public TCache::ICallbacks {
+    public:
+        TKey GetKey(size_t i) const override {
+            return i;
+        }
+        TValue* CreateObject(size_t i) const override {
+            UNIT_ASSERT(i < Values.size());
+            return new TString(Values[i]);
+        }
+    };
+
+    Y_UNIT_TEST(Test) {
+        TCallbacks callbacks;
+        TCache cache(callbacks, 6);
+
+        auto item = cache.Get(0);
+        UNIT_ASSERT(*item == "a");
+        UNIT_ASSERT(cache.TotalSize() == 1);
+        UNIT_ASSERT(cache.Size() == 1);
+
+        item = cache.Get(1);
+        UNIT_ASSERT(*item == "bb");
+        UNIT_ASSERT(cache.TotalSize() == 3);
+        UNIT_ASSERT(cache.Size() == 2);
+
+        item = cache.Get(2);
+        UNIT_ASSERT(*item == "ccc");
+        UNIT_ASSERT(cache.TotalSize() == 6);
+        UNIT_ASSERT(cache.Size() == 3);
+
+        item = cache.Get(3);
+        UNIT_ASSERT(*item == "dddd");
+        UNIT_ASSERT(cache.TotalSize() == 4);
+        UNIT_ASSERT(cache.Size() == 1);
+
+        item = cache.Get(0);
+        UNIT_ASSERT(*item == "a");
+        UNIT_ASSERT(cache.TotalSize() == 5);
+        UNIT_ASSERT(cache.Size() == 2);
+
+        item = cache.Get(4);
+        UNIT_ASSERT(*item == "eeeee");
+        UNIT_ASSERT(cache.TotalSize() == 6);
+        UNIT_ASSERT(cache.Size() == 2);
+
+        cache.Update(0, MakeAtomicShared<TString>("aaa"));
+        item = cache.Get(0);
+        UNIT_ASSERT(*item == "aaa");
+        UNIT_ASSERT(cache.TotalSize() == 3);
+        UNIT_ASSERT(cache.Size() == 1);
+    }
+}
+
+Y_UNIT_TEST_SUITE(TThreadSafeLFUCacheWithSizeProviderTest) {
+    struct TStringLengthSizeProvider {
+        size_t operator()(const TString& s) const {
+            return s.size();
+        }
+    };
+    using TCache = TThreadSafeLFUCacheWithSizeProvider<size_t, TString, TStringLengthSizeProvider, size_t>;
+
+    TVector<TString> Values = {"a", "bb", "ccc", "dddd", "eeeee"};
+
+    class TCallbacks: public TCache::ICallbacks {
+    public:
+        TKey GetKey(size_t i) const override {
+            return i;
+        }
+        TValue* CreateObject(size_t i) const override {
+            UNIT_ASSERT(i < Values.size());
+            return new TString(Values[i]);
+        }
+    };
+
+    Y_UNIT_TEST(Test) {
+        TCallbacks callbacks;
+        TCache cache(callbacks, 6);
+
+        auto item = cache.Get(0);
+        UNIT_ASSERT(*item == "a");
+        UNIT_ASSERT(cache.TotalSize() == 1);
+        UNIT_ASSERT(cache.Size() == 1);
+
+        item = cache.Get(1);
+        UNIT_ASSERT(*item == "bb");
+        UNIT_ASSERT(cache.TotalSize() == 3);
+        UNIT_ASSERT(cache.Size() == 2);
+
+        item = cache.Get(2);
+        UNIT_ASSERT(*item == "ccc");
+        UNIT_ASSERT(cache.TotalSize() == 6);
+        UNIT_ASSERT(cache.Size() == 3);
+
+        cache.Get(0);
+        cache.Get(0);
+        cache.Get(0);
+
+        cache.Get(1);
+
+        cache.Get(2);
+        cache.Get(2);
+
+        // evict 1. 0 and 3 left
+        item = cache.Get(3);
+        UNIT_ASSERT(*item == "dddd");
+        UNIT_ASSERT(cache.TotalSize() == 5);
+        UNIT_ASSERT(cache.Size() == 2);
+
+        cache.Get(0);
+        UNIT_ASSERT(cache.TotalSize() == 5);
+        UNIT_ASSERT(cache.Size() == 2);
+
+        // evict 3. 0 and 4 left
+        cache.Get(4);
+        UNIT_ASSERT(cache.TotalSize() == 6);
+        UNIT_ASSERT(cache.Size() == 2);
+
+        cache.Get(4);
+        cache.Get(4);
+        cache.Get(4);
+        cache.Get(4);
+        cache.Get(4);
+        // evict both 0 and 4, even if evict only 4 was ok to fit size
+        // thats because 4 used more times, so it is deleted only after 0
+        cache.Get(2);
+        UNIT_ASSERT(cache.TotalSize() == 3);
+        UNIT_ASSERT(cache.Size() == 1);
+    }
+}