/* Create a Timer Task that takes in the running time and it's associated
function to be called after its running time is elapsed */
#include <time.h>
#define NUM 5
typedef void (*funcToBeCalled)(void);
typedef struct timer TIMER;
struct timer
{
int runningTime;
funcToBeCalled func;
};
static TIMER timerArray[NUM];
static time_t reference;
static int count;
int LEFT(int index)
{
if(index < NUM)
return (index * 2 + 1);
}
int RIGHT(int index)
{
if(index < NUM)
return (index * 2 + 2);
}
static void print(void)
{
printf("Timer task has been called\n");
}
// Initialise the timer data structure
void Init()
{
int index;
count = NUM;
// Note down the reference time
reference = time(0);
printf("reference : %ld\n", reference);
// Initialise the data structure such that associate function gets
// called after 3, 6, 9, 12, 15 seconds respectively.
for(index = 0; index < count; index++)
{
timerArray[index].runningTime = (index + 1) * 3;
timerArray[index].func = print;
}
}
// This function check the min heap property and arrange
// the element such that at every node, root node should be
// less than its right and left child element.
Heapify(int index)
{
int left, right, minIndex;
TIMER temp;
left = LEFT(index);
right = RIGHT(index);
if(left < (count) &&
(timerArray[left].runningTime < timerArray[index].runningTime))
{
minIndex = left;
}
else
{
minIndex = index;
}
if(right < (count) &&
(timerArray[right].runningTime < timerArray[minIndex].runningTime))
{
minIndex = right;
}
if(minIndex != index)
{
temp.runningTime = timerArray[index].runningTime;
temp.func = timerArray[index].func;
timerArray[index].runningTime = timerArray[minIndex].runningTime;
timerArray[index].func = timerArray[minIndex].func;
timerArray[minIndex].runningTime = temp.runningTime;
timerArray[minIndex].func = temp.func;
Heapify(minIndex);
}
}
// This function builds the MIN heap data structure
void BuildHeap()
{
int len, i;
len = sizeof(timerArray)/sizeof(timerArray[0]);
i = (len - 1)/2;
while(i >= 0)
{
Heapify(i);
i--;
}
Heapify(0);
}
// This function extract the top element of the heap
// Min heap has the min element at the top always.
int HeapExtract()
{
TIMER temp;
// Swap the 0 the element with last element of the array
temp.runningTime = timerArray[0].runningTime;
temp.func = timerArray[0].func;
timerArray[0].runningTime = timerArray[count-1].runningTime;
timerArray[0].func = timerArray[count-1].func;
timerArray[count-1].runningTime = temp.runningTime;
timerArray[count-1].func = temp.func;
count--;
// Check the heap property heapify if it got violated
Heapify(0);
// return the minimum element of the heap
return (count);
}
void scheduler()
{
time_t now;
int diff_time, minIndex;
while(count >= 0)
{
now = time(0);
printf("Current Time: %ld\n", time(0));
diff_time = now- reference;
printf("diff_time : %ld\n", diff_time);
if(diff_time >= timerArray[0].runningTime)
{
minIndex = HeapExtract();
timerArray[minIndex].func();
}
else
{
sleep(timerArray[0].runningTime - diff_time);
}
}
}
main()
{
int index, minIndex;
TIMER temp;
// Initialise the data structure
Init();
// Build MIn heap data structure
BuildHeap(timerArray);
// Run the scheduler
scheduler();
return;
}
The ouput of above code is
Timer Task is about to run
reference : 1312510772
Current Time: 1312510775
diff_time : 3
Timer task has been called
Current Time: 1312510778
diff_time : 6
Timer task has been called
Current Time: 1312510781
diff_time : 9
Timer task has been called
Current Time: 1312510784
diff_time : 12
Timer task has been called
Current Time: 1312510787
diff_time : 15
Timer task has been called
Please share your comments
On Thu, Aug 4, 2011 at 11:43 AM, Anand Shastri <[email protected]>wrote:
> Obviously you need to run the task that a closet running time.
>
> For Example
>
> Task 1 : running time = 2 secs
>
> Task 2: running time = 4 secs
>
> This means I want to run the task 1 after 2 secs and task 2 after 4 second.
>
> How I hope the question is clear to you know
>
> On Thu, Aug 4, 2011 at 11:37 AM, mohit verma <[email protected]>wrote:
>
>> there is nothing like "search min or max time and then call function"
>> given . It can be the case: "call the functions in order of nodes or times
>> saved in objects". M i wrong?
>>
>>
>> On Thu, Aug 4, 2011 at 11:56 PM, Anand Shastri <[email protected]
>> > wrote:
>>
>>> You mean to say linked to maintain all time task with its corresponding
>>> running time and associate function. In that case how will find the task
>>> which has the closed running time.
>>>
>>> If you use min heap it would be easy to find the task that has closest
>>> runing time in O(1) complexity.
>>>
>>> On Thu, Aug 4, 2011 at 10:57 AM, mohit verma <[email protected]>wrote:
>>>
>>>> why are u maintaining heap? can't we use link list here?
>>>>
>>>> On Thu, Aug 4, 2011 at 11:16 PM, Anand Shastri <
>>>> [email protected]> wrote:
>>>>
>>>>> *You have given a structure which has two member, One which stores
>>>>> the
>>>>> time and other stores the function pointer Your function has to call
>>>>> the *
>>>>> *function stored in the fuction poitner after the time given in the
>>>>> structure elapses.
>>>>> Design that function? *
>>>>>
>>>>> Approach: To design this function I would use a min Heap data
>>>>> structure. Each node of a heap has
>>>>> two parameters one is the running time and other one is
>>>>> the function pointer.
>>>>>
>>>>> // Initialise a function pointer
>>>>> typedef void (*functionToBeCalled)(int arg1, int arg2);
>>>>>
>>>>> // Timer structure
>>>>> typedef struct timer
>>>>> {
>>>>> float runingTime; // in terms of seconds
>>>>> functionToBeCalled funcToBeCall; // function pointer
>>>>> }TIMER;
>>>>>
>>>>> void initTimer()
>>>>> {
>>>>> Initialise few nodes with running time and its corresponding
>>>>> function
>>>>> Initialise a MIN heap data structure
>>>>> }
>>>>>
>>>>> void addTimer(uint32 runingTime, functionToBeCalled func)
>>>>> {
>>>>> TIMER *temp;
>>>>> temp = (TIMER *)malloc(sizeof(TIMER));
>>>>> temp->runingTime = runningTime
>>>>> temp->funcToBeCall = func;
>>>>> HeapAdd(temp);
>>>>> Heapify();
>>>>> }
>>>>>
>>>>> void scheduler()
>>>>> {
>>>>> uint32 currentTime = ObtainCurrentTime();
>>>>> // Obtain the runing time of top most element of the min
>>>>> Heap
>>>>> uint32 runingTime = PeakHeap();
>>>>> // if the runningTime is equal to current time then extract
>>>>> the top most
>>>>> // element of the heap and execute the function associate
>>>>> with it
>>>>> // Heapify the MIN heap data structure
>>>>> // Obtain the runing time of top most element of the min
>>>>> heap
>>>>> // scheduler sleep for that much amount of time.
>>>>> if(runingTime == currentTime)
>>>>> {
>>>>> TIMER * node = ExtractMinHeap();
>>>>> CreateThread(node->func, Thread);
>>>>> Heapify();
>>>>> runingTime = PeakHeap();
>>>>> sleep(runningTime);
>>>>> }
>>>>> else
>>>>> {
>>>>> // scheduler updates its sleep time
>>>>> // if runing time is not equal to current time
>>>>> sleep(runningTime);
>>>>> }
>>>>>
>>>>> }
>>>>>
>>>>> Let me know your comments
>>>>>
>>>>> --
>>>>> You received this message because you are subscribed to the Google
>>>>> Groups "Algorithm Geeks" group.
>>>>> To post to this group, send email to [email protected].
>>>>> To unsubscribe from this group, send email to
>>>>> [email protected].
>>>>> For more options, visit this group at
>>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>>
>>>>
>>>>
>>>>
>>>> --
>>>> ........................
>>>> *MOHIT VERMA*
>>>>
>>>> --
>>>> You received this message because you are subscribed to the Google
>>>> Groups "Algorithm Geeks" group.
>>>> To post to this group, send email to [email protected].
>>>> To unsubscribe from this group, send email to
>>>> [email protected].
>>>> For more options, visit this group at
>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to [email protected].
>>> To unsubscribe from this group, send email to
>>> [email protected].
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>>
>>
>> --
>> ........................
>> *MOHIT VERMA*
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to [email protected].
>> To unsubscribe from this group, send email to
>> [email protected].
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
