1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
|
#ifndef EXPIRING_SET_INL_H_
#error "Direct inclusion of this file is not allowed, include expiring_set.h"
// For the sake of sane code completion.
#include "expiring_set.h"
#endif
#include <array>
namespace NYT {
////////////////////////////////////////////////////////////////////////////////
template <class TItem, class THash, class TEqual>
void TExpiringSet<TItem, THash, TEqual>::SetTTl(TDuration ttl)
{
TTl_ = ttl;
}
template <class TItem, class THash, class TEqual>
void TExpiringSet<TItem, THash, TEqual>::Insert(TInstant now, const TItem& item)
{
std::array<std::reference_wrapper<const TItem>, 1> items{std::cref(item)};
InsertMany(now, items);
}
template <class TItem, class THash, class TEqual>
template <class TItems>
void TExpiringSet<TItem, THash, TEqual>::InsertMany(TInstant now, const TItems& items)
{
Expire(now);
auto deadline = now + TTl_;
for (const auto& item : items) {
ItemToDeadline_[item] = deadline;
}
ExpirationQueue_.push(TItemPack{.Items = {items.begin(), items.end()}, .Deadline = deadline});
}
template <class TItem, class THash, class TEqual>
void TExpiringSet<TItem, THash, TEqual>::Expire(TInstant now)
{
while (!ExpirationQueue_.empty() && ExpirationQueue_.top().Deadline <= now) {
for (const auto& item : ExpirationQueue_.top().Items) {
if (auto it = ItemToDeadline_.find(item); it != ItemToDeadline_.end()) {
if (it->second <= now) {
ItemToDeadline_.erase(it);
}
}
}
ExpirationQueue_.pop();
}
}
template <class TItem, class THash, class TEqual>
void TExpiringSet<TItem, THash, TEqual>::Clear()
{
ItemToDeadline_ = {};
ExpirationQueue_ = {};
}
template <class TItem, class THash, class TEqual>
template <class TItemLike>
bool TExpiringSet<TItem, THash, TEqual>::Contains(const TItemLike& item) const
{
return ItemToDeadline_.contains(item);
}
template <class TItem, class THash, class TEqual>
int TExpiringSet<TItem, THash, TEqual>::GetSize() const
{
return std::ssize(ItemToDeadline_);
}
template <class TItem, class THash, class TEqual>
bool TExpiringSet<TItem, THash, TEqual>::TItemPack::operator<(const TItemPack& other) const
{
// Reversed ordering for the priority queue.
return Deadline > other.Deadline;
}
////////////////////////////////////////////////////////////////////////////////
} // namespace NYT
|
