¿Cuál es la mejor manera de escribir código genérico de plantilla de clase en C?

Question

Necesito escribir AVL-tree con tipo genérico en C. Lo mejor que sé es usar [void *] y escribir algunas funciones para crear, copiar, asignar y destruir. Por favor, cuéntame una mejor manera.

Answer 1

Le daré un ejemplo de cómo puede lograr la funcionalidad de genéricos en C. El ejemplo está en una lista vinculada, pero estoy seguro de que puede adaptarlo en su árbol AVL si es necesario.

En primer lugar, deberá definir una estructura para el elemento de la lista. Una posible (implementación más sencilla):

struct list_element_s { 
    void *data; 
    struct list_element_s *next; 

}; 
typedef struct list_element_s list_element; 

Donde 'datos' actuará como el "contenedor" en el que se va a mantener su información, y 'siguiente' es la referencia al elemento vinculado directa. (NOTA: el elemento del árbol binario debe incluir una referencia a los elementos secundarios derecho/izquierdo).

Después de crear su estructura de elementos, necesitará crear su estructura de lista. Una buena práctica es tener algunos miembros que apunten a funciones: destructor (necesario para liberar la memoria retenida por "datos") y comparador (para poder comparar dos de los elementos de su lista).

Una lista implementación estructura podría tener este aspecto:

struct list_s { 
    void (*destructor)(void *data);  
    int (*cmp)(const void *e1, const void *e2); 
    unsigned int size; 
    list_element *head; 
    list_element *tail; 

}; 
typedef struct list_s list; 

Después de diseñar la estructura de datos, debe diseñar la interfaz de estructura de datos. Digamos que nuestra lista tendrá la siguiente, más simple, interfaz:

nmlist *list_alloc(void (*destructor)(void *data)); 
int list_free(list *l); 
int list_insert_next(list *l, list_element *element, const void *data); 
void *list_remove_next(list *l, list_element *element); 

Dónde:

• list_alloc: se Alocate memoria para su lista.
• list_free: liberará la memoria asignada para la lista, y todos los 'datos' serán retenidos por list_element (s).
• list_insert_next: insertará un nuevo elemento junto a 'element'. Si 'element' es NULL, la inserción se realizará al principio de la lista.
• list_remove_next: eliminará & return (void *) 'data' retenido por 'element-> next'. Si 'element' es NULL, realizará "list-> head removal".

Y ahora la implementación funciones:

list *list_alloc(void (*destructor)(void *data)) 
{ 
    list *l = NULL; 
    if ((l = calloc(1,sizeof(*l))) != NULL) { 
     l->size = 0; 
     l->destructor = destructor; 
     l->head = NULL; 
     l->tail = NULL; 
    } 
    return l; 
} 

int list_free(list *l) 
{ 
    void *data; 
    if(l == NULL || l->destructor == NULL){ 
     return (-1); 
    }  
    while(l->size>0){  
     if((data = list_remove_next(l, NULL)) != NULL){ 
      list->destructor(data); 
     } 
    } 
    free(l); 
    return (0); 
} 

int list_insert_next(list *l, list_element *element, const void *data) 
{ 
    list_element *new_e = NULL; 
    new_e = calloc(1, sizeof(*new_e)); 
    if (l == NULL || new_e == NULL) { 
     return (-1); 
    } 
    new_e->data = (void*) data; 
    new_e->next = NULL; 
    if (element == NULL) { 
     if (l->size == 0) { 
      l->tail = new_e; 
     } 
     new_e->next = l->head; 
     l->head = new_e; 
    } else { 
     if (element->next == NULL) { 
      l->tail = new_e; 
     } 
     new_e->next = element->next; 
     element->next = new_e; 
    } 
    l->size++; 
    return (0); 
} 

void *list_remove_next(list *l, list_element *element) 
{ 
    void *data = NULL; 
    list_element *old_e = NULL; 
    if (l == NULL || l->size == 0) { 
     return NULL; 
    } 
    if (element == NULL) { 
     data = l->head->data; 
     old_e = l->head; 
     l->head = l->head->next; 
     if (l->size == 1) { 
      l->tail = NULL; 
     } 
    } else { 
     if (element->next == NULL) {  
      return NULL;  
     }  
     data = element->next->data; 
     old_e = element->next; 
     element->next = old_e->next; 
     if (element->next == NULL) { 
      l->tail = element; 
     } 
    } 
    free(old_e); 
    l->size--; 
    return data; 
} 

