Pointeur de structure jette

J’essaie d’implémenter une liste chaînée comme ceci:

typedef struct SLnode { void* item; void* next; } SLnode; typedef struct DLnode { void* item; void* next; struct DLnode* prev; } DLnode; typedef struct LinkedList { void* head; /*SLnode if doubly_linked is false, otherwise DLnode*/ void* tail; /* here too */ bool doubly_linked; } LinkedList; 

Et je veux y accéder comme ça:

 void* llnode_at(const LinkedList* ll, size_t index) { size_t i; SLnode* current; current = ll->head; for(i = 0; i next; } return current; } 

Donc ma question est:

  • Suis-je autorisé à faire un casting entre ces structures tant que je n’ai access qu’aux membres communs? J’ai lu des opinions divergentes à ce sujet.
  • Puis-je également créer le prochain pointeur des types respectifs? Ou est-ce que ce serait UB de l’utiliser dans mon exemple, au cas où ce serait vraiment DLnode?

Si cela ne fonctionne pas, y a-t-il d’autres moyens de faire quelque chose comme ça? J’ai lu que les syndicats pourraient fonctionner, mais ce code devrait également être utilisé en C89 et, autant que je sache, un autre membre du syndicat que celui écrit en dernier est UB.

Vous essayez donc de construire des sous-classes en C. Une solution possible consiste à faire de la structure de base le premier élément de la structure enfant, car dans ce cas, le standard C permet explicitement de basculer entre ces 2 types:

6.7.2.1 Spécificateurs de structure et d’union

§ 13 … Un pointeur sur un object de structure, converti de manière appropriée, pointe vers son membre initial (ou si ce membre est un champ de bits, puis vers l’unité dans laquelle il réside), et inversement …

L’inconvénient est que vous avez besoin d’un casting dans la classe de base pour accéder à ses membres:

Exemple de code:

 typedef struct SLnode { void* item; void* next; } SLnode; typedef struct DLnode { struct SLnode base; struct DLnode* prev; } DLnode; 

Vous pouvez ensuite l’utiliser de cette façon:

  DLnode *node = malloc(sizeof(DLnode)); ((SLnode*) node)->next = NULL; // or node->base.next = NULL ((SLnode *)node)->item = val; node->prev = NULL; 

Vous pouvez le faire en toute sécurité si vous utilisez une union pour contenir les deux structures:

 union Lnode { struct SLnode slnode; struct DLnode dlnode; }; 

La section 6.5.2.3 de la norme C actuelle , ainsi que la section 6.3.2.3 de la norme C89, stipulent ce qui suit:

6 Une garantie spéciale est fournie afin de simplifier l’utilisation des unions: si une union contient plusieurs structures partageant une séquence initiale commune (voir ci-dessous), et si l’object union contient actuellement l’une de ces structures, il est autorisé à inspecter le partie initiale commune de l’un d’entre eux où qu’une déclaration du type complet de l’union soit visible. Deux structures partagent une séquence initiale commune si les membres correspondants ont des types compatibles (et, pour les champs de bits, les mêmes largeurs) pour une séquence d’un ou de plusieurs membres initiaux.

Les deux premiers membres des deux structures étant du même type, vous pouvez accéder librement à ces membres en utilisant l’un des membres du syndicat.

Ce que vous décrivez devrait être autorisé en vertu de la norme C. La confusion de la règle de séquence initiale commune découle d’un problème plus important: la norme ne spécifie pas quand l’utilisation d’un pointeur ou d’une valeur qui est visiblement dérivée d’un autre est considérée comme une utilisation de l’original. Si la réponse est “jamais”, alors tout membre d’une structure ou d’une union d’un type non-caractère serait pratiquement inutile, car le membre serait une lvalue dont le type ne serait pas valide pour accéder à la structure ou à l’union. Une telle vision serait clairement absurde. Si la réponse est “uniquement si elle est formée en appliquant directement”. “Ou” -> “sur le type struct ou union, ou un pointeur sur un tel type, la possibilité d’utiliser” & “sur struct et union Je pense que ce sharepoint vue n’est que légèrement moins absurde.

