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.