Y ahora, cómo utilizar su implementación simple lista enlazada genérico.En el siguiente ejemplo, la lista está actuando como una pila:

#include <stdlib.h> 
#include <stdio.h> 
#include "nmlist.h" 

void simple_free(void *data){ 
    free(data); 
} 

int main(int argc, char *argv[]){ 
    list *l = NULL; 
    int i, *j; 

    l = list_alloc(simple_free); 
    for(i = 0; i < 10; i++){ 
     j = calloc(1, sizeof(*j)); 
     if(j != NULL){ 
      *j = i; 
      list_insert_next(l, NULL, (void*) j); 
     } 
    } 

    for(i = 0; i < 10; i++){ 
     j = (int*) list_remove_next(l, NULL); 
     if(j != NULL){ 
      printf("%d \n", *j); 
     } 
    } 

    list_free(l); 

    return (0); 
} 

Tenga en cuenta que en lugar de "int * j" se puede utilizar un puntero que hace referencia a estructuras más complejas. Si lo hace, no se olvide de modificar su función 'list-> destructor' en consecuencia.

Answer 2

Lo que dijo Alex. En c, void * es lo que hay.

Suponiendo que debe trabajar en C, sin embargo ... ¿Por qué necesita proporcionar las funciones de creación/copia/asignación/destrucción a la biblioteca? ¿Qué características de esta biblioteca requieren el código del árbol AVL para usar esas operaciones?

Las principales operaciones en un árbol de búsqueda son insertar, eliminar y buscar, ¿correcto? Tendrá que proporcionar una función de comparación para todas esas operaciones, pero debe permitir que los clientes de esta biblioteca manejen todas las demás operaciones. Simple es probablemente mejor en este caso.

Answer 3

Para hacer genéricos reales, eficaces en C, hackear con el preprocesador. Este enfoque tiene muchas de las mismas desventajas del enfoque de plantilla de C++; a saber, que todos (la mayoría, de todos modos) código deben vivir en archivos de encabezado, y la depuración y la prueba son un problema. Las ventajas también están ahí; que puede obtener un rendimiento superior y dejar que el compilador haga todo tipo de operaciones para acelerar las cosas, minimizar las asignaciones reduciendo indirectamente y un poco de seguridad tipo.

La definición parece (imaginemos que tenemos un conjunto de hash)

int my_int_set(int x); 
#define HASH_SET_CONTAINED_TYPE int 
#define HASH_SET_TYPE my_int_set 
#define HASH_SET_FUNC hash_int 
#include "hash_set.h" 

Y después de usarlo, sólo tiene que utilizar el tipo que creó anteriormente:

my_int_set x; 
my_int_set_init(&x); 
my_int_set_add(&x, 7); 
if (my_int_set_check(&x, 7)) printf("It worked!\n"); 
... 
// or, if you prefer 
my_int_set *x = my_int_set_create(); 

Internamente, esto es implementado por un grupo completo de pegado de tokens, etc., y (como se señaló anteriormente) es un gran dolor para probar.

Así que algo como:

#ifndef HASH_SET_CONTAINED_TYPE 
    #error Must define HASH_SET_CONTAINED_TYPE 
#endif 
... /// more parameter checking 

#define HASH_SET_ENTRY_TYPE HASH_SET_TYPE ## _entry 
typedef struct HASH_SET_ENTRY_TYPE ## _tag { 
    HASH_SET_CONTAINED_TYPE key; 
    bool present; 
} HASH_SET_ENTRY_TYPE; 
typedef struct HASH_SET_TYPE ## _tag { 
    HASH_SET_TYPE ## _entry data[]; 
    size_t elements; 
} HASH_SET_TYPE; 

void HASH_SET_TYPE ## _add(HASH_SET_CONTAINED_TYPE value) { 
    ... 
} 
... 
#undef HASH_SET_CONTAINED_TYPE 
... // remaining uninitialization 

Incluso se puede añadir opciones; como #define HASH_SET_VALUE_TYPE o #define HASH_SET_DEBUG.