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