listas - Las estructuras de datos genéricos de tipo seguro en C simple?
listas enlazadas ejemplos (10)
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 un tiempo de ejecución de C ++?
He hecho mucha más programación C ++ que la programación "simple antigua C". Una cosa que extraño mucho cuando programo en la C simple son las estructuras de datos genéricos seguros de tipo, que se proporcionan en C ++ a través de plantillas.
En aras de lo concreto, considere una lista genérica de enlace único. En C ++, es una cuestión simple definir su propia clase de plantilla, y luego crear una instancia para los tipos que necesita.
En C, puedo pensar en algunas formas de implementar una lista genérica de enlace único:
- Escriba los tipos de lista vinculados y los procedimientos de respaldo una vez, usando punteros vacíos para recorrer el sistema de tipos.
- Escriba las macros del preprocesador tomando los nombres de tipos necesarios, etc., para generar una versión específica de tipo de la estructura de datos y los procedimientos de soporte.
- Use una herramienta independiente más sofisticada para generar el código para los tipos que necesita.
No me gusta la opción 1, ya que subvierte el sistema de tipo, y probablemente tenga un peor rendimiento que una implementación especializada específica de tipo. El uso de una representación uniforme de la estructura de datos para todos los tipos, y la conversión a / desde punteros vacíos, hasta donde puedo ver, necesita un direccionamiento indirecto que podría evitarse mediante una implementación especializada para el tipo de elemento.
La opción 2 no requiere ninguna herramienta adicional, pero se siente un poco torpe, y podría dar errores de compilador incorrectos cuando se usa incorrectamente.
La opción 3 podría dar mejores mensajes de error del compilador que la opción 2, ya que el código de estructura de datos especializados residiría en forma expandida que podría abrirse en un editor e inspeccionarse por el programador (a diferencia del código generado por las macros del preprocesador). Sin embargo, esta opción es la más pesada, una especie de "plantillas de pobres". He utilizado este enfoque antes, usando un simple script sed para especializar una versión "con plantilla" de algún código C.
Me gustaría programar mis futuros proyectos de "bajo nivel" en C en lugar de C ++, pero me ha asustado la idea de reescribir estructuras de datos comunes para cada tipo específico.
¿Qué experiencia tienen las personas con este problema? ¿Hay buenas bibliotecas de estructuras de datos genéricos y algoritmos en C que no se ajustan a la Opción 1 (es decir, conversión desde y hacia punteros vacíos, que sacrifica la seguridad del tipo y agrega un nivel de indirección)?
C tiene un tipo diferente de belleza que C ++, y tipo seguridad y poder ver siempre qué es todo cuando rastrear a través del código sin involucrar moldes en su depurador normalmente no es uno de ellos.
La belleza de C proviene en gran medida de su falta de seguridad de tipo, de trabajar en torno al sistema de tipos y en el nivel básico 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, las estructuras de longitud variable, el uso de 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 de preservar ABI cuando trabajas en este nivel inferior.
Así que hay un tipo diferente de estética involucrado aquí, así como diferentes desafíos, y recomendaría un cambio de mentalidad cuando trabajes en C. Para realmente apreciarlo, te sugiero que hagas cosas que mucha gente da por sentadas estos días, como implementando su propio asignador de memoria o controlador de dispositivo. Cuando trabajas en un nivel tan bajo, no puedes 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 el código de manipulación de bit / byte de bajo nivel donde 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 enlazada, sugeriría una versión no intrusiva de un nodo vinculado (uno que no requiera almacenar punteros de lista en el tipo de elemento, T , en sí mismo, permitiendo que la lógica y representación de la lista enlazada se desacople de la propia T ), al igual que:
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 como ese:
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;
Como es C, no hay verificación de tipo alguna cuando se lanzan punteros de esta forma, y eso probablemente también te dará una sensación incómoda si vienes de un fondo de C ++.
La parte difícil aquí es asegurarse de que este miembro, element , esté alineado correctamente para el tipo que desee almacenar. Cuando pueda resolver ese problema de la manera más portable que necesita, tendrá una solución poderosa para crear diseños y asignaciones de memoria eficientes. A menudo, esto hará que solo utilice la alineación máxima para todo lo que pueda parecer un desperdicio, pero normalmente no lo es si está utilizando estructuras de datos y asignadores adecuados 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. Es poco lo que puede hacer si no dispone de una versión separada del código de este nodo de lista y la lógica correspondiente para trabajar con él para cada tipo, T, que desee admitir (salvo el polimorfismo dinámico). Sin embargo, no implica un nivel adicional de direccionamiento indirecto, ya que podría haber pensado que era necesario, y aún así asigna el nodo y el elemento de la lista completa en una única asignación.
Y recomendaría esta forma simple de lograr genericidad en C en muchos casos. Simplemente reemplace T con un buffer que tenga un sizeof(T) coincidencia de longitud de sizeof(T) y 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 los golpes de caché, reduce la frecuencia de asignaciones / desasignaciones de montones, la cantidad de indirección requerida, tiempos de construcción, etc.
Si necesita más automatización como list_new_node inicializar struct Foo , recomendaría crear una estructura de tabla de tipo general que pueda pasar que contenga información como qué tan grande es T, un puntero de función apuntando a una función para crear una instancia predeterminada de T , otro para copiar T, clonar T, destruir T, un comparador, etc. En C ++, puede generar esta tabla automáticamente usando plantillas y conceptos de lenguaje integrados como constructores de copia y destructores. C requiere un poco más de esfuerzo manual, pero aún puede reducirlo un poco con macros.
Otro truco que puede ser útil si se usa una ruta de generación de código orientada a macros es cobrar un prefijo o convención de nomenclatura basada en sufijos de identificadores. Por ejemplo, CLONE (Type, ptr) podría definirse 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 parecido a la sobrecarga de funciones en C, y es útil cuando se genera código a granel (cuando CLONE se usa para implementar otra macro) o incluso un poco de copiar y pegar código repetitivo al menos mejorar la uniformidad de la repetición.
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 por rendimiento crudo (juegos). Se usa un enfoque X-macros .
Un problema doloroso que surge constantemente con la Opción 2 es: "Suponiendo un número finito de opciones, como las claves de 8/16/32/64 bits, ¿hago que dicho valor sea constante y defino varias funciones, cada una con un elemento diferente de este conjunto de valores que la constante puede asumir, ¿o simplemente lo hago una variable miembro? " El primero significa un caché de instrucciones menos eficiente ya que tiene muchas funciones repetidas con solo uno o dos números diferentes, mientras que el último significa que debe hacer referencia a las variables asignadas, lo que en el peor de los casos significa que falta un caché de datos. Como la Opción 1 es puramente dinámica, hará que dichos valores sean variables miembro sin siquiera pensar en ello. Esto realmente es una micro-optimización, sin embargo.
Además, tenga en cuenta el compromiso entre punteros de devolución y valores: el último es más eficaz cuando el tamaño del elemento de datos es menor o igual que el tamaño del puntero; mientras que si el elemento de datos es más grande, lo más probable es que sea mejor devolver los punteros que forzar una copia de un objeto grande devolviendo el valor.
Recomiendo ir por la Opción 1 en cualquier escenario en el que no esté 100% seguro de que el rendimiento de la colección será su 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 los valores void * en mi lista y mapa. Esto es suficiente para el 90% de las circunstancias.
GLib tiene una serie de estructuras de datos genéricos, http://www.gtk.org/
CCAN tiene un montón de fragmentos útiles y tales ccan.ozlabs.org
Hay una variación común en la opción 1, que es más eficiente ya que usa las uniones para almacenar los valores en los nodos de la lista, es decir, no hay indirección adicional. Esto tiene la desventaja 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 de la union utilizando un miembro flexible de matriz 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;
}
La opción 1 es el enfoque adoptado por la mayoría de las implementaciones C de contenedores genéricos que veo. El kit del controlador de Windows y el kernel de Linux usan una macro para permitir que los enlaces de los contenedores se incrusten en cualquier parte de una estructura, con la macro utilizada para obtener el puntero de estructura desde un puntero al campo de enlace:
La opción 2 es la táctica tomada por la implementación del contenedor tree.h y queue.h de BSD:
No creo que considere que ninguno de estos enfoques sea seguro. Útil, pero no tipo seguro.
La opción 1, ya sea usar void * o alguna variante basada en union , es lo que utilizan la mayoría de los programas de C, y puede proporcionarle 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 menos presión de icache y menos fallas de icache.
Su opción 1 es la que utilizarían la mayoría de los programadores de c tiempo, posiblemente con un poco de 2 para reducir el tipado repetitivo, y tal vez empleando algunos punteros a funciones para obtener un sabor de polimorfismo.
Una vieja pregunta, lo sé, pero en caso de que todavía tenga interés: estaba experimentando con la opción 2 (macros de preprocesador) hoy, y se me ocurrió el ejemplo que voy a pegar a continuación. Un poco torpe de hecho, pero no terrible. El código no es completamente seguro, pero contiene verificaciones de cordura para proporcionar un nivel razonable de seguridad. Y lidiar con los mensajes de error del compilador mientras escribía fue leve en comparación con lo que vi cuando las plantillas C ++ entraron en juego. Probablemente sea mejor comenzar a leer esto en el código de uso de ejemplo en la función "principal".
#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, puede pensar en cada tipo nuevo, definido con typedef, como una pseudoclase. 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 presentará el nuevo tipo. Tenga en cuenta la estructura en el archivo fuente "node.c". Allí hice un puntero nulo al atributo "información". Este puntero puede portar 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 definir el manejador apropiado de cada tipo. Entonces, en el archivo header.h ", 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".
archivo de origen main.c
#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;
}
Archivo de origen node.c
#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 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();
Archivo de origen matrix.c
#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 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();
Archivo fuente complex.c
#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);
}
Archivo de encabezado de complex.h
#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.