A priority based timer using priority queue

Question

I am trying to implement a priority-based timer where certain events are fired out based on their expiry and the priority.

So if there are 3 timers with the following expiry time and priorities

Timers	Expiry Time (s)	Priorities
T1	5	1
T2	5	10
T3	10	1

The order of timers triggering should be T2, T1, T3.

Initially, I thought of creating POSIX timer for each event but priority wouldn't be respected, so then I came up with a priority queue approach where each item is stored in the order of their expiry time and priority. Also creating a timer for each event probably sounds like an overkill.

So in the above example, it would be T2 -> T1 -> T3.

Implementation:

• Each node in the list contains the refTime which basically stores the expiry time with an offset to the time recorded at the start of the application (refTime = expiryTime + startTime) so every node is timed is referenced.

• MONOTONIC timer is used to avoid relying on the changes into system clock be it leap year, or day light savings. The idea is make sure the time elapsed from the initial time to current time remains positive and mostly accurate, since that's what would be needed for triggering the timer.

• There would be one main thread that constantly checks if the current time exceeds the time stored in the node and once that's true, it indicates the timer needs to trigger so it would delete the node, and append the same timer in the priority queue with an updated time i.e current time + expiry time

list.h

#include "string.h"
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
typedef struct node
{
 struct node *head;
 char *name;
 int priority;
 unsigned int expiry;
 unsigned int refTime;
 struct node *nxt;
} Node;
void push(Node **node, char *name, int expiry, int priority);
void popAndPush(Node **node);
Node *CreateNode(char *name, unsigned int expiry, int priority);
void print(Node *node);

list.c

#include "list.h"
extern struct timespec startTime;
struct timespec endTime;
// print the list
void print(Node *node)
{
 for (; node != NULL; node = node->nxt)
 {
 printf ("%d (%s,%d,%u) -> ", node->refTime, node->name, node->priority, node->expiry);
 }
 printf ("\n=============================================\n\n");
}
Node *CreateNode(char *name, unsigned int expiry, int priority)
{
 Node *node = malloc(sizeof(*node) + strlen(name) + 1);
 node->name = name;
 clock_gettime(CLOCK_MONOTONIC, &endTime);
 unsigned int timeElapsed = ( endTime.tv_sec - startTime.tv_sec );
 node->refTime = expiry + timeElapsed;
 node->expiry = expiry;
 node->priority = priority;
 node->nxt = NULL;
 printf ("Create - name: %s, expiry: %u, refTime: %u, priority: %d, timeElapsed: %u\n", node->name, node->expiry, node->refTime, node->priority, timeElapsed);
 return node;
}
void push(Node **node, char *name, int expiry, int priority)
{ 
 unsigned int curTime;
 unsigned int updatedTime;
 Node *head = *node;
 Node *tmp = CreateNode(name, expiry, priority);
 printf ("[Head] name: %s, nxt: %p, headExpiry: %d, refTime: %u\n", head->name, head->nxt, head->expiry, head->refTime);
 printf ("[Temp] name: %s, nxt: %p, headExpiry: %d, refTime: %u, Head>Tmp: %d\n", tmp->name, tmp->nxt, tmp->expiry, tmp->refTime, head->expiry > tmp->expiry);
 if (tmp->refTime <= head->refTime) // append before head
 {
 printf ("New node expiry <= head expiry -- ");
 if (tmp->priority > head->priority || tmp->refTime < head->refTime) // append before head only when HIGH priority
 {
 printf ("tmp->priority > head->priority - append tmp before Head\n");
 tmp->nxt = head;
 *node = tmp;
 }
 else // append after head
 {
 printf ("tmp->priority < head->priority - append tmp after Head\n");
 tmp->nxt = head->nxt;
 head->nxt = tmp;
 }
 }
 else
 {
 while(head->nxt)
 {
 if (tmp->refTime < head->nxt->refTime)
 {
 break;
 } 
 else if (tmp->refTime == head->nxt->refTime)
 {
 if (tmp->priority > head->nxt->priority)
 {
 break;
 }
 }
 head = head->nxt;
 }
 tmp->nxt = head->nxt;
 head->nxt = tmp; 
 }
 printf ("\n");
 print(*node);
}
void popAndPush(Node **node)
{
 Node *tmp = *node;
 printf ("....Popping node (%s,%d,%d)......\n", tmp->name, tmp->priority, tmp->expiry);
 // changing head
 *node = (*node)->nxt;
 printf ("New head: %s\n", (*node)->name);
 char *name = tmp->name;
 unsigned int expiry = tmp->expiry;
 unsigned int priority = tmp->priority;
 
 // delete the node
 free(tmp);
 // pushing new node
 push(node, name, expiry, priority);
}

