[cweb-CVS] bigdata/src/java/com/bigdata/btree BytesUtil$UnsignedByteArrayComparator.class, NONE, 1

SourceForge Headquarters 1320 Columbia Street Suite 310 San Diego, CA 92101 +1 (858) 422-6466

Update of /cvsroot/cweb/bigdata/src/java/com/bigdata/btree
In directory sc8-pr-cvs4.sourceforge.net:/tmp/cvs-serv9284/src/java/com/bigdata/btree

Added Files:
	BytesUtil$UnsignedByteArrayComparator.class ILinearList.java 
	PO.java DataOutputBuffer.java BatchInsert.java 
	IndexSegmentExtensionMetadata.java Tuple.java IBatchOp.java 
	SuccessorUtil.java NoSuccessorException.java BytesUtil.c 
	BTreeMetadata.java AbstractBTree.java 
	ByteArrayValueSerializer.java Counters.java IndexSegment.java 
	ReadOnlyIndex.java BTree.java IKeySerializer.java 
	IEntryIterator.java BatchRemove.java IEvictionListener.java 
	AbstractKeyBuffer.java ConditionalInsert.java Leaf.java 
	compile.sh Node.java BatchContains.java 
	IndexSegmentMetadata.java MutableKeyBuffer.java 
	DirtyChildIterator.java BytesUtil.java IValueSerializer.java 
	IKeyBuffer.java Errors.java ImmutableKeyBuffer.java 
	IndexSegmentMerger.java IndexSegmentPlan.java 
	DataInputBuffer.java IAbstractNode.java ReadOnlyFusedView.java 
	IBatchBTree.java PackedAddressSerializer.java 
	ConditionalInsertNoValue.java IDirty.java IRangeQuery.java 
	IAddressSerializer.java IndexSegmentBuilder.java 
	INodeFactory.java INodeIterator.java AddressSerializer.java 
	INodeData.java UserDefinedFunction.java IAbstractNodeData.java 
	KeyBufferSerializer.java AbstractNode.java package.html 
	EntryIterator.java IFusedView.java BytesUtil.class 
	IndexSegmentFileStore.java BatchLookup.java 
	IIdentityAccess.java IIndex.java ISimpleBTree.java 
	KeyBuilder.java IReadOnlyBatchOp.java NodeSerializer.java 
	ILeafData.java EmptyEntryIterator.java RecordCompressor.java 
	ChildIterator.java DefaultEvictionListener.java 
Log Message:
Package rename from com.bigdata.objndx to com.bigdata.btree.  Since we are using CVS, this is going to break the access to prior versions in the source file history.

--- NEW FILE: IndexSegmentFileStore.java ---
package com.bigdata.btree;

import it.unimi.dsi.mg4j.util.BloomFilter;

import java.io.File;
import java.io.IOException;
import java.io.RandomAccessFile;
import java.lang.reflect.Constructor;
import java.nio.ByteBuffer;

import org.apache.log4j.Logger;

import com.bigdata.io.SerializerUtil;
import com.bigdata.rawstore.Addr;
import com.bigdata.rawstore.IRawStore;

/**
 * A read-only store backed by a file. The section of the file containing the
 * index nodes may be fully buffered.
 * 
 * Note: An LRU disk cache is a poor choice for the leaves. Since the btree
 * already maintains a cache of the recently touched leaf objects, a recent read
 * against the disk is the best indication that we have that we will not want to
 * read that region again soon.
 * 
 * @author <a href="mailto:tho...@us...">Bryan Thompson</a>
 * @version $Id$
 */
public class IndexSegmentFileStore implements IRawStore {

    /**
     * Logger.
     */
    protected static final Logger log = Logger
            .getLogger(IndexSegmentFileStore.class);

    /**
     * A buffer containing the disk image of the nodes in the index segment.
     * While some nodes will be held in memory by the hard reference queue
     * the use of this buffer means that reading a node that has fallen off
     * of the queue does not require any IOs.
     */
    private ByteBuffer buf_nodes;

    /**
     * The file containing the index segment.
     */
    protected final File file;

    /**
     * The random access file used to read the index segment.
     */
    private RandomAccessFile raf;

    /**
     * A read-only view of the metadata record for the index segment.
     */
    protected IndexSegmentMetadata metadata;

    /**
     * A read-only view of the extension metadata record for the index segment.
     */
    protected IndexSegmentExtensionMetadata extensionMetadata;

    /**
     * True iff the store is open.
     */
    private boolean open = false;

    /**
     * Open the read-only store.
     * 
     * @param file
     * 
     * @throws IOException
     * 
     * @todo make it optional to fully buffer the index nodes?
     * @todo make it optional to fully buffer the leaves as well as the nodes?
     * 
     * @see #load()
     */
    public IndexSegmentFileStore(File file) {

        if (file == null)
            throw new IllegalArgumentException();

        this.file = file;

        reopen();

    }

    /**
     * Re-open a closed store. This operation should succeed if the backing file
     * is still accessible.
     * 
     * @exception IllegalStateException
     *                if the store is not closed.
     * 
     * @see #close()
     */
    public void reopen() {

        if (open)
            throw new IllegalStateException("Already open.");

        if (!file.exists()) {

            throw new RuntimeException("File does not exist: "
                    + file.getAbsoluteFile());

        }

        try {

            // open the file.
            this.raf = new RandomAccessFile(file, "r");

            // read the metadata record from the file.
            this.metadata = new IndexSegmentMetadata(raf);

            IndexSegment.log.info(metadata.toString());

            /*
             * Read in the extension metadata record.
             */
            this.extensionMetadata = readExtensionMetadata();

            /*
             * Read the index nodes from the file into a buffer. If there are no
             * index nodes then we skip this step. Note that we always read in
             * the root, so if the index is just a root leaf then the root will
             * be a deserialized object and the file will not be buffered in
             * memory.
             */
            this.buf_nodes = (metadata.nnodes > 0 ? bufferIndexNodes(raf)
                    : null);

            /*
             * Mark as open so that we can use read(long addr) to read other
             * data (the root node/leaf).
             */
            this.open = true;

        } catch (IOException ex) {

            throw new RuntimeException(ex);

        }

    }

