¿Estructuras de datos genéricas seguras de tipo en C?

C tiene un tipo diferente de belleza que C++, y la seguridad de tipo y ser capaz de ver siempre lo que es todo cuando se rastrea a través del código sin involucrar casts en su depurador normalmente no es una de ellas.

La belleza de C proviene mucho de su falta de seguridad de tipos, de trabajar alrededor del sistema de tipos y en el nivel raw de bits y bytes. Debido a eso, hay ciertas cosas que puede hacer más fácilmente sin luchar contra el lenguaje como, por ejemplo, estructuras de longitud variable, usar la pila incluso para matrices cuyos tamaños se determinan en tiempo de ejecución, etc. También tiende a ser mucho más simple preservar ABI cuando se está trabajando en este nivel inferior.

Así que hay un tipo diferente de estética involucrada aquí, así como diferentes desafíos, y recomendaría un cambio de mentalidad cuando trabajas en C. Para apreciarlo realmente, sugeriría hacer cosas que muchas personas dan por sentadas en estos días, como implementar tu propio asignador de memoria o controlador de dispositivo. Cuando estás trabajando en un nivel tan bajo, no puede evitar mirar todo como diseños de memoria de bits y bytes en lugar de 'objetos' con comportamientos adjuntos. Además, puede llegar un punto en este código de manipulación de bits/bytes de bajo nivel en el que C se vuelve más fácil de comprender que el código C++ lleno de reinterpret_casts, por ejemplo,

En cuanto a su ejemplo de lista vinculada, sugeriría una versión no intrusiva de un nodo vinculado (uno que no requiere almacenar punteros de lista en el tipo de elemento, T, en sí, permitiendo que la lógica y la representación de la lista enlazada se desacoplen de T, así:

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.
};

Ahora podemos crear un nodo de lista así:

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);

Para recuperar el elemento de la lista como T*:

T* element = list_node->element;

Dado que es C, no hay comprobación de tipo alguna al emitir punteros de esta manera, y eso probablemente también le dará una sensación incómoda si viene de un fondo de C++.

La parte difícil aquí es asegurarse de que este miembro, element, es alineado correctamente para cualquier tipo que desee almacenar. Cuando pueda resolver ese problema tan portablemente como lo necesite, tendrá una solución poderosa para crear diseños y asignadores de memoria eficientes. A menudo, esto le hará usar la alineación máxima para todo lo que puede parecer un desperdicio, pero generalmente no lo es si está utilizando estructuras de datos y asignadores apropiados que no están pagando esta sobrecarga por numerosos elementos pequeños de forma individual.

Ahora esta solución todavía implica el tipo de fundición. Hay poco que se puede hacer al respecto, sin tener una versión separada del código de este nodo de la lista y la lógica correspondiente para trabajar con él para cada tipo, T, que desea soportar (corto de polimorfismo dinámico). Sin embargo, no implica un nivel adicional de indirección como podría haber pensado que era necesario, y todavía asigna todo el nodo de la lista y el elemento en una sola asignación.

Y yo recomendaría esta manera sencilla de lograr genericidad en C en muchos casos. Simplemente reemplace T con un búfer que tenga una longitud que coincida con sizeof(T) y esté alineado correctamente. Si tiene una forma razonablemente portátil y segura que puede generalizar para garantizar una alineación adecuada, tendrá una forma muy poderosa de trabajar con la memoria de una manera que a menudo mejora las visitas a la caché, reduce la frecuencia de asignaciones/desasignaciones de montones, la cantidad de indirecciones requeridas, los tiempos de compilación, etc.

Si necesita más automatización, como tener list_new_node automáticamente initialize struct Foo, recomendaría crear una estructura de tabla de tipo general que pueda pasar y que contenga información como qué tan grande es T, un puntero de función que apunte a una función para crear una instancia predeterminada de T, otra para copiar T, clonar T, destruir T, un comparador, etc. En C++, puede generar esta tabla automáticamente utilizando plantillas y conceptos de lenguaje integrados como constructores de copia y destructores. C requiere un poco más de esfuerzo manual, pero todavía se puede reducir el boilerplate un poco con macros.

