Clover coverage report -
Coverage timestamp: Sun Nov 1 2009 23:08:24 UTC
Overview   Package   File
    FRAMES   NO FRAMES  
file stats: LOC: 1,126   Methods: 63
NCLOC: 704   Classes: 5
 
 Source file Conditionals Statements Methods TOTAL
BTree.java 67.6% 71.1% 77.8% 71%
coverage coverage
 1    /*
 2    * Licensed to the Apache Software Foundation (ASF) under one or more
 3    * contributor license agreements. See the NOTICE file distributed with
 4    * this work for additional information regarding copyright ownership.
 5    * The ASF licenses this file to You under the Apache License, Version 2.0
 6    * (the "License"); you may not use this file except in compliance with
 7    * the License. You may obtain a copy of the License at
 8    *
 9    * http://www.apache.org/licenses/LICENSE-2.0
 10    *
 11    * Unless required by applicable law or agreed to in writing, software
 12    * distributed under the License is distributed on an "AS IS" BASIS,
 13    * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 14    * See the License for the specific language governing permissions and
 15    * limitations under the License.
 16    *
 17    * $Id: BTree.java 712571 2008-11-09 22:00:06Z natalia $
 18    */
 19   
 20    package org.apache.xindice.core.filer;
 21   
 22    import org.apache.commons.logging.Log;
 23    import org.apache.commons.logging.LogFactory;
 24    import org.apache.xindice.core.DBException;
 25    import org.apache.xindice.core.FaultCodes;
 26    import org.apache.xindice.core.data.Value;
 27    import org.apache.xindice.core.indexer.IndexQuery;
 28   
 29    import java.io.ByteArrayOutputStream;
 30    import java.io.DataInput;
 31    import java.io.DataInputStream;
 32    import java.io.DataOutputStream;
 33    import java.io.File;
 34    import java.io.IOException;
 35    import java.io.RandomAccessFile;
 36    import java.io.DataOutput;
 37    import java.lang.ref.WeakReference;
 38    import java.util.Arrays;
 39    import java.util.Map;
 40    import java.util.WeakHashMap;
 41   
 42    /**
 43    * BTree represents a Variable Magnitude Simple-Prefix B+Tree File.
 44    * A BTree is a bit flexible in that it can be used for set or
 45    * map-based indexing. {@link BTreeFiler} uses the BTree as a set for
 46    * producing RecordSet entries. The Indexers use BTree as a map for
 47    * indexing entity and attribute values in Documents.
 48    *
 49    * <br>
 50    * For those who don't know how a Simple-Prefix B+Tree works, the primary
 51    * distinction is that instead of promoting actual keys to branch pages,
 52    * when leaves are split, a shortest-possible separator is generated at
 53    * the pivot. That separator is what is promoted to the parent branch
 54    * (and continuing up the list). As a result, actual keys and pointers
 55    * can only be found at the leaf level. This also affords the index the
 56    * ability to ignore costly merging and redistribution of pages when
 57    * deletions occur. Deletions only affect leaf pages in this
 58    * implementation, and so it is entirely possible for a leaf page to be
 59    * completely empty after all of its keys have been removed.
 60    *
 61    * <br>
 62    * Also, the Variable Magnitude attribute means that the btree attempts
 63    * to store as many values and pointers on one page as is possible.
 64    *
 65    * <br>
 66    * This implementation supports the notion of nested roots. This means
 67    * that you can create a btree where the pointers actually point to the
 68    * root of a separate btree being managed in the same file.
 69    *
 70    * @version $Revision: 712571 $, $Date: 2008-11-09 22:00:06 +0000 (Sun, 09 Nov 2008) $
 71    */
 72    public class BTree extends Paged {
 73   
 74    private static final Log log = LogFactory.getLog(BTree.class);
 75   
 76    protected static final byte LEAF = 1;
 77    protected static final byte BRANCH = 2;
 78    protected static final byte STREAM = 3;
 79   
 80    protected static final long VALUE_DOES_NOT_EXIST = -1;
 81   
 82    /**
 83    * Identity map of the recently used tree nodes to ensure that same
 84    * node is present in the memory once and only once.
 85    *
 86    * <p>Cache contains weak references to the BTreeNode objects, keys
 87    * are page numbers (Long objects). Access synchronized by this map
 88    * object itself.
 89    *
 90    * <p>This identity map can be made into cache to store nodes for
 91    * extended time periods, but that might not be necessary since
 92    * documents are cached on the Collection level.
 93    */
 94    private final Map cache = new WeakHashMap();
 95   
 96    private BTreeFileHeader fileHeader;
 97    private BTreeRootInfo rootInfo;
 98    private BTreeNode rootNode;
 99   
 100   
 101  1392 public BTree() {
 102  1392 super();
 103  1392 fileHeader = (BTreeFileHeader) getFileHeader();
 104    }
 105   
 106  0 public BTree(File file) {
 107  0 this();
 108  0 setFile(file);
 109    }
 110   
 111  1389 public boolean open() throws DBException {
 112  1389 if (super.open()) {
 113  1389 long p = fileHeader.getRootPage();
 114  1389 rootInfo = new BTreeRootInfo(p);
 115  1389 rootNode = getBTreeNode(p, null);
 116  1389 return true;
 117    } else {
 118  0 return false;
 119    }
 120    }
 121   
 122  1151 public boolean create() throws DBException {
 123  1151 if (super.create()) {
 124  1151 try {
 125    // Don't call this.open() as it will try to read rootNode from the disk
 126  1151 super.open();
 127   
 128  1151 Page p = getFreePage();
 129  1151 long pn = p.getPageNum();
 130  1151 fileHeader.setRootPage(pn);
 131   
 132  1151 rootInfo = new BTreeRootInfo(pn);
 133   
 134    // Initialize root node
 135  1151 rootNode = new BTreeNode(p, null, new Value[0], new long[0]);
 136  1151 rootNode.ph.setStatus(LEAF);
 137  1151 rootNode.write();
 138  1151 synchronized (cache) {
 139  1151 cache.put(rootNode.page, new WeakReference(rootNode));
 140    }
 141  1151 close();
 142  1151 return true;
 143    } catch (Exception e) {
 144  0 if (log.isWarnEnabled()) {
 145  0 log.warn("Failed to create BTree, return false", e);
 146    }
 147    }
 148    }
 149  0 return false;
 150    }
 151   
 152  2541 public synchronized boolean close() throws DBException {
 153  2541 boolean closed = super.close();
 154  2541 if (closed) {
 155  2541 synchronized (cache) {
 156  2541 cache.clear();
 157    }
 158    }
 159   
 160  2541 return closed;
 161    }
 162   
 163    /**
 164    * addKey adds a Value to the BTree and associates a pointer with
 165    * it. The pointer can be used for referencing any type of data, it
 166    * just so happens that Xindice uses it for referencing pages of
 167    * associated data in the BTree file or other files.
 168    *
 169    * @param value The Value to add
 170    * @return Pointer to the value
 171    */
 172  13243 public long addKey(Value value) throws IOException, BTreeException {
 173  13243 return getRootNode().addKey(value);
 174    }
 175   
 176    /**
 177    * addValue adds a Value to the BTree and associates a pointer with
 178    * it. The pointer can be used for referencing any type of data, it
 179    * just so happens that Xindice uses it for referencing pages of
 180    * associated data in the BTree file or other files.
 181    *
 182    * @param value The Value to add
 183    * @param pointer The pointer to associate with it
 184    * @return The previous value for the pointer (or -1)
 185    */
 186  3973 public long addValue(Value value, long pointer) throws IOException, BTreeException {
 187  3973 return getRootNode().addValue(value, pointer);
 188    }
 189   
 190    /**
 191    * addValue adds a Value to the BTree and associates a pointer with
 192    * it. The pointer can be used for referencing any type of data, it
 193    * just so happens that Xindice uses it for referencing pages of
 194    * associated data in the BTree file or other files.
 195    *
 196    * @param root The BTree's root information (for nested trees)
 197    * @param value The Value to add
 198    * @param pointer The pointer to associate with it
 199    * @return The previous value for the pointer (or -1)
 200    */
 201  917 public long addValue(BTreeRootInfo root, Value value, long pointer) throws IOException, BTreeException {
 202  917 return getRootNode(root).addValue(value, pointer);
 203    }
 204   
 205    /**
 206    * removeValue removes a Value from the BTree and returns the
 207    * associated pointer for it.
 208    *
 209    * @param value The Value to remove
 210    * @return The pointer that was associated with it
 211    */
 212  2979 public long removeValue(Value value) throws IOException, BTreeException {
 213  2979 return getRootNode().removeValue(value);
 214    }
 215   
 216    /**
 217    * removeValue removes a Value from the BTree and returns the
 218    * associated pointer for it.
 219    *
 220    * @param root The BTree's root information (for nested trees)
 221    * @param value The Value to remove
 222    * @return The pointer that was associated with it
 223    */
 224  1 public long removeValue(BTreeRootInfo root, Value value) throws IOException, BTreeException {
 225  1 return getRootNode(root).removeValue(value);
 226    }
 227   
 228    /**
 229    * findValue finds a Value in the BTree and returns the associated
 230    * pointer for it.
 231    *
 232    * @param value The Value to find
 233    * @return The pointer that was associated with it
 234    */
 235  47104 public long findValue(Value value) throws IOException, BTreeException {
 236  47104 return getRootNode().findValue(value);
 237    }
 238   
 239    /**
 240    * findValue finds a Value in the BTree and returns the associated
 241    * pointer for it.
 242    *
 243    * @param root The BTree's root information (for nested trees)
 244    * @param value The Value to find
 245    * @return The pointer that was associated with it
 246    */
 247  0 public long findValue(BTreeRootInfo root, Value value) throws IOException, BTreeException {
 248  0 return getRootNode(root).findValue(value);
 249    }
 250   
 251    /**
 252    * query performs a query against the BTree and performs callback
 253    * operations to report the search results.
 254    *
 255    * @param query The IndexQuery to use (or null for everything)
 256    * @param callback The callback instance
 257    */
 258  596 public void query(IndexQuery query, BTreeCallback callback) throws IOException, BTreeException {
 259  596 getRootNode().query(query, callback);
 260    }
 261   
 262    /**
 263    * query performs a query against the BTree and performs callback
 264    * operations to report the search results.
 265    *
 266    * @param root The BTree's root information (for nested trees)
 267    * @param query The IndexQuery to use (or null for everything)
 268    * @param callback The callback instance
 269    */
 270  135 public void query(BTreeRootInfo root, IndexQuery query, BTreeCallback callback) throws IOException, BTreeException {
 271  135 getRootNode(root).query(query, callback);
 272    }
 273   
 274    /**
 275    * createBTreeRoot creates a new BTree root node in the BTree file
 276    * based on the provided value for the main tree.
 277    *
 278    * @param v The sub-tree Value to create
 279    * @return The new BTreeRootInfo instance
 280    */
 281  885 protected final BTreeRootInfo createBTreeRoot(Value v) throws IOException, BTreeException {
 282  885 BTreeNode n = createBTreeNode(BTree.LEAF, null);
 283  885 n.write();
 284   
 285  885 long position = n.page.getPageNum();
 286  885 addValue(v, position);
 287  885 return new BTreeRootInfo(v, position);
 288    }
 289   
 290    /**
 291    * createBTreeRoot creates a new BTree root node in the BTree file
 292    * based on the provided root information, and value for the tree.
 293    *
 294    * @param root The BTreeRootInfo to build off of
 295    * @param v The sub-tree Value to create
 296    * @return The new BTreeRootInfo instance
 297    */
 298  0 protected final BTreeRootInfo createBTreeRoot(BTreeRootInfo root, Value v) throws IOException, BTreeException {
 299  0 BTreeNode n = createBTreeNode(BTree.LEAF, null);
 300  0 n.write();
 301   
 302  0 long position = n.page.getPageNum();
 303  0 addValue(v, position);
 304  0 return new BTreeRootInfo(root, v, position);
 305    }
 306   
 307    /**
 308    * findBTreeRoot searches for a BTreeRoot in the file and returns
 309    * the BTreeRootInfo for the specified value based on the main tree.
 310    *
 311    * @param v The sub-tree Value to search for
 312    * @return The new BTreeRootInfo instance
 313    */
 314  918 protected final BTreeRootInfo findBTreeRoot(Value v) throws IOException, BTreeException {
 315  918 long position = findValue(v);
 316  918 return position == VALUE_DOES_NOT_EXIST ? null : new BTreeRootInfo(v, position);
 317    }
 318   
 319    /**
 320    * findBTreeRoot searches for a BTreeRoot in the file and returns
 321    * the BTreeRootInfo for the specified value based on the provided
 322    * BTreeRootInfo value.
 323    *
 324    * @param root The BTreeRootInfo to search from
 325    * @param v The sub-tree Value to search for
 326    * @return The new BTreeRootInfo instance
 327    */
 328  0 protected final BTreeRootInfo findBTreeRoot(BTreeRootInfo root, Value v) throws IOException, BTreeException {
 329  0 long position = findValue(root, v);
 330  0 return new BTreeRootInfo(root, v, position);
 331    }
 332   
 333    /**
 334    * setRootNode resets the root for the specified root object to the
 335    * provided BTreeNode's page number.
 336    *
 337    * This method is not thread safe.
 338    *
 339    * @param root The root to reset
 340    * @param newRoot the new root node to use
 341    */
 342  0 protected final void setRootNode(BTreeRootInfo root, BTreeNode newRoot) throws IOException, BTreeException {
 343  0 BTreeRootInfo parent = root.getParent();
 344  0 if (parent == null) {
 345  0 rootNode = newRoot;
 346  0 long p = rootNode.page.getPageNum();
 347  0 rootInfo.setPage(p);
 348  0 fileHeader.setRootPage(p);
 349    } else {
 350  0 long p = newRoot.page.getPageNum();
 351  0 root.setPage(p);
 352  0 addValue(parent, root.name, p);
 353    }
 354    }
 355   
 356    /**
 357    * setRootNode resets the file's root to the provided
 358    * BTreeNode's page number.
 359    *
 360    * This method is not thread safe.
 361    *
 362    * @param rootNode the new root node to use
 363    */
 364  0 protected final void setRootNode(BTreeNode rootNode) throws IOException, BTreeException {
 365  0 setRootNode(rootInfo, rootNode);
 366    }
 367   
 368    /**
 369    * getRootNode retreives the BTree node for the specified
 370    * root object.
 371    *
 372    * @param root The root object to retrieve with
 373    * @return The root node
 374    */
 375  1053 protected final BTreeNode getRootNode(BTreeRootInfo root) {
 376  1053 if (root.page == rootInfo.page) {
 377  0 return rootNode;
 378    } else {
 379  1053 return getBTreeNode(root.getPage(), null);
 380    }
 381    }
 382   
 383    /**
 384    * getRootNode retreives the BTree node for the file's root.
 385    *
 386    * @return The root node
 387    */
 388  67895 protected final BTreeNode getRootNode() {
 389  67895 return rootNode;
 390    }
 391   
 392  13743 private BTreeNode getBTreeNode(long page, BTreeNode parent) {
 393  13743 try {
 394  13743 BTreeNode node = null;
 395  13743 synchronized (cache) {
 396  13743 WeakReference ref = (WeakReference) cache.get(new PageKey(page));
 397  13743 if (ref != null) {
 398  12290 node = (BTreeNode) ref.get();
 399    }
 400   
 401  13743 if (node == null) {
 402  1508 node = new BTreeNode(getPage(page), parent);
 403    } else {
 404  12235 node.parent = parent;
 405    }
 406   
 407  13743 cache.put(node.page, new WeakReference(node));
 408    }
 409   
 410  13743 node.read();
 411  13743 return node;
 412    } catch (Exception e) {
 413  0 if (log.isWarnEnabled()) {
 414  0 log.warn("Ignored exception", e);
 415    }
 416  0 return null;
 417    }
 418    }
 419   
 420  996 private BTreeNode createBTreeNode(byte status, BTreeNode parent) throws IOException {
 421  996 Page p = getFreePage();
 422  996 BTreeNode node = new BTreeNode(p, parent, new Value[0], new long[0]);
 423  996 node.ph.setStatus(status);
 424  996 synchronized (cache) {
 425  996 cache.put(p, new WeakReference(node));
 426    }
 427  996 return node;
 428    }
 429   
 430    /**
 431    * BTreeRootInfo
 432    */
 433    public final class BTreeRootInfo {
 434    private final BTreeRootInfo parent;
 435    private final Value name;
 436    private long page;
 437   
 438  0 public BTreeRootInfo(BTreeRootInfo parent, String name, long page) {
 439  0 this.parent = parent;
 440  0 this.name = new Value(name);
 441  0 this.page = page;
 442    }
 443   
 444  0 public BTreeRootInfo(BTreeRootInfo parent, Value name, long page) {
 445  0 this.parent = parent;
 446  0 this.name = name;
 447  0 this.page = page;
 448    }
 449   
 450  0 public BTreeRootInfo(String name, long page) {
 451  0 this.parent = rootInfo;
 452  0 this.name = new Value(name);
 453  0 this.page = page;
 454    }
 455   
 456  1053 public BTreeRootInfo(Value name, long page) {
 457  1053 this.parent = rootInfo;
 458  1053 this.name = name;
 459  1053 this.page = page;
 460    }
 461   
 462  2540 private BTreeRootInfo(long page) {
 463  2540 parent = null;
 464  2540 name = null;
 465  2540 this.page = page;
 466    }
 467   
 468  0 public BTreeRootInfo getParent() {
 469  0 return parent;
 470    }
 471   
 472  0 public Value getName() {
 473  0 return name;
 474    }
 475   
 476  1053 public synchronized long getPage() {
 477  1053 return page;
 478    }
 479   
 480  0 public synchronized void setPage(long page) {
 481  0 this.page = page;
 482    }
 483    }
 484   
 485    /**
 486    * BTreeNode
 487    */
 488    private final class BTreeNode {
 489    private final Page page;
 490    private final BTreePageHeader ph;
 491    private Value[] values;
 492    private long[] ptrs;
 493    private BTreeNode parent;
 494    private boolean loaded;
 495   
 496  0 public BTreeNode(Page page) {
 497  0 this(page, null);
 498    }
 499   
 500  3655 public BTreeNode(Page page, BTreeNode parent) {
 501  3655 this.page = page;
 502  3655 this.parent = parent;
 503  3655 this.ph = (BTreePageHeader) page.getPageHeader();
 504    }
 505   
 506  2147 public BTreeNode(Page page, BTreeNode parent, Value[] values, long[] ptrs) {
 507  2147 this(page, parent);
 508  2147 set(values, ptrs);
 509  2147 this.loaded = true;
 510    }
 511   
 512    /**
 513    * Sets values and pointers.
 514    * Internal (to the BTreeNode) method, not synchronized.
 515    */
 516  18256 private void set(Value[] values, long[] ptrs) {
 517  18256 this.values = values;
 518  18256 this.ph.setValueCount((short) values.length);
 519  18256 this.ptrs = ptrs;
 520    }
 521   
 522    /**
 523    * Reads node only if it is not loaded yet
 524    */
 525  13743 public synchronized void read() throws IOException {
 526  13743 if (!this.loaded) {
 527  1508 Value v = readValue(page);
 528  1508 DataInputStream is = new DataInputStream(v.getInputStream());
 529   
 530    // Read in the Values
 531  1508 values = new Value[ph.getValueCount()];
 532  1508 for (int i = 0; i < values.length; i++) {
 533  6752 short valSize = is.readShort();
 534  6752 byte[] b = new byte[valSize];
 535   
 536  6752 is.read(b);
 537  6752 values[i] = new Value(b);
 538    }
 539   
 540    // Read in the pointers
 541  1508 ptrs = new long[ph.getPointerCount()];
 542  1508 for (int i = 0; i < ptrs.length; i++) {
 543  6752 ptrs[i] = is.readLong();
 544    }
 545   
 546  1508 this.loaded = true;
 547    }
 548    }
 549   
 550  18056 public synchronized void write() throws IOException {
 551  18056 ByteArrayOutputStream bos = new ByteArrayOutputStream(fileHeader.getWorkSize());
 552  18056 DataOutputStream os = new DataOutputStream(bos);
 553   
 554    // Write out the Values
 555  18056 for (int i = 0; i < values.length; i++) {
 556  1214898 os.writeShort(values[i].getLength());
 557  1214898 values[i].streamTo(os);
 558    }
 559   
 560    // Write out the pointers
 561  18056 for (int i = 0; i < ptrs.length; i++) {
 562  1214987 os.writeLong(ptrs[i]);
 563    }
 564   
 565  18056 writeValue(page, new Value(bos.toByteArray()));
 566    }
 567   
 568    /**
 569    * Internal (to the BTreeNode) method.
 570    * Because this method is called only by BTreeNode itself, no synchronization done inside of this method.
 571    */
 572  11301 private BTreeNode getChildNode(int idx) {
 573  11301 if (ph.getStatus() == BRANCH && idx >= 0 && idx < ptrs.length) {
 574  11301 return getBTreeNode(ptrs[idx], this);
 575    } else {
 576  0 return null;
 577    }
 578    }
 579   
 580    /* Not used
 581    private synchronized void getChildStream(int idx, Streamable stream) throws IOException {
 582    if (ph.getStatus() == LEAF && idx >= 0 && idx < ptrs.length) {
 583    Value v = readValue(ptrs[idx]);
 584    DataInputStream dis = new DataInputStream(v.getInputStream());
 585    stream.read(dis);
 586    }
 587    }
 588    */
 589   
 590  4037 public synchronized long removeValue(Value value) throws IOException, BTreeException {
 591  4037 int idx = Arrays.binarySearch(values, value);
 592   
 593  4037 switch (ph.getStatus()) {
 594  1057 case BRANCH:
 595  1057 idx = idx < 0 ? -(idx + 1) : idx + 1;
 596  1057 return getChildNode(idx).removeValue(value);
 597   
 598  2980 case LEAF:
 599  2980 if (idx < 0) {
 600  235 return VALUE_DOES_NOT_EXIST;
 601    } else {
 602  2745 long oldPtr = ptrs[idx];
 603   
 604  2745 set(deleteArrayValue(values, idx), deleteArrayLong(ptrs, idx));
 605   
 606  2745 write();
 607  2745 return oldPtr;
 608    }
 609   
 610  0 default :
 611  0 throw new BTreeCorruptException("Invalid page type '" + ph.getStatus() +
 612    "' in removeValue");
 613    }
 614    }
 615   
 616  7362 public synchronized long addValue(Value value, long pointer) throws IOException, BTreeException {
 617  7362 if (value == null) {
 618  0 throw new BTreeException(FaultCodes.DBE_CANNOT_CREATE, "Can't add a null Value");
 619    }
 620   
 621  7362 int idx = Arrays.binarySearch(values, value);
 622   
 623  7362 switch (ph.getStatus()) {
 624  2472 case BRANCH:
 625  2472 idx = idx < 0 ? -(idx + 1) : idx + 1;
 626  2472 return getChildNode(idx).addValue(value, pointer);
 627   
 628  4890 case LEAF:
 629  4890 if (idx >= 0) {
 630    // Value was found... Overwrite
 631  0 long oldPtr = ptrs[idx];
 632  0 ptrs[idx] = pointer;
 633   
 634  0 set(values, ptrs);
 635   
 636  0 write();
 637  0 return oldPtr;
 638    } else {
 639    // Value was not found
 640  4890 idx = -(idx + 1);
 641   
 642    // Check to see if we've exhausted the block
 643  4890 boolean split = needSplit(value);
 644   
 645  4890 set(insertArrayValue(values, value, idx), insertArrayLong(ptrs, pointer, idx));
 646   
 647  4890 if (split) {
 648  48 split();
 649    } else {
 650  4842 write();
 651    }
 652    }
 653  4890 return -1;
 654   
 655  0 default :
 656  0 throw new BTreeCorruptException("Invalid Page Type In addValue");
 657    }
 658    }
 659   
 660  17002 public synchronized long addKey(Value value) throws IOException, BTreeException {
 661  17002 if (value == null) {
 662  0 throw new BTreeException(FaultCodes.DBE_CANNOT_CREATE, "Can't add a null Value");
 663    }
 664   
 665  17002 int idx = Arrays.binarySearch(values, value);
 666   
 667  17002 switch (ph.getStatus()) {
 668  3759 case BRANCH:
 669  3759 idx = idx < 0 ? -(idx + 1) : idx + 1;
 670  3759 return getChildNode(idx).addKey(value);
 671   
 672  13243 case LEAF:
 673  13243 if (idx >= 0) {
 674    // Key already exists
 675  5036 return ptrs[idx];
 676    } else {
 677    // Value was not found
 678  8207 idx = -(idx + 1);
 679   
 680    // Check to see if we've exhausted the block
 681  8207 boolean split = needSplit(value);
 682   
 683  8207 long pointer = getFreePage().getPageNum();
 684  8207 set(insertArrayValue(values, value, idx), insertArrayLong(ptrs, pointer, idx));
 685   
 686  8207 if (split) {
 687  41 split();
 688    } else {
 689  8166 write();
 690    }
 691   
 692  8207 fileHeader.incRecordCount();
 693  8207 return pointer;
 694    }
 695   
 696  0 default :
 697  0 throw new BTreeCorruptException("Invalid Page Type In addValue");
 698    }
 699    }
 700   
 701  67 private synchronized void promoteValue(Value value, long rightPointer) throws IOException, BTreeException {
 702    // Check to see if we've exhausted the block
 703  67 boolean split = needSplit(value);
 704   
 705  67 int idx = Arrays.binarySearch(values, value);
 706  67 idx = idx < 0 ? -(idx + 1) : idx + 1;
 707   
 708  67 set(insertArrayValue(values, value, idx), insertArrayLong(ptrs, rightPointer, idx + 1));
 709   
 710  67 if (split) {
 711  0 split();
 712    } else {
 713  67 write();
 714    }
 715    }
 716   
 717  89 private Value getSeparator(Value value1, Value value2) {
 718  89 int idx = value1.compareTo(value2);
 719  89 byte[] b = new byte[Math.abs(idx)];
 720  89 value2.copyTo(b, 0, b.length);
 721  89 return new Value(b);
 722    }
 723   
 724    /**
 725    * Do we need to split this node after adding one more value?
 726    */
 727  13164 private boolean needSplit(Value value) {
 728    // Do NOT split if just 4 key/values are in the node.
 729  13164 return this.values.length > 4 &&
 730    // CurrLength + one Long pointer + value length + one short
 731    this.ph.getDataLen() + 8 + value.getLength() + 2 > BTree.this.fileHeader.getWorkSize();
 732    }
 733   
 734    /**
 735    * Internal to the BTreeNode method
 736    */
 737  89 private void split() throws IOException, BTreeException {
 738  89 Value[] leftVals;
 739  89 Value[] rightVals;
 740  89 long[] leftPtrs;
 741  89 long[] rightPtrs;
 742  89 Value separator;
 743   
 744  89 short vc = ph.getValueCount();
 745  89 int pivot = vc / 2;
 746   
 747    // Split the node into two nodes
 748  89 switch (ph.getStatus()) {
 749  0 case BRANCH:
 750  0 leftVals = new Value[pivot];
 751  0 leftPtrs = new long[leftVals.length + 1];
 752  0 rightVals = new Value[vc - (pivot + 1)];
 753  0 rightPtrs = new long[rightVals.length + 1];
 754   
 755  0 System.arraycopy(values, 0, leftVals, 0, leftVals.length);
 756  0 System.arraycopy(ptrs, 0, leftPtrs, 0, leftPtrs.length);
 757  0 System.arraycopy(values, leftVals.length + 1, rightVals, 0, rightVals.length);
 758  0 System.arraycopy(ptrs, leftPtrs.length, rightPtrs, 0, rightPtrs.length);
 759   
 760  0 separator = values[leftVals.length];
 761  0 break;
 762   
 763  89 case LEAF:
 764  89 leftVals = new Value[pivot];
 765  89 leftPtrs = new long[leftVals.length];
 766  89 rightVals = new Value[vc - pivot];
 767  89 rightPtrs = new long[rightVals.length];
 768   
 769  89 System.arraycopy(values, 0, leftVals, 0, leftVals.length);
 770  89 System.arraycopy(ptrs, 0, leftPtrs, 0, leftPtrs.length);
 771  89 System.arraycopy(values, leftVals.length, rightVals, 0, rightVals.length);
 772  89 System.arraycopy(ptrs, leftPtrs.length, rightPtrs, 0, rightPtrs.length);
 773   
 774  89 separator = getSeparator(leftVals[leftVals.length - 1], rightVals[0]);
 775  89 break;
 776   
 777  0 default :
 778  0 throw new BTreeCorruptException("Invalid Page Type In split");
 779    }
 780   
 781    // Promote the pivot to the parent branch
 782  89 if (parent == null) {
 783    // This can only happen if this is the root
 784  22 BTreeNode rNode = createBTreeNode(ph.getStatus(), this);
 785  22 rNode.set(rightVals, rightPtrs);
 786   
 787  22 BTreeNode lNode = createBTreeNode(ph.getStatus(), this);
 788  22 lNode.set(leftVals, leftPtrs);
 789   
 790  22 ph.setStatus(BRANCH);
 791  22 set(new Value[] {
 792    separator
 793    },
 794    new long[] {
 795    lNode.page.getPageNum(),
 796    rNode.page.getPageNum()
 797    });
 798   
 799  22 write();
 800  22 rNode.write();
 801  22 lNode.write();
 802    } else {
 803  67 set(leftVals, leftPtrs);
 804   
 805  67 BTreeNode rNode = createBTreeNode(ph.getStatus(), parent);
 806  67 rNode.set(rightVals, rightPtrs);
 807   
 808  67 write();
 809  67 rNode.write();
 810  67 parent.promoteValue(separator,
 811    rNode.page.getPageNum());
 812    }
 813    }
 814   
 815    /////////////////////////////////////////////////////////////////
 816   
 817  51016 public synchronized long findValue(Value value) throws IOException, BTreeException {
 818  51016 if (value == null) {
 819  0 throw new BTreeException(FaultCodes.DBE_CANNOT_READ, "Can't search on null Value");
 820    }
 821   
 822  51016 int idx = Arrays.binarySearch(values, value);
 823   
 824  51016 switch (ph.getStatus()) {
 825  3912 case BRANCH:
 826  3912 idx = idx < 0 ? -(idx + 1) : idx + 1;
 827  3912 return getChildNode(idx).findValue(value);
 828   
 829  47104 case LEAF:
 830  47104 if (idx < 0) {
 831  9880 return VALUE_DOES_NOT_EXIST;
 832    } else {
 833  37224 return ptrs[idx];
 834    }
 835   
 836  0 default :
 837  0 throw new BTreeCorruptException("Invalid page type '" + ph.getStatus() +
 838    "' in findValue");
 839    }
 840    }
 841   
 842    // query is a BEAST of a method
 843  832 public synchronized void query(IndexQuery query, BTreeCallback callback) throws IOException, BTreeException {
 844  832 if (query != null && query.getOperator() != IndexQuery.ANY) {
 845  102 Value[] qvals = query.getValues();
 846  102 int n;
 847  102 int leftIdx = Arrays.binarySearch(values, qvals[0]);
 848  102 int rightIdx = qvals.length > 1 ? Arrays.binarySearch(values, qvals[qvals.length - 1]) : leftIdx;
 849   
 850  102 switch (ph.getStatus()) {
 851  9 case BRANCH:
 852  9 leftIdx = leftIdx < 0 ? -(leftIdx + 1) : leftIdx + 1;
 853  9 rightIdx = rightIdx < 0 ? -(rightIdx + 1) : rightIdx + 1;
 854   
 855  9 switch (query.getOperator()) {
 856  0 case IndexQuery.BWX:
 857  0 case IndexQuery.BW:
 858  0 case IndexQuery.IN:
 859  9 case IndexQuery.SW:
 860    // TODO: Can leftIdx be less than 0 here?
 861  9 if (leftIdx < 0) {
 862  0 leftIdx = 0;
 863    }
 864  9 if (rightIdx > ptrs.length - 1) {
 865  0 rightIdx = ptrs.length - 1;
 866    }
 867  9 for (int i = leftIdx; i <= rightIdx; i++) {
 868  9 getChildNode(i).query(query, callback);
 869    }
 870  9 break;
 871   
 872  0 case IndexQuery.NBWX:
 873  0 case IndexQuery.NBW:
 874  0 case IndexQuery.NIN:
 875  0 case IndexQuery.NSW:
 876  0 if (leftIdx > ptrs.length - 1) {
 877  0 leftIdx = ptrs.length - 1;
 878    }
 879  0 for (int i = 0; i <= leftIdx; i++) {
 880  0 getChildNode(i).query(query, callback);
 881    }
 882  0 if (rightIdx < 0) {
 883  0 rightIdx = 0;
 884    }
 885  0 for (int i = rightIdx; i < ptrs.length; i++) {
 886  0 getChildNode(i).query(query, callback);
 887    }
 888  0 break;
 889   
 890  0 case IndexQuery.EQ:
 891  0 getChildNode(leftIdx).query(query, callback);
 892  0 break;
 893   
 894  0 case IndexQuery.LT:
 895  0 case IndexQuery.LEQ:
 896  0 if (leftIdx > ptrs.length - 1) {
 897  0 leftIdx = ptrs.length - 1;
 898    }
 899  0 for (int i = 0; i <= leftIdx; i++) {
 900  0 getChildNode(i).query(query, callback);
 901    }
 902  0 break;
 903   
 904  0 case IndexQuery.GT:
 905  0 case IndexQuery.GEQ:
 906  0 if (rightIdx < 0) {
 907  0 rightIdx = 0;
 908    }
 909  0 for (int i = rightIdx; i < ptrs.length; i++) {
 910  0 getChildNode(i).query(query, callback);
 911    }
 912  0 break;
 913   
 914  0 case IndexQuery.NEQ:
 915  0 default :
 916  0 for (int i = 0; i < ptrs.length; i++) {
 917  0 getChildNode(i).query(query, callback);
 918    }
 919  0 break;
 920    }
 921  9 break;
 922   
 923  93 case LEAF:
 924  93 switch (query.getOperator()) {
 925  19 case IndexQuery.EQ:
 926  19 if (leftIdx >= 0) {
 927  19 callback.indexInfo(values[leftIdx], ptrs[leftIdx]);
 928    }
 929  19 break;
 930   
 931  2 case IndexQuery.NEQ:
 932  2 for (int i = 0; i < ptrs.length; i++) {
 933  8 if (i != leftIdx) {
 934  6 callback.indexInfo(values[i], ptrs[i]);
 935    }
 936    }
 937  2 break;
 938   
 939  1 case IndexQuery.BWX:
 940  2 case IndexQuery.BW:
 941  51 case IndexQuery.SW:
 942  1 case IndexQuery.IN:
 943  55 if (leftIdx < 0) {
 944  50 leftIdx = -(leftIdx + 1);
 945    }
 946  55 if (rightIdx < 0) {
 947  51 rightIdx = -(rightIdx + 1);
 948    }
 949  55 n = Math.min(rightIdx + 1, ptrs.length);
 950  55 for (int i = leftIdx; i < n; i++){
 951  80 if (query.testValue(values[i])) {
 952  72 callback.indexInfo(values[i], ptrs[i]);
 953    }
 954    }
 955  55 break;
 956   
 957  1 case IndexQuery.NBWX:
 958  1 case IndexQuery.NBW:
 959  0 case IndexQuery.NSW:
 960    // FIXME: Looks like operators are not used now. Need query optimizer?
 961  2 if (leftIdx < 0) {
 962  0 leftIdx = -(leftIdx + 1);
 963    }
 964  2 if (rightIdx < 0) {
 965  0 rightIdx = -(rightIdx + 1);
 966    }
 967  2 for (int i = 0; i < ptrs.length; i++) {
 968  8 if ((i <= leftIdx || i >= rightIdx) && query.testValue(values[i])) {
 969  5 callback.indexInfo(values[i], ptrs[i]);
 970    }
 971    }
 972  2 break;
 973   
 974  5 case IndexQuery.LT:
 975  2 case IndexQuery.LEQ:
 976  7 if (leftIdx < 0) {
 977  1 leftIdx = -(leftIdx + 1);
 978    }
 979  7 n = Math.min(leftIdx + 1, ptrs.length);
 980  7 for (int i = 0; i < n; i++) {
 981  27 if (query.testValue(values[i])) {
 982  22 callback.indexInfo(values[i], ptrs[i]);
 983    }
 984    }
 985  7 break;
 986   
 987  5 case IndexQuery.GT:
 988  2 case IndexQuery.GEQ:
 989  7 if (rightIdx < 0) {
 990  0 rightIdx = -(rightIdx + 1);
 991    }
 992  7 for (int i = rightIdx; i < ptrs.length; i++) {
 993  14 if (query.testValue(values[i])) {
 994  9 callback.indexInfo(values[i], ptrs[i]);
 995    }
 996    }
 997  7 break;
 998   
 999  1 case IndexQuery.NIN:
 1000  0 default :
 1001  1 for (int i = 0; i < ptrs.length; i++) {
 1002  4 if (query.testValue(values[i])) {
 1003  2 callback.indexInfo(values[i], ptrs[i]);
 1004    }
 1005    }
 1006  1 break;
 1007    }
 1008  93 break;
 1009   
 1010  0 default :
 1011  0 throw new BTreeCorruptException("Invalid Page Type In query");
 1012    }
 1013   
 1014    } else {
 1015    // No Query - Just Walk The Tree
 1016  730 switch (ph.getStatus()) {
 1017  18 case BRANCH:
 1018  18 for (int i = 0; i < ptrs.length; i++) {
 1019  92 getChildNode(i).query(query, callback);
 1020    }
 1021  18 break;
 1022   
 1023  712 case LEAF:
 1024  712 for (int i = 0; i < values.length; i++) {
 1025  51871 callback.indexInfo(values[i], ptrs[i]);
 1026    }
 1027  712 break;
 1028   
 1029  0 default :
 1030  0 throw new BTreeCorruptException("Invalid Page Type In query");
 1031    }
 1032    }
 1033    }
 1034    }
 1035   
 1036    ////////////////////////////////////////////////////////////////////
 1037   
 1038  91 protected FileHeader createFileHeader() {
 1039  91 return new BTreeFileHeader();
 1040    }
 1041   
 1042  1118 protected PageHeader createPageHeader() {
 1043  1118 return new BTreePageHeader();
 1044    }
 1045   
 1046    /**
 1047    * BTreeFileHeader
 1048    */
 1049   
 1050    protected class BTreeFileHeader extends FileHeader {
 1051    private long rootPage;
 1052   
 1053  1392 public BTreeFileHeader() {
 1054    }
 1055   
 1056  2540 protected synchronized void read(RandomAccessFile raf) throws IOException {
 1057  2540 super.read(raf);
 1058  2540 rootPage = raf.readLong();
 1059    }
 1060   
 1061  18258 protected synchronized void write(RandomAccessFile raf) throws IOException {
 1062  18258 super.write(raf);
 1063  18258 raf.writeLong(rootPage);
 1064    }
 1065   
 1066    /** The root page of the storage tree */
 1067  1151 public synchronized final void setRootPage(long rootPage) {
 1068  1151 this.rootPage = rootPage;
 1069  1151 setDirty();
 1070    }
 1071   
 1072    /** The root page of the storage tree */
 1073  1389 public synchronized final long getRootPage() {
 1074  1389 return rootPage;
 1075    }
 1076    }
 1077   
 1078    /**
 1079    * BTreePageHeader
 1080    */
 1081   
 1082    protected class BTreePageHeader extends PageHeader {
 1083    private short valueCount;
 1084   
 1085  47937 public BTreePageHeader() {
 1086    }
 1087   
 1088  0 public BTreePageHeader(DataInput dis) throws IOException {
 1089  0 super(dis);
 1090    }
 1091   
 1092  38471 public synchronized void read(DataInput dis) throws IOException {
 1093  38471 super.read(dis);
 1094  38471 if (getStatus() == UNUSED) {
 1095  3 return;
 1096    }
 1097   
 1098  38468 valueCount = dis.readShort();
 1099    }
 1100   
 1101  33596 public synchronized void write(DataOutput dos) throws IOException {
 1102  33596 super.write(dos);
 1103  33596 dos.writeShort(valueCount);
 1104    }
 1105   
 1106    /** The number of values stored by this page */
 1107  18256 public synchronized final void setValueCount(short valueCount) {
 1108  18256 this.valueCount = valueCount;
 1109  18256 setDirty();
 1110    }
 1111   
 1112    /** The number of values stored by this page */
 1113  1597 public synchronized final short getValueCount() {
 1114  1597 return valueCount;
 1115    }
 1116   
 1117    /** The number of pointers stored by this page */
 1118  1508 public synchronized final short getPointerCount() {
 1119  1508 if (getStatus() == BRANCH) {
 1120  0 return (short) (valueCount + 1);
 1121    } else {
 1122  1508 return valueCount;
 1123    }
 1124    }
 1125    }
 1126    }
 
CloverReport generated by Clover Code Coverage v1.3.13
Sun Nov 1 2009 23:10:27 UTC.		   Open Source License registered to the Apache Xindice Project. This license of Clover is provided to support the development of Apache Xindice only.