--- /dev/null
+/*\r
+\r
+ Derby - Class org.apache.derby.impl.store.access.btree.BTreeForwardScan\r
+\r
+ Licensed to the Apache Software Foundation (ASF) under one or more\r
+ contributor license agreements. See the NOTICE file distributed with\r
+ this work for additional information regarding copyright ownership.\r
+ The ASF licenses this file to you under the Apache License, Version 2.0\r
+ (the "License"); you may not use this file except in compliance with\r
+ the License. You may obtain a copy of the License at\r
+\r
+ http://www.apache.org/licenses/LICENSE-2.0\r
+\r
+ Unless required by applicable law or agreed to in writing, software\r
+ distributed under the License is distributed on an "AS IS" BASIS,\r
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\r
+ See the License for the specific language governing permissions and\r
+ limitations under the License.\r
+\r
+ */\r
+\r
+package org.apache.derby.impl.store.access.btree;\r
+\r
+import org.apache.derby.iapi.reference.SQLState;\r
+\r
+import org.apache.derby.iapi.services.sanity.SanityManager;\r
+\r
+import org.apache.derby.iapi.error.StandardException;\r
+\r
+import org.apache.derby.iapi.store.access.ScanController;\r
+\r
+import org.apache.derby.iapi.store.raw.Page;\r
+import org.apache.derby.iapi.store.raw.RecordHandle;\r
+\r
+import org.apache.derby.iapi.types.DataValueDescriptor;\r
+import org.apache.derby.iapi.types.RowLocation;\r
+\r
+import org.apache.derby.iapi.store.access.BackingStoreHashtable;\r
+\r
+/**\r
+\r
+ A b-tree scan controller corresponds to an instance of an open b-tree scan.\r
+ <P>\r
+ <B>Concurrency Notes<\B>\r
+ <P>\r
+ The concurrency rules are derived from OpenBTree.\r
+ <P>\r
+ @see OpenBTree\r
+\r
+**/\r
+\r
+public class BTreeForwardScan extends BTreeScan\r
+{\r
+ /*\r
+ ** Private/Protected methods of This class, sorted alphabetically\r
+ */\r
+\r
+ /**\r
+ Position scan at "start" position.\r
+ <p>\r
+ Positions the scan to the slot just before the first record to be returned\r
+ from the scan. Returns the start page latched, and sets "current_slot" to\r
+ the slot number.\r
+\r
+ @exception StandardException Standard exception policy.\r
+ **/\r
+ protected void positionAtStartPosition(\r
+ BTreeRowPosition pos)\r
+ throws StandardException\r
+ {\r
+ positionAtStartForForwardScan(pos);\r
+ }\r
+\r
+ /**\r
+ * Fetch the next N rows from the table.\r
+ * <p>\r
+ * Utility routine used by both fetchSet() and fetchNextGroup().\r
+ *\r
+ * @exception StandardException Standard exception policy.\r
+ **/\r
+ protected int fetchRows(\r
+ BTreeRowPosition pos,\r
+ DataValueDescriptor[][] row_array,\r
+ RowLocation[] rowloc_array,\r
+ BackingStoreHashtable hash_table,\r
+ long max_rowcnt,\r
+ int[] key_column_numbers)\r
+ throws StandardException\r
+ {\r
+\r
+ int ret_row_count = 0;\r
+ DataValueDescriptor[] fetch_row = null;\r
+ RecordHandle rh;\r
+\r
+ if (max_rowcnt == -1)\r
+ max_rowcnt = Long.MAX_VALUE;\r
+\r
+\r
+ if (this.scan_state == BTreeScan.SCAN_INPROGRESS)\r
+ {\r
+ // reposition the scan at the row just before the next one to \r
+ // return.\r
+ // This routine handles the mess of repositioning if the row or \r
+ // the page has disappeared. This can happen if a lock was not \r
+ // held on the row while not holding the latch (can happen if\r
+ // this scan is read uncommitted).\r
+ //\r
+ // code path tested by readUncommitted.sql:TEST 1\r
+ //\r
+ if (!reposition(pos, true))\r
+ {\r
+ if (SanityManager.DEBUG)\r
+ {\r
+ SanityManager.THROWASSERT(\r
+ "can not fail with 2nd param true.");\r
+ }\r
+ }\r
+\r
+ }\r
+ else if (this.scan_state == SCAN_INIT)\r
+ {\r
+ // 1st positioning of scan (delayed from openScan).\r
+ positionAtStartPosition(pos);\r
+ }\r
+ else if (this.scan_state == SCAN_HOLD_INPROGRESS)\r
+ {\r
+ reopen();\r
+\r
+ this.scan_state = SCAN_INPROGRESS;\r
+\r
+ if (SanityManager.DEBUG)\r
+ {\r
+ SanityManager.ASSERT(scan_position.current_positionKey != null);\r
+ }\r
+\r
+ // reposition the scan at the row just before the next one to \r
+ // return.\r
+ // This routine handles the mess of repositioning if the row or \r
+ // the page has disappeared. This can happen if a lock was not \r
+ // held on the row while not holding the latch.\r
+ //\r
+ // code path tested by holdCursor.sql: TEST 9\r
+ if (!reposition(pos, true))\r
+ {\r
+ if (SanityManager.DEBUG)\r
+ {\r
+ SanityManager.THROWASSERT(\r
+ "can not fail with 2nd param true.");\r
+ }\r
+ }\r
+\r
+ }\r
+ else if (this.scan_state == SCAN_HOLD_INIT)\r
+ {\r
+ reopen();\r
+\r
+ positionAtStartForForwardScan(scan_position);\r
+ }\r
+ else\r
+ {\r
+ if (SanityManager.DEBUG)\r
+ SanityManager.ASSERT(this.scan_state == SCAN_DONE);\r
+\r
+ return(0);\r
+ }\r
+\r
+ if (SanityManager.DEBUG)\r
+ {\r
+ SanityManager.ASSERT(\r
+ init_template != null, "init_template is null");\r
+ }\r
+\r
+ if (SanityManager.DEBUG)\r
+ {\r
+ SanityManager.ASSERT(this.container != null,\r
+ "BTreeScan.next() called on a closed scan.");\r
+\r
+ if (row_array != null)\r
+ SanityManager.ASSERT(row_array[0] != null,\r
+ "first array slot in fetchNextGroup() must be non-null.");\r
+\r
+ // Btree's don't support RowLocations yet.\r
+ if (rowloc_array != null)\r
+ {\r
+ throw StandardException.newException(\r
+ SQLState.BTREE_UNIMPLEMENTED_FEATURE);\r
+ }\r
+ }\r
+\r
+ // System.out.println("top of fetchRows, fetch_row = " + fetch_row);\r
+\r
+\r
+ // At this point:\r
+ // current_page is latched. current_slot is the slot on current_page\r
+ // just before the "next" record this routine should process.\r
+\r
+ // loop through successive leaf pages and successive slots on those\r
+ // leaf pages. Stop when either the last leaf is reached (current_page\r
+ // will be null), or when stopKeyValue is reached/passed. Along the\r
+ // way apply qualifiers to skip rows which don't qualify.\r
+\r
+ while (pos.current_leaf != null)\r
+ {\r
+ // System.out.println(\r
+ // "1 of fetchSet loop, ret_row_count = " + ret_row_count +\r
+ // "fetch_row = " + fetch_row);\r
+\r
+ while ((pos.current_slot + 1) < pos.current_leaf.page.recordCount())\r
+ {\r
+\r
+ // System.out.println(\r
+ // "2 of fetchSet loop, ret_row_count = " + ret_row_count +\r
+ // "fetch_row = " + fetch_row + \r
+ // "hash_table = " + hash_table);\r
+\r
+\r
+ // unlock the previous row if doing read.\r
+ if (pos.current_rh != null)\r
+ {\r
+ this.getLockingPolicy().unlockScanRecordAfterRead(\r
+ pos, init_forUpdate);\r
+\r
+ // current_rh is used to track which row we need to unlock,\r
+ // at this point no row needs to be unlocked.\r
+ pos.current_rh = null;\r
+ }\r
+\r
+ // Allocate a new row to read the row into.\r
+ if (fetch_row == null)\r
+ {\r
+ if (hash_table == null)\r
+ {\r
+ // point at allocated row in array if one exists.\r
+ if (row_array[ret_row_count] == null)\r
+ {\r
+ row_array[ret_row_count] = \r
+ runtime_mem.get_row_for_export(getRawTran());\r
+ }\r
+\r
+ fetch_row = row_array[ret_row_count];\r
+ }\r
+ else\r
+ {\r
+ // get a brand new row.\r
+ fetch_row = \r
+ runtime_mem.get_row_for_export(getRawTran()); \r
+ }\r
+ }\r
+\r
+ // move scan current position forward.\r
+ pos.current_slot++;\r
+ this.stat_numrows_visited++;\r
+\r
+ rh =\r
+ pos.current_leaf.page.fetchFromSlot(\r
+ (RecordHandle) null,\r
+ pos.current_slot, fetch_row, \r
+ init_fetchDesc,\r
+ true);\r
+\r
+\r
+ pos.current_rh_qualified = true;\r
+\r
+ // See if this is the stop row.\r
+ if (init_stopKeyValue != null)\r
+ {\r
+ // See if current row is the >= the stopKeyValue.\r
+ //\r
+ // ret > 0: key is greater than row on page.\r
+ // ret == 0: key is exactly the row on page if full key,\r
+ // or partial match if partial key.\r
+ // ret < 0: key is less than row on page.\r
+ //\r
+ int ret = ControlRow.compareIndexRowToKey(\r
+ fetch_row,\r
+ init_stopKeyValue,\r
+ fetch_row.length,\r
+ 0, this.getConglomerate().ascDescInfo);\r
+\r
+ if ((ret == 0) && \r
+ (init_stopSearchOperator == ScanController.GE))\r
+ {\r
+ // if (partial) matched and stop is GE, end the scan.\r
+ ret = 1;\r
+ }\r
+\r
+ if (ret > 0)\r
+ {\r
+ // This is the first non-qualifying row. We're done.\r
+\r
+ pos.current_leaf.release();\r
+ pos.current_leaf = null;\r
+ positionAtDoneScan(pos);\r
+\r
+ return(ret_row_count);\r
+ }\r
+ }\r
+\r
+\r
+ // Only lock rows that are < the stopKeyValue. No need to\r
+ // requalify against stop position after losing the latch\r
+ // as the only change that could have happened is that the\r
+ // row was marked deleted - the key value cannot change.\r
+ boolean latch_released =\r
+ !this.getLockingPolicy().lockScanRow(\r
+ this, this.getConglomerate(), pos, \r
+ false, \r
+ init_lock_fetch_desc,\r
+ pos.current_lock_template,\r
+ pos.current_lock_row_loc,\r
+ false, init_forUpdate, lock_operation);\r
+\r
+ // special test to see if latch release code works\r
+ if (SanityManager.DEBUG)\r
+ {\r
+ latch_released = \r
+ test_errors(\r
+ this,\r
+ "BTreeScan_fetchNextGroup", false, \r
+ this.getLockingPolicy(),\r
+ pos.current_leaf, latch_released);\r
+ }\r
+\r
+ // At this point we have successfully locked this record, so\r
+ // remember the record handle so that it can be unlocked if\r
+ // necessary. If the above lock deadlocks, we will not try\r
+ // to unlock a lock we never got in close(), because current_rh\r
+ // is null until after the lock is granted.\r
+ pos.current_rh = rh;\r
+\r
+ if (latch_released)\r
+ {\r
+ // lost latch on page in order to wait for row lock.\r
+ // Because we have scan lock on page, we need only\r
+ // call reposition() which will use the saved record\r
+ // handle to reposition to the same spot on the page.\r
+ // We don't have to search the\r
+ // tree again, as we have the a scan lock on the page\r
+ // which means the current_rh is valid to reposition on.\r
+\r
+ if (this.getConglomerate().isUnique())\r
+ {\r
+ // Handle row location changing since lock request was \r
+ // initiated.\r
+ // In unique indexes, there is one case where an index \r
+ // row can have it's data lock key change (this usually\r
+ // cannot happen because only inserts and deletes are \r
+ // allowed - no updates). This case is an insert of a \r
+ // key, that exactly matches a committed deleted row, \r
+ // in a unique index. In that case the code updates \r
+ // the RowLocation column and flips the deleted bit to\r
+ // mark the row valid. The problem is that if this \r
+ // happens while we are waiting on a lock on the old\r
+ // RowLocation then when we wake up we have the wrong \r
+ // lock, and the row location we fetched earlier in\r
+ // this loop is invalid.\r
+\r
+ while (latch_released)\r
+ {\r
+ if (!reposition(pos, false))\r
+ {\r
+ if (SanityManager.DEBUG)\r
+ {\r
+ // can't fail while with scan lock\r
+ SanityManager.THROWASSERT(\r
+ "can not fail holding scan lock.");\r
+ }\r
+\r
+ // reposition will set pos.current_leaf to \r
+ // null, if it returns false so if the this\r
+ // ever does fail in delivered code, expect\r
+ // a null pointer exception on the next line,\r
+ // trying to call fetchFromSlot().\r
+\r
+ }\r
+\r
+ pos.current_leaf.page.fetchFromSlot(\r
+ (RecordHandle) null,\r
+ pos.current_slot, fetch_row, \r
+ init_fetchDesc,\r
+ true);\r
+\r
+ latch_released =\r
+ !this.getLockingPolicy().lockScanRow(\r
+ this, \r
+ this.getConglomerate(), \r
+ pos, \r
+ false, \r
+ init_lock_fetch_desc,\r
+ pos.current_lock_template,\r
+ pos.current_lock_row_loc,\r
+ false, init_forUpdate, lock_operation);\r
+ }\r
+ }\r
+ else\r
+ {\r
+ if (!reposition(pos, false))\r
+ {\r
+ if (SanityManager.DEBUG)\r
+ {\r
+ // can't fail while with scan lock\r
+ SanityManager.THROWASSERT(\r
+ "can not fail holding scan lock.");\r
+ }\r
+\r
+ // reposition will set pos.current_leaf to \r
+ // null, if it returns false so if the this\r
+ // ever does fail in delivered code, expect\r
+ // a null pointer exception on the next line,\r
+ // trying to call isDeletedAtSlot().\r
+\r
+ }\r
+\r
+ }\r
+ }\r
+\r
+\r
+ if (pos.current_leaf.page.isDeletedAtSlot(pos.current_slot))\r
+ {\r
+ this.stat_numdeleted_rows_visited++;\r
+ pos.current_rh_qualified = false;\r
+ }\r
+ else if (init_qualifier != null)\r
+ {\r
+ // Apply qualifiers if there are any.\r
+ pos.current_rh_qualified = \r
+ this.process_qualifier(fetch_row);\r
+ }\r
+\r
+ if (pos.current_rh_qualified)\r
+ {\r
+ // qualifying row. Save position, release latch and return.\r
+\r
+ // this.current_rh is save position of scan while latch is\r
+ // not held. It currently points at the current_slot in\r
+ // search (while latch is held).\r
+ if (SanityManager.DEBUG)\r
+ {\r
+ SanityManager.ASSERT(\r
+ pos.current_leaf.page.getSlotNumber(pos.current_rh)\r
+ == pos.current_slot);\r
+ }\r
+\r
+ // Found qualifying row. Are we done fetching rows for the\r
+ // group?\r
+ ret_row_count++;\r
+ stat_numrows_qualified++;\r
+\r
+ if (hash_table != null)\r
+ {\r
+ if (hash_table.putRow(false, fetch_row))\r
+ fetch_row = null;\r
+ }\r
+ else\r
+ {\r
+ fetch_row = null;\r
+ }\r
+\r
+ if (max_rowcnt <= ret_row_count) \r
+ {\r
+ // current_slot is invalid after releasing latch\r
+ pos.current_slot = Page.INVALID_SLOT_NUMBER;\r
+\r
+ // exit fetch row loop and return to the client.\r
+ pos.current_leaf.release();\r
+ pos.current_leaf = null;\r
+\r
+ return(ret_row_count);\r
+ }\r
+ }\r
+ }\r
+\r
+ // Move position of the scan to slot 0 of the next page. If there\r
+ // is no next page current_page will be null.\r
+ positionAtNextPage(pos);\r
+\r
+ this.stat_numpages_visited++;\r
+ }\r
+\r
+ // Reached last leaf of tree.\r
+ positionAtDoneScan(pos);\r
+\r
+\r
+ // we need to decrement when we stop scan at the end of the table.\r
+ this.stat_numpages_visited--;\r
+\r
+ return(ret_row_count);\r
+ }\r
+}\r
+\r