Contenedores genéricos de tipo seguro con macros

Question

Estoy intentando hacer una lista enlazada genérica de tipo seguro en C usando macros. Debería funcionar de manera similar a cómo funcionan las plantillas en C++. Por ejemplo,

LIST(int) *list = LIST_CREATE(int); 

Mi primer intento fue para #define LIST(TYPE) (la macro Solía ​​arriba) para definir un struct _List_##TYPE {...}. Eso, sin embargo, no funcionó porque la estructura se redefiniría cada vez que declarara una nueva lista. Me remediado el problema al hacer esto:

/* You would first have to use this macro, which will define 
    the `struct _List_##TYPE`...        */ 
DEFINE_LIST(int); 

int main(void) 
{ 
    /* ... And this macro would just be an alias for the struct, it 
     wouldn't actually define it.         */ 
    LIST(int) *list = LIST_CREATE(int); 
    return 0; 
} 

/* This is how the macros look like */ 

#define DEFINE_LIST(TYPE) \ 
    struct _List_##TYPE  \ 
    {      \ 
     ...     \ 
    } 

#define LIST(TYPE)  \ 
    struct _List_##TYPE 

Sin embargo, otro problema es que cuando tengo varios archivos que utilizan DEFINE_LIST(int), por ejemplo, y algunos de ellos incluyen entre sí, entonces todavía habrá múltiples definiciones de la misma estructura ¿Hay alguna manera de hacer DEFINE_LIST comprobar si la estructura ya se ha definido?

/* one.h */ 
DEFINE_LIST(int); 

/* two.h */ 
#include "one.h" 
DEFINE_LIST(int); /* Error: already defined in one.h */ 

Answer 1

¿Por qué no utiliza una biblioteca? me gusta usar GLib pero no me gusta los punteros void en mi código, con el fin de obtener una versión de seguridad de tipos de los tipos de datos proporcionados por GLib codifiqué algunas macros muy sencillo:

http://pastebin.com/Pc0KsadV

Si quiero una lista de símbolo * (asumiendo que es un tipo I definida anteriormente) Sólo necesito a:

GLIST_INSTANCE(SymbolList, Symbol*, symbol_list); 

Si no desea utilizar una biblioteca entera (lo que sería una especie de exageración) para un simple ligado Enumere, implemente una lista que maneje void * y cree algunas funciones para encapsular y hacer el tipo correcto de conversión.

Answer 2

¿Qué tal crear un archivo list_template.h y luego crear un archivo list_TYPE.h y un archivo list_TYPE.c para cada instancia de la plantilla. Estos pueden venir con los protectores de encabezado adecuados, por supuesto. Solo puede incluir el encabezado de su plantilla, pero asegúrese de agregar todos los archivos .c al proceso de compilación y enlace, y debería funcionar.

Esto es básicamente lo que C++ hace automáticamente para usted ... La duplicación de los casos ...

Answer 3

Siempre se puede añadir un segundo argumento al DEFINE_LIST macro que le permitirá "nombre" de la lista. Por ejemplo:

#define DEFINE_LIST(TYPE, NAME)   \ 
struct _List_##TYPE_##NAME    \ 
{          \ 
    TYPE member_1;      \ 
    struct _List_##TYPE_##NAME* next; \ 
} 

entonces se podría simplemente hacer:

DEFINE_LIST(int, my_list); 
//... more code that uses the "my_list" type 

sólo tendría que limitarse a no volver a utilizar la misma lista de "nombre" cuando dos archivos de cabecera diferentes incluyen entre sí, y ambos usan la macro DEFINE_LIST. También debería consultar la lista por nombre cuando usa LIST_CREATE, etc.

Al pasar las listas a las funciones que ha escrito, siempre puede crear tipos "genéricos" que las versiones "nombradas" definidas por el usuario se lanzan a. Esto no debería afectar nada ya que la información real en el struct permanece igual, y la etiqueta "nombre" simplemente diferencia los tipos de una declaración en lugar de un punto de vista binario.Por ejemplo, aquí hay una función que toma objetos de la lista que almacenan int tipos:

#define GENERIC_LIST_PTR(TYPE) struct _generic_list_type_##TYPE* 
#define LIST_CAST_PTR(OBJ, TYPE) (GENERIC_LIST_PTR(TYPE))(OBJ) 

void function(GENERIC_LIST_PTR(INT) list) 
{ 
    //...use list as normal (i.e., access it's int data-member, etc.) 
} 

DEFINE_LIST(int, my_list); 

int main() 
{ 
    LIST(int, my_list)* list = LIST_CREATE(int, my_list); 
    function(LIST_CAST_PTR(list, int)); 

    //...more code 

    return 0; 
} 

Sé que esto no es necesariamente lo más conveniente, pero esto no resolver los problemas de nomenclatura, y se puede controlar qué versiones de struct _generic_list_type_XXX se crean en algún archivo de encabezado privado que otros usuarios no agregarán (a menos que deseen hacerlo para sus propios tipos) ... pero sería un mecanismo para separar la declaración y la definición de la lista genérica -type del tipo de lista definido por el usuario real.

Answer 4

Realmente dudo que pueda hacer una comprobación de existencia y definir (una estructura) en una macro. Ponga otra marca #ifndef antes de DEFINE_LIST(int). No es elegante, pero hace lo que quieres.

Answer 5

Abordé este problema en C antes de que las plantillas adquiridas en C++ y todavía tengo código.

No se puede definir una plantilla de contenedor-de-T verdaderamente segura y genérica con las macros de una manera que se limite por completo a los archivos de encabezado. El preprocesador estándar no proporciona ningún medio para "empujar" y "hacer estallar" las asignaciones de macros que necesitará para preservar su integridad mediante contextos de expansión anidados y secuenciales . Y encontrará contextos anidados tan pronto como trate de comer su propia comida para perros definiendo un contenedor-de-contenedores-de-T.

La cosa se puede hacer, como veremos, sino como @immortal sugiere, implica la generación de distintos .h y .c archivos para cada valor de T que necesite. Puede, por ejemplo, definir una lista de-T completamente genérico con macros en un archivo en línea, por ejemplo, list_type.inl, y luego incluir list_type.inl en un cada una de par de pequeños envoltorios de puesta a punto - list_float.h y list_float.c - que respectivamente definirán e implementarán el contenedor de lista de flotación. Del mismo modo para list-of-int, list-of-list-of-float, list-of-vector-of-list-of-double, y así sucesivamente.

Un ejemplo esquemático lo dejará todo en claro. Pero primero solo obtenga la medida completa de el desafío Eat-your-Own-Dogfood.

Considere un contenedor de segundo orden como una lista de listas de cosas. Queremos ser capaces de instanciar estos estableciendo T = list-of-thingummy para nuestra macro solución de lista-de-T. Pero de ninguna manera la lista de cosas va a ser un tipo de datos POD . Si la lista de cosas es nuestra propia comida para perros o la de otra persona, es que va a ser un tipo de datos abstracto que vive en el montón y se representa a a través de un tipo de puntero typedef-ed. O al menos, va a tener componentes dinámicos retenidos en el montón. En cualquier caso, no POD.

Esto significa que no es suficiente para nuestra solución de lista de T acaba de decir que T = list-of-thingummy. También se debe indicar si una T requiere una copia-construcción y destrucción que no sea POD , y en caso afirmativo cómo copiar-construir y destruir una . En términos de C, que significa:

• Copy-construcción: Cómo crear una copia de un determinado T en una región -T tamaño de la memoria no comprometida, dada la dirección de una región de este tipo.

• Destrucción: cómo destruir la T en una dirección determinada.

Nos podemos hacer sin saber acerca de la construcción por defecto o la construcción de parámetros no-T, como se puede restringir razonablemente nuestra solución lista-de-T para la contención de los objetos copiados de los originales suministrados por el usuario . Pero hacemos tenemos que copiarlos, y tenemos que deshacerse de nuestras copias.

