Wie man in C typsichere generische Datenstrukturen schreibt

(danielchasehooper.com)

3 Punkte von GN⁺ 2025-07-01 | 2 Kommentare | Auf WhatsApp teilen

Auch in C lassen sich durch die Kombination aus Makros, void *, Flexible Array Membern und union typsichere generische Datenstrukturen bauen; das Beispiel zeigt die schrittweise Implementierung anhand einer verketteten Liste
Der Ansatz, typspezifische Header mehrfach zu includen, ist sicher, erschwert aber wegen makrogeneriertem Code das Nachverfolgen von Definitionen und Code Completion und kann Binärgröße sowie Build-Zeit erhöhen
Eine auf void * basierende Liste ist universell, verhindert aber keine Typfehler; wenn Knoten und Daten getrennt alloziert werden, entstehen zwei Allokationen pro Knoten und Cache-Misses
Speichert man die Daten mit einem Flexible Array Member im Knoten und kapselt List(type) in einer union, lässt sich Typinformation zur Compile-Zeit ohne Laufzeitkosten anhängen
Das Makro list_prepend gleicht über den ternären Operator den übergebenen Wert mit dem payload-Typ ab und erzwingt so Compile-Fehler; für den Rückgabe-Pointer-Typ kann __typeof__() verwendet werden

Ausgangspunkt für Generics in C

Ziel ist, in C typspezifische Listen wie List(int) oder List(Foo) deklarieren zu können, sodass beim Einfügen eines falschen Typs nicht kompiliert wird
Im Beispiel kann man in List(Foo) Werte vom Typ Foo einfügen, aber Code wie list_prepend(&foo_list, 7) mit einem anderen Typ kompiliert nicht
Innerhalb von list_for(item, &foo_list) kann item als Typ Foo * behandelt werden

Level 0: Generischer Header-Ansatz

Eine Möglichkeit ist, die Datenstruktur in einen Header zu schreiben und #include mehrfach auszuführen, wobei das Typmakro T jeweils geändert wird
list.h erzeugt auf Basis von T per Makro Typen und Funktionen wie FooListNode oder Foo_list_prepend
Dieser Ansatz ist generisch und typsicher, aber in der Nutzung recht sperrig
- Typen und Funktionen bestehen aus Makros, wodurch sich ihre Definitionen schwer auffinden lassen
- Code Completion funktioniert möglicherweise nicht gut
- Für jeden Typ entstehen identische Funktionskopien, was Binärgröße und Build-Zeit erhöht
- Statt eines einzigen list_prepend() muss man Funktionen mit Typpräfix wie Foo_list_prepend() oder int_list_prepend() verwenden
Für generische Funktionen, die typspezifische Codegenerierung benötigen, kann dieser Ansatz besser geeignet sein

Level 1: Liste auf Basis von `void *`

Wenn ListNode ein void *data enthält, kann es Daten vieler Typen aufnehmen
list_prepend(ListNode **head, void *data) speichert einfach den Daten-Pointer und ist daher leicht zu implementieren
Das Problem ist, dass diese Struktur nicht typsicher ist
Werden Knoten und Daten getrennt alloziert, steigen auch Speicher- und Performance-Kosten
- Pro Knoten sind zwei Allokationen nötig
- Der data-Pointer selbst verbraucht zusätzlichen Speicher
- Beim Traversieren der Liste kann es sowohl beim Zugriff auf den nächsten Knoten als auch auf die Daten zu Cache-Misses kommen
Im Beispielcode wird aus Vertrautheit malloc verwendet, tatsächlich wird aber die Nutzung einer Arena empfohlen; als weiterführendes Material dienen dieses Video und dieser Artikel

Level 2: Daten im Knoten selbst speichern

Statt void *data kann man ein Flexible Array Member verwenden, um die Daten direkt im Knoten abzulegen
struct ListNode enthält dann ListNode *next und char data[]; bei der Allokation wird in einem Schritt sizeof(* node) + data_size reserviert
list_prepend erhält die übergebenen Daten samt Größe und kopiert sie per memcpy nach node->data
So liegen next und die eigentlichen Daten im Speicher nahe beieinander, wodurch Allokations- und Cache-Probleme des void *-Ansatzes reduziert werden
Der Nachteil ist, dass der Aufrufer data_size mitgeben muss
Wenn man memcpy vermeiden möchte, kann list_alloc_front stattdessen einen Pointer auf den Datenbereich des Knotens zurückgeben, damit der Aufrufer den Speicher direkt initialisieren kann
Fragen zu Ausrichtung, Padding und Größenberechnung des data-Members sind ein eigenes Thema und werden im Beispiel nicht vertieft