Je pense qu’il est clair que, pour être utile, le langage C doit être considéré comme permettant l’utilisation de valeurs dérivées dans au moins certaines circonstances. Que votre code, ou la plupart des codes reposant sur la règle de séquence initiale commune, soit utilisable dépend de la nature de ces circonstances.

Le langage serait plutôt idiot si le code ne pouvait pas utiliser de manière fiable les valeurs dérivées pour accéder aux membres de la structure. Malheureusement, même si ce problème était apparent en 1992 (il est à la base du rapport sur les défauts n ° 028, publié cette année-là), le comité n’a pas abordé la question fondamentale mais est parvenu à une conclusion correcte reposant sur une logique totalement absurde. depuis disparu et ajouté une complexité inutile sous la forme de “Types efficaces” sans jamais se préoccuper de définir le comportement de someStruct.member .

Par conséquent, il n’ya aucun moyen d’écrire un code qui fasse beaucoup avec des structures ou des unions sans s’appuyer sur plus de comportements que ce qui serait réellement garanti par une lecture littérale de la norme, que ces access soient faits en contraignant à void* ou en indiquant le bon sens. types de membres.

Si l’on interprète l’intention de 6.5p7 comme étant de permettre en quelque sorte aux actions utilisant une lvalue dérivée d’un type particulier d’accéder à des objects de ce type, du moins dans les cas n’impliquant pas de véritable aliasing , note de bas de page n ° 88 “L’objective de cette liste est de spécifier les circonstances dans lesquelles un object peut ou non être aliasé.”), et reconnaît que l’aliasing nécessite l’access à une région de stockage à l’aide d’une référence X à un moment où il existe une autre référence à partir de laquelle X n’a ​​pas été dérivé visiblement qui sera utilisée à l’avenir pour accéder au stockage de manière conflictuelle; les compilateurs qui respectent cette intention devraient donc pouvoir gérer du code comme le vôtre sans difficulté.

Malheureusement, gcc et clang semblent interpréter p6.5p7 comme indiquant qu’une valeur provenant d’un autre type devrait souvent être présumée incapable d’identifier les objects de ce type même, même dans les cas où la dérivation est entièrement visible.

Étant donné quelque chose comme:

 struct s1 {int x;}; struct s2 {int x;}; union u {struct s1 v1; struct s2 v2;}; int test(union u arr[], int i1, int i2) { struct s1 *p1 = &arr[i1].v1; if (p1->x) { struct s2 *p2 = &arr[i2].v2; p2->x=23; } struct s1 *p3 = &arr[i1].v1; return p3->x; } 

Au moment de l’ p1->x , p1 est clairement dérivé d’une lvalue de type union et devrait donc être capable d’accéder à un tel object, et les seules autres références existantes qui seront jamais utilisées pour accéder au stockage sont les références à ce type d’union. De même quand on p2->x à p2->x et p3->x . Malheureusement, gcc et clang interprètent N1570 6.5p7 comme une indication qu’ils doivent ignorer les relations entre le syndicat et les pointeurs de ses membres. Si gcc et clang ne peuvent pas être utilisés utilement pour permettre à un code comme celui ci-dessus d’accéder à la séquence initiale commune de structures identiques, je ne leur ferais pas confiance pour gérer de manière fiable des structures comme la vôtre.

Sauf si ou jusqu’à ce que la norme soit corrigée pour indiquer dans quels cas une valeur dérivée peut être utilisée pour accéder à un membre d’une structure ou d’un syndicat, il n’est pas clair que tout code qui fait quelque chose d’inhabituel avec des structures ou des syndicats soit censé fonctionner en particulier dialectes -fssortingct-aliasing de gcc et clang. D’autre part, si l’on reconnaît le concept de dérivation de lvalue comme fonctionnant dans les deux sens, un compilateur peut être justifié en supposant qu’un pointeur qui est d’un type de structure ne sera pas utilisé de manière à aliaser une référence à un autre, même si le pointeur est converti vers le second type avant utilisation. Je suggérerais donc que l’utilisation de void* serait moins susceptible de poser problème si la norme fixe jamais les règles.