Typsichere generische Datenstrukturen in schlichtem C?

Lesezeit: 15 Minuten

Ich habe viel mehr C++-Programmierung gemacht als “normale alte C”-Programmierung. Was ich beim Programmieren in Plain C sehr vermisse, sind typsichere generische Datenstrukturen, die in C++ über Templates bereitgestellt werden.

Betrachten Sie der Konkretheit halber eine generische einfach verkettete Liste. In C++ ist es einfach, Ihre eigene Vorlagenklasse zu definieren und sie dann für die benötigten Typen zu instanziieren.

In C fallen mir einige Möglichkeiten ein, eine generische einfach verkettete Liste zu implementieren:

  1. Schreiben Sie den/die Typ(en) der verknüpften Liste und die unterstützenden Prozeduren einmal, indem Sie void-Zeiger verwenden, um das Typsystem zu umgehen.
  2. Schreiben Sie Präprozessormakros, die die erforderlichen Typnamen usw. verwenden, um eine typspezifische Version der Datenstruktur und der unterstützenden Prozeduren zu generieren.
  3. Verwenden Sie ein anspruchsvolleres, eigenständiges Tool, um den Code für die benötigten Typen zu generieren.

Ich mag Option 1 nicht, da sie das Typsystem untergräbt und wahrscheinlich eine schlechtere Leistung hätte als eine spezialisierte typspezifische Implementierung. Die Verwendung einer einheitlichen Darstellung der Datenstruktur für alle Typen und das Casting zu/von void-Zeigern erfordert meines Erachtens einen Umweg, der durch eine auf den Elementtyp spezialisierte Implementierung vermieden würde.

Option 2 erfordert keine zusätzlichen Tools, fühlt sich aber etwas klobig an und kann bei unsachgemäßer Verwendung zu schwerwiegenden Compilerfehlern führen.

Option 3 könnte bessere Compiler-Fehlermeldungen liefern als Option 2, da sich der spezialisierte Datenstrukturcode in erweiterter Form befinden würde, die in einem Editor geöffnet und vom Programmierer überprüft werden könnte (im Gegensatz zu Code, der von Präprozessormakros generiert wird). Diese Option ist jedoch das Schwergewicht, eine Art “Vorlage des armen Mannes”. Ich habe diesen Ansatz bereits früher verwendet, indem ich ein einfaches sed-Skript verwendet habe, um eine “Vorlagen”-Version von C-Code zu spezialisieren.

Ich würde meine zukünftigen “Low-Level”-Projekte lieber in C als in C++ programmieren, hatte aber Angst vor dem Gedanken, gemeinsame Datenstrukturen für jeden spezifischen Typ neu zu schreiben.

Welche Erfahrungen haben die Leute mit diesem Problem? Gibt es gute Bibliotheken mit generischen Datenstrukturen und Algorithmen in C, die nicht zu Option 1 passen (dh Casting zu und von void-Zeigern, was die Typsicherheit opfert und eine Ebene der Indirektion hinzufügt)?

  • 4) Implementieren Sie ein vollständig polymorphes Objektsystem in c. Was viel mehr Ärger macht, als es wert ist.

    – dmckee — Ex-Moderator-Kätzchen

    14. Juni 2010 um 17:51 Uhr

  • Nachdem ich Methode 2 ein paar Mal gemacht habe, denke ich, dass Methode 3 die Art und Weise sein würde, wie ich das nächste Mal angehen werde. Sie können 3 mit dem gleichen Aufwand wie 2 implementieren und erhalten gleichzeitig bessere Fehlermeldungen.

    – James

    14. Juni 2010 um 17:54 Uhr

  • @Bradford: Das Erstellen von OO in c ist ein großes Projekt, aber nicht so groß, wie es sich anhört (die Leute des Dillo-Projekts haben in einer sehr kleinen Menge Code für die v1.x-Serie gute Arbeit geleistet, bevor sie für die v2.x auf c++ umgestiegen sind Serie). Es ist nur so, wenn Sie brauchen all diese netten Garantien, dass Sie mit ziemlicher Sicherheit besser dran sind, c++ oder D oder object-c zu verwenden, oder etwas das hat sie schon.

    – dmckee — Ex-Moderator-Kätzchen

    14. Juni 2010 um 19:57 Uhr

  • @dmckee oder es gibt GObject …

    – Spudd86

    15. Juni 2010 um 18:25 Uhr

  • OpenGC3 [ see ccxll(T) ] ist, was Sie suchen! Es ist jedoch noch nicht vollständig, und es sind nur zwei Arten von verketteten Listen implementiert, aber es reicht aus, um zu demonstrieren, wie man mit der zweiten oben erwähnten Option typsichere generische Datenstrukturen in einfachem C erstellt.

    – Kevin Dong

    5. April 2017 um 6:36 Uhr


