5
\$\begingroup\$

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]);
}
\$\endgroup\$
  • 2
    \$\begingroup\$ 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 has O(1) time to see the top element and O(lg n) time to dequeue the top element. With p = number of priorities, your queue has O(p) time to look and O(p) time to dequeue (assuming I've analyzed your queue implementation correctly for O(1) and O(1)). Your implementation is basically as fast as it can get for small p. When lg n < p, a traditional queue is asymptotically faster \$\endgroup\$ – Corbin Jan 5 '14 at 9:00
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thank you for your remarks. Isn't using the suffix _t considered bad since it's reserved by POSIX? \$\endgroup\$ – 2013Asker Jan 28 '14 at 15:37
  • \$\begingroup\$ @2013Asker I don't think so, it's used to indicate that a struct is a typedef. \$\endgroup\$ – syb0rg Jan 28 '14 at 15:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.