yc_chkarray.c

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

{
    if( uninit_self == src )
        return -1;
    {
        size_t len = chkarr_itr_diff( &(src->m_finish), &(src->m_start) );

        *uninit_self = *src;
        chkarr_init_array_and_iterator( uninit_self );

        if( false == chkarr_insert_append(uninit_self, 0, len) )
            return 0;

        chkarr_copy_range( uninit_self, uninit_self->m_start, src->m_start,
                           len, uninit_self->m_elmt_init_copy, NULL );
    }

    return 1;
}

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

int chkarr_assign_copy( chkarray* self, const chkarray* src )
{
    if( self == src || self->m_element_size != src->m_element_size
        || self->m_chunk_size != src->m_chunk_size
        || self->m_elmt_init_copy != src->m_elmt_init_copy
        || self->m_elmt_assign_copy != src->m_elmt_assign_copy )
        return -1;
    else
    {
        size_t dst_len = chkarr_itr_diff( &(self->m_finish), &(self->m_start) );
        size_t src_len = chkarr_itr_diff( &(src->m_finish), &(src->m_start) );

        chkarr_iterator mid = chkarr_copy_range( self, self->m_start,
                        src->m_start, dst_len < src_len ? dst_len : src_len,
                        self->m_elmt_assign_copy, NULL );

        if( dst_len > src_len )
            chkarr_erase_range( self, chkarr_itr_diff( &mid, &(self->m_start) ),
                                dst_len );
        else if( dst_len < src_len )
        {
            chkarr_iterator src_mid = chkarr_itr_add( src->m_start, dst_len );

            for( ; dst_len < src_len; ++dst_len )
            {
                if( false == chkarr_push_back(self, src_mid.current) )
                    return 0;
                ITR_INC( src_mid );
            }
        }
    }

    return 1;
}

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

void chkarr_init_move( chkarray* uninit_self, chkarray* src )
{
    if( uninit_self != src )
    {
        *uninit_self = *src;
        chkarr_init_array_and_iterator( src );
    }
}

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

void chkarr_assign_move( chkarray* self, chkarray* src )
{
    if( self != src )
    {
        chkarray temp = *self;
        *self = *src;
        *src = temp;
    }
}

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

void chkarr_reverse( chkarray* self )
{
    size_t len = chkarr_itr_diff( &(self->m_finish), &(self->m_start) );

    if( len > 1 )
    {
        size_t swap_count = len / 2;
        chkarr_iterator front = self->m_start;
        chkarr_iterator back = chkarr_itr_sub( self->m_finish, 1 );

#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 )
        {
            while( swap_count > 0 )
            {
                --swap_count;
                self->m_elmt_assign_move( buf, front.current );
                self->m_elmt_assign_move( front.current, back.current );
                self->m_elmt_assign_move( back.current, buf );
                ITR_INC( front );
                ITR_DEC( back );
            }
        }
        else
        {
            while( swap_count > 0 )
            {
                --swap_count;
                self->m_elmt_assign_copy( buf, front.current );
                self->m_elmt_assign_copy( front.current, back.current );
                self->m_elmt_assign_copy( back.current, buf );
                ITR_INC( front );
                ITR_DEC( back );
            }
        }

        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
    }
}

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

chkarr_iterator chkarr_erase_pos( chkarray* self, size_t index )
{
    chkarr_iterator pos;
    size_t len = chkarr_itr_diff( &(self->m_finish), &(self->m_start) );

    if( index >= len )
        return self->m_finish;

    pos = chkarr_itr_add( self->m_start, index );

    if( index < len / 2 )  /* 移动 [m_start, index) */
    {
        chkarr_rcopy_range( self, chkarr_itr_add(pos, 1), pos, index,
                            self->m_elmt_assign_copy,
                            self->m_elmt_assign_move );

        chkarr_pop_front( self );
    }
    else  /* 移动 [index, m_finish) */
    {
        chkarr_copy_range( self, pos, chkarr_itr_add(pos, 1),
                           len - index - 1, self->m_elmt_assign_copy,
                           self->m_elmt_assign_move );

        chkarr_pop_back( self );
    }

    return chkarr_itr_add( self->m_start, index );
}

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

