Bopl : Listes

BoplHandle : (lists handle)
- C'est un container, il est utilisé pour la création des listes de plus haut niveau.
  Typiquement, il est alloué et détruit une fois dans un programme pour y placer les listes dont ce programme a besoin. Mais il peut être plus avantageux pour un programme d'en allouer plusieurs.
- Fonctions concernées :
  - boplNew() : allocation d'un lists handle.
  - boplDelete() : desallocation du handle et des listes qu'il contient.
  - boplNewList() : Création d'une liste.
BoplEntry
- Ce type référence un élement de liste qui peut être soit une liste soit un simple élément
  . Nous parlerons pour les différencier de genre d'élément pour éviter toute ambiguité avec le mot "type". Il contient les informations relatives au chainage des éléments et la référence aux données associées à l'élément (Outre la liste référencée par un élément de genre liste, les éléments de genre liste peuvent référencer aussi des données,

Ces structures de données ne devraient être utilisée que par l'intermédiaire de l'API, celle-ci étant supposée assurer la compatibilité.

Survol des fonctions

Elles permettent de créer/supprimer des listes et d'autres éléments, d'associer des données à ces éléments, de parcourir les listes etc.

Allocation/suppression d'un handle.

boplNew() : allocation d'un lists handle.
boplDelete() : desallocation du handle et des listes qu'il contient.

Création/suppression d'éléments de liste.

boplNewList() : Allocation d'une liste de plus haut niveau dans le handle spécifié.
boplDelEntry() : Suppression d'un élément. Supprime éventuellement les données associées à l'élément. Losqu'il s'agit d'un élément de genre liste, les éléments et listes de niveau inférieur sont aussi supprimées, sauf dans le cas où une liste est référencée par d'autres listes.
boplCreFirst() boplCreLast() : Crée un simple élément resp. au début ou à la fin d'une liste.
boplCreAfter() boplCreBefore() : Crée un simple élément resp. après ou avant un autre élement.
boplCreSubFirst() boplCreSubLast() : Crée un élément de genre liste resp. au début ou à la fin d'une liste.
boplCreSubAfter() boplCreSubBefore() : Crée un élément de genre liste resp. après ou avant un autre élement.
boplRefSubFirst() boplRefSubLast() : référence un élément de genre liste déjà existant resp. au début ou à la fin d'une liste.
boplRefSubAfter() boplRefSubBefore() : référence un élément de genre liste déjà existant resp. après ou avant un autre élement.

Parcours des listes.

boplGetFirst() boplGetLast() : Accède au resp. premier élément d'une liste.
boplGetNext() boplGetPrev() : Accède à resp. l'élément suivant ou précédant.
boplScanF() boplScanB() : Parcours d'une liste dans un sens ou dans l'autre.

Accès aux données des éléments.

boplSetData() boplGiveData() boplCopyData() : Associe des données à un élément.
boplGetData() : accède au données d'un élément.
boplGetLength() : accède à la longueur des données d'un élément.

Test des caractéristiques d'un élément

BoplIsList() : test si un élément est du genre liste.
BoplIsEmpty() : test si un liste est vide d'élément.
BoplIsEnd() : test si une condition End-Of-List a été atteinte lors du parcours d'une liste.
BoplGetNumLink() : retourne le nombre de références à une liste (référence count).

API détaillée

Remarques.

Lorsque un argument d'une fonction doit être de genre liste, il est appelé "liste[n]" dans cette documentation, par exemple :
BoplEntry * boplGetFirst( BoplEntry * liste )
Lorsque un argument d'une fonction peut être de genre liste ou simple entry, il est appelé "entry", par exemple :
BoplEntry * boplGetNext( BoplEntry * entry )

Des données peuvent liées à un élément de liste, vous me direz que c'est la moindre des choses ;-).
Duand des données sont liées à un élément de genre liste, ces données sont liées à cette liste référencée et non à la référence qui en est faite, i.e. si plusieurs éléments listes référencent une même liste, toute modification de la liste référencée modifient les autres références à cette liste, ce qui semble être un comportement généralement souhaitable, mais cela change aussi les données liées aux éléments listes référençant cette liste.
les éléments de genre liste sont des références à des listes, les données de la liste ne sont pas associées à cette référence mais à la liste référencée.

Fichier à inclure.

#include <bop.2/bop.h>

Allocation/suppression d'un handle.

BoplHandle * boplNew( BopcHandle * container )
Retourne un handle qui sera utilisé pour créer les listes du plus haut niveau.
container designe, lorsqu'il n'a pas la valeur NULL, le container dans lequel doit être placée le handle.
int boplDelete( void * unused, BoplHandle * handle )
Desallocation du handle et des listes qu'il contient ainsi que les données associées aux éléments de liste lorsque cela a été précisé au moment de l'association des données à ces éléments.
Lorsque des sous-listes sont également référencées par un autre handle, elles ne sont pas libérées, elles ne sont libérées que lorqu'elles sont déférencées pour la dernière fois (On peut établir un parallèle avec les "hard links" d'un système de fichiers).
L'argument "unused" est reservé pour un usage ultérieur et devrait être à NULL.