Level 3: Typinformation mit `union` anhängen

Der zentrale Trick besteht darin, List(type) als union zu definieren und darin sowohl den eigentlichen Listen-Head als auch einen Pointer für Typinformation abzulegen

#define List(type) union { \
    ListNode *head; \
    type *payload; \
}

payload wird zur Laufzeit nicht verwendet, liefert aber Typinformation zur Compile-Zeit
Da union verwendet wird, verbraucht payload keinen zusätzlichen Speicher
So lassen sich typspezifische Listen wie List(Foo) foo_list oder List(int) int_list erzeugen

Typprüfung mit dem ternären Operator

Das Makro list_prepend ruft intern _list_prepend auf und gleicht mit einem ternären Operator die Typen von item und (list)->payload ab

#define list_prepend(list, item) \
    _list_prepend(&((list)->head), \
                  (1 ? (item) : (list)->payload), \
                  sizeof(*(list)->payload))

Wenn die beiden möglichen Typen des ternären Operators nicht zusammenpassen, meldet der Compiler einen Typkonflikt
Übergibt man zum Beispiel an List(Foo) einen Bar *, markiert Clang die Pointer-Typen Foo * und Bar * als unvereinbar
Dasselbe Makro übergibt über sizeof(*(list)->payload) auch automatisch die Größe des gespeicherten Typs
Die eigentliche Arbeit übernimmt eine generische interne Funktion wie _list_prepend(ListNode **head, void *data, size_t data_size)

`typeof()` für den Rückgabetyp

Wenn eine generische Funktion einen internen Daten-Pointer zurückgeben soll, kann der Rückgabewert vom Typ void * mit __typeof__() auf den payload-Typ gecastet werden

#define list_alloc_front(list) \
    (__typeof__((list)->payload))_list_alloc_front(&(list)->head, sizeof(*(list)->payload))

__typeof__() wird von Clang, GCC und MSVC ab Version 19.39 unterstützt
Vor seiner Aufnahme in C23 war __typeof__() eine optionale Erweiterung
Bei Compilern ohne __typeof__(), etwa älteren MSVC-Versionen vor 19.39, kann weiterhin die auf dem ternären Operator basierende Typprüfung verwendet werden
Eine typsichere Rückgabe ist auch über ein auf payload basierendes Allokationsmuster möglich, die Details der Implementierung werden jedoch ausgelassen

Frühere Methode und Hinweise zur Sprachdefinition

Eine frühere Variante rief _list_prepend auf, indem sie es in einen Funktionspointer-Typ castete, der __typeof__((list)->payload) enthielt
Der Aufruf über einen gecasteten Funktionspointer ist technisch gesehen undefiniertes Verhalten, gilt auf modernen Compilern und Plattformen in der Praxis aber als unproblematisch
Der aktuelle Ansatz erzwingt Fehler nicht mehr über Funktionspointer-Casts, sondern über Typgleichheit im ternären Operator

Das Problem beim Übergeben von `List(Foo)` als Argument

C-Compiler müssen zwei List(Foo)-Definitionen mit identischer Struktur nicht zwingend als denselben Typ behandeln

List(Foo) a;
List(Foo) b = a; // error

Auch wenn man eine Funktion als void my_function(List(Foo) list) definiert und dann my_function(a) aufruft, kann ein Fehler wegen inkompatibler Typen auftreten
Die Lösung besteht darin, dem Typ per typedef einen Namen zu geben

typedef List(Foo) ListFoo;

ListFoo a;
ListFoo b = a; // ok

void my_function(ListFoo list);
my_function(a); // ok

Für lokale Variablen kann weiterhin die Form List(Foo) local_foo_list verwendet werden
In GCC 15 und Clang gegen Ende 2025 sollen durch eine Regeländerung strukturell identische Typen mit demselben Tag-Namen als derselbe Typ behandelt werden

Auch auf andere Datenstrukturen anwendbar

Dieselbe Technik lässt sich nicht nur auf Listen, sondern auch auf Maps, Arrays, Binärbäume und andere Datenstrukturen anwenden
Sie kann auch auf Datenstrukturen erweitert werden, die mehrere zusammengehörige Typen benötigen
So kann eine Hash-Map zum Beispiel ihre interne Struktur sowie Schlüssel- und Werttyp gemeinsam in einer union halten

#define Map(key_type, value_type) union { \
    MapInternal map; \
    key_type *key; \
    value_type *value; \
}

