btree.java

Java Crawler with domain knowledge path

        }
        if ( value == null ) {
            throw new IllegalArgumentException( "Argument 'value' is null" );
        }

        BPage rootPage = getRoot();

        if ( rootPage == null ) {
            // BTree is currently empty, create a new root BPage
            if (DEBUG) {
                System.out.println( "BTree.insert() new root BPage" );
            }
            rootPage = new BPage( this, key, value );
            _root = rootPage._recid;
            _height = 1;
            _entries = 1;
            _recman.update( _recid, this );
            return null;
        } else {
            BPage.InsertResult insert = rootPage.insert( _height, key, value, replace );
            boolean dirty = false;
            if ( insert._overflow != null ) {
                // current root page overflowed, we replace with a new root page
                if ( DEBUG ) {
                    System.out.println( "BTree.insert() replace root BPage due to overflow" );
                }
                rootPage = new BPage( this, rootPage, insert._overflow );
                _root = rootPage._recid;
                _height += 1;
                dirty = true;
            }
            if ( insert._existing == null ) {
                _entries++;
                dirty = true;
            }
            if ( dirty ) {
                _recman.update( _recid, this );
            }
            // insert might have returned an existing value
            return insert._existing;
        }
    }


    /**
     * Remove an entry with the given key from the BTree.
     *
     * @param key Removal key
     * @return Value associated with the key, or null if no entry with given
     *         key existed in the BTree.
     */
    public synchronized Object remove( Object key )
        throws IOException
    {
        if ( key == null ) {
            throw new IllegalArgumentException( "Argument 'key' is null" );
        }

        BPage rootPage = getRoot();
        if ( rootPage == null ) {
            return null;
        }
        boolean dirty = false;
        BPage.RemoveResult remove = rootPage.remove( _height, key );
        if ( remove._underflow && rootPage.isEmpty() ) {
            _height -= 1;
            dirty = true;

            // TODO:  check contract for BPages to be removed from recman.
            if ( _height == 0 ) {
                _root = 0;
            } else {
                _root = rootPage.childBPage( _pageSize-1 )._recid;
            }
        }
        if ( remove._value != null ) {
            _entries--;
            dirty = true;
        }
        if ( dirty ) {
            _recman.update( _recid, this );
        }
        return remove._value;
    }


    /**
     * Find the value associated with the given key.
     *
     * @param key Lookup key.
     * @return Value associated with the key, or null if not found.
     */
    public synchronized Object find( Object key )
        throws IOException
    {
        if ( key == null ) {
            throw new IllegalArgumentException( "Argument 'key' is null" );
        }
        BPage rootPage = getRoot();
        if ( rootPage == null ) {
            return null;
        }

        Tuple tuple = new Tuple( null, null );
        TupleBrowser browser = rootPage.find( _height, key );

        if ( browser.getNext( tuple ) ) {
            // find returns the matching key or the next ordered key, so we must
            // check if we have an exact match
            if ( _comparator.compare( key, tuple.getKey() ) != 0 ) {
                return null;
            } else {
                return tuple.getValue();
            }
        } else {
            return null;
        }
    }


    /**
     * Find the value associated with the given key, or the entry immediately
     * following this key in the ordered BTree.
     *
     * @param key Lookup key.
     * @return Value associated with the key, or a greater entry, or null if no
     *         greater entry was found.
     */
    public synchronized Tuple findGreaterOrEqual( Object key )
        throws IOException
    {
        Tuple         tuple;
        TupleBrowser  browser;

        if ( key == null ) {
            // there can't be a key greater than or equal to "null"
            // because null is considered an infinite key.
            return null;
        }

        tuple = new Tuple( null, null );
        browser = browse( key );
        if ( browser.getNext( tuple ) ) {
            return tuple;
        } else {
            return null;
        }
    }


    /**
     * Get a browser initially positioned at the beginning of the BTree.
     * <p><b>
     * WARNING: 營f you make structural modifications to the BTree during
     * browsing, you will get inconsistent browing results.
     * </b>
     *
     * @return Browser positionned at the beginning of the BTree.
     */
    public synchronized TupleBrowser browse()
        throws IOException
    {
        BPage rootPage = getRoot();
        if ( rootPage == null ) {
            return EmptyBrowser.INSTANCE;
        }
        TupleBrowser browser = rootPage.findFirst();
        return browser;
    }


    /**
     * Get a browser initially positioned just before the given key.
     * <p><b>
     * WARNING: 營f you make structural modifications to the BTree during
     * browsing, you will get inconsistent browing results.
     * </b>
     *
     * @param key Key used to position the browser.  If null, the browser
     *            will be positionned after the last entry of the BTree.
     *            (Null is considered to be an "infinite" key)
     * @return Browser positionned just before the given key.
     */
    public synchronized TupleBrowser browse( Object key )
        throws IOException
    {
        BPage rootPage = getRoot();
        if ( rootPage == null ) {
            return EmptyBrowser.INSTANCE;
        }
        TupleBrowser browser = rootPage.find( _height, key );
        return browser;
    }


    /**
     * Return the number of entries (size) of the BTree.
     */
    public synchronized int size()
    {
        return _entries;
    }


    /**
     * Return the persistent record identifier of the BTree.
     */
    public long getRecid()
    {
        return _recid;
    }


    /**
     * Return the root BPage, or null if it doesn't exist.
     */
    private BPage getRoot()
        throws IOException
    {
        if ( _root == 0 ) {
            return null;
        }
        BPage root = (BPage) _recman.fetch( _root, _bpageSerializer );
        root._recid = _root;
        root._btree = this;
        return root;
    }

    /**
     * Implement Externalizable interface.
     */
    public void readExternal( ObjectInput in )
        throws IOException, ClassNotFoundException
    {
        _comparator = (Comparator) in.readObject();
        _keySerializer = (Serializer) in.readObject();
        _valueSerializer = (Serializer) in.readObject();
        _height = in.readInt();
        _root = in.readLong();
        _pageSize = in.readInt();
        _entries = in.readInt();
    }


    /**
     * Implement Externalizable interface.
     */
    public void writeExternal( ObjectOutput out )
        throws IOException
    {
        out.writeObject( _comparator );
        out.writeObject( _keySerializer );
        out.writeObject( _valueSerializer );
        out.writeInt( _height );
        out.writeLong( _root );
        out.writeInt( _pageSize );
        out.writeInt( _entries );
    }


    /*
    public void assert() throws IOException {
        BPage root = getRoot();
        if ( root != null ) {
            root.assertRecursive( _height );
        }
    }
    */


    /*
    public void dump() throws IOException {
        BPage root = getRoot();
        if ( root != null ) {
            root.dumpRecursive( _height, 0 );
        }
    }
    */


    /** PRIVATE INNER CLASS
     *  Browser returning no element.
     */
    static class EmptyBrowser
        extends TupleBrowser
    {

        static TupleBrowser INSTANCE = new EmptyBrowser();

        public boolean getNext( Tuple tuple )
        {
            return false;
        }

        public boolean getPrevious( Tuple tuple )
        {
            return false;
        }
    }
}