From 788043cd0b20e01fc07f8a4673de678404938240 Mon Sep 17 00:00:00 2001 From: Alexey Botchkov Date: Wed, 4 May 2011 23:20:17 +0500 Subject: Precise GIS functions added. --- sql/gcalc_tools.cc | 1156 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 1156 insertions(+) create mode 100644 sql/gcalc_tools.cc (limited to 'sql/gcalc_tools.cc') diff --git a/sql/gcalc_tools.cc b/sql/gcalc_tools.cc new file mode 100644 index 00000000000..0e2970116ce --- /dev/null +++ b/sql/gcalc_tools.cc @@ -0,0 +1,1156 @@ +/* Copyright (c) 2000, 2010 Oracle and/or its affiliates. All rights reserved. + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; version 2 of the License. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */ + + +#include "mysql_priv.h" + +#ifdef HAVE_SPATIAL + +#include "gcalc_tools.h" +#include "spatial.h" + +#define float_to_coord(d) ((double) d) + + +/* + Adds new shape to the relation. + After that it can be used as an argument of an operation. +*/ + +gcalc_shape_info Gcalc_function::add_new_shape(uint32 shape_id, + shape_type shape_kind) +{ + shapes_buffer.q_append((uint32) shape_kind); + return n_shapes++; +} + + +/* + Adds new operation to the constructed relation. + To construct the complex relation one has to specify operations + in prefix style. +*/ + +void Gcalc_function::add_operation(op_type operation, uint32 n_operands) +{ + uint32 op_code= (uint32 ) operation + n_operands; + function_buffer.q_append(op_code); +} + + +/* + Sometimes the number of arguments is unknown at the moment the operation + is added. That allows to specify it later. +*/ + +void Gcalc_function::add_operands_to_op(uint32 operation_pos, uint32 n_operands) +{ + uint32 op_code= uint4korr(function_buffer.ptr() + operation_pos) + n_operands; + function_buffer.write_at_position(operation_pos, op_code); +} + + +/* + Just like the add_operation() but the result will be the inverted + value of an operation. +*/ + +void Gcalc_function::add_not_operation(op_type operation, uint32 n_operands) +{ + uint32 op_code= ((uint32) op_not | (uint32 ) operation) + n_operands; + function_buffer.q_append(op_code); +} + + +int Gcalc_function::single_shape_op(shape_type shape_kind, gcalc_shape_info *si) +{ + if (reserve_shape_buffer(1) || reserve_op_buffer(1)) + return 1; + *si= add_new_shape(0, shape_kind); + add_operation(op_shape, *si); + return 0; +} + + +/* + Specify how many arguments we're going to have. +*/ + +int Gcalc_function::reserve_shape_buffer(uint n_shapes) +{ + return shapes_buffer.reserve(n_shapes * 4, 512); +} + + +/* + Specify how many operations we're going to have. +*/ + +int Gcalc_function::reserve_op_buffer(uint n_ops) +{ + return function_buffer.reserve(n_ops * 4, 512); +} + + +int Gcalc_function::alloc_states() +{ + if (function_buffer.reserve((n_shapes+1) * sizeof(int))) + return 1; + i_states= (int *) (function_buffer.ptr() + ALIGN_SIZE(function_buffer.length())); + return 0; +} + + +int Gcalc_function::count_internal() +{ + int c_op= uint4korr(cur_func); + op_type next_func= (op_type) (c_op & op_any); + int mask= (c_op & op_not) ? 1:0; + int n_ops= c_op & ~op_any; + int result; + + cur_func+= 4; + if (next_func == op_shape) + return i_states[c_op & ~(op_any | op_not)] ^ mask; + + result= count_internal(); + + while (--n_ops) + { + int next_res= count_internal(); + switch (next_func) + { + case op_union: + result= result | next_res; + break; + case op_intersection: + result= result & next_res; + break; + case op_symdifference: + result= result ^ next_res; + break; + case op_difference: + result= result & !next_res; + break; + case op_backdifference: + result= !result & next_res; + break; + default: + DBUG_ASSERT(FALSE); + }; + } + + return result ^ mask; +} + + +/* + Clear the state of the object. +*/ + +void Gcalc_function::reset() +{ + n_shapes= 0; + shapes_buffer.length(0); + function_buffer.length(0); +} + + +int Gcalc_function::find_function(Gcalc_scan_iterator &scan_it) +{ + while (scan_it.more_points()) + { + if (scan_it.step()) + return -1; + Gcalc_scan_events ev= scan_it.get_event(); + const Gcalc_scan_iterator::point *evpos= scan_it.get_event_position(); + if (ev & (scev_point | scev_end | scev_two_ends)) + continue; + + clear_state(); + for (Gcalc_point_iterator pit(&scan_it); pit.point() != evpos; ++pit) + { + gcalc_shape_info si= pit.point()->get_shape(); + if ((get_shape_kind(si) == Gcalc_function::shape_polygon)) + invert_state(si); + } + invert_state(evpos->get_shape()); + + if (ev == scev_intersection) + { + const Gcalc_scan_iterator::point *evnext= evpos->c_get_next(); + if ((get_shape_kind(evpos->get_shape()) != + Gcalc_function::shape_polygon) || + (get_shape_kind(evnext->get_shape()) != + Gcalc_function::shape_polygon)) + invert_state(evnext->get_shape()); + } + + if (count()) + return 1; + } + return 0; +} + + +int Gcalc_operation_transporter::single_point(double x, double y) +{ + gcalc_shape_info si; + return m_fn->single_shape_op(Gcalc_function::shape_point, &si) || + int_single_point(si, x, y); +} + + +int Gcalc_operation_transporter::start_line() +{ + int_start_line(); + return m_fn->single_shape_op(Gcalc_function::shape_line, &m_si); +} + + +int Gcalc_operation_transporter::complete_line() +{ + int_complete_line(); + return 0; +} + + +int Gcalc_operation_transporter::start_poly() +{ + int_start_poly(); + return m_fn->single_shape_op(Gcalc_function::shape_polygon, &m_si); +} + + +int Gcalc_operation_transporter::complete_poly() +{ + int_complete_poly(); + return 0; +} + + +int Gcalc_operation_transporter::start_ring() +{ + int_start_ring(); + return 0; +} + + +int Gcalc_operation_transporter::complete_ring() +{ + int_complete_ring(); + return 0; +} + + +int Gcalc_operation_transporter::add_point(double x, double y) +{ + return int_add_point(m_si, x, y); +} + + +int Gcalc_operation_transporter::start_collection(int n_objects) +{ + if (m_fn->reserve_shape_buffer(n_objects) || m_fn->reserve_op_buffer(1)) + return 1; + m_fn->add_operation(Gcalc_function::op_union, n_objects); + return 0; +} + + +int Gcalc_result_receiver::start_shape(Gcalc_function::shape_type shape) +{ + if (buffer.reserve(4*2, 512)) + return 1; + cur_shape= shape; + shape_pos= buffer.length(); + buffer.length(shape_pos + ((shape == Gcalc_function::shape_point) ? 4:8)); + n_points= 0; + shape_area= 0.0; + + return 0; +} + + +int Gcalc_result_receiver::add_point(double x, double y) +{ + if (n_points && x == prev_x && y == prev_y) + return 0; + + if (!n_points++) + { + prev_x= first_x= x; + prev_y= first_y= y; + return 0; + } + + shape_area+= prev_x*y - prev_y*x; + + if (buffer.reserve(8*2, 512)) + return 1; + buffer.q_append(prev_x); + buffer.q_append(prev_y); + prev_x= x; + prev_y= y; + return 0; +} + + +int Gcalc_result_receiver::complete_shape() +{ + if (n_points == 0) + { + buffer.length(shape_pos); + return 0; + } + if (n_points == 1) + { + if (cur_shape != Gcalc_function::shape_point) + { + cur_shape= Gcalc_function::shape_point; + buffer.length(buffer.length()-4); + } + } + else + { + DBUG_ASSERT(cur_shape != Gcalc_function::shape_point); + if (cur_shape == Gcalc_function::shape_hole) + { + shape_area+= prev_x*first_y - prev_y*first_x; + if (fabs(shape_area) < 1e-8) + { + buffer.length(shape_pos); + return 0; + } + } + + if ((cur_shape == Gcalc_function::shape_polygon || + cur_shape == Gcalc_function::shape_hole) && + prev_x == first_x && prev_y == first_y) + { + n_points--; + buffer.write_at_position(shape_pos+4, n_points); + goto do_complete; + } + buffer.write_at_position(shape_pos+4, n_points); + } + + if (buffer.reserve(8*2, 512)) + return 1; + buffer.q_append(prev_x); + buffer.q_append(prev_y); + +do_complete: + buffer.write_at_position(shape_pos, (uint32) cur_shape); + + if (!n_shapes++) + { + DBUG_ASSERT(cur_shape != Gcalc_function::shape_hole); + common_shapetype= cur_shape; + } + else if (cur_shape == Gcalc_function::shape_hole) + { + ++n_holes; + } + else if (!collection_result && (cur_shape != common_shapetype)) + { + collection_result= true; + } + return 0; +} + + +int Gcalc_result_receiver::single_point(double x, double y) +{ + return start_shape(Gcalc_function::shape_point) || + add_point(x, y) || + complete_shape(); +} + + +int Gcalc_result_receiver::done() +{ + return 0; +} + + +void Gcalc_result_receiver::reset() +{ + buffer.length(0); + collection_result= FALSE; + n_shapes= n_holes= 0; +} + + +int Gcalc_result_receiver::get_result_typeid() +{ + if (!n_shapes) + return 0; + + if (collection_result) + return Geometry::wkb_geometrycollection; + switch (common_shapetype) + { + case Gcalc_function::shape_polygon: + return (n_shapes - n_holes == 1) ? + Geometry::wkb_polygon : Geometry::wkb_multipolygon; + case Gcalc_function::shape_point: + return (n_shapes == 1) ? Geometry::wkb_point : Geometry::wkb_multipoint; + case Gcalc_function::shape_line: + return (n_shapes == 1) ? Geometry::wkb_linestring : + Geometry::wkb_multilinestring; + default: + DBUG_ASSERT(0); + } + return 0; +} + + +int Gcalc_result_receiver::move_hole(uint32 dest_position, uint32 source_position, + uint32 *new_dest_position) +{ + char *ptr; + int source_len; + if (dest_position == source_position) + { + *new_dest_position= position(); + return 0; + } + + source_len= buffer.length() - source_position; + if (buffer.reserve(source_len, MY_ALIGN(source_len, 512))) + return 1; + + ptr= (char *) buffer.ptr(); + memmove(ptr + dest_position + source_len, ptr + dest_position, + buffer.length() - dest_position); + memcpy(ptr + dest_position, ptr + buffer.length(), source_len); + *new_dest_position= dest_position + source_len; + return 0; +} + + +Gcalc_operation_reducer::Gcalc_operation_reducer(size_t blk_size) : + Gcalc_dyn_list(blk_size, sizeof(res_point)), + m_res_hook((Gcalc_dyn_list::Item **)&m_result), + m_first_active_thread(NULL) +{} + + +void Gcalc_operation_reducer::init(Gcalc_function *fn, modes mode) +{ + m_fn= fn; + m_mode= mode; + m_first_active_thread= NULL; +} + + +Gcalc_operation_reducer:: +Gcalc_operation_reducer(Gcalc_function *fn, modes mode, size_t blk_size) : + Gcalc_dyn_list(blk_size, sizeof(res_point)), + m_res_hook((Gcalc_dyn_list::Item **)&m_result) +{ + init(fn, mode); +} + + +inline int Gcalc_operation_reducer::continue_range(active_thread *t, + const Gcalc_heap::Info *p) +{ + DBUG_ASSERT(t->result_range); + res_point *rp= add_res_point(); + if (!rp) + return 1; + rp->glue= NULL; + rp->down= t->rp; + t->rp->up= rp; + rp->intersection_point= false; + rp->pi= p; + t->rp= rp; + return 0; +} + + +inline int Gcalc_operation_reducer::continue_i_range(active_thread *t, + const Gcalc_heap::Info *p, + double x, double y) +{ + DBUG_ASSERT(t->result_range); + res_point *rp= add_res_point(); + if (!rp) + return 1; + rp->glue= NULL; + rp->down= t->rp; + t->rp->up= rp; + rp->intersection_point= true; + rp->x= x; + rp->pi= p; + rp->y= y; + t->rp= rp; + return 0; +} + +inline int Gcalc_operation_reducer::start_range(active_thread *t, + const Gcalc_heap::Info *p) +{ + res_point *rp= add_res_point(); + if (!rp) + return 1; + rp->glue= rp->down= NULL; + rp->intersection_point= false; + rp->pi= p; + t->result_range= 1; + t->rp= rp; + return 0; +} + +inline int Gcalc_operation_reducer::start_i_range(active_thread *t, + const Gcalc_heap::Info *p, + double x, double y) +{ + res_point *rp= add_res_point(); + if (!rp) + return 1; + rp->glue= rp->down= NULL; + rp->intersection_point= true; + rp->x= x; + rp->y= y; + rp->pi= p; + t->result_range= 1; + t->rp= rp; + return 0; +} + +inline int Gcalc_operation_reducer::end_range(active_thread *t, + const Gcalc_heap::Info *p) +{ + res_point *rp= add_res_point(); + if (!rp) + return 1; + rp->glue= rp->up= NULL; + rp->down= t->rp; + rp->intersection_point= false; + rp->pi= p; + t->rp->up= rp; + t->result_range= 0; + return 0; +} + +inline int Gcalc_operation_reducer::end_i_range(active_thread *t, + const Gcalc_heap::Info *p, + double x, double y) +{ + res_point *rp= add_res_point(); + if (!rp) + return 1; + rp->glue= rp->up= NULL; + rp->down= t->rp; + rp->intersection_point= true; + rp->x= x; + rp->pi= p; + rp->y= y; + t->rp->up= rp; + t->result_range= 0; + return 0; +} + +int Gcalc_operation_reducer::start_couple(active_thread *t0, active_thread *t1, + const Gcalc_heap::Info *p, + const active_thread *prev_range) +{ + res_point *rp0, *rp1; + if (!(rp0= add_res_point()) || !(rp1= add_res_point())) + return 1; + rp0->glue= rp1; + rp1->glue= rp0; + rp0->intersection_point= rp1->intersection_point= false; + rp0->down= rp1->down= NULL; + rp0->pi= rp1->pi= p; + t0->rp= rp0; + t1->rp= rp1; + if (prev_range) + { + rp0->outer_poly= prev_range->thread_start; + t1->thread_start= prev_range->thread_start; + } + else + { + rp0->outer_poly= 0; + t0->thread_start= rp0; + } + return 0; +} + +int Gcalc_operation_reducer::start_i_couple(active_thread *t0, active_thread *t1, + const Gcalc_heap::Info *p0, + const Gcalc_heap::Info *p1, + double x, double y, + const active_thread *prev_range) +{ + res_point *rp0, *rp1; + if (!(rp0= add_res_point()) || !(rp1= add_res_point())) + return 1; + rp0->glue= rp1; + rp1->glue= rp0; + rp0->pi= p0; + rp1->pi= p1; + rp0->intersection_point= rp1->intersection_point= true; + rp0->down= rp1->down= NULL; + rp0->x= rp1->x= x; + rp0->y= rp1->y= y; + t0->result_range= t1->result_range= 1; + t0->rp= rp0; + t1->rp= rp1; + if (prev_range) + { + rp0->outer_poly= prev_range->thread_start; + t1->thread_start= prev_range->thread_start; + } + else + { + rp0->outer_poly= 0; + t0->thread_start= rp0; + } + return 0; +} + +int Gcalc_operation_reducer::end_couple(active_thread *t0, active_thread *t1, + const Gcalc_heap::Info *p) +{ + res_point *rp0, *rp1; + DBUG_ASSERT(t1->result_range); + if (!(rp0= add_res_point()) || !(rp1= add_res_point())) + return 1; + rp0->down= t0->rp; + rp1->down= t1->rp; + rp1->glue= rp0; + rp0->glue= rp1; + rp0->up= rp1->up= NULL; + t0->rp->up= rp0; + t1->rp->up= rp1; + rp0->intersection_point= rp1->intersection_point= false; + rp0->pi= rp1->pi= p; + t0->result_range= t1->result_range= 0; + return 0; +} + +int Gcalc_operation_reducer::end_i_couple(active_thread *t0, active_thread *t1, + const Gcalc_heap::Info *p0, + const Gcalc_heap::Info *p1, + double x, double y) +{ + res_point *rp0, *rp1; + if (!(rp0= add_res_point()) || !(rp1= add_res_point())) + return 1; + rp0->down= t0->rp; + rp1->down= t1->rp; + rp0->pi= p0; + rp1->pi= p1; + rp1->glue= rp0; + rp0->glue= rp1; + rp0->up= rp1->up= NULL; + rp0->intersection_point= rp1->intersection_point= true; + rp0->x= rp1->x= x; + rp0->y= rp1->y= y; + t0->result_range= t1->result_range= 0; + t0->rp->up= rp0; + t1->rp->up= rp1; + return 0; +} + +int Gcalc_operation_reducer::add_single_point(const Gcalc_heap::Info *p) +{ + res_point *rp= add_res_point(); + if (!rp) + return 1; + rp->glue= rp->up= rp->down= NULL; + rp->intersection_point= false; + rp->pi= p; + rp->x= p->x; + rp->y= p->y; + return 0; +} + +int Gcalc_operation_reducer::add_i_single_point(const Gcalc_heap::Info *p, + double x, double y) +{ + res_point *rp= add_res_point(); + if (!rp) + return 1; + rp->glue= rp->up= rp->down= NULL; + rp->intersection_point= true; + rp->x= x; + rp->pi= p; + rp->y= y; + return 0; +} + +int Gcalc_operation_reducer:: +handle_lines_intersection(active_thread *t0, active_thread *t1, + const Gcalc_heap::Info *p0, const Gcalc_heap::Info *p1, + double x, double y) +{ + m_fn->invert_state(p0->shape); + m_fn->invert_state(p1->shape); + int intersection_state= m_fn->count(); + if ((t0->result_range | t1->result_range) == intersection_state) + return 0; + + if (t0->result_range && + (end_i_range(t0, p1, x, y) || start_i_range(t0, p1, x, y))) + return 1; + + if (t1->result_range && + (end_i_range(t1, p0, x, y) || start_i_range(t1, p0, x, y))) + return 1; + + if (intersection_state && + add_i_single_point(p0, x, y)) + return 1; + + return 0; +} + +inline int Gcalc_operation_reducer:: +handle_line_polygon_intersection(active_thread *l, const Gcalc_heap::Info *pl, + int line_state, int poly_state, + double x, double y) +{ + int range_after= ~poly_state & line_state; + if (l->result_range == range_after) + return 0; + return range_after ? start_i_range(l, pl, x, y) : end_i_range(l, pl, x, y); +} + +static inline void switch_athreads(Gcalc_operation_reducer::active_thread *t0, + Gcalc_operation_reducer::active_thread *t1, + Gcalc_dyn_list::Item **hook) +{ + *hook= t1; + t0->next= t1->next; + t1->next= t0; +} + +inline int Gcalc_operation_reducer:: +handle_polygons_intersection(active_thread *t0, active_thread *t1, + Gcalc_dyn_list::Item **t_hook, + const Gcalc_heap::Info *p0, + const Gcalc_heap::Info *p1, + int prev_state, double x, double y, + const active_thread *prev_range) +{ + m_fn->invert_state(p0->shape); + int state_11= m_fn->count(); + m_fn->invert_state(p1->shape); + int state_2= m_fn->count(); + int state_01= prev_state ^ t0->result_range; + if ((prev_state == state_01) && (prev_state == state_2)) + { + if (state_11 == prev_state) + { + switch_athreads(t0, t1, t_hook); + return 0; + } + return start_i_couple(t0, t1, p0, p1, x, y, prev_range); + } + if (prev_state == state_2) + { + if (state_01 == state_11) + { + if (m_mode & polygon_selfintersections_allowed) + { + switch_athreads(t0, t1, t_hook); + return 0; + } + if (prev_state != (m_mode & prefer_big_with_holes)) + return continue_i_range(t0, p0, x, y) || continue_i_range(t1, p1, x, y); + return end_i_couple(t0, t1, p0, p1, x, y) || + start_i_couple(t0, t1, p0, p1, x, y, prev_range); + } + else + return end_i_couple(t0, t1, p0, p1, x, y); + } + if (state_01 ^ state_11) + { + switch_athreads(t0, t1, t_hook); + return 0; + } + + active_thread *thread_to_continue; + const Gcalc_heap::Info *way_to_go; + if (prev_state == state_01) + { + thread_to_continue= t1; + way_to_go= p1; + } + else + { + thread_to_continue= t0; + way_to_go= p0; + } + return continue_i_range(thread_to_continue, way_to_go, x, y); +} + +int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si) +{ + Gcalc_point_iterator pi(si); + active_thread *cur_t= m_first_active_thread; + Gcalc_dyn_list::Item **at_hook= (Gcalc_dyn_list::Item **)&m_first_active_thread; + const active_thread *prev_range; + int prev_state; + + if (si->get_event() & (scev_point | scev_end | scev_two_ends)) + { + for (; pi.point() != si->get_event_position(); ++pi, cur_t= cur_t->get_next()) + at_hook= &cur_t->next; + + switch (si->get_event()) + { + case scev_point: + { + if (cur_t->result_range && + continue_range(cur_t, pi.get_pi())) + return 1; + break; + } + case scev_end: + { + if (cur_t->result_range && + end_range(cur_t, pi.get_pi())) + return 1; + *at_hook= cur_t->next; + free_item(cur_t); + break; + } + case scev_two_ends: + { + active_thread *cur_t1= cur_t->get_next(); + if (cur_t->result_range && + end_couple(cur_t, cur_t1, pi.get_pi())) + return 1; + + *at_hook= cur_t1->next; + free_list(cur_t, &cur_t1->next); + break; + } + default: + DBUG_ASSERT(0); + } + return 0; + } + + prev_state= 0; + prev_range= 0; + + m_fn->clear_state(); + for (; pi.point() != si->get_event_position(); ++pi, cur_t= cur_t->get_next()) + { + if (m_fn->get_shape_kind(pi.get_shape()) == Gcalc_function::shape_polygon) + { + m_fn->invert_state(pi.get_shape()); + prev_state^= cur_t->result_range; + } + at_hook= &cur_t->next; + if (cur_t->result_range) + prev_range= prev_state ? cur_t : 0; + } + + switch (si->get_event()) + { + case scev_thread: + { + active_thread *new_t= new_active_thread(); + if (!new_t) + return 1; + m_fn->invert_state(pi.get_shape()); + new_t->result_range= prev_state ^ m_fn->count(); + new_t->next= *at_hook; + *at_hook= new_t; + if (new_t->result_range && + start_range(new_t, pi.get_pi())) + return 1; + break; + } + case scev_two_threads: + { + active_thread *new_t0, *new_t1; + int fn_result; + if (!(new_t0= new_active_thread()) || !(new_t1= new_active_thread())) + return 1; + + m_fn->invert_state(pi.get_shape()); + fn_result= m_fn->count(); + new_t0->result_range= new_t1->result_range= prev_state ^ fn_result; + new_t1->next= *at_hook; + new_t0->next= new_t1; + *at_hook= new_t0; + if (new_t0->result_range && + start_couple(new_t0, new_t1, pi.get_pi(), prev_range)) + return 1; + break; + } + case scev_intersection: + { + active_thread *cur_t1= cur_t->get_next(); + const Gcalc_heap::Info *p0, *p1; + p0= pi.get_pi(); + ++pi; + p1= pi.get_pi(); + bool line0= m_fn->get_shape_kind(p0->shape) == Gcalc_function::shape_line; + bool line1= m_fn->get_shape_kind(p1->shape) == Gcalc_function::shape_line; + + if (!line0 && !line1) /* two polygons*/ + { + if (handle_polygons_intersection(cur_t, cur_t1, at_hook, p0, p1, + prev_state, pi.get_x(), si->get_y(), + prev_range)) + return 1; + } + else if (line0 && line1) + { + if (!prev_state && + handle_lines_intersection(cur_t, cur_t1, + p0, p1, pi.get_x(), si->get_y())) + return 1; + switch_athreads(cur_t, cur_t1, at_hook); + } + else + { + int poly_state; + int line_state; + const Gcalc_heap::Info *line; + active_thread *line_t; + m_fn->invert_state(p0->shape); + if (line0) + { + line_state= m_fn->count(); + poly_state= prev_state; + line= p0; + line_t= cur_t1; + } + else + { + poly_state= m_fn->count(); + m_fn->invert_state(p1->shape); + line_state= m_fn->count(); + line= p1; + line_t= cur_t; + } + if (handle_line_polygon_intersection(line_t, line, + line_state, poly_state, + pi.get_x(), si->get_y())) + return 1; + switch_athreads(cur_t, cur_t1, at_hook); + } + break; + } + case scev_single_point: + { + m_fn->invert_state(pi.get_shape()); + if ((prev_state ^ m_fn->count()) && + add_single_point(pi.get_pi())) + return 1; + break; + } + default: + DBUG_ASSERT(0); + } + + return 0; +} + +int Gcalc_operation_reducer::count_all(Gcalc_heap *hp) +{ + Gcalc_scan_iterator si; + si.init(hp); + while (si.more_points()) + { + if (si.step()) + return 1; + if (count_slice(&si)) + return 1; + } + return 0; +} + +inline void Gcalc_operation_reducer::free_result(res_point *res) +{ + if ((*res->prev_hook= res->next)) + { + res->get_next()->prev_hook= res->prev_hook; + } + free_item(res); +} + + +inline int Gcalc_operation_reducer::get_single_result(res_point *res, + Gcalc_result_receiver *storage) +{ + if (res->intersection_point) + { + if (storage->single_point(float_to_coord(res->x), + float_to_coord(res->y))) + return 1; + } + else + if (storage->single_point(res->x, res->y)) + return 1; + free_result(res); + return 0; +} + + +int Gcalc_operation_reducer::get_result_thread(res_point *cur, + Gcalc_result_receiver *storage, + int move_upward) +{ + res_point *next; + bool glue_step= false; + res_point *first_poly_node= cur; + double x, y; + while (cur) + { + if (!glue_step) + { + if (cur->intersection_point) + { + x= float_to_coord(cur->x); + y= float_to_coord(cur->y); + } + else + { + x= cur->pi->x; + y= cur->pi->y; + } + if (storage->add_point(x, y)) + return 1; + } + + next= move_upward ? cur->up : cur->down; + if (!next && !glue_step) + { + next= cur->glue; + move_upward^= 1; + glue_step= true; + if (next) + next->glue= NULL; + } + else + glue_step= false; + + cur->first_poly_node= first_poly_node; + free_result(cur); + cur= next; + } + return 0; +} + + +int Gcalc_operation_reducer::get_polygon_result(res_point *cur, + Gcalc_result_receiver *storage) +{ + res_point *glue= cur->glue; + glue->up->down= NULL; + free_result(glue); + return get_result_thread(cur, storage, 1) || + storage->complete_shape(); +} + + +int Gcalc_operation_reducer::get_line_result(res_point *cur, + Gcalc_result_receiver *storage) +{ + res_point *next; + int move_upward= 1; + if (cur->glue) + { + /* Here we have to find the beginning of the line */ + next= cur->up; + move_upward= 1; + while (next) + { + cur= next; + next= move_upward ? next->up : next->down; + if (!next) + { + next= cur->glue; + move_upward^= 1; + } + } + } + + return get_result_thread(cur, storage, move_upward) || + storage->complete_shape(); +} + + +int Gcalc_operation_reducer::get_result(Gcalc_result_receiver *storage) +{ + *m_res_hook= NULL; + while (m_result) + { + if (!m_result->up) + { + if (get_single_result(m_result, storage)) + return 1; + continue; + } + Gcalc_function::shape_type shape= m_fn->get_shape_kind(m_result->pi->shape); + if (shape == Gcalc_function::shape_polygon) + { + if (m_result->outer_poly) + { + uint32 *insert_position, hole_position; + insert_position= &m_result->outer_poly->first_poly_node->poly_position; + DBUG_ASSERT(*insert_position); + hole_position= storage->position(); + storage->start_shape(Gcalc_function::shape_hole); + if (get_polygon_result(m_result, storage) || + storage->move_hole(*insert_position, hole_position, + insert_position)) + return 1; + } + else + { + uint32 *poly_position= &m_result->poly_position; + storage->start_shape(Gcalc_function::shape_polygon); + if (get_polygon_result(m_result, storage)) + return 1; + *poly_position= storage->position(); + } + } + else + { + storage->start_shape(shape); + if (get_line_result(m_result, storage)) + return 1; + } + } + + m_res_hook= (Gcalc_dyn_list::Item **)&m_result; + storage->done(); + return 0; +} + + +void Gcalc_operation_reducer::reset() +{ + free_list(m_result, m_res_hook); + m_res_hook= (Gcalc_dyn_list::Item **)&m_result; + free_list(m_first_active_thread); +} + +#endif /*HAVE_SPATIAL*/ + -- cgit v1.2.1 From f3b850a7b52b5947eb694b5a1f73d0425de5bb0e Mon Sep 17 00:00:00 2001 From: Alexey Botchkov Date: Tue, 5 Jul 2011 19:42:35 +0500 Subject: bug #804305 Crash in wkb_get_double with ST_INTERSECTION. That crash happened with the complicated topology of the result. If we found a hole in a polygon whose outside border was already found, we need to paste the hole right after it and respectively shift polygons after it. Also we need to update poly_position fields in these polygons. That last thing wasn't properly done that led to the crash. To fix that we keep the list of the found polygons and update the poly_positions that are bigger or equal to where we placed the next hole. per-file comments: mysql-test/r/gis-precise.result bug #804305 Crash in wkb_get_double with ST_INTERSECTION. test result updated. mysql-test/t/gis-precise.test bug #804305 Crash in wkb_get_double with ST_INTERSECTION. test result added. sql/gcalc_tools.cc bug #804305 Crash in wkb_get_double with ST_INTERSECTION. keep the list of the found polygons and update their poly_position fields respectively. sql/gcalc_tools.h bug #804305 Crash in wkb_get_double with ST_INTERSECTION. Gcalc_result_receiver::move_hole interface changed. --- sql/gcalc_tools.cc | 31 ++++++++++++++++++++----------- 1 file changed, 20 insertions(+), 11 deletions(-) (limited to 'sql/gcalc_tools.cc') diff --git a/sql/gcalc_tools.cc b/sql/gcalc_tools.cc index 0e2970116ce..11d452cd8cf 100644 --- a/sql/gcalc_tools.cc +++ b/sql/gcalc_tools.cc @@ -419,17 +419,16 @@ int Gcalc_result_receiver::get_result_typeid() int Gcalc_result_receiver::move_hole(uint32 dest_position, uint32 source_position, - uint32 *new_dest_position) + uint32 *position_shift) { char *ptr; int source_len; + + *position_shift= source_len= buffer.length() - source_position; + if (dest_position == source_position) - { - *new_dest_position= position(); return 0; - } - source_len= buffer.length() - source_position; if (buffer.reserve(source_len, MY_ALIGN(source_len, 512))) return 1; @@ -437,7 +436,6 @@ int Gcalc_result_receiver::move_hole(uint32 dest_position, uint32 source_positio memmove(ptr + dest_position + source_len, ptr + dest_position, buffer.length() - dest_position); memcpy(ptr + dest_position, ptr + buffer.length(), source_len); - *new_dest_position= dest_position + source_len; return 0; } @@ -1098,6 +1096,8 @@ int Gcalc_operation_reducer::get_line_result(res_point *cur, int Gcalc_operation_reducer::get_result(Gcalc_result_receiver *storage) { + poly_instance *polygons= NULL; + *m_res_hook= NULL; while (m_result) { @@ -1112,19 +1112,28 @@ int Gcalc_operation_reducer::get_result(Gcalc_result_receiver *storage) { if (m_result->outer_poly) { - uint32 *insert_position, hole_position; - insert_position= &m_result->outer_poly->first_poly_node->poly_position; - DBUG_ASSERT(*insert_position); + uint32 insert_position, hole_position, position_shift; + poly_instance *cur_poly; + insert_position= m_result->outer_poly->first_poly_node->poly_position; + DBUG_ASSERT(insert_position); hole_position= storage->position(); storage->start_shape(Gcalc_function::shape_hole); if (get_polygon_result(m_result, storage) || - storage->move_hole(*insert_position, hole_position, - insert_position)) + storage->move_hole(insert_position, hole_position, + &position_shift)) return 1; + for (cur_poly= polygons; + cur_poly && *cur_poly->after_poly_position >= insert_position; + cur_poly= cur_poly->get_next()) + *cur_poly->after_poly_position+= position_shift; } else { uint32 *poly_position= &m_result->poly_position; + poly_instance *p= new_poly(); + p->after_poly_position= poly_position; + p->next= polygons; + polygons= p; storage->start_shape(Gcalc_function::shape_polygon); if (get_polygon_result(m_result, storage)) return 1; -- cgit v1.2.1 From 13f6e1119f831ecde5a8e82e8a68f2848b2b54a1 Mon Sep 17 00:00:00 2001 From: Alexey Botchkov Date: Thu, 7 Jul 2011 16:59:45 +0500 Subject: Fix for bug #804324 Assertion 0 in Gcalc_scan_iterator::pop_suitable_intersection There were actually two bugs. One was when the line that intersects itself the intersection point treated as it doesn't belong to the line. Second when edges partly coincide, wrong result produced when we try to find their intersection. per-file comments: mysql-test/r/gis-precise.result Fix for bug #804324 Assertion 0 in Gcalc_scan_iterator::pop_suitable_intersection test result updated. mysql-test/t/gis-precise.test Fix for bug #804324 Assertion 0 in Gcalc_scan_iterator::pop_suitable_intersection test case added. sql/gcalc_slicescan.cc Fix for bug #804324 Assertion 0 in Gcalc_scan_iterator::pop_suitable_intersection skip the intersection if it just line that intersects itself. sql/gcalc_tools.cc Fix for bug #804324 Assertion 0 in Gcalc_scan_iterator::pop_suitable_intersection if edges coincide, just pick the first coinciding poing as an intersection. --- sql/gcalc_tools.cc | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) (limited to 'sql/gcalc_tools.cc') diff --git a/sql/gcalc_tools.cc b/sql/gcalc_tools.cc index 11d452cd8cf..a360a4c100a 100644 --- a/sql/gcalc_tools.cc +++ b/sql/gcalc_tools.cc @@ -701,7 +701,8 @@ handle_lines_intersection(active_thread *t0, active_thread *t1, double x, double y) { m_fn->invert_state(p0->shape); - m_fn->invert_state(p1->shape); + if (p0->shape != p1->shape) + m_fn->invert_state(p1->shape); int intersection_state= m_fn->count(); if ((t0->result_range | t1->result_range) == intersection_state) return 0; -- cgit v1.2.1 From 67e937095cec8aa922ff3ea971204d59ee3047ff Mon Sep 17 00:00:00 2001 From: Alexey Botchkov Date: Fri, 8 Jul 2011 15:38:15 +0500 Subject: Fix for bug #804259 Second assertion in Gis_geometry_collection::init_from_opresult. A polygon has no right to have holes that are actually points. So just skip them when we collect the result of an operation. per-file comments: mysql-test/r/gis-precise.result Fix for bug #804259 Second assertion in Gis_geometry_collection::init_from_opresult. test result updated. mysql-test/t/gis-precise.test Fix for bug #804259 Second assertion in Gis_geometry_collection::init_from_opresult. test case added. sql/gcalc_tools.cc Fix for bug #804259 Second assertion in Gis_geometry_collection::init_from_opresult. Skip the point in the result if it's the hole inside a polygon. --- sql/gcalc_tools.cc | 5 +++++ 1 file changed, 5 insertions(+) (limited to 'sql/gcalc_tools.cc') diff --git a/sql/gcalc_tools.cc b/sql/gcalc_tools.cc index a360a4c100a..2a9090a04a1 100644 --- a/sql/gcalc_tools.cc +++ b/sql/gcalc_tools.cc @@ -319,6 +319,11 @@ int Gcalc_result_receiver::complete_shape() { if (cur_shape != Gcalc_function::shape_point) { + if (cur_shape == Gcalc_function::shape_hole) + { + buffer.length(shape_pos); + return 0; + } cur_shape= Gcalc_function::shape_point; buffer.length(buffer.length()-4); } -- cgit v1.2.1 From e7c9f52fd960440614c30c3f852bf74f1febe6b3 Mon Sep 17 00:00:00 2001 From: Alexey Botchkov Date: Tue, 12 Jul 2011 11:21:20 +0500 Subject: Fix for bug #801217 Assertion `t1->result_range' in Gcalc_operation_reducer::end_couple. We cannot cut a line from a polygon. So if the polygon fits the condition, and the intersection of a line and the polygon doesn't, we just skip the line. That rule wasn't applied if the line start was inside the polygon, which leaded to the assertion. per-file comments: mysql-test/r/gis-precise.result Fix for bug #801217 Assertion `t1->result_range' in Gcalc_operation_reducer::end_couple. test result updated. mysql-test/t/gis-precise.test Fix for bug #801217 Assertion `t1->result_range' in Gcalc_operation_reducer::end_couple. test case added. sql/gcalc_tools.cc Fix for bug #801217 Assertion `t1->result_range' in Gcalc_operation_reducer::end_couple. Don't mark the line as a border if it's inside a polygon that fits the result condition. --- sql/gcalc_tools.cc | 9 +++++++-- 1 file changed, 7 insertions(+), 2 deletions(-) (limited to 'sql/gcalc_tools.cc') diff --git a/sql/gcalc_tools.cc b/sql/gcalc_tools.cc index 2a9090a04a1..d89385fa78c 100644 --- a/sql/gcalc_tools.cc +++ b/sql/gcalc_tools.cc @@ -879,7 +879,7 @@ int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si) if (!new_t) return 1; m_fn->invert_state(pi.get_shape()); - new_t->result_range= prev_state ^ m_fn->count(); + new_t->result_range= ~prev_state & m_fn->count(); new_t->next= *at_hook; *at_hook= new_t; if (new_t->result_range && @@ -891,12 +891,17 @@ int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si) { active_thread *new_t0, *new_t1; int fn_result; + const Gcalc_heap::Info *p= pi.get_pi(); + bool line= m_fn->get_shape_kind(p->shape) == Gcalc_function::shape_line; if (!(new_t0= new_active_thread()) || !(new_t1= new_active_thread())) return 1; m_fn->invert_state(pi.get_shape()); fn_result= m_fn->count(); - new_t0->result_range= new_t1->result_range= prev_state ^ fn_result; + if (line) + new_t0->result_range= new_t1->result_range= ~prev_state & fn_result; + else + new_t0->result_range= new_t1->result_range= prev_state ^ fn_result; new_t1->next= *at_hook; new_t0->next= new_t1; *at_hook= new_t0; -- cgit v1.2.1 From 90c4df7a4af542707d884e53990827672bb8feea Mon Sep 17 00:00:00 2001 From: Alexey Botchkov Date: Wed, 13 Jul 2011 14:57:27 +0500 Subject: Fix for bug #804266 Memory corruption/valgrind warning/crash in move_hole() with ST_UNION. Second smaller hole in the polygon got link to the bigger one as it's the outer ring. Fixed by specifying the outer ring explicitly. per-file comments: mysql-test/r/gis-precise.result Fix for bug #804266 Memory corruption/valgrind warning/crash in move_hole() with ST_UNION. test result updated. mysql-test/t/gis-precise.test Fix for bug #804266 Memory corruption/valgrind warning/crash in move_hole() with ST_UNION. test case added. sql/gcalc_tools.cc Fix for bug #804266 Memory corruption/valgrind warning/crash in move_hole() with ST_UNION. specify the outer ring explicitly in the get_polygon_result parameter. sql/gcalc_tools.h Fix for bug #804266 Memory corruption/valgrind warning/crash in move_hole() with ST_UNION. add the outer ring as a parameter to the get_polygon_result. --- sql/gcalc_tools.cc | 16 +++++++++------- 1 file changed, 9 insertions(+), 7 deletions(-) (limited to 'sql/gcalc_tools.cc') diff --git a/sql/gcalc_tools.cc b/sql/gcalc_tools.cc index d89385fa78c..25e71d7bfca 100644 --- a/sql/gcalc_tools.cc +++ b/sql/gcalc_tools.cc @@ -1023,11 +1023,11 @@ inline int Gcalc_operation_reducer::get_single_result(res_point *res, int Gcalc_operation_reducer::get_result_thread(res_point *cur, Gcalc_result_receiver *storage, - int move_upward) + int move_upward, + res_point *first_poly_node) { res_point *next; bool glue_step= false; - res_point *first_poly_node= cur; double x, y; while (cur) { @@ -1068,12 +1068,13 @@ int Gcalc_operation_reducer::get_result_thread(res_point *cur, int Gcalc_operation_reducer::get_polygon_result(res_point *cur, - Gcalc_result_receiver *storage) + Gcalc_result_receiver *storage, + res_point *first_poly_node) { res_point *glue= cur->glue; glue->up->down= NULL; free_result(glue); - return get_result_thread(cur, storage, 1) || + return get_result_thread(cur, storage, 1, first_poly_node) || storage->complete_shape(); } @@ -1100,7 +1101,7 @@ int Gcalc_operation_reducer::get_line_result(res_point *cur, } } - return get_result_thread(cur, storage, move_upward) || + return get_result_thread(cur, storage, move_upward, 0) || storage->complete_shape(); } @@ -1129,7 +1130,8 @@ int Gcalc_operation_reducer::get_result(Gcalc_result_receiver *storage) DBUG_ASSERT(insert_position); hole_position= storage->position(); storage->start_shape(Gcalc_function::shape_hole); - if (get_polygon_result(m_result, storage) || + if (get_polygon_result(m_result, storage, + m_result->outer_poly->first_poly_node) || storage->move_hole(insert_position, hole_position, &position_shift)) return 1; @@ -1146,7 +1148,7 @@ int Gcalc_operation_reducer::get_result(Gcalc_result_receiver *storage) p->next= polygons; polygons= p; storage->start_shape(Gcalc_function::shape_polygon); - if (get_polygon_result(m_result, storage)) + if (get_polygon_result(m_result, storage, m_result)) return 1; *poly_position= storage->position(); } -- cgit v1.2.1 From 152f3c5e28fe2ae3fd950f15bb3de7064500ced5 Mon Sep 17 00:00:00 2001 From: Alexey Botchkov Date: Thu, 1 Sep 2011 11:44:56 +0500 Subject: PostGIS-style 'same point' handling. --- sql/gcalc_tools.cc | 915 +++++++++++++++++++++++++++++------------------------ 1 file changed, 495 insertions(+), 420 deletions(-) (limited to 'sql/gcalc_tools.cc') diff --git a/sql/gcalc_tools.cc b/sql/gcalc_tools.cc index 25e71d7bfca..ab173803323 100644 --- a/sql/gcalc_tools.cc +++ b/sql/gcalc_tools.cc @@ -106,13 +106,26 @@ int Gcalc_function::reserve_op_buffer(uint n_ops) int Gcalc_function::alloc_states() { - if (function_buffer.reserve((n_shapes+1) * sizeof(int))) + if (function_buffer.reserve((n_shapes+1) * 2 * sizeof(int))) return 1; i_states= (int *) (function_buffer.ptr() + ALIGN_SIZE(function_buffer.length())); + saved_i_states= i_states + (n_shapes + 1); return 0; } +void Gcalc_function::save_states() +{ + memcpy(saved_i_states, i_states, (n_shapes+1) * sizeof(int)); +} + + +void Gcalc_function::restore_states() +{ + memcpy(i_states, saved_i_states, (n_shapes+1) * sizeof(int)); +} + + int Gcalc_function::count_internal() { int c_op= uint4korr(cur_func); @@ -170,36 +183,64 @@ void Gcalc_function::reset() int Gcalc_function::find_function(Gcalc_scan_iterator &scan_it) { + const Gcalc_scan_iterator::point *eq_start, *cur_eq, *events; + while (scan_it.more_points()) { if (scan_it.step()) return -1; - Gcalc_scan_events ev= scan_it.get_event(); - const Gcalc_scan_iterator::point *evpos= scan_it.get_event_position(); - if (ev & (scev_point | scev_end | scev_two_ends)) + events= scan_it.get_events(); + + /* these kinds of events don't change the function */ + if (events->simple_event()) continue; + Gcalc_point_iterator pit(&scan_it); clear_state(); - for (Gcalc_point_iterator pit(&scan_it); pit.point() != evpos; ++pit) + /* Walk to the event, marking polygons we met */ + for (; pit.point() != scan_it.get_event_position(); ++pit) { gcalc_shape_info si= pit.point()->get_shape(); if ((get_shape_kind(si) == Gcalc_function::shape_polygon)) invert_state(si); } - invert_state(evpos->get_shape()); - - if (ev == scev_intersection) - { - const Gcalc_scan_iterator::point *evnext= evpos->c_get_next(); - if ((get_shape_kind(evpos->get_shape()) != - Gcalc_function::shape_polygon) || - (get_shape_kind(evnext->get_shape()) != - Gcalc_function::shape_polygon)) - invert_state(evnext->get_shape()); - } + save_states(); + /* Check the status of the event point */ + for (; events; events= events->get_next()) + set_on_state(events->get_shape()); if (count()) return 1; + + if (scan_it.get_event_position() == scan_it.get_event_end()) + continue; + + /* Check the status after the event */ + restore_states(); + eq_start= pit.point(); + do + { + ++pit; + if (pit.point() != scan_it.get_event_end() && + eq_start->cmp_dx_dy(pit.point()) == 0) + continue; + save_states(); + for (cur_eq= eq_start; cur_eq != pit.point(); + cur_eq= cur_eq->get_next()) + set_on_state(cur_eq->get_shape()); + if (count()) + return 1; + restore_states(); + for (cur_eq= eq_start; cur_eq != pit.point(); cur_eq= cur_eq->get_next()) + { + gcalc_shape_info si= cur_eq->get_shape(); + if ((get_shape_kind(si) == Gcalc_function::shape_polygon)) + invert_state(si); + } + if (count()) + return 1; + eq_start= pit.point(); + } while (pit.point() != scan_it.get_event_end()); } return 0; } @@ -457,6 +498,10 @@ void Gcalc_operation_reducer::init(Gcalc_function *fn, modes mode) m_fn= fn; m_mode= mode; m_first_active_thread= NULL; + m_lines= NULL; + m_lines_hook= (Gcalc_dyn_list::Item **) &m_lines; + m_poly_borders= NULL; + m_poly_borders_hook= (Gcalc_dyn_list::Item **) &m_poly_borders; } @@ -470,10 +515,10 @@ Gcalc_operation_reducer(Gcalc_function *fn, modes mode, size_t blk_size) : inline int Gcalc_operation_reducer::continue_range(active_thread *t, - const Gcalc_heap::Info *p) + const Gcalc_heap::Info *p, + int horiz_dir, double dx_dy) { - DBUG_ASSERT(t->result_range); - res_point *rp= add_res_point(); + res_point *rp= add_res_point(t->rp->type); if (!rp) return 1; rp->glue= NULL; @@ -482,16 +527,17 @@ inline int Gcalc_operation_reducer::continue_range(active_thread *t, rp->intersection_point= false; rp->pi= p; t->rp= rp; + t->horiz_dir= horiz_dir; + t->dx_dy= dx_dy; return 0; } inline int Gcalc_operation_reducer::continue_i_range(active_thread *t, - const Gcalc_heap::Info *p, - double x, double y) + double x, double y, + int horiz_dir, double dx_dy) { - DBUG_ASSERT(t->result_range); - res_point *rp= add_res_point(); + res_point *rp= add_res_point(t->rp->type); if (!rp) return 1; rp->glue= NULL; @@ -499,133 +545,10 @@ inline int Gcalc_operation_reducer::continue_i_range(active_thread *t, t->rp->up= rp; rp->intersection_point= true; rp->x= x; - rp->pi= p; - rp->y= y; - t->rp= rp; - return 0; -} - -inline int Gcalc_operation_reducer::start_range(active_thread *t, - const Gcalc_heap::Info *p) -{ - res_point *rp= add_res_point(); - if (!rp) - return 1; - rp->glue= rp->down= NULL; - rp->intersection_point= false; - rp->pi= p; - t->result_range= 1; - t->rp= rp; - return 0; -} - -inline int Gcalc_operation_reducer::start_i_range(active_thread *t, - const Gcalc_heap::Info *p, - double x, double y) -{ - res_point *rp= add_res_point(); - if (!rp) - return 1; - rp->glue= rp->down= NULL; - rp->intersection_point= true; - rp->x= x; rp->y= y; - rp->pi= p; - t->result_range= 1; t->rp= rp; - return 0; -} - -inline int Gcalc_operation_reducer::end_range(active_thread *t, - const Gcalc_heap::Info *p) -{ - res_point *rp= add_res_point(); - if (!rp) - return 1; - rp->glue= rp->up= NULL; - rp->down= t->rp; - rp->intersection_point= false; - rp->pi= p; - t->rp->up= rp; - t->result_range= 0; - return 0; -} - -inline int Gcalc_operation_reducer::end_i_range(active_thread *t, - const Gcalc_heap::Info *p, - double x, double y) -{ - res_point *rp= add_res_point(); - if (!rp) - return 1; - rp->glue= rp->up= NULL; - rp->down= t->rp; - rp->intersection_point= true; - rp->x= x; - rp->pi= p; - rp->y= y; - t->rp->up= rp; - t->result_range= 0; - return 0; -} - -int Gcalc_operation_reducer::start_couple(active_thread *t0, active_thread *t1, - const Gcalc_heap::Info *p, - const active_thread *prev_range) -{ - res_point *rp0, *rp1; - if (!(rp0= add_res_point()) || !(rp1= add_res_point())) - return 1; - rp0->glue= rp1; - rp1->glue= rp0; - rp0->intersection_point= rp1->intersection_point= false; - rp0->down= rp1->down= NULL; - rp0->pi= rp1->pi= p; - t0->rp= rp0; - t1->rp= rp1; - if (prev_range) - { - rp0->outer_poly= prev_range->thread_start; - t1->thread_start= prev_range->thread_start; - } - else - { - rp0->outer_poly= 0; - t0->thread_start= rp0; - } - return 0; -} - -int Gcalc_operation_reducer::start_i_couple(active_thread *t0, active_thread *t1, - const Gcalc_heap::Info *p0, - const Gcalc_heap::Info *p1, - double x, double y, - const active_thread *prev_range) -{ - res_point *rp0, *rp1; - if (!(rp0= add_res_point()) || !(rp1= add_res_point())) - return 1; - rp0->glue= rp1; - rp1->glue= rp0; - rp0->pi= p0; - rp1->pi= p1; - rp0->intersection_point= rp1->intersection_point= true; - rp0->down= rp1->down= NULL; - rp0->x= rp1->x= x; - rp0->y= rp1->y= y; - t0->result_range= t1->result_range= 1; - t0->rp= rp0; - t1->rp= rp1; - if (prev_range) - { - rp0->outer_poly= prev_range->thread_start; - t1->thread_start= prev_range->thread_start; - } - else - { - rp0->outer_poly= 0; - t0->thread_start= rp0; - } + t->horiz_dir= horiz_dir; + t->dx_dy= dx_dy; return 0; } @@ -633,8 +556,9 @@ int Gcalc_operation_reducer::end_couple(active_thread *t0, active_thread *t1, const Gcalc_heap::Info *p) { res_point *rp0, *rp1; - DBUG_ASSERT(t1->result_range); - if (!(rp0= add_res_point()) || !(rp1= add_res_point())) + DBUG_ASSERT(t0->rp->type == t1->rp->type); + if (!(rp0= add_res_point(t0->rp->type)) || + !(rp1= add_res_point(t0->rp->type))) return 1; rp0->down= t0->rp; rp1->down= t1->rp; @@ -645,341 +569,492 @@ int Gcalc_operation_reducer::end_couple(active_thread *t0, active_thread *t1, t1->rp->up= rp1; rp0->intersection_point= rp1->intersection_point= false; rp0->pi= rp1->pi= p; - t0->result_range= t1->result_range= 0; return 0; } -int Gcalc_operation_reducer::end_i_couple(active_thread *t0, active_thread *t1, - const Gcalc_heap::Info *p0, - const Gcalc_heap::Info *p1, - double x, double y) -{ - res_point *rp0, *rp1; - if (!(rp0= add_res_point()) || !(rp1= add_res_point())) - return 1; - rp0->down= t0->rp; - rp1->down= t1->rp; - rp0->pi= p0; - rp1->pi= p1; - rp1->glue= rp0; - rp0->glue= rp1; - rp0->up= rp1->up= NULL; - rp0->intersection_point= rp1->intersection_point= true; - rp0->x= rp1->x= x; - rp0->y= rp1->y= y; - t0->result_range= t1->result_range= 0; - t0->rp->up= rp0; - t1->rp->up= rp1; - return 0; -} -int Gcalc_operation_reducer::add_single_point(const Gcalc_heap::Info *p) +int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si) { - res_point *rp= add_res_point(); - if (!rp) - return 1; - rp->glue= rp->up= rp->down= NULL; - rp->intersection_point= false; - rp->pi= p; - rp->x= p->x; - rp->y= p->y; - return 0; -} + Gcalc_point_iterator pi(si); + const Gcalc_heap::Info *event_point= NULL; + int prev_state= 0; + int sav_prev_state; + active_thread *prev_range= NULL; + const Gcalc_scan_iterator::point *events; + const Gcalc_scan_iterator::point *eq_start; + active_thread **cur_t_hook= &m_first_active_thread; + active_thread **starting_t_hook; + active_thread *bottom_threads= NULL; + active_thread *eq_thread, *point_thread;; -int Gcalc_operation_reducer::add_i_single_point(const Gcalc_heap::Info *p, - double x, double y) -{ - res_point *rp= add_res_point(); - if (!rp) - return 1; - rp->glue= rp->up= rp->down= NULL; - rp->intersection_point= true; - rp->x= x; - rp->pi= p; - rp->y= y; - return 0; -} + m_fn->clear_state(); + /* Walk to the event, remembering what is needed. */ + for (; pi.point() != si->get_event_position(); + ++pi, cur_t_hook= (active_thread **) &(*cur_t_hook)->next) + { + active_thread *cur_t= *cur_t_hook; + if (cur_t->enabled() && + cur_t->rp->type == Gcalc_function::shape_polygon) + { + prev_state^= 1; + prev_range= prev_state ? cur_t : 0; + } + if (m_fn->get_shape_kind(pi.get_shape()) == Gcalc_function::shape_polygon) + m_fn->invert_state(pi.get_shape()); + } -int Gcalc_operation_reducer:: -handle_lines_intersection(active_thread *t0, active_thread *t1, - const Gcalc_heap::Info *p0, const Gcalc_heap::Info *p1, - double x, double y) -{ - m_fn->invert_state(p0->shape); - if (p0->shape != p1->shape) - m_fn->invert_state(p1->shape); - int intersection_state= m_fn->count(); - if ((t0->result_range | t1->result_range) == intersection_state) + events= si->get_events(); + if (events->simple_event()) + { + active_thread *cur_t= *cur_t_hook; + switch (events->event) + { + case scev_point: + { + if (cur_t->enabled() && + continue_range(cur_t, events->pi, events->horiz_dir, events->dx_dy)) + return 1; + break; + } + case scev_end: + { + if (cur_t->enabled() && end_line(cur_t, events->pi, si)) + return 1; + *cur_t_hook= cur_t->get_next(); + free_item(cur_t); + break; + } + case scev_two_ends: + { + if (cur_t->enabled() && + end_couple(cur_t, cur_t->get_next(), events->pi)) + return 1; + *cur_t_hook= cur_t->get_next()->get_next(); + free_item(cur_t->next); + free_item(cur_t); + break; + } + default: + DBUG_ASSERT(0); + } return 0; + } - if (t0->result_range && - (end_i_range(t0, p1, x, y) || start_i_range(t0, p1, x, y))) - return 1; + starting_t_hook= cur_t_hook; + sav_prev_state= prev_state; - if (t1->result_range && - (end_i_range(t1, p0, x, y) || start_i_range(t1, p0, x, y))) - return 1; + /* Walk through the event, collecting all the 'incoming' threads */ + for (; events; events= events->get_next()) + { + active_thread *cur_t= *cur_t_hook; - if (intersection_state && - add_i_single_point(p0, x, y)) - return 1; - - return 0; -} + if (!event_point && events->event != scev_intersection) + event_point= events->pi; + if (events->event == scev_single_point) + continue; -inline int Gcalc_operation_reducer:: -handle_line_polygon_intersection(active_thread *l, const Gcalc_heap::Info *pl, - int line_state, int poly_state, - double x, double y) -{ - int range_after= ~poly_state & line_state; - if (l->result_range == range_after) - return 0; - return range_after ? start_i_range(l, pl, x, y) : end_i_range(l, pl, x, y); -} + if (events->event == scev_thread || + events->event == scev_two_threads) + { + active_thread *new_t= new_active_thread(); + if (!new_t) + return 1; + new_t->rp= NULL; + /* Insert into the main thread list before the current */ + new_t->next= cur_t; + *cur_t_hook= new_t; + cur_t_hook= (active_thread **) &new_t->next; + } + else + { + if (events->is_bottom()) + { + /* Move thread from the main list to the bottom_threads. */ + *cur_t_hook= cur_t->get_next(); + cur_t->next= bottom_threads; + bottom_threads= cur_t; + } + if (cur_t->enabled()) + { + if (cur_t->rp->type == Gcalc_function::shape_line) + { + DBUG_ASSERT(!prev_state); + add_line(1, cur_t, events); + } + else + { + add_poly_border(1, cur_t, prev_state, events); + prev_state^= 1; + } + if (!events->is_bottom()) + { + active_thread *new_t= new_active_thread(); + if (!new_t) + return 1; + new_t->rp= NULL; + /* Replace the current thread with the new. */ + new_t->next= cur_t->next; + *cur_t_hook= new_t; + cur_t_hook= (active_thread **) &new_t->next; + /* And move old to the bottom list */ + cur_t->next= bottom_threads; + bottom_threads= cur_t; + } + } + else if (!events->is_bottom()) + cur_t_hook= (active_thread **) &cur_t->next; + } + } + prev_state= sav_prev_state; + cur_t_hook= starting_t_hook; -static inline void switch_athreads(Gcalc_operation_reducer::active_thread *t0, - Gcalc_operation_reducer::active_thread *t1, - Gcalc_dyn_list::Item **hook) -{ - *hook= t1; - t0->next= t1->next; - t1->next= t0; -} + eq_start= pi.point(); + eq_thread= point_thread= *starting_t_hook; + while (eq_start != si->get_event_end()) + { + const Gcalc_scan_iterator::point *cur_eq; + int in_state, after_state; -inline int Gcalc_operation_reducer:: -handle_polygons_intersection(active_thread *t0, active_thread *t1, - Gcalc_dyn_list::Item **t_hook, - const Gcalc_heap::Info *p0, - const Gcalc_heap::Info *p1, - int prev_state, double x, double y, - const active_thread *prev_range) -{ - m_fn->invert_state(p0->shape); - int state_11= m_fn->count(); - m_fn->invert_state(p1->shape); - int state_2= m_fn->count(); - int state_01= prev_state ^ t0->result_range; - if ((prev_state == state_01) && (prev_state == state_2)) + ++pi; + point_thread= point_thread->get_next(); + + if (pi.point() != si->get_event_end() && + eq_start->cmp_dx_dy(pi.point()) == 0) + continue; + + m_fn->save_states(); + for (cur_eq= eq_start; cur_eq != pi.point(); cur_eq= cur_eq->get_next()) + m_fn->set_on_state(cur_eq->get_shape()); + in_state= m_fn->count(); + + m_fn->restore_states(); + for (cur_eq= eq_start; cur_eq != pi.point(); cur_eq= cur_eq->get_next()) + { + gcalc_shape_info si= cur_eq->get_shape(); + if ((m_fn->get_shape_kind(si) == Gcalc_function::shape_polygon)) + m_fn->invert_state(si); + } + after_state= m_fn->count(); + if (prev_state != after_state) + { + if (add_poly_border(0, eq_thread, prev_state, eq_start)) + return 1; + } + else if (!prev_state /* &&!after_state */ && in_state) + { + if (add_line(0, eq_thread, eq_start)) + return 1; + } + + prev_state= after_state; + eq_start= pi.point(); + eq_thread= point_thread; + } + + if (!sav_prev_state && !m_poly_borders && !m_lines) { - if (state_11 == prev_state) + /* Check if we need to add the event point itself */ + m_fn->clear_state(); + for (pi.restart(si); pi.point() != si->get_event_position(); ++pi) { - switch_athreads(t0, t1, t_hook); - return 0; + if (m_fn->get_shape_kind(pi.get_shape()) == Gcalc_function::shape_polygon) + m_fn->invert_state(pi.get_shape()); } - return start_i_couple(t0, t1, p0, p1, x, y, prev_range); + for (events= si->get_events(); events; events= events->get_next()) + m_fn->set_on_state(events->get_shape()); + + return m_fn->count() ? add_single_point(event_point, si) : 0; } - if (prev_state == state_2) + + if (m_poly_borders) { - if (state_01 == state_11) + *m_poly_borders_hook= NULL; + while (m_poly_borders) { - if (m_mode & polygon_selfintersections_allowed) - { - switch_athreads(t0, t1, t_hook); - return 0; - } - if (prev_state != (m_mode & prefer_big_with_holes)) - return continue_i_range(t0, p0, x, y) || continue_i_range(t1, p1, x, y); - return end_i_couple(t0, t1, p0, p1, x, y) || - start_i_couple(t0, t1, p0, p1, x, y, prev_range); + poly_border *pb1, *pb2; + pb1= m_poly_borders; + DBUG_ASSERT(m_poly_borders->next); + + pb2= get_pair_border(pb1); + /* Remove pb1 from the list. The pb2 already removed in get_pair_border. */ + m_poly_borders= pb1->get_next(); + if (connect_threads(pb1->incoming, pb2->incoming, + pb1->t, pb2->t, pb1->p, pb2->p, + prev_range, event_point, si, + Gcalc_function::shape_polygon)) + return 1; + + free_item(pb1); + free_item(pb2); } - else - return end_i_couple(t0, t1, p0, p1, x, y); + m_poly_borders_hook= (Gcalc_dyn_list::Item **) &m_poly_borders; + m_poly_borders= NULL; } - if (state_01 ^ state_11) + + if (m_lines) { - switch_athreads(t0, t1, t_hook); - return 0; + *m_lines_hook= NULL; + if (m_lines->get_next() && + !m_lines->get_next()->get_next()) + { + if (connect_threads(m_lines->incoming, m_lines->get_next()->incoming, + m_lines->t, m_lines->get_next()->t, + m_lines->p, m_lines->get_next()->p, NULL, + event_point, si, Gcalc_function::shape_line)) + return 1; + } + else + { + for (line *cur_line= m_lines; cur_line; cur_line= cur_line->get_next()) + { + if (cur_line->incoming) + { + if (end_line(cur_line->t, event_point, si)) + return 1; + } + else + start_line(cur_line->t, cur_line->p, event_point, si); + } + } + free_list(m_lines); + m_lines= NULL; + m_lines_hook= (Gcalc_dyn_list::Item **) &m_lines; } - active_thread *thread_to_continue; - const Gcalc_heap::Info *way_to_go; - if (prev_state == state_01) + if (bottom_threads) + free_list(bottom_threads); + + return 0; +} + + +int Gcalc_operation_reducer::add_single_point(const Gcalc_heap::Info *p, + const Gcalc_scan_iterator *si) +{ + res_point *rp= add_res_point(Gcalc_function::shape_point); + if (!rp) + return 1; + rp->glue= rp->up= rp->down= NULL; + if (p) { - thread_to_continue= t1; - way_to_go= p1; + rp->intersection_point= false; + rp->pi= p; } - else + else { - thread_to_continue= t0; - way_to_go= p0; + rp->intersection_point= true; + rp->x= si->get_y(); + rp->y= si->get_events()->x; } - return continue_i_range(thread_to_continue, way_to_go, x, y); + return 0; } -int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si) -{ - Gcalc_point_iterator pi(si); - active_thread *cur_t= m_first_active_thread; - Gcalc_dyn_list::Item **at_hook= (Gcalc_dyn_list::Item **)&m_first_active_thread; - const active_thread *prev_range; - int prev_state; - if (si->get_event() & (scev_point | scev_end | scev_two_ends)) +Gcalc_operation_reducer::poly_border + *Gcalc_operation_reducer::get_pair_border(poly_border *b1) +{ + poly_border *prev_b= b1; + poly_border *result= b1->get_next(); + if (b1->prev_state) { - for (; pi.point() != si->get_event_position(); ++pi, cur_t= cur_t->get_next()) - at_hook= &cur_t->next; - - switch (si->get_event()) + if (b1->incoming) { - case scev_point: + /* Find the first outgoing, otherwise the last one. */ + while (result->incoming && result->get_next()) { - if (cur_t->result_range && - continue_range(cur_t, pi.get_pi())) - return 1; - break; + prev_b= result; + result= result->get_next(); } - case scev_end: + } + else + { + /* Get the last one */ + while (result->get_next()) { - if (cur_t->result_range && - end_range(cur_t, pi.get_pi())) - return 1; - *at_hook= cur_t->next; - free_item(cur_t); - break; + prev_b= result; + result= result->get_next(); } - case scev_two_ends: + } + } + else /* !b1->prev_state */ + { + if (b1->incoming) + { + /* Get the next incoming, otherwise the last one. */ + while (!result->incoming && result->get_next()) { - active_thread *cur_t1= cur_t->get_next(); - if (cur_t->result_range && - end_couple(cur_t, cur_t1, pi.get_pi())) - return 1; - - *at_hook= cur_t1->next; - free_list(cur_t, &cur_t1->next); - break; + prev_b= result; + result= result->get_next(); } - default: - DBUG_ASSERT(0); } - return 0; + else + { + /* Just pick the next one */ + } } + /* Delete the result from the list. */ + prev_b->next= result->next; + return result; +} - prev_state= 0; - prev_range= 0; - m_fn->clear_state(); - for (; pi.point() != si->get_event_position(); ++pi, cur_t= cur_t->get_next()) +int Gcalc_operation_reducer::connect_threads( + int incoming_a, int incoming_b, + active_thread *ta, active_thread *tb, + const Gcalc_scan_iterator::point *pa, const Gcalc_scan_iterator::point *pb, + active_thread *prev_range, const Gcalc_heap::Info *ev_p, + const Gcalc_scan_iterator *si, Gcalc_function::shape_type s_t) +{ + if (incoming_a && incoming_b) { - if (m_fn->get_shape_kind(pi.get_shape()) == Gcalc_function::shape_polygon) + res_point *rpa, *rpb; + DBUG_ASSERT(ta->rp->type == tb->rp->type); + if (!(rpa= add_res_point(ta->rp->type)) || + !(rpb= add_res_point(ta->rp->type))) + return 1; + rpa->down= ta->rp; + rpb->down= tb->rp; + rpb->glue= rpa; + rpa->glue= rpb; + rpa->up= rpb->up= NULL; + ta->rp->up= rpa; + tb->rp->up= rpb; + if (ev_p) { - m_fn->invert_state(pi.get_shape()); - prev_state^= cur_t->result_range; + rpa->intersection_point= rpb->intersection_point= false; + rpa->pi= rpb->pi= ev_p; + } + else + { + rpa->intersection_point= rpb->intersection_point= true; + rpa->x= rpb->x= si->get_events()->x; + rpa->y= rpb->y= si->get_y(); } - at_hook= &cur_t->next; - if (cur_t->result_range) - prev_range= prev_state ? cur_t : 0; - } - switch (si->get_event()) - { - case scev_thread: - { - active_thread *new_t= new_active_thread(); - if (!new_t) - return 1; - m_fn->invert_state(pi.get_shape()); - new_t->result_range= ~prev_state & m_fn->count(); - new_t->next= *at_hook; - *at_hook= new_t; - if (new_t->result_range && - start_range(new_t, pi.get_pi())) - return 1; - break; + ta->rp= tb->rp= NULL; + return 0; } - case scev_two_threads: + if (!incoming_a) { - active_thread *new_t0, *new_t1; - int fn_result; - const Gcalc_heap::Info *p= pi.get_pi(); - bool line= m_fn->get_shape_kind(p->shape) == Gcalc_function::shape_line; - if (!(new_t0= new_active_thread()) || !(new_t1= new_active_thread())) + DBUG_ASSERT(!incoming_b); + + res_point *rp0, *rp1; + if (!(rp0= add_res_point(s_t)) || !(rp1= add_res_point(s_t))) return 1; - - m_fn->invert_state(pi.get_shape()); - fn_result= m_fn->count(); - if (line) - new_t0->result_range= new_t1->result_range= ~prev_state & fn_result; + rp0->glue= rp1; + rp1->glue= rp0; + if (ev_p) + { + rp0->intersection_point= rp1->intersection_point= false; + rp0->pi= rp1->pi= ev_p; + } else - new_t0->result_range= new_t1->result_range= prev_state ^ fn_result; - new_t1->next= *at_hook; - new_t0->next= new_t1; - *at_hook= new_t0; - if (new_t0->result_range && - start_couple(new_t0, new_t1, pi.get_pi(), prev_range)) - return 1; - break; - } - case scev_intersection: - { - active_thread *cur_t1= cur_t->get_next(); - const Gcalc_heap::Info *p0, *p1; - p0= pi.get_pi(); - ++pi; - p1= pi.get_pi(); - bool line0= m_fn->get_shape_kind(p0->shape) == Gcalc_function::shape_line; - bool line1= m_fn->get_shape_kind(p1->shape) == Gcalc_function::shape_line; - - if (!line0 && !line1) /* two polygons*/ { - if (handle_polygons_intersection(cur_t, cur_t1, at_hook, p0, p1, - prev_state, pi.get_x(), si->get_y(), - prev_range)) - return 1; + rp0->intersection_point= rp1->intersection_point= true; + rp0->x= rp1->x= si->get_events()->x; + rp0->y= rp1->y= si->get_y(); } - else if (line0 && line1) + rp0->down= rp1->down= NULL; + ta->rp= rp0; + tb->rp= rp1; + ta->horiz_dir= pa->horiz_dir; + ta->dx_dy= pa->dx_dy; + + tb->horiz_dir= pb->horiz_dir; + tb->dx_dy= pb->dx_dy; + + if (prev_range) { - if (!prev_state && - handle_lines_intersection(cur_t, cur_t1, - p0, p1, pi.get_x(), si->get_y())) - return 1; - switch_athreads(cur_t, cur_t1, at_hook); + rp0->outer_poly= prev_range->thread_start; + tb->thread_start= prev_range->thread_start; } else { - int poly_state; - int line_state; - const Gcalc_heap::Info *line; - active_thread *line_t; - m_fn->invert_state(p0->shape); - if (line0) - { - line_state= m_fn->count(); - poly_state= prev_state; - line= p0; - line_t= cur_t1; - } - else - { - poly_state= m_fn->count(); - m_fn->invert_state(p1->shape); - line_state= m_fn->count(); - line= p1; - line_t= cur_t; - } - if (handle_line_polygon_intersection(line_t, line, - line_state, poly_state, - pi.get_x(), si->get_y())) - return 1; - switch_athreads(cur_t, cur_t1, at_hook); + rp0->outer_poly= 0; + ta->thread_start= rp0; } - break; + return 0; } - case scev_single_point: + /* else, if only ta is incoming */ + + DBUG_ASSERT(tb != ta); + tb->rp= ta->rp; + tb->thread_start= ta->thread_start; + if (Gcalc_scan_iterator::point:: + compare_dx_dy(ta->horiz_dir, ta->dx_dy, + pb->horiz_dir, pb->dx_dy) != 0) { - m_fn->invert_state(pi.get_shape()); - if ((prev_state ^ m_fn->count()) && - add_single_point(pi.get_pi())) + if (ev_p ? continue_range(tb, ev_p, pb->horiz_dir, pb->dx_dy): + continue_i_range(tb, + si->get_events()->x, si->get_y(), + pb->horiz_dir, pb->dx_dy)) return 1; - break; } - default: - DBUG_ASSERT(0); + else + { + tb->horiz_dir= pb->horiz_dir; + tb->dx_dy= pb->dx_dy; + } + + return 0; +} + + +int Gcalc_operation_reducer::start_line(active_thread *t, + const Gcalc_scan_iterator::point *p, + const Gcalc_heap::Info *ev_p, + const Gcalc_scan_iterator *si) +{ + res_point *rp= add_res_point(Gcalc_function::shape_line); + if (!rp) + return 1; + rp->glue= rp->down= NULL; + if (ev_p) + { + rp->intersection_point= false; + rp->pi= ev_p; + } + else + { + rp->intersection_point= true; + rp->x= si->get_events()->x; + rp->y= si->get_y(); + } + t->rp= rp; + t->horiz_dir= p->horiz_dir; + t->dx_dy= p->dx_dy; + return 0; +} + + +int Gcalc_operation_reducer::end_line(active_thread *t, + const Gcalc_heap::Info *ev_p, + const Gcalc_scan_iterator *si) +{ + DBUG_ASSERT(t->rp->type == Gcalc_function::shape_line); + res_point *rp= add_res_point(Gcalc_function::shape_line); + if (!rp) + return 1; + rp->glue= rp->up= NULL; + rp->down= t->rp; + if (ev_p) + { + rp->intersection_point= false; + rp->pi= ev_p; + } + else + { + rp->intersection_point= true; + rp->x= si->get_events()->x; + rp->y= si->get_y(); } + t->rp->up= rp; + t->rp= NULL; return 0; } + int Gcalc_operation_reducer::count_all(Gcalc_heap *hp) { Gcalc_scan_iterator si; @@ -1014,7 +1089,7 @@ inline int Gcalc_operation_reducer::get_single_result(res_point *res, return 1; } else - if (storage->single_point(res->x, res->y)) + if (storage->single_point(res->pi->x, res->pi->y)) return 1; free_result(res); return 0; @@ -1113,13 +1188,13 @@ int Gcalc_operation_reducer::get_result(Gcalc_result_receiver *storage) *m_res_hook= NULL; while (m_result) { - if (!m_result->up) + Gcalc_function::shape_type shape= m_result->type; + if (shape == Gcalc_function::shape_point) { if (get_single_result(m_result, storage)) return 1; continue; } - Gcalc_function::shape_type shape= m_fn->get_shape_kind(m_result->pi->shape); if (shape == Gcalc_function::shape_polygon) { if (m_result->outer_poly) -- cgit v1.2.1 From eefff87652cde1cb0c986fd167ed057e87230250 Mon Sep 17 00:00:00 2001 From: Alexey Botchkov Date: Sun, 4 Sep 2011 19:11:04 +0500 Subject: bug 801466 ST_INTERSECTION() returns invalid value on empty intersection in maria-5.3-gis. We didn't implement an empty geometry. And returning NULL instead of it is not quite correct. So here is the implementation of the empty value as GEOMETRYCOLLECTION(). per-file comments: mysql-test/r/gis-precise.result bug 801466 ST_INTERSECTION() returns invalid value on empty intersection in maria-5.3-gis. test result updated. mysql-test/r/gis.result bug 801466 ST_INTERSECTION() returns invalid value on empty intersection in maria-5.3-gis. test result updated. mysql-test/t/gis-precise.test bug 801466 ST_INTERSECTION() returns invalid value on empty intersection in maria-5.3-gis. test case added. mysql-test/t/gis.test bug 801466 ST_INTERSECTION() returns invalid value on empty intersection in maria-5.3-gis. test case added. sql/field.cc bug 801466 ST_INTERSECTION() returns invalid value on empty intersection in maria-5.3-gis. store GEOMETRYCOLLECTION() properly. sql/gcalc_tools.cc bug 801466 ST_INTERSECTION() returns invalid value on empty intersection in maria-5.3-gis. create the GEOMETRYCOLLECTION() for the empty result. sql/gstream.h bug 801466 ST_INTERSECTION() returns invalid value on empty intersection in maria-5.3-gis. next_symbol() added. sql/spatial.cc bug 801466 ST_INTERSECTION() returns invalid value on empty intersection in maria-5.3-gis. code modified to handle 0 geometries in the GEOMETRYCOLLECTION properly. --- sql/gcalc_tools.cc | 9 +++++---- 1 file changed, 5 insertions(+), 4 deletions(-) (limited to 'sql/gcalc_tools.cc') diff --git a/sql/gcalc_tools.cc b/sql/gcalc_tools.cc index ab173803323..0d5c1c52d61 100644 --- a/sql/gcalc_tools.cc +++ b/sql/gcalc_tools.cc @@ -137,6 +137,8 @@ int Gcalc_function::count_internal() cur_func+= 4; if (next_func == op_shape) return i_states[c_op & ~(op_any | op_not)] ^ mask; + if (n_ops == 0) + return mask; result= count_internal(); @@ -442,11 +444,9 @@ void Gcalc_result_receiver::reset() int Gcalc_result_receiver::get_result_typeid() { - if (!n_shapes) - return 0; - - if (collection_result) + if (!n_shapes || collection_result) return Geometry::wkb_geometrycollection; + switch (common_shapetype) { case Gcalc_function::shape_polygon: @@ -1186,6 +1186,7 @@ int Gcalc_operation_reducer::get_result(Gcalc_result_receiver *storage) poly_instance *polygons= NULL; *m_res_hook= NULL; + while (m_result) { Gcalc_function::shape_type shape= m_result->type; -- cgit v1.2.1 From 6dfa30e938babc2cac59f2d5eac1f4d46a361b93 Mon Sep 17 00:00:00 2001 From: Alexey Botchkov Date: Sun, 4 Sep 2011 23:48:17 +0500 Subject: bug 839341 100% CPU usage with ST_UNION in maria-5.3-gis. Line loops weren't recognized when collect results. Fixed by checking if we got the same beginning point of the line. per-file comments: mysql-test/r/gis-precise.result bug 839341 100% CPU usage with ST_UNION in maria-5.3-gis. test result updated. mysql-test/t/gis-precise.test bug 839341 100% CPU usage with ST_UNION in maria-5.3-gis. test case added. sql/gcalc_tools.cc bug 839341 100% CPU usage with ST_UNION in maria-5.3-gis. check if we get the beginning node of the linestring, then cut the loop. --- sql/gcalc_tools.cc | 9 +++++++++ 1 file changed, 9 insertions(+) (limited to 'sql/gcalc_tools.cc') diff --git a/sql/gcalc_tools.cc b/sql/gcalc_tools.cc index 0d5c1c52d61..e502d54a160 100644 --- a/sql/gcalc_tools.cc +++ b/sql/gcalc_tools.cc @@ -1158,6 +1158,7 @@ int Gcalc_operation_reducer::get_line_result(res_point *cur, Gcalc_result_receiver *storage) { res_point *next; + res_point *cur_orig= cur; int move_upward= 1; if (cur->glue) { @@ -1171,6 +1172,14 @@ int Gcalc_operation_reducer::get_line_result(res_point *cur, if (!next) { next= cur->glue; + if (next == cur_orig) + { + /* It's the line loop */ + cur= cur_orig; + cur->glue->glue= NULL; + move_upward= 1; + break; + } move_upward^= 1; } } -- cgit v1.2.1 From a1315808b4a067fd82877ea1cfbd8867f9a8588a Mon Sep 17 00:00:00 2001 From: Alexey Botchkov Date: Mon, 5 Sep 2011 09:49:46 +0500 Subject: bug 839327 Crash in Gcalc_operation_reducer::end_couple with ST_UNION and MULTIPOLYGONs in 5.3-gis. When edges of a polygon coicide, it can form an pike, that is turned into a line after an operation. In this case a former polygon point can be an end of a single line, and that case wasn't properly handled. per-file comments: mysql-test/r/gis-precise.result bug 839327 Crash in Gcalc_operation_reducer::end_couple with ST_UNION and MULTIPOLYGONs in 5.3-gis. test result updated. mysql-test/t/gis-precise.test bug 839327 Crash in Gcalc_operation_reducer::end_couple with ST_UNION and MULTIPOLYGONs in 5.3-gis. test case added. sql/gcalc_tools.cc bug 839327 Crash in Gcalc_operation_reducer::end_couple with ST_UNION and MULTIPOLYGONs in 5.3-gis. in the scev_two_ends case check if we have single line ending on a polygon node. --- sql/gcalc_tools.cc | 16 +++++++++++++--- 1 file changed, 13 insertions(+), 3 deletions(-) (limited to 'sql/gcalc_tools.cc') diff --git a/sql/gcalc_tools.cc b/sql/gcalc_tools.cc index e502d54a160..3ee58646ca4 100644 --- a/sql/gcalc_tools.cc +++ b/sql/gcalc_tools.cc @@ -626,9 +626,19 @@ int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si) } case scev_two_ends: { - if (cur_t->enabled() && - end_couple(cur_t, cur_t->get_next(), events->pi)) - return 1; + if (cur_t->enabled() && cur_t->get_next()->enabled()) + { + /* When two threads are ended here */ + if (end_couple(cur_t, cur_t->get_next(), events->pi)) + return 1; + } + else if (cur_t->enabled() || cur_t->get_next()->enabled()) + { + /* Rare case when edges of a polygon coincide */ + if (end_line(cur_t->enabled() ? cur_t : cur_t->get_next(), + events->pi, si)) + return 1; + } *cur_t_hook= cur_t->get_next()->get_next(); free_item(cur_t->next); free_item(cur_t); -- cgit v1.2.1 From 5a04ac7bf0ee359fb36f4ebc00f0aebc142d36b7 Mon Sep 17 00:00:00 2001 From: Alexey Botchkov Date: Tue, 13 Sep 2011 18:26:16 +0500 Subject: Fix for bug 848939 Wrong result with ST_INTERSECTION between linestrings and a polygon in 5.3-gis Coordinates were mistakenly reversed for MULTIPOINT. per-file comments: mysql-test/r/gis-precise.result Fix for bug 848939 Wrong result with ST_INTERSECTION between linestrings and a polygon in 5.3-gis test result updated. mysql-test/t/gis-precise.test Fix for bug 848939 Wrong result with ST_INTERSECTION between linestrings and a polygon in 5.3-gis test case added. sql/gcalc_tools.cc Fix for bug 848939 Wrong result with ST_INTERSECTION between linestrings and a polygon in 5.3-gis coordinates set in the proper order. --- sql/gcalc_tools.cc | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'sql/gcalc_tools.cc') diff --git a/sql/gcalc_tools.cc b/sql/gcalc_tools.cc index 3ee58646ca4..baff6278444 100644 --- a/sql/gcalc_tools.cc +++ b/sql/gcalc_tools.cc @@ -853,8 +853,8 @@ int Gcalc_operation_reducer::add_single_point(const Gcalc_heap::Info *p, else { rp->intersection_point= true; - rp->x= si->get_y(); - rp->y= si->get_events()->x; + rp->y= si->get_y(); + rp->x= si->get_events()->x; } return 0; } -- cgit v1.2.1 From 0249413a6ae4a5900b51f434b361b9efa6133ad1 Mon Sep 17 00:00:00 2001 From: Alexey Botchkov Date: Wed, 21 Sep 2011 00:04:41 +0500 Subject: several bugs fixed here. 849789 Second assertion `m_poly_borders->next' failed in Gcalc_operation_reducer::count_slice in maria-5.3-gis 849791 Fourth assertion `n > 0 && n < SINUSES_CALCULATED*2+1' in get_n_sincos 849789 Second assertion `m_poly_borders->next' failed in Gcalc_operation_reducer::count_slice in maria-5.3-gis 848901 Assertion `fabs(cur_isc->x-m_cur_intersection->x) + fabs(cur_isc->y-m_cur_intersection->y) < 0.000000000001' failed in Gcalc_scan_iterator::intersection_scan() in maria-5.3-gis per-file comments: mysql-test/r/gis-precise.result test result updated. mysql-test/r/gis.result test result updated. sql/gcalc_slicescan.cc bugfixes. sql/gcalc_slicescan.h bugfixes. sql/gcalc_tools.cc bugfixes. sql/gcalc_tools.h bugfixes. sql/item_geofunc.cc bugfixes. sql/spatial.cc bugfixes. --- sql/gcalc_tools.cc | 293 ++++++++++++++++++++++++++++++++++------------------- 1 file changed, 189 insertions(+), 104 deletions(-) (limited to 'sql/gcalc_tools.cc') diff --git a/sql/gcalc_tools.cc b/sql/gcalc_tools.cc index baff6278444..90c39f08d0b 100644 --- a/sql/gcalc_tools.cc +++ b/sql/gcalc_tools.cc @@ -347,6 +347,10 @@ int Gcalc_result_receiver::add_point(double x, double y) buffer.q_append(prev_y); prev_x= x; prev_y= y; +#ifndef NO_TESTING + if (n_points == 53) + printf("xxx\n"); +#endif /*NO_TESTING*/ return 0; } @@ -488,6 +492,9 @@ int Gcalc_result_receiver::move_hole(uint32 dest_position, uint32 source_positio Gcalc_operation_reducer::Gcalc_operation_reducer(size_t blk_size) : Gcalc_dyn_list(blk_size, sizeof(res_point)), +#ifndef DBUG_OFF + n_res_points(0), +#endif /*DBUG_OFF*/ m_res_hook((Gcalc_dyn_list::Item **)&m_result), m_first_active_thread(NULL) {} @@ -514,9 +521,73 @@ Gcalc_operation_reducer(Gcalc_function *fn, modes mode, size_t blk_size) : } -inline int Gcalc_operation_reducer::continue_range(active_thread *t, - const Gcalc_heap::Info *p, - int horiz_dir, double dx_dy) +void Gcalc_operation_reducer::res_point::set(const Gcalc_scan_iterator *si) +{ + if ((intersection_point= si->intersection_step())) + ii= si->get_cur_ii(); + else + pi= si->get_cur_pi(); +} + +#ifndef NO_TESTING +void call_checkpoint(int d) +{ + printf("%d\n", d); +} +#endif /*NO_TESTING*/ + +Gcalc_operation_reducer::res_point * + Gcalc_operation_reducer::add_res_point(Gcalc_function::shape_type type) +{ + res_point *result= (res_point *)new_item(); + *m_res_hook= result; + result->prev_hook= m_res_hook; + m_res_hook= &result->next; + result->type= type; +#ifndef DBUG_OFF + result->point_n= n_res_points++; +#endif /*DBUG_OFF*/ +#ifndef NO_TESTING + if (result->point_n == 74) + call_checkpoint(74); +#endif /*NO_TESTING*/ + return result; +} + +int Gcalc_operation_reducer::add_line(int incoming, active_thread *t, + const Gcalc_scan_iterator::point *p) +{ + line *l= new_line(); + if (!l) + return 1; + l->incoming= incoming; + l->t= t; + l->p= p; + *m_lines_hook= l; + m_lines_hook= &l->next; + return 0; +} + + +int Gcalc_operation_reducer::add_poly_border(int incoming, + active_thread *t, int prev_state, const Gcalc_scan_iterator::point *p) +{ + poly_border *b= new_poly_border(); + if (!b) + return 1; + b->incoming= incoming; + b->t= t; + b->prev_state= prev_state; + b->p= p; + *m_poly_borders_hook= b; + m_poly_borders_hook= &b->next; + return 0; +} + + +int Gcalc_operation_reducer::continue_range(active_thread *t, + const Gcalc_heap::Info *p, + const Gcalc_heap::Info *p_next) { res_point *rp= add_res_point(t->rp->type); if (!rp) @@ -527,15 +598,14 @@ inline int Gcalc_operation_reducer::continue_range(active_thread *t, rp->intersection_point= false; rp->pi= p; t->rp= rp; - t->horiz_dir= horiz_dir; - t->dx_dy= dx_dy; + t->p1= p; + t->p2= p_next; return 0; } inline int Gcalc_operation_reducer::continue_i_range(active_thread *t, - double x, double y, - int horiz_dir, double dx_dy) + const Gcalc_heap::Intersection_info *ii) { res_point *rp= add_res_point(t->rp->type); if (!rp) @@ -544,11 +614,8 @@ inline int Gcalc_operation_reducer::continue_i_range(active_thread *t, rp->down= t->rp; t->rp->up= rp; rp->intersection_point= true; - rp->x= x; - rp->y= y; + rp->ii= ii; t->rp= rp; - t->horiz_dir= horiz_dir; - t->dx_dy= dx_dy; return 0; } @@ -573,6 +640,9 @@ int Gcalc_operation_reducer::end_couple(active_thread *t0, active_thread *t1, } +#ifndef NO_TESTING +int ca_counter= 0; +#endif /*NO_TESTING*/ int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si) { Gcalc_point_iterator pi(si); @@ -587,8 +657,16 @@ int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si) active_thread *bottom_threads= NULL; active_thread *eq_thread, *point_thread;; +#ifndef NO_TESTING + if (ca_counter == 11522) + call_checkpoint(89); +#endif /*NO_TESTING*/ m_fn->clear_state(); /* Walk to the event, remembering what is needed. */ +#ifndef NO_TESTING + if (si->get_event_position() == pi.point()) + printf("yyy\n"); +#endif /*NO_TESTING*/ for (; pi.point() != si->get_event_position(); ++pi, cur_t_hook= (active_thread **) &(*cur_t_hook)->next) { @@ -612,13 +690,13 @@ int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si) case scev_point: { if (cur_t->enabled() && - continue_range(cur_t, events->pi, events->horiz_dir, events->dx_dy)) + continue_range(cur_t, events->pi, events->next_pi)) return 1; break; } case scev_end: { - if (cur_t->enabled() && end_line(cur_t, events->pi, si)) + if (cur_t->enabled() && end_line(cur_t, si)) return 1; *cur_t_hook= cur_t->get_next(); free_item(cur_t); @@ -635,8 +713,7 @@ int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si) else if (cur_t->enabled() || cur_t->get_next()->enabled()) { /* Rare case when edges of a polygon coincide */ - if (end_line(cur_t->enabled() ? cur_t : cur_t->get_next(), - events->pi, si)) + if (end_line(cur_t->enabled() ? cur_t : cur_t->get_next(), si)) return 1; } *cur_t_hook= cur_t->get_next()->get_next(); @@ -647,6 +724,9 @@ int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si) default: DBUG_ASSERT(0); } +#ifndef NO_TESTING + goto testing; +#endif /*NO_TESTING*/ return 0; } @@ -773,7 +853,7 @@ int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si) for (events= si->get_events(); events; events= events->get_next()) m_fn->set_on_state(events->get_shape()); - return m_fn->count() ? add_single_point(event_point, si) : 0; + return m_fn->count() ? add_single_point(si) : 0; } if (m_poly_borders) @@ -783,6 +863,10 @@ int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si) { poly_border *pb1, *pb2; pb1= m_poly_borders; +#ifndef NO_TESTING + if (!m_poly_borders->next) + call_checkpoint(3); +#endif /*NO_TESTING*/ DBUG_ASSERT(m_poly_borders->next); pb2= get_pair_border(pb1); @@ -790,8 +874,7 @@ int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si) m_poly_borders= pb1->get_next(); if (connect_threads(pb1->incoming, pb2->incoming, pb1->t, pb2->t, pb1->p, pb2->p, - prev_range, event_point, si, - Gcalc_function::shape_polygon)) + prev_range, si, Gcalc_function::shape_polygon)) return 1; free_item(pb1); @@ -809,8 +892,8 @@ int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si) { if (connect_threads(m_lines->incoming, m_lines->get_next()->incoming, m_lines->t, m_lines->get_next()->t, - m_lines->p, m_lines->get_next()->p, NULL, - event_point, si, Gcalc_function::shape_line)) + m_lines->p, m_lines->get_next()->p, + NULL, si, Gcalc_function::shape_line)) return 1; } else @@ -819,11 +902,11 @@ int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si) { if (cur_line->incoming) { - if (end_line(cur_line->t, event_point, si)) + if (end_line(cur_line->t, si)) return 1; } else - start_line(cur_line->t, cur_line->p, event_point, si); + start_line(cur_line->t, cur_line->p, si); } } free_list(m_lines); @@ -834,28 +917,56 @@ int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si) if (bottom_threads) free_list(bottom_threads); +#ifndef NO_TESTING +testing: + { + Gcalc_point_iterator x_pi(si); + active_thread **x_cur_t_hook= &m_first_active_thread; + int x_prev_state= 0; + m_fn->save_states(); + m_fn->clear_state(); + if (ca_counter == /*11552*/90) + call_checkpoint(10); + for (; x_pi.point(); ++x_pi) + { + active_thread *cur_t= *x_cur_t_hook; + if (cur_t->enabled() && + cur_t->rp->type == Gcalc_function::shape_polygon) + x_prev_state^= 1; + int ppb= m_fn->count(); + if (m_fn->get_shape_kind(x_pi.get_shape()) == Gcalc_function::shape_polygon) + m_fn->invert_state(x_pi.get_shape()); + int ppa= m_fn->count(); + if (ppa != x_prev_state) + { + if (x_pi.point()->cmp_dx_dy(x_pi.point()->get_next()) != 0) + call_checkpoint(21); + } + if (cur_t->enabled()) + { + if (m_fn->get_shape_kind(x_pi.get_shape()) == Gcalc_function::shape_polygon) + if (ppa == ppb) + call_checkpoint(22); + else + if (ppa != 0 && ppb != 0) + call_checkpoint(23); + } + x_cur_t_hook= (active_thread **) &(*x_cur_t_hook)->next; + } + m_fn->restore_states(); + } +#endif /*NO_TESTING*/ return 0; } -int Gcalc_operation_reducer::add_single_point(const Gcalc_heap::Info *p, - const Gcalc_scan_iterator *si) +int Gcalc_operation_reducer::add_single_point(const Gcalc_scan_iterator *si) { res_point *rp= add_res_point(Gcalc_function::shape_point); if (!rp) return 1; rp->glue= rp->up= rp->down= NULL; - if (p) - { - rp->intersection_point= false; - rp->pi= p; - } - else - { - rp->intersection_point= true; - rp->y= si->get_y(); - rp->x= si->get_events()->x; - } + rp->set(si); return 0; } @@ -912,7 +1023,7 @@ int Gcalc_operation_reducer::connect_threads( int incoming_a, int incoming_b, active_thread *ta, active_thread *tb, const Gcalc_scan_iterator::point *pa, const Gcalc_scan_iterator::point *pb, - active_thread *prev_range, const Gcalc_heap::Info *ev_p, + active_thread *prev_range, const Gcalc_scan_iterator *si, Gcalc_function::shape_type s_t) { if (incoming_a && incoming_b) @@ -929,18 +1040,8 @@ int Gcalc_operation_reducer::connect_threads( rpa->up= rpb->up= NULL; ta->rp->up= rpa; tb->rp->up= rpb; - if (ev_p) - { - rpa->intersection_point= rpb->intersection_point= false; - rpa->pi= rpb->pi= ev_p; - } - else - { - rpa->intersection_point= rpb->intersection_point= true; - rpa->x= rpb->x= si->get_events()->x; - rpa->y= rpb->y= si->get_y(); - } - + rpa->set(si); + rpb->set(si); ta->rp= tb->rp= NULL; return 0; } @@ -953,35 +1054,30 @@ int Gcalc_operation_reducer::connect_threads( return 1; rp0->glue= rp1; rp1->glue= rp0; - if (ev_p) - { - rp0->intersection_point= rp1->intersection_point= false; - rp0->pi= rp1->pi= ev_p; - } - else - { - rp0->intersection_point= rp1->intersection_point= true; - rp0->x= rp1->x= si->get_events()->x; - rp0->y= rp1->y= si->get_y(); - } + rp0->set(si); + rp1->set(si); rp0->down= rp1->down= NULL; ta->rp= rp0; tb->rp= rp1; - ta->horiz_dir= pa->horiz_dir; - ta->dx_dy= pa->dx_dy; + ta->p1= pa->pi; + ta->p2= pa->next_pi; - tb->horiz_dir= pb->horiz_dir; - tb->dx_dy= pb->dx_dy; + tb->p1= pb->pi; + tb->p2= pb->next_pi; if (prev_range) { rp0->outer_poly= prev_range->thread_start; tb->thread_start= prev_range->thread_start; + /* Chack if needed */ + ta->thread_start= prev_range->thread_start; } else { rp0->outer_poly= 0; ta->thread_start= rp0; + /* Chack if needed */ + tb->thread_start= rp0; } return 0; } @@ -991,20 +1087,18 @@ int Gcalc_operation_reducer::connect_threads( tb->rp= ta->rp; tb->thread_start= ta->thread_start; if (Gcalc_scan_iterator::point:: - compare_dx_dy(ta->horiz_dir, ta->dx_dy, - pb->horiz_dir, pb->dx_dy) != 0) + cmp_dx_dy(ta->p1, ta->p2, pb->pi, pb->next_pi) != 0) { - if (ev_p ? continue_range(tb, ev_p, pb->horiz_dir, pb->dx_dy): - continue_i_range(tb, - si->get_events()->x, si->get_y(), - pb->horiz_dir, pb->dx_dy)) + if (si->intersection_step() ? + continue_i_range(tb, si->get_cur_ii()) : + continue_range(tb, si->get_cur_pi(), pb->next_pi)) +#ifdef TMP_BLOCK + continue_range(tb, si->get_cur_pi()) +#endif /*TMP_BLOCK*/ return 1; } - else - { - tb->horiz_dir= pb->horiz_dir; - tb->dx_dy= pb->dx_dy; - } + tb->p1= pb->pi; + tb->p2= pb->next_pi; return 0; } @@ -1012,33 +1106,21 @@ int Gcalc_operation_reducer::connect_threads( int Gcalc_operation_reducer::start_line(active_thread *t, const Gcalc_scan_iterator::point *p, - const Gcalc_heap::Info *ev_p, const Gcalc_scan_iterator *si) { res_point *rp= add_res_point(Gcalc_function::shape_line); if (!rp) return 1; rp->glue= rp->down= NULL; - if (ev_p) - { - rp->intersection_point= false; - rp->pi= ev_p; - } - else - { - rp->intersection_point= true; - rp->x= si->get_events()->x; - rp->y= si->get_y(); - } + rp->set(si); t->rp= rp; - t->horiz_dir= p->horiz_dir; - t->dx_dy= p->dx_dy; + t->p1= p->pi; + t->p2= p->next_pi; return 0; } int Gcalc_operation_reducer::end_line(active_thread *t, - const Gcalc_heap::Info *ev_p, const Gcalc_scan_iterator *si) { DBUG_ASSERT(t->rp->type == Gcalc_function::shape_line); @@ -1047,17 +1129,7 @@ int Gcalc_operation_reducer::end_line(active_thread *t, return 1; rp->glue= rp->up= NULL; rp->down= t->rp; - if (ev_p) - { - rp->intersection_point= false; - rp->pi= ev_p; - } - else - { - rp->intersection_point= true; - rp->x= si->get_events()->x; - rp->y= si->get_y(); - } + rp->set(si); t->rp->up= rp; t->rp= NULL; @@ -1071,6 +1143,11 @@ int Gcalc_operation_reducer::count_all(Gcalc_heap *hp) si.init(hp); while (si.more_points()) { +#ifndef NO_TESTING + printf("Point %d\n", ++ca_counter); + if (ca_counter == 12) + call_checkpoint(10); +#endif /*NO_TESTING*/ if (si.step()) return 1; if (count_slice(&si)) @@ -1094,8 +1171,9 @@ inline int Gcalc_operation_reducer::get_single_result(res_point *res, { if (res->intersection_point) { - if (storage->single_point(float_to_coord(res->x), - float_to_coord(res->y))) + double x, y; + res->ii->calc_xy(&x, &y); + if (storage->single_point(x,y)) return 1; } else @@ -1105,6 +1183,9 @@ inline int Gcalc_operation_reducer::get_single_result(res_point *res, return 0; } +#ifndef NO_TESTING +int pc_counter= 0; +#endif /*NO_TESTING*/ int Gcalc_operation_reducer::get_result_thread(res_point *cur, Gcalc_result_receiver *storage, @@ -1116,12 +1197,16 @@ int Gcalc_operation_reducer::get_result_thread(res_point *cur, double x, y; while (cur) { +#ifndef NO_TESTING + ++pc_counter; + if (pc_counter == 79) + call_checkpoint(79); +#endif /*NO_TESTING*/ if (!glue_step) { if (cur->intersection_point) { - x= float_to_coord(cur->x); - y= float_to_coord(cur->y); + cur->ii->calc_xy(&x, &y); } else { -- cgit v1.2.1 From 5123f59ed2b363ac25fdef374af607f93ec9d762 Mon Sep 17 00:00:00 2001 From: Alexey Botchkov Date: Thu, 22 Sep 2011 18:53:36 +0500 Subject: fixed bugs 855485 ST_CROSSES returns different result than PostGIS for overlapping polygons 855487 ST_WITHIN returns wrong result for partially overlapping polygons 855492 ST_WITHIN returns TRUE on point on the edge of a polygon 855497 ST_ENVELOPE of GEOMETRYCOLLECTION EMPTY returns NULL and not GEOMETRYCOLLECTION EMPTY 855503 ST_EQUALS reports TRUE between a POLYGON and a MULTILINESTRING 855505 ST_TOUCHES reports TRUE for intersecting polygon and linestring Changed the way weird functions like Crosses or Touches treated. Added BORDER handling to the Gcalc_function. per-file comments: mysql-test/r/gis-precise.result GIS bugs fixed. test result updated. mysql-test/t/gis-precise.test GIS bugs fixed. test cases added. sql/gcalc_slicescan.h GIS bugs fixed. sql/gcalc_tools.cc GIS bugs fixed. sql/gcalc_tools.h GIS bugs fixed. sql/item_create.cc GIS bugs fixed. sql/item_geofunc.cc GIS bugs fixed. sql/item_geofunc.h GIS bugs fixed. sql/spatial.cc GIS bugs fixed. --- sql/gcalc_tools.cc | 211 +++++++++++++++++++++++++++++++++++++++++------------ 1 file changed, 165 insertions(+), 46 deletions(-) (limited to 'sql/gcalc_tools.cc') diff --git a/sql/gcalc_tools.cc b/sql/gcalc_tools.cc index 90c39f08d0b..6a2fdbccacb 100644 --- a/sql/gcalc_tools.cc +++ b/sql/gcalc_tools.cc @@ -43,7 +43,7 @@ gcalc_shape_info Gcalc_function::add_new_shape(uint32 shape_id, in prefix style. */ -void Gcalc_function::add_operation(op_type operation, uint32 n_operands) +void Gcalc_function::add_operation(uint operation, uint32 n_operands) { uint32 op_code= (uint32 ) operation + n_operands; function_buffer.q_append(op_code); @@ -84,6 +84,15 @@ int Gcalc_function::single_shape_op(shape_type shape_kind, gcalc_shape_info *si) } +int Gcalc_function::repeat_expression(uint32 exp_pos) +{ + if (reserve_op_buffer(1)) + return 1; + add_operation(op_repeat, exp_pos); + return 0; +} + + /* Specify how many arguments we're going to have. */ @@ -109,42 +118,61 @@ int Gcalc_function::alloc_states() if (function_buffer.reserve((n_shapes+1) * 2 * sizeof(int))) return 1; i_states= (int *) (function_buffer.ptr() + ALIGN_SIZE(function_buffer.length())); - saved_i_states= i_states + (n_shapes + 1); + b_states= i_states + (n_shapes + 1); return 0; } -void Gcalc_function::save_states() +int Gcalc_function::count_internal(const char *cur_func, uint set_type, + const char **end) { - memcpy(saved_i_states, i_states, (n_shapes+1) * sizeof(int)); -} - - -void Gcalc_function::restore_states() -{ - memcpy(i_states, saved_i_states, (n_shapes+1) * sizeof(int)); -} - - -int Gcalc_function::count_internal() -{ - int c_op= uint4korr(cur_func); + uint c_op= uint4korr(cur_func); op_type next_func= (op_type) (c_op & op_any); int mask= (c_op & op_not) ? 1:0; - int n_ops= c_op & ~op_any; + uint n_ops= c_op & ~(op_any | op_not | v_mask); + uint n_shape= c_op & ~(op_any | op_not | v_mask); /* same as n_ops */ + value v_state= (value) (c_op & v_mask); int result; + const char *sav_cur_func= cur_func; cur_func+= 4; if (next_func == op_shape) - return i_states[c_op & ~(op_any | op_not)] ^ mask; + { + if (set_type == 0) + result= i_states[n_shape] | b_states[n_shape]; + else if (set_type == op_border) + result= b_states[n_shape]; + else if (set_type == op_internals) + result= i_states[n_shape] && !b_states[n_shape]; + goto exit; + } + + if (next_func == op_false) + { + result= 0; + goto exit; + } + + if (next_func == op_border || next_func == op_internals) + { + result= count_internal(cur_func, next_func, &cur_func); + goto exit; + } + + if (next_func == op_repeat) + { + result= count_internal(function_buffer.ptr() + n_ops, set_type, 0); + goto exit; + } + if (n_ops == 0) return mask; - result= count_internal(); + result= count_internal(cur_func, set_type, &cur_func); while (--n_ops) { - int next_res= count_internal(); + int next_res= count_internal(cur_func, set_type, &cur_func); switch (next_func) { case op_union: @@ -159,15 +187,59 @@ int Gcalc_function::count_internal() case op_difference: result= result & !next_res; break; - case op_backdifference: - result= !result & next_res; - break; default: DBUG_ASSERT(FALSE); }; } - return result ^ mask; +exit: + result^= mask; + if (v_state != v_empty) + { + switch (v_state) + { + case v_find_t: + if (result) + { + c_op= (c_op & ~v_mask) | v_t_found; + int4store(sav_cur_func, c_op); + }; + break; + case v_find_f: + if (!result) + { + c_op= (c_op & ~v_mask) | v_f_found; + int4store(sav_cur_func, c_op); + }; + break; + case v_t_found: + result= 1; + break; + case v_f_found: + result= 0; + break; + default: + DBUG_ASSERT(0); + }; + } + + if (end) + *end= cur_func; + return result; +} + + +void Gcalc_function::clear_i_states() +{ + for (uint i= 0; i < n_shapes; i++) + i_states[i]= 0; +} + + +void Gcalc_function::clear_b_states() +{ + for (uint i= 0; i < n_shapes; i++) + b_states[i]= 0; } @@ -183,7 +255,7 @@ void Gcalc_function::reset() } -int Gcalc_function::find_function(Gcalc_scan_iterator &scan_it) +int Gcalc_function::check_function(Gcalc_scan_iterator &scan_it) { const Gcalc_scan_iterator::point *eq_start, *cur_eq, *events; @@ -194,31 +266,58 @@ int Gcalc_function::find_function(Gcalc_scan_iterator &scan_it) events= scan_it.get_events(); /* these kinds of events don't change the function */ - if (events->simple_event()) - continue; - Gcalc_point_iterator pit(&scan_it); - clear_state(); + clear_b_states(); + clear_i_states(); /* Walk to the event, marking polygons we met */ for (; pit.point() != scan_it.get_event_position(); ++pit) { gcalc_shape_info si= pit.point()->get_shape(); if ((get_shape_kind(si) == Gcalc_function::shape_polygon)) - invert_state(si); + invert_i_state(si); } - save_states(); + if (events->simple_event()) + { + if (events->event == scev_end) + set_b_state(events->get_shape()); + + if (count()) + return 1; + clear_b_states(); + continue; + } + /* Check the status of the event point */ for (; events; events= events->get_next()) - set_on_state(events->get_shape()); + { + gcalc_shape_info si= events->get_shape(); + if (events->event == scev_thread || + events->event == scev_end || + (get_shape_kind(si) == Gcalc_function::shape_polygon)) + set_b_state(si); + else if (get_shape_kind(si) == Gcalc_function::shape_line) + invert_i_state(si); + } if (count()) return 1; + /* Set back states changed in the loop above. */ + for (events= scan_it.get_events(); events; events= events->get_next()) + { + gcalc_shape_info si= events->get_shape(); + if (events->event == scev_thread || + events->event == scev_end || + (get_shape_kind(si) == Gcalc_function::shape_polygon)) + clear_b_state(si); + else if (get_shape_kind(si) == Gcalc_function::shape_line) + invert_i_state(si); + } + if (scan_it.get_event_position() == scan_it.get_event_end()) continue; /* Check the status after the event */ - restore_states(); eq_start= pit.point(); do { @@ -226,18 +325,28 @@ int Gcalc_function::find_function(Gcalc_scan_iterator &scan_it) if (pit.point() != scan_it.get_event_end() && eq_start->cmp_dx_dy(pit.point()) == 0) continue; - save_states(); for (cur_eq= eq_start; cur_eq != pit.point(); cur_eq= cur_eq->get_next()) - set_on_state(cur_eq->get_shape()); + { + gcalc_shape_info si= cur_eq->get_shape(); + if (get_shape_kind(si) == Gcalc_function::shape_polygon) + set_b_state(si); + else + invert_i_state(si); + } if (count()) return 1; - restore_states(); + for (cur_eq= eq_start; cur_eq != pit.point(); cur_eq= cur_eq->get_next()) { gcalc_shape_info si= cur_eq->get_shape(); if ((get_shape_kind(si) == Gcalc_function::shape_polygon)) - invert_state(si); + { + clear_b_state(si); + invert_i_state(si); + } + else + invert_i_state(cur_eq->get_shape()); } if (count()) return 1; @@ -313,6 +422,15 @@ int Gcalc_operation_transporter::start_collection(int n_objects) } +int Gcalc_operation_transporter::empty_shape() +{ + if (m_fn->reserve_op_buffer(1)) + return 1; + m_fn->add_operation(Gcalc_function::op_false, 0); + return 0; +} + + int Gcalc_result_receiver::start_shape(Gcalc_function::shape_type shape) { if (buffer.reserve(4*2, 512)) @@ -661,7 +779,7 @@ int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si) if (ca_counter == 11522) call_checkpoint(89); #endif /*NO_TESTING*/ - m_fn->clear_state(); + m_fn->clear_i_states(); /* Walk to the event, remembering what is needed. */ #ifndef NO_TESTING if (si->get_event_position() == pi.point()) @@ -678,7 +796,7 @@ int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si) prev_range= prev_state ? cur_t : 0; } if (m_fn->get_shape_kind(pi.get_shape()) == Gcalc_function::shape_polygon) - m_fn->invert_state(pi.get_shape()); + m_fn->invert_i_state(pi.get_shape()); } events= si->get_events(); @@ -800,6 +918,7 @@ int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si) eq_start= pi.point(); eq_thread= point_thread= *starting_t_hook; + m_fn->clear_b_states(); while (eq_start != si->get_event_end()) { const Gcalc_scan_iterator::point *cur_eq; @@ -812,17 +931,16 @@ int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si) eq_start->cmp_dx_dy(pi.point()) == 0) continue; - m_fn->save_states(); for (cur_eq= eq_start; cur_eq != pi.point(); cur_eq= cur_eq->get_next()) - m_fn->set_on_state(cur_eq->get_shape()); + m_fn->set_b_state(cur_eq->get_shape()); in_state= m_fn->count(); - m_fn->restore_states(); + m_fn->clear_b_states(); for (cur_eq= eq_start; cur_eq != pi.point(); cur_eq= cur_eq->get_next()) { gcalc_shape_info si= cur_eq->get_shape(); if ((m_fn->get_shape_kind(si) == Gcalc_function::shape_polygon)) - m_fn->invert_state(si); + m_fn->invert_i_state(si); } after_state= m_fn->count(); if (prev_state != after_state) @@ -844,14 +962,15 @@ int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si) if (!sav_prev_state && !m_poly_borders && !m_lines) { /* Check if we need to add the event point itself */ - m_fn->clear_state(); + m_fn->clear_i_states(); + /* b_states supposed to be clean already */ for (pi.restart(si); pi.point() != si->get_event_position(); ++pi) { if (m_fn->get_shape_kind(pi.get_shape()) == Gcalc_function::shape_polygon) - m_fn->invert_state(pi.get_shape()); + m_fn->invert_i_state(pi.get_shape()); } for (events= si->get_events(); events; events= events->get_next()) - m_fn->set_on_state(events->get_shape()); + m_fn->set_b_state(events->get_shape()); return m_fn->count() ? add_single_point(si) : 0; } -- cgit v1.2.1 From dca6ff48c1a26f8eab911f4ad246f56be5005fd7 Mon Sep 17 00:00:00 2001 From: Alexey Botchkov Date: Fri, 23 Sep 2011 15:25:48 +0500 Subject: fix for bug 857051 ST_EQUALS returns TRUE on two nonidentical MULTIPOINTs The 'single point' event was forgotten in the relation's calculation per-file comments: mysql-test/r/gis-precise.result fix for bug 857051 ST_EQUALS returns TRUE on two nonidentical MULTIPOINTs test result updated. mysql-test/t/gis-precise.test fix for bug 857051 ST_EQUALS returns TRUE on two nonidentical MULTIPOINTs test case added. sql/gcalc_tools.cc fix for bug 857051 ST_EQUALS returns TRUE on two nonidentical MULTIPOINTs scev_single_point is properly handled. --- sql/gcalc_tools.cc | 2 ++ 1 file changed, 2 insertions(+) (limited to 'sql/gcalc_tools.cc') diff --git a/sql/gcalc_tools.cc b/sql/gcalc_tools.cc index 6a2fdbccacb..4c56e5c58bd 100644 --- a/sql/gcalc_tools.cc +++ b/sql/gcalc_tools.cc @@ -293,6 +293,7 @@ int Gcalc_function::check_function(Gcalc_scan_iterator &scan_it) gcalc_shape_info si= events->get_shape(); if (events->event == scev_thread || events->event == scev_end || + events->event == scev_single_point || (get_shape_kind(si) == Gcalc_function::shape_polygon)) set_b_state(si); else if (get_shape_kind(si) == Gcalc_function::shape_line) @@ -308,6 +309,7 @@ int Gcalc_function::check_function(Gcalc_scan_iterator &scan_it) gcalc_shape_info si= events->get_shape(); if (events->event == scev_thread || events->event == scev_end || + events->event == scev_single_point || (get_shape_kind(si) == Gcalc_function::shape_polygon)) clear_b_state(si); else if (get_shape_kind(si) == Gcalc_function::shape_line) -- cgit v1.2.1 From 5b83aee35dffff0de4758a2a595624a18bec2b3e Mon Sep 17 00:00:00 2001 From: Alexey Botchkov Date: Fri, 23 Sep 2011 15:36:56 +0500 Subject: bug #857050 ST_WITHIN returns wrong result with MULTIPOINT and POLYGON actually only testcase added as the bug was fixed already. modified: mysql-test/r/gis-precise.result bug #857050 ST_WITHIN returns wrong result with MULTIPOINT and POLYGON test result updated. mysql-test/t/gis-precise.test bug #857050 ST_WITHIN returns wrong result with MULTIPOINT and POLYGON test case added. sql/gcalc_tools.cc superfluous variable removed. --- sql/gcalc_tools.cc | 4 ++++ 1 file changed, 4 insertions(+) (limited to 'sql/gcalc_tools.cc') diff --git a/sql/gcalc_tools.cc b/sql/gcalc_tools.cc index 4c56e5c58bd..69071c16ee8 100644 --- a/sql/gcalc_tools.cc +++ b/sql/gcalc_tools.cc @@ -766,7 +766,9 @@ int ca_counter= 0; int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si) { Gcalc_point_iterator pi(si); +#ifdef TMP_BLOCK const Gcalc_heap::Info *event_point= NULL; +#endif /*TMP_BLOCK*/ int prev_state= 0; int sav_prev_state; active_thread *prev_range= NULL; @@ -858,8 +860,10 @@ int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si) { active_thread *cur_t= *cur_t_hook; +#ifdef TMP_BLOCK if (!event_point && events->event != scev_intersection) event_point= events->pi; +#endif /*TMP_BLOCK*/ if (events->event == scev_single_point) continue; -- cgit v1.2.1 From 6e7d578b2b3fad8671504785b757e53b11516b22 Mon Sep 17 00:00:00 2001 From: Alexey Botchkov Date: Fri, 23 Sep 2011 17:00:36 +0500 Subject: bug 857087 Wrong result with ST_INTERSECTS and LINESTRINGs Line autointersection point was treated as if it doesn't belong to the line. It's in some way logical, but seems to confuse people. Fixed. per_file_comments: mysql-test/r/gis-precise.result bug 857087 Wrong result with ST_INTERSECTS and LINESTRINGs test result updated. mysql-test/t/gis-precise.test bug 857087 Wrong result with ST_INTERSECTS and LINESTRINGs test case added. sql/gcalc_tools.cc bug 857087 Wrong result with ST_INTERSECTS and LINESTRINGs Point of line autointersection handled as it belongs to the line. sql/gcalc_tools.h bug 857087 Wrong result with ST_INTERSECTS and LINESTRINGs Gcalc_function::set_i_state() added --- sql/gcalc_tools.cc | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'sql/gcalc_tools.cc') diff --git a/sql/gcalc_tools.cc b/sql/gcalc_tools.cc index 69071c16ee8..8e881b84c5d 100644 --- a/sql/gcalc_tools.cc +++ b/sql/gcalc_tools.cc @@ -297,7 +297,7 @@ int Gcalc_function::check_function(Gcalc_scan_iterator &scan_it) (get_shape_kind(si) == Gcalc_function::shape_polygon)) set_b_state(si); else if (get_shape_kind(si) == Gcalc_function::shape_line) - invert_i_state(si); + set_i_state(si); } if (count()) @@ -313,7 +313,7 @@ int Gcalc_function::check_function(Gcalc_scan_iterator &scan_it) (get_shape_kind(si) == Gcalc_function::shape_polygon)) clear_b_state(si); else if (get_shape_kind(si) == Gcalc_function::shape_line) - invert_i_state(si); + clear_i_state(si); } if (scan_it.get_event_position() == scan_it.get_event_end()) -- cgit v1.2.1 From e99850774b67f012f078c1a2b36f27dbbea8e804 Mon Sep 17 00:00:00 2001 From: Alexey Botchkov Date: Tue, 4 Oct 2011 15:01:21 +0500 Subject: GIS library code cleanup. GCALC_DBUG_OFF and related infrastructure defined so we can enable/disable debugging conveniently. per-file comments: sql/gcalc_slicescan.cc GIS library code cleanup. sql/gcalc_slicescan.h GIS library code cleanup. sql/gcalc_tools.cc GIS library code cleanup. sql/gcalc_tools.h GIS library code cleanup. --- sql/gcalc_tools.cc | 283 +++++++++++++++++++++-------------------------------- 1 file changed, 109 insertions(+), 174 deletions(-) (limited to 'sql/gcalc_tools.cc') diff --git a/sql/gcalc_tools.cc b/sql/gcalc_tools.cc index 8e881b84c5d..5871dce8642 100644 --- a/sql/gcalc_tools.cc +++ b/sql/gcalc_tools.cc @@ -135,6 +135,8 @@ int Gcalc_function::count_internal(const char *cur_func, uint set_type, int result; const char *sav_cur_func= cur_func; + // GCALC_DBUG_ENTER("Gcalc_function::count_internal"); + cur_func+= 4; if (next_func == op_shape) { @@ -167,6 +169,7 @@ int Gcalc_function::count_internal(const char *cur_func, uint set_type, if (n_ops == 0) return mask; + //GCALC_DBUG_RETURN(mask); result= count_internal(cur_func, set_type, &cur_func); @@ -219,13 +222,14 @@ exit: result= 0; break; default: - DBUG_ASSERT(0); + GCALC_DBUG_ASSERT(0); }; } if (end) *end= cur_func; return result; + //GCALC_DBUG_RETURN(result); } @@ -258,11 +262,12 @@ void Gcalc_function::reset() int Gcalc_function::check_function(Gcalc_scan_iterator &scan_it) { const Gcalc_scan_iterator::point *eq_start, *cur_eq, *events; + GCALC_DBUG_ENTER("Gcalc_function::check_function"); while (scan_it.more_points()) { if (scan_it.step()) - return -1; + GCALC_DBUG_RETURN(-1); events= scan_it.get_events(); /* these kinds of events don't change the function */ @@ -282,7 +287,7 @@ int Gcalc_function::check_function(Gcalc_scan_iterator &scan_it) set_b_state(events->get_shape()); if (count()) - return 1; + GCALC_DBUG_RETURN(1); clear_b_states(); continue; } @@ -301,7 +306,7 @@ int Gcalc_function::check_function(Gcalc_scan_iterator &scan_it) } if (count()) - return 1; + GCALC_DBUG_RETURN(1); /* Set back states changed in the loop above. */ for (events= scan_it.get_events(); events; events= events->get_next()) @@ -337,7 +342,7 @@ int Gcalc_function::check_function(Gcalc_scan_iterator &scan_it) invert_i_state(si); } if (count()) - return 1; + GCALC_DBUG_RETURN(1); for (cur_eq= eq_start; cur_eq != pit.point(); cur_eq= cur_eq->get_next()) { @@ -351,11 +356,11 @@ int Gcalc_function::check_function(Gcalc_scan_iterator &scan_it) invert_i_state(cur_eq->get_shape()); } if (count()) - return 1; + GCALC_DBUG_RETURN(1); eq_start= pit.point(); } while (pit.point() != scan_it.get_event_end()); } - return 0; + GCALC_DBUG_RETURN(0); } @@ -435,52 +440,51 @@ int Gcalc_operation_transporter::empty_shape() int Gcalc_result_receiver::start_shape(Gcalc_function::shape_type shape) { + GCALC_DBUG_ENTER("Gcalc_result_receiver::start_shape"); if (buffer.reserve(4*2, 512)) - return 1; + GCALC_DBUG_RETURN(1); cur_shape= shape; shape_pos= buffer.length(); buffer.length(shape_pos + ((shape == Gcalc_function::shape_point) ? 4:8)); n_points= 0; shape_area= 0.0; - return 0; + GCALC_DBUG_RETURN(0); } int Gcalc_result_receiver::add_point(double x, double y) { + GCALC_DBUG_ENTER("Gcalc_result_receiver::add_point"); if (n_points && x == prev_x && y == prev_y) - return 0; + GCALC_DBUG_RETURN(0); if (!n_points++) { prev_x= first_x= x; prev_y= first_y= y; - return 0; + GCALC_DBUG_RETURN(0); } shape_area+= prev_x*y - prev_y*x; if (buffer.reserve(8*2, 512)) - return 1; + GCALC_DBUG_RETURN(1); buffer.q_append(prev_x); buffer.q_append(prev_y); prev_x= x; prev_y= y; -#ifndef NO_TESTING - if (n_points == 53) - printf("xxx\n"); -#endif /*NO_TESTING*/ - return 0; + GCALC_DBUG_RETURN(0); } int Gcalc_result_receiver::complete_shape() { + GCALC_DBUG_ENTER("Gcalc_result_receiver::complete_shape"); if (n_points == 0) { buffer.length(shape_pos); - return 0; + GCALC_DBUG_RETURN(0); } if (n_points == 1) { @@ -489,7 +493,7 @@ int Gcalc_result_receiver::complete_shape() if (cur_shape == Gcalc_function::shape_hole) { buffer.length(shape_pos); - return 0; + GCALC_DBUG_RETURN(0); } cur_shape= Gcalc_function::shape_point; buffer.length(buffer.length()-4); @@ -504,7 +508,7 @@ int Gcalc_result_receiver::complete_shape() if (fabs(shape_area) < 1e-8) { buffer.length(shape_pos); - return 0; + GCALC_DBUG_RETURN(0); } } @@ -520,7 +524,7 @@ int Gcalc_result_receiver::complete_shape() } if (buffer.reserve(8*2, 512)) - return 1; + GCALC_DBUG_RETURN(1); buffer.q_append(prev_x); buffer.q_append(prev_y); @@ -540,7 +544,7 @@ do_complete: { collection_result= true; } - return 0; + GCALC_DBUG_RETURN(0); } @@ -593,28 +597,30 @@ int Gcalc_result_receiver::move_hole(uint32 dest_position, uint32 source_positio { char *ptr; int source_len; + GCALC_DBUG_ENTER("Gcalc_result_receiver::move_hole"); + GCALC_DBUG_PRINT(("ps %d %d", dest_position, source_position)); *position_shift= source_len= buffer.length() - source_position; if (dest_position == source_position) - return 0; + GCALC_DBUG_RETURN(0); if (buffer.reserve(source_len, MY_ALIGN(source_len, 512))) - return 1; + GCALC_DBUG_RETURN(1); ptr= (char *) buffer.ptr(); memmove(ptr + dest_position + source_len, ptr + dest_position, buffer.length() - dest_position); memcpy(ptr + dest_position, ptr + buffer.length(), source_len); - return 0; + GCALC_DBUG_RETURN(0); } Gcalc_operation_reducer::Gcalc_operation_reducer(size_t blk_size) : Gcalc_dyn_list(blk_size, sizeof(res_point)), -#ifndef DBUG_OFF +#ifndef GCALC_DBUG_OFF n_res_points(0), -#endif /*DBUG_OFF*/ +#endif /*GCALC_DBUG_OFF*/ m_res_hook((Gcalc_dyn_list::Item **)&m_result), m_first_active_thread(NULL) {} @@ -649,43 +655,35 @@ void Gcalc_operation_reducer::res_point::set(const Gcalc_scan_iterator *si) pi= si->get_cur_pi(); } -#ifndef NO_TESTING -void call_checkpoint(int d) -{ - printf("%d\n", d); -} -#endif /*NO_TESTING*/ Gcalc_operation_reducer::res_point * Gcalc_operation_reducer::add_res_point(Gcalc_function::shape_type type) { + GCALC_DBUG_ENTER("Gcalc_operation_reducer::add_res_point"); res_point *result= (res_point *)new_item(); *m_res_hook= result; result->prev_hook= m_res_hook; m_res_hook= &result->next; result->type= type; -#ifndef DBUG_OFF +#ifndef GCALC_DBUG_OFF result->point_n= n_res_points++; -#endif /*DBUG_OFF*/ -#ifndef NO_TESTING - if (result->point_n == 74) - call_checkpoint(74); -#endif /*NO_TESTING*/ - return result; +#endif /*GCALC_DBUG_OFF*/ + GCALC_DBUG_RETURN(result); } int Gcalc_operation_reducer::add_line(int incoming, active_thread *t, const Gcalc_scan_iterator::point *p) { line *l= new_line(); + GCALC_DBUG_ENTER("Gcalc_operation_reducer::add_line"); if (!l) - return 1; + GCALC_DBUG_RETURN(1); l->incoming= incoming; l->t= t; l->p= p; *m_lines_hook= l; m_lines_hook= &l->next; - return 0; + GCALC_DBUG_RETURN(0); } @@ -693,15 +691,16 @@ int Gcalc_operation_reducer::add_poly_border(int incoming, active_thread *t, int prev_state, const Gcalc_scan_iterator::point *p) { poly_border *b= new_poly_border(); + GCALC_DBUG_ENTER("Gcalc_operation_reducer::add_poly_border"); if (!b) - return 1; + GCALC_DBUG_RETURN(1); b->incoming= incoming; b->t= t; b->prev_state= prev_state; b->p= p; *m_poly_borders_hook= b; m_poly_borders_hook= &b->next; - return 0; + GCALC_DBUG_RETURN(0); } @@ -710,8 +709,9 @@ int Gcalc_operation_reducer::continue_range(active_thread *t, const Gcalc_heap::Info *p_next) { res_point *rp= add_res_point(t->rp->type); + GCALC_DBUG_ENTER("Gcalc_operation_reducer::continue_range"); if (!rp) - return 1; + GCALC_DBUG_RETURN(1); rp->glue= NULL; rp->down= t->rp; t->rp->up= rp; @@ -720,7 +720,7 @@ int Gcalc_operation_reducer::continue_range(active_thread *t, t->rp= rp; t->p1= p; t->p2= p_next; - return 0; + GCALC_DBUG_RETURN(0); } @@ -728,25 +728,27 @@ inline int Gcalc_operation_reducer::continue_i_range(active_thread *t, const Gcalc_heap::Intersection_info *ii) { res_point *rp= add_res_point(t->rp->type); + GCALC_DBUG_ENTER("Gcalc_operation_reducer::continue_i_range"); if (!rp) - return 1; + GCALC_DBUG_RETURN(1); rp->glue= NULL; rp->down= t->rp; t->rp->up= rp; rp->intersection_point= true; rp->ii= ii; t->rp= rp; - return 0; + GCALC_DBUG_RETURN(0); } int Gcalc_operation_reducer::end_couple(active_thread *t0, active_thread *t1, const Gcalc_heap::Info *p) { res_point *rp0, *rp1; + GCALC_DBUG_ENTER("Gcalc_operation_reducer::end_couple"); DBUG_ASSERT(t0->rp->type == t1->rp->type); if (!(rp0= add_res_point(t0->rp->type)) || !(rp1= add_res_point(t0->rp->type))) - return 1; + GCALC_DBUG_RETURN(1); rp0->down= t0->rp; rp1->down= t1->rp; rp1->glue= rp0; @@ -756,19 +758,13 @@ int Gcalc_operation_reducer::end_couple(active_thread *t0, active_thread *t1, t1->rp->up= rp1; rp0->intersection_point= rp1->intersection_point= false; rp0->pi= rp1->pi= p; - return 0; + GCALC_DBUG_RETURN(0); } -#ifndef NO_TESTING -int ca_counter= 0; -#endif /*NO_TESTING*/ int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si) { Gcalc_point_iterator pi(si); -#ifdef TMP_BLOCK - const Gcalc_heap::Info *event_point= NULL; -#endif /*TMP_BLOCK*/ int prev_state= 0; int sav_prev_state; active_thread *prev_range= NULL; @@ -778,17 +774,10 @@ int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si) active_thread **starting_t_hook; active_thread *bottom_threads= NULL; active_thread *eq_thread, *point_thread;; + GCALC_DBUG_ENTER("Gcalc_operation_reducer::count_slice"); -#ifndef NO_TESTING - if (ca_counter == 11522) - call_checkpoint(89); -#endif /*NO_TESTING*/ m_fn->clear_i_states(); /* Walk to the event, remembering what is needed. */ -#ifndef NO_TESTING - if (si->get_event_position() == pi.point()) - printf("yyy\n"); -#endif /*NO_TESTING*/ for (; pi.point() != si->get_event_position(); ++pi, cur_t_hook= (active_thread **) &(*cur_t_hook)->next) { @@ -813,13 +802,13 @@ int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si) { if (cur_t->enabled() && continue_range(cur_t, events->pi, events->next_pi)) - return 1; + GCALC_DBUG_RETURN(1); break; } case scev_end: { if (cur_t->enabled() && end_line(cur_t, si)) - return 1; + GCALC_DBUG_RETURN(1); *cur_t_hook= cur_t->get_next(); free_item(cur_t); break; @@ -830,13 +819,13 @@ int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si) { /* When two threads are ended here */ if (end_couple(cur_t, cur_t->get_next(), events->pi)) - return 1; + GCALC_DBUG_RETURN(1); } else if (cur_t->enabled() || cur_t->get_next()->enabled()) { /* Rare case when edges of a polygon coincide */ if (end_line(cur_t->enabled() ? cur_t : cur_t->get_next(), si)) - return 1; + GCALC_DBUG_RETURN(1); } *cur_t_hook= cur_t->get_next()->get_next(); free_item(cur_t->next); @@ -846,10 +835,7 @@ int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si) default: DBUG_ASSERT(0); } -#ifndef NO_TESTING - goto testing; -#endif /*NO_TESTING*/ - return 0; + GCALC_DBUG_RETURN(0); } starting_t_hook= cur_t_hook; @@ -860,10 +846,6 @@ int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si) { active_thread *cur_t= *cur_t_hook; -#ifdef TMP_BLOCK - if (!event_point && events->event != scev_intersection) - event_point= events->pi; -#endif /*TMP_BLOCK*/ if (events->event == scev_single_point) continue; @@ -872,7 +854,7 @@ int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si) { active_thread *new_t= new_active_thread(); if (!new_t) - return 1; + GCALC_DBUG_RETURN(1); new_t->rp= NULL; /* Insert into the main thread list before the current */ new_t->next= cur_t; @@ -904,7 +886,7 @@ int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si) { active_thread *new_t= new_active_thread(); if (!new_t) - return 1; + GCALC_DBUG_RETURN(1); new_t->rp= NULL; /* Replace the current thread with the new. */ new_t->next= cur_t->next; @@ -952,12 +934,12 @@ int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si) if (prev_state != after_state) { if (add_poly_border(0, eq_thread, prev_state, eq_start)) - return 1; + GCALC_DBUG_RETURN(1); } else if (!prev_state /* &&!after_state */ && in_state) { if (add_line(0, eq_thread, eq_start)) - return 1; + GCALC_DBUG_RETURN(1); } prev_state= after_state; @@ -978,7 +960,7 @@ int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si) for (events= si->get_events(); events; events= events->get_next()) m_fn->set_b_state(events->get_shape()); - return m_fn->count() ? add_single_point(si) : 0; + GCALC_DBUG_RETURN(m_fn->count() ? add_single_point(si) : 0); } if (m_poly_borders) @@ -988,10 +970,6 @@ int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si) { poly_border *pb1, *pb2; pb1= m_poly_borders; -#ifndef NO_TESTING - if (!m_poly_borders->next) - call_checkpoint(3); -#endif /*NO_TESTING*/ DBUG_ASSERT(m_poly_borders->next); pb2= get_pair_border(pb1); @@ -1000,7 +978,7 @@ int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si) if (connect_threads(pb1->incoming, pb2->incoming, pb1->t, pb2->t, pb1->p, pb2->p, prev_range, si, Gcalc_function::shape_polygon)) - return 1; + GCALC_DBUG_RETURN(1); free_item(pb1); free_item(pb2); @@ -1019,7 +997,7 @@ int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si) m_lines->t, m_lines->get_next()->t, m_lines->p, m_lines->get_next()->p, NULL, si, Gcalc_function::shape_line)) - return 1; + GCALC_DBUG_RETURN(1); } else { @@ -1028,7 +1006,7 @@ int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si) if (cur_line->incoming) { if (end_line(cur_line->t, si)) - return 1; + GCALC_DBUG_RETURN(1); } else start_line(cur_line->t, cur_line->p, si); @@ -1042,57 +1020,19 @@ int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si) if (bottom_threads) free_list(bottom_threads); -#ifndef NO_TESTING -testing: - { - Gcalc_point_iterator x_pi(si); - active_thread **x_cur_t_hook= &m_first_active_thread; - int x_prev_state= 0; - m_fn->save_states(); - m_fn->clear_state(); - if (ca_counter == /*11552*/90) - call_checkpoint(10); - for (; x_pi.point(); ++x_pi) - { - active_thread *cur_t= *x_cur_t_hook; - if (cur_t->enabled() && - cur_t->rp->type == Gcalc_function::shape_polygon) - x_prev_state^= 1; - int ppb= m_fn->count(); - if (m_fn->get_shape_kind(x_pi.get_shape()) == Gcalc_function::shape_polygon) - m_fn->invert_state(x_pi.get_shape()); - int ppa= m_fn->count(); - if (ppa != x_prev_state) - { - if (x_pi.point()->cmp_dx_dy(x_pi.point()->get_next()) != 0) - call_checkpoint(21); - } - if (cur_t->enabled()) - { - if (m_fn->get_shape_kind(x_pi.get_shape()) == Gcalc_function::shape_polygon) - if (ppa == ppb) - call_checkpoint(22); - else - if (ppa != 0 && ppb != 0) - call_checkpoint(23); - } - x_cur_t_hook= (active_thread **) &(*x_cur_t_hook)->next; - } - m_fn->restore_states(); - } -#endif /*NO_TESTING*/ - return 0; + GCALC_DBUG_RETURN(0); } int Gcalc_operation_reducer::add_single_point(const Gcalc_scan_iterator *si) { res_point *rp= add_res_point(Gcalc_function::shape_point); + GCALC_DBUG_ENTER("Gcalc_operation_reducer::add_single_point"); if (!rp) - return 1; + GCALC_DBUG_RETURN(1); rp->glue= rp->up= rp->down= NULL; rp->set(si); - return 0; + GCALC_DBUG_RETURN(0); } @@ -1101,6 +1041,7 @@ Gcalc_operation_reducer::poly_border { poly_border *prev_b= b1; poly_border *result= b1->get_next(); + GCALC_DBUG_ENTER("Gcalc_operation_reducer::get_pair_border"); if (b1->prev_state) { if (b1->incoming) @@ -1140,7 +1081,7 @@ Gcalc_operation_reducer::poly_border } /* Delete the result from the list. */ prev_b->next= result->next; - return result; + GCALC_DBUG_RETURN(result); } @@ -1151,13 +1092,15 @@ int Gcalc_operation_reducer::connect_threads( active_thread *prev_range, const Gcalc_scan_iterator *si, Gcalc_function::shape_type s_t) { + GCALC_DBUG_ENTER("Gcalc_operation_reducer::connect_threads"); + GCALC_DBUG_PRINT(("incoming %d %d", incoming_a, incoming_b)); if (incoming_a && incoming_b) { res_point *rpa, *rpb; DBUG_ASSERT(ta->rp->type == tb->rp->type); if (!(rpa= add_res_point(ta->rp->type)) || !(rpb= add_res_point(ta->rp->type))) - return 1; + GCALC_DBUG_RETURN(1); rpa->down= ta->rp; rpb->down= tb->rp; rpb->glue= rpa; @@ -1168,7 +1111,7 @@ int Gcalc_operation_reducer::connect_threads( rpa->set(si); rpb->set(si); ta->rp= tb->rp= NULL; - return 0; + GCALC_DBUG_RETURN(0); } if (!incoming_a) { @@ -1176,7 +1119,7 @@ int Gcalc_operation_reducer::connect_threads( res_point *rp0, *rp1; if (!(rp0= add_res_point(s_t)) || !(rp1= add_res_point(s_t))) - return 1; + GCALC_DBUG_RETURN(1); rp0->glue= rp1; rp1->glue= rp0; rp0->set(si); @@ -1204,7 +1147,7 @@ int Gcalc_operation_reducer::connect_threads( /* Chack if needed */ tb->thread_start= rp0; } - return 0; + GCALC_DBUG_RETURN(0); } /* else, if only ta is incoming */ @@ -1217,15 +1160,12 @@ int Gcalc_operation_reducer::connect_threads( if (si->intersection_step() ? continue_i_range(tb, si->get_cur_ii()) : continue_range(tb, si->get_cur_pi(), pb->next_pi)) -#ifdef TMP_BLOCK - continue_range(tb, si->get_cur_pi()) -#endif /*TMP_BLOCK*/ - return 1; + GCALC_DBUG_RETURN(1); } tb->p1= pb->pi; tb->p2= pb->next_pi; - return 0; + GCALC_DBUG_RETURN(0); } @@ -1234,51 +1174,49 @@ int Gcalc_operation_reducer::start_line(active_thread *t, const Gcalc_scan_iterator *si) { res_point *rp= add_res_point(Gcalc_function::shape_line); + GCALC_DBUG_ENTER("Gcalc_operation_reducer::start_line"); if (!rp) - return 1; + GCALC_DBUG_RETURN(1); rp->glue= rp->down= NULL; rp->set(si); t->rp= rp; t->p1= p->pi; t->p2= p->next_pi; - return 0; + GCALC_DBUG_RETURN(0); } int Gcalc_operation_reducer::end_line(active_thread *t, const Gcalc_scan_iterator *si) { + GCALC_DBUG_ENTER("Gcalc_operation_reducer::end_line"); DBUG_ASSERT(t->rp->type == Gcalc_function::shape_line); res_point *rp= add_res_point(Gcalc_function::shape_line); if (!rp) - return 1; + GCALC_DBUG_RETURN(1); rp->glue= rp->up= NULL; rp->down= t->rp; rp->set(si); t->rp->up= rp; t->rp= NULL; - return 0; + GCALC_DBUG_RETURN(0); } int Gcalc_operation_reducer::count_all(Gcalc_heap *hp) { Gcalc_scan_iterator si; + GCALC_DBUG_ENTER("Gcalc_operation_reducer::count_all"); si.init(hp); while (si.more_points()) { -#ifndef NO_TESTING - printf("Point %d\n", ++ca_counter); - if (ca_counter == 12) - call_checkpoint(10); -#endif /*NO_TESTING*/ if (si.step()) - return 1; + GCALC_DBUG_RETURN(1); if (count_slice(&si)) - return 1; + GCALC_DBUG_RETURN(1); } - return 0; + GCALC_DBUG_RETURN(0); } inline void Gcalc_operation_reducer::free_result(res_point *res) @@ -1294,23 +1232,21 @@ inline void Gcalc_operation_reducer::free_result(res_point *res) inline int Gcalc_operation_reducer::get_single_result(res_point *res, Gcalc_result_receiver *storage) { + GCALC_DBUG_ENTER("Gcalc_operation_reducer::get_single_result"); if (res->intersection_point) { double x, y; res->ii->calc_xy(&x, &y); if (storage->single_point(x,y)) - return 1; + GCALC_DBUG_RETURN(1); } else if (storage->single_point(res->pi->x, res->pi->y)) - return 1; + GCALC_DBUG_RETURN(1); free_result(res); - return 0; + GCALC_DBUG_RETURN(0); } -#ifndef NO_TESTING -int pc_counter= 0; -#endif /*NO_TESTING*/ int Gcalc_operation_reducer::get_result_thread(res_point *cur, Gcalc_result_receiver *storage, @@ -1320,13 +1256,9 @@ int Gcalc_operation_reducer::get_result_thread(res_point *cur, res_point *next; bool glue_step= false; double x, y; + GCALC_DBUG_ENTER("Gcalc_operation_reducer::get_result_thread"); while (cur) { -#ifndef NO_TESTING - ++pc_counter; - if (pc_counter == 79) - call_checkpoint(79); -#endif /*NO_TESTING*/ if (!glue_step) { if (cur->intersection_point) @@ -1339,7 +1271,7 @@ int Gcalc_operation_reducer::get_result_thread(res_point *cur, y= cur->pi->y; } if (storage->add_point(x, y)) - return 1; + GCALC_DBUG_RETURN(1); } next= move_upward ? cur->up : cur->down; @@ -1358,7 +1290,7 @@ int Gcalc_operation_reducer::get_result_thread(res_point *cur, free_result(cur); cur= next; } - return 0; + GCALC_DBUG_RETURN(0); } @@ -1366,11 +1298,12 @@ int Gcalc_operation_reducer::get_polygon_result(res_point *cur, Gcalc_result_receiver *storage, res_point *first_poly_node) { + GCALC_DBUG_ENTER("Gcalc_operation_reducer::get_polygon_result"); res_point *glue= cur->glue; glue->up->down= NULL; free_result(glue); - return get_result_thread(cur, storage, 1, first_poly_node) || - storage->complete_shape(); + GCALC_DBUG_RETURN(get_result_thread(cur, storage, 1, first_poly_node) || + storage->complete_shape()); } @@ -1380,6 +1313,7 @@ int Gcalc_operation_reducer::get_line_result(res_point *cur, res_point *next; res_point *cur_orig= cur; int move_upward= 1; + GCALC_DBUG_ENTER("Gcalc_operation_reducer::get_line_result"); if (cur->glue) { /* Here we have to find the beginning of the line */ @@ -1405,8 +1339,8 @@ int Gcalc_operation_reducer::get_line_result(res_point *cur, } } - return get_result_thread(cur, storage, move_upward, 0) || - storage->complete_shape(); + GCALC_DBUG_RETURN(get_result_thread(cur, storage, move_upward, 0) || + storage->complete_shape()); } @@ -1414,6 +1348,7 @@ int Gcalc_operation_reducer::get_result(Gcalc_result_receiver *storage) { poly_instance *polygons= NULL; + GCALC_DBUG_ENTER("Gcalc_operation_reducer::get_result"); *m_res_hook= NULL; while (m_result) @@ -1422,7 +1357,7 @@ int Gcalc_operation_reducer::get_result(Gcalc_result_receiver *storage) if (shape == Gcalc_function::shape_point) { if (get_single_result(m_result, storage)) - return 1; + GCALC_DBUG_RETURN(1); continue; } if (shape == Gcalc_function::shape_polygon) @@ -1439,7 +1374,7 @@ int Gcalc_operation_reducer::get_result(Gcalc_result_receiver *storage) m_result->outer_poly->first_poly_node) || storage->move_hole(insert_position, hole_position, &position_shift)) - return 1; + GCALC_DBUG_RETURN(1); for (cur_poly= polygons; cur_poly && *cur_poly->after_poly_position >= insert_position; cur_poly= cur_poly->get_next()) @@ -1454,7 +1389,7 @@ int Gcalc_operation_reducer::get_result(Gcalc_result_receiver *storage) polygons= p; storage->start_shape(Gcalc_function::shape_polygon); if (get_polygon_result(m_result, storage, m_result)) - return 1; + GCALC_DBUG_RETURN(1); *poly_position= storage->position(); } } @@ -1462,13 +1397,13 @@ int Gcalc_operation_reducer::get_result(Gcalc_result_receiver *storage) { storage->start_shape(shape); if (get_line_result(m_result, storage)) - return 1; + GCALC_DBUG_RETURN(1); } } m_res_hook= (Gcalc_dyn_list::Item **)&m_result; storage->done(); - return 0; + GCALC_DBUG_RETURN(0); } -- cgit v1.2.1 From 0048f0b1aefa1206c6d8f35707ded2f87bc8aec1 Mon Sep 17 00:00:00 2001 From: Alexey Botchkov Date: Wed, 5 Oct 2011 14:45:39 +0500 Subject: Valgrind warning fixed. Coordinate size limitation removed. per-file comments: mysql-test/r/gis-precise.result test result updated. sql/gcalc_slicescan.cc Check coordinate extent to pick better precidion in the ::set_double() sql/gcalc_slicescan.h free_list() can lead to valgrind warnig. Fixed sql/gcalc_tools.cc free_list() call changed. --- sql/gcalc_tools.cc | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'sql/gcalc_tools.cc') diff --git a/sql/gcalc_tools.cc b/sql/gcalc_tools.cc index 5871dce8642..56a3c5ee5f2 100644 --- a/sql/gcalc_tools.cc +++ b/sql/gcalc_tools.cc @@ -1409,7 +1409,7 @@ int Gcalc_operation_reducer::get_result(Gcalc_result_receiver *storage) void Gcalc_operation_reducer::reset() { - free_list(m_result, m_res_hook); + free_list((Gcalc_heap::Item **) &m_result, m_res_hook); m_res_hook= (Gcalc_dyn_list::Item **)&m_result; free_list(m_first_active_thread); } -- cgit v1.2.1 From bf2deb5ed30b03e9cada6162d8aa837115dce4cc Mon Sep 17 00:00:00 2001 From: Alexey Botchkov Date: Thu, 6 Oct 2011 17:41:28 +0500 Subject: Copyright notices fixed. --- sql/gcalc_tools.cc | 1 + 1 file changed, 1 insertion(+) (limited to 'sql/gcalc_tools.cc') diff --git a/sql/gcalc_tools.cc b/sql/gcalc_tools.cc index 56a3c5ee5f2..eabc42a6c51 100644 --- a/sql/gcalc_tools.cc +++ b/sql/gcalc_tools.cc @@ -1,4 +1,5 @@ /* Copyright (c) 2000, 2010 Oracle and/or its affiliates. All rights reserved. + Copyright (C) 2011 Monty Program Ab. This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by -- cgit v1.2.1 From 8432284d4fe276db8fe99f434b98e3631e707146 Mon Sep 17 00:00:00 2001 From: Alexey Botchkov Date: Fri, 14 Oct 2011 16:10:55 +0500 Subject: GIS code. Forward calculations introduced. per-file comments: sql/gcalc_slicescan.cc sql/gcalc_slicescan.h sql/gcalc_tools.cc sql/gcalc_tools.h sql/item_geofunc.cc --- sql/gcalc_tools.cc | 48 ++++++++++++++++++++++++++++-------------------- 1 file changed, 28 insertions(+), 20 deletions(-) (limited to 'sql/gcalc_tools.cc') diff --git a/sql/gcalc_tools.cc b/sql/gcalc_tools.cc index eabc42a6c51..f6203ba552f 100644 --- a/sql/gcalc_tools.cc +++ b/sql/gcalc_tools.cc @@ -192,7 +192,7 @@ int Gcalc_function::count_internal(const char *cur_func, uint set_type, result= result & !next_res; break; default: - DBUG_ASSERT(FALSE); + GCALC_DBUG_ASSERT(FALSE); }; } @@ -262,7 +262,8 @@ void Gcalc_function::reset() int Gcalc_function::check_function(Gcalc_scan_iterator &scan_it) { - const Gcalc_scan_iterator::point *eq_start, *cur_eq, *events; + const Gcalc_scan_iterator::point *eq_start, *cur_eq; + const Gcalc_scan_iterator::event_point *events; GCALC_DBUG_ENTER("Gcalc_function::check_function"); while (scan_it.more_points()) @@ -502,7 +503,7 @@ int Gcalc_result_receiver::complete_shape() } else { - DBUG_ASSERT(cur_shape != Gcalc_function::shape_point); + GCALC_DBUG_ASSERT(cur_shape != Gcalc_function::shape_point); if (cur_shape == Gcalc_function::shape_hole) { shape_area+= prev_x*first_y - prev_y*first_x; @@ -534,7 +535,7 @@ do_complete: if (!n_shapes++) { - DBUG_ASSERT(cur_shape != Gcalc_function::shape_hole); + GCALC_DBUG_ASSERT(cur_shape != Gcalc_function::shape_hole); common_shapetype= cur_shape; } else if (cur_shape == Gcalc_function::shape_hole) @@ -587,7 +588,7 @@ int Gcalc_result_receiver::get_result_typeid() return (n_shapes == 1) ? Geometry::wkb_linestring : Geometry::wkb_multilinestring; default: - DBUG_ASSERT(0); + GCALC_DBUG_ASSERT(0); } return 0; } @@ -648,6 +649,7 @@ Gcalc_operation_reducer(Gcalc_function *fn, modes mode, size_t blk_size) : } +#ifdef TMP_BLOCK void Gcalc_operation_reducer::res_point::set(const Gcalc_scan_iterator *si) { if ((intersection_point= si->intersection_step())) @@ -655,6 +657,12 @@ void Gcalc_operation_reducer::res_point::set(const Gcalc_scan_iterator *si) else pi= si->get_cur_pi(); } +#endif /*TMP_BLOCK*/ +void Gcalc_operation_reducer::res_point::set(const Gcalc_scan_iterator *si) +{ + intersection_point= si->intersection_step(); + pi= si->get_cur_pi(); +} Gcalc_operation_reducer::res_point * @@ -726,7 +734,7 @@ int Gcalc_operation_reducer::continue_range(active_thread *t, inline int Gcalc_operation_reducer::continue_i_range(active_thread *t, - const Gcalc_heap::Intersection_info *ii) + const Gcalc_heap::Info *ii) { res_point *rp= add_res_point(t->rp->type); GCALC_DBUG_ENTER("Gcalc_operation_reducer::continue_i_range"); @@ -736,7 +744,7 @@ inline int Gcalc_operation_reducer::continue_i_range(active_thread *t, rp->down= t->rp; t->rp->up= rp; rp->intersection_point= true; - rp->ii= ii; + rp->pi= ii; t->rp= rp; GCALC_DBUG_RETURN(0); } @@ -746,7 +754,7 @@ int Gcalc_operation_reducer::end_couple(active_thread *t0, active_thread *t1, { res_point *rp0, *rp1; GCALC_DBUG_ENTER("Gcalc_operation_reducer::end_couple"); - DBUG_ASSERT(t0->rp->type == t1->rp->type); + GCALC_DBUG_ASSERT(t0->rp->type == t1->rp->type); if (!(rp0= add_res_point(t0->rp->type)) || !(rp1= add_res_point(t0->rp->type))) GCALC_DBUG_RETURN(1); @@ -769,7 +777,7 @@ int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si) int prev_state= 0; int sav_prev_state; active_thread *prev_range= NULL; - const Gcalc_scan_iterator::point *events; + const Gcalc_scan_iterator::event_point *events; const Gcalc_scan_iterator::point *eq_start; active_thread **cur_t_hook= &m_first_active_thread; active_thread **starting_t_hook; @@ -834,7 +842,7 @@ int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si) break; } default: - DBUG_ASSERT(0); + GCALC_DBUG_ASSERT(0); } GCALC_DBUG_RETURN(0); } @@ -875,7 +883,7 @@ int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si) { if (cur_t->rp->type == Gcalc_function::shape_line) { - DBUG_ASSERT(!prev_state); + GCALC_DBUG_ASSERT(!prev_state); add_line(1, cur_t, events); } else @@ -971,7 +979,7 @@ int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si) { poly_border *pb1, *pb2; pb1= m_poly_borders; - DBUG_ASSERT(m_poly_borders->next); + GCALC_DBUG_ASSERT(m_poly_borders->next); pb2= get_pair_border(pb1); /* Remove pb1 from the list. The pb2 already removed in get_pair_border. */ @@ -1098,7 +1106,7 @@ int Gcalc_operation_reducer::connect_threads( if (incoming_a && incoming_b) { res_point *rpa, *rpb; - DBUG_ASSERT(ta->rp->type == tb->rp->type); + GCALC_DBUG_ASSERT(ta->rp->type == tb->rp->type); if (!(rpa= add_res_point(ta->rp->type)) || !(rpb= add_res_point(ta->rp->type))) GCALC_DBUG_RETURN(1); @@ -1116,7 +1124,7 @@ int Gcalc_operation_reducer::connect_threads( } if (!incoming_a) { - DBUG_ASSERT(!incoming_b); + GCALC_DBUG_ASSERT(!incoming_b); res_point *rp0, *rp1; if (!(rp0= add_res_point(s_t)) || !(rp1= add_res_point(s_t))) @@ -1152,14 +1160,14 @@ int Gcalc_operation_reducer::connect_threads( } /* else, if only ta is incoming */ - DBUG_ASSERT(tb != ta); + GCALC_DBUG_ASSERT(tb != ta); tb->rp= ta->rp; tb->thread_start= ta->thread_start; if (Gcalc_scan_iterator::point:: cmp_dx_dy(ta->p1, ta->p2, pb->pi, pb->next_pi) != 0) { if (si->intersection_step() ? - continue_i_range(tb, si->get_cur_ii()) : + continue_i_range(tb, si->get_cur_pi()) : continue_range(tb, si->get_cur_pi(), pb->next_pi)) GCALC_DBUG_RETURN(1); } @@ -1191,7 +1199,7 @@ int Gcalc_operation_reducer::end_line(active_thread *t, const Gcalc_scan_iterator *si) { GCALC_DBUG_ENTER("Gcalc_operation_reducer::end_line"); - DBUG_ASSERT(t->rp->type == Gcalc_function::shape_line); + GCALC_DBUG_ASSERT(t->rp->type == Gcalc_function::shape_line); res_point *rp= add_res_point(Gcalc_function::shape_line); if (!rp) GCALC_DBUG_RETURN(1); @@ -1237,7 +1245,7 @@ inline int Gcalc_operation_reducer::get_single_result(res_point *res, if (res->intersection_point) { double x, y; - res->ii->calc_xy(&x, &y); + res->pi->calc_xy(&x, &y); if (storage->single_point(x,y)) GCALC_DBUG_RETURN(1); } @@ -1264,7 +1272,7 @@ int Gcalc_operation_reducer::get_result_thread(res_point *cur, { if (cur->intersection_point) { - cur->ii->calc_xy(&x, &y); + cur->pi->calc_xy(&x, &y); } else { @@ -1368,7 +1376,7 @@ int Gcalc_operation_reducer::get_result(Gcalc_result_receiver *storage) uint32 insert_position, hole_position, position_shift; poly_instance *cur_poly; insert_position= m_result->outer_poly->first_poly_node->poly_position; - DBUG_ASSERT(insert_position); + GCALC_DBUG_ASSERT(insert_position); hole_position= storage->position(); storage->start_shape(Gcalc_function::shape_hole); if (get_polygon_result(m_result, storage, -- cgit v1.2.1 From 9cde33f9ef139f7511db66393694bbc3af6a863f Mon Sep 17 00:00:00 2001 From: Alexey Botchkov Date: Thu, 17 Nov 2011 18:03:47 +0400 Subject: small fixes to make compiler happy. --- sql/gcalc_tools.cc | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'sql/gcalc_tools.cc') diff --git a/sql/gcalc_tools.cc b/sql/gcalc_tools.cc index f6203ba552f..b4b01767f5f 100644 --- a/sql/gcalc_tools.cc +++ b/sql/gcalc_tools.cc @@ -133,7 +133,7 @@ int Gcalc_function::count_internal(const char *cur_func, uint set_type, uint n_ops= c_op & ~(op_any | op_not | v_mask); uint n_shape= c_op & ~(op_any | op_not | v_mask); /* same as n_ops */ value v_state= (value) (c_op & v_mask); - int result; + int result= 0; const char *sav_cur_func= cur_func; // GCALC_DBUG_ENTER("Gcalc_function::count_internal"); -- cgit v1.2.1 From 5a4c91003a73c551d89e0c6878edfe03704352fe Mon Sep 17 00:00:00 2001 From: Alexey Botchkov Date: Sun, 20 Nov 2011 12:30:43 +0400 Subject: Fix for bug #809849 spatial operations must be KILL-able. Checks for thd->killed state added to the long loops in geometry calculations. per-file comments: sql/gcalc_slicescan.cc Fix for bug #809849 spatial operations must be KILL-able. checks for TERMINATED_STATE added. sql/gcalc_slicescan.h Fix for bug #809849 spatial operations must be KILL-able. defines added to include checks for termination in the library. sql/gcalc_tools.cc Fix for bug #809849 spatial operations must be KILL-able. checks for TERMINATED_STATE added. sql/gcalc_tools.h Fix for bug #809849 spatial operations must be KILL-able. TERMINATED_STATE pointers added. sql/item_geofunc.cc Fix for bug #809849 spatial operations must be KILL-able. sql/item_geofunc.h Fix for bug #809849 spatial operations must be KILL-able. --- sql/gcalc_tools.cc | 2 ++ 1 file changed, 2 insertions(+) (limited to 'sql/gcalc_tools.cc') diff --git a/sql/gcalc_tools.cc b/sql/gcalc_tools.cc index b4b01767f5f..161fa385f16 100644 --- a/sql/gcalc_tools.cc +++ b/sql/gcalc_tools.cc @@ -637,6 +637,7 @@ void Gcalc_operation_reducer::init(Gcalc_function *fn, modes mode) m_lines_hook= (Gcalc_dyn_list::Item **) &m_lines; m_poly_borders= NULL; m_poly_borders_hook= (Gcalc_dyn_list::Item **) &m_poly_borders; + GCALC_SET_TERMINATED(killed, 0); } @@ -1218,6 +1219,7 @@ int Gcalc_operation_reducer::count_all(Gcalc_heap *hp) Gcalc_scan_iterator si; GCALC_DBUG_ENTER("Gcalc_operation_reducer::count_all"); si.init(hp); + GCALC_SET_TERMINATED(si.killed, killed); while (si.more_points()) { if (si.step()) -- cgit v1.2.1