    /**
     * Load the {@link IndexSegment} or derived class from the store. The
     * {@link IndexSegment} or derived class MUST provide a public constructor
     * with the following signature: <code>
     * 
     * <i>className</i>(IndexSegmentFileStore store)
     * 
     * </code>
     * 
     * @param store
     *            The store.
     * 
     * @return The {@link IndexSegment} or derived class loaded from that store.
     * 
     * @see IndexSegmentExtensionMetadata, which provides a metadata extension
     *      protocol for the {@link IndexSegment}.
     */
    public IndexSegment load() {

        try {

            Class cl = Class.forName(extensionMetadata.getClassName());

            Constructor ctor = cl
                    .getConstructor(new Class[] { IndexSegmentFileStore.class });

            IndexSegment seg = (IndexSegment) ctor
                    .newInstance(new Object[] { this });

            return seg;

        } catch(Exception ex) {

            throw new RuntimeException(ex);

        }

    }

    public boolean isOpen() {

        return open;

    }

    public boolean isStable() {

        return true;

    }

    public boolean isFullyBuffered() {

        return false;

    }

    public File getFile() {

        return file;

    }

    /**
     * Closes the file and releases the internal buffers and metadata records.
     * This operation may be reversed by {@link #reopen()} as long as the
     * backing file remains available.
     */
    public void close() {

        if (!open)
            throw new IllegalStateException();

        try {

            raf.close();

            raf = null;

            buf_nodes = null;

            metadata = null;

            extensionMetadata = null;

            open = false;

        } catch (IOException ex) {

            throw new RuntimeException(ex);

        }

    }

    public void closeAndDelete() {

        close();

        if(!file.delete()) {

            System.err.println("WARN: Could not delete: "+file.getAbsolutePath());

        }

    }

    public long write(ByteBuffer data) {

        throw new UnsupportedOperationException();

    }

    public void force(boolean metadata) {

        throw new UnsupportedOperationException();

    }

    public long size() {

        return metadata.length;

    }

    /**
     * Read from the index segment. If the request is in the node region and
     * the nodes have been buffered then this uses a slice on the node
     * buffer. Otherwise this reads through to the backing file.
     */
    public ByteBuffer read(long addr) {

        if (!open)
            throw new IllegalStateException();

        final int offset = Addr.getOffset(addr);

        final int length = Addr.getByteCount(addr);

        final int offsetNodes = Addr.getOffset(metadata.addrNodes);

        ByteBuffer dst;

        if (offset >= offsetNodes && buf_nodes != null) {

            /*
             * the data are buffered. create a slice onto the read-only
             * buffer that reveals only those bytes that contain the desired
             * node. the position() of the slice will be zero(0) and the
             * limit() will be the #of bytes in the compressed record.
             */

            // correct the offset so that it is relative to the buffer.
            int off = offset - offsetNodes;

            // System.err.println("offset="+offset+", length="+length);

            // set the limit on the buffer to the end of the record.
            buf_nodes.limit(off + length);

            // set the position on the buffer to the start of the record.
            buf_nodes.position(off);

            // create a slice of that view.
            dst = buf_nodes.slice();

        } else {

            // Allocate buffer.
            dst = ByteBuffer.allocate(length);

            /*
             * the data need to be read from the file.
             */

            dst.limit(length);

            dst.position(0);

            try {

                // read into [dst] - does not modify the channel's position().
                raf.getChannel().read(dst, offset);

            } catch (IOException ex) {

                throw new RuntimeException(ex);

            }

            dst.flip(); // Flip buffer for reading.

        }

        return dst;

    }

    /**
     * Reads the index nodes into a buffer.
     * 
     * @return A read-only view of a buffer containing the index nodes.
     */
    protected ByteBuffer bufferIndexNodes(RandomAccessFile raf)
            throws IOException {

        if(metadata.addrNodes == 0L) {

            throw new IllegalStateException("No nodes.");

        }

        final int offset = Addr.getOffset(metadata.addrNodes);

        final int nbytes = Addr.getByteCount(metadata.addrLeaves);

        /*
         * Note: The direct buffer imposes a higher burden on the JVM and all
         * operations after we read the data from the disk should be faster with
         * a heap buffer, so my expectation is that a heap buffer is the correct
         * choice here.
         */
//        ByteBuffer buf = ByteBuffer.allocateDirect(nbytes);
        ByteBuffer buf = ByteBuffer.allocate(nbytes);

        raf.getChannel().read(buf, offset);

        return buf.asReadOnlyBuffer();

    }

    /**
     * Reads the bloom filter directly from the file.
     * 
     * @return The bloom filter -or- <code>null</code> if the bloom filter was
     *         not constructed when the {@link IndexSegment} was built.
     */
    protected BloomFilter readBloomFilter() throws IOException {

        final long addr = metadata.addrBloom;

        if(addr == 0L) {

            return null;

        }

        log.info("reading bloom filter: "+Addr.toString(addr));

        final int off = Addr.getOffset(addr);

        final int len = Addr.getByteCount(addr);

        ByteBuffer buf = ByteBuffer.allocate(len);

        buf.limit(len);

        buf.position(0);

        try {

            // read into [dst] - does not modify the channel's position().
            final int nread = raf.getChannel().read(buf, off);

            assert nread == len;

            buf.flip(); // Flip buffer for reading.

        } catch (IOException ex) {

            throw new RuntimeException(ex);

        }

        assert buf.position() == 0;
        assert buf.limit() == len;

//        ByteBufferInputStream bais = new ByteBufferInputStream(buf);
//        
////        ByteArrayInputStream bais = new ByteArrayInputStream(buf.array());
//        
//        ObjectInputStream ois = new ObjectInputStream(bais);
//        
//        try {
//
//            BloomFilter bloomFilter = (BloomFilter) ois.readObject();
//            
//            log.info("Read bloom filter: minKeys=" + bloomFilter.size()
//                    + ", entryCount=" + metadata.nentries + ", bytesOnDisk="
//                    + len + ", errorRate=" + metadata.errorRate);
//            
//            return bloomFilter;
//            
//        }
//        
//        catch(Exception ex) {
//            
//            IOException ex2 = new IOException("Could not read bloom filter: "+ex);
//            
//            ex2.initCause(ex);
//            
//            throw ex2;
//            
//        }

      BloomFilter bloomFilter = (BloomFilter) SerializerUtil.deserialize(buf);

      log.info("Read bloom filter: minKeys=" + bloomFilter.size()
              + ", entryCount=" + metadata.nentries + ", bytesOnDisk="
              + len + ", errorRate=" + metadata.errorRate);

      return bloomFilter;

    }

