Ziirish's Home :: Blog

Ziirish's Pub

 
 

Comme certains d'entre-vous le savent, ma deuxième passion dans la vie, c'est le C.

Je sais même plus quelle est ma première passion en fait <_<

Mais comme tout le monde le sait, le C c'est compliqué ! (j'aime cette répétition du son [C])

J'ai personnellement appris à coder avec du Java, et il faut le reconnaître, y'a pas mal d'outils de haut niveau qui sont plaisants.

Un exemple, l'ArrayList. C'est un tableau à taille variable et capable de stocker des objets de n'importe quel type (ou presque).

Pour un de mes projets, j'ai eu besoin d'un outil de ce genre, et je vous propose donc ci-dessous le code. Mon code étant basé sur la glib, je vais tenter de le traduire ici au plus bas niveau (pour éviter les dépendances), mais j'ai la flemme de tester, donc je ne garanti pas que ce soit 100% fonctionnel du premier coup :D

On commence par définir quelques structures :


#define TRUE 1
#define FALSE 0
/**
 * Une énumération de types
 */
typedef enum {
    TYPE_INVALID,
    TYPE_STRING,
    TYPE_INT,
    TYPE_BOOLEAN
} Type;

typedef struct _DataTable DataTable;
typedef struct _DataContent DataContent;
typedef struct _DataCase DataCase;

/**
 * Notre tableau
 */
struct _DataTable {
    size_t length;
    DataCase *head;
    DataCase *tail;
};

/**
 * Le contenu d'une case
 */
struct _DataContent {
    union {
        char *string;
        int iNumber;
        short booleen;
    };
    Type type;
};

/**
 * Une case du tableau
 */
struct _DataCase {
    DataContent *content;
    DataCase *next;
    DataCase *prev;
};

Comme vous pouvez le remarquer, on va se baser sur le principe des listes doublement chaînées.

Maintenant qu'on a nos "objets", il nous faut des fonctions pour les instancier :


/**
 * Initialise un nouveau tableau
 */
static DataTable *
datatable_new (void)
{
    DataTable *ret = NULL;
    ret = malloc (sizeof(*DataTable));
    if (ret != NULL)
    {
        ret->length = 0;
        ret->head = NULL;
        ret->tail = NULL;
    }
    return ret;
}

/**
 * Initialise une nouvelle case
 */
static DataCase *
datacase_new (void)
{
    DataCase *ret = NULL;
    ret = malloc (sizeof(*DataCase));
    if (ret != NULL) 
    {
        ret->content = NULL;
        ret->next = NULL;
        ret->prev = NULL;
    }
    return ret;
}

/**
 * Permet de créer un nouvel élément pouvant être inséré dans une liste
 * @param iType type de l'élément
 * @param value valeur de l'élément
 * @return nouvel élément
 */
DataContent *
datacontent_new (Type iType, void *value)
{
    DataContent *ret = NULL;
    ret = malloc (sizeof(*DataContent));
    if (ret != NULL)
    {
        ret->type = iType;
        switch (iType) 
        {
            case TYPE_STRING:
                ret->string = NULL;
                ret->string = malloc (strlen((char *) value)*sizeof(char)+1);
                strcpy(ret->string, (char *) value);
                break;
            case TYPE_INT:
                ret->iNumber = (int) value;
                break;
            case TYPE_BOOLEAN:
                ret->booleen = (short) value;
                break;
            default:
                free(ret);
                return NULL;
        }
    }
    return ret;
}

/**
 * Fonction permettant de créer un tableau dynamique
 * @param iDataType le type des données qui suivent
 * @param ... les données, pouvant être des chaînes, des booléens, des 
 * entiers, ou des Type. Il faut obligatoirement terminer par un
 * TYPE_INVALID
 * @return pointeur vers notre structure
 */
DataTable *
create_datatable (Type iDataType, ...)
{
    DataTable *res = datatable_new();
    Type iCurrType = iDataType;
    va_list args;
    va_start(args,iDataType);
    void *current;
    while ((current = va_arg(args,void *)) != TYPE_INVALID) {
        DataContent *tmp = NULL;
        if ((Type) current == TYPE_BOOLEAN || (Type) current == TYPE_INT || (Type) current == TYPE_STRING)
        {
            iCurrType = (Type) current;
            continue;
        }
        switch (iCurrType) 
        {
            case TYPE_BOOLEAN:
                tmp = datacontent_new_boolean(current);
                break;
            case TYPE_STRING:
                tmp = datacontent_new_string(current);
                break;
            case TYPE_INT:
                tmp = datacontent_new_int(current);
                break;
            default:
                iCurrType = (Type) current;
        }
        datatable_append(&res,tmp);
    }
    va_end(args);
    return res;
}

