indexbranchnode.java

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

// You can redistribute this software and/or modify it under the terms of
// the Ozone Core License version 1 published by ozone-db.org.
//
// Copyright (C) 2003-@year@, Leo Mekenkamp. All rights reserved.
//
// $Id: IndexBranchNode.java,v 1.4 2004/02/01 20:55:47 leomekenkamp Exp $

package org.ozoneDB.core.storage.gammaStore;

import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.SortedMap;
import java.util.TreeMap;
import java.util.logging.Level;
import org.ozoneDB.ObjectNotFoundException;
import org.ozoneDB.OzoneInternalException;

/**
 * @author <a href="mailto:leoATmekenkampD0Tcom">Leo Mekenkamp (mind the anti sp@m)</a>
 * @version $Id: IndexBranchNode.java,v 1.4 2004/02/01 20:55:47 leomekenkamp Exp $
 */
final class IndexBranchNode extends IndexNode {
    
    private static final long serialVersionUID = 0L;

    // key: long minimum object id; value: long node id
    private NodeIdLoc nodeIdLoc;
    
    /**
     * Creates a branch node; created node places itself in the index managers
     * cache, but is not yet connected to any other nodes.
     */
    IndexBranchNode(IndexManager indexManager) {
        super(indexManager);
        setMaxSize(indexManager.getMaxBranchNodeSize());
        nodeIdLoc = new NodeIdLoc(getMaxSize(), 0);
        setIndexManager(indexManager);
    }
 
    // private so it can be inlined
    private NodeIdLoc getNodeIdLoc() {
        return nodeIdLoc;
    }
    
    /**
     * Returns the id of a child node of this node, containing the specified
     * object id. If the specified object id does not exist in any child node,
     * this method returns the most appropriate child node.
     */
    long getChildNodeId(long objectId) {
        int pos = getNodeIdLoc().getKeyPosOrNearestSmaller(objectId);
        if (pos < 0) {
            pos = getNodeIdLoc().getKeyPosOrNearestGreater(objectId);
            if (pos < 0) {
                throw new OzoneInternalException("BUG: no smaller AND no greater for " + objectId);
            }
        }
        return getNodeIdLoc().getNodeId(pos);
    }

    /**
     * Adds a child node in this node. Does not do any merging or
     * splitting, but does inform parent if changed because of this action.
     *
     * @throws IndexOutOfBoundsException maximum size has already been reached
     */
    private void rawPutChildNode(IndexNode childNode) {
        // compiler tells us we must initialize; not very smart compiler
        long oldMinObjectId = LONGNULL;
        if (getParentNodeId() != LONGNULL) {
            oldMinObjectId = getMinObjectId();
        }

        int pos = getNodeIdLoc().putKey(childNode.getMinObjectId());
        getNodeIdLoc().putNodeId(pos, childNode.getNodeId());
        childNode.setParentNode(this);
        setDirty();

        if (getParentNodeId() != LONGNULL && getMinObjectId() != oldMinObjectId) {
            IndexBranchNode p = getParentNode();
            p.childMinObjectIdChanged(this, oldMinObjectId);
            p.endInvoke();
        }
    }

    void putChildNode(IndexNode childNode) {
//if (childNode.getNodeId() == 2 || childNode.getMinObjectId() < -1000000) {
//    log.severe("putting " + childNode.getNodeId() + " into " + this);
//}
        if (log.isLoggable(Level.FINE)) log.fine("putting " + childNode.getNodeId() + " on key " + childNode.getMinObjectId() + " in " + getNodeId());
        if (!isFull()) {
            
            rawPutChildNode(childNode);
        } else {
            if (log.isLoggable(Level.FINER)) log.fine(getNodeId() + " is full");
            if (getParentNodeId() == LONGNULL) {

                // we are the root and we are full; it is time to create a
                // new root and make it our parent
                IndexBranchNode newRoot = new IndexBranchNode(getIndexManager());
                newRoot.putChildNode(this);
                getIndexManager().setRootNode(newRoot);
                newRoot.endInvoke();

                // after we have created a new root we can now simply split
            }
            split(childNode);
        }
//if (childNode.getNodeId() == 2) {
//    log.severe("ready putting " + childNode.getNodeId() + " into " + this);
//}
    }
    
