18
\$\begingroup\$

Note: I have posted a follow-up question for a significantly updated version of this code.

I have implemented a class that provides portable one-shot or periodic timers.

The API provides a way to schedule one or more timer callbacks to fire some number of milliseconds in the future, and optionally fire again every so many milliseconds.

The API returns an ID which can be used later to see if the timer still exists, or destroy it.

The implementation assigns increasing IDs to the timers, starting at one. The timer IDs use a 64-bit unsigned integer, to avoid dealing with wraparound.

The implementation stores the context of each timer Instance in an unordered_map called active, keyed by ID. Each instance has a next member, which is a time_point that indicates when it needs to fire next.

The implementation uses a multiset called queue to sort the timers by the next member, using a functor.

The queue multiset stores reference_wrapper objects that refer directly to the Instance objects. This allows the queue's comparator to refer directly to the instances.

A worker thread is created to service the timer queue. A mutex and condition_variable are used for synchronization. The condition variable is used to notify the worker thread when a timer is created or destroyed, and to request worker thread shutdown.

The worker thread uses wait to wait for notification when there are no timers, and uses wait_for to wait until earliest notification needs to fire, or until awakened.

The lock is released during the callback when a timer fires.

The destructor sets the done flag to true, notifies the condition variable, releases the lock, then joins with the worker to wait for it to exit.

EDIT: I realized that there was a race condition that occurs if a timer is destroyed while its callback is in progress. I solved that by having a running flag on each instance. The worker thread checks it when a callback returns to see if that Instance needs to be destroyed. This avoids dereferencing an Instance that was destroyed while the lock was not held during the callback. The destroy method was also updated to see if the callback is running, and set running to false if so, to indicate to the worker that it needs to be destroyed. If the callback for that timer is not running, destroy destroys the Instance itself.

timer.h

#ifndef TIMER_H
#define TIMER_H

#include <thread>
#include <mutex>
#include <condition_variable>
#include <algorithm>
#include <functional>
#include <chrono>
#include <unordered_map>
#include <set>
#include <cstdint>

class Timer
{
public:
    typedef uint64_t timer_id;
    typedef std::function<void()> handler_type;

private:
    std::mutex sync;
    typedef std::unique_lock<std::mutex> ScopedLock;

    std::condition_variable wakeUp;

private:
    typedef std::chrono::steady_clock Clock;
    typedef std::chrono::time_point<Clock> Timestamp;
    typedef std::chrono::milliseconds Duration;

    struct Instance
    {
        Instance(timer_id id = 0)
            : id(id)
            , running(false)
        {
        }

        template<typename Tfunction>
        Instance(timer_id id, Timestamp next, Duration period, Tfunction&& handler) noexcept
            : id(id)
            , next(next)
            , period(period)
            , handler(std::forward<Tfunction>(handler))
            , running(false)
        {
        }

        Instance(Instance const& r) = delete;

        Instance(Instance&& r) noexcept
            : id(r.id)
            , next(r.next)
            , period(r.period)
            , handler(std::move(r.handler))
            , running(r.running)
        {
        }

        Instance& operator=(Instance const& r) = delete;

        Instance& operator=(Instance&& r)
        {
            if (this != &r)
            {
                id = r.id;
                next = r.next;
                period = r.period;
                handler = std::move(r.handler);
                running = r.running;
            }
            return *this;
        }

        timer_id id;
        Timestamp next;
        Duration period;
        handler_type handler;
        bool running;
    };

    typedef std::unordered_map<timer_id, Instance> InstanceMap;
    timer_id nextId;
    InstanceMap active;

    // Comparison functor to sort the timer "queue" by Instance::next
    struct NextActiveComparator
    {
        bool operator()(const Instance &a, const Instance &b) const
        {
            return a.next < b.next;
        }
    };
    NextActiveComparator comparator;

    // Queue is a set of references to Instance objects, sorted by next
    typedef std::reference_wrapper<Instance> QueueValue;
    typedef std::multiset<QueueValue, NextActiveComparator> Queue;
    Queue queue;

    // Thread and exit flag
    std::thread worker;
    bool done;
    void threadStart();

public:
    Timer();
    ~Timer();

    timer_id create(uint64_t when, uint64_t period, const handler_type& handler);
    timer_id create(uint64_t when, uint64_t period, handler_type&& handler);

private:
    timer_id createImpl(Instance&& item);

public:
    bool destroy(timer_id id);

    bool exists(timer_id id);
};

#endif // TIMER_H

timer.cpp

#include "timer.h"

