org.hsqldb/hsqldb/2.5.0 : org/hsqldb/index/IndexAVL.java

IndexAVL
http://hsqldb.org: HSQLDB - Lightweight 100% Java SQL Database Engine (The HSQL Development Group)
HSQLDB License, a BSD open source license
Blaine Simpson
/*
 * For work developed by the HSQL Development Group:
 *
 * Copyright (c) 2001-2019, 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.
 *
 *
 *
 * For work originally developed by the Hypersonic SQL Group:
 *
 * 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.
 */


package org.hsqldb.index;

import org.hsqldb.Constraint;
import org.hsqldb.HsqlNameManager.HsqlName;
import org.hsqldb.OpTypes;
import org.hsqldb.RangeVariable.RangeVariableConditions;
import org.hsqldb.Row;
import org.hsqldb.RowAVL;
import org.hsqldb.SchemaObject;
import org.hsqldb.Session;
import org.hsqldb.Table;
import org.hsqldb.TableBase;
import org.hsqldb.Tokens;
import org.hsqldb.TransactionManager;
import org.hsqldb.error.Error;
import org.hsqldb.error.ErrorCode;
import org.hsqldb.lib.ArrayUtil;
import org.hsqldb.lib.OrderedHashSet;
import org.hsqldb.navigator.RowIterator;
import org.hsqldb.persist.PersistentStore;
import org.hsqldb.rights.Grantee;
import org.hsqldb.types.DateTimeType;
import org.hsqldb.types.TimestampData;
import org.hsqldb.types.Type;

// fredt@users 20020221 - patch 513005 by sqlbob@users - corrections
// fredt@users - patch 1.8.0 - reworked the interface and comparison methods
// fredt@users - patch 1.8.0 - improved reliability for cached indexes
// fredt@users - patch 1.9.0 - iterators and concurrency
// fredt@users - patch 2.0.0 - enhanced selection and iterators

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.
An Index object also holds information on table columns (in the form of int
indexes) that are covered by it.

New class derived from Hypersonic SQL code and enhanced in HSQLDB. 

Author: Thomas Mueller (Hypersonic SQL Group), Fred Toussi (fredt@users dot sourceforge.net)
Version: 2.5.0
Since: Hypersonic SQL/**
 * 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.<p>
 *
 * New class derived from Hypersonic SQL code and enhanced in HSQLDB. <p>
 *
 * @author Thomas Mueller (Hypersonic SQL Group)
 * @author Fred Toussi (fredt@users dot sourceforge.net)
 * @version 2.5.0
 * @since Hypersonic SQL
 */
public class IndexAVL implements Index {

    private static final IndexRowIterator emptyIterator =
        new IndexRowIterator(null, null, null, null, 0, false, false);

    // fields
    private final long       persistenceId;
    protected final HsqlName name;
    private final boolean[]  colCheck;
    final int[]              colIndex;
    private final int[]      defaultColMap;
    final Type[]             colTypes;
    private final boolean[]  colDesc;
    private final boolean[]  nullsLast;
    final boolean            isSimpleOrder;
    final boolean            isSimple;
    protected final boolean  isPK;        // PK with or without columns
    protected final boolean  isUnique;    // DDL uniqueness
    protected final boolean  isConstraint;
    private final boolean    isForward;
    private boolean          isClustered;
    protected TableBase      table;
    int                      position;
    private IndexUse[]       asArray;

    //
    Object[] nullData;

    Constructor declaration
Params: name – HsqlName of the index
id – persistnece id
table – table of the index
columns – array of column indexes
descending – boolean[]
nullsLast – boolean[]
colTypes – array of column types
pk – if index is for a primary key
unique – is this a unique index
constraint – does this index belonging to a constraint
forward – is this an auto-index for an FK that refers to a table
  defined after this table/**
     * Constructor declaration
     *
     * @param name HsqlName of the index
     * @param id persistnece id
     * @param table table of the index
     * @param columns array of column indexes
     * @param descending boolean[]
     * @param nullsLast boolean[]
     * @param colTypes array of column types
     * @param pk if index is for a primary key
     * @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
     */
    public IndexAVL(HsqlName name, long id, TableBase table, int[] columns,
                    boolean[] descending, boolean[] nullsLast,
                    Type[] colTypes, boolean pk, boolean unique,
                    boolean constraint, boolean forward) {

        this.persistenceId = id;
        this.name          = name;
        this.colIndex      = columns;
        this.colTypes      = colTypes;
        this.colDesc       = descending == null ? new boolean[columns.length]
                                                : descending;
        this.nullsLast     = nullsLast == null ? new boolean[columns.length]
                                               : nullsLast;
        this.isPK          = pk;
        this.isUnique      = unique;
        this.isConstraint  = constraint;
        this.isForward     = forward;
        this.table         = table;
        this.colCheck      = table.getNewColumnCheckList();
        this.asArray = new IndexUse[]{ new IndexUse(this, colIndex.length) };

        ArrayUtil.intIndexesToBooleanArray(colIndex, colCheck);

        this.defaultColMap = new int[columns.length];

        ArrayUtil.fillSequence(defaultColMap);

        boolean simpleOrder = colIndex.length > 0;

        for (int i = 0; i < colDesc.length; i++) {
            if (this.colDesc[i] || this.nullsLast[i]) {
                simpleOrder = false;
            }
        }

        isSimpleOrder = simpleOrder;
        isSimple      = isSimpleOrder && colIndex.length == 1;
        nullData      = new Object[colIndex.length];
    }

