leafcontrolrow.java

derby database source code.good for you.

/*

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

   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.FormatIdUtil;
import org.apache.derby.iapi.services.io.StoredFormatIds;
import org.apache.derby.iapi.services.io.TypedFormat;
import org.apache.derby.iapi.error.StandardException;

import org.apache.derby.iapi.store.access.conglomerate.LogicalUndo;

import org.apache.derby.iapi.store.access.AccessFactoryGlobals;
import org.apache.derby.iapi.store.access.ConglomerateController;
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.raw.ContainerHandle;
import org.apache.derby.iapi.store.raw.FetchDescriptor;
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 java.io.PrintStream;
import org.apache.derby.iapi.services.io.FormatableBitSet;

/**
 * @format_id ACCESS_BTREE_LEAFCONTROLROW_V1_ID
 *
 * @purpose   Btree pages all have a control row at the front of every page.  To
 *            determine the type of row, read the first column which is a format
 *            id and it tells what kind of control row it is.
 *
 * @upgrade   This format was made obsolete in the kimono release.
 *
 * @disk_layout 
 * column 1 - control row type         : StorableFormatId
 * column 2 - left sibling page number : SQLLongint
 * column 3 - right sibling page number: SQLLongint
 * column 4 - parent page number       : SQLLongint
 * column 5 - level number (0 is leaf) : SQLLongint
 * column 6 - isRoot                   : SQLLongint
 * column 7 - Conglomerate object      : null unless it is root else
 *                                       a Conglomerate object, matching
 *                                       that of current table.
 *                                       Currently this field
 *                                       is only used by logical undo and
 *                                       the type of object is inferred by
 *                                       the logical undo code.
 **/

public class LeafControlRow extends ControlRow
{
	/*
	** Constructors of BranchControlRow
	*/

    /**
     * No arg constructor.
     * <p>
     * Public no arg constructor is for the monitor to call for format
     * id implemenation, it should not be called for any other reason.
     **/
    public LeafControlRow()
    {
    }

    /**
     * Constructs a leaf-page control row, for a newly allocated leaf page.  
     *
     * @param btree     The open btree to allocate this page from.
     * @param page      The newly allocated page where the control row will
     *                  be inserted.
     * @param parent    The parent of the leaf page.  Set to null for root.
     *                  RESOLVE (mikem) - set to null otherwise?
     * @param isRoot    Is this page the root of the tree?
     *
     * @exception StandardException Standard exception policy.
     */
    LeafControlRow(
    OpenBTree         btree,
    Page		      page, 
    ControlRow	      parent,
    boolean           isRoot)
            throws StandardException
    {
        // All leaf pages are at level 0.
        super(btree, page, 0, parent, isRoot);
    }

    /* Private/Protected methods of This class: */

    /**
     * Allocate a new leaf page to the conglomerate.
     *
     * @param btree     The open conglomerate from which to get the leaf from
     * @param parent    The parent page of the newly allocated page, null if
     *                  allocating root page.
     * 
     * @exception StandardException Standard exception policy.
     */
    private static LeafControlRow Allocate(
    OpenBTree   btree, 
    ControlRow  parent)
        throws StandardException
    {
        Page      page      = btree.container.addPage();

        // Create a control row for the new page.
        LeafControlRow control_row = 
            new LeafControlRow(btree, page, parent, false);

        // Insert the control row on the page, in the first slot on the page.
        // This operation is only done as part of a new tree or split, which
        // which both will be undone physically so no logical undo record is
        // needed.
		byte insertFlag = Page.INSERT_INITIAL;
		insertFlag |= Page.INSERT_DEFAULT;
        RecordHandle rh = 
            page.insertAtSlot(Page.FIRST_SLOT_NUMBER,
                control_row.getRow(),
                (FormatableBitSet) null, 
                (LogicalUndo) null, insertFlag,
				AccessFactoryGlobals.BTREE_OVERFLOW_THRESHOLD);

        if (SanityManager.DEBUG)
        {
            RecordHandle    rh2 = null;

            rh2 = page.fetchFromSlot(
                    (RecordHandle) null, page.FIRST_SLOT_NUMBER, 
                    new DataValueDescriptor[0], (FetchDescriptor) null, true); 

            SanityManager.ASSERT(rh.getId() == rh2.getId() &&
                                 rh.getPageNumber() == rh2.getPageNumber());
        }

        // Page is returned latched.
        return(control_row);
    }

    /**
     * Return the number of non-deleted rows from slot 1 through "startslot"
     * <p>
     * Return the number of non-deleted rows that exist on the page starting
     * at slot one through "startslot".
     * <p>
     * RESOLVE (mikem) - is the expense of this routine worth it, it is only
     * used for costing.  Could an estimate from the nonDeletedRecordCount()
     * be used instead?
     *
	 * @return The requested non_deleted_row_count.
     *
     * @param startslot  Count non deleted row up to and including this slot.
     *
	 * @exception  StandardException  Standard exception policy.
     **/
    private float get_left_nondeleted_rowcnt(
    int startslot)
        throws StandardException
    {
        int non_deleted_row_count = 0;

        for (int slot = 1; slot <= startslot; slot++)
        {
            if (!this.page.isDeletedAtSlot(slot))
            {
                non_deleted_row_count++;
            }
        }
        return(non_deleted_row_count);
    }


