btree.java

JXTA&#8482 is a set of open, generalized peer-to-peer (P2P) protocols that allow any networked devi

package net.jxta.impl.xindice.core.filer;


/*
 * The Apache Software License, Version 1.1
 *
 *
 * Copyright (c) 1999 The Apache Software Foundation.  All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 *
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in
 *    the documentation and/or other materials provided with the
 *    distribution.
 *
 * 3. The end-user documentation included with the redistribution,
 *    if any, must include the following acknowledgment:
 *       "This product includes software developed by the
 *        Apache Software Foundation (http://www.apache.org/)."
 *    Alternately, this acknowledgment may appear in the software itself,
 *    if and wherever such third-party acknowledgments normally appear.
 *
 * 4. The names "Xindice" and "Apache Software Foundation" must
 *    not be used to endorse or promote products derived from this
 *    software without prior written permission. For written
 *    permission, please contact [e-mail].
 *
 * 5. Products derived from this software may not be called "Apache",
 *    nor may "Apache" appear in their name, without prior written
 *    permission of the Apache Software Foundation.
 *
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED.  IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 * ====================================================================
 *
 * This software consists of voluntary contributions made by many
 * individuals on behalf of the Apache Software Foundation and was
 * originally based on software copyright (c) 1999-2001, The dbXML
 * Group, L.L.C., http://www.dbxmlgroup.com.  For more
 * information on the Apache Software Foundation, please see
 * <http://www.apache.org/>.
 *

 */

import net.jxta.impl.xindice.core.DBException;
import net.jxta.impl.xindice.core.FaultCodes;
import net.jxta.impl.xindice.core.data.Value;
import net.jxta.impl.xindice.core.indexer.IndexQuery;

import java.io.ByteArrayOutputStream;
import java.io.DataInputStream;
import java.io.DataOutputStream;
import java.io.File;
import java.io.IOException;
import java.io.RandomAccessFile;
import java.lang.ref.WeakReference;
import java.util.Arrays;
import java.util.Map;
import java.util.WeakHashMap;

import java.util.logging.Level;
import net.jxta.logging.Logging;
import java.util.logging.Logger;


/**
 * BTree represents a Variable Magnitude Simple-Prefix B+Tree File.
 * A BTree is a bit flexible in that it can be used for set or
 * map-based indexing.  HashFiler uses the BTree as a set for
 * producing RecordSet entries.  The Indexers use BTree as a map for
 * indexing entity and attribute values in Documents.
 * <br><br>
 * For those who don't know how a Simple-Prefix B+Tree works, the primary
 * distinction is that instead of promoting actual keys to branch pages,
 * when leaves are split, a shortest-possible separator is generated at
 * the pivot.  That separator is what is promoted to the parent branch
 * (and continuing up the list).  As a result, actual keys and pointers
 * can only be found at the leaf level.  This also affords the index the
 * ability to ignore costly merging and redistribution of pages when
 * deletions occur.  Deletions only affect leaf pages in this
 * implementation, and so it is entirely possible for a leaf page to be
 * completely empty after all of its keys have been removed.
 * <br><br>
 * Also, the Variable Magnitude attribute means that the btree attempts
 * to store as many values and pointers on one page as is possible.
 * <br><br>
 * This implementation supports the notion of nested roots.  This means
 * that you can create a btree where the pointers actually point to the
 * root of a separate btree being managed in the same file.
 */

public class BTree extends Paged {
    private final static Logger LOG = Logger.getLogger(BTree.class.getName());
    protected static final byte LEAF = 1;
    protected static final byte BRANCH = 2;
    protected static final byte STREAM = 3;

    /**
     * Cache of the recently used tree nodes.
     *
     * Cache contains weak references to the BTreeNode objects, keys are page numbers (Long objects).
     * Access synchronized by this map itself.
     */
    private final Map<Long, WeakReference<BTreeNode>> cache = new WeakHashMap<Long, WeakReference<BTreeNode>>();

    private BTreeFileHeader fileHeader;
    private BTreeRootInfo rootInfo;
    private BTreeNode rootNode;

    public BTree() {
        super();
        fileHeader = (BTreeFileHeader) getFileHeader();
    }

    public BTree(File file) {
        this();
        setFile(file);
    }

