Ausrichtung des C-Struktur-Vererbungszeigers

Question 1

Hintergrund

Ich habe hauptsächlich zu Lernzwecken eine grundlegende Datenstruktur für verknüpfte Listen erstellt. Ein Ziel der Liste war, dass sie mit unterschiedlichen Datenstrukturen umgehen kann. Daher habe ich mich an der Strukturzusammensetzung versucht, um “Vererbung” in C zu simulieren. Hier sind die Strukturen, die die Grundlage für meine verknüpfte Liste bilden.

typedef struct Link {
    struct Link* next;
    struct Link* prev;
} Link;

typedef Link List;

In meiner Implementierung habe ich mich für einen Sentinel-Knoten entschieden, der sowohl als Kopf als auch als Ende der Liste dient (weshalb Link == List).

Damit die Liste tatsächlich Daten verarbeitet, enthält eine Struktur einfach die Link-Struktur als erstes Mitglied:

typedef struct {
    Link link;
    float data;
} Node;

Die verknüpfte Liste sieht also so aus.

         ┌───┬───┬───┐     ┌───┬───┐     ┌───┬───┬───┐     
... <--->│ P │ N │ D │<--->│ P │ N │<--->│ P │ N │ D │<---> ... 
         └───┴───┴───┘     └───┴───┘     └───┴───┴───┘
         End Node          myList        First Node

List myList;
Node node1 = {{}, 1.024};
....
Node nodeN = {{}, 3.14};

list_init(&myList) // myList.next = &myList; myList.prev = &myList;
list_append(&myList, &node1);
....
list_append(&myList, &nodeN);

Frage

Um diese Liste zu durchlaufen a Node Zeiger zeigt zunächst auf die Erster Knoten. Er durchquert dann die Liste, bis er wieder auf den Wächter zeigt, und stoppt dann.

void traverse()
{
    Node* ptr;
    for(ptr = myList.next; ptr != &myList; ptr = ptr->link.next)
    {
        printf("%f ", ptr->data);
    }
}

Meine Frage bezieht sich auf die Leitung ptr != &myList. Gibt es ein Zeigerausrichtungsproblem mit dieser Zeile?

Die for-Schleife erzeugt korrekt die Warnungen: (warning: assignment from incompatible pointer type und warning: comparison of distinct pointer types lacks a cast), das zum Schweigen gebracht werden kann, indem man tut, was es sagt, und zu ihm wirkt Node*. Aber ist das ein DumbThingToDo™? Ich greife nie zu ptr->data wenn es darauf hindeutet &myList da die Schleife einmal endet ptr == &myList.

TLDR

In C-Strukturen a Base* kann auf a hinweisen Derived wenn Base ist das erste Mitglied Derived. Kann A Derived* zeigen auf a Base wenn keine Derived auf bestimmte Mitglieder zugegriffen wird?

BEARBEITEN: Relevante Funktionsaufrufe durch ihren entsprechenden Inline-Code ersetzt.

Question 2

Kudos für Ihre Präsentation.

Ich denke, Ihre Implementierung sollte gut funktionieren, da C garantiert, dass die Adresse einer Struktur die Adresse ihres ursprünglichen Mitglieds ist. Abgesehen von den Aussagen, die C über die Ausrichtung von Strukturmitgliedern macht, sollte diese Garantie bedeuten, dass, solange Ihre Implementierung Link immer als erstes Mitglied setzt, dies keine Ausrichtungsprobleme verursachen sollte.

ab hier: C99 §6.7.2.1:

13 Innerhalb eines Strukturobjekts haben die Mitglieder, die keine Bitfelder sind, und die Einheiten, in denen sich Bitfelder befinden, Adressen, die in der Reihenfolge aufsteigen, in der sie deklariert werden. Ein geeignet umgewandelter Zeiger auf ein Strukturobjekt zeigt auf sein Anfangselement (oder, wenn dieses Element ein Bitfeld ist, dann auf die Einheit, in der es sich befindet) und umgekehrt. Innerhalb eines Strukturobjekts kann es unbenannte Auffüllungen geben, jedoch nicht an seinem Anfang

Das sollte das sein, was du damit sagen wolltest Base * und Derived *obwohl es so etwas in reinem C nicht gibt. Sie sind nur Strukturen, die zufällig das gleiche Speicherlayout haben.

Allerdings finde ich es etwas spröde, das so zu implementieren, da Node und Link direkt voneinander abhängen. Wenn Sie die Struktur von Node ändern würden, würde Ihr Code ungültig. Im Moment sehe ich keinen Sinn darin, ein Extra zu haben struct Linkabgesehen davon, dass Sie einfach einen neuen Knoten für einen neuen Typ unter Wiederverwendung von Link schreiben können.

