activemq-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From chir...@apache.org
Subject svn commit: r677302 [2/4] - in /activemq/sandbox/xindice-stripped: ./ src/ src/main/ src/main/java/ src/main/java/org/ src/main/java/org/apache/ src/main/java/org/apache/xindice/ src/main/java/org/apache/xindice/core/ src/main/java/org/apache/xindice/c...
Date Wed, 16 Jul 2008 15:18:22 GMT
Added: activemq/sandbox/xindice-stripped/src/main/java/org/apache/xindice/core/filer/BTree.java
URL: http://svn.apache.org/viewvc/activemq/sandbox/xindice-stripped/src/main/java/org/apache/xindice/core/filer/BTree.java?rev=677302&view=auto
==============================================================================
--- activemq/sandbox/xindice-stripped/src/main/java/org/apache/xindice/core/filer/BTree.java (added)
+++ activemq/sandbox/xindice-stripped/src/main/java/org/apache/xindice/core/filer/BTree.java Wed Jul 16 08:18:20 2008
@@ -0,0 +1,1150 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ *
+ * $Id: BTree.java 541508 2007-05-25 01:54:12Z vgritsenko $
+ */
+
+package org.apache.xindice.core.filer;
+
+import java.io.ByteArrayOutputStream;
+import java.io.DataInput;
+import java.io.DataInputStream;
+import java.io.DataOutput;
+import java.io.DataOutputStream;
+import java.io.File;
+import java.io.IOException;
+import java.io.RandomAccessFile;
+import java.lang.ref.WeakReference;
+import java.util.Arrays;
+import java.util.Map;
+import java.util.WeakHashMap;
+
+import org.apache.commons.logging.Log;
+import org.apache.commons.logging.LogFactory;
+import org.apache.xindice.core.DBException;
+import org.apache.xindice.core.FaultCodes;
+import org.apache.xindice.core.data.Value;
+
+/**
+ * BTree represents a Variable Magnitude Simple-Prefix B+Tree File.
+ * A BTree is a bit flexible in that it can be used for set or
+ * map-based indexing. {@link BTreeFiler} uses the BTree as a set for
+ * producing RecordSet entries. The Indexers use BTree as a map for
+ * indexing entity and attribute values in Documents.
+ *
+ * <br>
+ * For those who don't know how a Simple-Prefix B+Tree works, the primary
+ * distinction is that instead of promoting actual keys to branch pages,
+ * when leaves are split, a shortest-possible separator is generated at
+ * the pivot.  That separator is what is promoted to the parent branch
+ * (and continuing up the list).  As a result, actual keys and pointers
+ * can only be found at the leaf level.  This also affords the index the
+ * ability to ignore costly merging and redistribution of pages when
+ * deletions occur.  Deletions only affect leaf pages in this
+ * implementation, and so it is entirely possible for a leaf page to be
+ * completely empty after all of its keys have been removed.
+ *
+ * <br>
+ * Also, the Variable Magnitude attribute means that the btree attempts
+ * to store as many values and pointers on one page as is possible.
+ *
+ * <br>
+ * This implementation supports the notion of nested roots. This means
+ * that you can create a btree where the pointers actually point to the
+ * root of a separate btree being managed in the same file.
+ *
+ * @version $Revision: 541508 $, $Date: 2007-05-24 21:54:12 -0400 (Thu, 24 May 2007) $
+ */
+public class BTree extends Paged {
+
+    private static final Log log = LogFactory.getLog(BTree.class);
+
+    protected static final byte LEAF   = 1;
+    protected static final byte BRANCH = 2;
+    protected static final byte STREAM = 3;
+
+    /**
+     * Identity map of the recently used tree nodes to ensure that same
+     * node is present in the memory once and only once.
+     *
+     * <p>Cache contains weak references to the BTreeNode objects, keys
+     * are page numbers (Long objects). Access synchronized by this map
+     * object itself.
+     *
+     * <p>This identity map can be made into cache to store nodes for
+     * extended time periods, but that might not be necessary since
+     * documents are cached on the Collection level.
+     */
+    private final Map cache = new WeakHashMap();
+
+    private BTreeFileHeader fileHeader;
+    private BTreeRootInfo rootInfo;
+    private BTreeNode rootNode;
+
+
+    public BTree() {
+        super();
+        fileHeader = (BTreeFileHeader) getFileHeader();
+    }
+
+    public BTree(File file) {
+        this();
+        setFile(file);
+    }
+
+    public boolean open() throws DBException {
+        if (super.open()) {
+            long p = fileHeader.getRootPage();
+            rootInfo = new BTreeRootInfo(p);
+            rootNode = getBTreeNode(p, null);
+            return true;
+        } else {
+            return false;
+        }
+    }
+
+    public boolean create() throws DBException {
+        if (super.create()) {
+            try {
+                // Don't call this.open() as it will try to read rootNode from the disk
+                super.open();
+
+                Page p = getFreePage();
+                long pn = p.getPageNum();
+                fileHeader.setRootPage(pn);
+
+                rootInfo = new BTreeRootInfo(pn);
+
+                // Initialize root node
+                rootNode = new BTreeNode(p, null, new Value[0], new long[0]);
+                rootNode.ph.setStatus(LEAF);
+                rootNode.write();
+                synchronized (cache) {
+                    cache.put(rootNode.page, new WeakReference(rootNode));
+                }
+                close();
+                return true;
+            } catch (Exception e) {
+                if (log.isWarnEnabled()) {
+                    log.warn("Failed to create BTree, return false", e);
+                }
+            }
+        }
+        return false;
+    }
+
+    public synchronized boolean close() throws DBException {
+        boolean closed = super.close();
+        if (closed) {
+            synchronized (cache) {
+                cache.clear();
+            }
+        }
+
+        return closed;
+    }
+
+    /**
+     * addKey adds a Value to the BTree and associates a pointer with
+     * it.  The pointer can be used for referencing any type of data, it
+     * just so happens that Xindice uses it for referencing pages of
+     * associated data in the BTree file or other files.
+     *
+     * @param value The Value to add
+     * @return Pointer to the value
+     */
+    public long addKey(Value value) throws IOException, BTreeException {
+        return getRootNode().addKey(value);
+    }
+
+    /**
+     * addValue adds a Value to the BTree and associates a pointer with
+     * it.  The pointer can be used for referencing any type of data, it
+     * just so happens that Xindice uses it for referencing pages of
+     * associated data in the BTree file or other files.
+     *
+     * @param value The Value to add
+     * @param pointer The pointer to associate with it
+     * @return The previous value for the pointer (or -1)
+     */
+    public long addValue(Value value, long pointer) throws IOException, BTreeException {
+        return getRootNode().addValue(value, pointer);
+    }
+
+    /**
+     * addValue adds a Value to the BTree and associates a pointer with
+     * it.  The pointer can be used for referencing any type of data, it
+     * just so happens that Xindice uses it for referencing pages of
+     * associated data in the BTree file or other files.
+     *
+     * @param root The BTree's root information (for nested trees)
+     * @param value The Value to add
+     * @param pointer The pointer to associate with it
+     * @return The previous value for the pointer (or -1)
+     */
+    public long addValue(BTreeRootInfo root, Value value, long pointer) throws IOException, BTreeException {
+        return getRootNode(root).addValue(value, pointer);
+    }
+
+    /**
+     * removeValue removes a Value from the BTree and returns the
+     * associated pointer for it.
+     *
+     * @param value The Value to remove
+     * @return The pointer that was associated with it
+     */
+    public long removeValue(Value value) throws IOException, BTreeException {
+        return getRootNode().removeValue(value);
+    }
+
+    /**
+     * removeValue removes a Value from the BTree and returns the
+     * associated pointer for it.
+     *
+     * @param root The BTree's root information (for nested trees)
+     * @param value The Value to remove
+     * @return The pointer that was associated with it
+     */
+    public long removeValue(BTreeRootInfo root, Value value) throws IOException, BTreeException {
+        return getRootNode(root).removeValue(value);
+    }
+
+    /**
+     * findValue finds a Value in the BTree and returns the associated
+     * pointer for it.
+     *
+     * @param value The Value to find
+     * @return The pointer that was associated with it
+     */
+    public long findValue(Value value) throws IOException, BTreeException {
+        return getRootNode().findValue(value);
+    }
+
+    /**
+     * findValue finds a Value in the BTree and returns the associated
+     * pointer for it.
+     *
+     * @param root The BTree's root information (for nested trees)
+     * @param value The Value to find
+     * @return The pointer that was associated with it
+     */
+    public long findValue(BTreeRootInfo root, Value value) throws IOException, BTreeException {
+        return getRootNode(root).findValue(value);
+    }
+
+//    /**
+//     * query performs a query against the BTree and performs callback
+//     * operations to report the search results.
+//     *
+//     * @param query The IndexQuery to use (or null for everything)
+//     * @param callback The callback instance
+//     */
+//    public void query(IndexQuery query, BTreeCallback callback) throws IOException, BTreeException {
+//        getRootNode().query(query, callback);
+//    }
+//
+//    /**
+//     * query performs a query against the BTree and performs callback
+//     * operations to report the search results.
+//     *
+//     * @param root The BTree's root information (for nested trees)
+//     * @param query The IndexQuery to use (or null for everything)
+//     * @param callback The callback instance
+//     */
+//    public void query(BTreeRootInfo root, IndexQuery query, BTreeCallback callback) throws IOException, BTreeException {
+//        getRootNode(root).query(query, callback);
+//    }
+//    
+    
+     /**
+      * Iterate against the BTree and performs callback
+      * operations to report the search results.
+      *
+      * @param query The IndexQuery to use (or null for everything)
+      * @param callback The callback instance
+      */
+    public void iterate(BTreeCallback callback) throws IOException, BTreeException {
+        getRootNode().iterate(callback);
+    }
+
+    /**
+     * Iterates the BTree and performs callback
+     * operations to report the search results.
+     *
+     * @param root The BTree's root information (for nested trees)
+     * @param callback The callback instance
+     */
+    public void iterate(BTreeRootInfo root, BTreeCallback callback) throws IOException, BTreeException {
+        getRootNode(root).iterate(callback);
+    }
+
+    /**
+     * createBTreeRoot creates a new BTree root node in the BTree file
+     * based on the provided value for the main tree.
+     *
+     * @param v The sub-tree Value to create
+     * @return The new BTreeRootInfo instance
+     */
+    protected final BTreeRootInfo createBTreeRoot(Value v) throws IOException, BTreeException {
+        BTreeNode n = createBTreeNode(BTree.LEAF, null);
+        n.write();
+
+        long position = n.page.getPageNum();
+        addValue(v, position);
+        return new BTreeRootInfo(v, position);
+    }
+
+    /**
+     * createBTreeRoot creates a new BTree root node in the BTree file
+     * based on the provided root information, and value for the tree.
+     *
+     * @param root The BTreeRootInfo to build off of
+     * @param v The sub-tree Value to create
+     * @return The new BTreeRootInfo instance
+     */
+    protected final BTreeRootInfo createBTreeRoot(BTreeRootInfo root, Value v) throws IOException, BTreeException {
+        BTreeNode n = createBTreeNode(BTree.LEAF, null);
+        n.write();
+
+        long position = n.page.getPageNum();
+        addValue(v, position);
+        return new BTreeRootInfo(root, v, position);
+    }
+
+    /**
+     * findBTreeRoot searches for a BTreeRoot in the file and returns
+     * the BTreeRootInfo for the specified value based on the main tree.
+     *
+     * @param v The sub-tree Value to search for
+     * @return The new BTreeRootInfo instance
+     */
+    protected final BTreeRootInfo findBTreeRoot(Value v) throws IOException, BTreeException {
+        long position = findValue(v);
+        return new BTreeRootInfo(v, position);
+    }
+
+    /**
+     * findBTreeRoot searches for a BTreeRoot in the file and returns
+     * the BTreeRootInfo for the specified value based on the provided
+     * BTreeRootInfo value.
+     *
+     * @param root The BTreeRootInfo to search from
+     * @param v The sub-tree Value to search for
+     * @return The new BTreeRootInfo instance
+     */
+    protected final BTreeRootInfo findBTreeRoot(BTreeRootInfo root, Value v) throws IOException, BTreeException {
+        long position = findValue(root, v);
+        return new BTreeRootInfo(root, v, position);
+    }
+
+    /**
+     * setRootNode resets the root for the specified root object to the
+     * provided BTreeNode's page number.
+     *
+     * This method is not thread safe.
+     *
+     * @param root The root to reset
+     * @param newRoot the new root node to use
+     */
+    protected final void setRootNode(BTreeRootInfo root, BTreeNode newRoot) throws IOException, BTreeException {
+        BTreeRootInfo parent = root.getParent();
+        if (parent == null) {
+            rootNode = newRoot;
+            long p = rootNode.page.getPageNum();
+            rootInfo.setPage(p);
+            fileHeader.setRootPage(p);
+        } else {
+            long p = newRoot.page.getPageNum();
+            root.setPage(p);
+            addValue(parent, root.name, p);
+        }
+    }
+
+    /**
+     * setRootNode resets the file's root to the provided
+     * BTreeNode's page number.
+     *
+     * This method is not thread safe.
+     *
+     * @param rootNode the new root node to use
+     */
+    protected final void setRootNode(BTreeNode rootNode) throws IOException, BTreeException {
+        setRootNode(rootInfo, rootNode);
+    }
+
+    /**
+     * getRootNode retreives the BTree node for the specified
+     * root object.
+     *
+     * @param root The root object to retrieve with
+     * @return The root node
+     */
+    protected final BTreeNode getRootNode(BTreeRootInfo root) {
+        if (root.page == rootInfo.page) {
+            return rootNode;
+        } else {
+            return getBTreeNode(root.getPage(), null);
+        }
+    }
+
+    /**
+     * getRootNode retreives the BTree node for the file's root.
+     *
+     * @return The root node
+     */
+    protected final BTreeNode getRootNode() {
+        return rootNode;
+    }
+
+    private BTreeNode getBTreeNode(long page, BTreeNode parent) {
+        try {
+            BTreeNode node = null;
+            synchronized (cache) {
+                WeakReference ref = (WeakReference) cache.get(new PageKey(page));
+                if (ref != null) {
+                    node = (BTreeNode) ref.get();
+                }
+
+                if (node == null) {
+                    node = new BTreeNode(getPage(page), parent);
+                } else {
+                    node.parent = parent;
+                }
+
+                cache.put(node.page, new WeakReference(node));
+            }
+
+            node.read();
+            return node;
+        } catch (Exception e) {
+            if (log.isWarnEnabled()) {
+                log.warn("Ignored exception", e);
+            }
+            return null;
+        }
+    }
+
+    private BTreeNode createBTreeNode(byte status, BTreeNode parent) throws IOException {
+        Page p = getFreePage();
+        BTreeNode node = new BTreeNode(p, parent, new Value[0], new long[0]);
+        node.ph.setStatus(status);
+        synchronized (cache) {
+            cache.put(p, new WeakReference(node));
+        }
+        return node;
+    }
+
+    /**
+     * BTreeRootInfo
+     */
+    public final class BTreeRootInfo {
+        private final BTreeRootInfo parent;
+        private final Value name;
+        private long page;
+
+        public BTreeRootInfo(BTreeRootInfo parent, String name, long page) {
+            this.parent = parent;
+            this.name = new Value(name);
+            this.page = page;
+        }
+
+        public BTreeRootInfo(BTreeRootInfo parent, Value name, long page) {
+            this.parent = parent;
+            this.name = name;
+            this.page = page;
+        }
+
+        public BTreeRootInfo(String name, long page) {
+            this.parent = rootInfo;
+            this.name = new Value(name);
+            this.page = page;
+        }
+
+        public BTreeRootInfo(Value name, long page) {
+            this.parent = rootInfo;
+            this.name = name;
+            this.page = page;
+        }
+
+        private BTreeRootInfo(long page) {
+            parent = null;
+            name = null;
+            this.page = page;
+        }
+
+        public BTreeRootInfo getParent() {
+            return parent;
+        }
+
+        public Value getName() {
+            return name;
+        }
+
+        public synchronized long getPage() {
+            return page;
+        }
+
+        public synchronized void setPage(long page) {
+            this.page = page;
+        }
+    }
+
+    /**
+     * BTreeNode
+     */
+    private final class BTreeNode {
+        private final Page page;
+        private final BTreePageHeader ph;
+        private Value[] values;
+        private long[] ptrs;
+        private BTreeNode parent;
+        private boolean loaded;
+
+        public BTreeNode(Page page) {
+            this(page, null);
+        }
+
+        public BTreeNode(Page page, BTreeNode parent) {
+            this.page = page;
+            this.parent = parent;
+            this.ph = (BTreePageHeader) page.getPageHeader();
+        }
+
+        public BTreeNode(Page page, BTreeNode parent, Value[] values, long[] ptrs) {
+            this(page, parent);
+            set(values, ptrs);
+            this.loaded = true;
+        }
+
+        /**
+         * Sets values and pointers.
+         * Internal (to the BTreeNode) method, not synchronized.
+         */
+        private void set(Value[] values, long[] ptrs) {
+            this.values = values;
+            this.ph.setValueCount((short) values.length);
+            this.ptrs = ptrs;
+        }
+
+        /**
+         * Reads node only if it is not loaded yet
+         */
+        public synchronized void read() throws IOException {
+            if (!this.loaded) {
+                Value v = readValue(page);
+                DataInputStream is = new DataInputStream(v.getInputStream());
+
+                // Read in the Values
+                values = new Value[ph.getValueCount()];
+                for (int i = 0; i < values.length; i++) {
+                    short valSize = is.readShort();
+                    byte[] b = new byte[valSize];
+
+                    is.read(b);
+                    values[i] = new Value(b);
+                }
+
+                // Read in the pointers
+                ptrs = new long[ph.getPointerCount()];
+                for (int i = 0; i < ptrs.length; i++) {
+                    ptrs[i] = is.readLong();
+                }
+
+                this.loaded = true;
+            }
+        }
+
+        public synchronized void write() throws IOException {
+            ByteArrayOutputStream bos = new ByteArrayOutputStream(fileHeader.getWorkSize());
+            DataOutputStream os = new DataOutputStream(bos);
+
+            // Write out the Values
+            for (int i = 0; i < values.length; i++) {
+                os.writeShort(values[i].getLength());
+                values[i].streamTo(os);
+            }
+
+            // Write out the pointers
+            for (int i = 0; i < ptrs.length; i++) {
+                os.writeLong(ptrs[i]);
+            }
+
+            writeValue(page, new Value(bos.toByteArray()));
+        }
+
+        /**
+         * Internal (to the BTreeNode) method.
+         * Because this method is called only by BTreeNode itself, no synchronization done inside of this method.
+         */
+        private BTreeNode getChildNode(int idx) {
+            if (ph.getStatus() == BRANCH && idx >= 0 && idx < ptrs.length) {
+                return getBTreeNode(ptrs[idx], this);
+            } else {
+                return null;
+            }
+        }
+
+        /* Not used
+        private synchronized void getChildStream(int idx, Streamable stream) throws IOException {
+            if (ph.getStatus() == LEAF && idx >= 0 && idx < ptrs.length) {
+                Value v = readValue(ptrs[idx]);
+                DataInputStream dis = new DataInputStream(v.getInputStream());
+                stream.read(dis);
+            }
+        }
+        */
+
+        public synchronized long removeValue(Value value) throws IOException, BTreeException {
+            int idx = Arrays.binarySearch(values, value);
+
+            switch (ph.getStatus()) {
+                case BRANCH:
+                    idx = idx < 0 ? -(idx + 1) : idx + 1;
+                    return getChildNode(idx).removeValue(value);
+
+                case LEAF:
+                    if (idx < 0) {
+                        throw new BTreeNotFoundException("Value '" + value + "' doesn't exist");
+                    } else {
+                        long oldPtr = ptrs[idx];
+
+                        set(deleteArrayValue(values, idx), deleteArrayLong(ptrs, idx));
+
+                        write();
+                        return oldPtr;
+                    }
+
+                default :
+                    throw new BTreeCorruptException("Invalid page type '" + ph.getStatus() +
+                                                    "' in removeValue");
+            }
+        }
+
+        public synchronized long addValue(Value value, long pointer) throws IOException, BTreeException {
+            if (value == null) {
+                throw new BTreeException(FaultCodes.DBE_CANNOT_CREATE, "Can't add a null Value");
+            }
+
+            int idx = Arrays.binarySearch(values, value);
+
+            switch (ph.getStatus()) {
+                case BRANCH:
+                    idx = idx < 0 ? -(idx + 1) : idx + 1;
+                    return getChildNode(idx).addValue(value, pointer);
+
+                case LEAF:
+                    if (idx >= 0) {
+                        // Value was found... Overwrite
+                        long oldPtr = ptrs[idx];
+                        ptrs[idx] = pointer;
+
+                        set(values, ptrs);
+
+                        write();
+                        return oldPtr;
+                    } else {
+                        // Value was not found
+                        idx = -(idx + 1);
+
+                        // Check to see if we've exhausted the block
+                        boolean split = needSplit(value);
+
+                        set(insertArrayValue(values, value, idx), insertArrayLong(ptrs, pointer, idx));
+
+                        if (split) {
+                            split();
+                        } else {
+                            write();
+                        }
+                    }
+                    return -1;
+
+                default :
+                    throw new BTreeCorruptException("Invalid Page Type In addValue");
+            }
+        }
+
+        public synchronized long addKey(Value value) throws IOException, BTreeException {
+            if (value == null) {
+                throw new BTreeException(FaultCodes.DBE_CANNOT_CREATE, "Can't add a null Value");
+            }
+
+            int idx = Arrays.binarySearch(values, value);
+
+            switch (ph.getStatus()) {
+                case BRANCH:
+                    idx = idx < 0 ? -(idx + 1) : idx + 1;
+                    return getChildNode(idx).addKey(value);
+
+                case LEAF:
+                    if (idx >= 0) {
+                        // Key already exists
+                        return ptrs[idx];
+                    } else {
+                        // Value was not found
+                        idx = -(idx + 1);
+
+                        // Check to see if we've exhausted the block
+                        boolean split = needSplit(value);
+
+                        long pointer = getFreePage().getPageNum();
+                        set(insertArrayValue(values, value, idx), insertArrayLong(ptrs, pointer, idx));
+
+                        if (split) {
+                            split();
+                        } else {
+                            write();
+                        }
+
+                        fileHeader.incRecordCount();
+                        return pointer;
+                    }
+
+                default :
+                    throw new BTreeCorruptException("Invalid Page Type In addValue");
+            }
+        }
+
+        private synchronized void promoteValue(Value value, long rightPointer) throws IOException, BTreeException {
+            // Check to see if we've exhausted the block
+            boolean split = needSplit(value);
+
+            int idx = Arrays.binarySearch(values, value);
+            idx = idx < 0 ? -(idx + 1) : idx + 1;
+
+            set(insertArrayValue(values, value, idx), insertArrayLong(ptrs, rightPointer, idx + 1));
+
+            if (split) {
+                split();
+            } else {
+                write();
+            }
+        }
+
+        private Value getSeparator(Value value1, Value value2) {
+            int idx = value1.compareTo(value2);
+            byte[] b = new byte[Math.abs(idx)];
+            value2.copyTo(b, 0, b.length);
+            return new Value(b);
+        }
+
+        /**
+         * Do we need to split this node after adding one more value?
+         */
+        private boolean needSplit(Value value) {
+            // Do NOT split if just 4 key/values are in the node.
+            return this.values.length > 4 &&
+                   // CurrLength + one Long pointer + value length + one short
+                   this.ph.getDataLen() + 8 + value.getLength() + 2 > BTree.this.fileHeader.getWorkSize();
+        }
+
+        /**
+         * Internal to the BTreeNode method
+         */
+        private void split() throws IOException, BTreeException {
+            Value[] leftVals;
+            Value[] rightVals;
+            long[] leftPtrs;
+            long[] rightPtrs;
+            Value separator;
+
+            short vc = ph.getValueCount();
+            int pivot = vc / 2;
+
+            // Split the node into two nodes
+            switch (ph.getStatus()) {
+                case BRANCH:
+                    leftVals = new Value[pivot];
+                    leftPtrs = new long[leftVals.length + 1];
+                    rightVals = new Value[vc - (pivot + 1)];
+                    rightPtrs = new long[rightVals.length + 1];
+
+                    System.arraycopy(values, 0, leftVals, 0, leftVals.length);
+                    System.arraycopy(ptrs, 0, leftPtrs, 0, leftPtrs.length);
+                    System.arraycopy(values, leftVals.length + 1, rightVals, 0, rightVals.length);
+                    System.arraycopy(ptrs, leftPtrs.length, rightPtrs, 0, rightPtrs.length);
+
+                    separator = values[leftVals.length];
+                    break;
+
+                case LEAF:
+                    leftVals = new Value[pivot];
+                    leftPtrs = new long[leftVals.length];
+                    rightVals = new Value[vc - pivot];
+                    rightPtrs = new long[rightVals.length];
+
+                    System.arraycopy(values, 0, leftVals, 0, leftVals.length);
+                    System.arraycopy(ptrs, 0, leftPtrs, 0, leftPtrs.length);
+                    System.arraycopy(values, leftVals.length, rightVals, 0, rightVals.length);
+                    System.arraycopy(ptrs, leftPtrs.length, rightPtrs, 0, rightPtrs.length);
+
+                    separator = getSeparator(leftVals[leftVals.length - 1], rightVals[0]);
+                    break;
+
+                default :
+                    throw new BTreeCorruptException("Invalid Page Type In split");
+            }
+
+            // Promote the pivot to the parent branch
+            if (parent == null) {
+                // This can only happen if this is the root
+                BTreeNode rNode = createBTreeNode(ph.getStatus(), this);
+                rNode.set(rightVals, rightPtrs);
+
+                BTreeNode lNode = createBTreeNode(ph.getStatus(), this);
+                lNode.set(leftVals, leftPtrs);
+
+                ph.setStatus(BRANCH);
+                set(new Value[] {
+                        separator
+                    },
+                    new long[] {
+                        lNode.page.getPageNum(),
+                        rNode.page.getPageNum()
+                    });
+
+                write();
+                rNode.write();
+                lNode.write();
+            } else {
+                set(leftVals, leftPtrs);
+
+                BTreeNode rNode = createBTreeNode(ph.getStatus(), parent);
+                rNode.set(rightVals, rightPtrs);
+
+                write();
+                rNode.write();
+                parent.promoteValue(separator,
+                                    rNode.page.getPageNum());
+            }
+        }
+
+        /////////////////////////////////////////////////////////////////
+
+        public synchronized long findValue(Value value) throws IOException, BTreeException {
+            if (value == null) {
+                throw new BTreeNotFoundException("Can't search on null Value");
+            }
+
+            int idx = Arrays.binarySearch(values, value);
+
+            switch (ph.getStatus()) {
+                case BRANCH:
+                    idx = idx < 0 ? -(idx + 1) : idx + 1;
+                    return getChildNode(idx).findValue(value);
+
+                case LEAF:
+                    if (idx < 0) {
+                        throw new BTreeNotFoundException("Value '" + value + "' doesn't exist");
+                    } else {
+                        return ptrs[idx];
+                    }
+
+                default :
+                    throw new BTreeCorruptException("Invalid page type '" + ph.getStatus() +
+                                                    "' in findValue");
+            }
+        }
+
+//        // query is a BEAST of a method
+//        public synchronized void query(IndexQuery query, BTreeCallback callback) throws IOException, BTreeException {
+//            if (query != null && query.getOperator() != IndexQuery.ANY) {
+//                Value[] qvals = query.getValues();
+//                int n;
+//                int leftIdx = Arrays.binarySearch(values, qvals[0]);
+//                int rightIdx = qvals.length > 1 ? Arrays.binarySearch(values, qvals[qvals.length - 1]) : leftIdx;
+//
+//                switch (ph.getStatus()) {
+//                    case BRANCH:
+//                        leftIdx = leftIdx < 0 ? -(leftIdx + 1) : leftIdx + 1;
+//                        rightIdx = rightIdx < 0 ? -(rightIdx + 1) : rightIdx + 1;
+//
+//                        switch (query.getOperator()) {
+//                            case IndexQuery.BWX:
+//                            case IndexQuery.BW:
+//                            case IndexQuery.IN:
+//                            case IndexQuery.SW:
+//                                // TODO: Can leftIdx be less than 0 here?
+//                                if (leftIdx < 0) {
+//                                    leftIdx = 0;
+//                                }
+//                                if (rightIdx > ptrs.length - 1) {
+//                                    rightIdx = ptrs.length - 1;
+//                                }
+//                                for (int i = leftIdx; i <= rightIdx; i++) {
+//                                    getChildNode(i).query(query, callback);
+//                                }
+//                                break;
+//
+//                            case IndexQuery.NBWX:
+//                            case IndexQuery.NBW:
+//                            case IndexQuery.NIN:
+//                            case IndexQuery.NSW:
+//                                if (leftIdx > ptrs.length - 1) {
+//                                    leftIdx = ptrs.length - 1;
+//                                }
+//                                for (int i = 0; i <= leftIdx; i++) {
+//                                    getChildNode(i).query(query, callback);
+//                                }
+//                                if (rightIdx < 0) {
+//                                    rightIdx = 0;
+//                                }
+//                                for (int i = rightIdx; i < ptrs.length; i++) {
+//                                    getChildNode(i).query(query, callback);
+//                                }
+//                                break;
+//
+//                            case IndexQuery.EQ:
+//                                getChildNode(leftIdx).query(query, callback);
+//                                break;
+//
+//                            case IndexQuery.LT:
+//                            case IndexQuery.LEQ:
+//                                if (leftIdx > ptrs.length - 1) {
+//                                    leftIdx = ptrs.length - 1;
+//                                }
+//                                for (int i = 0; i <= leftIdx; i++) {
+//                                    getChildNode(i).query(query, callback);
+//                                }
+//                                break;
+//
+//                            case IndexQuery.GT:
+//                            case IndexQuery.GEQ:
+//                                if (rightIdx < 0) {
+//                                    rightIdx = 0;
+//                                }
+//                                for (int i = rightIdx; i < ptrs.length; i++) {
+//                                    getChildNode(i).query(query, callback);
+//                                }
+//                                break;
+//
+//                            case IndexQuery.NEQ:
+//                            default :
+//                                for (int i = 0; i < ptrs.length; i++) {
+//                                    getChildNode(i).query(query, callback);
+//                                }
+//                                break;
+//                        }
+//                        break;
+//
+//                    case LEAF:
+//                        switch (query.getOperator()) {
+//                            case IndexQuery.EQ:
+//                                if (leftIdx >= 0) {
+//                                    callback.indexInfo(values[leftIdx], ptrs[leftIdx]);
+//                                }
+//                                break;
+//
+//                            case IndexQuery.NEQ:
+//                                for (int i = 0; i < ptrs.length; i++) {
+//                                    if (i != leftIdx) {
+//                                        callback.indexInfo(values[i], ptrs[i]);
+//                                    }
+//                                }
+//                                break;
+//
+//                            case IndexQuery.BWX:
+//                            case IndexQuery.BW:
+//                            case IndexQuery.SW:
+//                            case IndexQuery.IN:
+//                                if (leftIdx < 0) {
+//                                    leftIdx = -(leftIdx + 1);
+//                                }
+//                                if (rightIdx < 0) {
+//                                    rightIdx = -(rightIdx + 1);
+//                                }
+//                                n = Math.min(rightIdx + 1, ptrs.length);
+//                                for (int i = leftIdx; i < n; i++){
+//                                    if (query.testValue(values[i])) {
+//                                        callback.indexInfo(values[i], ptrs[i]);
+//                                    }
+//                                }
+//                                break;
+//
+//                            case IndexQuery.NBWX:
+//                            case IndexQuery.NBW:
+//                            case IndexQuery.NSW:
+//                                // FIXME: Looks like operators are not used now. Need query optimizer?
+//                                if (leftIdx < 0) {
+//                                    leftIdx = -(leftIdx + 1);
+//                                }
+//                                if (rightIdx < 0) {
+//                                    rightIdx = -(rightIdx + 1);
+//                                }
+//                                for (int i = 0; i < ptrs.length; i++) {
+//                                    if ((i <= leftIdx || i >= rightIdx) && query.testValue(values[i])) {
+//                                        callback.indexInfo(values[i], ptrs[i]);
+//                                    }
+//                                }
+//                                break;
+//
+//                            case IndexQuery.LT:
+//                            case IndexQuery.LEQ:
+//                                if (leftIdx < 0) {
+//                                    leftIdx = -(leftIdx + 1);
+//                                }
+//                                n = Math.min(leftIdx + 1, ptrs.length);
+//                                for (int i = 0; i < n; i++) {
+//                                    if (query.testValue(values[i])) {
+//                                        callback.indexInfo(values[i], ptrs[i]);
+//                                    }
+//                                }
+//                                break;
+//
+//                            case IndexQuery.GT:
+//                            case IndexQuery.GEQ:
+//                                if (rightIdx < 0) {
+//                                    rightIdx = -(rightIdx + 1);
+//                                }
+//                                for (int i = rightIdx; i < ptrs.length; i++) {
+//                                    if (query.testValue(values[i])) {
+//                                        callback.indexInfo(values[i], ptrs[i]);
+//                                    }
+//                                }
+//                                break;
+//
+//                            case IndexQuery.NIN:
+//                            default :
+//                                for (int i = 0; i < ptrs.length; i++) {
+//                                    if (query.testValue(values[i])) {
+//                                        callback.indexInfo(values[i], ptrs[i]);
+//                                    }
+//                                }
+//                                break;
+//                        }
+//                        break;
+//
+//                    default :
+//                        throw new BTreeCorruptException("Invalid Page Type In query");
+//                }
+//
+//            } else {
+//                // No Query - Just Walk The Tree
+//                iterate(callback);
+//            }
+//        }
+
+        private void iterate(BTreeCallback callback) throws BTreeCorruptException {
+            switch (ph.getStatus()) {
+                case BRANCH:
+                    for (int i = 0; i < ptrs.length; i++) {
+                        getChildNode(i).iterate(callback);
+                    }
+                    break;
+
+                case LEAF:
+                    for (int i = 0; i < values.length; i++) {
+                        callback.indexInfo(values[i], ptrs[i]);
+                    }
+                    break;
+
+                default :
+                    throw new BTreeCorruptException("Invalid Page Type In query");
+            }
+        }
+    }
+
+    ////////////////////////////////////////////////////////////////////
+
+    protected FileHeader createFileHeader() {
+        return new BTreeFileHeader();
+    }
+
+    protected PageHeader createPageHeader() {
+        return new BTreePageHeader();
+    }
+
+    /**
+     * BTreeFileHeader
+     */
+
+    protected class BTreeFileHeader extends FileHeader {
+        private long rootPage;
+
+        public BTreeFileHeader() {
+        }
+
+        protected synchronized void read(RandomAccessFile raf) throws IOException {
+            super.read(raf);
+            rootPage = raf.readLong();
+        }
+
+        protected synchronized void write(RandomAccessFile raf) throws IOException {
+            super.write(raf);
+            raf.writeLong(rootPage);
+        }
+
+        /** The root page of the storage tree */
+        public synchronized final void setRootPage(long rootPage) {
+            this.rootPage = rootPage;
+            setDirty();
+        }
+
+        /** The root page of the storage tree */
+        public synchronized final long getRootPage() {
+            return rootPage;
+        }
+    }
+
+    /**
+     * BTreePageHeader
+     */
+
+    protected class BTreePageHeader extends PageHeader {
+        private short valueCount;
+
+        public BTreePageHeader() {
+        }
+
+        public BTreePageHeader(DataInput dis) throws IOException {
+            super(dis);
+        }
+
+        public synchronized void read(DataInput dis) throws IOException {
+            super.read(dis);
+            if (getStatus() == UNUSED) {
+                return;
+            }
+
+            valueCount = dis.readShort();
+        }
+
+        public synchronized void write(DataOutput dos) throws IOException {
+            super.write(dos);
+            dos.writeShort(valueCount);
+        }
+
+        /** The number of values stored by this page */
+        public synchronized final void setValueCount(short valueCount) {
+            this.valueCount = valueCount;
+            setDirty();
+        }
+
+        /** The number of values stored by this page */
+        public synchronized final short getValueCount() {
+            return valueCount;
+        }
+
+        /** The number of pointers stored by this page */
+        public synchronized final short getPointerCount() {
+            if (getStatus() == BRANCH) {
+                return (short) (valueCount + 1);
+            } else {
+                return valueCount;
+            }
+        }
+    }
+}