Option 1 ist der Ansatz, den die meisten C-Implementierungen von generischen Containern verfolgen, die ich sehe. Das Windows-Treiberkit und der Linux-Kernel verwenden ein Makro, um zu ermöglichen, dass Links für die Container irgendwo in eine Struktur eingebettet werden, wobei das Makro verwendet wird, um den Strukturzeiger von einem Zeiger auf das Linkfeld zu erhalten:

Option 2 ist der Weg, den die Containerimplementierung tree.h und queue.h von BSD eingeschlagen hat:

Ich glaube nicht, dass ich einen dieser Ansätze als typsicher betrachten würde. Nützlich, aber nicht typsicher.

  • mit dem ganzen Kernel-Zeug herausgenommen: ccan.ozlabs.org/browse/ccan/list CCAN ist voll davon. ccan.ozlabs.org Dort gibt es auch einige Dinge, die bei der Typensicherheit helfen

    – Spudd86

    15. Juni 2010 um 18:23 Uhr


  • Die Methode „sys/queue.h“ ist vollständig typsicher. Es erstellt neue Strukturen für jeden definierten Listentyp, sodass die öffentliche API typsicher ist, obwohl sie unter der Haube generische Zeiger verwendet. Es produziert im Allgemeinen auch weniger Code und Daten als generische Listenroutinen und hat coole Dinge wie kreisförmige Warteschlangen zusätzlich zu einfach und doppelt verknüpften Listen. die linux list.h ist eine abgespeckte Version von queue für den Kernel, sys/queue selbst ist portabel, de facto standardisiert und bekannt, kein Grund, die linuxspezifische Version zu verwenden.

    – John Meacham

    13. Februar 2014 um 12:56 Uhr


  • Ich kann die ersten beiden Links nicht öffnen.

    – Ekrem Dinçel

    10. September 2020 um 10:07 Uhr

C hat eine andere Art von Schönheit als C++, und Typsicherheit und die Möglichkeit, immer zu sehen, was alles ist, wenn Sie den Code durchlaufen, ohne Umwandlungen in Ihren Debugger einzubeziehen, gehören normalerweise nicht dazu.

Die Schönheit von C kommt zum großen Teil von seinem Mangel an Typsicherheit, dem Arbeiten um das Typsystem herum und auf der rohen Ebene von Bits und Bytes. Aus diesem Grund gibt es bestimmte Dinge, die es einfacher machen kann, ohne gegen die Sprache zu kämpfen, wie zum Beispiel Strukturen mit variabler Länge, die Verwendung des Stacks sogar für Arrays, deren Größe zur Laufzeit bestimmt wird, usw. Es ist auch viel einfacher zu sein Bewahren Sie ABI, wenn Sie auf dieser niedrigeren Ebene arbeiten.

