leafcontrolrow.java

derby database source code.good for you.

            // System.out.println(
            //   "\n\t non_deleted_row_count = " + non_deleted_row_count +
            // "\n\t non_deleted_left_rows = " + non_deleted_left_rows +
            // "\n\t startslot = " + startslot);

            if (this.getIsRoot())
            {
                sp.current_fraction = 1;
                sp.left_fraction    = 0;
            }

            // calculate the fraction of rows in the table which are left of
            // the current slot in the search.  After the search is completed
            // (sp.left_fraction * number of rows), is the estimated number
            // of rows to the left of the current row.

            if (non_deleted_row_count > 1)
                sp.left_fraction    += 
                    (sp.current_fraction) * 
                    (non_deleted_left_rows / (non_deleted_row_count - 1));

            // no-one really uses current fraction after leaf is through with
            // it.  Set it to help diagnose algorithm.
            if (non_deleted_row_count > 1)
                sp.current_fraction = 
                    (sp.current_fraction) * 
                    (((float) 1) / (non_deleted_row_count - 1));
        }

        return(this);
    }
	
    /**
     * Search and return the left most leaf page.
     * <p>
	 * Perform a recursive search, ultimately returning the
     * leftmost leaf page which is the first leaf page in the
	 * leaf sibling chain.  (This method might better be called
	 * getFirstLeafPage()).
     *
	 * @return The leftmost leaf page.
     *
     * @param btree  The open btree to associate latches/locks with.
     *
	 * @exception  StandardException  Standard exception policy.
     **/
	protected ControlRow searchLeft(OpenBTree btree)
        throws StandardException
    {
        return(this);
    }

    /**
     * Search and return the right most leaf page.
     * <p>
	 * Perform a recursive search, ultimately returning the
	 * rightmost leaf page which is the last leaf page in the
	 * leaf sibling chain.  (This method might better be called
	 * getLastLeafPage()).
     *
	 * @return The rightmost leaf page.
     *
     * @param btree  The open btree to associate latches/locks with.
     *
	 * @exception  StandardException  Standard exception policy.
     **/
	protected ControlRow searchRight(OpenBTree btree)
        throws StandardException
    {
        return(this);
    }


	/**
	 **	Perform a recursive shrink operation for the key.
	 ** If this method returns true, the caller should
	 ** remove the corresponding entry for the page.
	 ** This routine is not guaranteed to successfully
	 ** shrink anything.  The page lead to by the key might
	 ** turn out not to be empty by the time shrink gets
	 ** there, and shrinks will give up if there is a deadlock.
	 ** <P>
	 ** The receiver page must be latched on entry and is
	 ** returned unlatched.
     *
     * @exception StandardException Standard exception policy.
	 **/
	protected boolean shrinkFor(
    OpenBTree               btree, 
    DataValueDescriptor[]   key)
        throws StandardException
    {
        boolean shrink_me = false;

        try
        {
            // If this page is empty (ie. only has a control row), and it's not 
            // the root page, unlink it.  An empty btree consists of
            // simply an empty leaf-root page.

            // RESOLVE (mikem) - may want this routine to try to purge 
            // committed delete rows here?
            
            if ((this.page.recordCount() == 1) && !getIsRoot())
            {
                 // See if we can unlink this page (might not be able to because
                 // unlinking can cause deadlocks).  A successful unlink 
                 // unlatches the page.
                 shrink_me = unlink(btree);
            }
        }
        finally
        {
            if (!shrink_me)
                this.release();
        }

		return(shrink_me);
    }


    /**
     * Perform a top down split pass making room for the the key in "row".
     * <p>
     * Perform a split such that a subsequent call to insert
	 * given the argument index row will likely find room for it.  Since 
     * latches are released the client must code for the case where another
     * user has grabbed the space made available by the split pass and be
     * ready to do another split.
     * <p>
     * On entry, the parent is either null or latched, and the
     * current page is latched.  On exit, all pages will have been
     * unlatched.  If the parent is null, then this page is a root
     * leaf page.
     *
	 * @return page number of the newly allocated leaf page created by split.
     *
     * @param open_btree  The open btree to associate latches with.
     * @param template    A scratch area to use while searching for split pass.
     * @param parent_page The parent page of the current page in the split pass.
     *                    starts at null for root.
     * @param splitrow    The key to make room for during the split pass.
     * @param flag        A flag used to direct where point of split should be
     *                    chosen.
     *
	 * @exception  StandardException  Standard exception policy.
     **/
    protected long splitFor(
    OpenBTree               open_btree, 
    DataValueDescriptor[]   template,
    BranchControlRow        parent_page, 
    DataValueDescriptor[]	splitrow,
    int                     flag)
        throws StandardException
    {
        long current_leaf_pageno = this.page.getPageNumber();

        if (SanityManager.DEBUG)
        {
			if (parent_page == null && ( ! this.getIsRoot()))
            	SanityManager.THROWASSERT(
                	this + " splitFor null parent and non-root");
        }

        // See if this page has space.
        if ((this.page.recordCount() - 1 < 
                open_btree.getConglomerate().maxRowsPerPage) &&
            (this.page.spaceForInsert(splitrow, (FormatableBitSet) null,
				AccessFactoryGlobals.BTREE_OVERFLOW_THRESHOLD)))
        {
            // The splitFor() operation is complete, commit the work done
            // before releasing the latches.
            open_btree.getXactMgr().commit();
             
            if (parent_page != null)
                 parent_page.release();

            this.release();

            return(current_leaf_pageno);
        }

        // RESOLVE (mikem) - for rows bigger than pages this assert may 
        // trigger until we have long rows.
        if (SanityManager.DEBUG)
            SanityManager.ASSERT(this.page.recordCount() > 1);

        // Track.LeafSplit++;

        if (this.getIsRoot())
        {
            // Track.LeafSplitRoot++;

            growRoot(open_btree, template, this);

         
            // At this point, this page has been unlatched.  So code below this
            // point must not access this object's fields.
            
            ControlRow new_root = ControlRow.Get(open_btree, BTree.ROOTPAGEID);

            return(
                new_root.splitFor(open_btree, template, null, splitrow, flag));
        }

        // At this point we know that this page has to be split and
        // that it isn't a root page.

        int splitpoint = (this.page.recordCount() - 1) / 2 + 1;

        if ((flag & ControlRow.SPLIT_FLAG_FIRST_ON_PAGE) != 0)
        {
            // move all the row to the new page
            splitpoint = 1;
        }
        else if ((flag & ControlRow.SPLIT_FLAG_LAST_ON_PAGE) != 0)
        {
            // This is not optimal as we would rather move no rows to the
            // next page, but what should we use as a discriminator?
            splitpoint = this.page.recordCount() - 1;
        }

        if (SanityManager.DEBUG)
        {
			if (splitpoint <= 0)
            	SanityManager.THROWASSERT(this + " yikes! splitpoint of 0!");
        }

        // Save away current split point leaf row, and build a branch row
        // based on it.
        DataValueDescriptor[] split_leaf_row = 
            open_btree.getConglomerate().createTemplate();

        this.page.fetchFromSlot(
            (RecordHandle) null, splitpoint, split_leaf_row, 
            (FetchDescriptor) null, true); 

        // Create the branch row to insert onto the parent page.  For now
        // use a fake page number because we don't know the real page 
        // number until the allocate is done, but want to delay the 
        // allocate until we know the insert will succeed.
        BranchRow branchrow = BranchRow.createBranchRowFromOldLeafRow(
            split_leaf_row, BranchRow.DUMMY_PAGE_NUMBER);


        // At this point we have guaranteed there is space in the parent
        // page for splitrow, but it could be the case that the new
        // "branchrow" does not fit on the parent page.
        if (!parent_page.page.spaceForInsert(
                branchrow.getRow(), (FormatableBitSet) null,
				AccessFactoryGlobals.BTREE_OVERFLOW_THRESHOLD))
        {
            // There is no room on the parent page to complete a split at
            // the current level, so restart the split at top with the 
            // branchrow that did not fit.  On return from this routine
            // there is no way to know the state of the tree, so the
            // current split pass recursion must end.
            return(
                ((BranchControlRow) parent_page).restartSplitFor(
                    open_btree, template, parent_page, this, 
                    branchrow.getRow(), splitrow, flag));

        }
        // Before moving the rows on the page, while having the latch on the
        // page, notify btree scans that the rows on this page may be moving
        // onto another page.
        //
        // RESOLVE (mikem) - need to pass conlgomid.
        // RESOLVE (mikem) - some optimization later, we only need to notify
        // the scans which are positioned on moving rows.
        if (SanityManager.DEBUG)
            SanityManager.ASSERT(open_btree.init_open_user_scans != null);

        open_btree.init_open_user_scans.saveScanPositions(
                open_btree.getConglomerate(), this.page);

        // Get exclusive RECORD_ID_PROTECTION_HANDLE lock to make sure that
        // we wait for scans in other transactions to move off of this page
        // before we split.

        if (!open_btree.getLockingPolicy().lockScan(
                this, parent_page, true /* for update */, 
                ConglomerateController.LOCK_UPD))
        {
            // we had to give up latches on this and parent_page to get the
            // split lock.  Redo the whole split pass as we have lost our
            // latches.  Just returning is ok, as the caller can not assume
            // that split has succeeded in making space.  Note that at this
            // point in the split no write work has been done in the current
            // internal transaction, so giving up here is fairly cheap.

            // RESOLVE RLL PERFORMANCE - we could keep a stack of visited
            // pages so as to not have to redo the complete search.
            return(current_leaf_pageno);
        }

        // Create a new leaf page under the parent.
        LeafControlRow newleaf = 
            LeafControlRow.Allocate(open_btree, parent_page);

        // Now that we know the page number of the new child page update
        // the branch row to be inserted with the correct value.
        branchrow.setPageNumber(newleaf.page.getPageNumber());

        // Test fail after allocation
        if (SanityManager.DEBUG)
        {
            if (SanityManager.DEBUG_ON("leaf_split_abort1"))
            {
                throw StandardException.newException(
                        SQLState.BTREE_ABORT_THROUGH_TRACE);
            }
        }

        // Link it to the right of the current page.
        newleaf.linkRight(open_btree, this);


		// Copy the index rows (from the splitpoint to the end of the page) 
        // from the old page to the new leaf, do not
        // copy the control row.  This routine will purge all the copied rows
        // and maintain the deleted status of the moved rows.
        int num_rows_to_move = this.page.recordCount() - splitpoint;

        if (SanityManager.DEBUG)
            SanityManager.ASSERT(num_rows_to_move >= 0);

        if (num_rows_to_move != 0)
        {
            this.page.copyAndPurge(
                newleaf.page, splitpoint, num_rows_to_move, 1);
        }

        // Test fail after new page has been updated.
        if (SanityManager.DEBUG)
        {
            if (SanityManager.DEBUG_ON("leaf_split_abort2"))
            {
                throw StandardException.newException(
                        SQLState.BTREE_ABORT_THROUGH_TRACE);
            }
        }

        // Test fail after new page has been updated.
        if (SanityManager.DEBUG)
        {
            if (SanityManager.DEBUG_ON("leaf_split_abort3"))
            {
                throw StandardException.newException(
                        SQLState.BTREE_ABORT_THROUGH_TRACE);
            }
        }

        // Find spot to insert branch row, and insert it.


        BranchRow branch_template = 
            BranchRow.createEmptyTemplate(open_btree.getConglomerate());
        SearchParameters sp = 
            new SearchParameters(
                branchrow.getRow(),
                SearchParameters.POSITION_LEFT_OF_PARTIAL_KEY_MATCH,
                branch_template.getRow(),
                open_btree, false);

        parent_page.searchForEntry(sp);

        // There must be space on the parent to insert the row!
        if (SanityManager.DEBUG)
        {
            SanityManager.ASSERT(
                parent_page.page.spaceForInsert(
                    branchrow.getRow(), (FormatableBitSet) null,
					AccessFactoryGlobals.BTREE_OVERFLOW_THRESHOLD));