0001: /* Copyright (c) 1995-2000, The Hypersonic SQL Group.
0002: * All rights reserved.
0003: *
0004: * Redistribution and use in source and binary forms, with or without
0005: * modification, are permitted provided that the following conditions are met:
0006: *
0007: * Redistributions of source code must retain the above copyright notice, this
0008: * list of conditions and the following disclaimer.
0009: *
0010: * Redistributions in binary form must reproduce the above copyright notice,
0011: * this list of conditions and the following disclaimer in the documentation
0012: * and/or other materials provided with the distribution.
0013: *
0014: * Neither the name of the Hypersonic SQL Group nor the names of its
0015: * contributors may be used to endorse or promote products derived from this
0016: * software without specific prior written permission.
0017: *
0018: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
0019: * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
0020: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
0021: * ARE DISCLAIMED. IN NO EVENT SHALL THE HYPERSONIC SQL GROUP,
0022: * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
0023: * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
0024: * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
0025: * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
0026: * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
0027: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
0028: * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
0029: *
0030: * This software consists of voluntary contributions made by many individuals
0031: * on behalf of the Hypersonic SQL Group.
0032: *
0033: *
0034: * For work added by the HSQL Development Group:
0035: *
0036: * Copyright (c) 2001-2005, The HSQL Development Group
0037: * All rights reserved.
0038: *
0039: * Redistribution and use in source and binary forms, with or without
0040: * modification, are permitted provided that the following conditions are met:
0041: *
0042: * Redistributions of source code must retain the above copyright notice, this
0043: * list of conditions and the following disclaimer.
0044: *
0045: * Redistributions in binary form must reproduce the above copyright notice,
0046: * this list of conditions and the following disclaimer in the documentation
0047: * and/or other materials provided with the distribution.
0048: *
0049: * Neither the name of the HSQL Development Group nor the names of its
0050: * contributors may be used to endorse or promote products derived from this
0051: * software without specific prior written permission.
0052: *
0053: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
0054: * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
0055: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
0056: * ARE DISCLAIMED. IN NO EVENT SHALL HSQL DEVELOPMENT GROUP, HSQLDB.ORG,
0057: * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
0058: * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
0059: * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
0060: * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
0061: * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
0062: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
0063: * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
0064: */
0065:
0066: package org.hsqldb;
0067:
0068: import java.util.NoSuchElementException;
0069:
0070: import org.hsqldb.HsqlNameManager.HsqlName;
0071: import org.hsqldb.index.RowIterator;
0072: import org.hsqldb.lib.ArrayUtil;
0073:
0074: // fredt@users 20020221 - patch 513005 by sqlbob@users - corrections
0075: // fredt@users 20020225 - patch 1.7.0 - changes to support cascading deletes
0076: // tony_lai@users 20020820 - patch 595052 - better error message
0077: // fredt@users 20021205 - patch 1.7.2 - changes to method signature
0078: // fredt@users - patch 1.80 - reworked the interface and comparison methods
0079:
0080: /**
0081: * Implementation of an AVL tree with parent pointers in nodes. Subclasses
0082: * of Node implement the tree node objects for memory or disk storage. An
0083: * Index has a root Node that is linked with other nodes using Java Object
0084: * references or file pointers, depending on Node implementation.<p>
0085: * An Index object also holds information on table columns (in the form of int
0086: * indexes) that are covered by it.(fredt@users)
0087: *
0088: * @author Thomas Mueller (Hypersonic SQL Group)
0089: * @version 1.8.0
0090: * @since Hypersonic SQL
0091: */
0092: public class Index {
0093:
0094: // types of index
0095: static final int MEMORY_INDEX = 0;
0096: static final int DISK_INDEX = 1;
0097: static final int POINTER_INDEX = 2;
0098:
0099: // fields
0100: private final HsqlName indexName;
0101: final boolean[] colCheck;
0102: private final int[] colIndex;
0103: private final int[] colTypes;
0104: final int[] pkCols;
0105: final int[] pkTypes;
0106: private final boolean isUnique; // DDL uniqueness
0107: private final boolean useRowId;
0108: final boolean isConstraint;
0109: final boolean isForward;
0110: final boolean isTemp;
0111: private Node root;
0112: private int depth;
0113: final Collation collation;
0114: static IndexRowIterator emptyIterator = new IndexRowIterator(null,
0115: null, null);
0116: IndexRowIterator updatableIterators;
0117: final boolean onCommitPreserve;
0118: final Table table;
0119:
0120: /**
0121: * Constructor declaration
0122: *
0123: *
0124: * @param name HsqlName of the index
0125: * @param table table of the index
0126: * @param column array of column indexes
0127: * @param type array of column types
0128: * @param unique is this a unique index
0129: * @param constraint does this index belonging to a constraint
0130: * @param forward is this an auto-index for an FK that refers to a table defined after this table
0131: * @param visColumns count of visible columns
0132: */
0133: Index(Database database, HsqlName name, Table table, int[] column,
0134: int[] colTypes, boolean isPk, boolean unique,
0135: boolean constraint, boolean forward, int[] pkcols,
0136: int[] pktypes, boolean temp) {
0137:
0138: this .table = table;
0139: this .indexName = name;
0140: this .colIndex = column;
0141: this .colTypes = colTypes;
0142: this .pkCols = pkcols;
0143: this .pkTypes = pktypes;
0144: isUnique = unique;
0145: isConstraint = constraint;
0146: isForward = forward;
0147: useRowId = (!isUnique && pkCols.length == 0)
0148: || (colIndex.length == 0);
0149: colCheck = table.getNewColumnCheckList();
0150:
0151: ArrayUtil.intIndexesToBooleanArray(colIndex, colCheck);
0152:
0153: updatableIterators = new IndexRowIterator(null, null, null);
0154: updatableIterators.next = updatableIterators.last = updatableIterators;
0155: collation = database.collation;
0156: isTemp = temp;
0157: onCommitPreserve = table.onCommitPreserve;
0158: }
0159:
0160: /**
0161: * Returns the HsqlName object
0162: */
0163: HsqlName getName() {
0164: return indexName;
0165: }
0166:
0167: /**
0168: * Changes index name. Used by 'alter index rename to'. Argument isquoted
0169: * is true if the name was quoted in the DDL.
0170: */
0171: void setName(String name, boolean isquoted) throws HsqlException {
0172: indexName.rename(name, isquoted);
0173: }
0174:
0175: /**
0176: * Returns the count of visible columns used
0177: */
0178: int getVisibleColumns() {
0179: return colIndex.length;
0180: }
0181:
0182: /**
0183: * Is this a UNIQUE index?
0184: */
0185: boolean isUnique() {
0186: return isUnique;
0187: }
0188:
0189: /**
0190: * Does this index belong to a constraint?
0191: */
0192: boolean isConstraint() {
0193: return isConstraint;
0194: }
0195:
0196: /**
0197: * Returns the array containing column indexes for index
0198: */
0199: int[] getColumns() {
0200: return colIndex; // todo: this gives back also primary key field(s)!
0201: }
0202:
0203: /**
0204: * Returns the array containing column indexes for index
0205: */
0206: int[] getColumnTypes() {
0207: return colTypes; // todo: this gives back also primary key field(s)!
0208: }
0209:
0210: String getColumnNameList() {
0211:
0212: String columnNameList = "";
0213:
0214: for (int j = 0; j < colIndex.length; ++j) {
0215: columnNameList += table.getColumn(colIndex[j]).columnName.statementName;
0216:
0217: if (j < colIndex.length - 1) {
0218: columnNameList += ",";
0219: }
0220: }
0221:
0222: return columnNameList;
0223: }
0224:
0225: /**
0226: * Returns the node count.
0227: */
0228: int size(Session session) throws HsqlException {
0229:
0230: int count = 0;
0231: RowIterator it = firstRow(session);
0232:
0233: while (it.hasNext()) {
0234: it.next();
0235:
0236: count++;
0237: }
0238:
0239: return count;
0240: }
0241:
0242: boolean isEmpty(Session session) {
0243: return getRoot(session) == null;
0244: }
0245:
0246: public int sizeEstimate() throws HsqlException {
0247:
0248: firstRow(null);
0249:
0250: return (int) (1L << depth);
0251: }
0252:
0253: void clearAll(Session session) {
0254:
0255: setRoot(session, null);
0256:
0257: depth = 0;
0258: updatableIterators.next = updatableIterators.last = updatableIterators;
0259: }
0260:
0261: void clearIterators() {
0262: updatableIterators.next = updatableIterators.last = updatableIterators;
0263: }
0264:
0265: void setRoot(Session session, Node node) {
0266:
0267: if (isTemp) {
0268: session.setIndexRoot(indexName, onCommitPreserve, node);
0269: } else {
0270: root = node;
0271: }
0272: }
0273:
0274: int getRoot() {
0275: return (root == null) ? -1 : root.getKey();
0276: }
0277:
0278: private Node getRoot(Session session) {
0279:
0280: if (isTemp && session != null) {
0281: return session.getIndexRoot(indexName, onCommitPreserve);
0282: } else {
0283: return root;
0284: }
0285: }
0286:
0287: /**
0288: * Insert a node into the index
0289: */
0290: void insert(Session session, Row row, int offset)
0291: throws HsqlException {
0292:
0293: Node n = getRoot(session);
0294: Node x = n;
0295: boolean isleft = true;
0296: int compare = -1;
0297:
0298: while (true) {
0299: if (n == null) {
0300: if (x == null) {
0301: setRoot(session, row.getNode(offset));
0302:
0303: return;
0304: }
0305:
0306: set(x, isleft, row.getNode(offset));
0307:
0308: break;
0309: }
0310:
0311: compare = compareRowForInsert(session, row, n.getRow());
0312:
0313: if (compare == 0) {
0314: int errorCode = Trace.VIOLATION_OF_UNIQUE_INDEX;
0315: String name = indexName.statementName;
0316:
0317: if (isConstraint) {
0318: Constraint c = table
0319: .getUniqueOrPKConstraintForIndex(this );
0320:
0321: if (c != null) {
0322: name = c.getName().name;
0323: errorCode = Trace.VIOLATION_OF_UNIQUE_CONSTRAINT;
0324: }
0325: }
0326:
0327: throw Trace.error(errorCode, new Object[] { name,
0328: getColumnNameList() });
0329: }
0330:
0331: isleft = compare < 0;
0332: x = n;
0333: n = child(x, isleft);
0334: }
0335:
0336: balance(session, x, isleft);
0337: }
0338:
0339: /**
0340: * Balances part of the tree after an alteration to the index.
0341: */
0342: private void balance(Session session, Node x, boolean isleft)
0343: throws HsqlException {
0344:
0345: while (true) {
0346: int sign = isleft ? 1 : -1;
0347:
0348: x = x.getUpdatedNode();
0349:
0350: switch (x.getBalance() * sign) {
0351:
0352: case 1:
0353: x.setBalance(0);
0354:
0355: return;
0356:
0357: case 0:
0358: x.setBalance(-sign);
0359: break;
0360:
0361: case -1:
0362: Node l = child(x, isleft);
0363:
0364: if (l.getBalance() == -sign) {
0365: replace(session, x, l);
0366: set(x, isleft, child(l, !isleft));
0367: set(l, !isleft, x);
0368:
0369: x = x.getUpdatedNode();
0370:
0371: x.setBalance(0);
0372:
0373: l = l.getUpdatedNode();
0374:
0375: l.setBalance(0);
0376: } else {
0377: Node r = child(l, !isleft);
0378:
0379: replace(session, x, r);
0380: set(l, !isleft, child(r.getUpdatedNode(), isleft));
0381: set(r, isleft, l);
0382: set(x, isleft, child(r.getUpdatedNode(), !isleft));
0383: set(r, !isleft, x);
0384:
0385: int rb = r.getUpdatedNode().getBalance();
0386:
0387: x.getUpdatedNode().setBalance(
0388: (rb == -sign) ? sign : 0);
0389: l.getUpdatedNode().setBalance(
0390: (rb == sign) ? -sign : 0);
0391: r.getUpdatedNode().setBalance(0);
0392: }
0393:
0394: return;
0395: }
0396:
0397: x = x.getUpdatedNode();
0398:
0399: if (x.isRoot()) {
0400: return;
0401: }
0402:
0403: isleft = x.isFromLeft();
0404: x = x.getParent();
0405: }
0406: }
0407:
0408: /**
0409: * Delete a node from the index
0410: */
0411: void delete(Session session, Node x) throws HsqlException {
0412:
0413: if (x == null) {
0414: return;
0415: }
0416:
0417: for (IndexRowIterator it = updatableIterators.next; it != updatableIterators; it = it.next) {
0418: it.updateForDelete(x);
0419: }
0420:
0421: Node n;
0422:
0423: if (x.getLeft() == null) {
0424: n = x.getRight();
0425: } else if (x.getRight() == null) {
0426: n = x.getLeft();
0427: } else {
0428: Node d = x;
0429:
0430: x = x.getLeft();
0431:
0432: /*
0433: // todo: this can be improved
0434:
0435: while (x.getRight() != null) {
0436: if (Trace.STOP) {
0437: Trace.stop();
0438: }
0439:
0440: x = x.getRight();
0441: }
0442: */
0443: for (Node temp = x; (temp = temp.getRight()) != null;) {
0444: x = temp;
0445: }
0446:
0447: // x will be replaced with n later
0448: n = x.getLeft();
0449:
0450: // swap d and x
0451: int b = x.getBalance();
0452:
0453: x = x.getUpdatedNode();
0454:
0455: x.setBalance(d.getBalance());
0456:
0457: d = d.getUpdatedNode();
0458:
0459: d.setBalance(b);
0460:
0461: // set x.parent
0462: Node xp = x.getParent();
0463: Node dp = d.getParent();
0464:
0465: x = x.getUpdatedNode();
0466:
0467: if (d.isRoot()) {
0468: setRoot(session, x);
0469: }
0470:
0471: x.setParent(dp);
0472:
0473: if (dp != null) {
0474: dp = dp.getUpdatedNode();
0475:
0476: if (dp.isRight(d)) {
0477: dp.setRight(x);
0478: } else {
0479: dp.setLeft(x);
0480: }
0481: }
0482:
0483: // relink d.parent, x.left, x.right
0484: d = d.getUpdatedNode();
0485:
0486: if (d.equals(xp)) {
0487: d.setParent(x);
0488:
0489: if (d.isLeft(x)) {
0490: x = x.getUpdatedNode();
0491:
0492: x.setLeft(d);
0493:
0494: Node dr = d.getRight();
0495:
0496: x = x.getUpdatedNode();
0497:
0498: x.setRight(dr);
0499: } else {
0500: x.setRight(d);
0501:
0502: Node dl = d.getLeft();
0503:
0504: x = x.getUpdatedNode();
0505:
0506: x.setLeft(dl);
0507: }
0508: } else {
0509: d.setParent(xp);
0510:
0511: xp = xp.getUpdatedNode();
0512:
0513: xp.setRight(d);
0514:
0515: Node dl = d.getLeft();
0516: Node dr = d.getRight();
0517:
0518: x = x.getUpdatedNode();
0519:
0520: x.setLeft(dl);
0521: x.setRight(dr);
0522: }
0523:
0524: x.getRight().setParent(x);
0525: x.getLeft().setParent(x);
0526:
0527: // set d.left, d.right
0528: d = d.getUpdatedNode();
0529:
0530: d.setLeft(n);
0531:
0532: if (n != null) {
0533: n = n.getUpdatedNode();
0534:
0535: n.setParent(d);
0536: }
0537:
0538: d = d.getUpdatedNode();
0539:
0540: d.setRight(null);
0541:
0542: x = d;
0543: }
0544:
0545: boolean isleft = x.isFromLeft();
0546:
0547: replace(session, x, n);
0548:
0549: n = x.getParent();
0550: x = x.getUpdatedNode();
0551:
0552: x.delete();
0553:
0554: while (n != null) {
0555: x = n;
0556:
0557: int sign = isleft ? 1 : -1;
0558:
0559: x = x.getUpdatedNode();
0560:
0561: switch (x.getBalance() * sign) {
0562:
0563: case -1:
0564: x.setBalance(0);
0565: break;
0566:
0567: case 0:
0568: x.setBalance(sign);
0569:
0570: return;
0571:
0572: case 1:
0573: Node r = child(x, !isleft);
0574: int b = r.getBalance();
0575:
0576: if (b * sign >= 0) {
0577: replace(session, x, r);
0578: set(x, !isleft, child(r, isleft));
0579: set(r, isleft, x);
0580:
0581: if (b == 0) {
0582: x = x.getUpdatedNode();
0583:
0584: x.setBalance(sign);
0585:
0586: r = r.getUpdatedNode();
0587:
0588: r.setBalance(-sign);
0589:
0590: return;
0591: }
0592:
0593: x = x.getUpdatedNode();
0594:
0595: x.setBalance(0);
0596:
0597: r = r.getUpdatedNode();
0598:
0599: r.setBalance(0);
0600:
0601: x = r;
0602: } else {
0603: Node l = child(r, isleft);
0604:
0605: replace(session, x, l);
0606:
0607: l = l.getUpdatedNode();
0608: b = l.getBalance();
0609:
0610: set(r, isleft, child(l, !isleft));
0611: set(l, !isleft, r);
0612: set(x, !isleft, child(l, isleft));
0613: set(l, isleft, x);
0614:
0615: x = x.getUpdatedNode();
0616:
0617: x.setBalance((b == sign) ? -sign : 0);
0618:
0619: r = r.getUpdatedNode();
0620:
0621: r.setBalance((b == -sign) ? sign : 0);
0622:
0623: l = l.getUpdatedNode();
0624:
0625: l.setBalance(0);
0626:
0627: x = l;
0628: }
0629: }
0630:
0631: isleft = x.isFromLeft();
0632: n = x.getParent();
0633: }
0634: }
0635:
0636: RowIterator findFirstRow(Session session, Object[] rowdata,
0637: int[] rowColMap) throws HsqlException {
0638:
0639: Node node = findNotNull(session, rowdata, rowColMap, true);
0640:
0641: return getIterator(session, node);
0642: }
0643:
0644: RowIterator findFirstRowForDelete(Session session,
0645: Object[] rowdata, int[] rowColMap) throws HsqlException {
0646:
0647: Node node = findNotNull(session, rowdata, rowColMap, true);
0648: IndexRowIterator it = getIterator(session, node);
0649:
0650: if (node != null) {
0651: updatableIterators.link(it);
0652: }
0653:
0654: return it;
0655: }
0656:
0657: /**
0658: * Finds an existing row
0659: */
0660: Row findRow(Session session, Row row) throws HsqlException {
0661:
0662: Node node = search(session, row);
0663:
0664: return node == null ? null : node.getRow();
0665: }
0666:
0667: boolean exists(Session session, Object[] rowdata, int[] rowColMap)
0668: throws HsqlException {
0669: return findNotNull(session, rowdata, rowColMap, true) != null;
0670: }
0671:
0672: RowIterator emptyIterator() {
0673: return emptyIterator;
0674: }
0675:
0676: /**
0677: * Finds a foreign key referencing rows (in child table)
0678: *
0679: * @param rowdata array containing data for the index columns
0680: * @param rowColMap map of the data to columns
0681: * @param first true if the first matching node is required, false if any node
0682: * @return matching node or null
0683: * @throws HsqlException
0684: */
0685: private Node findNotNull(Session session, Object[] rowdata,
0686: int[] rowColMap, boolean first) throws HsqlException {
0687:
0688: Node x = getRoot(session);
0689: Node n;
0690: Node result = null;
0691:
0692: if (isNull(rowdata, rowColMap)) {
0693: return null;
0694: }
0695:
0696: while (x != null) {
0697: int i = this .compareRowNonUnique(session, rowdata,
0698: rowColMap, x.getData());
0699:
0700: if (i == 0) {
0701: if (first == false) {
0702: result = x;
0703:
0704: break;
0705: } else if (result == x) {
0706: break;
0707: }
0708:
0709: result = x;
0710: n = x.getLeft();
0711: } else if (i > 0) {
0712: n = x.getRight();
0713: } else {
0714: n = x.getLeft();
0715: }
0716:
0717: if (n == null) {
0718: break;
0719: }
0720:
0721: x = n;
0722: }
0723:
0724: return result;
0725: }
0726:
0727: /**
0728: * Finds any row that matches the rowdata. Use rowColMap to map index
0729: * columns to rowdata. Limit to visible columns of data.
0730: *
0731: * @param rowdata array containing data for the index columns
0732: * @param rowColMap map of the data to columns
0733: * @return node matching node
0734: * @throws HsqlException
0735: */
0736: /*
0737: Node find(Object[] rowdata, int[] rowColMap) throws HsqlException {
0738:
0739: Node x = root;
0740:
0741: while (x != null) {
0742: int c = compareRowNonUnique(rowdata, rowColMap, x.getData());
0743:
0744: if (c == 0) {
0745: return x;
0746: } else if (c < 0) {
0747: x = x.getLeft();
0748: } else {
0749: x = x.getRight();
0750: }
0751: }
0752:
0753: return null;
0754: }
0755: */
0756:
0757: /**
0758: * Determines if a table row has a null column for any of the columns given
0759: * in the rowColMap array.
0760: */
0761: static boolean isNull(Object[] row, int[] rowColMap) {
0762:
0763: int count = rowColMap.length;
0764:
0765: for (int i = 0; i < count; i++) {
0766: if (row[rowColMap[i]] == null) {
0767: return true;
0768: }
0769: }
0770:
0771: return false;
0772: }
0773:
0774: /**
0775: * Determines if a table row has a null column for any of the indexed
0776: * columns.
0777: */
0778: boolean isNull(Object[] row) {
0779:
0780: int count = colIndex.length;
0781:
0782: for (int i = 0; i < count; i++) {
0783: int j = colIndex[i];
0784:
0785: if (row[j] == null) {
0786: return true;
0787: }
0788: }
0789:
0790: return false;
0791: }
0792:
0793: /**
0794: * Return the first node equal to the rowdata object. Use visible columns
0795: * only. The rowdata has the same column mapping as this table.
0796: *
0797: * @param rowdata array containing table row data
0798: * @return iterator
0799: * @throws HsqlException
0800: */
0801: RowIterator findFirstRow(Session session, Object[] rowdata)
0802: throws HsqlException {
0803:
0804: Node x = getRoot(session);
0805: Node found = null;
0806: boolean unique = isUnique && !isNull(rowdata);
0807:
0808: while (x != null) {
0809: int c = compareRowNonUnique(session, rowdata, colIndex, x
0810: .getData());
0811:
0812: if (c == 0) {
0813: found = x;
0814:
0815: if (unique) {
0816: break;
0817: }
0818:
0819: x = x.getLeft();
0820: } else if (c < 0) {
0821: x = x.getLeft();
0822: } else {
0823: x = x.getRight();
0824: }
0825: }
0826:
0827: return getIterator(session, found);
0828: }
0829:
0830: /**
0831: * Finds the first node that is larger or equal to the given one based
0832: * on the first column of the index only.
0833: *
0834: * @param value value to match
0835: * @param compare comparison Expression type
0836: *
0837: * @return iterator
0838: *
0839: * @throws HsqlException
0840: */
0841: RowIterator findFirstRow(Session session, Object value, int compare)
0842: throws HsqlException {
0843:
0844: boolean isEqual = compare == Expression.EQUAL
0845: || compare == Expression.IS_NULL;
0846: Node x = getRoot(session);
0847: int iTest = 1;
0848:
0849: if (compare == Expression.BIGGER) {
0850: iTest = 0;
0851: }
0852:
0853: if (value == null && !isEqual) {
0854: return emptyIterator;
0855: }
0856:
0857: /*
0858: // this method returns the correct node only with the following conditions
0859: boolean check = compare == Expression.BIGGER
0860: || compare == Expression.EQUAL
0861: || compare == Expression.BIGGER_EQUAL;
0862:
0863: if (!check) {
0864: Trace.doAssert(false, "Index.findFirst");
0865: }
0866: */
0867: while (x != null) {
0868: boolean t = Column.compare(collation, value,
0869: x.getData()[colIndex[0]], colTypes[0]) >= iTest;
0870:
0871: if (t) {
0872: Node r = x.getRight();
0873:
0874: if (r == null) {
0875: break;
0876: }
0877:
0878: x = r;
0879: } else {
0880: Node l = x.getLeft();
0881:
0882: if (l == null) {
0883: break;
0884: }
0885:
0886: x = l;
0887: }
0888: }
0889:
0890: /*
0891: while (x != null
0892: && Column.compare(value, x.getData()[colIndex_0], colType_0)
0893: >= iTest) {
0894: x = next(x);
0895: }
0896: */
0897: while (x != null) {
0898: Object colvalue = x.getData()[colIndex[0]];
0899: int result = Column.compare(collation, value, colvalue,
0900: colTypes[0]);
0901:
0902: if (result >= iTest) {
0903: x = next(x);
0904: } else {
0905: if (isEqual) {
0906: if (result != 0) {
0907: x = null;
0908: }
0909: } else if (colvalue == null) {
0910: x = next(x);
0911:
0912: continue;
0913: }
0914:
0915: break;
0916: }
0917: }
0918:
0919: return getIterator(session, x);
0920: }
0921:
0922: /**
0923: * Finds the first node where the data is not null.
0924: *
0925: * @return iterator
0926: *
0927: * @throws HsqlException
0928: */
0929: RowIterator findFirstRowNotNull(Session session)
0930: throws HsqlException {
0931:
0932: Node x = getRoot(session);
0933:
0934: while (x != null) {
0935: boolean t = Column.compare(collation, null,
0936: x.getData()[colIndex[0]], colTypes[0]) >= 0;
0937:
0938: if (t) {
0939: Node r = x.getRight();
0940:
0941: if (r == null) {
0942: break;
0943: }
0944:
0945: x = r;
0946: } else {
0947: Node l = x.getLeft();
0948:
0949: if (l == null) {
0950: break;
0951: }
0952:
0953: x = l;
0954: }
0955: }
0956:
0957: while (x != null) {
0958: Object colvalue = x.getData()[colIndex[0]];
0959:
0960: if (colvalue == null) {
0961: x = next(x);
0962: } else {
0963: break;
0964: }
0965: }
0966:
0967: return getIterator(session, x);
0968: }
0969:
0970: /**
0971: * Returns the row for the first node of the index
0972: *
0973: * @return Iterator for first row
0974: *
0975: * @throws HsqlException
0976: */
0977: RowIterator firstRow(Session session) throws HsqlException {
0978:
0979: depth = 0;
0980:
0981: Node x = getRoot(session);
0982: Node l = x;
0983:
0984: while (l != null) {
0985: x = l;
0986: l = x.getLeft();
0987:
0988: depth++;
0989: }
0990:
0991: return getIterator(session, x);
0992: }
0993:
0994: /**
0995: * Returns the row for the last node of the index
0996: *
0997: * @return last row
0998: *
0999: * @throws HsqlException
1000: */
1001: Row lastRow(Session session) throws HsqlException {
1002:
1003: Node x = getRoot(session);
1004: Node l = x;
1005:
1006: while (l != null) {
1007: x = l;
1008: l = x.getRight();
1009: }
1010:
1011: return x == null ? null : x.getRow();
1012: }
1013:
1014: /**
1015: * Returns the node after the given one
1016: *
1017: * @param x node
1018: *
1019: * @return next node
1020: *
1021: * @throws HsqlException
1022: */
1023: Node next(Node x) throws HsqlException {
1024:
1025: if (x == null) {
1026: return null;
1027: }
1028:
1029: Node r = x.getRight();
1030:
1031: if (r != null) {
1032: x = r;
1033:
1034: Node l = x.getLeft();
1035:
1036: while (l != null) {
1037: x = l;
1038: l = x.getLeft();
1039: }
1040:
1041: return x;
1042: }
1043:
1044: Node ch = x;
1045:
1046: x = x.getParent();
1047:
1048: while (x != null && ch.equals(x.getRight())) {
1049: ch = x;
1050: x = x.getParent();
1051: }
1052:
1053: return x;
1054: }
1055:
1056: /**
1057: * Returns either child node
1058: *
1059: * @param x node
1060: * @param isleft boolean
1061: *
1062: * @return child node
1063: *
1064: * @throws HsqlException
1065: */
1066: private Node child(Node x, boolean isleft) throws HsqlException {
1067: return isleft ? x.getLeft() : x.getRight();
1068: }
1069:
1070: /**
1071: * Replace two nodes
1072: *
1073: * @param x node
1074: * @param n node
1075: *
1076: * @throws HsqlException
1077: */
1078: private void replace(Session session, Node x, Node n)
1079: throws HsqlException {
1080:
1081: if (x.isRoot()) {
1082: if (n != null) {
1083: n = n.getUpdatedNode();
1084:
1085: n.setParent(null);
1086: }
1087:
1088: setRoot(session, n);
1089: } else {
1090: set(x.getParent(), x.isFromLeft(), n);
1091: }
1092: }
1093:
1094: /**
1095: * Set a node as child of another
1096: *
1097: * @param x parent node
1098: * @param isleft boolean
1099: * @param n child node
1100: *
1101: * @throws HsqlException
1102: */
1103: private void set(Node x, boolean isleft, Node n)
1104: throws HsqlException {
1105:
1106: x = x.getUpdatedNode();
1107:
1108: if (isleft) {
1109: x.setLeft(n);
1110: } else {
1111: x.setRight(n);
1112: }
1113:
1114: if (n != null) {
1115: n = n.getUpdatedNode();
1116:
1117: n.setParent(x);
1118: }
1119: }
1120:
1121: /**
1122: * Find a node with matching data
1123: *
1124: * @param row row data
1125: *
1126: * @return matching node
1127: *
1128: * @throws HsqlException
1129: */
1130: private Node search(Session session, Row row) throws HsqlException {
1131:
1132: Object[] d = row.getData();
1133: Node x = getRoot(session);
1134:
1135: while (x != null) {
1136: int c = compareRowForInsert(session, row, x.getRow());
1137:
1138: if (c == 0) {
1139: return x;
1140: } else if (c < 0) {
1141: x = x.getLeft();
1142: } else {
1143: x = x.getRight();
1144: }
1145: }
1146:
1147: return null;
1148: }
1149:
1150: /**
1151: * Compares two table rows based on the columns of this index. The rowColMap
1152: * parameter specifies which columns of the other table are to be compared
1153: * with the colIndex columns of this index. The rowColMap can cover all
1154: * or only some columns of this index.
1155: *
1156: * @param a row from another table
1157: * @param rowColMap column indexes in the other table
1158: * @param b a full row in this table
1159: *
1160: * @return comparison result, -1,0,+1
1161: * @throws HsqlException
1162: */
1163: int compareRowNonUnique(Session session, Object[] a,
1164: int[] rowColMap, Object[] b) throws HsqlException {
1165:
1166: int i = Column.compare(collation, a[rowColMap[0]],
1167: b[colIndex[0]], colTypes[0]);
1168:
1169: if (i != 0) {
1170: return i;
1171: }
1172:
1173: int fieldcount = rowColMap.length;
1174:
1175: for (int j = 1; j < fieldcount; j++) {
1176: i = Column.compare(collation, a[rowColMap[j]],
1177: b[colIndex[j]], colTypes[j]);
1178:
1179: if (i != 0) {
1180: return i;
1181: }
1182: }
1183:
1184: return 0;
1185: }
1186:
1187: /**
1188: * compares two full table rows based on a set of columns
1189: *
1190: * @param a a full row
1191: * @param b a full row
1192: * @param cols array of column indexes to compare
1193: *
1194: * @return comparison result, -1,0,+1
1195: * @throws HsqlException
1196: */
1197: static int compareRows(Session session, Object[] a, Object[] b,
1198: int[] cols, int[] coltypes) throws HsqlException {
1199:
1200: int fieldcount = cols.length;
1201:
1202: for (int j = 0; j < fieldcount; j++) {
1203: int i = Column.compare(session.database.collation,
1204: a[cols[j]], b[cols[j]], coltypes[cols[j]]);
1205:
1206: if (i != 0) {
1207: return i;
1208: }
1209: }
1210:
1211: return 0;
1212: }
1213:
1214: /**
1215: * Compare two rows of the table for inserting rows into unique indexes
1216: *
1217: * @param a data
1218: * @param b data
1219: *
1220: * @return comparison result, -1,0,+1
1221: *
1222: * @throws HsqlException
1223: */
1224: private int compareRowForInsert(Session session, Row newRow,
1225: Row existingRow) throws HsqlException {
1226:
1227: Object[] a = newRow.getData();
1228: Object[] b = existingRow.getData();
1229: int j = 0;
1230: boolean hasNull = false;
1231:
1232: for (; j < colIndex.length; j++) {
1233: Object currentvalue = a[colIndex[j]];
1234: int i = Column.compare(collation, currentvalue,
1235: b[colIndex[j]], colTypes[j]);
1236:
1237: if (i != 0) {
1238: return i;
1239: }
1240:
1241: if (currentvalue == null) {
1242: hasNull = true;
1243: }
1244: }
1245:
1246: if (isUnique && !useRowId && !hasNull) {
1247: return 0;
1248: }
1249:
1250: for (j = 0; j < pkCols.length; j++) {
1251: Object currentvalue = a[pkCols[j]];
1252: int i = Column.compare(collation, currentvalue,
1253: b[pkCols[j]], pkTypes[j]);
1254:
1255: if (i != 0) {
1256: return i;
1257: }
1258: }
1259:
1260: if (useRowId) {
1261: int difference = newRow.getPos() - existingRow.getPos();
1262:
1263: if (difference < 0) {
1264: difference = -1;
1265: } else if (difference > 0) {
1266: difference = 1;
1267: }
1268:
1269: return difference;
1270: }
1271:
1272: return 0;
1273: }
1274:
1275: /**
1276: * Returns a value indicating the order of different types of index in
1277: * the list of indexes for a table. The position of the groups of Indexes
1278: * in the list in ascending order is as follows:
1279: *
1280: * primary key index
1281: * unique constraint indexes
1282: * autogenerated foreign key indexes for FK's that reference this table or
1283: * tables created before this table
1284: * user created indexes (CREATE INDEX)
1285: * autogenerated foreign key indexes for FK's that reference tables created
1286: * after this table
1287: *
1288: * Among a group of indexes, the order is based on the order of creation
1289: * of the index.
1290: *
1291: * @return ordinal value
1292: */
1293: int getIndexOrderValue() {
1294:
1295: int value = 0;
1296:
1297: if (isConstraint) {
1298: return isForward ? 4 : isUnique ? 0 : 1;
1299: } else {
1300: return 2;
1301: }
1302: }
1303:
1304: private IndexRowIterator getIterator(Session session, Node x) {
1305:
1306: if (x == null) {
1307: return emptyIterator;
1308: } else {
1309: IndexRowIterator it = new IndexRowIterator(session, this , x);
1310:
1311: return it;
1312: }
1313: }
1314:
1315: static class IndexRowIterator implements RowIterator {
1316:
1317: Session session;
1318: Index index;
1319: Node nextnode;
1320: protected IndexRowIterator last;
1321: protected IndexRowIterator next;
1322:
1323: /**
1324: * When session == null, rows from all sessions are returned
1325: */
1326: private IndexRowIterator(Session session, Index index, Node node) {
1327:
1328: if (index == null) {
1329: return;
1330: }
1331:
1332: this .session = session;
1333: this .index = index;
1334: this .nextnode = node;
1335: }
1336:
1337: public boolean hasNext() {
1338: return nextnode != null;
1339: }
1340:
1341: public Row next() {
1342:
1343: if (hasNext()) {
1344: try {
1345: Row row = nextnode.getRow();
1346:
1347: nextnode = index.next(nextnode);
1348:
1349: return row;
1350: } catch (Exception e) {
1351: throw new NoSuchElementException(e.getMessage());
1352: }
1353: } else {
1354: return null;
1355: }
1356: }
1357:
1358: void updateForDelete(Node node) {
1359:
1360: try {
1361: if (node.equals(nextnode)) {
1362: nextnode = index.next(node);
1363: }
1364: } catch (Exception e) {
1365: }
1366: }
1367:
1368: void link(IndexRowIterator other) {
1369:
1370: other.next = next;
1371: other.last = this ;
1372: next.last = other;
1373: next = other;
1374: }
1375:
1376: public void release() {
1377:
1378: if (last != null) {
1379: last.next = next;
1380: }
1381:
1382: if (next != null) {
1383: next.last = last;
1384: }
1385: }
1386: }
1387: }
|