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 22/03/2015 20:26 | #
Sympa ça
Citer : Posté le 22/03/2015 23:15 | #
maintenant, la question est: est-ce que ça intéresse du monde que je continue à travailler dessus ou non?
à savoir, je peux commencer à travailler sur les points suivants:
# la documentation. parce que là, ya clairement rien de documenté correctement
# plus de conteneurs, par exemple queue, list, set, etc..
# inclure aussi des algorithmes génériques comme des tris etc...
Il faudrait aussi déterminer les critères de développement de la librairie, à savoir:
# est-ce que je favorise la lisibilité et la sécurité du code par rapport à la performance?
# est-ce que je favorise la vitesse d'éxécution par rapport au coût en mémoire?
# est-ce que je favorise la cohérence par rapport à l'ergonomie?
Citer : Posté le 23/03/2015 07:28 | #
Cool le principe
Citer : Posté le 23/03/2015 08:13 | #
maintenant, la question est: est-ce que ça intéresse du monde que je continue à travailler dessus ou non?
à savoir, je peux commencer à travailler sur les points suivants:
# la documentation. parce que là, ya clairement rien de documenté correctement
# plus de conteneurs, par exemple queue, list, set, etc..
# inclure aussi des algorithmes génériques comme des tris etc...
Il faudrait aussi déterminer les critères de développement de la librairie, à savoir:
# est-ce que je favorise la lisibilité et la sécurité du code par rapport à la performance?
# est-ce que je favorise la vitesse d'éxécution par rapport au coût en mémoire?
# est-ce que je favorise la cohérence par rapport à l'ergonomie?
moi, ça m’intéresse
Après, les autres questions me laissent indécis
Citer : Posté le 23/03/2015 18:37 | #
C'est plutôt intéressant comme projet.
Même si je trouve que ça dénature un peu le C, comme les exceptions d'Eiyeron...
Pour répondre quand même à tes questions :
est-ce que ça intéresse du monde que je continue à travailler dessus ou non?
Alors oui, moi ça m'intéresse de voir comment tu les implémentes, même si je ne suis pas certain de les utiliser vraiment.
# la documentation. parce que là, ya clairement rien de documenté correctement
Te gêne pas sur la doc. Une API bien documentée n'a même pas besoin d'exemples...
# plus de conteneurs, par exemple queue, list, set, etc..
Personnellement je bosse surtout avec des listes. Je te conseille de jeter un coup d’œil à l'API de Qt (exemple : http://doc.qt.io/qt-5/qvector.html ), qui à mon goût corrige bien certaines choses malaisées de la STL.
# inclure aussi des algorithmes génériques comme des tris etc...
Faudrait pas que ce soit trop lourd, mais sinon ça se défend oui. Un merge sort sur place n'est jamais trop de refus.
# est-ce que je favorise la lisibilité et la sécurité du code par rapport à la performance?
Non.
# est-ce que je favorise la vitesse d'éxécution par rapport au coût en mémoire?
Là, je ne saurais quoi te répondre.
Ça dépend trop des usages.
# est-ce que je favorise la cohérence par rapport à l'ergonomie?
Oui.
Citer : Posté le 23/03/2015 20:10 | #
Bon, bah entre temps, j'ai implémenté deque, qui servira de base pour toutes les interfaces de type stack, linked list et queue.
C'est une pauvre liste doublement chaînée avec un pointeur sur l'avant et l'arrièrre et une taille.
L'implémentation de Qlist est intéressante, même si je vois mal comment relocaliser efficacement les données lors de la réallocation...
Citer : Posté le 23/03/2015 20:31 | #
[...] même si je vois mal comment relocaliser efficacement les données lors de la réallocation...
Tiens c'est marrant, c'est spécifiquement un point dont l'implémentation m'intéresse
Citer : Posté le 23/03/2015 20:32 | #
Bah de ce que j'ai lu, ils recopient les données linéairement à chaque réallocation...
c'est pas extra comme implémentation >.<
Citer : Posté le 23/03/2015 20:34 | #
De toute façon tu crois que realloc() fait quoi ?
Si tu dois optimiser, alloue toujours modulo 4 et copie le tout avec des pointeurs en int *. C'est quatre fois plus rapide !
Ce qui me pose problème avec ce genre de conteneur c'est qu'on ne contrôle plus l'allocation de mémoire.
Citer : Posté le 23/03/2015 20:38 | #
bah realloc le fait UNIQUEMENT quand il n'y a pas d'autre choix
quand tu peux juste agrandir ton bloc d'allocation sans changer les données de place, tu vas pas t'embêter à faire une opération en O(N).
là sur QList ils font du O(N) à chaque fois.
et le coup de recopier par tranche de 4 c'est foireux et c'est du undefined behaviour.
Citer : Posté le 23/03/2015 20:41 | #
ce qui est bizarre, c'est que quand je manipule des objets de la STL, j'ai l'impression de manipuler de la dynamite, alors quand l'api de qt, je me sens parfaitement en sécurité
Citer : Posté le 23/03/2015 20:46 | #
Bah c'est
peut-êtremoi qui suis maso, mais j'aime bien la STL.C'est cohérent de A à Z.
d'ailleurs, c'est décidé, j'implémente les regex dans les algorithmes de cette lib.
ça a rien à voir avec les conteneurs, mais j'ai envie de le faire
Citer : Posté le 24/03/2015 07:49 | #
cool
Citer : Posté le 24/03/2015 19:00 | #
et le coup de recopier par tranche de 4 c'est foireux et c'est du undefined behaviour.
Mais... en quoi ?
Citer : Posté le 24/03/2015 22:43 | #
déjà, int ne fais pas forcément 32bits (ça dépend des systèmes), à la limite tu utilise uint32_t
pareil, vu que la lib dois rester portable, les implémentations des assignations ne sont pas les mêmes suivant les processeurs et les compilateurs, et il y en a où ce genre d'opérations sera de toutes façons optimisé.
après, à priori, memmove() est optimisé pour chaque architecture, donc autant s'en servir: source
le memmove de BSD utilise déjà ce système, et il s'occupe des octets finaux qui ne tiendraient pas dans n = 4 * k taille: source
Citer : Posté le 25/03/2015 11:41 | #
Ah oui, tu cherches la portabilité...
Citer : Posté le 25/03/2015 11:48 | #
bon, pour l'histoire de Qlist, il n'y a effectivement aucun moyen de réallouer devant une allocation préexistante. du coup je vais plutot prendre une approche par segmentation, avec une méthode pour défragmenter quand le programmeur a besoin d'un espace de données contigu.
Citer : Posté le 25/03/2015 11:49 | #
Oui mais du coup tu réduis la vitesse d'accès et tu fais des calculs avant un accès direct...
Citer : Posté le 25/03/2015 12:12 | #
bah c'est un compromis.
la défragmentation tu ne la fera que très peu de fois, et elle te permet de passer un tableau classique aux fonctions de type qsort.
de toutes façons, j'implémenterai les deux approches, faudra juste que je trouve des noms appropriés...
l'approche de Qlist reste intéressante sur des petites listes (ça devient coûteux de réallouer une grosse liste si c'est du O(N) à chaque fois)
l'approche par segmentation devient plus intéressante sur des grandes listes (c'est un peu con de stocker un segment de 64 octets pour deux pauvres int...)
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