← Back to branch summary

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

« back to all changes in this revision

Viewing changes to storage/ndb/src/kernel/blocks/dbtux/DbtuxSearch.cpp

  • 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/ndb/src/kernel/blocks/dbtux/DbtuxSearch.cpp
 
1
/* Copyright (C) 2003 MySQL AB
 
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
#define DBTUX_SEARCH_CPP
 
17
#include "Dbtux.hpp"
 
18
 
 
19
/*
 
20
 * Search for entry to add.
 
21
 *
 
22
 * Similar to searchToRemove (see below).
 
23
 */
 
24
bool
 
25
Dbtux::searchToAdd(Frag& frag, ConstData searchKey, TreeEnt searchEnt, TreePos& treePos)
 
26
{
 
27
  const TreeHead& tree = frag.m_tree;
 
28
  const unsigned numAttrs = frag.m_numAttrs;
 
29
  NodeHandle currNode(frag);
 
30
  currNode.m_loc = tree.m_root;
 
31
  if (currNode.m_loc == NullTupLoc) {
 
32
    // empty tree
 
33
    jam();
 
34
    return true;
 
35
  }
 
36
  NodeHandle glbNode(frag);     // potential g.l.b of final node
 
37
  /*
 
38
   * In order to not (yet) change old behaviour, a position between
 
39
   * 2 nodes returns the one at the bottom of the tree.
 
40
   */
 
41
  NodeHandle bottomNode(frag);
 
42
  while (true) {
 
43
    jam();
 
44
    selectNode(currNode, currNode.m_loc);
 
45
    int ret;
 
46
    // compare prefix
 
47
    unsigned start = 0;
 
48
    ret = cmpSearchKey(frag, start, searchKey, currNode.getPref(), tree.m_prefSize);
 
49
    if (ret == NdbSqlUtil::CmpUnknown) {
 
50
      jam();
 
51
      // read and compare remaining attributes
 
52
      ndbrequire(start < numAttrs);
 
53
      readKeyAttrs(frag, currNode.getMinMax(0), start, c_entryKey);
 
54
      ret = cmpSearchKey(frag, start, searchKey, c_entryKey);
 
55
      ndbrequire(ret != NdbSqlUtil::CmpUnknown);
 
56
    }
 
57
    if (ret == 0) {
 
58
      jam();
 
59
      // keys are equal, compare entry values
 
60
      ret = searchEnt.cmp(currNode.getMinMax(0));
 
61
    }
 
62
    if (ret < 0) {
 
63
      jam();
 
64
      const TupLoc loc = currNode.getLink(0);
 
65
      if (loc != NullTupLoc) {
 
66
        jam();
 
67
        // continue to left subtree
 
68
        currNode.m_loc = loc;
 
69
        continue;
 
70
      }
 
71
      if (! glbNode.isNull()) {
 
72
        jam();
 
73
        // move up to the g.l.b but remember the bottom node
 
74
        bottomNode = currNode;
 
75
        currNode = glbNode;
 
76
      }
 
77
    } else if (ret > 0) {
 
78
      jam();
 
79
      const TupLoc loc = currNode.getLink(1);
 
80
      if (loc != NullTupLoc) {
 
81
        jam();
 
82
        // save potential g.l.b
 
83
        glbNode = currNode;
 
84
        // continue to right subtree
 
85
        currNode.m_loc = loc;
 
86
        continue;
 
87
      }
 
88
    } else {
 
89
      jam();
 
90
      treePos.m_loc = currNode.m_loc;
 
91
      treePos.m_pos = 0;
 
92
      // entry found - error
 
93
      return false;
 
94
    }
 
95
    break;
 
96
  }
 
97
  // anticipate
 
98
  treePos.m_loc = currNode.m_loc;
 
99
  // binary search
 
100
  int lo = -1;
 
101
  int hi = currNode.getOccup();
 
102
  int ret;
 
103
  while (1) {
 
104
    jam();
 
105
    // hi - lo > 1 implies lo < j < hi
 
106
    int j = (hi + lo) / 2;
 
107
    // read and compare attributes
 
108
    unsigned start = 0;
 
109
    readKeyAttrs(frag, currNode.getEnt(j), start, c_entryKey);
 
110
    ret = cmpSearchKey(frag, start, searchKey, c_entryKey);
 
111
    ndbrequire(ret != NdbSqlUtil::CmpUnknown);
 
112
    if (ret == 0) {
 
113
      jam();
 
114
      // keys are equal, compare entry values
 
115
      ret = searchEnt.cmp(currNode.getEnt(j));
 
116
    }
 
117
    if (ret < 0)
 
118
      hi = j;
 
119
    else if (ret > 0)
 
120
      lo = j;
 
121
    else {
 
122
      treePos.m_pos = j;
 
123
      // entry found - error
 
124
      return false;
 
125
    }
 
126
    if (hi - lo == 1)
 
127
      break;
 
128
  }
 
129
  if (ret < 0) {
 
130
    jam();
 
131
    treePos.m_pos = hi;
 
132
    return true;
 
133
  }
 
134
  if ((uint) hi < currNode.getOccup()) {
 
135
    jam();
 
136
    treePos.m_pos = hi;
 
137
    return true;
 
138
  }
 
139
  if (bottomNode.isNull()) {
 
140
    jam();
 
141
    treePos.m_pos = hi;
 
142
    return true;
 
143
  }
 
144
  jam();
 
145
  // backwards compatible for now
 
146
  treePos.m_loc = bottomNode.m_loc;
 
147
  treePos.m_pos = 0;
 
148
  return true;
 
149
}
 
