btreecontroller.java

derby database source code.good for you.

/*

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

   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 java.io.IOException;
import java.util.Properties;

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.TransactionManager;
import org.apache.derby.iapi.store.access.AccessFactoryGlobals;
import org.apache.derby.iapi.store.access.ConglomerateController;
import org.apache.derby.iapi.store.access.DynamicCompiledOpenConglomInfo;
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.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.iapi.services.io.FormatableBitSet;
import org.apache.derby.impl.store.access.conglomerate.ConglomerateUtil;
import org.apache.derby.impl.store.access.conglomerate.TemplateRow;



/**

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

**/

public class BTreeController extends OpenBTree implements ConglomerateController
{

    transient DataValueDescriptor[] scratch_template = null;

    /**
     * Whether to get lock on the row being inserted, usually this lock
     * has already been gotten when the row was inserted into the base table.
     **/
    boolean get_insert_row_lock;

    /* Constructors: */

	public BTreeController()
	{
	}

	/*
	** private Methods of BTreeController
	*/

    /**
     * Attempt to reclaim committed deleted rows from the page.
     * <p>
     * Get exclusive latch on page, and then loop backward through
     * page searching for deleted rows which are committed.  The routine
     * assumes that it is called from a transaction which cannot have 
     * deleted any rows on the page.  For each deleted row on the page
     * it attempts to get an exclusive lock on the deleted row, NOWAIT.
     * If it succeeds, and since this row did not delete the row then the
     * row must have been deleted by a transaction which has committed, so
     * it is safe to purge the row.  It then purges the row from the page.
     * <p>
     * Note that this routine may remove all rows from the page, it will not
     * attempt a merge in this situation.  This is because this routine is
     * called from split which is attempting an insert on the given page, so
     * it would be a waste to merge the page only to split it again to allow
     * the insert of the row causing the split.
     *
	 * @return true if at least one row was purged.
     *
     * @param open_btree The already open btree to use to get latch on page.
     * @param pageno     The page number of the leaf to attempt the reclaim on.
     *
	 * @exception  StandardException  Standard exception policy.
     **/
    private boolean reclaim_deleted_rows(
    OpenBTree   open_btree,
    long        pageno)
		throws StandardException
    {
        boolean     purged_at_least_one_row = false;
        ControlRow  controlRow              = null; 

        try
        {

            if ((controlRow = ControlRow.Get(open_btree, pageno)) == null)
                return(false);

            LeafControlRow leaf       = (LeafControlRow) controlRow;

            BTreeLockingPolicy  btree_locking_policy = 
                open_btree.getLockingPolicy();


            // The number records that can be reclaimed is:
            // total recs - control row - recs_not_deleted
            int num_possible_commit_delete = 
                leaf.page.recordCount() - 1 - leaf.page.nonDeletedRecordCount();

            if ((num_possible_commit_delete > 0) &&
                (btree_locking_policy.lockScanForReclaimSpace(leaf)))
            {
                // Need to get an exclusive scan lock on the page before we can
                // do any sort of purges, otherwise other concurrent scans would
                // not work.  If we can't get the lock NOWAIT, just give up on
                // purging rows and do the split without reclaiming rows.

                Page page   = leaf.page;


                // RowLocation column is in last column of template.
                FetchDescriptor lock_fetch_desc = 
                    RowUtil.getFetchDescriptorConstant(
                        scratch_template.length - 1);

                // loop backward so that purges which affect the slot table 
                // don't affect the loop (ie. they only move records we 
                // have already looked at).
                for (int slot_no = page.recordCount() - 1; 
                     slot_no > 0; 
                     slot_no--) 
                {
                    if (page.isDeletedAtSlot(slot_no))
                    {
                        // try to get an exclusive lock on the row, if we can 
                        // then the row is a committed deleted row and it is 
                        // safe to purge it.
                        if (btree_locking_policy.lockScanCommittedDeletedRow(
                                open_btree, leaf, scratch_template, 
                                lock_fetch_desc, slot_no))
                        {
                            // the row is a committed deleted row, purge it.
                            page.purgeAtSlot(slot_no, 1, true);

                            purged_at_least_one_row = true;
                        }
                    }
                }

            }
        }
        catch (java.lang.ClassCastException cce)
        {
            // because we give up the latch on the leaf before entering this
            // routine, the page might change from a leaf to branch.  If that
            // happens this routine will get a ClassCastException, and we
            // just give up trying to reclaim space.
        }
        finally
        {
            if (controlRow != null)
                controlRow.release();

            return(purged_at_least_one_row);
        }
    }

