1 /******************************************************************************* 2 * Copyright (c) 2005, 2016 QNX Software Systems and others. 3 * 4 * This program and the accompanying materials 5 * are made available under the terms of the Eclipse Public License 2.0 6 * which accompanies this distribution, and is available at 7 * https://www.eclipse.org/legal/epl-2.0/ 8 * 9 * SPDX-License-Identifier: EPL-2.0 10 * 11 * Contributors: 12 * QNX - Initial API and implementation 13 * Andrew Ferguson (Symbian) - Provide B-tree deletion routine 14 * Markus Schorn (Wind River Systems) 15 *******************************************************************************/ 16 package org.eclipse.jdt.internal.core.nd.db; 17 18 import java.text.MessageFormat; 19 20 import org.eclipse.core.runtime.IStatus; 21 import org.eclipse.core.runtime.Status; 22 import org.eclipse.jdt.core.JavaCore; 23 import org.eclipse.jdt.internal.core.nd.AbstractTypeFactory; 24 import org.eclipse.jdt.internal.core.nd.ITypeFactory; 25 import org.eclipse.jdt.internal.core.nd.Nd; 26 27 /** 28 * Implements B-Tree search structure. 29 */ 30 public class BTree { 31 private static final int DEFAULT_DEGREE = 8; 32 // Constants for internal deletion routine (see deleteImp doc). 33 private static final int DELMODE_NORMAL = 0; 34 private static final int DELMODE_DELETE_MINIMUM = 1; 35 private static final int DELMODE_DELETE_MAXIMUM = 2; 36 37 public static final int RECORD_SIZE = Database.PTR_SIZE; 38 39 private final Nd nd; 40 protected final Database db; 41 protected final long rootPointer; 42 43 protected final int degree; 44 protected final int maxRecords; 45 protected final int maxChildren; 46 protected final int minRecords; 47 protected final int offsetChildren; 48 protected final int medianRecord; 49 50 protected final IBTreeComparator cmp; 51 BTree(Nd nd, long rootPointer, IBTreeComparator cmp)52 public BTree(Nd nd, long rootPointer, IBTreeComparator cmp) { 53 this(nd, rootPointer, DEFAULT_DEGREE, cmp); 54 } 55 56 /** 57 * Constructor. 58 * 59 * @param nd the database containing the btree 60 * @param rootPointer offset into database of the pointer to the root node 61 */ BTree(Nd nd, long rootPointer, int degree, IBTreeComparator cmp)62 public BTree(Nd nd, long rootPointer, int degree, IBTreeComparator cmp) { 63 this.nd = nd; 64 if (degree < 2) 65 throw new IllegalArgumentException("Illegal degree " + degree + " in tree"); //$NON-NLS-1$ //$NON-NLS-2$ 66 67 this.db = nd.getDB(); 68 this.rootPointer = rootPointer; 69 this.cmp = cmp; 70 71 this.degree = degree; 72 this.minRecords = this.degree - 1; 73 this.maxRecords = 2*this.degree - 1; 74 this.maxChildren = 2*this.degree; 75 this.offsetChildren = this.maxRecords * Database.INT_SIZE; 76 this.medianRecord = this.degree - 1; 77 } 78 getFactory(final IBTreeComparator cmp)79 public static ITypeFactory<BTree> getFactory(final IBTreeComparator cmp) { 80 return getFactory(8, cmp); 81 } 82 getFactory(final int degree, final IBTreeComparator cmp)83 public static ITypeFactory<BTree> getFactory(final int degree, final IBTreeComparator cmp) { 84 return new AbstractTypeFactory<BTree>() { 85 @Override 86 public BTree create(Nd dom, long address) { 87 return new BTree(dom, address, degree, cmp); 88 } 89 90 @Override 91 public int getRecordSize() { 92 return RECORD_SIZE; 93 } 94 95 @Override 96 public Class<?> getElementClass() { 97 return BTree.class; 98 } 99 100 @Override 101 public void destruct(Nd dom, long address) { 102 destructFields(dom, address); 103 } 104 105 @Override 106 public void destructFields(Nd dom, long address) { 107 create(dom, address).destruct(); 108 } 109 }; 110 } 111 112 protected long getRoot() throws IndexException { 113 return this.db.getRecPtr(this.rootPointer); 114 } 115 116 protected final void putRecord(Chunk chunk, long node, int index, long record) { 117 chunk.putRecPtr(node + index * Database.INT_SIZE, record); 118 } 119 120 protected final long getRecord(Chunk chunk, long node, int index) { 121 return chunk.getRecPtr(node + index * Database.INT_SIZE); 122 } 123 124 protected final void putChild(Chunk chunk, long node, int index, long child) { 125 chunk.putRecPtr(node + this.offsetChildren + index * Database.INT_SIZE, child); 126 } 127 128 protected final long getChild(Chunk chunk, long node, int index) { 129 return chunk.getRecPtr(node + this.offsetChildren + index * Database.INT_SIZE); 130 } 131 132 public void destruct() { 133 long root = getRoot(); 134 135 if (root == 0) { 136 return; 137 } 138 139 deallocateChildren(root); 140 } 141 142 private void deallocateChildren(long record) { 143 Chunk chunk = this.db.getChunk(record); 144 145 // Copy all the children pointers to an array of longs so all the reads will happen on the same chunk 146 // consecutively 147 long[] children = new long[this.maxRecords + 1]; 148 149 for (int idx = 0; idx < children.length; idx++) { 150 children[idx] = getChild(chunk, record, idx); 151 } 152 153 this.db.free(record, Database.POOL_BTREE); 154 155 chunk = null; 156 157 for (long nextChild : children) { 158 if (nextChild != 0) { 159 deallocateChildren(nextChild); 160 } 161 } 162 } 163 164 /** 165 * Inserts the record into the b-tree. We don't insert if the key was already there, 166 * in which case we return the record that matched. In other cases, we just return 167 * the record back. 168 * 169 * @param record offset of the record 170 */ 171 public long insert(long record) throws IndexException { 172 long root = getRoot(); 173 174 // Is this our first time in. 175 if (root == 0) { 176 firstInsert(record); 177 return record; 178 } 179 180 return insert(null, 0, 0, root, record); 181 } 182 183 private long insert(Chunk pChunk, long parent, int iParent, long node, long record) throws IndexException { 184 Chunk chunk = this.db.getChunk(node); 185 186 // If this node is full (last record isn't null), split it. 187 if (getRecord(chunk, node, this.maxRecords - 1) != 0) { 188 long median = getRecord(chunk, node, this.medianRecord); 189 if (median == record) { 190 // Found it, never mind. 191 return median; 192 } else { 193 chunk.makeDirty(); 194 // Split it. 195 // Create the new node and move the larger records over. 196 long newnode = allocateNode(); 197 Chunk newchunk = this.db.getChunk(newnode); 198 for (int i = 0; i < this.medianRecord; ++i) { 199 putRecord(newchunk, newnode, i, getRecord(chunk, node, this.medianRecord + 1 + i)); 200 putRecord(chunk, node, this.medianRecord + 1 + i, 0); 201 putChild(newchunk, newnode, i, getChild(chunk, node, this.medianRecord + 1 + i)); 202 putChild(chunk, node, this.medianRecord + 1 + i, 0); 203 } 204 putChild(newchunk, newnode, this.medianRecord, getChild(chunk, node, this.maxRecords)); 205 putChild(chunk, node, this.maxRecords, 0); 206 207 if (parent == 0) { 208 // Create a new root 209 parent = allocateNode(); 210 pChunk = this.db.getChunk(parent); 211 this.db.putRecPtr(this.rootPointer, parent); 212 putChild(pChunk, parent, 0, node); 213 } else { 214 // Insert the median into the parent. 215 for (int i = this.maxRecords - 2; i >= iParent; --i) { 216 long r = getRecord(pChunk, parent, i); 217 if (r != 0) { 218 // Re-fetch pChunk since we can only dirty the page that was fetched most recently from 219 // the database (anything fetched earlier may have been paged out) 220 pChunk = pChunk.getWritableChunk(); 221 putRecord(pChunk, parent, i + 1, r); 222 putChild(pChunk, parent, i + 2, getChild(pChunk, parent, i + 1)); 223 } 224 } 225 } 226 pChunk = pChunk.getWritableChunk(); 227 putRecord(pChunk, parent, iParent, median); 228 putChild(pChunk, parent, iParent + 1, newnode); 229 230 putRecord(chunk, node, this.medianRecord, 0); 231 232 // Set the node to the correct one to follow. 233 if (this.cmp.compare(this.nd, record, median) > 0) { 234 node = newnode; 235 chunk = newchunk; 236 } 237 } 238 } 239 240 // Binary search to find the insert point. 241 int lower= 0; 242 int upper= this.maxRecords - 1; 243 while (lower < upper && getRecord(chunk, node, upper - 1) == 0) { 244 upper--; 245 } 246 247 while (lower < upper) { 248 int middle= (lower + upper) / 2; 249 long checkRec= getRecord(chunk, node, middle); 250 if (checkRec == 0) { 251 upper= middle; 252 } else { 253 int compare= this.cmp.compare(this.nd, checkRec, record); 254 if (compare > 0) { 255 upper= middle; 256 } else if (compare < 0) { 257 lower= middle + 1; 258 } else { 259 // Found it, no insert, just return the matched record. 260 return checkRec; 261 } 262 } 263 } 264 265 // Note that the call to compare, above, may have paged out and reallocated the chunk so fetch it again now. 266 chunk = this.db.getChunk(node); 267 final int i= lower; 268 long child = getChild(chunk, node, i); 269 if (child != 0) { 270 // Visit the children. 271 return insert(chunk, node, i, child, record); 272 } else { 273 // We are at the leaf, add us in. 274 // First copy everything after over one. 275 for (int j = this.maxRecords - 2; j >= i; --j) { 276 long r = getRecord(chunk, node, j); 277 if (r != 0) 278 putRecord(chunk, node, j + 1, r); 279 } 280 putRecord(chunk, node, i, record); 281 return record; 282 } 283 } 284 285 private void firstInsert(long record) throws IndexException { 286 // Create the node and save it as root. 287 long root = allocateNode(); 288 this.db.putRecPtr(this.rootPointer, root); 289 // Put the record in the first slot of the node. 290 putRecord(this.db.getChunk(root), root, 0, record); 291 } 292 293 private long allocateNode() throws IndexException { 294 return this.db.malloc((2 * this.maxRecords + 1) * Database.INT_SIZE, Database.POOL_BTREE); 295 } 296 297 /** 298 * Deletes the specified record from the B-tree. 299 * <p> 300 * If the specified record is not present then this routine has no effect. 301 * <p> 302 * Specifying a record r for which there is another record q existing in the B-tree 303 * where cmp.compare(r,q)==0 && r!=q will also have no effect 304 * <p> 305 * N.B. The record is not deleted itself - its storage is not deallocated. 306 * The reference to the record in the btree is deleted. 307 * 308 * @param record the record to delete 309 * @throws IndexException 310 */ 311 public void delete(long record) throws IndexException { 312 try { 313 deleteImp(record, getRoot(), DELMODE_NORMAL); 314 } catch (BTreeKeyNotFoundException e) { 315 // Contract of this method is to NO-OP upon this event. 316 } 317 } 318 319 private class BTreeKeyNotFoundException extends Exception { 320 private static final long serialVersionUID = 9065438266175091670L; 321 public BTreeKeyNotFoundException(String msg) { 322 super(msg); 323 } 324 } 325 326 /** 327 * Used in implementation of delete routines 328 */ 329 private class BTNode { 330 final long node; 331 final int keyCount; 332 Chunk chunk; 333 334 BTNode(long node) throws IndexException { 335 this.node = node; 336 this.chunk = BTree.this.db.getChunk(node); 337 int i= 0; 338 while (i < BTree.this.maxRecords && getRecord(this.chunk, node, i) != 0) 339 i++; 340 this.keyCount = i; 341 } 342 343 BTNode getChild(int index) throws IndexException { 344 if (0 <= index && index < BTree.this.maxChildren) { 345 long child = BTree.this.getChild(this.chunk, this.node, index); 346 if (child != 0) 347 return new BTNode(child); 348 } 349 return null; 350 } 351 352 public void makeWritable() { 353 this.chunk = this.chunk.getWritableChunk(); 354 } 355 } 356 357 /** 358 * Implementation for deleting a key/record from the B-tree. 359 * <p> 360 * There is no distinction between keys and records. 361 * <p> 362 * This implements a single downward pass (with minor exceptions) deletion 363 * <p> 364 * @param key the address of the record to delete 365 * @param nodeRecord a node that (directly or indirectly) contains the specified key/record 366 * @param mode one of DELMODE_NORMAL, DELMODE_DELETE_MINIMUM, DELMODE_DELETE_MAXIMUM 367 * where DELMODE_NORMAL: locates the specified key/record using the comparator provided 368 * DELMODE_DELETE_MINIMUM: locates and deletes the minimum element in the subtree rooted at nodeRecord 369 * DELMODE_DELETE_MAXIMUM: locates and deletes the maximum element in the subtree rooted at nodeRecord 370 * @return the address of the record removed from the B-tree 371 * @throws IndexException 372 */ 373 private long deleteImp(long key, long nodeRecord, int mode) 374 throws IndexException, BTreeKeyNotFoundException { 375 BTNode node = new BTNode(nodeRecord); 376 377 // Determine index of key in current node, or -1 if its not in this node. 378 int keyIndexInNode = -1; 379 if (mode == DELMODE_NORMAL) 380 for (int i= 0; i < node.keyCount; i++) 381 if (getRecord(node.chunk, node.node, i) == key) { 382 keyIndexInNode = i; 383 break; 384 } 385 386 if (getChild(node.chunk, node.node, 0) == 0) { 387 /* Case 1: leaf node containing the key (by method precondition) */ 388 if (keyIndexInNode != -1) { 389 nodeContentDelete(node, keyIndexInNode, 1); 390 return key; 391 } else { 392 if (mode == DELMODE_DELETE_MINIMUM) { 393 long subst = getRecord(node.chunk, node.node, 0); 394 nodeContentDelete(node, 0, 1); 395 return subst; 396 } else if (mode == DELMODE_DELETE_MAXIMUM) { 397 long subst = getRecord(node.chunk, node.node, node.keyCount - 1); 398 nodeContentDelete(node, node.keyCount - 1, 1); 399 return subst; 400 } 401 throw new BTreeKeyNotFoundException("Deletion on absent key " + key + ", mode = " + mode); //$NON-NLS-1$//$NON-NLS-2$ 402 } 403 } else { 404 if (keyIndexInNode != -1) { 405 /* Case 2: non-leaf node which contains the key itself */ 406 407 BTNode succ = node.getChild(keyIndexInNode + 1); 408 if (succ != null && succ.keyCount > this.minRecords) { 409 node.makeWritable(); 410 /* Case 2a: Delete key by overwriting it with its successor (which occurs in a leaf node) */ 411 long subst = deleteImp(-1, succ.node, DELMODE_DELETE_MINIMUM); 412 putRecord(node.chunk, node.node, keyIndexInNode, subst); 413 return key; 414 } 415 416 BTNode pred = node.getChild(keyIndexInNode); 417 if (pred != null && pred.keyCount > this.minRecords) { 418 node.makeWritable(); 419 /* Case 2b: Delete key by overwriting it with its predecessor (which occurs in a leaf node) */ 420 long subst = deleteImp(-1, pred.node, DELMODE_DELETE_MAXIMUM); 421 putRecord(node.chunk, node.node, keyIndexInNode, subst); 422 return key; 423 } 424 425 /* Case 2c: Merge successor and predecessor */ 426 // assert(pred != null && succ != null); 427 if (pred != null) { 428 succ.makeWritable(); 429 node.makeWritable(); 430 pred.makeWritable(); 431 mergeNodes(succ, node, keyIndexInNode, pred); 432 return deleteImp(key, pred.node, mode); 433 } 434 return key; 435 } else { 436 /* Case 3: non-leaf node which does not itself contain the key */ 437 438 /* Determine root of subtree that should contain the key */ 439 int subtreeIndex; 440 switch(mode) { 441 case DELMODE_NORMAL: 442 subtreeIndex = node.keyCount; 443 for (int i= 0; i < node.keyCount; i++) 444 if (this.cmp.compare(this.nd, getRecord(node.chunk, node.node, i), key)>0) { 445 subtreeIndex = i; 446 break; 447 } 448 break; 449 case DELMODE_DELETE_MINIMUM: subtreeIndex = 0; break; 450 case DELMODE_DELETE_MAXIMUM: subtreeIndex = node.keyCount; break; 451 default: throw new IndexException(new Status(IStatus.ERROR, JavaCore.PLUGIN_ID, IStatus.OK, "Unknown delete mode " + mode, null)); //$NON-NLS-1$ 452 } 453 454 BTNode child = node.getChild(subtreeIndex); 455 if (child == null) { 456 throw new IndexException(new Status(IStatus.ERROR, JavaCore.PLUGIN_ID, IStatus.OK, 457 "BTree integrity error (null child found)", null)); //$NON-NLS-1$ 458 } 459 460 if (child.keyCount > this.minRecords) { 461 return deleteImp(key, child.node, mode); 462 } else { 463 child.makeWritable(); 464 node.makeWritable(); 465 BTNode sibR = node.getChild(subtreeIndex + 1); 466 if (sibR != null && sibR.keyCount > this.minRecords) { 467 sibR.makeWritable(); 468 /* Case 3a (i): child will underflow upon deletion, take a key from rightSibling */ 469 long rightKey = getRecord(node.chunk, node.node, subtreeIndex); 470 long leftmostRightSiblingKey = getRecord(sibR.chunk, sibR.node, 0); 471 append(child, rightKey, getChild(sibR.chunk, sibR.node, 0)); 472 nodeContentDelete(sibR, 0, 1); 473 putRecord(node.chunk, node.node, subtreeIndex, leftmostRightSiblingKey); 474 return deleteImp(key, child.node, mode); 475 } 476 477 BTNode sibL = node.getChild(subtreeIndex - 1); 478 if (sibL != null && sibL.keyCount > this.minRecords) { 479 sibL.makeWritable(); 480 /* Case 3a (ii): child will underflow upon deletion, take a key from leftSibling */ 481 long leftKey = getRecord(node.chunk, node.node, subtreeIndex - 1); 482 prepend(child, leftKey, getChild(sibL.chunk, sibL.node, sibL.keyCount)); 483 long rightmostLeftSiblingKey = getRecord(sibL.chunk, sibL.node, sibL.keyCount - 1); 484 putRecord(sibL.chunk, sibL.node, sibL.keyCount - 1, 0); 485 putChild(sibL.chunk, sibL.node, sibL.keyCount, 0); 486 putRecord(node.chunk, node.node, subtreeIndex - 1, rightmostLeftSiblingKey); 487 return deleteImp(key, child.node, mode); 488 } 489 490 /* Case 3b (i,ii): leftSibling, child, rightSibling all have minimum number of keys */ 491 492 if (sibL != null) { // merge child into leftSibling 493 mergeNodes(child, node, subtreeIndex - 1, sibL); 494 return deleteImp(key, sibL.node, mode); 495 } 496 497 if (sibR != null) { // merge rightSibling into child 498 mergeNodes(sibR, node, subtreeIndex, child); 499 return deleteImp(key, child.node, mode); 500 } 501 502 throw new BTreeKeyNotFoundException( 503 MessageFormat.format("Deletion of key not in btree: {0} mode={1}", //$NON-NLS-1$ 504 new Object[]{new Long(key), new Integer(mode)})); 505 } 506 } 507 } 508 } 509 510 /** 511 * Merge node 'src' onto the right side of node 'dst' using node 512 * 'keyProvider' as the source of the median key. Bounds checking is not 513 * performed. 514 * @param src the key to merge into dst 515 * @param keyProvider the node that provides the median key for the new node 516 * @param kIndex the index of the key in the node <i>mid</i> which is to become the new node's median key 517 * @param dst the node which is the basis and result of the merge 518 */ 519 public void mergeNodes(BTNode src, BTNode keyProvider, int kIndex, BTNode dst) 520 throws IndexException { 521 nodeContentCopy(src, 0, dst, dst.keyCount + 1, src.keyCount + 1); 522 long midKey = getRecord(keyProvider.chunk, keyProvider.node, kIndex); 523 putRecord(dst.chunk, dst.node, dst.keyCount, midKey); 524 long keySucc = kIndex + 1 == this.maxRecords ? 0 : getRecord(keyProvider.chunk, keyProvider.node, kIndex + 1); 525 this.db.free(getChild(keyProvider.chunk, keyProvider.node, kIndex + 1), Database.POOL_BTREE); 526 nodeContentDelete(keyProvider, kIndex + 1, 1); 527 putRecord(keyProvider.chunk, keyProvider.node, kIndex, keySucc); 528 if (kIndex == 0 && keySucc == 0) { 529 /* 530 * The root node is excused from the property that a node must have a least MIN keys 531 * This means we must special case it at the point when its had all of its keys deleted 532 * entirely during merge operations (which push one of its keys down as a pivot) 533 */ 534 long rootNode = getRoot(); 535 if (rootNode == keyProvider.node) { 536 this.db.putRecPtr(this.rootPointer, dst.node); 537 this.db.free(rootNode, Database.POOL_BTREE); 538 } 539 } 540 } 541 542 /** 543 * Insert the key and (its predecessor) child at the left side of the specified node. Bounds checking 544 * is not performed. 545 * @param node the node to prepend to 546 * @param key the new leftmost (least) key 547 * @param child the new leftmost (least) subtree root 548 */ 549 private void prepend(BTNode node, long key, long child) { 550 nodeContentCopy(node, 0, node, 1, node.keyCount + 1); 551 putRecord(node.chunk, node.node, 0, key); 552 putChild(node.chunk, node.node, 0, child); 553 } 554 555 /** 556 * Insert the key and (its successor) child at the right side of the specified node. Bounds 557 * checking is not performed. 558 * @param node 559 * @param key 560 * @param child 561 */ 562 private void append(BTNode node, long key, long child) { 563 putRecord(node.chunk, node.node, node.keyCount, key); 564 putChild(node.chunk, node.node, node.keyCount + 1, child); 565 } 566 567 /** 568 * Overwrite a section of the specified node (dst) with the specified section of the source 569 * node. Bounds checking is not performed. To allow just copying of the final child (which has 570 * no corresponding key) the routine behaves as though there were a corresponding key existing 571 * with value zero.<p> 572 * Copying from a node to itself is permitted. 573 * @param src the node to read from 574 * @param srcPos the initial index to read from (inclusive) 575 * @param dst the node to write to 576 * @param dstPos the initial index to write to (inclusive) 577 * @param length the number of (key,(predecessor)child) nodes to write 578 */ 579 private void nodeContentCopy(BTNode src, int srcPos, BTNode dst, int dstPos, int length) { 580 for (int i=length - 1; i >= 0; i--) { // this order is important when src == dst! 581 int srcIndex = srcPos + i; 582 int dstIndex = dstPos + i; 583 584 if (srcIndex < src.keyCount + 1) { 585 long srcChild = getChild(src.chunk, src.node, srcIndex); 586 putChild(dst.chunk, dst.node, dstIndex, srcChild); 587 588 if (srcIndex < src.keyCount) { 589 long srcKey = getRecord(src.chunk, src.node, srcIndex); 590 putRecord(dst.chunk, dst.node, dstIndex, srcKey); 591 } 592 } 593 } 594 } 595 596 /** 597 * Delete a section of node content - (key, (predecessor)child) pairs. Bounds checking 598 * is not performed. To allow deletion of the final child (which has no corresponding key) 599 * the routine behaves as though there were a corresponding key existing with value zero.<p> 600 * Content is deleted and remaining content is moved leftward the appropriate amount. 601 * @param node the node to delete content from 602 * @param i the start index (inclusive) to delete from 603 * @param length the length of the sequence to delete 604 */ 605 private void nodeContentDelete(BTNode node, int i, int length) { 606 for (int index= i; index <= this.maxRecords; index++) { 607 long newKey = (index + length) < node.keyCount ? getRecord(node.chunk, node.node, index + length) : 0; 608 long newChild = (index + length) < node.keyCount + 1 ? getChild(node.chunk, node.node, index + length) : 0; 609 if (index < this.maxRecords) { 610 putRecord(node.chunk, node.node, index, newKey); 611 } 612 if (index < this.maxChildren) { 613 putChild(node.chunk, node.node, index, newChild); 614 } 615 } 616 } 617 618 /** 619 * Visit all nodes beginning when the visitor comparator 620 * returns >= 0 until the visitor visit returns falls. 621 * 622 * @param visitor 623 */ 624 public boolean accept(IBTreeVisitor visitor) throws IndexException { 625 return accept(this.db.getRecPtr(this.rootPointer), visitor); 626 } 627 628 private boolean accept(long node, IBTreeVisitor visitor) throws IndexException { 629 // If found is false, we are still in search mode. 630 // Once found is true visit everything. 631 // Return false when ready to quit. 632 633 if (node == 0) { 634 return true; 635 } 636 if (visitor instanceof IBTreeVisitor2) { 637 ((IBTreeVisitor2) visitor).preNode(node); 638 } 639 640 try { 641 Chunk chunk = this.db.getChunk(node); 642 643 // Binary search to find first record greater or equal. 644 int lower= 0; 645 int upper= this.maxRecords - 1; 646 while (lower < upper && getRecord(chunk, node, upper - 1) == 0) { 647 upper--; 648 } 649 while (lower < upper) { 650 int middle= (lower + upper) / 2; 651 long checkRec = getRecord(chunk, node, middle); 652 if (checkRec == 0) { 653 upper= middle; 654 } else { 655 int compare= visitor.compare(checkRec); 656 if (compare >= 0) { 657 upper= middle; 658 } else { 659 lower= middle + 1; 660 } 661 } 662 } 663 664 // Start with first record greater or equal, reuse comparison results. 665 int i= lower; 666 for (; i < this.maxRecords; ++i) { 667 long record = getRecord(chunk, node, i); 668 if (record == 0) 669 break; 670 671 int compare= visitor.compare(record); 672 if (compare > 0) { 673 // Start point is to the left. 674 return accept(getChild(chunk, node, i), visitor); 675 } else if (compare == 0) { 676 if (!accept(getChild(chunk, node, i), visitor)) 677 return false; 678 if (!visitor.visit(record)) 679 return false; 680 } 681 } 682 return accept(getChild(chunk, node, i), visitor); 683 } finally { 684 if (visitor instanceof IBTreeVisitor2) { 685 ((IBTreeVisitor2) visitor).postNode(node); 686 } 687 } 688 } 689 690 /* 691 * TODO: It would be good to move these into IBTreeVisitor and eliminate 692 * IBTreeVisitor2 if this is acceptable. 693 */ 694 private interface IBTreeVisitor2 extends IBTreeVisitor { 695 void preNode(long node) throws IndexException; 696 void postNode(long node) throws IndexException; 697 } 698 699 /** 700 * Debugging method for checking B-tree invariants 701 * @return the empty String if B-tree invariants hold, otherwise 702 * a human readable report 703 * @throws IndexException 704 */ 705 public String getInvariantsErrorReport() throws IndexException { 706 InvariantsChecker checker = new InvariantsChecker(); 707 accept(checker); 708 return checker.isValid() ? "" : checker.getMsg(); //$NON-NLS-1$ 709 } 710 711 /** 712 * A B-tree visitor for checking some B-tree invariants. 713 * Note ordering invariants are not checked here. 714 */ 715 private class InvariantsChecker implements IBTreeVisitor2 { 716 boolean valid = true; 717 String msg = ""; //$NON-NLS-1$ 718 Integer leafDepth; 719 int depth; 720 721 public InvariantsChecker() {} 722 public String getMsg() { return this.msg; } 723 public boolean isValid() { return this.valid; } 724 @Override 725 public void postNode(long node) throws IndexException { this.depth--; } 726 @Override 727 public int compare(long record) throws IndexException { return 0; } 728 @Override 729 public boolean visit(long record) throws IndexException { return true; } 730 731 @Override 732 public void preNode(long node) throws IndexException { 733 this.depth++; 734 735 // Collect information for checking. 736 int keyCount = 0; 737 int indexFirstBlankKey = BTree.this.maxRecords; 738 int indexLastNonBlankKey = 0; 739 for (int i= 0; i < BTree.this.maxRecords; i++) { 740 if (getRecord(BTree.this.db.getChunk(node), node, i) != 0) { 741 keyCount++; 742 indexLastNonBlankKey = i; 743 } else if (indexFirstBlankKey == BTree.this.maxRecords) { 744 indexFirstBlankKey = i; 745 } 746 } 747 748 int childCount = 0; 749 for (int i= 0; i < BTree.this.maxChildren; i++) { 750 if (getChild(BTree.this.db.getChunk(node), node, i) != 0) { 751 childCount++; 752 } 753 } 754 755 // Check that non-blank keys are contiguous and blank key terminated. 756 if (indexFirstBlankKey != indexLastNonBlankKey + 1) { 757 boolean full = indexFirstBlankKey == BTree.this.maxRecords && indexLastNonBlankKey == BTree.this.maxRecords - 1; 758 boolean empty = indexFirstBlankKey == 0 && indexLastNonBlankKey == 0; 759 if (!full && !empty) { 760 this.valid = false; 761 this.msg += MessageFormat.format("[{0} blanks inconsistent b={1} nb={2}]", //$NON-NLS-1$ 762 new Object[] { new Long(node), new Integer(indexFirstBlankKey), 763 new Integer(indexLastNonBlankKey) }); 764 } 765 } 766 767 // Check: Key number constrains child numbers 768 if (childCount != 0 && childCount != keyCount + 1) { 769 this.valid = false; 770 this.msg += MessageFormat.format("[{0} wrong number of children with respect to key count]", //$NON-NLS-1$ 771 new Object[] { new Long(node) }); 772 } 773 774 // The root node is excused from the remaining node constraints. 775 if (node == BTree.this.db.getRecPtr(BTree.this.rootPointer)) { 776 return; 777 } 778 779 // Check: Non-root nodes must have a keyCount within a certain range 780 if (keyCount < BTree.this.minRecords || keyCount > BTree.this.maxRecords) { 781 this.valid = false; 782 this.msg += MessageFormat.format("[{0} key count out of range]", new Object[] { new Long(node) }); //$NON-NLS-1$ 783 } 784 785 // Check: All leaf nodes are at the same depth 786 if (childCount == 0) { 787 if (this.leafDepth == null) { 788 this.leafDepth = new Integer(this.depth); 789 } 790 if (this.depth != this.leafDepth.intValue()) { 791 this.valid = false; 792 this.msg += "Leaf nodes at differing depths"; //$NON-NLS-1$ 793 } 794 } 795 } 796 } 797 } 798