GCL - une librairie de conteneurs génériques en C
Posté le 22/03/2015 19:33
Ça faisait longtemps.
Aujourd'hui, pas grand chose d'innovant, mais qui peut toujours être utile: je vous présente GCL, un petit projet de librairie qui occupe mes pauses déjeuner ces derniers temps.
GCL (Generic Container Library) est une librairie qui fournit des templates de conteneurs en C. Pour ceux qui ont fait du C++, mon but est effectivement de réimplémenter la
STL en pur C89.
Le principe est relativement simple. Normalement, en C, quand vous voulez utiliser des conteneurs dynamiques (list, vector, map, stack, etc...), vous devez non seulement les implémenter vous-même, mais en plus, ceux-ci nécessitent généralement une implémentation par type de donnée stockée (ou alors des pointeurs void *, mais dans ce cas on perd la sécurité des types).
Avec GCL, vous pouvez instancier des templates de conteneurs pour n'importe quels types, puis les utiliser dans votre programme en spécifiant le type sur lequel vous travaillez.
Toutes les instanciations sont faites à la compilation, ce qui permet une vitesse d'exécution optimisée.
Pour le moment, je n'ai implémenté que deux conteneurs, ceux qui sont à mon sens les plus utiles:
# vector: Un tableau à taille dynamique. Permet un accès aléatoire en temps constant. Se redimensionne au besoin.
# map: Un conteneur associatif. Permet d'associer une clé à une valeur. Accès en O(log N) temps. Implémenté sous la forme d'un arbre bicolore.
Pour illustrer le concept, voici un petit programme qui compte le nombre d'occurences des mots dans une chaine de caractères.
[brown]#include <stdlib.h>[/brown]
[brown]#include <stdio.h>[/brown]
[brown]#include <string.h>[/brown]
[brown]#include [gray]"gcl.h"[/gray][/brown]
[purple]int[/purple] main() {
size_t i;
map_iterator(str, int) itr;
vector_t(str) my_vector;
map_t(str, int) my_map;
[purple]char[/purple] text[] = [gray]"Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed [b][blue]do[/blue][/b] eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum."[/gray];
const [purple]char[/purple] delimiter[] = [gray]" "[/gray];
[purple]char[/purple] *token;
token = strtok(text, delimiter);
vector_init(str)(&my_vector, [maroon]0[/maroon]);
map_init(str, int)(&my_map, strcmp);
[b][blue]while[/blue][/b] (token != NULL) {
vector_push_back(str)(&my_vector, token);
token = strtok(NULL, delimiter);
}
[b][blue]for[/blue][/b] (i = [maroon]0[/maroon]; i < my_vector.size; ++i) {
++map_at(str, int)(&my_map,
my_vector.data[i ]);;
}
map_foreach(str, int, &itr, &my_map) {
printf([gray]"%*s: %d\n"[/gray], [maroon]16[/maroon], itr[b]->[/b]key, itr[b]->[/b]value);
}
map_destroy(str, int)(&my_map);
vector_destroy(str)(&my_vector);
[b][blue]return[/blue][/b] 0;
}
gcl.h contient:
[brown]#ifndef GCL_H[/brown]
[brown]#define GCL_H[/brown]
typedef const char* str;
[brown]#define TYPE str[/brown]
[brown]#include [gray]"gcl/vector.h"[/gray][/brown]
[brown]#include [gray]"gcl/vector.def"[/gray][/brown]
[brown]#undef TYPE[/brown]
[brown]#define KEY_TYPE str[/brown]
[brown]#define VALUE_TYPE int[/brown]
[brown]#include [gray]"gcl/map.h"[/gray][/brown]
[brown]#include [gray]"gcl/map.def"[/gray][/brown]
[brown]#undef KEY_TYPE[/brown]
[brown]#undef VALUE_TYPE[/brown]
#endif
Vous pourrez suivre la progression du projet sur
github. Si vous pensez que le projet est intéressant, ou si vous avez des suggestions, faîtes-le savoir.
Citer : Posté le 25/03/2015 13:42 | #
Ouais, avec le recul ça paraît évident.
Enfin, bon courage quand même, parce que ça va pas être le plus facile...
Faut que voie si mon concept de fragmentation multidimensionnelle est réalisable au fait
Citer : Posté le 25/03/2015 13:46 | #
alors je vais te dire
après avoir implémenté le red-black tree
ya plus grand chose qui me fait peur
non parce que p*tain j'en ai ch*é
Citer : Posté le 25/03/2015 13:49 | #
alors je vais te dire
après avoir implémenté le red-black tree
ya plus grand chose qui me fait peur
Erf, qu'est-ce que tu veux que je te dise avec après ça... -_-
Citer : Posté le 26/03/2015 16:38 | #
Bon alors finalement, j'ai bien réfléchi pour la seglist (liste segmentée), et j'en suis venu à la conclusion suivante:
lors de la création de la liste, on passe au constructeur la taille des segments en nombre d'éléments.
Pour expliquer les avantages et inconvénients des différentes solutions, je présenterai les critères suivants:
- accès aléatoire : le temps qu'il faut pour accéder à un élément par son index (comme on le ferait avec tableau[index])
- insertion/suppression aux extrémités : utile quand on veut implémenter des interfaces de type stack ou queue
- insertion/suppression au millieu
- espace alloué inutilisé
- itération
et donc , considérons N la taille de la liste, et S le nombre d'éléments par segment:
- accès aléatoire : O(N/S)
- insertion/suppression aux extrémités : O(1)
- insertion/suppression au millieu : O(S)
- espace alloué inutilisé : O(S)
- itération : O(1)
maintenant, si vous passez 0 comme taille de segment au constructeur, la taille des segments doublera à chaque segment:
- accès aléatoire : O(log(N))
- insertion/suppression aux extrémités : O(1)
- insertion/suppression au millieu : O(N)
- espace alloué inutilisé : O(N)
- itération : O(1)
pour avoir une idée des performances des autres conteneurs:
vector:
- accès aléatoire : O(1)
- insertion/suppression à l'avant : O(N)
- insertion/suppression à l'arrièrre : O(1)
- insertion/suppression au millieu : O(N)
- espace alloué inutilisé : O(N)
- itération : O(1)
map:
- accès aléatoire : O(log(N))
- insertion/suppression : O(log(N))
- espace alloué inutilisé : O(1)
- itération : O(log(N))
linkedlist:
- accès aléatoire : O(N)
- insertion/suppression : O(1)
- espace alloué inutilisé : O(1)
- itération : O(1)
Ajouté le 28/03/2015 à 10:25 :
Est-ce que quelqu'un sait si les calculatrices casio ont un système de cache, et si c'est le cas, quelle est la taille des lignes de cache? (ça influencera beaucoup la performance de certains conteneurs)
Ajouté le 28/03/2015 à 10:32 :
nevermind, trouvé
page 83 de ce petit document
à priori 512 lignes de 32 octets (+ les étiquettes et les flags)
Citer : Posté le 28/03/2015 10:59 | #
Hmm, oublie pas que c'est le SH-4 ça.
Ceci dit, il y en a aussi sur les SH3.
Citer : Posté le 30/03/2015 20:49 | #
Té mais le pervers polymorphe est de retour ici? Sans déconner, je croyais que t'avais abandonné la prog pour caltos!
Citer : Posté le 30/03/2015 20:50 | #
tout le monde peut changer d'avis, même les pervers polymorphes
Citer : Posté le 30/03/2015 20:50 | #
Té mais le pervers polymorphe est de retour ici? Sans déconner, je croyais que t'avais abandonné la prog pour caltos!
On a parlé de portabilité plus haut. Ce qui laisse entendre que...
tout le monde peut changer d'avis, même les pervers polymorphes
Non, c'est pas vraiment ce que ça laisse entendre
Citer : Posté le 30/03/2015 20:54 | #
Il m'aura donné du rêve, cette andouille. Et pas dans ce sens là, pervers!
Goodspeed bro, continue comme ça!
Citer : Posté le 31/03/2015 09:18 | #
mais merde Eiyeron, laisse-les encore un peu dans l'innocence de leurs années de lycée...
bon j'ai réussi à hijack mon cours d'archi pour faire d'une pierre deux coups avec ma liste segmentée.
du coup d'ici cet aprèm j'aurais fait un exposé sur la performance des conteneurs vis-à-vis du cache et j'aurais cette liste à la con.
Citer : Posté le 04/04/2015 12:11 | #
Je me demande un peu comment ça pourrait me serviiiiir- nan c'est bon. Je vais me cloner ça et voir où je vais pouvoir fourrer ces libs dans HBE. Siap, on peu swapper facilement deux éléments d'un vector ou faire un sort en passant un fonction pointer à une fonction ? On pourrait faire un quicksort générique pour ces conteneurs.
Citer : Posté le 04/04/2015 13:17 | #
Il est super cool ce projet !
C'est pas forcément très utile dans le développement de jeux, mais c'est du beau code.
Juste une remarque, dans vector j'ai l'impression qu'il n'y a pas de sécurité sur le retour de realloc.
Citer : Posté le 04/04/2015 19:45 | #
Pierrot! Reste parmi nous! Ça fait plaisir de te voir parmi nous!
Citer : Posté le 04/04/2015 22:27 | #
quicksort est déjà dans la lib standard du C Eiyeron:
#include <stdlib.h>
void qsort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *));
void qsort_r(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *, void *),
void *arg);
du coup tu n'a qu'à faire:
{
[purple]int[/purple] int_a = * ( (int*) a );
[purple]int[/purple] int_b = * ( (int*) b );
[b][blue]if[/blue][/b] ( int_a == int_b ) [b][blue]return[/blue][/b] 0;
[b][blue]else[/blue][/b] if ( int_a < int_b ) [b][blue]return[/blue][/b] -1;
[b][blue]else[/blue][/b] return 1;
}
qsort(void my_vector.data, my_vector.size, sizeof(int), compare_int);
j'ajouterai des algorithmes génériques dans GCL pour qu'on puisse faire des trucs du genre compare(int)
Citer : Posté le 04/04/2015 22:32 | #
Mais sur les vectors ?
Citer : Posté le 04/04/2015 22:35 | #
et oui j'ai pas encore fait les checks de realloc et malloc
Citer : Posté le 05/04/2015 08:00 | #
quicksort est déjà dans la lib standard du C Eiyeron:
#include <stdlib.h>
void qsort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *));
void qsort_r(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *, void *),
void *arg);
du coup tu n'a qu'à faire:
{
[purple]int[/purple] int_a = * ( (int*) a );
[purple]int[/purple] int_b = * ( (int*) b );
[b][blue]if[/blue][/b] ( int_a == int_b ) [b][blue]return[/blue][/b] 0;
[b][blue]else[/blue][/b] if ( int_a < int_b ) [b][blue]return[/blue][/b] -1;
[b][blue]else[/blue][/b] return 1;
}
qsort(void my_vector.data, my_vector.size, sizeof(int), compare_int);
j'ajouterai des algorithmes génériques dans GCL pour qu'on puisse faire des trucs du genre compare(int)
Oui je sais, mais les wrapper afin de faciliter leur utilisation, nan?
Citer : Posté le 05/04/2015 22:29 | #
Bah écoutes Eiyo
t'as accès au repo du projet
donc tu viens m'aider un peu le temps que je finisse mes partiels
si ça t'ammuse occupe-toi de faire un fichier du genre algorithm.h avec la même structure que les autres
Ajouté le 08/04/2015 à 00:23 :
c'est juré, dès que j'ai fini mes partiels, je me repenche dessus
Ajouté le 02/05/2015 à 16:39 :
passage rapide pour dire que les chaines refcounted marchent:
string str1 = str_new([gray]"Hello world!"[/gray]);
printf([gray]"str1: %s\n"[/gray], str1);
string str2 = str_copy(str1);
printf([gray]"str2: %s\n"[/gray], str2);
string str3 = str_copy(str1);
printf([gray]"str3: %s\n"[/gray], str3);
str3 = str_append(str3, [gray]" How are you?"[/gray]);
printf([gray]"str3: %s\n"[/gray], str3);
str3 = str_append(str3, [gray]" I'm fine."[/gray]);
printf([gray]"str3: %s\n"[/gray], str3);
str_delete(str1);
str_delete(str2);
str_delete(str3);
[b][blue]return[/blue][/b] 0;
}
ce qui donne:
str1: Hello world!
str2: Hello world!
str3: Hello world!
[allocation]
str3: Hello world! How are you?
str3: Hello world! How are you? I'm fine.
[deallocation]
[deallocation]
voilà voilà
je m'y remet
Citer : Posté le 02/05/2015 16:59 | #
Sympa