Problème avec PriorityQueue en C

J’essaie d’écrire une PriorityQueue pour un projet ac. Le programme se bloque lorsque j’essaie de retirer des éléments de la queue; Cependant, je pense que le problème vient de la façon dont j’ai ajouté les éléments, comme si j’essayais d’accéder au premier élément de la liste après avoir ajouté le troisième élément, je tombais aussi en panne.

header de fichier:

#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 

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

Fondamentalement, l’erreur semble se produire lorsque j’essaie d’accéder à pq-> head-> data après avoir ajouté le troisième élément – je l’ai réduit aux zones commentées // ERREUR ICI. Cela me semble étrange, car l’ajout du troisième élément devrait fonctionner de la même manière que l’ajout du deuxième. De même, ni pq-> head == NULL ni pq-> head> data == NULL.

Je vois les problèmes suivants:

  • queue_free ne queue_free pas la mémoire pour son object beforeFirst .
  • add_priority ne libérera pas l’élément si l’allocation de données échoue. Cela n’a pas beaucoup d’importance depuis votre départ, mais ce serait bien si vous décidiez de renvoyer une erreur (en d’autres termes, cela arrêterait une fuite de mémoire).

Cependant, j’ai testé ce code en insérant un nouvel élément, un élément avant celui-ci, puis un élément à la fin, et cela me semble correct. Quelles valeurs de priorité insérez-vous (dans l’ordre)?

Et vous voudrez peut-être publier le code qui appelle ce code. Il est fort possible qu’il s’agisse d’un problème de corruption de mémoire sans rapport avec ce code réel.


Bien que j’apprécie votre tentative d’introduire les éléments beforeFirst pour que votre code soit agréable, vous devriez vraiment mordre la balle et vous en débarrasser. Sa suppression fera probablement plus que compenser la quantité minimale de code supplémentaire que vous devrez append pour gérer une liste vraiment vide. Ce code plus simple doit gérer tous les scénarios sans le traitement supplémentaire requirejs pour garder les pointeurs supplémentaires synchronisés.

Je n’ai pas réellement testé cela autrement que dans mon environnement mais cela devrait (espérons-le) fonctionner correctement:

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

N’oubliez pas que queue_add_priority crée une copie de la mémoire pour pouvoir la transmettre de manière dynamic ou autrement. Cette fonction n’accepte pas la responsabilité de libérer la mémoire allouée que vous lui transmettez. Si elle est allouée dynamicment, vous devez toujours la libérer vous-même. Cela a été fait de cette façon afin que vous puissiez passer dans n’importe quelle mémoire.

D’autre part, queue_remove vous renvoie simplement la mémoire allouée, vous êtes donc responsable de la libérer lorsque vous avez terminé. La mémoire que vous recevez aura toujours été obtenue via malloc .

Vous pouvez optimiser queue_add_priority sorte que vous puissiez spécifier que la mémoire en cours de queue_add_priority est allouée via malloc . Vous transférez la responsabilité en modifiant la première partie de la fonction:

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

En d’autres termes, définissez le paramètre final sur true si les données ont été obtenues via malloc et si vous acceptez de renoncer à leur responsabilité. Ainsi, la fonction prend simplement votre bloc de mémoire en l’état.

Sinon, utilisez false et une copie sera faite.

Voici un modèle d’access qui pose un problème.

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

Les articles de priorité plus élevée doivent-ils apparaître en tête? Cela ne se produit pas dans votre code s’il le devrait.

Après les deux premiers ajouts, le nombre est égal à deux et l’élément le moins prioritaire à la tête ( 0 1 , nombre: 2 ). La suppression suivante prend l’élément head décrémentant le compte. Ce qui rest est l’élément de priorité 1 ( 1 , compte: 1 ). Le problème est l’ajout d’un autre élément de priorité 0, cela n’ajoute rien à la queue et le nombre est toujours incrémenté ( 1 , nombre: 2 ). Ensuite, puisque la file a enregistré qu’il y a 2 éléments alors qu’il n’y en a qu’un, la suppression échoue.

Le problème réside dans votre traversée de la queue. Plus précisément, l’endroit où vous commencez (le pointeur beforefirst ) n’est pas mis à jour après une suppression. Après une suppression, il pointe toujours vers le nœud “supprimé”. En fait, tous les ajouts en cours s’appendont à la fin du nœud précédemment supprimé, laissant la queue réelle dans un état incohérent. C’est l’une des raisons pour lesquelles il est judicieux de libérer systématiquement de la mémoire lorsque cela n’est pas nécessaire et de définir ensuite le pointeur sur NULL .

En plus des problèmes mentionnés par paxdiablo , vous oubliez également de mettre à jour beforefirst->next dans le cas où vous supprimez la tête de la queue. Voici ce qui se passe:

 Avant queue_remove:

   avant la queue
        |  |  |
        VVV
 + ------------- + + ------------- + + ------------- +
 |  espace réservé |  -> |  x |  -> |  y |  -> NULL
 + ------------- + + ------------- + + ------------- +



 Après queue_remove:

   avant la queue
        |  |  |
        VVV
 + ------------- + + ------------- + + ------------- +
 |  espace réservé |  -> |  x |  -> |  y |  -> NULL
 + ------------- + + ------------- + + ------------- +

Vous devez corriger queue_remove pour que beforefirst->next pointe sur head->next si head est non-NULL (NULL sinon).

Vous devez corriger queue_add pour changer aussi before_first si l’élément inséré est à la première position.

Généralement, je n’utiliserais pas before_first. Il suffit de changer vos boucles pour vérifier que ptr est current == null et que l’élément start soit le premier.

Devrait éliminer tous les autres problèmes aussi.

hth

Mario