cvdatastructs.cpp.svn-base

来自「非结构化路识别」· SVN-BASE 代码 · 共 2,404 行 · 第 1/5 页

    CV_FUNCNAME( "cvGetSeqElem" );

    __BEGIN__;

    if( !seq )
        CV_ERROR( CV_StsNullPtr, "" );
    total = seq->total;
    index += index < 0 ? total : 0;
    index -= index >= total ? total : 0;

    if( (unsigned)index < (unsigned)total )
    {
        block = seq->first;
        while( index >= (count = block->count) )
        {
            index -= count;
            block = block->next;
        }

        if( _block )
            *_block = block;
        elem = block->data + index * seq->elem_size;
    }

    __END__;

    return elem;
}


/* calculates index of sequence element */
CV_IMPL int
cvSeqElemIdx( const CvSeq* seq, const void* _element, CvSeqBlock** _block )
{
    const char *element = (const char *)_element;
    int elem_size;
    int id = -1;
    CvSeqBlock *first_block;
    CvSeqBlock *block;

    CV_FUNCNAME( "cvSeqElemIdx" );

    __BEGIN__;

    if( !seq || !element )
        CV_ERROR( CV_StsNullPtr, "" );

    block = first_block = seq->first;
    elem_size = seq->elem_size;

    for( ;; )
    {
        if( (unsigned)(element - block->data) < (unsigned) (block->count * elem_size) )
        {
            if( _block )
                *_block = block;
            id = (element - block->data) / elem_size +
                block->start_index - seq->first->start_index;
            break;
        }
        block = block->next;
        if( block == first_block )
            break;
    }

    __END__;

    return id;
}


int icvSliceLength( CvSlice slice, CvSeq* seq )
{
    int total = seq->total;
    int length;
    if( slice.startIndex < 0 )
        slice.startIndex += total;
    if( slice.endIndex <= 0 )
        slice.endIndex += total;
    length = slice.endIndex - slice.startIndex;
    if( length < 0 )
    {
        length += total;
        /*if( length < 0 )
            length += total;*/
    }
    else if( length > total )
        length = total;

    return length;
};


/* copies all the sequence elements into single continuous array */
CV_IMPL void*
cvCvtSeqToArray( CvSeq *seq, void *array, CvSlice slice )
{
    int elem_size, total;
    CvSeqBlock *block;
    char *dstPtr = (char*)array;
    char *ptr = 0;

    CV_FUNCNAME( "cvCvtSeqToArray" );

    __BEGIN__;

    if( !seq || !array )
        CV_ERROR( CV_StsNullPtr, "" );

    elem_size = seq->elem_size;
    total = icvSliceLength( slice, seq )*elem_size;
    ptr = cvGetSeqElem( seq, slice.startIndex, &block );

    if( !ptr )
        CV_ERROR_FROM_STATUS( CV_BADRANGE_ERR );

    while( total > 0 )
    {
        int count = block->data + block->count*elem_size - ptr;
        if( count > total )
            count = total;

        memcpy( dstPtr, ptr, count );
        dstPtr += count;
        total -= count;
        block = block->next;
        ptr = block->data;
    }

    __END__;

    return array;
}


/* constructs sequence from array without copying any data.
   the resultant sequence can't grow above its initial size */
CV_IMPL CvSeq*
cvMakeSeqHeaderForArray( int seq_flags, int header_size, int elem_size,
                         void *array, int total, CvSeq *seq, CvSeqBlock * block )
{
    CvSeq* result = 0;
    
    CV_FUNCNAME( "cvMakeSeqHeaderForArray" );

    __BEGIN__;

    if( elem_size <= 0 || header_size < (int)sizeof( CvSeq ) || total < 0 )
        CV_ERROR_FROM_STATUS( CV_BADSIZE_ERR );

    if( !seq || ((!array || !block) && total > 0) )
        CV_ERROR( CV_StsNullPtr, "" );

    memset( seq, 0, header_size );

    seq->header_size = header_size;
    seq->flags = (seq_flags & ~CV_MAGIC_MASK) | CV_SEQ_MAGIC_VAL;
    {
        int elemtype = CV_MAT_TYPE(seq_flags);
        int typesize = icvPixSize[elemtype];

        if( elemtype != CV_SEQ_ELTYPE_GENERIC &&
            typesize != 0 && typesize != elem_size )
            CV_ERROR( CV_StsBadSize,
            "Element size doesn't match to the size of predefined element type "
            "(try to use 0 for sequence element type)" );
    }
    seq->elem_size = elem_size;
    seq->total = total;
    seq->block_max = seq->ptr = (char *) array + total * elem_size;

    if( total > 0 )
    {
        seq->first = block;
        block->prev = block->next = block;
        block->start_index = 0;
        block->count = total;
        block->data = (char *) array;
    }

    result = seq;

    __END__;

    return result;
}


