index.java

hsql是很有名的嵌入式数据库

                if (l == null) {
                    break;
                }

                x = l;
            }
        }

        while (x != null) {
            Object colvalue = x.getData()[colIndex[0]];

            if (colvalue == null) {
                x = next(x);
            } else {
                break;
            }
        }

        return x == null ? emptyIterator
                         : new IndexRowIterator(session, this, x);
    }

    /**
     * Returns the row for the first node of the index
     *
     * @return Iterator for first row
     *
     * @throws HsqlException
     */
    RowIterator firstRow(Session session) throws HsqlException {

        depth = 0;

        Node x = getRoot(session);
        Node l = x;

        while (l != null) {
            x = l;
            l = x.getLeft();

            depth++;
        }

        return x == null ? emptyIterator
                         : new IndexRowIterator(session, this, x);
    }

    /**
     * Returns the row for the last node of the index
     *
     * @return last row
     *
     * @throws HsqlException
     */
    Row lastRow(Session session) throws HsqlException {

        Node x = getRoot(session);
        Node l = x;

        while (l != null) {
            x = l;
            l = x.getRight();
        }

        return x == null ? null
                         : x.getRow();
    }

    /**
     * Returns the node after the given one
     *
     * @param x node
     *
     * @return next node
     *
     * @throws HsqlException
     */
    Node next(Node x) throws HsqlException {

        if (x == null) {
            return null;
        }

        Node r = x.getRight();

        if (r != null) {
            x = r;

            Node l = x.getLeft();

            while (l != null) {
                x = l;
                l = x.getLeft();
            }

            return x;
        }

        Node ch = x;

        x = x.getParent();

        while (x != null && ch.equals(x.getRight())) {
            ch = x;
            x  = x.getParent();
        }

        return x;
    }

    /**
     * Returns either child node
     *
     * @param x node
     * @param isleft boolean
     *
     * @return child node
     *
     * @throws HsqlException
     */
    private Node child(Node x, boolean isleft) throws HsqlException {
        return isleft ? x.getLeft()
                      : x.getRight();
    }

    /**
     * Replace two nodes
     *
     * @param x node
     * @param n node
     *
     * @throws HsqlException
     */
    private void replace(Session session, Node x,
                         Node n) throws HsqlException {

        if (x.equals(getRoot(session))) {
            setRoot(session, n);

            if (n != null) {
                n.setParent(null);
            }
        } else {
            set(x.getParent(), x.isFromLeft(), n);
        }
    }

    /**
     * Set a node as child of another
     *
     * @param x parent node
     * @param isleft boolean
     * @param n child node
     *
     * @throws HsqlException
     */
    private void set(Node x, boolean isleft, Node n) throws HsqlException {

        if (isleft) {
            x.setLeft(n);
        } else {
            x.setRight(n);
        }

        if (n != null) {
            n.setParent(x);
        }
    }

    /**
     * Find a node with matching data
     *
     * @param row row data
     *
     * @return matching node
     *
     * @throws HsqlException
     */
    Node search(Session session, Row row) throws HsqlException {

        Object[] d = row.getData();
        Node     x = getRoot(session);

        while (x != null) {
            int c = compareRowUnique(session, row, x.getRow());

            if (c == 0) {
                return x;
            } else if (c < 0) {
                x = x.getLeft();
            } else {
                x = x.getRight();
            }
        }

        return null;
    }

    /**
     * Compares two table rows based on the columns of this index. The rowColMap
     * parameter specifies which columns of the other table are to be compared
     * with the colIndex columns of this index. The rowColMap can cover all
     * or only some columns of this index. The invisible column is never
     * compared
     *
     * @param a row from another table
     * @param rowColMap column indexes in the other table
     * @param b a full row in this table
     *
     * @return comparison result, -1,0,+1
     * @throws HsqlException
     */
    int compareRowNonUnique(Session session, Object[] a, int[] rowColMap,
                            Object[] b) throws HsqlException {

        int i = Column.compare(collation, a[rowColMap[0]], b[colIndex[0]],
                               colType[0]);

        if (i != 0) {
            return i;
        }

        int fieldcount = rowColMap.length;

        for (int j = 1; j < fieldcount; j++) {
            i = Column.compare(collation, a[rowColMap[j]], b[colIndex[j]],
                               colType[j]);

            if (i != 0) {
                return i;
            }
        }

        return 0;
    }

    /**
     * compares two full table rows based on a set of columns
     *
     * @param a a full row
     * @param b a full row
     * @param cols array of column indexes to compare
     *
     * @return comparison result, -1,0,+1
     * @throws HsqlException
     */
    static int compareRows(Session session, Object[] a, Object[] b,
                           int[] cols, int[] coltypes) throws HsqlException {

        int fieldcount = cols.length;

        for (int j = 0; j < fieldcount; j++) {
            int i = Column.compare(session.database.collation, a[cols[j]],
                                   b[cols[j]], coltypes[cols[j]]);

            if (i != 0) {
                return i;
            }
        }

        return 0;
    }

    /**
     * Compare two rows of the table for inserting rows into unique indexes
     *
     * @param a data
     * @param b data
     *
     * @return comparison result, -1,0,+1
     *
     * @throws HsqlException
     */
    private int compareRowUnique(Session session, Row left,
                                 Row right) throws HsqlException {

        Object[] a       = left.getData();
        Object[] b       = right.getData();
        int      j       = 0;
        boolean  hasNull = false;

        for (; j < colIndex.length; j++) {
            Object currentvalue = a[colIndex[j]];
            int i = Column.compare(collation, currentvalue, b[colIndex[j]],
                                   colType[j]);

            if (i != 0) {
                return i;
            }

            if (currentvalue == null) {
                hasNull = true;
            }
        }

        if (isUnique &&!useRowId &&!hasNull) {
            return 0;
        }

        for (j = 0; j < pkCols.length; j++) {
            Object currentvalue = a[pkCols[j]];
            int i = Column.compare(collation, currentvalue, b[pkCols[j]],
                                   pkTypes[j]);

            if (i != 0) {
                return i;
            }
        }

        if (useRowId) {
            int difference = left.getPos() - right.getPos();

            if (difference < 0) {
                difference = -1;
            } else if (difference > 0) {
                difference = 1;
            }

            return difference;
        }

        return 0;
    }

    /**
     * Returns a value indicating the order of different types of index in
     * the list of indexes for a table. The position of the groups of Indexes
     * in the list in ascending order is as follows:
     *
     * primary key index
     * unique constraint indexes
     * autogenerated foreign key indexes for FK's that reference this table or
     *  tables created before this table
     * user created indexes (CREATE INDEX)
     * autogenerated foreign key indexes for FK's that reference tables created
     *  after this table
     *
     * Among a group of indexes, the order is based on the order of creation
     * of the index.
     *
     * @return ordinal value
     */
    int getIndexOrderValue() {

        int value = 0;

        if (isConstraint) {
            return isForward ? 4
                             : isUnique ? 0
                                        : 1;
        } else {
            return 2;
        }
    }

    static class IndexRowIterator implements RowIterator {

        Session                    session;
        Index                      index;
        Node                       nextnode;
        protected IndexRowIterator last;
        protected IndexRowIterator next;

        /**
         * When session == null, rows from all sessions are returned
         */
        private IndexRowIterator(Session session, Index index, Node node) {

            if (index == null) {
                return;
            }

            this.session  = session;
            this.index    = index;
            this.nextnode = node;
        }

        public boolean hasNext() {
            return nextnode != null;
        }

        public Row next() {

            if (hasNext()) {
                try {
                    Row row = nextnode.getRow();

                    nextnode = index.next(nextnode);

                    return row;
                } catch (Exception e) {
                    throw new NoSuchElementException();
                }
            } else {
                return null;
            }
        }

        void link(IndexRowIterator other) {

            other.next = next;
            next.last  = other;
            other.last = this;
            next       = other;
        }

        public void release() {

            if (last != null) {
                last.next = next;
            }

            if (next != null) {
                next.last = last;
            }
        }

        void updateForDelete(Node node) {

            try {
                if (node.equals(nextnode)) {
                    nextnode = index.next(node);
                }
            } catch (Exception e) {}
        }
    }
}