Type-sécurité générique des structures de données dans la plaine, vieux C?

C est un autre genre de beauté que C++, et le type de sécurité et d'être toujours en mesure de voir ce que tout est tracé à l'aide de code sans impliquer jette dans votre débogueur n'est généralement pas l'un d'eux.

C est la beauté vient beaucoup de son manque de sécurité de type, de contourner le système de type et à la crue au niveau des bits et des octets. En raison de cela, il y a certaines choses qu'il peut faire plus facilement sans lutter contre la langue, comme, par exemple, de longueur variable, aux structures, à l'aide de la pile de même pour les tableaux dont les dimensions sont déterminées au moment de l'exécution, etc. Il a aussi tendance à être beaucoup plus simple de préserver ABI lorsque vous travaillez à ce faible niveau.

Donc, il y a un type différent de l'esthétique impliqué ici, ainsi que les différents défis, et je le recommande un changement dans l'état d'esprit lorsque vous travaillez dans C. Pour vraiment l'apprécier, je vous suggère de faire des choses beaucoup de gens prennent pour acquis ces jours-ci, à l'instar de la mise en œuvre de votre propre allocateur de mémoire ou de pilote de périphérique. Lorsque vous travaillez à un niveau si faible, vous ne pouvez pas aider mais regarder tout ce que la mémoire des schémas de bits et d'octets par opposition aux "objets", avec des comportements attachés. En outre, il peut venir un moment dans ce bas-niveau bit/octet code de manipulation où C devient plus facile de comprendre que le code C++ jonché de reinterpret_casts, par exemple

Comme pour votre liste chaînée exemple, je vous suggère un non-intrusive version de nœud (qui ne nécessite pas de stockage de liste de pointeurs dans le type d'élément, les T, lui-même, permettant la liste liée de la logique et de la représentation pour être découplée de T lui-même), comme suit:

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

Maintenant, nous pouvons créer une liste de nœud comme suit:

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

Pour récupérer l'élément de la liste comme T*:

T* element = list_node->element;

Puisque c'est C, il n'y a pas de vérification de type que ce soit lors de la coulée des pointeurs de cette façon, et qui sera probablement également vous donner un sentiment de malaise si vous êtes en provenance d'un C++ arrière-plan.

La partie la plus délicate est de faire en sorte que ce membre, element, est correctement aligné quel que soit le type que vous souhaitez stocker. Quand vous pouvez résoudre ce problème de façon portable comme vous le souhaitez, vous aurez une solution puissante pour la création efficace de la mémoire et des mises allocateurs. Souvent, cela vous permettra de vous juste à l'aide de max alignement pour tout ce qui peut paraître aberrant, mais généralement ce n'est pas si vous êtes en utilisant des structures de données et les allocateurs qui ne sont pas à payer ces frais pour de nombreux petits éléments sur une base individuelle.

Maintenant cette solution implique la conversion de type. Il y a peu de choses que vous pouvez faire à ce sujet à moins d'avoir une version distincte de code de cette liste de nœud et de la logique correspondante de travailler avec elle pour chaque type, T, que vous souhaitez soutenir (à court de dynamique polymorphisme). Cependant, elle n'implique pas un niveau supplémentaire d'indirection que vous pourriez avoir pensé était nécessaire, et encore alloue la totalité de la liste de nœud et de l'élément en une allocation unique.

Et je recommanderais cette façon simple d'obtenir un genericity dans C dans beaucoup de cas. Il suffit de remplacer T avec un tampon a une longueur correspondant sizeof(T) et alignés correctement. Si vous avez un raisonnablement portable de manière sécurisée et vous pouvez généraliser pour assurer un alignement parfait, que vous aurez un très puissant moyen de travailler avec la mémoire d'une manière qui améliore souvent le cache, réduit la fréquence des allocations de tas/deallocations, le montant de l'indirection nécessaire, les temps de construire, etc.

Si vous avez besoin de plus d'automatisation comme avoir list_new_node initialiser automatiquement struct Foo, je recommande la création d'un général table de type struct que vous pouvez passer autour de laquelle contient des informations comme la façon dont big T est un pointeur de fonction qui pointe vers une fonction pour créer une instance par défaut de T, une autre pour copier T, clone T, détruire T, un comparateur, etc. En C++, vous pouvez générer ce tableau automatiquement à l'aide de modèles et intégré dans la langue des concepts comme la copie des constructeurs et des destructeurs. C nécessite un peu plus d'effort manuel, mais vous pouvez encore réduire le passe-partout un peu avec les macros.

Un autre truc qui peut être utile si vous allez avec un plus macro-orientée vers la génération de code de la route est de l'argent dans un préfixe ou un suffixe à base de convention de nommage des identifiants. Par exemple, CLONE(Type ptr) pourrait être défini pour revenir Type##Clone(ptr), donc CLONE(Foo, foo) peut invoquer FooClone(foo). C'est une sorte de tricher pour obtenir quelque chose qui ressemble à de surcharge de fonctions en C, et est utile lors de la génération de code en vrac (quand le CLONE est utilisé pour mettre en œuvre une autre macro) ou même un peu de la copie et collage de texte standard-type de code pour au moins améliorer l'uniformité de la réutilisable.

GLib est a un tas de données générique structures, http://www.gtk.org/

CCAN a un tas de utile des extraits et ces http://ccan.ozlabs.org/

Il y a une variation fréquente de l'option 1, qui est plus efficace, car elle utilise des syndicats pour stocker les valeurs dans la liste des noeuds, c'est à dire il n'y a aucun indirection. Cela a l'inconvénient que la liste accepte uniquement les valeurs de certains types et potentiellement les déchets de la mémoire si les types sont de tailles différentes.

Cependant, il est possible de se débarrasser de la union par la flexibilité des membres de la pile de la place si vous êtes prêt à casser la stricte aliasing. C99 exemple de code:

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

- Je utiliser des pointeurs void (void*) pour représenter les structures de données générique défini avec les structures et les typedefs. Ci-dessous je partage ma mise en œuvre d'une lib qui je travaille.

Avec ce type de mise en œuvre, vous pouvez penser de chaque nouveau type, défini avec la définition de type, comme une pseudo-classe. Ici, cette pseudo-classe est l'ensemble du code source (some_type_implementation.c) et son fichier d'en-tête (some_type_implementation.h).

Dans le code source, vous devez définir la structure qui présentera le nouveau type. Remarque la structure dans le "nœud.c" fichier source. Là, j'ai fait un vide pointeur vers le "info" attribut. Ce pointeur peut transporter n'importe quel type de pointeur (je pense), mais le prix que vous devez payer est un identificateur de type à l'intérieur de la structure (de type int), et tous les switchs pour faire de la propper poignée de chaque type défini. Ainsi, dans le nœud.h" fichier d'en-tête, j'ai défini le type "Nœud" (juste pour éviter d'avoir à type struct noeud à chaque fois), et aussi, j'ai eu à définir les constantes "EMPTY_NODE", "COMPLEX_NODE", et "MATRIX_NODE".

Vous pouvez effectuer la compilation, à la main, avec "gcc *.c -lm".

principal.Fichier Source 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;
}

nœud.Fichier Source 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);
}

nœud.h Fichier d'en-Tête

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

de la matrice.Fichier Source 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);
}

de la matrice.h Fichier d'en-Tête

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

complexe.Fichier Source 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);
}

complexe.h Fichier d'en-Tête

#define ANALITIC 0 
#define POLAR    1 
typedef struct complex Complex;
Complex* mkCpx(int type,double a,double b);
void printCpx(Complex* number);
void testCpx();

Je l'espère, je n'avais pas manqué de rien.