3
\$\begingroup\$

You think that your code is perfect ... until you put it up for code review.

I put up my priority queue for review and received lots of really good feedback. Including a memory leak which was embarrassing.

See here:

Priority queue implementation in C based on heap ordered (resizable) array

So I added in most of the suggestions and here it is. I would like to see if I interpreted the suggestions correctly and also see if there is anything else that needs fixing.

I realise of course that to make it really industrial strength, like for example the C library sort functions or the C++ standard library then changes would be required. But hopefully this code is still useful for some uses.

One remaining item that I have not addressed is the array_resize function. Fixing that is not trivial so have left that issue for now. Basically, if realloc fails, what to do.

Here is the code.

priority_queue.h - header:

/*
Heap ordered priority queue storing in a resizable array
*/

#ifndef PRIORITY_QUEUE_
#define PRIORITY_QUEUE_

struct priority_queue;
typedef struct priority_queue priority_queue_t;

/* priority_queue_init initialises the priority queue and returns a handle which 
must be passed to subsequent priority_queue_xxx functions..  Argument is the
comparison function.  This comparison function must return a negative value if
the first argument is less than the second, a positive integer value if the 
first argument is greater than the second, and zero if the arguments are equal.
The function must also not modify the objects passed to it.  The meaning of
greater or less can be reversed. */
priority_queue_t* priority_queue_init(int(*compare)(const void* element1, const void* element2));
/* priority_queue_free frees memory used by priority queue. init in constant time */
void priority_queue_free(priority_queue_t* pq);
/* returns 1 if the queue is empty, 0 otherwise. constant time */
int priority_queue_empty(const priority_queue_t* pq);
/* insert an object into the priority queue. insert in logarithmic time */
void priority_queue_insert(priority_queue_t* pq, void* el);
/* pops the 'top' element and removes from the priority queue. pop in logarithmic time */
void* priority_queue_pop(priority_queue_t* pq);
/* returns the top element but does not remove from priority queue. top in constant time */
void* priority_queue_top(const priority_queue_t* pq);
/* returns number of elements in priority queue. constant time */
int priority_queue_size(const priority_queue_t* pq);

#endif // PRIORITY_QUEUE_

priority_queue.c - the implementation:

#include "priority_queue.h"

#include <stdlib.h>

typedef int(*compare)(const void* element1, const void* element2);

struct priority_queue {
    int capacity;
    int n;
    void** array;
    compare cmp;
};

static const int initial_size = 16;

static void swap(priority_queue_t* pq, int index1, int index2) {
    // shallow copy of pointers only
    void* tmp = pq->array[index1];
    pq->array[index1] = pq->array[index2];
    pq->array[index2] = tmp;
}


static void rise(priority_queue_t* pq, int k) {
    while (k > 1 && pq->cmp(pq->array[k / 2], pq->array[k]) < 0) {
        swap(pq, k, k / 2);
        k = k / 2;
    }
}

static void fall(priority_queue_t* pq, int k) {
    while (2 * k <= pq->n) {
        int child = 2 * k;
        if (child < pq->n && pq->cmp(pq->array[child], pq->array[child + 1]) < 0) {
            child++;
        }

        if (pq->cmp(pq->array[k], pq->array[child]) < 0) {
            swap(pq, k, child);
        }
        k = child;
    }
}

static void** array_resize(void** array, int newlength) {
    /* reallocate array to new size
       this is problematic because realloc may fail and return NULL
       in which case there is a leak because array is still allocated
       but not returned so cannot be free'd */
    return realloc(array, newlength * sizeof(void*));
}

priority_queue_t* priority_queue_init(int(*compare)(const void* element1, const void* element2)) {
    priority_queue_t* pq = malloc(sizeof(priority_queue_t));
    pq->array = NULL;
    pq->capacity = 0;
    pq->n = 0;
    pq->cmp = compare;
    return pq;
}

void priority_queue_free(priority_queue_t* pq) {
    free(pq->array);
    free(pq);
}

int priority_queue_empty(const priority_queue_t* pq) {
    return pq->n == 0;
}

