yc_chkarray.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_chkarray.h"

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

typedef  void**  array_t;

enum YOUNG_LIBRARY_CHUNK_ARRAY_CONSTANT
{
    CHKARR_INIT_ARRAY_LEN = 32,
    CHKARR_DEFAULT_CHUNK_SIZE = 512
};

#define ITR_INC( ITR )                                                      \
        (ITR).current = (ylib_byte_t*)((ITR).current) + (ITR).element_size; \
        if( (ITR).current == (ITR).last )                                   \
        {                                                                   \
            chkarr_itr_set_chunk( &(ITR), (ITR).map + 1 );                  \
            (ITR).current = (ITR).first;                                    \
        }

#define ITR_DEC( ITR )                                        \
        if( (ITR).current == (ITR).first )                    \
        {                                                     \
            chkarr_itr_set_chunk( &(ITR), (ITR).map - 1 );    \
            (ITR).current = (ITR).last;                       \
        }                                                     \
        (ITR).current = (ylib_byte_t*)((ITR).current) - (ITR).element_size

/******************************************************************************/
/* iterator */
/******************************************************************************/

static void chkarr_itr_set_chunk( chkarr_iterator* pitr, array_t new_chunk )
{
    pitr->map = new_chunk;
    pitr->first = *new_chunk;
    pitr->last = (ylib_byte_t*)(*new_chunk) + pitr->element_size
                 * ( pitr->chunk_size / pitr->element_size );
}

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

ptrdiff_t chkarr_itr_diff( const chkarr_iterator* minuend,
                           const chkarr_iterator* subtrahend )
{
    ptrdiff_t d1, d2;

    if( minuend->current == subtrahend->current )
        return 0;

    d1 = (ylib_byte_t*)(minuend->current) - (ylib_byte_t*)(minuend->first);
    d2 = (ylib_byte_t*)(subtrahend->last) - (ylib_byte_t*)(subtrahend->current);

    return ( minuend->chunk_size / minuend->element_size )
           * (minuend->map - subtrahend->map - 1)
           + (d1 + d2) / minuend->element_size;
}

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

void chkarr_itr_inc( chkarr_iterator* pitr )
{
    pitr->current = (ylib_byte_t*)(pitr->current) + pitr->element_size;

    if( pitr->current == pitr->last )
    {
        chkarr_itr_set_chunk( pitr, pitr->map + 1 );
        pitr->current = pitr->first;
    }
}

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

void chkarr_itr_dec( chkarr_iterator* pitr )
{
    if( pitr->current == pitr->first )
    {
        chkarr_itr_set_chunk( pitr, pitr->map - 1 );
        pitr->current = pitr->last;
    }

    pitr->current = (ylib_byte_t*)(pitr->current) - pitr->element_size;
}

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

void chkarr_itr_inc_n( chkarr_iterator* pitr, ptrdiff_t n )
{
    ptrdiff_t chunk_elmts = pitr->chunk_size / pitr->element_size;
    ptrdiff_t offset_elmts = ( (ylib_byte_t*)(pitr->current)
                               - (ylib_byte_t*)(pitr->first) )
                             / pitr->element_size + n;

    if( offset_elmts >= 0 && offset_elmts < chunk_elmts )
        pitr->current = (ylib_byte_t*)(pitr->current) + n * pitr->element_size;
    else
    {
        ptrdiff_t offset_chunk = 0;

        if( offset_elmts > 0 )
            offset_chunk = offset_elmts / chunk_elmts;
        else
            offset_chunk = -( (-offset_elmts - 1) / chunk_elmts ) - 1;

        chkarr_itr_set_chunk( pitr, pitr->map + offset_chunk );
        pitr->current = (ylib_byte_t*)(pitr->first) + pitr->element_size
                        * ( offset_elmts - offset_chunk * chunk_elmts );
    }
}

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

#ifndef __MACRO_C_YOUNG_LIBRARY_COMPILER_SUPPORT_INLINE_FUNCTION__
    void chkarr_itr_dec_n( chkarr_iterator* pitr, ptrdiff_t n )
    {
        chkarr_itr_inc_n( pitr, -n );
    }

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

    chkarr_iterator chkarr_itr_add( chkarr_iterator itr, ptrdiff_t n )
    {
        chkarr_itr_inc_n( &itr, n );
        return itr;
    }

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

    chkarr_iterator chkarr_itr_sub( chkarr_iterator itr, ptrdiff_t n )
    {
        chkarr_itr_inc_n( &itr, -n );
        return itr;
    }

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

    void* chkarr_itr_deref( chkarr_iterator* itr )
    {
        return itr->current;
    }

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

    bool chkarr_itr_equal( const chkarr_iterator* left,
                           const chkarr_iterator* right )
    {
        return left->current == right->current ? true : false;
    }

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

    bool chkarr_itr_less( const chkarr_iterator* left,
                          const chkarr_iterator* right )
    {
        if( left->map == right->map )
            return left->current < right->current ? true : false;
        else
            return left->map < right->map ? true : false;
    }
#endif

/******************************************************************************/
/* chunk array */
/******************************************************************************/

static void chkarr_init_range( chkarray* self,
                               chkarr_iterator* first,
                               size_t count )
{
    while( count > 0 )
    {
        --count;
        self->m_elmt_init( first->current );
        ITR_INC( *first );
    }
}

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

