Les membres ayant 30 points peuvent parler sur les canaux annonces, projets et hs du chat.
La shoutbox n'est pas chargée par défaut pour des raisons de performances. Cliquez pour charger.

Forum Casio - Projets de programmation


Index du Forum » Projets de programmation » GCL - une librairie de conteneurs génériques en C
Siapran Hors ligne Membre Points: 3248 Défis: 17 Message

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.


1, 2 Suivante
Dark storm Hors ligne Labélisateur Points: 11620 Défis: 176 Message

Citer : Posté le 22/03/2015 20:26 | #


Sympa ça
Finir est souvent bien plus difficile que commencer. — Jack Beauregard
Siapran Hors ligne Membre Points: 3248 Défis: 17 Message

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?
-florian66- Hors ligne Ancien rédacteur Points: 2383 Défis: 20 Message

Citer : Posté le 23/03/2015 07:28 | #


Cool le principe
In Arch, I trust ! And you ?
Intelligide Hors ligne Membre de CreativeCalc Points: 49 Défis: 5 Message

Citer : Posté le 23/03/2015 08:13 | #


Siapran a écrit :
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
Lephenixnoir Hors ligne Administrateur Points: 24069 Défis: 169 Message

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 :

Siapran a écrit :
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.

Siapran a écrit :
# 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...

Siapran a écrit :
# 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.

Siapran a écrit :
# 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.

Siapran a écrit :
# est-ce que je favorise la lisibilité et la sécurité du code par rapport à la performance?

Non.

Siapran a écrit :
# 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.

Siapran a écrit :
# est-ce que je favorise la cohérence par rapport à l'ergonomie?

Oui.

Mon graphe (25 Fév): (PythonExtra ; fxsdk#11 ; gint#27 ; (Rogue Life || HH2) ; serial gint ; Boson X ; ...) || (shoutbox v5 ; v5)
Siapran Hors ligne Membre Points: 3248 Défis: 17 Message

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...
Lephenixnoir Hors ligne Administrateur Points: 24069 Défis: 169 Message

Citer : Posté le 23/03/2015 20:31 | #


Siapran a écrit :
[...] 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
Mon graphe (25 Fév): (PythonExtra ; fxsdk#11 ; gint#27 ; (Rogue Life || HH2) ; serial gint ; Boson X ; ...) || (shoutbox v5 ; v5)
Siapran Hors ligne Membre Points: 3248 Défis: 17 Message

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 >.<
Lephenixnoir Hors ligne Administrateur Points: 24069 Défis: 169 Message

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.
Mon graphe (25 Fév): (PythonExtra ; fxsdk#11 ; gint#27 ; (Rogue Life || HH2) ; serial gint ; Boson X ; ...) || (shoutbox v5 ; v5)
Siapran Hors ligne Membre Points: 3248 Défis: 17 Message

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.
Intelligide Hors ligne Membre de CreativeCalc Points: 49 Défis: 5 Message

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é essaye de reproduire ça
Siapran Hors ligne Membre Points: 3248 Défis: 17 Message

Citer : Posté le 23/03/2015 20:46 | #


Bah c'est peut-être moi 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
Intelligide Hors ligne Membre de CreativeCalc Points: 49 Défis: 5 Message

Citer : Posté le 24/03/2015 07:49 | #


cool vive le regex!
Lephenixnoir Hors ligne Administrateur Points: 24069 Défis: 169 Message

Citer : Posté le 24/03/2015 19:00 | #


Siapran a écrit :
et le coup de recopier par tranche de 4 c'est foireux et c'est du undefined behaviour.

Mais... en quoi ?
Mon graphe (25 Fév): (PythonExtra ; fxsdk#11 ; gint#27 ; (Rogue Life || HH2) ; serial gint ; Boson X ; ...) || (shoutbox v5 ; v5)
Siapran Hors ligne Membre Points: 3248 Défis: 17 Message

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
Lephenixnoir Hors ligne Administrateur Points: 24069 Défis: 169 Message

Citer : Posté le 25/03/2015 11:41 | #


Ah oui, tu cherches la portabilité...
Mon graphe (25 Fév): (PythonExtra ; fxsdk#11 ; gint#27 ; (Rogue Life || HH2) ; serial gint ; Boson X ; ...) || (shoutbox v5 ; v5)
Siapran Hors ligne Membre Points: 3248 Défis: 17 Message

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.
Lephenixnoir Hors ligne Administrateur Points: 24069 Défis: 169 Message

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...
Mon graphe (25 Fév): (PythonExtra ; fxsdk#11 ; gint#27 ; (Rogue Life || HH2) ; serial gint ; Boson X ; ...) || (shoutbox v5 ; v5)
Siapran Hors ligne Membre Points: 3248 Défis: 17 Message

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...)
Lephenixnoir Hors ligne Administrateur Points: 24069 Défis: 169 Message

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
Mon graphe (25 Fév): (PythonExtra ; fxsdk#11 ; gint#27 ; (Rogue Life || HH2) ; serial gint ; Boson X ; ...) || (shoutbox v5 ; v5)
1, 2 Suivante

LienAjouter une imageAjouter une vidéoAjouter un lien vers un profilAjouter du codeCiterAjouter un spoiler(texte affichable/masquable par un clic)Ajouter une barre de progressionItaliqueGrasSoulignéAfficher du texte barréCentréJustifiéPlus petitPlus grandPlus de smileys !
Cliquez pour épingler Cliquez pour détacher Cliquez pour fermer
Alignement de l'image: Redimensionnement de l'image (en pixel):
Afficher la liste des membres
:bow: :cool: :good: :love: ^^
:omg: :fusil: :aie: :argh: :mdr:
:boulet2: :thx: :champ: :whistle: :bounce:
valider
 :)  ;)  :D  :p
 :lol:  8)  :(  :@
 0_0  :oops:  :grr:  :E
 :O  :sry:  :mmm:  :waza:
 :'(  :here:  ^^  >:)

Σ π θ ± α β γ δ Δ σ λ
Veuillez donner la réponse en chiffre
Vous devez activer le Javascript dans votre navigateur pour pouvoir valider ce formulaire.

Si vous n'avez pas volontairement désactivé cette fonctionnalité de votre navigateur, il s'agit probablement d'un bug : contactez l'équipe de Planète Casio.

Planète Casio v4.3 © créé par Neuronix et Muelsaco 2004 - 2024 | Il y a 41 connectés | Nous contacter | Qui sommes-nous ? | Licences et remerciements

Planète Casio est un site communautaire non affilié à Casio. Toute reproduction de Planète Casio, même partielle, est interdite.
Les programmes et autres publications présentes sur Planète Casio restent la propriété de leurs auteurs et peuvent être soumis à des licences ou copyrights.
CASIO est une marque déposée par CASIO Computer Co., Ltd