1 /* Copyright (c) 2000, 2017, Oracle and/or its affiliates. All rights reserved. 2 3 This program is free software; you can redistribute it and/or modify 4 it under the terms of the GNU General Public License, version 2.0, 5 as published by the Free Software Foundation. 6 7 This program is also distributed with certain software (including 8 but not limited to OpenSSL) that is licensed under separate terms, 9 as designated in a particular file or component or in included license 10 documentation. The authors of MySQL hereby grant you an additional 11 permission to link the program and your derivative works with the 12 separately licensed software that they have included with MySQL. 13 14 This program is distributed in the hope that it will be useful, 15 but WITHOUT ANY WARRANTY; without even the implied warranty of 16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 17 GNU General Public License, version 2.0, for more details. 18 19 You should have received a copy of the GNU General Public License 20 along with this program; if not, write to the Free Software 21 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */ 22 23 24 #ifndef GCALC_TOOLS_INCLUDED 25 #define GCALC_TOOLS_INCLUDED 26 27 #include "gcalc_slicescan.h" 28 29 30 /* 31 The Gcalc_function class objects are used to check for a binary relation. 32 The relation can be constructed with the prefix notation using predicates as 33 op_not (as !A) 34 op_union ( A || B || C... ) 35 op_intersection ( A && B && C ... ) 36 op_symdifference ( A+B+C+... == 1 ) 37 op_difference ( A && !(B||C||..)) 38 with the calls of the add_operation(operation, n_operands) method. 39 The relation is calculated over a set of shapes, that in turn have 40 to be added with the add_new_shape() method. All the 'shapes' can 41 be set to 0 with clear_shapes() method and single value 42 can be changed with the invert_state() method. 43 Then the value of the relation can be calculated with the count() method. 44 Frequently used method is find_function(Gcalc_scan_iterator it) that 45 iterates through the 'it' until the relation becomes TRUE. 46 */ 47 48 class Gcalc_function 49 { 50 private: 51 static const uint32 function_buffer_item_size= 4; 52 static const uint32 shape_buffer_item_size= 4; 53 String shapes_buffer; 54 String function_buffer; 55 const char *cur_func; 56 int *i_states; 57 uint32 cur_object_id; 58 uint n_shapes; 59 int count_internal(); 60 public: 61 #ifndef DBUG_OFF 62 /** 63 Convert operation code to its readable name. 64 */ 65 static const char *op_name(int code); 66 /** 67 Convert shape code to its readable name. 68 */ 69 static const char *shape_name(int code); 70 #endif 71 enum op_type 72 { 73 op_shape= 0, 74 op_not= 0x80000000, 75 op_union= 0x10000000, 76 op_intersection= 0x20000000, 77 op_symdifference= 0x30000000, 78 op_difference= 0x40000000, 79 op_backdifference= 0x50000000, 80 op_any= 0x70000000 81 }; 82 enum shape_type 83 { 84 shape_point= 0, 85 shape_line= 1, 86 shape_polygon= 2, 87 shape_hole= 3 88 }; Gcalc_function()89 Gcalc_function() : n_shapes(0) {} 90 gcalc_shape_info add_new_shape(uint32 shape_id, shape_type shape_kind); 91 /* 92 Adds the leaf operation that returns the shape value. 93 Also adds the shape to the list of operands. 94 */ 95 int single_shape_op(shape_type shape_kind, gcalc_shape_info *si); 96 void add_operation(op_type operation, uint32 n_operands); 97 void add_not_operation(op_type operation, uint32 n_operands); get_next_operation_pos()98 uint32 get_next_operation_pos() { return function_buffer.length(); } 99 /** 100 Read operand number from the given position and add more operands. 101 */ 102 void add_operands_to_op(uint32 operation_pos, uint32 n_operands); 103 /** 104 Set operand number at the given position (replace the old operand number). 105 */ 106 void set_operands_to_op(uint32 operation_pos, uint32 n_operands); set_cur_obj(uint32 cur_obj)107 void set_cur_obj(uint32 cur_obj) { cur_object_id= cur_obj; } 108 int reserve_shape_buffer(uint n_shapes); 109 int reserve_op_buffer(uint n_ops); get_nshapes()110 uint get_nshapes() const { return n_shapes; } get_shape_kind(gcalc_shape_info si)111 shape_type get_shape_kind(gcalc_shape_info si) const 112 { 113 return (shape_type) uint4korr(shapes_buffer.ptr() + (si*4)); 114 } 115 set_states(int * shape_states)116 void set_states(int *shape_states) { i_states= shape_states; } 117 int alloc_states(); invert_state(gcalc_shape_info shape)118 void invert_state(gcalc_shape_info shape) { i_states[shape]^= 1; } get_state(gcalc_shape_info shape)119 int get_state(gcalc_shape_info shape) { return i_states[shape]; } count()120 int count() 121 { 122 cur_func= function_buffer.ptr(); 123 return count_internal(); 124 } clear_state()125 void clear_state() { memset(i_states, 0, n_shapes * sizeof(int)); } 126 void reset(); 127 128 int find_function(Gcalc_scan_iterator &scan_it); 129 130 #ifndef DBUG_OFF 131 /** 132 Print function buffer created after shape transformation 133 into mysqld log and into client side warnings. 134 Printing to mysqld log is useful when server crashed during an operation. 135 Printing to client side warnings is useful for mtr purposes. 136 */ 137 void debug_print_function_buffer(); 138 #endif 139 }; 140 141 142 /* 143 Gcalc_operation_transporter class extends the Gcalc_shape_transporter. 144 In addition to the parent's functionality, it fills the Gcalc_function 145 object so it has the function that determines the proper shape. 146 For example Multipolyline will be represented as an union of polylines. 147 */ 148 149 class Gcalc_operation_transporter : public Gcalc_shape_transporter 150 { 151 protected: 152 Gcalc_function *m_fn; 153 gcalc_shape_info m_si; 154 public: Gcalc_operation_transporter(Gcalc_function * fn,Gcalc_heap * heap)155 Gcalc_operation_transporter(Gcalc_function *fn, Gcalc_heap *heap) : 156 Gcalc_shape_transporter(heap), m_fn(fn) {} 157 158 int single_point(Gcalc_shape_status *st, double x, double y); 159 int start_line(Gcalc_shape_status *st); 160 int complete_line(Gcalc_shape_status *st); 161 int start_poly(Gcalc_shape_status *st); 162 int complete_poly(Gcalc_shape_status *st); 163 int start_ring(Gcalc_shape_status *st); 164 int complete_ring(Gcalc_shape_status *st); 165 int add_point(Gcalc_shape_status *st, double x, double y); 166 int start_collection(Gcalc_shape_status *st, int nshapes); 167 int complete_collection(Gcalc_shape_status *st); 168 int collection_add_item(Gcalc_shape_status *st_collection, 169 Gcalc_shape_status *st_item); 170 }; 171 172 173 /* 174 When we calculate the result of an spatial operation like 175 Union or Intersection, we receive vertexes of the result 176 one-by-one, and probably need to treat them in variative ways. 177 So, the Gcalc_result_receiver class designed to get these 178 vertexes and construct shapes/objects out of them. 179 and to store the result in an appropriate format 180 */ 181 182 class Gcalc_result_receiver 183 { 184 String buffer; 185 uint32 n_points; 186 Gcalc_function::shape_type common_shapetype; 187 bool collection_result; 188 uint32 n_shapes; 189 uint32 n_holes; 190 191 Gcalc_function::shape_type cur_shape; 192 uint32 shape_pos; 193 double first_x, first_y, prev_x, prev_y; 194 double shape_area; 195 public: 196 197 class chunk_info 198 { 199 public: 200 void *first_point; 201 uint32 order; 202 uint32 position; 203 uint32 length; 204 bool is_poly_hole; 205 #ifndef DBUG_OFF 206 inline void dbug_print() const; 207 #endif 208 }; 209 Gcalc_result_receiver()210 Gcalc_result_receiver() : n_points(0), collection_result(FALSE), n_shapes(0), 211 n_holes(0), prev_x(0), prev_y(0), shape_area(0) 212 {} 213 int start_shape(Gcalc_function::shape_type shape); 214 int add_point(double x, double y); 215 int complete_shape(); 216 int single_point(double x, double y); 217 int done(); 218 void reset(); 219 result()220 const char *result() { return buffer.ptr(); } length()221 uint length() { return buffer.length(); } get_nshapes()222 int get_nshapes() { return n_shapes; } get_nholes()223 int get_nholes() { return n_holes; } 224 int get_result_typeid(); position()225 uint32 position() { return buffer.length(); } 226 int reorder_chunks(chunk_info *chunks, int nchunks); 227 }; 228 229 230 /* 231 Gcalc_operation_reducer class incapsulates the spatial 232 operation functionality. It analyses the slices generated by 233 the slicescan and calculates the shape of the result defined 234 by some Gcalc_function. 235 */ 236 237 class Gcalc_operation_reducer : public Gcalc_dyn_list 238 { 239 public: 240 enum modes 241 { 242 /* Numeric values important here - careful with changing */ 243 default_mode= 0, 244 prefer_big_with_holes= 1, 245 polygon_selfintersections_allowed= 2, /* allowed in the result */ 246 line_selfintersections_allowed= 4 /* allowed in the result */ 247 }; 248 249 Gcalc_operation_reducer(size_t blk_size=8192); 250 void init(Gcalc_function *fn, modes mode= default_mode); 251 Gcalc_operation_reducer(Gcalc_function *fn, modes mode= default_mode, 252 size_t blk_size=8192); 253 int count_slice(Gcalc_scan_iterator *si); 254 int count_all(Gcalc_heap *hp); 255 int get_result(Gcalc_result_receiver *storage); 256 void reset(); 257 258 class res_point : public Gcalc_dyn_list::Item 259 { 260 res_point *m_outer_poly; 261 public: 262 bool intersection_point; 263 double x,y; 264 res_point *up; 265 res_point *down; 266 res_point *glue; 267 union 268 { 269 const Gcalc_heap::Info *pi; // is valid before get_result_thread() 270 res_point *first_poly_node; // is valid after get_result_thread() 271 }; 272 Gcalc_dyn_list::Item **prev_hook; get_next()273 res_point *get_next() { return (res_point *)next; } set_outer_poly(res_point * p)274 void set_outer_poly(res_point *p) 275 { 276 m_outer_poly= p; 277 DBUG_PRINT("info", ("setting outer_poly of #%u to #%u", 278 item_id(), 279 m_outer_poly ? m_outer_poly->item_id() : 0)); 280 } get_outer_poly()281 res_point *get_outer_poly() { return m_outer_poly; } 282 }; 283 284 class active_thread : public Gcalc_dyn_list::Item 285 { 286 res_point *m_thread_start; 287 public: 288 res_point *rp; 289 int result_range; init()290 void init() 291 { 292 rp= m_thread_start= NULL; 293 result_range= 0; 294 DBUG_PRINT("info", ("setting m_thread_start of #%u to NULL (reset)", 295 item_id())); 296 } get_next()297 active_thread *get_next() { return (active_thread *)next; } set_thread_start(res_point * p)298 void set_thread_start(res_point *p) 299 { 300 DBUG_PRINT("info", ("setting m_thread_start of #%u to #%u", 301 item_id(), p ? p->item_id() : 0)); 302 m_thread_start= p; 303 } thread_start()304 res_point *thread_start() const { return m_thread_start; } 305 }; 306 307 protected: 308 Gcalc_function *m_fn; 309 Gcalc_dyn_list::Item **m_res_hook; 310 res_point *m_result; 311 int m_mode; 312 313 res_point *result_heap; 314 active_thread *m_first_active_thread; 315 add_res_point(const Gcalc_heap::Info * pi)316 res_point *add_res_point(const Gcalc_heap::Info *pi) 317 { 318 res_point *rp= new_res_point(pi, false); 319 if (!rp) 320 return NULL; 321 DBUG_PRINT("info", ("add_res_point #%u: pi=(%g,%g,#%u)", 322 rp->item_id(), pi->x, pi->y, pi->shape)); 323 return rp; 324 } 325 add_res_i_point(const Gcalc_heap::Info * pi,double x,double y)326 res_point *add_res_i_point(const Gcalc_heap::Info *pi, double x, double y) 327 { 328 res_point *rp= new_res_point(pi, true); 329 if (!rp) 330 return NULL; 331 DBUG_PRINT("info", ("add_res_i_point #%u: pi=(%g,%g,#%u) xy=(%g,%g)", 332 rp->item_id(), pi->x, pi->y, pi->shape, x, y)); 333 rp->x= x; 334 rp->y= y; 335 return rp; 336 } 337 add_res_single_point(const Gcalc_heap::Info * pi)338 res_point *add_res_single_point(const Gcalc_heap::Info *pi) 339 { 340 res_point *rp= new_res_point(pi, false); 341 if (!rp) 342 return NULL; 343 DBUG_PRINT("info", ("add_res_single_point #%u: pi=(%g,%g,#%u)", 344 rp->item_id(), pi->x, pi->y, pi->shape)); 345 rp->x= pi->x; 346 rp->y= pi->y; 347 return rp; 348 } 349 new_active_thread()350 active_thread *new_active_thread() 351 { 352 active_thread *tmp= (active_thread *) new_item(); 353 if (tmp) 354 tmp->init(); 355 return tmp; 356 } 357 358 private: 359 new_res_point(const Gcalc_heap::Info * pi,bool intersection_point)360 res_point *new_res_point(const Gcalc_heap::Info *pi, 361 bool intersection_point) 362 { 363 res_point *result= (res_point *) new_item(); 364 result->up= result->down= result->glue= NULL; 365 result->set_outer_poly(NULL); 366 result->pi= NULL; 367 result->first_poly_node= NULL; 368 *m_res_hook= result; 369 result->prev_hook= m_res_hook; 370 m_res_hook= &result->next; 371 result->pi= pi; 372 result->intersection_point= intersection_point; 373 result->x= 0; 374 result->y= 0; 375 return result; 376 } 377 378 int continue_range(active_thread *t, const Gcalc_heap::Info *p); 379 int continue_i_range(active_thread *t, const Gcalc_heap::Info *p, 380 double x, double y); 381 int start_range(active_thread *t, const Gcalc_heap::Info *p); 382 int start_i_range(active_thread *t, const Gcalc_heap::Info *p, 383 double x, double y); 384 int end_range(active_thread *t, const Gcalc_heap::Info *p); 385 int end_i_range(active_thread *t, const Gcalc_heap::Info *p, 386 double x, double y); 387 int start_couple(active_thread *t0, active_thread *t1,const Gcalc_heap::Info *p, 388 const active_thread *prev_range); 389 int start_i_couple(active_thread *t0, active_thread *t1, 390 const Gcalc_heap::Info *p0, 391 const Gcalc_heap::Info *p1, 392 double x, double y, 393 const active_thread *prev_range); 394 int end_couple(active_thread *t0, active_thread *t1, const Gcalc_heap::Info *p); 395 int end_i_couple(active_thread *t0, active_thread *t1, 396 const Gcalc_heap::Info *p0, 397 const Gcalc_heap::Info *p1, 398 double x, double y); 399 int add_single_point(const Gcalc_heap::Info *p); 400 int add_i_single_point(const Gcalc_heap::Info *p, double x, double y); 401 402 int handle_lines_intersection(active_thread *t0, active_thread *t1, 403 const Gcalc_heap::Info *p0, 404 const Gcalc_heap::Info *p1, 405 double x, double y); 406 int handle_polygons_intersection(active_thread *t0, active_thread *t1, 407 Gcalc_dyn_list::Item **t_hook, 408 const Gcalc_heap::Info *p0, 409 const Gcalc_heap::Info *p1, 410 int prev_state, double x, double y, 411 const active_thread *prev_range); 412 int handle_line_polygon_intersection(active_thread *l, 413 const Gcalc_heap::Info *pl, 414 int line_state, int poly_state, 415 double x, double y); 416 417 int get_single_result(res_point *res, Gcalc_result_receiver *storage); 418 int get_result_thread(res_point *cur, Gcalc_result_receiver *storage, 419 int move_upward); 420 int get_polygon_result(res_point *cur, Gcalc_result_receiver *storage); 421 int get_line_result(res_point *cur, Gcalc_result_receiver *storage); 422 423 void free_result(res_point *res); 424 }; 425 426 #endif /*GCALC_TOOLS_INCLUDED*/ 427 428