stb_ds.h ist ebenfalls ein Beispiel für typsichere generische Datenstrukturen, verwendet für Arrays und Maps aber C-Arrays, sodass manche Typfehler nicht beim Übergeben eines Werts, sondern erst bei der Array-Zuweisung erkannt werden

2 Kommentare

click 2025-07-01

Da fragt man sich schon, ob man dann nicht einfach Zig verwenden sollte?

GN⁺ 2025-07-01

Hacker-News-Kommentare

Im Code von Level 2 ist uint64_t data[]; für Typen mit Alignment-Anforderungen größer als uint64_t falsch und für kleinere Typen verschwenderisch. Ein Beispiel dafür ist eine ilp32-ABI auf einer 64-Bit-Architektur
Der Code von Level 3 müsste int main() { List(Foo) foo_list = {NULL}; sein
Wenn man mangels typeof einen Workaround verwendet, kann man nichts zurückgeben, und weil == symmetrisch ist, erlaubt dieser Workaround auch const-bezogene Fehler
Auch payload kann man nicht sicher weglassen. Man braucht es, um die korrekte Größe zu kennen. Wenn man zu List(int64_t) ein int32_t hinzufügen will, sollte das möglich sein, aber man kennt das sizeof dieses int32_t nicht. Damit dieser Code korrekt funktioniert, fehlt noch einiges
Derzeit haben Generics in C zwei große Einschränkungen. Erstens ist die Delegation an eine vtable funktional begrenzt, weil Structs keine Makros enthalten können, sondern nur Funktionen. Zweitens muss man, um Overhead zu vermeiden, an eine externe vtable delegieren, und dafür muss man alle Typen, die die vtable verwenden, vorwärts deklarieren
Die beste Lösung, die ich bisher gefunden habe, war, in einem Forward-Header, der den typedef deklariert, nur static-Funktionen zu deklarieren, aber nicht zu definieren. In GCC und Clang tritt die Warnung „undefined static“ zu unterschiedlichen Zeitpunkten auf, wenn man den Header eines bestimmten Typs in einer Translation Unit nicht eingebunden hat
Man kann sich zum Beispiel eine Funktion vorstellen, die struct SizedBuffer {void *p; size_t len;}; oder struct BoundedBuffer {void *begin; void *end;}; aus unterschiedlichen Headern sowie jeweils deren const-Versionen akzeptiert
- Wegen des Problems, dass man für die Delegation an eine externe vtable alle Typen vorwärts deklarieren muss, wurde im Apache-Clownfish-Projekt, an dem ich früher beteiligt war, dafür sogar ein eigener Compiler gebaut
  Anfangs wurden .h-Dateien geparst, aber schließlich erschien es sinnvoller, mit .cfh eine kleine Header-Sprache namens „Clownfish Header“ zu schaffen
  Um die CharBuf-Version der im Elternteil Obj definierten Methode Clone aufzurufen, wurde folgender Code erzeugt
  
  typedef cfish_CharBuf*
  (*CFISH_CharBuf_Clone_t)(cfish_CharBuf* self);
  
  extern uint32_t CFISH_CharBuf_Clone_OFFSET;
  
  static inline cfish_CharBuf*
  CFISH_CharBuf_Clone(cfish_CharBuf* self) {
  const CFISH_CharBuf_Clone_t method
  = (CFISH_CharBuf_Clone_t)cfish_obj_method(
  self,
  CFISH_CharBuf_Clone_OFFSET
  );
  return method(self);
  }
  
  Verwendet wurde es so
  
  cfish_CharBuf *charbuf = cfish_CharBuf_new();
  cfish_CharBuf *clone = CFISH_CharBuf_Clone(charbuf);
  
  Das Ziel von Clownfish war es, ein Objektmodell als kleinsten gemeinsamen Nenner für verschiedene Bindings dynamischer Sprachen bereitzustellen, und die .cfh-Dateien wurden auch genutzt, um Typen für die Binding-Sprachen abzuleiten. Trotzdem war die Menge an erzeugtem Boilerplate-Code zur Vermeidung der genannten Probleme wirklich absurd groß
  Deshalb verzichten fast alle auf Typsicherheit und verwenden stattdessen einfach einen void*-Cast auf das Aufrufziel
  https://github.com/apache/lucy-clownfish
- In C bedeutet int main() nicht, dass keine Argumente angenommen werden, sondern dass eine unbekannte Anzahl von Argumenten angenommen wird. Wenn man ausdrücken will, dass keine Argumente angenommen werden, muss man int main(void) schreiben. Leute, die C++ verwenden, vergessen das oft
- Es wäre schön, wenn sich union assoziativ erweitern ließe. Also so, dass ein Typ sich selbst als Teil derselben Union wie andere Typen deklarieren kann, ohne dass man alle möglichen Typen zentral an einer Stelle vorab deklarieren muss
- Auch malloc(sizeof(*node) + data_size); kann wegen Padding problematisch sein. Die berechnete Größe könnte zu klein werden
Widerspruch
Ich habe einmal mit trick#0 aus dem Artikel einen kompletten C-Dialekt gebaut. Ein generischer Binär-Heap steht zum Beispiel hier: https://github.com/gritzko/librdx/blob/master/abc/HEAPx.h
Die Syntax ist zwar etwas schwerfällig, aber der große Vorteil ist, dass man am Ende gewöhnliche, vorhersehbare und leicht zu optimierende normale C-Structs erhält. Das ist Code, den ein Compiler geradezu zum Frühstück verspeist
Andere Ansätze brauchen letztlich doch void* und Größenberechnung des Speichers zur Laufzeit, und Makros muss man sowieso definieren
- Ich bin der Autor. Binär-Heaps und verkettete Listen haben unterschiedliche Anwendungsfälle. Ein Binär-Heap muss zum korrekten Speichern die eingefügten Daten lesen, eine verkettete Liste muss das nicht
  Wenn ich einen generischen Binär-Heap verwendet hätte, hätte ich die Alternativen vielleicht anders abgewogen. Ich habe das auch in einer Fußnote erwähnt
- Es gibt tatsächlich mehrere gute Gründe, Header-Implementierungen zu bevorzugen. Anders als Makro-Funktionen kann man in Header-Code im Debugger hineinsteigen, und die Typsichtbarkeit des Debuggers ist ebenfalls besser, was das Debugging verbessert
  Weil jede Instanz monomorphisiert wird, hat der Compiler auch mehr Optimierungsspielraum, und wegen der variablen Größe muss man keinen Laufzeitpreis zahlen. Bei fester Größe kann man generische Structs auch auf dem Stack ablegen
  Mindestens zwei der vom Autor genannten Probleme lassen sich umgehen. Namen kann man mit einem einfachen Name-Mangling-Makro von Bar_func(args…) zu func(Bar)(args…) ändern. Die Bloat im Binärformat lässt sich teilweise reduzieren, indem man weak symbols nutzt, sodass der Linker zwischen Translation Units geteilte Funktionen deduplizieren kann
  Generische Container für Zeigertypen haben andere Probleme, aber die kann man mit typedefs oder Typ-Aliassen umgehen
  In C sind intrusive Datenstrukturen immer noch bequemer, aber im Debugger sind sie eine Qual
Funktions-Typ-Casting setzt voraus, dass der Zeiger auf den Eintragstyp, zum Beispiel Foo*, dieselbe Darstellung wie void* hat, aber der C-Standard garantiert das nicht. Im Sprachgebrauch des Standards sind die beiden Typen nicht „kompatibel"
Daher ist es undefiniertes Verhalten, eine Funktion mit dem umgewandelten Typ aufzurufen. Selbst wenn die Zeigerdarstellung zufällig gleich ist, beeinflusst das auch die Alias-Analyse des Compilers. Dazu ist auch [0] lesenswert
Das Casten von Funktionen mit unterschiedlichen Argumenttypen scheint der Kern der Typsicherheit generischer Aufrufe zu sein, aber ich weiß nicht, ob sich dieses Problem beheben lässt
https://news.ycombinator.com/item?id=44421185
- Das wurde in der Fußnote behandelt. Das Casting ist nicht der Kern der Typsicherheit. Lies einfach den ganzen Artikel
Wenn man „C mit Generics“ will, sollte man dann nicht statt solcher Verrenkungen einfach C++ verwenden?
- Weil man in Legacy-Projekten arbeitet, die an Sicherheitsvorgaben und andere Qualitätssicherungsanforderungen gebunden sind. Eine nach C++ portierte Lösung kann man nicht einfach in der nächsten Version ausrollen, oft nicht einmal in der zehnten. Also muss man es unter Umständen irgendwie zum Laufen bringen, bis es möglich wird
  Für neue Projekte kann man aber Standards und Erwartungen so festlegen, dass C++ verwendet wird, und genau das tun wir auch, mit einer Vorgabe für ein bestimmtes std
  Diese Haltung sieht man auf Hacker News ziemlich oft; sie wirkt fast wie „Werd einfach besser“. Ich finde, hier braucht es deutlich mehr Kontext
- In vielen Einsatzbereichen von C würde der Wechsel zu C++ sogar noch mehr Verrenkungen erfordern
- Manche hassen C++ einfach bis ins Mark, deshalb taucht diese Art Arbeit immer wieder auf
  Selbst nachdem Microsoft begonnen hatte, Linux und freie Open-Source-Software positiver zu sehen, war es wirklich enttäuschend, dass man sich nicht von der Haltung „C++ ist die Zukunft“ gelöst hat
  https://herbsutter.com/2012/05/03/reader-qa-what-about-vc-an...
  https://devblogs.microsoft.com/cppblog/c11-and-c17-standard-...
  Inzwischen ist das wegen neuer Richtlinien bei Microsoft zu C und C++ infolge staatlicher und Cyber-Regulierung nicht mehr besonders wichtig
  https://azure.microsoft.com/en-us/blog/microsoft-azure-secur...
  https://blogs.windows.com/windowsexperience/2024/11/19/windo...
- Die ehrliche Antwort ist: weil das hier mehr Spaß macht
- Wenn sich in C mit ein paar Workarounds dasselbe Ergebnis erreichen lässt, warum dann C++ verwenden?
Netter Trick. Ich verwende das schon in meiner experimentellen Bibliothek https://github.com/uecker/noplate/blob/main/src/list.h
- Du scheinst jemand zu sein, der das wissen könnte: Siehst du eine Möglichkeit, diesen Ansatz auch auf intrusive Datenstrukturen anzuwenden?
  Also statt die Daten in den Knoten zu legen, die Knotenstruktur in die Daten einzubetten, sodass ein Objekt nebenbei in mehreren Containern liegen kann
Bei der Aussage „Strukturell identische Typen werden in GCC 15 und im späteren Clang von 2025 dank einer Regeländerung als derselbe Typ behandelt“ ist Vorsicht geboten
Nach der neuen Regel werden nur Unionen mit Tag als derselbe Typ betrachtet, und auch nur dann, wenn sowohl Struktur als auch Tag gleich sind
Das List(T)-Makro müsste so geändert werden, dass es für jedes unterschiedliche T einen anderen Tag erzeugt. Für einfache Ein-Wort-Typen ist das mit ## leicht, aber schon bei etwas komplexeren Dingen wie char-Zeigern, also Strings, ist es unmöglich
Natürlich könnte man verlangen, dass alle Typen vor der Verwendung mit List per typedef definiert werden, aber das würde die Allgemeingültigkeit stark einschränken

typedef char *str;
List(str) my_list_of_str;
List(str) tokenize(str input) {...}
- Ich verstehe nicht, was mit „Nur Unionen mit Tag werden als derselbe Typ betrachtet“ gemeint ist. Ist eine Tagged Union nicht einfach ein Entwurfsmuster?
Der übliche Begriff für ein Mitglied, das nichts tut und nur einen Typ trägt, ist wohl type witness. Überraschenderweise gibt es dazu viel weniger Literatur, als ich erwartet hätte
- Einen ähnlichen Begriff gibt es mit phantom type, wenn ein Typparameter im tatsächlichen Variablentyp überhaupt nicht verwendet wird
  Ich habe das vor allem in Haskell gesehen und in Scala auch einmal verwendet, um eine Typ-Hierarchie nachzubilden, die es im eigentlichen Typsystem gar nicht gibt
  In gewisser Weise ähnelt auch dieser Union-Trick einem phantom type, weil der Hilfstyp tatsächlich überhaupt nicht verwendet wird
Es gibt auch den Ansatz aus dem Linux-Kernel. Dabei wird struct list_head als Listeninformation in die typspezifische Struktur eingebettet
https://kernelnewbies.org/FAQ/LinkedLists
- Die Namen LIST_HEAD_INIT und INIT_LIST_HEAD sind verwirrend
Wenn ich so etwas machen müsste, würde ich lieber direkt C++-Templates verwenden
In D macht man das so

struct ListNode(T) {
ListNode* next;
T data;
}

T!int node;

Warum sich mit dem C-Präprozessor abmühen? Präprozessor-Makros zu verwenden ist so, als würde man bei der Feinarbeit in der Schreinerei statt einer Nagelpistole einen Hammer benutzen. Eine Nagelpistole ist 10-mal schneller, schlägt den Nagel jedes Mal präzise ein und hinterlässt auch keine halbmondförmigen Druckstellen am Werkstück.

In diesem Artikel geht es um C. In manchen Projekten muss man zwingend C verwenden.
Man muss nicht nur den Hammer verwenden, sondern kann zusätzlich einen Durchschlag benutzen. Einen Ziernagel mit dem Hammer etwa 1/8 Zoll weit herausstehen lassen und ihn dann mit dem Durchschlag vollständig versenken.