main.c

#include <stdio.h>
#include "list.h"
#include <time.h>
#include <pthread.h>
typedef struct
{
 char *type;
 int expiry;
 int priority;
 char *msg; 
} TimerInfo;
TimerInfo timerList[] = {
 {
 .type = "taskA",
 .expiry = 5,
 .priority = 10,
 .msg = "Sending TaskA"
 },
 {
 .type = "taskB",
 .expiry = 4,
 .priority = 1,
 .msg = "Sending TaskB"
 },
 {
 .type = "taskC",
 .expiry = 5,
 .priority = 1,
 .msg = "Sending TaskC"
 },
 {
 .type = "taskD",
 .expiry = 2,
 .priority = 11,
 .msg = "Sending TaskD"
 }
}; 
Node *head; 
struct timespec startTime;
struct timespec curTime;
void someCallback(char *msg)
{
 // do something with msg
}
void *Scheduler(void *arg)
{ 
 unsigned int timeElapsed;
 printf (">>>>> Scheduler starts <<<<<\n");
 while(1)
 { 
 clock_gettime(CLOCK_MONOTONIC, &curTime); // get current time
 timeElapsed = curTime.tv_sec - startTime.tv_sec; // time elapsed since startTime
 if (timeElapsed >= head->refTime) // timer has triggered
 {
 printf ("%s (%d) expires - time elasped: %d\n", head->name, head->refTime, timeElapsed);
 popAndPush(&head);
 someCallback(head->msg);
 }
 }
}
int main(void) 
{
 clock_gettime(CLOCK_MONOTONIC, &startTime); // record the time at the start of the app
 pthread_t tId;
 head = CreateNode(timerList[1].type, timerList[1].expiry, timerList[1].priority);
 
 print(head);
 push(&head, timerList[2].type, timerList[2].expiry, timerList[2].priority);
 push(&head, timerList[0].type, timerList[0].expiry, timerList[0].priority);
 push(&head, timerList[3].type, timerList[3].expiry, timerList[3].priority);
 
 pthread_create(&tId, NULL, Scheduler, NULL);
 pthread_join(tId, NULL);
 return 0;
}

If you copy the code into an online compiler, you should be able to run it and see how the output relates to the code in case of any confusion.

The program seems to work fine but posting to see if there are any corner cases that I forgot to take into account or any design approach that would work better. Appreciate any help!

Edit:

• Would having a run queue be beneficial for debugging purposes? If so, what should it store? A generic run queue seems to hold the number of idle and active tasks but in my case, that happens based on the expiry and priority.
• if the someCallback() writes to a message queue that's read by an external MCU for instance, and there needs to be ACK sent for each request received by the MCU, waiting for some time till the ACK is received in the scheduler might mess up with the logic I suppose? How could that be dealt with given that's a scenario?

• pacmaninbw: Please do not edit the question, especially the code, after an answer has been posted. Changing the question may cause answer invalidation. Everyone needs to be able to see what the reviewer was referring to. What to do after the question has been answered.
• xyf: my apologies. only did so cause there was a compilation error as one of the commenters pointed out and anyone attempting to try out the code may run into errors
• Neil: Do you really need expiry and priority? It would be simpler just to merge them, but I guess that depends on how many time steps polling takes.
• xyf: yeah well priority mainly comes into the picture if the timeouts of different nodes are the same. So NodeA expiring in 5s and so does NodeB except it has a higher priority than NodeA therefore the head of the queue must be pointing to NodeB