A continuación, supongamos que aspiramos a ofrecer una plantilla para el conjunto de T o mapa de T1 a T2, , además de la lista de T. Estos tipos de datos ordenados por clave añaden otro parámetro , tendremos que conectarnos para cualquier valor que no sea POD de T o T1, es decir, cómo ordenar dos objetos cualquiera del tipo de clave. De hecho, necesitaremos ese parámetro para , cualquier tipo de datos clave para los cuales memcmp() no funcionarán.

Habiendo notado eso, nos quedaremos con el problema más simple de la lista de T para el ejemplo del esquema ; y para mayor simplicidad, olvidaré la conveniencia de cualquier API const.

Para este y cualquier otro tipo de contenedor de plantilla, querremos algunas macros que pegan token y que nos permiten ensamblar identificadores de funciones y tipos, plus probablemente otras macros de utilidades. Todo esto puede ir en un encabezado, macro_kit.h decir, tales como:

#ifndef MACRO_KIT_H 
#define MACRO_KIT_H 

/* macro_kit.h */ 

#define _CAT2(x,y) x##y 

// Concatenate 2 tokens x and y 
#define CAT2(x,y) _CAT2(x,y) 
// Concatenate 3 tokens x, y and z 
#define CAT3(x,y,z) CAT2(x,CAT2(y,z)) 

// Join 2 tokens x and y with '_' = x_y 
#define JOIN2(x,y) CAT3(x,_,y) 
// Join 3 tokens x, y and z with '_' = x_y_z 
#define JOIN3(x,y,z) JOIN2(x,JOIN2(y,z)) 
// Compute the memory footprint of n T's 
#define SPAN(n,T) ((n) * sizeof(T)) 

#endif 

ahora a la estructura esquemática de list_type.inl:

//! There is intentionally no idempotence guard on this file 
#include "macro_kit.h" 
#include <stddef.h> 

#ifndef INCLUDE_LIST_TYPE_INL 
#error This file should only be included from headers \ 
that define INCLUDE_LIST_TYPE_INL 
#endif 

#ifndef LIST_ELEMENT_TYPE 
#error Need a definition for LIST_ELEMENT_TYPE 
#endif 

/* list_type.inl 

    Defines and implements a generic list-of-T container 
    for T the current values of the macros: 

    - LIST_ELEMENT_TYPE: 
     - must have a definition = the datatype (or typedef alias) for \ 
     which a list container is required. 

    - LIST_ELEMENT_COPY_INITOR: 
     - If undefined, then LIST_ELEMENT_TYPE is assumed to be copy- 
     initializable by the assignment operator. Otherwise must be defined 
     as the name of a copy initialization function having a prototype of 
     the form: 

     LIST_ELEMENT_TYPE * copy_initor_name(LIST_ELEMENT_TYPE *pdest, 
              LIST_ELEMENT_TYPE *psrc); 

     that will attempt to copy the LIST_ELEMENT_TYPE at `psrc` into the 
     uncommitted memory at `pdest`, returning `pdest` on success and NULL 
     on failure. 

     N.B. This file itself defines the copy initializor for the list-type 
     that it generates. 

    - LIST_ELEMENT_DISPOSE 
     If undefined, then LIST_ELEMENT_TYPE is assumed to need no 
     destruction. Otherwise the name of a destructor function having a 
     protoype of the form: 

     void dtor_name(LIST_ELEMENT_TYPE pt*); 

     that appropriately destroys the LIST_ELEMENT_TYPE at `pt`. 

     N.B. This file itself defines the destructor for the list-type that 
     it generates. 
*/ 

/* Define the names of the list-type to generate, 
    e.g. list_int, list_float 
*/ 
#define LIST_TYPE JOIN2(list,LIST_ELEMENT_TYPE) 