    /**
     * Reads the {@link IndexSegmentExtensionMetadata} record directly from the
     * file.
     */
    protected IndexSegmentExtensionMetadata readExtensionMetadata() throws IOException {

        final long addr = metadata.addrExtensionMetadata;

        assert addr != 0L;

        log.info("reading extension metadata record: "+Addr.toString(addr));

        final int off = Addr.getOffset(addr);

        final int len = Addr.getByteCount(addr);

        ByteBuffer buf = ByteBuffer.allocate(len);

        buf.limit(len);

        buf.position(0);

        try {

            // read into [dst] - does not modify the channel's position().
            final int nread = raf.getChannel().read(buf, off);

            assert nread == len;

            buf.flip(); // Flip buffer for reading.

        } catch (IOException ex) {

            throw new RuntimeException(ex);

        }

        assert buf.position() == 0;
        assert buf.limit() == len;

        IndexSegmentExtensionMetadata extensionMetadata = (IndexSegmentExtensionMetadata) SerializerUtil
                .deserialize(buf);

        log.info("Read extension metadata: " + extensionMetadata);

        return extensionMetadata;

    }

}

--- NEW FILE: ConditionalInsertNoValue.java ---
package com.bigdata.btree;

/**
 * User defined function supporting the conditional insert of a value iff no
 * entry is found under a search key.
 * 
 * @author <a href="mailto:tho...@us...">Bryan Thompson</a>
 * @version $Id$
 */
final public class ConditionalInsertNoValue implements UserDefinedFunction {

    private static final long serialVersionUID = 2942811843264522254L;

    public ConditionalInsertNoValue(Object value) {

    }

    /**
     * Do not insert if an entry is found.
     */
    public Object found(byte[] key, Object oldval) {

        return oldval;

    }

    /**
     * Insert if not found.
     */
    public Object notFound(byte[] key) {

        return INSERT_NULL;

    }

    public Object returnValue(byte[] key, Object oldval) {

        return oldval;

    }

}
--- NEW FILE: MutableKeyBuffer.java ---
package com.bigdata.btree;

/**
 * A mutable implementation of {@link IKeyBuffer}.
 * 
 * @todo 27% of the search cost is dealing with the prefix.
 * @todo track prefix length for mutable keys (update when first/last key are
 * updated). at present the node/leaf logic directly manipulates the
 * keys. that will have to be changed to track the prefix length.
 * 
 * @author <a href="mailto:tho...@us...">Bryan Thompson</a>
 * @version $Id$
 */
public class MutableKeyBuffer extends AbstractKeyBuffer {

    /**
     * The #of defined keys.
     */
    int nkeys;

    /**
     * An array containing the keys.  The size of the array is the maximum
     * capacity of the key buffer.
     */
    final byte[][] keys;

    /**
     * Allocate a mutable key buffer capable of storing <i>capacity</i> keys.
     * 
     * @param capacity
     *            The capacity of the key buffer.
     */
    public MutableKeyBuffer(int capacity) {

        nkeys = 0;

        keys = new byte[capacity][];

    }

    /**
     * Constructor wraps an existing byte[][].
     * 
     * @param nkeys
     *            The #of defined keys in the array.
     * @param keys
     *            The array of keys.
     */
    public MutableKeyBuffer(int nkeys, byte[][] keys ) {

        assert nkeys >= 0; // allow deficient root.

        assert keys != null;

        assert keys.length >= nkeys;

        this.nkeys = nkeys;

        this.keys = keys;

    }

    /**
     * Creates a new instance using a new array of keys but sharing the key
     * references with the provided {@link MutableKeyBuffer}.
     * 
     * @param src
     *            An existing instance.
     */
    public MutableKeyBuffer(MutableKeyBuffer src) {

        assert src != null;

//        assert capacity > src.nkeys;

        this.nkeys = src.nkeys;

        this.keys = new byte[src.keys.length][];

        for( int i=0; i<nkeys; i++ ) {

            // Note: copies the reference.
            this.keys[i] = src.keys[i];

        }

    }

    /**
     * Builds a mutable key buffer from an immutable key buffer.
     * 
     * @param src
     *            The immutable key buffer.
     */
    public MutableKeyBuffer(ImmutableKeyBuffer src) {

        assert nkeys >= 0; // allow deficient root.

        assert src != null;

        nkeys = src.nkeys;

        keys = src.toKeyArray();

    }

    /**
     * Returns a reference to the key at that index.
     */
    final public byte[] getKey(int index) {

//        assert index >= 0 && index < nkeys;

        return keys[index];

    }

    final public int getKeyCount() {

        return nkeys;

    }

    /**
     * The maximum #of keys that may be held in the buffer (its capacity).
     */
    final public int getMaxKeys() {

        return keys.length;

    }

    /**
     * True iff the key buffer can not contain another key.
     */
    final public boolean isFull() {

        return nkeys == keys.length;

    }

    /*
     * Mutation api. The contents of individual keys are never modified. Some of
     * the driver logic in Leaf and Node uses loops where nkeys is being
     * decremented while keys are being processed from, e.g., a split point to
     * the last key position. This has the effect that an assert such as
     * 
     * index < nkeys
     * 
     * will fail. Those looping constructs are not wrong as originally written
     * but a move to encapsulate the key buffer puts their treatment of nkeys at
     * odds with index testing since nkeys is temporarily inconsistent with the
     * keys[].
     * 
     * @todo maintain the prefix length. A trivial example of shortening the
     * shared prefix occurs when keys are inserted into the root leaf. Consider
     * that we first insert <code>4,5,6</code>. Since there is only one key
     * in the root leaf, the length of the prefix is the same as the length of
     * the key. If we then insert <code>4,5,6,1</code> the prefix does not
     * change. However, if we then insert <code>4,5,2</code> the prefix is now
     * shortened to <code>4,5</code>. If we insert <code>5</code>, then
     * the prefix is shortened to an empty byte[]. Prefix shortening can also
     * occur in trees with more than one level whenever a key is inserted into a
     * leaf and becomes either the first or last key in that leaf. Likewise, it
     * is possible for the prefix length to either grow when a leaf overflows
     * and keys are redistributed.
     */

    /**
     * Set the key at the specified index.
     * 
     * @param index
     *            The index in [0:nkeys-1].
     * @param key
     *            The key (non-null).
     * 
     * @todo Who uses this? Track prefixLength?
     */
    final public void setKey(int index, byte[] key) {

        assert index >= 0 && index < nkeys;

        keys[index] = key;

    }

    /**
     * Set the key at the specified index to <code>null</code>. This is used
     * to clear elements of {@link #keys} that are no longer defined. The caller
     * is responsible for updating {@link #nkeys} when using this method.
     * 
     * @param index
     *            The key index in [0:maxKeys-1];
     */
    final protected void zeroKey(int index) {

//        assert index >= 0 && index < nkeys;

        keys[index] = null;

    }