CvSeq*
icvPointSeqFromMat( int seq_kind, const CvArr* arr,
                    CvContour* contour_header, CvSeqBlock* block )
{
    CvSeq* contour = 0;

    CV_FUNCNAME( "icvPointSeqFromMat" );

    assert( arr != 0 && contour_header != 0 && block != 0 );

    __BEGIN__;
    
    int eltype;
    CvMat* mat = (CvMat*)arr;
    
    if( !CV_IS_MAT( mat ))
        CV_ERROR( CV_StsBadArg, "Input array is not a valid matrix" ); 

    eltype = CV_MAT_TYPE( mat->type );
    if( eltype != CV_32SC2 && eltype != CV_32FC2 )
        CV_ERROR( CV_StsUnsupportedFormat,
        "The matrix can not be converted to point sequence because of "
        "inappropriate element type" );

    if( mat->width != 1 && mat->height != 1 || !CV_IS_MAT_CONT(mat->type))
        CV_ERROR( CV_StsBadArg,
        "The matrix converted to point sequence must be "
        "1-dimensional and continuous" );

    CV_CALL( cvMakeSeqHeaderForArray(
            (seq_kind & (CV_SEQ_KIND_MASK|CV_SEQ_FLAG_CLOSED)) | eltype,
            sizeof(CvContour), icvPixSize[eltype], mat->data.ptr,
            mat->width*mat->height, (CvSeq*)contour_header, block ));

    contour = (CvSeq*)contour_header;

    __END__;

    return contour;
}


/* tries to allocate space for at least single sequence element.
   if the sequence has released blocks (seq->free_blocks != 0),
   they are used, else additional space is allocated in the storage */
static void
icvGrowSeq( CvSeq *seq, int in_front_of )
{
    CV_FUNCNAME( "icvGrowSeq" );

    __BEGIN__;

    CvSeqBlock *free_blocks;

    if( !seq )
        CV_ERROR( CV_StsNullPtr, "" );
    free_blocks = seq->free_blocks;

    if( !free_blocks )
    {
        int elem_size = seq->elem_size;
        int delta_elems = seq->delta_elems;
        CvMemStorage *storage = seq->storage;

        if( !storage )
            CV_ERROR( CV_StsNullPtr, "The sequence has NULL storage pointer" );

        /* if there is a free space just after last allocated block
           and it's big enough then enlarge the last block
           (this can happen only if the new block is added to the end of sequence */
        if( (unsigned)(ICV_FREE_PTR(storage) - seq->block_max) < CV_STRUCT_ALIGN &&
            storage->free_space >= seq->elem_size && !in_front_of )
        {
            int delta = storage->free_space / elem_size;

            delta = MIN( delta, delta_elems ) * elem_size;
            seq->block_max += delta;
            storage->free_space = (((char*)storage->top + storage->block_size) -
                                   seq->block_max) & -CV_STRUCT_ALIGN;
            EXIT;
        }
        else
        {
            int delta = elem_size * delta_elems + ICV_ALIGNED_SEQ_BLOCK_SIZE;

            /* try to allocate <delta_elements> elements */
            if( storage->free_space < delta )
            {
                int small_block_size = MAX(1, delta_elems/3)*elem_size +
                                       ICV_ALIGNED_SEQ_BLOCK_SIZE;
                /* try to allocate smaller part */
                if( storage->free_space >= small_block_size + CV_STRUCT_ALIGN )
                {
                    delta = ((storage->free_space - ICV_ALIGNED_SEQ_BLOCK_SIZE)/
                            seq->elem_size)*seq->elem_size + ICV_ALIGNED_SEQ_BLOCK_SIZE;
                }
                else
                {
                    CV_CALL( icvGoNextMemBlock( storage ));
                    assert( storage->free_space >= delta );
                }
            }

            CV_CALL( free_blocks = (CvSeqBlock*)cvMemStorageAlloc( storage, delta ));
            free_blocks->data = (char*)icvAlignPtr( free_blocks + 1, CV_STRUCT_ALIGN );
            free_blocks->count = delta - ICV_ALIGNED_SEQ_BLOCK_SIZE;
            free_blocks->prev = free_blocks->next = 0;
        }
    }
    else
    {
        seq->free_blocks = free_blocks->next;
    }

    if( !(seq->first) )
    {
        seq->first = free_blocks;
        free_blocks->prev = free_blocks->next = free_blocks;
    }
    else
    {
        free_blocks->prev = seq->first->prev;
        free_blocks->next = seq->first;
        free_blocks->prev->next = free_blocks->next->prev = free_blocks;
    }

    /* for free blocks the <count> field means total number of bytes in the block.
       And for used blocks it means a current number of sequence
       elements in the block */
    assert( free_blocks->count % seq->elem_size == 0 && free_blocks->count > 0 );

    if( !in_front_of )
    {
        seq->ptr = free_blocks->data;
        seq->block_max = free_blocks->data + free_blocks->count;
        free_blocks->start_index = free_blocks == free_blocks->prev ? 0 :
            free_blocks->prev->start_index + free_blocks->prev->count;
    }
    else
    {
        int delta = free_blocks->count / seq->elem_size;
        free_blocks->data += free_blocks->count;

        if( free_blocks != free_blocks->prev )
        {
            assert( seq->first->start_index == 0 );
            seq->first = free_blocks;
        }
        else
        {
            seq->block_max = seq->ptr = free_blocks->data;
        }

        free_blocks->start_index = 0;

        for( ;; )
        {
            free_blocks->start_index += delta;
            free_blocks = free_blocks->next;
            if( free_blocks == seq->first )
                break;
        }
    }

    free_blocks->count = 0;

    __END__;
}

