controlrow.java

derby database source code.good for you.

                use_last_search_result_hint = 
                    (midslot == this.last_search_result) ? true : false;
                this.last_search_result = midslot;

                return;
            }
            else if (compare_ret > 0)
            {
                // key falls to the left of midslot
                rightslot  = midslot;
                rightrange = midslot - 1;
            }
            else
            {
                // key falls to the right of midslot
                leftslot   = midslot;
                leftrange  = midslot + 1;
            }

            midslot = (leftrange + rightrange) / 2;
            //midslot = (leftrange + rightrange) >> 1;
        }

        // update the hints based on result of the search.
        this.use_last_search_result_hint = 
            (leftslot == this.last_search_result);
        this.last_search_result = leftslot;

        // no exact match found, leftslot will point at the slot on the
        // page just before where the row should be inserted.  In the case
        // where the key is before rows on the page then leftslot will be
        // 0 (an empty page is a special case of this).
        if (SanityManager.DEBUG)
        {
			if (leftslot != rightslot - 1)
            	SanityManager.THROWASSERT(
                	"leftslot = " + leftslot + "; rightslot = " + rightslot);
        }

        params.resultSlot  = leftslot;
        params.resultExact = false;

        if (SanityManager.DEBUG)
        {
            // System.out.println("searchForEntry() exit: params:" + params);
        }

        return;
    }

	/**
	Compare two orderable rows, considering nCompareCols, and return -1, 0, or 1
	depending on whether the first row (indexrow) is less than, equal to, or 
    greater than the second (key).  The key may have fewer columns present 
    than nCompareCols.

	In such a case, if all the columns of the partial key match all of the 
    corresponding columns in the index row, then the value passed in in 
    partialKeyOrder is returned.  The caller should pass in partialKeyOrder=1 
    if the index rows which match a partial key should be considered to be 
    greater than the partial key, and -1 if they should be considered to be 
    less.

    This routine only reads objects off the page if it needs them, so if a 
    multi-part key differs in the first column the subsequent columns are not
    read.

    @param indexpage Controlrow of page to get target row from.
    @param slot      Slot to get control row from.
    @param indexrow template of the target row (the row in the index).
	@param key the (possibly partial) search key.
	@param nCompareCols the number of columns to compare.
	@param partialKeyOrder what to return on a partial key match.
	@param ascOrDesc column sort order information
	@throws StandardException if lower levels have a problem.

    @exception StandardException Standard exception policy.
	**/
	public static int CompareIndexRowFromPageToKey(
    ControlRow              indexpage,
    int                     slot,
    DataValueDescriptor[]   indexrow, 
    DataValueDescriptor[]	key,
    int                     nCompareCols, 
    int                     partialKeyOrder,
    boolean[]               ascOrDesc)
        throws StandardException
	{
        int compare_result;

		// Get the actual number of key columns present
		// in the partial key.
		int partialKeyCols = key.length;

        // Fetch entire index row from page.
        // RESOLVE (mikem) - it may be more efficient to fetch just the
        // columns you need, but there is overhead currently in raw
        // store, since to get to the n'th column you have to walk 
        // through the preceding n-1 columns.
        indexpage.page.fetchFromSlot(
            (RecordHandle) null, slot, indexrow, 
            (FetchDescriptor) null,
            true);

		// Compare corresponding columns in the index row and the key.
		for (int i = 0; i < nCompareCols; i++)
		{
			// See if we have run out of partial key columns.
			if (i >= partialKeyCols)
			{
				// All the columns of the partial key match, and 
				// there are more columns in the index row.  We
				// want to return -1 or 1, depending on whether the
				// caller wants to direct the search to the beginning
				// of this key range or the beginning of the next
				// one.  If the caller passes in -1, the index row
				// will appear less than the partial key, sending the
				// search to the next range ("to the right").  If the
				// caller passes in 1, the index row will appear
				// to be greater than the search key, sending the search
				// to the beginning of the range ("to the left").
				return partialKeyOrder;
			}

			// Get the corresponding columns to compare

			// Orderable indexcol = (Orderable) indexrow[i];
			// Orderable keycol = (Orderable) key[i];

			// Compare them.
			// int r = indexcol.compare(keycol);

            int r = indexrow[i].compare(key[i]);

			// If the columns don't compare equal, we're done.
			// Return the sense of the comparison.
			if (r != 0)
			{
				//coulmns could have been sorted in ascending or descending
				//order. depending on ascending/descending order search 
				//direction will change.

				if (ascOrDesc[i])  // true - Ascending order
					return r;
				else
					return -r;
		    }
		}

		// We made it through all the columns, and they must have
		// all compared equal.  So return that the rows compare equal.
		return 0;
	}

	public static int CompareIndexRowToKey(
    DataValueDescriptor[]   indexrow, 
    DataValueDescriptor[]   key,
    int                     nCompareCols, 
    int                     partialKeyOrder,
    boolean[]               ascOrDesc)
        throws StandardException
	{
		// Get the actual number of key columns present
		// in the partial key.
		int partialKeyCols = key.length;

		// Compare corresponding columns in the index row and the key.
		for (int i = 0; i < nCompareCols; i++)
		{
			// See if we have run out of partial key columns.
			if (i >= partialKeyCols)
			{
				// All the columns of the partial key match, and 
				// there are more columns in the index row.  We
				// want to return -1 or 1, depending on whether the
				// caller wants to direct the search to the beginning
				// of this key range or the beginning of the next
				// one.  If the caller passes in -1, the index row
				// will appear less than the partial key, sending the
				// search to the next range ("to the right").  If the
				// caller passes in 1, the index row will appear
				// to be greater than the search key, sending the search
				// to the beginning of the range ("to the left").
				return partialKeyOrder;
			}

			// Get the corresponding columns to compare
			DataValueDescriptor indexcol = indexrow[i];
			DataValueDescriptor keycol = key[i];

			// Compare them.
			int r = indexcol.compare(keycol);

			// If the columns don't compare equal, we're done.
			// Return the sense of the comparison.
			if (r != 0)
			{
				if (ascOrDesc[i])  // true - column in ascending order
					return r;
				else
					return -r;
		    }
		}

		// We made it through all the columns, and they must have
		// all compared equal.  So return that the rows compare equal.
		return 0;
	}

	/**
	 ** Perform consistency checks which are common to all
	 ** pages that derive from ControlRow (both leaf and 
	 ** branch pages).  The checks are:
	 ** <menu>
	 ** <li> This page thinks the parent argument is actually
	 **      its parent.
	 ** <li> The level of this page is 1 less than the level of
	 **      the parent.
	 ** <li> All the rows on the page are in order.
	 ** <li> Both left and right siblings, if they exist, are at
	 **      the same level of this page.
	 ** <li> This page is the left sibling of its right sibling,
	 **      and it's the right sibling of its left sibling.
	 ** <li> The last row on the left sibling is < the first
	 **      row on this page.
	 ** <li> The first row on the right sibling is > than the
	 **      the last row on this page.
	 ** </menu>
	 ** Note that these last two are really only true if there
	 ** are never duplicate keys.

    @exception StandardException Standard exception policy.
	 **/  
	protected void checkGeneric(
    OpenBTree  btree, 
    ControlRow parent,
    boolean    check_other_pages)
        throws StandardException
	{
        if (SanityManager.DEBUG)
        {
            SanityManager.ASSERT(this.page.recordCount() >= 1);
            SanityManager.ASSERT(!this.page.isDeletedAtSlot(0));

            // Make sure that we think we're a child of the parent.
			if (((parent != null) &&
                 (parent.page.getPageNumber() != this.getParentPageNumber())))
            	SanityManager.THROWASSERT(this + " not child of " + parent);

            // Check this page's level.
			if (((parent != null) &&
                 (parent.getLevel() != this.getLevel() + 1)))
            	SanityManager.THROWASSERT(this +
						" at wrong level when compared to parent:" + parent);
            
            // Check rows are in order.
            checkRowOrder(btree, parent);

            // Check siblings.
            if (check_other_pages)
                checkSiblings(btree);
        }
	}

	/**
	 ** Check that all rows on the page are in order.  This
	 ** means that each key is > than the previous key.

    @exception StandardException Standard exception policy.
	 **/
	protected boolean checkRowOrder(OpenBTree btree, ControlRow parent)
        throws StandardException
	{
        if (SanityManager.DEBUG)
        {
            RecordHandle            lesser_handle   = null;
            RecordHandle            greater_handle  = null;
            DataValueDescriptor[]   lesser          = getRowTemplate(btree);
            DataValueDescriptor[]   greater         = getRowTemplate(btree);
            boolean                 is_consistent   = true;
           
            
            int numslots = page.recordCount();
            for (int i = ControlRow.CR_SLOT + 1; (i + 1) < numslots; i++)
            {
               lesser_handle = 
                   page.fetchFromSlot(
                       (RecordHandle) null, i, lesser, 
                       (FetchDescriptor) null, true); 
               greater_handle = 
                   page.fetchFromSlot(
                       (RecordHandle) null, i + 1, greater, 
                       (FetchDescriptor) null, true); 

               SanityManager.ASSERT(btree.getConglomerate().nUniqueColumns <= 
                                    btree.getConglomerate().nKeyFields);
               int compare_result = 
                   CompareIndexRowToKey(
                       lesser, greater,
                       btree.getConglomerate().nUniqueColumns, 0,
                       btree.getConglomerate().ascDescInfo);

               // >= 0 means that lesser >= greater
			   if (compare_result >= 0)
               {
                   SanityManager.THROWASSERT(
                       "Bad order of rows found in conglomerate: " + btree +
                       "\n." +
                       "compare result = " + compare_result + ".  " + 
                       "nKeyFields = "     + btree.getConglomerate().nKeyFields +
                       ".\n" +  
                       this + " rows " + (i) + " and " + (i + 1) +
                       " out of order.\n" +
                       "row[" + i + "] + "  + RowUtil.toString(lesser) + "\n" + 
                       "row[" + (i + 1) + "] + "  + RowUtil.toString(greater) +
                       "\ndump of page = " + 
                           debugPage(btree) +
                       "\ndump of parent page = " + 
                           ((parent != null) ? 
                                parent.debugPage(btree) : "null parent") +
                       "\rawstore dump = " + this.page);

                   is_consistent = false;
               }
            }
            return(is_consistent);
        }
        else
        {
            return(true);
        }
	}

    protected boolean compareRowsOnSiblings(
        OpenBTree   btree,
        ControlRow  left_sib,
        ControlRow  right_sib)
            throws StandardException
    {
        if (SanityManager.DEBUG)
        {
            boolean is_consistent = true;

            // Check that left last row is < right page's first row.
            if (left_sib.page.recordCount()  > 1 && 
                right_sib.page.recordCount() > 1)
            {
                DataValueDescriptor[] left_lastrow   = getRowTemplate(btree);
                DataValueDescriptor[] right_firstrow = getRowTemplate(btree);

                RecordHandle    left_lastrow_handle   = 
                    left_sib.page.fetchFromSlot(
                        (RecordHandle) null, left_sib.page.recordCount() - 1, 
                        left_lastrow, 
                        (FetchDescriptor) null, true); 

                RecordHandle    right_firstrow_handle  = 
                    right_sib.page.fetchFromSlot(
                        (RecordHandle) null, 1, right_firstrow, 
                        (FetchDescriptor) null, true); 

                int r = 
                    CompareIndexRowToKey(
                        left_lastrow, right_firstrow,
                        btree.getConglomerate().nUniqueColumns,
                        0, btree.getConglomerate().ascDescInfo);

				if (r >= 0)
                {
                	SanityManager.THROWASSERT(
                      "last row on left page " + 
                          left_sib.page.getPageNumber() + 
                      " > than first row on right page " + 
                          right_sib.page.getPageNumber() + "\n" + 
                      "left last row = " + RowUtil.toString(left_lastrow) +
                      "right first row = " + RowUtil.toString(right_firstrow)+
                      left_sib + " last > first of " + right_sib);

                    is_consistent = false;
                }
            }
            return(is_consistent);
        }
        else
        {
            return(true);
        }
    }