/* Define the function-names of the LIST_TYPE API. 
    Each of the API macros LIST_XXXX generates a function name in 
    which LIST becomes the value of LIST_TYPE and XXXX becomes lowercase, 
    e.g list_int_new 
*/ 
#define LIST_NEW JOIN2(LIST_TYPE,new) 
#define LIST_NODE JOIN2(LIST_TYPE,node) 
#define LIST_DISPOSE JOIN2(LIST_TYPE,dispose) 
#define LIST_COPY_INIT JOIN2(LIST_TYPE,copy_init) 
#define LIST_COPY JOIN2(LIST_TYPE,copy) 
#define LIST_BEGIN JOIN2(LIST_TYPE,begin) 
#define LIST_END JOIN2(LIST_TYPE,end) 
#define LIST_SIZE JOIN2(LIST_TYPE,size) 
#define LIST_INSERT_BEFORE JOIN3(LIST_TYPE,insert,before) 
#define LIST_DELETE_BEFORE JOIN3(LIST_TYPE,delete,before) 
#define LIST_PUSH_BACK JOIN3(LIST_TYPE,push,back) 
#define LIST_PUSH_FRONT JOIN3(LIST_TYPE,push,front) 
#define LIST_POP_BACK JOIN3(LIST_TYPE,pop,back) 
#define LIST_POP_FRONT JOIN3(LIST_TYPE,pop,front) 
#define LIST_NODE_GET JOIN2(LIST_NODE,get) 
#define LIST_NODE_NEXT JOIN2(LIST_NODE,next) 
#define LIST_NODE_PREV JOIN2(LIST_NODE,prev) 

/* Define the name of the structure used to implement a LIST_TYPE. 
    This structure is not exposed to user code. 
*/ 
#define LIST_STRUCT JOIN2(LIST_TYPE,struct) 

/* Define the name of the structure used to implement a node of a LIST_TYPE. 
    This structure is not exposed to user code. 
*/ 
#define LIST_NODE_STRUCT JOIN2(LIST_NODE,struct) 

/* The LIST_TYPE API... */ 


// Define the abstract list type 
typedef struct LIST_STRUCT * LIST_TYPE; 

// Define the abstract list node type 
typedef struct LIST_NODE_STRUCT * LIST_NODE; 

/* Return a pointer to the LIST_ELEMENT_TYPE in a LIST_NODE `node`, 
    or NULL if `node` is null 
*/ 
extern LIST_ELEMENT_TYPE * LIST_NODE_GET(LIST_NODE node); 

/* Return the LIST_NODE successor of a LIST_NODE `node`, 
    or NULL if `node` is null. 
*/ 
extern LIST_NODE LIST_NODE_NEXT(LIST_NODE node); 

/* Return the LIST_NODE predecessor of a LIST_NODE `node`, 
    or NULL if `node` is null. 
*/ 
extern LIST_NODE LIST_NODE_PREV(LIST_NODE node); 


/* Create a new LIST_TYPE optionally initialized with elements copied from 
    `start` and until `end`. 

    If `end` is null it is assumed == `start` + 1. 

    If `start` is not NULL then elements will be appended to the 
    LIST_TYPE until `end` or until an element cannot be successfully copied. 
    The size of the LIST_TYPE will be the number of successfully copied 
    elements. 
*/ 
extern LIST_TYPE LIST_NEW(LIST_ELEMENT_TYPE *start, LIST_ELEMENT_TYPE *end); 

/* Dispose of a LIST_TYPE 
    If the pointer to LIST_TYPE `plist` is not null and addresses 
    a non-null LIST_TYPE then the LIST_TYPE it addresses is 
    destroyed and set NULL. 
*/ 
extern void LIST_DISPOSE(LIST_TYPE * plist); 

/* Copy the LIST_TYPE at `psrc` into the LIST_TYPE-sized region at `pdest`, 
    returning `pdest` on success, else NULL. 

    If copying is unsuccessful the LIST_TYPE-sized region at `pdest is 
    unchanged. 
*/ 
extern LIST_TYPE * LIST_COPY_INIT(LIST_TYPE *pdest, LIST_TYPE *psrc); 

/* Return a copy of the LIST_TYPE `src`, or NULL if `src` cannot be 
    successfully copied. 
*/ 
extern LIST_TYPE LIST_COPY(LIST_TYPE src); 

/* Return a LIST_NODE referring to the start of the 
    LIST_TYPE `list`, or NULL if `list` is null. 
*/ 
extern LIST_NODE LIST_BEGIN(LIST_TYPE list); 

/* Return a LIST_NODE referring to the end of the 
    LIST_TYPE `list`, or NULL if `list` is null. 
*/ 
extern LIST_NODE LIST_END(LIST_TYPE list); 