Es gibt hier also eine andere Art von Ästhetik sowie andere Herausforderungen, und ich würde empfehlen, die Denkweise zu ändern, wenn Sie in C arbeiten. Um es wirklich zu schätzen, würde ich vorschlagen, Dinge zu tun, die viele Menschen heutzutage als selbstverständlich ansehen, wie z Implementierung Ihres eigenen Speicherzuordners oder Gerätetreibers. Wenn Sie auf einer so niedrigen Ebene arbeiten, können Sie nicht anders, als alles als Speicherlayouts von Bits und Bytes zu betrachten, im Gegensatz zu “Objekten” mit angehängten Verhaltensweisen. Darüber hinaus kann es bei einem solchen Low-Level-Bit/Byte-Manipulationscode zu einem Punkt kommen, an dem C leichter zu verstehen ist als C++-Code, der mit übersät ist reinterpret_castsz.B

Was Ihr Beispiel für eine verknüpfte Liste betrifft, würde ich eine nicht aufdringliche Version eines verknüpften Knotens vorschlagen (eine, die keine Speicherung von Listenzeigern im Elementtyp erfordert, Tselbst, wodurch die Logik und Darstellung der verknüpften Liste entkoppelt werden kann T selbst), etwa so:

struct ListNode
{
    struct ListNode* prev;
    struct ListNode* next;
    MAX_ALIGN char element[1]; // Watch out for alignment here.
                               // see your compiler's specific info on 
                               // aligning data members.
};

Jetzt können wir einen Listenknoten wie folgt erstellen:

struct ListNode* list_new_node(int element_size)
{
    // Watch out for alignment here.
    return malloc_max_aligned(sizeof(struct ListNode) + element_size - 1);
}

// create a list node for 'struct Foo'
void foo_init(struct Foo*);
struct ListNode* foo_node = list_new_node(sizeof(struct Foo));
foo_init(foo_node->element);

So rufen Sie das Element aus der Liste als T* ab:

T* element = list_node->element;

Da es sich um C handelt, gibt es beim Casten von Zeigern auf diese Weise keinerlei Typprüfung, und das wird Ihnen wahrscheinlich auch ein ungutes Gefühl geben, wenn Sie aus einem C++-Hintergrund kommen.

Der knifflige Teil hier ist sicherzustellen, dass dieses Mitglied, element, ist für jeden Typ, den Sie speichern möchten, richtig ausgerichtet. Wenn Sie dieses Problem so portabel lösen können, wie Sie es benötigen, haben Sie eine leistungsstarke Lösung zum Erstellen effizienter Speicherlayouts und Zuweisungen. Oft müssen Sie nur die maximale Ausrichtung für alles verwenden, was verschwenderisch erscheinen mag, aber normalerweise nicht, wenn Sie geeignete Datenstrukturen und Zuweisungen verwenden, die diesen Overhead nicht für zahlreiche kleine Elemente auf individueller Basis bezahlen.

Nun beinhaltet diese Lösung noch das Typecasting. Es gibt wenig, was Sie dagegen tun können, außer eine separate Codeversion dieses Listenknotens und die entsprechende Logik zu haben, um damit für jeden Typ T zu arbeiten, den Sie unterstützen möchten (kurz vor dynamischem Polymorphismus). Es beinhaltet jedoch keine zusätzliche Indirektionsebene, wie Sie vielleicht dachten, dass es notwendig wäre, und weist dennoch den gesamten Listenknoten und das gesamte Element in einer einzigen Zuordnung zu.

Und ich würde diesen einfachen Weg empfehlen, um in vielen Fällen Generizität in C zu erreichen. Einfach austauschen T mit einem Puffer, der eine passende Länge hat sizeof(T) und richtig ausgerichtet. Wenn Sie eine einigermaßen tragbare und sichere Methode haben, die Sie verallgemeinern können, um eine ordnungsgemäße Ausrichtung sicherzustellen, haben Sie eine sehr leistungsfähige Methode, um mit dem Speicher so zu arbeiten, dass häufig Cache-Treffer verbessert, die Häufigkeit von Heap-Zuweisungen / -Aufhebungen und die Menge von reduziert werden benötigte Indirektion, Bauzeiten usw.