Maintenant, nous disposons d'outils de création. Attention, la dernière fonction nécessite la présence de la fonction datatable_append que nous implémenterons plus bas. J'ai également utilisé plusieurs MACRO pour "éclaircir" le code.

Voici les définitions des MACRO :


#define datacontent_new_string(val) datacontent_new(TYPE_STRING, (void*)val)
#define datacontent_new_int(val) datacontent_new(TYPE_INT, (void*)val)
#define datacontent_new_boolean(val) datacontent_new(TYPE_BOOLEAN, (void*)val)

On a donc nos outils d'initialisation des "objets". Il nous reste à implémenter les manipulations que l'on peut y faire.


/**
 * Permet d'ajouter un élément en fin de liste
 * @param p_list liste a laquelle on souhaite ajouter un element
 * @param data élément à ajouter
 * @return nouvelle liste
 */
void
datatable_append(DataTable **p_list, DataContent *data)
{
    if (*p_list != NULL) 
    {
        DataCase *p_new = datacase_new(); 
        if (p_new != NULL) 
        {
            p_new->content = data; 
            p_new->next = NULL; 
            if ((*p_list)->tail == NULL)
            {
                p_new->prev = NULL; 
                (*p_list)->head = p_new;
                (*p_list)->tail = p_new;
            }
            else
            {
                (*p_list)->tail->next = p_new;
                p_new->prev = (*p_list)->tail;
                (*p_list)->tail = p_new;
            }
            (*p_list)->length++;
        }
    }
}

/**
 * Permet d'ajouter un élément en début de liste
 * @param p_list liste a laquelle on souhaite ajouter un element
 * @param data élément à ajouter
 * @return nouvelle liste
 */
void
datatable_prepend(DataTable **p_list, DataContent *data)
{
    if (*p_list != NULL)
    {
        DataCase *p_new = datacase_new();
        if (p_new != NULL)
        {
            p_new->content = data;
            p_new->prev = NULL;
            if ((*p_list)->tail == NULL)
            {
                p_new->next = NULL;
                (*p_list)->head = p_new;
                (*p_list)->tail = p_new;
            }
            else
            {
                (*p_list)->head->prev = p_new;
                p_new->next = (*p_list)->head;
                (*p_list)->head = p_new;
            }
            (*p_list)->length++;
       }
    }
}

/**
 * Permet d'insérer un élément à l'indice souhaité
 * @param p_list liste dans laquelle on souhaite ajouter l'élément
 * @param data élément à ajouter
 * @param position indice ou l'on souhaite ajouter l'élément
 * @return nouvelle liste
 */
void
datatable_insert(DataTable **p_list, DataContent *data, int position)
{
    if (*p_list != NULL)
    {
        if (position < 0)
        {
            datatable_prepend(p_list,data);
            return;
        }
        else 
        if (position > (int) datatable_length(*p_list))
        {
            datatable_append(p_list,data);
            return;
        }
        DataCase *p_temp = (*p_list)->head;
        int i = 1;
        while (p_temp != NULL && i <= position)
        {
            if (position == i)
            {
                if (p_temp->next == NULL)
                {
                    datatable_append(p_list, data);
                }
                else if (p_temp->prev == NULL)
                {
                    datatable_prepend(p_list, data);
                }
                else
                {
                    DataCase *p_new = datacase_new();
                    if (p_new != NULL)
                    {
                        p_new->content = data;
                        p_temp->next->prev = p_new;
                        p_temp->prev->next = p_new;
                        p_new->prev = p_temp->prev;
                        p_new->next = p_temp;
                        (*p_list)->length++;
                    }
                }
            }
            else
            {
                p_temp = p_temp->next;
            }
            i++;
        }
    }
}

Ça c'est pour l'ajout d'éléments à la liste, la fonction d'insertion nécessite datatable_length dont le code est donné ci-dessous.


/**
 * Permet de connaître la taille d'une liste
 * @param p_list liste dont on souhaite connaître la taille
 * @return taille de la liste
 */
size_t
datatable_length(DataTable *p_list)
{
    size_t ret = 0;
    if (p_list != NULL)
    {
        ret = p_list->length;
    }
    return ret;
}

Mais dans une ArrayList, on peut également supprimer des éléments.


