priority queue for fixed number of entities
main features:
- malloc-free
- single header
- gcc only
- not thread safe
- designed for event driven systems
The design is based on the use case of an event driven system where the main loop waits for the next event in a sleep mode to reduce power consumption and processes the next event calling event handler(s) which may reinserting event requests in the queue for the future. In the majority of the similar systems there are only a limited number of sources of such events and those are known at compile time. This queue uses this assumption and has a fixed number of entries in the queue which is implemented as an array. To prevent the sudden queue full exceptions, all entities needs to allocate an entry in this array calling the pq_reg() API. Preferably these pq_reg() calls happens near boot time or application start time and the results should be assert()ed to find out queue size issues early. After each pq_reg() successfully registered an entity in the queue, it can be used safely to insert and reinsert requests. The pq_reg() will return an array index for the caller and pq_enq()ing on this ID will overwrite the previous value and also reorder the queue when needed.
PQ_SIZE: maximum number of registered entities for the queue (default: 50)
PQ_TYPE: type of the priority field of the queue (default: unsigned long)
PQ_PRIFLOOR: minimum value of the priorities (default: 0)
PQ_STRUCT: additional struct data stored for items (default: undefined)
void pq_init(struct pq *p);
Initialize the given pq struct which should be provided by the caller.
int pq_reg(struct pq *p);
Registering a new client for the queue. Returns the client ID (>0) which should be used when calling pq_enq(). Returns 0 when no more space available.
void pq_enq(struct pq *p, int id, PQ_TYPE pri);
Replacing the priority value of the corresponding client ID or add it if it was missing
struct pqi *pq_next(struct pq *p);
Consuming the item with the lowest priority of the queue. Returns NULL when the queue is empty. Returns struct pqi * item pointer which have a ud field for the PQ_STRUCT when it is defined. The returned item has the lowest priority and it's also removed from the queue.
int pq_peek(struct pq *p);
Returns the client ID of the lowest priority item or 0 when the queue is empty. The item will not be removed from the queue.
struct pqi *pq_data(struct pq *p, int id);
Returns the struct pqi * pointer of the given client ID.
Returns the struct pqi * pointer of the lowest priority item or NULL when the queue is empty. The item will not be removed from the queue.
void pq_iter(struct pq *p, void (*f)(int id, struct pqi *elm));
Iterating over the queue and calling the f() function on every item with the client ID and a pointer to the actual item.
The queue is designed for single threaded finite state machine based event driven systems where multiple but fixed number of entities (modes/functions/etc) can add time based events to a common queue which can be used as a single schedule table for waking up at the closest event.