btree.java

derby database source code.good for you.

/*

   Derby - Class org.apache.derby.impl.store.access.btree.BTree

   Copyright 1997, 2004 The Apache Software Foundation or its licensors, as applicable.

   Licensed under the Apache License, Version 2.0 (the "License");
   you may not use this file except in compliance with the License.
   You may obtain a copy of the License at

      http://www.apache.org/licenses/LICENSE-2.0

   Unless required by applicable law or agreed to in writing, software
   distributed under the License is distributed on an "AS IS" BASIS,
   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   See the License for the specific language governing permissions and
   limitations under the License.

 */

package org.apache.derby.impl.store.access.btree;


import org.apache.derby.iapi.reference.SQLState;

import org.apache.derby.iapi.services.io.ArrayInputStream;
import org.apache.derby.iapi.services.io.FormatableBitSet;

import org.apache.derby.iapi.services.monitor.Monitor;
import org.apache.derby.iapi.services.sanity.SanityManager;

import org.apache.derby.iapi.services.io.FormatIdUtil;
import org.apache.derby.iapi.services.io.Storable;

import org.apache.derby.iapi.services.stream.InfoStreams;


import org.apache.derby.iapi.error.StandardException;
import org.apache.derby.iapi.store.access.conglomerate.Conglomerate;
import org.apache.derby.iapi.store.access.conglomerate.ScanManager;
import org.apache.derby.iapi.store.access.conglomerate.TransactionManager;
import org.apache.derby.iapi.store.access.ConglomerateController;
import org.apache.derby.iapi.store.access.DynamicCompiledOpenConglomInfo;
import org.apache.derby.iapi.store.access.Qualifier;
import org.apache.derby.iapi.store.access.RowLocationRetRowSource;
import org.apache.derby.iapi.store.access.RowUtil;
import org.apache.derby.iapi.store.access.ScanController;
import org.apache.derby.iapi.store.access.StaticCompiledOpenConglomInfo;
import org.apache.derby.iapi.store.access.TransactionController;

import org.apache.derby.iapi.store.raw.LockingPolicy;
import org.apache.derby.iapi.store.raw.Page;
import org.apache.derby.iapi.store.raw.RawStoreFactory;
import org.apache.derby.iapi.store.raw.RecordHandle;
import org.apache.derby.iapi.store.raw.ContainerHandle;
import org.apache.derby.iapi.store.raw.Transaction;
import org.apache.derby.iapi.store.raw.ContainerKey;

import org.apache.derby.iapi.types.DataValueDescriptor;

import org.apache.derby.iapi.types.RowLocation;

import org.apache.derby.impl.store.access.conglomerate.ConglomerateUtil;
import org.apache.derby.impl.store.access.conglomerate.GenericConglomerate;
import org.apache.derby.impl.store.access.conglomerate.OpenConglomerateScratchSpace;
import org.apache.derby.impl.store.access.conglomerate.TemplateRow;


import java.io.IOException;
import java.io.ObjectOutput;
import java.io.ObjectInput;

import java.util.Properties;


/**

  A b-tree object corresponds to an instance of a b-tree conglomerate.  It 
  contains the static information about a conglomerate which is built at 
  create conglomerate time.
  <p>
  This generic implementation is expected to be extended by the concreate
  implementations.
  <P>
  The fields are set when the conglomerate is created and never changed 
  thereafter.  When alter table is supported then it will change under the
  control of a table level lock.
  <p>
  They have package scope because they're read by the scans and controllers.
  <p>
  A table of all conglomerates in the system is maintained by the accessmanager.
  A cache of conglomerates is maintained in the accessmanager, and references
  to the read only objects are handed out.  A copy of the Conglomerate
  object is kept in the control row of the root page, so that during logical
  undo this information can be read without needing to access the possibly
  corrupt table maintained by the access manager.
**/

public abstract class BTree extends GenericConglomerate
{
    /**************************************************************************
     * Public Constants of BTree class:
     **************************************************************************
     */

    /**
     * The page number of the root page is always at the fixed page number:
     * ROOTPAGEID.  This means that given an open container, during logical
     * undo one can always find the root page and look up the conglomerate
     * information.
     **/
    public static final long ROOTPAGEID = ContainerHandle.FIRST_PAGE_NUMBER;

	/** 
    Property name for the maximum number of rows to place in a btree page (leaf
    or branch).  Equal to 'derby.access.btreeMaxRowPerPage'.  Used by tests
    and debugging to exactly control split points, and to make it easier to test
    tall trees without needing lots of data.
	*/
	public static final String PROPERTY_MAX_ROWS_PER_PAGE_PARAMETER = 
        (SanityManager.DEBUG ?  "derby.access.btreeMaxRowPerPage" : null);

    /* properties of a btree see create(). */
    public static final String PROPERTY_ALLOWDUPLICATES = "allowDuplicates";
    public static final String PROPERTY_NKEYFIELDS      = "nKeyFields";
    public static final String PROPERTY_NUNIQUECOLUMNS  = "nUniqueColumns";
    public static final String PROPERTY_PARENTLINKS     = "maintainParentLinks";



    /**************************************************************************
     * Protected Fields of BTree class:
     **************************************************************************
     */

	/**
	The id of the container in which this b-tree is stored. 
	**/
	protected ContainerKey id;

	/**
	The number of key fields.
	**/
	protected int nKeyFields;

