summaryrefslogtreecommitdiffstats
path: root/storage/myisam/rt_split.c
diff options
context:
space:
mode:
Diffstat (limited to 'storage/myisam/rt_split.c')
-rw-r--r--storage/myisam/rt_split.c348
1 files changed, 348 insertions, 0 deletions
diff --git a/storage/myisam/rt_split.c b/storage/myisam/rt_split.c
new file mode 100644
index 00000000..1adcdb8e
--- /dev/null
+++ b/storage/myisam/rt_split.c
@@ -0,0 +1,348 @@
+/*
+ Copyright (c) 2002, 2015, Oracle and/or its affiliates
+
+ 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 St, Fifth Floor, Boston, MA 02110-1335 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);
+
+ /* Check if not finite (i.e. infinity or NaN) */
+ if (!isfinite(square))
+ square = DBL_MAX;
+
+ 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;
+
+ *seed_a = node;
+ *seed_b = node + 1;
+
+ 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 *UNINIT_VAR(a), *UNINIT_VAR(b);
+ double *g1 = reserve_coords(d_buffer, n_dim);
+ double *g2 = reserve_coords(d_buffer, n_dim);
+ SplitStruct *UNINIT_VAR(next);
+ int UNINIT_VAR(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;
+ int n_dim;
+ uchar *source_cur, *cur1, *cur2;
+ uchar *new_page= info->buff;
+ 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);
+ DBUG_ENTER("rtree_split_page");
+ DBUG_PRINT("rtree", ("splitting block"));
+
+ 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))))
+ DBUG_RETURN(-1); /* purecov: inspected */
+
+ 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;
+
+ 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;
+ }
+
+ info->buff_used= 1;
+ stop = task + (max_keys + 1);
+ cur1 = rt_PAGE_FIRST_KEY(page, nod_flag);
+ cur2 = rt_PAGE_FIRST_KEY(new_page, nod_flag);
+
+ n1= 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);
+ DBUG_PRINT("rtree", ("split new block: %lu", (ulong) *new_page_offs));
+
+split_err:
+ my_afree((uchar*) coord_buf);
+ DBUG_RETURN(err_code);
+}
+
+#endif /*HAVE_RTREE_KEYS*/
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-28 15:31:32 +0000