Я вижу следующие проблемы:
queue_free не освобождает память для объекта beforeFirst. add_priority не освобождает элемент, еслираспределение данных не удается.Это не имеет большого значения, так как вы выходите, но было бы неплохо, если вы когда-нибудь решите вернуть ошибку (другими словами, это остановит утечку памяти).
ОднакоЯ протестировал этот код, вставив новый элемент, элемент перед этим, затем элемент в конце, и это выглядит нормально.Какие значения приоритетов вы вставляете (по порядку)?
И вы можете разместить код, который вызывает этот код.Вполне возможно, что это может быть проблема повреждения памяти, не связанная с этим фактическим кодом.
Хотя я ценю вашу попытку ввести материал beforeFirst, чтобы сохранить ваш код приятным, вам действительно нужно просто откусить пулюи избавиться от этого.Его удаление, вероятно, более чем компенсирует минимальный объем дополнительного кода, который вам придется добавить для обработки действительно пустого списка.Этот более простой код должен обрабатывать все сценарии без дополнительной обработки, необходимой для синхронизации дополнительных указателей.
На самом деле я не проверял это, кроме как в моем программном обеспечении, но он должен (надеюсь) работать нормально:
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.
}
Имейте в виду, что queue_add_priority делает копию памяти, чтобы вы могли передать еединамически распределяемая память или иным образом.Эта функция не несет ответственности за освобождение выделенной памяти, которую вы ей передаете.Если он распределяется динамически, вы все равно должны освободить его самостоятельно.Это было сделано таким образом, чтобы вы могли передавать в любую память любого типа.
С другой стороны, queue_remove просто передает вам выделенную память, чтобы вы были ответственность за освобождение, когда вы закончите.Полученная вами память будет всегда получена через malloc.
Вы можете оптимизировать queue_add_priority, чтобы вы могли указать, что передаваемая памятьраспределяется через malloc, и вы передаете ответственность, изменяя первую часть функции с:
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);
на:
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;
}
Другими словами, установите для конечного параметра значение trueесли данные были получены с помощью malloc, и вы соглашаетесь отказаться от ответственности за них - таким образом, функция просто принимает ваш блок памяти как есть.
В противном случае используйте false, и будет сделана копия.