/* Return the number of LIST_ELEMENT_TYPEs in the LIST_TYPE `list` 
    or 0 if `list` is null. 
*/ 
extern size_t LIST_SIZE(LIST_TYPE list); 

/* Etc. etc. - extern prototypes for all API functions. 
    ... 
    ... 
*/ 

/* If LIST_IMPLEMENT is defined then the implementation of LIST_TYPE is 
    compiled, otherwise skipped. #define LIST_IMPLEMENT to include this 
    file in the .c file that implements LIST_TYPE. Leave it undefined 
    to include this file in the .h file that defines the LIST_TYPE API. 
*/ 
#ifdef LIST_IMPLEMENT 
// Implementation code now included. 

// Standard library #includes...? 

// The heap structure of a list node 
struct LIST_NODE_STRUCT { 
    struct LIST_NODE_STRUCT * _next; 
    struct LIST_NODE_STRUCT * _prev; 
    LIST_ELEMENT_TYPE _data[1]; 
}; 

// The heap structure of a LIST_TYPE 
struct LIST_STRUCT { 
    size_t _size; 
    struct LIST_NODE_STRUCT * _anchor; 
}; 

/* Etc. etc. - implementations for all API functions 
    ... 
    ... 
*/ 

/* Undefine LIST_IMPLEMENT whenever it was defined. 
    Should never fall through. 
*/ 
#undef LIST_IMPLEMENT 

#endif // LIST_IMPLEMENT 

/* Always undefine all the LIST_TYPE parameters. 
    Should never fall through. 
*/ 
#undef LIST_ELEMENT_TYPE 
#undef LIST_ELEMENT_COPY_INITOR 
#undef LIST_ELEMENT_DISPOSE 
/* Also undefine the "I really meant to include this" flag. */ 

#undef INCLUDE_LIST_TYPE_INL 

Tenga en cuenta que no tiene list_type.inl macro-guardia contra la inclusión del mutliple. Desea que al menos parte de ella, al menos la plantilla API, se incluya cada vez que se vea .

Si lee los comentarios en la parte superior del archivo, puede adivinar cómo codificaría un encabezado de embalaje para importar un tipo de contenedor de lista de int.

#ifndef LIST_INT_H 
#define LIST_INT_H 

/* list_int.h*/ 

#define LIST_ELEMENT_TYPE int 
#define INCLUDE_LIST_TYPE_INL 
#include "list_type.inl" 

#endif 

y asimismo cómo se codificar el encabezado de envoltura para importar una lista de lista de tipo int- contenedor:

#ifndef LIST_LIST_INT_H 
#define LIST_LIST_INT_H 

/* list_list_int.h*/ 

#define LIST_ELEMENT_TYPE list_int 
#define LIST_ELEMENT_COPY_INIT list_int_copy_init 
#define LIST_ELEMENT_DISPOSE list_int_dispose 
#define INCLUDE_LIST_TYPE_INL 
#include "list_type.inl" 

#endif 

Sus aplicaciones pueden incluir de manera segura dichos envoltorios, por ejemplo,

#include "list_int.h" 
#include "list_list_int.h" 

a pesar de la Definen LIST_ELEMENT_TYPE de maneras contradictorias porque list_type.inl siempre #undefs todas las macros que parametrizan la lista de tipo cuando se hace con ellos: ver las últimas líneas del archivo.

Tenga en cuenta también el uso de la macro LIST_IMPLEMENT. Si no está definido cuando list_type.inl se analiza, solo se expone la plantilla API; la implementación de la plantilla es omitida. Si se define LIST_IMPLEMENT, entonces se compila todo el archivo.Por lo tanto, nuestros encabezados de embalaje , al no definir LIST_IMPLEMENT, importan solo la API tipo lista.

inversa para nuestros archivos de origen envoltura list_int.c, list_list_int.c, vamos a definir LIST_IMPLEMENT. Después de eso, no hay nada que hacer, pero incluyen la correspondiente cabecera:

/* list_int.c */ 
#define LIST_IMPLEMENT 
#include "list_int.h" 

y:

