main

Les tableaux dynamiques :

Les tableaux dynamiques sont une très bonne alternative au listes chaînées.
Ils permettent de stocker un nombre variable et évolutif de données lorsque l'ordre de celles-ci n'ont pas d'importance.
Le tout est basé sur une structure de gestion, en effet en plus des données il faut conserver certaines informations concernant le tableau.
Ici quelques fonctions de base pour les tableaux dynamiques.

La structure utilisée :


typedef struct
{
    unsigned int inUse, /*number of value in use*/
                 capacity;  /*number of value it can store*/

    size_t elemSize;    /*byte length of one value*/
    void* data;    /*the data array itself*/
}
CEV_DynamicArray;
					

Définitions :

L'initialisation :


int CEV_tabInit(CEV_DynamicArray *table, unsigned int num, size_t size)
{/*structure init*/

    table->inUse    = 0;
    table->capacity = 0;
    table->elemSize = size;
    table->data    = malloc(size*num);

    if (table->data == NULL)
        return(FUNC_ERR);
    /*else*/
        table->capacity = num;

    return FUNC_OK;
}
						

  • table : est un pointeur vers une structure CEV_DynamicArray.
  • num : est le nombre d'élément que doit contenir la table
  • size : correspond à la taille d'un élément du tableau.
Si par exemple vous voulez gérer un tableau dynamique de int, disons 20 pour commencer, la fonction appelée sera du type CEV_tabInit(&maTable, 20, sizeof(int));

L'extension de la table:


int CEV_tabSizeExtend(CEV_DynamicArray *table)
{/*extend array by 1*/

    void* tempPtr = table->data;

    tempPtr = realloc(table->data, (table->capacity+1)*table->elemSize);   /*new size*/

    if (tempPtr == NULL)
    {/*on error*/
        fprintf(stderr, "Err / CEV_tabSizeExtend : %s.\n", strerror(errno));
        return(FUNC_ERR);
    }
    /*else*/
    table->capacity++;  /*1 more space available*/
    table->data = tempPtr;

    return(FUNC_OK);
}
						

Etend la table de données pour accueillir des données supplémentaire dans la table.
A utiliser si on voit venir, le plus souvent, j'utilise la version CEV_tabAddValue() qui appelle cette fonction si nécessaire/
Il faut faire appel à cette fonction lorsque que l'on veut créer un nouvelle élément et que table.inUse > table.capacity.
Si les données ne sont pas de volume trop importantes, il est préférable de doubler la taille de la table lorsque celle-ci se trouve être trop petite.

Doubler la table :


						
int CEV_tabSizeDouble(CEV_DynamicArray *table)
{/*extend array by twice*/

    void* tempPtr = table->data;

    tempPtr = realloc(table->data, 2*table->capacity * table->elemSize);   /*twice bigger*/

    if (tempPtr == NULL)
    {/*si echec de realloc*/
        fprintf(stderr, "Err / CEV_tabSizeDouble : %s.\n", strerror(errno));
        return(FUNC_ERR);
    }
    /*else*/
    table->data = tempPtr;
    table->capacity *= 2;   /*twice the space available*/

    return(FUNC_OK);
}
						

Etend la table de données pour doubler le nombre de données qu'il sera possible de stocker.
Il faut faire appel à cette fonction lorsque que l'on veut créer un nouvelle élément et que dynTable.inUse > dynTable.capacity.
A utiliser lorsque la taille des données n'est pas abusive, sinon utiliser la fonction CEV_tabSizeExtend pour que la table fasse juste la bonne taille.

Ajout à la volée :


						
int CEV_tabAddValue(CEV_DynamicArray *table, void* value)
{/*add a value in the table*/

    int  sts  = FUNC_OK;/*enum FUNC_OK =0*/

    if (table->inUse + 1 > table->capacity)
        sts += CEV_tabSizeExtend(table);

    if (!sts)
    {
        /*no NULL can occur, we just extendend the table if empty*/
        memcpy(CEV_tabGetIndex(table, table->inUse), value, table->elemSize);
        table->inUse++;
    }

    return sts;
}
						

