bpage.java

Java Crawler with domain knowledge path

     */
    private static void copyChildren( BPage source, int indexSource,
                                      BPage dest, int indexDest, int count )
    {
        System.arraycopy( source._keys, indexSource, dest._keys, indexDest, count);
        System.arraycopy( source._children, indexSource, dest._children, indexDest, count);
    }

    
    /**
     * Return the child BPage at given index.
     */
    BPage childBPage( int index )
        throws IOException
    {
        return loadBPage( _children[ index ] );
    }


    /**
     * Load the BPage at the given recid.
     */
    private BPage loadBPage( long recid )
        throws IOException
    {
        BPage child = (BPage) _btree._recman.fetch( recid, this );
        child._recid = recid;
        child._btree = _btree;
        return child;
    }

    
    private final int compare( Object value1, Object value2 )
    {
        if ( value1 == null ) {
            return 1;
        }
        if ( value2 == null ) {
            return -1;
        }
        return _btree._comparator.compare( value1, value2 );
    }

    static byte[] readByteArray( ObjectInput in )
        throws IOException
    {
        int len = in.readInt();
        if ( len < 0 ) {
            return null;
        }
        byte[] buf = new byte[ len ];
        in.readFully( buf );
        return buf;
    }


    static void writeByteArray( ObjectOutput out, byte[] buf )
        throws IOException
    {
        if ( buf == null ) {
            out.writeInt( -1 );
        } else {
            out.writeInt( buf.length );
            out.write( buf );
        }
    }

    /**
     * Dump the structure of the tree on the screen.  This is used for debugging
     * purposes only.
     */
    private void dump( int height )
    {
        String prefix = "";
        for ( int i=0; i<height; i++ ) {
           prefix += "    ";
        }
        System.out.println( prefix + "-------------------------------------- BPage recid=" + _recid);
        System.out.println( prefix + "first=" + _first );
        for ( int i=0; i< _btree._pageSize; i++ ) {
            if ( _isLeaf ) {
                System.out.println( prefix + "BPage [" + i + "] " + _keys[ i ] + " " + _values[ i ] );
            } else {
                System.out.println( prefix + "BPage [" + i + "] " + _keys[ i ] + " " + _children[ i ] );
            }
        }
        System.out.println( prefix + "--------------------------------------" );
    }


    /**
     * Recursively dump the state of the BTree on screen.  This is used for
     * debugging purposes only.
     */
    void dumpRecursive( int height, int level )
        throws IOException
    {
        height -= 1;
        level += 1;
        if ( height > 0 ) {
            for ( int i=_first; i<_btree._pageSize; i++ ) {
                if ( _keys[ i ] == null ) break;
                BPage child = childBPage( i );
                child.dump( level );
                child.dumpRecursive( height, level );
            }
        }
    }


    /**
     * Assert the ordering of the keys on the BPage.  This is used for testing
     * purposes only.
     */
    private void assertConsistency()
    {
        for ( int i=_first; i<_btree._pageSize-1; i++ ) {
            if ( compare( (byte[]) _keys[ i ], (byte[]) _keys[ i+1 ] ) >= 0 ) {
                dump( 0 );
                throw new Error( "BPage not ordered" );
            }
        }
    }


    /**
     * Recursively assert the ordering of the BPage entries on this page
     * and sub-pages.  This is used for testing purposes only.
     */
    void assertConsistencyRecursive( int height ) 
        throws IOException 
    {
        assertConsistency();
        if ( --height > 0 ) {
            for ( int i=_first; i<_btree._pageSize; i++ ) {
                if ( _keys[ i ] == null ) break;
                BPage child = childBPage( i );
                if ( compare( (byte[]) _keys[ i ], child.getLargestKey() ) != 0 ) {
                    dump( 0 );
                    child.dump( 0 );
                    throw new Error( "Invalid child subordinate key" );
                }
                child.assertConsistencyRecursive( height );
            }
        }
    }


    /**
     * Deserialize the content of an object from a byte array.
     *
     * @param serialized Byte array representation of the object
     * @return deserialized object
     *
     */
    public Object deserialize( byte[] serialized ) 
        throws IOException
    {
        ByteArrayInputStream  bais;
        ObjectInputStream     ois;
        BPage                 bpage;

        bpage = new BPage();
        bais = new ByteArrayInputStream( serialized );
        ois = new ObjectInputStream( bais );
        
        bpage._isLeaf = ois.readBoolean();
        if ( bpage._isLeaf ) {
            bpage._previous = ois.readLong();
            bpage._next = ois.readLong();
        }

        bpage._first = ois.readInt();

        bpage._keys = new Object[ _btree._pageSize ];
        try {
            for ( int i=bpage._first; i<_btree._pageSize; i++ ) {
                if ( _btree._keySerializer == null ) {
                    bpage._keys[ i ] = ois.readObject();
                } else {
                    serialized = readByteArray( ois );
                    if ( serialized != null ) {
                        bpage._keys[ i ] = _btree._keySerializer.deserialize( serialized );
                    }
                }
            }
        } catch ( ClassNotFoundException except ) {
            throw new IOException( except.getMessage() );
        }
        
        if ( bpage._isLeaf ) {
            bpage._values = new Object[ _btree._pageSize ];
            try {
                for ( int i=bpage._first; i<_btree._pageSize; i++ ) {
                    if ( _btree._valueSerializer == null ) {
                        bpage._values[ i ] = ois.readObject();
                    } else {
                        serialized = readByteArray( ois );
                        if ( serialized != null ) {
                            bpage._values[ i ] = _btree._valueSerializer.deserialize( serialized );
                        }
                    }
                }
            } catch ( ClassNotFoundException except ) {
                throw new IOException( except.getMessage() );
            }
        } else {
            bpage._children = new long[ _btree._pageSize ];
            for ( int i=bpage._first; i<_btree._pageSize; i++ ) {
                bpage._children[ i ] = ois.readLong();
            }
        }
        ois.close();
        bais.close();
        
        return bpage;
    }

    
    /** 
     * Serialize the content of an object into a byte array.
     *
     * @param obj Object to serialize
     * @return a byte array representing the object's state
     *
     */
    public byte[] serialize( Object obj ) 
        throws IOException
    {
        byte[]                 serialized;
        ByteArrayOutputStream  baos;
        ObjectOutputStream     oos;
        BPage                  bpage;
        byte[]                 data;
        
        // note:  It is assumed that BPage instance doing the serialization is the parent
        // of the BPage object being serialized.
        
        bpage = (BPage) obj;
        baos = new ByteArrayOutputStream();
        oos = new ObjectOutputStream( baos );        
        
        oos.writeBoolean( bpage._isLeaf );
        if ( bpage._isLeaf ) {
            oos.writeLong( bpage._previous );
            oos.writeLong( bpage._next );
        }

        oos.writeInt( bpage._first );
        
        for ( int i=bpage._first; i<_btree._pageSize; i++ ) {
            if ( _btree._keySerializer == null ) {
                oos.writeObject( bpage._keys[ i ] );
            } else {
                if ( bpage._keys[ i ] != null ) {
                    serialized = _btree._keySerializer.serialize( bpage._keys[ i ] );
                    writeByteArray( oos, serialized );
                } else {
                    writeByteArray( oos, null );
                }
            }
        }

        if ( bpage._isLeaf ) {
            for ( int i=bpage._first; i<_btree._pageSize; i++ ) {
                if ( _btree._valueSerializer == null ) {
                    oos.writeObject( bpage._values[ i ] );
                } else {
                    if ( bpage._values[ i ] != null ) {
                        serialized = _btree._valueSerializer.serialize( bpage._values[ i ] );
                        writeByteArray( oos, serialized );
                    } else {
                        writeByteArray( oos, null );
                    }
                }
            }
        } else {
            for ( int i=bpage._first; i<_btree._pageSize; i++ ) {
                oos.writeLong( bpage._children[ i ] );
            }
        }
        
        oos.flush();
        data = baos.toByteArray();
        oos.close();
        baos.close();
        return data;
    }
    
    
    /** STATIC INNER CLASS
     *  Result from insert() method call
     */
    static class InsertResult {

        /**
         * Overflow page.
         */
        BPage _overflow;

        /**
         * Existing value for the insertion key.
         */
        Object _existing;

    }

    /** STATIC INNER CLASS
     *  Result from remove() method call
     */
    static class RemoveResult {

        /**
         * Set to true if underlying pages underflowed
         */
        boolean _underflow;

        /**
         * Removed entry value
         */
        Object _value;
    }


    /** PRIVATE INNER CLASS
     * Browser to traverse leaf BPages.
     */
    static class Browser
        extends TupleBrowser
    {

        /**
         * Current page.
         */
        private BPage _page;


        /**
         * Current index in the page.  The index positionned on the next
         * tuple to return.
         */
        private int _index;


        /**
         * Create a browser.
         *
         * @param page Current page
         * @param index Position of the next tuple to return.
         */
        Browser( BPage page, int index )
        {
            _page = page;
            _index = index;
        }

        public boolean getNext( Tuple tuple )
            throws IOException
        {
            if ( _index < _page._btree._pageSize ) {
                if ( _page._keys[ _index ] == null ) {
                    // reached end of the tree.
                    return false;
                }
            } else if ( _page._next != 0 ) {
                // move to next page
                _page = _page.loadBPage( _page._next );
                _index = _page._first;
            }
            tuple.setKey( _page._keys[ _index ] );
            tuple.setValue( _page._values[ _index ] );
            _index++;
            return true;
        }

        public boolean getPrevious( Tuple tuple )
            throws IOException
        {
            if ( _index == _page._first ) {

                if ( _page._previous != 0 ) {
                    _page = _page.loadBPage( _page._previous );
                    _index = _page._btree._pageSize;
                } else {
                    // reached beginning of the tree
                    return false;
                }
            }
            _index--;
            tuple.setKey( _page._keys[ _index ] );
            tuple.setValue( _page._values[ _index ] );
            return true;

        }
    }

}