Added: activemq/sandbox/xindice-stripped/src/main/java/org/apache/xindice/core/filer/BTreeCallback.java
URL: http://svn.apache.org/viewvc/activemq/sandbox/xindice-stripped/src/main/java/org/apache/xindice/core/filer/BTreeCallback.java?rev=677302&view=auto
==============================================================================
--- activemq/sandbox/xindice-stripped/src/main/java/org/apache/xindice/core/filer/BTreeCallback.java (added)
+++ activemq/sandbox/xindice-stripped/src/main/java/org/apache/xindice/core/filer/BTreeCallback.java Wed Jul 16 08:18:20 2008
@@ -0,0 +1,40 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ *
+ * $Id: BTreeCallback.java 541508 2007-05-25 01:54:12Z vgritsenko $
+ */
+
+package org.apache.xindice.core.filer;
+
+import org.apache.xindice.core.data.Value;
+
+/**
+ * BTreeCallback is a callback interface for BTree queries.
+ *
+ * @version $Revision: 541508 $, $Date: 2007-05-24 21:54:12 -0400 (Thu, 24 May 2007) $
+ */
+public interface BTreeCallback {
+
+    /**
+     * indexInfo is a callback method for index enumeration.
+     *
+     * @param value The Value being reported
+     * @param pointer The data pointer being reported
+     * @return false to cancel the enumeration
+     */
+    boolean indexInfo(Value value, long pointer);
+}
+