Ajoute un élément dans la table dynamique et étend celle-ci si nécessaire.
On copie l'élément, ainsi la source peut être libérée ou modifiée.

Supprimer une donnée de la table :


						
void CEV_tabRemoveIndex(CEV_DynamicArray *table, unsigned int index)
{/*copies last value into index*/

    if(index >= table->inUse) /*index off limits*/
        return;

    else if(table->inUse>=2) /*at least 2 values to copy*/
    {
        char  *temp = table->data, /*ptr to array*/
              *src  = temp + ((table->inUse-1) * table->elemSize),  /*ptr to last value*/
              *dst  = temp + (index * table->elemSize);   /*ptr to the one to remove*/

        memcpy(dst, src, table->elemSize);  /*copy last one into the one to be removed*/
    }

    table->inUse--; /*one less in use*/
}
						

L'élément à supprimer n'est en fait pas supprimé, il est remplacé par le dernier élément actif de la table, le nombre d'éléments "actifs" est réduit de 1.
Il va de soi que si la donnée à supprimer à fait l'objet d'allocation, il faudra en faire la libération avant de passer par cette fonction.
A noter que la fonction memcpy() nécéssite string.h.

Récupérer un élément :


							
void *CEV_tabGetIndex(CEV_DynamicArray *table, unsigned int index)
{
    char *ptr = (char*) table->data;

    /*checkin index is available*/
    if (index >= table->inUse)
        return NULL;

    ptr += table->elemSize * index;

    return (void*)ptr;
}
							

Retourne un pointeur sur le Nième index
Permet de récupérer un élément de la table.

La libération de la table :


							
void CEV_tabFree(CEV_DynamicArray *table)
{/*destroy*/

    free(table->data);
}
							

Libère la table qui a été allouée.
Il va de soi que si les données stockées dans la table ont fait l'objet d'allocations, il faudra en faire la libération avant de passer par cette fonction.

Test des fonctions :


							
void tableTest(void)
{/*testing dynamic tables*/

    CEV_DynamicArray tester;
    int vars[12] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
    int* loc;

    puts("test init :");
    CEV_tabInit(&tester, 10, sizeof(int));
    L_tableDump(&tester);

    puts("test remove index off limit (i5):");
    CEV_tabRemoveIndex(&tester, 5);
    L_tableDump(&tester);

    puts ("test add 1 value (5):");
    CEV_tabAddValue(&tester, &vars[5]);
    L_tableDump(&tester);

    puts("test getIndex out off limit(i5):");
    loc = (int*)CEV_tabGetIndex(&tester, 5);
    if (!loc)
        puts("result is NULL");
    L_tableDump(&tester);

    puts ("test remove 1 value (i0):");
    CEV_tabRemoveIndex(&tester, 0);
    L_tableDump(&tester);

    puts("test addValue loop:");
    for (int i=0; i<10; i++)
        CEV_tabAddValue(&tester, &vars[i]);
    L_tableDump(&tester);

    puts("test addValue off limit (i10, i11):");
    CEV_tabAddValue(&tester, &vars[10]);
    CEV_tabAddValue(&tester, &vars[11]);
    L_tableDump(&tester);

    puts("test remove (5):");
    CEV_tabRemoveIndex(&tester, 5);
    L_tableDump(&tester);

    puts("test extend:");
    CEV_tabSizeExtend(&tester);
    L_tableDump(&tester);

    puts("test double:");
    CEV_tabSizeDouble(&tester);
    L_tableDump(&tester);

    puts("test getIndex (5):");	
    printf("%d\n", *(int*)CEV_tabGetIndex(&tester, 5));/*je sais qu'il existe, mais pourrait être NULL, attention*/
    L_tableDump(&tester);

    CEV_tabFree(&tester);
}


void L_tableDump(CEV_DynamicArray* array)
{
    int *loc = (int*)array->data;

    printf("capacite : %d\n", array->capacity);
    printf("inUse : %d\n", array->inUse);

    for (int i=0; i < array->inUse; i++)
        printf("%d ", loc[i]);

    putchar('\n');
    putchar('\n');
}
							

Code utilisé pour tester et vérifier la robustesse des fonctions.
N'hésitez pas à signaler un bug.