Création/suppression.

BoplEntry * boplNew(BoplHandle * handle)
Allocation d'une liste de plus haut niveau dans le handle spécifié. Retourne un élément de genre liste nouvellement alloué.
int boplDelEntry(BoplEntry * entry)
Suppression de l'élément entry. Supprime éventuellement les données associées à l'élément. Losqu'il s'agit d'un élément de genre liste, les éléments et listes de niveau inférieur sont aussi supprimées, sauf dans le cas où une liste est référencée par d'autres listes, le "reference count" de la liste est alors décrémenté.
La valeur retournée est sans signification pour l'appelant.
BoplEntry * boplCreFirst( BoplEntry * liste )
BoplEntry * boplCreLast( boplEntry * liste )
Crée un simple élément resp. au début ou à la fin d'une liste.
liste doit être du genre liste.
Retourne l'élément créé.
BoplEntry * boplCreAfter( BoplEntry * entry )
BoplEntry * boplCreBefore( BoplEntry * entry )
Crée un simple élément resp. après ou avant un autre élement.
entry peut être du genre liste ou simple.
Retourne l'élément créé.
BoplEntry * boplCreSubFirst( boplEntry * liste )
BoplEntry * boplCreSubFirst( boplEntry * liste )
Crée un élément de genre liste resp. au début ou à la fin d'une liste.
liste doit être du genre liste.
Retourne l'élément liste créé.
BoplEntry * boplCreSubAfter( boplEntry * entry )
BoplEntry * boplCreSubBefore( boplEntry * entry )
Crée un élément liste resp. après ou avant un autre élement.
entry peut être du genre liste ou simple.
Retourne l'élément liste créé.
BoplEntry * boplRefSubFirst( BoplEntry * liste1, BoplEntry * liste2 )
BoplEntry * boplRefSubFirst( BoplEntry * liste1, BoplEntry * liste2 )
Crée un élément de genre liste resp. au début ou à la fin de la liste liste1. Cet entry référence la liste liste2 déjà existante,
liste1 et liste2 doivent être du genre liste.
Retourne l'élément liste créé.
BoplEntry * boplRefSubAfter( BoplEntry * entry, BoplEntry * liste )
BoplEntry * boplRefSubBefore( BoplEntry * entry, BoplEntry * liste2 )
Crée un élément de genre liste resp. après ou avant l'élément entry. Cet entry créé référence la liste liste déjà existante,
liste doit être du genre liste.
Retourne l'élément liste créé.

Parcours des listes.

