hashdirectory.java

Java Crawler with domain knowledge path

/**
 * JDBM LICENSE v1.00
 *
 * Redistribution and use of this software and associated documentation
 * ("Software"), with or without modification, are permitted provided
 * that the following conditions are met:
 *
 * 1. Redistributions of source code must retain copyright
 *    statements and notices.  Redistributions must also contain a
 *    copy of this document.
 *
 * 2. Redistributions in binary form must reproduce the
 *    above copyright notice, this list of conditions and the
 *    following disclaimer in the documentation and/or other
 *    materials provided with the distribution.
 *
 * 3. The name "JDBM" must not be used to endorse or promote
 *    products derived from this Software without prior written
 *    permission of Cees de Groot.  For written permission,
 *    please contact [e-mail].
 *
 * 4. Products derived from this Software may not be called "JDBM"
 *    nor may "JDBM" appear in their names without prior written
 *    permission of Cees de Groot.
 *
 * 5. Due credit should be given to the JDBM Project
 *    (http://jdbm.sourceforge.net/).
 *
 * THIS SOFTWARE IS PROVIDED BY THE JDBM PROJECT AND CONTRIBUTORS
 * ``AS IS'' AND ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT
 * NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
 * FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL
 * CEES DE GROOT OR ANY CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
 * OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * Copyright 2000 (C) Cees de Groot. All Rights Reserved.
 * Contributions are Copyright (C) 2000 by their associated contributors.
 *
 */

package jdbm.htree;

import jdbm.RecordManager;

import jdbm.helper.FastIterator;
import jdbm.helper.IterationException;

import java.io.Externalizable;
import java.io.IOException;
import java.io.ObjectInput;
import java.io.ObjectOutput;

import java.util.ArrayList;
import java.util.Iterator;

/**
 *  Hashtable directory page.
 *
 *  @author <a href="mailto:[e-mail]">Alex Boisvert</a>
 *  @version $Id: HashDirectory.java,v 1.5 2005/06/25 23:12:32 doomdark Exp $
 */
final class HashDirectory
    extends HashNode
    implements Externalizable
{

    static final long serialVersionUID = 1L;


    /**
     * Maximum number of children in a directory.
     *
     * (Must be a power of 2 -- if you update this value, you must also
     *  update BIT_SIZE and MAX_DEPTH.)
     */
    static final int MAX_CHILDREN = 256;


    /**
     * Number of significant bits per directory level.
     */
    static final int BIT_SIZE = 8; // log2(256) = 8


    /**
     * Maximum number of levels (zero-based)
     *
     * (4 * 8 bits = 32 bits, which is the size of an "int", and as
     *  you know, hashcodes in Java are "ints")
     */
    static final int MAX_DEPTH = 3; // 4 levels


    /**
     * Record ids of children pages.
     */
    private long[] _children;


    /**
     * Depth of this directory page, zero-based
     */
    private byte _depth;


    /**
     * PageManager used to persist changes in directory and buckets
     */
    private transient RecordManager _recman;


    /**
     * This directory's record ID in the PageManager.  (transient)
     */
    private transient long _recid;


    /**
     * Public constructor used by serialization
     */
    public HashDirectory() {
        // empty
    }

    /**
     * Construct a HashDirectory
     *
     * @param depth Depth of this directory page.
     */
    HashDirectory(byte depth) {
        _depth = depth;
        _children = new long[MAX_CHILDREN];
    }


    /**
     * Sets persistence context.  This method must be called before any
     * persistence-related operation.
     *
     * @param recman RecordManager which stores this directory
     * @param recid Record id of this directory.
     */
    void setPersistenceContext( RecordManager recman, long recid )
    {
        this._recman = recman;
        this._recid = recid;
    }


    /**
     * Get the record identifier used to load this hashtable.
     */
    long getRecid() {
        return _recid;
    }


    /**
     * Returns whether or not this directory is empty.  A directory
     * is empty when it no longer contains buckets or sub-directories.
     */
    boolean isEmpty() {
        for (int i=0; i<_children.length; i++) {
            if (_children[i] != 0) {
                return false;
            }
        }
        return true;
    }

    /**
     * Returns the value which is associated with the given key. Returns
     * <code>null</code> if there is not association for this key.
     *
     * @param key key whose associated value is to be returned
     */
    Object get(Object key)
        throws IOException
    {
        int hash = hashCode( key );
        long child_recid = _children[ hash ];
        if ( child_recid == 0 ) {
            // not bucket/page --> not found
            return null;
        } else {
            HashNode node = (HashNode) _recman.fetch( child_recid );
            // System.out.println("HashDirectory.get() child is : "+node);

            if ( node instanceof HashDirectory ) {
                // recurse into next directory level
                HashDirectory dir = (HashDirectory) node;
                dir.setPersistenceContext( _recman, child_recid );
                return dir.get( key );
            } else {
                // node is a bucket
                HashBucket bucket = (HashBucket) node;
                return bucket.getValue( key );
            }
        }
    }


    /**
     * Associates the specified value with the specified key.
     *
     * @param key key with which the specified value is to be assocated.
     * @param value value to be associated with the specified key.
     * @return object which was previously associated with the given key,
     *          or <code>null</code> if no association existed.
     */
    Object put(Object key, Object value)
    throws IOException {
        if (value == null) {
            return remove(key);
        }
        int hash = hashCode(key);
        long child_recid = _children[hash];
        if (child_recid == 0) {
            // no bucket/page here yet, let's create a bucket
            HashBucket bucket = new HashBucket(_depth+1);

            // insert (key,value) pair in bucket
            Object existing = bucket.addElement(key, value);

            long b_recid = _recman.insert(bucket);
            _children[hash] = b_recid;

            _recman.update(_recid, this);

            // System.out.println("Added: "+bucket);
            return existing;
        } else {
            HashNode node = (HashNode) _recman.fetch( child_recid );

            if ( node instanceof HashDirectory ) {
                // recursive insert in next directory level
                HashDirectory dir = (HashDirectory) node;
                dir.setPersistenceContext( _recman, child_recid );
                return dir.put( key, value );
            } else {
                // node is a bucket
                HashBucket bucket = (HashBucket)node;
                if (bucket.hasRoom()) {
                    Object existing = bucket.addElement(key, value);
                    _recman.update(child_recid, bucket);
                    // System.out.println("Added: "+bucket);
                    return existing;
                } else {
                    // overflow, so create a new directory
                    if (_depth == MAX_DEPTH) {
                        throw new RuntimeException( "Cannot create deeper directory. "
                                                    + "Depth=" + _depth );
                    }
                    HashDirectory dir = new HashDirectory( (byte) (_depth+1) );
                    long dir_recid = _recman.insert( dir );
                    dir.setPersistenceContext( _recman, dir_recid );

                    _children[hash] = dir_recid;
                    _recman.update( _recid, this );

                    // discard overflown bucket
                    _recman.delete( child_recid );

                    // migrate existing bucket elements
                    ArrayList keys = bucket.getKeys();
                    ArrayList values = bucket.getValues();
                    int entries = keys.size();
                    for ( int i=0; i<entries; i++ ) {
                        dir.put( keys.get( i ), values.get( i ) );