You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@activemq.apache.org by ch...@apache.org on 2008/07/16 17:18:22 UTC
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...
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);
+ }
+}