I wrote this code to handle a fixed number of priority levels. I believe performance will depend on the number of priority levels.
Considering only a few levels (3 to 5), is there a more efficient way of doing this? I would also like to know how to improve code quality.
I'm just storing the elements in separate queues based on their priority. And to retrieve, looking for the first queue with element_count > 0
in ascending or descending order depending on the function being called.
For the queues I'm using the code I posted before: Queue implementation in C
priority_queue.h
#ifndef PRIORITY_QUEUE_H
#define PRIORITY_QUEUE_H
#include <stdlib.h>
#include <stdint.h>
#include "queue.h"
#define PQ_SUCCESS 0
#define PQ_ERROR 1
#define VERY_HIGH_PRIORITY 4
#define HIGH_PRIORITY 3
#define NORMAL_PRIORITY 2
#define LOW_PRIORITY 1
#define VERY_LOW_PRIORITY 0
typedef struct Priority_Queue Priority_Queue;
Priority_Queue *pq_allocate_custom( uint8_t priority_levels,
size_t lines_per_priority_level,
size_t line_capacity );
Priority_Queue *pq_allocate(void);
void pq_free(Priority_Queue *pq);
int pq_insert(Priority_Queue *pq, void *content, uint8_t priority);
int pq_insert_with_default_priority(Priority_Queue *pq, void *content);
void *pq_dequeue_highest(Priority_Queue *pq);
void *pq_dequeue_lowest(Priority_Queue *pq);
void pq_shrink_to_fit(Priority_Queue *pq);
#endif
priority_queue.c
#include "priority_queue.h"
#define PQ_PRIORITY_LEVELS 5
#define PQ_LINES 4
#define PQ_LINE_CAPACITY 50
//It just keeps separate queues based on priority.
struct Priority_Queue {
Queue **index; //Queue array
size_t element_count;
uint8_t priority_levels;
};
//Internal methods
static void deallocate_all_queues(Priority_Queue *pq)
{
for(uint8_t i = 0; i < pq->priority_levels; ++i)
qu_free(pq->index[i]);
}
//Public methods
//Allocate all data structures according to given values
Priority_Queue *pq_allocate_custom( uint8_t priority_levels,
size_t lines_per_priority_level,
size_t line_capacity )
{
if(priority_levels < 2
|| lines_per_priority_level < 2
|| line_capacity < 1)
return NULL;
//Allocate queue and index
Priority_Queue *pq = malloc(sizeof(Priority_Queue)
+ sizeof(Queue *) * priority_levels);
if(pq == NULL)
return NULL;
//Point the index to the right location
pq->index = (Queue **)(pq + 1);
//Create the queues
for(uint8_t i = 0; i < priority_levels; ++i){
pq->index[i] = qu_allocate_custom(lines_per_priority_level, line_capacity);
//Handle error
if(pq->index[i] == NULL){
//set successfully created queues so deallocation will work
pq->priority_levels = i;
deallocate_all_queues(pq);
free(pq);
return NULL;
}
}
//Set values
pq->element_count = 0;
pq->priority_levels = priority_levels;
return pq;
}
Priority_Queue *pq_allocate(void)
{
return pq_allocate_custom(PQ_PRIORITY_LEVELS, PQ_LINES, PQ_LINE_CAPACITY);
}
void pq_free(Priority_Queue *pq)
{
if(pq == NULL)
return;
deallocate_all_queues(pq);
free(pq);
}
//Will break if priority is not in range
int pq_insert(Priority_Queue *pq, void *content, uint8_t priority)
{
//Try to insert at the correct queue
if(qu_enqueue(pq->index[priority], content) == QU_ERROR)
return PQ_ERROR;
++pq->element_count;
return PQ_SUCCESS;
}
int pq_insert_with_default_priority(Priority_Queue *pq, void *content)
{
return pq_insert(pq, content, pq->priority_levels / 2);
}
void *pq_dequeue_highest(Priority_Queue *pq)
{
if(pq->element_count == 0)
return NULL;
//Find the first queue with element count > 0
uint8_t i;
for(i = pq->priority_levels - 1; qu_get_count(pq->index[i]) == 0; --i)
;
--pq->element_count;
return qu_dequeue(pq->index[i]);
}
void *pq_dequeue_lowest(Priority_Queue *pq)
{
if(pq->element_count == 0)
return NULL;
//Find the first queue with element count > 0
uint8_t i;
for(i = 0; qu_get_count(pq->index[i]) == 0; ++i)
;
--pq->element_count;
return qu_dequeue(pq->index[i]);
}
void pq_shrink_to_fit(Priority_Queue *pq)
{
for(uint8_t i = 0; i < pq->priority_levels; ++i)
qu_shrink_to_fit(pq->index[i]);
}
Considering only a few levels (3 to 5), is there a more efficient way of doing this?
Short answer: no. A PQ is typically implemented as some type of heap (binary or Fibonacci primarily). A heap-backed PQ hasO(1)
time to see the top element andO(lg n)
time to dequeue the top element. Withp = number of priorities
, your queue hasO(p)
time to look andO(p)
time to dequeue (assuming I've analyzed your queue implementation correctly forO(1) and O(1)
). Your implementation is basically as fast as it can get for smallp
. Whenlg n < p
, a traditional queue is asymptotically faster \$\endgroup\$