Answer 1

any corner cases that I forgot to take into account

No error handling

e.g.: malloc() may return NULL.

---

any design approach that would work better.

Improve name space

list.h defines node, Node, push, popAndPush, CreateNode, print.

I recommend instead to have node.h to define node, node_push, node_popAndPush, node_create, node_print.

Missing code guard

.h files deserve code guard and minimal included .h files.

#ifndef list_h
#define list_h
//#include "string.h"
//#include <stdlib.h>
//#include <stdio.h>
//#include <time.h>
...
#endif 

Use const

Greater clarity, application and optimization potential.

// void print(Node *node)
void print(const Node *node)

---

Appreciate any help!

Wrong size

With the given struct, there is no need to allocate for the string. Node only saves the pointer to the original string.

// malloc(sizeof(*node) + strlen(name) + 1);
malloc(sizeof *node);

If wanting a copy of the string, consider instead a flexible member array.

typedef struct node {
 struct node *head;
 int priority;
 unsigned int expiry;
 unsigned int refTime;
 struct node *nxt;
 char name[];
} Node;
size_t sz = strlen(name) + 1;
Node *node = malloc(sizeof *node + sz);
node->... = ...
strcpy(node->name, name);

• xyf: Thanks. In response to malloc error handling, CreateNode() returns *node ... so given that, what'd you return in case of a malloc failure? I was thinking of returning an ERROR code ENUM but that's not possible with this...
• chux: @xyf "what'd you return in case of a malloc failure" --> Node *CreateNode(char *name, unsigned int expiry, int priority) { Node *node = malloc(sizeof(*node) + strlen(name) + 1); if (node == NULL) return NULL; ....}.

Answer 2

Code structure There are three important components here

1. Priority queue
2. Scheduler
3. Timer

Scheduler picks up timer based on priority queue and fires.

Should priority queue know about details of Timer? No

Priority queue node needn't know details about timer. It only needs to know how to compute priority of node representing timer. So name, expiry time and refTime shouldn't be part of priority queue node.

typedef struct node
{
 struct node *head;
 char *name; // Shouldn't be part of the struct
 int priority;
 unsigned int expiry; // Shouldn't be part of the struct
 unsigned int refTime; // Shouldn't be part of the struct
 struct node *nxt;
} Node;

Node should take timer as opaque pointer and a pointer to a function which compares priority of two timers.

typedef int (*NodeComparator)(void* nodedata_a , void* nodedata_b );
typedef struct node
{
 struct node *head; 
 int priority;
 void* nodedata; // Opaque pointer. In OOPS world it could be interface.
 NodeComparator comparator;
 struct node *nxt;
} 

Should Scheduler know timer details? No. Should Scheduler know priority queue details? No Current code is good with respect to these two questions.

Priority queue

Heap based implementation will be more efficient than current implementation. We don't need to maintain a sorted list because at any time we need to know which timer is going to be fired next.

Code review

1. Compilation error: head doesn't have msg. Probably you wanted to use name

someCallback(head->msg);

2. In function signature mark input parameters not expected to be changed as const

