index.java

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

/* Copyright (c) 1995-2000, The Hypersonic SQL Group.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * Redistributions of source code must retain the above copyright notice, this
 * list of conditions and the following disclaimer.
 *
 * Redistributions in binary form must reproduce the above copyright notice,
 * this list of conditions and the following disclaimer in the documentation
 * and/or other materials provided with the distribution.
 *
 * Neither the name of the Hypersonic SQL Group nor the names of its
 * contributors may be used to endorse or promote products derived from this
 * software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE HYPERSONIC SQL GROUP,
 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * This software consists of voluntary contributions made by many individuals 
 * on behalf of the Hypersonic SQL Group.
 *
 *
 * For work added by the HSQL Development Group:
 *
 * Copyright (c) 2001-2005, The HSQL Development Group
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * Redistributions of source code must retain the above copyright notice, this
 * list of conditions and the following disclaimer.
 *
 * Redistributions in binary form must reproduce the above copyright notice,
 * this list of conditions and the following disclaimer in the documentation
 * and/or other materials provided with the distribution.
 *
 * Neither the name of the HSQL Development Group nor the names of its
 * contributors may be used to endorse or promote products derived from this
 * software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL HSQL DEVELOPMENT GROUP, HSQLDB.ORG,
 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */


package org.hsqldb;

import java.util.NoSuchElementException;

import org.hsqldb.HsqlNameManager.HsqlName;
import org.hsqldb.index.RowIterator;
import org.hsqldb.lib.ArrayUtil;

