Quadcap Embeddable Database

com/quadcap/sql/file/BlockAccess.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.ConfigNumber;
import com.quadcap.util.Debug;
import com.quadcap.util.Util;

/**
 * This class implements a randomly accessible, growable region within
 * a <b>BlockFile</b> object.  The region is defined by a root block,
 * which either contains the entire data for the region (if it will fit),
 * or contains a set of references to secondary blocks which contain the
 * actual data.  If the region is large enough, those secondary blocks
 * themselves may be references, and so on.
 *
 * @author Stan Bailes
 */

public class BlockAccess extends RandomAccess {
    static final int HEADER_SIZE        = 8;    // size of 'header' in bytes
    static final int REF_SIZE           = 8;    // size of a ref, in bytes

    /**
     * The underlying store.
     */
    PageManager         file;
    
    /**
     * The 'root' block of this data area.
     * The format of this block is as follows:
     * <p>Bytes 0-3: The size of this data area, in bytes.
     */
    long                rootBlock;
    long                size;

    /**
     * A vector of <b>depth</b> elements, indicating the size of
     * the recursive sub-block at each level.
     */
    int[]               radices         = null;

    byte[]              b1              = new byte[1];

    /**
     * Depth of this data area.  A depth of zero indicates
     * that the actual data area is entirely contained within the
     * root block.  A depth of one indicates that the data is contained
     * in sub-blocks, and the root block contains the block numbers of
     * the sub-blocks.  Larger depths indicate that the sub-blocks
     * contain pointers to other sub-blocks, etc.
     */
    int                 depth           = 0;

    /**
     * Path from root to leaf blocks
     */
    BlockPath           path            = null;

    /**
     * The file lock
     */
    Object              fileLock        = null;

    /**
     * Default public constructor
     */
    public BlockAccess() {}
    
    /**
     * Construct a new <tt>BlockAccess</tt> attached to the specified
     * block.
     */
    public BlockAccess(PageManager file, long rootBlock) throws IOException {
        init(file, rootBlock);
    }

    public void init(PageManager file, long rootBlock) throws IOException {
        this.file = file;
        this.fileLock = file.getLock();
        this.rootBlock = rootBlock;
        this.path = null;

        synchronized (fileLock) {
            Page root = file.getPage(rootBlock);
            try {
                this.size = root.readLong(0);
                //#ifdef DEBUG
                if (Trace.bit(3)) {
                    Debug.println("INIT: " + this);
                }
                //#endif
            } finally {
                root.decrRefCount();
            }
        }
        this.depth = depthForSize(this.size);
        this.radices = radicesForDepth(this.depth);
    }

    /**
     * Return the size of this region
     */
    public long size() {
        return this.size;
    }

    /**
     * Resize the region.
     */
    public void resize(long newSize) throws IOException {
        //#ifdef DEBUG
        if (Trace.bit(2)) {
            Debug.println("BlockAccess[" + toString(rootBlock) + ":" + size + 
                          "] resize(" + newSize + ")");
        }
        //#endif
        synchronized (fileLock) {
            Page root = file.getPage(rootBlock);
            try {
                long curSize = root.readLong(0);
                byte[] bufx = new byte[bufLen()];
                int rsize = bufx.length - HEADER_SIZE;
                this.size = newSize;
        
                int newDepth = depthForSize(newSize);
                while (newDepth > depth) {          
                    // ---- growing
                    long newPage = file.newPage();
                    Page b = file.getPage(newPage);
                    try {
                        root.read(HEADER_SIZE, bufx, 0, rsize);
                        root.clear();
                        b.write(0, bufx, 0, rsize);
                        setBlockRef(root, 0, newPage, true);
                        radices = radicesForDepth(++depth);
                    } finally {
                        b.decrRefCount();
                    }
                }
        
                while (newDepth < depth) {
                    // ---- shrinking
                    for (int i = 1; i < refsForLevel(0); i++) {
                        long blk = getBlockRef(root, i, true);
                        if (blk != 0) {
                            file.freePage(blk);
                            setBlockRef(root, i, 0, true);
                        }
                    }
                    long freePage = getBlockRef(root, 0, true);
                    Page b = file.getPage(freePage);
                    try {
                        b.read(0, bufx, 0, rsize);
                        root.write(HEADER_SIZE, bufx, 0, rsize);
                        radices = radicesForDepth(--depth);
                    } finally {
                        b.decrRefCount();
                    }
                    file.freePage(freePage);
                }
                root.writeLong(0, newSize);
            } finally {
                root.decrRefCount();
            }
        }
    }

