← Back to branch summary

~ubuntu-branches/ubuntu/precise/mysql-5.1/precise

« back to all changes in this revision

Viewing changes to storage/myisam/rt_split.c

  • Committer: Bazaar Package Importer
  • Author(s): Norbert Tretkowski
  • Date: 2010-03-17 14:56:02 UTC
  • Revision ID: james.westby@ubuntu.com-20100317145602-x7e30l1b2sb5s6w6
Tags: upstream-5.1.45
Import upstream version 5.1.45

Show diffs side-by-side

added added

removed removed

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