Wenn Sie mehr Automatisierung benötigen, wie z list_new_node automatisch initialisieren struct Foo, würde ich empfehlen, eine allgemeine Tabellenstruktur zu erstellen, die Sie weitergeben können und die Informationen enthält, wie z. ein Komparator usw. In C++ können Sie diese Tabelle automatisch generieren, indem Sie Vorlagen und eingebaute Sprachkonzepte wie Kopierkonstruktoren und -destruktoren verwenden. C erfordert etwas mehr manuellen Aufwand, aber Sie können es mit Makros immer noch ein wenig reduzieren.

Ein weiterer Trick, der nützlich sein kann, wenn Sie sich für eine eher makroorientierte Codegenerierungsroute entscheiden, besteht darin, eine präfix- oder suffixbasierte Namenskonvention für Bezeichner einzulösen. Beispielsweise könnte CLONE(Type, ptr) für die Rückgabe definiert werden Type##Clone(ptr)Also CLONE(Foo, foo) berufen könnte FooClone(foo). Dies ist eine Art Cheat, um so etwas wie das Überladen von Funktionen in C zu erreichen, und ist nützlich, wenn Sie Code in großen Mengen generieren (wenn CLONE verwendet wird, um ein anderes Makro zu implementieren) oder sogar ein wenig Kopieren und Einfügen von Boilerplate-Code Verbesserung der Gleichmäßigkeit der Kesselplatte.

Option 1, entweder mit void * oder einige union Die meisten C-Programme verwenden eine basierte Variante, die Ihnen möglicherweise eine BESSERE Leistung bietet als der C++/Makro-Stil mit mehreren Implementierungen für verschiedene Typen, da sie weniger Codeduplizierung und damit weniger Icache-Druck und weniger Icache-Fehlschläge hat.

GLib enthält eine Reihe generischer Datenstrukturen, http://www.gtk.org/

CCAN hat eine Reihe nützlicher Schnipsel und dergleichen http://ccan.ozlabs.org/

Ich verwende Void-Zeiger (void*), um generische Datenstrukturen darzustellen, die mit Structs und Typedefs definiert sind. Unten teile ich meine Implementierung einer Bibliothek, an der ich arbeite.

Bei dieser Art der Implementierung können Sie sich jeden neuen mit typedef definierten Typ wie eine Pseudoklasse vorstellen. Hier ist diese Pseudoklasse die Menge des Quellcodes (some_type_implementation.c) und seiner Header-Datei (some_type_implementation.h).

Im Quellcode müssen Sie die Struktur definieren, die den neuen Typ darstellt. Beachten Sie die Struktur in der Quelldatei “node.c”. Dort habe ich einen void-Zeiger auf das Attribut “info” gemacht. Dieser Zeiger kann jede Art von Zeiger enthalten (glaube ich), aber der Preis, den Sie zahlen müssen, ist eine Typkennung innerhalb der Struktur (int type) und alle Schalter, um das richtige Handle für jeden definierten Typ zu machen. Also habe ich in der Header-Datei node.h” den Typ “Node” definiert (um nicht jedes Mal struct node eingeben zu müssen), und ich musste auch die Konstanten “EMPTY_NODE”, “COMPLEX_NODE” und “MATRIX_NODE “.

Sie können die Kompilierung von Hand mit “gcc *.c -lm” durchführen.

main.c Quelldatei

#include <stdio.h>
#include <math.h>

#define PI M_PI

#include "complex.h"
#include "matrix.h"
#include "node.h" 


int main()
{
    //testCpx();
    //testMtx();
    testNode();

    return 0;
}

node.c Quelldatei

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#include "node.h"
#include "complex.h"
#include "matrix.h"

#define PI M_PI


struct node
{
    int type;

    void* info;
};


Node* newNode(int type,void* info)
{
    Node* newNode = (Node*) malloc(sizeof(Node));

    newNode->type = type;

    if(info != NULL)
    {
        switch(type)
        {
            case COMPLEX_NODE:
                newNode->info = (Complex*) info;
            break;

            case MATRIX_NODE:
                newNode->info = (Matrix*) info;
            break;
        }
    }
    else
        newNode->info = NULL;

    return newNode;
}

int emptyInfoNode(Node* node)
{
    return (node->info == NULL);
}

void printNode(Node* node)
{
    if(emptyInfoNode(node))
    {
        printf("Type:%d\n",node->type);
        printf("Empty info\n");
    }
    else
    {
        switch(node->type)
        {
            case COMPLEX_NODE:
                printCpx(node->info);
            break;

            case MATRIX_NODE:
                printMtx(node->info);
            break;
        }
    }
}

void testNode()
{
    Node *node1,*node2, *node3;
    Complex *Z;
    Matrix *M;

    Z = mkCpx(POLAR,5,3*PI/4);

    M = newMtx(3,4,PI);

    node1 = newNode(COMPLEX_NODE,Z);
    node2 = newNode(MATRIX_NODE,M);
    node3 = newNode(EMPTY_NODE,NULL);



    printNode(node1);
    printNode(node2);
    printNode(node3);
}

node.h Header-Datei

#define EMPTY_NODE   0
#define COMPLEX_NODE 1
#define MATRIX_NODE  2


typedef struct node Node;


Node* newNode(int type,void* info);
int emptyInfoNode(Node* node);
void printNode(Node* node);
void testNode();

matrix.c-Quelldatei

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#include "matrix.h"

struct matrix
{
    // Meta-information about the matrix 
    int rows;
    int cols;

    // The elements of the matrix, in the form of a vector 
    double** MTX;
};

Matrix* newMtx(int rows,int cols,double value)
{
    register int row , col;
    Matrix* M = (Matrix*)malloc(sizeof(Matrix));

    M->rows = rows;
    M->cols = cols;
    M->MTX = (double**) malloc(rows*sizeof(double*));

    for(row = 0; row < rows ; row++)
    {
        M->MTX[row] = (double*) malloc(cols*sizeof(double));

        for(col = 0; col < cols ; col++) 
            M->MTX[row][col] = value;
    }

    return M;
}

Matrix* mkMtx(int rows,int cols,double** MTX)
{   
    Matrix* M;
    if(MTX == NULL)
    {
        M = newMtx(rows,cols,0);
    }
    else
    {
        M = (Matrix*)malloc(sizeof(Matrix));
        M->rows = rows;
        M->cols = cols;
        M->MTX  = MTX;
    }
    return M;
}

double getElemMtx(Matrix* M , int row , int col)
{
    return M->MTX[row][col];
}

void printRowMtx(double* row,int cols)
{
    register int j;
    for(j = 0 ; j < cols ; j++) 
        printf("%g ",row[j]);           
}

void printMtx(Matrix* M)
{
    register int row = 0, col = 0;

    printf("\vSize\n");
    printf("\tRows:%d\n",M->rows);
    printf("\tCols:%d\n",M->cols);
    printf("\n");
    for(; row < M->rows ; row++)
    {
        printRowMtx(M->MTX[row],M->cols);
        printf("\n");
    }

    printf("\n");
}

void testMtx()
{
    Matrix* M = mkMtx(10,10,NULL);
    printMtx(M);
}

matrix.h Header-Datei

typedef struct matrix Matrix;

Matrix* newMtx(int rows,int cols,double value);
Matrix* mkMatrix(int rows,int cols,double** MTX);
void print(Matrix* M);
double getMtx(Matrix* M , int row , int col);
void printRowMtx(double* row,int cols);
void printMtx(Matrix* M);
void testMtx();

complex.c-Quelldatei

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#include "complex.h"

