rt_split.c
上传用户:romrleung
上传日期:2022-05-23
资源大小:18897k
文件大小:8k
源码类别:

MySQL数据库

开发平台:

Visual C++

  1. /* Copyright (C) 2000 MySQL AB & Alexey Botchkov & MySQL Finland AB 
  2.    & TCX DataKonsult AB
  3.    
  4.    This program is free software; you can redistribute it and/or modify
  5.    it under the terms of the GNU General Public License as published by
  6.    the Free Software Foundation; either version 2 of the License, or
  7.    (at your option) any later version.
  8.    
  9.    This program is distributed in the hope that it will be useful,
  10.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12.    GNU General Public License for more details.
  13.    
  14.    You should have received a copy of the GNU General Public License
  15.    along with this program; if not, write to the Free Software
  16.    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
  17. #include "myisamdef.h"
  18. #ifdef HAVE_RTREE_KEYS
  19. #include "rt_index.h"
  20. #include "rt_key.h"
  21. #include "rt_mbr.h"
  22. typedef struct
  23. {
  24.   double square;
  25.   int n_node;
  26.   uchar *key;
  27.   double *coords;
  28. } SplitStruct;
  29. inline static double *reserve_coords(double **d_buffer, int n_dim)
  30. {
  31.   double *coords = *d_buffer;
  32.   (*d_buffer) += n_dim * 2;
  33.   return coords;
  34. }
  35. static void mbr_join(double *a, const double *b, int n_dim)
  36. {
  37.   double *end = a + n_dim * 2;
  38.   do
  39.   {
  40.     if (a[0] > b[0])
  41.       a[0] = b[0];
  42.     if (a[1] < b[1])
  43.       a[1] = b[1];
  44.     a += 2;
  45.     b += 2;
  46.   }while (a != end);
  47. }
  48. /*
  49. Counts the square of mbr which is a join of a and b
  50. */
  51. static double mbr_join_square(const double *a, const double *b, int n_dim)
  52. {
  53.   const double *end = a + n_dim * 2;
  54.   double square = 1.0;
  55.   do
  56.   {
  57.     square *= 
  58.       ((a[1] < b[1]) ? b[1] : a[1]) - ((a[0] > b[0]) ? b[0] : a[0]);
  59.     a += 2;
  60.     b += 2;
  61.   }while (a != end);
  62.   return square;
  63. }
  64. static double count_square(const double *a, int n_dim)
  65. {
  66.   const double *end = a + n_dim * 2;
  67.   double square = 1.0;
  68.   do
  69.   {
  70.     square *= a[1] - a[0];
  71.     a += 2;
  72.   }while (a != end);
  73.   return square;
  74. }
  75. inline static void copy_coords(double *dst, const double *src, int n_dim)
  76. {
  77.   memcpy(dst, src, sizeof(double) * (n_dim * 2));
  78. }
  79. /* 
  80. Select two nodes to collect group upon
  81. */
  82. static void pick_seeds(SplitStruct *node, int n_entries, 
  83.      SplitStruct **seed_a, SplitStruct **seed_b, int n_dim)
  84. {
  85.   SplitStruct *cur1;
  86.   SplitStruct *lim1 = node + (n_entries - 1);
  87.   SplitStruct *cur2;
  88.   SplitStruct *lim2 = node + n_entries;
  89.   double max_d = -DBL_MAX;
  90.   double d;
  91.   for (cur1 = node; cur1 < lim1; ++cur1)
  92.   {
  93.     for (cur2=cur1 + 1; cur2 < lim2; ++cur2)
  94.     {
  95.       
  96.       d = mbr_join_square(cur1->coords, cur2->coords, n_dim) - cur1->square - 
  97.           cur2->square;
  98.       if (d > max_d)
  99.       {
  100.         max_d = d;
  101.         *seed_a = cur1;
  102.         *seed_b = cur2;
  103.       }
  104.     }
  105.   }
  106. }
  107. /* 
  108. Select next node and group where to add 
  109. */
  110. static void pick_next(SplitStruct *node, int n_entries, double *g1, double *g2,
  111.     SplitStruct **choice, int *n_group, int n_dim)
  112. {
  113.   SplitStruct *cur = node;
  114.   SplitStruct *end = node + n_entries;
  115.   double max_diff = -DBL_MAX;
  116.   for (; cur<end; ++cur)
  117.   {
  118.     double diff;
  119.     double abs_diff;
  120.     if (cur->n_node)
  121.     {
  122.       continue;
  123.     }
  124.     diff = mbr_join_square(g1, cur->coords, n_dim) -
  125.       mbr_join_square(g2, cur->coords, n_dim);
  126.     abs_diff = fabs(diff);
  127.     if (abs_diff  > max_diff)
  128.     {
  129.       max_diff = abs_diff;
  130.       *n_group = 1 + (diff > 0);
  131.       *choice = cur;
  132.     }
  133.   }
  134. }
  135. /*
  136. Mark not-in-group entries as n_group
  137. */
  138. static void mark_all_entries(SplitStruct *node, int n_entries, int n_group)
  139. {
  140.   SplitStruct *cur = node;
  141.   SplitStruct *end = node + n_entries;
  142.   for (; cur<end; ++cur)
  143.   {
  144.     if (cur->n_node)
  145.     {
  146.       continue;
  147.     }
  148.     cur->n_node = n_group;
  149.   }
  150. }
  151. static int split_rtree_node(SplitStruct *node, int n_entries, 
  152.                    int all_size, /* Total key's size */
  153.                    int key_size,
  154.                    int min_size, /* Minimal group size */
  155.                    int size1, int size2 /* initial group sizes */,
  156.                    double **d_buffer, int n_dim)
  157. {
  158.   SplitStruct *cur;
  159.   SplitStruct *a;
  160.   SplitStruct *b;
  161.   double *g1 = reserve_coords(d_buffer, n_dim);
  162.   double *g2 = reserve_coords(d_buffer, n_dim);
  163.   SplitStruct *next;
  164.   int next_node;
  165.   int i;
  166.   SplitStruct *end = node + n_entries;
  167.   if (all_size < min_size * 2)
  168.   {
  169.     return 1;
  170.   }
  171.   cur = node;
  172.   for (; cur<end; ++cur)
  173.   {
  174.     cur->square = count_square(cur->coords, n_dim);
  175.     cur->n_node = 0;
  176.   }
  177.   pick_seeds(node, n_entries, &a, &b, n_dim);
  178.   a->n_node = 1;
  179.   b->n_node = 2;
  180.   
  181.   copy_coords(g1, a->coords, n_dim);
  182.   size1 += key_size;
  183.   copy_coords(g2, b->coords, n_dim);
  184.   size2 += key_size;
  185.   for (i=n_entries - 2; i>0; --i)
  186.   {
  187.     if (all_size - (size2 + key_size) < min_size) /* Can't write into group 2 */
  188.     {
  189.       mark_all_entries(node, n_entries, 1);
  190.       break;
  191.     }
  192.     if (all_size - (size1 + key_size) < min_size) /* Can't write into group 1 */
  193.     {
  194.       mark_all_entries(node, n_entries, 2);
  195.       break;
  196.     }
  197.     pick_next(node, n_entries, g1, g2, &next, &next_node, n_dim);
  198.     if (next_node == 1)
  199.     {
  200.       size1 += key_size;
  201.       mbr_join(g1, next->coords, n_dim);
  202.     }
  203.     else
  204.     {
  205.       size2 += key_size;
  206.       mbr_join(g2, next->coords, n_dim);
  207.     }
  208.     next->n_node = next_node;
  209.   }
  210.   return 0;
  211. }
  212. int rtree_split_page(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *page, uchar *key, 
  213.                      uint key_length, my_off_t *new_page_offs)
  214. {
  215.   int n1, n2; /* Number of items in groups */
  216.   SplitStruct *task;
  217.   SplitStruct *cur;
  218.   SplitStruct *stop;
  219.   double *coord_buf;
  220.   double *next_coord;
  221.   double *old_coord;
  222.   int n_dim;
  223.   uchar *source_cur, *cur1, *cur2;
  224.   uchar *new_page;
  225.   int err_code = 0;
  226.   uint nod_flag = mi_test_if_nod(page);
  227.   uint full_length = key_length + (nod_flag ? nod_flag : 
  228.                                    info->s->base.rec_reflength);
  229.   int max_keys = (mi_getint(page)-2) / (full_length);
  230.   n_dim = keyinfo->keysegs / 2;
  231.   
  232.   if (!(coord_buf= (double*) my_alloca(n_dim * 2 * sizeof(double) *
  233.        (max_keys + 1 + 4) +
  234.        sizeof(SplitStruct) * (max_keys + 1))))
  235.     return -1;
  236.   task= (SplitStruct *)(coord_buf + n_dim * 2 * (max_keys + 1 + 4));
  237.   next_coord = coord_buf;
  238.  
  239.   stop = task + max_keys;
  240.   source_cur = rt_PAGE_FIRST_KEY(page, nod_flag);
  241.   for (cur = task; cur < stop; ++cur, source_cur = rt_PAGE_NEXT_KEY(source_cur, 
  242.        key_length, nod_flag))
  243.   {
  244.     cur->coords = reserve_coords(&next_coord, n_dim);
  245.     cur->key = source_cur;
  246.     rtree_d_mbr(keyinfo->seg, source_cur, key_length, cur->coords);
  247.   }
  248.   cur->coords = reserve_coords(&next_coord, n_dim);
  249.   rtree_d_mbr(keyinfo->seg, key, key_length, cur->coords);
  250.   cur->key = key;
  251.   old_coord = next_coord;
  252.   if (split_rtree_node(task, max_keys + 1,
  253.        mi_getint(page) + full_length + 2, full_length, 
  254.        rt_PAGE_MIN_SIZE(keyinfo->block_length),
  255.        2, 2, &next_coord, n_dim))
  256.   {
  257.     err_code = 1;
  258.     goto split_err;
  259.   }
  260.   if (!(new_page = (uchar*)my_alloca((uint)keyinfo->block_length)))
  261.   {
  262.     err_code= -1;
  263.     goto split_err;
  264.   }
  265.   
  266.   stop = task + (max_keys + 1);
  267.   cur1 = rt_PAGE_FIRST_KEY(page, nod_flag);
  268.   cur2 = rt_PAGE_FIRST_KEY(new_page, nod_flag);
  269.   n1 = 0;
  270.   n2 = 0;
  271.   for (cur = task; cur < stop; ++cur)
  272.   {
  273.     uchar *to;
  274.     if (cur->n_node == 1)
  275.     {
  276.       to = cur1;
  277.       cur1 = rt_PAGE_NEXT_KEY(cur1, key_length, nod_flag);
  278.       ++n1;
  279.     }
  280.     else
  281.     {
  282.       to = cur2;
  283.       cur2 = rt_PAGE_NEXT_KEY(cur2, key_length, nod_flag);
  284.       ++n2;
  285.     }
  286.     if (to != cur->key)
  287.       memcpy(to - nod_flag, cur->key - nod_flag, full_length);
  288.   }
  289.  
  290.   mi_putint(page, 2 + n1 * full_length, nod_flag);
  291.   mi_putint(new_page, 2 + n2 * full_length, nod_flag);
  292.   if ((*new_page_offs= _mi_new(info, keyinfo, DFLT_INIT_HITS)) == 
  293.                                                                HA_OFFSET_ERROR)
  294.     err_code= -1;
  295.   else
  296.     err_code= _mi_write_keypage(info, keyinfo, *new_page_offs,
  297.                                 DFLT_INIT_HITS, new_page);
  298.   my_afree((byte*)new_page);
  299. split_err:
  300.   my_afree((byte*) coord_buf);
  301.   return err_code;
  302. }
  303. #endif /*HAVE_RTREE_KEYS*/