CODEWITHSUNDEEP
c++cdata-structurestimerimplementation
vindyz
vindyz

Reputation: 1101

API for calling function in periodic time intervals

Had an interesting question in a recent interview, here it goes.

Need to implement a function, which will accept a function pointer and a time interval. And it should enable func1 to be called every time_interval.

We are provided with an API which will be called for every clock tick. there can be multiple calls to create_timer, in that case it should call each of the function pointer as per their respective time interval.

    // api    
    create_timer(&func, interval) 

    // call to api would look like
    create_timer(&func1, 10);
    create_timer(&func2, 5);

I suggested creating a linked list of function pointers, but in that case, it's linear search for every clock tick. That's not a good solution.

I suggested a priority queue solution also, but that did not work out as well. We need to store the time create_timer is called for every function, & then calculate the difference with current time, & then if that difference is multiple of time_interval, we call the function.

Any interesting solutions ?

Upvotes: 2

Views: 883

Answers (2)

LihO
LihO

Reputation: 42085

"I suggested creating a linked list of function pointers"

Note that this kind of implementation would have to iterate through all planned events over and over again upon each new tick, just to find out whether some function should be called or not.

A better approach would be using a sorted data structure with well defined order, let's say a priority queue, in which all events would be sorted in order, in which they should be handled / executed. I.e.:

create_timer(&func1, 10);
create_timer(&func2, 5);
create_timer(&func3, 15);

might result in a following priority queue:

5   func1
10  func2
15  func3

by the time the timer would reach 5th tick, it would call func1 and remove it from the queue, then it would insert it back to this queue with updated value "last val + 5":

10  func2
10  func1
15  func3

and so on.

Upvotes: 1

malaugh
malaugh

Reputation: 157

That's a pretty good answer. To avoid decrementing every timer in the link list on every tick, you can search for the timer that will expire first, and note its time to expire. Then decrement that timer every tick, and when it expires, decrement the rest of the timers by the stored time to expire, while finding the next timer that will expire, then repeat the process. That way you only traverse the link list after a timer expires

Upvotes: 0

Related Questions