root/trunk/thune/array.c

/*============================================================================
    Urlan Interpreter
    Copyright (C) 2005-2006  Karl Robillard

    This library is free software; you can redistribute it and/or
    modify it under the terms of the GNU Lesser General Public
    License as published by the Free Software Foundation; either
    version 2.1 of the License, or (at your option) any later version.

    This library is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
    Lesser General Public License for more details.

    You should have received a copy of the GNU Lesser General Public
    License along with this library; if not, write to the Free Software
    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
===========================================================================*/


#include "os.h"
#include "urlan.h"


void ur_arrayInit( UArray* arr, int elemSize, int elemCount )
{
    long size = elemSize * elemCount;
    if( size )
    {
        arr->ptr.v = memAlloc( size );
        if( arr->ptr.v )
            arr->avail = elemCount;
        else
            arr->avail = 0;
    }
    else
    {
        arr->ptr.v = 0;
        arr->avail = 0;
    }
    arr->used  = 0;
}


/**
  Frees the memory pointed to by arr->ptr.
*/
void ur_arrayFree( UArray* arr )
{
    assert( arr );

    if( arr->ptr.v )
    {
        memFree( arr->ptr.v );
        arr->ptr.v = 0;
        arr->avail = 0;
        arr->used  = 0;
    }
}


/**
  Allocates enough memory to hold elemCount elements.
  arr->used is not changed.
*/
void ur_arrayReserve( UArray* arr, int elemSize, int elemCount )
{
    assert( arr );
    assert( arr->avail > -1 );

    if( elemCount > arr->avail )
    {
        int count;
        void* buf;

        /* Double the buffer size (unless that is not big enough). */
        count = arr->avail * 2;
        if( count < elemCount )
        {
            /* Using a minimum size of 4 rather than 8 results in ~10% less
               wasted memory.  Using 2 results in ~13% less.
               Waste seems to run 100%-150% of used memory.
             */
            if( elemSize >= 16 )
                count = (elemCount < 4) ? 4 : elemCount;
            else
                count = (elemCount < 8) ? 8 : elemCount;
        }

#if 1
        buf = memRealloc( arr->ptr.v, elemSize * count );
        assert( buf );
        //printf( "realloc %d\n", buf == arr->ptr.v );
        arr->ptr.v = buf;
        arr->avail = count;
#else
        buf = memAlloc( elemSize * count );
        assert( buf );
        if( buf )
        {
            if( arr->ptr.v )
            {
                if( arr->used ) 
                    memCpy( buf, arr->ptr.v, elemSize * arr->used );
                memFree( arr->ptr.v );
            }
            arr->ptr.v = buf;
            arr->avail = count;
        }
#endif
    }
}


/**
  Remove count elements from the array starting at index.
*/
void ur_arrayErase( UArray* arr, int elemSize, int index, int count )
{
    assert( arr );
    assert( index < arr->used );

    if( (index + count) >= arr->used )
    {
        arr->used = index;
        return;
    }

    if( elemSize == 1 )
    {
        char* buf;
        char* src;
        char* end;

        buf = arr->ptr.c + index;
        src = buf + count;
        end = arr->ptr.c + arr->used;

        while( src != end )
            *buf++ = *src++;
    }
    else if( elemSize == 16 )
    {
#if __WORDSIZE == 64
        uint64_t* buf;
        uint64_t* src;
        uint64_t* end;

        buf = ((uint64_t*) arr->ptr.i) + (index * 2);
        src = buf + (count * 2);
        end = ((uint64_t*) arr->ptr.i) + (arr->used * 2);

        while( src != end )
        {
            *buf++ = *src++;
            *buf++ = *src++;
        }
#else
        uint32_t* buf;
        uint32_t* src;
        uint32_t* end;

        buf = ((uint32_t*) arr->ptr.i) + (index * 4);
        src = buf + (count * 4);
        end = ((uint32_t*) arr->ptr.i) + (arr->used * 4);

        while( src != end )
        {
            *buf++ = *src++;
            *buf++ = *src++;
            *buf++ = *src++;
            *buf++ = *src++;
        }
#endif
    }
    else
    {
        char* buf; 
        buf = arr->ptr.c + (elemSize * index);
        memMove( buf, buf + (elemSize * count),
                 elemSize * (arr->used - index - count) );
    }

    arr->used -= count;
}


/**
  Create space in the array for count elements starting at index.
  The memory in the new space is uninitialized.
*/
void ur_arrayExpand( UArray* arr, int elemSize, int index, int count )
{
    ur_arrayReserve( arr, elemSize, arr->used + count );

    if( index < arr->used )
    {
        char* buf = arr->ptr.c + (elemSize * index);
        memMove( buf + (elemSize * count), buf,
                 elemSize * (arr->used - index) );
    }

    arr->used += count;
}


/*EOF*/