    /**
     * Write into the data region.
     *
     * @param pos the starting position to write
     * @param buf the buffer containing the data to write
     * @param offset the position of the first byte in the buffer
     * @param len the number of bytes to write
     */
    public void write(long pos, byte[] buf, int offset, int len)
        throws IOException
    {
        synchronized (fileLock) {
            //#ifdef DEBUG
            if (Trace.bit(2)) {
                Debug.println("[" + toString(rootBlock) + ":" + size + 
                              "] write(" + 
                              pos + ", " + Util.strBytes(buf, offset, len) + ")");
            }
            //#endif
            Page root = file.getPage(rootBlock);
            try {
                BlockPath p = getPath(pos);
                int hdr = (depth >= 1) ? 0 : HEADER_SIZE;
                while (len > 0) {
                    int bufloc = p.getBufPos();
                    int amt = Math.min(len, (bufLen() - hdr) - bufloc);
                    Page b = p.getLeafBlock();
                    try {
                        b.write(bufloc + hdr, buf, offset, amt);
                    } finally {
                        b.decrRefCount();
                    }
                    len -= amt;
                    offset += amt;
                    //pos += amt;       // pos used only for debug
                    //Debug.println("Before incr: " + this);
                    if (len > 0) p.incr(amt);
                }
            } finally {
                root.decrRefCount();
            }
        }
    }

    /**
     * Read from the data region.
     */
    public void read(long pos, byte[] buf, int offset, int len)
        throws IOException
    {
        //#ifdef DEBUG
        if (pos + len > size) {
            throw new IOException("BlockAccess.read() out of bounds: " +
                                  "pos = " + pos +
                                  ", len = " + len +
                                  ", size = " + size());
        }
        long save_pos = pos;
        int save_offset = offset;
        int save_len = len;
        //#endif

        synchronized (fileLock) {
            Page root = file.getPage(rootBlock);
            try {
                BlockPath p = getPath(pos);
                int hdr = (depth >= 1) ? 0 : HEADER_SIZE;
                while (len > 0) {
                    int bufloc = p.getBufPos();
                    int amt = Math.min(len, (bufLen() - hdr) - bufloc);
                    //#ifdef DEBUG
                    if (amt <= 0) {
                        Debug.println("pos = " + pos + ", offset = " + offset +
                                      ", len = " + len + ", bufloc = " + bufloc +
                                      ", bufLen() = " + bufLen());
                        Debug.println("save_pos = " + save_pos +
                                      ", save_offset = " + save_offset +
                                      ", save_len = " + save_len);
                        Debug.println("p = " + p);
                        Debug.println("size = " + size);
                        Debug.println("depth = " + depth);
                        for (int i = 0; i < radices.length; i++) {
                            Debug.println("radix[" + i + "] = " + radices[i]);
                        }
                        throw new RuntimeException("Internal error: amt: " + amt);
                    }
                    //#endif
                    Page b = p.getLeafBlock();
                    try {
                        b.read(bufloc + hdr, buf, offset, amt);
                    } finally {
                        b.decrRefCount();
                    }
                    len -= amt;
                    offset += amt;
                    //pos += amt;
                    if (len > 0) p.incr(amt);
                }
            } finally {
                root.decrRefCount();
            }
        }
    }

    /**
     * Finalization: We're done with this region.
     */
    public void close() {
    }

    public void flush() {
    }