typedef struct priority_queue_node
{
 void *data;
 struct priority_queue_node *nxt;
} priority_queue_node;
// Checks if priority of nodedata_a is higher than nodedata_b
typedef bool (*NodeComparator)(void* nodedata_a, void* nodedata_b); 
typedef struct 
{
 priority_queue_node* head;
 NodeComparator comparator;
} priority_queue;
typedef struct TimerInfo
{
 char* type ;
 int expiry = 0;
 DWORD refTime = 0;
 int priority = 0;
 char* msg;
} TimerInfo;
bool TimerInfoComparator(void *timerInfo_a, void *timerinfo_b)
{
 TimerInfo* timer_a = (TimerInfo*)timerInfo_a;
 TimerInfo* timer_b = (TimerInfo*)timerinfo_b;
 return (timer_a->refTime < timer_b->refTime) ||
 ((timer_a->refTime == timer_b->refTime) &&
 (timer_a->priority > timer_b->priority));
}
void push(priority_queue *queue, priority_queue_node** node)
{
 priority_queue_node* head = queue->head;
 priority_queue_node* tmp = *node;
 if (queue->comparator(tmp, head))
 {
 queue->head = tmp;
 tmp->nxt = head;
 }
 else
 {
 while (head && head->nxt)
 {
 if (!queue->comparator(tmp, head->nxt))
 break;
 head = head->nxt;
 }
 tmp->nxt = head->nxt;
 head->nxt = tmp;
 }
}
```

• xyf: Thanks. Good point about drawling a line between priority queue and other details. 1) so nodedata could also be a pointer to a TimerInfo, and void* since you want to make it sort of generic? 2) regarding the comparator, note that I'm just not doing comparing between two priorities but also the timeouts. other than that, do you please mind elaborating on what really could go inside the comparator? in my logic, for e.g: push(), there's a bunch of conditions I'm taking into account to ensure the new node gets pushed at the right place...
• xyf: and by heap based implementation, you're referring to something like a binary tree?
• Neil: This would be good to store implicitly.
• nkvns: @xyf: Yes nodedata should be pointer to TimerInfo and void* as priority queue needn't know details about pointed data. Aim is have loose coupling.
• G. Sliepen: comparator should not be part of a node; apart from the unnecessary memory overhead, what happens if two nodes have different comparators? Ideally there should be a struct priority_queue which has members NodeComparator comparator and struct priority_queue_node *head.

Answer 3

There seems to be some confusion between this struct:

typedef struct node
{
 struct node *head;
 char *name;
 int priority;
 unsigned int expiry;
 unsigned int refTime;
 struct node *nxt;
} Node;

and allocation of its instances:

Node *CreateNode(const char *name, unsigned int expiry, int priority)
{
 Node *node = malloc(sizeof(*node) + strlen(name) + 1);
 node->name = name;

It looks like you meant to write a flexible array member:

typedef struct node
{
 struct node *head;
 int priority;
 unsigned int expiry;
 unsigned int refTime;
 struct node *nxt;
 char name[];
} Node;

Node *CreateNode(const char *name, unsigned int expiry, int priority)
{
 Node *node = malloc(sizeof *node + strlen(name) + 1);
 if (!node) return node;
 strcpy(node->name, name);

Note that we accept pointer to const char, because we're making a copy of the name (and we no longer require the caller to keep the string alive for us), and also that we test the result of malloc() so that we don't attempt to dereference any null pointers.

---

Pointers passed to vararg functions such as printf are not auto-converted to void* as they are in other contexts, so we need to explicitly cast them:

 printf ("[Head] name: %s, nxt: %p, headExpiry: %d, refTime: %u\n",
 head->name, (void*)head->nxt, head->expiry, head->refTime);
 printf ("[Temp] name: %s, nxt: %p, headExpiry: %d, refTime: %u, Head>Tmp: %d\n",
 tmp->name, (void*)tmp->nxt, tmp->expiry, tmp->refTime, head->expiry > tmp->expiry);

---

We play fast and loose with integer conversion such as this one:

 unsigned int timeElapsed = endTime.tv_sec - startTime.tv_sec;

We're truncating a long to unsigned int here, which can corrupt the value (remember that maximum unsigned int can be as low as 65536). Use the correct types throughout (I recommend gcc -Wconversion to help identify these; there's too many to list in this answer).

---

Similarly, assigning string literals to char * variables can lead to undefined behaviour. It's fairly easy to fix here, as we want to use const char* in most places (use gcc -Wwrite-strings to catch these).

• Neil: Good point about the unsigned int; this code would be much longer lasting with the proper types.
• xyf: Thanks. Also do you see any overflow happening at some point say when timer value goes beyond its size which is long?