Adding upstream version 1:10.5.12.upstream/1%10.5.12upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 607 insertions, 0 deletions

diff --git a/sql/gcalc_slicescan.h b/sql/gcalc_slicescan.h
new file mode 100644
index 00000000..b5188f29
--- /dev/null
+++ b/sql/gcalc_slicescan.h
@@ -0,0 +1,607 @@
+/* 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 */
+
+
+#ifndef GCALC_SLICESCAN_INCLUDED
+#define GCALC_SLICESCAN_INCLUDED
+
+#ifndef DBUG_OFF
+// #define GCALC_CHECK_WITH_FLOAT
+#else
+#define GCALC_DBUG_OFF
+#endif /*DBUG_OFF*/
+
+#ifndef GCALC_DBUG_OFF
+#define GCALC_DBUG_PRINT(b) DBUG_PRINT("Gcalc", b)
+#define GCALC_DBUG_ENTER(a) DBUG_ENTER("Gcalc " a)
+#define GCALC_DBUG_RETURN(r) DBUG_RETURN(r)
+#define GCALC_DBUG_VOID_RETURN DBUG_VOID_RETURN
+#define GCALC_DBUG_ASSERT(r) DBUG_ASSERT(r)
+#else
+#define GCALC_DBUG_PRINT(b)     do {} while(0)
+#define GCALC_DBUG_ENTER(a)     do {} while(0)
+#define GCALC_DBUG_RETURN(r)    return (r)
+#define GCALC_DBUG_VOID_RETURN  do {} while(0)
+#define GCALC_DBUG_ASSERT(r)    do {} while(0)
+#endif /*GCALC_DBUG_OFF*/
+
+#define GCALC_TERMINATED(state_var) (state_var && (*state_var))
+#define GCALC_SET_TERMINATED(state_var, val) state_var= val
+#define GCALC_DECL_TERMINATED_STATE(varname) \
+  volatile int *varname;
+
+/*
+  Gcalc_dyn_list class designed to manage long lists of same-size objects
+  with the possible efficiency.
+  It allocates fixed-size blocks of memory (blk_size specified at the time
+  of creation). When new object is added to the list, it occupies part of
+  this block until it's full. Then the new block is allocated.
+  Freed objects are chained to the m_free list, and if it's not empty, the
+  newly added object is taken from this list instead the block.
+*/
+
+class Gcalc_dyn_list
+{
+public:
+  class Item
+  {
+  public:
+    Item *next;
+  };
+
+  Gcalc_dyn_list(size_t blk_size, size_t sizeof_item);
+  Gcalc_dyn_list(const Gcalc_dyn_list &dl);
+  ~Gcalc_dyn_list();
+  Item *new_item()
+  {
+    Item *result;
+    if (m_free)
+    {
+      result= m_free;
+      m_free= m_free->next;
+    }
+    else
+      result= alloc_new_blk();
+
+    return result;
+  }
+  inline void free_item(Item *item)
+  {
+    item->next= m_free;
+    m_free= item;
+  }
+  inline void free_list(Item **list, Item **hook)
+  {
+    *hook= m_free;
+    m_free= *list;
+  }
+
+  void free_list(Item *list)
+  {
+    Item **hook= &list;
+    while (*hook)
+      hook= &(*hook)->next;
+    free_list(&list, hook);
+  }
+
+  void reset();
+  void cleanup();
+
+protected:
+  size_t m_blk_size;
+  size_t m_sizeof_item;
+  unsigned int m_points_per_blk;
+  void *m_first_blk;
+  void **m_blk_hook;
+  Item *m_free;
+  Item *m_keep;
+
+  Item *alloc_new_blk();
+  void format_blk(void* block);
+  inline Item *ptr_add(Item *ptr, int n_items)
+  {
+    return (Item *)(((char*)ptr) + n_items * m_sizeof_item);
+  }
+};
+
+/* Internal Gcalc coordinates to provide the precise calculations */
+
+#define GCALC_DIG_BASE     1000000000
+typedef uint32 gcalc_digit_t;
+typedef unsigned long long gcalc_coord2;
+typedef gcalc_digit_t Gcalc_internal_coord;
+#define GCALC_COORD_BASE 2
+#define GCALC_COORD_BASE2 4
+#define GCALC_COORD_BASE3 6
+#define GCALC_COORD_BASE4 8
+#define GCALC_COORD_BASE5 10
+
+typedef gcalc_digit_t Gcalc_coord1[GCALC_COORD_BASE];
+typedef gcalc_digit_t Gcalc_coord2[GCALC_COORD_BASE*2];
+typedef gcalc_digit_t Gcalc_coord3[GCALC_COORD_BASE*3];
+
+
+void gcalc_mul_coord(Gcalc_internal_coord *result, int result_len,
+                     const Gcalc_internal_coord *a, int a_len,
+                     const Gcalc_internal_coord *b, int b_len);
+
+void gcalc_add_coord(Gcalc_internal_coord *result, int result_len,
+                     const Gcalc_internal_coord *a,
+                     const Gcalc_internal_coord *b);
+
+void gcalc_sub_coord(Gcalc_internal_coord *result, int result_len,
+                     const Gcalc_internal_coord *a,
+                     const Gcalc_internal_coord *b);
+
+int gcalc_cmp_coord(const Gcalc_internal_coord *a,
+                    const Gcalc_internal_coord *b, int len);
+
+/* Internal coordinates declarations end. */
+
+
+typedef uint gcalc_shape_info;
+
+/*
+  Gcalc_heap represents the 'dynamic list' of Info objects, that
+  contain information about vertexes of all the shapes that take
+  part in some spatial calculation. Can become quite long.
+  After filled, the list is usually sorted and then walked through
+  in the slicescan algorithm.
+  The Gcalc_heap and the algorithm can only operate with two
+  kinds of shapes - polygon and polyline. So all the spatial
+  objects should be represented as sets of these two.
+*/
+
+class Gcalc_heap : public Gcalc_dyn_list
+{
+public:
+  enum node_type
+  {
+    nt_shape_node,
+    nt_intersection,
+    nt_eq_node
+  };
+  class Info : public Gcalc_dyn_list::Item
+  {
+  public:
+    node_type type;
+    union
+    {
+      struct
+      {
+        /* nt_shape_node */
+        gcalc_shape_info shape;
+        Info *left;
+        Info *right;
+        double x,y;
+        Gcalc_coord1 ix, iy;
+        int top_node;
+      } shape;
+      struct
+      {
+        /* nt_intersection */
+        /* Line p1-p2 supposed to intersect line p3-p4 */
+        const Info *p1;
+        const Info *p2;
+        const Info *p3;
+        const Info *p4;
+        void *data;
+        int equal;
+      } intersection;
+      struct
+      {
+        /* nt_eq_node */
+        const Info *node;
+        void *data;
+      } eq;
+    } node;
+
+    bool is_bottom() const
+      { GCALC_DBUG_ASSERT(type == nt_shape_node); return !node.shape.left; }
+    bool is_top() const
+      { GCALC_DBUG_ASSERT(type == nt_shape_node); return node.shape.top_node; }
+    bool is_single_node() const
+      { return is_bottom() && is_top(); }
+
+    void calc_xy(double *x, double *y) const;
+    int equal_pi(const Info *pi) const;
+#ifdef GCALC_CHECK_WITH_FLOAT
+    void calc_xy_ld(long double *x, long double *y) const;
+#endif /*GCALC_CHECK_WITH_FLOAT*/
+
+    Info *get_next() { return (Info *)next; }
+    const Info *get_next() const { return (const Info *)next; }
+  };
+
+  Gcalc_heap(size_t blk_size=8192) :
+    Gcalc_dyn_list(blk_size, sizeof(Info)),
+    m_hook(&m_first), m_n_points(0)
+  {}
+
+  Gcalc_heap(const Gcalc_heap &gh) :
+    Gcalc_dyn_list(gh),
+    m_hook(&m_first), m_n_points(0)
+  {}
+
+  void set_extent(double xmin, double xmax, double ymin, double ymax);
+  Info *new_point_info(double x, double y, gcalc_shape_info shape);
+  void free_point_info(Info *i, Gcalc_dyn_list::Item **i_hook);
+  Info *new_intersection(const Info *p1, const Info *p2,
+                         const Info *p3, const Info *p4);
+  void prepare_operation();
+  inline bool ready() const { return m_hook == NULL; }
+  Info *get_first() { return (Info *)m_first; }
+  const Info *get_first() const { return (const Info *)m_first; }
+  Gcalc_dyn_list::Item **get_last_hook() { return m_hook; }
+  void reset();
+#ifdef GCALC_CHECK_WITH_FLOAT
+  long double get_double(const Gcalc_internal_coord *c) const;
+#endif /*GCALC_CHECK_WITH_FLOAT*/
+  double coord_extent;
+  Gcalc_dyn_list::Item **get_cur_hook() { return m_hook; }
+
+private:
+  Gcalc_dyn_list::Item *m_first;
+  Gcalc_dyn_list::Item **m_hook;
+  int m_n_points;
+};
+
+
+/*
+  the spatial object has to be represented as a set of
+  simple polygones and polylines to be sent to the slicescan.
+
+  Gcalc_shape_transporter class and his descendants are used to
+  simplify storing the information about the shape into necessary structures.
+  This base class only fills the Gcalc_heap with the information about
+  shapes and vertices.
+
+  Normally the Gcalc_shape_transporter family object is sent as a parameter
+  to the 'get_shapes' method of an 'spatial' object so it can pass
+  the spatial information about itself. The virtual methods are
+  treating this data in a way the caller needs.
+*/
+
+class Gcalc_shape_transporter
+{
+private:
+  Gcalc_heap::Info *m_first;
+  Gcalc_heap::Info *m_prev;
+  Gcalc_dyn_list::Item **m_prev_hook;
+  int m_shape_started;
+  void int_complete();
+protected:
+  Gcalc_heap *m_heap;
+  int int_single_point(gcalc_shape_info Info, double x, double y);
+  int int_add_point(gcalc_shape_info Info, double x, double y);
+  void int_start_line()
+  {
+    DBUG_ASSERT(!m_shape_started);
+    m_shape_started= 1;
+    m_first= m_prev= NULL;
+  }
+  void int_complete_line()
+  {
+    DBUG_ASSERT(m_shape_started== 1);
+    int_complete();
+    m_shape_started= 0;
+  }
+  void int_start_ring()
+  {
+    DBUG_ASSERT(m_shape_started== 2);
+    m_shape_started= 3;
+    m_first= m_prev= NULL;
+  }
+  void int_complete_ring()
+  {
+    DBUG_ASSERT(m_shape_started== 3);
+    int_complete();
+    m_shape_started= 2;
+  }
+  void int_start_poly()
+  {
+    DBUG_ASSERT(!m_shape_started);
+    m_shape_started= 2;
+  }
+  void int_complete_poly()
+  {
+    DBUG_ASSERT(m_shape_started== 2);
+    m_shape_started= 0;
+  }
+  bool line_started() { return m_shape_started == 1; };
+public:
+  Gcalc_shape_transporter(Gcalc_heap *heap) :
+    m_shape_started(0), m_heap(heap) {}
+
+  virtual int single_point(double x, double y)=0;
+  virtual int start_line()=0;
+  virtual int complete_line()=0;
+  virtual int start_poly()=0;
+  virtual int complete_poly()=0;
+  virtual int start_ring()=0;
+  virtual int complete_ring()=0;
+  virtual int add_point(double x, double y)=0;
+  virtual int start_collection(int n_objects) { return 0; }
+  virtual int empty_shape() { return 0; }
+  int start_simple_poly()
+  {
+    return start_poly() || start_ring();
+  }
+  int complete_simple_poly()
+  {
+    return complete_ring() || complete_poly();
+  }
+  virtual ~Gcalc_shape_transporter() {}
+};
+
+
+enum Gcalc_scan_events
+{
+  scev_none= 0,
+  scev_point= 1,         /* Just a new point in thread */
+  scev_thread= 2,        /* Start of the new thread */
+  scev_two_threads= 4,   /* A couple of new threads started */
+  scev_intersection= 8,  /* Intersection happened */
+  scev_end= 16,          /* Single thread finished */
+  scev_two_ends= 32,     /* A couple of threads finished */
+  scev_single_point= 64  /* Got single point */
+};
+
+
+/* 
+   Gcalc_scan_iterator incapsulates the slicescan algorithm.
+   It takes filled Gcalc_heap as a datasource. Then can be
+   iterated through the vertexes and intersection points with
+   the step() method. After the 'step()' one usually observes
+   the current 'slice' to do the necessary calculations, like
+   looking for intersections, calculating the area, whatever.
+*/
+
+class Gcalc_scan_iterator : public Gcalc_dyn_list
+{
+public:
+  class point : public Gcalc_dyn_list::Item
+  {
+  public:
+    Gcalc_coord1 dx;
+    Gcalc_coord1 dy;
+    Gcalc_heap::Info *pi;
+    Gcalc_heap::Info *next_pi;
+    Gcalc_heap::Info *ev_pi;
+    const Gcalc_coord1 *l_border;
+    const Gcalc_coord1 *r_border;
+    point *ev_next;
+
+    Gcalc_scan_events event;
+
+    inline const point *c_get_next() const
+      { return (const point *)next; }
+    inline bool is_bottom() const { return !next_pi; }
+    gcalc_shape_info get_shape() const { return pi->node.shape.shape; }
+    inline point *get_next() { return (point *)next; }
+    inline const point *get_next() const { return (const point *)next; }
+    /* Compare the dx_dy parameters regarding the horiz_dir */
+    /* returns -1 if less, 0 if equal, 1 if bigger          */
+    static int cmp_dx_dy(const Gcalc_coord1 dx_a,
+                         const Gcalc_coord1 dy_a,
+                         const Gcalc_coord1 dx_b,
+                         const Gcalc_coord1 dy_b);
+    static int cmp_dx_dy(const Gcalc_heap::Info *p1,
+                         const Gcalc_heap::Info *p2,
+                         const Gcalc_heap::Info *p3,
+                         const Gcalc_heap::Info *p4);
+    int cmp_dx_dy(const point *p) const;
+    point **next_ptr() { return (point **) &next; }
+#ifndef GCALC_DBUG_OFF
+    unsigned int thread;
+#endif /*GCALC_DBUG_OFF*/
+#ifdef GCALC_CHECK_WITH_FLOAT
+    void calc_x(long double *x, long double y, long double ix) const;
+#endif /*GCALC_CHECK_WITH_FLOAT*/
+  };
+
+  /* That class introduced mostly for the 'typecontrol' reason.      */
+  /* only difference from the point classis the get_next() function. */
+  class event_point : public point
+  {
+  public:
+    inline const event_point *get_next() const
+    { return (const event_point*) ev_next; }
+    int simple_event() const
+    {
+      return !ev_next ? (event & (scev_point | scev_end)) : 
+        (!ev_next->ev_next && event == scev_two_ends);
+    }
+  };
+
+  class intersection_info : public Gcalc_dyn_list::Item
+  {
+  public:
+    point *edge_a;
+    point *edge_b;
+
+    Gcalc_coord2 t_a;
+    Gcalc_coord2 t_b;
+    int t_calculated;
+    Gcalc_coord3 x_exp;
+    int x_calculated;
+    Gcalc_coord3 y_exp;
+    int y_calculated;
+    void calc_t()
+    {if (!t_calculated) do_calc_t(); }
+    void calc_y_exp()
+    { if (!y_calculated) do_calc_y(); }
+    void calc_x_exp()
+    { if (!x_calculated) do_calc_x(); }
+
+    void do_calc_t();
+    void do_calc_x();
+    void do_calc_y();
+  };
+
+
+  class slice_state
+  {
+  public:
+    point *slice;
+    point **event_position_hook;
+    point *event_end;
+    const Gcalc_heap::Info *pi;
+  };
+
+public:
+  Gcalc_scan_iterator(size_t blk_size= 8192);
+
+  GCALC_DECL_TERMINATED_STATE(killed)
+
+  void init(Gcalc_heap *points); /* Iterator can be reused */
+  void reset();
+  int step();
+
+  Gcalc_heap::Info *more_points() { return m_cur_pi; }
+  bool more_trapezoids()
+    { return m_cur_pi && m_cur_pi->next; }
+
+  const point *get_bottom_points() const
+    { return m_bottom_points; }
+  const point *get_event_position() const
+    { return *state.event_position_hook; }
+  const point *get_event_end() const
+    { return state.event_end; }
+  const event_point *get_events() const
+    { return (const event_point *)
+        (*state.event_position_hook == state.event_end ?
+            m_bottom_points : *state.event_position_hook); }
+  const point *get_b_slice() const { return state.slice; }
+  double get_h() const;
+  double get_y() const;
+  double get_event_x() const;
+  double get_sp_x(const point *sp) const;
+  int intersection_step() const
+    { return state.pi->type == Gcalc_heap::nt_intersection; }
+  const Gcalc_heap::Info *get_cur_pi() const
+  {
+    return state.pi;
+  }
+
+private:
+  Gcalc_heap *m_heap;
+  Gcalc_heap::Info *m_cur_pi;
+  slice_state state;
+
+#ifndef GCALC_DBUG_OFF
+  unsigned int m_cur_thread;
+#endif /*GCALC_DBUG_OFF*/
+
+  point *m_bottom_points;
+  point **m_bottom_hook;
+
+  int node_scan();
+  void eq_scan();
+  void intersection_scan();
+  void remove_bottom_node();
+  int insert_top_node();
+  int add_intersection(point *sp_a, point *sp_b,
+                       Gcalc_heap::Info *pi_from);
+  int add_eq_node(Gcalc_heap::Info *node, point *sp);
+  int add_events_for_node(point *sp_node);
+
+  point *new_slice_point()
+  {
+    point *new_point= (point *)new_item();
+    return new_point;
+  }
+  intersection_info *new_intersection_info(point *a, point *b)
+  {
+    intersection_info *ii= (intersection_info *)new_item();
+    ii->edge_a= a;
+    ii->edge_b= b;
+    ii->t_calculated= ii->x_calculated= ii->y_calculated= 0;
+    return ii;
+  }
+  int arrange_event(int do_sorting, int n_intersections);
+  static double get_pure_double(const Gcalc_internal_coord *d, int d_len);
+};
+
+
+/* 
+   Gcalc_trapezoid_iterator simplifies the calculations on
+   the current slice of the Gcalc_scan_iterator.
+   One can walk through the trapezoids formed between
+   previous and current slices.
+*/
+
+#ifdef TMP_BLOCK
+class Gcalc_trapezoid_iterator
+{
+protected:
+  const Gcalc_scan_iterator::point *sp0;
+  const Gcalc_scan_iterator::point *sp1;
+public:
+  Gcalc_trapezoid_iterator(const Gcalc_scan_iterator *scan_i) :
+    sp0(scan_i->get_b_slice()),
+    sp1(scan_i->get_t_slice())
+    {}
+
+  inline bool more() const { return sp1 && sp1->next; }
+
+  const Gcalc_scan_iterator::point *lt() const { return sp1; }
+  const Gcalc_scan_iterator::point *lb() const { return sp0; }
+  const Gcalc_scan_iterator::point *rb() const
+  {
+    const Gcalc_scan_iterator::point *result= sp0;
+    while ((result= result->c_get_next())->is_bottom())
+    {}
+    return result;
+  }
+  const Gcalc_scan_iterator::point *rt() const
+    { return sp1->c_get_next(); }
+
+  void operator++()
+  {
+    sp0= rb();
+    sp1= rt();
+  }
+};
+#endif /*TMP_BLOCK*/
+
+
+/* 
+   Gcalc_point_iterator simplifies the calculations on
+   the current slice of the Gcalc_scan_iterator.
+   One can walk through the points on the current slice.
+*/
+
+class Gcalc_point_iterator
+{
+protected:
+  const Gcalc_scan_iterator::point *sp;
+public:
+  Gcalc_point_iterator(const Gcalc_scan_iterator *scan_i):
+    sp(scan_i->get_b_slice())
+    {}
+
+  inline bool more() const { return sp != NULL; }
+  inline void operator++() { sp= sp->c_get_next(); }
+  inline const Gcalc_scan_iterator::point *point() const { return sp; }
+  inline const Gcalc_heap::Info *get_pi() const { return sp->pi; }
+  inline gcalc_shape_info get_shape() const { return sp->get_shape(); }
+  inline void restart(const Gcalc_scan_iterator *scan_i)
+  { sp= scan_i->get_b_slice(); }
+};
+
+#endif /*GCALC_SLICESCAN_INCLUDED*/
+