Added: activemq/sandbox/xindice-stripped/src/main/java/org/apache/xindice/core/filer/BTreeCorruptException.java
URL: http://svn.apache.org/viewvc/activemq/sandbox/xindice-stripped/src/main/java/org/apache/xindice/core/filer/BTreeCorruptException.java?rev=677302&view=auto
==============================================================================
--- activemq/sandbox/xindice-stripped/src/main/java/org/apache/xindice/core/filer/BTreeCorruptException.java (added)
+++ activemq/sandbox/xindice-stripped/src/main/java/org/apache/xindice/core/filer/BTreeCorruptException.java Wed Jul 16 08:18:20 2008
@@ -0,0 +1,42 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ *
+ * $Id: BTreeCorruptException.java 541508 2007-05-25 01:54:12Z vgritsenko $
+ */
+
+package org.apache.xindice.core.filer;
+
+import org.apache.xindice.core.FaultCodes;
+
+/**
+ * A BTreecorruptException is thrown by the BTree if the BTree
+ * appears to be corrupted in some way.
+ *
+ * @version $Revision: 541508 $, $Date: 2007-05-24 21:54:12 -0400 (Thu, 24 May 2007) $
+ */
+public final class BTreeCorruptException extends BTreeException {
+    public BTreeCorruptException() {
+        super(FaultCodes.IDX_CORRUPTED);
+    }
+
+    public BTreeCorruptException(String message) {
+        super(FaultCodes.IDX_CORRUPTED, message);
+    }
+
+    public BTreeCorruptException(String message, Throwable cause) {
+        super(FaultCodes.IDX_CORRUPTED, message, cause);
+    }
+}