    // SchemaObject implementation
    public int getType() {
        return SchemaObject.INDEX;
    }

    public HsqlName getName() {
        return name;
    }

    public HsqlName getCatalogName() {
        return name.schema.schema;
    }

    public HsqlName getSchemaName() {
        return name.schema;
    }

    public Grantee getOwner() {
        return name.schema.owner;
    }

    public OrderedHashSet getReferences() {
        return new OrderedHashSet();
    }

    public OrderedHashSet getComponents() {
        return null;
    }

    public void compile(Session session, SchemaObject parentObject) {}

    public String getSQL() {

        StringBuilder sb = new StringBuilder(128);

        sb.append(Tokens.T_CREATE).append(' ');

        if (isUnique()) {
            sb.append(Tokens.T_UNIQUE).append(' ');
        }

        sb.append(Tokens.T_INDEX).append(' ');
        sb.append(getName().statementName);
        sb.append(' ').append(Tokens.T_ON).append(' ');
        sb.append(((Table) table).getName().getSchemaQualifiedStatementName());
        sb.append(((Table) table).getColumnListSQL(colIndex, colIndex.length));

        return sb.toString();
    }

    public long getChangeTimestamp() {
        return 0;
    }

    // IndexInterface
    public IndexUse[] asArray() {
        return asArray;
    }

    public RowIterator emptyIterator() {
        return emptyIterator;
    }

    public int getPosition() {
        return position;
    }

    public void setPosition(int position) {
        this.position = position;
    }

    public long getPersistenceId() {
        return persistenceId;
    }

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

    Is this a PRIMARY_KEY index?
/**
     * Is this a PRIMARY_KEY index?
     */
    public boolean isPrimaryKey() {
        return isPK;
    }

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

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

    Returns the array containing column indexes for index
/**
     * Returns the array containing column indexes for index
     */
    public int[] getColumns() {
        return colIndex;
    }

    Returns the array containing column indexes for index
/**
     * Returns the array containing column indexes for index
     */
    public Type[] getColumnTypes() {
        return colTypes;
    }

    public boolean[] getColumnDesc() {
        return colDesc;
    }

