Implement register_callback API with given timeout in a library

Question

I have to implement below API in a library:

register_callback(callback_func, timeout);

In this API implementation, callback_func is supposed to be called after given timeout value.

Application is going to call this library API multiple times for different callback,

application()
{
    register_callback(fun1, 5);
    register_callback(fun2, 10);
    register_callback(fun3, 15);
}

so, my question is, which data structure should I use to implement this API in library?

I can think of tree (C++ STL map) data structure which will store sorted list of mapping of timeout with func_name (timeout is key and map sorted based on timeout) And timeout will be stored as current_time() + timeout. For every x time interval, one worker thread can keep checking current_time() with first entry in map and if it matches then library will call the callback function and remove the entry from map.

Problem with this approach is, if timeout is in millisecond, then my worker thread will keep checking map for every millisecond.

So, is there any other data structure that I can use here more efficiently?

Answer 1

The standard data structure for simultaneously running alarms/timers, or more generally whenever you need to do n things at various specific points in the future, is a priority queue. You insert the items, keyed on the time when they need to be handled, and the one which needs to be handled soonest is at the front of the queue. Then you just sleep until the time comes to handle that one; there's no need to check at regular intervals. If one thread is handling the timeouts and another thread is adding it, the second thread may need to artificially wake the first thread when a new timer is added which ends up at the front of the queue.

Any dynamic sorted set can be used as a priority queue, but heap structures (like binomial heaps) are more asymptotically efficient.