Quadcap Embeddable Database

com/quadcap/sql/index/Btree.java

Go to the documentation of this file.

package com.quadcap.sql.index;

/* 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 java.io.PrintWriter;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

import com.quadcap.sql.file.BlockFile;

import com.quadcap.util.Debug;
import com.quadcap.util.Util;

/**
 * A Btree implementation.  Most of the real work happens in the Bnode
 * class.
 *
 * @author Stan Bailes
 */
public class Btree implements BIndex {
    BlockFile           file;
    Comparator          compare;
    long                rootBlock;
    Bnode               root;
    Object              lock;
    byte[]              tbuf = new byte[16];

    /**
     * Open a btree index.  Fetch the root block and create an empty tree if
     * the block is zero, open the existing tree otherwise.
     *
     * @param file the (already opened) blockfile
     * @param compare the compare function for key ordering
     * @param rootBlock the block number of the root block of this tree
     * @param create if true, initialize the rootblock to be empty.
     *          
     * @exception IOException if an I/O error occurs opening or accessing
     *          the file.
     */
    public Btree(BlockFile file, Comparator compare,
                 long rootBlock, boolean create)
        throws IOException
    {
        //#ifdef DEBUG
        if (Trace.bit(0)) {
            Debug.println("Btree(" + file + ", " + rootBlock + ", " +
                          create + ")");
        }
        //#endif
        this.file = file;
        this.lock = file.getLock();
        this.compare = compare;
        this.rootBlock = rootBlock;
        this.root = getNode(rootBlock);
        if (create) {
            root.init(true);
        } else {
            root.checkMagic();
        }
    }

    /**
     * Open a btree index.  Fetch the root block and create an empty tree if
     * the block is zero, open the existing tree otherwise.
     *
     * @param file the (already opened) blockfile
     * @param rootBlock the block number of the root block of this tree
     * @param create if true, initialize the rootblock to be empty.
     *          
     * @exception IOException if an I/O error occurs opening or accessing
     *          the file.
     */
    public Btree(BlockFile file, long rootBlock, boolean create)
        throws IOException
    {
        this(file, Comparator.compare, rootBlock, create);
    }

    public int size() throws IOException {
        return getRoot().size();
    }

    final private BCursor getMyCursor() throws IOException {
        return BtreeCursor.get(this, true);
        // *Don't* put in activeCursors
    }
    
    /**
     * Get the data bytes for the specified key.  If the key is found,
     * return the length of the data portion and place as many bytes
     * as will fit in the data array.  If the key isn't found, return
     * -1.
     */
    public int get(byte[] key, int klen, byte[] data) throws IOException {
        synchronized (lock) {
            BCursor cursor = getMyCursor();
            try {
                if (!cursor.seek(key)) return -1;
                return cursor.getVal(data);
            } finally {
                cursor.release();
            }
        }
    }

    public byte[] get(byte[] key) throws IOException {
        synchronized (lock) {
            BCursor cursor = getMyCursor();
            try {
                if (!cursor.seek(key, key.length)) return null;
                int len = cursor.getValLen();
                byte[] ret = new byte[len];
                if (cursor.getVal(ret) != len) {
                    throw new IOException("What the hella?");
                }
                return ret;
            } finally {
                cursor.release();
            }
        }
    }

    public boolean delete(byte[] key) throws IOException {
        synchronized (lock) {
            BCursor cursor = getMyCursor();
            try {
                boolean ret = cursor.seek(key, key.length);
                if (ret) ret = cursor.delete();
                return ret;
            } finally {
                cursor.release();
            }
        }
    }

    public boolean deleteObs(byte[] key) throws IOException {
        synchronized (lock) {
            //#ifdef DEBUG
            if (Trace.bit(0)) {
                Debug.println(0, "BTree[" + rootBlock + "].delete(" +
                              Util.hexBytes(key) + ")");
            }
            //#endif
            return getRoot().delete(key);
        }
    }

    public void set(byte[] key, byte[] val) throws IOException {
        set(key, key.length, val, 0, val.length);
    }

