objectbtree.java

开源的axion的数据库代码

/*
 * $Id: ObjectBTree.java,v 1.14 2003/07/11 17:04:06 rwald Exp $
 * =======================================================================
 * Copyright (c) 2002-2003 Axion Development Team.  All rights reserved.
 *  
 * Redistribution and use in source and binary forms, with or without 
 * modification, are permitted provided that the following conditions 
 * are met:
 * 
 * 1. Redistributions of source code must retain the above 
 *    copyright notice, this list of conditions and the following 
 *    disclaimer. 
 *   
 * 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 names "Tigris", "Axion", nor the names of its contributors may 
 *    not be used to endorse or promote products derived from this 
 *    software without specific prior written permission. 
 *  
 * 4. Products derived from this software may not be called "Axion", nor 
 *    may "Tigris" or "Axion" appear in their names without specific prior
 *    written permission.
 *   
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 
 * "AS IS" AND ANY EXPRESS 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 THE COPYRIGHT 
 * OWNER OR 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.
 * =======================================================================
 */

package org.axiondb.util;

import java.io.File;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import org.apache.commons.collections.primitives.ArrayIntList;
import org.apache.commons.collections.primitives.IntIterator;
import org.apache.commons.collections.primitives.IntList;
import org.apache.commons.collections.primitives.IntListIterator;
import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;

// XXX FIX ME XXX: factor out a base parent class?

/**
 * A B-Tree for <code>Object</code>s, based on the implementation described
 * in "Introduction to Algorithms" by Cormen, Leiserson and Rivest (CLR).
 * 
 * (Based on BTree, written by Chuck Burdick and Dave Pekarek Krohn.)
 * 
 * @version $Revision: 1.14 $ $Date: 2003/07/11 17:04:06 $
 * @author Dave Pekarek Krohn
 */
public class ObjectBTree {
    private static Log _log = LogFactory.getLog(ObjectBTree.class);
    private int _degree = 1000;
    private int _maxCap = (2 * _degree) - 1;
    private int _counter = 0; //Only used if object is root
    private int _fileId = 0; //The id that will be used for the file that is written
    private StringBuffer _buf = new StringBuffer(30);
    private ArrayList _keys = null;
    private IntList _vals = null;
    private IntList _childIds = null;
    private Map _loadedChildren = null;
    private File _idxDir = null;
    private ObjectBTree _root = null;
    private String _idxName = null;
    private Comparator _comparator = null;

    // constructors --------------------------------------------------------------------------------

    /**
     * Create or load a new root node
     */
    public ObjectBTree(File idxDir, String idxName, int degree, Comparator comp) throws IOException, ClassNotFoundException {
        this(idxDir, idxName, degree, comp, null);
    }

    /**
     * Create or load a node
     */
    public ObjectBTree(File idxDir, String idxName, int degree, Comparator comp, ObjectBTree root) throws IOException, ClassNotFoundException {
        _idxDir = idxDir;
        _idxName = idxName;
        _degree = degree; // t
        _maxCap = (2 * _degree) - 1;
        _keys = new ArrayList(_maxCap);
        _vals = new ArrayIntList(_maxCap);
        _childIds = new ArrayIntList(_maxCap + 1);
        _loadedChildren = new HashMap();
        _comparator = comp;

        if (root != null) {
            //Child node need to allocate the next in the sequence
            _root = root;
        } else {
            //Root node need to load the counter file
            _root = this;

            boolean treeExists = (null != idxDir) && getCounterFile().exists();
            if (treeExists) {
                setCounter(0);
                setFileId(getCounter());

                loadIdxCtr();
                read();
            } else {
                allocate();
            }
        }
    }

    /**
     * Create or load a new node
     */
    public ObjectBTree(File idxDir, String idxName, int degree, Comparator comp, ObjectBTree root, boolean shouldCreate) throws IOException, ClassNotFoundException {
        this(idxDir, idxName, degree, comp, root);
        if (shouldCreate) {
            allocate();
        }
    }

    /**
     * Read in an existing node file
     */
    public ObjectBTree(File idxDir, String idxName, int degree, int fileId, Comparator comp, ObjectBTree root) throws IOException, ClassNotFoundException {
        this(idxDir, idxName, degree, comp, root);
        setFileId(fileId);
        read();
    }

    // public methods --------------------------------------------------------------------------------

    /**
     * Sets the fileId.
     */
    public void allocate() {
        setFileId(getRoot().getCounter());
        getRoot().setCounter(getFileId() + 1);
    }

    /**
     * Loads the counter file if it exists.
     * This sets the counter.  Only the root
     * should ever call this.
     */
    public void loadIdxCtr() throws IOException {
        File idxCtr = getCounterFile();
        if (!isRoot()) {
            //If this isn't the root, then there is a problem.
            _log.warn("Non root attempting to load counter file");
            return;
        }
        FileInputStream fin = null;
        ObjectInputStream in = null;
        try {
            fin = new FileInputStream(idxCtr);
            in = new ObjectInputStream(fin);
            setCounter(in.readInt());
        } catch (IOException e) {
            throw e;
        } finally {
            try {
                in.close();
            } catch (Exception e) {}
            try {
                fin.close();
            } catch (Exception e) {}
        }
    }

