fulltreemapimpl.java

Java的面向对象数据库系统的源代码

/*
 * $Id: FullTreeMapImpl.java,v 1.6 2003/11/27 15:55:11 leomekenkamp Exp $
 * This file is based on TreeMap.java from GNU Classpath. Quote:

TreeMap.java -- a class providing a basic Red-Black Tree data structure,
mapping Object --> Object
Copyright (C) 1998, 1999, 2000, 2001, 2002 Free Software Foundation, Inc.

This file is part of GNU Classpath.

GNU Classpath is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2, or (at your option)
any later version.

GNU Classpath is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
General Public License for more details.

You should have received a copy of the GNU General Public License
along with GNU Classpath; see the file COPYING.  If not, write to the
Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
02111-1307 USA.

Linking this library statically or dynamically with other modules is
making a combined work based on this library.  Thus, the terms and
conditions of the GNU General Public License cover the whole
combination.

As a special exception, the copyright holders of this library give you
permission to link this library with independent modules to produce an
executable, regardless of the license terms of these independent
modules, and to copy and distribute the resulting executable under
terms of your choice, provided that you also meet, for each linked
independent module, the terms and conditions of the license of that
module.  An independent module is a module which is not derived from
or based on this library.  If you modify this library, you may extend
this exception to your version of the library, but you are not
obligated to do so.  If you do not wish to do so, delete this
exception statement from your version.

 * end quote.
 *
 * This file is licenced under the same conditions as its original (GPL +
 * "special exception").
 */

package org.ozoneDB.collections;


import java.io.ObjectOutputStream;
import java.io.ObjectInputStream;
import java.io.IOException;
import java.util.Comparator;
import java.util.Map;
import java.util.SortedMap;
/**
 * This class provides a red-black tree implementation of the SortedMap
 * interface.  Elements in the Map will be sorted by either a user-provided
 * Comparator object, or by the natural ordering of the keys.
 *
 * The algorithms are adopted from Corman, Leiserson, and Rivest's
 * <i>Introduction to Algorithms.</i>  TreeMap guarantees O(log n)
 * insertion and deletion of elements.  That being said, there is a large
 * enough constant coefficient in front of that "log n" (overhead involved
 * in keeping the tree balanced), that TreeMap may not be the best choice
 * for small collections. If something is already sorted, you may want to
 * just use a LinkedHashMap to maintain the order while providing O(1) access.
 *
 * TreeMap is a part of the JDK1.2 Collections API.  Null keys are allowed
 * only if a Comparator is used which can deal with them; natural ordering
 * cannot cope with null.  Null values are always allowed. Note that the
 * ordering must be <i>consistent with equals</i> to correctly implement
 * the Map interface. If this condition is violated, the map is still
 * well-behaved, but you may have suprising results when comparing it to
 * other maps.<p>
 *
 * This implementation is not synchronized. If you need to share this between
 * multiple threads, do something like:<br>
 * <code>SortedMap m
 *       = Collections.synchronizedSortedMap(new TreeMap(...));</code><p>
 *
 * The iterators are <i>fail-fast</i>, meaning that any structural
 * modification, except for <code>remove()</code> called on the iterator
 * itself, cause the iterator to throw a
 * <code>ConcurrentModificationException</code> rather than exhibit
 * non-deterministic behavior.
 *
 * <p>Note that the first call to <code>entrySet()</code>, <code>keySet()</code>
 * and <code>values()</code> results in the creation of a new ozone object.</p>
 *
 * <p><b>NOTE:</b> Because of issues with implementing 2 Ozone objects that have
 * to share non-Ozone objects, it can happen that a <code>FullXxx</code> 
 * instance is written to the backend-store while the <code>Iterator</code>
 * remains in memory. If that happens you will receive a <code>ConcurrentModificationException</code>.
 * If you receive such an exception and are completely sure that the collection
 * has not been changed (objects added or removed from it) by another process, 
 * you should increase the memory available to the Ozone server, or decrease the
 * time between successive calls on the methods of the iterator. It should be
 * noted that there is no way to guarantee that an exception is thrown in this
 * situation, just like there is no guarantee that an exception will be thrown
 * when a 'regular' <code>java.util.Collection</code> is changed while an
 * iterator is at the same time iterating over it. This is theory, but in the 
 * real world the changes of this happening are negligable.</code>
 
 </p>
 *
 * @author Jon Zeppieri
 * @author Bryce McKinlay
 * @author Eric Blake <[e-mail]>
 * @author <a href="mailto:ozoneATmekenkampD0Tcom">Leo Mekenkamp (mind the anti-sp@m)</a> (adaptation for ozone)
 * @see java.util.TreeMap
 * @see java.util.Collections#synchronizedSortedMap(SortedMap)
 */
