Quadcap Embeddable Database

com/quadcap/sql/file/BlockPath.java

Go to the documentation of this file.

package com.quadcap.sql.file;

/* Copyright 1997 - 2003 Quadcap Software.  All rights reserved.
 *
 * This software is distributed under the Quadcap Free Software License.
 * This software may be used or modified for any purpose, personal or
 * commercial.  Open Source redistributions are permitted.  Commercial
 * redistribution of larger works derived from, or works which bundle
 * this software requires a "Commercial Redistribution License"; see
 * http://www.quadcap.com/purchase.
 *
 * Redistributions qualify as "Open Source" under  one of the following terms:
 *   
 *    Redistributions are made at no charge beyond the reasonable cost of
 *    materials and delivery.
 *
 *    Redistributions are accompanied by a copy of the Source Code or by an
 *    irrevocable offer to provide a copy of the Source Code for up to three
 *    years at the cost of materials and delivery.  Such redistributions
 *    must allow further use, modification, and redistribution of the Source
 *    Code under substantially the same terms as this license.
 *
 * Redistributions of source code must retain the copyright notices as they
 * appear in each source code file, these license terms, and the
 * disclaimer/limitation of liability set forth as paragraph 6 below.
 *
 * Redistributions in binary form must reproduce this Copyright Notice,
 * these license terms, and the disclaimer/limitation of liability set
 * forth as paragraph 6 below, in the documentation and/or other materials
 * provided with the distribution.
 *
 * The Software is provided on an "AS IS" basis.  No warranty is
 * provided that the Software is free of defects, or fit for a
 * particular purpose.  
 *
 * Limitation of Liability. Quadcap Software shall not be liable
 * for any damages suffered by the Licensee or any third party resulting
 * from use of the Software.
 */

import java.io.IOException;

import com.quadcap.util.Debug;

/**
 * This class is used to locate a specified offset within a randomly
 * accessible <code>BlockAccess</code> object.  The path has two
 * components, a logical component, <b>p</b> which specifies the offsets of the
 * block references needed to locate the block and position corresponding
 * to the selected byte, and a physical component <b>r</b> which contains
 * the block references of the blocks needed to locate the actual byte.
 *
 * @author Stan Bailes
 */

class BlockPath {
    /** The actual bytes */
    BlockAccess         a;
    /** Depth of this path */
    int                 depth;
    /** Byte offset info 'a' */
    long                pos;
    /** Logical path */
    int[]               p;
    /** Block refs */
    long[]              r;
    /** A temporary (logical) path */
    int[]               tp;

    /**
     * Construct a new BlockPath to represent the specified byte in the
     * specified region.
     *
     * @param a the region into which the index is made
     * @param pos the byte offset in the region
     */
    public BlockPath(BlockAccess a, long pos) throws IOException {
        this.a = a;
        this.pos = pos;

        depth = a.depth;
        
        p = new int[depth + 1];
        r = new long[depth + 1];
        tp = new int[depth + 1];

        getPath(pos, p);
        getRefs();
    }

    /**
     * Return the block which actually contains the data.  This is the
     * final block in the path.
     * <p>
     * <B>NOTE</b>: This block needs to have its reference count decremented
     * when you're done with it!!
     */
    public final Page getLeafBlock() throws IOException {
        return a.file.getPage(r[r.length-1]);
    }

    /**
     * Return the byte offset within the leaf block where the designated
     * byte can be found.
     */
    public final int getBufPos() {
        return p[p.length-1];
    }

    /**
     * Return the depth of this path
     */
    public final int getDepth() { return depth; }

    /**
     * Return the current position referred to by this path
     */
    public final long getPos() { return pos; }


    /**
     * Return the current position referred to by this path
     */
    public final void setPos(long newpos) throws IOException {
        if (newpos != pos) {
            getPath(newpos, tp);
            updatePath(tp);
            pos = newpos;
        }
    }

    /**
     * Adjust this BlockPath to point to a new location, with a minimum
     * number of block accesses.
     *
     * @param cnt  The offset from the current location
     */
    public final void incr(long offset) throws IOException {
        setPos(pos + offset);
    }

    /**
     * Build the (logical) path vector for a specified byte in the region.
     */
    private final void getPath(long pos, int[] path) {
        //Debug.println("getPath(" + pos + ")");
        int len = a.radices.length;
        for (int i = 0; i < len; i++) {
            path[i] = (int)(pos / a.radices[i]);
            pos %= a.radices[i];
            //Debug.println("   " + i + ": " + path[i] + " (" + a.radices[i] +
            //              ", pos = " + pos + ")");
        }
        path[len] = (int)pos;
        //Debug.println(" * " + len + ": " + path[len]);
    }

    /**
     * Find the actual block refs, given the logical path vector.
     */
    private final void getRefs() throws IOException {
        r[0] = a.rootBlock;
        for (int i = 1; i < r.length; i++) {
            try {
                Page b = a.file.getPage(r[i-1]);
                try {
                    r[i] = a.makeBlockRef(b, p[i-1], i==1);
                } finally {
                    b.decrRefCount();
                }
            } catch (IOException ex) {
                Debug.println("getRefs, i = " + i +
                              ", r[" + i + "]=" +
                              SubPageManager.toString(r[i-1]));
                Debug.println("this = " + this);
                throw ex;
            } catch (RuntimeException ex) {
                Debug.println("getRefs, i = " + i +
                              ", r[" + i + "]=" +
                              SubPageManager.toString(r[i-1]));
                Debug.println("this = " + this);
                throw ex;
            }
        }
    }

    /**
     * Update the block refs, given a new logical path, attempting
     * to minimize the number of block accesses.
     */
    private final void updatePath(int[] path) throws IOException {
        if (true) {
            this.p = path;
            getRefs();
        } else {
            boolean update = false;
            for (int i = 1; i < r.length; i++) {
                update |= (p[i-1] != path[i-1]);
                p[i-1] = path[i-1];
                if (update) {
                    Page b = a.file.getPage(r[i-1]);
                    try {
                        r[i] = a.makeBlockRef(b, path[i-1], i==1);
                    } finally {
                        b.decrRefCount();
                    }
                }
            }
            p[r.length-1] = path[r.length-1];
        }
    }

    //#ifdef DEBUG
    /**
     * For debugging, return a displayable representation of this BlockPath.
     */
    public String toString() {
        StringBuffer sb = new StringBuffer();
        sb.append("Path[" + pos + "] p(");
        for (int i = 0; i < p.length; i++) {
            if (i > 0) sb.append(", ");
            sb.append("" + p[i]);
        }
        sb.append(") r(");
        for (int i = 0; i < r.length; i++) {
            if (i > 0) sb.append(", ");
            sb.append("" + SubPageManager.toString(r[i]));
        }
        sb.append(")");
        return sb.toString();
    }
    //#endif

}