1 /* Copyright (c) 2000, 2010 Oracle and/or its affiliates. All rights reserved. 2 Copyright (C) 2011 Monty Program Ab. 3 4 This program is free software; you can redistribute it and/or modify 5 it under the terms of the GNU General Public License as published by 6 the Free Software Foundation; version 2 of the License. 7 8 This program is distributed in the hope that it will be useful, 9 but WITHOUT ANY WARRANTY; without even the implied warranty of 10 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 11 GNU General Public License for more details. test_clock_getres()12 13 You should have received a copy of the GNU General Public License 14 along with this program; if not, write to the Free Software 15 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1335 USA */ 16 17 18 #include "mariadb.h" 19 20 #ifdef HAVE_SPATIAL 21 22 #include "gcalc_tools.h" 23 #include "spatial.h" 24 25 #define float_to_coord(d) ((double) d) 26 27 28 /* 29 Adds new shape to the relation. 30 After that it can be used as an argument of an operation. 31 */ 32 33 gcalc_shape_info Gcalc_function::add_new_shape(uint32 shape_id, 34 shape_type shape_kind) 35 { 36 shapes_buffer.q_append((uint32) shape_kind); 37 return n_shapes++; 38 } 39 test_clock_id_now()40 41 /* 42 Adds new operation to the constructed relation. 43 To construct the complex relation one has to specify operations 44 in prefix style. 45 */ 46 47 void Gcalc_function::add_operation(uint operation, uint32 n_operands) 48 { 49 uint32 op_code= (uint32 ) operation + n_operands; 50 function_buffer.q_append(op_code); 51 } test_clock_id_pid_cpu_clock_id()52 53 54 /* 55 Sometimes the number of arguments is unknown at the moment the operation 56 is added. That allows to specify it later. 57 */ 58 59 void Gcalc_function::add_operands_to_op(uint32 operation_pos, uint32 n_operands) 60 { 61 uint32 op_code= uint4korr(function_buffer.ptr() + operation_pos) + n_operands; 62 function_buffer.write_at_position(operation_pos, op_code); 63 } 64 65 66 /* 67 Just like the add_operation() but the result will be the inverted 68 value of an operation. 69 */ 70 71 void Gcalc_function::add_not_operation(op_type operation, uint32 n_operands) 72 { 73 uint32 op_code= ((uint32) op_not | (uint32 ) operation) + n_operands; 74 function_buffer.q_append(op_code); 75 } 76 77 78 int Gcalc_function::single_shape_op(shape_type shape_kind, gcalc_shape_info *si) 79 { 80 if (reserve_shape_buffer(1) || reserve_op_buffer(1)) 81 return 1; 82 *si= add_new_shape(0, shape_kind); 83 add_operation(op_shape, *si); 84 return 0; 85 } 86 87 88 int Gcalc_function::repeat_expression(uint32 exp_pos) 89 { 90 if (reserve_op_buffer(1)) 91 return 1; 92 add_operation(op_repeat, exp_pos); 93 return 0; 94 } 95 96 97 /* 98 Specify how many arguments we're going to have. 99 */ 100 101 int Gcalc_function::reserve_shape_buffer(uint n_shapes) 102 { 103 return shapes_buffer.reserve(n_shapes * 4, 512); 104 } 105 106 107 /* 108 Specify how many operations we're going to have. 109 */ 110 111 int Gcalc_function::reserve_op_buffer(uint n_ops) 112 { 113 return function_buffer.reserve(n_ops * 4, 512); 114 } 115 116 117 int Gcalc_function::alloc_states() 118 { 119 if (function_buffer.reserve((n_shapes+1) * 2 * sizeof(int))) 120 return 1; 121 i_states= (int *) (function_buffer.ptr() + ALIGN_SIZE(function_buffer.length())); 122 b_states= i_states + (n_shapes + 1); 123 return 0; 124 } 125 126 127 int Gcalc_function::count_internal(const char *cur_func, uint set_type, 128 const char **end) 129 { 130 uint c_op= uint4korr(cur_func); 131 op_type next_func= (op_type) (c_op & op_any); 132 int mask= (c_op & op_not) ? 1:0; 133 uint n_ops= c_op & ~(op_any | op_not | v_mask); 134 uint n_shape= c_op & ~(op_any | op_not | v_mask); /* same as n_ops */ 135 value v_state= (value) (c_op & v_mask); 136 int result= 0; 137 const char *sav_cur_func= cur_func; 138 139 // GCALC_DBUG_ENTER("Gcalc_function::count_internal"); 140 141 cur_func+= 4; 142 if (next_func == op_shape) 143 { 144 if (set_type == 0) 145 result= i_states[n_shape] | b_states[n_shape]; 146 /* the last call for the count_internal outside of all shapes. */ 147 else if (set_type == 1) 148 result= 0; 149 else if (set_type == op_border) 150 result= b_states[n_shape]; 151 else if (set_type == op_internals) 152 result= i_states[n_shape] && !b_states[n_shape]; 153 goto exit; 154 } 155 156 if (next_func == op_false) 157 { 158 result= 0; 159 goto exit; 160 } 161 162 if (next_func == op_border || next_func == op_internals) 163 { 164 result= count_internal(cur_func, 165 (set_type == 1) ? set_type : next_func, &cur_func); 166 goto exit; 167 } 168 169 if (next_func == op_repeat) 170 { 171 result= count_internal(function_buffer.ptr() + n_ops, set_type, 0); 172 goto exit; 173 } 174 175 if (n_ops == 0) 176 return mask; 177 //GCALC_DBUG_RETURN(mask); 178 179 result= count_internal(cur_func, set_type, &cur_func); 180 181 while (--n_ops) 182 { 183 int next_res= count_internal(cur_func, set_type, &cur_func); 184 switch (next_func) 185 { 186 case op_union: 187 if (result == result_true || next_res == result_true) 188 result= result_true; 189 else if (result == result_unknown || next_res == result_unknown) 190 result= result_unknown; 191 else 192 result= result_false; 193 break; 194 case op_intersection: 195 if (result == result_false || next_res == result_false) 196 result= result_false; 197 else if (result == result_unknown || next_res == result_unknown) 198 result= result_unknown; 199 else 200 result= result_true; 201 break; 202 case op_symdifference: 203 if (result == result_unknown || next_res == result_unknown) 204 result= result_unknown; 205 else 206 result= result ^ next_res; 207 break; 208 case op_difference: 209 if (result == result_false || next_res == result_true) 210 result= result_false; 211 else if (result == result_unknown || next_res == result_unknown) 212 result= result_unknown; 213 else 214 result= result_true; 215 break; 216 default: 217 GCALC_DBUG_ASSERT(FALSE); 218 }; 219 } 220 221 exit: 222 if (result != result_unknown) 223 result^= mask; 224 if (v_state != v_empty) 225 { 226 switch (v_state) 227 { 228 case v_find_t: 229 if (result == result_true) 230 { 231 c_op= (c_op & ~v_mask) | v_t_found; 232 int4store(sav_cur_func, c_op); 233 } 234 else 235 { 236 if (set_type != 1) 237 result= result_unknown; 238 } 239 break; 240 case v_find_f: 241 if (result == result_false) 242 { 243 c_op= (c_op & ~v_mask) | v_f_found; 244 int4store(sav_cur_func, c_op); 245 } 246 else 247 { 248 if (set_type != 1) 249 result= result_unknown; 250 } 251 break; 252 case v_t_found: 253 result= 1; 254 break; 255 case v_f_found: 256 result= 0; 257 break; 258 default: 259 GCALC_DBUG_ASSERT(0); 260 }; 261 } 262 263 if (end) 264 *end= cur_func; 265 return result; 266 //GCALC_DBUG_RETURN(result); 267 } 268 269 270 void Gcalc_function::clear_i_states() 271 { 272 for (uint i= 0; i < n_shapes; i++) 273 i_states[i]= 0; 274 } 275 276 277 void Gcalc_function::clear_b_states() 278 { 279 for (uint i= 0; i < n_shapes; i++) 280 b_states[i]= 0; 281 } 282 283 284 /* 285 Clear the state of the object. 286 */ 287 288 void Gcalc_function::reset() 289 { 290 n_shapes= 0; 291 shapes_buffer.length(0); 292 function_buffer.length(0); 293 } 294 295 296 int Gcalc_function::check_function(Gcalc_scan_iterator &scan_it) 297 { 298 const Gcalc_scan_iterator::point *eq_start, *cur_eq; 299 const Gcalc_scan_iterator::event_point *events; 300 int result; 301 GCALC_DBUG_ENTER("Gcalc_function::check_function"); 302 303 while (scan_it.more_points()) 304 { 305 if (scan_it.step()) 306 GCALC_DBUG_RETURN(-1); 307 events= scan_it.get_events(); 308 309 /* these kinds of events don't change the function */ 310 Gcalc_point_iterator pit(&scan_it); 311 clear_b_states(); 312 clear_i_states(); 313 /* Walk to the event, marking polygons we met */ 314 for (; pit.point() != scan_it.get_event_position(); ++pit) 315 { 316 gcalc_shape_info si= pit.point()->get_shape(); 317 if ((get_shape_kind(si) == Gcalc_function::shape_polygon)) 318 invert_i_state(si); 319 } 320 if (events->simple_event()) 321 { 322 if (events->event == scev_end) 323 set_b_state(events->get_shape()); 324 325 if ((result= count()) != result_unknown) 326 GCALC_DBUG_RETURN(result); 327 clear_b_states(); 328 continue; 329 } 330 331 /* Check the status of the event point */ 332 for (; events; events= events->get_next()) 333 { 334 gcalc_shape_info si= events->get_shape(); 335 if (events->event == scev_thread || 336 events->event == scev_end || 337 (get_shape_kind(si) == Gcalc_function::shape_polygon)) 338 set_b_state(si); 339 else if (events->event == scev_single_point || 340 get_shape_kind(si) == Gcalc_function::shape_line) 341 set_i_state(si); 342 } 343 344 if ((result= count()) != result_unknown) 345 GCALC_DBUG_RETURN(result); 346 347 /* Set back states changed in the loop above. */ 348 for (events= scan_it.get_events(); events; events= events->get_next()) 349 { 350 gcalc_shape_info si= events->get_shape(); 351 if (events->event == scev_thread || 352 events->event == scev_end || 353 get_shape_kind(si) == Gcalc_function::shape_polygon) 354 clear_b_state(si); 355 else if (events->event == scev_single_point || 356 get_shape_kind(si) == Gcalc_function::shape_line) 357 clear_i_state(si); 358 } 359 360 if (scan_it.get_event_position() == scan_it.get_event_end()) 361 continue; 362 363 /* Check the status after the event */ 364 eq_start= pit.point(); 365 do 366 { 367 ++pit; 368 if (pit.point() != scan_it.get_event_end() && 369 eq_start->cmp_dx_dy(pit.point()) == 0) 370 continue; 371 for (cur_eq= eq_start; cur_eq != pit.point(); 372 cur_eq= cur_eq->get_next()) 373 { 374 gcalc_shape_info si= cur_eq->get_shape(); 375 if (get_shape_kind(si) == Gcalc_function::shape_polygon) 376 set_b_state(si); 377 else 378 invert_i_state(si); 379 } 380 if ((result= count()) != result_unknown) 381 GCALC_DBUG_RETURN(result); 382 383 for (cur_eq= eq_start; cur_eq != pit.point(); cur_eq= cur_eq->get_next()) 384 { 385 gcalc_shape_info si= cur_eq->get_shape(); 386 if ((get_shape_kind(si) == Gcalc_function::shape_polygon)) 387 { 388 clear_b_state(si); 389 invert_i_state(si); 390 } 391 else 392 invert_i_state(cur_eq->get_shape()); 393 } 394 if ((result= count()) != result_unknown) 395 GCALC_DBUG_RETURN(result); 396 397 eq_start= pit.point(); 398 } while (pit.point() != scan_it.get_event_end()); 399 } 400 GCALC_DBUG_RETURN(count_last()); 401 } 402 403 404 int Gcalc_operation_transporter::single_point(double x, double y) 405 { 406 gcalc_shape_info si; 407 return m_fn->single_shape_op(Gcalc_function::shape_point, &si) || 408 int_single_point(si, x, y); 409 } 410 411 412 int Gcalc_operation_transporter::start_line() 413 { 414 int_start_line(); 415 return m_fn->single_shape_op(Gcalc_function::shape_line, &m_si); 416 } 417 418 419 int Gcalc_operation_transporter::complete_line() 420 { 421 int_complete_line(); 422 return 0; 423 } 424 425 426 int Gcalc_operation_transporter::start_poly() 427 { 428 int_start_poly(); 429 return m_fn->single_shape_op(Gcalc_function::shape_polygon, &m_si); 430 } 431 432 433 int Gcalc_operation_transporter::complete_poly() 434 { 435 int_complete_poly(); 436 return 0; 437 } 438 439 440 int Gcalc_operation_transporter::start_ring() 441 { 442 int_start_ring(); 443 return 0; 444 } 445 446 447 int Gcalc_operation_transporter::complete_ring() 448 { 449 int_complete_ring(); 450 return 0; 451 } 452 453 454 int Gcalc_operation_transporter::add_point(double x, double y) 455 { 456 return int_add_point(m_si, x, y); 457 } 458 459 460 int Gcalc_operation_transporter::start_collection(int n_objects) 461 { 462 if (m_fn->reserve_shape_buffer(n_objects) || m_fn->reserve_op_buffer(1)) 463 return 1; 464 m_fn->add_operation(Gcalc_function::op_union, n_objects); 465 return 0; 466 } 467 468 469 int Gcalc_operation_transporter::empty_shape() 470 { 471 if (m_fn->reserve_op_buffer(1)) 472 return 1; 473 m_fn->add_operation(Gcalc_function::op_false, 0); 474 return 0; 475 } 476 477 478 int Gcalc_result_receiver::start_shape(Gcalc_function::shape_type shape) 479 { 480 GCALC_DBUG_ENTER("Gcalc_result_receiver::start_shape"); 481 if (buffer.reserve(4*2, 512)) 482 GCALC_DBUG_RETURN(1); 483 cur_shape= shape; 484 shape_pos= buffer.length(); 485 buffer.length(shape_pos + ((shape == Gcalc_function::shape_point) ? 4:8)); 486 n_points= 0; 487 shape_area= 0.0; 488 489 GCALC_DBUG_RETURN(0); 490 } 491 492 493 int Gcalc_result_receiver::add_point(double x, double y) 494 { 495 GCALC_DBUG_ENTER("Gcalc_result_receiver::add_point"); 496 if (n_points && x == prev_x && y == prev_y) 497 GCALC_DBUG_RETURN(0); 498 499 if (!n_points++) 500 { 501 prev_x= first_x= x; 502 prev_y= first_y= y; 503 GCALC_DBUG_RETURN(0); 504 } 505 506 shape_area+= prev_x*y - prev_y*x; 507 508 if (buffer.reserve(8*2, 512)) 509 GCALC_DBUG_RETURN(1); 510 buffer.q_append(prev_x); 511 buffer.q_append(prev_y); 512 prev_x= x; 513 prev_y= y; 514 GCALC_DBUG_RETURN(0); 515 } 516 517 518 int Gcalc_result_receiver::complete_shape() 519 { 520 GCALC_DBUG_ENTER("Gcalc_result_receiver::complete_shape"); 521 if (n_points == 0) 522 { 523 buffer.length(shape_pos); 524 GCALC_DBUG_RETURN(0); 525 } 526 if (n_points == 1) 527 { 528 if (cur_shape != Gcalc_function::shape_point) 529 { 530 if (cur_shape == Gcalc_function::shape_hole) 531 { 532 buffer.length(shape_pos); 533 GCALC_DBUG_RETURN(0); 534 } 535 cur_shape= Gcalc_function::shape_point; 536 buffer.length(buffer.length()-4); 537 } 538 } 539 else 540 { 541 GCALC_DBUG_ASSERT(cur_shape != Gcalc_function::shape_point); 542 if (cur_shape == Gcalc_function::shape_hole) 543 { 544 shape_area+= prev_x*first_y - prev_y*first_x; 545 if (fabs(shape_area) < 1e-8) 546 { 547 buffer.length(shape_pos); 548 GCALC_DBUG_RETURN(0); 549 } 550 } 551 552 if ((cur_shape == Gcalc_function::shape_polygon || 553 cur_shape == Gcalc_function::shape_hole) && 554 prev_x == first_x && prev_y == first_y) 555 { 556 n_points--; 557 buffer.write_at_position(shape_pos+4, n_points); 558 goto do_complete; 559 } 560 buffer.write_at_position(shape_pos+4, n_points); 561 } 562 563 if (buffer.reserve(8*2, 512)) 564 GCALC_DBUG_RETURN(1); 565 buffer.q_append(prev_x); 566 buffer.q_append(prev_y); 567 568 do_complete: 569 buffer.write_at_position(shape_pos, (uint32) cur_shape); 570 571 if (!n_shapes++) 572 { 573 GCALC_DBUG_ASSERT(cur_shape != Gcalc_function::shape_hole); 574 common_shapetype= cur_shape; 575 } 576 else if (cur_shape == Gcalc_function::shape_hole) 577 { 578 ++n_holes; 579 } 580 else if (!collection_result && (cur_shape != common_shapetype)) 581 { 582 collection_result= true; 583 } 584 GCALC_DBUG_RETURN(0); 585 } 586 587 588 int Gcalc_result_receiver::single_point(double x, double y) 589 { 590 return start_shape(Gcalc_function::shape_point) || 591 add_point(x, y) || 592 complete_shape(); 593 } 594 595 596 int Gcalc_result_receiver::done() 597 { 598 return 0; 599 } 600 601 602 void Gcalc_result_receiver::reset() 603 { 604 buffer.length(0); 605 collection_result= FALSE; 606 n_shapes= n_holes= 0; 607 } 608 609 610 int Gcalc_result_receiver::get_result_typeid() 611 { 612 if (!n_shapes || collection_result) 613 return Geometry::wkb_geometrycollection; 614 615 switch (common_shapetype) 616 { 617 case Gcalc_function::shape_polygon: 618 return (n_shapes - n_holes == 1) ? 619 Geometry::wkb_polygon : Geometry::wkb_multipolygon; 620 case Gcalc_function::shape_point: 621 return (n_shapes == 1) ? Geometry::wkb_point : Geometry::wkb_multipoint; 622 case Gcalc_function::shape_line: 623 return (n_shapes == 1) ? Geometry::wkb_linestring : 624 Geometry::wkb_multilinestring; 625 default: 626 GCALC_DBUG_ASSERT(0); 627 } 628 return 0; 629 } 630 631 632 int Gcalc_result_receiver::move_hole(uint32 dest_position, uint32 source_position, 633 uint32 *position_shift) 634 { 635 char *ptr; 636 int source_len; 637 GCALC_DBUG_ENTER("Gcalc_result_receiver::move_hole"); 638 GCALC_DBUG_PRINT(("ps %d %d", dest_position, source_position)); 639 640 *position_shift= source_len= buffer.length() - source_position; 641 642 if (dest_position == source_position) 643 GCALC_DBUG_RETURN(0); 644 645 if (buffer.reserve(source_len, MY_ALIGN(source_len, 512))) 646 GCALC_DBUG_RETURN(1); 647 648 ptr= (char *) buffer.ptr(); 649 memmove(ptr + dest_position + source_len, ptr + dest_position, 650 buffer.length() - dest_position); 651 memcpy(ptr + dest_position, ptr + buffer.length(), source_len); 652 GCALC_DBUG_RETURN(0); 653 } 654 655 656 Gcalc_operation_reducer::Gcalc_operation_reducer(size_t blk_size) : 657 Gcalc_dyn_list(blk_size, sizeof(res_point)), 658 #ifndef GCALC_DBUG_OFF 659 n_res_points(0), 660 #endif /*GCALC_DBUG_OFF*/ 661 m_res_hook((Gcalc_dyn_list::Item **)&m_result), 662 m_first_active_thread(NULL) 663 {} 664 665 666 Gcalc_operation_reducer::Gcalc_operation_reducer( 667 const Gcalc_operation_reducer &gor) : 668 Gcalc_dyn_list(gor), 669 #ifndef GCALC_DBUG_OFF 670 n_res_points(0), 671 #endif /*GCALC_DBUG_OFF*/ 672 m_res_hook((Gcalc_dyn_list::Item **)&m_result), 673 m_first_active_thread(NULL) 674 {} 675 676 677 void Gcalc_operation_reducer::init(Gcalc_function *fn, modes mode) 678 { 679 m_fn= fn; 680 m_mode= mode; 681 m_first_active_thread= NULL; 682 m_lines= NULL; 683 m_lines_hook= (Gcalc_dyn_list::Item **) &m_lines; 684 m_poly_borders= NULL; 685 m_poly_borders_hook= (Gcalc_dyn_list::Item **) &m_poly_borders; 686 GCALC_SET_TERMINATED(killed, 0); 687 } 688 689 690 Gcalc_operation_reducer:: 691 Gcalc_operation_reducer(Gcalc_function *fn, modes mode, size_t blk_size) : 692 Gcalc_dyn_list(blk_size, sizeof(res_point)), 693 m_res_hook((Gcalc_dyn_list::Item **)&m_result) 694 { 695 init(fn, mode); 696 } 697 698 699 void Gcalc_operation_reducer::res_point::set(const Gcalc_scan_iterator *si) 700 { 701 intersection_point= si->intersection_step(); 702 pi= si->get_cur_pi(); 703 } 704 705 706 Gcalc_operation_reducer::res_point * 707 Gcalc_operation_reducer::add_res_point(Gcalc_function::shape_type type) 708 { 709 GCALC_DBUG_ENTER("Gcalc_operation_reducer::add_res_point"); 710 res_point *result= (res_point *)new_item(); 711 *m_res_hook= result; 712 result->prev_hook= m_res_hook; 713 m_res_hook= &result->next; 714 result->type= type; 715 #ifndef GCALC_DBUG_OFF 716 result->point_n= n_res_points++; 717 #endif /*GCALC_DBUG_OFF*/ 718 GCALC_DBUG_RETURN(result); 719 } 720 721 int Gcalc_operation_reducer::add_line(int incoming, active_thread *t, 722 const Gcalc_scan_iterator::point *p) 723 { 724 line *l= new_line(); 725 GCALC_DBUG_ENTER("Gcalc_operation_reducer::add_line"); 726 if (!l) 727 GCALC_DBUG_RETURN(1); 728 l->incoming= incoming; 729 l->t= t; 730 l->p= p; 731 *m_lines_hook= l; 732 m_lines_hook= &l->next; 733 GCALC_DBUG_RETURN(0); 734 } 735 736 737 int Gcalc_operation_reducer::add_poly_border(int incoming, 738 active_thread *t, int prev_state, const Gcalc_scan_iterator::point *p) 739 { 740 poly_border *b= new_poly_border(); 741 GCALC_DBUG_ENTER("Gcalc_operation_reducer::add_poly_border"); 742 if (!b) 743 GCALC_DBUG_RETURN(1); 744 b->incoming= incoming; 745 b->t= t; 746 b->prev_state= prev_state; 747 b->p= p; 748 *m_poly_borders_hook= b; 749 m_poly_borders_hook= &b->next; 750 GCALC_DBUG_RETURN(0); 751 } 752 753 754 int Gcalc_operation_reducer::continue_range(active_thread *t, 755 const Gcalc_heap::Info *p, 756 const Gcalc_heap::Info *p_next) 757 { 758 res_point *rp= add_res_point(t->rp->type); 759 GCALC_DBUG_ENTER("Gcalc_operation_reducer::continue_range"); 760 if (!rp) 761 GCALC_DBUG_RETURN(1); 762 rp->glue= NULL; 763 rp->down= t->rp; 764 t->rp->up= rp; 765 rp->intersection_point= false; 766 rp->pi= p; 767 t->rp= rp; 768 t->p1= p; 769 t->p2= p_next; 770 GCALC_DBUG_RETURN(0); 771 } 772 773 774 inline int Gcalc_operation_reducer::continue_i_range(active_thread *t, 775 const Gcalc_heap::Info *ii) 776 { 777 res_point *rp= add_res_point(t->rp->type); 778 GCALC_DBUG_ENTER("Gcalc_operation_reducer::continue_i_range"); 779 if (!rp) 780 GCALC_DBUG_RETURN(1); 781 rp->glue= NULL; 782 rp->down= t->rp; 783 t->rp->up= rp; 784 rp->intersection_point= true; 785 rp->pi= ii; 786 t->rp= rp; 787 GCALC_DBUG_RETURN(0); 788 } 789 790 int Gcalc_operation_reducer::end_couple(active_thread *t0, active_thread *t1, 791 const Gcalc_heap::Info *p) 792 { 793 res_point *rp0, *rp1; 794 GCALC_DBUG_ENTER("Gcalc_operation_reducer::end_couple"); 795 GCALC_DBUG_ASSERT(t0->rp->type == t1->rp->type); 796 if (!(rp0= add_res_point(t0->rp->type)) || 797 !(rp1= add_res_point(t0->rp->type))) 798 GCALC_DBUG_RETURN(1); 799 rp0->down= t0->rp; 800 rp1->down= t1->rp; 801 rp1->glue= rp0; 802 rp0->glue= rp1; 803 rp0->up= rp1->up= NULL; 804 t0->rp->up= rp0; 805 t1->rp->up= rp1; 806 rp0->intersection_point= rp1->intersection_point= false; 807 rp0->pi= rp1->pi= p; 808 GCALC_DBUG_RETURN(0); 809 } 810 811 812 int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si) 813 { 814 Gcalc_point_iterator pi(si); 815 int prev_state= 0; 816 int sav_prev_state; 817 active_thread *prev_range= NULL; 818 const Gcalc_scan_iterator::event_point *events; 819 const Gcalc_scan_iterator::point *eq_start; 820 active_thread **cur_t_hook= &m_first_active_thread; 821 active_thread **starting_t_hook; 822 active_thread *bottom_threads= NULL; 823 active_thread *eq_thread, *point_thread;; 824 GCALC_DBUG_ENTER("Gcalc_operation_reducer::count_slice"); 825 826 m_fn->clear_i_states(); 827 /* Walk to the event, remembering what is needed. */ 828 for (; pi.point() != si->get_event_position(); 829 ++pi, cur_t_hook= (active_thread **) &(*cur_t_hook)->next) 830 { 831 active_thread *cur_t= *cur_t_hook; 832 if (cur_t->enabled() && 833 cur_t->rp->type == Gcalc_function::shape_polygon) 834 { 835 prev_state^= 1; 836 prev_range= prev_state ? cur_t : 0; 837 } 838 if (m_fn->get_shape_kind(pi.get_shape()) == Gcalc_function::shape_polygon) 839 m_fn->invert_i_state(pi.get_shape()); 840 } 841 842 events= si->get_events(); 843 if (events->simple_event()) 844 { 845 active_thread *cur_t= *cur_t_hook; 846 switch (events->event) 847 { 848 case scev_point: 849 { 850 if (cur_t->enabled() && 851 continue_range(cur_t, events->pi, events->next_pi)) 852 GCALC_DBUG_RETURN(1); 853 break; 854 } 855 case scev_end: 856 { 857 if (cur_t->enabled() && end_line(cur_t, si)) 858 GCALC_DBUG_RETURN(1); 859 *cur_t_hook= cur_t->get_next(); 860 free_item(cur_t); 861 break; 862 } 863 case scev_two_ends: 864 { 865 if (cur_t->enabled() && cur_t->get_next()->enabled()) 866 { 867 /* When two threads are ended here */ 868 if (end_couple(cur_t, cur_t->get_next(), events->pi)) 869 GCALC_DBUG_RETURN(1); 870 } 871 else if (cur_t->enabled() || cur_t->get_next()->enabled()) 872 { 873 /* Rare case when edges of a polygon coincide */ 874 if (end_line(cur_t->enabled() ? cur_t : cur_t->get_next(), si)) 875 GCALC_DBUG_RETURN(1); 876 } 877 *cur_t_hook= cur_t->get_next()->get_next(); 878 free_item(cur_t->next); 879 free_item(cur_t); 880 break; 881 } 882 default: 883 GCALC_DBUG_ASSERT(0); 884 } 885 GCALC_DBUG_RETURN(0); 886 } 887 888 starting_t_hook= cur_t_hook; 889 sav_prev_state= prev_state; 890 891 /* Walk through the event, collecting all the 'incoming' threads */ 892 for (; events; events= events->get_next()) 893 { 894 active_thread *cur_t= *cur_t_hook; 895 896 if (events->event == scev_single_point) 897 continue; 898 899 if (events->event == scev_thread || 900 events->event == scev_two_threads) 901 { 902 active_thread *new_t= new_active_thread(); 903 if (!new_t) 904 GCALC_DBUG_RETURN(1); 905 new_t->rp= NULL; 906 /* Insert into the main thread list before the current */ 907 new_t->next= cur_t; 908 *cur_t_hook= new_t; 909 cur_t_hook= (active_thread **) &new_t->next; 910 } 911 else 912 { 913 if (events->is_bottom()) 914 { 915 /* Move thread from the main list to the bottom_threads. */ 916 *cur_t_hook= cur_t->get_next(); 917 cur_t->next= bottom_threads; 918 bottom_threads= cur_t; 919 } 920 if (cur_t->enabled()) 921 { 922 if (cur_t->rp->type == Gcalc_function::shape_line) 923 { 924 GCALC_DBUG_ASSERT(!prev_state); 925 add_line(1, cur_t, events); 926 } 927 else 928 { 929 add_poly_border(1, cur_t, prev_state, events); 930 prev_state^= 1; 931 } 932 if (!events->is_bottom()) 933 { 934 active_thread *new_t= new_active_thread(); 935 if (!new_t) 936 GCALC_DBUG_RETURN(1); 937 new_t->rp= NULL; 938 /* Replace the current thread with the new. */ 939 new_t->next= cur_t->next; 940 *cur_t_hook= new_t; 941 cur_t_hook= (active_thread **) &new_t->next; 942 /* And move old to the bottom list */ 943 cur_t->next= bottom_threads; 944 bottom_threads= cur_t; 945 } 946 } 947 else if (!events->is_bottom()) 948 cur_t_hook= (active_thread **) &cur_t->next; 949 } 950 } 951 prev_state= sav_prev_state; 952 cur_t_hook= starting_t_hook; 953 954 eq_start= pi.point(); 955 eq_thread= point_thread= *starting_t_hook; 956 m_fn->clear_b_states(); 957 while (eq_start != si->get_event_end()) 958 { 959 const Gcalc_scan_iterator::point *cur_eq; 960 int in_state, after_state; 961 962 ++pi; 963 point_thread= point_thread->get_next(); 964 965 if (pi.point() != si->get_event_end() && 966 eq_start->cmp_dx_dy(pi.point()) == 0) 967 continue; 968 969 for (cur_eq= eq_start; cur_eq != pi.point(); cur_eq= cur_eq->get_next()) 970 m_fn->set_b_state(cur_eq->get_shape()); 971 in_state= m_fn->count(); 972 973 m_fn->clear_b_states(); 974 for (cur_eq= eq_start; cur_eq != pi.point(); cur_eq= cur_eq->get_next()) 975 { 976 gcalc_shape_info si= cur_eq->get_shape(); 977 if ((m_fn->get_shape_kind(si) == Gcalc_function::shape_polygon)) 978 m_fn->invert_i_state(si); 979 } 980 after_state= m_fn->count(); 981 if (prev_state != after_state) 982 { 983 if (add_poly_border(0, eq_thread, prev_state, eq_start)) 984 GCALC_DBUG_RETURN(1); 985 } 986 else if (!prev_state /* &&!after_state */ && in_state) 987 { 988 if (add_line(0, eq_thread, eq_start)) 989 GCALC_DBUG_RETURN(1); 990 } 991 992 prev_state= after_state; 993 eq_start= pi.point(); 994 eq_thread= point_thread; 995 } 996 997 if (!sav_prev_state && !m_poly_borders && !m_lines) 998 { 999 /* Check if we need to add the event point itself */ 1000 m_fn->clear_i_states(); 1001 /* b_states supposed to be clean already */ 1002 for (pi.restart(si); pi.point() != si->get_event_position(); ++pi) 1003 { 1004 if (m_fn->get_shape_kind(pi.get_shape()) == Gcalc_function::shape_polygon) 1005 m_fn->invert_i_state(pi.get_shape()); 1006 } 1007 for (events= si->get_events(); events; events= events->get_next()) 1008 m_fn->set_b_state(events->get_shape()); 1009 1010 GCALC_DBUG_RETURN(m_fn->count() ? add_single_point(si) : 0); 1011 } 1012 1013 if (m_poly_borders) 1014 { 1015 *m_poly_borders_hook= NULL; 1016 while (m_poly_borders) 1017 { 1018 poly_border *pb1, *pb2; 1019 pb1= m_poly_borders; 1020 GCALC_DBUG_ASSERT(m_poly_borders->next); 1021 1022 pb2= get_pair_border(pb1); 1023 /* Remove pb1 from the list. The pb2 already removed in get_pair_border. */ 1024 m_poly_borders= pb1->get_next(); 1025 if (connect_threads(pb1->incoming, pb2->incoming, 1026 pb1->t, pb2->t, pb1->p, pb2->p, 1027 prev_range, si, Gcalc_function::shape_polygon)) 1028 GCALC_DBUG_RETURN(1); 1029 1030 free_item(pb1); 1031 free_item(pb2); 1032 } 1033 m_poly_borders_hook= (Gcalc_dyn_list::Item **) &m_poly_borders; 1034 m_poly_borders= NULL; 1035 } 1036 1037 if (m_lines) 1038 { 1039 *m_lines_hook= NULL; 1040 if (m_lines->get_next() && 1041 !m_lines->get_next()->get_next()) 1042 { 1043 if (connect_threads(m_lines->incoming, m_lines->get_next()->incoming, 1044 m_lines->t, m_lines->get_next()->t, 1045 m_lines->p, m_lines->get_next()->p, 1046 NULL, si, Gcalc_function::shape_line)) 1047 GCALC_DBUG_RETURN(1); 1048 } 1049 else 1050 { 1051 for (line *cur_line= m_lines; cur_line; cur_line= cur_line->get_next()) 1052 { 1053 if (cur_line->incoming) 1054 { 1055 if (end_line(cur_line->t, si)) 1056 GCALC_DBUG_RETURN(1); 1057 } 1058 else 1059 start_line(cur_line->t, cur_line->p, si); 1060 } 1061 } 1062 free_list(m_lines); 1063 m_lines= NULL; 1064 m_lines_hook= (Gcalc_dyn_list::Item **) &m_lines; 1065 } 1066 1067 if (bottom_threads) 1068 free_list(bottom_threads); 1069 1070 GCALC_DBUG_RETURN(0); 1071 } 1072 1073 1074 int Gcalc_operation_reducer::add_single_point(const Gcalc_scan_iterator *si) 1075 { 1076 res_point *rp= add_res_point(Gcalc_function::shape_point); 1077 GCALC_DBUG_ENTER("Gcalc_operation_reducer::add_single_point"); 1078 if (!rp) 1079 GCALC_DBUG_RETURN(1); 1080 rp->glue= rp->up= rp->down= NULL; 1081 rp->set(si); 1082 GCALC_DBUG_RETURN(0); 1083 } 1084 1085 1086 Gcalc_operation_reducer::poly_border 1087 *Gcalc_operation_reducer::get_pair_border(poly_border *b1) 1088 { 1089 poly_border *prev_b= b1; 1090 poly_border *result= b1->get_next(); 1091 GCALC_DBUG_ENTER("Gcalc_operation_reducer::get_pair_border"); 1092 if (b1->prev_state) 1093 { 1094 if (b1->incoming) 1095 { 1096 /* Find the first outgoing, otherwise the last one. */ 1097 while (result->incoming && result->get_next()) 1098 { 1099 prev_b= result; 1100 result= result->get_next(); 1101 } 1102 } 1103 else 1104 { 1105 /* Get the last one */ 1106 while (result->get_next()) 1107 { 1108 prev_b= result; 1109 result= result->get_next(); 1110 } 1111 } 1112 } 1113 else /* !b1->prev_state */ 1114 { 1115 if (b1->incoming) 1116 { 1117 /* Get the next incoming, otherwise the last one. */ 1118 while (!result->incoming && result->get_next()) 1119 { 1120 prev_b= result; 1121 result= result->get_next(); 1122 } 1123 } 1124 else 1125 { 1126 /* Just pick the next one */ 1127 } 1128 } 1129 /* Delete the result from the list. */ 1130 prev_b->next= result->next; 1131 GCALC_DBUG_RETURN(result); 1132 } 1133 1134 1135 int Gcalc_operation_reducer::connect_threads( 1136 int incoming_a, int incoming_b, 1137 active_thread *ta, active_thread *tb, 1138 const Gcalc_scan_iterator::point *pa, const Gcalc_scan_iterator::point *pb, 1139 active_thread *prev_range, 1140 const Gcalc_scan_iterator *si, Gcalc_function::shape_type s_t) 1141 { 1142 GCALC_DBUG_ENTER("Gcalc_operation_reducer::connect_threads"); 1143 GCALC_DBUG_PRINT(("incoming %d %d", incoming_a, incoming_b)); 1144 if (incoming_a && incoming_b) 1145 { 1146 res_point *rpa, *rpb; 1147 GCALC_DBUG_ASSERT(ta->rp->type == tb->rp->type); 1148 if (!(rpa= add_res_point(ta->rp->type)) || 1149 !(rpb= add_res_point(ta->rp->type))) 1150 GCALC_DBUG_RETURN(1); 1151 rpa->down= ta->rp; 1152 rpb->down= tb->rp; 1153 rpb->glue= rpa; 1154 rpa->glue= rpb; 1155 rpa->up= rpb->up= NULL; 1156 ta->rp->up= rpa; 1157 tb->rp->up= rpb; 1158 rpa->set(si); 1159 rpb->set(si); 1160 ta->rp= tb->rp= NULL; 1161 GCALC_DBUG_RETURN(0); 1162 } 1163 if (!incoming_a) 1164 { 1165 GCALC_DBUG_ASSERT(!incoming_b); 1166 1167 res_point *rp0, *rp1; 1168 if (!(rp0= add_res_point(s_t)) || !(rp1= add_res_point(s_t))) 1169 GCALC_DBUG_RETURN(1); 1170 rp0->glue= rp1; 1171 rp1->glue= rp0; 1172 rp0->set(si); 1173 rp1->set(si); 1174 rp0->down= rp1->down= NULL; 1175 ta->rp= rp0; 1176 tb->rp= rp1; 1177 ta->p1= pa->pi; 1178 ta->p2= pa->next_pi; 1179 1180 tb->p1= pb->pi; 1181 tb->p2= pb->next_pi; 1182 1183 if (prev_range) 1184 { 1185 rp0->outer_poly= prev_range->thread_start; 1186 tb->thread_start= prev_range->thread_start; 1187 /* Check if needed */ 1188 ta->thread_start= prev_range->thread_start; 1189 } 1190 else 1191 { 1192 rp0->outer_poly= 0; 1193 ta->thread_start= rp0; 1194 /* Check if needed */ 1195 tb->thread_start= rp0; 1196 } 1197 GCALC_DBUG_RETURN(0); 1198 } 1199 /* else, if only ta is incoming */ 1200 1201 GCALC_DBUG_ASSERT(tb != ta); 1202 tb->rp= ta->rp; 1203 tb->thread_start= ta->thread_start; 1204 if (Gcalc_scan_iterator::point:: 1205 cmp_dx_dy(ta->p1, ta->p2, pb->pi, pb->next_pi) != 0) 1206 { 1207 if (si->intersection_step() ? 1208 continue_i_range(tb, si->get_cur_pi()) : 1209 continue_range(tb, si->get_cur_pi(), pb->next_pi)) 1210 GCALC_DBUG_RETURN(1); 1211 } 1212 tb->p1= pb->pi; 1213 tb->p2= pb->next_pi; 1214 1215 GCALC_DBUG_RETURN(0); 1216 } 1217 1218 1219 int Gcalc_operation_reducer::start_line(active_thread *t, 1220 const Gcalc_scan_iterator::point *p, 1221 const Gcalc_scan_iterator *si) 1222 { 1223 res_point *rp= add_res_point(Gcalc_function::shape_line); 1224 GCALC_DBUG_ENTER("Gcalc_operation_reducer::start_line"); 1225 if (!rp) 1226 GCALC_DBUG_RETURN(1); 1227 rp->glue= rp->down= NULL; 1228 rp->set(si); 1229 t->rp= rp; 1230 t->p1= p->pi; 1231 t->p2= p->next_pi; 1232 GCALC_DBUG_RETURN(0); 1233 } 1234 1235 1236 int Gcalc_operation_reducer::end_line(active_thread *t, 1237 const Gcalc_scan_iterator *si) 1238 { 1239 GCALC_DBUG_ENTER("Gcalc_operation_reducer::end_line"); 1240 GCALC_DBUG_ASSERT(t->rp->type == Gcalc_function::shape_line); 1241 res_point *rp= add_res_point(Gcalc_function::shape_line); 1242 if (!rp) 1243 GCALC_DBUG_RETURN(1); 1244 rp->glue= rp->up= NULL; 1245 rp->down= t->rp; 1246 rp->set(si); 1247 t->rp->up= rp; 1248 t->rp= NULL; 1249 1250 GCALC_DBUG_RETURN(0); 1251 } 1252 1253 1254 int Gcalc_operation_reducer::count_all(Gcalc_heap *hp) 1255 { 1256 Gcalc_scan_iterator si; 1257 GCALC_DBUG_ENTER("Gcalc_operation_reducer::count_all"); 1258 si.init(hp); 1259 GCALC_SET_TERMINATED(si.killed, killed); 1260 while (si.more_points()) 1261 { 1262 if (si.step()) 1263 GCALC_DBUG_RETURN(1); 1264 if (count_slice(&si)) 1265 GCALC_DBUG_RETURN(1); 1266 } 1267 GCALC_DBUG_RETURN(0); 1268 } 1269 1270 inline void Gcalc_operation_reducer::free_result(res_point *res) 1271 { 1272 if ((*res->prev_hook= res->next)) 1273 { 1274 res->get_next()->prev_hook= res->prev_hook; 1275 } 1276 free_item(res); 1277 } 1278 1279 1280 inline int Gcalc_operation_reducer::get_single_result(res_point *res, 1281 Gcalc_result_receiver *storage) 1282 { 1283 GCALC_DBUG_ENTER("Gcalc_operation_reducer::get_single_result"); 1284 if (res->intersection_point) 1285 { 1286 double x, y; 1287 res->pi->calc_xy(&x, &y); 1288 if (storage->single_point(x,y)) 1289 GCALC_DBUG_RETURN(1); 1290 } 1291 else 1292 if (storage->single_point(res->pi->node.shape.x, res->pi->node.shape.y)) 1293 GCALC_DBUG_RETURN(1); 1294 free_result(res); 1295 GCALC_DBUG_RETURN(0); 1296 } 1297 1298 1299 int Gcalc_operation_reducer::get_result_thread(res_point *cur, 1300 Gcalc_result_receiver *storage, 1301 int move_upward, 1302 res_point *first_poly_node) 1303 { 1304 res_point *next; 1305 bool glue_step= false; 1306 double x, y; 1307 GCALC_DBUG_ENTER("Gcalc_operation_reducer::get_result_thread"); 1308 while (cur) 1309 { 1310 if (!glue_step) 1311 { 1312 if (cur->intersection_point) 1313 { 1314 cur->pi->calc_xy(&x, &y); 1315 } 1316 else 1317 { 1318 x= cur->pi->node.shape.x; 1319 y= cur->pi->node.shape.y; 1320 } 1321 if (storage->add_point(x, y)) 1322 GCALC_DBUG_RETURN(1); 1323 } 1324 1325 next= move_upward ? cur->up : cur->down; 1326 if (!next && !glue_step) 1327 { 1328 next= cur->glue; 1329 move_upward^= 1; 1330 glue_step= true; 1331 if (next) 1332 next->glue= NULL; 1333 } 1334 else 1335 glue_step= false; 1336 1337 cur->first_poly_node= first_poly_node; 1338 free_result(cur); 1339 cur= next; 1340 } 1341 GCALC_DBUG_RETURN(0); 1342 } 1343 1344 1345 int Gcalc_operation_reducer::get_polygon_result(res_point *cur, 1346 Gcalc_result_receiver *storage, 1347 res_point *first_poly_node) 1348 { 1349 GCALC_DBUG_ENTER("Gcalc_operation_reducer::get_polygon_result"); 1350 res_point *glue= cur->glue; 1351 glue->up->down= NULL; 1352 free_result(glue); 1353 GCALC_DBUG_RETURN(get_result_thread(cur, storage, 1, first_poly_node) || 1354 storage->complete_shape()); 1355 } 1356 1357 1358 int Gcalc_operation_reducer::get_line_result(res_point *cur, 1359 Gcalc_result_receiver *storage) 1360 { 1361 res_point *next; 1362 res_point *cur_orig= cur; 1363 int move_upward= 1; 1364 GCALC_DBUG_ENTER("Gcalc_operation_reducer::get_line_result"); 1365 if (cur->glue) 1366 { 1367 /* Here we have to find the beginning of the line */ 1368 next= cur->up; 1369 move_upward= 1; 1370 while (next) 1371 { 1372 cur= next; 1373 next= move_upward ? next->up : next->down; 1374 if (!next) 1375 { 1376 next= cur->glue; 1377 if (next == cur_orig) 1378 { 1379 /* It's the line loop */ 1380 cur= cur_orig; 1381 cur->glue->glue= NULL; 1382 move_upward= 1; 1383 break; 1384 } 1385 move_upward^= 1; 1386 } 1387 } 1388 } 1389 1390 GCALC_DBUG_RETURN(get_result_thread(cur, storage, move_upward, 0) || 1391 storage->complete_shape()); 1392 } 1393 1394 1395 int Gcalc_operation_reducer::get_result(Gcalc_result_receiver *storage) 1396 { 1397 poly_instance *polygons= NULL; 1398 1399 GCALC_DBUG_ENTER("Gcalc_operation_reducer::get_result"); 1400 *m_res_hook= NULL; 1401 1402 /* This is to workaround an old gcc's bug */ 1403 if (m_res_hook == (Gcalc_dyn_list::Item **) &m_result) 1404 goto done; 1405 1406 while (m_result) 1407 { 1408 Gcalc_function::shape_type shape= m_result->type; 1409 if (shape == Gcalc_function::shape_point) 1410 { 1411 if (get_single_result(m_result, storage)) 1412 GCALC_DBUG_RETURN(1); 1413 continue; 1414 } 1415 if (shape == Gcalc_function::shape_polygon) 1416 { 1417 if (m_result->outer_poly) 1418 { 1419 uint32 insert_position, hole_position, position_shift; 1420 poly_instance *cur_poly; 1421 insert_position= m_result->outer_poly->first_poly_node->poly_position; 1422 GCALC_DBUG_ASSERT(insert_position); 1423 hole_position= storage->position(); 1424 storage->start_shape(Gcalc_function::shape_hole); 1425 if (get_polygon_result(m_result, storage, 1426 m_result->outer_poly->first_poly_node) || 1427 storage->move_hole(insert_position, hole_position, 1428 &position_shift)) 1429 GCALC_DBUG_RETURN(1); 1430 for (cur_poly= polygons; 1431 cur_poly && *cur_poly->after_poly_position >= insert_position; 1432 cur_poly= cur_poly->get_next()) 1433 *cur_poly->after_poly_position+= position_shift; 1434 } 1435 else 1436 { 1437 uint32 *poly_position= &m_result->poly_position; 1438 poly_instance *p= new_poly(); 1439 p->after_poly_position= poly_position; 1440 p->next= polygons; 1441 polygons= p; 1442 storage->start_shape(Gcalc_function::shape_polygon); 1443 if (get_polygon_result(m_result, storage, m_result)) 1444 GCALC_DBUG_RETURN(1); 1445 *poly_position= storage->position(); 1446 } 1447 } 1448 else 1449 { 1450 storage->start_shape(shape); 1451 if (get_line_result(m_result, storage)) 1452 GCALC_DBUG_RETURN(1); 1453 } 1454 } 1455 1456 done: 1457 m_res_hook= (Gcalc_dyn_list::Item **)&m_result; 1458 storage->done(); 1459 GCALC_DBUG_RETURN(0); 1460 } 1461 1462 1463 void Gcalc_operation_reducer::reset() 1464 { 1465 free_list((Gcalc_heap::Item **) &m_result, m_res_hook); 1466 m_res_hook= (Gcalc_dyn_list::Item **)&m_result; 1467 free_list(m_first_active_thread); 1468 } 1469 1470 #endif /*HAVE_SPATIAL*/ 1471 1472