	/**
	The number of uniqueness columns.  These are the columns that
	are considered for the purpose of detecting duplicate keys and rows.
	**/
	int nUniqueColumns;

	/**
	Whether the index allows duplicates or not.
	**/
	boolean allowDuplicates;

	/**
	Whether the parent should maintain links from child pages to their parent.
	These links are only used for consistency checking purposes.  They improve
	consistency checking at the cost of run-time efficiency.
	**/
	boolean maintainParentLinks;

    /**
    Maximum rows per page to place on a btree leaf or nonleaf page.  Used
    by testing to finely control split points.  Only changed for debugging
    purposes.

    RESOLVE (mikem) - this should not be static.  Need to design a way in
    debugging mode to get btree created with a persistent "maxRowsPerPage".
    This hack makes all btrees get created with the "last" maxRowsPerPage 
    value set.
    **/
    static int maxRowsPerPage = Integer.MAX_VALUE;

	/**
    Format id of the conglomerate.
	**/
	protected int conglom_format_id;

    /**
    The array of format id's, one for each column in the template.
    **/
    int[]    format_ids;

	//columns sorting order information
	// true - Ascending Order ; false -Descending Order
	protected boolean[]	ascDescInfo;

	/*
	** Private Methods of BTree.
	*/

	/*
	** Public Methods of BTree.
	*/


    /**************************************************************************
     * Abstract Protected locking methods of BTree:
     *     getBtreeLockingPolicy
     *     lockScan
     *     unlockScan
     *     lockPreviousRow
     *     lockRowOnPage
     *     lockRow
     *     lockTable
     **************************************************************************
     */

    /**
     * Create a new btree locking policy from scratch.
     *
	 * @exception  StandardException  Standard exception policy.
     **/
    abstract protected BTreeLockingPolicy getBtreeLockingPolicy(
    Transaction             rawtran,
    int                     lock_level,
    int                     mode,
    int                     isolation_level,
    ConglomerateController  base_cc,
    OpenBTree               open_btree)
		throws StandardException;

    /**
     * Lock the base table.
     * <p>
     * Assumes that segment of the base container is the same as the segment
     * of the btree segment.
     * <p>
     * RESOLVE - we really want to get the lock without opening the container.
     * raw store will be providing this.
     *
     * @param xact_manager Transaction to associate the lock with.
     *
	 * @exception  StandardException  Standard exception policy.
     **/
    abstract public ConglomerateController lockTable(
    TransactionManager  xact_manager,
    int                 open_mode,
    int                 lock_level,
    int                 isolation_level)
		throws StandardException;


    /**************************************************************************
     * Private/Protected methods of BTree:
     **************************************************************************
     */


    /**
     * Create a branch row template for this conglomerate.
     * <p>
     * Reads the format id's of each of the columns and manufactures object of
     * the given type for each.  It then uses these "empty" objects to create
     * a template row.  The object passed in is then added to the last column
     * of the row.
     *
	 * @return The new template.
     *
	 * @exception  StandardException  Standard exception policy.
     **/
    final DataValueDescriptor[] createBranchTemplate(
    DataValueDescriptor page_ptr)
        throws StandardException
    {
        return(TemplateRow.newBranchRow(format_ids, page_ptr));
    }


    /**************************************************************************
     * Public methods of BTree:
     **************************************************************************
     */

    /**
     * Create a template for this conglomerate.
     * <p>
     * Reads the format id's of each of the columns and manufactures object of
     * the given type for each.  It then uses these "empty" objects to create
     * a template row.
     * <p>
     * This method is public so that B2IUndo() can call it.
     *
	 * @return The new template.
     *
	 * @exception  StandardException  Standard exception policy.
     **/
    final public DataValueDescriptor[] createTemplate()
        throws StandardException
    {
        if (SanityManager.DEBUG)
            SanityManager.ASSERT(format_ids != null);

        return(TemplateRow.newRow((FormatableBitSet) null, format_ids));
    }

    /**
     * Is this a "unique" index?
     **/
    final public boolean isUnique()
    {
        return(nKeyFields != nUniqueColumns);
    }

    /**************************************************************************
     * Public Methods of Conglomerate Interface:
     **************************************************************************
     */

    /**
     * Add a column to the conglomerate.
     * <p>
     * Currently B2I does not support this operation.
     * input template column.  
     * 
     * @param xact_manager      Transaction to associate the lock with.
     * @param column_id        The column number to add this column at.
     * @param template_column  An instance of the column to be added to table.
     *
	 * @exception  StandardException  Standard exception policy.
     **/
	public void addColumn(
    TransactionManager  xact_manager,
    int                 column_id,
    Storable            template_column)
        throws StandardException
    {
        throw StandardException.newException(
                SQLState.BTREE_UNIMPLEMENTED_FEATURE);
    }

    /**
     * Get the id of the container of the conglomerate.
     * <p>
     * Will have to change when a conglomerate could have more than one 
     * container.  The ContainerKey is a combination of the container id
     * and segment id.
     *
	 * @return The ContainerKey.
     **/
    public final ContainerKey getId()
    {
        return(id);
    }


	/**
	Do the generic part of creating a b-tree conglomerate.  This method 
    is called from the concrete subclass (which may also read some properties).
    <p>
    This method processes all properties which are generic to all BTree's.  It
    creates the container for the btree.
    <p>