/* recycles a sequence block for the further use */
static void
icvFreeSeqBlock( CvSeq *seq, int in_front_of )
{
    /*CV_FUNCNAME( "icvFreeSeqBlock" );*/

    __BEGIN__;

    CvSeqBlock *block = seq->first;

    assert( (in_front_of ? block : block->prev)->count == 0 );

    if( block == block->prev )  /* single block case */
    {
        block->count = (seq->block_max - block->data) + block->start_index * seq->elem_size;
        block->data = seq->block_max - block->count;
        seq->first = 0;
        seq->ptr = seq->block_max = 0;
        seq->total = 0;
    }
    else
    {
        if( !in_front_of )
        {
            block = block->prev;
            assert( seq->ptr == block->data );

            block->count = seq->block_max - seq->ptr;
            seq->block_max = seq->ptr = block->prev->data +
                block->prev->count * seq->elem_size;
        }
        else
        {
            int delta = block->start_index;

            block->count = delta * seq->elem_size;
            block->data -= block->count;

            /* update start indices of sequence blocks */
            for( ;; )
            {
                block->start_index -= delta;
                block = block->next;
                if( block == seq->first )
                    break;
            }

            seq->first = block->next;
        }

        block->prev->next = block->next;
        block->next->prev = block->prev;
    }

    assert( block->count > 0 && block->count % seq->elem_size == 0 );
    block->next = seq->free_blocks;
    seq->free_blocks = block;

    __END__;
}


/****************************************************************************************\
*                             Sequence Writer implementation                             *
\****************************************************************************************/

/* initializes sequence writer */
CV_IMPL void
cvStartAppendToSeq( CvSeq *seq, CvSeqWriter * writer )
{
    CV_FUNCNAME( "cvStartAppendToSeq" );

    __BEGIN__;

    if( !seq || !writer )
        CV_ERROR( CV_StsNullPtr, "" );

    memset( writer, 0, sizeof( *writer ));
    writer->header_size = sizeof( CvSeqWriter );

    writer->seq = seq;
    writer->block = seq->first ? seq->first->prev : 0;
    writer->ptr = seq->ptr;
    writer->block_max = seq->block_max;

    __END__;
}


/* initializes sequence writer */
CV_IMPL void
cvStartWriteSeq( int seq_flags, int header_size,
                 int elem_size, CvMemStorage * storage, CvSeqWriter * writer )
{
    CvSeq *seq = 0;

    CV_FUNCNAME( "cvStartWriteSeq" );

    __BEGIN__;

    if( !storage || !writer )
        CV_ERROR( CV_StsNullPtr, "" );

    CV_CALL( seq = cvCreateSeq( seq_flags, header_size, elem_size, storage ));
    cvStartAppendToSeq( seq, writer );

    __END__;
}


/* updates sequence header */
CV_IMPL void
cvFlushSeqWriter( CvSeqWriter * writer )
{
    CvSeq *seq = 0;

    CV_FUNCNAME( "cvFlushSeqWriter" );

    __BEGIN__;

    if( !writer )
        CV_ERROR( CV_StsNullPtr, "" );

    seq = writer->seq;