    /**
     * Start an internal transaction and do the split.
     * <p>
     * This routine starts a new transaction, and handles any errors that
     * may come during the transaction.  This transation must not obtain any
     * locks as they are likely to conflict with the current user transaction.
     * <p>
     * If attempt_to_reclaim_deleted_rows is true this routine will 
     * attempt to reclaim space on the leaf page input, by purging 
     * committed deleted rows from the leaf.  If it succeeds in purging at
     * least one row, then it will commit the internal transaction and return
     * without actually performing a split.  
     *
     * @param scratch_template  A scratch template used to search a page.
     * @param rowToInsert       The row to insert, make sure during split to
     *                          make room for this row.
     *
	 * @exception  StandardException  Standard exception policy.
     **/
    private long 
    start_xact_and_dosplit(
    boolean                 attempt_to_reclaim_deleted_rows,
    long                    leaf_pageno,
    DataValueDescriptor[]   scratch_template, 
    DataValueDescriptor[]   rowToInsert,
    int                     flag)
        throws StandardException
    {
        TransactionManager split_xact       = null;
        OpenBTree          split_open_btree = null;
        ControlRow         root             = null;

        // Get an internal transaction to be used for the split.
        split_xact = this.init_open_user_scans.getInternalTransaction();

        // open the btree again so that actions on it take place in the
        // split_xact, don't get any locks in this transaction.

		if (SanityManager.DEBUG)
		{
            if (((getOpenMode() & ContainerHandle.MODE_FORUPDATE) !=
								   ContainerHandle.MODE_FORUPDATE))
            {
                SanityManager.THROWASSERT(
                    "Container not opened with update should not cause split");
            }
		}


        boolean do_split = true;
        if (attempt_to_reclaim_deleted_rows)
        {
            // Get lock on base table.

            ConglomerateController base_cc = null;

            try
            {
                base_cc = 
                    this.getConglomerate().lockTable(
                        split_xact, 
                        (ContainerHandle.MODE_FORUPDATE |
                         ContainerHandle.MODE_LOCK_NOWAIT), 
                        TransactionController.MODE_RECORD,
                        TransactionController.ISOLATION_REPEATABLE_READ);
            }
            catch (StandardException se)
            {
                // any error just don't try to reclaim deleted rows.  The
                // expected error is that we can't get the lock, which the
                // current interface throws as a containerNotFound exception.
            }

            if (base_cc != null)
            {
                // we got IX lock on the base table, so can try reclaim space.


                // We can only reclaim space by opening the btree in row lock 
                // mode.  Table level lock row recovery is hard as we can't 
                // determine if the deleted rows we encounter have been 
                // deleted by our parent caller and have been committed or 
                // not.  We will have to get those rows offline.
                split_open_btree = new OpenBTree();
                split_open_btree.init(
                    this.init_open_user_scans, 
                    split_xact, 
                    null,                           // open the container.
                    split_xact.getRawStoreXact(), 
                    false,
                    (ContainerHandle.MODE_FORUPDATE | 
                     ContainerHandle.MODE_LOCK_NOWAIT),
                    TransactionManager.MODE_RECORD,
                    this.getConglomerate().getBtreeLockingPolicy(
                        split_xact.getRawStoreXact(), 
                        TransactionController.MODE_RECORD,
                        LockingPolicy.MODE_RECORD,
                        TransactionController.ISOLATION_REPEATABLE_READ, 
                        (ConglomerateController) base_cc, 
                        split_open_btree),
                    this.getConglomerate(), 
                    (LogicalUndo) null,
                    (DynamicCompiledOpenConglomInfo) null);

                // don't split if we reclaim any rows.
                do_split = !reclaim_deleted_rows(split_open_btree, leaf_pageno);

                split_open_btree.close();
            }
        }

        long new_leaf_pageno = leaf_pageno; 
        if (do_split)
        {
            split_open_btree = new OpenBTree();
            split_open_btree.init(
                this.init_open_user_scans, 
                split_xact, 
                null,                           // open the container.
                split_xact.getRawStoreXact(), 
                false,
                getOpenMode(),                  // use same mode this controller
                                                // was opened with
                TransactionManager.MODE_NONE,
                this.getConglomerate().getBtreeLockingPolicy(
                    split_xact.getRawStoreXact(), 
                    this.init_lock_level,
                    LockingPolicy.MODE_RECORD,
                    TransactionController.ISOLATION_REPEATABLE_READ, 
                    (ConglomerateController) null, // no base row locks during split
                    split_open_btree),
                this.getConglomerate(), 
                (LogicalUndo) null,
                (DynamicCompiledOpenConglomInfo) null);


            // Get the root page back, and perform a split following the
            // to-be-inserted key.  The split releases the root page latch.
            root = ControlRow.Get(split_open_btree, BTree.ROOTPAGEID);

            if (SanityManager.DEBUG)
                SanityManager.ASSERT(root.page.isLatched());

            new_leaf_pageno = 
                root.splitFor(
                    split_open_btree, scratch_template, 
                    null, rowToInsert, flag);