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