|
Packit |
89ede9 |
/*
|
|
Packit |
89ede9 |
* vplist.c
|
|
Packit |
89ede9 |
*
|
|
Packit |
89ede9 |
* Version: 1/9/2017
|
|
Packit |
89ede9 |
*
|
|
Packit |
89ede9 |
* Copyright (c) Chris Putnam 2011-2018
|
|
Packit |
89ede9 |
*
|
|
Packit |
89ede9 |
* Source code released under the GPL version 2
|
|
Packit |
89ede9 |
*
|
|
Packit |
89ede9 |
* Implements a simple managed array of pointers to void
|
|
Packit |
89ede9 |
*
|
|
Packit |
89ede9 |
*/
|
|
Packit |
89ede9 |
#include <stdlib.h>
|
|
Packit |
89ede9 |
#include "vplist.h"
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
/* Do not use asserts in VPLIST_NOASSERT defined */
|
|
Packit |
89ede9 |
#ifdef VPLIST_NOASSERT
|
|
Packit |
89ede9 |
#define NDEBUG
|
|
Packit |
89ede9 |
#endif
|
|
Packit |
89ede9 |
#include <assert.h>
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
#define VPLIST_MINALLOC (20)
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
#define VPLIST_EXACT_SIZE (0)
|
|
Packit |
89ede9 |
#define VPLIST_DOUBLE_SIZE (1)
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
void
|
|
Packit |
89ede9 |
vplist_init( vplist *vpl )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
assert( vpl );
|
|
Packit |
89ede9 |
vpl->data = NULL;
|
|
Packit |
89ede9 |
vpl->n = vpl->max = 0;
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
vplist *
|
|
Packit |
89ede9 |
vplist_new( void )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
vplist *vpl;
|
|
Packit |
89ede9 |
vpl = ( vplist * ) malloc( sizeof( vplist ) );
|
|
Packit |
89ede9 |
if ( vpl ) vplist_init( vpl );
|
|
Packit |
89ede9 |
return vpl;
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
static inline int
|
|
Packit |
89ede9 |
vplist_alloc( vplist *vpl, vplist_index alloc )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
vpl->data = ( void ** ) malloc( sizeof( void * ) * alloc );
|
|
Packit |
89ede9 |
if ( !vpl->data ) return VPLIST_MEMERR;
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
vpl->max = alloc;
|
|
Packit |
89ede9 |
vpl->n = 0;
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
return VPLIST_OK;
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
static inline int
|
|
Packit |
89ede9 |
vplist_realloc( vplist *vpl, vplist_index alloc )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
void **more;
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
more = ( void ** ) realloc( vpl->data, sizeof( void * ) * alloc );
|
|
Packit |
89ede9 |
if ( !more ) return VPLIST_MEMERR;
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
vpl->data = more;
|
|
Packit |
89ede9 |
vpl->max = alloc;
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
return VPLIST_OK;
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
/* vplist_ensure_space( vpl, n, mode )
|
|
Packit |
89ede9 |
*
|
|
Packit |
89ede9 |
* Makes sure that vplist can hold at least n members, allocating memory if required.
|
|
Packit |
89ede9 |
*
|
|
Packit |
89ede9 |
* mode
|
|
Packit |
89ede9 |
* - Can either be VPLIST_DOUBLE_SIZE or VPLIST_EXACT_SIZE.
|
|
Packit |
89ede9 |
* - If VPLIST_EXACT_SIZE and current size < n, size will be exactly n.
|
|
Packit |
89ede9 |
* - If VPLIST_DOUBLE_SIZE and current size < n, size will be doubled (or VPLIST_MINALLOC
|
|
Packit |
89ede9 |
* if the vplist is empty) or n, whichever is bigger.
|
|
Packit |
89ede9 |
*
|
|
Packit |
89ede9 |
* Returns VPLIST_OK or VPLIST_MEMERR.
|
|
Packit |
89ede9 |
*/
|
|
Packit |
89ede9 |
static int
|
|
Packit |
89ede9 |
vplist_ensure_space( vplist *vpl, vplist_index n, unsigned char mode )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
vplist_index alloc = n;
|
|
Packit |
89ede9 |
int status = VPLIST_OK;
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
if ( vpl->max == 0 ) {
|
|
Packit |
89ede9 |
if ( mode == VPLIST_DOUBLE_SIZE && alloc < VPLIST_MINALLOC ) alloc = VPLIST_MINALLOC;
|
|
Packit |
89ede9 |
status = vplist_alloc( vpl, alloc );
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
else if ( vpl->max < n ) {
|
|
Packit |
89ede9 |
if ( mode == VPLIST_DOUBLE_SIZE && alloc < 2 * vpl->max ) alloc = 2 * vpl->max;
|
|
Packit |
89ede9 |
status = vplist_realloc( vpl, alloc );
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
return status;
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
int
|
|
Packit |
89ede9 |
vplist_copy( vplist *to, vplist *from )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
vplist_index i;
|
|
Packit |
89ede9 |
int status;
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
assert( to );
|
|
Packit |
89ede9 |
assert( from );
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
status = vplist_ensure_space( to, from->n, VPLIST_EXACT_SIZE );
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
if ( status == VPLIST_OK ) {
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
for ( i=0; i<from->n; ++i )
|
|
Packit |
89ede9 |
to->data[i] = from->data[i];
|
|
Packit |
89ede9 |
to->n = from->n;
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
return status;
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
int
|
|
Packit |
89ede9 |
vplist_fill( vplist *vpl, vplist_index n, void *v )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
vplist_index i;
|
|
Packit |
89ede9 |
int status;
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
assert( vpl );
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
status = vplist_ensure_space( vpl, n, VPLIST_EXACT_SIZE );
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
if ( status == VPLIST_OK ) {
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
for ( i=0; i
|
|
Packit |
89ede9 |
vpl->data[i] = v;
|
|
Packit |
89ede9 |
vpl->n = n;
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
return status;
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
int
|
|
Packit |
89ede9 |
vplist_add( vplist *vpl, void *v )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
int status;
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
assert( vpl );
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
status = vplist_ensure_space( vpl, vpl->n + 1, VPLIST_DOUBLE_SIZE );
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
if ( status == VPLIST_OK ) {
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
vpl->data[vpl->n] = v;
|
|
Packit |
89ede9 |
vpl->n++;
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
return status;
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
int
|
|
Packit |
89ede9 |
vplist_insert_list( vplist *vpl, vplist_index pos, vplist *add )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
vplist_index i;
|
|
Packit |
89ede9 |
int status;
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
assert( vpl );
|
|
Packit |
89ede9 |
assert( add );
|
|
Packit |
89ede9 |
assert( pos <= vpl->n );
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
/* nothing to do here */
|
|
Packit |
89ede9 |
if ( add->n < 1 ) return VPLIST_OK;
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
status = vplist_ensure_space( vpl, vpl->n + add->n, VPLIST_DOUBLE_SIZE );
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
if ( status == VPLIST_OK ) {
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
for ( i=vpl->n-1; i>=pos; --i )
|
|
Packit |
89ede9 |
vpl->data[i+add->n] = vpl->data[i];
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
for ( i=0; i<add->n; ++i )
|
|
Packit |
89ede9 |
vpl->data[pos+i] = add->data[i];
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
vpl->n += add->n;
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
return status;
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
int
|
|
Packit |
89ede9 |
vplist_append( vplist *vpl, vplist *add )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
vplist_index i;
|
|
Packit |
89ede9 |
int status;
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
assert( vpl );
|
|
Packit |
89ede9 |
assert( add );
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
status = vplist_ensure_space( vpl, vpl->n + add->n, VPLIST_DOUBLE_SIZE );
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
if ( status == VPLIST_OK ) {
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
for ( i=0; i<add->n; ++i )
|
|
Packit |
89ede9 |
vpl->data[ vpl->n + i ] = add->data[i];
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
vpl->n += add->n;
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
return status;
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
static void
|
|
Packit |
89ede9 |
vplist_freemembers( vplist *vpl, vplist_ptrfree vpf )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
vplist_index i;
|
|
Packit |
89ede9 |
void *v;
|
|
Packit |
89ede9 |
for ( i=0; i<vpl->n; ++i ) {
|
|
Packit |
89ede9 |
v = vplist_get( vpl, i );
|
|
Packit |
89ede9 |
if ( v ) (*vpf)( v );
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
void
|
|
Packit |
89ede9 |
vplist_emptyfn( vplist *vpl, vplist_ptrfree vpf )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
assert( vpl );
|
|
Packit |
89ede9 |
if ( vpf ) vplist_freemembers( vpl, vpf );
|
|
Packit |
89ede9 |
vpl->n = 0;
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
void
|
|
Packit |
89ede9 |
vplist_empty( vplist *vpl )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
vplist_emptyfn( vpl, NULL );
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
void
|
|
Packit |
89ede9 |
vplist_freefn( vplist *vpl, vplist_ptrfree vpf )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
assert( vpl );
|
|
Packit |
89ede9 |
if ( vpf ) vplist_freemembers( vpl, vpf );
|
|
Packit |
89ede9 |
if ( vpl->data ) free( vpl->data );
|
|
Packit |
89ede9 |
vplist_init( vpl );
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
void
|
|
Packit |
89ede9 |
vplist_free( vplist *vpl )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
vplist_freefn( vpl, NULL );
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
void
|
|
Packit |
89ede9 |
vplist_deletefn( vplist **vpl, vplist_ptrfree vpf )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
vplist_freefn( *vpl, vpf );
|
|
Packit |
89ede9 |
free( *vpl );
|
|
Packit |
89ede9 |
*vpl = NULL;
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
void
|
|
Packit |
89ede9 |
vplist_delete( vplist **vpl )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
vplist_deletefn( vpl, NULL );
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
static inline int
|
|
Packit |
89ede9 |
vplist_validindex( vplist *vpl, vplist_index n )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
if ( n < 0 || n >= vpl->n ) return 0;
|
|
Packit |
89ede9 |
return 1;
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
void *
|
|
Packit |
89ede9 |
vplist_get( vplist *vpl, vplist_index n )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
assert( vpl );
|
|
Packit |
89ede9 |
if ( !vplist_validindex( vpl, n ) ) return NULL;
|
|
Packit |
89ede9 |
return vpl->data[ n ];
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
void
|
|
Packit |
89ede9 |
vplist_set( vplist *vpl, vplist_index n, void *v )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
assert( vpl );
|
|
Packit |
89ede9 |
assert( vplist_validindex( vpl, n ) );
|
|
Packit |
89ede9 |
vpl->data[ n ] = v;
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
int
|
|
Packit |
89ede9 |
vplist_find( vplist *vpl, void *v )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
vplist_index i;
|
|
Packit |
89ede9 |
assert( vpl );
|
|
Packit |
89ede9 |
for ( i=0; i<vpl->n; ++i )
|
|
Packit |
89ede9 |
if ( vpl->data[i]==v ) return i;
|
|
Packit |
89ede9 |
return -1;
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
void
|
|
Packit |
89ede9 |
vplist_swap( vplist *vpl, vplist_index n1, vplist_index n2 )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
void *tmp;
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
assert( vpl );
|
|
Packit |
89ede9 |
assert( vplist_validindex( vpl, n1 ) );
|
|
Packit |
89ede9 |
assert( vplist_validindex( vpl, n2 ) );
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
tmp = vpl->data[n1];
|
|
Packit |
89ede9 |
vpl->data[n1] = vpl->data[n2];
|
|
Packit |
89ede9 |
vpl->data[n2] = tmp;
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
int
|
|
Packit |
89ede9 |
vplist_removefn( vplist *vpl, vplist_index n, vplist_ptrfree vpf )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
vplist_index i;
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
assert( vpl );
|
|
Packit |
89ede9 |
assert( vplist_validindex( vpl, n ) );
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
if ( vpf ) (*vpf)( vplist_get( vpl, n ) );
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
for ( i=n+1; i<vpl->n; ++i )
|
|
Packit |
89ede9 |
vpl->data[ i-1 ] = vpl->data[ i ];
|
|
Packit |
89ede9 |
vpl->n -= 1;
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
return 1;
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
int
|
|
Packit |
89ede9 |
vplist_remove( vplist *vpl, vplist_index n )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
return vplist_removefn( vpl, n, NULL );
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
int
|
|
Packit |
89ede9 |
vplist_removevpfn( vplist *vpl, void *v, vplist_ptrfree vpf )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
vplist_index n;
|
|
Packit |
89ede9 |
int count = 0;
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
assert( vpl );
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
do {
|
|
Packit |
89ede9 |
n = vplist_find( vpl, v );
|
|
Packit |
89ede9 |
if ( vplist_found( vpl, n ) ) {
|
|
Packit |
89ede9 |
vplist_removefn( vpl, n, vpf );
|
|
Packit |
89ede9 |
count++;
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
} while ( vplist_found( vpl, n ) );
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
return count;
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
int
|
|
Packit |
89ede9 |
vplist_removevp( vplist *vpl, void *v )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
return vplist_removevpfn( vpl, v, NULL );
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
void
|
|
Packit |
89ede9 |
vplist_remove_rangefn( vplist *vpl, vplist_index start, vplist_index endplusone, vplist_ptrfree vpf )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
vplist_index i, n;
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
assert( endplusone <= vpl->n );
|
|
Packit |
89ede9 |
assert( endplusone > start );
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
n = endplusone - start;
|
|
Packit |
89ede9 |
if ( vpf ) {
|
|
Packit |
89ede9 |
for ( i=start; i
|
|
Packit |
89ede9 |
(*vpf)( vplist_get( vpl, i ) );
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
for ( i=endplusone; i<vpl->n; ++i ) {
|
|
Packit |
89ede9 |
vpl->data[i-n] = vpl->data[i];
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
vpl->n -= n;
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
void
|
|
Packit |
89ede9 |
vplist_remove_range( vplist *vpl, vplist_index start, vplist_index endplusone )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
vplist_remove_rangefn( vpl, start, endplusone, NULL );
|
|
Packit |
89ede9 |
}
|