rt_split.c
上传用户:romrleung
上传日期:2022-05-23
资源大小:18897k
文件大小:8k
- /* Copyright (C) 2000 MySQL AB & Alexey Botchkov & MySQL Finland AB
- & TCX DataKonsult 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; either version 2 of the License, or
- (at your option) any later version.
-
- 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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */
- #include "myisamdef.h"
- #ifdef HAVE_RTREE_KEYS
- #include "rt_index.h"
- #include "rt_key.h"
- #include "rt_mbr.h"
- typedef struct
- {
- double square;
- int n_node;
- uchar *key;
- double *coords;
- } SplitStruct;
- inline static double *reserve_coords(double **d_buffer, int n_dim)
- {
- double *coords = *d_buffer;
- (*d_buffer) += n_dim * 2;
- return coords;
- }
- static void mbr_join(double *a, const double *b, int n_dim)
- {
- double *end = a + n_dim * 2;
- do
- {
- if (a[0] > b[0])
- a[0] = b[0];
- if (a[1] < b[1])
- a[1] = b[1];
- a += 2;
- b += 2;
- }while (a != end);
- }
- /*
- Counts the square of mbr which is a join of a and b
- */
- static double mbr_join_square(const double *a, const double *b, int n_dim)
- {
- const double *end = a + n_dim * 2;
- double square = 1.0;
- do
- {
- square *=
- ((a[1] < b[1]) ? b[1] : a[1]) - ((a[0] > b[0]) ? b[0] : a[0]);
- a += 2;
- b += 2;
- }while (a != end);
- return square;
- }
- static double count_square(const double *a, int n_dim)
- {
- const double *end = a + n_dim * 2;
- double square = 1.0;
- do
- {
- square *= a[1] - a[0];
- a += 2;
- }while (a != end);
- return square;
- }
- inline static void copy_coords(double *dst, const double *src, int n_dim)
- {
- memcpy(dst, src, sizeof(double) * (n_dim * 2));
- }
- /*
- Select two nodes to collect group upon
- */
- static void pick_seeds(SplitStruct *node, int n_entries,
- SplitStruct **seed_a, SplitStruct **seed_b, int n_dim)
- {
- SplitStruct *cur1;
- SplitStruct *lim1 = node + (n_entries - 1);
- SplitStruct *cur2;
- SplitStruct *lim2 = node + n_entries;
- double max_d = -DBL_MAX;
- double d;
- for (cur1 = node; cur1 < lim1; ++cur1)
- {
- for (cur2=cur1 + 1; cur2 < lim2; ++cur2)
- {
-
- d = mbr_join_square(cur1->coords, cur2->coords, n_dim) - cur1->square -
- cur2->square;
- if (d > max_d)
- {
- max_d = d;
- *seed_a = cur1;
- *seed_b = cur2;
- }
- }
- }
- }
- /*
- Select next node and group where to add
- */
- static void pick_next(SplitStruct *node, int n_entries, double *g1, double *g2,
- SplitStruct **choice, int *n_group, int n_dim)
- {
- SplitStruct *cur = node;
- SplitStruct *end = node + n_entries;
- double max_diff = -DBL_MAX;
- for (; cur<end; ++cur)
- {
- double diff;
- double abs_diff;
- if (cur->n_node)
- {
- continue;
- }
- diff = mbr_join_square(g1, cur->coords, n_dim) -
- mbr_join_square(g2, cur->coords, n_dim);
- abs_diff = fabs(diff);
- if (abs_diff > max_diff)
- {
- max_diff = abs_diff;
- *n_group = 1 + (diff > 0);
- *choice = cur;
- }
- }
- }
- /*
- Mark not-in-group entries as n_group
- */
- static void mark_all_entries(SplitStruct *node, int n_entries, int n_group)
- {
- SplitStruct *cur = node;
- SplitStruct *end = node + n_entries;
- for (; cur<end; ++cur)
- {
- if (cur->n_node)
- {
- continue;
- }
- cur->n_node = n_group;
- }
- }
- static int split_rtree_node(SplitStruct *node, int n_entries,
- int all_size, /* Total key's size */
- int key_size,
- int min_size, /* Minimal group size */
- int size1, int size2 /* initial group sizes */,
- double **d_buffer, int n_dim)
- {
- SplitStruct *cur;
- SplitStruct *a;
- SplitStruct *b;
- double *g1 = reserve_coords(d_buffer, n_dim);
- double *g2 = reserve_coords(d_buffer, n_dim);
- SplitStruct *next;
- int next_node;
- int i;
- SplitStruct *end = node + n_entries;
- if (all_size < min_size * 2)
- {
- return 1;
- }
- cur = node;
- for (; cur<end; ++cur)
- {
- cur->square = count_square(cur->coords, n_dim);
- cur->n_node = 0;
- }
- pick_seeds(node, n_entries, &a, &b, n_dim);
- a->n_node = 1;
- b->n_node = 2;
-
- copy_coords(g1, a->coords, n_dim);
- size1 += key_size;
- copy_coords(g2, b->coords, n_dim);
- size2 += key_size;
- for (i=n_entries - 2; i>0; --i)
- {
- if (all_size - (size2 + key_size) < min_size) /* Can't write into group 2 */
- {
- mark_all_entries(node, n_entries, 1);
- break;
- }
- if (all_size - (size1 + key_size) < min_size) /* Can't write into group 1 */
- {
- mark_all_entries(node, n_entries, 2);
- break;
- }
- pick_next(node, n_entries, g1, g2, &next, &next_node, n_dim);
- if (next_node == 1)
- {
- size1 += key_size;
- mbr_join(g1, next->coords, n_dim);
- }
- else
- {
- size2 += key_size;
- mbr_join(g2, next->coords, n_dim);
- }
- next->n_node = next_node;
- }
- return 0;
- }
- int rtree_split_page(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *page, uchar *key,
- uint key_length, my_off_t *new_page_offs)
- {
- int n1, n2; /* Number of items in groups */
- SplitStruct *task;
- SplitStruct *cur;
- SplitStruct *stop;
- double *coord_buf;
- double *next_coord;
- double *old_coord;
- int n_dim;
- uchar *source_cur, *cur1, *cur2;
- uchar *new_page;
- int err_code = 0;
- uint nod_flag = mi_test_if_nod(page);
- uint full_length = key_length + (nod_flag ? nod_flag :
- info->s->base.rec_reflength);
- int max_keys = (mi_getint(page)-2) / (full_length);
- n_dim = keyinfo->keysegs / 2;
-
- if (!(coord_buf= (double*) my_alloca(n_dim * 2 * sizeof(double) *
- (max_keys + 1 + 4) +
- sizeof(SplitStruct) * (max_keys + 1))))
- return -1;
- task= (SplitStruct *)(coord_buf + n_dim * 2 * (max_keys + 1 + 4));
- next_coord = coord_buf;
-
- stop = task + max_keys;
- source_cur = rt_PAGE_FIRST_KEY(page, nod_flag);
- for (cur = task; cur < stop; ++cur, source_cur = rt_PAGE_NEXT_KEY(source_cur,
- key_length, nod_flag))
- {
- cur->coords = reserve_coords(&next_coord, n_dim);
- cur->key = source_cur;
- rtree_d_mbr(keyinfo->seg, source_cur, key_length, cur->coords);
- }
- cur->coords = reserve_coords(&next_coord, n_dim);
- rtree_d_mbr(keyinfo->seg, key, key_length, cur->coords);
- cur->key = key;
- old_coord = next_coord;
- if (split_rtree_node(task, max_keys + 1,
- mi_getint(page) + full_length + 2, full_length,
- rt_PAGE_MIN_SIZE(keyinfo->block_length),
- 2, 2, &next_coord, n_dim))
- {
- err_code = 1;
- goto split_err;
- }
- if (!(new_page = (uchar*)my_alloca((uint)keyinfo->block_length)))
- {
- err_code= -1;
- goto split_err;
- }
-
- stop = task + (max_keys + 1);
- cur1 = rt_PAGE_FIRST_KEY(page, nod_flag);
- cur2 = rt_PAGE_FIRST_KEY(new_page, nod_flag);
- n1 = 0;
- n2 = 0;
- for (cur = task; cur < stop; ++cur)
- {
- uchar *to;
- if (cur->n_node == 1)
- {
- to = cur1;
- cur1 = rt_PAGE_NEXT_KEY(cur1, key_length, nod_flag);
- ++n1;
- }
- else
- {
- to = cur2;
- cur2 = rt_PAGE_NEXT_KEY(cur2, key_length, nod_flag);
- ++n2;
- }
- if (to != cur->key)
- memcpy(to - nod_flag, cur->key - nod_flag, full_length);
- }
-
- mi_putint(page, 2 + n1 * full_length, nod_flag);
- mi_putint(new_page, 2 + n2 * full_length, nod_flag);
- if ((*new_page_offs= _mi_new(info, keyinfo, DFLT_INIT_HITS)) ==
- HA_OFFSET_ERROR)
- err_code= -1;
- else
- err_code= _mi_write_keypage(info, keyinfo, *new_page_offs,
- DFLT_INIT_HITS, new_page);
- my_afree((byte*)new_page);
- split_err:
- my_afree((byte*) coord_buf);
- return err_code;
- }
- #endif /*HAVE_RTREE_KEYS*/