Source Code Cross Referenced for Index.java in  » Database-DBMS » hsql » org » hsqldb » Java Source Code / Java DocumentationJava Source Code and Java Documentation

Java Source Code / Java Documentation
1. 6.0 JDK Core
2. 6.0 JDK Modules
3. 6.0 JDK Modules com.sun
4. 6.0 JDK Modules com.sun.java
5. 6.0 JDK Modules sun
6. 6.0 JDK Platform
7. Ajax
8. Apache Harmony Java SE
9. Aspect oriented
10. Authentication Authorization
11. Blogger System
12. Build
13. Byte Code
14. Cache
15. Chart
16. Chat
17. Code Analyzer
18. Collaboration
19. Content Management System
20. Database Client
21. Database DBMS
22. Database JDBC Connection Pool
23. Database ORM
24. Development
25. EJB Server geronimo
26. EJB Server GlassFish
27. EJB Server JBoss 4.2.1
28. EJB Server resin 3.1.5
29. ERP CRM Financial
30. ESB
31. Forum
32. GIS
33. Graphic Library
34. Groupware
35. HTML Parser
36. IDE
37. IDE Eclipse
38. IDE Netbeans
39. Installer
40. Internationalization Localization
41. Inversion of Control
42. Issue Tracking
43. J2EE
44. JBoss
45. JMS
46. JMX
47. Library
48. Mail Clients
49. Net
50. Parser
51. PDF
52. Portal
53. Profiler
54. Project Management
55. Report
56. RSS RDF
57. Rule Engine
58. Science
59. Scripting
60. Search Engine
61. Security
62. Sevlet Container
63. Source Control
64. Swing Library
65. Template Engine
66. Test Coverage
67. Testing
68. UML
69. Web Crawler
70. Web Framework
71. Web Mail
72. Web Server
73. Web Services
74. Web Services apache cxf 2.0.1
75. Web Services AXIS2
76. Wiki Engine
77. Workflow Engines
78. XML
79. XML UI
Java
Java Tutorial
Java Open Source
Jar File Download
Java Articles
Java Products
Java by API
Photoshop Tutorials
Maya Tutorials
Flash Tutorials
3ds-Max Tutorials
Illustrator Tutorials
GIMP Tutorials
C# / C Sharp
C# / CSharp Tutorial
C# / CSharp Open Source
ASP.Net
ASP.NET Tutorial
JavaScript DHTML
JavaScript Tutorial
JavaScript Reference
HTML / CSS
HTML CSS Reference
C / ANSI-C
C Tutorial
C++
C++ Tutorial
Ruby
PHP
Python
Python Tutorial
Python Open Source
SQL Server / T-SQL
SQL Server / T-SQL Tutorial
Oracle PL / SQL
Oracle PL/SQL Tutorial
PostgreSQL
SQL / MySQL
MySQL Tutorial
VB.Net
VB.Net Tutorial
Flash / Flex / ActionScript
VBA / Excel / Access / Word
XML
XML Tutorial
Microsoft Office PowerPoint 2007 Tutorial
Microsoft Office Excel 2007 Tutorial
Microsoft Office Word 2007 Tutorial
Java Source Code / Java Documentation » Database DBMS » hsql » org.hsqldb 
Source Cross Referenced  Class Diagram Java Document (Java Doc) 


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:        }
www.java2java.com | Contact Us
Copyright 2009 - 12 Demo Source and Support. All rights reserved.
All other trademarks are property of their respective owners.