14

Gestionnaire de listes

  1. typedef struct _list {
  2.     int l;
  3.     void **v;
  4. } *list;

Un type list est constitué d'une simple suite consécutive de pointeurs. l donne le nombre d'éléments dans la liste. v pointe sur une zone en mémoire assez grande pour contenir tous les éléments de la liste.

  1. extern list list_alloc( void );
  2. extern list list_init( list this );
  3. extern list list_new( void );
  4. extern void list_free( list this );
  5. extern int list_length( list this );
  6. extern void *list_get( list this, int key );
  7. extern void *list_put( list this, int key, void *val );
  8. extern void *list_delete( list this, int key );
  9. extern void *list_insert( list this, int key, void *val );

list_new retourne une nouvelle liste vide.
list_free désalloue la mémoire occupée par une liste.
list_length donne le nombre d'éléments contenus dans une liste.
list_get retourne un élément d'une liste.
list_put, list_insert et list_delete modifient le contenu d'une liste.

  1. list list_alloc( void ) {
  2.     return (list)calloc( 1, sizeof ( struct _list ));
  3. }
  4.  
  5. list list_init( list this ) {
  6.     return this;
  7. }
  8.  
  9. list list_new( void ) {
  10.     return list_init( list_alloc() );
  11. }
  12.  
  13. void list_free( list this ) {
  14.     if ( this->v )
  15.         free( this->v );
  16.     free( this );
  17. }

list_new retourne une instance de list nouvellement allouée et initialisée.
list_alloc alloue la mémoire nécessaire à une liste et la retourne.
list_init retourne la liste this après l'avoir initialisée.

list_free libère la mémoire occupée par le tableau de pointeurs et la structure de la liste this.

  1. int list_length( list this ) {
  2.     return this->l;
  3. }

list_length retourne le nombre d'éléments de la liste this.

  1. void *list_get( list this, int key ) {
  2.     if ( key < 0 )
  3.         return this->l ? this->v[ this->l - 1 ] : 0;
  4.     else if ( key < this->l )
  5.         return this->v[ key ];
  6.     else
  7.         return 0;
  8. }

list_get retourne l'élément de la liste this à la position key.
Si key est négatif, list_get retourne le dernier élément de la liste.
Si la liste est vide ou si key est supérieur à la longueur de la liste, list_get retourne 0.

  1. void *list_put( list this, int key, void *val ) {
  2.     if ( key < 0 )
  3.         key = this->l;
  4.     if ( key < this->l )
  5.         this->v[ key ] = val;
  6.     else {
  7.         this->l = key + 1;
  8.         this->v = (void **)realloc( this->v, (key + 1) * sizeof ( void * ));
  9.         this->v[ key ] = val;
  10.     }
  11.  
  12.     return val;
  13. }

list_put place val à la position key dans la liste this. val est un pointeur quelconque.
Si key est négatif, val est ajouté à la fin de la liste.
Si la liste est vide ou si key est supérieur à la longueur de la liste, list_put alloue assez d'espace pour contenir key éléments et place val à la fin de la liste. NOTE : realloc prend soin de copier les données si un nouveau bloc de mémoire est effectivement alloué.

list_put retourne val.

  1. void *list_delete( list this, int key ) {
  2.     void **p, *val;
  3.  
  4.     if ( key < 0 )
  5.         key = this->l ? this->l - 1 : 0;
  6.     if ( key < this->l ) {
  7.         val = this->v[ key ];
  8.         this->l--;
  9.         for ( p = this->v + key; p < this->v + this->l; p++ )
  10.             *p = *(p+1);
  11.         return val;
  12.     }
  13.     else
  14.         return 0;
  15. }

list_delete supprime l'élément de la liste this à la position key.
Si key est négatif, list_delete supprime le dernier élément de la liste.
list_delete décrémente la longueur de la liste et décale tous les éléments de la liste vers la gauche à partir de key + 1. Tous les éléments après key changent d'index.

list_delete retourne l'élément supprimé ou 0 si la liste est vide ou si key est supérieur à la longueur de la liste.

  1. void *list_insert( list this, int key, void *val ) {
  2.     void **p;
  3.  
  4.     if ( key < 0 || key >= this->l )
  5.         return list_put( this, key, val );
  6.  
  7.     this->l++;
  8.     this->v = (void **)realloc( this->v, this->l * sizeof ( void * ));
  9.  
  10.     for ( p = this->v + (this->l - 1); p > this->v + key; p-- )
  11.         *p = *(p-1);
  12.  
  13.     this->v[ key ] = val;
  14.  
  15.     return val;
  16. }

list_insert insère l'élément val à la position key dans la liste this. val Si key est négatif ou supérieur à la longueur de la liste, val est ajouté à la fin de la liste.
list_insert incrémente la longueur de la liste, alloue assez d'espace pour contenir un élément de plus, décale tous les éléments de la liste vers la droite à partir de key + 1 et place val à la position key. Tous les éléments après key changent d'index. NOTE : realloc prend soin de copier les données si un nouveau bloc de mémoire est effectivement alloué.

list_insert retourne l'élément ajouté.

Commentaires

Votre commentaire :
[p] [b] [i] [u] [s] [quote] [pre] [br] [code] [url] [email] strip aide 2000

Entrez un maximum de 2000 caractères.
Améliorez la présentation de votre texte avec les balises de formatage suivantes :
[p]paragraphe[/p], [b]gras[/b], [i]italique[/i], [u]souligné[/u], [s]barré[/s], [quote]citation[/quote], [pre]tel quel[/pre], [br]à la ligne,
[url]http://www.izend.org[/url], [url=http://www.izend.org]site[/url], [email]izend@izend.org[/email], [email=izend@izend.org]izend[/email],
[code]commande[/code], [code=langage]code source en c, java, php, html, javascript, xml, css, sql, bash, dos, make, etc.[/code].