yc_dyrscarr.c

一个类STL的多平台可移植的算法容器库,主要用于嵌入式系统编程时的内存管理等方面

/*
 * The young Library
 * Copyright (c) 2005 by Yang Huan(杨桓)

 * Permission to use, copy, modify, distribute and sell this software for any
 * purpose is hereby granted without fee, provided that the above copyright
 * notice appear in all copies and that both that copyright notice and this
 * permission notice appear in supporting documentation.
 * The author make no representations about the suitability of this software
 * for any purpose. It is provided "as is" without express or implied warranty.
 */

/******************************************************************************/
/******************************************************************************/
#include "yc_memalgo.h"
#include "yc_rscalgo.h"
#include "yc_dyrscarr.h"

#ifdef __cplusplus
    namespace youngc {  extern "C" {
#endif
/******************************************************************************/
/******************************************************************************/

enum DYRSCARR_CONSTANT
{
    DYRSCARR_ALIGN_SIZE = sizeof(long) * 16
};

typedef enum
{
    FAILURE = 0,
    MORE = 1,
    LESS = 2,
    REALLOC = 3
}  append_info;

#define POS( PARR, index ) \
        ( (ylib_byte_t*)((PARR)->m_start) + (index) * (PARR)->m_element_size )

#define LENGTH( PARR )                       \
        ( ( (ylib_byte_t*)((PARR)->m_finish) \
            - (ylib_byte_t*)((PARR)->m_start) ) / (PARR)->m_element_size )

#define CAPACITY( PARR )                     \
        ( ( (ylib_byte_t*)((PARR)->m_utmost) \
            - (ylib_byte_t*)((PARR)->m_start) ) / (PARR)->m_element_size )

#define LEN_SIZE( PARR ) \
        ( (ylib_byte_t*)((PARR)->m_finish) - (ylib_byte_t*)((PARR)->m_start) )

#define CAPA_SIZE( PARR ) \
        ( (ylib_byte_t*)((PARR)->m_utmost) - (ylib_byte_t*)((PARR)->m_start) )

/******************************************************************************/

static size_t dyrscarr_alloc_size( const dyrscarray* self, size_t len )
{
    size_t alloc_size = DYRSCARR_ALIGN_SIZE;
    size_t request_size = len * self->m_element_size;

    while( alloc_size < request_size )
        alloc_size *= 2;

    return alloc_size;
}

/******************************************************************************/

/*
 * 返回 LESS:    index 后的已初始化空间 < new_count
 * 返回 MORE:    index 后的已初始化空间 >= new_count
 * 返回 REALLOC: 重新分配了存储空间并且执行成功
 * 返回 FAILURE: 函数运行出错
 */
static append_info dymemarr_memory_reserve( dyrscarray* self,
                                            size_t index,
                                            size_t old_count,
                                            size_t new_count )
{
    append_info ret = MORE;
    size_t old_len = LENGTH( self );
    size_t new_len = old_len - old_count + new_count;
    size_t keep_len = old_len - index - old_count;

    if( CAPACITY(self) < new_len )
    {
        size_t new_size = dyrscarr_alloc_size( self, new_len );
        ylib_byte_t* new_data = (ylib_byte_t*)( self->m_alloc( new_size ) );

        if( !new_data )
            return FAILURE;

        if( self->m_elmt_init_move )
        {
            /* [old_data, old_data + insert_index) to
               [new_data, new_data + index) */
            rscmove( new_data, self->m_start, index,
                     self->m_element_size, self->m_element_size,
                     self->m_elmt_init_move );

            /* [old_data + index, old_data + old_length) to
               [new_data + index + new_count, new_data + new_length) */
            rscmove( new_data + (index + new_count) * self->m_element_size,
                     POS(self, index + old_count), keep_len,
                     self->m_element_size, self->m_element_size,
                     self->m_elmt_init_move );
        }
        else
        {
            rsccopy( new_data, self->m_start, index,
                     self->m_element_size, self->m_element_size,
                     self->m_elmt_init_copy );

            rsccopy( new_data + (index + new_count) * self->m_element_size,
                     POS(self, index + old_count), keep_len,
                     self->m_element_size, self->m_element_size,
                     self->m_elmt_init_copy );
        }

        dyrscarr_destroy( self );

        self->m_start = new_data;
        self->m_utmost = new_data + new_size;
        ret = REALLOC;
    }
    else  /* CAPACITY(self) >= new_len */
    {
        if( new_count < old_count )
        {
            dyrscarr_erase_range( self, index + new_count, index + old_count );
            ret = MORE;
        }
        else if( new_count > old_count )
        {
            size_t inited_space = old_len - index;

            if( inited_space <= new_count )
            {
                /* [index, old_len) to [index + new_count, new_len) */
                if( self->m_elmt_init_move )
                    rscmove( POS(self, index + new_count),
                             POS(self, index), keep_len,
                             self->m_element_size, self->m_element_size,
                             self->m_elmt_init_move );
                else
                    rsccopy( POS(self, index + new_count),
                             POS(self, index), keep_len,
                             self->m_element_size, self->m_element_size,
                             self->m_elmt_init_copy );

                ret = inited_space < new_count ? LESS : MORE;
            }
            else
            {
                void* mid_pos = POS( self, old_count + (old_len - new_count) );

                /* [mid, old_end) to [old_end, new_len) */
                if( self->m_elmt_init_move )
                    rscmove( self->m_finish, mid_pos, new_count - old_count,
                             self->m_element_size, self->m_element_size,
                             self->m_elmt_init_move );
                else
                    rsccopy( self->m_finish, mid_pos, new_count - old_count,
                             self->m_element_size, self->m_element_size,
                             self->m_elmt_init_copy );

                /* [index, mid) to
                   [old_end - (keep_len - (new_count - old_count)), old_end) */
                if( self->m_elmt_assign_move )
                    rrscmove( self->m_finish, mid_pos,
                              keep_len - (new_count - old_count),
                              self->m_element_size, self->m_element_size,
                              self->m_elmt_assign_move );
                else
                    rrsccopy( self->m_finish, mid_pos,
                              keep_len - (new_count - old_count),
                              self->m_element_size, self->m_element_size,
                              self->m_elmt_assign_copy );

                ret = MORE;
            }
        }
    }

    self->m_finish = POS( self, new_len );
    return ret;
}

/******************************************************************************/

void dyrscarr_init( dyrscarray* uninit_self,
                    size_t element_size,
                    ylib_fp_oper_t elmt_init,
                    ylib_fp_copy_t elmt_init_copy,
                    ylib_fp_copy_t elmt_assign_copy,
                    ylib_fp_move_t elmt_init_move,
                    ylib_fp_move_t elmt_assign_move,
                    ylib_fp_oper_t elmt_destroy,
                    ylib_fp_alloc_t alloc,
                    ylib_fp_dealloc_t dealloc )
{
    uninit_self->m_start = NULL;
    uninit_self->m_finish = NULL;
    uninit_self->m_utmost = NULL;
    uninit_self->m_element_size = element_size;
    uninit_self->m_elmt_init = elmt_init;
    uninit_self->m_elmt_init_copy = elmt_init_copy;
    uninit_self->m_elmt_assign_copy = elmt_assign_copy;
    uninit_self->m_elmt_init_move = elmt_init_move;
    uninit_self->m_elmt_assign_move = elmt_assign_move;
    uninit_self->m_elmt_destroy = elmt_destroy;
    uninit_self->m_alloc = alloc;
    uninit_self->m_dealloc = dealloc;
}

/******************************************************************************/

void dyrscarr_reinit( dyrscarray* self,
                      size_t element_size,
                      ylib_fp_oper_t elmt_init,
                      ylib_fp_copy_t elmt_init_copy,
                      ylib_fp_copy_t elmt_assign_copy,
                      ylib_fp_move_t elmt_init_move,
                      ylib_fp_move_t elmt_assign_move,
                      ylib_fp_oper_t elmt_destroy )
{
    if( self->m_start && self->m_elmt_destroy )
        rforeach( self->m_finish, LENGTH(self),
                  self->m_element_size, self->m_elmt_destroy );

    self->m_finish = self->m_start;
    self->m_element_size = element_size;
    self->m_elmt_init = elmt_init;
    self->m_elmt_init_copy = elmt_init_copy;
    self->m_elmt_assign_copy = elmt_assign_copy;
    self->m_elmt_init_move = elmt_init_move;
    self->m_elmt_assign_move = elmt_assign_move;
    self->m_elmt_destroy = elmt_destroy;
}

/******************************************************************************/

void dyrscarr_destroy( dyrscarray* self )
{
    if( self->m_start )
    {
        if( self->m_elmt_destroy )
            rforeach( self->m_finish, LENGTH(self),
                      self->m_element_size, self->m_elmt_destroy );

        self->m_dealloc( self->m_start, CAPA_SIZE(self) );
    }

    self->m_start = NULL;
    self->m_finish = NULL;
    self->m_utmost = NULL;
}

/******************************************************************************/

int dyrscarr_init_copy( dyrscarray* uninit_self, const dyrscarray* src )
{
    if( uninit_self == src )
        return -1;
    else
    {
        if( src->m_start == src->m_finish )
        {
            *uninit_self = *src;
            uninit_self->m_start = NULL;
            uninit_self->m_finish = NULL;
            uninit_self->m_utmost = NULL;
        }
        else
        {
            size_t len = LENGTH( src );
            size_t alloc_size = dyrscarr_alloc_size( src, len );

            *uninit_self = *src;
            uninit_self->m_start = uninit_self->m_alloc( alloc_size );

            if( !(uninit_self->m_start) )
            {
                uninit_self->m_finish = NULL;
                uninit_self->m_utmost = NULL;
                return 0;
            }
            else
            {
                rsccopy( uninit_self->m_start, src->m_start, len,
                         uninit_self->m_element_size, src->m_element_size,
                         uninit_self->m_elmt_init_copy );

                uninit_self->m_finish = (ylib_byte_t*)(uninit_self->m_start)
                                        + LEN_SIZE( src );

                uninit_self->m_utmost = (ylib_byte_t*)(uninit_self->m_start)
                                        + alloc_size;
            }
        }
    }

    return 1;
}

/******************************************************************************/

int dyrscarr_assign_copy( dyrscarray* self, const dyrscarray* src )
{
    if( self == src || self->m_element_size != src->m_element_size
        || self->m_elmt_init_copy != src->m_elmt_init_copy
        || self->m_elmt_assign_copy != src->m_elmt_assign_copy )
        return -1;

    return true == dyrscarr_replace_array( self, 0, LENGTH(self),
                                           src->m_start, LENGTH(src) ) ? 1 : 0;
}

/******************************************************************************/

void dyrscarr_init_move( dyrscarray* uninit_self, dyrscarray* src )
{
    if( uninit_self != src )
    {
        *uninit_self = *src;
        src->m_start = NULL;
        src->m_finish = NULL;
        src->m_utmost = NULL;
    }
}

/******************************************************************************/

void dyrscarr_assign_move( dyrscarray* self, dyrscarray* src )
{
    if( self != src )
    {
        dyrscarray temp = *self;
        *self = *src;
        *src = temp;
    }
}

/******************************************************************************/

bool dyrscarr_reserve( dyrscarray* self, size_t new_capacity )
{
    if( CAPACITY(self) < new_capacity )
    {
        size_t new_size = dyrscarr_alloc_size( self, new_capacity );
        ylib_byte_t* new_data = (ylib_byte_t*)( self->m_alloc( new_size ) );

        if( !new_data )
            return false;
        else
        {
            size_t length = LENGTH( self );
            if( self->m_start )
            {
                if( self->m_elmt_init_move )
                    rscmove( new_data, self->m_start, length,
                             self->m_element_size, self->m_element_size,
                             self->m_elmt_init_move );
                else
                    rsccopy( new_data, self->m_start, length,
                             self->m_element_size, self->m_element_size,
                             self->m_elmt_init_copy );

                dyrscarr_destroy( self );
            }
            self->m_start = new_data;
            self->m_finish = POS( self, length );
            self->m_utmost = (ylib_byte_t*)(self->m_start) + new_size;
        }
    }

    return true;
}

/******************************************************************************/

void dyrscarr_reverse( dyrscarray* self )
{
    size_t len = LENGTH( self );

    if( len < 2 )
        return;
    else if( !(self->m_elmt_assign_copy) && !(self->m_elmt_assign_move) )
        memreverse( self->m_start, len, self->m_element_size );
    else
    {
        size_t swap_count = len / 2;
        ylib_byte_t* front = (ylib_byte_t*)( self->m_start );
        ylib_byte_t* back = (ylib_byte_t*)(self->m_finish)
                            - self->m_element_size;

#ifndef __MACRO_C_YOUNG_LIBRARY_COMPILER_SUPPORT_VARIABLE_LENGTH_ARRAY__
        ylib_byte_t* buf = (ylib_byte_t*)(self->m_alloc(self->m_element_size));
        if( !buf )
            return;
#else
        ylib_byte_t buf[ self->m_element_size ];
#endif

        if( self->m_elmt_init )
            self->m_elmt_init( buf );

        if( self->m_elmt_assign_move )
        {
            for( ; swap_count > 0; --swap_count )
            {
                self->m_elmt_assign_move( buf, front );
                self->m_elmt_assign_move( front, back );
                self->m_elmt_assign_move( back, buf );
                front += ( self->m_element_size );
                back -= ( self->m_element_size );
            }
        }
        else
        {
            for( ; swap_count > 0; --swap_count )
            {
                self->m_elmt_assign_copy( buf, front );
                self->m_elmt_assign_copy( front, back );
                self->m_elmt_assign_copy( back, buf );
                front += ( self->m_element_size );
                back -= ( self->m_element_size );
            }
        }

        if( self->m_elmt_destroy )
            self->m_elmt_destroy( buf );

#ifndef __MACRO_C_YOUNG_LIBRARY_COMPILER_SUPPORT_VARIABLE_LENGTH_ARRAY__
        self->m_dealloc( buf, self->m_element_size );
#endif
    }
}

/******************************************************************************/