////////////////////////////////////////////////////////////////////////////////////////////  IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.////  By downloading, copying, installing or using the software you agree to this license.//  If you do not agree to this license, do not download, install,//  copy or use the software.//////                 License For Embedded Computer Vision Library//// Copyright (c) 2008, EMCV Project,// Copyright (c) 2000-2007, Intel Corporation,// All rights reserved.// Third party copyrights are property of their respective owners.//// Redistribution and use in source and binary forms, with or without modification, // are permitted provided that the following conditions are met:////    * Redistributions of source code must retain the above copyright notice, //      this list of conditions and the following disclaimer.//    * Redistributions in binary form must reproduce the above copyright notice, //      this list of conditions and the following disclaimer in the documentation //      and/or other materials provided with the distribution.//    * Neither the name of the copyright holders nor the names of their contributors //      may be used to endorse or promote products derived from this software //      without specific prior written permission.//// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND // ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED // WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. // IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, // INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT // NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, // OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, // WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) // ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY // OF SUCH DAMAGE.//// Contributors://    * Shiqi Yu (Shenzhen Institute of Advanced Technology, Chinese Academy of Sciences)#include "cxcore.h"#define ICV_FREE_PTR(storage)  \    ((char*)(storage)->top + (storage)->block_size - (storage)->free_space)#define ICV_ALIGNED_SEQ_BLOCK_SIZE  \    (int)cvAlign(sizeof(CvSeqBlock), CV_STRUCT_ALIGN)CV_INLINE intcvAlignLeft( int size, int align ){    return size & -align;}#define CV_GET_LAST_ELEM( seq, block ) \    ((block)->data + ((block)->count - 1)*((seq)->elem_size))#define CV_SWAP_ELEMS(a,b,elem_size)  \{                                     \    int k;                            \    for( k = 0; k < elem_size; k++ )  \    {                                 \        char t0 = (a)[k];             \        char t1 = (b)[k];             \        (a)[k] = t1;                  \        (b)[k] = t0;                  \    }                                 \}#define ICV_SHIFT_TAB_MAX 32static const char icvPower2ShiftTab[] ={    0, 1, -1, 2, -1, -1, -1, 3, -1, -1, -1, -1, -1, -1, -1, 4,    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 5};/****************************************************************************************\*            Functions for manipulating memory storage - list of memory blocks           *\****************************************************************************************//* initializes allocated storage */static voidicvInitMemStorage( CvMemStorage* storage, int block_size ){    CV_FUNCNAME( "icvInitMemStorage " );        __BEGIN__;    if( !storage )        CV_ERROR( CV_StsNullPtr, "" );    if( block_size <= 0 )        block_size = CV_STORAGE_BLOCK_SIZE;    block_size = cvAlign( block_size, CV_STRUCT_ALIGN );    assert( sizeof(CvMemBlock) % CV_STRUCT_ALIGN == 0 );    memset( storage, 0, sizeof( *storage ));    storage->signature = CV_STORAGE_MAGIC_VAL;    storage->block_size = block_size;    __END__;}/* creates root memory storage */CV_IMPL CvMemStorage*cvCreateMemStorage( int block_size ){    CvMemStorage *storage = 0;    CV_FUNCNAME( "cvCreateMemStorage" );    __BEGIN__;    CV_CALL( storage = (CvMemStorage *)cvAlloc( sizeof( CvMemStorage )));    CV_CALL( icvInitMemStorage( storage, block_size ));    __END__;    if( cvGetErrStatus() < 0 )        cvFree( &storage );    return storage;}/* creates child memory storage */CV_IMPL CvMemStorage *cvCreateChildMemStorage( CvMemStorage * parent ){    CvMemStorage *storage = 0;    CV_FUNCNAME( "cvCreateChildMemStorage" );    __BEGIN__;    if( !parent )        CV_ERROR( CV_StsNullPtr, "" );    CV_CALL( storage = cvCreateMemStorage(parent->block_size));    storage->parent = parent;    __END__;    if( cvGetErrStatus() < 0 )        cvFree( &storage );    return storage;}/* releases all blocks of the storage (or returns them to parent if any) */static voidicvDestroyMemStorage( CvMemStorage* storage ){    CV_FUNCNAME( "icvDestroyMemStorage" );    __BEGIN__;    int k = 0;    CvMemBlock *block;    CvMemBlock *dst_top = 0;    if( !storage )        CV_ERROR( CV_StsNullPtr, "" );    if( storage->parent )        dst_top = storage->parent->top;    for( block = storage->bottom; block != 0; k++ )    {        CvMemBlock *temp = block;        block = block->next;        if( storage->parent )        {            if( dst_top )            {                temp->prev = dst_top;                temp->next = dst_top->next;                if( temp->next )                    temp->next->prev = temp;                dst_top = dst_top->next = temp;            }            else            {                dst_top = storage->parent->bottom = storage->parent->top = temp;                temp->prev = temp->next = 0;                storage->free_space = storage->block_size - sizeof( *temp );            }        }        else        {            cvFree( &temp );        }    }    storage->top = storage->bottom = 0;    storage->free_space = 0;    __END__;}/* releases memory storage */CV_IMPL voidcvReleaseMemStorage( CvMemStorage** storage ){    CvMemStorage *st;    CV_FUNCNAME( "cvReleaseMemStorage" );    __BEGIN__;    if( !storage )        CV_ERROR( CV_StsNullPtr, "" );    st = *storage;    *storage = 0;    if( st )    {        CV_CALL( icvDestroyMemStorage( st ));        cvFree( &st );    }    __END__;}/* clears memory storage (returns blocks to the parent if any) */CV_IMPL voidcvClearMemStorage( CvMemStorage * storage ){    CV_FUNCNAME( "cvClearMemStorage" );    __BEGIN__;    if( !storage )        CV_ERROR( CV_StsNullPtr, "" );    if( storage->parent )    {        icvDestroyMemStorage( storage );    }    else    {        storage->top = storage->bottom;        storage->free_space = storage->bottom ? storage->block_size - sizeof(CvMemBlock) : 0;    }    __END__;}/* moves stack pointer to next block.   If no blocks, allocate new one and link it to the storage */static voidicvGoNextMemBlock( CvMemStorage * storage ){    CV_FUNCNAME( "icvGoNextMemBlock" );        __BEGIN__;        if( !storage )        CV_ERROR( CV_StsNullPtr, "" );    if( !storage->top || !storage->top->next )    {        CvMemBlock *block;        if( !(storage->parent) )        {            CV_CALL( block = (CvMemBlock *)cvAlloc( storage->block_size ));        }        else        {            CvMemStorage *parent = storage->parent;            CvMemStoragePos parent_pos;            cvSaveMemStoragePos( parent, &parent_pos );            CV_CALL( icvGoNextMemBlock( parent ));            block = parent->top;            cvRestoreMemStoragePos( parent, &parent_pos );            if( block == parent->top )  /* the single allocated block */            {                assert( parent->bottom == block );                parent->top = parent->bottom = 0;                parent->free_space = 0;            }            else            {                /* cut the block from the parent's list of blocks */                parent->top->next = block->next;                if( block->next )                    block->next->prev = parent->top;            }        }        /* link block */        block->next = 0;        block->prev = storage->top;        if( storage->top )            storage->top->next = block;        else            storage->top = storage->bottom = block;    }    if( storage->top->next )        storage->top = storage->top->next;    storage->free_space = storage->block_size - sizeof(CvMemBlock);    assert( storage->free_space % CV_STRUCT_ALIGN == 0 );    __END__;}/* remembers memory storage position */CV_IMPL voidcvSaveMemStoragePos( const CvMemStorage * storage, CvMemStoragePos * pos ){    CV_FUNCNAME( "cvSaveMemStoragePos" );    __BEGIN__;    if( !storage || !pos )        CV_ERROR( CV_StsNullPtr, "" );    pos->top = storage->top;    pos->free_space = storage->free_space;    __END__;}/* restores memory storage position */CV_IMPL voidcvRestoreMemStoragePos( CvMemStorage * storage, CvMemStoragePos * pos ){    CV_FUNCNAME( "cvRestoreMemStoragePos" );    __BEGIN__;    if( !storage || !pos )        CV_ERROR( CV_StsNullPtr, "" );    if( pos->free_space > storage->block_size )        CV_ERROR( CV_StsBadSize, "" );    /*    // this breaks icvGoNextMemBlock, so comment it off for now    if( storage->parent && (!pos->top || pos->top->next) )    {        CvMemBlock* save_bottom;        if( !pos->top )            save_bottom = 0;        else        {            save_bottom = storage->bottom;            storage->bottom = pos->top->next;            pos->top->next = 0;            storage->bottom->prev = 0;        }        icvDestroyMemStorage( storage );        storage->bottom = save_bottom;    }*/    storage->top = pos->top;    storage->free_space = pos->free_space;    if( !storage->top )    {        storage->top = storage->bottom;        storage->free_space = storage->top ? storage->block_size - sizeof(CvMemBlock) : 0;    }    __END__;}/* Allocates continuous buffer of the specified size in the storage */CV_IMPL void*cvMemStorageAlloc( CvMemStorage* storage, size_t size ){    char *ptr = 0;        CV_FUNCNAME( "cvMemStorageAlloc" );    __BEGIN__;    if( !storage )        CV_ERROR( CV_StsNullPtr, "NULL storage pointer" );    if( size > INT_MAX )        CV_ERROR( CV_StsOutOfRange, "Too large memory block is requested" );    assert( storage->free_space % CV_STRUCT_ALIGN == 0 );    if( (size_t)storage->free_space < size )    {        size_t max_free_space = cvAlignLeft(storage->block_size - sizeof(CvMemBlock), CV_STRUCT_ALIGN);        if( max_free_space < size )            CV_ERROR( CV_StsOutOfRange, "requested size is negative or too big" );        CV_CALL( icvGoNextMemBlock( storage ));    }    ptr = ICV_FREE_PTR(storage);    assert( (size_t)ptr % CV_STRUCT_ALIGN == 0 );    storage->free_space = cvAlignLeft(storage->free_space - (int)size, CV_STRUCT_ALIGN );    __END__;    return ptr;}CV_IMPL CvStringcvMemStorageAllocString( CvMemStorage* storage, const char* ptr, int len ){    CvString str;    CV_FUNCNAME( "cvMemStorageAllocString" );    __BEGIN__;    str.len = len >= 0 ? len : (int)strlen(ptr);    CV_CALL( str.ptr = (char*)cvMemStorageAlloc( storage, str.len + 1 ));    memcpy( str.ptr, ptr, str.len );    str.ptr[str.len] = '\0';    __END__;    return str;}/****************************************************************************************\*                               Sequence implementation                                  *\****************************************************************************************//* creates empty sequence */CV_IMPL CvSeq *cvCreateSeq( int seq_flags, int header_size, int elem_size, CvMemStorage * storage ){    CvSeq *seq = 0;    CV_FUNCNAME( "cvCreateSeq" );    __BEGIN__;    if( !storage )        CV_ERROR( CV_StsNullPtr, "" );    if( header_size < (int)sizeof( CvSeq ) || elem_size <= 0 )        CV_ERROR( CV_StsBadSize, "" );    /* allocate sequence header */    CV_CALL( seq = (CvSeq*)cvMemStorageAlloc( storage, header_size ));    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 = CV_ELEM_SIZE(elemtype);        if( elemtype != CV_SEQ_ELTYPE_GENERIC &&            typesize != 0 && typesize != elem_size )            CV_ERROR( CV_StsBadSize,            "Specified element size doesn't match to the size of the specified element type "            "(try to use 0 for element type)" );    }    seq->elem_size = elem_size;    seq->storage = storage;