Very simple priority queue

Question

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]);
}

Answer 1

Like @Corbin said, there is little that can be done to improve the efficiency of your code. But there are a few things I can do to improve the code quality.

• You list define a lot of priorities in your header file.

  #define VERY_HIGH_PRIORITY 4
  #define HIGH_PRIORITY 3
  #define NORMAL_PRIORITY 2
  #define LOW_PRIORITY 1
  #define VERY_LOW_PRIORITY 0
  

  Put them in an enum instead.

  typedef enum {VERY_LOW, LOW, NORMAL, HIGH, VERY_HIGH} priority_t;
  

  You will have to change your struct definition though (and perhaps some other definitions in other areas).

  struct Priority_Queue
  {
      Queue **index; //Queue array
      size_t element_count;
      enum priority_t priority_levels;
  };
  

• This is an odd line that may need re-writing. You should change the overall queue struct to be defined as queue_t in my opinion

  typedef struct Priority_Queue Priority_Queue; // can be confusing
  typedef struct queue_t Priority_Queue; // goes from abstract to concrete, readable
  

• You have some very long name definition such as pq_insert_with_default_priority. That can be a task to type without an IDE, and annoying if you misspell it. Perhaps you should make the name shorter.