    /**
     * Removes a child node from this node. Does not do any merging or
     * splitting, but does inform parent if changing because of this action.
     * Also removes itself from the tree if empty after the remove.
     *
     */
    private void rawRemoveChildNode(IndexNode childNode) {
        int pos = getNodeIdLoc().getKeyPos(childNode.getMinObjectId());
        if (pos < 0) {
            throw new OzoneInternalException("no such child node with minObjectId: " + childNode.getMinObjectId());
        }
        if (size() == 1) {
            if (getNextNodeId() != LONGNULL) {
                IndexNode n = getNextNode();
                n.setPrevNodeId(getPrevNodeId());
                n.endInvoke();
            }
            
            if (getPrevNodeId() != LONGNULL) {
                IndexNode p = getPrevNode();
                p.setNextNodeId(getNextNodeId());
                p.endInvoke();
            }
            // we only remove ourselves if we are not the root
            if (getParentNodeId() != LONGNULL) {
                IndexBranchNode p = getParentNode();
                p.removeChildNode(this);
                p.endInvoke();
                
                // removes us from the index manager cache
                setIndexManager(null);
            }
        }
        
        long oldMinObjectId = getMinObjectId();
        getNodeIdLoc().removePos(pos);
        childNode.setParentNode(null);
        setDirty();
        
        if (getParentNodeId() != LONGNULL) {
            long newMinObjectId = getMinObjectId();
            if (oldMinObjectId != newMinObjectId) {
                IndexBranchNode p = getParentNode();
                p.childMinObjectIdChanged(this, oldMinObjectId);
                p.endInvoke();
            }
        }
    }

    /**
     * @throws OzoneInternalException when given node not found
     */
    void removeChildNode(IndexNode childNode) {
//if (childNode.getNodeId() == 8) {
//    log.severe("removing childNode " + childNode + "\nfrom " + this);
//}
        if (log.isLoggable(Level.FINE)) log.fine("removing on key " + childNode.getMinObjectId() + " from " + getNodeId());

        rawRemoveChildNode(childNode);

        // remove ourselves if we have only one child and no siblings, move our
        // child over to our parent
        if (size() == 1 && getNextNodeId() == LONGNULL && getPrevNodeId() == LONGNULL) {
            long moveUpId = getNodeIdLoc().getNodeId(getNodeIdLoc().getMinPos());
            IndexNode moveUp = getIndexManager().getNode(moveUpId);
            if (getParentNodeId() == LONGNULL) {
                if (moveUp instanceof IndexLeafNode) {
                    // we do absolutely nothing here, since the indexmanager
                    // must always have a root node (branch) and (at least) one
                    // leaf node as its child
                } else {
                    if (log.isLoggable(Level.FINE)) log.fine("root node " + getNodeId() + " has one (branch) child (" + moveUp.getNodeId() + ") and no siblings, so making that new root node");
                    getIndexManager().setRootNode((IndexBranchNode) moveUp);
                    removeChildNode(moveUp);
                    
                    // removes ourselves from cache and storage
                    setIndexManager(null);
                }
            } else {
                if (log.isLoggable(Level.FINE)) log.fine("branch node " + getNodeId() + " has one child (" + moveUp.getNodeId() + ") and no siblings, so child is taking branchnodes place");
                IndexBranchNode p = getParentNode();
                
                // next statement effectively overwrites 'our' entry in the
                // parent, because our minObjId == moveUps minObjId, since
                // moveUp is our only child
                p.rawPutChildNode(moveUp);
                p.endInvoke();
                
                // removes ourselves from cache and storage
                setIndexManager(null);
            }
            moveUp.endInvoke();
        }
        
//if (childNode.getNodeId() == 8) {
//    log.severe("ready removing childNode " + childNode + "\nfrom " + this);
//}
    }
    
