objectbtree.java

开源的axion的数据库代码

        int i = 0; // prepare index for loops below

        _log.debug("Create new child to take excess data");
        ObjectBTree fetus = new ObjectBTree(_idxDir, getName(), _degree, _comparator, _root, true);
        addChild(pivot + 1, fetus);

        _log.debug("Transfer (t-1) vals from existing child to new child");
        {
            List sub = child.getKeys().subList(_degree, _maxCap);
            if (_log.isDebugEnabled()) {
                _log.debug("Moving keys " + sub.toString());
            }
            fetus.getKeys().addAll(sub);
        }
        IntList sub = child.getValues().subList(_degree, _maxCap);
        fetus.getValues().addAll(sub);
        if (!child.isLeaf()) {
            _log.debug("Transfer t children from existing child to new child");
            sub = child.getChildIds().subList(_degree, _maxCap + 1);
            fetus.addChildren(sub, child.getLoadedChildren());
            for (i = _maxCap; i >= _degree; i--) {
                child.getChildIds().removeElementAt(i);
            }
        }

        _log.debug("Add new pivot key that divides children");
        Object pivotKey = child.getKeys().get(_degree - 1);
        if (_log.isDebugEnabled()) {
            _log.debug("Pivot key: " + pivotKey);
        }
        int pivotVal = child.getValues().get(_degree - 1);
        getKeys().add(pivot, pivotKey);
        getValues().add(pivot, pivotVal);

        _log.debug("Trim child to new size");
        for (i = (_maxCap - 1); i > (_degree - 2); i--) {
            child.getKeys().remove(i);
            child.getValues().removeElementAt(i);
        }
    }

    /**
     * Writes the node file out.  This is differentiated from save in
     * that it doesn't save the entire tree or the counter file.
     */
    public void write() throws IOException {
        File idxFile = getFileById(getFileId());
        if (idxFile == null) {
            throw new NullPointerException("ObjectBTree must be allocated before writing out to disk");
        }
        if (!idxFile.exists()) {
            idxFile.createNewFile();
        }
        if (_log.isDebugEnabled()) {
            _log.debug("Writing out file " + idxFile);
            _log.debug(toString());
        }
        FileOutputStream fout = new FileOutputStream(idxFile);
        ObjectOutputStream out = new ObjectOutputStream(fout);
        out.writeInt(size());
        for (int i = 0; i < size(); i++) {
            out.writeObject(getKeys().get(i));
            out.writeInt(getValues().get(i));
        }
        out.writeInt(getChildIds().size());
        for (int i = 0; i < getChildIds().size(); i++) {
            out.writeInt(getChildIds().get(i));
        }
        out.flush();
        out.close();
        fout.close();
    }

    /**
     * Saves the tree.  It saves the counter file, writes out the node
     * and then calls save recursively through the tree.
     */
    public void save(File dataDirectory) throws IOException, ClassNotFoundException {
        _idxDir = dataDirectory;
        save();
    }

    public void save() throws IOException, ClassNotFoundException {
        if (isRoot()) {
            saveIdxCtr();
        }
        write();
        for (int i = 0; i < getChildIds().size(); i++) {
            getChild(i).save(_idxDir);
        }
    }

    /**
     * Reads in the node.  This doesn't read in the entire subtree,
     * which happens incrementally as files are needed.
     */
    public void read() throws IOException, ClassNotFoundException {
        File idxFile = getFileById(getFileId());
        if (_log.isDebugEnabled()) {
            _log.debug("Reading in file " + idxFile);
        }
        FileInputStream fin = new FileInputStream(idxFile);
        ObjectInputStream in = new ObjectInputStream(fin);
        int size = in.readInt();
        for (int i = 0; i < size; i++) {
            getKeys().add(in.readObject());
            getValues().add(in.readInt());
        }
        size = in.readInt();
        for (int i = 0; i < size; i++) {
            getChildIds().add(in.readInt());
        }
        in.close();
        fin.close();
    }

    public String getChildName(int index) {
        return getChildName(getName(), index);
    }

    public String getChildName(String baseName, int index) {
        _buf.setLength(0);
        _buf.append(baseName);
        _buf.append(".");
        _buf.append(index);
        return _buf.toString();
    }

    public ObjectBTree getChild(int index) throws IOException, ClassNotFoundException {
        if (index >= getChildIds().size()) {
            throw new IOException("Node " + _fileId + " has no child at index " + index);
        } else {
            Integer fileid = new Integer(getChildIds().get(index));
            if (_loadedChildren.get(fileid) == null) {
                _loadedChildren.put(
                    fileid,
                    new ObjectBTree(
                        _idxDir,
                        getName(),
                        _degree,
                        fileid.intValue(),
                        _comparator,
                        _root));
            }
            return (ObjectBTree)_loadedChildren.get(fileid);
        }
    }

    public void addChild(ObjectBTree child) {
        getChildIds().add(child.getFileId());
        _loadedChildren.put(new Integer(child.getFileId()), child);
    }

    public void addChild(int index, ObjectBTree child) {
        getChildIds().add(index, child.getFileId());
        _loadedChildren.put(new Integer(child.getFileId()), child);
    }

    public void addChildrenFrom(ObjectBTree tree) {
        addChildren(tree.getChildIds(), tree.getLoadedChildren());
    }

    public void addChildren(IntList childIds, Map children) {
        IntIterator iter = childIds.iterator();
        while (iter.hasNext()) {
            int fileid = iter.next();
            addChild((ObjectBTree)children.get(new Integer(fileid)));
        }
    }

    public boolean isValid() throws IOException, ClassNotFoundException {
        return isValid(true);
    }

    public boolean isValid(boolean isRoot) throws IOException, ClassNotFoundException {
        //Check to make sure that the node isn't an empty branch
        if (!isLeaf() && (size() == 0)) {
            _log.warn("INVALID: " + this.toString());
            _log.warn("Node has no keys and " + getChildIds().size() + " children");
            return false;
        }
        //Check to make sure that the node has enough children
        if (!isRoot && getKeys().size() < _degree - 1) {
            _log.warn("INVALID: " + this.toString());
            _log.warn(
                "Node has only " + getKeys().size() + " keys for a degree of " + _degree);
            return false;
        }
        //Check to make sure that there aren't too many children for the number of entries
        if (!isLeaf()
            && (getChildIds().size() != getKeys().size() + 1
                || getKeys().size() != getValues().size())) {
            _log.warn("INVALID: " + this.toString());
            _log.warn("child ids: " + getChildIds().size());
            _log.warn("keys: " + getKeys().size());
            _log.warn("values: " + getValues().size());
            return false;
        }
        //Check all of the children
        if (!isLeaf()) {
            for (int i = 0; i < getChildIds().size(); i++) {
                if (!getChild(i).isValid(false)) {
                    return false;
                }
            }
        }
        return true;
    }

    public void replaceId(Object key, int oldId, int newId)
        throws ClassNotFoundException, IOException {
        int i = findNearestKeyAbove(key);
        boolean valSet = false;
        while ((i < size()) && isEqual(key, getKeys().get(i))) {
            if (!isLeaf()) {
                getChild(i).replaceId(key, oldId, newId);
            }
            if (getValue(i) == oldId) {
                setValue(i, newId);
                valSet = true;
                break;
            }
            i++;
        }
        if (!valSet && !isLeaf()) {
            getChild(i).replaceId(key, oldId, newId);
        }
    }

    public String toString() {
        StringBuffer buf = new StringBuffer();
        buf.append("{");
        buf.append(_fileId);
        buf.append(":");
        buf.append("[");
        for (int i = 0; i < size() + 1; i++) {
            if (!isLeaf()) {
                try {
                    buf.append(getChild(i).toString());
                } catch (IOException e) {
                    _log.error("Cannot retrieve child", e);
                } catch (ClassNotFoundException e) {
                    _log.error("Cannot retrieve child", e);
                }
                if (i < size()) {
                    buf.append(",");
                }
            }
            if (i < size()) {
                buf.append(getKeys().get(i));
                buf.append("/");
                buf.append(getValues().get(i));
                if (!isLeaf() || i < (size() - 1)) {
                    buf.append(",");
                }
            }
        }
        buf.append("]");
        buf.append("}");
        return buf.toString();
    }

    // private methods -------------------------------------------------------------

    private int compare(Object x, Object y) {
        return _comparator.compare(x,y);
    }

    private boolean isEqual(Object x, Object y) {
        return compare(x,y) == 0;
    }

    private boolean isNotEqual(Object x, Object y) {
        return compare(x,y) != 0;
    }

    private boolean isGreaterThan(Object x, Object y) {
        return compare(x,y) > 0;
    }

    private boolean isGreaterThanOrEqual(Object x, Object y) {
        return compare(x,y) >= 0;
    }

    private boolean isLessThan(Object x, Object y) {
        return compare(x,y) < 0;
    }

    private int findNearestKeyBelow(Object key) {
        int high = size();
        int low = 0;
        int cur = 0;

        //Short circuit
        if (size() == 0) {
            return -1;
        } else if (compare(getKeys().get(size() - 1), key) <= 0) {
            return size() - 1;
        } else if (isGreaterThan(getKeys().get(0), key)) {
            return -1;
        }

        while (low < high) {
            cur = (high + low) / 2;
            int comp = compare(key, getKeys().get(cur));
            if (0 == comp) {
                //We found it now move to the last
                for (;(cur < size()) && isEqual(key, getKeys().get(cur)); cur++);
                break;
            } else if (comp > 0) {
                if (low == cur) {
                    low++;
                } else {
                    low = cur;
                }
            } else { // comp < 0
                high = cur;
            }
        }

        //Now go to the nearest if there are multiple entries
        for (;(cur >= 0) && (isLessThan(key, getKeys().get(cur))); cur--);

        return cur;
    }

    private int findNearestKeyAbove(Object key) {
        int high = size();
        int low = 0;
        int cur = 0;

        //Short circuit
        if (size() == 0) {
            return 0;
        } else if (isLessThan(getKeys().get(size() - 1), key)) {
            return size();
        } else if (isGreaterThanOrEqual(getKeys().get(0), key)) {
            return 0;
        }

        while (low < high) {
            cur = (high + low) / 2;
            int comp = compare(key, getKeys().get(cur));
            if (high == low) {
                cur = low;
                break;
            } else if (comp == 0) {
                //We found it now move to the first
                for (;(cur > 0) && (isEqual(key, getKeys().get(cur))); cur--);
                break;
            } else if (high - low == 1) {
                cur = high;
                break;
            } else if (comp > 0) {
                if (low == cur) {
                    low++;
                } else {
                    low = cur;
                }
            } else { // comp < 0
                high = cur;
            }
        }

        //Now go to the nearest if there are multiple entries
        for (;(cur < size()) && isGreaterThan(key, getKeys().get(cur)); cur++) {};

        return cur;
    }
}