0001: /*
0002:
0003: Derby - Class org.apache.derby.impl.store.access.btree.BranchControlRow
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 org.apache.derby.iapi.reference.SQLState;
0025:
0026: import org.apache.derby.iapi.services.io.FormatIdUtil;
0027: import org.apache.derby.iapi.services.io.Storable;
0028: import org.apache.derby.iapi.services.io.StoredFormatIds;
0029:
0030: import org.apache.derby.iapi.services.sanity.SanityManager;
0031:
0032: import org.apache.derby.iapi.error.StandardException;
0033:
0034: import org.apache.derby.iapi.store.access.conglomerate.LogicalUndo;
0035:
0036: import org.apache.derby.iapi.store.access.AccessFactoryGlobals;
0037: import org.apache.derby.iapi.store.access.Qualifier;
0038: import org.apache.derby.iapi.store.access.RowUtil;
0039: import org.apache.derby.iapi.store.access.ScanController;
0040:
0041: import org.apache.derby.iapi.store.raw.ContainerHandle;
0042: import org.apache.derby.iapi.store.raw.FetchDescriptor;
0043: import org.apache.derby.iapi.store.raw.Page;
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:
0050: import org.apache.derby.iapi.services.io.FormatableBitSet;
0051:
0052: /**
0053: * @format_id ACCESS_BTREE_BRANCHCONTROLROW_V1_ID
0054: *
0055: * @purpose Btree pages all have a control row at the front of every page.
0056: * To determine the type of row, read the first column which is a
0057: * format id and it tells what kind of control row it is.
0058: *
0059: * @upgrade RESOLVE.
0060: *
0061: * @disk_layout
0062: * column 1 - control row type : StorableFormatId
0063: * column 2 - left sibling page number : SQLLongint
0064: * column 3 - right sibling page number: SQLLongint
0065: * column 4 - parent page number : SQLLongint
0066: * column 5 - level number (0 is leaf) : SQLLongint
0067: * column 6 - isRoot : SQLLongint
0068: * column 7 - Conglomerate object : null unless it is root else
0069: * a Conglomerate object, matching
0070: * that of current table.
0071: * Currently this field
0072: * is only used by logical undo and
0073: * the type of object is inferred by
0074: * the logical undo code.
0075: * column 8 - left child page number : SQLLongint
0076: **/
0077:
0078: /**
0079: A branch row contains key fields and the pointer to the child page.
0080: **/
0081: public class BranchControlRow extends ControlRow {
0082: protected SQLLongint left_child_page = null;
0083:
0084: /**
0085: * Only allocate one child_pageno_buf to read the page pointer field into,
0086: * then cache to "empty" object for reuse by the page itself.
0087: **/
0088: transient SQLLongint child_pageno_buf = null;
0089:
0090: /* Column assignments */
0091: private static final int CR_LEFTCHILD = ControlRow.CR_COLID_LAST + 1;
0092: private static final int CR_COLID_LAST = CR_LEFTCHILD;
0093: private static final int CR_NCOLUMNS = CR_COLID_LAST + 1;
0094:
0095: /**
0096: * bit sets used to fetch single columns at a time.
0097: **/
0098: protected static final FormatableBitSet CR_LEFTCHILD_BITMAP = new FormatableBitSet(
0099: CR_LEFTCHILD + 1);
0100:
0101: /*
0102: ** Constructors of BranchControlRow
0103: */
0104:
0105: static {
0106: CR_LEFTCHILD_BITMAP.set(CR_LEFTCHILD);
0107: }
0108:
0109: /**
0110: * No arg constructor.
0111: * <p>
0112: * Public no arg constructor is for the monitor to call for format
0113: * id implementation, it should not be called for any other reason.
0114: **/
0115: public BranchControlRow() {
0116: }
0117:
0118: public BranchControlRow(OpenBTree open_btree, Page page, int level,
0119: ControlRow parent, boolean isRoot, long left_child)
0120: throws StandardException {
0121: super (open_btree, page, level, parent, isRoot);
0122:
0123: this .left_child_page = new SQLLongint(left_child);
0124:
0125: // finish initializing the row to be used for interacting with
0126: // raw store to insert, fetch, and update the control row on the page.
0127: this .row[CR_LEFTCHILD] = left_child_page;
0128:
0129: // set up buffer to read a branch row's page number into.
0130: child_pageno_buf = new SQLLongint();
0131: }
0132:
0133: /*
0134: ** Non - Debug/consistency check Methods of ControlRow:
0135: */
0136:
0137: /**
0138: * Perform page specific initialization.
0139: * <p>
0140: **/
0141: protected final void ControlRowInit() {
0142: child_pageno_buf = new SQLLongint();
0143: }
0144:
0145: /**
0146: * Is the current page the leftmost leaf of tree?
0147: * <p>
0148: *
0149: * @return true if the current page is the leftmost leaf of the tree,
0150: * else return false.
0151: *
0152: * @exception StandardException Standard exception policy.
0153: **/
0154: public boolean isLeftmostLeaf() throws StandardException {
0155: return (false);
0156: }
0157:
0158: /**
0159: * Is the current page the rightmost leaf of tree?
0160: * <p>
0161: *
0162: * @return true if the current page is the rightmost leaf of the tree,
0163: * else return false.
0164: *
0165: * @exception StandardException Standard exception policy.
0166: **/
0167: public boolean isRightmostLeaf() throws StandardException {
0168: return (false);
0169: }
0170:
0171: /**
0172: * Get the number of columns in the control row.
0173: * <p>
0174: * Control rows all share the first columns as defined by this class and
0175: * then add columns to the end of the control row. For instance a branch
0176: * control row add a child page pointer field.
0177: * <p>
0178: *
0179: * @return The total number of columns in the control row.
0180: **/
0181: protected final int getNumberOfControlRowColumns() {
0182: return (this .CR_NCOLUMNS);
0183: }
0184:
0185: public static long restartSplitFor(OpenBTree open_btree,
0186: DataValueDescriptor[] template, BranchControlRow parent,
0187: ControlRow child, DataValueDescriptor[] newbranchrow,
0188: DataValueDescriptor[] splitrow, int flag)
0189: throws StandardException {
0190: // release parent and current latch
0191: parent.release();
0192: child.release();
0193: parent = null;
0194: child = null;
0195:
0196: // Get the root page back, and perform a split following the
0197: // branch row which would not fit.
0198: ControlRow root = ControlRow.Get(open_btree, BTree.ROOTPAGEID);
0199:
0200: if (SanityManager.DEBUG)
0201: SanityManager.ASSERT(root.page.isLatched());
0202:
0203: return (root.splitFor(open_btree, template, null, newbranchrow,
0204: flag));
0205: }
0206:
0207: /**
0208: ** Perform a recursive search, ultimately returning the latched
0209: ** leaf page and row slot after which the given key belongs.
0210: ** The slot is returned in the result structure. If the key
0211: ** exists on the page, the result.exact will be true. Otherwise,
0212: ** result.exact will be false, and the row slot returned will be
0213: ** the one immediately preceding the position at which the key
0214: ** belongs.
0215: **
0216: ** @exception StandardException Standard exception policy.
0217: **/
0218: public ControlRow search(SearchParameters sp)
0219: throws StandardException {
0220: ControlRow childpage = null;
0221: long childpageid;
0222: boolean got_error = true;
0223:
0224: try {
0225: searchForEntry(sp);
0226:
0227: if (sp.searchForOptimizer) {
0228: // Update left_fraction to be used to esitimate the number of
0229: // rows left of the current search key.
0230:
0231: // Some search results leave the search positioned on the 0th
0232: // slot which is a control row, in branch pages this results
0233: // in following the left page pointer, there is no key
0234: // associated with this slot. Set left_rows to be the number
0235: // of leaf page pointers on the page which are left
0236: // of the current slot.
0237: float left_rows = sp.resultSlot;
0238:
0239: // include the control row count here, as it accounts for the
0240: // left page pointer which has no associated key.
0241: int row_count = this .page.recordCount();
0242:
0243: if (this .getIsRoot()) {
0244: sp.current_fraction = 1;
0245: sp.left_fraction = 0;
0246: }
0247:
0248: // calculate the fraction of rows in the table which are left
0249: // of the current slot in the search. This number represents
0250: // the fraction of rows in the sub-tree which includes all
0251: // rows left of rows pointed at by the sub-tree to be followed
0252: // by the code below which descends the child page pointer.
0253: // After the search is
0254: // completed (sp.left_fraction * number of rows), is the
0255: // estimated number of rows to the left of the current row.
0256: sp.left_fraction += (sp.current_fraction)
0257: * (left_rows / row_count);
0258:
0259: sp.current_fraction = (sp.current_fraction)
0260: * (((float) 1) / row_count);
0261: }
0262:
0263: childpage = this
0264: .getChildPageAtSlot(sp.btree, sp.resultSlot);
0265:
0266: this .release();
0267:
0268: got_error = false;
0269:
0270: return childpage.search(sp);
0271: } finally {
0272: if (got_error) {
0273: if (childpage != null)
0274: childpage.release();
0275: if (this .page.isLatched())
0276: this .release();
0277: }
0278: }
0279: }
0280:
0281: /**
0282: * Search and return the left most leaf page.
0283: * <p>
0284: * Perform a recursive search, ultimately returning the
0285: * leftmost leaf page which is the first leaf page in the
0286: * leaf sibling chain. (This method might better be called
0287: * getFirstLeafPage()).
0288: *
0289: * @return The leftmost leaf page.
0290: *
0291: * @param btree The open btree to associate latches/locks with.
0292: *
0293: * @exception StandardException Standard exception policy.
0294: **/
0295: protected ControlRow searchLeft(OpenBTree btree)
0296: throws StandardException {
0297: ControlRow childpage = null;
0298: boolean got_error = true;
0299:
0300: try {
0301: childpage = this .getLeftChild(btree);
0302: this .release();
0303:
0304: got_error = false;
0305: return childpage.searchLeft(btree);
0306: } finally {
0307: if (got_error) {
0308: if (childpage != null)
0309: childpage.release();
0310: if (this .page.isLatched())
0311: this .release();
0312: }
0313: }
0314: }
0315:
0316: /**
0317: * Search and return the right most leaf page.
0318: * <p>
0319: * Perform a recursive search, ultimately returning the
0320: * rightmost leaf page which is the last leaf page in the
0321: * leaf sibling chain. (This method might better be called
0322: * getLastLeafPage()).
0323: *
0324: * @return The rightmost leaf page.
0325: *
0326: * @param btree The open btree to associate latches/locks with.
0327: *
0328: * @exception StandardException Standard exception policy.
0329: **/
0330: protected ControlRow searchRight(OpenBTree btree)
0331: throws StandardException {
0332: ControlRow childpage = null;
0333: boolean got_error = true;
0334:
0335: try {
0336: childpage = this .getRightChild(btree);
0337: this .release();
0338:
0339: got_error = false;
0340: return (childpage.searchRight(btree));
0341: } finally {
0342: if (got_error) {
0343: if (childpage != null)
0344: childpage.release();
0345: if (this .page.isLatched())
0346: this .release();
0347: }
0348: }
0349: }
0350:
0351: /**
0352: ** Perform a recursive shrink operation for the key.
0353: ** If this method returns true, the caller should
0354: ** remove the corresponding entry for the page.
0355: ** This routine is not guaranteed to successfully
0356: ** shrink anything. The page lead to by the key might
0357: ** turn out not to be empty by the time shrink gets
0358: ** there, and shrinks will give up if there is a deadlock.
0359: ** <P>
0360: ** The receiver page must be latched on entry and is
0361: ** returned latched.
0362: **
0363: ** @exception StandardException Standard exception policy.
0364: **/
0365: protected boolean shrinkFor(OpenBTree open_btree,
0366: DataValueDescriptor[] shrink_key) throws StandardException {
0367: ControlRow childpage = null;
0368: boolean shrinkme = false;
0369:
0370: try {
0371: if (SanityManager.DEBUG)
0372: SanityManager.ASSERT(this .page.isLatched());
0373:
0374: // Find the child page for the shrink key.
0375:
0376: BranchRow branch_template = BranchRow
0377: .createEmptyTemplate(open_btree.getConglomerate());
0378: SearchParameters sp = new SearchParameters(
0379: shrink_key,
0380: SearchParameters.POSITION_LEFT_OF_PARTIAL_KEY_MATCH,
0381: branch_template.getRow(), open_btree, false);
0382:
0383: this .searchForEntry(sp);
0384: childpage = this
0385: .getChildPageAtSlot(sp.btree, sp.resultSlot);
0386:
0387: // Recursively shrink the child. If this call returns
0388: // true, then the child page has been deleted from its
0389: // sibling chain, and we have to delete the entry for it
0390: // in this page.
0391:
0392: if (childpage.shrinkFor(open_btree, shrink_key)) {
0393: // Child was deallocated.
0394: if (sp.resultSlot != 0) {
0395: // Remove the corresponding branch row. This call assumes
0396: // that raw store will shift all higher slots down to fill
0397: // the purged slot.
0398: this .page.purgeAtSlot(sp.resultSlot, 1, true);
0399: } else {
0400: // Shrunk slot is zero, which means the left child page was
0401: // deallocated. If the current page is empty, then
0402: // we have to deallocate it. Otherwise, we "slide" the rows
0403: // down, making the first index row into the left child,
0404: // and the second index row into the first, etc.
0405:
0406: if (this .page.recordCount() > 1) {
0407: // There is a branch row on this page (besides the
0408: // control row). Make the first branch row into the
0409: // left child.
0410:
0411: long leftchildpageid = getChildPageIdAtSlot(
0412: open_btree, 1);
0413:
0414: this .setLeftChildPageno(leftchildpageid);
0415:
0416: // purge the row we just made the "left child", this
0417: // will automatically shifta all other rows "left" in
0418: // the tree.
0419: this .page.purgeAtSlot(1, 1, true);
0420: } else {
0421: // We shrunk the left child which was the last child on
0422: // the page. This means that this entire subtree is
0423: // empty. Again, there are two cases: root vs.
0424: // non-root. Because this method waits till pages are
0425: // completely empty before deallocating them from the
0426: // index, an empty root page means an empty index.
0427: // If this page is not the root, then simply
0428: // deallocate it and return that fact to the caller.
0429:
0430: if (this .getIsRoot()) {
0431: // The root page has become empty. If the root page
0432: // is empty, then the index is empty. What has to
0433: // happen here is that this page has to be
0434: // converted back to an empty leaf page.
0435:
0436: // With the current interface, after this page has
0437: // been converted to a leaf, the caller will be
0438: // left with a branch control row object, although
0439: // the page is a leaf page. This same problem was
0440: // addressed in splitFor by adjusting the interface
0441: // - the two routines should at least have the same
0442: // interface style.
0443:
0444: if (SanityManager.DEBUG) {
0445: SanityManager.ASSERT(this .page
0446: .recordCount() == 1);
0447: }
0448:
0449: LeafControlRow newleafroot = new LeafControlRow(
0450: open_btree, this .page, null, true);
0451:
0452: newleafroot.page.updateAtSlot(0,
0453: newleafroot.getRow(),
0454: (FormatableBitSet) null);
0455:
0456: newleafroot.release();
0457:
0458: shrinkme = true;
0459: } else {
0460: // This page is empty, but it's not the root. We
0461: // have to unlink this page from its siblings, and
0462: // return to the parent branch page that its
0463: // branch row should be removed.
0464:
0465: // Unlink this page from its siblings.
0466: if (this .unlink(open_btree)) {
0467: // Tell the caller to remove entry.
0468: shrinkme = true;
0469: }
0470: }
0471: }
0472: }
0473: }
0474: } finally {
0475: // If shrinkme then the page has been unlatched either by
0476: // page.removePage(), or by the process of changing the root branch
0477: // page to a root leaf page.
0478: if (!shrinkme)
0479: this .release();
0480: }
0481:
0482: return (shrinkme);
0483: }
0484:
0485: /**
0486: * Perform a top down split pass making room for the the key in "row".
0487: * <p>
0488: * Perform a split such that a subsequent call to insert
0489: * given the argument index row will likely find room for it. Since
0490: * latches are released the client must code for the case where another
0491: * user has grabbed the space made available by the split pass and be
0492: * ready to do another split.
0493: * <p>
0494: * Latches:
0495: * o PARENT : is latched on entry (unless the split is the root then
0496: * there is no parent.
0497: * o THISBRANCH: the current page is latched on entry.
0498: * o CHILD : latch the child page which will be pointed at by the
0499: * left child pointer of the new page.
0500: * RESOLVE (mikem) -see comments below
0501: * o NEWPAGE : Allocate and latch new page.
0502: * o CHILD : release. (RESOLVE)
0503: * o fixparents: latch pages and reset their parent pointers.
0504: * Conditionally fix up the parent links on the pages
0505: * pointed at by the newly allocated page. First get latch
0506: * and release on the left child page and then loop through
0507: * slots on NEWPAGE, from left to right getting and
0508: * releasing latches.
0509: *
0510: *
0511: * @return page number of the newly allocated leaf page created by split.
0512: *
0513: * @param open_btree The open btree to associate latches with.
0514: * @param template A scratch area to use while searching for split pass.
0515: * @param parent The parent page of the current page in the split pass.
0516: * starts at null for root.
0517: * @param splitrow The key to make room for during the split pass.
0518: * @param flag A flag used to direct where point of split should be
0519: * chosen.
0520: *
0521: * @exception StandardException Standard exception policy.
0522: **/
0523: protected long splitFor(OpenBTree open_btree,
0524: DataValueDescriptor[] template, BranchControlRow parent,
0525: DataValueDescriptor[] splitrow, int flag)
0526: throws StandardException {
0527: int childpageid;
0528: ControlRow childpage;
0529:
0530: // On entry, the parent page is either latched by the caller,
0531: // or it's null (which implies that this object is the root).
0532:
0533: if (SanityManager.DEBUG) {
0534: SanityManager.ASSERT(parent != null || this .getIsRoot());
0535:
0536: SanityManager.ASSERT(parent == null
0537: || parent.page.isLatched(),
0538: "parent page is not latched");
0539:
0540: SanityManager.ASSERT(this .page.isLatched(),
0541: "page is not latched:");
0542: }
0543:
0544: if ((this .page.recordCount() - 1 >= open_btree
0545: .getConglomerate().maxRowsPerPage)
0546: || (!this .page.spaceForInsert(splitrow,
0547: (FormatableBitSet) null,
0548: AccessFactoryGlobals.BTREE_OVERFLOW_THRESHOLD))) {
0549:
0550: if (this .page.recordCount() == 1) {
0551: // RESOLVE (mikem) long row issue. For now it makes no sense
0552: // to split if there are no rows. So if spaceForRecord() fails
0553: // on empty page, we throw exception.
0554: throw StandardException
0555: .newException(SQLState.BTREE_NO_SPACE_FOR_KEY);
0556: }
0557:
0558: // Track.BranchSplit++;
0559:
0560: if (this .getIsRoot()) {
0561: // Track.BranchSplitRoot++;
0562: growRoot(open_btree, template, this );
0563:
0564: parent = (BranchControlRow) ControlRow.Get(open_btree,
0565: BTree.ROOTPAGEID);
0566:
0567: return (parent.splitFor(open_btree, template, null,
0568: splitrow, flag));
0569: }
0570:
0571: // At this point we know that this page has to be split and
0572: // that it isn't a root page.
0573: if (SanityManager.DEBUG) {
0574: SanityManager.ASSERT(!this .getIsRoot());
0575: SanityManager.ASSERT(parent != null);
0576: }
0577:
0578: int splitpoint = (this .page.recordCount() - 1) / 2 + 1;
0579:
0580: if ((flag & ControlRow.SPLIT_FLAG_FIRST_ON_PAGE) != 0) {
0581: // move all the row to the new page
0582: splitpoint = 1;
0583: } else if ((flag & ControlRow.SPLIT_FLAG_LAST_ON_PAGE) != 0) {
0584: // This is not optimal as we would rather move no rows to the
0585: // next page, but what should we use as a discriminator?
0586: splitpoint = this .page.recordCount() - 1;
0587: }
0588:
0589: if (SanityManager.DEBUG) {
0590: if (splitpoint <= 0)
0591: SanityManager.THROWASSERT(this
0592: + "yikes! splitpoint of 0!");
0593: }
0594:
0595: // Before any logged operation is done in the current internal
0596: // xact, make sure that there is room in the parent to insert
0597: // the new branch row.
0598: //
0599: // Create a new branch row which points to the new page,
0600: // and insert it on parent page.
0601:
0602: // Read in the branch row which is at the split point.
0603: BranchRow split_branch_row = BranchRow
0604: .createEmptyTemplate(open_btree.getConglomerate());
0605:
0606: this .page.fetchFromSlot((RecordHandle) null, splitpoint,
0607: split_branch_row.getRow(), (FetchDescriptor) null,
0608: true);
0609:
0610: // Create the branch row to insert onto the parent page. For now
0611: // use a fake page number because we don't know the real page
0612: // number until the allocate is done, but want to delay the
0613: // allocate until we know the insert will succeed.
0614: BranchRow newbranchrow = split_branch_row
0615: .createBranchRowFromOldBranchRow(BranchRow.DUMMY_PAGE_NUMBER);
0616:
0617: // At this point we have guaranteed there is space in the parent
0618: // page for splitrow, but it could be the case that the new
0619: // "newbranchrow" does not fit on the parent page.
0620: if (!parent.page.spaceForInsert(newbranchrow.getRow(),
0621: (FormatableBitSet) null,
0622: AccessFactoryGlobals.BTREE_OVERFLOW_THRESHOLD)) {
0623: // There is no room on the parent page to complete a split at
0624: // the current level, so restart the split at top with the
0625: // branchrow that did not fit. On return from this routine
0626: // there is no way to know the state of the tree, so the
0627: // current split pass recursion must end.
0628: return (parent.restartSplitFor(open_btree, template,
0629: parent, this , newbranchrow.getRow(), splitrow,
0630: flag));
0631: }
0632:
0633: // Get the child page for the index row at the split point
0634: // This will be the left child for the new page. We're
0635: // getting the page because BranchControlRow.Allocate
0636: // sets the left child pointer from a BranchControlRow.
0637: // If there were a version which just took the pageid,
0638: // we wouldn't have to get the page (the latch on this
0639: // page is enough to ensure that the child page won't
0640: // disappear).
0641:
0642: childpage = this .getChildPageAtSlot(open_btree, splitpoint);
0643:
0644: // Allocate a new branch page and link it to the
0645: // right of the current page.
0646: BranchControlRow newbranch = BranchControlRow.Allocate(
0647: open_btree, childpage, this .getLevel(), parent);
0648: newbranch.linkRight(open_btree, this );
0649:
0650: // Test fail after allocation
0651: if (SanityManager.DEBUG) {
0652: if (SanityManager.DEBUG_ON("branch_split_abort1")) {
0653: throw StandardException
0654: .newException(SQLState.BTREE_ABORT_THROUGH_TRACE);
0655: }
0656: }
0657:
0658: // Done with the child page.
0659: childpage.release();
0660:
0661: // Now that we know the page number of the new child page update
0662: // the branch row to be inserted with the correct value.
0663: newbranchrow.setPageNumber(newbranch.page.getPageNumber());
0664:
0665: BranchRow branch_template = BranchRow
0666: .createEmptyTemplate(open_btree.getConglomerate());
0667: SearchParameters sp = new SearchParameters(
0668: newbranchrow.getRow(),
0669: SearchParameters.POSITION_LEFT_OF_PARTIAL_KEY_MATCH,
0670: branch_template.getRow(), open_btree, false);
0671:
0672: parent.searchForEntry(sp);
0673:
0674: byte insertFlag = Page.INSERT_INITIAL;
0675: insertFlag |= Page.INSERT_DEFAULT;
0676: insertFlag |= Page.INSERT_UNDO_WITH_PURGE;
0677: if (parent.page.insertAtSlot(sp.resultSlot + 1,
0678: newbranchrow.getRow(), (FormatableBitSet) null,
0679: (LogicalUndo) null, insertFlag,
0680: AccessFactoryGlobals.BTREE_OVERFLOW_THRESHOLD) == null) {
0681: throw StandardException
0682: .newException(SQLState.BTREE_NO_SPACE_FOR_KEY);
0683: }
0684:
0685: // Test fail after of row onto parent page.
0686: if (SanityManager.DEBUG) {
0687: if (SanityManager.DEBUG_ON("branch_split_abort2")) {
0688: throw StandardException
0689: .newException(SQLState.BTREE_ABORT_THROUGH_TRACE);
0690: }
0691: }
0692:
0693: // newbranchrow only valid while contents of split_branch_row
0694: // remain unchanged.
0695: newbranchrow = null;
0696:
0697: // Copy the rows from the split point, but not including it (since
0698: // the split point is turning into the left child of the new
0699: // branch), onto the new page. Purge the rows including the split
0700: // point from the current page.
0701: int num_rows_to_move = this .page.recordCount()
0702: - (splitpoint + 1);
0703:
0704: if (num_rows_to_move > 0) {
0705: this .page.copyAndPurge(newbranch.page, splitpoint + 1,
0706: num_rows_to_move, 1);
0707: }
0708:
0709: // remove the splitpoint row, we didn't copy it because it became
0710: // the "left child", but we do need to get rid of it.
0711: this .page.purgeAtSlot(splitpoint, 1, true);
0712:
0713: // Test fail after of copy of rows to new page.
0714: if (SanityManager.DEBUG) {
0715: if (SanityManager.DEBUG_ON("branch_split_abort3")) {
0716: throw StandardException
0717: .newException(SQLState.BTREE_ABORT_THROUGH_TRACE);
0718: }
0719: }
0720:
0721: // Test fail after purge of rows on old page.
0722: if (SanityManager.DEBUG) {
0723: if (SanityManager.DEBUG_ON("branch_split_abort4")) {
0724: throw StandardException
0725: .newException(SQLState.BTREE_ABORT_THROUGH_TRACE);
0726: }
0727: }
0728:
0729: // Check pages that have been altered by above split
0730: if (SanityManager.DEBUG) {
0731: if (SanityManager
0732: .DEBUG_ON("enableBtreeConsistencyCheck")) {
0733: parent.checkConsistency(open_btree, null, false);
0734: newbranch.checkConsistency(open_btree, parent,
0735: false);
0736: this .checkConsistency(open_btree, parent, false);
0737: }
0738: }
0739:
0740: // Fix up the parent links on the pages for the rows that moved to
0741: // the new branch.
0742: newbranch.fixChildrensParents(open_btree, null);
0743:
0744: // At this point a unit of work in the split down the tree has
0745: // been performed in an internal transaction (ie. writes have been
0746: // done to latched pages), and the resulting
0747: // tree is logically consistent, thus the work can be committed.
0748: // This work must be committed before any latches are released.
0749: open_btree.getXactMgr().commit();
0750:
0751: // Decide whether we're following the current page or the new page.
0752: BranchControlRow pagetofollow;
0753:
0754: if (CompareIndexRowToKey(splitrow, split_branch_row
0755: .getRow(), split_branch_row.getRow().length - 1, 0,
0756: open_btree.getConglomerate().ascDescInfo) >= 0) {
0757: // Follow the new branch
0758: pagetofollow = newbranch;
0759: this .release();
0760: } else {
0761: // Follow the current branch
0762: pagetofollow = this ;
0763: newbranch.release();
0764: }
0765:
0766: // At this point we hold latches on the parent, and the current
0767: // child of the page that we are following. Note that committing
0768: // the internal transaction did not release the latches.
0769: if (SanityManager.DEBUG) {
0770: SanityManager.ASSERT(parent != null);
0771: SanityManager.ASSERT(parent.page.isLatched());
0772: SanityManager.ASSERT(pagetofollow.page.isLatched());
0773: }
0774:
0775: // Recurse down the tree splitting if necessary.
0776: return (pagetofollow.splitFor(open_btree, template, parent,
0777: splitrow, flag));
0778: }
0779:
0780: if (SanityManager.DEBUG) {
0781: if (SanityManager.DEBUG_ON("enableBtreeConsistencyCheck")) {
0782: this .checkConsistency(open_btree, parent, false);
0783: }
0784: }
0785:
0786: // Don't need the parent any more.
0787: if (parent != null)
0788: parent.release();
0789:
0790: // RESOLVE (mikem) - should this be passed in?
0791: BranchRow branch_template = BranchRow
0792: .createEmptyTemplate(open_btree.getConglomerate());
0793: SearchParameters sp = new SearchParameters(splitrow,
0794: SearchParameters.POSITION_LEFT_OF_PARTIAL_KEY_MATCH,
0795: branch_template.getRow(), open_btree, false);
0796:
0797: searchForEntry(sp);
0798:
0799: childpage = this .getChildPageAtSlot(open_btree, sp.resultSlot);
0800:
0801: return (childpage.splitFor(open_btree, template, this ,
0802: splitrow, flag));
0803: }
0804:
0805: /*
0806: ** Debug/consistency check Methods of ControlRow:
0807: */
0808:
0809: /**
0810: ** Perform consistency checks for a branch page. The checks
0811: ** specific to a branch page are:
0812: ** <menu>
0813: ** <li> The rows on the page are indeed branch rows, and
0814: ** they all have the correct number of fields (which
0815: ** is the b-tree's key fields plus one for the child
0816: ** page number.
0817: ** <li> The child pages pointed to by the left child pointer
0818: ** and the index rows are linked together in the same
0819: ** order that they appear on the page.
0820: ** <li> The child pages themselves are all consistent.
0821: ** </menu>
0822: ** This method also performs the consistency checks that
0823: ** are common to both leaf and branch pages (see
0824: ** ControlRow.checkGeneric).
0825: **
0826: ** @exception StandardException Standard exception policy.
0827: **/
0828: public int checkConsistency(OpenBTree btree, ControlRow parent,
0829: boolean check_other_pages) throws StandardException {
0830: // Do the consistency checks that are common to all
0831: // types of pages.
0832: checkGeneric(btree, parent, check_other_pages);
0833:
0834: // Branch specific Control Row checks.
0835: if (SanityManager.DEBUG) {
0836: SanityManager.ASSERT(this .getLevel() > 0,
0837: "branch not above level 0");
0838:
0839: // RESOLVE (mikem) - how to check right version?
0840: /*
0841: if (this.getVersion() != CURRENT_BRANCH_VERSION)
0842: SanityManager.THROWASSERT(
0843: "Expected branch version:(" + CURRENT_BRANCH_VERSION +
0844: ") but got (" + this.getVersion());
0845: */
0846: SanityManager
0847: .ASSERT(this .page.fetchNumFieldsAtSlot(CR_SLOT) == BranchControlRow.CR_NCOLUMNS);
0848: SanityManager
0849: .ASSERT(getLeftChildPageno() != ContainerHandle.INVALID_PAGE_NUMBER);
0850:
0851: // RESOLVE (mikem) - this makes an assumption about page numbering,
0852: // that may not be always valid in all implementations but has
0853: // been useful in finding bugs with uninitialized fields.
0854: SanityManager
0855: .ASSERT(getLeftChildPageno() >= BTree.ROOTPAGEID);
0856: }
0857:
0858: // The remaining checks are specific to branch pages.
0859: if (SanityManager.DEBUG) {
0860:
0861: // Check that all the branch rows are branch rows
0862: // (we'll get a case error otherwise), and have the right
0863: // number of columns. Every branch row should have the
0864: // btree's key columns plus one for the child link.
0865: int numslots = this .page.recordCount();
0866: for (int slot = 1; slot < numslots; slot++) {
0867: if ((this .page.fetchNumFieldsAtSlot(slot) != (btree
0868: .getConglomerate().nKeyFields + 1)))
0869: SanityManager.THROWASSERT("row[" + slot + "]"
0870: + " has "
0871: + this .page.fetchNumFieldsAtSlot(slot)
0872: + " columns, should have at least "
0873: + (btree.getConglomerate().nKeyFields + 1));
0874:
0875: SanityManager.ASSERT(this .getChildPageIdAtSlot(btree,
0876: slot) != ContainerHandle.INVALID_PAGE_NUMBER);
0877:
0878: // Rows on branch pages are never deleted, they are only purged.
0879: SanityManager.ASSERT(!this .page.isDeletedAtSlot(slot));
0880:
0881: // RESOLVE (mikem) - this makes an assumption about page
0882: // numbering, that may not be always valid in all
0883: // implementations but has been useful in finding bugs with
0884: // uninitialized fields.
0885: SanityManager
0886: .ASSERT(getLeftChildPageno() >= BTree.ROOTPAGEID);
0887: }
0888: }
0889:
0890: // Check that the linkage of the children is in the
0891: // same order as the branch rows.
0892: // RESOLVE (mikem) enable when multiple latches work.
0893: if (check_other_pages)
0894: checkChildOrderAgainstRowOrder(btree);
0895:
0896: // Check the children.
0897: int nchildren = 0;
0898:
0899: // RESOLVE (mikem) enable when multiple latches work.
0900: if (check_other_pages)
0901: nchildren = checkChildren(btree);
0902:
0903: // Return the number of children visited plus one for this page.
0904: return nchildren + 1;
0905: }
0906:
0907: private int checkChildren(OpenBTree btree) throws StandardException {
0908: int nchildren = 0;
0909: ControlRow childpage = null;
0910:
0911: try {
0912: // Check the left child.
0913: childpage = this .getLeftChild(btree);
0914: nchildren += childpage.checkConsistency(btree, this , true);
0915: childpage.release();
0916: childpage = null;
0917:
0918: // Check children from each index row.
0919: int numslots = this .page.recordCount();
0920: for (int slot = 1; slot < numslots; slot++) {
0921: childpage = this .getChildPageAtSlot(btree, slot);
0922: nchildren += childpage.checkConsistency(btree, this ,
0923: true);
0924: childpage.release();
0925: childpage = null;
0926: }
0927:
0928: return (nchildren);
0929: } finally {
0930: if (childpage != null)
0931: childpage.release();
0932: }
0933: }
0934:
0935: private void checkChildOrderAgainstRowOrder(OpenBTree btree)
0936: throws StandardException {
0937: ControlRow cur = null;
0938: ControlRow prev = null;
0939:
0940: try {
0941: prev = this .getLeftChild(btree);
0942:
0943: int numslots = this .page.recordCount();
0944: for (int slot = 1; slot < numslots; slot++) {
0945: cur = this .getChildPageAtSlot(btree, slot);
0946:
0947: long shouldbecur_pageno = prev
0948: .getrightSiblingPageNumber();
0949: if (SanityManager.DEBUG) {
0950: if (shouldbecur_pageno != cur.page.getPageNumber())
0951: SanityManager
0952: .THROWASSERT("child linkage error going right.\n"
0953: + "cur page control row = "
0954: + cur
0955: + "\n"
0956: + "prev page control row = "
0957: + prev + "\n");
0958: }
0959:
0960: long shouldbeprev_pageno = cur
0961: .getleftSiblingPageNumber();
0962:
0963: if (SanityManager.DEBUG) {
0964: SanityManager.ASSERT(
0965: shouldbeprev_pageno == prev.page
0966: .getPageNumber(),
0967: "child linkeage error going left");
0968: }
0969:
0970: prev.release();
0971: prev = cur;
0972: cur = null;
0973: }
0974:
0975: prev.release();
0976: prev = null;
0977: } finally {
0978: if (prev != null)
0979: prev.release();
0980: if (cur != null)
0981: cur.release();
0982: }
0983:
0984: return;
0985: }
0986:
0987: /**
0988: * Recursively print the tree starting at current node in tree.
0989: *
0990: * @param btree the open btree to print.
0991: *
0992: * @exception StandardException Standard exception policy.
0993: **/
0994: public void printTree(OpenBTree btree) throws StandardException {
0995: if (SanityManager.DEBUG) {
0996: SanityManager.DEBUG_PRINT("p_tree", this .debugPage(btree));
0997:
0998: ControlRow child = null;
0999:
1000: try {
1001: child = this .getLeftChild(btree);
1002:
1003: child.printTree(btree);
1004: child.release();
1005: child = null;
1006:
1007: int numslots = this .page.recordCount();
1008: for (int slot = 1; slot < numslots; slot++) {
1009: child = this .getChildPageAtSlot(btree, slot);
1010: child.printTree(btree);
1011: child.release();
1012: child = null;
1013: }
1014: } finally {
1015: if (child != null)
1016: child.release();
1017: }
1018:
1019: return;
1020: }
1021: }
1022:
1023: /*
1024: * Private methods of BranchControlRow
1025: */
1026:
1027: /**
1028: ** Add a level to the tree by moving the current branch-root page up
1029: ** one level and adding a new page as it's left child. On exit the
1030: ** current root page remains the root of the tree.
1031: ** <P>
1032: ** On entry, the current branch root page is expected to be latched.
1033: ** On exit, all latches will have been released.
1034: ** <P>
1035: ** Latch order:
1036: ** o ROOT: on entry current root is latched.
1037: ** No other latches should be held.
1038: ** o ROOT_OLDCHILD: Get and Latch root's left child page.
1039: ** o ROOT_NEWCHILD: Allocate a new branch page with latch.
1040: ** o Conditionally fix up the parent links on the pages pointed at
1041: ** by the newly allocated page. Loop through slots on ROOT_NEWCHILD,
1042: ** from left to right getting and releasing latches. Note that
1043: ** fixChildrensParents() must not latch the leftchild as ROOT_OLDCHILD
1044: ** is already latched.
1045: ** RESOLVE: (mikem) does order of release matter.
1046: ** o ROOT : released.
1047: ** o ROOT_NEWCHILD: released.
1048: ** o ROOT_OLDCHILD: released.
1049: **/
1050: private static void growRoot(OpenBTree open_btree,
1051: DataValueDescriptor[] template, BranchControlRow root)
1052: throws StandardException {
1053: ControlRow leftchild = null;
1054: BranchControlRow branch = null;
1055:
1056: try {
1057: if (SanityManager.DEBUG) {
1058: SanityManager.ASSERT(root.page.isLatched());
1059: SanityManager.ASSERT(root.getIsRoot());
1060: }
1061:
1062: // System.out.println("Growing root: control row = " + root);
1063: // System.out.println("Growing root: page = " + root.page);
1064:
1065: // Get and latch the current root's left child. This will become
1066: // the left child on the new branch page (and the new
1067: // branch will become the left child of the root).
1068: leftchild = root.getLeftChild(open_btree);
1069:
1070: // Allocate a new branch page. This one will take the
1071: // rows from the root, and remain at the old root's level.
1072: // Its parent is the root.
1073: branch = BranchControlRow.Allocate(open_btree, leftchild,
1074: root.getLevel(), root);
1075:
1076: // Copy all the index rows from the root to the new branch.
1077: // Purge the index rows from the root now that they're safely on the
1078: // new branch page. Leave the branch control row on the page.
1079: root.page.copyAndPurge(branch.page, 1, root.page
1080: .recordCount() - 1, 1);
1081:
1082: // Set the root's left child to be the new branch.
1083: root.setLeftChild(branch);
1084:
1085: // Move the root up a level
1086: root.setLevel(root.getLevel() + 1);
1087:
1088: // The parent of the old root's children has changed.
1089: // It used to be page 0 (the old root, but now it's
1090: // the new branch page. Fix this up.
1091: branch.fixChildrensParents(open_btree, leftchild);
1092:
1093: if (SanityManager.DEBUG) {
1094: if (SanityManager
1095: .DEBUG_ON("enableBtreeConsistencyCheck")) {
1096: root.checkConsistency(open_btree, null, false);
1097: branch.checkConsistency(open_btree, root, false);
1098: leftchild.checkConsistency(open_btree, branch,
1099: false);
1100: }
1101: }
1102:
1103: // At this point a unit of work in the split down the tree has
1104: // been performed in an internal transaction. This work must
1105: // be committed before any latches are released.
1106: open_btree.getXactMgr().commit();
1107:
1108: } finally {
1109: // At the end of a growRoot() no latches are held, the caller must
1110: // restart at the root.
1111: //
1112: root.release();
1113: if (branch != null)
1114: branch.release();
1115: if (leftchild != null)
1116: leftchild.release();
1117: }
1118: return;
1119: }
1120:
1121: /**
1122: * Allocate a new leaf page to the conglomerate.
1123: *
1124: * @exception StandardException Standard exception policy.
1125: */
1126: private static BranchControlRow Allocate(OpenBTree open_btree,
1127: ControlRow leftchild, int level, ControlRow parent)
1128: throws StandardException {
1129: Page page = open_btree.container.addPage();
1130:
1131: // Create a control row for the new page.
1132: BranchControlRow control_row = new BranchControlRow(open_btree,
1133: page, level, parent, false, leftchild.page
1134: .getPageNumber());
1135:
1136: // Insert the control row on the page.
1137: byte insertFlag = Page.INSERT_INITIAL;
1138: insertFlag |= Page.INSERT_DEFAULT;
1139: page.insertAtSlot(Page.FIRST_SLOT_NUMBER, control_row.getRow(),
1140: (FormatableBitSet) null, (LogicalUndo) null,
1141: insertFlag,
1142: AccessFactoryGlobals.BTREE_OVERFLOW_THRESHOLD);
1143:
1144: // Page is returned latched.
1145: return (control_row);
1146: }
1147:
1148: protected void setLeftChildPageno(long leftchild_pageno)
1149: throws StandardException {
1150: // Store the field.
1151: if (left_child_page == null)
1152: left_child_page = new SQLLongint(leftchild_pageno);
1153: else
1154: this .left_child_page.setValue(leftchild_pageno);
1155:
1156: // Write the field through to the underlying row
1157: this .page.updateFieldAtSlot(CR_SLOT, CR_LEFTCHILD,
1158: this .left_child_page, null);
1159: }
1160:
1161: protected void setLeftChild(ControlRow leftchild)
1162: throws StandardException {
1163: this .setLeftChildPageno(leftchild.page.getPageNumber());
1164: }
1165:
1166: /**
1167: ** A branch page that has just been allocated as part
1168: ** of a split has index rows and a left child pointer
1169: ** that were copied from another page. The parent
1170: ** link on the corresponding pages will still point to
1171: ** the original page. This method fixes their parent
1172: ** pointers so that they point to the curren page like
1173: ** they're supposed to.
1174: ** <P>
1175: ** Note that maintaining the parent link is kind of a
1176: ** pain, and will slow down applications. It's only
1177: ** needed for consistency checks, so we may want to
1178: ** have implementations that don't bother to maintain it.
1179: ** <P)
1180: ** This
1181: **/
1182: private void fixChildrensParents(OpenBTree btree,
1183: ControlRow leftchild) throws StandardException {
1184: ControlRow child = null;
1185:
1186: try {
1187: if (leftchild == null) {
1188: child = this .getLeftChild(btree);
1189: child.setParent(this .page.getPageNumber());
1190:
1191: if (SanityManager.DEBUG) {
1192: if (SanityManager
1193: .DEBUG_ON("enableBtreeConsistencyCheck")) {
1194: child.checkConsistency(btree, this , false);
1195: }
1196: }
1197:
1198: child.release();
1199: child = null;
1200: } else {
1201: leftchild.setParent(this .page.getPageNumber());
1202:
1203: if (SanityManager.DEBUG) {
1204: if (SanityManager
1205: .DEBUG_ON("enableBtreeConsistencyCheck")) {
1206: leftchild.checkConsistency(btree, this , false);
1207: }
1208: }
1209: }
1210:
1211: int numslots = this .page.recordCount();
1212: for (int slot = 1; slot < numslots; slot++) {
1213: child = getChildPageAtSlot(btree, slot);
1214: child.setParent(this .page.getPageNumber());
1215: if (SanityManager.DEBUG) {
1216: if (SanityManager
1217: .DEBUG_ON("enableBtreeConsistencyCheck")) {
1218: child.checkConsistency(btree, this , false);
1219: }
1220: }
1221:
1222: child.release();
1223: child = null;
1224: }
1225: } finally {
1226: if (child != null)
1227: child.release();
1228: }
1229: }
1230:
1231: private long getChildPageIdAtSlot(OpenBTree btree, int slot)
1232: throws StandardException {
1233: long child_page_id;
1234:
1235: if (slot == 0) {
1236: child_page_id = this .getLeftChildPageno();
1237: } else {
1238: this .page.fetchFieldFromSlot(slot,
1239: btree.getConglomerate().nKeyFields,
1240: child_pageno_buf);
1241: child_page_id = child_pageno_buf.getLong();
1242: }
1243:
1244: return (child_page_id);
1245: }
1246:
1247: protected ControlRow getChildPageAtSlot(OpenBTree open_btree,
1248: int slot) throws StandardException {
1249: ControlRow child_control_row;
1250:
1251: if (slot == 0) {
1252: child_control_row = this .getLeftChild(open_btree);
1253: } else {
1254: this .page.fetchFieldFromSlot(slot, open_btree
1255: .getConglomerate().nKeyFields, child_pageno_buf);
1256:
1257: child_control_row = ControlRow.Get(open_btree,
1258: child_pageno_buf.getLong());
1259: }
1260:
1261: return (child_control_row);
1262: }
1263:
1264: /**
1265: * Return the left child pointer for the page.
1266: * <p>
1267: * Leaf pages don't have children, so they override this and return null.
1268: *
1269: * @return The page which is the leftmost child of this page.
1270: *
1271: * @param open_btree The open btree to associate latches/locks with.
1272: *
1273: * @exception StandardException Standard exception policy.
1274: **/
1275: public ControlRow getLeftChild(OpenBTree open_btree)
1276: throws StandardException {
1277: return (ControlRow.Get(open_btree, this .getLeftChildPageno()));
1278: }
1279:
1280: /**
1281: * Return the right child pointer for the page.
1282: * <p>
1283: * Leaf pages don't have children, so they override this and return null.
1284: *
1285: * @return The page which is the rightmost child of this page.
1286: *
1287: * @param open_btree The open btree to associate latches/locks with.
1288: *
1289: * @exception StandardException Standard exception policy.
1290: **/
1291: protected ControlRow getRightChild(OpenBTree open_btree)
1292: throws StandardException {
1293: ControlRow right_child;
1294: int num_slots = this .page.recordCount();
1295:
1296: // if num_slots is 1 then there are no branch rows, so just follow
1297: // the left page pointer, else if num_slots is > 1 then follow the
1298: // last branch row to find the rightmost child.
1299: right_child = (num_slots == 1 ? ControlRow.Get(open_btree, this
1300: .getLeftChildPageno()) : getChildPageAtSlot(open_btree,
1301: (num_slots - 1)));
1302:
1303: return (right_child);
1304: }
1305:
1306: /**
1307: ** Return the left child page number for the page. Leaf pages
1308: ** don't have left children, so they override this and return
1309: ** null.
1310: **/
1311: long getLeftChildPageno() throws StandardException {
1312: if (this .left_child_page == null) {
1313: this .left_child_page = new SQLLongint();
1314:
1315: scratch_row[CR_LEFTCHILD] = this .left_child_page;
1316:
1317: fetchDesc.setValidColumns(CR_LEFTCHILD_BITMAP);
1318: this .page.fetchFromSlot((RecordHandle) null, CR_SLOT,
1319: scratch_row, fetchDesc, false);
1320: }
1321: return (left_child_page.getLong());
1322: }
1323:
1324: /*
1325: * TypedFormat:
1326: */
1327:
1328: /**
1329: Return my format identifier.
1330:
1331: @see org.apache.derby.iapi.services.io.TypedFormat#getTypeFormatId
1332: */
1333: public int getTypeFormatId() {
1334: return StoredFormatIds.ACCESS_BTREE_BRANCHCONTROLROW_V1_ID;
1335: }
1336:
1337: /**
1338: * Return a new template for reading a data row from the current page.
1339: * <p>
1340: * Default implementation for rows which are the same as the conglomerates
1341: * template, sub-classes can alter if underlying template is different
1342: * (for instance branch rows add an extra field at the end).
1343: *
1344: * @return Newly allocated template.
1345: *
1346: * @exception StandardException Standard exception policy.
1347: **/
1348: public DataValueDescriptor[] getRowTemplate(OpenBTree open_btree)
1349: throws StandardException {
1350: return (BranchRow.createEmptyTemplate(open_btree
1351: .getConglomerate()).getRow());
1352: }
1353:
1354: /**
1355: ** The standard toString.
1356: **/
1357: public String toString() {
1358: if (SanityManager.DEBUG) {
1359: String string = super .toString();
1360:
1361: try {
1362: string += "left child page = " + getLeftChildPageno()
1363: + ";";
1364:
1365: } catch (Throwable t) {
1366: string += "error encountered while doing ControlRow.toString()";
1367: }
1368:
1369: return (string);
1370: } else {
1371: return (null);
1372: }
1373: }
1374: }
|