diff options
Diffstat (limited to 'sql/gcalc_tools.cc')
| -rw-r--r-- | sql/gcalc_tools.cc | 1471 |
1 files changed, 1471 insertions, 0 deletions
diff --git a/sql/gcalc_tools.cc b/sql/gcalc_tools.cc new file mode 100644 index 00000000..25c80a7a --- /dev/null +++ b/sql/gcalc_tools.cc @@ -0,0 +1,1471 @@ +/* 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 + 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 Street, Fifth Floor, Boston, MA 02110-1335 USA */ + + +#include "mariadb.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(uint 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; +} + + +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. +*/ + +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) * 2 * sizeof(int))) + return 1; + i_states= (int *) (function_buffer.ptr() + ALIGN_SIZE(function_buffer.length())); + b_states= i_states + (n_shapes + 1); + return 0; +} + + +int Gcalc_function::count_internal(const char *cur_func, uint set_type, + const char **end) +{ + uint c_op= uint4korr(cur_func); + op_type next_func= (op_type) (c_op & op_any); + int mask= (c_op & op_not) ? 1:0; + 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 */ + op_type v_state= (op_type) (c_op & v_mask); + int result= 0; + const char *sav_cur_func= cur_func; + + // GCALC_DBUG_ENTER("Gcalc_function::count_internal"); + + cur_func+= 4; + if (next_func == op_shape) + { + if (set_type == 0) + result= i_states[n_shape] | b_states[n_shape]; + /* the last call for the count_internal outside of all shapes. */ + else if (set_type == 1) + result= 0; + 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, + (set_type == 1) ? set_type : 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; + //GCALC_DBUG_RETURN(mask); + + result= count_internal(cur_func, set_type, &cur_func); + + while (--n_ops) + { + int next_res= count_internal(cur_func, set_type, &cur_func); + switch (next_func) + { + case op_union: + if (result == result_true || next_res == result_true) + result= result_true; + else if (result == result_unknown || next_res == result_unknown) + result= result_unknown; + else + result= result_false; + break; + case op_intersection: + if (result == result_false || next_res == result_false) + result= result_false; + else if (result == result_unknown || next_res == result_unknown) + result= result_unknown; + else + result= result_true; + break; + case op_symdifference: + if (result == result_unknown || next_res == result_unknown) + result= result_unknown; + else + result= result ^ next_res; + break; + case op_difference: + if (result == result_false || next_res == result_true) + result= result_false; + else if (result == result_unknown || next_res == result_unknown) + result= result_unknown; + else + result= result_true; + break; + default: + GCALC_DBUG_ASSERT(FALSE); + }; + } + +exit: + if (result != result_unknown) + result^= mask; + if (v_state != v_empty) + { + switch (v_state) + { + case v_find_t: + if (result == result_true) + { + c_op= (c_op & ~v_mask) | v_t_found; + int4store(sav_cur_func, c_op); + } + else + { + if (set_type != 1) + result= result_unknown; + } + break; + case v_find_f: + if (result == result_false) + { + c_op= (c_op & ~v_mask) | v_f_found; + int4store(sav_cur_func, c_op); + } + else + { + if (set_type != 1) + result= result_unknown; + } + break; + case v_t_found: + result= 1; + break; + case v_f_found: + result= 0; + break; + default: + GCALC_DBUG_ASSERT(0); + }; + } + + if (end) + *end= cur_func; + return result; + //GCALC_DBUG_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; +} + + +/* + Clear the state of the object. +*/ + +void Gcalc_function::reset() +{ + n_shapes= 0; + shapes_buffer.length(0); + function_buffer.length(0); +} + + +int Gcalc_function::check_function(Gcalc_scan_iterator &scan_it) +{ + const Gcalc_scan_iterator::point *eq_start, *cur_eq; + const Gcalc_scan_iterator::event_point *events; + int result; + GCALC_DBUG_ENTER("Gcalc_function::check_function"); + + while (scan_it.more_points()) + { + if (scan_it.step()) + GCALC_DBUG_RETURN(-1); + events= scan_it.get_events(); + + /* these kinds of events don't change the function */ + Gcalc_point_iterator pit(&scan_it); + 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_i_state(si); + } + if (events->simple_event()) + { + if (events->event == scev_end) + set_b_state(events->get_shape()); + + if ((result= count()) != result_unknown) + GCALC_DBUG_RETURN(result); + clear_b_states(); + continue; + } + + /* Check the status of the event point */ + for (; 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)) + set_b_state(si); + else if (events->event == scev_single_point || + get_shape_kind(si) == Gcalc_function::shape_line) + set_i_state(si); + } + + if ((result= count()) != result_unknown) + GCALC_DBUG_RETURN(result); + + /* 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 (events->event == scev_single_point || + get_shape_kind(si) == Gcalc_function::shape_line) + clear_i_state(si); + } + + if (scan_it.get_event_position() == scan_it.get_event_end()) + continue; + + /* Check the status after the event */ + eq_start= pit.point(); + do + { + ++pit; + if (pit.point() != scan_it.get_event_end() && + eq_start->cmp_dx_dy(pit.point()) == 0) + continue; + 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) + set_b_state(si); + else + invert_i_state(si); + } + if ((result= count()) != result_unknown) + GCALC_DBUG_RETURN(result); + + 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)) + { + clear_b_state(si); + invert_i_state(si); + } + else + invert_i_state(cur_eq->get_shape()); + } + if ((result= count()) != result_unknown) + GCALC_DBUG_RETURN(result); + + eq_start= pit.point(); + } while (pit.point() != scan_it.get_event_end()); + } + GCALC_DBUG_RETURN(count_last()); +} + + +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_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) +{ + GCALC_DBUG_ENTER("Gcalc_result_receiver::start_shape"); + if (buffer.reserve(4*2, 512)) + 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; + + 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) + GCALC_DBUG_RETURN(0); + + if (!n_points++) + { + prev_x= first_x= x; + prev_y= first_y= y; + GCALC_DBUG_RETURN(0); + } + + shape_area+= prev_x*y - prev_y*x; + + if (buffer.reserve(8*2, 512)) + GCALC_DBUG_RETURN(1); + buffer.q_append(prev_x); + buffer.q_append(prev_y); + prev_x= x; + prev_y= y; + 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); + GCALC_DBUG_RETURN(0); + } + if (n_points == 1) + { + if (cur_shape != Gcalc_function::shape_point) + { + if (cur_shape == Gcalc_function::shape_hole) + { + buffer.length(shape_pos); + GCALC_DBUG_RETURN(0); + } + cur_shape= Gcalc_function::shape_point; + buffer.length(buffer.length()-4); + } + } + else + { + 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; + if (fabs(shape_area) < 1e-8) + { + buffer.length(shape_pos); + GCALC_DBUG_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)) + GCALC_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++) + { + GCALC_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; + } + GCALC_DBUG_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 || 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: + GCALC_DBUG_ASSERT(0); + } + return 0; +} + + +int Gcalc_result_receiver::move_hole(uint32 dest_position, uint32 source_position, + uint32 *position_shift) +{ + 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) + GCALC_DBUG_RETURN(0); + + if (buffer.reserve(source_len, MY_ALIGN(source_len, 512))) + 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); + GCALC_DBUG_RETURN(0); +} + + +Gcalc_operation_reducer::Gcalc_operation_reducer(size_t blk_size) : + Gcalc_dyn_list(blk_size, sizeof(res_point)), +#ifndef GCALC_DBUG_OFF + n_res_points(0), +#endif /*GCALC_DBUG_OFF*/ + m_res_hook((Gcalc_dyn_list::Item **)&m_result), + m_first_active_thread(NULL) +{} + + +Gcalc_operation_reducer::Gcalc_operation_reducer( + const Gcalc_operation_reducer &gor) : + Gcalc_dyn_list(gor), +#ifndef GCALC_DBUG_OFF + n_res_points(0), +#endif /*GCALC_DBUG_OFF*/ + 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; + 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; + GCALC_SET_TERMINATED(killed, 0); +} + + +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); +} + + +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 * + 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 GCALC_DBUG_OFF + result->point_n= n_res_points++; +#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) + GCALC_DBUG_RETURN(1); + l->incoming= incoming; + l->t= t; + l->p= p; + *m_lines_hook= l; + m_lines_hook= &l->next; + GCALC_DBUG_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(); + GCALC_DBUG_ENTER("Gcalc_operation_reducer::add_poly_border"); + if (!b) + 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; + GCALC_DBUG_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); + GCALC_DBUG_ENTER("Gcalc_operation_reducer::continue_range"); + if (!rp) + GCALC_DBUG_RETURN(1); + rp->glue= NULL; + rp->down= t->rp; + t->rp->up= rp; + rp->intersection_point= false; + rp->pi= p; + t->rp= rp; + t->p1= p; + t->p2= p_next; + GCALC_DBUG_RETURN(0); +} + + +inline int Gcalc_operation_reducer::continue_i_range(active_thread *t, + const Gcalc_heap::Info *ii) +{ + res_point *rp= add_res_point(t->rp->type); + GCALC_DBUG_ENTER("Gcalc_operation_reducer::continue_i_range"); + if (!rp) + GCALC_DBUG_RETURN(1); + rp->glue= NULL; + rp->down= t->rp; + t->rp->up= rp; + rp->intersection_point= true; + rp->pi= ii; + t->rp= rp; + 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"); + 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); + 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; + GCALC_DBUG_RETURN(0); +} + + +int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si) +{ + Gcalc_point_iterator pi(si); + int prev_state= 0; + int sav_prev_state; + active_thread *prev_range= NULL; + 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; + active_thread *bottom_threads= NULL; + active_thread *eq_thread, *point_thread;; + GCALC_DBUG_ENTER("Gcalc_operation_reducer::count_slice"); + + m_fn->clear_i_states(); + /* 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_i_state(pi.get_shape()); + } + + 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->next_pi)) + GCALC_DBUG_RETURN(1); + break; + } + case scev_end: + { + if (cur_t->enabled() && end_line(cur_t, si)) + GCALC_DBUG_RETURN(1); + *cur_t_hook= cur_t->get_next(); + free_item(cur_t); + break; + } + case scev_two_ends: + { + 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)) + 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)) + GCALC_DBUG_RETURN(1); + } + *cur_t_hook= cur_t->get_next()->get_next(); + free_item(cur_t->next); + free_item(cur_t); + break; + } + default: + GCALC_DBUG_ASSERT(0); + } + GCALC_DBUG_RETURN(0); + } + + starting_t_hook= cur_t_hook; + sav_prev_state= prev_state; + + /* Walk through the event, collecting all the 'incoming' threads */ + for (; events; events= events->get_next()) + { + active_thread *cur_t= *cur_t_hook; + + if (events->event == scev_single_point) + continue; + + if (events->event == scev_thread || + events->event == scev_two_threads) + { + active_thread *new_t= new_active_thread(); + if (!new_t) + GCALC_DBUG_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) + { + GCALC_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) + GCALC_DBUG_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; + + 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; + int in_state, after_state; + + ++pi; + point_thread= point_thread->get_next(); + + if (pi.point() != si->get_event_end() && + eq_start->cmp_dx_dy(pi.point()) == 0) + continue; + + for (cur_eq= eq_start; cur_eq != pi.point(); cur_eq= cur_eq->get_next()) + m_fn->set_b_state(cur_eq->get_shape()); + in_state= m_fn->count(); + + 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_i_state(si); + } + after_state= m_fn->count(); + if (prev_state != after_state) + { + if (add_poly_border(0, eq_thread, prev_state, eq_start)) + GCALC_DBUG_RETURN(1); + } + else if (!prev_state /* &&!after_state */ && in_state) + { + if (add_line(0, eq_thread, eq_start)) + GCALC_DBUG_RETURN(1); + } + + prev_state= after_state; + eq_start= pi.point(); + eq_thread= point_thread; + } + + if (!sav_prev_state && !m_poly_borders && !m_lines) + { + /* Check if we need to add the event point itself */ + 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_i_state(pi.get_shape()); + } + for (events= si->get_events(); events; events= events->get_next()) + m_fn->set_b_state(events->get_shape()); + + GCALC_DBUG_RETURN(m_fn->count() ? add_single_point(si) : 0); + } + + if (m_poly_borders) + { + *m_poly_borders_hook= NULL; + while (m_poly_borders) + { + poly_border *pb1, *pb2; + pb1= m_poly_borders; + 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. */ + m_poly_borders= pb1->get_next(); + if (connect_threads(pb1->incoming, pb2->incoming, + pb1->t, pb2->t, pb1->p, pb2->p, + prev_range, si, Gcalc_function::shape_polygon)) + GCALC_DBUG_RETURN(1); + + free_item(pb1); + free_item(pb2); + } + m_poly_borders_hook= (Gcalc_dyn_list::Item **) &m_poly_borders; + m_poly_borders= NULL; + } + + if (m_lines) + { + *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, si, Gcalc_function::shape_line)) + GCALC_DBUG_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, si)) + GCALC_DBUG_RETURN(1); + } + else + start_line(cur_line->t, cur_line->p, si); + } + } + free_list(m_lines); + m_lines= NULL; + m_lines_hook= (Gcalc_dyn_list::Item **) &m_lines; + } + + if (bottom_threads) + free_list(bottom_threads); + + 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) + GCALC_DBUG_RETURN(1); + rp->glue= rp->up= rp->down= NULL; + rp->set(si); + GCALC_DBUG_RETURN(0); +} + + +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(); + GCALC_DBUG_ENTER("Gcalc_operation_reducer::get_pair_border"); + if (b1->prev_state) + { + if (b1->incoming) + { + /* Find the first outgoing, otherwise the last one. */ + while (result->incoming && result->get_next()) + { + prev_b= result; + result= result->get_next(); + } + } + else + { + /* Get the last one */ + while (result->get_next()) + { + prev_b= result; + result= result->get_next(); + } + } + } + else /* !b1->prev_state */ + { + if (b1->incoming) + { + /* Get the next incoming, otherwise the last one. */ + while (!result->incoming && result->get_next()) + { + prev_b= result; + result= result->get_next(); + } + } + else + { + /* Just pick the next one */ + } + } + /* Delete the result from the list. */ + prev_b->next= result->next; + GCALC_DBUG_RETURN(result); +} + + +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_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; + 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); + 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; + rpa->set(si); + rpb->set(si); + ta->rp= tb->rp= NULL; + GCALC_DBUG_RETURN(0); + } + if (!incoming_a) + { + GCALC_DBUG_ASSERT(!incoming_b); + + res_point *rp0, *rp1; + if (!(rp0= add_res_point(s_t)) || !(rp1= add_res_point(s_t))) + GCALC_DBUG_RETURN(1); + rp0->glue= rp1; + rp1->glue= rp0; + rp0->set(si); + rp1->set(si); + rp0->down= rp1->down= NULL; + ta->rp= rp0; + tb->rp= rp1; + ta->p1= pa->pi; + ta->p2= pa->next_pi; + + 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; + /* Check if needed */ + ta->thread_start= prev_range->thread_start; + } + else + { + rp0->outer_poly= 0; + ta->thread_start= rp0; + /* Check if needed */ + tb->thread_start= rp0; + } + GCALC_DBUG_RETURN(0); + } + /* else, if only ta is incoming */ + + 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_pi()) : + continue_range(tb, si->get_cur_pi(), pb->next_pi)) + GCALC_DBUG_RETURN(1); + } + tb->p1= pb->pi; + tb->p2= pb->next_pi; + + GCALC_DBUG_RETURN(0); +} + + +int Gcalc_operation_reducer::start_line(active_thread *t, + const Gcalc_scan_iterator::point *p, + 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) + GCALC_DBUG_RETURN(1); + rp->glue= rp->down= NULL; + rp->set(si); + t->rp= rp; + t->p1= p->pi; + t->p2= p->next_pi; + 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"); + 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); + rp->glue= rp->up= NULL; + rp->down= t->rp; + rp->set(si); + t->rp->up= rp; + t->rp= NULL; + + 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); + GCALC_SET_TERMINATED(si.killed, killed); + while (si.more_points()) + { + if (si.step()) + GCALC_DBUG_RETURN(1); + if (count_slice(&si)) + GCALC_DBUG_RETURN(1); + } + GCALC_DBUG_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) +{ + GCALC_DBUG_ENTER("Gcalc_operation_reducer::get_single_result"); + if (res->intersection_point) + { + double x, y; + res->pi->calc_xy(&x, &y); + if (storage->single_point(x,y)) + GCALC_DBUG_RETURN(1); + } + else + if (storage->single_point(res->pi->node.shape.x, res->pi->node.shape.y)) + GCALC_DBUG_RETURN(1); + free_result(res); + GCALC_DBUG_RETURN(0); +} + + +int Gcalc_operation_reducer::get_result_thread(res_point *cur, + Gcalc_result_receiver *storage, + int move_upward, + res_point *first_poly_node) +{ + res_point *next; + bool glue_step= false; + double x, y; + GCALC_DBUG_ENTER("Gcalc_operation_reducer::get_result_thread"); + while (cur) + { + if (!glue_step) + { + if (cur->intersection_point) + { + cur->pi->calc_xy(&x, &y); + } + else + { + x= cur->pi->node.shape.x; + y= cur->pi->node.shape.y; + } + if (storage->add_point(x, y)) + GCALC_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; + } + GCALC_DBUG_RETURN(0); +} + + +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); + GCALC_DBUG_RETURN(get_result_thread(cur, storage, 1, first_poly_node) || + storage->complete_shape()); +} + + +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; + GCALC_DBUG_ENTER("Gcalc_operation_reducer::get_line_result"); + 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; + if (next == cur_orig) + { + /* It's the line loop */ + cur= cur_orig; + cur->glue->glue= NULL; + move_upward= 1; + break; + } + move_upward^= 1; + } + } + } + + GCALC_DBUG_RETURN(get_result_thread(cur, storage, move_upward, 0) || + storage->complete_shape()); +} + + +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; + + /* This is to workaround an old gcc's bug */ + if (m_res_hook == (Gcalc_dyn_list::Item **) &m_result) + goto done; + + while (m_result) + { + Gcalc_function::shape_type shape= m_result->type; + if (shape == Gcalc_function::shape_point) + { + if (get_single_result(m_result, storage)) + GCALC_DBUG_RETURN(1); + continue; + } + if (shape == Gcalc_function::shape_polygon) + { + if (m_result->outer_poly) + { + uint32 insert_position, hole_position, position_shift; + poly_instance *cur_poly; + insert_position= m_result->outer_poly->first_poly_node->poly_position; + GCALC_DBUG_ASSERT(insert_position); + hole_position= storage->position(); + storage->start_shape(Gcalc_function::shape_hole); + if (get_polygon_result(m_result, storage, + m_result->outer_poly->first_poly_node) || + storage->move_hole(insert_position, hole_position, + &position_shift)) + GCALC_DBUG_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, m_result)) + GCALC_DBUG_RETURN(1); + *poly_position= storage->position(); + } + } + else + { + storage->start_shape(shape); + if (get_line_result(m_result, storage)) + GCALC_DBUG_RETURN(1); + } + } + +done: + m_res_hook= (Gcalc_dyn_list::Item **)&m_result; + storage->done(); + GCALC_DBUG_RETURN(0); +} + + +void Gcalc_operation_reducer::reset() +{ + 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); +} + +#endif /*HAVE_SPATIAL*/ + |