List

list.c

/*
 *
 * Libreria para listas de proposito general
 * Haga lo que quiera con ella, pero no hay garantias
 * Silvio Quadri (c) 2009
 * Buenos Aires, Argentina
 *
 * */

#include  "list.h"
#include  <stdlib.h>
#include  <string.h>
#include  <assert.h>


#define  LIST_ALLOC(n)      malloc(n)
#define  LIST_REALLOC(p,n)  realloc(p,n)
#define  LIST_FREE(p)       free(p)

#define  DEFAULT_ALLOC      10

/*
 * Definicion de nueva lista
 */
_list*  list_nueva( _list_freefunc free_func ){
    return list_nueva_con_tamanio( free_func, DEFAULT_ALLOC );
}

/*
 * Define una nueva lista con un tamanio pasado por parametro
 * */

_list*  list_nueva_con_tamanio( _list_freefunc free_func, int size ){
    _list*  l = LIST_ALLOC(sizeof(_list));  
    if( size < DEFAULT_ALLOC ) size = DEFAULT_ALLOC;
    l->entradas = 0;
    l->tamanio  = size;
    l->data     = LIST_ALLOC( sizeof(void*) * size );
    l->actual   = 0;
    l->free_func = free_func;
    return l;
}

/*
 * Agrega un nuevo elemento
 * */
void    list_agrega( _list* lista, void* data ){
    if( lista->entradas == lista->tamanio ){
        lista->tamanio += DEFAULT_ALLOC;
        assert( lista->data = LIST_REALLOC( lista->data, lista->tamanio * sizeof(void*) ) );
    }
    lista->data[lista->entradas++] = data;
}

/*
 * Quita algo de la lista y mueve todo el aparato
 * */
void    list_quita( _list* lista, int entrada ){

    // Una comprobacion importante y de bajo costo!
    assert( entrada < lista->entradas );

    if( lista->free_func ) lista->free_func( lista->data[entrada] );
    if( lista->actual >= entrada ) lista->actual --;

    if( lista->entradas - entrada - 1 > 0 ){
        memmove( lista->data + entrada, lista->data + entrada + 1, 
                 ( lista->entradas - entrada - 1 ) * sizeof( void* ) );
    }

    lista->entradas --;

}

/*
 * Toma el último valor y lo quita de la lista
 *
 * */
void*   list_pop( _list*  lista ){

    void* v;
    if( lista->entradas == 0 ){
        return NULL;
    }

    lista->entradas --;
    v = lista->data[lista->entradas];
    return v;
}

/*
 * Limpia los datos de la lista
 * y la lista también ...
 * */
void    list_free( _list* lista ){

    int i;
    if( lista->free_func ){
        for( i = 0; i < lista->entradas; i ++ ){
            if( lista->free_func ) lista->free_func( lista->data[i] );
        }
    }

    LIST_FREE( lista );

}

list.h

/*
 *
 * Libreria para listas de proposito general
 * Haga lo que quiera con ella, pero no hay garantias
 * Silvio Quadri (c) 2009
 *
 * */

#ifndef  LIST_INCLUDED
#define  LIST_INCLUDED

typedef  void(*_list_freefunc)(void*);

#ifndef  NULL  
#define  NULL  (void*)0
#endif

typedef  struct  _str_list{
    void**  data;
    unsigned int    entradas;
    unsigned int    tamanio;
    unsigned int    actual;
    _list_freefunc   free_func;
}  _list;


_list*  list_nueva( _list_freefunc free_func );
_list*  list_nueva_con_tamanio( _list_freefunc free_func, int size );
void    list_agrega( _list* lista, void* data );
void    list_quita( _list* lista, int entrada );
void*   list_pop( _list*  lista );
void    list_free( _list* );

static inline void    list_inicio( _list* lista ) { lista->actual = 0; } 
static inline void    list_final( _list* lista )  { lista->actual = lista->entradas - 1; } 

static inline void*   list_siguiente( _list* lista ) {
    if( lista->actual >= lista->entradas ){ return NULL; }
    return( lista->data[ lista->actual++ ] );
}

static inline void*   list_anterior( _list* lista ){
    if( lista->actual == 0 ) return NULL;
    return lista->data[ lista->actual-- ];
}

static inline void*   list_top( _list* lista ){
    if( !lista->entradas ) return NULL;
    return lista->data[lista->entradas-1];
}

#define   list_push    list_agrega


#endif

test_list.c

#include   <stdio.h>
#include   <string.h>
#include  <stdlib.h>
#include   <assert.h>
#include   "list.h"

void  free_char(void* d){
    free( d );
}


int  main(int argc, char** argv){
    _list* l;
    int x, act;
    char* v;
  
    printf( "." ); 
    assert( l = list_nueva(free_char) );
    for( x = 0; x < 100; x ++ ){ 
        char*  linea;
        linea = (char*) malloc( 24 );
        sprintf( linea, "Nueva %d", x );
        list_agrega( l, (void*) linea ); 
    }

    printf( "." ); 
    assert( l->entradas == 100 );

    printf( "." ); 
    assert( strcmp( l->data[0], "Nueva 0" ) == 0 );
    assert( strcmp( l->data[1], "Nueva 1" ) == 0 );

    list_quita( l, 22 );
    printf( "." ); 
    assert( l->entradas == 99 );

    printf( "." ); 
    assert( strcmp( l->data[0], "Nueva 0" ) == 0 );
    assert( strcmp( l->data[1], "Nueva 1" ) == 0 );
    assert( strcmp( l->data[23], "Nueva 24" ) == 0 );
    assert( strcmp( l->data[97], "Nueva 98" ) == 0 );
    assert( strcmp( l->data[98], "Nueva 99" ) == 0 );

    // Compruebo el armado ...
    list_inicio( l );
    x = 0; act = 0;
    assert( l->actual == act );
    while( ( v = list_siguiente( l ) ) ){
        if( x == 22 ) x ++;
        assert( l->actual ==( ++act ) );
        char lll[24];
        printf( "." ); 
        sprintf( lll, "Nueva %d", x );
        // printf( "(%d) %s == %s\n", l->actual, lll, v );
        assert( strcmp( v, lll ) == 0 );
        x ++;
    }

    // Ahora al reves ...
    list_final( l );
    x = 99;
    while( ( v = list_anterior( l ) ) ){
        if( x == 22 ) x --;
        char lll[24];
        printf( "." ); 
        sprintf( lll, "Nueva %d", x );
        assert( strcmp( v, lll ) == 0 );
        x --;
    }

    // Pop
    v = list_pop( l );
    printf( "." ); 
    assert( strcmp( v, "Nueva 99" ) == 0 );
    assert( l->entradas == 98 );

    printf( "\n" );
    list_free( l );
    return 0;

}