Added: activemq/sandbox/xindice-stripped/src/main/java/org/apache/xindice/core/filer/BTreeException.java
URL: http://svn.apache.org/viewvc/activemq/sandbox/xindice-stripped/src/main/java/org/apache/xindice/core/filer/BTreeException.java?rev=677302&view=auto
==============================================================================
--- activemq/sandbox/xindice-stripped/src/main/java/org/apache/xindice/core/filer/BTreeException.java (added)
+++ activemq/sandbox/xindice-stripped/src/main/java/org/apache/xindice/core/filer/BTreeException.java Wed Jul 16 08:18:20 2008
@@ -0,0 +1,40 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ *
+ * $Id: BTreeException.java 541508 2007-05-25 01:54:12Z vgritsenko $
+ */
+
+package org.apache.xindice.core.filer;
+
+/**
+ * A BTreeException is thrown by the BTree if an exception occurs
+ * in the managing of the BTree.
+ *
+ * @version $Revision: 541508 $, $Date: 2007-05-24 21:54:12 -0400 (Thu, 24 May 2007) $
+ */
+public class BTreeException extends FilerException {
+    public BTreeException(int faultCode) {
+        super(faultCode);
+    }
+
+    public BTreeException(int faultCode, String message) {
+        super(faultCode, message);
+    }
+
+    public BTreeException(int faultCode, String message, Throwable cause) {
+        super(faultCode, message, cause);
+    }
+}