/* list_list_int.c*/ 
#include "list_int.h" 
#define LIST_IMPLEMENT 
#include "list_list_int.h" 

Ahora en su aplicación, no hay lista de macros en plantillas aparecen. Sus envolver cabeceras analizan a nombre de "código real": (!)

#include "list_int.h" 
#include "list_list_int.h" 
// etc. 

int main(void) 
{ 
    int idata[10] = {1,2,3,4,5,6,7,8,9,10}; 
    //... 
    list_int lint = list_int_new(idata,idata + 10); 
    //... 
    list_list_int llint = list_list_int_new(&lint,0); 
    //... 
    list_int_dispose(&lint); 
    //... 
    list_list_int_dispose(&llint); 
    //... 
    exit(0); 
} 

equiparse con una "biblioteca de plantillas C" de esta manera el único trabajo duro es escribir el archivo .inl para cada tipo de contenedor que quiere y para probarlo muy, muy a fondo. Probablemente genere un archivo de objeto y un encabezado para cada combinación de tipo de datos nativo y tipo de contenedor para vinculación comercial y elimine las envolturas .h y .c en un abrir y cerrar de ojos para otros tipos bajo demanda.

Huelga decir que, tan pronto como C++ brotaron plantillas mi entusiasta para sudar de esta manera se evaporó. Pero se puede hacer de esta manera, completamente genéricamente, si por alguna razón C es la única opción.

Answer 6

Es posible crear contenedores genéricos y tipográficos con macros. Desde el punto de vista de la teoría de la computación, el lenguaje (código) generado a partir de las macroexpansiones puede ser reconocido por un autómata de empuje no determinista, lo que significa que es como máximo una gramática libre de contexto. La declaración mencionada hace que nuestro objetivo parezca imposible de lograr ya que el contenedor y sus iteradores afiliados deben recordar el tipo que contienen, pero esto solo puede hacerse mediante una gramática sensible al contexto. Sin embargo, podemos hacer algunos trucos!

La clave del éxito radica en el proceso de compilación, creación de tablas de símbolos. Si el tipo de variable se puede reconocer cuando el compilador consulta la tabla y no se produce una conversión de tipo inseguro, se considera seguro para el tipo. Por lo tanto, tenemos que dar a cada struct un nombre especial porque el nombre de la estructura puede entrar en conflicto si se declaran dos o más estructuras en el mismo nivel de alcance. La forma más fácil es agregar el número de línea actual al nombre de la estructura. El estándar C admite la macro predefinida __LINE__ y macro concatenation/ desde ANSI C (C89/C90).

Entonces, lo que tenemos que hacer es ocultar algunos atributos en la estructura que definimos anteriormente. Si desea crear otro registro de lista en tiempo de ejecución, poner un puntero a sí mismo en la estructura realmente resolverá el problema. Sin embargo, esto no es suficiente. Es posible que necesitemos una variable adicional para almacenar cuántos registros de lista asignamos en tiempo de ejecución. Esto nos ayuda a descubrir cómo liberar la memoria cuando la lista es destruida explícitamente por los programadores. Además, podemos aprovechar la extensión __typeof__() que es ampliamente utilizada en macroprogramación.

yo soy el autor de la OpenGC3 que tiene por objeto con seguridad de tipos de construcción contenedores genéricos con macros, y aquí es un ejemplo corto y breve de cómo funciona esta biblioteca las obras:

ccxll(int) list;      // declare a list of type int 
ccxll_init(list);      // initialize the list record 

for (int cnt = 8; cnt-- > 0;)  // 
    ccxll_push_back(list, rand()); // insert "rand()" to the end 

ccxll_sort(list);      // sort with comparator: XLEQ 

CCXLL_INCR_AUTO(pnum, list)   // traverse the list forward: 
    printf("num = %d\n", *pnum);  // access elems through iters 

ccxll_free(list);      // destroy the list after use 

Es bastante similar a la sintaxis de la STL. El tipo de lista se determina cuando se declara list. No tenemos que preocuparnos por la seguridad del tipo porque no hay un tipo de transmisión inseguro cuando se realizan operaciones en la lista.