Discussion :

[Gugelhupf]

Bonjour,


J'ai récemment décidé de publier au fur et à mesure des bibliothèques que j'ai commencé à créer durant mes études sur Github (lien). Parmi ces libs il y en a une (liste chaînée générique), dont je souhaiterais vous présenter afin d'avoir votre avis et l'améliorer si possible, ce dernier possède les caractéristiques suivants :

• Peut contenir n'importe quel type de variable (ps: void*)
• Compatible C89 et plus
• Compatible C++ 98 et plus
• Valide avec l'option Wextra du compilateur GCC (cf: typage strict)
• Possède un itérateur Iterator pour parcourir les variables
• Utilise un pattern objet

Voici un exemple d'utilisation :

Code c :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include "generic_linked_list.h"
#include <stdio.h> // for printf
 
int main(void) {
    List list = List_make();
    int i1 = 123, i2 = 456, i3 = 789, i4 = 321, i5 = 654, i6 = 987;
 
    // add + get
    list.add(&list, &i1);
    list.add(&list, &i2);
    list.add(&list, &i3);
    printf("%d\n", *(int*) list.get(&list, 0));
    printf("%d\n", *(int*) list.get(&list, 1));
    printf("%d\n", *(int*) list.get(&list, 2));
 
    // update + get
    list.update(&list, 0, &i4);
    list.update(&list, 1, &i5);
    list.update(&list, 2, &i6);
    printf("%d\n", *(int*) list.get(&list, 0));
    printf("%d\n", *(int*) list.get(&list, 1));
    printf("%d\n", *(int*) list.get(&list, 2));
 
    // remove + size
    list.remove(&list, 3); // tried with 0, 1, 2, 3
    printf("%d\n", list.size(&list));
 
    // removeAll + size
    list.removeAll(&list);
    printf("%d\n", list.size(&list));
 
    // Iterator
    printf("\n\nIterate: \n");
    list.add(&list, &i1);
    list.add(&list, &i2);
    list.add(&list, &i3);
 
    // Iterator loop pattern
    for (Iterator* it = list.iterator(&list); it != NULL; it = it->next(it)) {
        printf("%d\n", *(int*) it->get(it));
    }
 
    // Iterator loop with remove pattern
    Iterator* ite = list.iterator(&list);
    while (ite != NULL) {
        int* element = (int*) ite->get(ite);
        // You can free() element if you have instanciated it with malloc()
        if (*element == 456) {
            ite = ite->removeAndNext(ite);
        } else {
            ite = ite->next(ite);
        }
    }
 
    printf("\n");
    for (Iterator* it = list.iterator(&list); it != NULL; it = it->next(it)) {
        printf("%d\n", *(int*) it->get(it));
    }
 
    return 0;
}

Qu'en pensez-vous ? (N'hésitez pas à lire le generic_linked_list.h et generic_linked_list.c avant)

Souhaiteriez-vous un benchmark comparatif avec une autre lib ? Nous pourrions par exemple créer un repo, comparer le nombre d'instruction assembleur du main, le temps d'exécution moyen pour N insertions puis suppression durant une iteration, la consommation moyenne etc...


Je vous remercie par avance, cordialement,

[Matt_Houston]

Quelques petites remarques en vrac :

• préfère size_t à unsigned int pour adresser et stocker des tailles ;
• ta structure n'a pas l'ownership complet des éléments qu'elle stocke : elle ne réalise pas d'allocation, mais peut néanmoins libérer la mémoire occupée. Pourquoi pas, mais il faut que ce soit bien clair pour l'utilisateur ;
• laisse tomber la prise en charge C++ : ton code n'a pas d'avantage sur la STL (à part le temps de compilation peut-être) et de toute manière le C ne se compile pas tel quel avec un compilateur C++ (on utilise des symboles dédiés) ;
• les identifiants commençant par un underscore sont parfois réservés ;
• il manque peut-être quelques occurrences de const.

[Gugelhupf]

Merci pour ton retour @Matt_Houston

J'ai remplacé unsigned int par size_t, par contre je n'ai pas ajouté const car trop restrictifs pour certaines méthodes modifiants les variables de la liste (du coup ça casse l'"harmonie" d'en mettre à certains prototypes seulement je trouve). La compatibilité avec un compilateur C++ se résume à un simple cast pour le retour de la fonction malloc(), si j'enlève cette compatibilité toutes les personnes sous Windows avec un compilateur Visual Studio C++ ne pourront pas tester le code chez eux par exemple.

En effet, la liste laisse libre recours au développeur pour allouer/libérer la mémoire, cependant la librairie offre une fonction bonus removeAndFreeAll() (en plus de removeAll() utilisé en "temps normal") pour libérer l'ensemble des éléments de la mémoire sans avoir à recoder une itération.