/**
 * Permet de supprimer le premier élément 'data' de la liste 'p_list'
 * @param p_list liste de depart
 * @param data élément à supprimer
 * @return nouvelle liste 
 */
void
datatable_remove(DataTable **p_list, DataContent *data)
{
    if (*p_list != NULL)
    {
        DataCase *p_temp = (*p_list)->head;
        short found = FALSE;
        while (p_temp != NULL && !found)
        {
            if (datacontent_equals(p_temp->content,data))
            {
                if (p_temp->next == NULL)
                {
                    free_datacase((*p_list)->tail);
                    (*p_list)->tail = p_temp->prev;
                    free_datacase((*p_list)->tail->next);
                    (*p_list)->tail->next = NULL;
                }
                else if (p_temp->prev == NULL)
                {
                    free_datacase((*p_list)->head);
                    (*p_list)->head = p_temp->next;
                    free_datacase((*p_list)->tail->prev);
                    (*p_list)->head->prev = NULL;
                }
                else
                {
                    p_temp->next->prev = p_temp->prev;
                    p_temp->prev->next = p_temp->next;
                }
                free_datacase(p_temp);
                (*p_list)->length--;
                found = TRUE;
            }
            else
            {
                p_temp = p_temp->next;
            }
        }
    }
}

/**
 * Permet de supprimer tous les éléments 'data' de la liste 'p_list'
 * @param p_list liste de depart
 * @param data élément à supprimer
 * @return nouvelle liste
 */
void
datatable_remove_all(DataTable **p_list, DataContent *data)
{
    if (*p_list != NULL)
    {
        DataCase *p_temp = (*p_list)->head;
        while (p_temp != NULL)
        {
            if (datacontent_equals(p_temp->content,data))
            {
                DataCase *p_del = p_temp;
                p_temp = p_temp->next;
                if (p_del->next == NULL)
                {
                    (*p_list)->tail = p_del->prev;
                    (*p_list)->tail->next = NULL;
                }
                else if (p_del->prev == NULL)
                {
                    (*p_list)->head = p_del->next;
                    (*p_list)->head->prev = NULL;
                }
                else
                {
                    p_del->next->prev = p_del->prev;
                    p_del->prev->next = p_del->next;
                }
                free_datacase(p_del);
                (*p_list)->length--;
            }
            else
            {
                p_temp = p_temp->next;
            }
        }
    }
}

/**
 * Supprime de la liste 'p_list' l'élément situé à l'indice 'position'
 * @param p_list liste de départ
 * @param position indice de l'élément à supprimer
 * @return nouvelle liste
 */
void
datatable_remove_id(DataTable **p_list, int position)
{
    if (*p_list != NULL)
    {
        DataCase *p_temp = (*p_list)->head;
        int i = 1;
        while (p_temp != NULL && i <= position)
        {
            if (position == i)
            {
                if (p_temp->next == NULL)
                {
                    (*p_list)->tail = p_temp->prev;
                    (*p_list)->tail->next = NULL;
                }
                else if (p_temp->prev == NULL)
                {
                    (*p_list)->head = p_temp->next;
                    (*p_list)->head->prev = NULL;
                }
                else
                {
                    p_temp->next->prev = p_temp->prev;
                    p_temp->prev->next = p_temp->next;
                }
                free_datacase(p_temp);
                (*p_list)->length--;
            }
            else
            {
                p_temp = p_temp->next;
            }
            i++;
        }
    }
}

Ces fonctions de suppression utilisent une fonction de comparaison, ainsi que des fonctions de destruction, autrement dit, des free.


/**
 * Permet de comparer deux éléments
 * @param d1 élément 1
 * @param d2 élément 2
 * @return TRUE si les éléments sont égaux (en terme de valeur), sinon FALSE 
 */
short
datacontent_equals (DataContent *d1, DataContent *d2)
{
    if (d1 == NULL || d2 == NULL)
        return FALSE;
    if (d1->type != d2->type)
        return FALSE;
    switch (d1->type) 
    {
        case TYPE_STRING:
            return strcmp(d1->string,d2->string) == 0;
        case TYPE_INT:
            return d1->iNumber == d2->iNumber;
        case TYPE_BOOLEAN:
            return d1->booleen == d2->booleen;
    }
}

/**
 * Permet de supprimer un élément
 * @param pCase élément à supprimer
 * @param pData données provenant du foreach
 */
void
free_datacase_full (DataCase *pCase, void *pData)
{
    if (pCase != NULL)
    {
        free_datacontent(pCase->content);
        free(pCase);
    }
}