Added: activemq/sandbox/xindice-stripped/src/main/java/org/apache/xindice/core/filer/BTreeFiler.java
URL: http://svn.apache.org/viewvc/activemq/sandbox/xindice-stripped/src/main/java/org/apache/xindice/core/filer/BTreeFiler.java?rev=677302&view=auto
==============================================================================
--- activemq/sandbox/xindice-stripped/src/main/java/org/apache/xindice/core/filer/BTreeFiler.java (added)
+++ activemq/sandbox/xindice-stripped/src/main/java/org/apache/xindice/core/filer/BTreeFiler.java Wed Jul 16 08:18:20 2008
@@ -0,0 +1,335 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ *
+ * $Id: BTreeFiler.java 541516 2007-05-25 02:46:51Z vgritsenko $
+ */
+
+package org.apache.xindice.core.filer;
+
+import java.io.DataInput;
+import java.io.DataOutput;
+import java.io.File;
+import java.io.IOException;
+import java.io.RandomAccessFile;
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.Iterator;
+import java.util.List;
+
+import org.apache.commons.logging.Log;
+import org.apache.commons.logging.LogFactory;
+import org.apache.xindice.core.DBException;
+import org.apache.xindice.core.FaultCodes;
+import org.apache.xindice.core.data.Key;
+import org.apache.xindice.core.data.Record;
+import org.apache.xindice.core.data.RecordSet;
+import org.apache.xindice.core.data.Value;
+
+/**
+ * BTreeFiler is a Filer implementation based on the BTree class.
+ *
+ * <br>
+ * BTreeFiler has folowing configuration attributes:
+ * <ul>
+ * <li><strong>pagesize</strong>: Size of the page used by the filer.
+ *     Default page size is 4096 bytes. This parameter can be set only
+ *     before paged file is created. Once it is created, this parameter
+ *     can not be changed.</li>
+ * <li><strong>pagecount</strong>: Number of pages filer will be created
+ *     with.</li>
+ * <li><strong>maxkeysize</strong>: Maximum allowed size of the key.
+ *     Default maximum key size is 256 bytes.</li>
+ * <li><strong>max-descriptors</strong>: Defines maximum amount of
+ *     simultaneously opened file descriptors this paged file can have.
+ *     Several descriptors are needed to provide multithreaded access
+ *     to the underlying file. Too large number will limit amount of
+ *     collections you can open. Default value is 16
+ *     (DEFAULT_DESCRIPTORS_MAX).</li>
+ * </ul>
+ *
+ * @version $Revision: 541516 $, $Date: 2007-05-24 22:46:51 -0400 (Thu, 24 May 2007) $
+ */
+public class BTreeFiler extends BTree
+                        implements Filer {
+
+    private static final Log log = LogFactory.getLog(BTreeFiler.class);
+
+    /**
+     * Record page status
+     */
+    protected static final byte RECORD = 20;
+
+
+    private BTreeFilerHeader fileHeader;
+
+
+    public BTreeFiler() {
+        super();
+        fileHeader = (BTreeFilerHeader) getFileHeader();
+    }
+
+    public void setLocation(File root, String location) {
+        setFile(new File(root, location + ".tbl"));
+    }
+
+    public String getName() {
+        return "BTreeFiler";
+    }
+
+    public Record readRecord(Key key) throws DBException {
+        return readRecord(key, false);
+    }
+
+    public Record readRecord(Key key, boolean metaOnly) throws DBException {
+        if (key == null || key.getLength() == 0) {
+            return null;
+        }
+
+        checkOpened();
+        try {
+            long pos = findValue(key);
+            Page startPage = getPage(pos);
+            Value v = metaOnly ? null : readValue(startPage);
+            BTreeFilerPageHeader sph = (BTreeFilerPageHeader) startPage.getPageHeader();
+
+            HashMap meta = new HashMap(2, 1.5F);
+            meta.put(Record.CREATED, new Long(sph.getCreated()));
+            meta.put(Record.MODIFIED, new Long(sph.getModified()));
+
+            return new Record(key, v, meta);
+        } catch (BTreeNotFoundException e) {
+            if (log.isDebugEnabled()) {
+                log.debug("Record '" + key + "' not found: " + e);
+            }
+        } catch (IOException e) {
+            throw new FilerException(FaultCodes.DBE_CANNOT_READ,
+                                     "Can't read record '" + key + "': " + e.getMessage(), e);
+        }
+        return null;
+    }
+
+    public Record writeRecord(Key key, Value value) throws DBException {
+        if (key == null || key.getLength() == 0) {
+            throw new FilerException(FaultCodes.DBE_CANNOT_CREATE, "Invalid key: null or empty");
+        }
+        if (value == null) {
+            throw new FilerException(FaultCodes.DBE_CANNOT_CREATE, "Invalid value: null");
+        }
+
+        checkOpened();
+        try {
+            long pos = addKey(key);
+            Page p = getPage(pos);
+
+            BTreeFilerPageHeader ph = (BTreeFilerPageHeader) p.getPageHeader();
+            long t = System.currentTimeMillis();
+            if (ph.getStatus() == UNUSED) {
+                ph.setCreated(t);
+            }
+            ph.setModified(t);
+            ph.setStatus(RECORD);
+
+            writeValue(p, value);
+            flush();
+
+            HashMap meta = new HashMap(3);
+            meta.put(Record.CREATED, new Long(ph.getCreated()));
+            meta.put(Record.MODIFIED, new Long(t));
+            return new Record(key, value, meta);
+
+        } catch (IOException e) {
+            // FIXME: cleanup?
+            throw new FilerException(FaultCodes.DBE_CANNOT_CREATE,
+                                     "Can't write record '" + key + "': " + e.getMessage(), e);
+        }
+    }
+
+    public boolean deleteRecord(Key key) throws DBException {
+        if (key == null || key.getLength() == 0) {
+            return false;
+        }
+
+        checkOpened();
+        try {
+            long pos = removeValue(key);
+            Page p = getPage(pos);
+            unlinkPages(p);
+
+            fileHeader.decRecordCount();
+
+            flush();
+            return true;
+        } catch (BTreeNotFoundException e) {
+            if (log.isDebugEnabled()) {
+                log.debug("Record '" + key + "' not found (" + e + ")");
+            }
+        } catch (IOException e) {
+            throw new FilerException(FaultCodes.DBE_CANNOT_DROP,
+                                     "Can't delete record '" + key + "': " + e.getMessage(), e);
+        }
+
+        return false;
+    }
+
+    public long getRecordCount() throws DBException {
+        checkOpened();
+        return fileHeader.getRecordCount();
+    }
+
+    public RecordSet getRecordSet() throws DBException {
+        checkOpened();
+        return new BTreeFilerRecordSet();
+    }
+
+    /**
+     * BTreeFilerRecordSet
+     */
+    private class BTreeFilerRecordSet implements RecordSet, BTreeCallback {
+        private List keys = new ArrayList();
+        private Iterator iter;
+
+        public BTreeFilerRecordSet() throws DBException {
+            try {
+                iterate(this);
+                iter = keys.iterator();
+            } catch (IOException e) {
+                throw new FilerException(FaultCodes.GEN_CRITICAL_ERROR,
+                                         "Error generating RecordSet", e);
+            }
+        }
+
+        public synchronized boolean indexInfo(Value value, long pointer) {
+            keys.add(new Key(value));
+            return true;
+        }
+
+        public synchronized Key getNextKey() {
+            return (Key) iter.next();
+        }
+
+        public synchronized Record getNextRecord() throws DBException {
+            return readRecord((Key) iter.next(), false);
+        }
+
+        public synchronized Value getNextValue() throws DBException {
+            return getNextRecord().getValue();
+        }
+
+        public synchronized boolean hasMoreRecords() {
+            return iter.hasNext();
+        }
+    }
+
+    ////////////////////////////////////////////////////////////////////
+
+    protected FileHeader createFileHeader() {
+        return new BTreeFilerHeader();
+    }
+
+    protected PageHeader createPageHeader() {
+        return new BTreeFilerPageHeader();
+    }
+
+    /**
+     * BTreeFilerHeader
+     */
+    private final class BTreeFilerHeader extends BTreeFileHeader {
+        private long totalBytes;
+
+        public BTreeFilerHeader() {
+        }
+
+        protected synchronized void read(RandomAccessFile raf) throws IOException {
+            super.read(raf);
+            totalBytes = raf.readLong();
+        }
+
+        protected synchronized void write(RandomAccessFile raf) throws IOException {
+            super.write(raf);
+            raf.writeLong(totalBytes);
+        }
+
+        /** The total number of bytes in use by the file */
+        public synchronized void setTotalBytes(long totalBytes) {
+            this.totalBytes = totalBytes;
+            setDirty();
+        }
+
+        /** The total number of bytes in use by the file */
+        public synchronized long getTotalBytes() {
+            return totalBytes;
+        }
+    }
+
+    /**
+     * BTreeFilerPageHeader
+     */
+    private final class BTreeFilerPageHeader extends BTreePageHeader {
+        private long created;
+        private long modified;
+
+        public BTreeFilerPageHeader() {
+        }
+
+        public BTreeFilerPageHeader(DataInput dis) throws IOException {
+            super(dis);
+        }
+
+        public synchronized void read(DataInput dis) throws IOException {
+            super.read(dis);
+
+            if (getStatus() == UNUSED) {
+                return;
+            }
+
+            created = dis.readLong();
+            modified = dis.readLong();
+        }
+
+        public synchronized void write(DataOutput dos) throws IOException {
+            super.write(dos);
+            dos.writeLong(created);
+            dos.writeLong(modified);
+        }
+
+        public synchronized void setRecordLen(int recordLen) {
+            fileHeader.setTotalBytes((fileHeader.totalBytes - getRecordLen()) + recordLen);
+            super.setRecordLen(recordLen);
+        }
+
+        /** UNIX-time when this record was created */
+        public synchronized void setCreated(long created) {
+            this.created = created;
+            setDirty();
+        }
+
+        /** UNIX-time when this record was created */
+        public synchronized long getCreated() {
+            return created;
+        }
+
+        /** UNIX-time when this record was last modified */
+        public synchronized void setModified(long modified) {
+            this.modified = modified;
+            setDirty();
+        }
+
+        /** UNIX-time when this record was last modified */
+        public synchronized long getModified() {
+            return modified;
+        }
+    }
+}