static void chkarr_fill_value( chkarray* self,
                               chkarr_iterator* pdst,
                               const void* value,
                               size_t count,
                               ylib_fp_copy_t copy_val )
{
    if( copy_val )
    {
        while( count > 0 )
        {
            --count;
            copy_val( pdst->current, value );
            ITR_INC( *pdst );
        }
    }
    else
    {
        size_t elmt_size = self->m_element_size;

        while( count > 0 )
        {
            --count;
            ylib_memcopy( pdst->current, value, elmt_size );
            ITR_INC( *pdst );
        }
    }
}

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

static void chkarr_copy_array( chkarray* self,
                               chkarr_iterator* pdst,
                               const void* src,
                               size_t count,
                               ylib_fp_copy_t copy_val )
{
    const ylib_byte_t* s = (const ylib_byte_t*)src;

    if( copy_val )
    {
        while( count > 0 )
        {
            --count;
            copy_val( pdst->current, s );
            s += self->m_element_size;
            ITR_INC( *pdst );
        }
    }
    else
    {
        while( count > 0 )
        {
            --count;
            ylib_memcopy( pdst->current, s, self->m_element_size );
            s += self->m_element_size;
            ITR_INC( *pdst );
        }
    }
}

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

static chkarr_iterator chkarr_copy_range( chkarray* self,
                                          chkarr_iterator dst_begin,
                                          chkarr_iterator src_begin,
                                          size_t count,
                                          ylib_fp_copy_t copy_val,
                                          ylib_fp_move_t move_val )
{
    if( move_val )
    {
        while( count > 0 )
        {
            --count;
            move_val( dst_begin.current, src_begin.current );
            ITR_INC( dst_begin );
            ITR_INC( src_begin );
        }
    }
    else if( copy_val )
    {
        while( count > 0 )
        {
            --count;
            copy_val( dst_begin.current, src_begin.current );
            ITR_INC( dst_begin );
            ITR_INC( src_begin );
        }
    }
    else
    {
        size_t elmt_size = self->m_element_size;

        while( count > 0 )
        {
            --count;
            ylib_memcopy( dst_begin.current, src_begin.current, elmt_size );
            ITR_INC( dst_begin );
            ITR_INC( src_begin );
        }
    }

    return dst_begin;
}

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

static chkarr_iterator chkarr_rcopy_range( chkarray* self,
                                           chkarr_iterator dst_end,
                                           chkarr_iterator src_end,
                                           size_t count,
                                           ylib_fp_copy_t copy_val,
                                           ylib_fp_move_t move_val )
{
    if( move_val )
    {
        while( count > 0 )
        {
            --count;
            ITR_DEC( dst_end );
            ITR_DEC( src_end );
            move_val( dst_end.current, src_end.current );
        }
    }
    else if( copy_val )
    {
        while( count > 0 )
        {
            --count;
            ITR_DEC( dst_end );
            ITR_DEC( src_end );
            copy_val( dst_end.current, src_end.current );
        }
    }
    else
    {
        size_t elmt_size = self->m_element_size;

        while( count > 0 )
        {
            --count;
            ITR_DEC( dst_end );
            ITR_DEC( src_end );
            ylib_memcopy( dst_end.current, src_end.current, elmt_size );
        }
    }

    return dst_end;
}

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

static bool chkarr_reserve_array( chkarray* self,
                                  size_t add_chunks,
                                  bool at_front )
{
    array_t new_start;
    size_t old_chunks, new_chunks;

    if( false == at_front && add_chunks + 1 <= (self->m_array_len
                        - (self->m_finish.map - self->m_chunk_array)) )
        return true;

    if( true == at_front && add_chunks <= (size_t)(self->m_start.map
                                                   - self->m_chunk_array) )
        return true;

    old_chunks = self->m_finish.map - self->m_start.map + 1;
    new_chunks = old_chunks + add_chunks;

    if( self->m_array_len > new_chunks * 2 )  /* array 剩余空间足够 */
    {
        /* 如果在前面增加 chunks 则必须将已有的 chunks 后移 */
        new_start = self->m_chunk_array + (self->m_array_len - new_chunks) / 2
                    + ( true == at_front ? add_chunks : 0 );

        if( new_start < self->m_start.map )  /* 向前移动已有的 chunks */
            ylib_memcopy( new_start, self->m_start.map,
                          sizeof(array_t) * old_chunks );
        else  /* 向后移动已有的 chunks */
            ylib_memmove( new_start, self->m_start.map,
                          sizeof(array_t) * old_chunks );
    }
    else  /* 空间不够，重新申请空间更大的 array */
    {
        size_t need_chunks = self->m_array_len + 2 + ( self->m_array_len
                             < add_chunks ? add_chunks : self->m_array_len );
        size_t new_array_len = ( CHKARR_INIT_ARRAY_LEN < need_chunks
                                 ? need_chunks : CHKARR_INIT_ARRAY_LEN );

        array_t new_array = (array_t)( self->m_alloc( sizeof(array_t)
                                                      * new_array_len ) );

        if( !new_array )
            return false;

        ylib_memset( new_array, 0, new_array_len * sizeof(array_t) );