Wie man in C typsichere (generische) Datenstrukturen schreibt

 (danielchasehooper.com)
3 Punkte von GN⁺ 2025-07-01 | 2 Kommentare | Auf WhatsApp teilen
  • Dieser Artikel erklärt eine neue Methode, um typsichere (generische) Datenstrukturen in C zu erstellen
  • Beschrieben wird eine Technik, die Typinformationen mithilfe von union mit der Datenstruktur verknüpft, am Beispiel einer Implementierung einer Linked List
  • Dabei werden Unterschiede zu bestehenden generischen C-Mustern (Makros, void-Pointer, Flexible Array Member) sowie die Nachteile der jeweiligen Ansätze verglichen
  • Typprüfung zur Compile-Zeit ist möglich, sodass falsche Typverwendung im Voraus verhindert werden kann
  • Die neue Technik bietet klare und konsistente Funktions-/Datenstruktur-Schnittstellen wie foo_list

Einleitung

  • Es wird vorgestellt, wie sich generische Datenstrukturen in C typsicher erstellen lassen
  • Diese Technik verknüpft Typinformationen mithilfe von union zur Compile-Zeit mit der Datenstruktur
  • Sie lässt sich auf Maps, Arrays, binäre Bäume und andere Datenstrukturen anwenden und wird anhand einer einfachen Linked-List-Implementierung erklärt
  • Da viele Entwickler davon ausgehen, dass Generics in C nicht möglich sind, erfolgt die Erklärung schrittweise und leicht verständlich

Traditionelle makrobasierte Generics

  • Der traditionelle Ansatz zur Implementierung generischer Datenstrukturen in C verwendet Makros, um Namen von Strukturen, Funktionen und Typen zu erzeugen
  • Er wird erweitert, indem der Header der Datenstruktur für verschiedene Typen mehrfach eingebunden wird

Beispiele:

  • Verwendung von Makros (z. B. CONCAT, NODE_TYPE, PREPEND_FUNC), um typgerechte Struktur- und Funktionsnamen zu erzeugen
  • Für jeden Typ werden separate Funktionen und Strukturen generiert, sodass für Typen wie int und Foo jeweils eigene Datenstrukturdefinitionen entstehen

Nachteile:

  • Es ist schwer nachzuvollziehen, wo Typ- und Funktionsdefinitionen liegen (da sie per Makro erzeugt werden)
  • Code-Autovervollständigung lässt sich nur schwer nutzen
  • Mehrfach erzeugte identische Funktionen vergrößern Binärdateien und verlängern Build-Zeiten
  • Funktionsnamen benötigen ein Typpräfix (z. B. Foo_list_prepend)

Generic Schritt 1: void-Pointer-Ansatz

  • Der Datentyp der Datenstruktur wird auf void * gesetzt und damit typunabhängig gemacht
  • Das Feld data der Linked List wird als void * deklariert
  • Da keine Typprüfung möglich ist, können Typfehler zur Laufzeit auftreten; die Sicherheit zur Compile-Zeit ist gering
  • Ineffiziente Speicher- und Cache-Nutzung: Node und Daten werden getrennt alloziert, was unnötigen Overhead und mehr Cache-Misses verursacht

Generic Schritt 2: Inline-Speicher (Flexible Array Member)

  • Mithilfe von Flexible Array Member werden statt eines Pointers die Daten selbst zusammen mit dem Node gespeichert
  • Pro Node genügt eine einzige Allokation, und Daten sowie next-Pointer liegen im Cache nah beieinander
  • Dieser Ansatz erfordert die Übergabe von Größeninformationen etwa für memcpy, verbessert aber durch ein konsistentes Speicherlayout die Performance
  • Mit der Funktion list_alloc_front lässt sich eine Struktur auch ohne memcpy direkt initialisieren

Generic Schritt 3: Typprüfung implementieren

  • Es wird ein parametrisierter Typ-Pointer im payload-Member einer union deklariert, um der Datenstruktur Typinformationen zur Compile-Zeit hinzuzufügen
  • Beispiel: #define List(type) union { ListNode *head; type *payload; }
  • So lässt sich mit __typeof__(foo_list.payload) der Typ der jeweiligen Liste ermitteln
  • Durch Type-Casting des Funktionstyps im Makro list_prepend lässt sich sicherstellen, dass nur der korrekte Typ kompiliert
  • Bei falscher Typverwendung tritt ein Fehler zur Compile-Zeit auf

