1 #include "test_precomp.hpp" 2 3 using namespace cv; 4 using namespace std; 5 6 typedef struct CvTsSimpleSeq 7 { 8 schar* array; 9 int count; 10 int max_count; 11 int elem_size; 12 } CvTsSimpleSeq; 13 14 15 static CvTsSimpleSeq* cvTsCreateSimpleSeq( int max_count, int elem_size ) 16 { 17 CvTsSimpleSeq* seq = (CvTsSimpleSeq*)cvAlloc( sizeof(*seq) + max_count * elem_size ); 18 seq->elem_size = elem_size; 19 seq->max_count = max_count; 20 seq->count = 0; 21 seq->array = (schar*)(seq + 1); 22 return seq; 23 } 24 25 26 static void cvTsReleaseSimpleSeq( CvTsSimpleSeq** seq ) 27 { 28 cvFree( seq ); 29 } 30 31 32 static schar* cvTsSimpleSeqElem( CvTsSimpleSeq* seq, int index ) 33 { 34 assert( 0 <= index && index < seq->count ); 35 return seq->array + index * seq->elem_size; 36 } 37 38 39 static void cvTsClearSimpleSeq( CvTsSimpleSeq* seq ) 40 { 41 seq->count = 0; 42 } 43 44 45 static void cvTsSimpleSeqShiftAndCopy( CvTsSimpleSeq* seq, int from_idx, int to_idx, void* elem=0 ) 46 { 47 int elem_size = seq->elem_size; 48 49 if( from_idx == to_idx ) 50 return; 51 assert( (from_idx > to_idx && !elem) || (from_idx < to_idx && elem) ); 52 53 if( from_idx < seq->count ) 54 { 55 memmove( seq->array + to_idx*elem_size, seq->array + from_idx*elem_size, 56 (seq->count - from_idx)*elem_size ); 57 } 58 seq->count += to_idx - from_idx; 59 if( elem && to_idx > from_idx ) 60 memcpy( seq->array + from_idx*elem_size, elem, (to_idx - from_idx)*elem_size ); 61 } 62 63 static void cvTsSimpleSeqInvert( CvTsSimpleSeq* seq ) 64 { 65 int i, k, len = seq->count, elem_size = seq->elem_size; 66 schar *data = seq->array, t; 67 68 for( i = 0; i < len/2; i++ ) 69 { 70 schar* a = data + i*elem_size; 71 schar* b = data + (len - i - 1)*elem_size; 72 for( k = 0; k < elem_size; k++ ) 73 CV_SWAP( a[k], b[k], t ); 74 } 75 } 76 77 /****************************************************************************************\ 78 * simple cvset implementation * 79 \****************************************************************************************/ 80 81 typedef struct CvTsSimpleSet 82 { 83 schar* array; 84 int count, max_count; 85 int elem_size; 86 int* free_stack; 87 int free_count; 88 } CvTsSimpleSet; 89 90 91 static void cvTsClearSimpleSet( CvTsSimpleSet* set_header ) 92 { 93 int i; 94 int elem_size = set_header->elem_size; 95 96 for( i = 0; i < set_header->max_count; i++ ) 97 { 98 set_header->array[i*elem_size] = 0; 99 set_header->free_stack[i] = set_header->max_count - i - 1; 100 } 101 set_header->free_count = set_header->max_count; 102 set_header->count = 0; 103 } 104 105 106 static CvTsSimpleSet* cvTsCreateSimpleSet( int max_count, int elem_size ) 107 { 108 CvTsSimpleSet* set_header = (CvTsSimpleSet*)cvAlloc( sizeof(*set_header) + max_count * 109 (elem_size + 1 + sizeof(int))); 110 set_header->elem_size = elem_size + 1; 111 set_header->max_count = max_count; 112 set_header->free_stack = (int*)(set_header + 1); 113 set_header->array = (schar*)(set_header->free_stack + max_count); 114 115 cvTsClearSimpleSet( set_header ); 116 return set_header; 117 } 118 119 120 static void cvTsReleaseSimpleSet( CvTsSimpleSet** set_header ) 121 { 122 cvFree( set_header ); 123 } 124 125 126 static schar* cvTsSimpleSetFind( CvTsSimpleSet* set_header, int index ) 127 { 128 int idx = index * set_header->elem_size; 129 assert( 0 <= index && index < set_header->max_count ); 130 return set_header->array[idx] ? set_header->array + idx + 1 : 0; 131 } 132 133 134 static int cvTsSimpleSetAdd( CvTsSimpleSet* set_header, void* elem ) 135 { 136 int idx, idx2; 137 assert( set_header->free_count > 0 ); 138 139 idx = set_header->free_stack[--set_header->free_count]; 140 idx2 = idx * set_header->elem_size; 141 assert( set_header->array[idx2] == 0 ); 142 set_header->array[idx2] = 1; 143 if( set_header->elem_size > 1 ) 144 memcpy( set_header->array + idx2 + 1, elem, set_header->elem_size - 1 ); 145 set_header->count = MAX( set_header->count, idx + 1 ); 146 147 return idx; 148 } 149 150 151 static void cvTsSimpleSetRemove( CvTsSimpleSet* set_header, int index ) 152 { 153 assert( set_header->free_count < set_header->max_count && 154 0 <= index && index < set_header->max_count ); 155 assert( set_header->array[index * set_header->elem_size] == 1 ); 156 157 set_header->free_stack[set_header->free_count++] = index; 158 set_header->array[index * set_header->elem_size] = 0; 159 } 160 161 162 /****************************************************************************************\ 163 * simple graph implementation * 164 \****************************************************************************************/ 165 166 typedef struct CvTsSimpleGraph 167 { 168 char* matrix; 169 int edge_size; 170 int oriented; 171 CvTsSimpleSet* vtx; 172 } CvTsSimpleGraph; 173 174 175 static void cvTsClearSimpleGraph( CvTsSimpleGraph* graph ) 176 { 177 int max_vtx_count = graph->vtx->max_count; 178 cvTsClearSimpleSet( graph->vtx ); 179 memset( graph->matrix, 0, max_vtx_count * max_vtx_count * graph->edge_size ); 180 } 181 182 183 static CvTsSimpleGraph* cvTsCreateSimpleGraph( int max_vtx_count, int vtx_size, 184 int edge_size, int oriented ) 185 { 186 CvTsSimpleGraph* graph; 187 188 assert( max_vtx_count > 1 && vtx_size >= 0 && edge_size >= 0 ); 189 graph = (CvTsSimpleGraph*)cvAlloc( sizeof(*graph) + 190 max_vtx_count * max_vtx_count * (edge_size + 1)); 191 graph->vtx = cvTsCreateSimpleSet( max_vtx_count, vtx_size ); 192 graph->edge_size = edge_size + 1; 193 graph->matrix = (char*)(graph + 1); 194 graph->oriented = oriented; 195 196 cvTsClearSimpleGraph( graph ); 197 return graph; 198 } 199 200 201 static void cvTsReleaseSimpleGraph( CvTsSimpleGraph** graph ) 202 { 203 if( *graph ) 204 { 205 cvTsReleaseSimpleSet( &(graph[0]->vtx) ); 206 cvFree( graph ); 207 } 208 } 209 210 211 static int cvTsSimpleGraphAddVertex( CvTsSimpleGraph* graph, void* vertex ) 212 { 213 return cvTsSimpleSetAdd( graph->vtx, vertex ); 214 } 215 216 217 static void cvTsSimpleGraphRemoveVertex( CvTsSimpleGraph* graph, int index ) 218 { 219 int i, max_vtx_count = graph->vtx->max_count; 220 int edge_size = graph->edge_size; 221 cvTsSimpleSetRemove( graph->vtx, index ); 222 223 /* remove all the corresponding edges */ 224 for( i = 0; i < max_vtx_count; i++ ) 225 { 226 graph->matrix[(i*max_vtx_count + index)*edge_size] = 227 graph->matrix[(index*max_vtx_count + i)*edge_size] = 0; 228 } 229 } 230 231 232 static void cvTsSimpleGraphAddEdge( CvTsSimpleGraph* graph, int idx1, int idx2, void* edge ) 233 { 234 int i, t, n = graph->oriented ? 1 : 2; 235 236 assert( cvTsSimpleSetFind( graph->vtx, idx1 ) && 237 cvTsSimpleSetFind( graph->vtx, idx2 )); 238 239 for( i = 0; i < n; i++ ) 240 { 241 int ofs = (idx1*graph->vtx->max_count + idx2)*graph->edge_size; 242 assert( graph->matrix[ofs] == 0 ); 243 graph->matrix[ofs] = 1; 244 if( graph->edge_size > 1 ) 245 memcpy( graph->matrix + ofs + 1, edge, graph->edge_size - 1 ); 246 247 CV_SWAP( idx1, idx2, t ); 248 } 249 } 250 251 252 static void cvTsSimpleGraphRemoveEdge( CvTsSimpleGraph* graph, int idx1, int idx2 ) 253 { 254 int i, t, n = graph->oriented ? 1 : 2; 255 256 assert( cvTsSimpleSetFind( graph->vtx, idx1 ) && 257 cvTsSimpleSetFind( graph->vtx, idx2 )); 258 259 for( i = 0; i < n; i++ ) 260 { 261 int ofs = (idx1*graph->vtx->max_count + idx2)*graph->edge_size; 262 assert( graph->matrix[ofs] == 1 ); 263 graph->matrix[ofs] = 0; 264 CV_SWAP( idx1, idx2, t ); 265 } 266 } 267 268 269 static schar* cvTsSimpleGraphFindVertex( CvTsSimpleGraph* graph, int index ) 270 { 271 return cvTsSimpleSetFind( graph->vtx, index ); 272 } 273 274 275 static char* cvTsSimpleGraphFindEdge( CvTsSimpleGraph* graph, int idx1, int idx2 ) 276 { 277 if( cvTsSimpleGraphFindVertex( graph, idx1 ) && 278 cvTsSimpleGraphFindVertex( graph, idx2 )) 279 { 280 char* edge = graph->matrix + (idx1 * graph->vtx->max_count + idx2)*graph->edge_size; 281 if( edge[0] ) return edge + 1; 282 } 283 return 0; 284 } 285 286 287 static int cvTsSimpleGraphVertexDegree( CvTsSimpleGraph* graph, int index ) 288 { 289 int i, count = 0; 290 int edge_size = graph->edge_size; 291 int max_vtx_count = graph->vtx->max_count; 292 assert( cvTsSimpleGraphFindVertex( graph, index ) != 0 ); 293 294 for( i = 0; i < max_vtx_count; i++ ) 295 { 296 count += graph->matrix[(i*max_vtx_count + index)*edge_size] + 297 graph->matrix[(index*max_vtx_count + i)*edge_size]; 298 } 299 300 if( !graph->oriented ) 301 { 302 assert( count % 2 == 0 ); 303 count /= 2; 304 } 305 return count; 306 } 307 308 309 ///////////////////////////////////// the tests ////////////////////////////////// 310 311 #define CV_TS_SEQ_CHECK_CONDITION( expr, err_msg ) \ 312 if( !(expr) ) \ 313 { \ 314 set_error_context( #expr, err_msg, __FILE__, __LINE__ ); \ 315 ts->set_failed_test_info( cvtest::TS::FAIL_INVALID_OUTPUT );\ 316 throw -1; \ 317 } 318 319 class Core_DynStructBaseTest : public cvtest::BaseTest 320 { 321 public: 322 Core_DynStructBaseTest(); 323 virtual ~Core_DynStructBaseTest(); 324 bool can_do_fast_forward(); 325 void clear(); 326 327 protected: 328 int read_params( CvFileStorage* fs ); 329 void run_func(void); 330 void set_error_context( const char* condition, 331 const char* err_msg, 332 const char* file, int line ); 333 int test_seq_block_consistence( int _struct_idx, CvSeq* seq, int total ); 334 void update_progressbar(); 335 336 int struct_count, max_struct_size, iterations, generations; 337 int min_log_storage_block_size, max_log_storage_block_size; 338 int min_log_elem_size, max_log_elem_size; 339 int gen, struct_idx, iter; 340 int test_progress; 341 int64 start_time; 342 double cpu_freq; 343 vector<void*> cxcore_struct; 344 vector<void*> simple_struct; 345 Ptr<CvMemStorage> storage; 346 }; 347 348 349 Core_DynStructBaseTest::Core_DynStructBaseTest() 350 { 351 struct_count = 2; 352 max_struct_size = 2000; 353 min_log_storage_block_size = 7; 354 max_log_storage_block_size = 12; 355 min_log_elem_size = 0; 356 max_log_elem_size = 8; 357 generations = 10; 358 iterations = max_struct_size*2; 359 gen = struct_idx = iter = -1; 360 test_progress = -1; 361 } 362 363 364 Core_DynStructBaseTest::~Core_DynStructBaseTest() 365 { 366 clear(); 367 } 368 369 370 void Core_DynStructBaseTest::run_func() 371 { 372 } 373 374 bool Core_DynStructBaseTest::can_do_fast_forward() 375 { 376 return false; 377 } 378 379 380 void Core_DynStructBaseTest::clear() 381 { 382 cvtest::BaseTest::clear(); 383 } 384 385 386 int Core_DynStructBaseTest::read_params( CvFileStorage* fs ) 387 { 388 int code = cvtest::BaseTest::read_params( fs ); 389 double sqrt_scale = sqrt(ts->get_test_case_count_scale()); 390 if( code < 0 ) 391 return code; 392 393 struct_count = cvReadInt( find_param( fs, "struct_count" ), struct_count ); 394 max_struct_size = cvReadInt( find_param( fs, "max_struct_size" ), max_struct_size ); 395 generations = cvReadInt( find_param( fs, "generations" ), generations ); 396 iterations = cvReadInt( find_param( fs, "iterations" ), iterations ); 397 generations = cvRound(generations*sqrt_scale); 398 iterations = cvRound(iterations*sqrt_scale); 399 400 min_log_storage_block_size = cvReadInt( find_param( fs, "min_log_storage_block_size" ), 401 min_log_storage_block_size ); 402 max_log_storage_block_size = cvReadInt( find_param( fs, "max_log_storage_block_size" ), 403 max_log_storage_block_size ); 404 min_log_elem_size = cvReadInt( find_param( fs, "min_log_elem_size" ), min_log_elem_size ); 405 max_log_elem_size = cvReadInt( find_param( fs, "max_log_elem_size" ), max_log_elem_size ); 406 407 struct_count = cvtest::clipInt( struct_count, 1, 100 ); 408 max_struct_size = cvtest::clipInt( max_struct_size, 1, 1<<20 ); 409 generations = cvtest::clipInt( generations, 1, 100 ); 410 iterations = cvtest::clipInt( iterations, 100, 1<<20 ); 411 412 min_log_storage_block_size = cvtest::clipInt( min_log_storage_block_size, 7, 20 ); 413 max_log_storage_block_size = cvtest::clipInt( max_log_storage_block_size, 414 min_log_storage_block_size, 20 ); 415 416 min_log_elem_size = cvtest::clipInt( min_log_elem_size, 0, 8 ); 417 max_log_elem_size = cvtest::clipInt( max_log_elem_size, min_log_elem_size, 10 ); 418 419 return 0; 420 } 421 422 423 void Core_DynStructBaseTest::update_progressbar() 424 { 425 int64 t; 426 427 if( test_progress < 0 ) 428 { 429 test_progress = 0; 430 cpu_freq = cv::getTickFrequency(); 431 start_time = cv::getTickCount(); 432 } 433 434 t = cv::getTickCount(); 435 test_progress = update_progress( test_progress, 0, 0, (double)(t - start_time)/cpu_freq ); 436 } 437 438 439 void Core_DynStructBaseTest::set_error_context( const char* condition, 440 const char* err_msg, 441 const char* filename, int lineno ) 442 { 443 ts->printf( cvtest::TS::LOG, "file %s, line %d: %s\n(\"%s\" failed).\n" 444 "generation = %d, struct_idx = %d, iter = %d\n", 445 filename, lineno, err_msg, condition, gen, struct_idx, iter ); 446 ts->set_failed_test_info( cvtest::TS::FAIL_INVALID_OUTPUT ); 447 } 448 449 450 int Core_DynStructBaseTest::test_seq_block_consistence( int _struct_idx, CvSeq* seq, int total ) 451 { 452 int sum = 0; 453 struct_idx = _struct_idx; 454 455 CV_TS_SEQ_CHECK_CONDITION( seq != 0, "Null sequence pointer" ); 456 457 if( seq->first ) 458 { 459 CvSeqBlock* block = seq->first; 460 CvSeqBlock* prev_block = block->prev; 461 462 int delta_idx = seq->first->start_index; 463 464 for( ;; ) 465 { 466 CV_TS_SEQ_CHECK_CONDITION( sum == block->start_index - delta_idx && 467 block->count > 0 && block->prev == prev_block && 468 prev_block->next == block, 469 "sequence blocks are inconsistent" ); 470 sum += block->count; 471 prev_block = block; 472 block = block->next; 473 if( block == seq->first ) break; 474 } 475 476 CV_TS_SEQ_CHECK_CONDITION( block->prev->count * seq->elem_size + 477 block->prev->data <= seq->block_max, 478 "block->data or block_max pointer are incorrect" ); 479 } 480 481 CV_TS_SEQ_CHECK_CONDITION( seq->total == sum && sum == total, 482 "total number of elements is incorrect" ); 483 484 return 0; 485 } 486 487 488 /////////////////////////////////// sequence tests //////////////////////////////////// 489 490 class Core_SeqBaseTest : public Core_DynStructBaseTest 491 { 492 public: 493 Core_SeqBaseTest(); 494 void clear(); 495 void run( int ); 496 497 protected: 498 int test_multi_create(); 499 int test_get_seq_elem( int _struct_idx, int iters ); 500 int test_get_seq_reading( int _struct_idx, int iters ); 501 int test_seq_ops( int iters ); 502 }; 503 504 505 Core_SeqBaseTest::Core_SeqBaseTest() 506 { 507 } 508 509 510 void Core_SeqBaseTest::clear() 511 { 512 for( size_t i = 0; i < simple_struct.size(); i++ ) 513 cvTsReleaseSimpleSeq( (CvTsSimpleSeq**)&simple_struct[i] ); 514 Core_DynStructBaseTest::clear(); 515 } 516 517 518 int Core_SeqBaseTest::test_multi_create() 519 { 520 vector<CvSeqWriter> writer(struct_count); 521 vector<int> pos(struct_count); 522 vector<int> index(struct_count); 523 int cur_count, elem_size; 524 RNG& rng = ts->get_rng(); 525 526 for( int i = 0; i < struct_count; i++ ) 527 { 528 double t; 529 CvTsSimpleSeq* sseq; 530 531 pos[i] = -1; 532 index[i] = i; 533 534 t = cvtest::randReal(rng)*(max_log_elem_size - min_log_elem_size) + min_log_elem_size; 535 elem_size = cvRound( exp(t * CV_LOG2) ); 536 elem_size = MIN( elem_size, (int)(storage->block_size - sizeof(void*) - 537 sizeof(CvSeqBlock) - sizeof(CvMemBlock)) ); 538 539 cvTsReleaseSimpleSeq( (CvTsSimpleSeq**)&simple_struct[i] ); 540 simple_struct[i] = sseq = cvTsCreateSimpleSeq( max_struct_size, elem_size ); 541 cxcore_struct[i] = 0; 542 sseq->count = cvtest::randInt( rng ) % max_struct_size; 543 Mat m( 1, MAX(sseq->count,1)*elem_size, CV_8UC1, sseq->array ); 544 cvtest::randUni( rng, m, Scalar::all(0), Scalar::all(256) ); 545 } 546 547 for( cur_count = struct_count; cur_count > 0; cur_count-- ) 548 { 549 for(;;) 550 { 551 int k = cvtest::randInt( rng ) % cur_count; 552 struct_idx = index[k]; 553 CvTsSimpleSeq* sseq = (CvTsSimpleSeq*)simple_struct[struct_idx]; 554 555 if( pos[struct_idx] < 0 ) 556 { 557 int hdr_size = (cvtest::randInt(rng) % 10)*4 + sizeof(CvSeq); 558 hdr_size = MIN( hdr_size, (int)(storage->block_size - sizeof(CvMemBlock)) ); 559 elem_size = sseq->elem_size; 560 561 if( cvtest::randInt(rng) % 2 ) 562 { 563 cvStartWriteSeq( 0, hdr_size, elem_size, storage, &writer[struct_idx] ); 564 } 565 else 566 { 567 CvSeq* s; 568 s = cvCreateSeq( 0, hdr_size, elem_size, storage ); 569 cvStartAppendToSeq( s, &writer[struct_idx] ); 570 } 571 572 cvSetSeqBlockSize( writer[struct_idx].seq, cvtest::randInt( rng ) % 10000 ); 573 pos[struct_idx] = 0; 574 } 575 576 update_progressbar(); 577 if( pos[struct_idx] == sseq->count ) 578 { 579 cxcore_struct[struct_idx] = cvEndWriteSeq( &writer[struct_idx] ); 580 /* del index */ 581 for( ; k < cur_count-1; k++ ) 582 index[k] = index[k+1]; 583 break; 584 } 585 586 { 587 schar* el = cvTsSimpleSeqElem( sseq, pos[struct_idx] ); 588 CV_WRITE_SEQ_ELEM_VAR( el, writer[struct_idx] ); 589 } 590 pos[struct_idx]++; 591 } 592 } 593 594 return 0; 595 } 596 597 598 int Core_SeqBaseTest::test_get_seq_elem( int _struct_idx, int iters ) 599 { 600 RNG& rng = ts->get_rng(); 601 602 CvSeq* seq = (CvSeq*)cxcore_struct[_struct_idx]; 603 CvTsSimpleSeq* sseq = (CvTsSimpleSeq*)simple_struct[_struct_idx]; 604 struct_idx = _struct_idx; 605 606 assert( seq->total == sseq->count ); 607 608 if( sseq->count == 0 ) 609 return 0; 610 611 for( int i = 0; i < iters; i++ ) 612 { 613 int idx = cvtest::randInt(rng) % (sseq->count*3) - sseq->count*3/2; 614 int idx0 = (unsigned)idx < (unsigned)(sseq->count) ? idx : idx < 0 ? 615 idx + sseq->count : idx - sseq->count; 616 int bad_range = (unsigned)idx0 >= (unsigned)(sseq->count); 617 schar* elem; 618 elem = cvGetSeqElem( seq, idx ); 619 620 if( bad_range ) 621 { 622 CV_TS_SEQ_CHECK_CONDITION( elem == 0, 623 "cvGetSeqElem doesn't " 624 "handle \"out of range\" properly" ); 625 } 626 else 627 { 628 CV_TS_SEQ_CHECK_CONDITION( elem != 0 && 629 !memcmp( elem, cvTsSimpleSeqElem(sseq, idx0), sseq->elem_size ), 630 "cvGetSeqElem returns wrong element" ); 631 632 idx = cvSeqElemIdx(seq, elem ); 633 CV_TS_SEQ_CHECK_CONDITION( idx >= 0 && idx == idx0, 634 "cvSeqElemIdx is incorrect" ); 635 } 636 } 637 638 return 0; 639 } 640 641 642 int Core_SeqBaseTest::test_get_seq_reading( int _struct_idx, int iters ) 643 { 644 const int max_val = 3*5 + 2; 645 CvSeq* seq = (CvSeq*)cxcore_struct[_struct_idx]; 646 CvTsSimpleSeq* sseq = (CvTsSimpleSeq*)simple_struct[_struct_idx]; 647 int total = seq->total; 648 RNG& rng = ts->get_rng(); 649 CvSeqReader reader; 650 vector<schar> _elem(sseq->elem_size); 651 schar* elem = &_elem[0]; 652 653 assert( total == sseq->count ); 654 this->struct_idx = _struct_idx; 655 656 int pos = cvtest::randInt(rng) % 2; 657 cvStartReadSeq( seq, &reader, pos ); 658 659 if( total == 0 ) 660 { 661 CV_TS_SEQ_CHECK_CONDITION( reader.ptr == 0, "Empty sequence reader pointer is not NULL" ); 662 return 0; 663 } 664 665 pos = pos ? seq->total - 1 : 0; 666 667 CV_TS_SEQ_CHECK_CONDITION( pos == cvGetSeqReaderPos(&reader), 668 "initial reader position is wrong" ); 669 670 for( iter = 0; iter < iters; iter++ ) 671 { 672 int op = cvtest::randInt(rng) % max_val; 673 674 if( op >= max_val - 2 ) 675 { 676 int new_pos, new_pos0; 677 int bad_range; 678 int is_relative = op == max_val - 1; 679 680 new_pos = cvtest::randInt(rng) % (total*2) - total; 681 new_pos0 = new_pos + (is_relative ? pos : 0 ); 682 683 if( new_pos0 < 0 ) new_pos0 += total; 684 if( new_pos0 >= total ) new_pos0 -= total; 685 686 bad_range = (unsigned)new_pos0 >= (unsigned)total; 687 cvSetSeqReaderPos( &reader, new_pos, is_relative ); 688 689 if( !bad_range ) 690 { 691 CV_TS_SEQ_CHECK_CONDITION( new_pos0 == cvGetSeqReaderPos( &reader ), 692 "cvset reader position doesn't work" ); 693 pos = new_pos0; 694 } 695 else 696 { 697 CV_TS_SEQ_CHECK_CONDITION( pos == cvGetSeqReaderPos( &reader ), 698 "reader doesn't stay at the current position after wrong positioning" ); 699 } 700 } 701 else 702 { 703 int direction = (op % 3) - 1; 704 memcpy( elem, reader.ptr, sseq->elem_size ); 705 706 if( direction > 0 ) 707 { 708 CV_NEXT_SEQ_ELEM( sseq->elem_size, reader ); 709 } 710 else if( direction < 0 ) 711 { 712 CV_PREV_SEQ_ELEM( sseq->elem_size, reader ); 713 } 714 715 CV_TS_SEQ_CHECK_CONDITION( memcmp(elem, cvTsSimpleSeqElem(sseq, pos), 716 sseq->elem_size) == 0, "reading is incorrect" ); 717 pos += direction; 718 if( -pos > 0 ) pos += total; 719 if( pos >= total ) pos -= total; 720 721 CV_TS_SEQ_CHECK_CONDITION( pos == cvGetSeqReaderPos( &reader ), 722 "reader doesn't move correctly after reading" ); 723 } 724 } 725 726 return 0; 727 } 728 729 730 int Core_SeqBaseTest::test_seq_ops( int iters ) 731 { 732 const int max_op = 14; 733 int max_elem_size = 0; 734 schar* elem2 = 0; 735 RNG& rng = ts->get_rng(); 736 737 for( int i = 0; i < struct_count; i++ ) 738 max_elem_size = MAX( max_elem_size, ((CvSeq*)cxcore_struct[i])->elem_size ); 739 740 vector<schar> elem_buf(max_struct_size*max_elem_size); 741 schar* elem = (schar*)&elem_buf[0]; 742 Mat elem_mat; 743 744 for( iter = 0; iter < iters; iter++ ) 745 { 746 struct_idx = cvtest::randInt(rng) % struct_count; 747 int op = cvtest::randInt(rng) % max_op; 748 CvSeq* seq = (CvSeq*)cxcore_struct[struct_idx]; 749 CvTsSimpleSeq* sseq = (CvTsSimpleSeq*)simple_struct[struct_idx]; 750 int elem_size = sseq->elem_size; 751 int whence = 0, pos = 0, count = 0; 752 753 switch( op ) 754 { 755 case 0: 756 case 1: 757 case 2: // push/pushfront/insert 758 if( sseq->count == sseq->max_count ) 759 break; 760 761 elem_mat = Mat(1, elem_size, CV_8U, elem); 762 cvtest::randUni( rng, elem_mat, cvScalarAll(0), cvScalarAll(255) ); 763 764 whence = op - 1; 765 if( whence < 0 ) 766 { 767 pos = 0; 768 cvSeqPushFront( seq, elem ); 769 } 770 else if( whence > 0 ) 771 { 772 pos = sseq->count; 773 cvSeqPush( seq, elem ); 774 } 775 else 776 { 777 pos = cvtest::randInt(rng) % (sseq->count + 1); 778 cvSeqInsert( seq, pos, elem ); 779 } 780 781 cvTsSimpleSeqShiftAndCopy( sseq, pos, pos + 1, elem ); 782 elem2 = cvGetSeqElem( seq, pos ); 783 CV_TS_SEQ_CHECK_CONDITION( elem2 != 0, "The inserted element could not be retrieved" ); 784 CV_TS_SEQ_CHECK_CONDITION( seq->total == sseq->count && 785 memcmp(elem2, cvTsSimpleSeqElem(sseq,pos), elem_size) == 0, 786 "The inserted sequence element is wrong" ); 787 break; 788 789 case 3: 790 case 4: 791 case 5: // pop/popfront/remove 792 if( sseq->count == 0 ) 793 break; 794 795 whence = op - 4; 796 if( whence < 0 ) 797 { 798 pos = 0; 799 cvSeqPopFront( seq, elem ); 800 } 801 else if( whence > 0 ) 802 { 803 pos = sseq->count-1; 804 cvSeqPop( seq, elem ); 805 } 806 else 807 { 808 pos = cvtest::randInt(rng) % sseq->count; 809 cvSeqRemove( seq, pos ); 810 } 811 812 if( whence != 0 ) 813 CV_TS_SEQ_CHECK_CONDITION( seq->total == sseq->count - 1 && 814 memcmp( elem, cvTsSimpleSeqElem(sseq,pos), elem_size) == 0, 815 "The popped sequence element isn't correct" ); 816 817 cvTsSimpleSeqShiftAndCopy( sseq, pos + 1, pos ); 818 819 if( sseq->count > 0 ) 820 { 821 elem2 = cvGetSeqElem( seq, pos < sseq->count ? pos : -1 ); 822 CV_TS_SEQ_CHECK_CONDITION( elem2 != 0, "GetSeqElem fails after removing the element" ); 823 824 CV_TS_SEQ_CHECK_CONDITION( memcmp( elem2, 825 cvTsSimpleSeqElem(sseq, pos - (pos == sseq->count)), elem_size) == 0, 826 "The first shifted element is not correct after removing another element" ); 827 } 828 else 829 { 830 CV_TS_SEQ_CHECK_CONDITION( seq->first == 0, 831 "The sequence doesn't become empty after the final remove" ); 832 } 833 break; 834 835 case 6: 836 case 7: 837 case 8: // push [front] multi/insert slice 838 if( sseq->count == sseq->max_count ) 839 break; 840 841 count = cvtest::randInt( rng ) % (sseq->max_count - sseq->count + 1); 842 elem_mat = Mat(1, MAX(count,1) * elem_size, CV_8U, elem); 843 cvtest::randUni( rng, elem_mat, cvScalarAll(0), cvScalarAll(255) ); 844 845 whence = op - 7; 846 pos = whence < 0 ? 0 : whence > 0 ? sseq->count : (int)(cvtest::randInt(rng) % (sseq->count+1)); 847 if( whence != 0 ) 848 { 849 cvSeqPushMulti( seq, elem, count, whence < 0 ); 850 } 851 else 852 { 853 CvSeq header; 854 CvSeqBlock block; 855 cvMakeSeqHeaderForArray( CV_SEQ_KIND_GENERIC, sizeof(CvSeq), 856 sseq->elem_size, 857 elem, count, 858 &header, &block ); 859 860 cvSeqInsertSlice( seq, pos, &header ); 861 } 862 cvTsSimpleSeqShiftAndCopy( sseq, pos, pos + count, elem ); 863 864 if( sseq->count > 0 ) 865 { 866 // choose the random element among the added 867 pos = count > 0 ? (int)(cvtest::randInt(rng) % count + pos) : MAX(pos-1,0); 868 elem2 = cvGetSeqElem( seq, pos ); 869 CV_TS_SEQ_CHECK_CONDITION( elem2 != 0, "multi push operation doesn't add elements" ); 870 CV_TS_SEQ_CHECK_CONDITION( seq->total == sseq->count && 871 memcmp( elem2, cvTsSimpleSeqElem(sseq,pos), elem_size) == 0, 872 "One of the added elements is wrong" ); 873 } 874 else 875 { 876 CV_TS_SEQ_CHECK_CONDITION( seq->total == 0 && seq->first == 0, 877 "Adding no elements to empty sequence fails" ); 878 } 879 break; 880 881 case 9: 882 case 10: 883 case 11: // pop [front] multi 884 if( sseq->count == 0 ) 885 break; 886 887 count = cvtest::randInt(rng) % (sseq->count+1); 888 whence = op - 10; 889 pos = whence < 0 ? 0 : whence > 0 ? sseq->count - count : 890 (int)(cvtest::randInt(rng) % (sseq->count - count + 1)); 891 892 if( whence != 0 ) 893 { 894 cvSeqPopMulti( seq, elem, count, whence < 0 ); 895 896 if( count > 0 ) 897 { 898 CV_TS_SEQ_CHECK_CONDITION( memcmp(elem, 899 cvTsSimpleSeqElem(sseq,pos), elem_size) == 0, 900 "The first (in the sequence order) removed element is wrong after popmulti" ); 901 } 902 } 903 else 904 { 905 cvSeqRemoveSlice( seq, cvSlice(pos, pos + count) ); 906 } 907 908 CV_TS_SEQ_CHECK_CONDITION( seq->total == sseq->count - count, 909 "The popmulti left a wrong number of elements in the sequence" ); 910 911 cvTsSimpleSeqShiftAndCopy( sseq, pos + count, pos, 0 ); 912 if( sseq->count > 0 ) 913 { 914 pos = whence < 0 ? 0 : MIN( pos, sseq->count - 1 ); 915 elem2 = cvGetSeqElem( seq, pos ); 916 CV_TS_SEQ_CHECK_CONDITION( elem2 && 917 memcmp( elem2, cvTsSimpleSeqElem(sseq,pos), elem_size) == 0, 918 "The last sequence element is wrong after POP" ); 919 } 920 else 921 { 922 CV_TS_SEQ_CHECK_CONDITION( seq->total == 0 && seq->first == 0, 923 "The sequence doesn't become empty after final POP" ); 924 } 925 break; 926 case 12: // seqslice 927 { 928 CvMemStoragePos storage_pos; 929 cvSaveMemStoragePos( storage, &storage_pos ); 930 931 int copy_data = cvtest::randInt(rng) % 2; 932 count = cvtest::randInt(rng) % (seq->total + 1); 933 pos = cvtest::randInt(rng) % (seq->total - count + 1); 934 CvSeq* seq_slice = cvSeqSlice( seq, cvSlice(pos, pos + count), storage, copy_data ); 935 936 CV_TS_SEQ_CHECK_CONDITION( seq_slice && seq_slice->total == count, 937 "cvSeqSlice returned incorrect slice" ); 938 939 if( count > 0 ) 940 { 941 int test_idx = cvtest::randInt(rng) % count; 942 elem2 = cvGetSeqElem( seq_slice, test_idx ); 943 schar* elem3 = cvGetSeqElem( seq, pos + test_idx ); 944 CV_TS_SEQ_CHECK_CONDITION( elem2 && 945 memcmp( elem2, cvTsSimpleSeqElem(sseq,pos + test_idx), elem_size) == 0, 946 "The extracted slice elements are not correct" ); 947 CV_TS_SEQ_CHECK_CONDITION( (elem2 == elem3) ^ copy_data, 948 "copy_data flag is handled incorrectly" ); 949 } 950 951 cvRestoreMemStoragePos( storage, &storage_pos ); 952 } 953 break; 954 case 13: // clear 955 cvTsClearSimpleSeq( sseq ); 956 cvClearSeq( seq ); 957 CV_TS_SEQ_CHECK_CONDITION( seq->total == 0 && seq->first == 0, 958 "The sequence doesn't become empty after clear" ); 959 break; 960 default: 961 assert(0); 962 return -1; 963 } 964 965 if( test_seq_block_consistence(struct_idx, seq, sseq->count) < 0 ) 966 return -1; 967 968 if( test_get_seq_elem(struct_idx, 7) < 0 ) 969 return -1; 970 971 update_progressbar(); 972 } 973 974 return 0; 975 } 976 977 978 void Core_SeqBaseTest::run( int ) 979 { 980 try 981 { 982 RNG& rng = ts->get_rng(); 983 int i; 984 double t; 985 986 clear(); 987 test_progress = -1; 988 989 simple_struct.resize(struct_count, 0); 990 cxcore_struct.resize(struct_count, 0); 991 992 for( gen = 0; gen < generations; gen++ ) 993 { 994 struct_idx = iter = -1; 995 996 if( !storage ) 997 { 998 t = cvtest::randReal(rng)*(max_log_storage_block_size - min_log_storage_block_size) 999 + min_log_storage_block_size; 1000 storage.reset(cvCreateMemStorage( cvRound( exp(t * CV_LOG2) ) )); 1001 } 1002 1003 iter = struct_idx = -1; 1004 test_multi_create(); 1005 1006 for( i = 0; i < struct_count; i++ ) 1007 { 1008 if( test_seq_block_consistence(i, (CvSeq*)cxcore_struct[i], 1009 ((CvTsSimpleSeq*)simple_struct[i])->count) < 0 ) 1010 return; 1011 1012 if( test_get_seq_elem( i, MAX(iterations/3,7) ) < 0 ) 1013 return; 1014 1015 if( test_get_seq_reading( i, MAX(iterations/3,7) ) < 0 ) 1016 return; 1017 update_progressbar(); 1018 } 1019 1020 if( test_seq_ops( iterations ) < 0 ) 1021 return; 1022 1023 if( cvtest::randInt(rng) % 2 ) 1024 storage.release(); 1025 else 1026 cvClearMemStorage( storage ); 1027 } 1028 } 1029 catch(int) 1030 { 1031 } 1032 } 1033 1034 1035 ////////////////////////////// more sequence tests ////////////////////////////////////// 1036 1037 class Core_SeqSortInvTest : public Core_SeqBaseTest 1038 { 1039 public: 1040 Core_SeqSortInvTest(); 1041 void run( int ); 1042 1043 protected: 1044 }; 1045 1046 1047 Core_SeqSortInvTest::Core_SeqSortInvTest() 1048 { 1049 } 1050 1051 1052 static int icvCmpSeqElems( const void* a, const void* b, void* userdata ) 1053 { 1054 return memcmp( a, b, ((CvSeq*)userdata)->elem_size ); 1055 } 1056 1057 static int icvCmpSeqElems2_elem_size = 0; 1058 static int icvCmpSeqElems2( const void* a, const void* b ) 1059 { 1060 return memcmp( a, b, icvCmpSeqElems2_elem_size ); 1061 } 1062 1063 1064 void Core_SeqSortInvTest::run( int ) 1065 { 1066 try 1067 { 1068 RNG& rng = ts->get_rng(); 1069 int i, k; 1070 double t; 1071 schar *elem0, *elem, *elem2; 1072 vector<uchar> buffer; 1073 1074 clear(); 1075 test_progress = -1; 1076 1077 simple_struct.resize(struct_count, 0); 1078 cxcore_struct.resize(struct_count, 0); 1079 1080 for( gen = 0; gen < generations; gen++ ) 1081 { 1082 struct_idx = iter = -1; 1083 1084 if( !storage ) 1085 { 1086 t = cvtest::randReal(rng)*(max_log_storage_block_size - min_log_storage_block_size) 1087 + min_log_storage_block_size; 1088 storage.reset(cvCreateMemStorage( cvRound( exp(t * CV_LOG2) ) )); 1089 } 1090 1091 for( iter = 0; iter < iterations/10; iter++ ) 1092 { 1093 int max_size = 0; 1094 test_multi_create(); 1095 1096 for( i = 0; i < struct_count; i++ ) 1097 { 1098 CvTsSimpleSeq* sseq = (CvTsSimpleSeq*)simple_struct[i]; 1099 max_size = MAX( max_size, sseq->count*sseq->elem_size ); 1100 } 1101 1102 buffer.resize(max_size); 1103 1104 for( i = 0; i < struct_count; i++ ) 1105 { 1106 CvSeq* seq = (CvSeq*)cxcore_struct[i]; 1107 CvTsSimpleSeq* sseq = (CvTsSimpleSeq*)simple_struct[i]; 1108 CvSlice slice = CV_WHOLE_SEQ; 1109 1110 //printf("%d. %d. %d-th size = %d\n", gen, iter, i, sseq->count ); 1111 1112 cvSeqInvert( seq ); 1113 cvTsSimpleSeqInvert( sseq ); 1114 1115 if( test_seq_block_consistence( i, seq, sseq->count ) < 0 ) 1116 return; 1117 1118 if( sseq->count > 0 && cvtest::randInt(rng) % 2 == 0 ) 1119 { 1120 slice.end_index = cvtest::randInt(rng) % sseq->count + 1; 1121 slice.start_index = cvtest::randInt(rng) % (sseq->count - slice.end_index + 1); 1122 slice.end_index += slice.start_index; 1123 } 1124 1125 cvCvtSeqToArray( seq, &buffer[0], slice ); 1126 1127 slice.end_index = MIN( slice.end_index, sseq->count ); 1128 CV_TS_SEQ_CHECK_CONDITION( sseq->count == 0 || memcmp( &buffer[0], 1129 sseq->array + slice.start_index*sseq->elem_size, 1130 (slice.end_index - slice.start_index)*sseq->elem_size ) == 0, 1131 "cvSeqInvert returned wrong result" ); 1132 1133 for( k = 0; k < (sseq->count > 0 ? 10 : 0); k++ ) 1134 { 1135 int idx0 = cvtest::randInt(rng) % sseq->count, idx = 0; 1136 elem0 = cvTsSimpleSeqElem( sseq, idx0 ); 1137 elem = cvGetSeqElem( seq, idx0 ); 1138 elem2 = cvSeqSearch( seq, elem0, k % 2 ? icvCmpSeqElems : 0, 0, &idx, seq ); 1139 1140 CV_TS_SEQ_CHECK_CONDITION( elem != 0 && 1141 memcmp( elem0, elem, seq->elem_size ) == 0, 1142 "cvSeqInvert gives incorrect result" ); 1143 CV_TS_SEQ_CHECK_CONDITION( elem2 != 0 && 1144 memcmp( elem0, elem2, seq->elem_size ) == 0 && 1145 elem2 == cvGetSeqElem( seq, idx ), 1146 "cvSeqSearch failed (linear search)" ); 1147 } 1148 1149 cvSeqSort( seq, icvCmpSeqElems, seq ); 1150 1151 if( test_seq_block_consistence( i, seq, sseq->count ) < 0 ) 1152 return; 1153 1154 if( sseq->count > 0 ) 1155 { 1156 // !!! This is not thread-safe !!! 1157 icvCmpSeqElems2_elem_size = sseq->elem_size; 1158 qsort( sseq->array, sseq->count, sseq->elem_size, icvCmpSeqElems2 ); 1159 1160 if( cvtest::randInt(rng) % 2 == 0 ) 1161 { 1162 slice.end_index = cvtest::randInt(rng) % sseq->count + 1; 1163 slice.start_index = cvtest::randInt(rng) % (sseq->count - slice.end_index + 1); 1164 slice.end_index += slice.start_index; 1165 } 1166 } 1167 1168 cvCvtSeqToArray( seq, &buffer[0], slice ); 1169 CV_TS_SEQ_CHECK_CONDITION( sseq->count == 0 || memcmp( &buffer[0], 1170 sseq->array + slice.start_index*sseq->elem_size, 1171 (slice.end_index - slice.start_index)*sseq->elem_size ) == 0, 1172 "cvSeqSort returned wrong result" ); 1173 1174 for( k = 0; k < (sseq->count > 0 ? 10 : 0); k++ ) 1175 { 1176 int idx0 = cvtest::randInt(rng) % sseq->count, idx = 0; 1177 elem0 = cvTsSimpleSeqElem( sseq, idx0 ); 1178 elem = cvGetSeqElem( seq, idx0 ); 1179 elem2 = cvSeqSearch( seq, elem0, icvCmpSeqElems, 1, &idx, seq ); 1180 1181 CV_TS_SEQ_CHECK_CONDITION( elem != 0 && 1182 memcmp( elem0, elem, seq->elem_size ) == 0, 1183 "cvSeqSort gives incorrect result" ); 1184 CV_TS_SEQ_CHECK_CONDITION( elem2 != 0 && 1185 memcmp( elem0, elem2, seq->elem_size ) == 0 && 1186 elem2 == cvGetSeqElem( seq, idx ), 1187 "cvSeqSearch failed (binary search)" ); 1188 } 1189 } 1190 1191 cvClearMemStorage( storage ); 1192 } 1193 1194 storage.release(); 1195 } 1196 } 1197 catch (int) 1198 { 1199 } 1200 } 1201 1202 1203 /////////////////////////////////////// set tests /////////////////////////////////////// 1204 1205 class Core_SetTest : public Core_DynStructBaseTest 1206 { 1207 public: 1208 Core_SetTest(); 1209 void clear(); 1210 void run( int ); 1211 1212 protected: 1213 //int test_seq_block_consistence( int struct_idx ); 1214 int test_set_ops( int iters ); 1215 }; 1216 1217 1218 Core_SetTest::Core_SetTest() 1219 { 1220 } 1221 1222 1223 void Core_SetTest::clear() 1224 { 1225 for( size_t i = 0; i < simple_struct.size(); i++ ) 1226 cvTsReleaseSimpleSet( (CvTsSimpleSet**)&simple_struct[i] ); 1227 Core_DynStructBaseTest::clear(); 1228 } 1229 1230 1231 int Core_SetTest::test_set_ops( int iters ) 1232 { 1233 const int max_op = 4; 1234 int max_elem_size = 0; 1235 int idx, idx0; 1236 CvSetElem *elem = 0, *elem2 = 0, *elem3 = 0; 1237 schar* elem_data = 0; 1238 RNG& rng = ts->get_rng(); 1239 //int max_active_count = 0, mean_active_count = 0; 1240 1241 for( int i = 0; i < struct_count; i++ ) 1242 max_elem_size = MAX( max_elem_size, ((CvSeq*)cxcore_struct[i])->elem_size ); 1243 1244 vector<schar> elem_buf(max_elem_size); 1245 Mat elem_mat; 1246 1247 for( iter = 0; iter < iters; iter++ ) 1248 { 1249 struct_idx = cvtest::randInt(rng) % struct_count; 1250 1251 CvSet* cvset = (CvSet*)cxcore_struct[struct_idx]; 1252 CvTsSimpleSet* sset = (CvTsSimpleSet*)simple_struct[struct_idx]; 1253 int pure_elem_size = sset->elem_size - 1; 1254 int prev_total = cvset->total, prev_count = cvset->active_count; 1255 int op = cvtest::randInt(rng) % (iter <= iters/10 ? 2 : max_op); 1256 int by_ptr = op % 2 == 0; 1257 CvSetElem* first_free = cvset->free_elems; 1258 CvSetElem* next_free = first_free ? first_free->next_free : 0; 1259 int pass_data = 0; 1260 1261 if( iter > iters/10 && cvtest::randInt(rng)%200 == 0 ) // clear set 1262 { 1263 prev_count = cvset->total; 1264 cvClearSet( cvset ); 1265 cvTsClearSimpleSet( sset ); 1266 1267 CV_TS_SEQ_CHECK_CONDITION( cvset->active_count == 0 && cvset->total == 0 && 1268 cvset->first == 0 && cvset->free_elems == 0 && 1269 (cvset->free_blocks != 0 || prev_count == 0), 1270 "cvClearSet doesn't remove all the elements" ); 1271 continue; 1272 } 1273 else if( op == 0 || op == 1 ) // add element 1274 { 1275 if( sset->free_count == 0 ) 1276 continue; 1277 1278 elem_mat = Mat(1, cvset->elem_size, CV_8U, &elem_buf[0]); 1279 cvtest::randUni( rng, elem_mat, cvScalarAll(0), cvScalarAll(255) ); 1280 elem = (CvSetElem*)&elem_buf[0]; 1281 1282 if( by_ptr ) 1283 { 1284 elem2 = cvSetNew( cvset ); 1285 CV_TS_SEQ_CHECK_CONDITION( elem2 != 0, "cvSetNew returned NULL pointer" ); 1286 } 1287 else 1288 { 1289 pass_data = cvtest::randInt(rng) % 2; 1290 idx = cvSetAdd( cvset, pass_data ? elem : 0, &elem2 ); 1291 CV_TS_SEQ_CHECK_CONDITION( elem2 != 0 && elem2->flags == idx, 1292 "cvSetAdd returned NULL pointer or a wrong index" ); 1293 } 1294 1295 elem_data = (schar*)elem + sizeof(int); 1296 1297 if( !pass_data ) 1298 memcpy( (schar*)elem2 + sizeof(int), elem_data, pure_elem_size ); 1299 1300 idx = elem2->flags; 1301 idx0 = cvTsSimpleSetAdd( sset, elem_data ); 1302 elem3 = cvGetSetElem( cvset, idx ); 1303 1304 CV_TS_SEQ_CHECK_CONDITION( CV_IS_SET_ELEM(elem3) && 1305 idx == idx0 && elem3 == elem2 && (!pass_data || 1306 memcmp( (char*)elem3 + sizeof(int), elem_data, pure_elem_size) == 0), 1307 "The added element is not correct" ); 1308 1309 CV_TS_SEQ_CHECK_CONDITION( (!first_free || elem3 == first_free) && 1310 (!next_free || cvset->free_elems == next_free) && 1311 cvset->active_count == prev_count + 1, 1312 "The free node list is modified incorrectly" ); 1313 } 1314 else if( op == 2 || op == 3 ) // remove element 1315 { 1316 idx = cvtest::randInt(rng) % sset->max_count; 1317 1318 if( sset->free_count == sset->max_count || idx >= sset->count ) 1319 continue; 1320 1321 elem_data = cvTsSimpleSetFind(sset, idx); 1322 if( elem_data == 0 ) 1323 continue; 1324 1325 elem = cvGetSetElem( cvset, idx ); 1326 CV_TS_SEQ_CHECK_CONDITION( CV_IS_SET_ELEM(elem) && elem->flags == idx && 1327 memcmp((char*)elem + sizeof(int), elem_data, pure_elem_size) == 0, 1328 "cvGetSetElem returned wrong element" ); 1329 1330 if( by_ptr ) 1331 { 1332 cvSetRemoveByPtr( cvset, elem ); 1333 } 1334 else 1335 { 1336 cvSetRemove( cvset, idx ); 1337 } 1338 1339 cvTsSimpleSetRemove( sset, idx ); 1340 1341 CV_TS_SEQ_CHECK_CONDITION( !CV_IS_SET_ELEM(elem) && !cvGetSetElem(cvset, idx) && 1342 (elem->flags & CV_SET_ELEM_IDX_MASK) == idx, 1343 "cvSetRemove[ByPtr] didn't release the element properly" ); 1344 1345 CV_TS_SEQ_CHECK_CONDITION( elem->next_free == first_free && 1346 cvset->free_elems == elem && 1347 cvset->active_count == prev_count - 1, 1348 "The free node list has not been updated properly" ); 1349 } 1350 1351 //max_active_count = MAX( max_active_count, cvset->active_count ); 1352 //mean_active_count += cvset->active_count; 1353 CV_TS_SEQ_CHECK_CONDITION( cvset->active_count == sset->max_count - sset->free_count && 1354 cvset->total >= cvset->active_count && 1355 (cvset->total == 0 || cvset->total >= prev_total), 1356 "The total number of cvset elements is not correct" ); 1357 1358 // CvSet and simple set do not necessary have the same "total" (active & free) number, 1359 // so pass "set->total" to skip that check 1360 test_seq_block_consistence( struct_idx, (CvSeq*)cvset, cvset->total ); 1361 update_progressbar(); 1362 } 1363 1364 return 0; 1365 } 1366 1367 1368 void Core_SetTest::run( int ) 1369 { 1370 try 1371 { 1372 RNG& rng = ts->get_rng(); 1373 double t; 1374 1375 clear(); 1376 test_progress = -1; 1377 1378 simple_struct.resize(struct_count, 0); 1379 cxcore_struct.resize(struct_count, 0); 1380 1381 for( gen = 0; gen < generations; gen++ ) 1382 { 1383 struct_idx = iter = -1; 1384 t = cvtest::randReal(rng)*(max_log_storage_block_size - min_log_storage_block_size) + min_log_storage_block_size; 1385 storage.reset(cvCreateMemStorage( cvRound( exp(t * CV_LOG2) ) )); 1386 1387 for( int i = 0; i < struct_count; i++ ) 1388 { 1389 t = cvtest::randReal(rng)*(max_log_elem_size - min_log_elem_size) + min_log_elem_size; 1390 int pure_elem_size = cvRound( exp(t * CV_LOG2) ); 1391 int elem_size = pure_elem_size + sizeof(int); 1392 elem_size = (elem_size + sizeof(size_t) - 1) & ~(sizeof(size_t)-1); 1393 elem_size = MAX( elem_size, (int)sizeof(CvSetElem) ); 1394 elem_size = MIN( elem_size, (int)(storage->block_size - sizeof(void*) - sizeof(CvMemBlock) - sizeof(CvSeqBlock)) ); 1395 pure_elem_size = MIN( pure_elem_size, elem_size-(int)sizeof(CvSetElem) ); 1396 1397 cvTsReleaseSimpleSet( (CvTsSimpleSet**)&simple_struct[i] ); 1398 simple_struct[i] = cvTsCreateSimpleSet( max_struct_size, pure_elem_size ); 1399 cxcore_struct[i] = cvCreateSet( 0, sizeof(CvSet), elem_size, storage ); 1400 } 1401 1402 if( test_set_ops( iterations*100 ) < 0 ) 1403 return; 1404 1405 storage.release(); 1406 } 1407 } 1408 catch(int) 1409 { 1410 } 1411 } 1412 1413 1414 /////////////////////////////////////// graph tests ////////////////////////////////// 1415 1416 class Core_GraphTest : public Core_DynStructBaseTest 1417 { 1418 public: 1419 Core_GraphTest(); 1420 void clear(); 1421 void run( int ); 1422 1423 protected: 1424 //int test_seq_block_consistence( int struct_idx ); 1425 int test_graph_ops( int iters ); 1426 }; 1427 1428 1429 Core_GraphTest::Core_GraphTest() 1430 { 1431 } 1432 1433 1434 void Core_GraphTest::clear() 1435 { 1436 for( size_t i = 0; i < simple_struct.size(); i++ ) 1437 cvTsReleaseSimpleGraph( (CvTsSimpleGraph**)&simple_struct[i] ); 1438 Core_DynStructBaseTest::clear(); 1439 } 1440 1441 1442 int Core_GraphTest::test_graph_ops( int iters ) 1443 { 1444 const int max_op = 4; 1445 int i, k; 1446 int max_elem_size = 0; 1447 int idx, idx0; 1448 CvGraphVtx *vtx = 0, *vtx2 = 0, *vtx3 = 0; 1449 CvGraphEdge* edge = 0, *edge2 = 0; 1450 RNG& rng = ts->get_rng(); 1451 //int max_active_count = 0, mean_active_count = 0; 1452 1453 for( i = 0; i < struct_count; i++ ) 1454 { 1455 CvGraph* graph = (CvGraph*)cxcore_struct[i]; 1456 max_elem_size = MAX( max_elem_size, graph->elem_size ); 1457 max_elem_size = MAX( max_elem_size, graph->edges->elem_size ); 1458 } 1459 1460 vector<schar> elem_buf(max_elem_size); 1461 Mat elem_mat; 1462 1463 for( iter = 0; iter < iters; iter++ ) 1464 { 1465 struct_idx = cvtest::randInt(rng) % struct_count; 1466 CvGraph* graph = (CvGraph*)cxcore_struct[struct_idx]; 1467 CvTsSimpleGraph* sgraph = (CvTsSimpleGraph*)simple_struct[struct_idx]; 1468 CvSet* edges = graph->edges; 1469 schar *vtx_data; 1470 char *edge_data; 1471 int pure_vtx_size = sgraph->vtx->elem_size - 1, 1472 pure_edge_size = sgraph->edge_size - 1; 1473 int prev_vtx_total = graph->total, 1474 prev_edge_total = graph->edges->total, 1475 prev_vtx_count = graph->active_count, 1476 prev_edge_count = graph->edges->active_count; 1477 int op = cvtest::randInt(rng) % max_op; 1478 int pass_data = 0, vtx_degree0 = 0, vtx_degree = 0; 1479 CvSetElem *first_free, *next_free; 1480 1481 if( cvtest::randInt(rng) % 200 == 0 ) // clear graph 1482 { 1483 int prev_vtx_count2 = graph->total, prev_edge_count2 = graph->edges->total; 1484 1485 cvClearGraph( graph ); 1486 cvTsClearSimpleGraph( sgraph ); 1487 1488 CV_TS_SEQ_CHECK_CONDITION( graph->active_count == 0 && graph->total == 0 && 1489 graph->first == 0 && graph->free_elems == 0 && 1490 (graph->free_blocks != 0 || prev_vtx_count2 == 0), 1491 "The graph is not empty after clearing" ); 1492 1493 CV_TS_SEQ_CHECK_CONDITION( edges->active_count == 0 && edges->total == 0 && 1494 edges->first == 0 && edges->free_elems == 0 && 1495 (edges->free_blocks != 0 || prev_edge_count2 == 0), 1496 "The graph is not empty after clearing" ); 1497 } 1498 else if( op == 0 ) // add vertex 1499 { 1500 if( sgraph->vtx->free_count == 0 ) 1501 continue; 1502 1503 first_free = graph->free_elems; 1504 next_free = first_free ? first_free->next_free : 0; 1505 1506 if( pure_vtx_size ) 1507 { 1508 elem_mat = Mat(1, graph->elem_size, CV_8U, &elem_buf[0]); 1509 cvtest::randUni( rng, elem_mat, cvScalarAll(0), cvScalarAll(255) ); 1510 } 1511 1512 vtx = (CvGraphVtx*)&elem_buf[0]; 1513 idx0 = cvTsSimpleGraphAddVertex( sgraph, vtx + 1 ); 1514 1515 pass_data = cvtest::randInt(rng) % 2; 1516 idx = cvGraphAddVtx( graph, pass_data ? vtx : 0, &vtx2 ); 1517 1518 if( !pass_data && pure_vtx_size > 0 ) 1519 memcpy( vtx2 + 1, vtx + 1, pure_vtx_size ); 1520 1521 vtx3 = cvGetGraphVtx( graph, idx ); 1522 1523 CV_TS_SEQ_CHECK_CONDITION( (CV_IS_SET_ELEM(vtx3) && vtx3->flags == idx && 1524 vtx3->first == 0) || (idx == idx0 && vtx3 == vtx2 && 1525 (!pass_data || pure_vtx_size == 0 || 1526 memcmp(vtx3 + 1, vtx + 1, pure_vtx_size) == 0)), 1527 "The added element is not correct" ); 1528 1529 CV_TS_SEQ_CHECK_CONDITION( (!first_free || first_free == (CvSetElem*)vtx3) && 1530 (!next_free || graph->free_elems == next_free) && 1531 graph->active_count == prev_vtx_count + 1, 1532 "The free node list is modified incorrectly" ); 1533 } 1534 else if( op == 1 ) // remove vertex 1535 { 1536 idx = cvtest::randInt(rng) % sgraph->vtx->max_count; 1537 if( sgraph->vtx->free_count == sgraph->vtx->max_count || idx >= sgraph->vtx->count ) 1538 continue; 1539 1540 vtx_data = cvTsSimpleGraphFindVertex(sgraph, idx); 1541 if( vtx_data == 0 ) 1542 continue; 1543 1544 vtx_degree0 = cvTsSimpleGraphVertexDegree( sgraph, idx ); 1545 first_free = graph->free_elems; 1546 1547 vtx = cvGetGraphVtx( graph, idx ); 1548 CV_TS_SEQ_CHECK_CONDITION( CV_IS_SET_ELEM(vtx) && vtx->flags == idx && 1549 (pure_vtx_size == 0 || memcmp( vtx + 1, vtx_data, pure_vtx_size) == 0), 1550 "cvGetGraphVtx returned wrong element" ); 1551 1552 if( cvtest::randInt(rng) % 2 ) 1553 { 1554 vtx_degree = cvGraphVtxDegreeByPtr( graph, vtx ); 1555 cvGraphRemoveVtxByPtr( graph, vtx ); 1556 } 1557 else 1558 { 1559 vtx_degree = cvGraphVtxDegree( graph, idx ); 1560 cvGraphRemoveVtx( graph, idx ); 1561 } 1562 1563 cvTsSimpleGraphRemoveVertex( sgraph, idx ); 1564 1565 CV_TS_SEQ_CHECK_CONDITION( vtx_degree == vtx_degree0, 1566 "Number of incident edges is different in two graph representations" ); 1567 1568 CV_TS_SEQ_CHECK_CONDITION( !CV_IS_SET_ELEM(vtx) && !cvGetGraphVtx(graph, idx) && 1569 (vtx->flags & CV_SET_ELEM_IDX_MASK) == idx, 1570 "cvGraphRemoveVtx[ByPtr] didn't release the vertex properly" ); 1571 1572 CV_TS_SEQ_CHECK_CONDITION( graph->edges->active_count == prev_edge_count - vtx_degree, 1573 "cvGraphRemoveVtx[ByPtr] didn't remove all the incident edges " 1574 "(or removed some extra)" ); 1575 1576 CV_TS_SEQ_CHECK_CONDITION( ((CvSetElem*)vtx)->next_free == first_free && 1577 graph->free_elems == (CvSetElem*)vtx && 1578 graph->active_count == prev_vtx_count - 1, 1579 "The free node list has not been updated properly" ); 1580 } 1581 else if( op == 2 ) // add edge 1582 { 1583 int v_idx[2] = {0,0}, res = 0; 1584 int v_prev_degree[2] = {0,0}, v_degree[2] = {0,0}; 1585 1586 if( sgraph->vtx->free_count >= sgraph->vtx->max_count-1 ) 1587 continue; 1588 1589 for( i = 0, k = 0; i < 10; i++ ) 1590 { 1591 int j = cvtest::randInt(rng) % sgraph->vtx->count; 1592 vtx_data = cvTsSimpleGraphFindVertex( sgraph, j ); 1593 if( vtx_data ) 1594 { 1595 v_idx[k] = j; 1596 if( k == 0 ) 1597 k++; 1598 else if( v_idx[0] != v_idx[1] && 1599 cvTsSimpleGraphFindEdge( sgraph, v_idx[0], v_idx[1] ) == 0 ) 1600 { 1601 k++; 1602 break; 1603 } 1604 } 1605 } 1606 1607 if( k < 2 ) 1608 continue; 1609 1610 first_free = graph->edges->free_elems; 1611 next_free = first_free ? first_free->next_free : 0; 1612 1613 edge = cvFindGraphEdge( graph, v_idx[0], v_idx[1] ); 1614 CV_TS_SEQ_CHECK_CONDITION( edge == 0, "Extra edge appeared in the graph" ); 1615 1616 if( pure_edge_size > 0 ) 1617 { 1618 elem_mat = Mat(1, graph->edges->elem_size, CV_8U, &elem_buf[0]); 1619 cvtest::randUni( rng, elem_mat, cvScalarAll(0), cvScalarAll(255) ); 1620 } 1621 edge = (CvGraphEdge*)&elem_buf[0]; 1622 1623 // assign some default weight that is easy to check for 1624 // consistensy, 'cause an edge weight is not stored 1625 // in the simple graph 1626 edge->weight = (float)(v_idx[0] + v_idx[1]); 1627 pass_data = cvtest::randInt(rng) % 2; 1628 1629 vtx = cvGetGraphVtx( graph, v_idx[0] ); 1630 vtx2 = cvGetGraphVtx( graph, v_idx[1] ); 1631 CV_TS_SEQ_CHECK_CONDITION( vtx != 0 && vtx2 != 0 && vtx->flags == v_idx[0] && 1632 vtx2->flags == v_idx[1], "Some of the vertices are missing" ); 1633 1634 if( cvtest::randInt(rng) % 2 ) 1635 { 1636 v_prev_degree[0] = cvGraphVtxDegreeByPtr( graph, vtx ); 1637 v_prev_degree[1] = cvGraphVtxDegreeByPtr( graph, vtx2 ); 1638 res = cvGraphAddEdgeByPtr(graph, vtx, vtx2, pass_data ? edge : 0, &edge2); 1639 v_degree[0] = cvGraphVtxDegreeByPtr( graph, vtx ); 1640 v_degree[1] = cvGraphVtxDegreeByPtr( graph, vtx2 ); 1641 } 1642 else 1643 { 1644 v_prev_degree[0] = cvGraphVtxDegree( graph, v_idx[0] ); 1645 v_prev_degree[1] = cvGraphVtxDegree( graph, v_idx[1] ); 1646 res = cvGraphAddEdge(graph, v_idx[0], v_idx[1], pass_data ? edge : 0, &edge2); 1647 v_degree[0] = cvGraphVtxDegree( graph, v_idx[0] ); 1648 v_degree[1] = cvGraphVtxDegree( graph, v_idx[1] ); 1649 } 1650 1651 //edge3 = (CvGraphEdge*)cvGetSetElem( graph->edges, idx ); 1652 CV_TS_SEQ_CHECK_CONDITION( res == 1 && edge2 != 0 && CV_IS_SET_ELEM(edge2) && 1653 ((edge2->vtx[0] == vtx && edge2->vtx[1] == vtx2) || 1654 (!CV_IS_GRAPH_ORIENTED(graph) && edge2->vtx[0] == vtx2 && edge2->vtx[1] == vtx)) && 1655 (!pass_data || pure_edge_size == 0 || memcmp( edge2 + 1, edge + 1, pure_edge_size ) == 0), 1656 "The edge has been added incorrectly" ); 1657 1658 if( !pass_data ) 1659 { 1660 if( pure_edge_size > 0 ) 1661 memcpy( edge2 + 1, edge + 1, pure_edge_size ); 1662 edge2->weight = edge->weight; 1663 } 1664 1665 CV_TS_SEQ_CHECK_CONDITION( v_degree[0] == v_prev_degree[0] + 1 && 1666 v_degree[1] == v_prev_degree[1] + 1, 1667 "The vertices lists have not been updated properly" ); 1668 1669 cvTsSimpleGraphAddEdge( sgraph, v_idx[0], v_idx[1], edge + 1 ); 1670 1671 CV_TS_SEQ_CHECK_CONDITION( (!first_free || first_free == (CvSetElem*)edge2) && 1672 (!next_free || graph->edges->free_elems == next_free) && 1673 graph->edges->active_count == prev_edge_count + 1, 1674 "The free node list is modified incorrectly" ); 1675 } 1676 else if( op == 3 ) // find & remove edge 1677 { 1678 int v_idx[2] = {0,0}, by_ptr; 1679 int v_prev_degree[2] = {0,0}, v_degree[2] = {0,0}; 1680 1681 if( sgraph->vtx->free_count >= sgraph->vtx->max_count-1 ) 1682 continue; 1683 1684 edge_data = 0; 1685 for( i = 0, k = 0; i < 10; i++ ) 1686 { 1687 int j = cvtest::randInt(rng) % sgraph->vtx->count; 1688 vtx_data = cvTsSimpleGraphFindVertex( sgraph, j ); 1689 if( vtx_data ) 1690 { 1691 v_idx[k] = j; 1692 if( k == 0 ) 1693 k++; 1694 else 1695 { 1696 edge_data = cvTsSimpleGraphFindEdge( sgraph, v_idx[0], v_idx[1] ); 1697 if( edge_data ) 1698 { 1699 k++; 1700 break; 1701 } 1702 } 1703 } 1704 } 1705 1706 if( k < 2 ) 1707 continue; 1708 1709 by_ptr = cvtest::randInt(rng) % 2; 1710 first_free = graph->edges->free_elems; 1711 1712 vtx = cvGetGraphVtx( graph, v_idx[0] ); 1713 vtx2 = cvGetGraphVtx( graph, v_idx[1] ); 1714 CV_TS_SEQ_CHECK_CONDITION( vtx != 0 && vtx2 != 0 && vtx->flags == v_idx[0] && 1715 vtx2->flags == v_idx[1], "Some of the vertices are missing" ); 1716 1717 if( by_ptr ) 1718 { 1719 edge = cvFindGraphEdgeByPtr( graph, vtx, vtx2 ); 1720 v_prev_degree[0] = cvGraphVtxDegreeByPtr( graph, vtx ); 1721 v_prev_degree[1] = cvGraphVtxDegreeByPtr( graph, vtx2 ); 1722 } 1723 else 1724 { 1725 edge = cvFindGraphEdge( graph, v_idx[0], v_idx[1] ); 1726 v_prev_degree[0] = cvGraphVtxDegree( graph, v_idx[0] ); 1727 v_prev_degree[1] = cvGraphVtxDegree( graph, v_idx[1] ); 1728 } 1729 1730 idx = edge->flags; 1731 1732 CV_TS_SEQ_CHECK_CONDITION( edge != 0 && edge->weight == v_idx[0] + v_idx[1] && 1733 ((edge->vtx[0] == vtx && edge->vtx[1] == vtx2) || 1734 (!CV_IS_GRAPH_ORIENTED(graph) && edge->vtx[1] == vtx && edge->vtx[0] == vtx2)) && 1735 (pure_edge_size == 0 || memcmp(edge + 1, edge_data, pure_edge_size) == 0), 1736 "An edge is missing or incorrect" ); 1737 1738 if( by_ptr ) 1739 { 1740 cvGraphRemoveEdgeByPtr( graph, vtx, vtx2 ); 1741 edge2 = cvFindGraphEdgeByPtr( graph, vtx, vtx2 ); 1742 v_degree[0] = cvGraphVtxDegreeByPtr( graph, vtx ); 1743 v_degree[1] = cvGraphVtxDegreeByPtr( graph, vtx2 ); 1744 } 1745 else 1746 { 1747 cvGraphRemoveEdge(graph, v_idx[0], v_idx[1] ); 1748 edge2 = cvFindGraphEdge( graph, v_idx[0], v_idx[1] ); 1749 v_degree[0] = cvGraphVtxDegree( graph, v_idx[0] ); 1750 v_degree[1] = cvGraphVtxDegree( graph, v_idx[1] ); 1751 } 1752 1753 CV_TS_SEQ_CHECK_CONDITION( !edge2 && !CV_IS_SET_ELEM(edge), 1754 "The edge has not been removed from the edge set" ); 1755 1756 CV_TS_SEQ_CHECK_CONDITION( v_degree[0] == v_prev_degree[0] - 1 && 1757 v_degree[1] == v_prev_degree[1] - 1, 1758 "The vertices lists have not been updated properly" ); 1759 1760 cvTsSimpleGraphRemoveEdge( sgraph, v_idx[0], v_idx[1] ); 1761 1762 CV_TS_SEQ_CHECK_CONDITION( graph->edges->free_elems == (CvSetElem*)edge && 1763 graph->edges->free_elems->next_free == first_free && 1764 graph->edges->active_count == prev_edge_count - 1, 1765 "The free edge list has not been modified properly" ); 1766 } 1767 1768 //max_active_count = MAX( max_active_count, graph->active_count ); 1769 //mean_active_count += graph->active_count; 1770 1771 CV_TS_SEQ_CHECK_CONDITION( graph->active_count == sgraph->vtx->max_count - sgraph->vtx->free_count && 1772 graph->total >= graph->active_count && 1773 (graph->total == 0 || graph->total >= prev_vtx_total), 1774 "The total number of graph vertices is not correct" ); 1775 1776 CV_TS_SEQ_CHECK_CONDITION( graph->edges->total >= graph->edges->active_count && 1777 (graph->edges->total == 0 || graph->edges->total >= prev_edge_total), 1778 "The total number of graph vertices is not correct" ); 1779 1780 // CvGraph and simple graph do not necessary have the same "total" (active & free) number, 1781 // so pass "graph->total" (or "graph->edges->total") to skip that check 1782 test_seq_block_consistence( struct_idx, (CvSeq*)graph, graph->total ); 1783 test_seq_block_consistence( struct_idx, (CvSeq*)graph->edges, graph->edges->total ); 1784 update_progressbar(); 1785 } 1786 1787 return 0; 1788 } 1789 1790 1791 void Core_GraphTest::run( int ) 1792 { 1793 try 1794 { 1795 RNG& rng = ts->get_rng(); 1796 int i, k; 1797 double t; 1798 1799 clear(); 1800 test_progress = -1; 1801 1802 simple_struct.resize(struct_count, 0); 1803 cxcore_struct.resize(struct_count, 0); 1804 1805 for( gen = 0; gen < generations; gen++ ) 1806 { 1807 struct_idx = iter = -1; 1808 t = cvtest::randReal(rng)*(max_log_storage_block_size - min_log_storage_block_size) + min_log_storage_block_size; 1809 int block_size = cvRound( exp(t * CV_LOG2) ); 1810 block_size = MAX(block_size, (int)(sizeof(CvGraph) + sizeof(CvMemBlock) + sizeof(CvSeqBlock))); 1811 1812 storage.reset(cvCreateMemStorage(block_size)); 1813 1814 for( i = 0; i < struct_count; i++ ) 1815 { 1816 int pure_elem_size[2], elem_size[2]; 1817 int is_oriented = (gen + i) % 2; 1818 for( k = 0; k < 2; k++ ) 1819 { 1820 t = cvtest::randReal(rng)*(max_log_elem_size - min_log_elem_size) + min_log_elem_size; 1821 int pe = cvRound( exp(t * CV_LOG2) ) - 1; // pure_elem_size==0 does also make sense 1822 int delta = k == 0 ? sizeof(CvGraphVtx) : sizeof(CvGraphEdge); 1823 int e = pe + delta; 1824 e = (e + sizeof(size_t) - 1) & ~(sizeof(size_t)-1); 1825 e = MIN( e, (int)(storage->block_size - sizeof(CvMemBlock) - 1826 sizeof(CvSeqBlock) - sizeof(void*)) ); 1827 pe = MIN(pe, e - delta); 1828 pure_elem_size[k] = pe; 1829 elem_size[k] = e; 1830 } 1831 1832 cvTsReleaseSimpleGraph( (CvTsSimpleGraph**)&simple_struct[i] ); 1833 simple_struct[i] = cvTsCreateSimpleGraph( max_struct_size/4, pure_elem_size[0], 1834 pure_elem_size[1], is_oriented ); 1835 cxcore_struct[i] = cvCreateGraph( is_oriented ? CV_ORIENTED_GRAPH : CV_GRAPH, 1836 sizeof(CvGraph), elem_size[0], elem_size[1], 1837 storage ); 1838 } 1839 1840 if( test_graph_ops( iterations*10 ) < 0 ) 1841 return; 1842 1843 storage.release(); 1844 } 1845 } 1846 catch(int) 1847 { 1848 } 1849 } 1850 1851 1852 //////////// graph scan test ////////////// 1853 1854 class Core_GraphScanTest : public Core_DynStructBaseTest 1855 { 1856 public: 1857 Core_GraphScanTest(); 1858 void run( int ); 1859 1860 protected: 1861 //int test_seq_block_consistence( int struct_idx ); 1862 int create_random_graph( int ); 1863 }; 1864 1865 1866 Core_GraphScanTest::Core_GraphScanTest() 1867 { 1868 iterations = 100; 1869 struct_count = 1; 1870 } 1871 1872 1873 int Core_GraphScanTest::create_random_graph( int _struct_idx ) 1874 { 1875 RNG& rng = ts->get_rng(); 1876 int is_oriented = cvtest::randInt(rng) % 2; 1877 int i, vtx_count = cvtest::randInt(rng) % max_struct_size; 1878 int edge_count = cvtest::randInt(rng) % MAX(vtx_count*20, 1); 1879 CvGraph* graph; 1880 1881 struct_idx = _struct_idx; 1882 cxcore_struct[_struct_idx] = graph = 1883 cvCreateGraph(is_oriented ? CV_ORIENTED_GRAPH : CV_GRAPH, 1884 sizeof(CvGraph), sizeof(CvGraphVtx), 1885 sizeof(CvGraphEdge), storage ); 1886 1887 for( i = 0; i < vtx_count; i++ ) 1888 cvGraphAddVtx( graph ); 1889 1890 assert( graph->active_count == vtx_count ); 1891 1892 for( i = 0; i < edge_count; i++ ) 1893 { 1894 int j = cvtest::randInt(rng) % vtx_count; 1895 int k = cvtest::randInt(rng) % vtx_count; 1896 1897 if( j != k ) 1898 cvGraphAddEdge( graph, j, k ); 1899 } 1900 1901 assert( graph->active_count == vtx_count && graph->edges->active_count <= edge_count ); 1902 1903 return 0; 1904 } 1905 1906 1907 void Core_GraphScanTest::run( int ) 1908 { 1909 CvGraphScanner* scanner = 0; 1910 try 1911 { 1912 RNG& rng = ts->get_rng(); 1913 vector<uchar> vtx_mask, edge_mask; 1914 double t; 1915 int i; 1916 1917 clear(); 1918 test_progress = -1; 1919 1920 cxcore_struct.resize(struct_count, 0); 1921 1922 for( gen = 0; gen < generations; gen++ ) 1923 { 1924 struct_idx = iter = -1; 1925 t = cvtest::randReal(rng)*(max_log_storage_block_size - min_log_storage_block_size) + min_log_storage_block_size; 1926 int storage_blocksize = cvRound( exp(t * CV_LOG2) ); 1927 storage_blocksize = MAX(storage_blocksize, (int)(sizeof(CvGraph) + sizeof(CvMemBlock) + sizeof(CvSeqBlock))); 1928 storage_blocksize = MAX(storage_blocksize, (int)(sizeof(CvGraphEdge) + sizeof(CvMemBlock) + sizeof(CvSeqBlock))); 1929 storage_blocksize = MAX(storage_blocksize, (int)(sizeof(CvGraphVtx) + sizeof(CvMemBlock) + sizeof(CvSeqBlock))); 1930 storage.reset(cvCreateMemStorage(storage_blocksize)); 1931 1932 if( gen == 0 ) 1933 { 1934 // special regression test for one sample graph. 1935 // !!! ATTENTION !!! The test relies on the particular order of the inserted edges 1936 // (LIFO: the edge inserted last goes first in the list of incident edges). 1937 // if it is changed, the test will have to be modified. 1938 1939 int vtx_count = -1, edge_count = 0, edges[][3] = 1940 { 1941 {0,4,'f'}, {0,1,'t'}, {1,4,'t'}, {1,2,'t'}, {2,3,'t'}, {4,3,'c'}, {3,1,'b'}, 1942 {5,7,'t'}, {7,5,'b'}, {5,6,'t'}, {6,0,'c'}, {7,6,'c'}, {6,4,'c'}, {-1,-1,0} 1943 }; 1944 1945 CvGraph* graph = cvCreateGraph( CV_ORIENTED_GRAPH, sizeof(CvGraph), 1946 sizeof(CvGraphVtx), sizeof(CvGraphEdge), storage ); 1947 1948 for( i = 0; edges[i][0] >= 0; i++ ) 1949 { 1950 vtx_count = MAX( vtx_count, edges[i][0] ); 1951 vtx_count = MAX( vtx_count, edges[i][1] ); 1952 } 1953 vtx_count++; 1954 1955 for( i = 0; i < vtx_count; i++ ) 1956 cvGraphAddVtx( graph ); 1957 1958 for( i = 0; edges[i][0] >= 0; i++ ) 1959 { 1960 CvGraphEdge* edge; 1961 cvGraphAddEdge( graph, edges[i][0], edges[i][1], 0, &edge ); 1962 edge->weight = (float)edges[i][2]; 1963 } 1964 1965 edge_count = i; 1966 scanner = cvCreateGraphScanner( graph, 0, CV_GRAPH_ALL_ITEMS ); 1967 1968 for(;;) 1969 { 1970 int code, a = -1, b = -1; 1971 const char* event = ""; 1972 code = cvNextGraphItem( scanner ); 1973 1974 switch( code ) 1975 { 1976 case CV_GRAPH_VERTEX: 1977 event = "Vertex"; 1978 vtx_count--; 1979 a = cvGraphVtxIdx( graph, scanner->vtx ); 1980 break; 1981 case CV_GRAPH_TREE_EDGE: 1982 event = "Tree Edge"; 1983 edge_count--; 1984 CV_TS_SEQ_CHECK_CONDITION( scanner->edge->weight == (float)'t', 1985 "Invalid edge type" ); 1986 a = cvGraphVtxIdx( graph, scanner->vtx ); 1987 b = cvGraphVtxIdx( graph, scanner->dst ); 1988 break; 1989 case CV_GRAPH_BACK_EDGE: 1990 event = "Back Edge"; 1991 edge_count--; 1992 CV_TS_SEQ_CHECK_CONDITION( scanner->edge->weight == (float)'b', 1993 "Invalid edge type" ); 1994 a = cvGraphVtxIdx( graph, scanner->vtx ); 1995 b = cvGraphVtxIdx( graph, scanner->dst ); 1996 break; 1997 case CV_GRAPH_CROSS_EDGE: 1998 event = "Cross Edge"; 1999 edge_count--; 2000 CV_TS_SEQ_CHECK_CONDITION( scanner->edge->weight == (float)'c', 2001 "Invalid edge type" ); 2002 a = cvGraphVtxIdx( graph, scanner->vtx ); 2003 b = cvGraphVtxIdx( graph, scanner->dst ); 2004 break; 2005 case CV_GRAPH_FORWARD_EDGE: 2006 event = "Forward Edge"; 2007 edge_count--; 2008 CV_TS_SEQ_CHECK_CONDITION( scanner->edge->weight == (float)'f', 2009 "Invalid edge type" ); 2010 a = cvGraphVtxIdx( graph, scanner->vtx ); 2011 b = cvGraphVtxIdx( graph, scanner->dst ); 2012 break; 2013 case CV_GRAPH_BACKTRACKING: 2014 event = "Backtracking"; 2015 a = cvGraphVtxIdx( graph, scanner->vtx ); 2016 break; 2017 case CV_GRAPH_NEW_TREE: 2018 event = "New search tree"; 2019 break; 2020 case CV_GRAPH_OVER: 2021 event = "End of procedure"; 2022 break; 2023 default: 2024 CV_TS_SEQ_CHECK_CONDITION( 0, "Invalid code appeared during graph scan" ); 2025 } 2026 2027 ts->printf( cvtest::TS::LOG, "%s", event ); 2028 if( a >= 0 ) 2029 { 2030 if( b >= 0 ) 2031 ts->printf( cvtest::TS::LOG, ": (%d,%d)", a, b ); 2032 else 2033 ts->printf( cvtest::TS::LOG, ": %d", a ); 2034 } 2035 2036 ts->printf( cvtest::TS::LOG, "\n" ); 2037 2038 if( code < 0 ) 2039 break; 2040 } 2041 2042 CV_TS_SEQ_CHECK_CONDITION( vtx_count == 0 && edge_count == 0, 2043 "Not every vertex/edge has been visited" ); 2044 update_progressbar(); 2045 } 2046 2047 // for a random graph the test just checks that every graph vertex and 2048 // every edge is vitisted during the scan 2049 for( iter = 0; iter < iterations; iter++ ) 2050 { 2051 create_random_graph(0); 2052 CvGraph* graph = (CvGraph*)cxcore_struct[0]; 2053 2054 // iterate twice to check that scanner doesn't damage the graph 2055 for( i = 0; i < 2; i++ ) 2056 { 2057 CvGraphVtx* start_vtx = cvtest::randInt(rng) % 2 || graph->active_count == 0 ? 0 : 2058 cvGetGraphVtx( graph, cvtest::randInt(rng) % graph->active_count ); 2059 2060 scanner = cvCreateGraphScanner( graph, start_vtx, CV_GRAPH_ALL_ITEMS ); 2061 2062 vtx_mask.resize(0); 2063 vtx_mask.resize(graph->active_count, 0); 2064 edge_mask.resize(0); 2065 edge_mask.resize(graph->edges->active_count, 0); 2066 2067 for(;;) 2068 { 2069 int code = cvNextGraphItem( scanner ); 2070 2071 if( code == CV_GRAPH_OVER ) 2072 break; 2073 else if( code & CV_GRAPH_ANY_EDGE ) 2074 { 2075 int edge_idx = scanner->edge->flags & CV_SET_ELEM_IDX_MASK; 2076 2077 CV_TS_SEQ_CHECK_CONDITION( edge_idx < graph->edges->active_count && 2078 edge_mask[edge_idx] == 0, 2079 "The edge is not found or visited for the second time" ); 2080 edge_mask[edge_idx] = 1; 2081 } 2082 else if( code & CV_GRAPH_VERTEX ) 2083 { 2084 int vtx_idx = scanner->vtx->flags & CV_SET_ELEM_IDX_MASK; 2085 2086 CV_TS_SEQ_CHECK_CONDITION( vtx_idx < graph->active_count && 2087 vtx_mask[vtx_idx] == 0, 2088 "The vtx is not found or visited for the second time" ); 2089 vtx_mask[vtx_idx] = 1; 2090 } 2091 } 2092 2093 cvReleaseGraphScanner( &scanner ); 2094 2095 CV_TS_SEQ_CHECK_CONDITION( cvtest::norm(Mat(vtx_mask),CV_L1) == graph->active_count && 2096 cvtest::norm(Mat(edge_mask),CV_L1) == graph->edges->active_count, 2097 "Some vertices or edges have not been visited" ); 2098 update_progressbar(); 2099 } 2100 cvClearMemStorage( storage ); 2101 } 2102 2103 storage.release(); 2104 } 2105 } 2106 catch(int) 2107 { 2108 } 2109 2110 cvReleaseGraphScanner( &scanner ); 2111 } 2112 2113 2114 TEST(Core_DS_Seq, basic_operations) { Core_SeqBaseTest test; test.safe_run(); } 2115 TEST(Core_DS_Seq, sort_invert) { Core_SeqSortInvTest test; test.safe_run(); } 2116 TEST(Core_DS_Set, basic_operations) { Core_SetTest test; test.safe_run(); } 2117 TEST(Core_DS_Graph, basic_operations) { Core_GraphTest test; test.safe_run(); } 2118 TEST(Core_DS_Graph, scan) { Core_GraphScanTest test; test.safe_run(); } 2119