    public int[] getDefaultColumnMap() {
        return this.defaultColMap;
    }

    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.
Returns: ordinal value/**
     * 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
     */
    public int getIndexOrderValue() {

        if (isPK) {
            return 0;
        }

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

    public boolean isForward() {
        return isForward;
    }

    public void setTable(TableBase table) {
        this.table = table;
    }

    public TableBase getTable() {
        return table;
    }

    public void setClustered(boolean clustered) {
        isClustered = clustered;
    }

    public boolean isClustered() {
        return isClustered;
    }

    Returns the node count.
/**
     * Returns the node count.
     */
    public long size(Session session, PersistentStore store) {
        return getNodeCount(session, store);
    }

    public long sizeUnique(PersistentStore store) {
        return store.elementCountUnique(this);
    }

    public double[] searchCost(Session session, PersistentStore store) {

        boolean  probeDeeper = false;
        int      counter     = 1;
        double[] changes     = new double[colIndex.length];
        int      depth       = 0;
        int[]    depths      = new int[1];

        store.readLock();

        try {
            NodeAVL node = getAccessor(store);
            NodeAVL temp = node;

            if (node == null) {
                return changes;
            }

            while (true) {
                node = temp;
                temp = node.getLeft(store);

                if (temp == null) {
                    break;
                }

                if (depth == Index.probeDepth) {
                    probeDeeper = true;

                    break;
                }

                depth++;
            }

            while (true) {
                temp  = next(store, node, depth, probeDepth, depths);
                depth = depths[0];

                if (temp == null) {
                    break;
                }

                compareRowForChange(session, node.getData(store),
                                    temp.getData(store), changes);

                node = temp;

                counter++;
            }

            if (probeDeeper) {
                double[] factors = new double[colIndex.length];
                int extras = probeFactor(session, store, factors, true)
                             + probeFactor(session, store, factors, false);

                for (int i = 0; i < colIndex.length; i++) {
                    factors[i] /= 2.0;

                    for (int j = 0; j < factors[i]; j++) {
                        changes[i] *= 2;
                    }
                }
            }

            long rowCount = store.elementCount();

            for (int i = 0; i < colIndex.length; i++) {
                if (changes[i] == 0) {
                    changes[i] = 1;
                }

                changes[i] = rowCount / changes[i];

                if (changes[i] < 2) {
                    changes[i] = 2;
                }
            }

/*
            StringBuilder s = new StringBuilder();

            s.append("count " + rowCount + " columns " + colIndex.length
                     + " selectivity " + changes[0]);
            System.out.println(s);
*/
            return changes;
        } finally {
            store.readUnlock();
        }
    }

    int probeFactor(Session session, PersistentStore store, double[] changes,
                    boolean left) {

        int     depth = 0;
        NodeAVL x     = getAccessor(store);
        NodeAVL n     = x;

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

        while (n != null) {
            x = n;
            n = left ? x.getLeft(store)
                     : x.getRight(store);

            depth++;

            if (depth > probeDepth && n != null) {
                compareRowForChange(session, x.getData(store),
                                    n.getData(store), changes);
            }
        }

        return depth - probeDepth;
    }

    public long getNodeCount(Session session, PersistentStore store) {

        long        count = 0;
        RowIterator it    = firstRow(session, store, null, 0, null);

        while (it.next()) {
            count++;
        }

        return count;
    }

    public boolean isEmpty(PersistentStore store) {

        store.readLock();

        try {
            return getAccessor(store) == null;
        } finally {
            store.readUnlock();
        }
    }

    Removes all links between memory nodes
/**
     * Removes all links between memory nodes
     */
    public void unlinkNodes(PersistentStore store, NodeAVL primaryRoot) {

        NodeAVL x = primaryRoot;
        NodeAVL l = x;

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

        while (x != null) {
            NodeAVL n = nextUnlink(store, x);

            x = n;
        }
    }

    private NodeAVL nextUnlink(PersistentStore store, NodeAVL x) {

        NodeAVL temp = x.getRight(null);

        if (temp != null) {
            x    = temp;
            temp = x.getLeft(null);

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

            return x;
        }

        temp = x;
        x    = x.getParent(null);

        while (x != null && x.isRight(store, temp)) {
            x.nRight = null;

            temp.getRow(null).destroy();
            temp.delete();

            //
            temp = x;
            x    = x.getParent(null);
        }

        if (x != null) {
            x.nLeft = null;
        }

        temp.getRow(null).destroy();
        temp.delete();

        return x;
    }

    public int checkIndex(Session session, PersistentStore store) {

        int errors = 0;

        store.readLock();

        try {
            NodeAVL p = getAccessor(store);
            NodeAVL f = null;

            while (p != null) {
                f = p;

                checkNodes(store, p);

                p = p.getLeft(store);
            }

            p = f;

            while (f != null) {
                errors += checkNodes(store, f);

                NodeAVL fnext = next(store, f);

                if (fnext != null) {
                    int c = compareRowForInsertOrDelete(session,
                                                        fnext.getRow(store),
                                                        f.getRow(store), true,
                                                        0);

                    if (c <= 0) {
                        if (errors < 10) {
                            System.out.println("broken index order "
                                               + getName().name);
                        }

                        errors++;
                    }
                }

                f = fnext;
            }
        } finally {
            store.readUnlock();
        }

        if (errors > 0) {
            System.out.println("total errors " + getName().name);
        }

        return errors;
    }

    int checkNodes(PersistentStore store, NodeAVL p) {

        NodeAVL l      = p.nLeft;
        NodeAVL r      = p.nRight;
        int     errors = 0;

        if (l != null && l.getBalance(store) == -2) {
            System.out.print("broken index - deleted");

            errors++;
        }

        if (r != null && r.getBalance(store) == -2) {
            System.out.print("broken index -deleted");

            errors++;
        }

        if (l != null && !p.equals(l.getParent(store))) {
            System.out.print("broken index - no parent");

            errors++;
        }

        if (r != null && !p.equals(r.getParent(store))) {
            System.out.print("broken index - no parent");

            errors++;
        }

        return errors;
    }

    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.
Params: session – Session
a – row from another table
rowColMap – column indexes in the other table
b – a full row in this table
Returns: comparison result, -1,0,+1/**
     * 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.
     *
     * @param session Session
     * @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
     */
    public int compareRowNonUnique(Session session, Object[] a, Object[] b,
                                   int[] rowColMap) {

        int fieldcount = rowColMap.length;

        for (int j = 0; j < fieldcount; j++) {
            int i = colTypes[j].compare(session, a[colIndex[j]],
                                        b[rowColMap[j]]);

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

        return 0;
    }

    public int compareRowNonUnique(Session session, Object[] a, Object[] b,
                                   int[] rowColMap, int fieldCount) {

        for (int j = 0; j < fieldCount; j++) {
            int i = colTypes[j].compare(session, a[colIndex[j]],
                                        b[rowColMap[j]]);

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

        return 0;
    }

    As above but use the index column data
/**
     * As above but use the index column data
     */
    public int compareRowNonUnique(Session session, Object[] a, Object[] b,
                                   int fieldCount) {

        for (int j = 0; j < fieldCount; j++) {
            int i = colTypes[j].compare(session, a[colIndex[j]],
                                        b[colIndex[j]]);

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

        return 0;
    }

    public void compareRowForChange(Session session, Object[] a, Object[] b,
                                    double[] changes) {

        int c = 0;

        for (int j = 0; j < colIndex.length; j++) {
            if (c == 0) {
                c = colTypes[j].compare(session, a[colIndex[j]],
                                        b[colIndex[j]]);
            }

            if (c != 0) {
                changes[j]++;
            }
        }
    }

    public int compareRow(Session session, Object[] a, Object[] b) {

        for (int j = 0; j < colIndex.length; j++) {
            int i = colTypes[j].compare(session, a[colIndex[j]],
                                        b[colIndex[j]]);

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

                boolean nulls = a[colIndex[j]] == null
                                || b[colIndex[j]] == null;

                if (colDesc[j] && !nulls) {
                    i = -i;
                }

                if (nullsLast[j] && nulls) {
                    i = -i;
                }

                return i;
            }
        }

        return 0;
    }

    Compare two rows of the table for inserting rows into unique indexes
Supports descending columns.
Params: session – Session
newRow – data
existingRow – data
useRowId – boolean
start – int
Returns: comparison result, -1,0,+1/**
     * Compare two rows of the table for inserting rows into unique indexes
     * Supports descending columns.
     *
     * @param session Session
     * @param newRow data
     * @param existingRow data
     * @param useRowId boolean
     * @param start int
     * @return comparison result, -1,0,+1
     */
    int compareRowForInsertOrDelete(Session session, Row newRow,
                                    Row existingRow, boolean useRowId,
                                    int start) {

        Object[] a = newRow.getData();
        Object[] b = existingRow.getData();

        for (int j = start; j < colIndex.length; j++) {
            int i = colTypes[j].compare(session, a[colIndex[j]],
                                        b[colIndex[j]]);

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

                boolean nulls = a[colIndex[j]] == null
                                || b[colIndex[j]] == null;

                if (colDesc[j] && !nulls) {
                    i = -i;
                }

                if (nullsLast[j] && nulls) {
                    i = -i;
                }

                return i;
            }
        }

        // versioned rows are ordered by timestamp and row id
        if (start == 0 && table.isSystemVersioned) {
            TimestampData newVersion      = newRow.getSystemEndVersion();
            TimestampData existingVersion = existingRow.getSystemEndVersion();
            int compare = Type.SQL_TIMESTAMP_WITH_TIME_ZONE.compare(session,
                newVersion, existingVersion);

            if (compare == 0) {
                if (newVersion.getSeconds()
                        != DateTimeType.epochLimitSeconds) {
                    useRowId = true;
                }
            } else {
                return compare;
            }
        }

        if (useRowId) {
            long diff = newRow.getPos() - existingRow.getPos();

            return diff == 0L ? 0
                              : diff > 0L ? 1
                                          : -1;
        }

        return 0;
    }

    int compareObject(Session session, Object[] a, Object[] b,
                      int[] rowColMap, int position, int opType) {
        return colTypes[position].compare(session, a[colIndex[position]],
                                          b[rowColMap[position]], opType);
    }

    boolean hasNulls(Session session, Object[] rowData) {

        boolean uniqueNulls = session == null
                              || session.database.sqlUniqueNulls;
        boolean compareId = false;

        for (int j = 0; j < colIndex.length; j++) {
            if (rowData[colIndex[j]] == null) {
                compareId = true;

                if (uniqueNulls) {
                    break;
                }
            } else if (!uniqueNulls) {
                compareId = false;

                break;
            }
        }

        return compareId;
    }

    Insert a node into the index
/**
     * Insert a node into the index
     */
    public void insert(Session session, PersistentStore store, Row row) {

        NodeAVL n;
        NodeAVL x;
        boolean isleft       = true;
        int     compare      = -1;
        boolean compareRowId = !isUnique || hasNulls(session, row.getData());

        n = getAccessor(store);
        x = n;

        if (n == null) {
            store.setAccessor(this, ((RowAVL) row).getNode(position));

            return;
        }

        while (true) {
            Row currentRow = n.getRow(store);

            compare = compareRowForInsertOrDelete(session, row, currentRow,
                                                  compareRowId, 0);

            // after the first match and check, all compares are with row id
            if (compare == 0 && session != null && !compareRowId
                    && session.database.txManager.isMVRows()) {
                if (!isEqualReadable(session, store, n)) {
                    compareRowId = true;
                    compare = compareRowForInsertOrDelete(session, row,
                                                          currentRow,
                                                          compareRowId,
                                                          colIndex.length);
                }
            }

            if (compare == 0) {
                Constraint c = null;

                if (isConstraint) {
                    c = ((Table) table).getUniqueConstraintForIndex(this);
                }

                if (c == null) {
                    throw Error.error(ErrorCode.X_23505, name.statementName);
                } else {
                    throw c.getException(row.getData());
                }
            }

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

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

        x = x.set(store, isleft, ((RowAVL) row).getNode(position));

        balance(store, x, isleft);
    }

    public void delete(Session session, PersistentStore store, Row row) {

        row = (Row) store.get(row, false);

        NodeAVL x = ((RowAVL) row).getNode(position);

        if (x == null) {
            return;
        }

        NodeAVL n;

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

            x = x.getLeft(store);

            while (true) {
                NodeAVL temp = x.getRight(store);

                if (temp == null) {
                    break;
                }

                x = temp;
            }

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

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

            x = x.setBalance(store, d.getBalance(store));
            d = d.setBalance(store, b);

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

            if (d.isRoot(store)) {
                store.setAccessor(this, x);
            }

            x = x.setParent(store, dp);

            if (dp != null) {
                if (dp.isRight(store, d)) {
                    dp = dp.setRight(store, x);
                } else {
                    dp = dp.setLeft(store, x);
                }
            }

            // relink d.parent, x.left, x.right
            if (d.equals(xp)) {
                d = d.setParent(store, x);

                if (d.isLeft(store, x)) {
                    x = x.setLeft(store, d);

                    NodeAVL dr = d.getRight(store);

                    x = x.setRight(store, dr);
                } else {
                    x = x.setRight(store, d);

                    NodeAVL dl = d.getLeft(store);

                    x = x.setLeft(store, dl);
                }
            } else {
                d  = d.setParent(store, xp);
                xp = xp.setRight(store, d);

                NodeAVL dl = d.getLeft(store);
                NodeAVL dr = d.getRight(store);

                x = x.setLeft(store, dl);
                x = x.setRight(store, dr);
            }

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

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

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

            d = d.setRight(store, null);
            x = d;
        }

        boolean isleft = x.isFromLeft(store);

        x.replace(store, this, n);

        n = x.getParent(store);

        x.delete();

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

            int sign = isleft ? 1
                              : -1;

            switch (x.getBalance(store) * sign) {

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

                case 0 :
                    x = x.setBalance(store, sign);

                    return;

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

                    if (b * sign >= 0) {
                        x.replace(store, this, r);

                        NodeAVL child = r.child(store, isleft);

                        x = x.set(store, !isleft, child);
                        r = r.set(store, isleft, x);

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

                            return;
                        }

                        x = x.setBalance(store, 0);
                        r = r.setBalance(store, 0);
                        x = r;
                    } else {
                        NodeAVL l = r.child(store, isleft);

                        x.replace(store, this, l);

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

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

    public boolean existsParent(Session session, PersistentStore store,
                                Object[] rowdata, int[] rowColMap) {

        NodeAVL node = findNode(session, store, rowdata, rowColMap,
                                rowColMap.length, OpTypes.EQUAL,
                                TransactionManager.ACTION_REF, false);

        return node != null;
    }

    Return the first node equal to the indexdata object. The rowdata has the
same column mapping as this index.
Params: session – session object
store – store object
rowdata – array containing index column data
matchCount – count of columns to match
compareType – int
reversed – boolean
map – boolean[]
Returns: iterator/**
     * Return the first node equal to the indexdata object. The rowdata has the
     * same column mapping as this index.
     *
     * @param session session object
     * @param store store object
     * @param rowdata array containing index column data
     * @param matchCount count of columns to match
     * @param compareType int
     * @param reversed boolean
     * @param map boolean[]
     * @return iterator
     */
    public RowIterator findFirstRow(Session session, PersistentStore store,
                                    Object[] rowdata, int matchCount,
                                    int distinctCount, int compareType,
                                    boolean reversed, boolean[] map) {

        NodeAVL node = findNode(session, store, rowdata, defaultColMap,
                                matchCount, compareType,
                                TransactionManager.ACTION_READ, reversed);

        if (node == null) {
            return emptyIterator;
        }

        return new IndexRowIterator(session, store, this, node, distinctCount,
                                    false, reversed);
    }

    Return the first node equal to the rowdata object.
The rowdata has the same column mapping as this table.
Params: session – session object
store – store object
rowdata – array containing table row data
Returns: iterator/**
     * Return the first node equal to the rowdata object.
     * The rowdata has the same column mapping as this table.
     *
     * @param session session object
     * @param store store object
     * @param rowdata array containing table row data
     * @return iterator
     */
    public RowIterator findFirstRow(Session session, PersistentStore store,
                                    Object[] rowdata) {

        NodeAVL node = findNode(session, store, rowdata, colIndex,
                                colIndex.length, OpTypes.EQUAL,
                                TransactionManager.ACTION_READ, false);

        if (node == null) {
            return emptyIterator;
        }

        return new IndexRowIterator(session, store, this, node, 0, false,
                                    false);
    }

    Return the first node equal to the rowdata object. The rowdata has the
column mapping provided in rowColMap.
Params: session – session object
store – store object
rowdata – array containing table row data
rowColMap – int[]
Returns: iterator/**
     * Return the first node equal to the rowdata object. The rowdata has the
     * column mapping provided in rowColMap.
     *
     * @param session session object
     * @param store store object
     * @param rowdata array containing table row data
     * @param rowColMap int[]
     * @return iterator
     */
    public RowIterator findFirstRow(Session session, PersistentStore store,
                                    Object[] rowdata, int[] rowColMap) {

        NodeAVL node = findNode(session, store, rowdata, rowColMap,
                                rowColMap.length, OpTypes.EQUAL,
                                TransactionManager.ACTION_READ, false);

        if (node == null) {
            return emptyIterator;
        }

        return new IndexRowIterator(session, store, this, node, 0, false,
                                    false);
    }

    Finds the first node where the data is not null.
Returns: iterator/**
     * Finds the first node where the data is not null.
     *
     * @return iterator
     */
    public RowIterator findFirstRowNotNull(Session session,
                                           PersistentStore store) {

        NodeAVL node = findNode(session, store, nullData, this.defaultColMap,
                                1, OpTypes.NOT,
                                TransactionManager.ACTION_READ, false);

        if (node == null) {
            return emptyIterator;
        }

        return new IndexRowIterator(session, store, this, node, 0, false,
                                    false);
    }

    Returns the row for the first node of the index
Returns: Iterator for first row/**
     * Returns the row for the first node of the index
     *
     * @return Iterator for first row
     */
    public RowIterator firstRow(Session session, PersistentStore store,
                                RangeVariableConditions[] conditions,
                                int distinctCount, boolean[] map) {

        store.readLock();

        try {
            NodeAVL x = getAccessor(store);
            NodeAVL l = x;

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

            while (session != null && x != null) {
                Row row = x.getRow(store);

                if (store.canRead(session, row,
                                  TransactionManager.ACTION_READ, null)) {
                    break;
                }

                x = next(store, x);
            }

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

            return new IndexRowIterator(session, store, this, x,
                                        distinctCount, false, false);
        } finally {
            store.readUnlock();
        }
    }

    public RowIterator firstRow(PersistentStore store) {

        store.readLock();

        try {
            NodeAVL x = getAccessor(store);
            NodeAVL l = x;

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

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

            return new IndexRowIterator(null, store, this, x, 0, false, false);
        } finally {
            store.readUnlock();
        }
    }

    Returns the row for the last node of the index
Returns: last row/**
     * Returns the row for the last node of the index
     *
     * @return last row
     */
    public RowIterator lastRow(Session session, PersistentStore store,
                               int distinctCount, boolean[] map) {

        store.readLock();

        try {
            NodeAVL x = getAccessor(store);
            NodeAVL l = x;

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

            while (session != null && x != null) {
                Row row = x.getRow(store);

                if (store.canRead(session, row,
                                  TransactionManager.ACTION_READ, null)) {
                    break;
                }

                x = last(store, x);
            }

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

            return new IndexRowIterator(session, store, this, x,
                                        distinctCount, false, true);
        } finally {
            store.readUnlock();
        }
    }

    Returns the node after the given one
/**
     * Returns the node after the given one
     */
    NodeAVL next(Session session, PersistentStore store, NodeAVL x,
                 int distinctCount) {

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

        if (distinctCount != 0) {
            return findDistinctNode(session, store, x, distinctCount, false);
        }

        while (true) {
            x = next(store, x);

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

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

            Row row = x.getRow(store);

            if (store.canRead(session, row, TransactionManager.ACTION_READ,
                              null)) {
                return x;
            }
        }
    }

    NodeAVL last(Session session, PersistentStore store, NodeAVL x,
                 int distinctCount) {

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

        if (distinctCount != 0) {
            return findDistinctNode(session, store, x, distinctCount, true);
        }

        while (true) {
            x = last(store, x);

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

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

            Row row = x.getRow(store);

            if (store.canRead(session, row, TransactionManager.ACTION_READ,
                              null)) {
                return x;
            }
        }
    }

    NodeAVL next(PersistentStore store, NodeAVL x) {

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

        RowAVL row = x.getRow(store);

        x = row.getNode(position);

        NodeAVL temp = x.getRight(store);

        if (temp != null) {
            x    = temp;
            temp = x.getLeft(store);

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

            return x;
        }

        temp = x;
        x    = x.getParent(store);

        while (x != null && x.isRight(store, temp)) {
            temp = x;
            x    = x.getParent(store);
        }

        return x;
    }

    NodeAVL next(PersistentStore store, NodeAVL x, int depth, int maxDepth,
                 int[] depths) {

        NodeAVL temp = depth == maxDepth ? null
                                         : x.getRight(store);

        if (temp != null) {
            depth++;

            x    = temp;
            temp = depth == maxDepth ? null
                                     : x.getLeft(store);

            while (temp != null) {
                depth++;

                x = temp;

                if (depth == maxDepth) {
                    temp = null;
                } else {
                    temp = x.getLeft(store);
                }
            }

            depths[0] = depth;

            return x;
        }

        temp = x;
        x    = x.getParent(store);

        depth--;

        while (x != null && x.isRight(store, temp)) {
            temp = x;
            x    = x.getParent(store);

            depth--;
        }

        depths[0] = depth;

        return x;
    }

    NodeAVL last(PersistentStore store, NodeAVL x) {

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

        RowAVL row = x.getRow(store);

        x = row.getNode(position);

        NodeAVL temp = x.getLeft(store);

        if (temp != null) {
            x    = temp;
            temp = x.getRight(store);

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

            return x;
        }

        temp = x;
        x    = x.getParent(store);

        while (x != null && x.isLeft(store, temp)) {
            temp = x;
            x    = x.getParent(store);
        }

        return x;
    }

    boolean isEqualReadable(Session session, PersistentStore store,
                            NodeAVL node) {

        NodeAVL  c = node;
        Object[] data;
        Object[] nodeData;
        Row      row;

        row = node.getRow(store);

        if (store.canRead(session, row, TransactionManager.ACTION_DUP, null)) {
            if (row.isCurrentSystemVersion()) {
                return true;
            }
        }

        data = node.getData(store);

        while (true) {
            c = last(store, c);

            if (c == null) {
                break;
            }

            nodeData = c.getData(store);

            if (compareRow(session, data, nodeData) == 0) {
                row = c.getRow(store);

                if (store.canRead(session, row, TransactionManager.ACTION_DUP,
                                  null)) {
                    if (row.isCurrentSystemVersion()) {
                        return true;
                    }
                }

                continue;
            }

            break;
        }

        while (true) {
            c = next(session, store, node, 0);

            if (c == null) {
                break;
            }

            nodeData = c.getData(store);

            if (compareRow(session, data, nodeData) == 0) {
                row = c.getRow(store);

                if (store.canRead(session, row, TransactionManager.ACTION_DUP,
                                  null)) {
                    if (row.isCurrentSystemVersion()) {
                        return true;
                    }
                }

                continue;
            }

            break;
        }

        return false;
    }

    Finds a match with a row from a different table
Params: session – Session
store – PersistentStore
rowdata – array containing data for the index columns
rowColMap – map of the data to columns
fieldCount – int
compareType – int
readMode – int
reversed – boolean
Returns: matching node or null/**
     * Finds a match with a row from a different table
     *
     * @param session Session
     * @param store PersistentStore
     * @param rowdata array containing data for the index columns
     * @param rowColMap map of the data to columns
     * @param fieldCount int
     * @param compareType int
     * @param readMode int
     * @param reversed boolean
     * @return matching node or null
     */
    NodeAVL findNode(Session session, PersistentStore store, Object[] rowdata,
                     int[] rowColMap, int fieldCount, int compareType,
                     int readMode, boolean reversed) {

        store.readLock();

        try {
            NodeAVL x          = getAccessor(store);
            NodeAVL n          = null;
            NodeAVL result     = null;
            Row     currentRow = null;

            if (compareType != OpTypes.EQUAL
                    && compareType != OpTypes.IS_NULL) {
                fieldCount--;

                if (compareType == OpTypes.SMALLER
                        || compareType == OpTypes.SMALLER_EQUAL
                        || compareType == OpTypes.MAX) {
                    reversed = true;
                }
            }

            while (x != null) {
                currentRow = x.getRow(store);

                int i = 0;

                if (fieldCount > 0) {
                    i = compareRowNonUnique(session, currentRow.getData(),
                                            rowdata, rowColMap, fieldCount);
                }

                if (i == 0) {
                    switch (compareType) {

                        case OpTypes.MAX :
                        case OpTypes.IS_NULL :
                        case OpTypes.EQUAL : {
                            result = x;

                            if (reversed) {
                                n = x.getRight(store);
                            } else {
                                n = x.getLeft(store);
                            }

                            break;
                        }
                        case OpTypes.NOT :
                        case OpTypes.GREATER : {
                            i = compareObject(session, currentRow.getData(),
                                              rowdata, rowColMap, fieldCount,
                                              compareType);

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

                            break;
                        }
                        case OpTypes.GREATER_EQUAL_PRE :
                        case OpTypes.GREATER_EQUAL : {
                            i = compareObject(session, currentRow.getData(),
                                              rowdata, rowColMap, fieldCount,
                                              compareType);

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

                            break;
                        }
                        case OpTypes.SMALLER : {
                            i = compareObject(session, currentRow.getData(),
                                              rowdata, rowColMap, fieldCount,
                                              compareType);

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

                            break;
                        }
                        case OpTypes.SMALLER_EQUAL : {
                            i = compareObject(session, currentRow.getData(),
                                              rowdata, rowColMap, fieldCount,
                                              compareType);

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

                            break;
                        }
                        default :
                            throw Error.runtimeError(ErrorCode.U_S0500,
                                                     "Index");
                    }
                } else if (i < 0) {
                    n = x.getRight(store);
                } else if (i > 0) {
                    n = x.getLeft(store);
                }

                if (n == null) {
                    break;
                }

                x = n;
            }

            // MVCC 190
            if (session == null) {
                return result;
            }

            while (result != null) {
                currentRow = result.getRow(store);

                if (store.canRead(session, currentRow, readMode, colIndex)) {
                    break;
                }

                result = reversed ? last(store, result)
                                  : next(store, result);

                if (result == null) {
                    break;
                }

                currentRow = result.getRow(store);

                if (fieldCount > 0
                        && compareRowNonUnique(
                            session, currentRow.getData(), rowdata, rowColMap,
                            fieldCount) != 0) {
                    result = null;

                    break;
                }
            }

            return result;
        } finally {
            store.readUnlock();
        }
    }

    NodeAVL findDistinctNode(Session session, PersistentStore store,
                             NodeAVL node, int fieldCount, boolean reversed) {

        store.readLock();

        try {
            NodeAVL  x          = getAccessor(store);
            NodeAVL  n          = null;
            NodeAVL  result     = null;
            Row      currentRow = null;
            Object[] rowData    = node.getData(store);

            while (x != null) {
                currentRow = x.getRow(store);

                int i = 0;

                i = compareRowNonUnique(session, currentRow.getData(),
                                        rowData, colIndex, fieldCount);

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

                if (n == null) {
                    break;
                }

                x = n;
            }

            // MVCC 190
            if (session == null) {
                return result;
            }

            while (result != null) {
                currentRow = result.getRow(store);

                if (store.canRead(session, currentRow,
                                  TransactionManager.ACTION_READ, colIndex)) {
                    break;
                }

                result = reversed ? last(store, result)
                                  : next(store, result);
            }

            return result;
        } finally {
            store.readUnlock();
        }
    }

    Balances part of the tree after an alteration to the index.
/**
     * Balances part of the tree after an alteration to the index.
     */
    void balance(PersistentStore store, NodeAVL x, boolean isleft) {

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

            switch (x.getBalance(store) * sign) {

                case 1 :
                    x = x.setBalance(store, 0);

                    return;

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

                case -1 :
                    NodeAVL l = x.child(store, isleft);

                    if (l.getBalance(store) == -sign) {
                        x.replace(store, this, l);

                        x = x.set(store, isleft, l.child(store, !isleft));
                        l = l.set(store, !isleft, x);
                        x = x.setBalance(store, 0);
                        l = l.setBalance(store, 0);
                    } else {
                        NodeAVL r = l.child(store, !isleft);

                        x.replace(store, this, r);

                        l = l.set(store, !isleft, r.child(store, isleft));
                        r = r.set(store, isleft, l);
                        x = x.set(store, isleft, r.child(store, !isleft));
                        r = r.set(store, !isleft, x);

                        int rb = r.getBalance(store);

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

                    return;
            }

            if (x.isRoot(store)) {
                return;
            }

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

    NodeAVL getAccessor(PersistentStore store) {

        NodeAVL node = (NodeAVL) store.getAccessor(this);

        return node;
    }

    IndexRowIterator getIterator(Session session, PersistentStore store,
                                 NodeAVL x, boolean single, boolean reversed) {

        if (x == null) {
            return emptyIterator;
        } else {
            IndexRowIterator it = new IndexRowIterator(session, store, this,
                x, 0, single, reversed);

            return it;
        }
    }

    public static final class IndexRowIterator implements RowIterator {

        final Session         session;
        final PersistentStore store;
        final IndexAVL        index;
        NodeAVL               nextnode;
        Row                   lastrow;
        int                   distinctCount;
        boolean               single;
        boolean               reversed;

        When session == null, rows from all sessions are returned
/**
         * When session == null, rows from all sessions are returned
         */
        public IndexRowIterator(Session session, PersistentStore store,
                                IndexAVL index, NodeAVL node,
                                int distinctCount, boolean single,
                                boolean reversed) {

            this.session       = session;
            this.store         = store;
            this.index         = index;
            this.distinctCount = distinctCount;
            this.single        = single;
            this.reversed      = reversed;

            if (index == null) {
                return;
            }

            nextnode = node;
        }

        public Object getField(int col) {

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

            return lastrow.getData()[col];
        }

        public boolean next() {

            getNextRow();

            return lastrow != null;
        }

        public Row getCurrentRow() {
            return lastrow;
        }

        public Object[] getCurrent() {

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

            return lastrow.getData();
        }

        private Row getNextRow() {

            if (nextnode == null) {
                release();

                lastrow = null;

                return null;
            }

            NodeAVL lastnode = nextnode;

            if (single) {
                nextnode = null;
            } else {
                store.readLock();

                try {
                    while (true) {
                        if (reversed) {
                            nextnode = index.last(session, store, nextnode,
                                                  distinctCount);
                        } else {
                            nextnode = index.next(session, store, nextnode,
                                                  distinctCount);
                        }

                        if (nextnode == null) {
                            break;
                        }

                        Row row = nextnode.getRow(store);

                        if (session == null
                                || store.canRead(
                                    session, row,
                                    TransactionManager.ACTION_READ, null)) {
                            break;
                        }
                    }
                } finally {
                    store.readUnlock();
                }
            }

            lastrow = lastnode.getRow(store);

            return lastrow;
        }

        public void removeCurrent() {
            store.delete(session, lastrow);
            store.remove(lastrow);
        }

        public void release() {}

        public long getRowId() {
            return lastrow.getPos();
        }
    }
}
Author:	Thomas Mueller (Hypersonic SQL Group), Fred Toussi (fredt@users dot sourceforge.net)
Version:	2.5.0
Since:	Hypersonic SQL
Params:	session – Session a – row from another table rowColMap – column indexes in the other table b – a full row in this table
Returns:	comparison result, -1,0,+1
Params:	session – Session newRow – data existingRow – data useRowId – boolean start – int
Returns:	comparison result, -1,0,+1
Params:	session – session object store – store object rowdata – array containing index column data matchCount – count of columns to match compareType – int reversed – boolean map – boolean[]
Returns:	iterator
Params:	session – Session store – PersistentStore rowdata – array containing data for the index columns rowColMap – map of the data to columns fieldCount – int compareType – int readMode – int reversed – boolean
Returns:	matching node or null
/

org.hsqldb/ hsqldb/ 2.5.0/ org/hsqldb/index/IndexAVL.java