    /**
     * Append a key to the end of the buffer, incrementing the #of keys in the
     * buffer.
     * 
     * @param key
     *            A key.
     * 
     * @return The #of keys in the buffer.
     * 
     * @todo update prefixLength, lazily compute prefix.
     */
    final public int add(byte[] key) {

        assert nkeys < keys.length;

        assert key != null;

        keys[nkeys++] = key;

        return nkeys;

    }

    /**
     * Insert a key into the buffer at the specified index, incrementing the #of
     * keys in the buffer by one and moving down all keys from that index on
     * down by one (towards the end of the array).
     * 
     * @param index
     *            The index in [0:nkeys] (you are allowed to append using this
     *            method).
     * @param key
     *            The key.
     * 
     * @return The #of keys in the buffer.
     * 
     * @todo if index==0 || index==nkeys-1 then update prefixLength, lazily
     *       compute prefix.
     */
    final public int insert(int index, byte[] key) {

        assert index >= 0 && index <= nkeys;

        if( index == nkeys ) {

            // append

            return add(key);

        }

        /* index = 2;
         * nkeys = 6;
         * 
         * [ 0 1 2 3 4 5 ]
         *       ^ index
         * 
         * count = keys - index = 4;
         */
        final int count = nkeys - index;

        assert count >= 1;

        System.arraycopy(keys, index, keys, index+1, 1);

        keys[index] = key;

        return ++nkeys;

    }

    /**
     * Remove a key in the buffer at the specified index, decrementing the #of
     * keys in the buffer by one and moving up all keys from that index on down
     * by one (towards the start of the array).
     * 
     * @param index
     *            The index in [0:nkeys-1].
     * @param key
     *            The key.
     * 
     * @return The #of keys in the buffer.
     * 
     * @todo if index==0 || index==nkeys-1 then update prefixLength, lazily
     *       compute prefix (requires that the application never directly
     *       modifies keys).
     */
    final public int remove(int index) {

        assert index >= 0 && index < nkeys;

        /*
         * Copy down to cover up the hole.
         */
        final int length = nkeys - index - 1;

        if(length > 0) {

            System.arraycopy(keys, index + 1, keys, index, length);

        }

        keys[--nkeys] = null;

        return nkeys;

    }

    public String toString() {

        StringBuilder sb = new StringBuilder();

        sb.append("nkeys=" + nkeys);
        sb.append(", maxKeys=" + keys.length);
        sb.append(", prefix=" + BytesUtil.toString(getPrefix()));
        sb.append(", [");

        for (int i = 0; i < keys.length; i++) {

            if (i > 0)
                sb.append(", ");

            byte[] key = keys[i];

            if (key == null) {

                sb.append("null");

            } else {

                sb.append(BytesUtil.toString(key));

            }

        }

        sb.append("]");

        return sb.toString();

    }

    public MutableKeyBuffer toMutableKeyBuffer() {

//        if( capacity < nkeys + 1 ) throw new IllegalArgumentException();

//        return new MutableKeyBuffer(capacity,this);

        return new MutableKeyBuffer(this);

    }

    final public int search(final byte[] searchKey) {

        if (searchKey == null)
            throw new IllegalArgumentException("searchKey is null");

        if( nkeys == 0 ) {

            /*
             * If there are no keys in the buffer, then any key would be
             * inserted at the first buffer position.
             */

            return -1;

        }

        /*
         * The length of the prefix shared by all keys in the buffer.
         */

        final int prefixLength = getPrefixLength();

        /*
         * Attempt to match the shared prefix.  If we can not then return the
         * insert position, which is either before the first key or after the
         * last key in the buffer.
         */

        final int insertPosition = _prefixMatchLength(prefixLength, searchKey);

        if( insertPosition < 0 ) {

            return insertPosition;

        }

        /*
         * Search keys, but only bytes from prefixLength on in each key.
         */

        if (nkeys < 16) {

            return _linearSearch(prefixLength, searchKey);

        } else {

            return _binarySearch(prefixLength, searchKey);

        }

    }

    final protected int _prefixMatchLength(final int prefixLength,
            final byte[] searchKey) {

        final int searchKeyLen = searchKey.length;

        /*
         * Do not compare more bytes than remain in either the search key or the
         * prefix, e.g., compareLen := min(searchKeyLen, prefixLen).
         */
        final int compareLen = (searchKeyLen <= prefixLength) ? searchKeyLen
                : prefixLength;

        int ret = BytesUtil.compareBytesWithLenAndOffset(//
                0, compareLen, searchKey,//
                0, compareLen, keys[0]//
                );

        if (ret < 0) {

            /* insert before the first key. */

            return -1;

        } else  if (ret > 0) {

            /* insert after the last key. */

            return -(nkeys) - 1;

        } else {

            /*
             * For the case when the search key is _shorter_ than the prefix,
             * matching on all bytes of the search key means that the search key
             * will be ordered before all keys in the buffer.
             */
            if (searchKeyLen < prefixLength)
                return -1;

            /*
             * entire prefix matched, continue to search the remainder for each
             * key.
             */

            return 0;

        }

    }

    final protected int _linearSearch(final int searchKeyOffset,
            final byte[] searchKey) {

        // #of bytes to search in the search key after the prefix match.
        final int searchKeyLen = searchKey.length - searchKeyOffset;

        // searching zero or more bytes in the search key after the prefix match.
        assert searchKeyLen >= 0;

        for (int i = 0; i < nkeys; i++) {

            final byte[] key = keys[i];

            final int keyLen = key.length - searchKeyOffset;
            assert keyLen >= 0;

            // skip the first offset bytes, then compare no more bytes than
            // remain in the key.
            final int ret = BytesUtil.compareBytesWithLenAndOffset(//
                    searchKeyOffset, keyLen, key,//
                    searchKeyOffset, searchKeyLen, searchKey//
                    );

            if (ret == 0)
                return i;

            if (ret > 0)
                return -(i + 1);

        }

        return -(nkeys + 1);

    }

    final protected int _binarySearch(final int searchKeyOffset,
            final byte[] searchKey) {

        final int searchKeyLen = searchKey.length - searchKeyOffset;

        assert searchKeyLen >= 0;

        int low = 0;

        int high = nkeys - 1;

        while (low <= high) {

            final int mid = (low + high) >> 1;

            final byte[] key = keys[mid];

            final int keyLen = key.length - searchKeyOffset;

            assert keyLen >= 0;

            // skip the first offset bytes, then compare no more bytes than
            // remain in the key.
            final int ret = BytesUtil.compareBytesWithLenAndOffset(//
                    searchKeyOffset, keyLen, key,//
                    searchKeyOffset, searchKeyLen, searchKey//
                    );

            if (ret < 0) {

                low = mid + 1;

            } else if (ret > 0) {

                high = mid - 1;

            } else {

                // Found: return offset.

                return mid;

            }

        }

        // Not found: return insertion point.

        return -(low + 1);

    }

