controlrow.java

derby database source code.good for you.

/*

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

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

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.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.Qualifier;
import org.apache.derby.iapi.store.access.RowUtil;

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

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

import org.apache.derby.iapi.types.SQLLongint;
import org.apache.derby.impl.store.access.StorableFormatId;


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

import org.apache.derby.impl.store.access.conglomerate.ConglomerateUtil;

/**

Base class for leaf and branch control rows.
<P>
<B>Concurrency Notes</B>
<P>
All access through control rows is serialized by an exclusive latch on 
the page the control row is for.  The page is latched when the control
row is "gotten" (ControlRow#Get), and unlatched when the control row
is released (ControlRow#release).
<P>
<B>To Do List</B>
<UL>
<LI> <I>[NOTE1]</I>
The code is arranged to fault in fields from the row as necessary.
many of the fields of a control row are rarely used (left sibling, parent).
The accessors fault in the underlying column only when
requested by allocating the appropriate object and calling fetchFromSlot and
only fetching the requested field.
<LI> <I>[NOTE2]</I> 
Currently, all the fields of the control row are stored as StorableU8s
for simplicity.  This is too few bits to hold the long page numbers, and
too many to hold the version, level, and isRoot flag.  Some consideration
will have to be given to the appropriate storage format for these values.
<LI> <I>[NOTE3]</I>
The implementation relies on the existance of page "auxiliary" pointers 
which keep Object versions of the control row.
<P>
@see ControlRow#Get
@see ControlRow#release

**/

public abstract class ControlRow implements AuxObject, TypedFormat
{
    /**
     * Version indentifier of the control row within the page.  
     * <p>
     * This is the format id of the control row.  The format id is currently
     * one of either StoredFormatIds.ACCESS_BTREE_LEAFCONTROLROW_ID or
     * StoredFormatIds.ACCESS_BTREE_BRANCHCONTROLROW_ID.
     **/
    private StorableFormatId    version = null;

    /**
     * Pointer to page which is "left" at the current level.
     * <p>
     * Currently all pages at a level are doubly linked.  The leftmost page
     * in a level has a leftSiblingPageNumber == 
     * ContainerHandle.INVALID_PAGE_NUMBER.  All key values on the page which
     * is left must precede the first key value on the current page.
     **/
	private SQLLongint leftSiblingPageNumber;

    /**
     * Pointer to page which is "right" at the current level.
     * <p>
     * Currently all pages at a level are doubly linked.  The rightmost page
     * in a level has a rightSiblingPageNumber == 
     * ContainerHandle.INVALID_PAGE_NUMBER.  All key values on the page which
     * is right of the current page must follow the last key value on the 
     * current page.
     **/
	private SQLLongint rightSiblingPageNumber;

    /**
     * The parent page of the current page.
     * <p>
     * For consistency checking it is useful to maintain the parentPageNumber
     * field of the current page.  The root page has a value of 
     * ContainerHandle.INVALID_PAGE_NUMBER in it's parentPageNumber field.
     * <p>
     * RESOLVE (mikem) - we need to come up with some way to not maintain these,
     * maybe by providing a property on secondary index or a different 2nd 
     * index.
     *
     **/
	private SQLLongint parentPageNumber; // for consistency checking


    /**
     * The level of the btree.
     * <p>
     * The leaf level of the btree is 0.  The first branch level (parent level
     * of the leaf), is level 1.  The height of the btree is (level + 1).
     * <p>
     * The smallest btree is a one page btree with only a leaf, and no branch
     * pages. 
     **/
	private SQLLongint level;

    /**
     * Is this page the root of the btree?
     * <p>
     * Currently "1" if the page is the root page, else "0".
     * <p>
     * RESOLVE (mikem) When real datatype come about, this value should 
     * probably be just a bit in some status word.
     **/
	private SQLLongint isRoot = null;

    /**
     * A copy of the Conglomerate that describes the owning conglom.
     * <p>
     * This information is used during logical undo to get the type information
     * so that rows can be compared and searched for.  We may be able to get
     * away with a subset of the information stored in the conglomerate.
     * <p>
     * RESOLVE (mikem) - change this to only store the info on the root page.
     **/
    private BTree    btree = null;

    /**
     * The page that this control row describes.
     **/
	protected Page page;

    /**
     * The page that this control row describes.
     **/
	protected DataValueDescriptor row[];

    /**
     * row used to replace fetchFieldFromSlot() calls.
     **/
    protected DataValueDescriptor[] scratch_row;

    /**
     * FetchDescriptor used to replace fetchFieldFromSlot() calls.
     **/
    protected FetchDescriptor   fetchDesc;

    /**
     * In memory hint about whether to use the last_search_result hint during
     * search.
     **/
    transient protected boolean use_last_search_result_hint = false;

    /**
     * In memory hint about where to begin the binary search to find a key
     * on the the current control page.
     **/
    transient protected int last_search_result = 0;

    /**
     * Column number assignments for columns of the control row.
     * <p>
     * The control row is stored as the first row in a btree page.  The row
     * is an array of columns.  The Control row columns are the columns numbered
     * from ControlRow.CR_COLID_FIRST through ControlRow.CR_COLID_LAST.  The
     * classes which implement the concrete derived classes of ControlRow may
     * add columns to the control row, but they must be added after the 
     * ControlRow columns.
     **/
	protected static final int CR_COLID_FIRST		= 0;
	protected static final int CR_VERSION_COLID		= CR_COLID_FIRST + 0;
	protected static final int CR_LEFTSIB_COLID		= CR_COLID_FIRST + 1;
	protected static final int CR_RIGHTSIB_COLID	= CR_COLID_FIRST + 2;
	protected static final int CR_PARENT_COLID		= CR_COLID_FIRST + 3;
	protected static final int CR_LEVEL_COLID		= CR_COLID_FIRST + 4;
	protected static final int CR_ISROOT_COLID		= CR_COLID_FIRST + 5;
	protected static final int CR_CONGLOM_COLID	    = CR_COLID_FIRST + 6;
	protected static final int CR_COLID_LAST		= CR_CONGLOM_COLID;
	protected static final int CR_NCOLUMNS			= CR_COLID_LAST + 1;

    /**
     * bit sets used to fetch single columns at a time.
     **/
    protected static final FormatableBitSet   CR_VERSION_BITSET = 
        new FormatableBitSet(CR_VERSION_COLID + 1);
    protected static final FormatableBitSet   CR_LEFTSIB_BITSET = 
        new FormatableBitSet(CR_LEFTSIB_COLID + 1);
    protected static final FormatableBitSet   CR_RIGHTSIB_BITSET =
        new FormatableBitSet(CR_RIGHTSIB_COLID + 1);
    protected static final FormatableBitSet   CR_PARENT_BITSET =
        new FormatableBitSet(CR_PARENT_COLID + 1);
    protected static final FormatableBitSet   CR_LEVEL_BITSET =
        new FormatableBitSet(CR_LEVEL_COLID + 1);
    protected static final FormatableBitSet   CR_ISROOT_BITSET =
        new FormatableBitSet(CR_ISROOT_COLID + 1);
    protected static final FormatableBitSet   CR_CONGLOM_BITSET =
        new FormatableBitSet(CR_CONGLOM_COLID + 1);


    /**
     * Values passed in the flag argument to splitFor.
     **/
    /* row causing split would be last row on leaf page */
    public static final int SPLIT_FLAG_LAST_ON_PAGE      = 0x000000001;
    /* row causing split would be last row in table */
    public static final int SPLIT_FLAG_LAST_IN_TABLE     = 0x000000002;
    /* row causing split would be first row on page */
    public static final int SPLIT_FLAG_FIRST_ON_PAGE     = 0x000000004;
    /* row causing split would be first row in table */
    public static final int SPLIT_FLAG_FIRST_IN_TABLE    = 0x000000008;

    /**
     * The slot at which all control rows reside.
     **/
	protected static final int CR_SLOT = 0;

	/*
	** Constructors of ControlRow
	*/

    static 
    {
        CR_VERSION_BITSET.set(CR_VERSION_COLID);
        CR_LEFTSIB_BITSET.set(CR_LEFTSIB_COLID);
        CR_RIGHTSIB_BITSET.set(CR_RIGHTSIB_COLID);
        CR_PARENT_BITSET.set(CR_PARENT_COLID);
        CR_LEVEL_BITSET.set(CR_LEVEL_COLID);
        CR_ISROOT_BITSET.set(CR_ISROOT_COLID);
        CR_CONGLOM_BITSET.set(CR_CONGLOM_COLID);
    }