    private final BlockPath getPath(long pos) throws IOException {
        if (path == null || depth != path.getDepth()) {
            path = new BlockPath(this, pos);
        } else {
            path.setPos(pos);
        }
        return path;
    }

    /**
     * Build the radices array for a region of the specified depth.
     */
    final int[] radicesForDepth(int depth) {
        int[] v = new int[depth];
        int r = bufLen();
        for (int i = depth-1; i >= 0; i--) {
            v[i] = r;
            r *= refsForLevel(i);
        }
        return v;
    }

    /**
     * Return the specified block reference.  This method treats the data
     * portion of the block as an array of integer blockrefs.
     *
     * @param b the block containing the array of blockrefs
     * @param pos the location in the blockref array of the block number
     *  to fetch.
     */
    final long getBlockRef(Page b, int pos, boolean isRoot)
        throws IOException
    {
        int offset = pos * REF_SIZE + (isRoot ? HEADER_SIZE : 0);
        long ref = b.readLong(offset);
        return ref;
    }

    /**
     * Return the specified block reference.  This method treats the data
     * portion of the block as an array of long blockrefs.  If the
     * selected blockref is zero, this routine will allocate a new
     * block and return the blockref of the newly created block, as well
     * as update <tt>b</tt>'s blockref array with the new blockref.
     *
     * @param b the block containing the array of blockrefs
     * @param pos the location in the blockref array of the block number
     *  to fetch.
     */
    final long makeBlockRef(Page b, int pos, boolean isRoot)
        throws IOException
    {
        int offset = pos * REF_SIZE + (isRoot ? HEADER_SIZE : 0);
        long ref = b.readLong(offset);
        if (ref == 0) {
            ref = file.newPage();
            b.writeLong(offset, ref);
        }
        return ref;
    }

    /**
     * Set the specified block reference.
     *
     * @param b the block containing the array of blockrefs
     * @param pos the (zero-offset) index of the blockref within the array
     * @param val the value to store in the array
     */
    final void setBlockRef(Page b, int pos, long val, boolean isRoot) {
        int offset = pos * REF_SIZE + (isRoot ? HEADER_SIZE : 0);
        b.writeLong(offset, val);
    }
    
    /**
     * Return the number of blockrefs that will fit in a block.
     */
    final int refsForLevel(int level) {
        return (bufLen() - (level == 0 ? HEADER_SIZE : 0)) / REF_SIZE;
    }

    /**
     * Return the size of the data portion of the block.
     */
    final int bufLen() {
        return file.getPageSize();
    }

    /**
     * Return the maximum size for a region of the specified depth.
     */
    private final long maxSizeForDepth(int level) {
        if (level == 0) {
            return bufLen() - HEADER_SIZE;
        }
        long ret = bufLen();
        for (int i = 0; i < level; i++) {
            ret *= refsForLevel(i);
        }
        return ret;
    }

    /**
     * Return the depth necessary to represent a region of the specified size
     *
     * @param size the size of the region
     */
    private final int depthForSize(long size) {
        if (size <= bufLen() - HEADER_SIZE) return 0;

        int ret = 1;
        long max = bufLen() * refsForLevel(0);

        while (size > max) {
            max *= refsForLevel(++ret);
        }
        return ret;
    }

    //#ifdef DEBUG
    final String toString(long page) {
        return SubPageManager.toString(page);
    }

    public String toString() {
        StringBuffer sb = new StringBuffer("BlockAccess(");
        sb.append("root=");
        sb.append(SubPageManager.toString(rootBlock));
        sb.append("  size=");
        sb.append(size);
        if (radices != null) {
            sb.append("  radices=");
            for (int i = 0; i < radices.length; i++) {
                if (i>0) sb.append(',');
                sb.append(radices[i]);
            }
        }
        sb.append("  depth=");
        sb.append(depth);
        sb.append("  path=");
        sb.append(path);
        sb.append(")");
        return sb.toString();
    }
    //#endif
}