    /**
     * Verifies that the keys are in sort order and that undefined keys are
     * [null].
     */
    protected final void assertKeysMonotonic() {

        for (int i = 1; i < nkeys; i++) {

            if (BytesUtil.compareBytes(keys[i], keys[ i - 1] ) <= 0) {

                throw new AssertionError("Keys out of order at index=" + i
                        + ", keys=" + this.toString());

            }

        }

        for( int i=nkeys; i<keys.length; i++ ) {

            if( keys[i] != null ) {

                throw new AssertionError("Expecting null at index="+i);

            }

        }

    }

    /**
     * Computes the length of the prefix by computed by counting the #of leading
     * bytes that match for the first and last key in the buffer.
     */
    public int getPrefixLength() {

        if( nkeys == 0 ) return 0;

        if( nkeys == 1 ) return keys[0].length;

        return BytesUtil.getPrefixLength(keys[0], keys[nkeys - 1]);

    }

    /**
     * Computes the #of leading bytes shared by all keys and returns a new
     * byte[] containing those bytes.
     */
    public byte[] getPrefix() {

        if( nkeys == 0 ) return EMPTY_PREFIX;

        if( nkeys == 1) return keys[0];

        return BytesUtil.getPrefix(keys[0], keys[nkeys-1]);

    }

    private static final transient byte[] EMPTY_PREFIX = new byte[]{};

}

--- NEW FILE: IFusedView.java ---
/**

The Notice below must appear in each file of the Source Code of any
copy you distribute of the Licensed Product.  Contributors to any
Modifications may add their own copyright notices to identify their
own contributions.

License:

The contents of this file are subject to the CognitiveWeb Open Source
License Version 1.1 (the License).  You may not copy or use this file,
in either source code or executable form, except in compliance with
the License.  You may obtain a copy of the License from

  http://www.CognitiveWeb.org/legal/license/

Software distributed under the License is distributed on an AS IS
basis, WITHOUT WARRANTY OF ANY KIND, either express or implied.  See
the License for the specific language governing rights and limitations
under the License.

Copyrights:

Portions created by or assigned to CognitiveWeb are Copyright
(c) 2003-2003 CognitiveWeb.  All Rights Reserved.  Contact
information for CognitiveWeb is available at

  http://www.CognitiveWeb.org

Portions Copyright (c) 2002-2003 Bryan Thompson.

Acknowledgements:

Special thanks to the developers of the Jabber Open Source License 1.0
(JOSL), from which this License was derived.  This License contains
terms that differ from JOSL.

Special thanks to the CognitiveWeb Open Source Contributors for their
suggestions and support of the Cognitive Web.

Modifications:

*/
/*
 * Created on Mar 6, 2007
 */

package com.bigdata.btree;

/**
 * A marker interface indicating fused view providing read-only operations on
 * multiple B+-Trees mapping variable length unsigned byte[] keys to arbitrary
 * values.
 * 
 * @author <a href="mailto:tho...@us...">Bryan Thompson</a>
 * @version $Id$
 */
public interface IFusedView extends IIndex {

    /**
     * Return the ordered array of sources from which the fused view is reading.
     */
    public AbstractBTree[] getSources();

}

--- NEW FILE: BatchInsert.java ---
/**

The Notice below must appear in each file of the Source Code of any
copy you distribute of the Licensed Product.  Contributors to any
Modifications may add their own copyright notices to identify their
own contributions.

License:

The contents of this file are subject to the CognitiveWeb Open Source
License Version 1.1 (the License).  You may not copy or use this file,
in either source code or executable form, except in compliance with
the License.  You may obtain a copy of the License from

  http://www.CognitiveWeb.org/legal/license/

Software distributed under the License is distributed on an AS IS
basis, WITHOUT WARRANTY OF ANY KIND, either express or implied.  See
the License for the specific language governing rights and limitations
under the License.

Copyrights:

Portions created by or assigned to CognitiveWeb are Copyright
(c) 2003-2003 CognitiveWeb.  All Rights Reserved.  Contact
information for CognitiveWeb is available at

  http://www.CognitiveWeb.org

Portions Copyright (c) 2002-2003 Bryan Thompson.

Acknowledgements:

Special thanks to the developers of the Jabber Open Source License 1.0
(JOSL), from which this License was derived.  This License contains
terms that differ from JOSL.

Special thanks to the CognitiveWeb Open Source Contributors for their
suggestions and support of the Cognitive Web.

Modifications:

*/
/*
 * Created on Feb 12, 2007
 */

package com.bigdata.btree;

/**
 * Data for a batch insert operation.
 * 
 * @author <a href="mailto:tho...@us...">Bryan Thompson</a>
 * @version $Id$
 */
public class BatchInsert implements IBatchOp {

    /**
     * The #of tuples to be processed.
     */
    public final int ntuples;

    /**
     * The keys for each tuple.
     */
    public final byte[][] keys;

    /**
     * The value corresponding to each key.
     */
    public final Object[] values;

    /**
     * The index of the tuple that is currently being processed.
     */
    public int tupleIndex = 0;

    /**
     * Create a batch insert operation.
     * 
     * Batch insert operation of N tuples presented in sorted order. This
     * operation can be very efficient if the tuples are presented sorted by key
     * order.
     * 
     * @param ntuples
     *            The #of tuples that are being inserted(in).
     * @param keys
     *            A series of keys paired to values (in). Each key is an
     *            variable length unsigned byte[]. The keys must be presented in
     *            sorted order in order to obtain maximum efficiency for the
     *            batch operation.<br>
     *            The individual byte[] keys provided to this method MUST be
     *            immutable - if the content of a given byte[] in <i>keys</i>
     *            is changed after the method is invoked then the change MAY
     *            have a side-effect on the keys stored in leaves of the tree.
     *            While this constraint applies to the individual byte[] keys,
     *            the <i>keys</i> byte[][] itself may be reused from invocation
     *            to invocation without side-effect.
     * @param values
     *            Values (one element per key) (in/out). Null elements are
     *            allowed. On output, each element is either null (if there was
     *            no entry for that key) or the old value stored under that key
     *            (which may be null).
     */
    public BatchInsert(int ntuples, byte[][] keys, Object[] values) {

        if (ntuples <= 0)
            throw new IllegalArgumentException(Errors.ERR_NTUPLES_NON_POSITIVE);

        if (keys == null)
            throw new IllegalArgumentException(Errors.ERR_KEYS_NULL);

        if( keys.length < ntuples )
            throw new IllegalArgumentException(Errors.ERR_NOT_ENOUGH_KEYS);

        if (values == null)
            throw new IllegalArgumentException(Errors.ERR_VALS_NULL);

        if( values.length < ntuples )
            throw new IllegalArgumentException(Errors.ERR_NOT_ENOUGH_VALS);

        this.ntuples = ntuples;
        this.keys = keys;
        this.values = values;

    }