void Timer::threadStart()
{
    ScopedLock lock(sync);

    while (!done)
    {
        if (queue.empty())
        {
            // Wait (forever) for work
            wakeUp.wait(lock);
        }
        else
        {
            auto firstInstance = queue.begin();
            Instance& instance = *firstInstance;
            auto now = Clock::now();
            if (now >= instance.next)
            {
                queue.erase(firstInstance);

                // Mark it as running to handle racing destroy
                instance.running = true;

                // Call the handler
                lock.unlock();
                instance.handler();
                lock.lock();

                if (done)
                {
                    break;
                }
                else if (!instance.running)
                {
                    // Running was set to false, destroy was called
                    // for this Instance while the callback was in progress
                    // (this thread was not holding the lock during the callback)
                    active.erase(instance.id);
                }
                else
                {
                    instance.running = false;

                    // If it is periodic, schedule a new one
                    if (instance.period.count() > 0)
                    {
                        instance.next = instance.next + instance.period;
                        queue.insert(instance);
                    } else {
                        active.erase(instance.id);
                    }
                }
            } else {
                // Wait until the timer is ready or a timer creation notifies
                wakeUp.wait_until(lock, instance.next);
            }
        }
    }
}

Timer::Timer()
    : nextId(1)
    , queue(comparator)
    , done(false)
{
    ScopedLock lock(sync);
    worker = std::thread(std::bind(&Timer::threadStart, this));
}

Timer::~Timer()
{
    ScopedLock lock(sync);
    done = true;
    wakeUp.notify_all();
    lock.unlock();
    worker.join();
}

Timer::timer_id Timer::create(uint64_t msFromNow, uint64_t msPeriod,
        const std::function<void()> &handler)
{
    return createImpl(Instance(0,
            Clock::now() + Duration(msFromNow), Duration(msPeriod),
            handler));
}

Timer::timer_id Timer::create(uint64_t msFromNow, uint64_t msPeriod,
        std::function<void()>&& handler)
{
    return createImpl(Instance(0,
            Clock::now() + Duration(msFromNow), Duration(msPeriod),
            std::move(handler)));
}

Timer::timer_id Timer::createImpl(Instance&& item)
{
    ScopedLock lock(sync);
    item.id = nextId++;
    auto iter = active.emplace(item.id, std::move(item));
    queue.insert(iter.first->second);
    wakeUp.notify_all();
    return item.id;
}

bool Timer::destroy(timer_id id)
{
    ScopedLock lock(sync);
    auto i = active.find(id);
    if (i == active.end())
        return false;
    else if (i->second.running)
    {
        // A callback is in progress for this Instance,
        // so flag it for deletion in the worker
        i->second.running = false;
    }
    else
    {
        queue.erase(std::ref(i->second));
        active.erase(i);
    }

    wakeUp.notify_all();
    return true;
}

bool Timer::exists(timer_id id)
{
    ScopedLock lock(sync);
    return active.find(id) != active.end();
}

Example:

#include "timer.h"
int main()
{
    Timer t;
    // Timer fires once, one second from now
    t.create(1000, 0,
             []() {
                 std::cout << "Non-periodic timer fired" << std::endl;
             });
    // Timer fires every second, starting five seconds from now
    t.create(5000, 1000,
             []() {
                 std::cout << "Timer fired 0" << std::endl;
             });
    // Timer fires every second, starting now
    t.create(0, 1000,
             []() {
                 std::cout << "Timer fired 1" << std::endl;
             });
    // Timer fires every 100ms, starting now
    t.create(0, 100,
             []() {
                 std::cout << "Timer fired 2" << std::endl;
             });
}

The third parameter is a std::function, so it could call a method on some instance of an object, like this:

class Foo
{
public:
    void bar() { std::cout << "Foo::bar called" << std::endl; }
};

int something()
{
    Foo example;

    // Assume "t" is a Timer
    auto tid = t.create(0, 100, std::bind(&Foo::bar, &example));
    // ... do stuff ...

The exists method is intended for scenarios where you desperately need to wait for a timer to go away before something goes out of scope. Definitely not pretty but I don't expect this scenario to occur a lot in my intended use cases:

    // Not pretty, but better than nothing:
    t.destroy(tid);
    while (t.exists(tid))
        std::this_thread::sleep_for(std::chrono::milliseconds(100));
}
\$\endgroup\$
  • \$\begingroup\$ Apologies for rolling back your last edit, but it's this site's policy to not edit the original code in a way that would invalidate the previous/existing answers. \$\endgroup\$ – ChrisW Jan 30 '14 at 21:27
  • \$\begingroup\$ @ChrisW No problem. What should I do if/when I implement suggested changes? I couldn't find anything specific in the Help Center. \$\endgroup\$ – doug65536 Jan 30 '14 at 21:37
  • \$\begingroup\$ You don't necessarily need to edit your improvements into the question: readers of the site will expect to see the code that was reviewed, not necessarily the post-review version of the code. If you want to present the finished post-review version, that's nice of you too (readers can then see how much you were able to improve it, how much difference the reviews made). If you want to do that, then the way is to append the changed code to the end of your question, perhaps separated with a horizontal line ( using --- in the markdown), ... \$\endgroup\$ – ChrisW Jan 30 '14 at 22:08
  • \$\begingroup\$ @ChrisW Will do. Thanks for answering what is probably a common question. \$\endgroup\$ – doug65536 Jan 30 '14 at 22:10
  • \$\begingroup\$ ... for example as on this question. If you do that (edit your question) you shouldn't generally expect to see new reviews of your edits: people often review new questions and don't notice edits to existing questions. If you want a review of edits which you make after the original question has been answered, you may post that as a new question: see How to deal with follow-up questions? for a description of how to do that. \$\endgroup\$ – ChrisW Jan 30 '14 at 22:11
