btreescan.java

derby database source code.good for you.

/*

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

   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.sanity.SanityManager;
import org.apache.derby.iapi.services.io.Storable;

import org.apache.derby.iapi.error.StandardException;

import org.apache.derby.iapi.store.access.conglomerate.Conglomerate;
import org.apache.derby.iapi.store.access.conglomerate.LogicalUndo;
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.GenericScanController;
import org.apache.derby.iapi.store.access.Qualifier;
import org.apache.derby.iapi.store.access.RowUtil;
import org.apache.derby.iapi.store.access.ScanController;
import org.apache.derby.iapi.store.access.ScanInfo;
import org.apache.derby.iapi.store.access.StaticCompiledOpenConglomInfo;
import org.apache.derby.iapi.store.access.TransactionController;

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

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.TemplateRow;

import org.apache.derby.iapi.services.io.FormatableBitSet;
import org.apache.derby.iapi.store.access.BackingStoreHashtable;

/**

  A b-tree scan controller corresponds to an instance of an open b-tree scan.
  <P>
  <B>Concurrency Notes<\B>
  <P>
  The concurrency rules are derived from OpenBTree.
  <P>
  @see OpenBTree

**/

public abstract class BTreeScan extends OpenBTree implements ScanManager
{

	/*
	** Fields of BTreeScan
	*/

    /**
     * init_startKeyValue, init_qualifier, and init_stopKeyValue all are used 
     * to store * references to the values passed in when ScanController.init()
     * is called.  It is assumed that these are not altered by the client
     * while the scan is active.
     */
    protected Transaction           init_rawtran             = null;
    protected boolean               init_forUpdate;
    protected FormatableBitSet               init_scanColumnList;
    protected DataValueDescriptor[] init_template;
    protected DataValueDescriptor[] init_startKeyValue;
    protected int                   init_startSearchOperator = 0;
    protected Qualifier             init_qualifier[][]       = null;
    protected DataValueDescriptor[] init_stopKeyValue;
    protected int                   init_stopSearchOperator  = 0;
    protected boolean               init_hold;


    /**
     * The fetch descriptor which describes the row to be returned by the scan.
     **/
    protected FetchDescriptor       init_fetchDesc;


    /**
     * A constant FetchDescriptor which describes the position of the 
     * RowLocation field within the btree, currently always the last column).  
     * Used by lock/unlock to fetch the RowLocation.  
     * Only needs to be allocated once per scan.
     **/
    protected FetchDescriptor       init_lock_fetch_desc;


    BTreeRowPosition                scan_position;


     /**
      * Whether the scan should requests UPDATE locks which then will be 
      * converted to X locks when the actual operation is performed.
     **/
     protected boolean init_useUpdateLocks = false;

    /*
     * There are 5 states a scan can be in.
     *     SCAN_INIT - A scan has started but no positioning has been done.
     *                 The scan will be positioned when the first next() call
     *                 has been made.  None of the positioning state variables
     *                 are valid in this state.
     *     SCAN_INPROGRESS -
     *                 A scan is in this state after the first next() call.
     *                 On exit from any BTreeScan method, while in this state,
     *                 the scan "points" at a row which qualifies for the 
     *                 scan.  While not maintaining latches on a page the 
     *                 current position of the scan is either kept by record
     *                 handle or key.  To tell which use the following:
     *                 if (record key == null)
     *                    record handle has current position
     *                 else
     *                    record key has current position
     *
     *     SCAN_DONE - Once the end of the table or the stop condition is met
     *                 then the scan is placed in this state.  Only valid 
     *                 ScanController method at this point is close().
     *
     *     SCAN_HOLD_INIT -
     *                 The scan has been opened and held open across a commit,
     *                 at the last commit the state was SCAN_INIT.
     *                 The scan has never progressed from the SCAN_INIT state
     *                 during a transaction.  When a next is done the state
     *                 will either progress to SCAN_INPROGRESS or SCAN_DONE.
     *
     *     SCAN_HOLD_INPROGRESS -
     *                 The scan has been opened and held open across a commit,
     *                 at the last commit the state was in SCAN_INPROGRESS.
     *                 The transaction which opened the scan has committed,
     *                 but the scan was opened with the "hold" option true.
     *                 At commit the locks were released and the "current"
     *                 position is remembered.  In this state only two calls
     *                 are valid, either next() or close().  When next() is
     *                 called the scan is reopened, the underlying container
     *                 is opened thus associating all new locks with the current
     *                 transaction, and the scan continues at the "next" row.
     */
    protected static final int    SCAN_INIT             = 1;
    protected static final int    SCAN_INPROGRESS       = 2;
    protected static final int    SCAN_DONE             = 3;
    protected static final int    SCAN_HOLD_INIT        = 4;
    protected static final int    SCAN_HOLD_INPROGRESS  = 5;

    /**
     * Delay positioning the  table at the start position until the first
     * next() call.  The initial position is done in positionAtStartPosition().
     */
    protected int         scan_state      = SCAN_INIT;

