Problema con PriorityQueue en C

Estoy tratando de escribir un PriorityQueue para un proyecto de CA. El progtwig se bloquea cuando bash quitar la cola de los elementos; sin embargo, creo que el problema proviene de la forma en que agrego los elementos, ya que si bash acceder al primer elemento de la lista después de agregar el tercer elemento, también se produce un locking.

Archivo de cabecera:

#ifndef PQUEUE_H_INCLUDED #define PQUEUE_H_INCLUDED #include  #include  #include  #include  //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 

Código de PriorityQueue:

 #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); } 

Básicamente, el error parece venir cuando bash acceder a pq-> head-> data después de haber agregado el tercer elemento. Lo reduje a las áreas comentadas // ERROR AQUÍ. Me parece extraño porque agregar el tercer elemento debería funcionar de manera idéntica a agregar el segundo. Tampoco pq-> head == NULL o pq-> head> data == NULL.

Veo los siguientes problemas:

  • queue_free no libera la memoria para su objeto beforeFirst .
  • add_priority no liberará el elemento si falla la asignación de datos. Esto no importa mucho ya que está saliendo, pero sería una buena forma si alguna vez decide devolver un error (en otras palabras, detendrá una pérdida de memoria).

Sin embargo, he probado ese código insertando un nuevo elemento, un elemento antes de ese elemento y luego un elemento al final, y parece estar bien. ¿Qué valores de prioridad están insertando (en orden)?

Y es posible que desee publicar el código que está llamando a este código. Es muy posible que sea un problema de corrupción de memoria no relacionado con este código real.


Si bien aprecio su bash de introducir las cosas de beforeFirst para mantener su código agradable, realmente debería morder la bala y deshacerse de ella. Su eliminación probablemente compensará con creces la cantidad mínima de código adicional que tendrá que agregar para manejar una lista verdaderamente vacía. Este código más simple debe manejar todos los escenarios sin el procesamiento adicional requerido para mantener los punteros adicionales sincronizados.

Realmente no he probado esto, excepto en mi wetware, pero debería (con suerte) funcionar bien:

 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. } 

Tenga en cuenta que queue_add_priority hace una copia de la memoria para que pueda pasarla asignada dinámicamente o de otra manera. Esa función no acepta la responsabilidad de liberar ninguna memoria asignada que se le pase. Si se asigna dinámicamente, todavía tienes que liberarlo tú mismo. Se hizo de esta manera para que pueda pasar en cualquier tipo de memoria.

Por otro lado, queue_remove solo te devuelve la memoria asignada, por lo que eres responsable de liberarla cuando hayas terminado. La memoria que reciba siempre se habrá obtenido a través de malloc .

Puede optimizar queue_add_priority para que pueda especificar que la memoria que se pasa se asigna a través de malloc y usted pasa responsabilidad al cambiar la primera parte de la función de:

 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); 

a:

 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; } 

En otras palabras, establezca el parámetro final en verdadero si los datos se obtuvieron a través de malloc y usted acepta renunciar a su responsabilidad; de esa forma, la función simplemente toma su bloque de memoria tal como está.

De lo contrario, utilice false y se hará una copia.

Aquí hay un patrón de acceso que causa un problema.

 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)); 

¿Deben aparecer en la cabeza artículos con mayor prioridad? Esto no sucede en tu código si debería.

Después de los dos primeros agregados, el conteo es dos y el elemento de prioridad más baja está en la cabecera ( 0 1 , conteo: 2 ). La siguiente eliminación toma el elemento de cabeza disminuyendo el conteo. Lo que queda es el elemento de prioridad 1 ( 1 , cuenta: 1 ). El problema es agregar otro elemento de prioridad 0, en realidad no agrega nada a la cola y el conteo aún se incrementa ( 1 , conteo: 2 ). Luego, dado que la cola ha registrado que hay 2 elementos cuando en realidad solo hay 1, la eliminación al final falla.

El problema radica en su recorrido de la cola. Más específicamente, donde se inicia (el puntero anterior) no se actualiza después de eliminar. Después de una eliminación, sigue apuntando al nodo “eliminado”. En efecto, todos los agregados de procedimientos se agregarán al final del nodo previamente eliminado, dejando la cola real en un estado inconsistente. Esta es una de las razones por las que es una buena idea liberar constantemente la memoria cuando no se necesita y configurar el puntero a NULL después.

Además de los problemas que mencionó paxdiablo , también se olvida de actualizar antes de beforefirst->next en el caso de que elimine la cabecera de la cola. Esto es lo que está pasando:

 Antes de queue_remove:

   antes de la cola de la cabeza
        |  |  |
        VVV
 + ------------- + + ------------- + + ------------- +
 |  marcador de posición |  -> |  x |  -> |  y |  -> NULL
 + ------------- + + ------------- + + ------------- +



 Después de queue_remove:

   antes de la cola de la cabeza
        |  |  |
        VVV
 + ------------- + + ------------- + + ------------- +
 |  marcador de posición |  -> |  x |  -> |  y |  -> NULL
 + ------------- + + ------------- + + ------------- +

queue_remove arreglar queue_remove para que antes de beforefirst->next apunta a head->next si head no es NULL (de lo contrario, NULL).

Debe corregir queue_add para que cambie también antes de primero si el elemento insertado está en la primera posición.

En general, no usaría before_first. Simplemente cambie sus bucles para verificar ptr a current == null y cambie el elemento de inicio para que sea el primero.

Debería eliminar todos los demás problemas también.

hth

Mario