16 #include <seastar/core/bitset-iter.hh>
17 #ifndef SEASTAR_MODULE
18 #include <boost/intrusive/list.hpp>
39 template<
typename Timer, boost::
intrusive::list_member_hook<> Timer::*link>
42 using time_point =
typename Timer::time_point;
43 using timer_list_t = boost::intrusive::list<Timer, boost::intrusive::member_hook<Timer, boost::intrusive::list_member_hook<>, link>>;
45 using duration =
typename Timer::duration;
46 using timestamp_t =
typename Timer::duration::rep;
48 static constexpr timestamp_t max_timestamp = std::numeric_limits<timestamp_t>::max();
49 static constexpr
int timestamp_bits = std::numeric_limits<timestamp_t>::digits;
52 static constexpr
int n_buckets = timestamp_bits + 1;
54 std::array<timer_list_t, n_buckets> _buckets;
58 std::bitset<n_buckets> _non_empty_buckets;
60 static timestamp_t get_timestamp(time_point _time_point) noexcept
62 return _time_point.time_since_epoch().count();
65 static timestamp_t get_timestamp(Timer&
timer) noexcept
70 int get_index(timestamp_t timestamp)
const noexcept
72 if (timestamp <= _last) {
76 auto index = bitsets::count_leading_zeros(timestamp ^ _last);
77 assert(index < n_buckets - 1);
81 int get_index(Timer&
timer)
const noexcept
83 return get_index(get_timestamp(
timer));
86 int get_last_non_empty_bucket()
const noexcept
88 return bitsets::get_last_set(_non_empty_buckets);
93 , _next(max_timestamp)
94 , _non_empty_buckets(0)
99 for (
auto&& list : _buckets) {
100 while (!list.empty()) {
101 auto&
timer = *list.begin();
126 auto timestamp = get_timestamp(
timer);
127 auto index = get_index(timestamp);
129 _buckets[index].push_back(
timer);
130 _non_empty_buckets[index] =
true;
132 if (timestamp < _next) {
152 auto index = get_index(
timer);
153 auto& list = _buckets[index];
154 list.erase(list.iterator_to(
timer));
156 _non_empty_buckets[index] =
false;
174 timer_list_t
expire(time_point now) noexcept
177 auto timestamp = get_timestamp(now);
179 if (timestamp < _last) {
183 auto index = get_index(timestamp);
185 for (
int i : bitsets::for_each_set(_non_empty_buckets, index + 1)) {
186 exp.splice(exp.end(), _buckets[i]);
187 _non_empty_buckets[i] =
false;
191 _next = max_timestamp;
193 auto& list = _buckets[index];
194 while (!list.empty()) {
195 auto&
timer = *list.begin();
198 exp.push_back(
timer);
204 _non_empty_buckets[index] = !list.empty();
206 if (_next == max_timestamp && _non_empty_buckets.any()) {
207 for (
auto&
timer : _buckets[get_last_non_empty_bucket()]) {
208 _next = std::min(_next, get_timestamp(
timer));
222 return time_point(duration(std::max(_last, _next)));
230 for (
int i : bitsets::for_each_set(_non_empty_buckets)) {
235 size_t size() const noexcept
238 for (
int i : bitsets::for_each_set(_non_empty_buckets)) {
239 res += _buckets[i].size();
249 return _non_empty_buckets.none();
252 time_point now() noexcept {
Definition: timer-set.hh:40
bool insert(Timer &timer) noexcept
Definition: timer-set.hh:124
void clear() noexcept
Definition: timer-set.hh:228
time_point get_next_timeout() const noexcept
Definition: timer-set.hh:220
timer_list_t expire(time_point now) noexcept
Definition: timer-set.hh:174
void remove(Timer &timer) noexcept
Definition: timer-set.hh:150
bool empty() const noexcept
Definition: timer-set.hh:247
time_point get_timeout() const noexcept
Definition: timer.hh:218
future now()
Returns a ready future.
Definition: later.hh:35
Seastar API namespace.
Definition: abort_on_ebadf.hh:26