/**
 * Permet de supprimer un conteneur
 * @param pContent contenu à supprimer
 * @param pData données provenant du foreach
 */
void
free_datacontent_full (DataContent *pContent, void *pData)
{
    if (pContent != NULL)
    {
        if (pContent->type == TYPE_STRING && pContent->string != NULL)
            free(pContent->string);
        free(pContent);
    }
}

#define free_datacase(val) free_datacase_full(val, NULL)

#define free_datacontent(val) free_datacontent_full(val, NULL)

Les fonctions utilisées sont en fait des MACRO permettant de simplifier la lecture du code.

Arrivés ici, nous disposons donc d'outils d'instanciation, d'ajout, et de suppressions d'éléments dans notre Liste. Mais un autre point intéressant des l'ArrayList est la présence d'un Itérateur.

Allons-y !


/**
 * Permet de parcourir tous les éléments d'une liste donnée, et d'effectuer le traitement voulu
 * @param p_list liste que l'on souhaite parcourir
 * @param func pointeur vers la fonction que l'on souhaite effectuer sur chaque élément de la liste
 * @param pData données à transmettre à la fonction func
 * /! pData[0] contiendra toujours l'indice de l'élément courant
 */
void
datatable_foreach (DataTable *p_list, DataAction func, void *pData)
{
    if (p_list != NULL)
    {
        DataCase *p_temp = p_list->head;
        short bCreateData = FALSE;
        if (pData == NULL)
        {
            pData = calloc (1,sizeof(void));
            bCreateData = TRUE;
        }
        int cpt = 1;
        while (p_temp != NULL)
        {
            pData[0] = &cpt;
            DataCase *p_del = malloc(sizeof(*p_temp));
            memcpy(p_del,p_temp,sizeof(*p_temp));
            func (p_temp, pData);
            p_temp = p_del->next;
            free(p_del);
            cpt++;
        }
        if (bCreateData)
        {
            free(pData);
        }
    }
}

Bien sûr, le but d'un Itérateur est d'effectuer des traitements sur les éléments de la liste. Pour cela, on défini un prototype de fonction de callback à appeler sur chaque élément.

Le voici :


typedef void (* DataAction) (DataCase *pCase, void *pData);

Maintenant, on peut déclarer une fonction de callback respectant ce prototype.


/**
 * Permet d'afficher la valeur d'un élément
 * @param pCase élément dont on souhaite afficher la valeur
 * @param pData données provenant éventuellement de datatable_foreach
 */
void
datacase_print (DataCase *pCase, void *pData)
{
    if (pCase != NULL && pCase->content != NULL)
    {
        switch (pCase->content->type) 
        {
            case TYPE_STRING:
                fprintf (stdout,"%s\n",pCase->content->string);
                break;
            case TYPE_INT:
                fprintf (stdout,"%d\n",pCase->content->iNumber);
                break;
            case TYPE_BOOLEAN:
                fprintf (stdout,"%s\n",pCase->content->booleen ? "TRUE" : "FALSE");
                break;
        }
    }
}

On pourra appeler cette fonction comme suit :


datatable_foreach(test,(DataAction)datacase_print,NULL);

Nous pouvons à l'aide de toutes ces fonctions, créer une fonction de "nettoyage" de notre liste.


/**
 * Fonction permettant de liberer notre liste
 * @param pointeur vers notre liste
 */
void
free_datatable (DataTable **p_list)
{
    if (*p_list != NULL)
    {
        datatable_foreach(*p_list,(DataAction) free_datacase_full, NULL);
        free(*p_list), *p_list = NULL;
    }
}

Nous pouvons terminer avec un petit exemple d'utilisation complet :


DataTable *test = create_datatable(TYPE_STRING,"blah","blih","bloh","toto","tata","titi","tutu",
TYPE_INT,5,12,TYPE_INVALID);
printf("size: %d\n",datatable_length(test));
datatable_append(&test,datacontent_new_int(56));
DataContent *blah = datacontent_new_string("toto");
datatable_remove(&test,blah);
free_datacontent(blah);
datatable_foreach(test,(DataAction)datacase_print,NULL);
free_datatable(&test);

On est pas encore tout à fait à l'ArrayList qu'on a l'habitude de croiser en Java, mais on en est pas très loin. Et ça suffit déjà à pas mal de choses.

J'espère vous avoir un peu réconcilié avec ce magnifique langage de programmation qu'est le C.