Problem with PriorityQueue in C

I am trying to write a PriorityQueue for a c project. The program is crashing when I try to dequeue items; however I think the issue is coming from the way I add the items, as If I try to access the first element in the list after adding the third element I get a crash as well.

Header file:

#ifndef PQUEUE_H_INCLUDED 
#define PQUEUE_H_INCLUDED

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

//Data structure for holding one element in pqueue
typedef struct _e {
    void *data;
    size_t datalen;
    int priority;
    struct _e *next;
} ELEMENT;

//data structure for the whole pqueue
typedef struct {
    ELEMENT *head;          //reference to first element 
    ELEMENT *tail;          //reference to last element
    ELEMENT *beforefirst;   //dummy element before 开发者_开发百科first element;
    int elements;
} PQUEUE;


extern PQUEUE*  queue_new(void);
extern void     queue_free(PQUEUE *);
extern void     queue_add_end(PQUEUE *, void *, size_t);
extern void     queue_add_priority(PQUEUE *, void *, size_t,int);
extern void*    queue_remove(PQUEUE *);
extern bool     queue_has_next(PQUEUE *);
extern int      queue_size(PQUEUE *);


#endif 

PriorityQueue code:

#include "pqueue.h"

PQUEUE *queue_new(void) {
    PQUEUE *pq = malloc(sizeof(PQUEUE));
    if (pq == NULL) {
        perror("queue_new");
        exit(EXIT_FAILURE);
    }
    pq->head = NULL;
    ELEMENT *newelement;
    newelement = calloc(1,sizeof(ELEMENT));
    pq->beforefirst = newelement;
    pq->beforefirst->next = pq->head;
    pq->tail = NULL;
    pq->elements = 0;

    return pq;
}

void queue_free(PQUEUE *pq) {
    ELEMENT *this, *save;
    this = pq->head;
    while(this!= NULL) {
        save = this;
        this = this->next;
        free(save->data);
        free(save);
    }
    free(pq);
}


void queue_add_priority(PQUEUE *pq, void *data, size_t datalen,int priority) {
    ELEMENT *newelement;
    newelement = calloc(1,sizeof(ELEMENT));
    if (newelement == NULL) {
        perror("queue_add");
        exit(EXIT_FAILURE);
    }
    newelement->data = malloc(datalen);
    newelement->priority = priority;
    if(newelement->data == NULL) {
        perror("queue_add");
        exit(EXIT_FAILURE);
    }
    memcpy(newelement->data,data,datalen);
    newelement->datalen = datalen;
    newelement->next = NULL;
    //sets pointer at beforefirst element and iterates through queue until ptr->next
    // priority is greater than newlement priority, or until end of queue.
    ELEMENT *ptr = pq->beforefirst;
    while (ptr->next != NULL) {
        if (ptr->next->priority > priority) break;
        ptr = ptr->next;
    }
    if (ptr == pq->beforefirst) {
        pq->head = newelement;
    }
    if (ptr->next == NULL) {
        pq->tail = newelement;
    }
    newelement->next = ptr->next;
    ptr->next = newelement;


    //ERROR HERE
    //void* d;
    //d = pq->head->data;
    pq->elements++;
}

void* queue_remove(PQUEUE *pq) {
    //ERROR HERE
    void* item = pq->head->data;
    pq->head = pq->head->next;
    pq->elements--;
    return item;
}

bool queue_has_next(PQUEUE *pq) {
    return !(pq->elements == 0);
}

Basically, the error seems to be coming when I try to access pq->head->data after I've added the third element - I narrowed it down to the areas commented //ERROR HERE. It seems odd to me because adding the third element should work identically to adding the second. Also neither pq->head == NULL or pq->head>data == NULL.

I see the following problems:

• queue_free does not free the memory for its beforeFirst object.
• add_priority won't free the element if the data allocation fails. This doesn't matter that much since you're exiting but it would be good form in case you ever decide to return an error (in other words, it will stop a memory leak).

However, I've tested that code by inserting a new element, an element before that one then an element at the end, and it seems fine. What priority values are you inserting (in order)?

And you may want to post the code that's calling this code. It's quite possible it may be a memory corruption issue unrelated to this actual code.

While I appreciate your attempt in introducing the beforeFirst stuff to keep your code nice, you really should just bite the bullet and get rid of it. Its removal will probably more than offset the minimal amount of extra code you're going to have to add for handling a truly empty list. This simpler code should handle all scenarios without the added processing required to keep extra pointers synchronised.

I haven't actually tested this other than in my wetware but it should (hopefully) work okay:

typedef struct _e {
    void *data;
    size_t datalen;
    int priority;
    struct _e *next;
} ELEMENT;

typedef struct {
    ELEMENT *head;          //reference to first element 
    ELEMENT *tail;          //reference to last element
    int elements;
} PQUEUE;

PQUEUE *queue_new(void) {
    PQUEUE *pq = malloc(sizeof(PQUEUE));
    if (pq == NULL) {
        perror("queue_new");
        exit(EXIT_FAILURE);
    }
    pq->head = pq->tail = NULL;
    pq->elements = 0;
    return pq;
}

void queue_free(PQUEUE *pq) {
    ELEMENT *this, *save;
    this = pq->head;
    while(this!= NULL) {
        save = this;
        this = this->next;
        free(save->data);
        free(save);
    }
    free(pq);
}

