Extract TExpiringSet to library/cpp/containers

commit_hash:dd1c08771b1d4865d03a492927afa0f9895a5f44

1 files changed, 54 insertions, 0 deletions

diff --git a/library/cpp/yt/containers/expiring_set.h b/library/cpp/yt/containers/expiring_set.h
new file mode 100644
index 0000000000..f8a1e33630
--- /dev/null
+++ b/library/cpp/yt/containers/expiring_set.h
@@ -0,0 +1,54 @@
+#pragma once
+
+#include <util/generic/hash.h>
+
+#include <util/datetime/base.h>
+
+#include <queue>
+
+namespace NYT {
+
+////////////////////////////////////////////////////////////////////////////////
+
+//! Maintains a set of items that expire after a certain time.
+template <class TItem, class THash = THash<TItem>, class TEqual = TEqualTo<TItem>>
+class TExpiringSet
+{
+public:
+    void SetTTl(TDuration ttl);
+
+    void Insert(TInstant now, const TItem& item);
+    template <class TItems>
+    void InsertMany(TInstant now, const TItems& items);
+
+    void Expire(TInstant now);
+
+    void Clear();
+
+    template <class TItemLike>
+    bool Contains(const TItemLike& item) const;
+
+    int GetSize() const;
+
+private:
+    TDuration TTl_;
+
+    struct TItemPack
+    {
+        std::vector<TItem> Items;
+        TInstant Deadline;
+
+        bool operator<(const TItemPack& other) const;
+    };
+
+    THashMap<TItem, TInstant, THash, TEqual> ItemToDeadline_;
+    std::priority_queue<TItemPack> ExpirationQueue_;
+};
+
+////////////////////////////////////////////////////////////////////////////////
+
+} // namespace NYT
+
+#define EXPIRING_SET_INL_H_
+#include "expiring_set-inl.h"
+#undef EXPIRING_SET_INL_H_