Otro truco que puede ser útil si va con una ruta de generación de código más orientada a macros es cobrar una convención de nombres de identificadores basada en prefijos o sufijos. Por ejemplo, CLONE (Type, ptr) se podría definir para devolver Type##Clone(ptr), por lo que CLONE(Foo, foo) podría invocar FooClone(foo). Esto es una especie de trampa para obtener algo similar a la sobrecarga de funciones en C, y es útil cuando se genera código en masa (cuando se usa el CLON para implementar otra macro) o incluso un poco de copiar y pegar de código de tipo boilerplate para al menos mejorar la uniformidad del boilerplate.

La opción 1, ya sea usando void * o alguna variante basada en union es lo que la mayoría de los programas de C usan, y puede darle un mejor rendimiento que el estilo C++/macro de tener múltiples implementaciones para diferentes tipos, ya que tiene menos duplicación de código, y por lo tanto menos presión de icache y menos errores de icache.

GLib tiene un montón de estructuras de datos genéricas, http://www.gtk.org /

CCAN tiene un montón de fragmentos útiles y tales http://ccan.ozlabs.org /

Su opción 1 es lo que la mayoría de los programadores de c de edad irían para, posiblemente salado con un poco de 2 para reducir la escritura repetitiva, y sólo tal vez empleando algunos punteros de función para un sabor de polimorfismo.

Hay una variación común a la opción 1 que es más eficiente, ya que utiliza uniones para almacenar los valores en los nodos de la lista, es decir, no hay indirección adicional. Esto tiene el inconveniente de que la lista solo acepta valores de ciertos tipos y potencialmente desperdicia algo de memoria si los tipos son de diferentes tamaños.

Sin embargo, es posible deshacerse del union utilizando el miembro de matriz flexible en su lugar si está dispuesto a romper el alias estricto. C99 código de ejemplo:

#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;
}

Una vieja pregunta, lo sé, pero en caso de que todavía sea de interés: Estaba experimentando con la opción 2) (macros preprocesadores) hoy, y se me ocurrió el ejemplo que pegaré a continuación. Un poco torpe de hecho, pero no terrible. El código no es totalmente seguro, pero contiene controles de cordura para proporcionar un nivel razonable de seguridad. Y lidiar con los mensajes de error del compilador mientras lo escribía fue leve en comparación con lo que he visto cuando las plantillas de C++ entraron en juego. Usted es probablemente el mejor comienzo leyendo esto en el ejemplo use código en la función "main".

#include <stdio.h>

#define LIST_ELEMENT(type) \
    struct \
    { \
        void *pvNext; \
        type value; \
    }

#define ASSERT_POINTER_TO_LIST_ELEMENT(type, pElement) \
    do { \
        (void)(&(pElement)->value  == (type *)&(pElement)->value); \
        (void)(sizeof(*(pElement)) == sizeof(LIST_ELEMENT(type))); \
    } while(0)

#define SET_POINTER_TO_LIST_ELEMENT(type, pDest, pSource) \
    do { \
        ASSERT_POINTER_TO_LIST_ELEMENT(type, pSource); \
        ASSERT_POINTER_TO_LIST_ELEMENT(type, pDest); \
        void **pvDest = (void **)&(pDest); \
        *pvDest = ((void *)(pSource)); \
    } while(0)

#define LINK_LIST_ELEMENT(type, pDest, pSource) \
    do { \
        ASSERT_POINTER_TO_LIST_ELEMENT(type, pSource); \
        ASSERT_POINTER_TO_LIST_ELEMENT(type, pDest); \
        (pDest)->pvNext = ((void *)(pSource)); \
    } while(0)

#define TERMINATE_LIST_AT_ELEMENT(type, pDest) \
    do { \
        ASSERT_POINTER_TO_LIST_ELEMENT(type, pDest); \
        (pDest)->pvNext = NULL; \
    } while(0)

#define ADVANCE_POINTER_TO_LIST_ELEMENT(type, pElement) \
    do { \
        ASSERT_POINTER_TO_LIST_ELEMENT(type, pElement); \
        void **pvElement = (void **)&(pElement); \
        *pvElement = (pElement)->pvNext; \
    } while(0)

typedef struct { int a; int b; } mytype;