Fehlerbeispiel:

  • Wenn zu foo_list ein int hinzugefügt wird, erscheint die Compiler-Fehlermeldung 'incompatible integer to pointer conversion'

Umgang mit Compilern ohne typeof-Unterstützung

  • Bis einschließlich vor C23 ist __typeof__ nicht standardisiert, daher funktioniert es auf einigen Compilern (z. B. älteren MSVC-Versionen) nicht
  • Über Umgehungslösungen wie die Nutzung eines payload-Members in einer struct ist ein ähnlicher Effekt möglich

Parameterübergabe und typedef

  • Selbst List(Foo) mit identischer Form wird vom Compiler als jeweils unterschiedlicher Typ behandelt
  • Mit typedef werden Parameterübergabe und Zuweisung reibungsloser

Beispiel:

  • typedef List(Foo) ListFoo;
  • Variablen vom Typ ListFoo können deklariert und als Funktionsparameter verwendet werden

Abschluss und Erweiterung auf verschiedene Datenstrukturen

  • Diese Technik lässt sich auch auf Datenstrukturen mit mehreren Typparametern anwenden (z. B. Hashmaps)
  • Über union kann die Typsicherheit für Schlüssel und Werte jeweils gewährleistet werden
  • Für detailliertere Praxisbeispiele und die Makro-Implementierung siehe den zugehörigen Code-Gist-Link

Fazit

  • Der neue Ansatz überwindet die Nachteile bisheriger Methoden (Lesbarkeit, Build-Effizienz, Wartbarkeit) und bietet ein konsistentes Benennungsschema für Funktionen sowie Typsicherheit
  • Er unterstützt problemlos verschiedene Datenstrukturen und mehrere Typparameter
  • Durch Typprüfung zur Compile-Zeit werden Sicherheit und Effizienz bei der Nutzung generischer Datenstrukturen zugleich erreicht

Danksagung

  • Dieser Artikel entstand mit Feedback und Ermutigung von Martin Fouilleul

