yc_chkarray.c

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

        new_start = new_array + (new_array_len - new_chunks) / 2
                    + ( true == at_front ? add_chunks : 0 );

        if( self->m_chunk_array )
        {
            ylib_memcopy( new_start, self->m_start.map,
                          sizeof(array_t) * old_chunks );
            self->m_dealloc( self->m_chunk_array,
                             sizeof(array_t) * self->m_array_len );
        }
        else
        {
            /* 如果 m_chunk_array 为空，则必须先分配一块 chunk
             * 否则后面的调用会出错 */
            *new_start = self->m_alloc( self->m_chunk_size );
            if( !(*new_start) )
            {
                self->m_dealloc( new_array, sizeof(array_t) * new_array_len );
                return false;
            }
            self->m_start.current = *new_start;
            self->m_finish.current = *new_start;
        }

        self->m_chunk_array = new_array;
        self->m_array_len = new_array_len;
    }

    chkarr_itr_set_chunk( &(self->m_start), new_start );
    chkarr_itr_set_chunk( &(self->m_finish), new_start + old_chunks - 1 );

    return true;
}

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

static bool chkarr_append_elements( chkarray* self,
                                    size_t count,
                                    bool at_front )
{
    size_t space = 0;

    if( self->m_chunk_array )
    {
        if( true == at_front )
            space = ( (ylib_byte_t*)(self->m_start.current)
                      - (ylib_byte_t*)(self->m_start.first) )
                    / self->m_element_size;
        else
            space = ( (ylib_byte_t*)(self->m_finish.last)
                      - (ylib_byte_t*)(self->m_finish.current) )
                    / self->m_element_size - 1;
    }

    if( space < count )
    {
        size_t chunk_elmts = self->m_chunk_size / self->m_element_size;
        bool empty = ( self->m_chunk_array ? false : true );
        size_t i, add_chunks;

        count -= space;
        add_chunks = 1 + (count - 1) / chunk_elmts;

        if( false == chkarr_reserve_array(self, add_chunks, at_front) )
            return false;

        /* 如果 m_chunk_array 为空并且 count % chunk_elmts != 0，
         * 那么表示 m_finish 在最后一块 chunk 内，没有必要再多分配一块 chunk，
         * 所以将 add_chunks 减 1 */
        if( true == empty && count % chunk_elmts > 0 )
            --add_chunks;

        if( true == at_front )
        {
            for( i = 1; i <= add_chunks; ++i )
            {
                *(self->m_start.map - i) = self->m_alloc(self->m_chunk_size);

                if( !(*(self->m_start.map - i)) )
                {
                    for( --i; i >= 1; --i )
                    {
                        self->m_dealloc( *(self->m_start.map - i),
                                         self->m_chunk_size );
                        *(self->m_start.map - i) = NULL;
                    }

                    return false;
                }
            }
        }
        else
        {
            for( i = 1; i <= add_chunks; ++i )
            {
                *(self->m_finish.map + i) = self->m_alloc(self->m_chunk_size);

                if( !(*(self->m_finish.map + i)) )
                {
                    for( --i; i >= 1; --i )
                    {
                        self->m_dealloc( *(self->m_finish.map + i),
                                         self->m_chunk_size );
                        *(self->m_finish.map + i) = NULL;
                    }

                    return false;
                }
            }
        }
    }

    return true;
}

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

static bool chkarr_insert_append( chkarray* self,
                                  size_t index,
                                  size_t count )
{
    size_t old_len = chkarr_itr_diff( &(self->m_finish), &(self->m_start) );
    chkarr_iterator pos = chkarr_itr_add( self->m_start, index );

    if( index < (old_len / 2) )  /* move [m_start, index) */
    {
        chkarr_iterator old_start, new_start;

        if( false == chkarr_append_elements(self, count, true) )
            return false;

        old_start = self->m_start;
        new_start = chkarr_itr_sub( self->m_start, count );
        pos = chkarr_itr_add( self->m_start, index );
        self->m_start = new_start;

        /* [old_start, pos) to [new_start, new_start + index) */
        if( index <= count )
        {
            chkarr_copy_range( self, new_start, old_start, index,
                               self->m_elmt_init_copy,
                               self->m_elmt_init_move );
        }
        else
        {
            /* [old_start, old_start + count) to [new_start, old_start) */
            new_start = chkarr_copy_range( self, new_start, old_start,
                                           count, self->m_elmt_init_copy,
                                           self->m_elmt_init_move );

            /* [old_start + count, pos) to
               [old_start, old_start + (index - count)) */
            chkarr_itr_inc_n( &old_start, count );
            chkarr_copy_range( self, new_start, old_start,
                               index - count, self->m_elmt_assign_copy,
                               self->m_elmt_assign_move );
        }
    }
    else  /* move [index, m_finish) */
    {
        size_t after = old_len - index;
        chkarr_iterator old_finish, new_finish;

        if( false == chkarr_append_elements(self, count, false) )
            return false;

        old_finish = self->m_finish;
        new_finish = chkarr_itr_add( self->m_finish, count );
        pos = chkarr_itr_add( self->m_start, index );
        self->m_finish = new_finish;

        if( after <= count )
        {
            /* [pos, old_finish) to [new_finish - after, new_finish) */
            chkarr_rcopy_range( self, new_finish, old_finish, after,
                                self->m_elmt_init_copy,
                                self->m_elmt_init_move );
        }
        else
        {
            /* [old_finish - insert, old_finish) to [old_finish, new_finish) */
            new_finish = chkarr_rcopy_range( self, new_finish,
                                             old_finish, count,
                                             self->m_elmt_init_copy,
                                             self->m_elmt_init_move );

            /* [pos, old_finish - count) to
               [old_finish - (after - count), old_finish) */
            chkarr_itr_dec_n( &old_finish, count );
            chkarr_rcopy_range( self, new_finish,
                                old_finish, after - count,
                                self->m_elmt_assign_copy,
                                self->m_elmt_assign_move );
        }
    }

    return true;
}

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