    protected final int size() {
        return getNodeIdLoc().size();
    }
    
    void childMinObjectIdChanged(IndexNode childNode, long childOldMinObjectId) {
//if (getNodeId() == 5) {
//    log.severe("child node changed, oldMin: " + childOldMinObjectId + ", child: " + childNode + ", parent: " + this);
//}
        if (log.isLoggable(Level.FINE)) log.fine("child changed, oldId " + childOldMinObjectId + "; node " + childNode + "\nthis: " + this);
        long oldMinObjectId = getMinObjectId();
            
        if (getNodeIdLoc().removeKey(childOldMinObjectId) < 0) {
            throw new OzoneInternalException("could not find " + childOldMinObjectId + " in " + this + "; child: " + childNode);
        }
        int pos = getNodeIdLoc().putKey(childNode.getMinObjectId());
        getNodeIdLoc().putNodeId(pos, childNode.getNodeId());

        setDirty();
        if (getMinObjectId() != oldMinObjectId && getParentNodeId() != LONGNULL) {
            IndexBranchNode p = getParentNode();
            p.childMinObjectIdChanged(this, oldMinObjectId);
            p.endInvoke();
        }
    }
    
    long getMaxObjectId() {
        long result;
        if (size() == 0) {
            result = MINOBJECTID;
        } else {
            result = getNodeIdLoc().getMaxKey();
        }
        return result;
    }
    
    long getMinObjectId() {
        long result;
        if (size() == 0) {
            result = MINOBJECTID;
        } else {
            result = getNodeIdLoc().getMinKey();
        }
        return result;
    }
    
    
    /**
     * Splits this instance into two nodes; the specified id is used to find
     * out which child nodes should remain in this instance, and which
     * should be put in the other one. Say we have a full node with sub node
     * ids [10, 20, 30, 40, 50] and we are adding 35, then we would split into
     * [10, 20, 30] and [40, 50].
     */
    private void split(IndexNode indexNode) {
        if (log.isLoggable(Level.FINE)) log.fine("split around " + indexNode.getMinObjectId() + " for indexBranchNode " + getNodeId());

        // since we are about to create a new node, we wait a little if the
        // serializer has too much still to do
        getIndexManager().checkSerializerSize();
        IndexBranchNode result = new IndexBranchNode(getIndexManager());
        if (log.isLoggable(Level.FINE)) log.fine("split created " + result.getNodeId());
        
        // Must test if new node is not full, because the maximum size may
        // change at runtime. If we don't, the new node may split itself also,
        // and since the new node does not know its parent yet we will then have
        // a problem...
        while (!result.isFull(1) && size() > 1) {
            int pos = getNodeIdLoc().getMaxPos();
            if (getNodeIdLoc().getKey(pos) < indexNode.getMaxObjectId()) {
                break;
            }
            long childNodeId = getNodeIdLoc().getNodeId(pos);
            IndexNode childNode = getIndexManager().getNode(childNodeId);
            rawRemoveChildNode(childNode);
            result.rawPutChildNode(childNode);
            childNode.endInvoke();
        }
        
        if (indexNode.getMaxObjectId() > getNodeIdLoc().getMaxKey()) {
            result.putChildNode(indexNode);
        } else {
            rawPutChildNode(indexNode);
        }
        
        // make new node known to our peers
        result.setPrevNode(this);
        if (getNextNodeId() != LONGNULL) {
            result.setNextNodeId(getNextNodeId());
            IndexNode n = getNextNode();
            n.setPrevNode(result);
            n.endInvoke();
        }
        setNextNode(result);
        
        // make new node known to our parent
        IndexBranchNode p = getParentNode();
        p.putChildNode(result);
        p.endInvoke();
        result.endInvoke();
    }
    
    public String toString() {
        return super.toString() + " " + getNodeIdLoc();
    }
    
}