Added: activemq/sandbox/xindice-stripped/src/main/java/org/apache/xindice/core/filer/BTreeNotFoundException.java
URL: http://svn.apache.org/viewvc/activemq/sandbox/xindice-stripped/src/main/java/org/apache/xindice/core/filer/BTreeNotFoundException.java?rev=677302&view=auto
==============================================================================
--- activemq/sandbox/xindice-stripped/src/main/java/org/apache/xindice/core/filer/BTreeNotFoundException.java (added)
+++ activemq/sandbox/xindice-stripped/src/main/java/org/apache/xindice/core/filer/BTreeNotFoundException.java Wed Jul 16 08:18:20 2008
@@ -0,0 +1,42 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ *
+ * $Id: BTreeNotFoundException.java 541508 2007-05-25 01:54:12Z vgritsenko $
+ */
+
+package org.apache.xindice.core.filer;
+
+import org.apache.xindice.core.FaultCodes;
+
+/**
+ * A BTreeNotFoundException is thrown by the BTree if a Value
+ * can't be found in the BTree.
+ *
+ * @version $Revision: 541508 $, $Date: 2007-05-24 21:54:12 -0400 (Thu, 24 May 2007) $
+ */
+public final class BTreeNotFoundException extends BTreeException {
+    public BTreeNotFoundException() {
+        super(FaultCodes.IDX_VALUE_NOT_FOUND);
+    }
+
+    public BTreeNotFoundException(String message) {
+        super(FaultCodes.IDX_VALUE_NOT_FOUND, message);
+    }
+
+    public BTreeNotFoundException(String message, Throwable cause) {
+        super(FaultCodes.IDX_VALUE_NOT_FOUND, message, cause);
+    }
+}