// fredt@users 20020221 - patch 513005 by sqlbob@users - corrections
// fredt@users 20020225 - patch 1.7.0 - changes to support cascading deletes
// tony_lai@users 20020820 - patch 595052 - better error message
// fredt@users 20021205 - patch 1.7.2 - changes to method signature
// fredt@users - patch 1.80 - reworked the interface and comparison methods

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

    // types of index
    static final int MEMORY_INDEX  = 0;
    static final int DISK_INDEX    = 1;
    static final int POINTER_INDEX = 2;

    // fields
    private final HsqlName indexName;
    final boolean[]        colCheck;
    private final int[]    colIndex;
    private final int[]    colType;
    final int[]            pkCols;
    final int[]            pkTypes;
    private final boolean  isUnique;    // DDL uniqueness
    private final boolean  useRowId;
    final boolean          isConstraint;
    final boolean          isForward;
    final boolean          isTemp;
    private Node           root;
    private int            depth;
    final Collation        collation;
    static IndexRowIterator emptyIterator = new IndexRowIterator(null, null,
        null);
    IndexRowIterator updatableIterators;
    final boolean    onCommitPreserve;

    /**
     * Constructor declaration
     *
     *
     * @param name HsqlName of the index
     * @param table table of the index
     * @param column array of column indexes
     * @param type array of column types
     * @param unique is this a unique index
     * @param constraint does this index belonging to a constraint
     * @param forward is this an auto-index for an FK that refers to a table defined after this table
     * @param visColumns count of visible columns
     */
    Index(Database database, HsqlName name, Table table, int[] column,
            int[] type, boolean isPk, boolean unique, boolean constraint,
            boolean forward, int[] pkcols, int[] pktypes, boolean temp) {

        indexName    = name;
        colIndex     = column;
        colType      = type;
        pkCols       = pkcols;
        pkTypes      = pktypes;
        isUnique     = unique;
        isConstraint = constraint;
        isForward    = forward;
        useRowId = (!isUnique && pkCols.length == 0)
                   || (colIndex.length == 0);
        colCheck = table.getNewColumnCheckList();

        ArrayUtil.intIndexesToBooleanArray(colIndex, colCheck);

        updatableIterators = new IndexRowIterator(null, null, null);
        updatableIterators.next = updatableIterators.last =
            updatableIterators;
        collation        = database.collation;
        isTemp           = temp;
        onCommitPreserve = table.onCommitPreserve;
    }

    /**
     * Returns the HsqlName object
     */
    HsqlName getName() {
        return indexName;
    }

    /**
     * Changes index name. Used by 'alter index rename to'. Argument isquoted
     * is true if the name was quoted in the DDL.
     */
    void setName(String name, boolean isquoted) throws HsqlException {
        indexName.rename(name, isquoted);
    }

    /**
     * Returns the count of visible columns used
     */
    int getVisibleColumns() {
        return colIndex.length;
    }

    /**
     * Is this a UNIQUE index?
     */
    boolean isUnique() {
        return isUnique;
    }

    /**
     * Does this index belong to a constraint?
     */
    boolean isConstraint() {
        return isConstraint;
    }

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

    /**
     * Returns the array containing column indexes for index
     */
    int[] getColumnTypes() {
        return colType;    // todo: this gives back also primary key field(s)!
    }

    /**
     * Returns the node count.
     */
    int size(Session session) throws HsqlException {

        int         count = 0;
        RowIterator it    = firstRow(session);

        while (it.hasNext()) {
            it.next();

            count++;
        }

        return count;
    }

    boolean isEmpty(Session session) {
        return getRoot(session) == null;
    }

    public int sizeEstimate() throws HsqlException {

        firstRow(null);

        return (int) (1L << depth);
    }

    void clearAll(Session session) {

        setRoot(session, null);

        depth = 0;
        updatableIterators.next = updatableIterators.last =
            updatableIterators;
    }

    void clearIterators() {
        updatableIterators.next = updatableIterators.last =
            updatableIterators;
    }

    void setRoot(Session session, Node node) {

        if (isTemp) {
            session.setIndexRoot(indexName, onCommitPreserve, node);
        } else {
            root = node;
        }
    }

    Node getRoot(Session session) {

        if (isTemp) {
            return session.getIndexRoot(indexName, onCommitPreserve);
        } else {
            return root;
        }
    }

    /**
     * Insert a node into the index
     */
    void insert(Session session, Row row, int offset) throws HsqlException {

        Node    n       = getRoot(session);
        Node    x       = n;
        boolean isleft  = true;
        int     compare = -1;

        while (true) {
            if (n == null) {
                if (x == null) {
                    setRoot(session, row.getNode(offset));

                    return;
                }

                set(x, isleft, row.getNode(offset));

                break;
            }

            compare = compareRowUnique(session, row, n.getRow());

            if (compare == 0) {
                throw Trace.error(Trace.VIOLATION_OF_UNIQUE_INDEX,
                                  indexName.name);
            }

            isleft = compare < 0;
            x      = n;
            n      = child(x, isleft);
        }

        balance(session, x, isleft);
    }

    /**
     * Balances part of the tree after an alteration to the index.
     */
    private void balance(Session session, Node x,
                         boolean isleft) throws HsqlException {

        while (true) {
            int sign = isleft ? 1
                              : -1;

            switch (x.getBalance() * sign) {

                case 1 :
                    x.setBalance(0);

                    return;

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

                case -1 :
                    Node l = child(x, isleft);

                    if (l.getBalance() == -sign) {
                        replace(session, x, l);
                        set(x, isleft, child(l, !isleft));
                        set(l, !isleft, x);
                        x.setBalance(0);
                        l.setBalance(0);
                    } else {
                        Node r = child(l, !isleft);

                        replace(session, x, r);
                        set(l, !isleft, child(r, isleft));
                        set(r, isleft, l);
                        set(x, isleft, child(r, !isleft));
                        set(r, !isleft, x);

                        int rb = r.getBalance();

                        x.setBalance((rb == -sign) ? sign
                                                   : 0);
                        l.setBalance((rb == sign) ? -sign
                                                  : 0);
                        r.setBalance(0);
                    }

                    return;
            }

            if (x.equals(getRoot(session))) {
                return;
            }

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

    /**
     * Delete a node from the index
     */
    void delete(Session session, Node x) throws HsqlException {

        if (x == null) {
            return;
        }

        for (IndexRowIterator it = updatableIterators.next;
                it != updatableIterators; it = it.next) {
            it.updateForDelete(x);
        }

        Node n;

        if (x.getLeft() == null) {
            n = x.getRight();
        } else if (x.getRight() == null) {
            n = x.getLeft();
        } else {
            Node d = x;

            x = x.getLeft();

/*
            // todo: this can be improved

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

                x = x.getRight();
            }
*/
            for (Node temp = x; (temp = temp.getRight()) != null; ) {
                x = temp;
            }

            // x will be replaced with n later
            n = x.getLeft();

            // swap d and x
            int b = x.getBalance();

            x.setBalance(d.getBalance());
            d.setBalance(b);

            // set x.parent
            Node xp = x.getParent();
            Node dp = d.getParent();

            if (d == getRoot(session)) {
                setRoot(session, x);
            }

            x.setParent(dp);

            if (dp != null) {
                if (dp.getRight().equals(d)) {
                    dp.setRight(x);
                } else {