void queue_add_priority(PQUEUE *pq, void *data, size_t datalen, int priority) {
    ELEMENT *newelement;
    newelement = calloc(1,sizeof(ELEMENT));
    if (newelement == NULL) {
        perror("queue_add");
        exit(EXIT_FAILURE);
    }
    newelement->data = malloc(datalen);
    if(newelement->data == NULL) {
        perror("queue_add");
        free (newelement);
        exit(EXIT_FAILURE);
    }
    memcpy(newelement->data,data,datalen);
    newelement->datalen = datalen;
    newelement->priority = priority;
    newelement->next = NULL;

    // Inserting into empty list.
    if (pq->elements == 0) {
        pq->head = pq->tail = newelement;
        pq->elements = 1;
        return;
    }

    // Inserting beyond tail.
    if (pq->tail->priority <= priority) {
        pq->tail->next = newelement;
        pq->tail = newelement;
        pq->elements++;
        return;
    }

    // Inserting before head.
    if (pq->head->priority > priority) {
        newelement->next = pq->head;
        pq->head = newelement;
        pq->elements++;
        return;
    }

    // Otherwise, we're inserting somewhere in the middle.
    ELEMENT *ptr = pq->head;
    while (ptr->next->priority <= priority)
        ptr = ptr->next;
    newelement->next = ptr->next;
    ptr->next = newelement;
    pq->elements++;
}

void* queue_remove(PQUEUE *pq) {
    if (pq->elements == 0)        // added, just in case.
        return NULL;
    void* item = pq->head->data;
    pq->head = pq->head->next;
    pq->elements--;
    return item;
}

bool queue_has_next(PQUEUE *pq) {
    return (pq->elements > 0);    // better, IMNSHO.
}

Keep in mind that queue_add_priority makes a copy of the memory so that you can pass it dynamically allocated memory or otherwise. That function doesn't accept responsibility for freeing any allocated memory that you pass to it. If it's dynamically allocated, you still have to free it yourself. It was done this way so you could pass in any sort of memory.

On the other hand, queue_remove just passes you back the allocated memory so you are responsible for freeing it when you're done. The memory you receive will have always been obtained via malloc.

You could optimise queue_add_priority so that you could specify that the memory being passed in is allocated via malloc and you are passing responsibility by changing the first part of the function from:

void queue_add_priority(PQUEUE *pq, void *data, size_t datalen, int priority) {
    ELEMENT *newelement;
    newelement = calloc(1,sizeof(ELEMENT));
    if (newelement == NULL) {
        perror("queue_add");
        exit(EXIT_FAILURE);
    }
    newelement->data = malloc(datalen);
    if(newelement->data == NULL) {
        perror("queue_add");
        free (newelement);
        exit(EXIT_FAILURE);
    }
    memcpy(newelement->data,data,datalen);

to:

void queue_add_priority(PQUEUE *pq, void *data, size_t datalen, int priority, int xfer) {
    ELEMENT *newelement;
    newelement = calloc(1,sizeof(ELEMENT));
    if (newelement == NULL) {
        perror("queue_add");
        exit(EXIT_FAILURE);
    }
    if (!xfer) {
        newelement->data = malloc(datalen);
        if(newelement->data == NULL) {
            perror("queue_add");
            free (newelement);
            exit(EXIT_FAILURE);
        }
        memcpy(newelement->data,data,datalen);
    } else {
        newelement->data = data;
    }

In other words, set the final parameter to true if the data was obtained via malloc and you agree to give up responsibility for it - that way, the function just takes your memory block as is.

Otherwise, use false and a copy will be made.

Here's an access pattern that causes a problem.

PQUEUE *queue = queue_new();
int x0 = 0;
int x1 = 1;
queue_add_priority(queue, &x0, sizeof(x0), x0); //add1
queue_add_priority(queue, &x1, sizeof(x1), x1); //add2
queue_remove(queue);                            //remove
queue_add_priority(queue, &x0, sizeof(x0), x0); //add3
while (queue_has_next(queue))
    printf("%d\n", *(int *)queue_remove(queue));

Should items with higher priority be appearing at the head? This doesn't happen in your code if it should.

After the first two adds, the count is two and the lower priority item is at the head (0 1, count:2). The following remove takes the head element decrementing the count. What's left is the priority 1 item (1, count:1). The problem is adding another 0 priority item, doesn't actually add anything to the queue and the count is still incremented (1, count:2). Then since the queue has recorded that there are 2 items when there really is only 1, the remove in the end fails.

The problem lies in your traversal of the queue. More specifically where you start (the beforefirst pointer) is not updated after a remove. After a remove, it is still pointing to the "removed" node. In effect, all proceeding adds will be adding to the end of the previously removed node leaving the actual queue in an inconsistent state. This is one of the reasons why it is a good idea to consistently free memory when it is not needed and to set the pointer to NULL afterwards.

In addition to the problems that paxdiablo mentioned, you're also forgetting to update beforefirst->next in the case where you remove the head of the queue. Here's what's happening:

Before queue_remove:

  beforefirst             head                tail
       |                   |                   |
       V                   V                   V
+-------------+     +-------------+     +-------------+
| placeholder | --> |      x      | --> |      y      | --> NULL
+-------------+     +-------------+     +-------------+



After queue_remove:

  beforefirst                             head   tail
       |                                    |      |
       V                                    V      V
+-------------+     +-------------+     +-------------+
| placeholder | --> |      x      | --> |      y      | --> NULL
+-------------+     +-------------+     +-------------+

You need to fix queue_remove so that beforefirst->next points to head->next if head is non-NULL (NULL otherwise).

You have to fix queue_add to also change before_first if the element inserted is at the first position.

Generally, I would not use before_first. Just change your loops to check for ptr to current == null and change the start element to be the first.

Should eliminate all other issues as well.

hth

Mario