struct complex
{
    int type;

    double a;
    double b;
};

Complex* mkCpx(int type,double a,double b)
{
    /** Doc - {{{
     * This function makes a new Complex number.
     * 
     * @params:
     * |-->type: Is an interger that denotes if the number is in
     * |         the analitic or in the polar form.
     * |         ANALITIC:0
     * |         POLAR   :1
     * |
     * |-->a: Is the real part if type = 0 and is the radius if 
     * |      type = 1
     * |
     * `-->b: Is the imaginary part if type = 0 and is the argument
     *        if type = 1
     * 
     * @return:
     *      Returns the new Complex number initialized with the values 
     *      passed
     *}}} */

    Complex* number = (Complex*)malloc(sizeof(Complex));

    number->type = type;
    number->a    = a;
    number->b    = b;

    return number;
}

void printCpx(Complex* number)
{
    switch(number->type)
    {
        case ANALITIC:
            printf("Re:%g | Im:%g\n",number->a,number->b);
        break;

        case POLAR:
            printf("Radius:%g | Arg:%g\n",number->a,number->b);
        break;
    }
}

void testCpx()
{
    Complex* Z = mkCpx(ANALITIC,3,2);
    printCpx(Z);
}

complex.h Header-Datei

#define ANALITIC 0 
#define POLAR    1 

typedef struct complex Complex;

Complex* mkCpx(int type,double a,double b);
void printCpx(Complex* number);
void testCpx();

Ich hoffe, ich hatte nichts verpasst.

Ihre Option 1 ist das, was die meisten alten C-Programmierer wählen würden, möglicherweise gesalzen mit ein wenig 2, um das wiederholte Tippen zu reduzieren, und nur kann sein Verwenden einiger Funktionszeiger für eine Art Polymorphismus.

Es gibt eine gängige Variante von Option 1, die effizienter ist, da sie Vereinigungen verwendet, um die Werte in den Listenknoten zu speichern, dh es gibt keinen zusätzlichen Umweg. Dies hat den Nachteil, dass die Liste nur Werte bestimmter Typen akzeptiert und möglicherweise Speicherplatz verschwendet, wenn die Typen unterschiedlich groß sind.

Es ist jedoch möglich, die loszuwerden union indem Sie stattdessen ein flexibles Array-Member verwenden, wenn Sie bereit sind, striktes Aliasing zu brechen. C99-Beispielcode:

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct ll_node
{
    struct ll_node *next;
    long long data[]; // use `long long` for alignment
};

extern struct ll_node *ll_unshift(
    struct ll_node *head, size_t size, void *value);

extern void *ll_get(struct ll_node *head, size_t index);

#define ll_unshift_value(LIST, TYPE, ...) \
    ll_unshift((LIST), sizeof (TYPE), &(TYPE){ __VA_ARGS__ })

#define ll_get_value(LIST, INDEX, TYPE) \
    (*(TYPE *)ll_get((LIST), (INDEX)))

struct ll_node *ll_unshift(struct ll_node *head, size_t size, void *value)
{
    struct ll_node *node = malloc(sizeof *node + size);
    if(!node) assert(!"PANIC");

    memcpy(node->data, value, size);
    node->next = head;

    return node;
}

void *ll_get(struct ll_node *head, size_t index)
{
    struct ll_node *current = head;
    while(current && index--)
        current = current->next;
    return current ? current->data : NULL;
}

int main(void)
{
    struct ll_node *head = NULL;
    head = ll_unshift_value(head, int, 1);
    head = ll_unshift_value(head, int, 2);
    head = ll_unshift_value(head, int, 3);

    printf("%i\n", ll_get_value(head, 0, int));
    printf("%i\n", ll_get_value(head, 1, int));
    printf("%i\n", ll_get_value(head, 2, int));

    return 0;
}

1413470cookie-checkTypsichere generische Datenstrukturen in schlichtem C?

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy