Quadcap Embeddable Database

com/quadcap/sql/index/BtreeCursor.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.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

import java.util.Properties;

import com.quadcap.sql.file.Block;
import com.quadcap.sql.file.BlockFile;
import com.quadcap.sql.file.ByteUtil;
import com.quadcap.sql.file.SubPageManager;

import com.quadcap.sql.lock.PooledObject;
import com.quadcap.sql.lock.ObjectPool;

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

/**
 * A cursor for a Quadcap Btree.
 *
 * @author Stan Bailes
 */
public class BtreeCursor extends PooledObject implements BCursor {
    Object                      fileLock;
    
    Btree                       tree;
    Bnode                       root            = null;
    Comparator                  compare         = null;

    Block[]                     blocks          = new Block[16];
    int[]                       pointers        = new int[16];

    byte[]                      curKey          = new byte[4096];
    byte[]                      curVal          = new byte[4096];
    int[]                       lengths         = new int[2];

    int                         depth           = -1;
    long                        size            = -1;

    /** 
     * <pre>
     * For the position variable:
     *  -2         unknown
     *  -1         after last
     *   0         before first
     *   >0        on key
     * </pre>
     */
    static final long           posUNKNOWN      = -2;
    static final long           posAFTER_LAST   = -1;
    static final long           posBEFORE_FIRST = 0;

    long                        position        = posUNKNOWN;

    /**
     * Constructor for cursor on a given Btree.
     */
    private BtreeCursor() {}

    static final boolean noPool = false;
    static ObjectPool pool = new ObjectPool(new BtreeCursor());

    static BtreeCursor get(Btree tree, boolean skipSetup) throws IOException {
        BtreeCursor c = null;
        if (noPool) {
            c = new BtreeCursor();
        } else {
            synchronized (tree.lock) {
                c = (BtreeCursor)pool.get();
            }
        }
        if (c != null) {
            c.init(tree, skipSetup);
        }
        return c;
    }

    public void release() {
        unsetup();
        synchronized (fileLock) {
            Btree theTree = tree;
            tree = null;
            fileLock = null;
            theTree.releaseCursor(this);
            if (!noPool) {
                pool.release(this);
            }
        }
    }
    
    /**
     * PooledObject factory
     */
    public PooledObject create() {
        return new BtreeCursor();
    }

    /**
     * Init for use/reuse
     */
    public void init(Btree tree, boolean skipSetup) throws IOException {
        this.tree = tree;
        this.fileLock = tree.lock;
        if (!skipSetup) {
            beforeFirst();
        }
    }

    /**
     * Called to re-establish the synchronization of this cursor in
     * the case where the underlying index has been modified.
     */
    protected void setup(boolean restoreKey) throws IOException {
        if (depth < 0) {
            synchronized (fileLock) {
                this.root = tree.getRoot();
                this.compare = tree.compare;
                if (restoreKey) {
                    if (lengths[0] > 0) {
                        seek(curKey, lengths[0]);
                    } else {
                        beforeFirst();
                    }
                }
            }
        }
    }

    /**
     * Called (in theory) by the owning Btree when the index is modified.
     */
    public void unsetup() {
        for (int i = 0; i < blocks.length; i++) {
            setBlock(i, null);
        }
        this.root = null;
        this.depth = -1;
        this.size = -1;
        if (position > 0) position = posUNKNOWN;
    }

    /**
     * Seek: Position the cursor on or before the specified key value.
     * Return true if the key matches exactly.
     */
    public final boolean seek(byte[] key) throws IOException {
        return seek(key, key.length);
    }

    /**
     * Seek, but the key can be a subsequence of the given byte array.
     */
    public boolean seek(byte[] key, int len) throws IOException {
        synchronized (fileLock) {
            position = posUNKNOWN;
            setup(false);
            setBlock(0, root.getBlock());
            boolean ret = seek1(0, key, len);
            if (ret) {
                holdKey(0);
            }
            //#ifdef DEBUG
            if (Trace.bit(6)) {
                Debug.println(toString() + ".seek(" +
                              Util.hexBytes(key, 0, len) + ") = " + ret);
            }
            //#endif
            return ret;
        }
    }

    //#ifdef DEBUG
    final String id() {
        return tree.getFile().getName().substring(0, 1) +
            " " + SubPageManager.toString(tree.getRootBlock());
    }
    final String dr() {
        return !Trace.bit(12) ? 
            ", val = " + (lengths[1] > 0 ? Util.hexBytes(getVal()) : "null") :
            "";
    }
    //#endif
        
    /**
     * (Private) seek recursion kernel
     */
    boolean seek1(int level, byte[] key, int len) throws IOException {
        Block b = blocks[level];
        int bs;
        bs = Bnode.bsearch(b, compare, key, len, 0, Bnode.getCount(b)-1);
        int index = bs < 0 ? (-1-bs) : bs;
        if (!Bnode.isLeaf(b)) {
            if (bs < 0) {
                index = index - 1;
                if (index < 0) index = 0;
            }
            pointers[level] = index;
            Block c = root.getBlock(Bnode.blockRef(b, index));
            setBlock(++level, c);
            return seek1(level, key, len);
        } else {
            pointers[level] = index;
            depth = level+1;
            return bs >= 0;
        }
    }

    /**
     * Manage updates to the 'blocks' array through this function to
     * assuage refcount madness.
     */
    final void setBlock(int i, Block b) {
        if (blocks[i] != null) blocks[i].decrRefCount();
        blocks[i] = b;
    }

    /**
     * Move the cursor before the first key.
     */
    public void beforeFirst() throws IOException {
        synchronized (fileLock) {
            this.root = tree.getRoot();
            this.compare = tree.compare;
            lengths[0] = lengths[1] = 0;
            Block b = root.getBlock();
            for (int level = 0; b != null; level++) {
                setBlock(level, b);
                pointers[level] = 0;
                if (!Bnode.isLeaf(b)) {
                    b = root.getBlock(Bnode.blockRef(b, 0));
                } else {
                    depth = level + 1;
                    b = null;
                }
            }
            position = posBEFORE_FIRST;

            //#ifdef DEBUG
            if (Trace.bit(1)) {
                Debug.println(toString() + ".beforeFirst()");
            }
            //#endif
        }
    }
    
    
    /**
     * Move the cursor after the last key.
     */
    public void afterLast() throws IOException {
        synchronized (fileLock) {
            setup(false);
            Block b = root.getBlock();
            for (int level = 0; b != null; level++) {
                setBlock(level, b);
                int count = Bnode.getCount(b);
                pointers[level] = count;
                if (!Bnode.isLeaf(b)) {
                    b = root.getBlock(Bnode.blockRef(b, pointers[level]-1));
                } else {
                    b = null;
                }
            }
            position = posAFTER_LAST;
            //#ifdef DEBUG
            if (Trace.bit(1)) {
                Debug.println(toString() + ".afterLast()");
            }
            //#endif
        }
    }

    /**
     * Move the cursor to the specified absolute position
     */
    public boolean absolute(int x) throws IOException {
        synchronized (fileLock) {
            if (x > 0) {
                // from first
                beforeFirst();
                int cur = 1;
                int cnt = Bnode.getCount(blocks[depth-1]);
                while (cur + cnt < x) {
                    cur += cnt;
                    if (!getNextBlock()) return false;
                    cnt = Bnode.getCount(blocks[depth-1]);
                }
                int p = x - cur;
                if (p < 0 || p >= cnt) return false;
                pointers[depth-1] = p;
                holdKey(0);
                pointers[depth-1]++;
                position = x;
                //#ifdef DEBUG
                if (Trace.bit(1)) {
                    Debug.println(toString() + ".absolute(" + x + ") = true");
                }
                //#endif
                return true;
            } else if (x < 0) {
                int absx = 0 - x;
                // from last
                afterLast();
                int cnt = Bnode.getCount(blocks[depth-1]);
                while (cnt < absx) {
                    absx -= cnt;
                    if (!getPrevBlock()) return false;
                    cnt = Bnode.getCount(blocks[depth-1]);
                }
                pointers[depth-1] -= absx;
                holdKey(0);
                //#ifdef DEBUG
                if (Trace.bit(1)) {
                    Debug.println(toString() + ".absolute(" + x + ") = true");
                }
                //#endif
                if (size > 0) position = size + x;
                return true;
            } else {
                throw new IOException("absolute 0");
            }
        }
    }

    /**
     * Move the cursor to the next row and return <b>true</b> if the
     * cursor is positioned on a valid row.
     */
    public boolean next() throws IOException {
        synchronized (fileLock) {
            setup(true);
            if (depth <= 0) return false;
            int p = pointers[depth-1];
            int cnt = Bnode.getCount(blocks[depth-1]);
            if (p >= cnt) {
                if (cnt == 0 || !getNextBlock()) {
                    //#ifdef DEBUG
                    if (Trace.bit(1)) {
                        Debug.println(toString() + ".next() false");
                    }
                    //#endif
                    return false;
                }
                p = pointers[depth-1];
                cnt = Bnode.getCount(blocks[depth-1]);
                if (p >= cnt) {
                    //#ifdef DEBUG
                    if (Trace.bit(1)) {
                        Debug.println(toString() + ".next() false");
                    }
                    //#endif
                    return false;
                }
            }
            holdKey(0);
            pointers[depth-1]++;
            if (position >= 0) position++;
            //#ifdef DEBUG
            if (Trace.bit(1)) {
                Debug.println(toString() + ".next(): " +
                              Util.hexBytes(getKeyBuf(), 0, getKeyLen()) +
                              " = " + dr());
            }
            //#endif
            return true;            
        }
    }

    /**
     * Move the cursor to the next row and return <b>true</b> if the
     * cursor is positioned on a valid row.
     */
    public boolean prev() throws IOException {
        synchronized (fileLock) {
            setup(true);
            if (depth < 0) return false;
            int p = pointers[depth-1] - 1;
            int cnt = Bnode.getCount(blocks[depth-1]);
            if (p < 0 || cnt <= 0) {
                if (cnt <= 0 || !getPrevBlock()) return false;
                p = pointers[depth-1];
                if (p < 0 || cnt <= 0) return false;
            }
            pointers[depth-1] = p;
            holdKey(0);
            if (position > 0) {
                position--;
            } else if (position == posAFTER_LAST) {
                if (size < 0) {
                    position = posUNKNOWN;
                } else {
                    position = size;
                }
            }
            //#ifdef DEBUG
            if (Trace.bit(1)) {
                Debug.println(toString() + ".prev() true");
            }
            //#endif
            return true;            
        }
    }

    /**
     * Delete the current row (if the cursor is positioned on a valid
     * row, that is ;-)
     */
    public boolean delete() throws IOException {
        synchronized (fileLock) {
            boolean ret = false;
            setup(true);
            if (depth >= 0) {
                int p = pointers[depth-1];
                int cnt = Bnode.getCount(blocks[depth-1]);
                if (p >= 0 && p < cnt) {
                    root.deleteKeyAtPos(blocks[depth-1], p, false);
                    tree.notifyUpdate(this);
                    ret = true;
                }
            }
            //#ifdef DEBUG
            if (Trace.bit(9)) {
                Debug.println(toString() + ".delete() = " + ret);
            }
            //#endif
            return ret;
        }
    }


    /**
     * Insert a new key/data pair.  We are presumably positioned just before
     * the spot where the new record should go, but we should check, anyway.
     * This will return false if the key already exists in the index.
     */
    public boolean insert(byte[] key, int klen,
                          byte[] data, int doff, int dlen) throws IOException {
        synchronized (fileLock) {
            setup(true);

            int p = pointers[depth-1];
            final Block b = blocks[depth-1];
            final int cnt = Bnode.getCount(b);
        
            if (p < 0 || p > cnt) throw new IOException("bad tree");

            boolean ret = true;
            if (p >= 0 && p < cnt) {
                int r = Bnode.keyCompareAtPos(compare, key, klen, b, p);
                if (r != -1) ret = false;
            } else if (p > 0 && cnt > 0) {
                int r = Bnode.keyCompareAtPos(compare, key, klen, b, p-1);
                if (r != 1) ret = false;
            }
            if (ret) {
                root.setKey(b, p, key, klen, data, doff, dlen, false);
                tree.notifyUpdate(this);
            }
            //#ifdef DEBUG
            if (Trace.bit(7)) {
                Debug.println(toString() + ".insert(" + k(key, 0, klen) +
                              (!Trace.bit(12) ? (", " + k(data, doff, dlen)) : "") +
                              ") = " + ret);
            }
            //#endif
            return ret;
        }
    }
    
    public boolean insert(byte[] key, byte[] data) throws IOException {
        return insert(key, key.length, data, 0, data.length);
    }

    /**
     * Replace the data portion of the current item with the specified data
     */
    public boolean replace(byte[] data, int doff, int dlen)
        throws IOException
    {
        synchronized (fileLock) {
            setup(true);

            int p = pointers[depth-1]; 
            final Block b = blocks[depth-1];
            final int cnt = Bnode.getCount(b);
        
            if (p < 0 || p > cnt) {
                throw new IOException("bad tree");
            }

            root.setKey(b, p, curKey, lengths[0], data, doff, dlen, true);
            tree.notifyUpdate(this);
            //#ifdef DEBUG
            if (Trace.bit(8)) {
                Debug.println(toString() + ".replace(" + k(curKey, 0, lengths[0]) + ") = true");
            }
            //#endif
            return true;
        }
    }

    public boolean replace(byte[] data) throws IOException {
        return replace(data, 0, data.length);
    }
    
    /**
     * Return the total number of entries in this index
     */
    public long size() throws IOException {
        synchronized (fileLock) {
            setup(true);
            if (size < 0) {
                size = subtreeSize(root, root.getBlock());
            }
            return size;
        }
    }

    /**
     * Return the current position in the index
     */
    public long position() throws IOException {
        synchronized (fileLock) {
            setup(true);
            if (position < 0) {
                long total = 0;
                boolean r = false;
                for (int d = 0; d < depth-1; d++) {
                    Block b = blocks[d];
                    int p = pointers[d];
                    int c = Bnode.getCount(b);
                    if (d == 0) r = (c / 2) <= p;
                    if (r) p++;
                    else { c = p; p = 0; }
                    if (Bnode.isLeaf(b)) {
                        total += (c - p);
                    } else {
                        for (int i = p; i < c; i++) {
                            Block s = root.getBlock(Bnode.blockRef(b, i));
                            try {
                                total += subtreeSize(root, s);
                            } finally {
                                s.decrRefCount();
                            }
                        }
                    }
                }
                position = r ? size() - total : total + 1;
            }
            return position;
        }
    }

    /**
     * Close the index
     */
    public void close() {
        unsetup();
    }

    public int getKey(byte[] buf) {
        System.arraycopy(curKey, 0, buf, 0, lengths[0]);
        return lengths[0];
    }

    public byte[] getKeyBuf() { return curKey; }

    public void setKeyBuf(byte[] buf) { curKey = buf; }

    public int getKeyLen() { return lengths[0]; }

    public byte[] getKey() {
        byte[] ret = new byte[lengths[0]];
        System.arraycopy(curKey, 0, ret, 0, ret.length);
        return ret;
    }

    public int getVal(byte[] buf) {
        System.arraycopy(curVal, 0, buf, 0, lengths[1]);
        return lengths[1];
    }

    public byte[] getValBuf() { return curVal; }

    public void setValBuf(byte[] buf) { curVal = buf; }

    public int getValLen() { return lengths[1]; }

    public byte[] getVal() {
        byte[] ret = new byte[lengths[1]];
        System.arraycopy(curVal, 0, ret, 0, ret.length);
        return ret;
    }

    public long getValAsLong() {
        return ByteUtil.getLong(curVal, 0);
    }

    //--------------------------------- private stuff

    final boolean getNextBlock() throws IOException {
        int d = depth - 2;
        while (d >= 0 && pointers[d]+1 >= Bnode.getCount(blocks[d])) {
            d--;
        }

        if (d < 0) return false;
        Block b = root.getBlock(Bnode.blockRef(blocks[d],
                                               ++pointers[d]));
        
        setBlock(d+1, b);
        pointers[d+1] = 0;

        for (int i = d+2; i < depth; i++) {
            pointers[i] = 0;
            Block c = root.getBlock(Bnode.blockRef(blocks[i-1],
                                                   pointers[i-1]));
            setBlock(i, c);
        }
        return true;
    }
    
    final boolean getPrevBlock() throws IOException {
        int d = depth - 2;
        while (d >= 0 && pointers[d] <= 0) {
            d--;
        }

        if (d < depth-1) {
            if (d < 0) {
                return false;
            }
            Block b = root.getBlock(Bnode.blockRef(blocks[d],
                                                   --pointers[d]));
            setBlock(d+1, b);
            pointers[d+1] = 0;

            for (int i = d+2; i < depth; i++) {
                Block c = root.getBlock(Bnode.blockRef(blocks[i-1],
                                                       pointers[i-1]));
                setBlock(i, c);
                pointers[i] = Bnode.getCount(c)-1;
            }
        }
        return true;
    }

    final void holdKey(int off) {
        int p = pointers[depth-1] - off;
        Block b = blocks[depth-1];
        if (p >= 0 && p < Bnode.getCount(b)) {
            if (!Bnode.getKeyAndData(b, p, curKey, curVal, lengths)) {
                throw new RuntimeException("holdKey: getKeyAndData failed");
            }
        } else {
            //msg("holdKey: p = " + p + ", pointers[depth(" + depth + ")-1]=" +
            //    pointers[depth-1] + ", off = " + off + ", count = " +
            //    Bnode.getCount(b));
            throw new RuntimeException("Hold what, mate?");
        }
        //Debug.println("holdKey: [" + k(curKey, 0, lengths[0]) +
        //" / " + k(curVal, 0, lengths[1]) + "]");
    }
        
    static long subtreeSize(Bnode root, Block b) throws IOException {
        int count = Bnode.getCount(b);
        if (Bnode.isLeaf(b)) return count;
        else {
            long total = 0;
            for (int i = 0; i < count; i++) {
                Block c = root.getBlock(Bnode.blockRef(b, i));
                try {
                    total += subtreeSize(root, c);
                } finally {
                    c.decrRefCount();
                }
            }
            return total;
        }
    }

    //#ifdef DEBUG

    public String toString() {
        return "BtreeCursor[" + tree + "]";
    }
    
    String k(byte[] b, int off, int len) {
        return tree.compare.toString(b, off, len);
    }
    
