/* Copyright (c) 2000, 2015, 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., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */ #include "my_global.h" #ifdef HAVE_SPATIAL #include "sql_string.h" #include "gcalc_tools.h" #include "gstream.h" // Gis_read_stream #include "spatial.h" #include "sql_class.h" // THD #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); } void Gcalc_function::set_operands_to_op(uint32 operation_pos, uint32 n_operands) { uint32 op_code= (uint4korr(function_buffer.ptr() + operation_pos) & op_any) + 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 * shape_buffer_item_size, 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 * function_buffer_item_size, 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; } #ifndef DBUG_OFF /** Return spatial operation name from its numeric code. */ const char *Gcalc_function::op_name(int code) { enum op_type type= (enum op_type) code; switch (type) { case op_shape: return "op_shape"; case op_not: return "op_not"; case op_union: return "op_union"; case op_intersection: return "op_intersection"; case op_symdifference: return "op_symdifference"; case op_difference: return "op_difference"; case op_backdifference: return "op_backdifference"; case op_any: return "op_any"; } return "op_unknown"; } const char *Gcalc_function::shape_name(int code) { switch (code) { case shape_point: return "shape_point"; case shape_line: return "shape_line"; case shape_polygon: return "shape_polygon"; case shape_hole: return "shape_hole"; } return "shape_unknown"; } /** Trace spatial operation buffer into debug log and optionally into client side warnings. */ void Gcalc_function::debug_print_function_buffer() { int i, nelements= function_buffer.length() / function_buffer_item_size; THD *thd= current_thd; DBUG_PRINT("info", ("nelements=%d", nelements)); for (i= 0; i < nelements; i++) { int c_op= uint4korr(function_buffer.ptr() + function_buffer_item_size * i); int func= (c_op & op_any); int mask= (c_op & op_not) ? 1 : 0; int n_ops= c_op & ~op_any; const char *c_op_name= op_name(func); const char *s_name= (func == op_shape) ? shape_name(uint4korr(shapes_buffer.ptr() + shape_buffer_item_size * n_ops)) : ""; DBUG_PRINT("info", ("[%d]=%d c_op=%d (%s) mask=%d n_ops=%d", i, c_op, func, c_op_name, mask, n_ops)); if (thd->get_gis_debug()) push_warning_printf(thd, Sql_condition::WARN_LEVEL_WARN, ER_UNKNOWN_ERROR, "[%d] %s[%d]%s", i, c_op_name, n_ops, s_name); } } #endif 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+= function_buffer_item_size; 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(Gcalc_shape_status *st, double x, double y) { DBUG_PRINT("info", ("Gcalc_operation_transporter::single_point: %g %g", x, 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(Gcalc_shape_status *st) { DBUG_PRINT("info", ("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(Gcalc_shape_status *st) { DBUG_PRINT("info", ("Gcalc_operation_transporter::complete_line")); int_complete_line(); return 0; } int Gcalc_operation_transporter::start_poly(Gcalc_shape_status *st) { DBUG_PRINT("info", ("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(Gcalc_shape_status *st) { DBUG_PRINT("info", ("Gcalc_operation_transporter::complete_poly")); int_complete_poly(); return 0; } int Gcalc_operation_transporter::start_ring(Gcalc_shape_status *st) { DBUG_PRINT("info", ("Gcalc_operation_transporter::start_ring")); int_start_ring(); return 0; } int Gcalc_operation_transporter::complete_ring(Gcalc_shape_status *st) { DBUG_PRINT("info", ("Gcalc_operation_transporter::complete_ring")); int_complete_ring(); return 0; } int Gcalc_operation_transporter::add_point(Gcalc_shape_status *st, double x, double y) { DBUG_PRINT("info", ("Gcalc_operation_transporter::add_point %g %g", x, y)); return int_add_point(m_si, x, y); } int Gcalc_operation_transporter::start_collection(Gcalc_shape_status *st, int n_objects) { DBUG_PRINT("info", ("Gcalc_operation_transporter::start_collection")); 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_operation_transporter::complete_collection(Gcalc_shape_status *st) { DBUG_PRINT("info", ("Gcalc_operation_transporter::complete_collection")); return 0; } int Gcalc_operation_transporter::collection_add_item(Gcalc_shape_status *st_collection, Gcalc_shape_status *st_item) { DBUG_PRINT("info", ("Gcalc_operation_transporter::collection_add_item")); return 0; } int Gcalc_result_receiver::start_shape(Gcalc_function::shape_type shape) { DBUG_ENTER("Gcalc_result_receiver::start_shape"); DBUG_PRINT("info", ("%s", Gcalc_function::shape_name(shape))); if (buffer.reserve(4*2, 512)) 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; DBUG_RETURN(0); } int Gcalc_result_receiver::add_point(double x, double y) { DBUG_ENTER("Gcalc_result_receiver::add_point"); DBUG_PRINT("info", ("xy=(%g,%g)", x, y)); if (n_points && x == prev_x && y == prev_y) DBUG_RETURN(0); if (!n_points++) { prev_x= first_x= x; prev_y= first_y= y; DBUG_RETURN(0); } shape_area+= prev_x*y - prev_y*x; if (buffer.reserve(8*2, 512)) DBUG_RETURN(1); buffer.q_append(prev_x); buffer.q_append(prev_y); prev_x= x; prev_y= y; DBUG_RETURN(0); } int Gcalc_result_receiver::complete_shape() { DBUG_ENTER("Gcalc_result_receiver::complete_shape"); DBUG_PRINT("info", ("n_points=%u", (uint) n_points)); if (n_points == 0) { buffer.length(shape_pos); DBUG_RETURN(0); } if (n_points == 1) { if (cur_shape == Gcalc_function::shape_hole || cur_shape == Gcalc_function::shape_polygon) { /* All points of a hole (or a polygon) have the same coordinates - remove the shape. */ buffer.length(shape_pos); DBUG_RETURN(0); } 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 || cur_shape == Gcalc_function::shape_polygon) { shape_area+= prev_x*first_y - prev_y*first_x; /* Remove a hole (or a polygon) if its area == 0. */ if (fabs(shape_area) < 1e-8) { buffer.length(shape_pos); DBUG_RETURN(0); } if (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)) DBUG_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; } DBUG_PRINT("info", ("n_shapes=%u cur_shape=%s common_shapetype=%s", (uint) n_shapes, Gcalc_function::shape_name(cur_shape), Gcalc_function::shape_name(common_shapetype))); DBUG_RETURN(0); } int Gcalc_result_receiver::single_point(double x, double y) { DBUG_PRINT("info", ("single_point xy=(%g,%g)", x, y)); return start_shape(Gcalc_function::shape_point) || add_point(x, y) || complete_shape(); } int Gcalc_result_receiver::done() { DBUG_ENTER("Gcalc_result_receiver::done"); DBUG_RETURN(0); } void Gcalc_result_receiver::reset() { DBUG_ENTER("Gcalc_result_receiver::reset"); buffer.length(0); collection_result= FALSE; n_shapes= n_holes= 0; DBUG_VOID_RETURN; } int Gcalc_result_receiver::get_result_typeid() { DBUG_ENTER("Gcalc_result_receiver::get_result_typeid"); if (!n_shapes) DBUG_RETURN(0); if (collection_result) DBUG_RETURN(Geometry::wkb_geometrycollection); switch (common_shapetype) { case Gcalc_function::shape_polygon: DBUG_RETURN((n_shapes - n_holes == 1) ? Geometry::wkb_polygon : Geometry::wkb_multipolygon); case Gcalc_function::shape_point: DBUG_RETURN((n_shapes == 1) ? Geometry::wkb_point : Geometry::wkb_multipoint); case Gcalc_function::shape_line: DBUG_RETURN((n_shapes == 1) ? Geometry::wkb_linestring : Geometry::wkb_multilinestring); default: DBUG_ASSERT(0); } DBUG_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) { // We use sizeof(res_point) in constructor, the other items must be smaller DBUG_ASSERT(sizeof(res_point) >= sizeof(active_thread)); } void Gcalc_operation_reducer::init(Gcalc_function *fn, modes mode) { DBUG_ENTER("Gcalc_result_receiver::init"); m_fn= fn; m_mode= mode; m_first_active_thread= NULL; DBUG_VOID_RETURN; } 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) { DBUG_ENTER("Gcalc_operation_reducer::Gcalc_operation_reducer"); init(fn, mode); DBUG_VOID_RETURN; } inline int Gcalc_operation_reducer::continue_range(active_thread *t, const Gcalc_heap::Info *p) { DBUG_ENTER("Gcalc_operation_reducer::continue_range"); DBUG_ASSERT(t->result_range); res_point *rp= add_res_point(p); if (!rp) DBUG_RETURN(1); rp->glue= NULL; rp->down= t->rp; t->rp->up= rp; t->rp= rp; DBUG_RETURN(0); } inline int Gcalc_operation_reducer::continue_i_range(active_thread *t, const Gcalc_heap::Info *p, double x, double y) { DBUG_ENTER("Gcalc_operation_reducer::continue_i_range"); DBUG_ASSERT(t->result_range); res_point *rp= add_res_i_point(p, x, y); if (!rp) DBUG_RETURN(1); rp->glue= NULL; rp->down= t->rp; t->rp->up= rp; t->rp= rp; DBUG_RETURN(0); } inline int Gcalc_operation_reducer::start_range(active_thread *t, const Gcalc_heap::Info *p) { DBUG_ENTER("Gcalc_operation_reducer::start_range"); res_point *rp= add_res_point(p); if (!rp) DBUG_RETURN(1); rp->glue= rp->down= NULL; t->result_range= 1; t->rp= rp; DBUG_RETURN(0); } inline int Gcalc_operation_reducer::start_i_range(active_thread *t, const Gcalc_heap::Info *p, double x, double y) { DBUG_ENTER("Gcalc_operation_reducer::start_i_range"); res_point *rp= add_res_i_point(p, x, y); if (!rp) DBUG_RETURN(1); rp->glue= rp->down= NULL; t->result_range= 1; t->rp= rp; DBUG_RETURN(0); } inline int Gcalc_operation_reducer::end_range(active_thread *t, const Gcalc_heap::Info *p) { DBUG_ENTER("Gcalc_operation_reducer::end_range"); res_point *rp= add_res_point(p); if (!rp) DBUG_RETURN(1); rp->glue= rp->up= NULL; rp->down= t->rp; t->rp->up= rp; t->result_range= 0; DBUG_RETURN(0); } inline int Gcalc_operation_reducer::end_i_range(active_thread *t, const Gcalc_heap::Info *p, double x, double y) { DBUG_ENTER("Gcalc_operation_reducer::end_i_range"); res_point *rp= add_res_i_point(p, x, y); if (!rp) DBUG_RETURN(1); rp->glue= rp->up= NULL; rp->down= t->rp; t->rp->up= rp; t->result_range= 0; DBUG_RETURN(0); } int Gcalc_operation_reducer::start_couple(active_thread *t0, active_thread *t1, const Gcalc_heap::Info *p, const active_thread *prev_range) { DBUG_ENTER("Gcalc_operation_reducer::start_couple"); res_point *rp0, *rp1; if (!(rp0= add_res_point(p)) || !(rp1= add_res_point(p))) DBUG_RETURN(1); rp0->glue= rp1; rp1->glue= rp0; rp0->down= rp1->down= NULL; t0->rp= rp0; t1->rp= rp1; if (prev_range) { rp0->set_outer_poly(prev_range->thread_start()); t1->set_thread_start(prev_range->thread_start()); } else { rp0->set_outer_poly(NULL); t0->set_thread_start(rp0); } DBUG_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) { DBUG_ENTER("Gcalc_operation_reducer::start_i_couple"); res_point *rp0, *rp1; if (!(rp0= add_res_i_point(p0, x, y)) || !(rp1= add_res_i_point(p1, x, y))) DBUG_RETURN(1); rp0->glue= rp1; rp1->glue= rp0; rp0->down= rp1->down= NULL; t0->result_range= t1->result_range= 1; t0->rp= rp0; t1->rp= rp1; if (prev_range) { rp0->set_outer_poly(prev_range->thread_start()); t1->set_thread_start(prev_range->thread_start()); } else { rp0->set_outer_poly(NULL); t0->set_thread_start(rp0); } DBUG_RETURN(0); } int Gcalc_operation_reducer::end_couple(active_thread *t0, active_thread *t1, const Gcalc_heap::Info *p) { DBUG_ENTER("Gcalc_operation_reducer::end_couple"); res_point *rp0, *rp1; DBUG_ASSERT(t1->result_range); if (!(rp0= add_res_point(p)) || !(rp1= add_res_point(p))) DBUG_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; t0->result_range= t1->result_range= 0; DBUG_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) { DBUG_ENTER("Gcalc_operation_reducer::end_i_couple"); res_point *rp0, *rp1; if (!(rp0= add_res_i_point(p0, x, y)) || !(rp1= add_res_i_point(p1, x, y))) DBUG_RETURN(1); rp0->down= t0->rp; rp1->down= t1->rp; rp1->glue= rp0; rp0->glue= rp1; rp0->up= rp1->up= NULL; t0->result_range= t1->result_range= 0; t0->rp->up= rp0; t1->rp->up= rp1; DBUG_RETURN(0); } int Gcalc_operation_reducer::add_single_point(const Gcalc_heap::Info *p) { DBUG_ENTER("Gcalc_operation_reducer::add_single_point"); res_point *rp= add_res_single_point(p); if (!rp) DBUG_RETURN(1); rp->glue= rp->up= rp->down= NULL; DBUG_RETURN(0); } int Gcalc_operation_reducer::add_i_single_point(const Gcalc_heap::Info *p, double x, double y) { DBUG_ENTER("Gcalc_operation_reducer::add_i_single_point"); res_point *rp= add_res_i_point(p, x, y); if (!rp) DBUG_RETURN(1); rp->glue= rp->up= rp->down= NULL; DBUG_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) { DBUG_ENTER("Gcalc_operation_reducer::handle_lines_intersection"); DBUG_PRINT("info", ("p=(%g,%g,#%u) p1=(%g,%g,#%u) xy=(%g,%g)", p0->x, p0->y, p0->shape, p1->x, p1->y, p1->shape, x, 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) DBUG_RETURN(0); if (t0->result_range && (end_i_range(t0, p1, x, y) || start_i_range(t0, p1, x, y))) DBUG_RETURN(1); if (t1->result_range && (end_i_range(t1, p0, x, y) || start_i_range(t1, p0, x, y))) DBUG_RETURN(1); if (intersection_state && add_i_single_point(p0, x, y)) DBUG_RETURN(1); DBUG_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) { DBUG_ENTER("Gcalc_operation_reducer::handle_line_polygon_intersection"); DBUG_PRINT("info", ("p=(%g,%g,#%u) xy=(%g,%g)", pl->x, pl->y, pl->shape, x, y)); int range_after= ~poly_state & line_state; if (l->result_range == range_after) DBUG_RETURN(0); DBUG_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) { DBUG_ENTER("Gcalc_operation_reducer::handle_polygons_intersection"); DBUG_PRINT("info", ("p0=(%g,%g,#%u) p1=(%g,%g,#%u) xy=(%g,%g)", p0->x, p0->y, p0->shape, p1->x, p1->y, p1->shape, x, y)); 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); DBUG_RETURN(0); } DBUG_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); DBUG_RETURN(0); } if (prev_state != (m_mode & prefer_big_with_holes)) DBUG_RETURN(continue_i_range(t0, p0, x, y) || continue_i_range(t1, p1, x, y)); DBUG_RETURN(end_i_couple(t0, t1, p0, p1, x, y) || start_i_couple(t0, t1, p0, p1, x, y, prev_range)); } else DBUG_RETURN(end_i_couple(t0, t1, p0, p1, x, y)); } if (state_01 ^ state_11) { switch_athreads(t0, t1, t_hook); DBUG_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; } DBUG_RETURN(continue_i_range(thread_to_continue, way_to_go, x, y)); } int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si) { DBUG_ENTER("Gcalc_operation_reducer::count_slice"); 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: { DBUG_PRINT("Gcalc_operation_reducer", ("event=scev_point")); if (cur_t->result_range && continue_range(cur_t, pi.get_pi())) DBUG_RETURN(1); break; } case scev_end: { DBUG_PRINT("Gcalc_operation_reducer", ("event=scev_end")); if (cur_t->result_range && end_range(cur_t, pi.get_pi())) DBUG_RETURN(1); *at_hook= cur_t->next; free_item(cur_t); break; } case scev_two_ends: { DBUG_PRINT("Gcalc_operation_reducer", ("event=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())) DBUG_RETURN(1); *at_hook= cur_t1->next; free_list(cur_t, &cur_t1->next); break; } default: DBUG_ASSERT(0); } DBUG_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: { DBUG_PRINT("info", ("event=scev_thread")); active_thread *new_t= new_active_thread(); if (!new_t) DBUG_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())) DBUG_RETURN(1); break; } case scev_two_threads: { DBUG_PRINT("info", ("event=scev_two_threads")); active_thread *new_t0, *new_t1; int fn_result; if (!(new_t0= new_active_thread()) || !(new_t1= new_active_thread())) DBUG_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)) DBUG_RETURN(1); break; } case scev_intersection: { DBUG_PRINT("info", ("event=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)) DBUG_RETURN(1); } else if (line0 && line1) { if (!prev_state && handle_lines_intersection(cur_t, cur_t1, p0, p1, pi.get_x(), si->get_y())) DBUG_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())) DBUG_RETURN(1); switch_athreads(cur_t, cur_t1, at_hook); } break; } case scev_single_point: { DBUG_PRINT("info", ("event=scev_single_point")); m_fn->invert_state(pi.get_shape()); if ((prev_state ^ m_fn->count()) && add_single_point(pi.get_pi())) DBUG_RETURN(1); break; } default: DBUG_ASSERT(0); } DBUG_RETURN(0); } int Gcalc_operation_reducer::count_all(Gcalc_heap *hp) { DBUG_ENTER("Gcalc_operation_reducer::count_all"); Gcalc_scan_iterator si; si.init(hp); while (si.more_points()) { if (si.step()) DBUG_RETURN(1); if (count_slice(&si)) DBUG_RETURN(1); } DBUG_RETURN(0); } inline void Gcalc_operation_reducer::free_result(res_point *res) { DBUG_ENTER("Gcalc_result_receiver::free_result"); if ((*res->prev_hook= res->next)) { res->get_next()->prev_hook= res->prev_hook; } free_item(res); DBUG_VOID_RETURN; } inline int Gcalc_operation_reducer::get_single_result(res_point *res, Gcalc_result_receiver *storage) { DBUG_ENTER("Gcalc_operation_reducer::get_single_result"); if (res->intersection_point) { if (storage->single_point(float_to_coord(res->x), float_to_coord(res->y))) DBUG_RETURN(1); } else if (storage->single_point(res->x, res->y)) DBUG_RETURN(1); free_result(res); DBUG_RETURN(0); } int Gcalc_operation_reducer::get_result_thread(res_point *cur, Gcalc_result_receiver *storage, int move_upward) { DBUG_ENTER("Gcalc_operation_reducer::get_result_thread"); 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)) DBUG_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; } DBUG_RETURN(0); } int Gcalc_operation_reducer::get_polygon_result(res_point *cur, Gcalc_result_receiver *storage) { DBUG_ENTER("Gcalc_operation_reducer::get_polygon_result"); res_point *glue= cur->glue; glue->up->down= NULL; free_result(glue); DBUG_RETURN(get_result_thread(cur, storage, 1) || storage->complete_shape()); } int Gcalc_operation_reducer::get_line_result(res_point *cur, Gcalc_result_receiver *storage) { DBUG_ENTER("Gcalc_operation_reducer::get_line_result"); 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; } } } DBUG_RETURN(get_result_thread(cur, storage, move_upward) || storage->complete_shape()); } static int chunk_info_cmp(const Gcalc_result_receiver::chunk_info *a1, const Gcalc_result_receiver::chunk_info *a2) { if (a1->first_point != a2->first_point) return a1->first_point < a2->first_point ? -1 : 1; if (a1->is_poly_hole != a2->is_poly_hole) return a1->is_poly_hole < a2->is_poly_hole ? -1 : 1; return (int) a1->order - (int) a2->order; } #ifndef DBUG_OFF void Gcalc_result_receiver::chunk_info::dbug_print() const { DBUG_PRINT("info", ("first_point=%p order=%d position=%d length=%d", first_point, (int) order, (int) position, (int) length)); } #endif /** Rearrange the result shape chunks according to the required order. */ int Gcalc_result_receiver::reorder_chunks(chunk_info *chunks, int nchunks) { DBUG_ENTER("Gcalc_result_receiver::sort_polygon_rings"); String tmp; uint32 reserve_length= buffer.length(); if (tmp.reserve(reserve_length, MY_ALIGN(reserve_length, 512))) DBUG_RETURN(1); // Put shape data in the required order for (chunk_info *chunk= chunks, *end= chunks + nchunks; chunk < end; chunk++) { #ifndef DBUG_OFF chunk->dbug_print(); #endif tmp.append(buffer.ptr() + chunk->position, (size_t) chunk->length); } // Make sure all chunks were put DBUG_ASSERT(tmp.length() == buffer.length()); // Get all data from tmp and unlink tmp from its buffer. buffer.takeover(tmp); DBUG_RETURN(0); } int Gcalc_operation_reducer::get_result(Gcalc_result_receiver *storage) { DBUG_ENTER("Gcalc_operation_reducer::get_result"); Dynamic_array<:chunk_info> chunks; bool polygons_found= false; *m_res_hook= NULL; while (m_result) { Gcalc_function::shape_type shape; Gcalc_result_receiver::chunk_info chunk; chunk.first_point= m_result; chunk.order= chunks.elements(); chunk.position= storage->position(); chunk.is_poly_hole= false; if (!m_result->up) { if (get_single_result(m_result, storage)) DBUG_RETURN(1); goto end_shape; } shape= m_fn->get_shape_kind(m_result->pi->shape); if (shape == Gcalc_function::shape_polygon) { polygons_found= true; if (m_result->get_outer_poly()) // Inner ring (hole) { chunk.first_point= m_result->get_outer_poly(); chunk.is_poly_hole= true; shape= Gcalc_function::shape_hole; } storage->start_shape(shape); if (get_polygon_result(m_result, storage)) DBUG_RETURN(1); chunk.first_point= ((res_point*) chunk.first_point)->first_poly_node; } else { storage->start_shape(shape); if (get_line_result(m_result, storage)) DBUG_RETURN(1); } end_shape: chunk.length= storage->position() - chunk.position; chunks.append(chunk); } /* In case if some polygons where found, we need to reorder polygon rings in the output buffer to make all hole rings go after their outer rings. */ if (polygons_found && chunks.elements() > 1) { chunks.sort(chunk_info_cmp); if (storage->reorder_chunks(chunks.front(), chunks.elements())) DBUG_RETURN(1); } m_res_hook= (Gcalc_dyn_list::Item **)&m_result; storage->done(); DBUG_RETURN(0); } void Gcalc_operation_reducer::reset() { DBUG_ENTER("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); DBUG_VOID_RETURN; } #endif /*HAVE_SPATIAL*/