    /**
     * Applies the operator using {@link ISimpleBTree#insert(Object, Object)}
     * 
     * @param btree
     */
    public void apply(ISimpleBTree btree) {

        while (tupleIndex < ntuples) {

            values[tupleIndex] = btree.insert(keys[tupleIndex],
                    values[tupleIndex]);

            tupleIndex ++;

        }

    }

}

--- NEW FILE: SuccessorUtil.java ---
/**

The Notice below must appear in each file of the Source Code of any
copy you distribute of the Licensed Product.  Contributors to any
Modifications may add their own copyright notices to identify their
own contributions.

License:

The contents of this file are subject to the CognitiveWeb Open Source
License Version 1.1 (the License).  You may not copy or use this file,
in either source code or executable form, except in compliance with
the License.  You may obtain a copy of the License from

  http://www.CognitiveWeb.org/legal/license/

Software distributed under the License is distributed on an AS IS
basis, WITHOUT WARRANTY OF ANY KIND, either express or implied.  See
the License for the specific language governing rights and limitations
under the License.

Copyrights:

Portions created by or assigned to CognitiveWeb are Copyright
(c) 2003-2003 CognitiveWeb.  All Rights Reserved.  Contact
information for CognitiveWeb is available at

  http://www.CognitiveWeb.org

Portions Copyright (c) 2002-2003 Bryan Thompson.

Acknowledgements:

Special thanks to the developers of the Jabber Open Source License 1.0
(JOSL), from which this License was derived.  This License contains
terms that differ from JOSL.

Special thanks to the CognitiveWeb Open Source Contributors for their
suggestions and support of the Cognitive Web.

Modifications:

*/
/*
 * Created on Feb 3, 2007
 */

package com.bigdata.btree;

/**
 * Utility methods for computing the successor of a value for various data
 * types.
 * 
 * @author <a href="mailto:tho...@us...">Bryan Thompson</a>
 * @version $Id$
 * 
 * @see BytesUtil#successor(byte[]), which computes the successor of a variable
 * length unsigned byte[].
 */
public class SuccessorUtil {

    /*
     * useful single precision values.
     */

    /**
     * Positive zero (+0f).
     * <p>
     * Note: +0f and -0f will compare as _equal_ in the language. This means
     * that you can not write tests that directly distinguish positive and
     * negative zero using >, <, or ==.
     */
    final public static float FPOS_ZERO = Float.intBitsToFloat(0x00000000);

    /**
     * Negative zero (-0f).
     * <p>
     * Note: +0f and -0f will compare as _equal_ in the language. This means
     * that you can not write tests that directly distinguish positive and
     * negative zero using >, <, or ==.
     */
    final public static float FNEG_ZERO = Float.intBitsToFloat(0x80000000);

    /**
     * Smallest non-zero positive value.
     */
    final public static float FPOS_MIN = Float.intBitsToFloat(0x00000001);

    /**
     * Smallest non-zero negative value.
     */
    final public static float FNEG_MIN = Float.intBitsToFloat(0x80000001);

    /**
     * Positive one (1f).
     */
    final public static float FPOS_ONE = 1f;

    /**
     * Negative one (-1f).
     */
    final public static float FNEG_ONE = -1f;

    /**
     * Largest positive float.
     */
    final public static float FPOS_MAX = Float.MAX_VALUE;

    /**
     * Largest negative float.
     */
    final public static float FNEG_MAX = Float.intBitsToFloat(0xFF7FFFFF);

    /*
     * useful double precision values.
     */
    /**
     * Positive zero (+0d).
     * <p>
     * Note: +0d and -0d will compare as _equal_ in the language. This means
     * that you can not write tests that directly distinguish positive and
     * negative zero using >, <, or ==.
     */
    final public static double DPOS_ZERO = Double.longBitsToDouble(0x0000000000000000L);

    /**
     * Negative zero (-0d).
     * <p>
     * Note: +0d and -0d will compare as _equal_ in the language. This means
     * that you can not write tests that directly distinguish positive and
     * negative zero using >, <, or ==.
     */
    final public static double DNEG_ZERO = Double.longBitsToDouble(0x8000000000000000L);

    /**
     * Smallest non-zero positive value.
     */
    final public static double DPOS_MIN = Double.longBitsToDouble(0x0000000000000001L);

    /**
     * Smallest non-zero negative value.
     */
    final public static double DNEG_MIN = Double.longBitsToDouble(0x8000000000000001L);

    /**
     * Positive one (1d).
     */
    final public static double DPOS_ONE = 1d;

    /**
     * Negative one (-1d).
     */
    final public static double DNEG_ONE = -1d;

    /**
     * Largest positive double.
     */
    final public static double DPOS_MAX = Double.MAX_VALUE;

    /**
     * Largest negative double.
     */
    final public static double DNEG_MAX = Double.longBitsToDouble(0xFFEFFFFFFFFFFFFFL);

    /*
     * successor methods.
     */

    /**
     * Computes the successor of a <code>byte</code> value.
     * 
     * @param n
     *            A value
     *            
     * @return The successor of that value.
     * 
     * @exception NoSuccessorException
     *                if there is no successor for that value.
     */
    public static byte successor( byte n ) throws NoSuccessorException {

        if (Byte.MAX_VALUE == n) {

            throw new NoSuccessorException();

        } else {

            return (byte) (n + 1);

        }

    }

    /**
     * Computes the successor of a <code>char</code> value.
     * 
     * @param n
     *            A value
     *            
     * @return The successor of that value.
     * 
     * @exception NoSuccessorException
     *                if there is no successor for that value.
     */
    public static char successor( char n ) throws NoSuccessorException
    {

        if (Character.MAX_VALUE == n) {

            throw new NoSuccessorException();

        } else {

            return (char) (n + 1);

        }

    }

    /**
     * Computes the successor of a <code>short</code> value.
     * 
     * @param n
     *            A value
     *            
     * @return The successor of that value.
     * 
     * @exception NoSuccessorException
     *                if there is no successor for that value.
     */
    public static short successor( short n ) throws NoSuccessorException
    {

        if (Short.MAX_VALUE == n) {

            throw new NoSuccessorException();

        } else {

            return (short) (n + 1);

        }

    }

