index.java

一个用java写的开源的数据库系统

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

                case 0 :
                    x.setBalance(sign);

                    return;

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

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

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

                            return;
                        }

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

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

                        replace(x, l);

                        b = l.getBalance();

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

                        x = l;
                    }
            }

            way = x.from();
            n   = x.getParent();
        }
    }

    /**
     * for finding foreign key referencing rows (in child table)
     *
     *
     * @param data
     *
     * @return
     *
     * @throws SQLException
     */
    Node findSimple(Object indexcoldata[],
                    boolean first) throws SQLException {

        Node x      = root, n;
        Node result = null;

        if (indexcoldata[0] == null) {
            return null;
        }

        while (x != null) {
            if (Trace.STOP) {
                Trace.stop();
            }

            int i = this.comparePartialRowNonUnique(indexcoldata,
                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;
    }

    /**
     * Method declaration
     *
     *
     * @param data
     *
     * @return
     *
     * @throws SQLException
     */
    Node find(Object data[]) throws SQLException {

        Node x = root, n;

        while (x != null) {
            if (Trace.STOP) {
                Trace.stop();
            }

            int i = compareRowNonUnique(data, x.getData());

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

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

            x = n;
        }

        return null;
    }

    /**
     * Method declaration
     *
     *
     * @param value
     * @param compare
     *
     * @return
     *
     * @throws SQLException
     */
    Node findFirst(Object value, int compare) throws SQLException {

        Trace.doAssert(compare == Expression.BIGGER
                       || compare == Expression.EQUAL
                       || compare
                          == Expression.BIGGER_EQUAL, "Index.findFirst");

        Node x     = root;
        int  iTest = 1;

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

        while (x != null) {
            if (Trace.STOP) {
                Trace.stop();
            }

            boolean t = compareValue(value, x.getData()[iColumn_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
                && compareValue(value, x.getData()[iColumn_0]) >= iTest) {
            if (Trace.STOP) {
                Trace.stop();
            }

            x = next(x);
        }

        return x;
    }

    /**
     * Method declaration
     *
     *
     * @return
     *
     * @throws SQLException
     */
    Node first() throws SQLException {

        Node x = root,
             l = x;

        while (l != null) {
            if (Trace.STOP) {
                Trace.stop();
            }

            x = l;
            l = x.getLeft();
        }

        return x;
    }

    /**
     * Method declaration
     *
     *
     * @param x
     *
     * @return
     *
     * @throws SQLException
     */
    Node next(Node x) throws SQLException {

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

        if (cleanUp && (++iNeedCleanUp & 127) == 0) {
            table.cleanUp();
        }

        Node r = x.getRight();

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

            Node l = x.getLeft();

            while (l != null) {
                if (Trace.STOP) {
                    Trace.stop();
                }

                x = l;
                l = x.getLeft();
            }

            return x;
        }

        Node ch = x;

        x = x.getParent();

        while (x != null && ch.equals(x.getRight())) {
            if (Trace.STOP) {
                Trace.stop();
            }

            ch = x;
            x  = x.getParent();
        }

        return x;
    }

    /**
     * Method declaration
     *
     *
     * @param x
     * @param w
     *
     * @return
     *
     * @throws SQLException
     */
    private Node child(Node x, boolean w) throws SQLException {
        return w ? x.getLeft()
                 : x.getRight();
    }

    /**
     * Method declaration
     *
     *
     * @param x
     * @param n
     *
     * @throws SQLException
     */
    private void replace(Node x, Node n) throws SQLException {

        if (x.equals(root)) {
            root = n;

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

    /**
     * Method declaration
     *
     *
     * @param x
     * @param w
     * @param n
     *
     * @throws SQLException
     */
    private void set(Node x, boolean w, Node n) throws SQLException {

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

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

    /**
     * Method declaration
     *
     *
     * @param d
     *
     * @return
     *
     * @throws SQLException
     */
    private Node search(Object d[]) throws SQLException {

        Node x = root;

        while (x != null) {
            if (Trace.STOP) {
                Trace.stop();
            }

            int c = compareRow(d, x.getData());

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

        return null;
    }

    /**
     * This method is used for finding foreign key references.
     *
     * It finds a row by comparing the values set in a[] and mapping to b[].
     * a[] contains only the column values which correspond to the columns
     * of the index. It does not necessarily cover
     * all the columns of the index, only the first a.length columns.
     *
     * b[] contains all the visible columns in a row of the table.
     *
     *
     * @param a a set of column values
     * @param b a full row
     *
     * @return
     *
     * @throws SQLException
     */
    int comparePartialRowNonUnique(Object a[],
                                   Object b[]) throws SQLException {

        int i = Column.compare(a[0], b[iColumn_0], iType_0);

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

        int fieldcount = visibleColumns;

        for (int j = 1; j < a.length && j < fieldcount; j++) {
            Object o = a[j];

            if (o == null) {
                continue;
            }

            i = Column.compare(o, b[iColumn[j]], iType[j]);

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

        return 0;
    }

    // todo: this is a hack

    /**
     * compares two full table rows based on the columns of the index
     *
     *
     * @param a a full row
     * @param b a full row
     *
     * @return
     *
     * @throws SQLException
     */
    private int compareRowNonUnique(Object a[],
                                    Object b[]) throws SQLException {

        int i = Column.compare(a[iColumn_0], b[iColumn_0], iType_0);

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

        int fieldcount = visibleColumns;

        for (int j = 1; j < fieldcount; j++) {
            i = Column.compare(a[iColumn[j]], b[iColumn[j]], iType[j]);

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

        return 0;
    }

    /**
     * Method declaration
     *
     *
     * @param a
     * @param b
     *
     * @return
     *
     * @throws SQLException
     */
    private int compareRow(Object a[], Object b[]) throws SQLException {

        int i = Column.compare(a[iColumn_0], b[iColumn_0], iType_0);

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

        for (int j = 1; j < iFields; j++) {
            i = Column.compare(a[iColumn[j]], b[iColumn[j]], iType[j]);

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

        return 0;
    }

    /**
     * Method declaration
     *
     *
     * @param a
     * @param b
     *
     * @return
     *
     * @throws SQLException
     */
    private int compareValue(Object a, Object b) throws SQLException {
        return Column.compare(a, b, iType_0);
    }
}