static bool chkarr_insert_chunk( chkarray* self,
                                 size_t index,
                                 size_t count )
{
    bool empty = ( self->m_chunk_array ? false : true );
    chkarr_iterator pos = chkarr_itr_add( self->m_start, index );
    size_t add_chunks = 1 + (count - 1)
                        / ( self->m_chunk_size / self->m_element_size );

    if( pos.map - self->m_start.map
        < ((self->m_finish.map - self->m_start.map) / 2) )
    {
        /* 在前面插入 chunks */
        size_t before_chunks = pos.map - self->m_start.map;

        if( false == chkarr_append_elements(self, count, true) )
            return false;

        if( true == empty )
        {
            self->m_finish = chkarr_itr_add( self->m_start, count );
            return true;
        }

        /* [add_chunks, pos - 1] -> [pos - 1, add_chunks] */
        memreverse( self->m_start.map - add_chunks,
                    add_chunks + before_chunks, sizeof(array_t) );

        /* [pos - 1, start] -> [start, pos - 1] */
        memreverse( self->m_start.map - add_chunks,
                    before_chunks, sizeof(array_t) );

        chkarr_itr_set_chunk( &(self->m_start),
                                self->m_start.map - add_chunks );
        self->m_start.current = self->m_start.first;
    }
    else
    {
        size_t index = chkarr_itr_diff( &pos, &(self->m_start) );
        size_t old_len = chkarr_itr_diff( &(self->m_finish), &(self->m_start) );
        size_t after_chunks = self->m_finish.map - pos.map + 1;

        if( false == chkarr_append_elements(self, count, false) )
            return false;

        if( true == empty )
        {
            self->m_finish = chkarr_itr_add( self->m_start, count );
            return true;
        }

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

        /* [pos, add_chunks] -> [add_chunks, pos] */
        memreverse( pos.map, add_chunks + after_chunks, sizeof(array_t) );

        /* [finish, pos] -> [pos, finish] */
        memreverse( pos.map + add_chunks, after_chunks, sizeof(array_t) );

        self->m_finish.map += add_chunks;

        if( 0 == index )
            self->m_start = chkarr_itr_sub(self->m_finish, old_len + count);
    }

    return true;
}

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

static chkarr_iterator chkarr_erase_chunk( chkarray* self,
                                           size_t first_index,
                                           size_t last_index )
{
    array_t chk;
    chkarr_iterator first = chkarr_itr_add( self->m_start, first_index );
    chkarr_iterator last = chkarr_itr_add( self->m_start, last_index );
    size_t erase_chunks = last.map - first.map;
    size_t erase_elmts = last_index - first_index;
    size_t len = chkarr_itr_diff( &(self->m_finish), &(self->m_start) );

    /* destroy elements */
    if( self->m_elmt_destroy )
    {
        size_t i;
        chkarr_iterator erase_end = last;

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

    for( chk = first.map; chk < last.map; ++chk )
        self->m_dealloc( *chk, self->m_chunk_size );

    if( first_index < (len - erase_elmts) / 2 )  /* 移动前面的 chunks */
    {
        size_t count = first.map - self->m_start.map;
        ylib_memmove( last.map - count, first.map - count,
                      sizeof(array_t) * count );
        ylib_memset( self->m_start.map, 0, erase_chunks * sizeof(array_t) );

        if( first.current == self->m_start.current )
            self->m_start = last;
        else
            self->m_start.map += erase_chunks;
    }
    else  /* 移动后面的 chunks */
    {
        ylib_memcopy( first.map, last.map,
                sizeof(array_t) * (self->m_finish.map - last.map + 1) );

        self->m_finish.map -= erase_chunks;

        ylib_memset( self->m_finish.map + 1, 0,
                     erase_chunks * sizeof(array_t) );

        if( first.current == self->m_start.current )
        {
            chkarr_itr_set_chunk( &(self->m_start), self->m_start.map );
            self->m_start.current = self->m_start.first;
        }
    }

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

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

static void chkarr_init_array_and_iterator( chkarray* self )
{
    self->m_chunk_array = NULL;
    self->m_array_len = 0;
    ylib_memset( &(self->m_start), 0, sizeof(chkarr_iterator) );
    ylib_memset( &(self->m_finish), 0, sizeof(chkarr_iterator) );
    self->m_start.element_size = self->m_element_size;
    self->m_finish.element_size = self->m_element_size;
    self->m_start.chunk_size = self->m_chunk_size;
    self->m_finish.chunk_size = self->m_chunk_size;
}

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

void chkarr_init( chkarray* uninit_self,
                  size_t element_size,
                  size_t chunk_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_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;

    uninit_self->m_chunk_size = ( chunk_size < 1 ? CHKARR_DEFAULT_CHUNK_SIZE
                                                 : chunk_size );
    if( uninit_self->m_chunk_size < element_size )
        uninit_self->m_chunk_size = element_size;

    chkarr_init_array_and_iterator( uninit_self );
}

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

void chkarr_destroy( chkarray* self )
{
    if( self->m_chunk_array )
    {
        chkarr_erase_range( self, 0, chkarr_itr_diff( &(self->m_finish),
                                                      &(self->m_start) ) );
        self->m_dealloc( *(self->m_start.map), self->m_chunk_size );
        self->m_dealloc( self->m_chunk_array,
                         sizeof(array_t) * self->m_array_len );
    }

    chkarr_init_array_and_iterator( self );
}

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

int chkarr_init_copy( chkarray* uninit_self, const chkarray* src )