int main(int argc, char **argv)
{
    LIST_ELEMENT(mytype) el1;
    LIST_ELEMENT(mytype) el2;
    LIST_ELEMENT(mytype) *pEl;
    el1.value.a = 1;
    el1.value.b = 2;
    el2.value.a = 3;
    el2.value.b = 4;
    LINK_LIST_ELEMENT(mytype, &el1, &el2);
    TERMINATE_LIST_AT_ELEMENT(mytype, &el2);
    printf("Testing.\n");
    SET_POINTER_TO_LIST_ELEMENT(mytype, pEl, &el1);
    if (pEl->value.a != 1)
        printf("pEl->value.a != 1: %d.\n", pEl->value.a);
    ADVANCE_POINTER_TO_LIST_ELEMENT(mytype, pEl);
    if (pEl->value.a != 3)
        printf("pEl->value.a != 3: %d.\n", pEl->value.a);
    ADVANCE_POINTER_TO_LIST_ELEMENT(mytype, pEl);
    if (pEl != NULL)
        printf("pEl != NULL.\n");
    printf("Done.\n");
    return 0;
}

Utilizo punteros void (void*) para representar estructuras de datos genéricas definidas con structs y typedefs. A continuación comparto mi implementación de una lib en la que estoy trabajando.

Con este tipo de implementación, se puede pensar en cada nuevo tipo, definido con typedef, como una pseudo-clase. Aquí, esta pseudo-clase es el conjunto del código fuente (some_type_implementation.c)y su archivo de cabecera (some_type_implementation.h).

En el código fuente, debe definir la estructura que presenta el nuevo tipo. Observe la estructura en el nodo".c " archivo fuente. Allí hice un puntero vacío al atributo "info". Este puntero puede llevar cualquier tipo de puntero (creo), pero el precio que tiene que pagar es un identificador de tipo dentro de la estructura (tipo int), y todos los conmutadores para hacer que el controlador propper de cada tipo definido. Por lo tanto, en el nodo.h "header file, definí el tipo "Node" (solo para evitar tener que escribir struct node cada vez), y también tuve que definir las constantes " EMPTY_NODE", "COMPLEX_NODE", y "MATRIX_NODE".

Puede realizar la compilación, a mano, con "gcc *.c-lm".

Main.c Source File

#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;
}

Nodo.c Source File

#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);
}

Nodo.h Header File

#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();

Matriz.c Source File

#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);
}

Matriz.h Header File

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();

Complejo.c Source File

#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);
}

Complejo.h Header File

#define ANALITIC 0 
#define POLAR    1 

typedef struct complex Complex;

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

Espero no haberme perdido nada.

Me gustaría programar mis futuros proyectos de "bajo nivel" en C en lugar de C++...

¿Por qué? ¿Su objetivo carece de un compilador de C++ o de tiempo de ejecución de C++?

Estoy usando la opción 2 para un par de colecciones de alto rendimiento, y es extremadamente lento trabajar a través de la cantidad de macro lógica necesaria para hacer algo realmente genérico en tiempo de compilación y que valga la pena usar. Estoy haciendo esto puramente para el rendimiento bruto (juegos). Se utiliza un método X-macros.

Un problema doloroso que surge constantemente con la opción 2 es: "Asumiendo un número finito de opciones, como las claves de 8/16/32/64 bits, ¿hago que dicho valor sea una constante y defino varias funciones cada uno con un elemento diferente de este conjunto de valores que constante puede tomar, o simplemente lo hago una variable miembro?"El primero significa una caché de instrucciones de menor rendimiento, ya que tiene muchas funciones repetidas con solo uno o dos números diferentes, mientras que el segundo significa que tiene que hacer referencia a las variables asignadas, lo que en el peor de los casos significa una pérdida de caché de datos. Dado que la opción 1 es puramente dinámica, hará que tales valores sean variables miembro sin siquiera pensar en ello. Este realmente es el micro-optimización, sin embargo.

También tenga en cuenta el equilibrio entre los punteros que devuelven vs.valores: este último es más eficiente cuando el tamaño del elemento de datos es menor o igual al tamaño del puntero; mientras que si el elemento de datos es más grande, es más probable que sea mejor devolver punteros que forzar una copia de un objeto grande devolviendo valor.

Sugiero encarecidamente optar por la opción 1 en cualquier escenario en el que no esté 100% seguro de que el rendimiento de la colección será tu cuello de botella. Incluso con mi uso de la Opción 2, mi biblioteca de colecciones proporciona una "configuración rápida" que es como la Opción 1, es decir, el uso de void * valores en mi lista y mapa. Esto es suficiente para el 90% de las circunstancias.