| /******************************************************************************* |
| * Copyright (c) 2005, 2007 QNX Software Systems and others. |
| * All rights reserved. This program and the accompanying materials |
| * are made available under the terms of the Eclipse Public License v1.0 |
| * which accompanies this distribution, and is available at |
| * http://www.eclipse.org/legal/epl-v10.html |
| * |
| * Contributors: |
| * QNX - Initial API and implementation |
| * Andrew Ferguson (Symbian) - Provide B-tree deletion routine |
| * Markus Schorn (Wind River Systems) |
| *******************************************************************************/ |
| |
| package org.eclipse.rephraserengine.internal.db.org.eclipse.cdt.internal.core.pdom.db; |
| |
| import java.text.MessageFormat; |
| |
| import org.eclipse.core.runtime.CoreException; |
| import org.eclipse.core.runtime.IStatus; |
| import org.eclipse.core.runtime.Status; |
| import org.eclipse.rephraserengine.internal.db.org.eclipse.cdt.core.CCorePlugin; |
| |
| |
| /** |
| * @author Doug Schaefer |
| * |
| */ |
| public class BTree { |
| // Constants for internal deletion routine (see deleteImp doc) |
| private static final int DELMODE_NORMAL = 0; |
| private static final int DELMODE_DELETE_MINIMUM = 1; |
| private static final int DELMODE_DELETE_MAXIMUM = 2; |
| |
| protected final Database db; |
| protected final int rootPointer; |
| |
| protected final int DEGREE; |
| protected final int MAX_RECORDS; |
| protected final int MAX_CHILDREN; |
| protected final int MIN_RECORDS; |
| protected final int OFFSET_CHILDREN; |
| protected final int MEDIAN_RECORD; |
| |
| protected final IBTreeComparator cmp; |
| |
| public BTree(Database db, int rootPointer, IBTreeComparator cmp) { |
| this(db, rootPointer, 8, cmp); |
| } |
| |
| /** |
| * Constructor. |
| * |
| * @param db the database containing the btree |
| * @param root offset into database of the pointer to the root node |
| */ |
| public BTree(Database db, int rootPointer, int degree, IBTreeComparator cmp) { |
| if(degree<2) |
| throw new IllegalArgumentException(Messages.getString("BTree.IllegalDegree")); //$NON-NLS-1$ |
| |
| this.db = db; |
| this.rootPointer = rootPointer; |
| this.cmp = cmp; |
| |
| this.DEGREE = degree; |
| this.MIN_RECORDS = DEGREE - 1; |
| this.MAX_RECORDS = 2*DEGREE - 1; |
| this.MAX_CHILDREN = 2*DEGREE; |
| this.OFFSET_CHILDREN = MAX_RECORDS * Database.INT_SIZE; |
| this.MEDIAN_RECORD = DEGREE - 1; |
| } |
| |
| protected int getRoot() throws CoreException { |
| return db.getInt(rootPointer); |
| } |
| |
| protected final void putRecord(Chunk chunk, int node, int index, int record) { |
| chunk.putInt(node + index * Database.INT_SIZE, record); |
| } |
| |
| protected final int getRecord(Chunk chunk, int node, int index) { |
| return chunk.getInt(node + index * Database.INT_SIZE); |
| } |
| |
| protected final void putChild(Chunk chunk, int node, int index, int child) { |
| chunk.putInt(node + OFFSET_CHILDREN + index * Database.INT_SIZE, child); |
| } |
| |
| protected final int getChild(Chunk chunk, int node, int index) { |
| return chunk.getInt(node + OFFSET_CHILDREN + index * Database.INT_SIZE); |
| } |
| |
| /** |
| * Inserts the record into the b-tree. We don't insert if the |
| * key was already there, in which case we return the record |
| * that matched. In other cases, we just return the record back. |
| * |
| * @param offset of the record |
| * @return |
| */ |
| public int insert(int record) throws CoreException { |
| int root = getRoot(); |
| |
| // is this our first time in |
| if (root == 0) { |
| firstInsert(record); |
| return record; |
| } |
| |
| return insert(null, 0, 0, root, record); |
| } |
| |
| private int insert(Chunk pChunk, int parent, int iParent, int node, int record) throws CoreException { |
| Chunk chunk = db.getChunk(node); |
| |
| // if this node is full (last record isn't null), split it |
| if (getRecord(chunk, node, MAX_RECORDS - 1) != 0) { |
| int median = getRecord(chunk, node, MEDIAN_RECORD); |
| if (median == record) |
| // found it, never mind |
| return median; |
| else { |
| // split it |
| // create the new node and move the larger records over |
| int newnode = allocateNode(); |
| Chunk newchunk = db.getChunk(newnode); |
| for (int i = 0; i < MEDIAN_RECORD; ++i) { |
| putRecord(newchunk, newnode, i, getRecord(chunk, node, MEDIAN_RECORD + 1 + i)); |
| putRecord(chunk, node, MEDIAN_RECORD + 1 + i, 0); |
| putChild(newchunk, newnode, i, getChild(chunk, node, MEDIAN_RECORD + 1 + i)); |
| putChild(chunk, node, MEDIAN_RECORD + 1 + i, 0); |
| } |
| putChild(newchunk, newnode, MEDIAN_RECORD, getChild(chunk, node, MAX_RECORDS)); |
| putChild(chunk, node, MAX_RECORDS, 0); |
| |
| if (parent == 0) { |
| // create a new root |
| parent = allocateNode(); |
| pChunk = db.getChunk(parent); |
| db.putInt(rootPointer, parent); |
| putChild(pChunk, parent, 0, node); |
| } else { |
| // insert the median into the parent |
| for (int i = MAX_RECORDS - 2; i >= iParent; --i) { |
| int r = getRecord(pChunk, parent, i); |
| if (r != 0) { |
| putRecord(pChunk, parent, i + 1, r); |
| putChild(pChunk, parent, i + 2, getChild(pChunk, parent, i + 1)); |
| } |
| } |
| } |
| putRecord(pChunk, parent, iParent, median); |
| putChild(pChunk, parent, iParent + 1, newnode); |
| |
| putRecord(chunk, node, MEDIAN_RECORD, 0); |
| |
| // set the node to the correct one to follow |
| if (cmp.compare(record, median) > 0) { |
| node = newnode; |
| chunk = newchunk; |
| } |
| } |
| } |
| |
| // binary search to find the insert point |
| int lower= 0; |
| int upper= MAX_RECORDS-1; |
| while (lower < upper && getRecord(chunk, node, upper-1) == 0) { |
| upper--; |
| } |
| |
| while (lower < upper) { |
| int middle= (lower+upper)/2; |
| int checkRec= getRecord(chunk, node, middle); |
| if (checkRec == 0) { |
| upper= middle; |
| } |
| else { |
| int compare= cmp.compare(checkRec, record); |
| if (compare > 0) { |
| upper= middle; |
| } |
| else if (compare < 0) { |
| lower= middle+1; |
| } |
| else { |
| // found it, no insert, just return the record |
| return record; |
| } |
| } |
| } |
| final int i= lower; |
| int child = getChild(chunk, node, i); |
| if (child != 0) { |
| // visit the children |
| return insert(chunk, node, i, child, record); |
| } else { |
| // were at the leaf, add us in. |
| // first copy everything after over one |
| for (int j = MAX_RECORDS - 2; j >= i; --j) { |
| int r = getRecord(chunk, node, j); |
| if (r != 0) |
| putRecord(chunk, node, j + 1, r); |
| } |
| putRecord(chunk, node, i, record); |
| return record; |
| } |
| } |
| |
| private void firstInsert(int record) throws CoreException { |
| // create the node and save it as root |
| int root = allocateNode(); |
| db.putInt(rootPointer, root); |
| // put the record in the first slot of the node |
| putRecord(db.getChunk(root), root, 0, record); |
| } |
| |
| private int allocateNode() throws CoreException { |
| return db.malloc((2 * MAX_RECORDS + 1) * Database.INT_SIZE); |
| } |
| |
| /** |
| * Deletes the specified record from the B-tree. |
| * <p> |
| * If the specified record is not present then this routine has no effect. |
| * <p> |
| * Specifying a record r for which there is another record q existing in the B-tree |
| * where cmp.compare(r,q)==0 && r!=q will also have no effect |
| * <p> |
| * N.B. The record is not deleted itself - its storage is not deallocated. |
| * The reference to the record in the btree is deleted. |
| * |
| * @param record the record to delete |
| * @param cmp the comparator for locating the record |
| * @throws CoreException |
| */ |
| public void delete(int record) throws CoreException { |
| try { |
| deleteImp(record, getRoot(), DELMODE_NORMAL); |
| } catch(BTreeKeyNotFoundException e) { |
| // contract of this method is to NO-OP upon this event |
| } |
| } |
| |
| private class BTreeKeyNotFoundException extends Exception { |
| private static final long serialVersionUID = 9065438266175091670L; |
| public BTreeKeyNotFoundException(String msg) { |
| super(msg); |
| } |
| } |
| |
| /** |
| * Used in implementation of delete routines |
| */ |
| private class BTNode { |
| final int node; |
| final int keyCount; |
| final Chunk chunk; |
| |
| BTNode(int node) throws CoreException { |
| this.node = node; |
| this.chunk = db.getChunk(node); |
| int i=0; |
| while(i<MAX_RECORDS && getRecord(chunk, node, i)!=0) |
| i++; |
| keyCount = i; |
| } |
| |
| private BTNode getChild(int index) throws CoreException { |
| if(0<=index && index<MAX_CHILDREN) { |
| int child = BTree.this.getChild(chunk, node, index); |
| if(child!=0) |
| return new BTNode(child); |
| } |
| return null; |
| } |
| } |
| |
| /** |
| * Implementation for deleting a key/record from the B-tree. |
| * <p> |
| * There is no distinction between keys and records. |
| * <p> |
| * This implements a single downward pass (with minor exceptions) deletion |
| * <p> |
| * @param key the address of the record to delete |
| * @param nodeRecord a node that (directly or indirectly) contains the specified key/record |
| * @param mode one of DELMODE_NORMAL, DELMODE_DELETE_MINIMUM, DELMODE_DELETE_MAXIMUM |
| * where DELMODE_NORMAL: locates the specified key/record using the comparator provided |
| * DELMODE_DELETE_MINIMUM: locates and deletes the minimum element in the subtree rooted at nodeRecord |
| * DELMODE_DELETE_MAXIMUM: locates and deletes the maximum element in the subtree rooted at nodeRecord |
| * @param cmp the comparator used to locate the record in the tree |
| * @return the address of the record removed from the B-tree |
| * @throws CoreException |
| */ |
| private int deleteImp(int key, int nodeRecord, int mode) |
| throws CoreException, BTreeKeyNotFoundException { |
| BTNode node = new BTNode(nodeRecord); |
| |
| // Determine index of key in current node, or -1 if its not in this node |
| int keyIndexInNode = -1; |
| if(mode==DELMODE_NORMAL) |
| for(int i=0; i<node.keyCount; i++) |
| if(getRecord(node.chunk, node.node, i) == key) { |
| keyIndexInNode = i; |
| break; |
| } |
| |
| if(getChild(node.chunk, node.node, 0)==0) { |
| /* Case 1: leaf node containing the key (by method precondition) */ |
| if(keyIndexInNode!=-1) { |
| nodeContentDelete(node, keyIndexInNode, 1); |
| return key; |
| } else { |
| if(mode==DELMODE_DELETE_MINIMUM) { |
| int subst = getRecord(node.chunk, node.node, 0); |
| nodeContentDelete(node, 0, 1); |
| return subst; |
| } else if(mode==DELMODE_DELETE_MAXIMUM) { |
| int subst = getRecord(node.chunk, node.node, node.keyCount-1); |
| nodeContentDelete(node, node.keyCount-1, 1); |
| return subst; |
| } |
| throw new BTreeKeyNotFoundException( |
| MessageFormat.format(Messages.getString("BTree.DeletionOnAbsentKey"), //$NON-NLS-1$ |
| new Object[]{new Integer(key), new Integer(mode)})); |
| } |
| } else { |
| if(keyIndexInNode != -1) { |
| /* Case 2: non-leaf node which contains the key itself */ |
| |
| BTNode succ = node.getChild(keyIndexInNode+1); |
| if(succ!=null && succ.keyCount > MIN_RECORDS) { |
| /* Case 2a: Delete key by overwriting it with its successor (which occurs in a leaf node) */ |
| int subst = deleteImp(-1, succ.node, DELMODE_DELETE_MINIMUM); |
| putRecord(node.chunk, node.node, keyIndexInNode, subst); |
| return key; |
| } |
| |
| BTNode pred = node.getChild(keyIndexInNode); |
| if(pred!=null && pred.keyCount > MIN_RECORDS) { |
| /* Case 2b: Delete key by overwriting it with its predecessor (which occurs in a leaf node) */ |
| int subst = deleteImp(-1, pred.node, DELMODE_DELETE_MAXIMUM); |
| putRecord(node.chunk, node.node, keyIndexInNode, subst); |
| return key; |
| } |
| |
| /* Case 2c: Merge successor and predecessor */ |
| // assert(pred!=null && succ!=null); |
| mergeNodes(succ, node, keyIndexInNode, pred); |
| return deleteImp(key, pred.node, mode); |
| } else { |
| /* Case 3: non-leaf node which does not itself contain the key */ |
| |
| /* Determine root of subtree that should contain the key */ |
| int subtreeIndex; |
| switch(mode) { |
| case DELMODE_NORMAL: |
| subtreeIndex = node.keyCount; |
| for(int i=0; i<node.keyCount; i++) |
| if(cmp.compare(getRecord(node.chunk, node.node, i), key)>0) { |
| subtreeIndex = i; |
| break; |
| } |
| break; |
| case DELMODE_DELETE_MINIMUM: subtreeIndex = 0; break; |
| case DELMODE_DELETE_MAXIMUM: subtreeIndex = node.keyCount; break; |
| default: throw new CoreException(new Status(IStatus.ERROR, CCorePlugin.PLUGIN_ID, IStatus.OK, Messages.getString("BTree.UnknownMode"), null)); //$NON-NLS-1$ |
| } |
| |
| BTNode child = node.getChild(subtreeIndex); |
| if(child==null) { |
| throw new CoreException(new Status(IStatus.ERROR, CCorePlugin.PLUGIN_ID, IStatus.OK, Messages.getString("BTree.IntegrityError"), null)); //$NON-NLS-1$ |
| } |
| |
| if(child.keyCount > MIN_RECORDS) { |
| return deleteImp(key, child.node, mode); |
| } else { |
| BTNode sibR = node.getChild(subtreeIndex+1); |
| if(sibR!=null && sibR.keyCount > MIN_RECORDS) { |
| /* Case 3a (i): child will underflow upon deletion, take a key from rightSibling */ |
| int rightKey = getRecord(node.chunk, node.node, subtreeIndex); |
| int leftmostRightSiblingKey = getRecord(sibR.chunk, sibR.node, 0); |
| append(child, rightKey, getChild(sibR.chunk, sibR.node, 0)); |
| nodeContentDelete(sibR, 0, 1); |
| putRecord(node.chunk, node.node, subtreeIndex, leftmostRightSiblingKey); |
| return deleteImp(key, child.node, mode); |
| } |
| |
| BTNode sibL = node.getChild(subtreeIndex-1); |
| if(sibL!=null && sibL.keyCount > MIN_RECORDS) { |
| /* Case 3a (ii): child will underflow upon deletion, take a key from leftSibling */ |
| int leftKey = getRecord(node.chunk, node.node, subtreeIndex-1); |
| prepend(child, leftKey, getChild(sibL.chunk, sibL.node, sibL.keyCount)); |
| int rightmostLeftSiblingKey = getRecord(sibL.chunk, sibL.node, sibL.keyCount-1); |
| putRecord(sibL.chunk, sibL.node, sibL.keyCount-1, 0); |
| putChild(sibL.chunk, sibL.node, sibL.keyCount, 0); |
| putRecord(node.chunk, node.node, subtreeIndex-1, rightmostLeftSiblingKey); |
| return deleteImp(key, child.node, mode); |
| } |
| |
| /* Case 3b (i,ii): leftSibling, child, rightSibling all have minimum number of keys */ |
| |
| if(sibL!=null) { // merge child into leftSibling |
| mergeNodes(child, node, subtreeIndex-1, sibL); |
| return deleteImp(key, sibL.node, mode); |
| } |
| |
| if(sibR!=null) { // merge rightSibling into child |
| mergeNodes(sibR, node, subtreeIndex, child); |
| return deleteImp(key, child.node, mode); |
| } |
| |
| throw new BTreeKeyNotFoundException( |
| MessageFormat.format(Messages.getString("BTree.DeletionOnAbsentKey"), //$NON-NLS-1$ |
| new Object[]{new Integer(key), new Integer(mode)})); |
| } |
| } |
| } |
| } |
| |
| /** |
| * Merge node 'src' onto the right side of node 'dst' using node |
| * 'keyProvider' as the source of the median key. Bounds checking is not |
| * performed. |
| * @param src the key to merge into dst |
| * @param mid the node that provides the median key for the new node |
| * @param kIndex the index of the key in the node <i>mid</i> which is to become the new node's median key |
| * @param dst the node which is the basis and result of the merge |
| */ |
| public void mergeNodes(BTNode src, BTNode keyProvider, int kIndex, BTNode dst) |
| throws CoreException { |
| nodeContentCopy(src, 0, dst, dst.keyCount+1, src.keyCount+1); |
| int midKey = getRecord(keyProvider.chunk, keyProvider.node, kIndex); |
| putRecord(dst.chunk, dst.node, dst.keyCount, midKey); |
| int keySucc = kIndex+1 == MAX_RECORDS ? 0 : getRecord(keyProvider.chunk, keyProvider.node, kIndex+1); |
| db.free(getChild(keyProvider.chunk, keyProvider.node, kIndex+1)); |
| nodeContentDelete(keyProvider, kIndex+1, 1); |
| putRecord(keyProvider.chunk, keyProvider.node, kIndex, keySucc); |
| if(kIndex == 0 && keySucc == 0) { |
| /* |
| * The root node is excused from the property that a node must have a least MIN keys |
| * This means we must special case it at the point when its had all of its keys deleted |
| * entirely during merge operations (which push one of its keys down as a pivot) |
| */ |
| int rootNode = getRoot(); |
| if(rootNode == keyProvider.node) { |
| db.putInt(rootPointer, dst.node); |
| db.free(rootNode); |
| } |
| } |
| } |
| |
| /** |
| * Insert the key and (its predecessor) child at the left side of the specified node. Bounds checking |
| * is not performed. |
| * @param node the node to prepend to |
| * @param key the new leftmost (least) key |
| * @param child the new leftmost (least) subtree root |
| */ |
| private void prepend(BTNode node, int key, int child) { |
| nodeContentCopy(node, 0, node, 1, node.keyCount+1); |
| putRecord(node.chunk, node.node, 0, key); |
| putChild(node.chunk, node.node, 0, child); |
| } |
| |
| /** |
| * Insert the key and (its successor) child at the right side of the specified node. Bounds checking |
| * is not performed. |
| * @param node |
| * @param key |
| * @param child |
| */ |
| private void append(BTNode node, int key, int child) { |
| putRecord(node.chunk, node.node, node.keyCount, key); |
| putChild(node.chunk, node.node, node.keyCount + 1, child); |
| } |
| |
| /** |
| * Overwrite a section of the specified node (dst) with the specified section of the source node. Bounds checking |
| * is not performed. To allow just copying of the final child (which has no corresponding key) the routine |
| * behaves as though there were a corresponding key existing with value zero.<p> |
| * Copying from a node to itself is permitted. |
| * @param src the node to read from |
| * @param srcPos the initial index to read from (inclusive) |
| * @param dst the node to write to |
| * @param dstPos the initial index to write to (inclusive) |
| * @param length the number of (key,(predecessor)child) nodes to write |
| */ |
| private void nodeContentCopy(BTNode src, int srcPos, BTNode dst, int dstPos, int length) { |
| for(int i=length-1; i>=0; i--) { // this order is important when src==dst! |
| int srcIndex = srcPos + i; |
| int dstIndex = dstPos + i; |
| |
| if(srcIndex<src.keyCount+1) { |
| int srcChild = getChild(src.chunk, src.node, srcIndex); |
| putChild(dst.chunk, dst.node, dstIndex, srcChild); |
| |
| if(srcIndex<src.keyCount) { |
| int srcKey = getRecord(src.chunk, src.node, srcIndex); |
| putRecord(dst.chunk, dst.node, dstIndex, srcKey); |
| } |
| } |
| } |
| } |
| |
| /** |
| * Delete a section of node content - (key, (predecessor)child) pairs. Bounds checking |
| * is not performed. To allow deletion of the final child (which has no corresponding key) the routine |
| * behaves as though there were a corresponding key existing with value zero.<p> |
| * Content is deleted and remaining content is moved leftward the appropriate amount. |
| * @param node the node to delete content from |
| * @param i the start index (inclusive) to delete from |
| * @param length the length of the sequence to delete |
| */ |
| private void nodeContentDelete(BTNode node, int i, int length) { |
| for(int index=i; index<=MAX_RECORDS; index++) { |
| int newKey = (index+length) < node.keyCount ? getRecord(node.chunk, node.node, index+length) : 0; |
| int newChild = (index+length) < node.keyCount+1 ? getChild(node.chunk, node.node, index+length) : 0; |
| if(index<MAX_RECORDS) { |
| putRecord(node.chunk, node.node, index, newKey); |
| } |
| if(index<MAX_CHILDREN) { |
| putChild(node.chunk, node.node, index, newChild); |
| } |
| } |
| } |
| |
| /** |
| * Visit all nodes beginning when the visitor comparator |
| * returns >= 0 until the visitor visit returns falls. |
| * |
| * @param visitor |
| */ |
| public void accept(IBTreeVisitor visitor) throws CoreException { |
| accept(db.getInt(rootPointer), visitor); |
| } |
| |
| private boolean accept(int node, IBTreeVisitor visitor) throws CoreException { |
| // if found is false, we are still in search mode |
| // once found is true visit everything |
| // return false when ready to quit |
| |
| if (node == 0) { |
| return true; |
| } |
| if(visitor instanceof IBTreeVisitor2) { |
| ((IBTreeVisitor2)visitor).preNode(node); |
| } |
| |
| try { |
| Chunk chunk = db.getChunk(node); |
| |
| // binary search to find first record greater or equal |
| int lower= 0; |
| int upper= MAX_RECORDS-1; |
| while (lower < upper && getRecord(chunk, node, upper-1) == 0) { |
| upper--; |
| } |
| while (lower < upper) { |
| int middle= (lower+upper)/2; |
| int checkRec= getRecord(chunk, node, middle); |
| if (checkRec == 0) { |
| upper= middle; |
| } |
| else { |
| int compare= visitor.compare(checkRec); |
| if (compare >= 0) { |
| upper= middle; |
| } |
| else { |
| lower= middle+1; |
| } |
| } |
| } |
| |
| // start with first record greater or equal, reuse comparison results. |
| int i= lower; |
| for (; i < MAX_RECORDS; ++i) { |
| int record = getRecord(chunk, node, i); |
| if (record == 0) |
| break; |
| |
| int compare= visitor.compare(record); |
| if (compare > 0) { |
| // start point is to the left |
| return accept(getChild(chunk, node, i), visitor); |
| } |
| else if (compare == 0) { |
| if (!accept(getChild(chunk, node, i), visitor)) |
| return false; |
| if (!visitor.visit(record)) |
| return false; |
| } |
| } |
| return accept(getChild(chunk, node, i), visitor); |
| } finally { |
| if(visitor instanceof IBTreeVisitor2) { |
| ((IBTreeVisitor2)visitor).postNode(node); |
| } |
| } |
| } |
| |
| /* |
| * TODO: It would be good to move these into IBTreeVisitor and eliminate |
| * IBTreeVisitor2 if this is acceptable. |
| */ |
| private interface IBTreeVisitor2 extends IBTreeVisitor { |
| void preNode(int node) throws CoreException; |
| void postNode(int node) throws CoreException; |
| } |
| |
| /** |
| * Debugging method for checking B-tree invariants |
| * @return the empty String if B-tree invariants hold, otherwise |
| * a human readable report |
| * @throws CoreException |
| */ |
| public String getInvariantsErrorReport() throws CoreException { |
| InvariantsChecker checker = new InvariantsChecker(); |
| accept(checker); |
| return checker.isValid() ? "" : checker.getMsg(); //$NON-NLS-1$ |
| } |
| |
| /** |
| * A B-tree visitor for checking some B-tree invariants. |
| * Note ordering invariants are not checked here. |
| */ |
| private class InvariantsChecker implements IBTreeVisitor2 { |
| boolean valid = true; |
| String msg = ""; //$NON-NLS-1$ |
| Integer leafDepth; |
| int depth; |
| |
| public String getMsg() { return msg; } |
| public boolean isValid() { return valid; } |
| public void postNode(int node) throws CoreException { depth--; } |
| public int compare(int record) throws CoreException { return 0; } |
| public boolean visit(int record) throws CoreException { return true; } |
| |
| public void preNode(int node) throws CoreException { |
| depth++; |
| |
| // collect information for checking |
| int keyCount = 0; |
| int indexFirstBlankKey = MAX_RECORDS; |
| int indexLastNonBlankKey = 0; |
| for(int i=0; i<MAX_RECORDS; i++) { |
| if(getRecord(db.getChunk(node), node, i)!=0) { |
| keyCount++; |
| indexLastNonBlankKey = i; |
| } else if(indexFirstBlankKey== MAX_RECORDS){ |
| indexFirstBlankKey = i; |
| } |
| } |
| |
| int childCount = 0; |
| for(int i=0; i<MAX_CHILDREN; i++) { |
| if(getChild(db.getChunk(node), node, i)!=0) { |
| childCount++; |
| } |
| } |
| |
| // check that non-blank keys are contiguous and blank key terminated |
| if(indexFirstBlankKey != indexLastNonBlankKey+1) { |
| boolean full = indexFirstBlankKey == MAX_RECORDS && indexLastNonBlankKey == MAX_RECORDS-1; |
| boolean empty = indexFirstBlankKey == 0 && indexLastNonBlankKey == 0; |
| if(!full && !empty){ |
| valid = false; |
| msg += MessageFormat.format(Messages.getString("BTree.IntegrityErrorA"), //$NON-NLS-1$ |
| new Object[]{new Integer(node), new Integer(indexFirstBlankKey), new Integer(indexLastNonBlankKey)}); |
| } |
| } |
| |
| // Check: Key number constrains child numbers |
| if(childCount!=0 && childCount!=keyCount+1) { |
| valid = false; |
| msg += MessageFormat.format(Messages.getString("BTree.IntegrityErrorB"), new Object[]{new Integer(node)}); //$NON-NLS-1$ |
| } |
| |
| // the root node is excused from the remaining node constraints |
| if(node == db.getInt(rootPointer)) { |
| return; |
| } |
| |
| // Check: Non-root nodes must have a keyCount within a certain range |
| if(keyCount < MIN_RECORDS || keyCount > MAX_RECORDS) { |
| valid = false; |
| msg += MessageFormat.format(Messages.getString("BTree.IntegrityErrorC"), new Object[]{new Integer(node)}); //$NON-NLS-1$ |
| } |
| |
| // Check: All leaf nodes are at the same depth |
| if(childCount==0) { |
| if(leafDepth==null) { |
| leafDepth = new Integer(depth); |
| } |
| if(depth!=leafDepth.intValue()) { |
| valid = false; |
| msg += Messages.getString("BTree.IntegrityErrorD"); //$NON-NLS-1$ |
| } |
| } |
| } |
| } |
| } |