6
\$\begingroup\$

I like your syntax, for example C++11 style such as std::reference_wrapper.

I like your algorithm, for example:

  • Sort the queue so that you only need to check the first one
  • Unlock before doing the timer callback (and re-lock afterwards)

Minor things about the style that made it harder to read:

  • Two private sections in Timer, containing a mix of type definitions and field definitions
  • Fields (instance data) defined at the top of the Timer class but at the end of the Instance class
  • Inline code in timer.h (users of the class might find it easier if lines of code were hidden away in timer.cpp).

The exists method is strange: what do you think users will use it for? It might return true but then have the timer go off immediately, i.e. it may return stale information.

I don't understand the use case for std::function<void()>&& handler and std::move(handler). It's probably cleverer than I am, maybe a comment or an example test case which uses it would help me.

\$\endgroup\$
  • 1
    \$\begingroup\$ It works because the mutex (sync) is released when it is waiting for the condition variable (wakeUp). wakeUp.wait and wakeUp.wait_until both release the lock before waiting. That's why you have to pass the lock as an argument to them. \$\endgroup\$ – doug65536 Jan 30 '14 at 20:32
  • \$\begingroup\$ I didn't feel comfortable mixing the private and public sections to be honest. I sorted that stuff roughly by purpose: first the public types, then the synchronization stuff, then the timing stuff, then the timer instance stuff, then the thing that sorts the queue, then the queue, then the thread related stuff, then the public API. I felt it would be easier to read if the related things were close together, instead of scattered across the class declaration. \$\endgroup\$ – doug65536 Jan 30 '14 at 20:37
  • 2
    \$\begingroup\$ @doug65536 I like to declare data at the top when I'm designing/coding the class; but for users/readers of the class, a harmless convention is to define the public API methods at the top (as you did for the Instance struct): see suggested style for declaration order. Otherwise I need to read a lot of implementation details before I find the public API. I also found it confusing to see Timer data members declared both above and delow the definition of the Instance struct. \$\endgroup\$ – ChrisW Jan 30 '14 at 20:47
  • \$\begingroup\$ I added examples. The purpose of having a const reference and rvalue reference version of create, was to enable move semantics, which could be very useful if you pass a lambda that has by-value captures of something that can't be copied, and improves efficiency when a lambda captures by value values that can be moved. \$\endgroup\$ – doug65536 Jan 30 '14 at 20:57
  • 1
    \$\begingroup\$ I implemented your suggestion of moving the public API to the top. Now it is a public section at the top, and the rest is all private. Way better. \$\endgroup\$ – doug65536 Jan 30 '14 at 21:03
4
\$\begingroup\$

I think I'm being confused by your type names. So each timer is actually called Timer::Instance and Timer is something else? Hmm.

In terms of English I can certainly see why "Timer" as a name for the whole timing system might make sense, even if it's atypical in the software world.

At the very least I'd suggest renaming Timer::Instance to Timer::Event.
Or, rename Timer to TimerManager or some other Javay abomination.

\$\endgroup\$
  • \$\begingroup\$ I agree, Timer is too vague and implies that it is singular. Instance is probably too vague too. \$\endgroup\$ – doug65536 Jan 30 '14 at 16:44
  • \$\begingroup\$ Worse, "instance" conflicts with the C++ meaning of the term. \$\endgroup\$ – Lightness Races in Orbit Jan 30 '14 at 16:47
  • 1
    \$\begingroup\$ Instance is a private implementation detail of the class, therefore harmless. Each timer is actually of type Timer, but each Timer can handle multiple timing tasks, which are each publicly identified by a timer_id. \$\endgroup\$ – ChrisW Jan 30 '14 at 19:04
  • \$\begingroup\$ @ChrisW: It's not harmless when you have to read the code and come to understand it. Something being an internal implementation detail is not an excuse to give it a confusing and inappropriate name. \$\endgroup\$ – Lightness Races in Orbit Jan 30 '14 at 19:27
  • \$\begingroup\$ I implemented the rename to TimerManager. \$\endgroup\$ – doug65536 Jan 30 '14 at 21:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.