    public void insert(byte[] key, int klen,
                       byte[] val, int off, int len) throws IOException {
        synchronized (lock) {
            //#ifdef DEBUG
            if (Trace.bit(0)) {
                Debug.println("Btree[" + rootBlock + "].insert(" +
                              Util.hexBytes(key, 0, klen) + ", " +
                              Util.hexBytes(val, off, len) + ")");
            }
            //#endif
            getRoot().set(key, klen, val, off, len, true, false);
            notifyUpdate(null);
        }
    }
    
    public void update(byte[] key, int klen,
                       byte[] val, int off, int len) throws IOException {
        synchronized (lock) {
            //#ifdef DEBUG
            if (Trace.bit(0)) {
                Debug.println("Btree[" + rootBlock + "].update(" +
                              Util.hexBytes(key, 0, klen) + ", " +
                              Util.hexBytes(val, off, len) + ")");
            }
            //#endif
            getRoot().set(key, klen, val, off, len, false, true);
            notifyUpdate(null);
        }
    }
    
    public boolean set(byte[] key, int klen,
                       byte[] val, int off, int len) throws IOException {
        synchronized (lock) {
            //#ifdef DEBUG
            if (Trace.bit(0)) {
                Debug.println("Btree[" + rootBlock + "].set(" +
                              Util.hexBytes(key) + ", " +
                              Util.hexBytes(val) + ")");
            }
            //#endif
            boolean ret = getRoot().set(key, klen, val, off, len, true, true);
            notifyUpdate(null);
            return ret;
        }
    }
    
    Bnode getNode(long ref) {
        return new Bnode(this, ref);
    }

    Bnode getRoot() { return root; }

    public long getRootBlock() {
        return rootBlock;
    }

    void setRoot(long ref) {
        root = getNode(rootBlock = ref);
    }

    /**
     * Return a reference to the underlying <code>BlockFile</code.
     */
    public BlockFile getFile() { return file; }

    /**
     * Return the comparator used to collate keys
     */
    public Comparator getComparator() {
        return compare;
    }

    /**
     * Get a cursor
     */
    public BCursor getCursor() throws IOException {
        return getCursor(false);
    }

    Set activeCursors = new HashSet();
    
    /**
     * Get a cursor
     */
    public BCursor getCursor(boolean skipSetup) throws IOException {
        BCursor bc = null;
        synchronized (lock) {
            bc = BtreeCursor.get(this, skipSetup);
            activeCursors.add(bc);
        }
        return bc;
    }

    public void releaseCursor(BCursor c) {
        synchronized (lock) {
            try {
                c.close();
            } catch (Throwable t) {}
            activeCursors.remove(c);
        }
    }

    public void notifyUpdate(BCursor notMe) {
        final Iterator iter = activeCursors.iterator();
        while (iter.hasNext()) {
            BtreeCursor bc = (BtreeCursor)iter.next();
            if (bc != notMe) bc.unsetup();
        }
    }
    
    /**
     * Destroy this tree and free all of its resources
     */
    public void free() throws IOException {
        //#ifdef DEBUG
        if (activeCursors.size() > 0) {
            final Iterator iter = activeCursors.iterator();
            while (iter.hasNext()) {
                BtreeCursor ac = (BtreeCursor)iter.next();
                Debug.println("Active cursor: " + ac);
                Debug.println("Error detected at: " + Util.stackTrace());
                try {
                    ac.release();
                } catch (Throwable t) {
                }
            }
            throw new IOException("Btree.free() called with active cursors");
        }
        if (Trace.bit(0)) {
            Debug.println("Btree[" + rootBlock + "].free()");
            //Debug.println(Util.stackTrace());
        }
        //#endif
        getRoot().free();
    }

    //#ifdef DEBUG
    public String toString() {
        return "Btree[" + rootBlock + "]";
    }

    public void display(PrintWriter w) throws IOException {
        BCursor bc = getCursor(false);
        try {
            while (bc.next()) {
                w.println("[" + new String(bc.getKey()) + "] = " +
                          new String(bc.getVal()));
            }
        } finally {
            bc.release();
        }
        
    }
    //#endif
}