150
 
 
151
/*
 
152
 * Search for entry to remove.
 
153
 *
 
154
 * Compares search key to each node min.  A move to right subtree can
 
155
 * overshoot target node.  The last such node is saved.  The final node
 
156
 * is a semi-leaf or leaf.  If search key is less than final node min
 
157
 * then the saved node is the g.l.b of the final node and we move back
 
158
 * to it.
 
159
 */
 
160
bool
 
161
Dbtux::searchToRemove(Frag& frag, ConstData searchKey, TreeEnt searchEnt, TreePos& treePos)
 
162
{
 
163
  const TreeHead& tree = frag.m_tree;
 
164
  const unsigned numAttrs = frag.m_numAttrs;
 
165
  NodeHandle currNode(frag);
 
166
  currNode.m_loc = tree.m_root;
 
167
  if (currNode.m_loc == NullTupLoc) {
 
168
    // empty tree - failed
 
169
    jam();
 
170
    return false;
 
171
  }
 
172
  NodeHandle glbNode(frag);     // potential g.l.b of final node
 
173
  while (true) {
 
174
    jam();
 
175
    selectNode(currNode, currNode.m_loc);
 
176
    int ret;
 
177
    // compare prefix
 
178
    unsigned start = 0;
 
179
    ret = cmpSearchKey(frag, start, searchKey, currNode.getPref(), tree.m_prefSize);
 
180
    if (ret == NdbSqlUtil::CmpUnknown) {
 
181
      jam();
 
182
      // read and compare remaining attributes
 
183
      ndbrequire(start < numAttrs);
 
184
      readKeyAttrs(frag, currNode.getMinMax(0), start, c_entryKey);
 
185
      ret = cmpSearchKey(frag, start, searchKey, c_entryKey);
 
186
      ndbrequire(ret != NdbSqlUtil::CmpUnknown);
 
187
    }
 
188
    if (ret == 0) {
 
189
      jam();
 
190
      // keys are equal, compare entry values
 
191
      ret = searchEnt.cmp(currNode.getMinMax(0));
 
192
    }
 
193
    if (ret < 0) {
 
194
      jam();
 
195
      const TupLoc loc = currNode.getLink(0);
 
196
      if (loc != NullTupLoc) {
 
197
        jam();
 
198
        // continue to left subtree
 
199
        currNode.m_loc = loc;
 
200
        continue;
 
201
      }
 
202
      if (! glbNode.isNull()) {
 
203
        jam();
 
204
        // move up to the g.l.b
 
205
        currNode = glbNode;
 
206
      }
 
207
    } else if (ret > 0) {
 
208
      jam();
 
209
      const TupLoc loc = currNode.getLink(1);
 
210
      if (loc != NullTupLoc) {
 
211
        jam();
 
212
        // save potential g.l.b
 
213
        glbNode = currNode;
 
214
        // continue to right subtree
 
215
        currNode.m_loc = loc;
 
216
        continue;
 
217
      }
 
218
    } else {
 
219
      jam();
 
220
      treePos.m_loc = currNode.m_loc;
 
221
      treePos.m_pos = 0;
 
222
      return true;
 
223
    }
 
224
    break;
 
225
  }
 
226
  // anticipate
 
227
  treePos.m_loc = currNode.m_loc;
 
228
  // pos 0 was handled above
 
229
  for (unsigned j = 1, occup = currNode.getOccup(); j < occup; j++) {
 
230
    jam();
 
231
    // compare only the entry
 
232
    if (searchEnt.eq(currNode.getEnt(j))) {
 
233
      jam();
 
234
      treePos.m_pos = j;
 
235
      return true;
 
236
    }
 
237
  }
 
238
  treePos.m_pos = currNode.getOccup();
 
239
  // not found - failed
 
240
  return false;
 
241
}
 
242
 
 
243
/*
 
244
 * Search for scan start position.
 
245
 *
 
246
 * Similar to searchToAdd.  The routines differ somewhat depending on
 
247
 * scan direction and are done by separate methods.
 
248
 */
 
249
void
 
250
Dbtux::searchToScan(Frag& frag, ConstData boundInfo, unsigned boundCount, bool descending, TreePos& treePos)
 
251
{
 
252
  const TreeHead& tree = frag.m_tree;
 
253
  if (tree.m_root != NullTupLoc) {
 
254
    if (! descending)
 
255
      searchToScanAscending(frag, boundInfo, boundCount, treePos);
 
256
    else
 
257
      searchToScanDescending(frag, boundInfo, boundCount, treePos);
 
258
    return;
 
259
  }
 
260
  // empty tree
 
261
}
 
262
 
 
263
void
 
264
Dbtux::searchToScanAscending(Frag& frag, ConstData boundInfo, unsigned boundCount, TreePos& treePos)
 
265
{
 
266
  const TreeHead& tree = frag.m_tree;
 
267
  NodeHandle currNode(frag);
 
268
  currNode.m_loc = tree.m_root;
 
269
  NodeHandle glbNode(frag);     // potential g.l.b of final node
 
270
  NodeHandle bottomNode(frag);
 
271
  while (true) {
 
272
    jam();
 
273
    selectNode(currNode, currNode.m_loc);
 
274
    int ret;
 
275
    // compare prefix
 
276
    ret = cmpScanBound(frag, 0, boundInfo, boundCount, currNode.getPref(), tree.m_prefSize);
 
277
    if (ret == NdbSqlUtil::CmpUnknown) {
 
278
      jam();
 
279
      // read and compare all attributes
 
280
      readKeyAttrs(frag, currNode.getMinMax(0), 0, c_entryKey);
 
281
      ret = cmpScanBound(frag, 0, boundInfo, boundCount, c_entryKey);
 
282
      ndbrequire(ret != NdbSqlUtil::CmpUnknown);
 
283
    }
 
284
    if (ret < 0) {
 
285
      // bound is left of this node
 
286
      jam();
 
287
      const TupLoc loc = currNode.getLink(0);
 
288
      if (loc != NullTupLoc) {
 
289
        jam();
 
290
        // continue to left subtree
 
291
        currNode.m_loc = loc;
 
292
        continue;
 
293
      }
 
294
      if (! glbNode.isNull()) {
 
295
        jam();
 
296
        // move up to the g.l.b but remember the bottom node
 
297
        bottomNode = currNode;
 
298
        currNode = glbNode;
 
299
      } else {
 
300
        // start scanning this node
 
301
        treePos.m_loc = currNode.m_loc;
 
302
        treePos.m_pos = 0;
 
303
        treePos.m_dir = 3;
 
304
        return;
 
305
      }
 
306
    } else {
 
307
      // bound is at or right of this node
 
308
      jam();
 
309
      const TupLoc loc = currNode.getLink(1);
 
310
      if (loc != NullTupLoc) {
 
311
        jam();
 
312
        // save potential g.l.b
 
313
        glbNode = currNode;
 
314
        // continue to right subtree
 
315
        currNode.m_loc = loc;
 
316
        continue;
 
317
      }
 
318
    }
 
319
    break;
 
320
  }
 
321
  for (unsigned j = 0, occup = currNode.getOccup(); j < occup; j++) {
 
322
    jam();
 
323
    int ret;
 
324
    // read and compare attributes
 
325
    readKeyAttrs(frag, currNode.getEnt(j), 0, c_entryKey);
 
326
    ret = cmpScanBound(frag, 0, boundInfo, boundCount, c_entryKey);
 
327
    ndbrequire(ret != NdbSqlUtil::CmpUnknown);
 
328
    if (ret < 0) {
 
329
      // found first entry satisfying the bound
 
330
      treePos.m_loc = currNode.m_loc;
 
331
      treePos.m_pos = j;
 
332
      treePos.m_dir = 3;
 
333
      return;
 
334
    }
 
335
  }
 
336
  // bound is to right of this node
 
337
  if (! bottomNode.isNull()) {
 
338
    jam();
 
339
    // start scanning the l.u.b
 
340
    treePos.m_loc = bottomNode.m_loc;
 
341
    treePos.m_pos = 0;
 
342
    treePos.m_dir = 3;
 
343
    return;
 
344
  }
 
345
  // start scanning upwards (pretend we came from right child)
 
346
  treePos.m_loc = currNode.m_loc;
 
347
  treePos.m_dir = 1;
 
348
}
 
349
 
 
350
void
 
351
Dbtux::searchToScanDescending(Frag& frag, ConstData boundInfo, unsigned boundCount, TreePos& treePos)
 
352
{
 
353
  const TreeHead& tree = frag.m_tree;
 
354
  NodeHandle currNode(frag);
 
355
  currNode.m_loc = tree.m_root;
 
356
  NodeHandle glbNode(frag);     // potential g.l.b of final node
 
357
  NodeHandle bottomNode(frag);
 
358
  while (true) {
 
359
    jam();
 
360
    selectNode(currNode, currNode.m_loc);
 
361
    int ret;
 
362
    // compare prefix
 
363
    ret = cmpScanBound(frag, 1, boundInfo, boundCount, currNode.getPref(), tree.m_prefSize);
 
364
    if (ret == NdbSqlUtil::CmpUnknown) {
 
365
      jam();
 
366
      // read and compare all attributes
 
367
      readKeyAttrs(frag, currNode.getMinMax(0), 0, c_entryKey);
 
368
      ret = cmpScanBound(frag, 1, boundInfo, boundCount, c_entryKey);
 
369
      ndbrequire(ret != NdbSqlUtil::CmpUnknown);
 
370
    }
 
371
    if (ret < 0) {
 
372
      // bound is left of this node
 
373
      jam();
 
374
      const TupLoc loc = currNode.getLink(0);
 
375
      if (loc != NullTupLoc) {
 
376
        jam();
 
377
        // continue to left subtree
 
378
        currNode.m_loc = loc;
 
379
        continue;
 
380
      }
 
381
      if (! glbNode.isNull()) {
 
382
        jam();
 
383
        // move up to the g.l.b but remember the bottom node
 
384
        bottomNode = currNode;
 
385
        currNode = glbNode;
 
386
      } else {
 
387
        // empty result set
 
388
        return;
 
389
      }
 
390
    } else {
 
391
      // bound is at or right of this node
 
392
      jam();
 
393
      const TupLoc loc = currNode.getLink(1);
 
394
      if (loc != NullTupLoc) {
 
395
        jam();
 
396
        // save potential g.l.b
 
397
        glbNode = currNode;
 
398
        // continue to right subtree
 
399
        currNode.m_loc = loc;
 
400
        continue;
 
401
      }
 
402
    }
 
403
    break;
 
404
  }
 
405
  for (unsigned j = 0, occup = currNode.getOccup(); j < occup; j++) {
 
406
    jam();
 
407
    int ret;
 
408
    // read and compare attributes
 
409
    readKeyAttrs(frag, currNode.getEnt(j), 0, c_entryKey);
 
410
    ret = cmpScanBound(frag, 1, boundInfo, boundCount, c_entryKey);
 
411
    ndbrequire(ret != NdbSqlUtil::CmpUnknown);
 
412
    if (ret < 0) {
 
413
      if (j > 0) {
 
414
        // start scanning from previous entry
 
415
        treePos.m_loc = currNode.m_loc;
 
416
        treePos.m_pos = j - 1;
 
417
        treePos.m_dir = 3;
 
418
        return;
 
419
      }
 
420
      // start scanning upwards (pretend we came from left child)
 
421
      treePos.m_loc = currNode.m_loc;
 
422
      treePos.m_pos = 0;
 
423
      treePos.m_dir = 0;
 
424
      return;
 
425
    }
 
426
  }
 
427
  // start scanning this node
 
428
  treePos.m_loc = currNode.m_loc;
 
429
  treePos.m_pos = currNode.getOccup() - 1;
 
430
  treePos.m_dir = 3;
 
431
}