Verwandte Beiträge

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

  • Es wurde darauf hingewiesen, dass die Verwendung von uint64_t data[]; im Code aus Schritt 2 für Typen mit größeren Alignment-Anforderungen als uint64_t ungeeignet ist und für kleinere Typen umgekehrt unnötig verschwenderisch ist; auf einer 64-Bit-Architektur mit ilp32-ABI sei das noch problematischer. Zum Code aus Schritt 3 wurde angemerkt, dass man int main() { List(Foo) foo_list = {NULL}; so schreiben müsse. Ohne typeof könne man keinen Rückgabewert zurückgeben, und beim Ersatzcode könnten const-bezogene Fehler auftreten; durch die Symmetrie des ==-Operators trete dieses Problem besonders deutlich hervor. Entferne man payload, fehle die Größeninformation, wodurch es unsicher werde; fügt man etwa int32_t zu List(int64_t) hinzu, sehe das zunächst unproblematisch aus, tatsächlich lasse sich die Größe von int32_t aber nicht bestimmen. Für echte Sicherheit seien daher Ergänzungen nötig. Außerdem wurde gesagt, es gebe zwei große Grenzen bei der Nutzung von Generics in C: Erstens sei der vtable-Delegationsansatz funktional eingeschränkt, weil Strukturen keine Makros enthalten könnten; zweitens müsse man bei Delegation an eine externe vtable alle zu verwendenden Typen im Voraus deklarieren. Am besten sei es, in einem Header mit typedef-Deklarationen nur statische Funktionen zu deklarieren; ergänzend wurde angemerkt, dass GCC und Clang zu unterschiedlichen Zeitpunkten Warnungen über undefinierte statische Funktionen ausgeben. Abschließend wurde als Beispiel eine Funktionsgestaltung erwähnt, die unterschiedliche Buffer-Strukturen annimmt, und betont, dass dabei auch alle const-Varianten mitverwaltet werden müssen

    • Zur Frage der Delegation an externe vtables berichtete jemand, in einem früheren Projekt sogar einen Compiler gebaut zu haben, um genau dieses Problem zu lösen. Beim Apache-Clownfish-Projekt habe man anfangs .h-Dateien geparst und schließlich ein eigenes Format namens Clownfish-Header (.cfh) geschaffen. Anhand eines Codebeispiels zum Aufruf der Methode Clone eines tatsächlichen Objekts wurde gezeigt, wie große Mengen solcher abenteuerlichen Codes generiert werden mussten, um Bindings für dynamische Sprachen mit objektorientierten Funktionen bereitzustellen. Ziel von Clownfish sei es gewesen, ein gemeinsames minimales Objektmodell bereitzustellen, und auch die Typen der Binding-Sprachen seien aus .cfh erzeugt worden. Wegen dieser Komplexität gäben die meisten letztlich die Typsicherheit auf und arbeiteten mit void*-Casts. https://github.com/apache/lucy-clownfish

    • Zu int main() wurde angemerkt, dass int main() in C bedeutet, dass die Anzahl der Argumente unbekannt ist. Erst int main(void) bedeute, dass es keine Argumente gibt. Das sei etwas, das viele C++-Autoren häufig vergessen

    • Es wurde die Erwartung geäußert, dass sich eine union wirklich „vereinigen“ sollte, also dass ein Typ sich selbst als Teil der union eines anderen Typs deklarieren können sollte

    • Es wurde darauf hingewiesen, dass beim malloc wegen internem Padding die berechnete Größe kleiner als die tatsächliche sein könnte; bei etwas wie malloc(sizeof(*node) + data_size); bestehe also ein Risiko

  • Trick Nr. 0 wurde widersprochen; jemand habe diesen Trick beim Erstellen eines vollständigen C-Dialekts selbst verwendet. Als Beispiel wurde Code für eine generische Binary-Heap-Implementierung geteilt: https://github.com/gritzko/librdx/blob/master/abc/HEAPx.h. Die Syntax sei zwar etwas schwerfällig, werde am Ende aber zu einer gewöhnlichen C-Struktur, was große Vorteile bei Optimierung und Vorhersehbarkeit bringe. Bei anderen Implementierungen halte man void*, Laufzeit-Speichergrößenbestimmung und Makrodefinitionen für unvermeidlich

    • Der Autor erklärte dazu, dass Binary Heap und Linked List unterschiedliche Ziele hätten. Da ein Binary Heap beim Speichern Daten lesen müsse, sei der Zugriff anders; beim Schreiben eines generischen Binary Heaps könne man daher andere Entscheidungen treffen. Das sei auch in einer Fußnote des Artikels erwähnt worden

    • Es wurden mehrere Gründe für die Bevorzugung einer Header-Implementierung genannt. Beim Debugging sei das Nachverfolgen des Codes und die Nutzung von Typinformationen einfacher als bei Makro-Funktionen. Der Compiler könne für jede Instanz monomorphisierte Optimierungen durchführen, ohne Laufzeitkosten oder die Last variabler Größen. Generische Strukturen könnten auf dem Stack liegen. Die zwei vom Autor genannten Probleme ließen sich umgehen: Über Funktionsnamen-Makros könne man Namen leicht ändern, und mit weak symbols könne man doppelte Definitionen beim Linken automatisch zusammenführen. Bei generischen Containern für Zeigertypen gebe es noch ein weiteres Problem, das sich aber etwa mit typedef lösen lasse. Intrusive Data Structures seien in C weiterhin bequem, auch wenn Debugging schwierig bleibe

    • Die Formulierung, der Compiler „verschlinge es wie Donuts“, habe einen Lachanfall ausgelöst

  • Beim Umwandeln von Funktionstypen nehme man etwa an, dass Foo* und void* intern gleich repräsentiert seien, doch das sei in Standard-C nicht garantiert. Wenn zwischen den Typen keine „compatible“-Beziehung bestehe, könne ein solcher Cast zu undefiniertem Verhalten führen. Das könne sich auch auf Alias-Analysen des Compilers auswirken (mit Referenzlink). https://news.ycombinator.com/item?id=44421185

    • Es wurde erwidert, das sei bereits in einer Fußnote erwähnt, und der Cast sei nicht der Kern der Typsicherheit. Man solle den ganzen Artikel lesen

  • Es wurde gefragt: „Warum solche Verrenkungen, um Generics in C zu benutzen? Warum nicht einfach C++ verwenden?“

    • Daraufhin wurde die Erfahrung geteilt, dass in Legacy-Projekten eine Migration zu C++ wegen Sicherheitskriterien und anderer Anforderungen oft nicht sofort möglich sei. In neuen Projekten führe man zwar per Standardisierung C++ ein, bestehende Projekte müssten aber vorerst in C bleiben. Die Haltung „Nehmt doch einfach C++“ könnte etwas mehr Kontext und Verständnis vertragen

    • Tatsächlich könne der Umstieg von C auf C++ in Umgebungen, in denen C verwendet wird, noch komplexer sein und mehr Probleme verursachen

    • Umgekehrt wurde die Position vertreten, dass man mit etwas zusätzlichem Aufwand in C dasselbe Ergebnis erzielen könne und daher nicht extra bis zu C++ gehen müsse

  • Es wurde ein in der Linux-Kernel-Praxis tatsächlich verwendetes Muster vorgestellt: struct list_head, das Listeninformationen enthält, wird in typspezifische Strukturen eingebettet. Ein passender Referenzlink wurde geteilt. https://kernelnewbies.org/FAQ/LinkedLists

    • Die Makronamen LIST_HEAD_INIT und INIT_LIST_HEAD im Linux-Kernel wirkten nicht besonders intuitiv

  • Im Code des Abschnitts „typeof on old compilers“ wurde darauf hingewiesen, dass (list)->payload = (item); in Wirklichkeit kein no-op ist, sondern den Listenkopf mit item überschreibt. Falls das beabsichtigte Verhalten sei, sollte es in if(0) eingeschlossen werden

    • Im Beispiel sei die union durch struct ersetzt worden, was ebenfalls verschwenderisch wirke. Eine Behandlung innerhalb von if(0) erscheine besser

  • Es wurde gezeigt, dass eine solche generische List-Struktur in der Sprache D deutlich einfacher ist; der Präprozessor von C sei dabei, als würde man mit einem Hammer auf Fingernägel schlagen, während eine Nail Gun fürs Nageln viel schneller und sauberer sei — eine Metapher für die Unbequemlichkeit von C-Makros

    • Darauf wurde erwidert, dass sich der Beitrag um C drehe und manche Projekte zwingend C verwenden müssten

  • Die Idee, union und typeof() zu nutzen, wurde als interessant bezeichnet. Nach eigener Erfahrung brauche man bei intrusiven Datenstrukturen am Ende doch Wrapper, die in große Makros gepackt sind; es wurde bezweifelt, ob sich so etwas auch mit union und typeof umsetzen lasse. Als Beispiel wurden Code für einen Hash-Table-Wrapper und Dokumentationslinks geteilt. https://github.com/FRRouting/frr/blob/master/lib/typesafe.h#L823-L971 https://docs.frrouting.org/projects/dev-guide/en/latest/lists.html

  • Jemand teilte mit, diese Technik bereits in einer experimentellen Bibliothek zu verwenden. https://github.com/uecker/noplate/blob/main/src/list.h

    • Es wurde nach einer Idee für intrusive Strukturen gefragt, also dafür, die Knotenstruktur in die Daten einzubetten, damit ein Objekt gleichzeitig zu mehreren Containern gehören kann

  • Der Kern scheine die Idee zu sein, über den Typ von Funktionszeigern Typsicherheit zu erreichen, statt den häufig verwendeten Handle-Typ zu nutzen. Es wurde geteilt, dass der C23-Standard Probleme bei der Typkompatibilität verbessert habe, zusammen mit dem entsprechenden Standarddokument und dem aktuellen Supportstatus in GCC/Clang. https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3037.pdf

    • Der Autor betonte daraufhin, die Kernidee sei, mittels union Typinformationen an generische Datentypen zu koppeln; Function-Casting sei nicht der einzige Weg, und mehrere Alternativen seien diskutiert worden, auch ausführlich in der Fußnote und im Abschnitt „typeof on old compilers“