faux-folly/folly/futures/detail/TimerMap.h

/*
 * Copyright 2015 Nest Labs, Inc. All Rights Reserved.
 *
 * 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 <functional>
#include <map>
#include <chrono>
#include <algorithm>

namespace folly { namespace detail {

/* A replacement for folly::HHWheelTimer (folly/io/async library) that
 * provides O(logN) insertion. This is not a drop-in replacement for
 * HHWHeelTimer, but is something that
 * folly::detail::ThreadWheelTimekeeper can use for its
 * implementation. Used to break the dependency on
 * folly/io/async. Their hashed and heirarchical timing wheel is
 * probably superior... and we should probably write our own.  See:
 * http://www.cs.columbia.edu/~nahum/w6998/papers/sosp87-timing-wheels.pdf
 */
class TimerMap
{
public:
    using clock_type = std::chrono::steady_clock;
    using time_point_type = clock_type::time_point;
    using duration_type = clock_type::duration;
    using callback_type = std::function<void()>;
    using multimap_type = std::multimap<time_point_type, callback_type>;
    using data_type = std::pair<time_point_type, callback_type>;

    TimerMap(duration_type tick);

    /* Non-copyable */
    TimerMap(const TimerMap& o) = delete;
    TimerMap& operator=(const TimerMap&o) = delete;
    TimerMap(TimerMap&& o) = delete;
    TimerMap& operator=(TimerMap&& o) = delete;

    /**
     * Get the "tick" size for the map.
     *
     * @return when calling nextTimeout(), the return values will be
     * at least this much time apart.
     */
    duration_type getTick() const {
        return tick_;
    }

    /**
     * Returns true if there are no events stored in database
     */
    bool empty() const {
        return db_.empty();
    }

    void scheduleTimeout(duration_type timeout, callback_type cb);
    void scheduleAlarm(time_point_type at, callback_type cb);
    time_point_type nextTimeout() const;
    void invokeTimers();
    template <typename Iterator>
    static void invokeTimers(Iterator beg, Iterator end);
    template <typename InsertIterator>
    void popExpiredTimers(InsertIterator it);
    template <typename InsertIterator>
    void popExpiredTimers(InsertIterator it, time_point_type t);

private:
    duration_type tick_;            //< Minimum time between next_tick_ values
    time_point_type next_tick_;     //< The next time invokeTimers() should be called
    multimap_type db_;              //< Internal database of timepoints and callbacks
};

/**
 * Invoke all timers between iterators beg and end.
 *
 * THIS IS A STATIC FUNCTION
 *
 * Given an iterator pair, invoke all the callbacks/closures between
 * them. The closures will be moved into the function and thus deleted
 * after each execution.
 *
 * The Iterator (it) type must support the following expressions:
 *
 *    1. ++it
 *    2. it != end
 *    3. std::move(it->second) // extract the closure
 *
 * The expectation is that the iterators are pointing to a
 * pair<Unspecified, callback_type>.
 *
 * @param beg iterator pointing to the first closure to execute.
 *
 * @param end iterator pointing to one-past-the-last closure to
 * execute.
 */
template <typename Iterator>
void TimerMap::invokeTimers(Iterator beg, Iterator end)
{
    Iterator cur;
    for (cur = beg ; cur != end ; ++cur) {
        /* destroy each closure after executing callback */
        callback_type tmp = std::move(cur->second);
        tmp();
    }
}

/**
 * Remove expired iterators from TimerMap, putting them in the provided iterator.
 *
 * This is a convenience function for popExpiredTimers(it, clock_type::now()).
 * See documentation for that function.
 *
 * @param it insertion iterator to place events.
 */
template <typename InsertIterator>
void TimerMap::popExpiredTimers(InsertIterator it) {
    auto t = clock_type::now();
    popExpiredTimers(it, t);
}

/**
 * Remove expired iterators from TimerMap, putting them in the provided iterator.
 *
 * Since it's not possible to query how many elements will be inserted
 * <em>a priori</em>, it is expected that you will provide an
 * <em>insertion iterator</em>, like.
 * std::insert_iterator<std::pair<time_point_type,
 * callback_type>>. The iterator (it) must support the following
 * expressions:
 *
 *    1. ++it
 *    2. (*it) = std::pair<time_point_type, callback_type>(...);
 *
 * @param it iterator pointing to the first place where the values
 * should be written.
 *
 * @param t extract all timers/callbacks/closures that expired before
 * or at this absolute time.
 */

template <typename ForwardInputIterator>
void TimerMap::popExpiredTimers(ForwardInputIterator it, time_point_type t) {
    multimap_type::iterator beg = db_.begin();
    multimap_type::iterator end = db_.upper_bound(t);

    // std::move() doesn't work because multimap_type::value_type
    // uses 'const Key' in the pair.
    for (auto cur = beg ; cur != end ; ++cur, ++it) {
        (*it) = std::make_pair(cur->first, std::move(cur->second));
    }

    db_.erase(beg, end);
    next_tick_ = t + tick_;
}

} // namespace detail
} // namespace folly