    /**
     * Computes the successor of an <code>int</code> value.
     * 
     * @param n
     *            A value
     *            
     * @return The successor of that value.
     * 
     * @exception NoSuccessorException
     *                if there is no successor for that value.
     */
    public static int successor( int n ) throws NoSuccessorException
    {

        if (Integer.MAX_VALUE == n) {

            throw new NoSuccessorException();

        } else {

            return n + 1;

        }

    }

    /**
     * Computes the successor of a <code>long</code> value.
     * 
     * @param n
     *            A value
     *            
     * @return The successor of that value.
     * 
     * @exception NoSuccessorException
     *                if there is no successor for that value.
     */
    public static long successor( long n ) throws NoSuccessorException
    {

        if (Long.MAX_VALUE == n) {

            throw new NoSuccessorException();

        } else {

            return n + 1L;

        }

    }

    /**
     * <p>
     * Computes the successor of a <code>float</code> value.
     * </p>
     * <p>
     * The IEEE floating point standard provides a means for computing the next
     * larger or smaller floating point value using a bit manipulation trick.
     * See <a
     * href="http://www.cygnus-software.com/papers/comparingfloats/comparingfloats.htm">
     * Comparing floating point numbers </a> by Bruce Dawson. The Java
     * {@link Float} and {@link Double} clases provide the static methods
     * required to convert a float or double into its IEEE 754 floating point
     * bit layout, which can be treated as an int (for floats) or a long (for
     * doubles). By testing for the sign, you can just add (or subtract) one (1)
     * to get the bit pattern of the successor (see the above referenced
     * article). Special exceptions must be made for NaNs, negative infinity and
     * positive infinity.
     * </p>
     * 
     * @param f
     *            The float value.
     * 
     * @return The next value in the value space for <code>float</code>.
     * 
     * @exception NoSuccessorException
     *                if there is no next value in the value space.
     */
    static public float successor( float f )
        throws NoSuccessorException
    {

        if (f == Float.MAX_VALUE) {

            return Float.POSITIVE_INFINITY;

        }

        if (Float.isNaN(f)) {

            throw new NoSuccessorException("NaN");

        }

        if (Float.isInfinite(f)) {

            if (f > 0) {

                throw new NoSuccessorException("Positive Infinity");

            } else {

                /* no successor for negative infinity (could be the largest
                 * negative value).
                 */

                throw new NoSuccessorException("Negative Infinity");

            }

        }

        int bits = Float.floatToIntBits(f);

        if (bits == 0x80000000) {

            /*
             * the successor of -0.0f is +0.0f
             * 
             * @todo Java defines the successor of floating point zeros as the
             * first non-zero value so maybe we should change this.
             */
            return +0.0f;

        }

        if (f >= +0.0f) {

            bits += 1;

        } else {

            bits -= 1;

        }

        float nxt = Float.intBitsToFloat(bits);

        return nxt;

    }

    /**
     * <p>
     * Computes the successor of a <code>double</code> value.
     * </p>
     * <p>
     * The IEEE floating point standard provides a means for computing the next
     * larger or smaller floating point value using a bit manipulation trick.
     * See <a
     * href="http://www.cygnus-software.com/papers/comparingfloats/comparingfloats.htm">
     * Comparing floating point numbers </a> by Bruce Dawson. The Java
     * {@link Float} and {@link Double} clases provide the static methods
     * required to convert a float or double into its IEEE 754 floating point
     * bit layout, which can be treated as an int (for floats) or a long (for
     * doubles). By testing for the sign, you can just add (or subtract) one (1)
     * to get the bit pattern of the successor (see the above referenced
     * article). Special exceptions must be made for NaNs, negative infinity and
     * positive infinity.
     * </p>
     * 
     * @param d The double value.
     * 
     * @return The next value in the value space for <code>double</code>.
     * 
     * @exception NoSuccessorException
     *                if there is no next value in the value space.
     */
    public static double successor( double d ) 
        throws NoSuccessorException
    {

        if (d == Double.MAX_VALUE) {

            return Double.POSITIVE_INFINITY;

        }

        if (Double.isNaN(d)) {

            throw new NoSuccessorException("Nan");

        }

        if (Double.isInfinite(d)) {

            if (d > 0) {

                throw new NoSuccessorException("Positive Infinity");

            } else {

                // The successor of negative infinity.

                return Double.MIN_VALUE;

            }

        }

        long bits = Double.doubleToLongBits(d);

        if (bits == 0x8000000000000000L) {

            /* the successor of -0.0d is +0.0d
             * 
             * @todo Java defines the successor of floating point zeros as the
             * first non-zero value so maybe we should change this.
             */
            return +0.0d;

        }

//        if (f >= +0.0f) {

        if (d >= +0.0) {

            bits += 1;

        } else {

            bits -= 1;

        }

        double nxt = Double.longBitsToDouble(bits);

        return nxt;

    }

    /**
     * The successor of a string value is formed by appending a <code>nul</code>.
     * The successor of a <code>null</code> string reference is an empty
     * string. The successor of a string value is defined unless the string is
     * too long.
     * 
     * @param s The string reference or <code>null</code>.
     * 
     * @return The successor and never <code>null</code>
     */
    public static String successor(String s) {

        if (s == null)
            return "\0";

        return s + "\0";

    }

}

--- NEW FILE: IBatchBTree.java ---
/**

The Notice below must appear in each file of the Source Code of any
copy you distribute of the Licensed Product.  Contributors to any
Modifications may add their own copyright notices to identify their
own contributions.

License:

The contents of this file are subject to the CognitiveWeb Open Source
License Version 1.1 (the License).  You may not copy or use this file,
in either source code or executable form, except in compliance with
the License.  You may obtain a copy of the License from

  http://www.CognitiveWeb.org/legal/license/

Software distributed under the License is distributed on an AS IS
basis, WITHOUT WARRANTY OF ANY KIND, either express or implied.  See
the License for the specific language governing rights and limitations
under the License.

Copyrights:

Portions created by or assigned to CognitiveWeb are Copyright
(c) 2003-2003 CognitiveWeb.  All Rights Reserved.  Contact
information for CognitiveWeb is available at

  http://www.CognitiveWeb.org

Portions Copyright (c) 2002-2003 Bryan Thompson.

Acknowledgements:

Special thanks to the developers of the Jabber Open Source License 1.0
(JOSL), from which this License was derived.  This License contains
terms that differ from JOSL.

Special thanks to the CognitiveWeb Open Source Contributors for their
suggestions and support of the Cognitive Web.

Modifications:

*/
/*
 * Created on Feb 1, 2007
 */