Added: activemq/sandbox/xindice-stripped/src/main/java/org/apache/xindice/core/filer/FSFiler.java
URL: http://svn.apache.org/viewvc/activemq/sandbox/xindice-stripped/src/main/java/org/apache/xindice/core/filer/FSFiler.java?rev=677302&view=auto
==============================================================================
--- activemq/sandbox/xindice-stripped/src/main/java/org/apache/xindice/core/filer/FSFiler.java (added)
+++ activemq/sandbox/xindice-stripped/src/main/java/org/apache/xindice/core/filer/FSFiler.java Wed Jul 16 08:18:20 2008
@@ -0,0 +1,318 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ *
+ * $Id: FSFiler.java 541516 2007-05-25 02:46:51Z vgritsenko $
+ */
+
+package org.apache.xindice.core.filer;
+
+import java.io.File;
+import java.io.FileFilter;
+import java.io.FileOutputStream;
+import java.io.IOException;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Set;
+import java.util.StringTokenizer;
+
+import org.apache.xindice.core.DBException;
+import org.apache.xindice.core.FaultCodes;
+import org.apache.xindice.core.data.Key;
+import org.apache.xindice.core.data.Record;
+import org.apache.xindice.core.data.RecordSet;
+import org.apache.xindice.core.data.Value;
+import org.apache.xindice.util.FileCache;
+import org.apache.xindice.util.LockManager;
+
+/**
+ * FSFiler allows you to use existing file systems withing Xindice.
+ *
+ * @version $Revision: 541516 $, $Date: 2007-05-24 22:46:51 -0400 (Thu, 24 May 2007) $
+ */
+public final class FSFiler implements Filer {
+
+    private static final String EXT = "ext";
+    private static final String READONLY = "readonly";
+
+    private FileCache cache = new FileCache();
+    private LockManager locks = new LockManager(16);
+
+    private Set<String> extensionSet;
+    private String extensions;
+    
+    private File dir;
+    private boolean opened;
+    private boolean readOnly;
+
+
+    public FSFiler() {
+    }
+
+    public String getName() {
+        return "FSFiler";
+    }
+
+    public void setLocation(File root, String location) {
+    }
+
+    private void checkOpened() throws DBException {
+        if (!opened) {
+            throw new FilerException(FaultCodes.COL_COLLECTION_CLOSED,
+                                     "Filer is closed");
+        }
+    }
+
+    private void checkReadOnly() throws DBException {
+        if (readOnly) {
+            throw new FilerException(FaultCodes.COL_COLLECTION_READ_ONLY,
+                                     "Filer is read-only");
+        }
+    }
+
+    public boolean close() {
+        opened = false;
+        return true;
+    }
+
+    public boolean open() {
+        opened = (dir.exists() && dir.isDirectory());
+        return opened;
+    }
+
+    public boolean drop() {
+        opened = false;
+        return true;
+    }
+
+    public boolean isOpened() {
+        return opened;
+    }
+
+    public boolean exists() {
+        return dir.exists();
+    }
+
+    public boolean create() {
+        if (!dir.exists()) {
+            return dir.mkdirs();
+        } else {
+            return true;
+        }
+    }
+
+    public void flush() {
+    }
+
+    public Record readRecord(Key key) throws DBException {
+        return readRecord(key, false);
+    }
+
+    public Record readRecord(Key key, boolean metaOnly) throws DBException {
+        if (key == null || key.getLength() == 0) {
+            return null;
+        }
+
+        checkOpened();
+
+        String fname = key.toString();
+        if (!isExtensionValid(fname)) {
+            return null;
+        }
+
+        File file = new File(dir, fname);
+        try {
+            locks.acquireSharedLock(file);
+
+            HashMap meta = new HashMap(2, 1.5F);
+            meta.put(Record.MODIFIED, new Long(file.lastModified()));
+
+            if (metaOnly && file.exists()) {
+                return new Record(key, null, meta);
+            } else {
+                byte[] valueData = cache.getFile(file);
+                if (valueData != null) {
+                    return new Record(key, new Value(valueData), meta);
+                }
+            }
+        } catch (IOException e) {
+            throw new FilerException(FaultCodes.DBE_CANNOT_READ,
+                                     "Can't read record '" + key + "': " + e.getMessage(), e);
+        } finally {
+            locks.releaseSharedLock(file);
+        }
+        return null;
+    }
+
+    public Record writeRecord(Key key, Value value) throws DBException {
+        if (key == null || key.getLength() == 0) {
+            throw new FilerException(FaultCodes.DBE_CANNOT_CREATE, "Invalid key: '" + key + "'");
+        }
+        if (value == null) {
+            throw new FilerException(FaultCodes.DBE_CANNOT_CREATE, "Invalid null value");
+        }
+
+        checkOpened();
+        checkReadOnly();
+
+        String fname = key.toString();
+        if (!isExtensionValid(fname)) {
+            throw new FilerException(FaultCodes.DBE_CANNOT_CREATE, "Invalid extention");
+        }
+
+        File file = new File(dir, fname);
+        try {
+            locks.acquireExclusiveLock(file);
+            FileOutputStream fos = new FileOutputStream(file);
+            value.streamTo(fos);
+            fos.close();
+
+            HashMap meta = new HashMap(2);
+            meta.put(Record.MODIFIED, new Long(file.lastModified()));
+
+            return new Record(key, value, meta);
+        } catch (IOException e) {
+            throw new FilerException(FaultCodes.DBE_CANNOT_CREATE,
+                                     "Can't write record '" + key + "': " + e.getMessage(), e);
+        } finally {
+            locks.releaseExclusiveLock(file);
+        }
+    }
+
+    public boolean deleteRecord(Key key) throws DBException {
+        if (key == null || key.getLength() == 0) {
+            return false;
+        }
+        checkOpened();
+        checkReadOnly();
+
+        String fname = key.toString();
+        if (!isExtensionValid(fname)) {
+            return false;
+        }
+
+        File file = new File(dir, fname);
+        try {
+            locks.acquireExclusiveLock(file);
+            // TODO: Should Exception (SecurityException) be catched here or not?
+            return file.delete();
+        } finally {
+            locks.releaseExclusiveLock(file);
+        }
+    }
+
+    public long getRecordCount() throws DBException {
+        checkOpened();
+
+        File[] files = dir.listFiles(new FileFilter() {
+            public boolean accept(File file) {
+                return file.isFile() && isExtensionValid(file.getName());
+            }
+        });
+        return files.length;
+    }
+
+    public RecordSet getRecordSet() throws DBException {
+        checkOpened();
+        return new FSRecordSet();
+    }
+
+    private boolean isExtensionValid(String fname) {
+        if (extensionSet != null) {
+            int idx = fname.lastIndexOf('.');
+            if (idx == -1) {
+                return false;
+            }
+            String ext = fname.substring(idx + 1);
+            if (!extensionSet.contains(ext)) {
+                return false;
+            }
+        }
+        return true;
+    }
+
+    /**
+     * FSRecordSet
+     */
+
+    private class FSRecordSet implements RecordSet {
+        public File[] files;
+        public int pos = 0;
+
+        public FSRecordSet() {
+            files = dir.listFiles(new FileFilter() {
+                public boolean accept(File file) {
+                    return file.isFile() && isExtensionValid(file.getName());
+                }
+            });
+        }
+
+        public synchronized boolean hasMoreRecords() {
+            return pos < files.length;
+        }
+
+        public synchronized Record getNextRecord() throws DBException {
+            File file = files[pos++];
+            return readRecord(new Key(file.getName()), false);
+        }
+
+        public synchronized Value getNextValue() throws DBException {
+            return getNextRecord().getValue();
+        }
+
+        public synchronized Key getNextKey() {
+            return new Key(files[pos++].getName());
+        }
+    }
+
+    public File getDir() {
+        return dir;
+    }
+
+    public void setDir(File dir) {
+        this.dir = dir;
+    }
+
+    public boolean isReadOnly() {
+        return readOnly;
+    }
+
+    public void setReadOnly(boolean readOnly) {
+        this.readOnly = readOnly;
+    }
+
+    public Set<String> getExtensionSet() {
+        return extensionSet;
+    }
+
+    public void setExtensionSet(Set<String> extensionSet) {
+        this.extensionSet = extensionSet;
+    }
+
+    public String getExtensions() {
+        return extensions;
+    }
+
+    public void setExtensions(String extensions) {
+        this.extensions = extensions;
+        if (extensions != null && extensions.trim().length() > 0) {
+            extensionSet = new HashSet();
+            StringTokenizer st = new StringTokenizer(extensions);
+            while (st.hasMoreTokens()) {
+                extensionSet.add(st.nextToken());
+            }
+        }
+    }
+}