BoplEntry * boplGetFirst( BoplEntry * liste )
BoplEntry * boplGetLast( BoplEntry * liste )
Retourne le resp. premier ou dernier élément d'une liste liste. Lorsque la liste est vide, renvoie un élément pouvant être testé par boplIsEnd()
BoplEntry * boplGetNext( BoplEntry * entry )
BoplEntry * boplGetPrev( BoplEntry * entry )
Retourne l'élément resp. suivant ou précédant l'élément entry. Après resp. le début ou la fin d'une liste, renvoie un élément pouvant être testé par boplIsEnd().
boplScanF( void * data, BoplEntry * liste,
int (* func)( void * data, BoplEntry *element) )

Parcours la liste à partir du premier élément en appelant la fonction func pour chaque element.
la fonction boplScanB( ) acceptant les mêmes arguments part du dernier élément et parcoure la liste dans le sens inverse.
La fonction n'explore pas les sous-listes de liste, cela peut être fait par la fonction func en appelant recursivement boplScanF (en se spécifiant éventuellement comme fonction à appeler).
L'argument data est passé à la fontion func à chacun de ses appels.
La fonction func doit renvoyer une valeur non-nulle pour que le parcours de la liste continue.
Retourne la valeur retournée par la dernière fonction func appelée ou 0 si c'est la fin de liste qui a provoqué l'arrêt de son parcours.

Accès aux données des éléments.

BoplEntry * boplSetData( BoplEntry * entry, void * data, size_t length )
Associe la donnée pointée par data et de longueur length à l'élément entry.
Cette donnée ne sera pas desallouée lorsque l'élément sera desalloué.
Retourne l'entry modifié.
BoplEntry * boplGiveData( BoplEntry * entry, void * data, size_t length )
Associe la donnée pointée par data et de longueur length à l'élément entry.
Cette donnée sera desallouée lorsque l'élément sera desalloué.
Retourne l'entry modifié.
BoplEntry * boplCopyData( BoplEntry * entry, void * data, size_t length )
Copie la donnée pointée par data et de longueur length et associe cette copie à l'élément entry.
Cette copie sera desallouée lorsque l'élément sera desalloué.
Retourne l'entry modifié.
void * boplGetData( BopEntry * entry )
Retourne un pointeur sur les données d'un élément.
size_t boplGetLength( BopEntry * entry )
Retourne la longueur des données d'un élément.

Test des caractéristiques d'un élément

int boplIsList( BoplEntry * entry )
Retourne 1 si l'élément entry est du genre liste, 0 sinon.
int boplIsEmpty( BoplEntry * liste )
Retourne 1 si la liste liste est vide d'élément, 0 sinon.
int boplIsEnd( BoplEntry * entry )
Teste si une condition End-Of-List a été atteinte lors du parcours d'une liste.
Retourne 1 lorsqu'on est en fin de liste, 0 sinon.
int boplGetLinkNum( BoplEntry * entry )
Retourne le référence count (nombre de listes à laquelle cette liste appartient) si entry est une liste, 0 sinon.
Dans le cas d'une liste, même de plus haut niveau, ce nombre est toujours positif.

Exemples.

Des programmes de test de Bop peuvent servir d'exemples :

bopwc.c
Ce programme compte et affiche les mots d'un fichier.

le programme bopmtrace de Bop-utils est aussi un exemple de la possible utilisation d'un hash dans le "monde réel".

Reste à faire

Une fonction permettant d'appeler une fonction spécifiée par l'utilisateur pour chaque élément d'une liste ou d'un arbre. elle permettra de parcourir l'arbre de manière préfixée ou postfixée.
Cette fonction devra permettre d'éviter une recursion infinie lorsqu'une liste référence une liste de niveau supérieur (dans l'arbre de laquelle elle est incluse), cela se fera classiquement par une technique de pile.

http://freefeed/bop/bopl.php (13/12/2006) Copyright © 2004 Patrick Davalan.
Il est permis de copier, distribuer et/ou modifier ce document selon les termes et condiions de la GNU Free Documentation License, version 1.2 ou toute version ulterieure publiée par la Free Software Foundation.
Warning: fopen(/home/web/patrick/data/locks/bop%2Fbopl.php): failed to open stream: No such file or directory in /home/web/patrick/include/functions.inc on line 315