package com.bigdata.btree;

/**
 * 
 * Interface for batch operations a B+-Tree mapping variable length unsigned
 * byte[] keys to arbitrary values. Batch operations can be very efficient if
 * the keys are presented in sorted order.
 * 
 * 
 * All mutation operations on a {@link BTree} are executed in a single threaded
 * context and are therefore atomic. A batch api operation that does NOT span
 * more than one index partition is therefore atomic. However, if an operation
 * spans multiple partitions of an index then NO GUARENTEE is made that the
 * operation is atomic over the set of index partitions.
 * 
 * 
 * @author <a href="mailto:tho...@us...">Bryan Thompson</a>
 * @version $Id$
 * 
 * @see KeyBuilder, which may be used to encode one or more values into a
 * variable length unsigned byte[] key.
 * 
 * @todo add batch api for rangeCount and rangeQuery.
 * 
 * @todo support batch api for indexOf(), keyAt(), valueAt()?
 * 
 * @todo add extensible operation defined by an vector
 * {@link UserDefinedFunction}. Use this to move application logic to the
 * indices as an alternative to scalar {@link UserDefinedFunction}s. For
 * example, the logic that tests an index for a key, increments a counter
 * if the key is not found, and inserts the counter under the key.
 */
public interface IBatchBTree {

    /**
     * Apply a batch insert operation.
     */
    public void insert(BatchInsert op);

    /**
     * Apply a batch lookup operation.
     */
    public void lookup(BatchLookup op);

    /**
     * Apply a batch existence test operation.
     */
    public void contains(BatchContains op);

    /**
     * Apply a batch remove operation.
     */
    public void remove(BatchRemove op);

}

--- NEW FILE: AbstractNode.java ---
/**

The Notice below must appear in each file of the Source Code of any
copy you distribute of the Licensed Product.  Contributors to any
Modifications may add their own copyright notices to identify their
own contributions.

License:

The contents of this file are subject to the CognitiveWeb Open Source
License Version 1.1 (the License).  You may not copy or use this file,
in either source code or executable form, except in compliance with
the License.  You may obtain a copy of the License from

  http://www.CognitiveWeb.org/legal/license/

Software distributed under the License is distributed on an AS IS
basis, WITHOUT WARRANTY OF ANY KIND, either express or implied.  See
the License for the specific language governing rights and limitations
[...1232 lines suppressed...]
     *            
     * @return A string suitable for indent at that height.
     */
    protected static String indent(int height) {

        if( height == -1 ) {

            // The height is not defined.

            return "";

        }

        return ws.substring(0, height * 4);

    }

    private static final transient String ws = "                                                                                                                                                                                                                  ";

}

--- NEW FILE: DirtyChildIterator.java ---
/**

The Notice below must appear in each file of the Source Code of any
copy you distribute of the Licensed Product.  Contributors to any
Modifications may add their own copyright notices to identify their
own contributions.

License:

The contents of this file are subject to the CognitiveWeb Open Source
License Version 1.1 (the License).  You may not copy or use this file,
in either source code or executable form, except in compliance with
the License.  You may obtain a copy of the License from

  http://www.CognitiveWeb.org/legal/license/

Software distributed under the License is distributed on an AS IS
basis, WITHOUT WARRANTY OF ANY KIND, either express or implied.  See
the License for the specific language governing rights and limitations
under the License.

Copyrights:

  http://www.CognitiveWeb.org

Portions Copyright (c) 2002-2003 Bryan Thompson.

Acknowledgements:

Special thanks to the developers of the Jabber Open Source License 1.0
(JOSL), from which this License was derived.  This License contains
terms that differ from JOSL.

Special thanks to the CognitiveWeb Open Source Contributors for their
suggestions and support of the Cognitive Web.

Modifications:

*/
/*
 * Created on Nov 15, 2006
 */
package com.bigdata.btree;

import java.lang.ref.WeakReference;
import java.util.NoSuchElementException;

/**
 * Visits the direct dirty children of a {@link Node} in the external key
 * ordering. Since dirty nodes are always resident this iterator never forces a
 * child to be loaded from the store.
 * 
 * @author <a href="mailto:tho...@us...">Bryan Thompson</a>
 * @version $Id$
 */
class DirtyChildIterator implements INodeIterator {

    private final Node node;

    /**
     * The index of the next child to return.
     */
    private int index = 0;

    /**
     * The index of the last child that was returned to the caller via
     * {@link #next()}.
     */
    private int lastVisited = -1;

    /**
     * The next child to return or null if we need to scan for the next child.
     * We always test to verify that the child is in fact dirty in
     * {@link #next()} since it may have been written out between
     * {@link #hasNext()} and {@link #next()}.
     */
    private AbstractNode child = null;

    /**
     * 
     * @param node
     *            The node whose direct dirty children will be visited in key
     *            order.
     */
    public DirtyChildIterator(Node node) {

        assert node != null;

        this.node = node;

    }

    /**
     * @return true iff there is a dirty child having a separator key greater
     *         than the last visited dirty child at the moment that this method
     *         was invoked. If this method returns <code>true</code> then an
     *         immediate invocation of {@link #next()} will succeed. However,
     *         that guarentee does not hold if intervening code forces the
     *         scheduled dirty child to be written onto the store.
     */
    public boolean hasNext() {

        /*
         * If we are only visiting dirty children, then we need to test the
         * current index. If it is not a dirty child, then we need to scan until
         * we either exhaust the children or find a dirty index.
         */

        if( child != null && child.isDirty() ) {

            /*
             * We have a child reference and it is still dirty.
             */
            return true;

        }

        for( ; index <= node.nkeys; index++ ) {

            WeakReference<AbstractNode> childRef = node.childRefs[index];

            if( childRef == null ) continue;

            child = childRef.get();

            if( child == null ) continue;

            if( ! child.isDirty() ) continue;

            /*
             * Note: We do NOT touch the hard reference queue here since the
             * DirtyChildrenIterator is used when persisting a node using a
             * post-order traversal. If a hard reference queue eviction drives
             * the serialization of a node and we touch the hard reference queue
             * during the post-order traversal then we break down the semantics
             * of HardReferenceQueue#append(...) as the eviction does not
             * necessarily cause the queue to reduce in length.
             */
//            /*
//             * Touch the child so that it will not be a candidate for eviction
//             * to the store.
//             */ 
//            node.btree.touch(node);

            ...

[truncated message content]