    /**
     * Setting this option forces all system buffers with the underlying device
     * if sync is set writes return after all modified data and attributes of the DB
     * have been written to the device.
     * by default sync is true.
     * {@link java.io.FileDescriptor}
     * @param sync if true, invokes FD.sync(), an expensive operation, required to ensure high consistency, especially
     * with system failures.
     */
    public void setSync(boolean sync) {
        this.sync = sync;
    }

    @Override
    public boolean open() throws DBException {
        if (super.open()) {
            long p = fileHeader.getRootPage();

            rootInfo = new BTreeRootInfo(p);
            rootNode = getBTreeNode(p, null);
            return true;
        } else {
            return false;
        }
    }

    @Override
    public boolean create() throws DBException {
        if (super.create()) {
            try {
                // Don't call this.open() as it will try to read rootNode from the disk
                super.open();

                long p = fileHeader.getRootPage();

                rootInfo = new BTreeRootInfo(p);

                // Initialize root node
                rootNode = new BTreeNode(getPage(p), null, new Value[0], new long[0]);
                rootNode.ph.setStatus(LEAF);
                rootNode.write();
                synchronized (cache) {
                    cache.put(rootNode.page.getPageNum(), new WeakReference<BTreeNode>(rootNode));
                }
                close();
                return true;
            } catch (Exception e) {
                if (Logging.SHOW_WARNING && LOG.isLoggable(Level.WARNING)) {
                    LOG.log(Level.WARNING, "Failed to create BTree, return false", e);
                }
            }
        }
        return false;
    }

    /**
     * addValue adds a Value to the BTree and associates a pointer with
     * it.  The pointer can be used for referencing any type of data, it
     * just so happens that Xindice uses it for referencing pages of
     * associated data in the BTree file or other files.
     *
     * @param value The Value to add
     * @param pointer The pointer to associate with it
     * @return The previous value for the pointer (or -1)
     * @throws java.io.IOException if an io error occurs
     * @throws BTreeException if a DB exception occurs
     */
    public long addValue(Value value, long pointer) throws IOException, BTreeException {
        return getRootNode().addValue(value, pointer);
    }

    /**
     * addValue adds a Value to the BTree and associates a pointer with
     * it.  The pointer can be used for referencing any type of data, it
     * just so happens that Xindice uses it for referencing pages of
     * associated data in the BTree file or other files.
     *
     * @param root The BTree's root information (for nested trees)
     * @param value The Value to add
     * @param pointer The pointer to associate with it
     * @return The previous value for the pointer (or -1)
     * @throws java.io.IOException if an io error occurs
     * @throws BTreeException if a DB exception occurs
     */
    public long addValue(BTreeRootInfo root, Value value, long pointer) throws IOException, BTreeException {
        return getRootNode(root).addValue(value, pointer);
    }

    /**
     * removeValue removes a Value from the BTree and returns the
     * associated pointer for it.
     *
     * @param value The Value to remove
     * @return The pointer that was associated with it
     * @throws java.io.IOException if an io error occurs
     * @throws BTreeException if a DB exception occurs
     */
    public long removeValue(Value value) throws IOException, BTreeException {
        return getRootNode().removeValue(value);
    }

    /**
     * removeValue removes a Value from the BTree and returns the
     * associated pointer for it.
     *
     * @param root The BTree's root information (for nested trees)
     * @param value The Value to remove
     * @return The pointer that was associated with it
     * @throws java.io.IOException if an io error occurs
     * @throws BTreeException if a DB exception occurs
     */
    public long removeValue(BTreeRootInfo root, Value value) throws IOException, BTreeException {
        return getRootNode(root).removeValue(value);
    }

    /**
     * findValue finds a Value in the BTree and returns the associated
     * pointer for it.
     *
     * @param value The Value to find
     * @return The pointer that was associated with it
     * @throws java.io.IOException if an io error occurs
     * @throws BTreeException if a DB exception occurs
     */
    public long findValue(Value value) throws IOException, BTreeException {
        return getRootNode().findValue(value);
    }

    /**
     * findValue finds a Value in the BTree and returns the associated
     * pointer for it.
     *
     * @param root The BTree's root information (for nested trees)
     * @param value The Value to find
     * @return The pointer that was associated with it
     * @throws java.io.IOException if an io error occurs
     * @throws BTreeException if a DB exception occurs
     */
    public long findValue(BTreeRootInfo root, Value value) throws IOException, BTreeException {
        return getRootNode(root).findValue(value);
    }

