hashdirectory.java

Java Crawler with domain knowledge path

                    }

                    // (finally!) insert new element
                    return dir.put( key, value );
                }
            }
        }
    }


    /**
     * Remove the value which is associated with the given key.  If the
     * key does not exist, this method simply ignores the operation.
     *
     * @param key key whose associated value is to be removed
     * @return object which was associated with the given key, or
     *          <code>null</code> if no association existed with given key.
     */
    Object remove(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.remove() child is : "+node);

            if (node instanceof HashDirectory) {
                // recurse into next directory level
                HashDirectory dir = (HashDirectory)node;
                dir.setPersistenceContext( _recman, child_recid );
                Object existing = dir.remove(key);
                if (existing != null) {
                    if (dir.isEmpty()) {
                        // delete empty directory
                        _recman.delete(child_recid);
                        _children[hash] = 0;
                        _recman.update(_recid, this);
                    }
                }
                return existing;
            } else {
                // node is a bucket
                HashBucket bucket = (HashBucket)node;
                Object existing = bucket.removeElement(key);
                if (existing != null) {
                    if (bucket.getElementCount() >= 1) {
                        _recman.update(child_recid, bucket);
                    } else {
                        // delete bucket, it's empty
                        _recman.delete(child_recid);
                        _children[hash] = 0;
                        _recman.update(_recid, this);
                    }
                }
                return existing;
            }
        }
    }

    /**
     * Calculates the hashcode of a key, based on the current directory
     * depth.
     */
    private int hashCode(Object key) {
        int hashMask = hashMask();
        int hash = key.hashCode();
        hash = hash & hashMask;
        hash = hash >>> ((MAX_DEPTH - _depth) * BIT_SIZE);
        hash = hash % MAX_CHILDREN;
        /*
        System.out.println("HashDirectory.hashCode() is: 0x"
                           +Integer.toHexString(hash)
                           +" for object hashCode() 0x"
                           +Integer.toHexString(key.hashCode()));
        */
        return hash;
    }

    /**
     * Calculates the hashmask of this directory.  The hashmask is the
     * bit mask applied to a hashcode to retain only bits that are
     * relevant to this directory level.
     */
    int hashMask() {
        int bits = MAX_CHILDREN-1;
        int hashMask = bits << ((MAX_DEPTH - _depth) * BIT_SIZE);
        /*
        System.out.println("HashDirectory.hashMask() is: 0x"
                           +Integer.toHexString(hashMask));
        */
        return hashMask;
    }

    /**
     * Returns an enumeration of the keys contained in this
     */
    FastIterator keys()
        throws IOException
    {
        return new HDIterator( true );
    }

    /**
     * Returns an enumeration of the values contained in this
     */
    FastIterator values()
        throws IOException
    {
        return new HDIterator( false );
    }


    /**
     * Implement Externalizable interface
     */
    public void writeExternal(ObjectOutput out)
    throws IOException {
        out.writeByte(_depth);
        out.writeObject(_children);
    }


    /**
     * Implement Externalizable interface
     */
    public synchronized void readExternal(ObjectInput in)
    throws IOException, ClassNotFoundException {
        _depth = in.readByte();
        _children = (long[])in.readObject();
    }


    ////////////////////////////////////////////////////////////////////////
    // INNER CLASS
    ////////////////////////////////////////////////////////////////////////

    /**
     * Utility class to enumerate keys/values in a HTree
     */
    public class HDIterator
        extends FastIterator
    {

        /**
         * True if we're iterating on keys, False if enumerating on values.
         */
        private boolean _iterateKeys;

        /**
         * Stacks of directories & last enumerated child position
         */
        private ArrayList _dirStack;
        private ArrayList _childStack;

        /**
         * Current HashDirectory in the hierarchy
         */
        private HashDirectory _dir;

        /**
         * Current child position
         */
        private int _child;

        /**
         * Current bucket iterator
         */
        private Iterator _iter;


        /**
         * Construct an iterator on this directory.
         *
         * @param iterateKeys True if iteration supplies keys, False
         *                  if iterateKeys supplies values.
         */
        HDIterator( boolean iterateKeys )
            throws IOException
        {
            _dirStack = new ArrayList();
            _childStack = new ArrayList();
            _dir = HashDirectory.this;
            _child = -1;
            _iterateKeys = iterateKeys;

            prepareNext();
        }


        /**
         * Returns the next object.
         */
        public Object next()
        {   
            Object next = null;      
            if( _iter != null && _iter.hasNext() ) {
              next = _iter.next();
            } else {
              try {
                prepareNext();
              } catch ( IOException except ) {
                throw new IterationException( except );
              }
              if ( _iter != null && _iter.hasNext() ) {
                return next();
              }
            }
            return next;         
        }


        /**
         * Prepare internal state so we can answer <code>hasMoreElements</code>
         *
         * Actually, this code prepares an Enumeration on the next
         * Bucket to enumerate.   If no following bucket is found,
         * the next Enumeration is set to <code>null</code>.
         */
        private void prepareNext() throws IOException {
            long child_recid = 0;

            // find next bucket/directory to enumerate
            do {
                _child++;
                if (_child >= MAX_CHILDREN) {

                    if (_dirStack.isEmpty()) {
                        // no more directory in the stack, we're finished
                        return;
                    }

                    // try next page
                    _dir = (HashDirectory) _dirStack.remove( _dirStack.size()-1 );
                    _child = ( (Integer) _childStack.remove( _childStack.size()-1 ) ).intValue();
                    continue;
                }
                child_recid = _dir._children[_child];
            } while (child_recid == 0);

            if (child_recid == 0) {
                throw new Error("child_recid cannot be 0");
            }

            HashNode node = (HashNode) _recman.fetch( child_recid );
            // System.out.println("HDEnumeration.get() child is : "+node);
 
            if ( node instanceof HashDirectory ) {
                // save current position
                _dirStack.add( _dir );
                _childStack.add( new Integer( _child ) );

                _dir = (HashDirectory)node;
                _child = -1;

                // recurse into
                _dir.setPersistenceContext( _recman, child_recid );
                prepareNext();
            } else {
                // node is a bucket
                HashBucket bucket = (HashBucket)node;
                if ( _iterateKeys ) {
                    _iter = bucket.getKeys().iterator();
                } else {
                    _iter = bucket.getValues().iterator();
                }
            }
        }
    }

}