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  ;
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   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   getColumnNameList() {
212 
213         String   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   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  [] {
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  [] 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  [] 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  [] 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  [] 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  [] 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  [] 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  [] 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   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   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   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  [] 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  [] a, int[] rowColMap,
1178                            Object  [] 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  [] a, Object  [] 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  [] a       = newRow.getData();
1242        Object  [] b       = existingRow.getData();
1243        int      j       = 0;
1244        boolean  hasNull = false;
1245
1246        for (; j < colIndex.length; j++) {
1247            Object   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   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   e) {
1367                    throw new NoSuchElementException  (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   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
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags