btreescan.java

derby database source code.good for you.

		throws StandardException
	{
		boolean         exact;

        // This routine should only be called from first next() call //
        if (SanityManager.DEBUG)
        {
            SanityManager.ASSERT(
                (scan_state == SCAN_INIT) || (scan_state == SCAN_HOLD_INIT));
            SanityManager.ASSERT(pos.current_rh          == null);
            SanityManager.ASSERT(pos.current_positionKey == null);
            SanityManager.ASSERT(pos.current_scan_pageno == 0);
        }

        // Loop until you can lock the row previous to the first row to be
        // returned by the scan, while holding the page latched, without
        // waiting.  If you have to wait, drop the latch, wait for the lock -
        // which makes it likely if you wait for the lock you will loop just
        // once, find the same lock satisfies the search and since you already
        // have the lock it will be granted.
        while (true)
        {
            // Find the starting page and row slot, must start at root and
            // search either for leftmost leaf, or search for specific key.
            ControlRow root = ControlRow.Get(this, BTree.ROOTPAGEID); 

            // include search of tree in page visited stats.
            stat_numpages_visited += root.getLevel() + 1;

            boolean need_previous_lock = true;

            if (init_startKeyValue == null)
            {
                // No start given, so position at 0 slot of leftmost leaf page
                pos.current_leaf = (LeafControlRow) root.searchLeft(this);

                pos.current_slot = ControlRow.CR_SLOT;
                exact     = false;
            }
            else
            {
                // Search for the starting row.

                if (SanityManager.DEBUG)
                    SanityManager.ASSERT(
                        (init_startSearchOperator == ScanController.GE) ||
                        (init_startSearchOperator == ScanController.GT));

                SearchParameters sp = new SearchParameters(
                    init_startKeyValue, 
                    ((init_startSearchOperator == ScanController.GE) ? 
                        SearchParameters.POSITION_LEFT_OF_PARTIAL_KEY_MATCH : 
                        SearchParameters.POSITION_RIGHT_OF_PARTIAL_KEY_MATCH),
                    init_template, this, false);

                pos.current_leaf = (LeafControlRow) root.search(sp);

                pos.current_slot = sp.resultSlot;
                exact     = sp.resultExact;

                // The way that scans are used, the caller calls next()
                // to position on the first row.  If the result of the
                // search that found the starting page and slot was not
                // exact, then the page/slot will refer to the row before
                // the first qualifying row.  The first call to next()
                // will therefore move to the first (potentially) qualifying
                // row.  However, if the search was exact, then we don't
                // want to move the position on the first call to next.
                // In that case, by decrementing the slot, the first call
                // to next will put us back	on the starting row.

                if (exact && init_startSearchOperator == ScanController.GE)
                {
                    pos.current_slot--;

                    // A scan on a unique index, with a start position of
                    // GE, need not get a previous key lock to protect the
                    // range.  Since it is unique no other key can go before
                    // the first row returned from the scan.
                    //
                    // RESOLVE - currently btree's only support allowDuplicates
                    // of "false", so no need to do the extra check, current
                    // btree implementation depends on RowLocation field
                    // making every key unique (duplicate indexes are supported
                    // by the nUniqueColumns and nKeyFields). 
                    if (getConglomerate().nUniqueColumns < getConglomerate().nKeyFields)
                    {
                        // this implies unique index, thus no prev key.
                        need_previous_lock = false;
                    }
                }
            }

            boolean latch_released = false;
            if (need_previous_lock)
            {
                latch_released = 
                    !this.getLockingPolicy().lockScanRow(
                        this, this.getConglomerate(), pos,
                        true, 
                        init_lock_fetch_desc,
                        pos.current_lock_template,
                        pos.current_lock_row_loc,
                        true, init_forUpdate, 
                        lock_operation);
            }
            else
            {
                // Don't need to lock the "previous key" but still need to get
                // the scan lock to protect the position in the btree.

                latch_released =
                    !this.getLockingPolicy().lockScan(
                        pos.current_leaf,   // the page we are positioned on.
                        (ControlRow) null,  // no other page to unlatch
                        false,              // lock for read.
                        lock_operation);    // not used.
            }

            // special test to see if latch release code works
            if (SanityManager.DEBUG)
            {
                latch_released = 
                    test_errors(
                        this,
                        "BTreeScan_positionAtStartPosition", true,
                        this.getLockingPolicy(), 
                        pos.current_leaf, latch_released);
            }

            if (latch_released)
            {
                // lost latch on pos.current_leaf, search the tree again.
                pos.current_leaf = null;
                continue;
            }
            else
            {
                // success! got all the locks, while holding the latch.
                break;
            }
        }

        this.scan_state         = SCAN_INPROGRESS;
        pos.current_scan_pageno = pos.current_leaf.page.getPageNumber();
		pos.current_slot        = pos.current_slot;

        if (SanityManager.DEBUG)
            SanityManager.ASSERT(pos.current_leaf != null);
	}

    /**
     * Position scan at "start" position for a backward scan.
     * <p>
     * Positions the scan to the slot just after the first record to be 
     * returned from the backward scan.  Returns the start page latched, and 
     * sets "current_slot" to the slot number just right of the first slot
     * to return.
     * <p>
     *
	 * @return The leaf page containing the start position, or null if no
     *         start position is found.
     *
	 * @exception  StandardException  Standard exception policy.
     **/
    protected void positionAtStartForBackwardScan(
    BTreeRowPosition    pos)
        throws StandardException
	{
		boolean         exact;

        // This routine should only be called from first next() call //
        if (SanityManager.DEBUG)
        {
            SanityManager.ASSERT(
                (this.scan_state == SCAN_INIT) || 
                (this.scan_state == SCAN_HOLD_INIT));

            SanityManager.ASSERT(pos.current_rh          == null);
            SanityManager.ASSERT(pos.current_positionKey         == null);
            SanityManager.ASSERT(pos.current_scan_pageno == 0);
        }

        // Loop until you can lock the row previous to the first row to be
        // returned by the scan, while holding the page latched, without
        // waiting.  If you have to wait, drop the latch, wait for the lock -
        // which makes it likely if you wait for the lock you will loop just
        // once, find the same lock satisfies the search and since you already
        // have the lock it will be granted.
        while (true)
        {
            // Find the starting page and row slot, must start at root and
            // search either for leftmost leaf, or search for specific key.
            ControlRow root = ControlRow.Get(this, BTree.ROOTPAGEID); 

            // include search of tree in page visited stats.
            stat_numpages_visited += root.getLevel() + 1;

            if (init_startKeyValue == null)
            {
                // No start given, position at last slot + 1 of rightmost leaf 
                pos.current_leaf = (LeafControlRow) root.searchRight(this);

                pos.current_slot = pos.current_leaf.page.recordCount();
                exact     = false;
            }
            else
            {
                /*
                if (SanityManager.DEBUG)
                    SanityManager.THROWASSERT(
                        "Code not ready yet for positioned backward scans.");
                        */


                if (SanityManager.DEBUG)
                    SanityManager.ASSERT(
                        (init_startSearchOperator == ScanController.GE) ||
                        (init_startSearchOperator == ScanController.GT));

                // Search for the starting row.

                SearchParameters sp = new SearchParameters(
                    init_startKeyValue, 
                    ((init_startSearchOperator == ScanController.GE) ? 
                        SearchParameters.POSITION_RIGHT_OF_PARTIAL_KEY_MATCH : 
                        SearchParameters.POSITION_LEFT_OF_PARTIAL_KEY_MATCH),
                    init_template, this, false);

                pos.current_leaf = (LeafControlRow) root.search(sp);

                pos.current_slot = sp.resultSlot;
                exact     = sp.resultExact;

                // The way that backward scans are used, the caller calls next()
                // to position on the first row.  If the result of the
                // search that found the starting page and slot was not
                // exact, then the page/slot will refer to the row before
                // the first qualifying row.  The first call to next()
                // will therefore move to the first (potentially) qualifying
                // row.  However, if the search was exact, then we don't
                // want to move the position on the first call to next.
                // In that case, by decrementing the slot, the first call
                // to next will put us back	on the starting row.


                if (exact)
                {
                    // the search has found exactly the start position key 
                    if (init_startSearchOperator == ScanController.GE)
                    {
                        // insure backward scan returns this row by moving
                        // slot to one after this row.
                        pos.current_slot++;
                    }
                    else
                    {
                        // no work necessary leave startslot positioned on the
                        // row, we will skip this record
                        if (SanityManager.DEBUG)
                            SanityManager.ASSERT(
                                init_startSearchOperator == ScanController.GT);
                    }
                }
                else
                {
                    // the search positioned one before the start position key,
                    // move it to one "after"
                    pos.current_slot++;
                }
            }

            boolean latch_released = 
                !this.getLockingPolicy().lockScanRow(
                    this, this.getConglomerate(), pos,
                    true, 
                    init_lock_fetch_desc,
                    pos.current_lock_template,
                    pos.current_lock_row_loc,
                    true, init_forUpdate, lock_operation);

            // special test to see if latch release code works
            if (SanityManager.DEBUG)
            {
                latch_released = 
                    test_errors(
                        this,
                        "BTreeScan_positionAtStartPosition", true,
                        this.getLockingPolicy(), pos.current_leaf, latch_released);
            }

            if (latch_released)
            {
                // lost latch on pos.current_leaf, search the tree again.
                pos.current_leaf = null;
                continue;
            }
            else
            {
                // success! got all the locks, while holding the latch.
                break;
            }
        }

        this.scan_state          = SCAN_INPROGRESS;
        pos.current_scan_pageno = pos.current_leaf.page.getPageNumber();

        if (SanityManager.DEBUG)
            SanityManager.ASSERT(pos.current_leaf != null);

        // System.out.println("backward scan end start position: " +
        //       " current_slot = " + this.current_slot );
	}

    /**
     * Position scan to 0 slot on next page.
     * <p>
     * Position to next page, keeping latch on previous page until we have 
     * latch on next page.  This routine releases the latch on current_page
     * once it has successfully gotten both the latch on the next page and
     * the scan lock on the next page.
     *
	 * @return The next leaf page, null if scan is done.
     *
     * @param pos           current row position of the scan.
     *
	 * @exception  StandardException  Standard exception policy.
     **/
    protected void positionAtNextPage(
    BTreeRowPosition    pos)
        throws StandardException
    {
        // RESOLVE (mikem) - not sure but someday in the future this
        // assert may not be true, but for now we always have the scan
        // lock when we call this routine.
        if (SanityManager.DEBUG)
            SanityManager.ASSERT(pos.current_scan_pageno != 0);

        while (true)
        {
            if ((pos.next_leaf = 
                 (LeafControlRow) pos.current_leaf.getRightSibling(this)) == null)
            {
                break;