Implémentation d'une file d'attente FIFO en C

Question

Pour une application embarquée, j'essaie d'implémenter une file d'attente FIFO (first-in, first-out) à l'aide de ANSI C. La façon la plus directe de le faire semble être linked-list, de sorte que chaque structure contienne un pointeur vers le suivant dans la file d'attente. Par conséquent je définis la structure elle-même comme:

typedef enum { LED_on, LED_off, etc } Action; 
typedef struct Queued_Action QueuedAction; 

struct Queued_Action 
{ 
    Action  action; 
    int   value; 
    QueuedAction *nextAction; 
}; 

Jusqu'ici tout va bien. Si je définis des pointeurs vers les premier et dernier éléments dans la file d'attente:

QueuedAction *firstAction; 
QueuedAction *lastAction; 

... je voudrais être en mesure d'ajouter une nouvelle action à la file d'attente en déclarant (par exemple):

if (!add_action_to_queue(LED_on, 100, &lastAction)) 
    printf("Error!\n); 

... donc, à son retour, lastAction serait un pointeur vers la dernière action nouvellement créée dans la file d'attente. D'où la routine pour ajouter l'action à la file d'attente ressemblerait à ceci:

int add_action_to_queue(Action newAction, int newValue, QueuedAction **lastAction) 
{ 
    QueuedAction *newQueuedAction; 

    // Create a new action in memory 
    if ((newQueuedAction = (QueuedAction *)malloc(sizeof(QueuedAction))) == NULL) 
     return 0; 

    // Make the old 'lastAction' point to the new Action, 
    // and the new Action to point to NULL: 
    *lastAction -> nextAction = newQueuedAction; 
    newQueuedAction -> nextAction = NULL; 
    newQueuedAction -> action = newAction; 
    newQueuedAction -> value = newValue; 

    // Designate the new Action as the new lastAction: 
    *lastAction = newQueuedAction; 
    return 1; 
} 

tout irait bien et dandy, à l'exception de ce code ne compilera pas. L'erreur est à la ligne en disant

*lastAction -> nextAction = newQueuedAction; 

... où le compilateur prétend l'élément à gauche du « -> » est pas un struct valide. Sûrement, cependant, cela doit être. Si en fait je fais ce qui devrait être une distribution entièrement redondante:

fakeAction = (QueuedAction *)(*lastAction); 
fakeAction -> nextAction = newQueuedAction; 

... alors le compilateur est plutôt content. Cependant, je suis inquiet que le message d'erreur fasse allusion à quelque chose de subtil que je puisse faire mal ici. Donc (pour arriver au point), quelqu'un peut-il me dire pourquoi le compilateur n'est pas content, et s'il y a une meilleure façon de faire ce que j'essaie de faire ici.

Answer 1

Avez-vous essayé:

(*lastAction) -> nextAction = newQueuedAction; 

Answer 2

Vous pouvez aussi le faire:

(*lastAction)->nextAction 

Je pense qu'il est une question de pecedence opérateur.

Answer 3

J'ai créé une petite bibliothèque capable de gérer les files d'attente. "UltraQueue"

Il est écrit en C++, mais est entièrement compatible avec ANSI C. Il peut être facilement converti en ANSI C si vous voulez vraiment.

Le code source est disponible via GIT.

Grtz

Answer 4

J'espère que cela vous aidera à l'avance. Tout d'abord, désolé pour mon anglais. Il pourrait y avoir plusieurs erreurs grammaticales ou ortographiques.

Le problème que je vois dans votre code est principalement que vous mélangez la définition d'un pointeur et l'implémentation du même.

De ANSI C à C99, même en C++ (non testé en C#), il y a un grand piratage en utilisant des pointeurs peut être utile à l'avance: pense que le pointeur est le premier élément d'un vecteur, la [0] un.

Un site expliquant ce concept est: http://boredzo.org/pointers/

Ce hack est une traduction nue, et une belle hacktool pour mieux comprendre les pointeurs.

Entrez en action, les garçons.

La fonction que vous utilisez pour ajouter des éléments dans une liste,

int add_action_to_queue(Action newAction, int newValue, QueuedAction **lastAction) 
{ 
    QueuedAction *newQueuedAction; 

    // Create a new action in memory 
    if ((newQueuedAction = (QueuedAction *)malloc(sizeof(QueuedAction))) == NULL) 
     return 0; 

    // Make the old 'lastAction' point to the new Action, 
    // and the new Action to point to NULL: 
    *lastAction -> nextAction = newQueuedAction; 
    newQueuedAction -> nextAction = NULL; 
    newQueuedAction -> action = newAction; 
    newQueuedAction -> value = newValue; 

    // Designate the new Action as the new lastAction: 
    *lastAction = newQueuedAction; 
    return 1; 
} 

contient des erreurs. tout, penser d'abord à l'aide

*lastAction -> ...; 

comme

lastAction[0] -> ...; 

Comme vous le voyez, vous ne pouvez pas utiliser le - pour accéder aux éléments internes opérateur>.

La même chose se produit ici:

lastAction[0] = newQueuedAction; 

Vous ne pouvez pas copier un pointeur à l'intérieur d'un struct. lastAction, en utilisant ce hack pour mieux comprendre, n'est plus un pointeur - en fait, c'est le contenu du premier élément de la structure que le compilateur a assigné dedans - donc vous devez changer cette ligne aussi pour changer le valeur du pointeur:

lastAction = newQueuedAction; 

en utilisant cette traduction et les annotations, votre code sera, maintenant:

int add_action_to_queue(Action newAction, int newValue, QueuedAction **lastAction) 
{ 
    QueuedAction *newQueuedAction; 

    // Create a new action in memory 
    if ((newQueuedAction = (QueuedAction *)malloc(sizeof(QueuedAction))) == NULL) 
     return 0; 

    // Make the old 'lastAction' point to the new Action, 
    // and the new Action to point to NULL: 
    lastAction[0] -> nextAction = newQueuedAction; 
    newQueuedAction -> nextAction = NULL; 
    newQueuedAction -> action = newAction; 
    newQueuedAction -> value = newValue; 

    // Designate the new Action as the new lastAction: 
    lastAction[0] = newQueuedAction; 
    return 1; 
} 

les erreurs sont, maintenant, visibles: vous essayez d'utiliser le - opérateur> à tort . Cela signifie que votre code sera modifié de deux façons:

• Utilisez le -> opérateur

Il ressemble à ceci:

int add_action_to_queue(Action newAction, int newValue, QueuedAction **lastAction) 
{ 
    QueuedAction *newQueuedAction; 

    // Create a new action in memory 
    if ((newQueuedAction = (QueuedAction *)malloc(sizeof(QueuedAction))) == NULL) 
     return 0; 

    // Make the old 'lastAction' point to the new Action, 
    // and the new Action to point to NULL: 
    lastAction -> nextAction = newQueuedAction; 
    newQueuedAction -> nextAction = NULL; 
    newQueuedAction -> action = newAction; 
    newQueuedAction -> value = newValue; 

    // Designate the new Action as the new lastAction: 
    lastAction = newQueuedAction; 
    return 1; 
} 

• Utilisez le . opérateur avec le [0] pirater

Il ressemble à ceci:

int add_action_to_queue(Action newAction, int newValue, QueuedAction **lastAction) 
{ 
    QueuedAction *newQueuedAction; 

    // Create a new action in memory 
    if ((newQueuedAction = (QueuedAction *)malloc(sizeof(QueuedAction))) == NULL) 
     return 0; 

    // Make the old 'lastAction' point to the new Action, 
    // and the new Action to point to NULL: 
    lastAction[0].nextAction = newQueuedAction; 
    newQueuedAction[0].nextAction = NULL; 
    newQueuedAction[0].action = newAction; 
    newQueuedAction[0].value = newValue; 

    // Designate the new Action as the new lastAction: 
    lastAction = newQueuedAction; 
    return 1; 
} 

Et ne pas oublier d'effacer le == NULL le code, vous rencontrerait avec un passif-aggressif programmeur qui définit NULL comme autre chose. Utilisez toujours des accolades pour assurer l'extensibilité. Cette ligne est seulement une recommandation de style de code.

Hope it helps,