index.java

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

                    dp.setLeft(x);
                }
            }

            // for in-memory tables we could use: d.rData=x.rData;
            // but not for cached tables
            // relink d.parent, x.left, x.right
            if (xp == d) {
                d.setParent(x);

                if (d.getLeft().equals(x)) {
                    x.setLeft(d);
                    x.setRight(d.getRight());
                } else {
                    x.setRight(d);
                    x.setLeft(d.getLeft());
                }
            } else {
                d.setParent(xp);
                xp.setRight(d);
                x.setRight(d.getRight());
                x.setLeft(d.getLeft());
            }

            x.getRight().setParent(x);
            x.getLeft().setParent(x);

            // set d.left, d.right
            d.setLeft(n);

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

            d.setRight(null);

            x = d;
        }

        boolean isleft = x.isFromLeft();

        replace(session, x, n);

        n = x.getParent();

        x.delete();

        while (n != null) {
            x = n;

            int sign = isleft ? 1
                              : -1;

            switch (x.getBalance() * sign) {

                case -1 :
                    x.setBalance(0);
                    break;

                case 0 :
                    x.setBalance(sign);

                    return;

                case 1 :
                    Node r = child(x, !isleft);
                    int  b = r.getBalance();

                    if (b * sign >= 0) {
                        replace(session, x, r);
                        set(x, !isleft, child(r, isleft));
                        set(r, isleft, x);

                        if (b == 0) {
                            x.setBalance(sign);
                            r.setBalance(-sign);

                            return;
                        }

                        x.setBalance(0);
                        r.setBalance(0);

                        x = r;
                    } else {
                        Node l = child(r, isleft);

                        replace(session, x, l);

                        b = l.getBalance();

                        set(r, isleft, child(l, !isleft));
                        set(l, !isleft, r);
                        set(x, !isleft, child(l, isleft));
                        set(l, isleft, x);
                        x.setBalance((b == sign) ? -sign
                                                 : 0);
                        r.setBalance((b == -sign) ? sign
                                                  : 0);
                        l.setBalance(0);

                        x = l;
                    }
            }

            isleft = x.isFromLeft();
            n      = x.getParent();
        }
    }

    RowIterator findFirstRow(Session session, Object[] rowdata,
                             int[] rowColMap) throws HsqlException {

        Node node = findNotNull(session, rowdata, rowColMap, true);

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

    RowIterator findFirstRowForDelete(Session session, Object[] rowdata,
                                      int[] rowColMap) throws HsqlException {

        Node node = findNotNull(session, rowdata, rowColMap, true);

        if (node == null) {
            return emptyIterator;
        } else {
            RowIterator it = new IndexRowIterator(session, this, node);

            updatableIterators.link((IndexRowIterator) it);

            return it;
        }
    }

    public Row findRow(Session session, Row row) throws HsqlException {

        Node node = search(session, row);

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

    boolean exists(Session session, Object[] rowdata,
                   int[] rowColMap) throws HsqlException {
        return findNotNull(session, rowdata, rowColMap, true) != null;
    }

    RowIterator emptyIterator() {
        return emptyIterator;
    }

    /**
     * Finds a foreign key referencing rows (in child table)
     *
     * @param rowdata array containing data for the index columns
     * @param rowColMap map of the data to columns
     * @param first true if the first matching node is required, false if any node
     * @return matching node or null
     * @throws HsqlException
     */
    private Node findNotNull(Session session, Object[] rowdata,
                             int[] rowColMap,
                             boolean first) throws HsqlException {

        Node x = getRoot(session);
        Node n;
        Node result = null;

        if (isNull(rowdata, rowColMap)) {
            return null;
        }

        while (x != null) {
            int i = this.compareRowNonUnique(session, rowdata, rowColMap,
                                             x.getData());

            if (i == 0) {
                if (first == false) {
                    result = x;

                    break;
                } else if (result == x) {
                    break;
                }

                result = x;
                n      = x.getLeft();
            } else if (i > 0) {
                n = x.getRight();
            } else {
                n = x.getLeft();
            }

            if (n == null) {
                break;
            }

            x = n;
        }

        return result;
    }

    /**
     * Finds any row that matches the rowdata. Use rowColMap to map index
     * columns to rowdata. Limit to visible columns of data.
     *
     * @param rowdata array containing data for the index columns
     * @param rowColMap map of the data to columns
     * @return node matching node
     * @throws HsqlException
     */
/*
    Node find(Object[] rowdata, int[] rowColMap) throws HsqlException {

        Node x = root;

        while (x != null) {
            int c = compareRowNonUnique(rowdata, rowColMap, x.getData());

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

        return null;
    }
*/

    /**
     * Determines if a table row has a null column for any of the columns given
     * in the rowColMap array.
     */
    static boolean isNull(Object[] row, int[] rowColMap) {

        int count = rowColMap.length;

        for (int i = 0; i < count; i++) {
            if (row[rowColMap[i]] == null) {
                return true;
            }
        }

        return false;
    }

    /**
     * Determines if a table row has a null column for any of the indexed
     * columns.
     */
    boolean isNull(Object[] row) {

        int count = colIndex.length;

        for (int i = 0; i < count; i++) {
            int j = colIndex[i];

            if (row[j] == null) {
                return true;
            }
        }

        return false;
    }

    /**
     * Return the first node equal to the rowdata object. Use visible columns
     * only. The rowdata has the same column mapping as this table.
     *
     * @param rowdata array containing table row data
     * @return matching node
     * @throws HsqlException
     */
    RowIterator findFirstRow(Session session,
                             Object[] rowdata) throws HsqlException {

        Node    x      = getRoot(session);
        Node    found  = null;
        boolean unique = isUnique &&!isNull(rowdata);

        while (x != null) {
            int c = compareRowNonUnique(session, rowdata, colIndex,
                                        x.getData());

            if (c == 0) {
                found = x;

                if (unique) {
                    break;
                }

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

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

    /**
     * Finds the first node that is larger or equal to the given one based
     * on the first column of the index only.
     *
     * @param value value to match
     * @param compare comparison Expression type
     *
     * @return matching node
     *
     * @throws HsqlException
     */
    RowIterator findFirstRow(Session session, Object value,
                             int compare) throws HsqlException {

        boolean isEqual = compare == Expression.EQUAL
                          || compare == Expression.IS_NULL;
        Node x     = getRoot(session);
        int  iTest = 1;

        if (compare == Expression.BIGGER) {
            iTest = 0;
        }

        if (value == null &&!isEqual) {
            return emptyIterator;
        }

/*
        // this method returns the correct node only with the following conditions
        boolean check = compare == Expression.BIGGER
                        || compare == Expression.EQUAL
                        || compare == Expression.BIGGER_EQUAL;

        if (!check) {
            Trace.doAssert(false, "Index.findFirst");
        }
*/
        while (x != null) {
            boolean t =
                Column.compare(
                    collation, value, x.getData()[colIndex[0]],
                    colType[0]) >= iTest;

            if (t) {
                Node r = x.getRight();

                if (r == null) {
                    break;
                }

                x = r;
            } else {
                Node l = x.getLeft();

                if (l == null) {
                    break;
                }

                x = l;
            }
        }

/*
        while (x != null
                && Column.compare(value, x.getData()[colIndex_0], colType_0)
                   >= iTest) {
            x = next(x);
        }
*/
        while (x != null) {
            Object colvalue = x.getData()[colIndex[0]];
            int result = Column.compare(collation, value, colvalue,
                                        colType[0]);

            if (result >= iTest) {
                x = next(x);
            } else {
                if (isEqual) {
                    if (result != 0) {
                        x = null;
                    }
                } else if (colvalue == null) {
                    x = next(x);

                    continue;
                }

                break;
            }
        }

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

    /**
     * Finds the first node where the data is not null.
     *
     * @return matching node
     *
     * @throws HsqlException
     */
    RowIterator findFirstRowNotNull(Session session) throws HsqlException {

        Node x = getRoot(session);

        while (x != null) {
            boolean t = Column.compare(
                collation, null, x.getData()[colIndex[0]], colType[0]) >= 0;

            if (t) {
                Node r = x.getRight();

                if (r == null) {
                    break;
                }

                x = r;
            } else {
                Node l = x.getLeft();