    /**
     * No arg constructor.
     * <p>
     * GetControlRowForPage() will call this constructor when it uses the 
     * monitor to create a control row dynamically given a given format id.
     **/
    protected ControlRow()
    {
        this.scratch_row = 
            new DataValueDescriptor[getNumberOfControlRowColumns()];

        this.fetchDesc   = 
            new FetchDescriptor(
                this.scratch_row.length, (FormatableBitSet) null, (Qualifier[][]) null);
    }

    /**
     * Constructor for making a new control row as part of allocating a new
	 * page.  Fills in all the fields but does not write them anywhere.
     * <p>
	 * <P>
	 * Changes to this constructor will probably require changes to the
	 * corresponding accessor(s).
     *
     * @param btree      Static information about the btree.
     * @param page       The page described by this control row.
     * @param parent     The parent page of this page, "null" if this page is 
     *                   root or if not maintaining parent links.
     * @param isRoot     Is this page the root of the tree?
     *
     *
     * @exception StandardException Standard exception policy.
     **/
	protected ControlRow(
    OpenBTree         btree,
    Page		      page, 
    int			      level, 
    ControlRow	      parent,
    boolean           isRoot
    )
        throws StandardException
	{
		// The caller is expected to have latched the pages.
        if (SanityManager.DEBUG)
        {
            SanityManager.ASSERT(page.isLatched());
            SanityManager.ASSERT(parent == null || parent.page.isLatched());
        }

		// Maintain which page this control row describes.
		this.page = page;

		// Page numbers start out "invalid".  Presumably the caller will
		// link the page into a page chain as one of its next steps.
		leftSiblingPageNumber  = 
            new SQLLongint(btree.container.INVALID_PAGE_NUMBER);
		rightSiblingPageNumber = 
            new SQLLongint(btree.container.INVALID_PAGE_NUMBER);

		// Remember the parent if there is one and we're remembering parents.
        parentPageNumber = new SQLLongint( 
            (parent == null ?  
                 btree.container.INVALID_PAGE_NUMBER : 
                 parent.page.getPageNumber()));

		// All pages start out not being root pages.  The caller will setIsRoot
		// if this is going to be a root page. Zero means false - see 
		// getIsRoot/setIsRoot.
		this.isRoot = new SQLLongint(isRoot ? 1 : 0);

        // set the rest of the state, as passed in.
		this.level   = new SQLLongint(level);
        this.version = new StorableFormatId(getTypeFormatId());

        // If it is a root page then store the real btree conglomerate, if it
        // is not a root page then set up an "empty" btree conglomerate which
        // will be stored as "null".
        this.btree = 
            (isRoot ? 
             btree.getConglomerate() : 
             (BTree) Monitor.newInstanceFromIdentifier(
                btree.getConglomerate().getTypeFormatId()));

        // Initialize the object array to be used for interacting with raw
        // store to insert, fetch, and update the control row.
        this.row = new DataValueDescriptor[getNumberOfControlRowColumns()];
	    this.row[CR_VERSION_COLID]	= this.version;
	    this.row[CR_LEFTSIB_COLID]	= this.leftSiblingPageNumber;
	    this.row[CR_RIGHTSIB_COLID]	= this.rightSiblingPageNumber;
	    this.row[CR_PARENT_COLID]	= this.parentPageNumber;
	    this.row[CR_LEVEL_COLID]	= this.level;
	    this.row[CR_ISROOT_COLID]	= this.isRoot;
	    this.row[CR_CONGLOM_COLID]  = this.btree;


		// Make the control row the aux object for the page so control row
		// getters end up with the same row.
		page.setAuxObject(this);
	}

    /**
     * Constructor for making a control row for an existing page.
     * <p>
     * Not all the fields are filled in; their values will get faulted in from 
     * the page as necessary.
     * <p>
	 * Classes which extend ControlRow must delegate to this constructor
	 * and may want to override it as well.
	 * Changes to this constructor will probably require changes to the
	 * corresponding accessor(s).
     *
     * @param container  Open container 
     * @param page       The page described by this control row.
     *
     * @exception StandardException Standard exception policy.
     **/
	protected ControlRow(ContainerHandle container, Page page)
        throws StandardException
	{