folly/folly/io/async/HHWheelTimer.h

/*
 * Copyright (c) Meta Platforms, Inc. and affiliates.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#pragma once

#include <array>
#include <chrono>
#include <cstddef>
#include <memory>

#include <boost/intrusive/list.hpp>
#include <glog/logging.h>

#include <folly/ExceptionString.h>
#include <folly/Optional.h>
#include <folly/io/async/AsyncTimeout.h>
#include <folly/io/async/DelayedDestruction.h>
#include <folly/io/async/HHWheelTimer-fwd.h>
#include <folly/portability/Config.h>

namespace folly {

namespace detail {
template <class Duration>
struct HHWheelTimerDurationConst;

template <class Duration>
class HHWheelTimerDurationInterval { … };

template <>
struct HHWheelTimerDurationConst<std::chrono::milliseconds> { … };

template <>
struct HHWheelTimerDurationConst<std::chrono::microseconds> { … };
} // namespace detail

/**
 * Hashed Hierarchical Wheel Timer
 *
 * We model timers as the number of ticks until the next
 * due event.  We allow 32-bits of space to track this
 * due interval, and break that into 4 regions of 8 bits.
 * Each region indexes into a bucket of 256 lists.
 *
 * Bucket 0 represents those events that are due the soonest.
 * Each tick causes us to look at the next list in a bucket.
 * The 0th list in a bucket is special; it means that it is time to
 * flush the timers from the next higher bucket and schedule them
 * into a different bucket.
 *
 * This technique results in a very cheap mechanism for
 * maintaining time and timers.
 *
 * Unlike the original timer wheel paper, this implementation does
 * *not* tick constantly, and instead calculates the exact next wakeup
 * time.
 */
template <class Duration>
class HHWheelTimerBase : private folly::AsyncTimeout,
                         public folly::DelayedDestruction { … };

// std::chrono::milliseconds
HHWheelTimer;
extern template class HHWheelTimerBase<std::chrono::milliseconds>;

// std::chrono::microseconds
template <>
void HHWheelTimerBase<std::chrono::microseconds>::scheduleTimeoutInternal(
    std::chrono::microseconds timeout);

HHWheelTimerHighRes;
extern template class HHWheelTimerBase<std::chrono::microseconds>;

} // namespace folly