void priority_queue_insert(priority_queue_t* pq, void* el) {

    if (pq->capacity == 0) {
        pq->capacity = initial_size;
        pq->array = array_resize(pq->array, pq->capacity + 1);
    }
    else if (pq->n == pq->capacity) {
        pq->capacity *= 2;
        // we need to resize the array
        pq->array = array_resize(pq->array, pq->capacity + 1);
    }

    // we always insert at end of array
    pq->array[++pq->n] = el;
    rise(pq, pq->n);
}

void* priority_queue_pop(priority_queue_t* pq) {

    // reduce array memory use if appropriate
    if (pq->capacity > initial_size && pq->n < pq->capacity / 4) {
        pq->capacity /= 2;
        pq->array = array_resize(pq->array, pq->capacity + 1);
    }

    void* el = pq->array[1];
    swap(pq, 1, pq->n--);
    pq->array[pq->n + 1] = NULL;  // looks tidier when stepping through code - not really necessary
    fall(pq, 1);
    return el;
}

void* priority_queue_top(const priority_queue_t* pq) {
    return pq->array[1];
}

int priority_queue_size(const priority_queue_t* pq) {
    return pq->n;
}

example driver program:

#include "priority_queue.h"

#include <string.h>
#include <stdlib.h>
#include <stdio.h>

typedef struct {
    int weight;
    char* data;
} element;


int descending(const void* a, const void* b) {
    const element* element1 = a;
    const element* element2 = b;
    if (element1->weight < element2->weight)
        return -1;
    if (element1->weight > element2->weight)
        return 1;

    return 0;
}

typedef struct {
    int vertex;
    int weight;
} edge;

int ascending(const void* a, const void* b) {
    const edge* edge1 = a;
    const edge* edge2 = b;
    if (edge2->weight < edge1->weight)
        return -1;

    if (edge2->weight > edge1->weight)
        return 1;

    return 0;
}

int main() {
    priority_queue_t* pq = priority_queue_init(descending);
    printf("size of pq now = %d\n", priority_queue_size(pq));

    int weights[] = { 14,8,15,16,11,1,12,13,4,10,9,3,5,7,2,6,6,6 };
    int size = sizeof(weights) / sizeof(weights[0]);

    // insert each one into priority queue
    for (int i = 0; i < size; ++i) {
        element* el = malloc(sizeof(element));

        // generate string
        char buffer[20];
        sprintf(buffer, "added no: %d", i + 1);
        el->data = malloc(strlen(buffer) + 1);
        strcpy(el->data, buffer);
        el->weight = weights[i];
        priority_queue_insert(pq, el);
    }
    printf("size of pq now = %d\n", priority_queue_size(pq));
    element* el = malloc(sizeof(element));
    el->weight = 22;
    el->data = "hi guys";
    priority_queue_insert(pq, el);
    printf("size of pq now = %d\n", priority_queue_size(pq));

    const element* top = priority_queue_top(pq);
    printf("peek of top item: %d %s\n", top->weight, top->data);

    while (!priority_queue_empty(pq)) {
        element* top = priority_queue_pop(pq);
        printf("top is: %d %s\n", top->weight, top->data);
        free(top);
    }
    printf("size of pq now = %d\n", priority_queue_size(pq));
    priority_queue_free(pq);

    // try using different data/comparator
    pq = priority_queue_init(ascending);
    edge* e1 = malloc(sizeof(edge));
    e1->vertex = 0;
    e1->weight = 1;
    priority_queue_insert(pq, e1);
    edge* e2 = malloc(sizeof(edge));
    e2->vertex = 1;
    e2->weight = 3;
    priority_queue_insert(pq, e2);

    edge* e3 = malloc(sizeof(edge));
    e3->vertex = 2;
    e3->weight = 3;  // same weight
    priority_queue_insert(pq, e3);

    while (!priority_queue_empty(pq)) {
        edge* top = priority_queue_pop(pq);
        printf("top is: %d %d\n", top->weight, top->vertex);
        free(top);
    }
    printf("size of pq now = %d\n", priority_queue_size(pq));
    priority_queue_free(pq);
}
\$\endgroup\$
  • \$\begingroup\$ This looks really nice. I don't see the need to reduce the size of the container on pop. But it looks like you at least do it in a sensical way. :) \$\endgroup\$ – Cris Luengo Feb 3 '18 at 15:54
  • \$\begingroup\$ Suggest adding clear review goals. \$\endgroup\$ – chux Feb 3 '18 at 19:24