    /**
     * query performs a query against the BTree and performs callback
     * operations to report the search results.
     *
     * @param query The IndexQuery to use (or null for everything)
     * @param callback The callback instance
     * @throws java.io.IOException if an io error occurs
     * @throws BTreeException if a DB exception occurs
     */
    public void query(IndexQuery query, BTreeCallback callback) throws IOException, BTreeException {
        getRootNode().query(query, callback);
    }

    /**
     * query performs a query against the BTree and performs callback
     * operations to report the search results.
     *
     * @param root The BTree's root information (for nested trees)
     * @param query The IndexQuery to use (or null for everything)
     * @param callback The callback instance
     * @throws java.io.IOException if an io error occurs
     * @throws BTreeException if a DB exception occurs
     */
    public void query(BTreeRootInfo root, IndexQuery query, BTreeCallback callback) throws IOException, BTreeException {
        getRootNode(root).query(query, callback);
    }

    /**
     * createBTreeRoot creates a new BTree root node in the BTree file
     * based on the provided value for the main tree.
     *
     * @param v The sub-tree Value to create
     * @return The new BTreeRootInfo instance
     * @throws java.io.IOException if an io error occurs
     * @throws BTreeException if a DB exception occurs
     */
    protected final BTreeRootInfo createBTreeRoot(Value v) throws IOException, BTreeException {
        BTreeNode n = createBTreeNode(BTree.LEAF, null);
        n.write();
        long position = n.page.getPageNum();

        addValue(v, position);
        return new BTreeRootInfo(v, position);
    }

    /**
     * createBTreeRoot creates a new BTree root node in the BTree file
     * based on the provided root information, and value for the tree.
     *
     * @param root The BTreeRootInfo to build off of
     * @param v The sub-tree Value to create
     * @return The new BTreeRootInfo instance
     * @throws java.io.IOException if an io error occurs
     * @throws BTreeException if a DB exception occurs
     */
    protected final BTreeRootInfo createBTreeRoot(BTreeRootInfo root, Value v) throws IOException, BTreeException {
        BTreeNode n = createBTreeNode(BTree.LEAF, null);

        n.write();

        long position = n.page.getPageNum();

        addValue(v, position);
        return new BTreeRootInfo(root, v, position);
    }

    /**
     * findBTreeRoot searches for a BTreeRoot in the file and returns
     * the BTreeRootInfo for the specified value based on the main tree.
     *
     * @param v The sub-tree Value to search for
     * @return The new BTreeRootInfo instance
     * @throws java.io.IOException if an io error occurs
     * @throws BTreeException if a DB exception occurs
     */
    protected final BTreeRootInfo findBTreeRoot(Value v) throws IOException, BTreeException {
        long position = findValue(v);

        return new BTreeRootInfo(v, position);
    }

    /**
     * findBTreeRoot searches for a BTreeRoot in the file and returns
     * the BTreeRootInfo for the specified value based on the provided
     * BTreeRootInfo value.
     *
     * @param root The BTreeRootInfo to search from
     * @param v The sub-tree Value to search for
     * @return The new BTreeRootInfo instance
     * @throws java.io.IOException if an io error occurs
     * @throws BTreeException if a DB exception occurs
     */
    protected final BTreeRootInfo findBTreeRoot(BTreeRootInfo root, Value v) throws IOException, BTreeException {
        long position = findValue(root, v);

        return new BTreeRootInfo(root, v, position);
    }

    /**
     * setRootNode resets the root for the specified root object to the
     * provided BTreeNode's page number.
     *
     * This method is not thread safe.
     *
     * @param root The root to reset
     * @param newRoot the new root node to use
     * @throws java.io.IOException if an io error occurs
     * @throws BTreeException if a DB exception occurs
     */
    protected final void setRootNode(BTreeRootInfo root, BTreeNode newRoot) throws IOException, BTreeException {
        BTreeRootInfo parent = root.getParent();

        if (parent == null) {
            rootNode = newRoot;
            long p = rootNode.page.getPageNum();

            rootInfo.setPage(p);
            fileHeader.setRootPage(p);
        } else {
            long p = newRoot.page.getPageNum();