public class FullTreeMapImpl extends BaseTreeMapImpl implements FullTreeMap {
    // Implementation note:
    // A red-black tree is a binary search tree with the additional properties
    // that all paths to a leaf node visit the same number of black nodes,
    // and no red node has red children. To avoid some null-pointer checks,
    // we use the special node nil which is always black, has no relatives,
    // and has key and value of null (but is not equal to a mapping of null).

    private static final long serialVersionUID = 1L;

    private class Node extends AbstractOzoneMap.AbstractNode implements BaseTreeMap.Node {

        private static final long serialVersionUID = 1L;

        private int color;

        private BaseTreeMap.Node left = BaseTreeMapImpl.nilNode;

        private BaseTreeMap.Node right = BaseTreeMapImpl.nilNode;

        private BaseTreeMap.Node parent = BaseTreeMapImpl.nilNode;

        public Node(Object key, Object value, int color) {
            super(key, value);
            setColor(color);
        }

        public void setRight(BaseTreeMap.Node right) {
            this.right = right;
        }

        public void setParent(BaseTreeMap.Node parent) {
            this.parent = parent;
        }

        public void setLeft(BaseTreeMap.Node left) {
            this.left = left;
        }

        public void setColor(int color) {
            this.color = color;
        }

        public BaseTreeMap.Node getRight() {
            return right;
        }

        public BaseTreeMap.Node getParent() {
            return parent;
        }

        public BaseTreeMap.Node getLeft() {
            return left;
        }

        public int getColor() {
            return color;
        }

        public boolean isNil() {
            return false;
        }

    }

    /**
     * Instantiate a new TreeMap with no elements, using the keys' natural
     * ordering to sort. All entries in the map must have a key which implements
     * Comparable, and which are <i>mutually comparable</i>, otherwise map
     * operations may throw a {@link ClassCastException}. Attempts to use
     * a null key will throw a {@link NullPointerException}.
     *
     * @see Comparable
     */
    public FullTreeMapImpl() {
    }

    /**
     * Instantiate a new TreeMap with no elements, using the provided comparator
     * to sort. All entries in the map must have keys which are mutually
     * comparable by the Comparator, otherwise map operations may throw a
     * {@link ClassCastException}.
     *
     * @param c (comparator) the sort order for the keys of this map, or null
     *        for the natural order
     */
    public FullTreeMapImpl(Comparator c) {
        super(c);
    }

    /**
     * Instantiate a new TreeMap, initializing it with all of the elements in
     * the provided Map.  The elements will be sorted using the natural
     * ordering of the keys. This algorithm runs in n*log(n) time. All entries
     * in the map must have keys which implement Comparable and are mutually
     * comparable, otherwise map operations may throw a
     * {@link ClassCastException}.
     *
     * @param map a Map, whose entries will be put into this TreeMap
     * @throws ClassCastException if the keys in the provided Map are not
     *         comparable
     * @throws NullPointerException if map is null
     * @see Comparable
     */
    public FullTreeMapImpl(Map map) {
        super(map);
    }

