0001: /*
0002:
0003: Derby - Class org.apache.derby.impl.store.access.btree.ControlRow
0004:
0005: Licensed to the Apache Software Foundation (ASF) under one or more
0006: contributor license agreements. See the NOTICE file distributed with
0007: this work for additional information regarding copyright ownership.
0008: The ASF licenses this file to you under the Apache License, Version 2.0
0009: (the "License"); you may not use this file except in compliance with
0010: the License. You may obtain a copy of the License at
0011:
0012: http://www.apache.org/licenses/LICENSE-2.0
0013:
0014: Unless required by applicable law or agreed to in writing, software
0015: distributed under the License is distributed on an "AS IS" BASIS,
0016: WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
0017: See the License for the specific language governing permissions and
0018: limitations under the License.
0019:
0020: */
0021:
0022: package org.apache.derby.impl.store.access.btree;
0023:
0024: import java.io.PrintStream;
0025:
0026: import org.apache.derby.iapi.services.monitor.Monitor;
0027: import org.apache.derby.iapi.services.sanity.SanityManager;
0028:
0029: import org.apache.derby.iapi.services.io.FormatIdUtil;
0030: import org.apache.derby.iapi.services.io.Storable;
0031: import org.apache.derby.iapi.services.io.TypedFormat;
0032:
0033: import org.apache.derby.iapi.error.StandardException;
0034:
0035: import org.apache.derby.iapi.store.access.conglomerate.LogicalUndo;
0036:
0037: import org.apache.derby.iapi.store.access.Qualifier;
0038: import org.apache.derby.iapi.store.access.RowUtil;
0039:
0040: import org.apache.derby.iapi.store.raw.AuxObject;
0041: import org.apache.derby.iapi.store.raw.FetchDescriptor;
0042: import org.apache.derby.iapi.store.raw.Page;
0043: import org.apache.derby.iapi.store.raw.ContainerHandle;
0044: import org.apache.derby.iapi.store.raw.RecordHandle;
0045:
0046: import org.apache.derby.iapi.types.DataValueDescriptor;
0047:
0048: import org.apache.derby.iapi.types.SQLLongint;
0049: import org.apache.derby.impl.store.access.StorableFormatId;
0050:
0051: import org.apache.derby.iapi.services.io.FormatableBitSet;
0052:
0053: import org.apache.derby.impl.store.access.conglomerate.ConglomerateUtil;
0054:
0055: /**
0056:
0057: Base class for leaf and branch control rows.
0058: <P>
0059: <B>Concurrency Notes</B>
0060: <P>
0061: All access through control rows is serialized by an exclusive latch on
0062: the page the control row is for. The page is latched when the control
0063: row is "gotten" (ControlRow#Get), and unlatched when the control row
0064: is released (ControlRow#release).
0065: <P>
0066: <B>To Do List</B>
0067: <UL>
0068: <LI> <I>[NOTE1]</I>
0069: The code is arranged to fault in fields from the row as necessary.
0070: many of the fields of a control row are rarely used (left sibling, parent).
0071: The accessors fault in the underlying column only when
0072: requested by allocating the appropriate object and calling fetchFromSlot and
0073: only fetching the requested field.
0074: <LI> <I>[NOTE2]</I>
0075: Currently, all the fields of the control row are stored as StorableU8s
0076: for simplicity. This is too few bits to hold the long page numbers, and
0077: too many to hold the version, level, and isRoot flag. Some consideration
0078: will have to be given to the appropriate storage format for these values.
0079: <LI> <I>[NOTE3]</I>
0080: The implementation relies on the existance of page "auxiliary" pointers
0081: which keep Object versions of the control row.
0082: <P>
0083: @see ControlRow#Get
0084: @see ControlRow#release
0085:
0086: **/
0087:
0088: public abstract class ControlRow implements AuxObject, TypedFormat {
0089: /**
0090: * Version indentifier of the control row within the page.
0091: * <p>
0092: * This is the format id of the control row. The format id is currently
0093: * one of either StoredFormatIds.ACCESS_BTREE_LEAFCONTROLROW_ID or
0094: * StoredFormatIds.ACCESS_BTREE_BRANCHCONTROLROW_ID.
0095: **/
0096: private StorableFormatId version = null;
0097:
0098: /**
0099: * Pointer to page which is "left" at the current level.
0100: * <p>
0101: * Currently all pages at a level are doubly linked. The leftmost page
0102: * in a level has a leftSiblingPageNumber ==
0103: * ContainerHandle.INVALID_PAGE_NUMBER. All key values on the page which
0104: * is left must precede the first key value on the current page.
0105: **/
0106: private SQLLongint leftSiblingPageNumber;
0107:
0108: /**
0109: * Pointer to page which is "right" at the current level.
0110: * <p>
0111: * Currently all pages at a level are doubly linked. The rightmost page
0112: * in a level has a rightSiblingPageNumber ==
0113: * ContainerHandle.INVALID_PAGE_NUMBER. All key values on the page which
0114: * is right of the current page must follow the last key value on the
0115: * current page.
0116: **/
0117: private SQLLongint rightSiblingPageNumber;
0118:
0119: /**
0120: * The parent page of the current page.
0121: * <p>
0122: * For consistency checking it is useful to maintain the parentPageNumber
0123: * field of the current page. The root page has a value of
0124: * ContainerHandle.INVALID_PAGE_NUMBER in it's parentPageNumber field.
0125: * <p>
0126: * RESOLVE (mikem) - we need to come up with some way to not maintain these,
0127: * maybe by providing a property on secondary index or a different 2nd
0128: * index.
0129: *
0130: **/
0131: private SQLLongint parentPageNumber; // for consistency checking
0132:
0133: /**
0134: * The level of the btree.
0135: * <p>
0136: * The leaf level of the btree is 0. The first branch level (parent level
0137: * of the leaf), is level 1. The height of the btree is (level + 1).
0138: * <p>
0139: * The smallest btree is a one page btree with only a leaf, and no branch
0140: * pages.
0141: **/
0142: private SQLLongint level;
0143:
0144: /**
0145: * Is this page the root of the btree?
0146: * <p>
0147: * Currently "1" if the page is the root page, else "0".
0148: * <p>
0149: * RESOLVE (mikem) When real datatype come about, this value should
0150: * probably be just a bit in some status word.
0151: **/
0152: private SQLLongint isRoot = null;
0153:
0154: /**
0155: * A copy of the Conglomerate that describes the owning conglom.
0156: * <p>
0157: * This information is used during logical undo to get the type information
0158: * so that rows can be compared and searched for. We may be able to get
0159: * away with a subset of the information stored in the conglomerate.
0160: * <p>
0161: * RESOLVE (mikem) - change this to only store the info on the root page.
0162: **/
0163: private BTree btree = null;
0164:
0165: /**
0166: * The page that this control row describes.
0167: **/
0168: protected Page page;
0169:
0170: /**
0171: * The page that this control row describes.
0172: **/
0173: protected DataValueDescriptor row[];
0174:
0175: /**
0176: * row used to replace fetchFieldFromSlot() calls.
0177: **/
0178: protected DataValueDescriptor[] scratch_row;
0179:
0180: /**
0181: * FetchDescriptor used to replace fetchFieldFromSlot() calls.
0182: **/
0183: protected FetchDescriptor fetchDesc;
0184:
0185: /**
0186: * In memory hint about whether to use the last_search_result hint during
0187: * search.
0188: **/
0189: transient protected boolean use_last_search_result_hint = false;
0190:
0191: /**
0192: * In memory hint about where to begin the binary search to find a key
0193: * on the the current control page.
0194: **/
0195: transient protected int last_search_result = 0;
0196:
0197: /**
0198: * Column number assignments for columns of the control row.
0199: * <p>
0200: * The control row is stored as the first row in a btree page. The row
0201: * is an array of columns. The Control row columns are the columns numbered
0202: * from ControlRow.CR_COLID_FIRST through ControlRow.CR_COLID_LAST. The
0203: * classes which implement the concrete derived classes of ControlRow may
0204: * add columns to the control row, but they must be added after the
0205: * ControlRow columns.
0206: **/
0207: protected static final int CR_COLID_FIRST = 0;
0208: protected static final int CR_VERSION_COLID = CR_COLID_FIRST + 0;
0209: protected static final int CR_LEFTSIB_COLID = CR_COLID_FIRST + 1;
0210: protected static final int CR_RIGHTSIB_COLID = CR_COLID_FIRST + 2;
0211: protected static final int CR_PARENT_COLID = CR_COLID_FIRST + 3;
0212: protected static final int CR_LEVEL_COLID = CR_COLID_FIRST + 4;
0213: protected static final int CR_ISROOT_COLID = CR_COLID_FIRST + 5;
0214: protected static final int CR_CONGLOM_COLID = CR_COLID_FIRST + 6;
0215: protected static final int CR_COLID_LAST = CR_CONGLOM_COLID;
0216: protected static final int CR_NCOLUMNS = CR_COLID_LAST + 1;
0217:
0218: /**
0219: * bit sets used to fetch single columns at a time.
0220: **/
0221: protected static final FormatableBitSet CR_VERSION_BITSET = new FormatableBitSet(
0222: CR_VERSION_COLID + 1);
0223: protected static final FormatableBitSet CR_LEFTSIB_BITSET = new FormatableBitSet(
0224: CR_LEFTSIB_COLID + 1);
0225: protected static final FormatableBitSet CR_RIGHTSIB_BITSET = new FormatableBitSet(
0226: CR_RIGHTSIB_COLID + 1);
0227: protected static final FormatableBitSet CR_PARENT_BITSET = new FormatableBitSet(
0228: CR_PARENT_COLID + 1);
0229: protected static final FormatableBitSet CR_LEVEL_BITSET = new FormatableBitSet(
0230: CR_LEVEL_COLID + 1);
0231: protected static final FormatableBitSet CR_ISROOT_BITSET = new FormatableBitSet(
0232: CR_ISROOT_COLID + 1);
0233: protected static final FormatableBitSet CR_CONGLOM_BITSET = new FormatableBitSet(
0234: CR_CONGLOM_COLID + 1);
0235:
0236: /**
0237: * Values passed in the flag argument to splitFor.
0238: **/
0239: /* row causing split would be last row on leaf page */
0240: public static final int SPLIT_FLAG_LAST_ON_PAGE = 0x000000001;
0241: /* row causing split would be last row in table */
0242: public static final int SPLIT_FLAG_LAST_IN_TABLE = 0x000000002;
0243: /* row causing split would be first row on page */
0244: public static final int SPLIT_FLAG_FIRST_ON_PAGE = 0x000000004;
0245: /* row causing split would be first row in table */
0246: public static final int SPLIT_FLAG_FIRST_IN_TABLE = 0x000000008;
0247:
0248: /**
0249: * The slot at which all control rows reside.
0250: **/
0251: protected static final int CR_SLOT = 0;
0252:
0253: /*
0254: ** Constructors of ControlRow
0255: */
0256:
0257: static {
0258: CR_VERSION_BITSET.set(CR_VERSION_COLID);
0259: CR_LEFTSIB_BITSET.set(CR_LEFTSIB_COLID);
0260: CR_RIGHTSIB_BITSET.set(CR_RIGHTSIB_COLID);
0261: CR_PARENT_BITSET.set(CR_PARENT_COLID);
0262: CR_LEVEL_BITSET.set(CR_LEVEL_COLID);
0263: CR_ISROOT_BITSET.set(CR_ISROOT_COLID);
0264: CR_CONGLOM_BITSET.set(CR_CONGLOM_COLID);
0265: }
0266:
0267: /**
0268: * No arg constructor.
0269: * <p>
0270: * GetControlRowForPage() will call this constructor when it uses the
0271: * monitor to create a control row dynamically given a given format id.
0272: **/
0273: protected ControlRow() {
0274: this .scratch_row = new DataValueDescriptor[getNumberOfControlRowColumns()];
0275:
0276: this .fetchDesc = new FetchDescriptor(this .scratch_row.length,
0277: (FormatableBitSet) null, (Qualifier[][]) null);
0278: }
0279:
0280: /**
0281: * Constructor for making a new control row as part of allocating a new
0282: * page. Fills in all the fields but does not write them anywhere.
0283: * <p>
0284: * <P>
0285: * Changes to this constructor will probably require changes to the
0286: * corresponding accessor(s).
0287: *
0288: * @param btree Static information about the btree.
0289: * @param page The page described by this control row.
0290: * @param parent The parent page of this page, "null" if this page is
0291: * root or if not maintaining parent links.
0292: * @param isRoot Is this page the root of the tree?
0293: *
0294: *
0295: * @exception StandardException Standard exception policy.
0296: **/
0297: protected ControlRow(OpenBTree btree, Page page, int level,
0298: ControlRow parent, boolean isRoot) throws StandardException {
0299: // The caller is expected to have latched the pages.
0300: if (SanityManager.DEBUG) {
0301: SanityManager.ASSERT(page.isLatched());
0302: SanityManager.ASSERT(parent == null
0303: || parent.page.isLatched());
0304: }
0305:
0306: // Maintain which page this control row describes.
0307: this .page = page;
0308:
0309: // Page numbers start out "invalid". Presumably the caller will
0310: // link the page into a page chain as one of its next steps.
0311: leftSiblingPageNumber = new SQLLongint(
0312: btree.container.INVALID_PAGE_NUMBER);
0313: rightSiblingPageNumber = new SQLLongint(
0314: btree.container.INVALID_PAGE_NUMBER);
0315:
0316: // Remember the parent if there is one and we're remembering parents.
0317: parentPageNumber = new SQLLongint(
0318: (parent == null ? btree.container.INVALID_PAGE_NUMBER
0319: : parent.page.getPageNumber()));
0320:
0321: // All pages start out not being root pages. The caller will setIsRoot
0322: // if this is going to be a root page. Zero means false - see
0323: // getIsRoot/setIsRoot.
0324: this .isRoot = new SQLLongint(isRoot ? 1 : 0);
0325:
0326: // set the rest of the state, as passed in.
0327: this .level = new SQLLongint(level);
0328: this .version = new StorableFormatId(getTypeFormatId());
0329:
0330: // If it is a root page then store the real btree conglomerate, if it
0331: // is not a root page then set up an "empty" btree conglomerate which
0332: // will be stored as "null".
0333: this .btree = (isRoot ? btree.getConglomerate()
0334: : (BTree) Monitor.newInstanceFromIdentifier(btree
0335: .getConglomerate().getTypeFormatId()));
0336:
0337: // Initialize the object array to be used for interacting with raw
0338: // store to insert, fetch, and update the control row.
0339: this .row = new DataValueDescriptor[getNumberOfControlRowColumns()];
0340: this .row[CR_VERSION_COLID] = this .version;
0341: this .row[CR_LEFTSIB_COLID] = this .leftSiblingPageNumber;
0342: this .row[CR_RIGHTSIB_COLID] = this .rightSiblingPageNumber;
0343: this .row[CR_PARENT_COLID] = this .parentPageNumber;
0344: this .row[CR_LEVEL_COLID] = this .level;
0345: this .row[CR_ISROOT_COLID] = this .isRoot;
0346: this .row[CR_CONGLOM_COLID] = this .btree;
0347:
0348: // Make the control row the aux object for the page so control row
0349: // getters end up with the same row.
0350: page.setAuxObject(this );
0351: }
0352:
0353: /**
0354: * Constructor for making a control row for an existing page.
0355: * <p>
0356: * Not all the fields are filled in; their values will get faulted in from
0357: * the page as necessary.
0358: * <p>
0359: * Classes which extend ControlRow must delegate to this constructor
0360: * and may want to override it as well.
0361: * Changes to this constructor will probably require changes to the
0362: * corresponding accessor(s).
0363: *
0364: * @param container Open container
0365: * @param page The page described by this control row.
0366: *
0367: * @exception StandardException Standard exception policy.
0368: **/
0369: protected ControlRow(ContainerHandle container, Page page)
0370: throws StandardException {
0371: System.out.println("ControlRow construct 2.");
0372:
0373: // The caller is expected to have latched the pages.
0374: if (SanityManager.DEBUG)
0375: SanityManager.ASSERT(page.isLatched());
0376:
0377: // Remember the page.
0378: this .page = page;
0379:
0380: // The rest of the fields are left null; they'll get faulted
0381: // in if/when necessary. See the accessors.
0382: }
0383:
0384: /* Private/Protected methods of ControlRow: */
0385:
0386: /**
0387: * Get version of the control row.
0388: * <p>
0389: * Returns the version of the control row, faulting it in from the page
0390: * if necessary.
0391: *
0392: * @return version of the control row.
0393: *
0394: * @exception StandardException Standard exception policy.
0395: **/
0396: protected int getVersion() throws StandardException {
0397: if (this .version == null) {
0398: // Fault in the version.
0399: this .version = new StorableFormatId();
0400:
0401: scratch_row[CR_VERSION_COLID] = this .version;
0402:
0403: fetchDesc.setValidColumns(CR_VERSION_BITSET);
0404:
0405: this .page.fetchFromSlot((RecordHandle) null, CR_SLOT,
0406: scratch_row, fetchDesc, false);
0407: }
0408: return this .version.getValue();
0409: }
0410:
0411: /**
0412: * Set version of the control row.
0413: * <p>
0414: * Sets the version of the control row. Updates both the in-memory
0415: * control row and the disk copy.
0416: *
0417: * @exception StandardException Standard exception policy.
0418: **/
0419: protected void setVersion(int version) throws StandardException {
0420: // Store the field.
0421: if (this .version == null)
0422: this .version = new StorableFormatId();
0423: this .version.setValue(version);
0424:
0425: // Write the field through to the underlying row.
0426: this .page.updateFieldAtSlot(CR_SLOT, CR_VERSION_COLID,
0427: this .version, null);
0428: }
0429:
0430: /**
0431: * Get the control row for this page's left sibling, or null if there is no
0432: * left sibling (which probably means it's the leftmost page at its level).
0433: * Since right-to-left traversal of an index level is deadlock-prone, this
0434: * method will only get get the left sibling if it can latch it without
0435: * waiting.
0436: *
0437: * @exception WaitError if the latch request would have had to wait.
0438: *
0439: * @exception StandardException Standard exception policy.
0440: **/
0441: public ControlRow getLeftSibling(OpenBTree btree)
0442: throws StandardException, WaitError {
0443: ControlRow cr;
0444:
0445: long pageno = this .getleftSiblingPageNumber();
0446:
0447: // Is there a left sibling?
0448: if (pageno == ContainerHandle.INVALID_PAGE_NUMBER)
0449: return null;
0450:
0451: // Try to get the control row without waiting
0452: cr = ControlRow.GetNoWait(btree, pageno);
0453: if (cr == null)
0454: throw new WaitError();
0455:
0456: return cr;
0457: }
0458:
0459: protected void setLeftSibling(ControlRow leftsib)
0460: throws StandardException {
0461: long left_sib_pageno = (leftsib == null ? ContainerHandle.INVALID_PAGE_NUMBER
0462: : leftsib.page.getPageNumber());
0463:
0464: // Store the field.
0465: if (leftSiblingPageNumber == null)
0466: leftSiblingPageNumber = new SQLLongint(left_sib_pageno);
0467: else
0468: this .leftSiblingPageNumber.setValue(left_sib_pageno);
0469:
0470: // Write the field through to the underlying row
0471: try {
0472: this .page.updateFieldAtSlot(CR_SLOT, CR_LEFTSIB_COLID,
0473: this .leftSiblingPageNumber, null);
0474: } catch (StandardException se) {
0475: // Since this is an update of a fixed length field it should
0476: // never fail, but it has happened enough that an assert helps
0477: // with debugging.
0478: if (SanityManager.DEBUG) {
0479: SanityManager
0480: .THROWASSERT("setLeftSibling got an exception: "
0481: + se
0482: + "control_row = "
0483: + this
0484: + "trying to update field number "
0485: + CR_LEFTSIB_COLID
0486: + "to new value "
0487: + this .leftSiblingPageNumber);
0488: }
0489: throw (se);
0490: }
0491: }
0492:
0493: /**
0494: Return the control row for this page's right sibling. Unlike getting
0495: the left sibling, it's ok to wait for the right sibling latch since
0496: left-to-right is the deadlock-free ordering.
0497:
0498: @exception StandardException Standard exception policy.
0499: **/
0500: protected ControlRow getRightSibling(OpenBTree open_btree)
0501: throws StandardException {
0502: long pageno = this .getrightSiblingPageNumber();
0503:
0504: // Return the control row for the page.
0505: if (pageno == ContainerHandle.INVALID_PAGE_NUMBER)
0506: return null;
0507: else
0508: return ControlRow.Get(open_btree, pageno);
0509: }
0510:
0511: // This method will have to update the row.
0512: protected void setRightSibling(ControlRow rightsib)
0513: throws StandardException {
0514: long right_sib_pageno = (rightsib == null ? ContainerHandle.INVALID_PAGE_NUMBER
0515: : rightsib.page.getPageNumber());
0516:
0517: // Store the field.
0518: if (rightSiblingPageNumber == null)
0519: rightSiblingPageNumber = new SQLLongint(right_sib_pageno);
0520: else
0521: this .rightSiblingPageNumber.setValue(right_sib_pageno);
0522:
0523: // Write the field through to the underlying row
0524: try {
0525: this .page.updateFieldAtSlot(CR_SLOT, CR_RIGHTSIB_COLID,
0526: this .rightSiblingPageNumber, null);
0527: } catch (StandardException se) {
0528: // Since this is an update of a fixed length field it should
0529: // never fail, but it has happened enough that an assert helps
0530: // with debugging.
0531:
0532: if (SanityManager.DEBUG) {
0533: SanityManager
0534: .THROWASSERT("setRightSibling got an exception: "
0535: + se
0536: + "control_row = "
0537: + this
0538: + "trying to update field number "
0539: + CR_RIGHTSIB_COLID
0540: + "to new value "
0541: + this .rightSiblingPageNumber);
0542: }
0543: throw (se);
0544: }
0545: }
0546:
0547: /**
0548: Get the page number of the left sibling. Fault it's value in if it
0549: hasn't been yet.
0550:
0551: @exception StandardException Standard exception policy.
0552: **/
0553: public long getleftSiblingPageNumber() throws StandardException {
0554: if (this .leftSiblingPageNumber == null) {
0555: // Fault in the page number.
0556: this .leftSiblingPageNumber = new SQLLongint();
0557:
0558: if (SanityManager.DEBUG)
0559: SanityManager.ASSERT(scratch_row != null);
0560:
0561: scratch_row[CR_LEFTSIB_COLID] = this .leftSiblingPageNumber;
0562:
0563: fetchDesc.setValidColumns(CR_LEFTSIB_BITSET);
0564: this .page.fetchFromSlot((RecordHandle) null, CR_SLOT,
0565: scratch_row, fetchDesc, false);
0566:
0567: }
0568:
0569: return (leftSiblingPageNumber.getLong());
0570: }
0571:
0572: /**
0573: Get the page number of the right sibling. Fault it's value in if it
0574: hasn't been yet.
0575:
0576: @exception StandardException Standard exception policy.
0577: **/
0578: protected long getrightSiblingPageNumber() throws StandardException {
0579: if (this .rightSiblingPageNumber == null) {
0580: // Fault in the page number.
0581: this .rightSiblingPageNumber = new SQLLongint();
0582:
0583: scratch_row[CR_RIGHTSIB_COLID] = this .rightSiblingPageNumber;
0584:
0585: fetchDesc.setValidColumns(CR_RIGHTSIB_BITSET);
0586: this .page.fetchFromSlot((RecordHandle) null, CR_SLOT,
0587: scratch_row, fetchDesc, false);
0588: }
0589:
0590: return (rightSiblingPageNumber.getLong());
0591: }
0592:
0593: /**
0594: Get the page number of the parent, if it's being maintained.
0595: Note that there is intentionally no way to get the control
0596: row for the parent page - the b-tree code NEVER traverses
0597: up the tree, even in consistency checks.
0598:
0599: @exception StandardException Standard exception policy.
0600: **/
0601: protected long getParentPageNumber() throws StandardException {
0602: if (this .parentPageNumber == null) {
0603: // Fault in the page number.
0604: this .parentPageNumber = new SQLLongint();
0605:
0606: scratch_row[CR_PARENT_COLID] = this .parentPageNumber;
0607:
0608: fetchDesc.setValidColumns(CR_PARENT_BITSET);
0609: this .page.fetchFromSlot((RecordHandle) null, CR_SLOT,
0610: scratch_row, fetchDesc, false);
0611: }
0612:
0613: // See NOTE3 about converting from int to long.
0614: long pageno = parentPageNumber.getLong();
0615: return pageno;
0616: }
0617:
0618: void setParent(long parent) throws StandardException {
0619: // Store the field.
0620: if (parentPageNumber == null)
0621: parentPageNumber = new SQLLongint();
0622: this .parentPageNumber.setValue(parent);
0623:
0624: // Write the field through to the underlying row
0625: try {
0626: this .page.updateFieldAtSlot(CR_SLOT, CR_PARENT_COLID,
0627: this .parentPageNumber, null);
0628: } catch (StandardException se) {
0629: // Since this is an update of a fixed length field it should
0630: // never fail, but it has happened enough that an assert helps
0631: // with debugging.
0632:
0633: if (SanityManager.DEBUG) {
0634: SanityManager
0635: .THROWASSERT("setParent got an exception: "
0636: + se + "control_row = " + this
0637: + "trying to update field number "
0638: + CR_PARENT_COLID + "to new value "
0639: + this .parentPageNumber);
0640: }
0641: throw (se);
0642: }
0643:
0644: return;
0645: }
0646:
0647: protected int getLevel() throws StandardException {
0648: if (this .level == null) {
0649: // Fault in the level
0650: this .level = new SQLLongint();
0651:
0652: scratch_row[CR_LEVEL_COLID] = this .level;
0653:
0654: fetchDesc.setValidColumns(CR_LEVEL_BITSET);
0655: this .page.fetchFromSlot((RecordHandle) null, CR_SLOT,
0656: scratch_row, fetchDesc, false);
0657: }
0658:
0659: return ((int) this .level.getLong());
0660: }
0661:
0662: protected void setLevel(int newlevel) throws StandardException {
0663: // Store the field.
0664: if (this .level == null)
0665: this .level = new SQLLongint();
0666: this .level.setValue((long) newlevel);
0667:
0668: // Write the field through to the underlying row.
0669: this .page.updateFieldAtSlot(CR_SLOT, CR_LEVEL_COLID,
0670: this .level, null);
0671: }
0672:
0673: protected boolean getIsRoot() throws StandardException {
0674: // convert 1 to true, 0 to false;
0675:
0676: if (this .isRoot == null) {
0677: // Fault in the level
0678: this .isRoot = new SQLLongint();
0679:
0680: scratch_row[CR_ISROOT_COLID] = this .isRoot;
0681:
0682: fetchDesc.setValidColumns(CR_ISROOT_BITSET);
0683: this .page.fetchFromSlot((RecordHandle) null, CR_SLOT,
0684: scratch_row, fetchDesc, false);
0685: }
0686:
0687: return ((this .isRoot.getLong() == 1));
0688: }
0689:
0690: protected void setIsRoot(boolean isRoot) throws StandardException {
0691: // RESOLVE (mmm) - need to store more efficiently //
0692:
0693: // Store the field.
0694: if (this .isRoot == null)
0695: this .isRoot = new SQLLongint();
0696:
0697: this .isRoot.setValue((isRoot) ? 1 : 0);
0698:
0699: // Write the field through to the underlying row.
0700: this .page.updateFieldAtSlot(CR_SLOT, CR_ISROOT_COLID,
0701: this .isRoot, null);
0702: }
0703:
0704: /**
0705: * Get format id information for row on page.
0706: * <p>
0707: * Returns the format id information for a row on the page. faulting it
0708: * in from the page if necessary.
0709: *
0710: * @return format id of a row on the page.
0711: *
0712: * @exception StandardException Standard exception policy.
0713: **/
0714: public BTree getConglom(int format_id) throws StandardException {
0715:
0716: if (SanityManager.DEBUG) {
0717: // this call is only valid on root pages. If called on non
0718: // root pages it will return a "null" conglom object.
0719: SanityManager
0720: .ASSERT((this .page.getPageNumber() == BTree.ROOTPAGEID)
0721: && getIsRoot());
0722: }
0723:
0724: if (this .btree == null) {
0725: // use format id to create empty instance of Conglomerate class
0726: this .btree = (BTree) Monitor
0727: .newInstanceFromIdentifier(format_id);
0728:
0729: scratch_row[CR_CONGLOM_COLID] = this .btree;
0730:
0731: fetchDesc.setValidColumns(CR_CONGLOM_BITSET);
0732: this .page.fetchFromSlot((RecordHandle) null, CR_SLOT,
0733: scratch_row, fetchDesc, false);
0734: }
0735: return this .btree;
0736: }
0737:
0738: /**
0739: * Set the conglomerate field in the btree.
0740: * <p>
0741: * Sets the btree field of the control row. Updates just the disk copy.
0742: *
0743: * @exception StandardException Standard exception policy.
0744: **/
0745: private void setConglom(BTree btree) throws StandardException {
0746: // Store the field. Delay faulting value into object until getConlgom()
0747: // call, which in general only happens during recovery.
0748:
0749: // Write the field through to the underlying row.
0750: this .page.updateFieldAtSlot(CR_SLOT, CR_CONGLOM_COLID, btree,
0751: null);
0752: }
0753:
0754: /*
0755: ** Methods for getting control rows from pages.
0756: */
0757:
0758: /**
0759: Get the control row from the given page in the b-tree.
0760: The returned control row will be of the correct type
0761: for the page (i.e., either a LeafControlRow or a
0762: BranchControlRow).
0763:
0764: @exception StandardException Standard exception policy.
0765: **/
0766: public static ControlRow Get(OpenBTree open_btree, long pageNumber)
0767: throws StandardException {
0768: return (ControlRow.Get(open_btree.container, pageNumber));
0769: }
0770:
0771: public static ControlRow Get(ContainerHandle container,
0772: long pageNumber) throws StandardException {
0773: if (SanityManager.DEBUG) {
0774: SanityManager
0775: .ASSERT(container != null,
0776: "ControlRow.Get() is being called on a closed container.");
0777: }
0778:
0779: // Get the page, waiting if necessary. The page is returned latched.
0780: Page page = container.getPage(pageNumber);
0781:
0782: if (SanityManager.DEBUG) {
0783: if (page == null)
0784: SanityManager.THROWASSERT("No page at pagenumber: "
0785: + pageNumber + "; ContainerHandle = "
0786: + container);
0787: }
0788:
0789: // Return the corresponding control row.
0790: return GetControlRowForPage(container, page);
0791: }
0792:
0793: /**
0794: Get the control row for the given page if the latch on the
0795: page can be obtained without waiting, else return null.
0796:
0797: @exception StandardException Standard exception policy.
0798: **/
0799: public static ControlRow GetNoWait(OpenBTree open_btree,
0800: long pageNumber) throws StandardException {
0801: // Try to get the page without waiting. If we would have
0802: // to wait, return null.
0803: Page page = open_btree.container.getUserPageNoWait(pageNumber);
0804: if (page == null)
0805: return null;
0806:
0807: // Got the page without waiting. Return the corresponding
0808: // control row.
0809: return GetControlRowForPage(open_btree.container, page);
0810: }
0811:
0812: protected static ControlRow GetControlRowForPage(
0813: ContainerHandle container, Page page)
0814: throws StandardException {
0815: ControlRow cr = null;
0816:
0817: // See if the control row is still cached with the page
0818: // If so, just use the cached control row.
0819: AuxObject auxobject = page.getAuxObject();
0820: if (auxobject != null)
0821: return (ControlRow) auxobject;
0822:
0823: if (SanityManager.DEBUG)
0824: SanityManager.ASSERT(page.recordCount() >= 1);
0825:
0826: // No cached control row, so create a new one.
0827:
0828: // Use the version field to determine the type of the row to
0829: // create. This routine depends on the version field being the same
0830: // number column in all control rows.
0831:
0832: StorableFormatId version = new StorableFormatId();
0833:
0834: DataValueDescriptor[] version_ret = new DataValueDescriptor[1];
0835:
0836: version_ret[0] = version;
0837:
0838: // TODO (mikem) - get rid of this new.
0839:
0840: page.fetchFromSlot((RecordHandle) null, CR_SLOT, version_ret,
0841: new FetchDescriptor(1, CR_VERSION_BITSET,
0842: (Qualifier[][]) null), false);
0843:
0844: // use format id to create empty instance of right Conglomerate class
0845: cr = (ControlRow) Monitor.newInstanceFromIdentifier(version
0846: .getValue());
0847: cr.page = page;
0848:
0849: // call page specific initialization.
0850: cr.ControlRowInit();
0851:
0852: // cache this Control row with the page in the cache.
0853: page.setAuxObject(cr);
0854:
0855: return (cr);
0856: }
0857:
0858: /**
0859: Release this control row's resources.
0860: **/
0861: public void release() {
0862: if (SanityManager.DEBUG)
0863: SanityManager.ASSERT(page != null);
0864:
0865: if (page != null)
0866: page.unlatch();
0867:
0868: // It might be nice to set the page object to null, but
0869: // since there might be multiple control rows on this
0870: // page, we'd have to maintain a use count. Rather than
0871: // doing that we'll let the garbage collector earn its
0872: // keep. We are also expecting that the raw store will
0873: // throw errors if we attempt to use an unlatched page.
0874: }
0875:
0876: /**
0877: Search this index page.
0878: <P>
0879: This method is very performance sensitive. It is the intention that no
0880: object allocations occur during the execution of this method.
0881: <P>
0882: This method performs a binary search on the page and finds the entry i on
0883: the page such that entry[i] <= key < entry[i+1]. The result of the search
0884: is filled into the passed in params structure.
0885:
0886: @param params the parameters of the search
0887:
0888: @exception StandardException could be thrown by underlying raw store
0889: operations.
0890:
0891: @see SearchParameters
0892: **/
0893: protected void searchForEntry(SearchParameters params)
0894: throws StandardException {
0895: if (SanityManager.DEBUG) {
0896: // System.out.println("searchForEntry() enter: params:" + params);
0897: // System.out.println("searchForEntry() enter: this:" + this);
0898: // System.out.println("searchForEntry() enter: this page:" + debugPage(params.btree));
0899: }
0900:
0901: // leftrange and rightrange indicates the range of slots to search.
0902: // The range starts as all the slots on the page not including slot
0903: // 0 which is the control row.
0904: int leftrange = 1;
0905: int rightrange = page.recordCount() - 1;
0906:
0907: // leftslot and rightslot if non-zero, mean that the key has been
0908: // compared to the row at that slot. If non-zero the key must be
0909: // greater than the key at leftslot and the key must be lest than
0910: // the key at rightslot.
0911: int leftslot = 0;
0912: int rightslot = rightrange + 1;
0913:
0914: int midslot;
0915: int compare_ret;
0916:
0917: // search until you either exactly find the key, or you have
0918: // compared 2 adjacent rows and found the value must exist between
0919: // the 2.
0920:
0921: if (this .use_last_search_result_hint) {
0922: // make sure to set midslot to point to somwhere in the legal range.
0923: midslot = ((this .last_search_result == 0) ? 1
0924: : this .last_search_result);
0925:
0926: if (midslot > rightrange)
0927: midslot = rightrange;
0928: } else {
0929: // if we don't think we have a good hint where to start the search
0930: // just go to the middle.
0931: midslot = (leftrange + rightrange) / 2;
0932: }
0933:
0934: if (SanityManager.DEBUG) {
0935: if ((leftslot != (rightslot - 1))
0936: && !(midslot >= leftrange && midslot <= rightrange)) {
0937: SanityManager.THROWASSERT("midslot = " + midslot
0938: + ";leftrange = " + leftrange
0939: + ";rightrange = " + rightrange);
0940: }
0941: }
0942:
0943: while (leftslot != (rightslot - 1)) {
0944: // Compare the index row to the key.
0945: compare_ret = CompareIndexRowFromPageToKey(this , midslot,
0946: params.template, params.searchKey, params.btree
0947: .getConglomerate().nUniqueColumns,
0948: params.partial_key_match_op, params.btree
0949: .getConglomerate().ascDescInfo);
0950:
0951: if (compare_ret == 0) {
0952: // Found exact match
0953: params.resultSlot = midslot;
0954: params.resultExact = true;
0955:
0956: // update the hints based on result of the search.
0957: use_last_search_result_hint = (midslot == this .last_search_result) ? true
0958: : false;
0959: this .last_search_result = midslot;
0960:
0961: return;
0962: } else if (compare_ret > 0) {
0963: // key falls to the left of midslot
0964: rightslot = midslot;
0965: rightrange = midslot - 1;
0966: } else {
0967: // key falls to the right of midslot
0968: leftslot = midslot;
0969: leftrange = midslot + 1;
0970: }
0971:
0972: midslot = (leftrange + rightrange) / 2;
0973: //midslot = (leftrange + rightrange) >> 1;
0974: }
0975:
0976: // update the hints based on result of the search.
0977: this .use_last_search_result_hint = (leftslot == this .last_search_result);
0978: this .last_search_result = leftslot;
0979:
0980: // no exact match found, leftslot will point at the slot on the
0981: // page just before where the row should be inserted. In the case
0982: // where the key is before rows on the page then leftslot will be
0983: // 0 (an empty page is a special case of this).
0984: if (SanityManager.DEBUG) {
0985: if (leftslot != rightslot - 1)
0986: SanityManager.THROWASSERT("leftslot = " + leftslot
0987: + "; rightslot = " + rightslot);
0988: }
0989:
0990: params.resultSlot = leftslot;
0991: params.resultExact = false;
0992:
0993: if (SanityManager.DEBUG) {
0994: // System.out.println("searchForEntry() exit: params:" + params);
0995: }
0996:
0997: return;
0998: }
0999:
1000: protected void searchForEntryBackward(SearchParameters params)
1001: throws StandardException {
1002: if (SanityManager.DEBUG) {
1003: // System.out.println("searchForEntry() enter: params:" + params);
1004: // System.out.println("searchForEntry() enter: this:" + this);
1005: // System.out.println("searchForEntry() enter: this page:" + debugPage(params.btree));
1006: }
1007:
1008: // leftrange and rightrange indicates the range of slots to search.
1009: // The range starts as all the slots on the page not including slot
1010: // 0 which is the control row.
1011: int leftrange = 1;
1012: int rightrange = page.recordCount() - 1;
1013:
1014: // leftslot and rightslot if non-zero, mean that the key has been
1015: // compared to the row at that slot. If non-zero the key must be
1016: // greater than the key at leftslot and the key must be lest than
1017: // the key at rightslot.
1018: int leftslot = 0;
1019: int rightslot = rightrange + 1;
1020:
1021: int midslot;
1022: int compare_ret;
1023:
1024: // search until you either exactly find the key, or you have
1025: // compared 2 adjacent rows and found the value must exist between
1026: // the 2.
1027:
1028: if (this .use_last_search_result_hint) {
1029: // make sure to set midslot to point to somwhere in the legal range.
1030: midslot = ((this .last_search_result == 0) ? 1
1031: : this .last_search_result);
1032:
1033: if (midslot > rightrange)
1034: midslot = rightrange;
1035: } else {
1036: // if we don't think we have a good hint where to start the search
1037: // just go to the middle.
1038: midslot = (leftrange + rightrange) / 2;
1039: }
1040:
1041: if (SanityManager.DEBUG) {
1042: if ((leftslot != (rightslot - 1))
1043: && !(midslot >= leftrange && midslot <= rightrange)) {
1044: SanityManager.THROWASSERT("midslot = " + midslot
1045: + ";leftrange = " + leftrange
1046: + ";rightrange = " + rightrange);
1047: }
1048: }
1049:
1050: while (leftslot != (rightslot - 1)) {
1051: // Compare the index row to the key.
1052: compare_ret = CompareIndexRowFromPageToKey(this , midslot,
1053: params.template, params.searchKey, params.btree
1054: .getConglomerate().nUniqueColumns,
1055: params.partial_key_match_op, params.btree
1056: .getConglomerate().ascDescInfo);
1057:
1058: if (compare_ret == 0) {
1059: // Found exact match
1060: params.resultSlot = midslot;
1061: params.resultExact = true;
1062:
1063: // update the hints based on result of the search.
1064: use_last_search_result_hint = (midslot == this .last_search_result) ? true
1065: : false;
1066: this .last_search_result = midslot;
1067:
1068: return;
1069: } else if (compare_ret > 0) {
1070: // key falls to the left of midslot
1071: rightslot = midslot;
1072: rightrange = midslot - 1;
1073: } else {
1074: // key falls to the right of midslot
1075: leftslot = midslot;
1076: leftrange = midslot + 1;
1077: }
1078:
1079: midslot = (leftrange + rightrange) / 2;
1080: //midslot = (leftrange + rightrange) >> 1;
1081: }
1082:
1083: // update the hints based on result of the search.
1084: this .use_last_search_result_hint = (leftslot == this .last_search_result);
1085: this .last_search_result = leftslot;
1086:
1087: // no exact match found, leftslot will point at the slot on the
1088: // page just before where the row should be inserted. In the case
1089: // where the key is before rows on the page then leftslot will be
1090: // 0 (an empty page is a special case of this).
1091: if (SanityManager.DEBUG) {
1092: if (leftslot != rightslot - 1)
1093: SanityManager.THROWASSERT("leftslot = " + leftslot
1094: + "; rightslot = " + rightslot);
1095: }
1096:
1097: params.resultSlot = leftslot;
1098: params.resultExact = false;
1099:
1100: if (SanityManager.DEBUG) {
1101: // System.out.println("searchForEntry() exit: params:" + params);
1102: }
1103:
1104: return;
1105: }
1106:
1107: /**
1108: Compare two orderable rows, considering nCompareCols, and return -1, 0, or 1
1109: depending on whether the first row (indexrow) is less than, equal to, or
1110: greater than the second (key). The key may have fewer columns present
1111: than nCompareCols.
1112:
1113: In such a case, if all the columns of the partial key match all of the
1114: corresponding columns in the index row, then the value passed in in
1115: partialKeyOrder is returned. The caller should pass in partialKeyOrder=1
1116: if the index rows which match a partial key should be considered to be
1117: greater than the partial key, and -1 if they should be considered to be
1118: less.
1119:
1120: This routine only reads objects off the page if it needs them, so if a
1121: multi-part key differs in the first column the subsequent columns are not
1122: read.
1123:
1124: @param indexpage Controlrow of page to get target row from.
1125: @param slot Slot to get control row from.
1126: @param indexrow template of the target row (the row in the index).
1127: @param key the (possibly partial) search key.
1128: @param nCompareCols the number of columns to compare.
1129: @param partialKeyOrder what to return on a partial key match.
1130: @param ascOrDesc column sort order information
1131: @throws StandardException if lower levels have a problem.
1132:
1133: @exception StandardException Standard exception policy.
1134: **/
1135: public static int CompareIndexRowFromPageToKey(
1136: ControlRow indexpage, int slot,
1137: DataValueDescriptor[] indexrow, DataValueDescriptor[] key,
1138: int nCompareCols, int partialKeyOrder, boolean[] ascOrDesc)
1139: throws StandardException {
1140: int compare_result;
1141:
1142: // Get the actual number of key columns present
1143: // in the partial key.
1144: int partialKeyCols = key.length;
1145:
1146: // Fetch entire index row from page.
1147: // RESOLVE (mikem) - it may be more efficient to fetch just the
1148: // columns you need, but there is overhead currently in raw
1149: // store, since to get to the n'th column you have to walk
1150: // through the preceding n-1 columns.
1151: indexpage.page.fetchFromSlot((RecordHandle) null, slot,
1152: indexrow, (FetchDescriptor) null, true);
1153:
1154: // Compare corresponding columns in the index row and the key.
1155: for (int i = 0; i < nCompareCols; i++) {
1156: // See if we have run out of partial key columns.
1157: if (i >= partialKeyCols) {
1158: // All the columns of the partial key match, and
1159: // there are more columns in the index row. We
1160: // want to return -1 or 1, depending on whether the
1161: // caller wants to direct the search to the beginning
1162: // of this key range or the beginning of the next
1163: // one. If the caller passes in -1, the index row
1164: // will appear less than the partial key, sending the
1165: // search to the next range ("to the right"). If the
1166: // caller passes in 1, the index row will appear
1167: // to be greater than the search key, sending the search
1168: // to the beginning of the range ("to the left").
1169: return partialKeyOrder;
1170: }
1171:
1172: // Get the corresponding columns to compare
1173:
1174: // Orderable indexcol = (Orderable) indexrow[i];
1175: // Orderable keycol = (Orderable) key[i];
1176:
1177: // Compare them.
1178: // int r = indexcol.compare(keycol);
1179:
1180: int r = indexrow[i].compare(key[i]);
1181:
1182: // If the columns don't compare equal, we're done.
1183: // Return the sense of the comparison.
1184: if (r != 0) {
1185: //coulmns could have been sorted in ascending or descending
1186: //order. depending on ascending/descending order search
1187: //direction will change.
1188:
1189: if (ascOrDesc[i]) // true - Ascending order
1190: return r;
1191: else
1192: return -r;
1193: }
1194: }
1195:
1196: // We made it through all the columns, and they must have
1197: // all compared equal. So return that the rows compare equal.
1198: return 0;
1199: }
1200:
1201: public static int CompareIndexRowToKey(
1202: DataValueDescriptor[] indexrow, DataValueDescriptor[] key,
1203: int nCompareCols, int partialKeyOrder, boolean[] ascOrDesc)
1204: throws StandardException {
1205: // Get the actual number of key columns present
1206: // in the partial key.
1207: int partialKeyCols = key.length;
1208:
1209: // Compare corresponding columns in the index row and the key.
1210: for (int i = 0; i < nCompareCols; i++) {
1211: // See if we have run out of partial key columns.
1212: if (i >= partialKeyCols) {
1213: // All the columns of the partial key match, and
1214: // there are more columns in the index row. We
1215: // want to return -1 or 1, depending on whether the
1216: // caller wants to direct the search to the beginning
1217: // of this key range or the beginning of the next
1218: // one. If the caller passes in -1, the index row
1219: // will appear less than the partial key, sending the
1220: // search to the next range ("to the right"). If the
1221: // caller passes in 1, the index row will appear
1222: // to be greater than the search key, sending the search
1223: // to the beginning of the range ("to the left").
1224: return partialKeyOrder;
1225: }
1226:
1227: // Get the corresponding columns to compare
1228: DataValueDescriptor indexcol = indexrow[i];
1229: DataValueDescriptor keycol = key[i];
1230:
1231: // Compare them.
1232: int r = indexcol.compare(keycol);
1233:
1234: // If the columns don't compare equal, we're done.
1235: // Return the sense of the comparison.
1236: if (r != 0) {
1237: if (ascOrDesc[i]) // true - column in ascending order
1238: return r;
1239: else
1240: return -r;
1241: }
1242: }
1243:
1244: // We made it through all the columns, and they must have
1245: // all compared equal. So return that the rows compare equal.
1246: return 0;
1247: }
1248:
1249: /**
1250: ** Perform consistency checks which are common to all
1251: ** pages that derive from ControlRow (both leaf and
1252: ** branch pages). The checks are:
1253: ** <menu>
1254: ** <li> This page thinks the parent argument is actually
1255: ** its parent.
1256: ** <li> The level of this page is 1 less than the level of
1257: ** the parent.
1258: ** <li> All the rows on the page are in order.
1259: ** <li> Both left and right siblings, if they exist, are at
1260: ** the same level of this page.
1261: ** <li> This page is the left sibling of its right sibling,
1262: ** and it's the right sibling of its left sibling.
1263: ** <li> The last row on the left sibling is < the first
1264: ** row on this page.
1265: ** <li> The first row on the right sibling is > than the
1266: ** the last row on this page.
1267: ** </menu>
1268: ** Note that these last two are really only true if there
1269: ** are never duplicate keys.
1270:
1271: @exception StandardException Standard exception policy.
1272: **/
1273: protected void checkGeneric(OpenBTree btree, ControlRow parent,
1274: boolean check_other_pages) throws StandardException {
1275: if (SanityManager.DEBUG) {
1276: SanityManager.ASSERT(this .page.recordCount() >= 1);
1277: SanityManager.ASSERT(!this .page.isDeletedAtSlot(0));
1278:
1279: // Make sure that we think we're a child of the parent.
1280: if (((parent != null) && (parent.page.getPageNumber() != this
1281: .getParentPageNumber())))
1282: SanityManager.THROWASSERT(this + " not child of "
1283: + parent);
1284:
1285: // Check this page's level.
1286: if (((parent != null) && (parent.getLevel() != this
1287: .getLevel() + 1)))
1288: SanityManager.THROWASSERT(this
1289: + " at wrong level when compared to parent:"
1290: + parent);
1291:
1292: // Check rows are in order.
1293: checkRowOrder(btree, parent);
1294:
1295: // Check siblings.
1296: if (check_other_pages)
1297: checkSiblings(btree);
1298: }
1299: }
1300:
1301: /**
1302: ** Check that all rows on the page are in order. This
1303: ** means that each key is > than the previous key.
1304:
1305: @exception StandardException Standard exception policy.
1306: **/
1307: protected boolean checkRowOrder(OpenBTree btree, ControlRow parent)
1308: throws StandardException {
1309: if (SanityManager.DEBUG) {
1310: RecordHandle lesser_handle = null;
1311: RecordHandle greater_handle = null;
1312: DataValueDescriptor[] lesser = getRowTemplate(btree);
1313: DataValueDescriptor[] greater = getRowTemplate(btree);
1314: boolean is_consistent = true;
1315:
1316: int numslots = page.recordCount();
1317: for (int i = ControlRow.CR_SLOT + 1; (i + 1) < numslots; i++) {
1318: lesser_handle = page.fetchFromSlot((RecordHandle) null,
1319: i, lesser, (FetchDescriptor) null, true);
1320: greater_handle = page.fetchFromSlot(
1321: (RecordHandle) null, i + 1, greater,
1322: (FetchDescriptor) null, true);
1323:
1324: SanityManager
1325: .ASSERT(btree.getConglomerate().nUniqueColumns <= btree
1326: .getConglomerate().nKeyFields);
1327: int compare_result = CompareIndexRowToKey(lesser,
1328: greater,
1329: btree.getConglomerate().nUniqueColumns, 0,
1330: btree.getConglomerate().ascDescInfo);
1331:
1332: // >= 0 means that lesser >= greater
1333: if (compare_result >= 0) {
1334: SanityManager
1335: .THROWASSERT("Bad order of rows found in conglomerate: "
1336: + btree
1337: + "\n."
1338: + "compare result = "
1339: + compare_result
1340: + ". "
1341: + "nKeyFields = "
1342: + btree.getConglomerate().nKeyFields
1343: + ".\n"
1344: + this
1345: + " rows "
1346: + (i)
1347: + " and "
1348: + (i + 1)
1349: + " out of order.\n"
1350: + "row["
1351: + i
1352: + "] + "
1353: + RowUtil.toString(lesser)
1354: + "\n"
1355: + "row["
1356: + (i + 1)
1357: + "] + "
1358: + RowUtil.toString(greater)
1359: + "\ndump of page = "
1360: + debugPage(btree)
1361: + "\ndump of parent page = "
1362: + ((parent != null) ? parent
1363: .debugPage(btree)
1364: : "null parent")
1365: + "\rawstore dump = " + this .page);
1366:
1367: is_consistent = false;
1368: }
1369: }
1370: return (is_consistent);
1371: } else {
1372: return (true);
1373: }
1374: }
1375:
1376: protected boolean compareRowsOnSiblings(OpenBTree btree,
1377: ControlRow left_sib, ControlRow right_sib)
1378: throws StandardException {
1379: if (SanityManager.DEBUG) {
1380: boolean is_consistent = true;
1381:
1382: // Check that left last row is < right page's first row.
1383: if (left_sib.page.recordCount() > 1
1384: && right_sib.page.recordCount() > 1) {
1385: DataValueDescriptor[] left_lastrow = getRowTemplate(btree);
1386: DataValueDescriptor[] right_firstrow = getRowTemplate(btree);
1387:
1388: RecordHandle left_lastrow_handle = left_sib.page
1389: .fetchFromSlot((RecordHandle) null,
1390: left_sib.page.recordCount() - 1,
1391: left_lastrow, (FetchDescriptor) null,
1392: true);
1393:
1394: RecordHandle right_firstrow_handle = right_sib.page
1395: .fetchFromSlot((RecordHandle) null, 1,
1396: right_firstrow, (FetchDescriptor) null,
1397: true);
1398:
1399: int r = CompareIndexRowToKey(left_lastrow,
1400: right_firstrow,
1401: btree.getConglomerate().nUniqueColumns, 0,
1402: btree.getConglomerate().ascDescInfo);
1403:
1404: if (r >= 0) {
1405: SanityManager.THROWASSERT("last row on left page "
1406: + left_sib.page.getPageNumber()
1407: + " > than first row on right page "
1408: + right_sib.page.getPageNumber() + "\n"
1409: + "left last row = "
1410: + RowUtil.toString(left_lastrow)
1411: + "right first row = "
1412: + RowUtil.toString(right_firstrow)
1413: + left_sib + " last > first of "
1414: + right_sib);
1415:
1416: is_consistent = false;
1417: }
1418: }
1419: return (is_consistent);
1420: } else {
1421: return (true);
1422: }
1423: }
1424:
1425: /**
1426: ** Perform checks on the siblings of this page: make sure
1427: ** that they're at the same level as this page, that they're
1428: ** mutually linked together, and that the first/last keys
1429: ** on sibling pages are in order.
1430:
1431: @exception StandardException Standard exception policy.
1432: **/
1433: protected void checkSiblings(OpenBTree btree)
1434: throws StandardException {
1435: if (SanityManager.DEBUG) {
1436: // Get this page's left sibling.
1437: ControlRow leftsib = null;
1438: ControlRow rightsib = null;
1439:
1440: try {
1441: try {
1442: leftsib = this .getLeftSibling(btree);
1443: } catch (WaitError e) {
1444: // In a normal system it may be possible to not get
1445: // the left sibling (some other thread either user
1446: // or daemon cache cleaner thread) may already have
1447: // the latch on the page, and waiting on it could cause
1448: // a latch/latch deadlock. So for now just give up
1449: // doing the consistency check in this case.
1450: //
1451: // RESOLVE (mikem) - We could do fancier things than
1452: // ignore this error, but the only safe way to wait for
1453: // a right to left latch is to release current latch which
1454: // will complicate all the code, and this is only a sanity
1455: // check.
1456:
1457: // SanityManager.DEBUG_PRINT(
1458: // "ControlRow.checkSiblings",
1459: // this + " left sibling deadlock");
1460:
1461: // give up on checking the left sibling.
1462: leftsib = null;
1463: }
1464:
1465: // There may not be a left sibling; if there is, check it out.
1466: if (leftsib != null) {
1467: // Check that it's at the same level as this page.
1468: if (leftsib.getLevel() != this .getLevel())
1469: SanityManager.THROWASSERT((leftsib
1470: + "not at same level as " + this ));
1471:
1472: // Check that its right sibling is this page.
1473: long hopefullythis _pageno = leftsib
1474: .getrightSiblingPageNumber();
1475:
1476: if (hopefullythis _pageno != this .page
1477: .getPageNumber())
1478: SanityManager.THROWASSERT("right sibling of "
1479: + leftsib + " isn't " + this );
1480:
1481: // Check that its last row is < this page's first row.
1482: compareRowsOnSiblings(btree, leftsib, this );
1483:
1484: // Done looking at the left sibling.
1485: leftsib.release();
1486: leftsib = null;
1487: }
1488:
1489: // Get the right sibling page.
1490: rightsib = this .getRightSibling(btree);
1491:
1492: // There may not be a right sibling; if there is, check it out.
1493: if (rightsib != null) {
1494: // Check that it's at the same level as this page.
1495: if (rightsib.getLevel() != this .getLevel())
1496: SanityManager.THROWASSERT(rightsib
1497: + "not at same level as " + this );
1498:
1499: // Check that its left sibling is this page.
1500: long hopefullythis _pageno = rightsib
1501: .getleftSiblingPageNumber();
1502:
1503: if (hopefullythis _pageno != this .page
1504: .getPageNumber())
1505: SanityManager.THROWASSERT("left sibling of "
1506: + rightsib + " isn't " + this );
1507:
1508: // Check that its first row is > this page's last row.
1509: compareRowsOnSiblings(btree, this , rightsib);
1510:
1511: // Done looking at it.
1512: rightsib.release();
1513: rightsib = null;
1514: }
1515: } finally {
1516: if (leftsib != null)
1517: leftsib.release();
1518: if (rightsib != null)
1519: rightsib.release();
1520: }
1521: }
1522: }
1523:
1524: /**
1525: ** Link this page to the right of the target page.
1526: ** <P>
1527: ** Upon entry, this page and the target must be
1528: ** latched. Upon exit, this page and the target
1529: ** remain latched.
1530: ** <P>
1531: ** This method carefully acquires pages from left
1532: ** to right in order to avoid deadlocks.
1533:
1534: @exception StandardException Standard exception policy.
1535: */
1536: void linkRight(OpenBTree btree, ControlRow target)
1537: throws StandardException {
1538: ControlRow rightSibling = null;
1539:
1540: try {
1541: rightSibling = target.getRightSibling(btree);
1542: this .setRightSibling(rightSibling);
1543: this .setLeftSibling(target);
1544: if (rightSibling != null)
1545: rightSibling.setLeftSibling(this );
1546: target.setRightSibling(this );
1547: } finally {
1548: if (rightSibling != null)
1549: rightSibling.release();
1550: }
1551: }
1552:
1553: /**
1554: ** Unlink this page from its siblings. This method
1555: ** will give up and return false rather than run the
1556: ** risk of a deadlock.
1557: ** <P>
1558: ** On entry this page must be latched. The siblings
1559: ** are latched and unlatched during the operation. Upon
1560: ** exit, this page will remain latched, but unlinked from
1561: ** its siblings and deallocated from the container.
1562: ** <P>
1563: ** The seemingly odd situation that this page will be
1564: ** returned latched but deallocated is intentional.
1565: ** The container will not be able to reuse this page
1566: ** until the latch is released, and the caller may still
1567: ** need to read information out of it.
1568:
1569: @exception StandardException Standard exception policy.
1570: **/
1571: boolean unlink(OpenBTree btree) throws StandardException {
1572: ControlRow leftsib = null;
1573: ControlRow rightsib = null;
1574:
1575: try {
1576: // Try to get the left sibling, and give up if
1577: // it can't be obtained without waiting.
1578:
1579: try {
1580: leftsib = this .getLeftSibling(btree);
1581: } catch (WaitError e) {
1582: return false;
1583: }
1584:
1585: // We can wait for the right sibling since it's
1586: // in the deadlock-free direction.
1587:
1588: rightsib = this .getRightSibling(btree);
1589:
1590: // Change the links that pointed to this page to
1591: // point to the appropriate sibling.
1592:
1593: if (leftsib != null)
1594: leftsib.setRightSibling(rightsib);
1595: if (rightsib != null)
1596: rightsib.setLeftSibling(leftsib);
1597:
1598: // Deallocate the page.
1599: // Would need to clear out aux object here.
1600: //
1601: // RESOLVE (mikem) - how to deallocate a page. //
1602: btree.container.removePage(this .page);
1603:
1604: // After removePage call the current page is unlatched, and should
1605: // not be referenced anymore.
1606: if (SanityManager.DEBUG) {
1607: SanityManager.ASSERT(!this .page.isLatched());
1608: }
1609:
1610: return true;
1611: } finally {
1612: // Unlatch the siblings.
1613: if (leftsib != null)
1614: leftsib.release();
1615: if (rightsib != null)
1616: rightsib.release();
1617: }
1618: }
1619:
1620: public Page getPage() {
1621: return (page);
1622: }
1623:
1624: /**
1625: * Get the row.
1626: * <p>
1627: * Return the object array that represents the control row for use
1628: * in raw store fetch, insert, and/or update.
1629: *
1630: * @return The row.
1631: *
1632: **/
1633: protected final DataValueDescriptor[] getRow() {
1634: return (row);
1635: }
1636:
1637: /*
1638: * The following methods must be implemented by all
1639: * control rows.
1640: */
1641:
1642: /**
1643: * Check consistency of the page and its children, returning the number of
1644: * pages seen, and throwing errors if inconsistencies are found.
1645: * <p>
1646: *
1647: * @return The identifier to be used to open the conglomerate later.
1648: *
1649: * @param btree The open btree to associate latches/locks with.
1650: * @param parent The parent page of this page, "null" if this page is
1651: * root or if not maintaining parent links.
1652: * @param check_other_pages
1653: * Should the consistency check go to other pages (this
1654: * option breaks the latch protocol).
1655: *
1656: * @exception StandardException Standard exception policy.
1657: **/
1658: abstract protected int checkConsistency(OpenBTree btree,
1659: ControlRow parent, boolean check_other_pages)
1660: throws StandardException;
1661:
1662: /**
1663: * Return the left child pointer for the page.
1664: * <p>
1665: * Leaf pages don't have children, so they override this and return null.
1666: *
1667: * @return The page which is the leftmost child of this page.
1668: *
1669: * @param btree The open btree to associate latches/locks with.
1670: *
1671: * @exception StandardException Standard exception policy.
1672: **/
1673: protected abstract ControlRow getLeftChild(OpenBTree btree)
1674: throws StandardException;
1675:
1676: /**
1677: * Return the right child pointer for the page.
1678: * <p>
1679: * Leaf pages don't have children, so they override this and return null.
1680: *
1681: * @return The page which is the rightmost child of this page.
1682: *
1683: * @param btree The open btree to associate latches/locks with.
1684: *
1685: * @exception StandardException Standard exception policy.
1686: **/
1687: protected abstract ControlRow getRightChild(OpenBTree btree)
1688: throws StandardException;
1689:
1690: /**
1691: * Perform page specific initialization.
1692: * <p>
1693: *
1694: **/
1695: protected abstract void ControlRowInit();
1696:
1697: /**
1698: * Is the current page the leftmost leaf of tree?
1699: * <p>
1700: *
1701: * @return true if the current page is the leftmost leaf of the tree,
1702: * else return false.
1703: *
1704: * @exception StandardException Standard exception policy.
1705: **/
1706: public abstract boolean isLeftmostLeaf() throws StandardException;
1707:
1708: /**
1709: * Is the current page the rightmost leaf of tree?
1710: * <p>
1711: *
1712: * @return true if the current page is the rightmost leaf of the tree,
1713: * else return false.
1714: *
1715: * @exception StandardException Standard exception policy.
1716: **/
1717: public abstract boolean isRightmostLeaf() throws StandardException;
1718:
1719: /**
1720: ** Perform a recursive search, ultimately returning the latched
1721: ** leaf page and row slot after which the given key belongs.
1722: ** The slot is returned in the result structure. If the key
1723: ** exists on the page, the resultExact field will be true. Otherwise,
1724: ** resultExact field will be false, and the row slot returned will be
1725: ** the one immediately preceding the position at which the key
1726: ** belongs.
1727:
1728: @exception StandardException Standard exception policy.
1729: **/
1730: public abstract ControlRow search(SearchParameters search_params)
1731: throws StandardException;
1732:
1733: /**
1734: * Get the number of columns in the control row.
1735: * <p>
1736: * Control rows all share the first columns as defined by this class and
1737: * then add columns to the end of the control row. For instance a branch
1738: * control row add a child page pointer field.
1739: * <p>
1740: *
1741: * @return The total number of columns in the control row.
1742: **/
1743: protected abstract int getNumberOfControlRowColumns();
1744:
1745: /**
1746: * Search and return the left most leaf page.
1747: * <p>
1748: * Perform a recursive search, ultimately returning the
1749: * leftmost leaf page which is the first leaf page in the
1750: * leaf sibling chain. (This method might better be called
1751: * getFirstLeafPage()).
1752: *
1753: * @return The leftmost leaf page.
1754: *
1755: * @param btree The open btree to associate latches/locks with.
1756: *
1757: * @exception StandardException Standard exception policy.
1758: **/
1759: protected abstract ControlRow searchLeft(OpenBTree btree)
1760: throws StandardException;
1761:
1762: /**
1763: * Search and return the right most leaf page.
1764: * <p>
1765: * Perform a recursive search, ultimately returning the
1766: * rightmost leaf page which is the last leaf page in the
1767: * leaf sibling chain. (This method might better be called
1768: * getLastLeafPage()).
1769: *
1770: * @return The rightmost leaf page.
1771: *
1772: * @param btree The open btree to associate latches/locks with.
1773: *
1774: * @exception StandardException Standard exception policy.
1775: **/
1776: protected abstract ControlRow searchRight(OpenBTree btree)
1777: throws StandardException;
1778:
1779: /**
1780: ** Perform a recursive shrink operation for the key.
1781: ** If this method returns true, the caller should
1782: ** remove the corresponding entry for the page.
1783: ** This routine is not guaranteed to successfully
1784: ** shrink anything. The page lead to by the key might
1785: ** turn out not to be empty by the time shrink gets
1786: ** there, and shrinks will give up if there is a deadlock.
1787: ** <P>
1788: ** As currently implemented shrinkFor must be executed while holding
1789: ** an exclusive container lock on the entire table. It is expected that
1790: ** this call is made within an internal transaction which has been called
1791: ** by a post commit thread. Latches are released by the code. The raw
1792: ** store guarantees that deallocated pages are not seen by other xacts
1793: ** until the transaction has been committed.
1794: ** <P>
1795: ** Note that a non-table level lock implementation must hold latches on
1796: ** pages affected until end transaction.
1797: ** <p>
1798: ** On entry, the current page is latched. On exit, all pages will have
1799: ** been unlatched.
1800: **
1801: ** @exception StandardException Standard exception policy.
1802: **/
1803: protected abstract boolean shrinkFor(OpenBTree btree,
1804: DataValueDescriptor[] key) throws StandardException;
1805:
1806: /**
1807: * Perform a top down split pass making room for the the key in "row".
1808: * <p>
1809: * Perform a split such that a subsequent call to insert
1810: * given the argument index row will likely find room for it. Since
1811: * latches are released the client must code for the case where another
1812: * user has grabbed the space made available by the split pass and be
1813: * ready to do another split.
1814: * <p>
1815: *
1816: * @return page number of the newly allocated leaf page created by split.
1817: *
1818: * @param open_btree The open btree to associate latches with.
1819: * @param template A scratch area to use while searching for split pass.
1820: * @param parentpage The parent page of the current page in the split pass.
1821: * starts at null for root.
1822: * @param row The key to make room for during the split pass.
1823: * @param flag A flag used to direct where point of split should be
1824: * chosen.
1825: *
1826: * @exception StandardException Standard exception policy.
1827: **/
1828: protected abstract long splitFor(OpenBTree open_btree,
1829: DataValueDescriptor[] template,
1830: BranchControlRow parentpage, DataValueDescriptor[] row,
1831: int flag) throws StandardException;
1832:
1833: /**
1834: ** Recursively print the tree starting at current node in tree.
1835:
1836: @exception StandardException Standard exception policy.
1837: **/
1838: public abstract void printTree(OpenBTree btree)
1839: throws StandardException;
1840:
1841: /*
1842: ** Methods of AuxObject
1843: */
1844:
1845: /**
1846: Called when the page is being evicted from cache or when a rollback
1847: happened on the page and may possibly have changed the control row's
1848: value
1849:
1850: @see AuxObject#auxObjectInvalidated
1851: **/
1852: public void auxObjectInvalidated() {
1853: version = null;
1854: leftSiblingPageNumber = null;
1855: rightSiblingPageNumber = null;
1856: parentPageNumber = null;
1857: level = null;
1858: isRoot = null;
1859: page = null;
1860: }
1861:
1862: /**
1863: * Return a new template for reading a data row from the current page.
1864: * <p>
1865: * Default implementation for rows which are the same as the conglomerates
1866: * template, sub-classes can alter if underlying template is different
1867: * (for instance branch rows add an extra field at the end).
1868: *
1869: * @return Newly allocated template.
1870: *
1871: * @exception StandardException Standard exception policy.
1872: **/
1873: public DataValueDescriptor[] getRowTemplate(OpenBTree open_btree)
1874: throws StandardException {
1875: return (open_btree.getConglomerate().createTemplate());
1876: }
1877:
1878: /**
1879: ** Debug toString() method's.
1880: **/
1881:
1882: /**
1883: * Dump complete information about control row and rows on the page.
1884: * <p>
1885: *
1886: * @return string with all info.
1887: *
1888: * @exception StandardException Standard exception policy.
1889: **/
1890: public String debugPage(OpenBTree open_btree)
1891: throws StandardException {
1892: String ret_str;
1893:
1894: if (SanityManager.DEBUG) {
1895: StringBuffer string = new StringBuffer(4096);
1896: string.append(this .toString());
1897: string.append("\n");
1898:
1899: DataValueDescriptor[] row = getRowTemplate(open_btree);
1900:
1901: string.append(ConglomerateUtil.debugPage(page,
1902: ControlRow.CR_SLOT + 1, false, row));
1903:
1904: ret_str = string.toString();
1905: } else {
1906: ret_str = null;
1907: }
1908:
1909: return (ret_str);
1910: }
1911:
1912: /**
1913: * The standard toString().
1914: * <p>
1915: * This is a concise print out of the info in the control row, does not
1916: * include anything the page.
1917: * <p>
1918: *
1919: **/
1920: public String toString() {
1921: if (SanityManager.DEBUG) {
1922: StringBuffer string = new StringBuffer(4096);
1923:
1924: try {
1925:
1926: // LEAF, BRANCH, LEAF-ROOT, BRANCH-ROOT
1927: string
1928: .append((getLevel() == 0) ? "\nLEAF"
1929: : "\nBRANCH");
1930: string.append((getIsRoot()) ? "-ROOT" : "");
1931:
1932: // (PAGE NUMBER)(LEVEL):num recs
1933: // example: (107)(lev=2):num recs = 16
1934: string.append("(");
1935: string.append(this .page.getPageNumber());
1936: string.append(")(lev=");
1937: string.append(level);
1938: string.append("): num recs = ");
1939: string.append(this .page.recordCount());
1940: string.append("\n");
1941:
1942: // rest of info
1943: string.append("\t");
1944:
1945: string.append("left = ");
1946: string.append(getleftSiblingPageNumber());
1947: string.append(";");
1948:
1949: string.append("right = ");
1950: string.append(getrightSiblingPageNumber());
1951: string.append(";");
1952:
1953: string.append("parent = ");
1954: string.append(getParentPageNumber());
1955: string.append(";");
1956:
1957: string.append("isRoot = ");
1958: string.append(getIsRoot());
1959: string.append(";");
1960:
1961: } catch (Throwable t) {
1962: string
1963: .append("error encountered while doing ControlRow.toString()");
1964: }
1965:
1966: return (string.toString());
1967: } else {
1968: return (null);
1969: }
1970: }
1971: }
|