    /**
     * Performance counters ...
     */
    protected int stat_numpages_visited         = 0;
    protected int stat_numrows_visited          = 0;
    protected int stat_numrows_qualified        = 0;
    protected int stat_numdeleted_rows_visited  = 0;

    /**
	 * What kind of row locks to get during the scan.
     **/
    protected int lock_operation;


    /**
     * A 1 element array to turn fetchNext and fetch calls into 
     * fetchNextGroup calls.
     **/
    protected DataValueDescriptor[][] fetchNext_one_slot_array = 
                                            new DataValueDescriptor[1][];

    /* Constructors for This class: */

	public BTreeScan()
	{
	}

	/*
	** Private/Protected methods of This class, sorted alphabetically
	*/

    /**
     * Fetch the next N rows from the table.
     * <p>
     * Utility routine used by both fetchSet() and fetchNextGroup().
     *
	 * @exception  StandardException  Standard exception policy.
     **/
    abstract protected int fetchRows(
    BTreeRowPosition        pos,
    DataValueDescriptor[][] row_array,
    RowLocation[]           rowloc_array,
    BackingStoreHashtable   hash_table,
    long                    max_rowcnt,
    int[]                   key_column_numbers)
        throws StandardException;


    /**
     * Shared initialization code between init() and reopenScan().
     * <p>
     * Basically save away input parameters describing qualifications for
     * the scan, and do some error checking.
     *
	 * @exception  StandardException  Standard exception policy.
     **/
	private void initScanParams(
    DataValueDescriptor[]   startKeyValue,
    int                     startSearchOperator,
    Qualifier               qualifier[][],
    DataValueDescriptor[]   stopKeyValue,
    int                     stopSearchOperator)
        throws StandardException
	{
        // startKeyValue init.
	    this.init_startKeyValue         = startKeyValue;
		if (RowUtil.isRowEmpty(this.init_startKeyValue, (FormatableBitSet) null))
			this.init_startKeyValue = null;

        // startSearchOperator init.
	    this.init_startSearchOperator   = startSearchOperator;

        // qualifier init.
        if ((qualifier != null) && (qualifier .length == 0))
            qualifier = null;
        this.init_qualifier             = qualifier;

        // stopKeyValue init.
	    this.init_stopKeyValue          = stopKeyValue;
        if (RowUtil.isRowEmpty(this.init_stopKeyValue, (FormatableBitSet) null))
            this.init_stopKeyValue = null;

        // stopSearchOperator init.
	    this.init_stopSearchOperator    = stopSearchOperator;

        // reset the "current" position to starting condition.
        // RESOLVE (mmm) - "compile" this.
        scan_position = new BTreeRowPosition();

        scan_position.init();

        scan_position.current_lock_template = 
            new DataValueDescriptor[this.init_template.length];

        scan_position.current_lock_template[this.init_template.length - 1] = 
            scan_position.current_lock_row_loc = 
                (RowLocation) ((RowLocation) 
                     init_template[init_template.length - 1]).cloneObject(); 

        // Verify that all columns in start key value, stop key value, and
        // qualifiers are present in the list of columns described by the
        // scanColumnList.
        if (SanityManager.DEBUG)
        {
            if (init_scanColumnList != null)
            {
                // verify that all columns specified in qualifiers, start
                // and stop positions are specified in the scanColumnList.  
                
                FormatableBitSet required_cols;

                if (qualifier != null)
                    required_cols = RowUtil.getQualifierBitSet(qualifier);
                else
                    required_cols = new FormatableBitSet(0);

                // add in start columns
                if (this.init_startKeyValue != null)
                {
					required_cols.grow(this.init_startKeyValue.length);
                    for (int i = 0; i < this.init_startKeyValue.length; i++)
                        required_cols.set(i);
                }

                if (this.init_stopKeyValue != null)
                {
					required_cols.grow(this.init_stopKeyValue.length);
                    for (int i = 0; i < this.init_stopKeyValue.length; i++)
                        required_cols.set(i);
                }

                FormatableBitSet required_cols_and_scan_list = 
                    (FormatableBitSet) required_cols.clone();

                required_cols_and_scan_list.and(init_scanColumnList);

				// FormatableBitSet equals requires the two FormatableBitSets to be of same
				// length.
				required_cols.grow(init_scanColumnList.size());

                if (!required_cols_and_scan_list.equals(required_cols))
                {
                    SanityManager.THROWASSERT(
                        "Some column specified in a Btree " +
                        " qualifier/start/stop list is " +
                        "not represented in the scanColumnList." +
                        "\n:required_cols_and_scan_list = " + 
                            required_cols_and_scan_list + 
                        "\n;required_cols = " + required_cols +
                        "\n;init_scanColumnList = " + init_scanColumnList);
                }
            }
		} 
	}

    /**
     * Position scan at "start" position for a forward scan.
     * <p> 
     * Positions the scan to the slot just before the first record to be 
     * returned from the scan.  Returns the start page latched, and 
     * sets "current_slot" to the slot number.
     * <p>
     *
	 * @return The leaf on which scan is positioned.
     *
	 * @exception  StandardException  Standard exception policy.
     **/
    protected void positionAtStartForForwardScan(
    BTreeRowPosition    pos)