Es gibt tatsächlich eine Linked-List-Implementierung, die mir sofort in den Sinn kam, als ich Ihren Beitrag sah, und die auf eine Weise funktioniert, die der Art und Weise, wie Sie Ihre Liste verwenden möchten, sehr ähnlich ist: die Kernel-Liste

Es verwendet dasselbe Listenelement (list_head):

struct list_head {
    struct list_head *next, *prev;
};

Es enthält dieses Funktionsmakro:

#define list_for_each_entry(pos, head, member)                          \
      for (pos = list_first_entry(head, typeof(*pos), member);        \
           &pos->member != (head);                                    \
           pos = list_next_entry(pos, member))

Wenn Sie sich die Art und Weise ansehen, wie das Makro implementiert ist, werden Sie feststellen, dass es eine Iteration über die Einträge einer Liste anbietet, ohne etwas über das Layout der Einträge zu wissen, in denen die Liste enthalten ist. Vorausgesetzt, ich interpretiere Ihre Absicht richtig, denke ich, dass dies der Fall ist so wie du es haben möchtest.

Question 3

In C-Strukturen kann eine Base* auf ein Derived zeigen, wenn Base das erste Element in Derived ist. Kann ein Derived* auf eine Base zeigen, wenn auf keines der Derived-spezifischen Mitglieder zugegriffen wird?

Wenn Sie meinen “kann ein abgeleitetes * auf eine beliebige Basis zeigen (einschließlich einer, die kein erstes Mitglied eines abgeleiteten Objekts ist)”, dann: Technisch gesehen nein. Mein Verständnis von Fehlerbericht Nr. 74 Die Ausrichtungsanforderungen können unterschiedlich sein.

F: Wenn eine Struktur ein Feld vom Typ t hat, können sich die Ausrichtungsanforderungen des Felds von den Ausrichtungsanforderungen von Objekten desselben Typs unterscheiden, die keine Mitglieder von Strukturen sind? Wenn die Antwort auf (a) „Ja“ lautet, dann sollte gegebenenfalls davon ausgegangen werden, dass die verbleibenden Fragen sowohl für Objekte innerhalb von Strukturen als auch für Objekte außerhalb von Strukturen gestellt wurden.

A: In Unterabschnitt 6.1.2.5 heißt es: „… Zeiger auf qualifizierte oder nicht qualifizierte Versionen kompatibler Typen müssen die gleichen Darstellungs- und Ausrichtungsanforderungen haben.“ In Unterabschnitt 6.5.2.1 heißt es: „Jedes Nicht-Bitfeld-Mitglied einer Struktur oder eines Vereinigungsobjekts wird in einer implementierungsdefinierten Weise ausgerichtet, die seinem Typ entspricht.“ Und später: ‘Daher kann es innerhalb eines Strukturobjekts unbenannte Auffüllungen geben, … je nach Bedarf, um die entsprechende Ausrichtung zu erreichen.’ a) Es ist möglich, dass eine Implementierung verallgemeinerte Anforderungen angibt, um Abschnitt 6.1.2.5 zu erfüllen. Diese Anforderungen können unter Verwendung des implementierungsdefinierten Verhaltens, das in Unterabschnitt 6.5.2.1 zur Verfügung gestellt wird, weiter verstärkt werden. Ja, die Ausrichtungsanforderungen können unterschiedlich sein.

Question 4

Ich habe dies in den Kommentaren zu Ouahs Antwort geschrieben, aber ich werde es als eigenständige Antwort präsentieren.

Es ist wahr, wie ouah den Code in Ihrer Frage schreibt könnte Theoretisch ein Ausrichtungsproblem haben, wenn Sie sich an den C-Standard halten. Ich glaube jedoch nicht, dass es eine einzige Architektur gibt, auf der Ihr Code wahrscheinlich (oder unwahrscheinlich) ausgeführt wird, deren ABI solche Ausrichtungsmuster aufweist. Zumindest keine, die ich kenne, mit Sicherheit, und dazu gehören Erfahrungen mit ein paar verschiedenen Desktop- und eingebetteten Architekturen. Ich kann mir auch keine Architektur vorstellen, die solchen Alignment-Eigenschaften etwas abgewinnen würde.

Es ist auch erwähnenswert, dass dieses Muster in der Praxis tatsächlich ziemlich häufig verwendet wird; Es ist wie die Tatsache, dass man immer passen kann ints in Hinweisen, da es durch keinen plattformübergreifenden Standard garantiert wird, aber es gibt praktisch keine Plattform, auf der es nicht wahr ist, und die Leute tun es die ganze Zeit.