    /**
     * Saves out the counter file.  This should only
     * ever be called by the root.
     */
    public void saveIdxCtr() throws IOException {
        File idxCtr = getCounterFile();
        if (!isRoot()) {
            //If this isn't the root, then there is a problem.
            _log.warn("Non root attempting to save counter file");
            return;
        }
        FileOutputStream fout = null;
        ObjectOutputStream out = null;
        if (!idxCtr.exists()) {
            idxCtr.createNewFile();
        }
        // increment counter
        try {
            fout = new FileOutputStream(idxCtr);
            out = new ObjectOutputStream(fout);
            out.writeInt(getCounter());
        } catch (IOException e) {
            throw e;
        } finally {
            try {
                out.close();
            } catch (Exception e) {}
            try {
                fout.close();
            } catch (Exception e) {}
        }
    }

    public File getFileById(int fileid) {
        _buf.setLength(0);
        _buf.append(getName());
        _buf.append('.');
        _buf.append(fileid);
        return new File(_idxDir, _buf.toString());
    }

    public File getCounterFile() {
        return new File(_idxDir, _idxName + ".ctr");
    }

    public String getName() {
        return _idxName;
    }

    public ArrayList getKeys() {
        return _keys;
    }

    public void setKeys(ArrayList keys) {
        _keys = keys;
    }

    public IntList getValues() {
        return _vals;
    }

    public void setValues(IntList vals) {
        _vals = vals;
    }

    public int getValue(int index) {
        return _vals.get(index);
    }

    public void setValue(int index, int val) {
        _vals.set(index, val);
    }

    public IntList getChildIds() {
        return _childIds;
    }

    public void setChildIds(IntList childIds) {
        _childIds = childIds;
    }

    public Map getLoadedChildren() {
        return _loadedChildren;
    }

    public int getCounter() {
        if (isRoot()) {
            return _counter;
        } else {
            return getRoot().getCounter();
        }
    }

    public void setCounter(int counter) {
        if (isRoot()) {
            _counter = counter;
        } else {
            getRoot().setCounter(counter);
        }
    }

    public int getFileId() {
        return _fileId;
    }

    public void setFileId(int fileId) {
        _fileId = fileId;
    }

    public ObjectBTree getRoot() {
        return _root;
    }

    public boolean isLeaf() {
        return (getChildIds().size() == 0);
    }

    public boolean isRoot() {
        return (getRoot() == this);
    }

    public int size() {
        return getKeys().size();
    }

    public void insert(Object key, int value) throws IOException, ClassNotFoundException {
        if (size() == _maxCap) {
            // grow and rotate tree
            if (_log.isDebugEnabled()) {
                _log.debug(
                    "Node " + _fileId + " reached max capacity. Splitting and rotating.");
            }

            _log.debug("Creating new child node");
            ObjectBTree child = new ObjectBTree(_idxDir, getName(), _degree, _comparator, _root, true);

            _log.debug("Transferring all data to child");
            child.getKeys().addAll(_keys);
            child.getValues().addAll(_vals);
            if (getChildIds().size() > 0) {
                child.addChildrenFrom(this);
                _log.debug("Transferred children to child");
            }

            _log.debug("Emptying my data");
            getKeys().clear();
            getValues().clear();
            getChildIds().clear();

            _log.debug("Attaching new child");
            addChild(0, child);

            _log.debug("Subdividing child into 2 children");
            subdivideChild(0, child);
        }
        insertNotfull(key, value);
    }

    public void delete(Object key) throws IOException, ClassNotFoundException {
        //Comments refer to the cases described in CLR (19.3)
        if (_log.isDebugEnabled()) {
            _log.debug("Deleting: " + key);
        }
        if (size() <= 0) {
            _log.warn("keys: " + getKeys());
            _log.warn("values: " + getValues());
            _log.warn("childids: " + getChildIds());
            _log.warn("Tree is empty: " + this);
            return;
        }
        int i = findNearestKeyBelow(key);
        if ((i < 0 && isNotEqual(getKeys().get(i + 1), key))
            || isNotEqual(getKeys().get(i), key)) {
            _log.debug("Case 3");
            //Case 3           
            int pivotLoc = i + 1;
            if (!isLeaf() && getChild(pivotLoc).getKeys().size() < _degree) {
                if (pivotLoc > 0 && getChild(pivotLoc - 1).getKeys().size() >= _degree) {
                    _log.debug("Case 3a, left");
                    //Case 3a, borrow-left
                    borrowLeft(pivotLoc);
                    getChild(pivotLoc).delete(key);
                } else if (