Contenedores generics de tipo seguro con macros.

Estoy tratando de hacer una lista enlazada genérica segura para el tipo 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 bash fue para #define LIST(TYPE) (la macro que usé anteriormente) para definir una struct _List_##TYPE {...} . Sin embargo, eso no funcionó porque la estructura se redefiniría cada vez que declarara una nueva lista. Remedia el problema haciendo 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 

Pero otro problema es que cuando tengo varios archivos que usan DEFINE_LIST(int) , por ejemplo, y algunos de ellos se incluyen entre sí, entonces todavía habrá múltiples definiciones de la misma estructura. ¿Hay alguna manera de hacer que DEFINE_LIST verifique 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 */ 

Resolví este problema en C antes de que C ++ adquiriera plantillas y todavía tengo código.

No puede definir una plantilla realmente genérica de contenedor-de-T con macros de una manera que se limite por completo a los archivos de encabezado. El preprocesador estándar no proporciona medios para “empujar” y “hacer estallar” las asignaciones de macros que necesitará para preservar su integridad a través de contextos de expansión nesteds y secuenciales. Y se encontrará con contextos nesteds tan pronto como intente comer su propia comida para perros definiendo un contenedor de contenedores de T.

Se puede hacer la cosa, como veremos, pero como sugiere @immortal, implica generar distintos archivos .h y .c para cada valor de T que necesite. Por ejemplo, puede definir una lista de T genérica completa con macros en un archivo en línea, por ejemplo, list_type.inl , y luego incluir list_type.inl en cada par de envoltorios de configuración pequeños – list_float.h y list_float.c – que definirá e implementará respectivamente el contenedor de lista de flotadores. De manera similar para list-of-int, list-of-list-of-float, list-of-vector-of-list-of-double, etc.

Un ejemplo esquemático lo aclarará todo. Pero primero solo obtén la medida completa del desafío de comer tu propio perro.

Considere tal contenedor de segundo orden como una lista de listas de objetos. Queremos poder crear una instancia de estos mediante el establecimiento de T = list-of-thingummy para nuestra solución de macro de lista de t. Pero de ninguna manera la lista de cosas será un tipo de datos POD. Ya sea que list-of-thingummy sea nuestra propia comida para perros o la de alguien más, será un tipo de datos abstracto que vive en el montón y se representa a sus usuarios a través de un tipo de puntero de tipo typedef-ed. O al menos, tendrá componentes dynamics en el montón. En cualquier caso, no POD.

Esto significa que no es suficiente que a nuestra solución de lista de T solo se le diga que T = list-of-thingummy. También se debe informar si una T requiere una construcción y destrucción de copias que no sean POD y, en caso afirmativo, cómo copiar-construir y destruir una. En términos C, eso significa:

  • Copia-construcción: cómo crear una copia de una T dada en una región de tamaño de T de memoria no confirmada, dada la dirección de dicha región.

  • Destrucción: Cómo destruir la T en una dirección dada.

Podemos hacerlo sin conocer la construcción por defecto o la construcción a partir de parámetros no-T, ya que podemos restringir razonablemente nuestra solución de lista de T a la contención de objetos copiados de originales suministrados por el usuario. Pero tenemos que copiarlos, y tenemos que deshacernos de nuestras copias.

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

Habiendo notado eso, seguiremos con el problema más simple de la lista de T para el ejemplo esquemático; y para mayor simplicidad, me olvidaré de la conveniencia de cualquier API de const .

Para este y cualquier otro tipo de contenedor de plantillas, querremos algunas macros de pegado de tokens que nos permitan ensamblar convenientemente identificadores de funciones y tipos, y probablemente otras macros de utilidad. Todos estos pueden ir en un encabezado, digamos macro_kit.h , como por ejemplo:

 #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  #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. NB 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`. NB This file itself defines the destructor for the list-type that it generates. */ /* Define the names of the list-type to generate, eg 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, eg 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 list_type.inl no tiene list_type.inl macros contra la inclusión múltiple. 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 ajuste 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 de la misma manera cómo codificaría el encabezado de ajuste para importar un tipo de contenedor de lista de lista de int:

 #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 forma segura tales envoltorios, por ejemplo,

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

a pesar de que definen LIST_ELEMENT_TYPE de manera conflictiva porque list_type.inl siempre #undefs todas las macros que parametrizan el tipo de lista cuando se hace con ellas: vea las últimas líneas del archivo.

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

