KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > hsqldb > Index


1 /* Copyright (c) 1995-2000, The Hypersonic SQL Group.
2  * All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions are met:
6  *
7  * Redistributions of source code must retain the above copyright notice, this
8  * list of conditions and the following disclaimer.
9  *
10  * Redistributions in binary form must reproduce the above copyright notice,
11  * this list of conditions and the following disclaimer in the documentation
12  * and/or other materials provided with the distribution.
13  *
14  * Neither the name of the Hypersonic SQL Group nor the names of its
15  * contributors may be used to endorse or promote products derived from this
16  * software without specific prior written permission.
17  *
18  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
19  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21  * ARE DISCLAIMED. IN NO EVENT SHALL THE HYPERSONIC SQL GROUP,
22  * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
23  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
24  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
25  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
26  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
28  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29  *
30  * This software consists of voluntary contributions made by many individuals
31  * on behalf of the Hypersonic SQL Group.
32  *
33  *
34  * For work added by the HSQL Development Group:
35  *
36  * Copyright (c) 2001-2005, The HSQL Development Group
37  * All rights reserved.
38  *
39  * Redistribution and use in source and binary forms, with or without
40  * modification, are permitted provided that the following conditions are met:
41  *
42  * Redistributions of source code must retain the above copyright notice, this
43  * list of conditions and the following disclaimer.
44  *
45  * Redistributions in binary form must reproduce the above copyright notice,
46  * this list of conditions and the following disclaimer in the documentation
47  * and/or other materials provided with the distribution.
48  *
49  * Neither the name of the HSQL Development Group nor the names of its
50  * contributors may be used to endorse or promote products derived from this
51  * software without specific prior written permission.
52  *
53  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
54  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
55  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
56  * ARE DISCLAIMED. IN NO EVENT SHALL HSQL DEVELOPMENT GROUP, HSQLDB.ORG,
57  * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
58  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
59  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
60  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
61  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
62  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
63  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
64  */

65
66
67 package org.hsqldb;
68
69 import java.util.NoSuchElementException JavaDoc;
70
71 import org.hsqldb.HsqlNameManager.HsqlName;
72 import org.hsqldb.index.RowIterator;
73 import org.hsqldb.lib.ArrayUtil;
74
75 // fredt@users 20020221 - patch 513005 by sqlbob@users - corrections
76
// fredt@users 20020225 - patch 1.7.0 - changes to support cascading deletes
77
// tony_lai@users 20020820 - patch 595052 - better error message
78
// fredt@users 20021205 - patch 1.7.2 - changes to method signature
79
// fredt@users - patch 1.80 - reworked the interface and comparison methods
80

81 /**
82  * Implementation of an AVL tree with parent pointers in nodes. Subclasses
83  * of Node implement the tree node objects for memory or disk storage. An
84  * Index has a root Node that is linked with other nodes using Java Object
85  * references or file pointers, depending on Node implementation.<p>
86  * An Index object also holds information on table columns (in the form of int
87  * indexes) that are covered by it.(fredt@users)
88  *
89  * @author Thomas Mueller (Hypersonic SQL Group)
90  * @version 1.8.0
91  * @since Hypersonic SQL
92  */

