Bops : Piles.

Présentation générale

Structures de données


Survol des fonctions


Création/suppression d'une pile.
Création/suppression, accès aux éléments de pile.
Accès aux données à partir d'un élément.
Les fonctions étendues.

Fichier à inclure.
Création/suppression d'une pile.
Création/suppression, accès aux éléments de pile.
Accès aux données à partir d'un éléments.
Les fonctions étendues.

Fonctionnalités.

Bops permet l'accès a des piles. Les piles sont des types simples de données, elles sont communément appelées LIFO (Last In First Out) stacks.
Leur gestion a le même niveau de difficulté que la gestion d'une pile d'assiettes dans un placard, cependant Bops a la particularité de rendre cette pile extensible, il agrandit votre placard lorsque vous voulez ajouter une assiette alors que celle du dessus de la pile touche déjà le haut du placard. il n'a de limites que celles imposées par le plafond de la cuisine (i.e. par la mémoire allouable disponible).
Assez généralement dans leurs utilisations courantes, les piles n'ont pas une très grande taille et l'extensibilité n'est pas une fonctionnalité très importante, elle décharge cependant le programmeur du choix d'une taille à allouer ou de la gestion du parametrage de cette taille par un utilisateur. Il est donc interessant de proposer cette fonctionnalité d'autant que son coût en ressources est faible.
Cette gestion de l'extensibilité de la pile demande a bops peu d'utilisation supplementaire de ressources, il n'execute de code supplémentaire qu'en cas de dépassement de capacité actuelle de la pile et aussi un peu lorsqu'une allocation ajoutée à la pile n'est plus utilisée.

La stratégie d'extension de la pile est paramétrable mais Bops propose un paramètrage par defaut qui convient pour beaucoup de cas d'utilisation des piles.

Pour paramétrer l'extension de la pile, l'utilisateur indique une allocation primaire, le nombre d'éléments disponibles dans la pile à sa création, et une allocation secondaire, le nombre d'éléments alloués lorsque l'allocation primaire (ou une allocation secondaire précédente) ne suffit plus. Bops propose des valeurs par défaut : il calcule le nombre d'éléments qui occupent une page de votre machine.

Afin de limiter les onereuses allocations et libérations de mémoire, Bops a une gestion un peu paresseuse de l'espace, lorsqu'une allocation secondaire n'est plus utilisée, il ne la libère pas d'emblée mais regarde s'il n'y a pas une seconde allocation non utilisée et la libère si c'est le cas. En quelque sorte, il garde toujours une allocation d'avance lorsqu'il en a de disponible, cela peut se réveler une gestion particulièrement économe lorsque le haut de la pile fluctue entre la fin d'une allocation et le début d'une autre.

Cette stratégie simple (mais efficace) n'est pas paramètrable (on ne peut fixer le nombre d'allocations que Bops doit garder d'avance), ce serait une complication que je juge inutile, le choix des allocations primaires et secondaires est sans doute très largement suffisant pour l'immense majorité des utilisations des piles. Laisser Bops choisir ces allocations est aussi un bon choix dans la plupart des cas. A moins que votre pile n'ait qu'une hauteur assez petite pour ne jamais dépasser l'allocation primaire, prenez les valeurs par défaut ou un de leur multiple, le programme bopinfo de Bop-utils vous indiquera les valeurs par défaut calculées pour votre plateforme.

Pour une bonne introduction aux piles, voir ce cours en français.

Les fonctionnalités étendues permettant de n'empiler que sous condition sont détaillées dans le chapitre consacré à l'API détaillée.

Présentation générale

Structures de données

Bops utilise principalement 2 types (typedef de structures) de données :

BopsHandle

• Ce type référence un pile.
BopsEntry

• Il contient les informations relatives aux données placées dans une pile, un pointeur vers les données et leur longueur.

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é, les structures étant par elle-même sujettes au changement.

Survol des fonctions

Elles permettent de créer/supprimer des piles, d'empiler et de dépiler (terme employé de manière peu conforme au dictionnaire, il s'agit ici de l'inverse d'empiler), d'associer des données à ces éléments etc.

Allocation/suppression d'une pile.

• bopsNew() : allocation d'une pile.
• bopsDelete() : desallocation d'une pile.

Création/suppression, accès aux éléments.

• bopsPush() : Ajout (empilement) d'un élément au somment de la pile.
• bopsPop() : Suppression (dépilement) de l'élément au sommet de la pile.
• bopsGetTop() : accède à l'élément en haut de la pile.
• bopsIsEmpty() : test si une pile est vide.

Accès aux données à partir d'un élément.

• bopsGetData() : accède à la donnée d'un élément.
• bopsGetLength() : accède à la longueur de la donnée d'un élément.

Les fonctions étendues.

• bopsXSet : Permet d'utiliser les fonctions étendues.
• bopsXUnset : retour à une pile "normale".
• bopsXPush : Empile si le donnée n'est pas déjà présente dans la pile.
• bopsXPop : dépile et "oublie" que la donnée est dans la pile.
• bopsXsetCursor : Place le haut de la pile à un endroit de cette pile.

API détaillée.

Fichier à inclure.

#include <bop.2/bop.h>


Allocation/suppression d'une pile.

• BopsHandle * bopsNew( BopcHandle * container, char * name, unsigned pSize, unsigned sSize )
  Crée une pile et retourne un handle permettant de l'utiliser.
  
  container est le container dans lequel doit être placée cette pile, ou NULL.
  name est le nom associé à cette pile, ou NULL.
  pSize est le nombre d'éléments reservés par l'allocation primaire, ou zero pour le nombre par defaut.
  sSize est le nombre d'éléments qui seront alloués par chaque allocation secondaire, ou zero pour le nombre par defaut.
  