Added: activemq/sandbox/xindice-stripped/src/main/java/org/apache/xindice/core/filer/Filer.java
URL: http://svn.apache.org/viewvc/activemq/sandbox/xindice-stripped/src/main/java/org/apache/xindice/core/filer/Filer.java?rev=677302&view=auto
==============================================================================
--- activemq/sandbox/xindice-stripped/src/main/java/org/apache/xindice/core/filer/Filer.java (added)
+++ activemq/sandbox/xindice-stripped/src/main/java/org/apache/xindice/core/filer/Filer.java Wed Jul 16 08:18:20 2008
@@ -0,0 +1,111 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ *
+ * $Id: Filer.java 541516 2007-05-25 02:46:51Z vgritsenko $
+ */
+
+package org.apache.xindice.core.filer;
+
+import java.io.File;
+
+import org.apache.xindice.core.DBException;
+import org.apache.xindice.core.DBObject;
+import org.apache.xindice.core.data.Key;
+import org.apache.xindice.core.data.Record;
+import org.apache.xindice.core.data.RecordSet;
+import org.apache.xindice.core.data.Value;
+
+/**
+ * Filer is the low-level file management interface for Xindice.  A Filer object
+ * is implemented in order to provide a data source to the Xindice Collection
+ * class.  Filers are developed to perform transparent storage and retrieval to
+ * and from heterogenous data sources (such as FTP, HTTP, RDBMS, etc...)
+ *
+ * @version $Revision: 541516 $, $Date: 2007-05-24 22:46:51 -0400 (Thu, 24 May 2007) $
+ */
+public interface Filer extends DBObject {
+    
+    /**
+     * getName retrieves the contextually important name of the object
+     *
+     * @return The object's name
+     */
+    String getName();
+    
+    /**
+     * setLocation tells the Filer where to store its data.
+     *
+     * @param root The root under which to store data
+     * @param location The name to use for storing data
+     */
+    void setLocation(File root, String location);
+
+    /**
+     * readRecord returns a Record from the Filer based on the specified
+     * Key.
+     *
+     * @param key The Record's Key
+     * @return The returned Record
+     */
+    Record readRecord(Key key) throws DBException;
+
+    /**
+     * readRecord returns a Record from the Filer based on the specified
+     * Key containing filer meta information and value.
+     *
+     * @param key The Record's Key
+     * @param metaOnly if true, resulting record contains only meta information
+     * @return The returned Record
+     */
+    Record readRecord(Key key, boolean metaOnly) throws DBException;
+
+    /**
+     * writeRecord writes a Value to the Filer based on the specified Key.
+     *
+     * @param key The Record's Key
+     * @param value The Record's Value
+     * @return Written Record
+     */
+    Record writeRecord(Key key, Value value) throws DBException;
+
+    /**
+     * deleteRecord removes a Record from the Filer based on the
+     * specified Key.
+     *
+     * @param key The Record's Key
+     * @return Whether or not the Record was deleted
+     */
+    boolean deleteRecord(Key key) throws DBException;
+
+    /**
+     * getRecordCount returns the number of Records in the Filer.
+     *
+     * @return The Record count
+     */
+    long getRecordCount() throws DBException;
+
+    /**
+     * getRecordSet returns a RecordSet object for the current Filer.
+     *
+     * @return The Filer Enumerator
+     */
+    RecordSet getRecordSet() throws DBException;
+
+    /**
+     * flush forcefully flushes any unwritten buffers to disk.
+     */
+    void flush() throws DBException;
+}

Added: activemq/sandbox/xindice-stripped/src/main/java/org/apache/xindice/core/filer/FilerException.java
URL: http://svn.apache.org/viewvc/activemq/sandbox/xindice-stripped/src/main/java/org/apache/xindice/core/filer/FilerException.java?rev=677302&view=auto
==============================================================================
--- activemq/sandbox/xindice-stripped/src/main/java/org/apache/xindice/core/filer/FilerException.java (added)
+++ activemq/sandbox/xindice-stripped/src/main/java/org/apache/xindice/core/filer/FilerException.java Wed Jul 16 08:18:20 2008
@@ -0,0 +1,42 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ *
+ * $Id: FilerException.java 541508 2007-05-25 01:54:12Z vgritsenko $
+ */
+
+package org.apache.xindice.core.filer;
+
+import org.apache.xindice.core.DBException;
+
+/**
+ * A FilerException is thrown by a Filer if an exception occurs
+ * in the managing of the Filer.
+ *
+ * @version $Revision: 541508 $, $Date: 2007-05-24 21:54:12 -0400 (Thu, 24 May 2007) $
+ */
+public class FilerException extends DBException {
+    public FilerException(int faultCode) {
+        super(faultCode);
+    }
+
+    public FilerException(int faultCode, String message) {
+        super(faultCode, message);
+    }
+
+    public FilerException(int faultCode, String message, Throwable cause) {
+        super(faultCode, message, cause);
+    }
+}



Mime
View raw message