branchcontrolrow.java

derby database source code.good for you.

    }


	/**
	 **	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 latched.
     **
     ** @exception StandardException Standard exception policy.
	 **/
	protected boolean shrinkFor(
    OpenBTree               open_btree, 
    DataValueDescriptor[]   shrink_key)
        throws StandardException
    {
        ControlRow childpage = null;
        boolean    shrinkme  = false;

        try
        {
            if (SanityManager.DEBUG)
                SanityManager.ASSERT(this.page.isLatched());

            // Find the child page for the shrink key.

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

            this.searchForEntry(sp);
            childpage = this.getChildPageAtSlot(sp.btree, sp.resultSlot);

            // Recursively shrink the child.  If this call returns
            // true, then the child page has been deleted from its
            // sibling chain, and we have to delete the entry for it
            // in this page.

            if (childpage.shrinkFor(open_btree, shrink_key))
            {
                // Child was deallocated.
                if (sp.resultSlot != 0)
                {
                    // Remove the corresponding branch row.  This call assumes
                    // that raw store will shift all higher slots down to fill
                    // the purged slot.
                    this.page.purgeAtSlot(sp.resultSlot, 1, true);
                }
                else
                {
                    // Shrunk slot is zero, which means the left child page was
                    // deallocated. If the current page is empty, then
                    // we have to deallocate it.  Otherwise, we "slide" the rows
                    // down, making the first index row into the left child,
                    // and the second index row into the first, etc.

                    if (this.page.recordCount() > 1)
                    {
                        // There is a branch row on this page (besides the
                        // control row).  Make the first branch row into the
                        // left child.

                        long leftchildpageid =
                            getChildPageIdAtSlot(open_btree, 1);

                        this.setLeftChildPageno(leftchildpageid);

                        // purge the row we just made the "left child", this
                        // will automatically shifta all other rows "left" in
                        // the tree.
                        this.page.purgeAtSlot(1, 1, true);
                    }
                    else
                    {
                        // We shrunk the left child which was the last child on
                        // the page.  This means that this entire subtree is
                        // empty.  Again, there are two cases: root vs.
                        // non-root.  Because this method waits till pages are
                        // completely empty before deallocating them from the
                        // index, an empty root page means an empty index.
                        // If this page is not the root, then simply
                        // deallocate it and return that fact to the caller.

                        if (this.getIsRoot())
                        {
                            // The root page has become empty.  If the root page
                            // is empty, then the index is empty.  What has to
                            // happen here is that this page has to be
                            // converted back to an empty leaf page.

                            // With the current interface, after this page has
                            // been converted to a leaf, the caller will be
                            // left with a branch control row object, although
                            // the page is a leaf page.  This same problem was
                            // addressed in splitFor by adjusting the interface
                            // - the two routines should at least have the same
                            // interface style.

                            if (SanityManager.DEBUG)
                            {
                                SanityManager.ASSERT(
                                    this.page.recordCount() == 1);
                            }

                            LeafControlRow newleafroot = new LeafControlRow(
                                open_btree, this.page, null, true);

                            newleafroot.page.updateAtSlot(
                                0, newleafroot.getRow(), 
                                (FormatableBitSet) null);

                            newleafroot.release();

                            shrinkme = true;
                        }
                        else
                        {
                            // This page is empty, but it's not the root.  We
                            // have to unlink this page from its siblings, and
                            // return to the parent branch page that its
                            // branch row should be removed.

                            // Unlink this page from its siblings.
                            if (this.unlink(open_btree))
                            {
                                // Tell the caller to remove entry.
                                shrinkme = true;
                            }
                        }
                    }
                }
            }
        }
        finally
        {
            // If shrinkme then the page has been unlatched either by
            // page.removePage(), or by the process of changing the root branch
            // page to a root leaf page.
            if (!shrinkme)
                this.release();
        }

        return(shrinkme);
    }

    /**
     * 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>
     * Latches:
     * o PARENT    : is latched on entry (unless the split is the root then
     *               there is no parent.
     * o THISBRANCH: the current page is latched on entry.
     * o CHILD     : latch the child page which will be pointed at by the
     *               left child pointer of the new page.
     *               RESOLVE (mikem) -see comments below
     * o NEWPAGE   : Allocate and latch new page.
     * o CHILD     : release. (RESOLVE)
     * o fixparents: latch pages and reset their parent pointers.
     *               Conditionally fix up the parent links on the pages
     *               pointed at by the newly allocated page.  First get latch
     *               and release on the left child page and then loop through
     *               slots on NEWPAGE, from left to right getting and
     *               releasing latches.
     *
     *
	 * @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     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,
    DataValueDescriptor[]	splitrow,
    int                     flag)
        throws StandardException
	{
		int        childpageid;
		ControlRow childpage;

		// On entry, the parent page is either latched by the caller,
		// or it's null (which implies that this object is the root).

        if (SanityManager.DEBUG)
        {
            SanityManager.ASSERT(parent != null || this.getIsRoot());

            SanityManager.ASSERT(
                parent == null || parent.page.isLatched(),
                "parent page is not latched");

            SanityManager.ASSERT(this.page.isLatched(),
                "page is not latched:");
        }

        if ((this.page.recordCount() - 1 >=
                open_btree.getConglomerate().maxRowsPerPage) ||
            (!this.page.spaceForInsert(splitrow, (FormatableBitSet) null,
				AccessFactoryGlobals.BTREE_OVERFLOW_THRESHOLD)))
        {

            if (this.page.recordCount() == 1)
            {
                // RESOLVE (mikem) long row issue.  For now it makes no sense
                // to split if there are no rows.  So if spaceForRecord() fails
                // on empty page, we throw exception.
                throw StandardException.newException(
                        SQLState.BTREE_NO_SPACE_FOR_KEY);
            }

			// Track.BranchSplit++;

			if (this.getIsRoot())
			{
				// Track.BranchSplitRoot++;
				growRoot(open_btree, template, this);

				parent = (BranchControlRow)
                    ControlRow.Get(open_btree, BTree.ROOTPAGEID);


				return(parent.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.
            if (SanityManager.DEBUG)
            {
                SanityManager.ASSERT(!this.getIsRoot());
                SanityManager.ASSERT(parent != null);
            }

            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!");
            }


            // Before any logged operation is done in the current internal
            // xact, make sure that there is room in the parent to insert
            // the new branch row.
            //
			// Create a new branch row which points to the new page,
            // and insert it on parent page.

            // Read in the branch row which is at the split point.
            BranchRow split_branch_row =
                BranchRow.createEmptyTemplate(open_btree.getConglomerate());

            this.page.fetchFromSlot(
                (RecordHandle) null, splitpoint, split_branch_row.getRow(), 
                (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 newbranchrow =
                split_branch_row.createBranchRowFromOldBranchRow(
                        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
            // "newbranchrow" does not fit on the parent page.
            if (!parent.page.spaceForInsert(
                    newbranchrow.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(
                    parent.restartSplitFor(
                        open_btree, template, parent, this,
                        newbranchrow.getRow(), splitrow, flag));
            }

			// Get the child page for the index row at the split point
			// This will be the left child for	the new page.  We're
			// getting the page because BranchControlRow.Allocate
			// sets the left child pointer from a BranchControlRow.
			// If there were a version which just took the pageid,
			// we wouldn't have to get the page (the latch on this
			// page is enough to ensure that the child page won't
			// disappear).

            childpage = this.getChildPageAtSlot(open_btree, splitpoint);

			// Allocate a new branch page and link it to the
			// right of the current page.
			BranchControlRow newbranch =
                BranchControlRow.Allocate(open_btree, childpage,
                    this.getLevel(), parent);
			newbranch.linkRight(open_btree, this);


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

			// Done with the child page.
			childpage.release();

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

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

			parent.searchForEntry(sp);

			byte insertFlag = Page.INSERT_INITIAL;
			insertFlag |= Page.INSERT_DEFAULT;
			insertFlag |= Page.INSERT_UNDO_WITH_PURGE;
			if (parent.page.insertAtSlot(
                    sp.resultSlot + 1,
                    newbranchrow.getRow(),
                    (FormatableBitSet) null,
                    (LogicalUndo)null,
                    insertFlag, AccessFactoryGlobals.BTREE_OVERFLOW_THRESHOLD)
					== null)
            {
                throw StandardException.newException(
                            SQLState.BTREE_NO_SPACE_FOR_KEY);
			}


            // Test fail after of row onto parent page.
            if (SanityManager.DEBUG)
            {
                if (SanityManager.DEBUG_ON("branch_split_abort2"))
                {
                    throw StandardException.newException(
                            SQLState.BTREE_ABORT_THROUGH_TRACE);
                }
            }