0
\$\begingroup\$

One remaining item that I have not addressed is the array_resize function. Fixing that is not trivial so have left that issue for now. Basically, if realloc fails, what to do(?)

  1. I find confusing for the pq->array allocated memory as proportional to pq->capacity + 1. Re-write code so the array's count is pq->capacity.

  2. I'd go for a array_resize() that can affect the state of priority_queue_t* pq to put it into a error/start state. Example

    // return true on problem
    static bool array_resize(priority_queue_t* pq, size_t new_count) {
      if (new_count > 0) {
        void *new_pointer = realloc(pq->array, sizeof *pq->array * new_count);
        if (new_pointer) {  // Success path
          pq->array = new_pointer;
          pq->capacity = new_count;
          return false; 
        }
        if (new_count <= pq->capacity) {
          return false;  // failure to reduce is not really an error.
        }
        // fall though on allocation failure
      }
      pq->n = 0;
      pq->capacity = 0;
      free(pq->array);
      pq->array = NULL;
      return new_count > 0;
    }
    

Other stuff

  1. Cope with unexpected function order usage. True that out of order function usage concerning init() and free() are problematic, but what about priority_queue_pop() with nothing in the queue? Code exhibits UB. Better to test and return NULL or somehow stop/warn/handle.

  2. Good ideas like below that are useful in debug could wrap in a macro. IMO, when the burden is light, just leave in debug and production code.

    #ifndef NDEBUG
      pq->array[pq->n + 1] = NULL;
    #endif 
    
  3. Note: priority_queue_pop() never shrinks the array allocation to 0. Not a bad design goal. Hmmm.

Minor

  1. Nice improvement.

  2. Add some blank lines to improve clarity.

    /* returns 1 if the queue is empty, 0 otherwise. constant time */
    int priority_queue_empty(const priority_queue_t* pq);
    
    /* insert an object into the priority queue. insert in logarithmic time */
    void priority_queue_insert(priority_queue_t* pq, void* el);
    
    /* pops the 'top' element and removes from the priority queue. pop in logarithmic time */
    void* priority_queue_pop(priority_queue_t* pq);
    
  3. size_t is "just right" type for array indexing and sizing. Neither too wide nor too narrow.

    struct priority_queue {
        // int capacity, n;
        size_t capacity, n;
        ...
    };
    
    // int priority_queue_size(const priority_queue_t* pq);
    size_t priority_queue_size(const priority_queue_t* pq);
    
  4. Good formatting. Yet look at the question's code. Is there a horizontal slide bar to show priority_queue.*? To me, that means code is too wide. Wrap to review's presentation width. Auto formatting should make that easy.

  5. Idiomatic compare that many compilers recognize and emit efficient code:
    (a > b) - (a < b)

    int descending(const void* a, const void* b) {
      ...
      return (element1->weight > element2->weight) - 
          (element1->weight < element2->weight);
    }
    

Advanced idea:

  1. Comments in .h do not details what priority_queue functions will do when items compare equal. Stable? Non-deterministic? If N items were inserted, all at the same priority, is the order in which they pop() determined? A classy priority_queue would return these in a way to prevent a stale item (one that sits in a long time). Perhaps if 2 items have the same priority, favor the one with the lower array index?
\$\endgroup\$
  • \$\begingroup\$ A good solution to "prevent a stale item" needs more thought. Hmmm. \$\endgroup\$ – chux Feb 3 '18 at 20:39
  • \$\begingroup\$ Thanks for the fantastic comments. And stale issue I hadn't thought about. \$\endgroup\$ – arcomber Feb 5 '18 at 17:54

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.