    String t() {
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < depth; i++) {
            if (i > 0) sb.append(' ');
            sb.append(String.valueOf(pointers[i]));
            sb.append('/');
            sb.append(String.valueOf(Bnode.getCount(blocks[i])));
        }
        return sb.toString();
    }
        
    static int lastCount = -1;
    static StringBuffer lastBuf = new StringBuffer();
    
    private static final int countNext(BCursor c) throws IOException {
        int cnt = 0;
        while (c.next()) cnt++;
        lastCount = cnt;
        return cnt;
    }
    
    private static final int countPrev(BCursor c) throws IOException {
        int cnt = 0;
        StringBuffer sb = lastBuf;
        sb.setLength(0);
        sb.append("{");
        byte[] buf = new byte[111];
        while (c.prev()) {
            cnt++;
            int len = c.getKey(buf);
            if (cnt > 0) sb.append(',');
            sb.append(new String(buf, 0, len));
        }
        sb.append("}");
        lastCount = cnt;
        return cnt;
    }

    final static String r(boolean b) {
        return b ? "{true}" : "{false}";
    }
    static void itest(BCursor bc) throws IOException {
        InputStreamReader ir = new InputStreamReader(System.in);
        BufferedReader r = new BufferedReader(ir);
        String ret = "";
        while (true) {
            System.out.print("BC" + ret + " (" + ((BtreeCursor)bc).t() + "): ");
            System.out.flush();
            String line = r.readLine();
            if (line == null) break;
            try {
                ret = doLine(bc, line);
                if (ret == null) break;
            } catch (Throwable t) {
                t.printStackTrace(System.out);
                System.out.println("-------------------------");
            }
        }
    }

    static String doLine(BCursor bc, String line) throws Exception {
        String ks = line.toLowerCase().substring(1).trim();
        byte[] k = ks.getBytes();
        byte[] d = ks.toUpperCase().getBytes();
        String ret = "";
        if (line.startsWith("g")) {
            ret = r(bc.seek(k));
        } else if (line.equals("<")) {
            bc.beforeFirst();
        } else if (line.equals(">")) {
            bc.afterLast();
        } else if (line.equals("n")) {
            ret = r(bc.next());
        } else if (line.equals("p")) {
            ret = r(bc.prev());
        } else if (line.equals("d")) {
            ret = r(bc.delete());
        } else if (line.startsWith("i")) {
            ret = r(bc.insert(k, k.length, d, 0, d.length));
        } else if (line.startsWith("r")) {
            ret = r(bc.replace(d, 0, d.length));
        } else if (line.equals("c")) {
            bc.close();
        } else if (line.equals("s")) {
            show("position = " + bc.position() + " of " +
                 bc.size() + " records");
        } else if (line.equals("k")) {
            show("current key = " + new String(bc.getKeyBuf(), 0,
                                               bc.getKeyLen()));
            show("current val = " + new String(bc.getValBuf(), 0,
                                               bc.getValLen()));
            show("current val as long: " + bc.getValAsLong());
                    
        } else if (line.equals("p")) {
            show("position = " + bc.position() + " of " +
                 bc.size() + " records");
        } else if (line.equals("q")) {
            return null;
        } else {
            int row = 0;
            boolean bad = true;
            try {
                row = Integer.parseInt(line);
                bad = false;
            } catch (Throwable t) {}
            if (!bad) {
                ret = r(bc.absolute(row));
            } else {
                show("g <key>                 seek(key)");
                show("i <key>                 insert(key,KEY)");
                show("r <key>                 replace(KEY)");
                show("<                       beforeFirst()");
                show(">                       afterLast()");
                show("n                       next()");
                show("p                       prev()");
                show("c                       close()");
                show("d                       delete()");
                show("s                       position / size");
            }
        }
        return ret;
    }

    static void show(String s) {
        System.out.println(s);
    }

    static final long tick() { return System.currentTimeMillis(); }

    static final void mkey(int i, byte[] b) {
        int x = b.length;
        while (x > 0 && i > 0) {
            b[--x] = (byte)('0' + (i % 10));
            i /= 10;
        }
        while (x > 0) b[--x] = '0';
    }
    
    static void ktest(BCursor c) throws IOException {
        long s = tick();
        byte[] k = new byte[8];
        for (int i = 0; i < k.length; i++) k[i] = '0';
        for (int ki = 0; ki < 100000; ki++) {
            int i = (ki * 2003) % 100000;
            mkey(i, k);
            if (c.seek(k)) throw new IOException("*** Error, found " + i);
            if (!c.insert(k, k.length, k, 0, k.length)) {
                throw new IOException("*** Error insert: " + i);
            }
        }
        long elap = tick() - s;
        System.out.println("insert: " + elap + " ms");
        kshow(c);
    }
    
    static void kshow(BCursor c) throws IOException {
        long s = tick();
        int count = 0;
        int total = 0;
        int etotal = 0;
        c.beforeFirst();
        while (c.next()) {
            etotal += count;
            count++;
            total += Integer.parseInt(new String(c.getValBuf(), 0,
                                                 c.getValLen()));
        }
        long elap = tick() - s;
        show("seek: " + elap + " ms");
        show("Count: " + count + ", total/etotal = " + total + "/" + etotal);
    }
    
    static void ktest(Btree t) throws IOException {
        long s = tick();
        byte[] k = new byte[8];
        for (int i = 0; i < k.length; i++) k[i] = '0';
        for (int ki = 0; ki < 100000; ki++) {
            int i = (ki * 2003) % 100000;
            mkey(i, k);
            t.set(k, k);
        }
        long elap = tick() - s;
        System.out.println("insert: " + elap + " ms");
        kshow(t.getCursor());
    }
    
    /**
     * Main for testing
     */
    public static void main(String[] args) {
        try {
            String name = "test.db";
            int blocksize = 4096;
            int cachesize = 256;
            BlockFile f = new BlockFile(name, "rw",
                                        new Properties(),
                                        blocksize, cachesize);
            long rootBlock = f.newPage();
            Btree t = new Btree(f, rootBlock, true);
//              tree.set("abc".getBytes(), "def".getBytes());
//              tree.set("aabc".getBytes(), "def".getBytes());
//              tree.set("fabc".getBytes(), "def".getBytes());
            
            BCursor c = t.getCursor();
            //itest(c);
            //jtest(c);
            //ktest(t);
            ktest(c);
        } catch (Throwable t) {
            t.printStackTrace(System.out);
        }
    }

    static void jtest(BCursor c) throws Exception {
        c.seek("abc".getBytes());
        c.insert("abc".getBytes(), 3, "def".getBytes(), 0, 3);
        c.seek("ahc".getBytes());
        c.insert("ahc".getBytes(), 3, "deh".getBytes(), 0, 3);
        c.seek("bbc".getBytes());
        c.insert("bbc".getBytes(), 3, "jej".getBytes(), 0, 3);

        int cSize = countNext(c);
        if (c.size() != cSize) {
            System.out.println("Bad size: " + cSize + " vs " + c.size());
        }
        for (int i = 1; i <= cSize; i++) {
            if (i == 0) c.beforeFirst(); else c.absolute(i);
            if (c.position() != i) {
                System.out.println("Bad position " + i + " vs " +
                                   c.position());
            }
            if (countNext(c) != cSize - i) {
                System.out.println("Bad count next: " + lastCount +
                                   " vs " + (cSize - i));
            }
            if (i == 0) c.beforeFirst(); else c.absolute(i);
            if (c.position() != i) {
                System.out.println("Bad position " + i + " vs " +
                                   c.position());
            }
            if (countPrev(c) != i) {
                System.out.println("Bad count prev: " + i + " vs " +
                                   lastCount + " " + lastBuf);
            }
            if (i == 0) c.afterLast(); else c.absolute(0 - i);
            if (c.position() != cSize - i) {
                System.out.println("Bad position " + (cSize-i) + " vs " +
                                   c.position());
            }
            if (countNext(c) != i-1) {
                System.out.println("Bad count next: " + lastCount +
                                   " vs " + (i-1));
            }
            if (i == 0) c.afterLast(); else c.absolute(0 - i);
            if (c.position() != (cSize-i)) {
                System.out.println("Bad position " + (cSize-i) + " vs " +
                                   c.position());
            }
            if (countPrev(c) != cSize - i + 1) {
                System.out.println("Bad count prev: " + (cSize-i+1) +
                                   " vs " +
                                   lastCount + " " + lastBuf);
            }
        }
                
        System.out.println("seek(abc) = " + c.seek("abc".getBytes()) +
                           ": " + c.position() + "/" + c.size());
        System.out.println("c.next() = " + c.next());
        System.out.println("c.next() = " + c.next());

        System.out.println("seek(abb) = " + c.seek("abb".getBytes()));
        System.out.println("c.next() = " + c.next());
        System.out.println("c.next() = " + c.next());

        System.out.println("seek(abd) = " + c.seek("abd".getBytes()));
        System.out.println("c.next() = " + c.next());
        System.out.println("c.next() = " + c.next());

        System.out.println("seek(zzz) = " + c.seek("zzz".getBytes()));
        System.out.println("c.next() = " + c.next());
        System.out.println("c.next() = " + c.next());
    }
    //#endif
}