chkarr_iterator chkarr_erase_range( chkarray* self,
                                    size_t first_index,
                                    size_t last_index )
{
    array_t chk;
    chkarr_iterator first, last;
    size_t erase_elmts;
    size_t len = chkarr_itr_diff( &(self->m_finish), &(self->m_start) );

    if( first_index >= last_index || first_index >= len )
        return self->m_finish;

    if( last_index > len )
        last_index = len;

    erase_elmts = last_index - first_index;
    first = chkarr_itr_add( self->m_start, first_index );
    last = chkarr_itr_add( self->m_start, last_index );

    /* 判断是否可以直接删除 chunk */
    if( first.current == first.first && last.current == last.first )
        return chkarr_erase_chunk( self, first_index, last_index );

    if( first_index < (len - erase_elmts) / 2 )  /* 移动 [m_start, first) */
    {
        chkarr_iterator new_start = chkarr_itr_add( self->m_start,
                                                    erase_elmts );

        /* [start, first) to [last - first, last) */
        chkarr_rcopy_range( self, last, first, first_index,
                            self->m_elmt_assign_copy,
                            self->m_elmt_assign_move );

        if( self->m_elmt_destroy )
        {
            chkarr_iterator erase_end = new_start;
            for( ; erase_elmts > 0; --erase_elmts )
            {
                ITR_DEC( erase_end );
                self->m_elmt_destroy( erase_end.current );
            }
        }

        for( chk = self->m_start.map; chk < new_start.map; ++chk )
        {
            self->m_dealloc( *chk, self->m_chunk_size );
            *chk = NULL;
        }

        self->m_start = new_start;
    }
    else  /* 移动 [last, m_finish) */
    {
        size_t after = len - last_index;
        chkarr_iterator new_finish = chkarr_itr_sub( self->m_finish,
                                                     erase_elmts );

        /* [last, finish) to [first, first + after) */
        chkarr_copy_range( self, first, last, after,
                           self->m_elmt_assign_copy,
                           self->m_elmt_assign_move );

        if( self->m_elmt_destroy )
        {
            chkarr_iterator erase_end = self->m_finish;
            for( ; erase_elmts > 0; --erase_elmts )
            {
                ITR_DEC( erase_end );
                self->m_elmt_destroy( erase_end.current );
            }
        }

        for( chk = self->m_finish.map; chk > new_finish.map; --chk )
        {
            self->m_dealloc( *chk, self->m_chunk_size );
            *chk = NULL;
        }

        self->m_finish = new_finish;
    }

    return chkarr_itr_add( self->m_start, first_index );
}

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

bool chkarr_insert_value( chkarray* self,
                          size_t index,
                          const void* value,
                          size_t count )
{
    chkarr_iterator pos;
    size_t old_len = chkarr_itr_diff( &(self->m_finish), &(self->m_start) );

    if( index > old_len || old_len > chkarr_max_size() - count )
        return false;

    pos = chkarr_itr_add( self->m_start, index );

    /* 判断是否可以整块 chunk 进行移动 */
    if( pos.current == pos.first
        && count % (self->m_chunk_size / self->m_element_size) == 0 )
    {
        if( false == chkarr_insert_chunk(self, index, count) )
            return false;

        /* 重新计算 pos */
        pos = chkarr_itr_add( self->m_start, index );

        if( !value )
        {
            if( self->m_elmt_init )
                chkarr_init_range( self, &pos, count );
        }
        else
            chkarr_fill_value( self, &pos, value, count,
                               self->m_elmt_init_copy );

        return true;
    }

    /* 移动元素 */
    if( false == chkarr_insert_append(self, index, count) )
        return false;

    if( index < (old_len / 2) )  /* 在前半区间插入元素 */
    {
        chkarr_iterator insert_start;

        pos = chkarr_itr_add( self->m_start, index + count );
        insert_start = chkarr_itr_sub( pos, count );

        if( !value )
        {
            if( self->m_elmt_init && index < count )
                chkarr_init_range( self, &insert_start, count - index );
        }
        else
        {
            if( count <= index )
            {
                chkarr_fill_value( self, &insert_start, value, count,
                                   self->m_elmt_assign_copy );
            }
            else
            {
                chkarr_fill_value( self, &insert_start, value, count - index,
                                   self->m_elmt_init_copy );

                chkarr_fill_value( self, &insert_start, value, index,
                                   self->m_elmt_assign_copy );
            }
        }
    }
    else  /* 在后半区间插入元素 */
    {
        size_t after = old_len - index;
        pos = chkarr_itr_sub( self->m_finish, after + count );

        if( !value )
        {
            if( self->m_elmt_init && after < count )
            {
                chkarr_itr_inc_n( &pos, after );
                chkarr_init_range( self, &pos, count - after );
            }
        }
        else
        {
            if( count <= after )
            {
                chkarr_fill_value( self, &pos, value, count,
                                   self->m_elmt_assign_copy );
            }
            else
            {
                chkarr_fill_value( self, &pos, value, after,
                                   self->m_elmt_assign_copy );

                chkarr_fill_value( self, &pos, value, count - after,
                                   self->m_elmt_init_copy );
            }
        }
    }

    return true;
}

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

bool chkarr_insert_array( chkarray* self,
                          size_t index,
                          const void* src,
                          size_t count )
{
    chkarr_iterator pos;
    size_t old_len = chkarr_itr_diff( &(self->m_finish), &(self->m_start) );

    if( index > old_len || old_len > chkarr_max_size() - count )
        return false;

    pos = chkarr_itr_add( self->m_start, index );

    /* 判断是否可以整块 chunk 进行移动 */
    if( pos.current == pos.first
        && count % (self->m_chunk_size / self->m_element_size) == 0 )
    {
        if( false == chkarr_insert_chunk(self, index, count) )
            return false;

        /* 重新计算 pos */
        pos = chkarr_itr_add( self->m_start, index );

        if( !src )
        {
            if( self->m_elmt_init )
                chkarr_init_range( self, &pos, count );
        }
        else
            chkarr_copy_array( self, &pos, src, count, self->m_elmt_init_copy );

        return true;
    }

    /* 移动元素 */