• int bopsDelete( void * unused, BopsHandle * stack)
  Desallocation de la pile stack et des ressources qui lui sont liées.
  unused est reservé pour un usage ulterieur.
  

Création/suppression, accès aux éléments.

• BopsEntry * bopsPush( BopsHandle* stack, void * data, size_t length )
  Ajout d'un élément en haut de la pile. un élément composé du pointeur data et de length est empilée.
  retourne NULL (l'élément juste empilé est accessible par bopsGetTop()).
  
• BopsEntry * bopsPop( BopsHandle* stack )
  Enlève de la pile l'élément du haut de la pile lorsque la pile n'est pas vide.
  Retourne un pointeur vers cet élément ou NULL lorsque la pile est vide.
  A partir de l'élément retourné on peut acceder à la donnée par les fonctions bopsGetData() et bopsGetLength().
  
• BopsEntry * bopsGetTop( BopsHandle* stack )
  Retourne l'élément situé au haut de la pile, la pile n'est pas modifiée.
  A partir de l'élément retourné on peut acceder à la donnée par les fonctions bopsGetData() et bopsGetLength.
  
• int bopsIsEmpty( BopsHandle* stack )
  Retourne non-zero si la pile est vide, 0 sinon.

Accès aux données à partir d'un élément.

• void * bopsGetData( entry )
  retourne un pointeur sur la donnée d'un élément.
  
• size_t bopsGetLength( entry )
  retourne la longueur de la donnée d'un élément.
  

Les fonctions étendues.

Précision terminologique : Lorsqu'il est parlé plus bas de pile étendue, cela n'a aucun rapport avec l'extensibilité de la taille de la pile, il s'agit d'un raccourci pour parler d'une pile pour laquelle les fonctionnalités étendues sont permises.

Un des interêts des fonctions étendues est de permettre d'éviter une récursion infinie dans une exploration de graphes cycliques par une technique de pile.

La fonction bopsXSet permet à la pile de se "remémorer" les données qu'elle empile par bopsXPush. Typiquement, bopXSet est appelée après la création de la pile et bopsXUnset n'est jamais appelé, mais elle peut, comme bopsXUnset, être appelée à n'importe quel moment de la vie de la pile.
Nota bene : Ce sont les données et leur longueur qui sont remémorées, non leur adresse et leur longueur.


Il est possible d'appeler les fonctions étendues sur une pile non-étendue et, inversement, les fonctions non-étendues sur une pile étendue. Il est dans ce cas necessaire de bien connaitre leur comportement.

Les fonctions non-étendues se comporte de la même manière que la pile soit ou non étendue. Les fonctions étendues se comportent comme des fonctions non-étendues lorsqu'elles sont appliquées à une pile non-étendue.
Pour qu'une donnée soit remémorée, il faut que la pile soit une pile étendue (par bopsXSet) et qu'elle ait été empilée par bopsXPush. Pour qu'une donnée soit oubliée, il faut que la pile soit étendue et qu'elle ait été dépilée par bopsXPop (ceci qu'elle ait ou non été remémorée lors de l'empilement de l'élément qui vient d'être dépilée).

Très généralement, à moins d'avoir de bonnes raisons d'avoir concu differement un logiciel utilisant Bops, il est préférable d'utiliser soit des fonctions non-étendues sur une pile non-étendue soit des fonctions étendues sur une pile étendue.
Notons qu'il est particulièrement dangereux et probablement sans interêt de dépiler par bopsPop un élément d'une pile étendue empilé par bopsXpush.


Digression technique : Bops utilise un hash Boph pour se remémorer les données empilées.

• int bopsXSet( BopsHandle * stack )
  Permet d'utiliser les fonctionnalitéss étendues.
  Retourne non-zero en cas de succès et zero lorsque la pile est déjà étendue.
  
• int bopsXUnsset( BopsHandle * stack )
  Retour à une pile non-étendue.
  Les données remémorées sont oubliées.
  
• BopsEntry * bopsXPush( BopsHandle * stack, void * data, size_t length )
  Se comporte comme bopsPush lorque stack n'est pas une pile étendue.
  Empile si la donnée n'est pas déjà remémorée dans la pile étendue, retourne sinon le élément de la pile ou elle est remémorée.
  Lorsque la donnée est empilée, se remémore l'avoir empilée à cet endroit et retourne NULL.
  
• BopsEntry * bopsXPop( BopsHandle * stack )
  Se comporte comme bopsPush lorque stack n'est pas une pile étendue.
  dépile et "oublie" que la donnée est dans la pile si elle remémorée dans une pile étendue.
• bopsXsetCursor( BopsHandle * stack, BopsEntry * element )
  Place le haut de la pile stack à un élément de cette pile designé par element.
  Se comporte comme si les éléments placés après cette entrée avaient été dépilés avec bopsXPop et qu'elle retournait la valeur de bopsGetTop.
  La valeur retournée est donc celle fournie en argument lorsque l' élément est trouvé dans la pile, Lorsque l'élément n'est pas dans la pile, la pile est vidée et la valeur retournée est celle qui serait retournée par bopsGetTop, i.e. NULL. Notons que cette fonction est gourmande en ressources, sutout lorsqu'elle s'applique à une pile étendue.

Exemples.

Des programmes de test de Bop, par ailleurs inutiles, peuvent servir d'exemples :

• boptac.c
  Ce programme imite le célèbre utilitaire Unix tac(1) (l'inverse de cat).
• bouptac.c
  Un tac amélioré, il teste les fonctions étendues.

Reste à faire.

Voir aussi.

Obstacks, chez moi la documentation se trouve sur :
file:/usr/share/doc/glibc-doc/html/libc_3.html#SEC42