    /* Public Methods of LeafControlRow class: */

    /**
     * Perform page specific initialization.
     * <p>
     *
	 * @return The identifier to be used to open the conglomerate later.
     *
     **/
    protected final void ControlRowInit()
    {
    }

    /**
     * Initialize conglomerate with one page, to be a 1 page btree.
     *
     * Given a conglomerate which already has one page allocated to it, 
     * initialize the page to be a leaf-root page with no entries.  Allocate
     * the control row and store it on the page.
     *
     * @param open_btree The open btree to initialize (container is open).
     *
     * @exception StandardException Standard exception policy.
     */
    public static void initEmptyBtree(
    OpenBTree   open_btree)
        throws StandardException
    {
        Page page = 
            open_btree.container.getPage(ContainerHandle.FIRST_PAGE_NUMBER);

        // create a leaf control row for root page of a single page index //
        LeafControlRow control_row =
            new LeafControlRow(open_btree, page, null, true);

		byte insertFlag = Page.INSERT_INITIAL;
		insertFlag |= Page.INSERT_DEFAULT;
        RecordHandle rh = 
            page.insertAtSlot(
                Page.FIRST_SLOT_NUMBER,
                control_row.getRow(),
                (FormatableBitSet) null,
                (LogicalUndo) null, insertFlag,
				AccessFactoryGlobals.BTREE_OVERFLOW_THRESHOLD);

        if (SanityManager.DEBUG)
        {
            RecordHandle    rh2 = null;

            rh2 = page.fetchFromSlot(
                    (RecordHandle) null, 
                    Page.FIRST_SLOT_NUMBER, 
                    new DataValueDescriptor[0], (FetchDescriptor) null, true); 

            SanityManager.ASSERT(rh.getId() == rh2.getId() &&
                                 rh.getPageNumber() == rh2.getPageNumber());
        }

        if (SanityManager.DEBUG)
        {
            if (SanityManager.DEBUG_ON("enableBtreeConsistencyCheck"))
            {
                control_row.checkConsistency(
                    open_btree, (ControlRow) null, true);
            }
        }

        page.unlatch();

        return;
    }

	/*
	** Non - Debug/consistency check Methods of ControlRow:
	*/


    /**
     * Get the number of columns in the control row.  
     * <p>
     * Control rows all share the first columns as defined by this class and
     * then add columns to the end of the control row.  For instance a branch
     * control row add a child page pointer field.
     * <p>
     *
	 * @return The total number of columns in the control row.
     **/
    protected final int getNumberOfControlRowColumns()
    {
        return(this.CR_NCOLUMNS);
    }

    /**
     * Is the current page the leftmost leaf of tree?
     * <p>
     *
	 * @return true if the current page is the leftmost leaf of the tree,
     *              else return false.
     *
	 * @exception  StandardException  Standard exception policy.
     **/
    public boolean isLeftmostLeaf()
		throws StandardException
    {
        return(getleftSiblingPageNumber() == 
               ContainerHandle.INVALID_PAGE_NUMBER); 
    }

    /**
     * Is the current page the rightmost leaf of tree?
     * <p>
     *
	 * @return true if the current page is the rightmost leaf of the tree,
     *              else return false.
     *
	 * @exception  StandardException  Standard exception policy.
     **/
    public boolean isRightmostLeaf()
		throws StandardException
    {
        return(getrightSiblingPageNumber() == 
               ContainerHandle.INVALID_PAGE_NUMBER); 
    }


	/**
	 ** Perform a search of this leaf page, ultimately returning the latched
	 ** leaf page and row slot after which the given key belongs.
	 ** The slot is returned in the result structure.  If the key
	 ** exists on the page, the result.exact will be true.  Otherwise,
	 ** result.exact will be false, and the row slot returned will be
	 ** the one immediately preceding the position at which the key
	 ** belongs.
     *
     * @exception StandardException Standard exception policy.
	 **/
	public ControlRow search(
        SearchParameters    sp)
            throws StandardException
    {
        searchForEntry(sp);

        if (sp.searchForOptimizer)
        {
            // Update left_fraction to be used to estimate the number of
            // rows left of the current search location.

            // after the code below startslot will be the slot that is one
            // before the first slot to be returned by the scan positioning
            // for this key, including GT/GE positioning.  This is exactly
            // what the LeafControlRow.positionAtStartForForwardScan() does,
            // to position for the start of a scan.

            int startslot = sp.resultSlot;

            if (sp.resultExact)
            {
                // we found exactly the row we are looking for.

                if (SanityManager.DEBUG)
                    SanityManager.ASSERT(sp.resultSlot > 0);

                // RESOLVE (mikem) - add in a search operator argument so that 
                //     below can be if (op == ScanController.GE)

                if (sp.partial_key_match_op == 
                        SearchParameters.POSITION_LEFT_OF_PARTIAL_KEY_MATCH)
                {
                    // This means the scan was positioned for GE rather than GT
                    startslot--;
                }
            }

            // non_deleted_left_row is the number of actual rows left of the 
            // first row to be returned by a scan positioned as requested.  
            // The 0th slot is a control row which is not counted.
            float non_deleted_left_rows = get_left_nondeleted_rowcnt(startslot);

            int   non_deleted_row_count = this.page.nonDeletedRecordCount();