93 public class Index {
94
95     // types of index
96
static final int MEMORY_INDEX = 0;
97     static final int DISK_INDEX = 1;
98     static final int POINTER_INDEX = 2;
99
100     // fields
101
private final HsqlName indexName;
102     final boolean[] colCheck;
103     private final int[] colIndex;
104     private final int[] colTypes;
105     final int[] pkCols;
106     final int[] pkTypes;
107     private final boolean isUnique; // DDL uniqueness
108
private final boolean useRowId;
109     final boolean isConstraint;
110     final boolean isForward;
111     final boolean isTemp;
112     private Node root;
113     private int depth;
114     final Collation collation;
115     static IndexRowIterator emptyIterator = new IndexRowIterator(null, null,
116         null);
117     IndexRowIterator updatableIterators;
118     final boolean onCommitPreserve;
119     final Table table;
120
121     /**
122      * Constructor declaration
123      *
124      *
125      * @param name HsqlName of the index
126      * @param table table of the index
127      * @param column array of column indexes
128      * @param type array of column types
129      * @param unique is this a unique index
130      * @param constraint does this index belonging to a constraint
131      * @param forward is this an auto-index for an FK that refers to a table defined after this table
132      * @param visColumns count of visible columns
133      */

134     Index(Database database, HsqlName name, Table table, int[] column,
135             int[] colTypes, boolean isPk, boolean unique, boolean constraint,
136             boolean forward, int[] pkcols, int[] pktypes, boolean temp) {
137
138         this.table = table;
139         this.indexName = name;
140         this.colIndex = column;
141         this.colTypes = colTypes;
142         this.pkCols = pkcols;
143         this.pkTypes = pktypes;
144         isUnique = unique;
145         isConstraint = constraint;
146         isForward = forward;
147         useRowId = (!isUnique && pkCols.length == 0)
148                    || (colIndex.length == 0);
149         colCheck = table.getNewColumnCheckList();
150
151         ArrayUtil.intIndexesToBooleanArray(colIndex, colCheck);
152
153         updatableIterators = new IndexRowIterator(null, null, null);
154         updatableIterators.next = updatableIterators.last =
155             updatableIterators;
156         collation = database.collation;
157         isTemp = temp;
158         onCommitPreserve = table.onCommitPreserve;
159     }
160
161     /**
162      * Returns the HsqlName object
163      */

164     HsqlName getName() {
165         return indexName;
166     }
167
168     /**
169      * Changes index name. Used by 'alter index rename to'. Argument isquoted
170      * is true if the name was quoted in the DDL.
171      */

172     void setName(String JavaDoc name, boolean isquoted) throws HsqlException {
173         indexName.rename(name, isquoted);
174     }
175
176     /**
177      * Returns the count of visible columns used
178      */

179     int getVisibleColumns() {
180         return colIndex.length;
181     }
182
183     /**
184      * Is this a UNIQUE index?
185      */

186     boolean isUnique() {
187         return isUnique;
188     }
189
190     /**
191      * Does this index belong to a constraint?
192      */

193     boolean isConstraint() {
194         return isConstraint;
195     }
196
197     /**
198      * Returns the array containing column indexes for index
199      */

200     int[] getColumns() {
201         return colIndex; // todo: this gives back also primary key field(s)!
202
}
203
204     /**
205      * Returns the array containing column indexes for index
206      */

207     int[] getColumnTypes() {
208         return colTypes; // todo: this gives back also primary key field(s)!
209
}
210
211     String JavaDoc getColumnNameList() {
212
213         String JavaDoc columnNameList = "";
214
215         for (int j = 0; j < colIndex.length; ++j) {
216             columnNameList +=
217                 table.getColumn(colIndex[j]).columnName.statementName;
218
219             if (j < colIndex.length - 1) {
220                 columnNameList += ",";
221             }
222         }
223
224         return columnNameList;
225     }
226
227     /**
228      * Returns the node count.
229      */

230     int size(Session session) throws HsqlException {
231
232         int count = 0;
233         RowIterator it = firstRow(session);
234
235         while (it.hasNext()) {
236             it.next();
237
238             count++;
239         }
240
241         return count;
242     }
243
244     boolean isEmpty(Session session) {
245         return getRoot(session) == null;
246     }
247
248     public int sizeEstimate() throws HsqlException {
249
250         firstRow(null);
251
252         return (int) (1L << depth);
253     }
254
255     void clearAll(Session session) {
256
257         setRoot(session, null);
258
259         depth = 0;
260         updatableIterators.next = updatableIterators.last =
261             updatableIterators;
262     }
263
264     void clearIterators() {
265         updatableIterators.next = updatableIterators.last =
266             updatableIterators;
267     }
268
269     void setRoot(Session session, Node node) {
270
271         if (isTemp) {
272             session.setIndexRoot(indexName, onCommitPreserve, node);
273         } else {
274             root = node;
275         }
276     }
277
278     int getRoot() {
279         return (root == null) ? -1
280                               : root.getKey();
281     }
282
283     private Node getRoot(Session session) {
284
285         if (isTemp && session != null) {
286             return session.getIndexRoot(indexName, onCommitPreserve);
287         } else {
288             return root;
289         }
290     }
291
292     /**
293      * Insert a node into the index
294      */

295     void insert(Session session, Row row, int offset) throws HsqlException {
296
297         Node n = getRoot(session);
298         Node x = n;
299         boolean isleft = true;
300         int compare = -1;
301
302         while (true) {
303             if (n == null) {
304                 if (x == null) {
305                     setRoot(session, row.getNode(offset));
306
307                     return;
308                 }
309
310                 set(x, isleft, row.getNode(offset));
311
312                 break;
313             }
314
315             compare = compareRowForInsert(session, row, n.getRow());
316
317             if (compare == 0) {
318                 int errorCode = Trace.VIOLATION_OF_UNIQUE_INDEX;
319                 String JavaDoc name = indexName.statementName;
320
321                 if (isConstraint) {
322                     Constraint c =
323                         table.getUniqueOrPKConstraintForIndex(this);
324
325                     if (c != null) {
326                         name = c.getName().name;
327                         errorCode = Trace.VIOLATION_OF_UNIQUE_CONSTRAINT;
328                     }
329                 }
330
331                 throw Trace.error(errorCode, new Object JavaDoc[] {
332                     name, getColumnNameList()
333                 });
334             }
335
336             isleft = compare < 0;
337             x = n;
338             n = child(x, isleft);
339         }
340
341         balance(session, x, isleft);
342     }
343
344     /**
345      * Balances part of the tree after an alteration to the index.
346      */

347     private void balance(Session session, Node x,
348                          boolean isleft) throws HsqlException {
349
350         while (true) {
351             int sign = isleft ? 1
352                               : -1;
353
354             x = x.getUpdatedNode();
355
356             switch (x.getBalance() * sign) {
357
358                 case 1 :
359                     x.setBalance(0);
360
361                     return;
362
363                 case 0 :
364                     x.setBalance(-sign);
365                     break;
366
367                 case -1 :
368                     Node l = child(x, isleft);
369
370                     if (l.getBalance() == -sign) {
371                         replace(session, x, l);
372                         set(x, isleft, child(l, !isleft));
373                         set(l, !isleft, x);
374
375                         x = x.getUpdatedNode();
376
377                         x.setBalance(0);
378
379                         l = l.getUpdatedNode();
380
381                         l.setBalance(0);
382                     } else {
383                         Node r = child(l, !isleft);
384
385                         replace(session, x, r);
386                         set(l, !isleft, child(r.getUpdatedNode(), isleft));
387                         set(r, isleft, l);
388                         set(x, isleft, child(r.getUpdatedNode(), !isleft));
389                         set(r, !isleft, x);
390
391                         int rb = r.getUpdatedNode().getBalance();
392
393                         x.getUpdatedNode().setBalance((rb == -sign) ? sign
394                                                                     : 0);
395                         l.getUpdatedNode().setBalance((rb == sign) ? -sign
396                                                                    : 0);
397                         r.getUpdatedNode().setBalance(0);
398                     }
399
400                     return;
401             }
402
403             x = x.getUpdatedNode();
404
405             if (x.isRoot()) {
406                 return;
407             }
408
409             isleft = x.isFromLeft();
410             x = x.getParent();
411         }
412     }
413
414     /**
415      * Delete a node from the index
416      */

417     void delete(Session session, Node x) throws HsqlException {
418
419         if (x == null) {
420             return;
421         }
422
423         for (IndexRowIterator it = updatableIterators.next;
424                 it != updatableIterators; it = it.next) {
425             it.updateForDelete(x);
426         }
427
428         Node n;
429
430         if (x.getLeft() == null) {
431             n = x.getRight();
432         } else if (x.getRight() == null) {
433             n = x.getLeft();
434         } else {
435             Node d = x;
436
437             x = x.getLeft();
438
439 /*
440             // todo: this can be improved
441
442             while (x.getRight() != null) {
443                 if (Trace.STOP) {
444                     Trace.stop();
445                 }
446
447                 x = x.getRight();
448             }
449 */

450             for (Node temp = x; (temp = temp.getRight()) != null; ) {
451                 x = temp;
452             }
453
454             // x will be replaced with n later
455
n = x.getLeft();
456
457             // swap d and x
458
int b = x.getBalance();
459
460             x = x.getUpdatedNode();
461
462             x.setBalance(d.getBalance());
463
464             d = d.getUpdatedNode();
465
466             d.setBalance(b);
467
468             // set x.parent
469
Node xp = x.getParent();
470             Node dp = d.getParent();
471
472             x = x.getUpdatedNode();
473
474             if (d.isRoot()) {
475                 setRoot(session, x);
476             }
477
478             x.setParent(dp);
479
480             if (dp != null) {
481                 dp = dp.getUpdatedNode();
482
483                 if (dp.isRight(d)) {
484                     dp.setRight(x);
485                 } else {
486                     dp.setLeft(x);
487                 }
488             }
489
490             // relink d.parent, x.left, x.right
491
d = d.getUpdatedNode();
492
493             if (d.equals(xp)) {
494                 d.setParent(x);
495
496                 if (d.isLeft(x)) {
497                     x = x.getUpdatedNode();
498
499                     x.setLeft(d);
500
501                     Node dr = d.getRight();
502
503                     x = x.getUpdatedNode();
504
505                     x.setRight(dr);
506                 } else {
507                     x.setRight(d);
508
509                     Node dl = d.getLeft();
510
511                     x = x.getUpdatedNode();
512
513                     x.setLeft(dl);
514                 }
515             } else {
516                 d.setParent(xp);
517
518                 xp = xp.getUpdatedNode();
519
520                 xp.setRight(d);
521
522                 Node dl = d.getLeft();
523                 Node dr = d.getRight();
524
525                 x = x.getUpdatedNode();
526
527                 x.setLeft(dl);
528                 x.setRight(dr);
529             }
530
531             x.getRight().setParent(x);
532             x.getLeft().setParent(x);
533
534             // set d.left, d.right
535
d = d.getUpdatedNode();
536
537             d.setLeft(n);
538
539             if (n != null) {
540                 n = n.getUpdatedNode();
541
542                 n.setParent(d);
543             }
544
545             d = d.getUpdatedNode();
546
547             d.setRight(null);
548
549             x = d;
550         }
551
552         boolean isleft = x.isFromLeft();
553
554         replace(session, x, n);
555
556         n = x.getParent();
557         x = x.getUpdatedNode();
558
559         x.delete();
560
561         while (n != null) {
562             x = n;
563
564             int sign = isleft ? 1
565                               : -1;
566
567             x = x.getUpdatedNode();
568
569             switch (x.getBalance() * sign) {
570
571                 case -1 :
572                     x.setBalance(0);
573                     break;
574
575                 case 0 :
576                     x.setBalance(sign);
577
578                     return;
579
580                 case 1 :
581                     Node r = child(x, !isleft);
582                     int b = r.getBalance();
583
584                     if (b * sign >= 0) {
585                         replace(session, x, r);
586                         set(x, !isleft, child(r, isleft));
587                         set(r, isleft, x);
588
589                         if (b == 0) {
590                             x = x.getUpdatedNode();
591
592                             x.setBalance(sign);
593
594                             r = r.getUpdatedNode();
595
596                             r.setBalance(-sign);
597
598                             return;
599                         }
600
601                         x = x.getUpdatedNode();
602
603                         x.setBalance(0);
604
605                         r = r.getUpdatedNode();
606
607                         r.setBalance(0);
608
609                         x = r;
610                     } else {
611                         Node l = child(r, isleft);
612
613                         replace(session, x, l);
614
615                         l = l.getUpdatedNode();
616                         b = l.getBalance();
617
618                         set(r, isleft, child(l, !isleft));
619                         set(l, !isleft, r);
620                         set(x, !isleft, child(l, isleft));
621                         set(l, isleft, x);
622
623                         x = x.getUpdatedNode();
624
625                         x.setBalance((b == sign) ? -sign
626                                                  : 0);
627
628                         r = r.getUpdatedNode();
629
630                         r.setBalance((b == -sign) ? sign
631                                                   : 0);
632
633                         l = l.getUpdatedNode();
634
635                         l.setBalance(0);
636
637                         x = l;
638                     }
639             }
640
641             isleft = x.isFromLeft();
642             n = x.getParent();
643         }
644     }
645
646     RowIterator findFirstRow(Session session, Object JavaDoc[] rowdata,
647                              int[] rowColMap) throws HsqlException {
648
649         Node node = findNotNull(session, rowdata, rowColMap, true);
650
651         return getIterator(session, node);
652     }
653
654     RowIterator findFirstRowForDelete(Session session, Object JavaDoc[] rowdata,
655                                       int[] rowColMap) throws HsqlException {
656
657         Node node = findNotNull(session, rowdata, rowColMap, true);
658         IndexRowIterator it = getIterator(session, node);
659
660         if (node != null) {
661             updatableIterators.link(it);
662         }
663
664         return it;
665     }
666
667     /**
668      * Finds an existing row
669      */

670     Row findRow(Session session, Row row) throws HsqlException {
671
672         Node node = search(session, row);
673
674         return node == null ? null
675                             : node.getRow();
676     }
677
678     boolean exists(Session session, Object JavaDoc[] rowdata,
679                    int[] rowColMap) throws HsqlException {
680         return findNotNull(session, rowdata, rowColMap, true) != null;
681     }
682
683     RowIterator emptyIterator() {
684         return emptyIterator;
685     }
686
687     /**
688      * Finds a foreign key referencing rows (in child table)
689      *
690      * @param rowdata array containing data for the index columns
691      * @param rowColMap map of the data to columns
692      * @param first true if the first matching node is required, false if any node
693      * @return matching node or null
694      * @throws HsqlException
695      */

696     private Node findNotNull(Session session, Object JavaDoc[] rowdata,
697                              int[] rowColMap,
698                              boolean first) throws HsqlException {
699
700         Node x = getRoot(session);
701         Node n;
702         Node result = null;
703
704         if (isNull(rowdata, rowColMap)) {
705             return null;
706         }
707
708         while (x != null) {
709             int i = this.compareRowNonUnique(session, rowdata, rowColMap,
710                                              x.getData());
711
712             if (i == 0) {
713                 if (first == false) {
714                     result = x;
715
716                     break;
717                 } else if (result == x) {
718                     break;
719                 }
720
721                 result = x;
722                 n = x.getLeft();
723             } else if (i > 0) {
724                 n = x.getRight();
725             } else {
726                 n = x.getLeft();
727             }
728
729             if (n == null) {
730                 break;
731             }
732
733             x = n;
734         }
735
736         return result;
737     }
738
739     /**
740      * Finds any row that matches the rowdata. Use rowColMap to map index
741      * columns to rowdata. Limit to visible columns of data.
742      *
743      * @param rowdata array containing data for the index columns
744      * @param rowColMap map of the data to columns
745      * @return node matching node
746      * @throws HsqlException
747      */

748 /*
749     Node find(Object[] rowdata, int[] rowColMap) throws HsqlException {
750
751         Node x = root;
752
753         while (x != null) {
754             int c = compareRowNonUnique(rowdata, rowColMap, x.getData());
755
756             if (c == 0) {
757                 return x;
758             } else if (c < 0) {
759                 x = x.getLeft();
760             } else {
761                 x = x.getRight();
762             }
763         }
764
765         return null;
766     }
767 */

768
769     /**
770      * Determines if a table row has a null column for any of the columns given
771      * in the rowColMap array.
772      */

773     static boolean isNull(Object JavaDoc[] row, int[] rowColMap) {
774
775         int count = rowColMap.length;
776
777         for (int i = 0; i < count; i++) {
778             if (row[rowColMap[i]] == null) {
779                 return true;
780             }
781         }
782
783         return false;
784     }
785
786     /**
787      * Determines if a table row has a null column for any of the indexed
788      * columns.
789      */

790     boolean isNull(Object JavaDoc[] row) {
791
792         int count = colIndex.length;
793
794         for (int i = 0; i < count; i++) {
795             int j = colIndex[i];
796
797             if (row[j] == null) {
798                 return true;
799             }
800         }
801
802         return false;
803     }
804
805     /**
806      * Return the first node equal to the rowdata object. Use visible columns
807      * only. The rowdata has the same column mapping as this table.
808      *
809      * @param rowdata array containing table row data
810      * @return iterator
811      * @throws HsqlException
812      */

813     RowIterator findFirstRow(Session session,
814                              Object JavaDoc[] rowdata) throws HsqlException {
815
816         Node x = getRoot(session);
817         Node found = null;
818         boolean unique = isUnique &&!isNull(rowdata);
819
820         while (x != null) {
821             int c = compareRowNonUnique(session, rowdata, colIndex,
822                                         x.getData());
823
824             if (c == 0) {
825                 found = x;
826
827                 if (unique) {
828                     break;
829                 }
830
831                 x = x.getLeft();
832             } else if (c < 0) {
833                 x = x.getLeft();
834             } else {
835                 x = x.getRight();
836             }
837         }
838
839         return getIterator(session, found);
840     }
841
842     /**
843      * Finds the first node that is larger or equal to the given one based
844      * on the first column of the index only.
845      *
846      * @param value value to match
847      * @param compare comparison Expression type
848      *
849      * @return iterator
850      *
851      * @throws HsqlException
852      */

853     RowIterator findFirstRow(Session session, Object JavaDoc value,
854                              int compare) throws HsqlException {
855
856         boolean isEqual = compare == Expression.EQUAL
857                           || compare == Expression.IS_NULL;
858         Node x = getRoot(session);
859         int iTest = 1;
860
861         if (compare == Expression.BIGGER) {
862             iTest = 0;
863         }
864
865         if (value == null &&!isEqual) {
866             return emptyIterator;
867         }
868
869 /*
870         // this method returns the correct node only with the following conditions
871         boolean check = compare == Expression.BIGGER
872                         || compare == Expression.EQUAL
873                         || compare == Expression.BIGGER_EQUAL;
874
875         if (!check) {
876             Trace.doAssert(false, "Index.findFirst");
877         }
878 */

879         while (x != null) {
880             boolean t =
881                 Column.compare(
882                     collation, value, x.getData()[colIndex[0]],
883                     colTypes[0]) >= iTest;
884
885             if (t) {
886                 Node r = x.getRight();
887
888                 if (r == null) {
889                     break;
890                 }
891
892                 x = r;
893             } else {
894                 Node l = x.getLeft();
895
896                 if (l == null) {
897                     break;
898                 }
899
900                 x = l;
901             }
902         }
903
904 /*
905         while (x != null
906                 && Column.compare(value, x.getData()[colIndex_0], colType_0)
907                    >= iTest) {
908             x = next(x);
909         }
910 */

911         while (x != null) {
912             Object JavaDoc colvalue = x.getData()[colIndex[0]];
913             int result = Column.compare(collation, value, colvalue,
914                                         colTypes[0]);
915
916             if (result >= iTest) {
917                 x = next(x);
918             } else {
919                 if (isEqual) {
920                     if (result != 0) {
921                         x = null;
922                     }
923                 } else if (colvalue == null) {
924                     x = next(x);
925
926                     continue;
927                 }
928
929                 break;
930             }
931         }
932
933         return getIterator(session, x);
934     }
935
936     /**
937      * Finds the first node where the data is not null.
938      *
939      * @return iterator
940      *
941      * @throws HsqlException
942      */

943     RowIterator findFirstRowNotNull(Session session) throws HsqlException {
944
945         Node x = getRoot(session);
946
947         while (x != null) {
948             boolean t = Column.compare(
949                 collation, null, x.getData()[colIndex[0]], colTypes[0]) >= 0;
950
951             if (t) {
952                 Node r = x.getRight();
953
954                 if (r == null) {
955                     break;
956                 }
957
958                 x = r;
959             } else {
960                 Node l = x.getLeft();
961
962                 if (l == null) {
963                     break;
964                 }
965
966                 x = l;
967             }
968         }
969
970         while (x != null) {
971             Object JavaDoc colvalue = x.getData()[colIndex[0]];
972
973             if (colvalue == null) {
974                 x = next(x);
975             } else {
976                 break;
977             }
978         }
979
980         return getIterator(session, x);
981     }
982
983     /**
984      * Returns the row for the first node of the index
985      *
986      * @return Iterator for first row
987      *
988      * @throws HsqlException
989      */

990     RowIterator firstRow(Session session) throws HsqlException {
991
992         depth = 0;
993
994         Node x = getRoot(session);
995         Node l = x;
996
997         while (l != null) {
998             x = l;
999             l = x.getLeft();
1000
1001            depth++;
1002        }
1003
1004        return getIterator(session, x);
1005    }
1006
1007    /**
1008     * Returns the row for the last node of the index
1009     *
1010     * @return last row
1011     *
1012     * @throws HsqlException
1013     */

1014    Row lastRow(Session session) throws HsqlException {
1015
1016        Node x = getRoot(session);
1017        Node l = x;
1018
1019        while (l != null) {
1020            x = l;
1021            l = x.getRight();
1022        }
1023
1024        return x == null ? null
1025                         : x.getRow();
1026    }
1027
1028    /**
1029     * Returns the node after the given one
1030     *
1031     * @param x node
1032     *
1033     * @return next node
1034     *
1035     * @throws HsqlException
1036     */

1037    Node next(Node x) throws HsqlException {
1038
1039        if (x == null) {
1040            return null;
1041        }
1042
1043        Node r = x.getRight();
1044
1045        if (r != null) {
1046            x = r;
1047
1048            Node l = x.getLeft();
1049
1050            while (l != null) {
1051                x = l;
1052                l = x.getLeft();
1053            }
1054
1055            return x;
1056        }
1057
1058        Node ch = x;
1059
1060        x = x.getParent();
1061
1062        while (x != null && ch.equals(x.getRight())) {
1063            ch = x;
1064            x = x.getParent();
1065        }
1066
1067        return x;
1068    }
1069
1070    /**
1071     * Returns either child node
1072     *
1073     * @param x node
1074     * @param isleft boolean
1075     *
1076     * @return child node
1077     *
1078     * @throws HsqlException
1079     */

1080    private Node child(Node x, boolean isleft) throws HsqlException {
1081        return isleft ? x.getLeft()
1082                      : x.getRight();
1083    }
1084
1085    /**
1086     * Replace two nodes
1087     *
1088     * @param x node
1089     * @param n node
1090     *
1091     * @throws HsqlException
1092     */

1093    private void replace(Session session, Node x,
1094                         Node n) throws HsqlException {
1095
1096        if (x.isRoot()) {
1097            if (n != null) {
1098                n = n.getUpdatedNode();
1099
1100                n.setParent(null);
1101            }
1102
1103            setRoot(session, n);
1104        } else {
1105            set(x.getParent(), x.isFromLeft(), n);
1106        }
1107    }
1108
1109    /**
1110     * Set a node as child of another
1111     *
1112     * @param x parent node
1113     * @param isleft boolean
1114     * @param n child node
1115     *
1116     * @throws HsqlException
1117     */

1118    private void set(Node x, boolean isleft, Node n) throws HsqlException {
1119
1120        x = x.getUpdatedNode();
1121
1122        if (isleft) {
1123            x.setLeft(n);
1124        } else {
1125            x.setRight(n);
1126        }
1127
1128        if (n != null) {
1129            n = n.getUpdatedNode();
1130
1131            n.setParent(x);
1132        }
1133    }
1134
1135    /**
1136     * Find a node with matching data
1137     *
1138     * @param row row data
1139     *
1140     * @return matching node
1141     *
1142     * @throws HsqlException
1143     */

1144    private Node search(Session session, Row row) throws HsqlException {
1145
1146        Object JavaDoc[] d = row.getData();
1147        Node x = getRoot(session);
1148
1149        while (x != null) {
1150            int c = compareRowForInsert(session, row, x.getRow());
1151
1152            if (c == 0) {
1153                return x;
1154            } else if (c < 0) {
1155                x = x.getLeft();
1156            } else {
1157                x = x.getRight();
1158            }
1159        }
1160
1161        return null;
1162    }
1163
1164    /**
1165     * Compares two table rows based on the columns of this index. The rowColMap
1166     * parameter specifies which columns of the other table are to be compared
1167     * with the colIndex columns of this index. The rowColMap can cover all
1168     * or only some columns of this index.
1169     *
1170     * @param a row from another table
1171     * @param rowColMap column indexes in the other table
1172     * @param b a full row in this table
1173     *
1174     * @return comparison result, -1,0,+1
1175     * @throws HsqlException
1176     */

1177    int compareRowNonUnique(Session session, Object JavaDoc[] a, int[] rowColMap,
1178                            Object JavaDoc[] b) throws HsqlException {
1179
1180        int i = Column.compare(collation, a[rowColMap[0]], b[colIndex[0]],
1181                               colTypes[0]);
1182
1183        if (i != 0) {
1184            return i;
1185        }
1186
1187        int fieldcount = rowColMap.length;
1188
1189        for (int j = 1; j < fieldcount; j++) {
1190            i = Column.compare(collation, a[rowColMap[j]], b[colIndex[j]],
1191                               colTypes[j]);
1192
1193            if (i != 0) {
1194                return i;
1195            }
1196        }
1197
1198        return 0;
1199    }
1200
1201    /**
1202     * compares two full table rows based on a set of columns
1203     *
1204     * @param a a full row
1205     * @param b a full row
1206     * @param cols array of column indexes to compare
1207     *
1208     * @return comparison result, -1,0,+1
1209     * @throws HsqlException
1210     */

1211    static int compareRows(Session session, Object JavaDoc[] a, Object JavaDoc[] b,
1212                           int[] cols, int[] coltypes) throws HsqlException {
1213
1214        int fieldcount = cols.length;
1215
1216        for (int j = 0; j < fieldcount; j++) {
1217            int i = Column.compare(session.database.collation, a[cols[j]],
1218                                   b[cols[j]], coltypes[cols[j]]);
1219
1220            if (i != 0) {
1221                return i;
1222            }
1223        }
1224
1225        return 0;
1226    }
1227
1228    /**
1229     * Compare two rows of the table for inserting rows into unique indexes
1230     *
1231     * @param a data
1232     * @param b data
1233     *
1234     * @return comparison result, -1,0,+1
1235     *
1236     * @throws HsqlException
1237     */

1238    private int compareRowForInsert(Session session, Row newRow,
1239                                    Row existingRow) throws HsqlException {
1240
1241        Object JavaDoc[] a = newRow.getData();
1242        Object JavaDoc[] b = existingRow.getData();
1243        int j = 0;
1244        boolean hasNull = false;
1245
1246        for (; j < colIndex.length; j++) {
1247            Object JavaDoc currentvalue = a[colIndex[j]];
1248            int i = Column.compare(collation, currentvalue, b[colIndex[j]],
1249                                   colTypes[j]);
1250
1251            if (i != 0) {
1252                return i;
1253            }
1254
1255            if (currentvalue == null) {
1256                hasNull = true;
1257            }
1258        }
1259
1260        if (isUnique &&!useRowId &&!hasNull) {
1261            return 0;
1262        }
1263
1264        for (j = 0; j < pkCols.length; j++) {
1265            Object JavaDoc currentvalue = a[pkCols[j]];
1266            int i = Column.compare(collation, currentvalue, b[pkCols[j]],
1267                                   pkTypes[j]);
1268
1269            if (i != 0) {
1270                return i;
1271            }
1272        }
1273
1274        if (useRowId) {
1275            int difference = newRow.getPos() - existingRow.getPos();
1276
1277            if (difference < 0) {
1278                difference = -1;
1279            } else if (difference > 0) {
1280                difference = 1;
1281            }
1282
1283            return difference;
1284        }
1285
1286        return 0;
1287    }
1288
1289    /**
1290     * Returns a value indicating the order of different types of index in
1291     * the list of indexes for a table. The position of the groups of Indexes
1292     * in the list in ascending order is as follows:
1293     *
1294     * primary key index
1295     * unique constraint indexes
1296     * autogenerated foreign key indexes for FK's that reference this table or
1297     * tables created before this table
1298     * user created indexes (CREATE INDEX)
1299     * autogenerated foreign key indexes for FK's that reference tables created
1300     * after this table
1301     *
1302     * Among a group of indexes, the order is based on the order of creation
1303     * of the index.
1304     *
1305     * @return ordinal value
1306     */

1307    int getIndexOrderValue() {
1308
1309        int value = 0;
1310
1311        if (isConstraint) {
1312            return isForward ? 4
1313                             : isUnique ? 0
1314                                        : 1;
1315        } else {
1316            return 2;
1317        }
1318    }
1319
1320    private IndexRowIterator getIterator(Session session, Node x) {
1321
1322        if (x == null) {
1323            return emptyIterator;
1324        } else {
1325            IndexRowIterator it = new IndexRowIterator(session, this, x);
1326
1327            return it;
1328        }
1329    }
1330
1331    static class IndexRowIterator implements RowIterator {
1332
1333        Session session;
1334        Index index;
1335        Node nextnode;
1336        protected IndexRowIterator last;
1337        protected IndexRowIterator next;
1338
1339        /**
1340         * When session == null, rows from all sessions are returned
1341         */

1342        private IndexRowIterator(Session session, Index index, Node node) {
1343
1344            if (index == null) {
1345                return;
1346            }
1347
1348            this.session = session;
1349            this.index = index;
1350            this.nextnode = node;
1351        }
1352
1353        public boolean hasNext() {
1354            return nextnode != null;
1355        }
1356
1357        public Row next() {
1358
1359            if (hasNext()) {
1360                try {
1361                    Row row = nextnode.getRow();
1362
1363                    nextnode = index.next(nextnode);
1364
1365                    return row;
1366                } catch (Exception JavaDoc e) {
1367                    throw new NoSuchElementException JavaDoc(e.getMessage());
1368                }
1369            } else {
1370                return null;
1371            }
1372        }
1373
1374        void updateForDelete(Node node) {
1375
1376            try {
1377                if (node.equals(nextnode)) {
1378                    nextnode = index.next(node);
1379                }
1380            } catch (Exception JavaDoc e) {}
1381        }
1382
1383        void link(IndexRowIterator other) {
1384
1385            other.next = next;
1386            other.last = this;
1387            next.last = other;
1388            next = other;
1389        }
1390
1391        public void release() {
1392
1393            if (last != null) {
1394                last.next = next;
1395            }
1396
1397            if (next != null) {
1398                next.last = last;
1399            }
1400        }
1401    }
1402}
1403
Popular Tags