C++ timer algorithm help needed

[Athena]

I've been banging my head on this for a couple hours now, and I'm just not getting it, so I thought I'd toss it out to the Doper crowd.

I basically need to schedule a bunch of events to happen. I maintain a queue, and things can be added at any point in the queue. For example, the queue might contain:

<something that needs to happen in 3 seconds>
<something that needs to happen in 7 seconds>
<something that needs to happen in 12 seconds>

At any point, things can be added any place in the queue.

I need to create a timer that processes these events. I could just set a new timer everyime something is added to the queue, but I could potentially have many, many timers going at once. I have a vague memory of an alogrithm that did this using only one timer, but I used last about 8 years ago, and I'm really fuzzy. Something tells me that it's very similar to the way Unix schedules events, but once again, I don't recall exactly. It had something to do with when you add something to the queue, you add it relative to the current timer that's going. Does this ring any bells?

[douglips]

How about:
1. Store each event along with the time when it should fire.
2. Calculate the time until the next event needs to fire.
3. Start a timer for that time period.
4. When the timer expires, dispatch all events whose eventtime is in the past.
5. Start over at 2.

You may have to add some niceties such as whenever you add an event verify that it is due after the current timer, or kill the current timer and start over.

Knock yourself out!

[yabob]

Maybe I'm missing something here, but I would just queue them with a time_t item for their absolute schedule time - if you get a interval when you queue them, just call time (&t) and add the interval to it.

Assuming you can then maintain the queue in order of scheduled occurence, or it's short enough to scan or sort, your timer handler does something like:

time(&t);
while (events queued and next on queue <= t)
{
service event;
time(&t);
}
if (queue not empty)
set timer for next on queue - t;

Also, when you queue a new one, if it is now the next on queue, you kill your old timer and set a new shorter one.

[Bobort]

It sounds to me like a priority queue (heap) would be a good way to go. When you insert an item into the heap, calculate the absolute time when it should be processed and store it along with the item. Then look at the top item on the heap and compare the time it should occur with the present time and set a timer accordingly (e.g. on Unix alarm(2) would work pretty well for this). Make sure any previous timers are disabled, since the top of the heap might have changed.

When the timer goes off, grab the item off the top of the heap, set a timer for the next item (what is now the top of the heap), and do whatever needs to be done.

If you're not familiar with priority queues/heaps, have a look here (http://www.onthenet.com.au/~grahamis/int2008/week11/lect11.html).