    /**
     * Instantiate a new TreeMap, initializing it with all of the elements in
     * the provided SortedMap.  The elements will be sorted using the same
     * comparator as in the provided SortedMap. This runs in linear time.
     *
     * @param sm a SortedMap, whose entries will be put into this TreeMap
     * @throws NullPointerException if sm is null
     */
    public FullTreeMapImpl(SortedMap sm) {
        super(sm); // super sm ??? LOL!
    }

    protected BaseTreeMap emptyClone() {
        // TODO: when FakeFactoryGenerator is finished replace with
        // return FullTreeMapImplFactory.getDefault().create();
        return (BaseTreeMap) database().createObject(FullTreeMapImpl.class);
    }

    protected BaseTreeMap.Node newNode(Object key, Object value, int color) {
        BaseTreeMap.Node result = new Node(key, value, color);
        return result;
    }

    /**
     * Deserializes this object from the given stream.
     *
     * @param s the stream to read from
     * @throws ClassNotFoundException if the underlying stream fails
     * @throws IOException if the underlying stream fails
     * @serialData the <i>size</i> (int), followed by key (Object) and value
     *             (Object) pairs in sorted order
     */
    private void readObject(ObjectInputStream s) throws IOException, ClassNotFoundException {
        root = nilNode;
        s.defaultReadObject();
        putFromObjStream(s, size, true);
    }

    /**
     * @param s the stream to read from
     * @param count the number of keys to read
     * @param readValues true to read values, false to insert "" as the value
     * @throws ClassNotFoundException if the underlying stream fails
     * @throws IOException if the underlying stream fails
     * @see #readObject(ObjectInputStream)
     * @see java.util.TreeSet#readObject(ObjectInputStream)
     */
    private void putFromObjStream(ObjectInputStream s, int count, boolean readValues)
            throws IOException, ClassNotFoundException {
        _org_ozoneDB_fabricateTree(count);
        BaseTreeMap.Node node = _org_ozoneDB_firstNode();

        while (--count >= 0) {
            node.setKey(s.readObject());
            node.setValue(readValues ? s.readObject() : "");
            node = _org_ozoneDB_successor(node);
        }
    }

    /**
     * Serializes this object to the given stream.
     *
     * @param s the stream to write to
     * @throws IOException if the underlying stream fails
     * @serialData the <i>size</i> (int), followed by key (Object) and value
     *             (Object) pairs in sorted order
     */
    private void writeObject(ObjectOutputStream s) throws IOException {
        s.defaultWriteObject();

        BaseTreeMap.Node node = _org_ozoneDB_firstNode();
        while (!node.isNil()) {
            s.writeObject(node.getKey());
            s.writeObject(node.getValue());
            node = _org_ozoneDB_successor(node);
        }
    }

    public boolean _org_ozoneDB_alwaysUseInternalIterator() {
        return false;
    }
    
    /**
     * Called automatically by Ozone. Increments the modification counter to
     * make sure all <code>Iterator</code>s that were connected to a previous
     * (memory) instance of this database object are invalidated.
     */
    public void onActivate() {
        // TODO: FIXME: Aren't we taking a risk here? The javadocs for <code>ConcurrentModificationException</code>
        // for instance clearly state that developers should not depend on that
        // exception being thrown, probably because there is a "1 in 2^32 chance"
        // that the internal mod counts for collection and iterator are the same
        // while the collection has been changed. Actually this chance might be a
        // lot smaller, since actually there have to be 2^32 operations on the
        // collection and at the same time the iterator should go unused.
        // Anyway, we <i>are</i> taking a risk here, albeit a small one, since
        // for the modCount to be the same on an iterator and this collection
        // we need either: 1) 0 changes on the collection and a roll-over on the
        // high bits (probably Integer.MAX_VALUE times); or 2) Integer.MAX_VALUE
        // changes for the low bits and Integer.MAX_VALUE - 1 writes for the high
        // bits 3) any multiple of the above with a complete roll-over of the
        // modCount. Since Java is not certified for use in nuclear installations,
        // hart-monitoring machines, etc. I am willing to take this risk.
        modCount += Integer.MAX_VALUE / 2;
    }
    
}