X-Git-Url: https://vcs.maemo.org/git/?a=blobdiff_plain;f=cxcore%2Fsrc%2Fcxdatastructs.cpp;fp=cxcore%2Fsrc%2Fcxdatastructs.cpp;h=b31b06f177a114713680e46d78ade9937eab89e7;hb=80cd7b93506cc1926882d5fd08a2c74ee9359e29;hp=f2512c29372701e52d49cb09592cf19667ffc246;hpb=467a270adf12425827305759c0c4ea8f5b2b3854;p=opencv diff --git a/cxcore/src/cxdatastructs.cpp b/cxcore/src/cxdatastructs.cpp index f2512c2..b31b06f 100644 --- a/cxcore/src/cxdatastructs.cpp +++ b/cxcore/src/cxdatastructs.cpp @@ -41,7 +41,7 @@ #include "_cxcore.h" #define ICV_FREE_PTR(storage) \ - ((char*)(storage)->top + (storage)->block_size - (storage)->free_space) + ((schar*)(storage)->top + (storage)->block_size - (storage)->free_space) #define ICV_ALIGNED_SEQ_BLOCK_SIZE \ (int)cvAlign(sizeof(CvSeqBlock), CV_STRUCT_ALIGN) @@ -68,7 +68,7 @@ cvAlignLeft( int size, int align ) } #define ICV_SHIFT_TAB_MAX 32 -static const char icvPower2ShiftTab[] = +static const schar 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 @@ -78,12 +78,12 @@ static const char icvPower2ShiftTab[] = * Functions for manipulating memory storage - list of memory blocks * \****************************************************************************************/ -/* initializes allocated storage */ +/* Initialize allocated storage: */ static void icvInitMemStorage( CvMemStorage* storage, int block_size ) { CV_FUNCNAME( "icvInitMemStorage " ); - + __BEGIN__; if( !storage ) @@ -103,7 +103,7 @@ icvInitMemStorage( CvMemStorage* storage, int block_size ) } -/* creates root memory storage */ +/* Create root memory storage: */ CV_IMPL CvMemStorage* cvCreateMemStorage( int block_size ) { @@ -125,7 +125,7 @@ cvCreateMemStorage( int block_size ) } -/* creates child memory storage */ +/* Create child memory storage: */ CV_IMPL CvMemStorage * cvCreateChildMemStorage( CvMemStorage * parent ) { @@ -149,7 +149,7 @@ cvCreateChildMemStorage( CvMemStorage * parent ) } -/* releases all blocks of the storage (or returns them to parent if any) */ +/* Release all blocks of the storage (or return them to parent, if any): */ static void icvDestroyMemStorage( CvMemStorage* storage ) { @@ -203,7 +203,7 @@ icvDestroyMemStorage( CvMemStorage* storage ) } -/* releases memory storage */ +/* Release memory storage: */ CV_IMPL void cvReleaseMemStorage( CvMemStorage** storage ) { @@ -228,7 +228,7 @@ cvReleaseMemStorage( CvMemStorage** storage ) } -/* clears memory storage (returns blocks to the parent if any) */ +/* Clears memory storage (return blocks to the parent, if any): */ CV_IMPL void cvClearMemStorage( CvMemStorage * storage ) { @@ -253,15 +253,15 @@ cvClearMemStorage( CvMemStorage * storage ) } -/* moves stack pointer to next block. - If no blocks, allocate new one and link it to the storage */ +/* Moves stack pointer to next block. + If no blocks, allocate new one and link it to the storage: */ static void icvGoNextMemBlock( CvMemStorage * storage ) { CV_FUNCNAME( "icvGoNextMemBlock" ); - + __BEGIN__; - + if( !storage ) CV_ERROR( CV_StsNullPtr, "" ); @@ -318,7 +318,7 @@ icvGoNextMemBlock( CvMemStorage * storage ) } -/* remembers memory storage position */ +/* Remember memory storage position: */ CV_IMPL void cvSaveMemStoragePos( const CvMemStorage * storage, CvMemStoragePos * pos ) { @@ -336,7 +336,7 @@ cvSaveMemStoragePos( const CvMemStorage * storage, CvMemStoragePos * pos ) } -/* restores memory storage position */ +/* Restore memory storage position: */ CV_IMPL void cvRestoreMemStoragePos( CvMemStorage * storage, CvMemStoragePos * pos ) { @@ -380,12 +380,12 @@ cvRestoreMemStoragePos( CvMemStorage * storage, CvMemStoragePos * pos ) } -/* Allocates continuous buffer of the specified size in the storage */ +/* Allocate continuous buffer of the specified size in the storage: */ CV_IMPL void* cvMemStorageAlloc( CvMemStorage* storage, size_t size ) { - char *ptr = 0; - + schar *ptr = 0; + CV_FUNCNAME( "cvMemStorageAlloc" ); __BEGIN__; @@ -440,7 +440,7 @@ cvMemStorageAllocString( CvMemStorage* storage, const char* ptr, int len ) * Sequence implementation * \****************************************************************************************/ -/* creates empty sequence */ +/* Create empty sequence: */ CV_IMPL CvSeq * cvCreateSeq( int seq_flags, int header_size, int elem_size, CvMemStorage * storage ) { @@ -522,8 +522,8 @@ cvSetSeqBlockSize( CvSeq *seq, int delta_elements ) } -/* finds sequence element by its index */ -CV_IMPL char* +/* Find a sequence element by its index: */ +CV_IMPL schar* cvGetSeqElem( const CvSeq *seq, int index ) { CvSeqBlock *block; @@ -561,11 +561,11 @@ cvGetSeqElem( const CvSeq *seq, int index ) } -/* calculates index of sequence element */ +/* Calculate index of a sequence element: */ CV_IMPL int cvSeqElemIdx( const CvSeq* seq, const void* _element, CvSeqBlock** _block ) { - const char *element = (const char *)_element; + const schar *element = (const schar *)_element; int elem_size; int id = -1; CvSeqBlock *first_block; @@ -610,7 +610,7 @@ cvSliceLength( CvSlice slice, const CvSeq* seq ) { int total = seq->total; int length = slice.end_index - slice.start_index; - + if( length != 0 ) { if( slice.start_index < 0 ) @@ -634,7 +634,7 @@ cvSliceLength( CvSlice slice, const CvSeq* seq ) } -/* copies all the sequence elements into single continuous array */ +/* Copy all sequence elements into single continuous array: */ CV_IMPL void* cvCvtSeqToArray( const CvSeq *seq, void *array, CvSlice slice ) { @@ -651,10 +651,10 @@ cvCvtSeqToArray( const CvSeq *seq, void *array, CvSlice slice ) elem_size = seq->elem_size; total = cvSliceLength( slice, seq )*elem_size; - + if( total == 0 ) EXIT; - + cvStartReadSeq( seq, &reader, 0 ); CV_CALL( cvSetSeqReaderPos( &reader, slice.start_index, 0 )); @@ -679,14 +679,14 @@ cvCvtSeqToArray( const CvSeq *seq, void *array, CvSlice slice ) } -/* constructs sequence from array without copying any data. - the resultant sequence can't grow above its initial size */ +/* Construct a sequence from an array without copying any data. + NB: The resultant sequence cannot grow beyond 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__; @@ -713,7 +713,7 @@ cvMakeSeqHeaderForArray( int seq_flags, int header_size, int elem_size, } seq->elem_size = elem_size; seq->total = total; - seq->block_max = seq->ptr = (char *) array + total * elem_size; + seq->block_max = seq->ptr = (schar *) array + total * elem_size; if( total > 0 ) { @@ -721,7 +721,7 @@ cvMakeSeqHeaderForArray( int seq_flags, int header_size, int elem_size, block->prev = block->next = block; block->start_index = 0; block->count = total; - block->data = (char *) array; + block->data = (schar *) array; } result = seq; @@ -732,9 +732,9 @@ cvMakeSeqHeaderForArray( int seq_flags, int header_size, int elem_size, } -/* the function allocates space for at least one more sequence element. - if there are free sequence blocks (seq->free_blocks != 0), - they are reused, otherwise the space is allocated in the storage */ +/* The function allocates space for at least one more sequence element. + If there are free sequence blocks (seq->free_blocks != 0) + they are reused, otherwise the space is allocated in the storage: */ static void icvGrowSeq( CvSeq *seq, int in_front_of ) { @@ -760,9 +760,9 @@ icvGrowSeq( CvSeq *seq, int in_front_of ) 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 there is a free space just after last allocated block + and it is 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 ) { @@ -770,7 +770,7 @@ icvGrowSeq( CvSeq *seq, int in_front_of ) delta = MIN( delta, delta_elems ) * elem_size; seq->block_max += delta; - storage->free_space = cvAlignLeft((int)(((char*)storage->top + storage->block_size) - + storage->free_space = cvAlignLeft((int)(((schar*)storage->top + storage->block_size) - seq->block_max), CV_STRUCT_ALIGN ); EXIT; } @@ -778,7 +778,7 @@ icvGrowSeq( CvSeq *seq, int in_front_of ) { int delta = elem_size * delta_elems + ICV_ALIGNED_SEQ_BLOCK_SIZE; - /* try to allocate elements */ + /* Try to allocate elements: */ if( storage->free_space < delta ) { int small_block_size = MAX(1, delta_elems/3)*elem_size + @@ -797,7 +797,7 @@ icvGrowSeq( CvSeq *seq, int in_front_of ) } CV_CALL( block = (CvSeqBlock*)cvMemStorageAlloc( storage, delta )); - block->data = (char*)cvAlignPtr( block + 1, CV_STRUCT_ALIGN ); + block->data = (schar*)cvAlignPtr( block + 1, CV_STRUCT_ALIGN ); block->count = delta - ICV_ALIGNED_SEQ_BLOCK_SIZE; block->prev = block->next = 0; } @@ -819,9 +819,12 @@ icvGrowSeq( CvSeq *seq, int in_front_of ) block->prev->next = block->next->prev = block; } - /* for free blocks the field means total number of bytes in the block. - And for used blocks it means a current number of sequence - elements in the block */ + /* For free blocks the field means + * total number of bytes in the block. + * + * For used blocks it means current number + * of sequence elements in the block: + */ assert( block->count % seq->elem_size == 0 && block->count > 0 ); if( !in_front_of ) @@ -862,7 +865,7 @@ icvGrowSeq( CvSeq *seq, int in_front_of ) __END__; } -/* recycles a sequence block for the further use */ +/* Recycle a sequence block: */ static void icvFreeSeqBlock( CvSeq *seq, int in_front_of ) { @@ -900,7 +903,7 @@ icvFreeSeqBlock( CvSeq *seq, int in_front_of ) block->count = delta * seq->elem_size; block->data -= block->count; - /* update start indices of sequence blocks */ + /* Update start indices of sequence blocks: */ for( ;; ) { block->start_index -= delta; @@ -928,7 +931,7 @@ icvFreeSeqBlock( CvSeq *seq, int in_front_of ) * Sequence Writer implementation * \****************************************************************************************/ -/* initializes sequence writer */ +/* Initialize sequence writer: */ CV_IMPL void cvStartAppendToSeq( CvSeq *seq, CvSeqWriter * writer ) { @@ -951,7 +954,7 @@ cvStartAppendToSeq( CvSeq *seq, CvSeqWriter * writer ) } -/* initializes sequence writer */ +/* Initialize sequence writer: */ CV_IMPL void cvStartWriteSeq( int seq_flags, int header_size, int elem_size, CvMemStorage * storage, CvSeqWriter * writer ) @@ -972,7 +975,7 @@ cvStartWriteSeq( int seq_flags, int header_size, } -/* updates sequence header */ +/* Update sequence header: */ CV_IMPL void cvFlushSeqWriter( CvSeqWriter * writer ) { @@ -1011,7 +1014,7 @@ cvFlushSeqWriter( CvSeqWriter * writer ) } -/* calls icvFlushSeqWriter and finishes writing process */ +/* Calls icvFlushSeqWriter and finishes writing process: */ CV_IMPL CvSeq * cvEndWriteSeq( CvSeqWriter * writer ) { @@ -1027,11 +1030,11 @@ cvEndWriteSeq( CvSeqWriter * writer ) CV_CALL( cvFlushSeqWriter( writer )); seq = writer->seq; - /* truncate the last block */ + /* Truncate the last block: */ if( writer->block && writer->seq->storage ) { CvMemStorage *storage = seq->storage; - char *storage_block_max = (char *) storage->top + storage->block_size; + schar *storage_block_max = (schar *) storage->top + storage->block_size; assert( writer->block->count > 0 ); @@ -1051,7 +1054,7 @@ cvEndWriteSeq( CvSeqWriter * writer ) } -/* creates new sequence block */ +/* Create new sequence block: */ CV_IMPL void cvCreateSeqBlock( CvSeqWriter * writer ) { @@ -1082,7 +1085,7 @@ cvCreateSeqBlock( CvSeqWriter * writer ) * Sequence Reader implementation * \****************************************************************************************/ -/* initializes sequence reader */ +/* Initialize sequence reader: */ CV_IMPL void cvStartReadSeq( const CvSeq *seq, CvSeqReader * reader, int reverse ) { @@ -1117,7 +1120,7 @@ cvStartReadSeq( const CvSeq *seq, CvSeqReader * reader, int reverse ) if( reverse ) { - char *temp = reader->ptr; + schar *temp = reader->ptr; reader->ptr = reader->prev_elem; reader->prev_elem = temp; @@ -1144,7 +1147,9 @@ cvStartReadSeq( const CvSeq *seq, CvSeqReader * reader, int reverse ) } -/* changes the current reading block to the previous or to the next */ +/* Change the current reading block + * to the previous or to the next: + */ CV_IMPL void cvChangeSeqBlock( void* _reader, int direction ) { @@ -1153,7 +1158,7 @@ cvChangeSeqBlock( void* _reader, int direction ) __BEGIN__; CvSeqReader* reader = (CvSeqReader*)_reader; - + if( !reader ) CV_ERROR( CV_StsNullPtr, "" ); @@ -1174,7 +1179,7 @@ cvChangeSeqBlock( void* _reader, int direction ) } -/* returns the current reader position */ +/* Return the current reader position: */ CV_IMPL int cvGetSeqReaderPos( CvSeqReader* reader ) { @@ -1202,8 +1207,10 @@ cvGetSeqReaderPos( CvSeqReader* reader ) } -/* sets reader position to given absolute or relative - (relatively to the current one) position */ +/* Set reader position to given position, + * either absolute or relative to the + * current one: + */ CV_IMPL void cvSetSeqReaderPos( CvSeqReader* reader, int index, int is_relative ) { @@ -1268,7 +1275,7 @@ cvSetSeqReaderPos( CvSeqReader* reader, int index, int is_relative ) } else { - char* ptr = reader->ptr; + schar* ptr = reader->ptr; index *= elem_size; block = reader->block; @@ -1302,11 +1309,11 @@ cvSetSeqReaderPos( CvSeqReader* reader, int index, int is_relative ) } -/* pushes element to the sequence */ -CV_IMPL char* +/* Push element onto the sequence: */ +CV_IMPL schar* cvSeqPush( CvSeq *seq, void *element ) { - char *ptr = 0; + schar *ptr = 0; size_t elem_size; CV_FUNCNAME( "cvSeqPush" ); @@ -1339,11 +1346,11 @@ cvSeqPush( CvSeq *seq, void *element ) } -/* pops the last element out of the sequence */ +/* Pop last element off of the sequence: */ CV_IMPL void cvSeqPop( CvSeq *seq, void *element ) { - char *ptr; + schar *ptr; int elem_size; CV_FUNCNAME( "cvSeqPop" ); @@ -1373,11 +1380,11 @@ cvSeqPop( CvSeq *seq, void *element ) } -/* pushes element to the front of the sequence */ -CV_IMPL char* +/* Push element onto the front of the sequence: */ +CV_IMPL schar* cvSeqPushFront( CvSeq *seq, void *element ) { - char* ptr = 0; + schar* ptr = 0; int elem_size; CvSeqBlock *block; @@ -1413,7 +1420,7 @@ cvSeqPushFront( CvSeq *seq, void *element ) } -/* pulls out the first element of the sequence */ +/* Shift out first element of the sequence: */ CV_IMPL void cvSeqPopFront( CvSeq *seq, void *element ) { @@ -1446,8 +1453,8 @@ cvSeqPopFront( CvSeq *seq, void *element ) __END__; } -/* inserts new element in the middle of the sequence */ -CV_IMPL char* +/* Insert new element in middle of sequence: */ +CV_IMPL schar* cvSeqInsert( CvSeq *seq, int before_index, void *element ) { int elem_size; @@ -1455,7 +1462,7 @@ cvSeqInsert( CvSeq *seq, int before_index, void *element ) CvSeqBlock *block; int delta_index; int total; - char* ret_ptr = 0; + schar* ret_ptr = 0; CV_FUNCNAME( "cvSeqInsert" ); @@ -1485,7 +1492,7 @@ cvSeqInsert( CvSeq *seq, int before_index, void *element ) if( before_index >= total >> 1 ) { - char *ptr = seq->ptr + elem_size; + schar *ptr = seq->ptr + elem_size; if( ptr > seq->block_max ) { @@ -1509,7 +1516,7 @@ cvSeqInsert( CvSeq *seq, int before_index, void *element ) memcpy( block->data, prev_block->data + block_size - elem_size, elem_size ); block = prev_block; - /* check that we don't fall in the infinite loop */ + /* Check that we don't fall into an infinite loop: */ assert( block != seq->first->prev ); } @@ -1547,7 +1554,8 @@ cvSeqInsert( CvSeq *seq, int before_index, void *element ) memmove( block->data, block->data + elem_size, block_size - elem_size ); memcpy( block->data + block_size - elem_size, next_block->data, elem_size ); block = next_block; - /* check that we don't fall in the infinite loop */ + + /* Check that we don't fall into an infinite loop: */ assert( block != seq->first ); } @@ -1569,11 +1577,11 @@ cvSeqInsert( CvSeq *seq, int before_index, void *element ) } -/* removes element from the sequence */ +/* Removes element from sequence: */ CV_IMPL void cvSeqRemove( CvSeq *seq, int index ) { - char *ptr; + schar *ptr; int elem_size; int block_size; CvSeqBlock *block; @@ -1661,7 +1669,7 @@ cvSeqRemove( CvSeq *seq, int index ) } -/* adds several elements to the end or in the beginning of sequence */ +/* Add several elements to the beginning or end of a sequence: */ CV_IMPL void cvSeqPushMulti( CvSeq *seq, void *_elements, int count, int front ) { @@ -1707,11 +1715,11 @@ cvSeqPushMulti( CvSeq *seq, void *_elements, int count, int front ) else { CvSeqBlock* block = seq->first; - + while( count > 0 ) { int delta; - + if( !block || block->start_index == 0 ) { CV_CALL( icvGrowSeq( seq, 1 )); @@ -1737,7 +1745,7 @@ cvSeqPushMulti( CvSeq *seq, void *_elements, int count, int front ) } -/* removes several elements from the end of sequence */ +/* Remove several elements from the end of sequence: */ CV_IMPL void cvSeqPopMulti( CvSeq *seq, void *_elements, int count, int front ) { @@ -1813,7 +1821,7 @@ cvSeqPopMulti( CvSeq *seq, void *_elements, int count, int front ) } -/* removes all elements from the sequence */ +/* Remove all elements from a sequence: */ CV_IMPL void cvClearSeq( CvSeq *seq ) { @@ -1833,15 +1841,15 @@ CV_IMPL CvSeq* cvSeqSlice( const CvSeq* seq, CvSlice slice, CvMemStorage* storage, int copy_data ) { CvSeq* subseq = 0; - + CV_FUNCNAME("cvSeqSlice"); __BEGIN__; - + int elem_size, count, length; CvSeqReader reader; CvSeqBlock *block, *first_block = 0, *last_block = 0; - + if( !CV_IS_SEQ(seq) ) CV_ERROR( CV_StsBadArg, "Invalid sequence header" ); @@ -1873,7 +1881,7 @@ cvSeqSlice( const CvSeq* seq, CvSlice slice, CvMemStorage* storage, int copy_dat do { int bl = MIN( count, length ); - + if( !copy_data ) { block = (CvSeqBlock*)cvMemStorageAlloc( storage, sizeof(*block) ); @@ -1903,14 +1911,14 @@ cvSeqSlice( const CvSeq* seq, CvSlice slice, CvMemStorage* storage, int copy_dat } while( length > 0 ); } - + __END__; return subseq; } -// Remove slice from the middle of the sequence +// Remove slice from the middle of the sequence. // !!! TODO !!! Implement more efficient algorithm CV_IMPL void cvSeqRemoveSlice( CvSeq* seq, CvSlice slice ) @@ -1987,14 +1995,14 @@ cvSeqRemoveSlice( CvSeq* seq, CvSlice slice ) } -// Inserts a new sequence into the middle of another sequence +// Insert a sequence into the middle of another sequence: // !!! TODO !!! Implement more efficient algorithm CV_IMPL void cvSeqInsertSlice( CvSeq* seq, int index, const CvArr* from_arr ) { CvSeqReader reader_to, reader_from; int i, elem_size, total, from_total; - + CV_FUNCNAME("cvSeqInsertSlice"); __BEGIN__; @@ -2022,7 +2030,7 @@ cvSeqInsertSlice( CvSeq* seq, int index, const CvArr* from_arr ) if( seq->elem_size != from->elem_size ) CV_ERROR( CV_StsUnmatchedSizes, - "Sizes of source and destination sequences' elements are different" ); + "Source and destination sequence element sizes are different." ); from_total = from->total; @@ -2084,8 +2092,8 @@ cvSeqInsertSlice( CvSeq* seq, int index, const CvArr* from_arr ) } // Sort the sequence using user-specified comparison function. -// The semantics is similar to qsort() function. The code is based -// on BSD system qsort(): +// The semantics is similar to qsort() function. +// The code is based on BSD system qsort(): // * Copyright (c) 1992, 1993 // * The Regents of the University of California. All rights reserved. // * @@ -2120,9 +2128,9 @@ cvSeqInsertSlice( CvSeq* seq, int index, const CvArr* from_arr ) typedef struct CvSeqReaderPos { CvSeqBlock* block; - char* ptr; - char* block_min; - char* block_max; + schar* ptr; + schar* block_min; + schar* block_max; } CvSeqReaderPos; @@ -2142,8 +2150,8 @@ CvSeqReaderPos; (reader).block_max = (pos).block_max; \ } -inline char* -icvMed3( char* a, char* b, char* c, CvCmpFunc cmp_func, void* aux ) +inline schar* +icvMed3( schar* a, schar* b, schar* c, CvCmpFunc cmp_func, void* aux ) { return cmp_func(a, b, aux) < 0 ? (cmp_func(b, c, aux) < 0 ? b : cmp_func(a, c, aux) < 0 ? c : a) @@ -2152,7 +2160,7 @@ icvMed3( char* a, char* b, char* c, CvCmpFunc cmp_func, void* aux ) CV_IMPL void cvSeqSort( CvSeq* seq, CvCmpFunc cmp_func, void* aux ) -{ +{ int elem_size; int isort_thresh = 7; CvSeqReader left, right; @@ -2168,7 +2176,7 @@ cvSeqSort( CvSeq* seq, CvCmpFunc cmp_func, void* aux ) CV_FUNCNAME( "cvSeqSort" ); __BEGIN__; - + if( !CV_IS_SEQ(seq) ) CV_ERROR( !seq ? CV_StsNullPtr : CV_StsBadArg, "Bad input sequence" ); @@ -2223,7 +2231,7 @@ cvSeqSort( CvSeq* seq, CvCmpFunc cmp_func, void* aux ) } while( ptr2.ptr != left.ptr ) { - char* cur = ptr2.ptr; + schar* cur = ptr2.ptr; CV_PREV_SEQ_ELEM( elem_size, ptr2 ); if( cmp_func( ptr2.ptr, cur, aux ) <= 0 ) break; @@ -2237,18 +2245,18 @@ cvSeqSort( CvSeq* seq, CvCmpFunc cmp_func, void* aux ) { CvSeqReader left0, left1, right0, right1; CvSeqReader tmp0, tmp1; - char *m1, *m2, *m3, *pivot; + schar *m1, *m2, *m3, *pivot; int swap_cnt = 0; int l, l0, l1, r, r0, r1; left0 = tmp0 = left; right0 = right1 = right; n /= elem_size; - + if( n > 40 ) { int d = n / 8; - char *p1, *p2, *p3; + schar *p1, *p2, *p3; p1 = tmp0.ptr; cvSetSeqReaderPos( &tmp0, d, 1 ); p2 = tmp0.ptr; @@ -2358,7 +2366,7 @@ cvSeqSort( CvSeq* seq, CvCmpFunc cmp_func, void* aux ) l1 = cvGetSeqReaderPos( &left1 ); if( l1 == 0 ) l1 = seq->total; - + n = MIN( l - l1, l1 - l0 ); if( n > 0 ) { @@ -2436,15 +2444,15 @@ cvSeqSort( CvSeq* seq, CvCmpFunc cmp_func, void* aux ) } -CV_IMPL char* +CV_IMPL schar* cvSeqSearch( CvSeq* seq, const void* _elem, CvCmpFunc cmp_func, int is_sorted, int* _idx, void* userdata ) { - char* result = 0; - const char* elem = (const char*)_elem; + schar* result = 0; + const schar* elem = (const schar*)_elem; int idx = -1; - - CV_FUNCNAME("cvSeqSort"); + + CV_FUNCNAME("cvSeqSearch"); __BEGIN__; @@ -2515,11 +2523,11 @@ cvSeqSearch( CvSeq* seq, const void* _elem, CvCmpFunc cmp_func, CV_ERROR( CV_StsNullPtr, "Null compare function" ); i = 0, j = total; - + while( j > i ) { int k = (i+j)>>1, code; - char* ptr = cvGetSeqElem( seq, k ); + schar* ptr = cvGetSeqElem( seq, k ); code = cmp_func( elem, ptr, userdata ); if( !code ) { @@ -2574,15 +2582,15 @@ cvSeqInvert( CvSeq* seq ) typedef struct CvPTreeNode { struct CvPTreeNode* parent; - char* element; + schar* element; int rank; } CvPTreeNode; -// the function splits the input sequence or set into one or more equivalence classes. +// This function splits the input sequence or set into one or more equivalence classes. // is_equal(a,b,...) returns non-zero if the two sequence elements -// belong to the same class. the function returns sequence of integers - +// belong to the same class. The function returns sequence of integers - // 0-based class indexes for each element. // // The algorithm is described in "Introduction to Algorithms" @@ -2594,7 +2602,7 @@ cvSeqPartition( const CvSeq* seq, CvMemStorage* storage, CvSeq** labels, CvSeq* result = 0; CvMemStorage* temp_storage = 0; int class_idx = 0; - + CV_FUNCNAME( "cvSeqPartition" ); __BEGIN__; @@ -2603,7 +2611,7 @@ cvSeqPartition( const CvSeq* seq, CvMemStorage* storage, CvSeq** labels, CvSeqReader reader, reader0; CvSeq* nodes; int i, j; - int is_set; + int is_set; if( !labels ) CV_ERROR( CV_StsNullPtr, "" ); @@ -2625,7 +2633,7 @@ cvSeqPartition( const CvSeq* seq, CvMemStorage* storage, CvSeq** labels, cvStartReadSeq( seq, &reader ); memset( &writer, 0, sizeof(writer)); - cvStartAppendToSeq( nodes, &writer ); + cvStartAppendToSeq( nodes, &writer ); // Initial O(N) pass. Make a forest of single-vertex trees. for( i = 0; i < seq->total; i++ ) @@ -2639,9 +2647,9 @@ cvSeqPartition( const CvSeq* seq, CvMemStorage* storage, CvSeq** labels, cvEndWriteSeq( &writer ); - // because in the next loop we will iterate + // Because in the next loop we will iterate // through all the sequence nodes each time, - // we do not need to initialize reader every time + // we do not need to initialize reader every time: cvStartReadSeq( nodes, &reader ); cvStartReadSeq( nodes, &reader0 ); @@ -2662,12 +2670,12 @@ cvSeqPartition( const CvSeq* seq, CvMemStorage* storage, CvSeq** labels, for( j = 0; j < nodes->total; j++ ) { CvPTreeNode* node2 = (CvPTreeNode*)reader.ptr; - + if( node2->element && node2 != node && is_equal( node->element, node2->element, userdata )) { CvPTreeNode* root2 = node2; - + // unite both trees while( root2->parent ) root2 = root2->parent; @@ -2684,7 +2692,7 @@ cvSeqPartition( const CvSeq* seq, CvMemStorage* storage, CvSeq** labels, } assert( root->parent == 0 ); - // compress path from node2 to the root + // Compress path from node2 to the root: while( node2->parent ) { CvPTreeNode* temp = node2; @@ -2692,7 +2700,7 @@ cvSeqPartition( const CvSeq* seq, CvMemStorage* storage, CvSeq** labels, temp->parent = root; } - // compress path from node to the root + // Compress path from node to the root: node2 = node; while( node2->parent ) { @@ -2716,7 +2724,7 @@ cvSeqPartition( const CvSeq* seq, CvMemStorage* storage, CvSeq** labels, { CvPTreeNode* node = (CvPTreeNode*)reader.ptr; int idx = -1; - + if( node->element ) { while( node->parent ) @@ -2746,7 +2754,7 @@ cvSeqPartition( const CvSeq* seq, CvMemStorage* storage, CvSeq** labels, * Set implementation * \****************************************************************************************/ -/* creates empty set */ +/* Creates empty set: */ CV_IMPL CvSet* cvCreateSet( int set_flags, int header_size, int elem_size, CvMemStorage * storage ) { @@ -2772,7 +2780,7 @@ cvCreateSet( int set_flags, int header_size, int elem_size, CvMemStorage * stora } -/* adds new element to the set */ +/* Add new element to the set: */ CV_IMPL int cvSetAdd( CvSet* set, CvSetElem* element, CvSetElem** inserted_element ) { @@ -2791,7 +2799,7 @@ cvSetAdd( CvSet* set, CvSetElem* element, CvSetElem** inserted_element ) { int count = set->total; int elem_size = set->elem_size; - char *ptr; + schar *ptr; CV_CALL( icvGrowSeq( (CvSeq *) set, 0 )); set->free_elems = (CvSetElem*) (ptr = set->ptr); @@ -2826,7 +2834,7 @@ cvSetAdd( CvSet* set, CvSetElem* element, CvSetElem** inserted_element ) } -/* removes element from the set given its index */ +/* Remove element from a set given element index: */ CV_IMPL void cvSetRemove( CvSet* set, int index ) { @@ -2844,7 +2852,7 @@ cvSetRemove( CvSet* set, int index ) } -/* removes all elements from the set */ +/* Remove all elements from a set: */ CV_IMPL void cvClearSet( CvSet* set ) { @@ -2864,7 +2872,7 @@ cvClearSet( CvSet* set ) * Graph implementation * \****************************************************************************************/ -/* creates new graph */ +/* Create a new graph: */ CV_IMPL CvGraph * cvCreateGraph( int graph_type, int header_size, int vtx_size, int edge_size, CvMemStorage * storage ) @@ -2878,10 +2886,12 @@ cvCreateGraph( int graph_type, int header_size, CvSet *vertices = 0; - if( header_size < (int)sizeof( CvGraph ) || - edge_size < (int)sizeof( CvGraphEdge ) || - vtx_size < (int)sizeof( CvGraphVtx )) + if( header_size < (int) sizeof( CvGraph ) + || edge_size < (int) sizeof( CvGraphEdge ) + || vtx_size < (int) sizeof( CvGraphVtx ) + ){ CV_ERROR( CV_StsBadSize, "" ); + } CV_CALL( vertices = cvCreateSet( graph_type, header_size, vtx_size, storage )); CV_CALL( edges = cvCreateSet( CV_SEQ_KIND_GENERIC | CV_SEQ_ELTYPE_GRAPH_EDGE, @@ -2896,7 +2906,7 @@ cvCreateGraph( int graph_type, int header_size, } -/* Removes all the vertices and edges from the graph */ +/* Remove all vertices and edges from a graph: */ CV_IMPL void cvClearGraph( CvGraph * graph ) { @@ -2914,7 +2924,7 @@ cvClearGraph( CvGraph * graph ) } -/* Adds vertex to the graph */ +/* Add a vertex to a graph: */ CV_IMPL int cvGraphAddVtx( CvGraph* graph, const CvGraphVtx* _vertex, CvGraphVtx** _inserted_vertex ) { @@ -2947,7 +2957,7 @@ cvGraphAddVtx( CvGraph* graph, const CvGraphVtx* _vertex, CvGraphVtx** _inserted } -/* Removes vertex from the graph together with incident edges */ +/* Remove a vertex from the graph together with its incident edges: */ CV_IMPL int cvGraphRemoveVtxByPtr( CvGraph* graph, CvGraphVtx* vtx ) { @@ -2980,7 +2990,7 @@ cvGraphRemoveVtxByPtr( CvGraph* graph, CvGraphVtx* vtx ) } -/* Removes vertex from the graph together with incident edges */ +/* Remove a vertex from the graph together with its incident edges: */ CV_IMPL int cvGraphRemoveVtx( CvGraph* graph, int index ) { @@ -3017,7 +3027,7 @@ cvGraphRemoveVtx( CvGraph* graph, int index ) } -/* Finds graph edge given pointers to the ending vertices */ +/* Find a graph edge given pointers to the ending vertices: */ CV_IMPL CvGraphEdge* cvFindGraphEdgeByPtr( const CvGraph* graph, const CvGraphVtx* start_vtx, @@ -3058,7 +3068,7 @@ cvFindGraphEdgeByPtr( const CvGraph* graph, } -/* Finds edge in the graph given indices of the ending vertices */ +/* Find an edge in the graph given indices of the ending vertices: */ CV_IMPL CvGraphEdge * cvFindGraphEdge( const CvGraph* graph, int start_idx, int end_idx ) { @@ -3084,8 +3094,10 @@ cvFindGraphEdge( const CvGraph* graph, int start_idx, int end_idx ) } -/* Connects the two given vertices if they were not connected before, - otherwise it returns the existing edge */ +/* Given two vertices, return the edge + * connecting them, creating it if it + * did not already exist: + */ CV_IMPL int cvGraphAddEdgeByPtr( CvGraph* graph, CvGraphVtx* start_vtx, CvGraphVtx* end_vtx, @@ -3155,8 +3167,10 @@ cvGraphAddEdgeByPtr( CvGraph* graph, return result; } -/* Connects the two given vertices if they were not connected before, - otherwise it returns the existing edge */ +/* Given two vertices, return the edge + * connecting them, creating it if it + * did not already exist: + */ CV_IMPL int cvGraphAddEdge( CvGraph* graph, int start_idx, int end_idx, @@ -3185,7 +3199,7 @@ cvGraphAddEdge( CvGraph* graph, } -/* Removes the graph edge connecting two given vertices */ +/* Remove the graph edge connecting two given vertices: */ CV_IMPL void cvGraphRemoveEdgeByPtr( CvGraph* graph, CvGraphVtx* start_vtx, CvGraphVtx* end_vtx ) { @@ -3250,7 +3264,7 @@ cvGraphRemoveEdgeByPtr( CvGraph* graph, CvGraphVtx* start_vtx, CvGraphVtx* end_v } -/* Removes the graph edge connecting two given vertices */ +/* Remove the graph edge connecting two given vertices: */ CV_IMPL void cvGraphRemoveEdge( CvGraph* graph, int start_idx, int end_idx ) { @@ -3273,7 +3287,7 @@ cvGraphRemoveEdge( CvGraph* graph, int start_idx, int end_idx ) } -/* Counts number of edges incident to the vertex */ +/* Count number of edges incident to a given vertex: */ CV_IMPL int cvGraphVtxDegreeByPtr( const CvGraph* graph, const CvGraphVtx* vertex ) { @@ -3299,7 +3313,7 @@ cvGraphVtxDegreeByPtr( const CvGraph* graph, const CvGraphVtx* vertex ) } -/* Counts number of edges incident to the vertex */ +/* Count number of edges incident to a given vertex: */ CV_IMPL int cvGraphVtxDegree( const CvGraph* graph, int vtx_idx ) { @@ -3344,7 +3358,7 @@ icvSeqElemsClearFlags( CvSeq* seq, int offset, int clear_mask ) CV_FUNCNAME("icvStartScanGraph"); __BEGIN__; - + CvSeqReader reader; int i, total, elem_size; @@ -3371,16 +3385,16 @@ icvSeqElemsClearFlags( CvSeq* seq, int offset, int clear_mask ) } -static char* +static schar* icvSeqFindNextElem( CvSeq* seq, int offset, int mask, int value, int* start_index ) { - char* elem_ptr = 0; - + schar* elem_ptr = 0; + CV_FUNCNAME("icvStartScanGraph"); __BEGIN__; - + CvSeqReader reader; int total, elem_size, index; @@ -3504,7 +3518,7 @@ CV_IMPL int cvNextGraphItem( CvGraphScanner* scanner ) { int code = -1; - + CV_FUNCNAME("cvNextGraphItem"); __BEGIN__; @@ -3544,10 +3558,10 @@ cvNextGraphItem( CvGraphScanner* scanner ) while( edge ) { dst = edge->vtx[vtx == edge->vtx[0]]; - + if( !CV_IS_GRAPH_EDGE_VISITED(edge) ) { - // check that the edge is outcoming + // Check that the edge is outgoing: if( !CV_IS_GRAPH_ORIENTED( scanner->graph ) || dst != edge->vtx[0] ) { edge->flags |= CV_GRAPH_ITEM_VISITED_FLAG; @@ -3560,7 +3574,7 @@ cvNextGraphItem( CvGraphScanner* scanner ) vtx->flags |= CV_GRAPH_SEARCH_TREE_NODE_FLAG; cvSeqPush( scanner->stack, &item ); - + if( scanner->mask & CV_GRAPH_TREE_EDGE ) { code = CV_GRAPH_TREE_EDGE; @@ -3667,7 +3681,7 @@ cvCloneGraph( const CvGraph* graph, CvMemStorage* storage ) int* flag_buffer = 0; CvGraphVtx** ptr_buffer = 0; CvGraph* result = 0; - + CV_FUNCNAME( "cvCloneGraph" ); __BEGIN__; @@ -3695,7 +3709,7 @@ cvCloneGraph( const CvGraph* graph, CvMemStorage* storage ) memcpy( result + sizeof(CvGraph), graph + sizeof(CvGraph), graph->header_size - sizeof(CvGraph)); - // pass 1. save flags, copy vertices + // Pass 1. Save flags, copy vertices: cvStartReadSeq( (CvSeq*)graph, &reader ); for( i = 0, k = 0; i < graph->total; i++ ) { @@ -3711,7 +3725,7 @@ cvCloneGraph( const CvGraph* graph, CvMemStorage* storage ) CV_NEXT_SEQ_ELEM( vtx_size, reader ); } - // pass 2. copy edges + // Pass 2. Copy edges: cvStartReadSeq( (CvSeq*)graph->edges, &reader ); for( i = 0; i < graph->edges->total; i++ ) { @@ -3727,7 +3741,7 @@ cvCloneGraph( const CvGraph* graph, CvMemStorage* storage ) CV_NEXT_SEQ_ELEM( edge_size, reader ); } - // pass 3. restore flags + // Pass 3. Restore flags: cvStartReadSeq( (CvSeq*)graph, &reader ); for( i = 0, k = 0; i < graph->edges->total; i++ ) { @@ -3755,7 +3769,7 @@ cvCloneGraph( const CvGraph* graph, CvMemStorage* storage ) * Working with sequence tree * \****************************************************************************************/ -// Gathers pointers to all the sequences, accessible from the , to the single sequence. +// Gather pointers to all the sequences, accessible from the , to the single sequence. CV_IMPL CvSeq* cvTreeToNodeSeq( const void* first, int header_size, CvMemStorage* storage ) { @@ -3793,11 +3807,11 @@ cvTreeToNodeSeq( const void* first, int header_size, CvMemStorage* storage ) typedef struct CvTreeNode { - int flags; /* micsellaneous flags */ - int header_size; /* size of sequence header */ - struct CvTreeNode* h_prev; /* previous sequence */ - struct CvTreeNode* h_next; /* next sequence */ - struct CvTreeNode* v_prev; /* 2nd previous sequence */ + int flags; /* micsellaneous flags */ + int header_size; /* size of sequence header */ + struct CvTreeNode* h_prev; /* previous sequence */ + struct CvTreeNode* h_next; /* next sequence */ + struct CvTreeNode* v_prev; /* 2nd previous sequence */ struct CvTreeNode* v_next; /* 2nd next sequence */ } CvTreeNode; @@ -3806,7 +3820,7 @@ CvTreeNode; // Insert contour into tree given certain parent sequence. // If parent is equal to frame (the most external contour), -// then added contour will have null pointer to parent. +// then added contour will have null pointer to parent: CV_IMPL void cvInsertNodeIntoTree( void* _node, void* _parent, void* _frame ) { @@ -3833,7 +3847,7 @@ cvInsertNodeIntoTree( void* _node, void* _parent, void* _frame ) } -// Removes contour from tree (together with the contour children). +// Remove contour from tree, together with the contour's children: CV_IMPL void cvRemoveNodeFromTree( void* _node, void* _frame ) { @@ -3879,7 +3893,7 @@ cvInitTreeNodeIterator( CvTreeNodeIterator* treeIterator, CV_FUNCNAME("icvInitTreeNodeIterator"); __BEGIN__; - + if( !treeIterator || !first ) CV_ERROR( CV_StsNullPtr, "" ); @@ -3898,11 +3912,11 @@ CV_IMPL void* cvNextTreeNode( CvTreeNodeIterator* treeIterator ) { CvTreeNode* prevNode = 0; - + CV_FUNCNAME("cvNextTreeNode"); __BEGIN__; - + CvTreeNode* node; int level; @@ -3947,7 +3961,7 @@ CV_IMPL void* cvPrevTreeNode( CvTreeNodeIterator* treeIterator ) { CvTreeNode* prevNode = 0; - + CV_FUNCNAME("cvPrevTreeNode"); __BEGIN__; @@ -3956,11 +3970,11 @@ cvPrevTreeNode( CvTreeNodeIterator* treeIterator ) int level; if( !treeIterator ) - CV_ERROR( CV_StsNullPtr, "" ); + CV_ERROR( CV_StsNullPtr, "" ); prevNode = node = (CvTreeNode*)treeIterator->node; level = treeIterator->level; - + if( node ) { if( !node->h_prev )