A la inversa, para nuestros archivos de origen de list_int.c , list_list_int.c , definiremos LIST_IMPLEMENT . Después de eso, no hay nada que hacer sino incluir el encabezado correspondiente:

 /* 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 aparecen macros de lista de plantillas. Sus cabeceras de envoltorio se analizan en “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); } 

Para equiparse con una “biblioteca de plantillas en C” de esta manera, el único trabajo (!) Es escribir el archivo .inl para cada tipo de contenedor que desee y probarlo muy, muy a fondo. Probablemente, luego generaría un archivo de objeto y un encabezado para cada combinación de tipo de datos nativo y tipo de contenedor para un enlace comercial, y eliminaría las envolturas .h y .c en un santiamén para otros tipos a pedido.

No hace falta decir que, tan pronto como C ++ brotaron las plantillas, mi entusiasmo por sudarlas de esta manera se evaporó. Pero se puede hacer de esta manera, de forma totalmente genérica, si por alguna razón C es la única opción.

Siempre puede agregar un segundo argumento a la macro DEFINE_LIST que le permitirá “nombrar” la lista. Por ejemplo:

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

Entonces podrías simplemente hacer:

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

Solo tendría que limitarse a no reutilizar el mismo “nombre” de lista cuando dos archivos de encabezado diferentes se incluyan entre sí, y ambos utilicen la macro DEFINE_LIST . También tendría que referirse a la lista por su nombre cuando use LIST_CREATE , etc.

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

 #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 (ie, 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 resuelve los problemas de nombres, y puede controlar a 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). -hacer para sus propios tipos) … pero sería un mecanismo para separar la statement y la definición del tipo de lista genérico del tipo de lista definido por el usuario real.

¿Por qué no usas una biblioteca? Me gusta usar GLib pero odio los punteros de vacío en mi código, para obtener una versión segura de los tipos de datos proporcionados por GLib codifiqué algunas macros muy simples:

http://pastebin.com/Pc0KsadV

Si quiero una lista de Símbolo * (asumiendo que es un tipo que definí anteriormente) solo necesito:

 GLIST_INSTANCE(SymbolList, Symbol*, symbol_list); 

Si no desea usar una biblioteca completa (lo que sería un tipo de exceso) para una lista enlazada simple, implemente una lista que maneje el nulo * y cree algunas funciones para encapsular y hacer la conversión de tipos correcta.

¿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 cabecera adecuados, por supuesto. Entonces, solo puede incluir el encabezado de su plantilla, pero asegúrese de agregar todos los archivos .c al proceso de comstackción y enlace, y debería funcionar.

Esto es básicamente lo que C ++ hace automáticamente por usted … Duplicando las instancias …

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

Es posible crear contenedores generics y de tipo seguro con macros. Desde el punto de vista de la teoría de la computación, el lenguaje (código) generado a partir de las expansiones macro puede reconocerse mediante un autómata pushdown no determinista, lo que significa que es a lo sumo una gramática libre de contexto. La statement mencionada hace que nuestro objective parezca imposible de lograr, ya que el contenedor y sus iteradores afiliados deben recordar el tipo que contiene, 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 comstackción, la creación de tablas de símbolos. Si el tipo de variable se puede reconocer cuando el comstackdor consulta la tabla y no se produce una conversión de tipos no segura, se considera que es de tipo seguro. 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 scope. La forma más sencilla es agregar el número de línea actual al nombre de la estructura. El estándar C es compatible con la macro predefinida __LINE__ y la concatenación / clasificación de macros desde ANSI C (C89 / C90).

Entonces, lo que tenemos que hacer es ocultar algunos atributos en la estructura que definimos como anteriormente. Si desea crear otro registro de lista en tiempo de ejecución, coloque un puntero sobre sí mismo en la estructura para 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 los progtwigdores destruyen explícitamente la lista. Además, podemos aprovechar la extensión __typeof__() que se usa ampliamente en la progtwigción de macros.

Soy el autor de OpenGC3, cuyo objective es crear contenedores generics seguros para el tipo con macros, y aquí hay un breve y breve ejemplo de cómo funciona esta biblioteca:

 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 syntax de la STL. El tipo de lista se determina cuando se declara la list . No tenemos que preocuparnos por el tipo de seguridad porque no hay conversión de tipos no segura cuando se realizan operaciones en la lista.