Return-Path: Delivered-To: apmail-activemq-commits-archive@www.apache.org Received: (qmail 65579 invoked from network); 18 Jul 2008 15:51:26 -0000 Received: from hermes.apache.org (HELO mail.apache.org) (140.211.11.2) by minotaur.apache.org with SMTP; 18 Jul 2008 15:51:26 -0000 Received: (qmail 27547 invoked by uid 500); 18 Jul 2008 15:51:23 -0000 Delivered-To: apmail-activemq-commits-archive@activemq.apache.org Received: (qmail 27519 invoked by uid 500); 18 Jul 2008 15:51:23 -0000 Mailing-List: contact commits-help@activemq.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@activemq.apache.org Delivered-To: mailing list commits@activemq.apache.org Received: (qmail 27432 invoked by uid 99); 18 Jul 2008 15:51:23 -0000 Received: from athena.apache.org (HELO athena.apache.org) (140.211.11.136) by apache.org (qpsmtpd/0.29) with ESMTP; Fri, 18 Jul 2008 08:51:23 -0700 X-ASF-Spam-Status: No, hits=-2000.0 required=10.0 tests=ALL_TRUSTED X-Spam-Check-By: apache.org Received: from [140.211.11.4] (HELO eris.apache.org) (140.211.11.4) by apache.org (qpsmtpd/0.29) with ESMTP; Fri, 18 Jul 2008 15:50:26 +0000 Received: by eris.apache.org (Postfix, from userid 65534) id 785A12388AA2; Fri, 18 Jul 2008 08:49:58 -0700 (PDT) Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Subject: svn commit: r677944 [8/11] - in /activemq/sandbox/kahadb: ./ src/ src/main/ src/main/java/ src/main/java/org/ src/main/java/org/apache/ src/main/java/org/apache/kahadb/ src/main/java/org/apache/kahadb/impl/ src/main/java/org/apache/kahadb/impl/async/ s... Date: Fri, 18 Jul 2008 15:49:52 -0000 To: commits@activemq.apache.org From: chirino@apache.org X-Mailer: svnmailer-1.0.8 Message-Id: <20080718154958.785A12388AA2@eris.apache.org> X-Virus-Checked: Checked by ClamAV on apache.org Added: activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/xindice/Value.java URL: http://svn.apache.org/viewvc/activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/xindice/Value.java?rev=677944&view=auto ============================================================================== --- activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/xindice/Value.java (added) +++ activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/xindice/Value.java Fri Jul 18 08:49:48 2008 @@ -0,0 +1,303 @@ +/* + * 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: Value.java 594315 2007-11-12 22:10:44Z vgritsenko $ + */ + +package org.apache.kahadb.xindice; + +import java.io.ByteArrayInputStream; +import java.io.IOException; +import java.io.InputStream; +import java.io.OutputStream; +import java.io.UnsupportedEncodingException; +import java.util.Arrays; + +/** + * Value is the primary base class for all data storing objects. + * The content window of value objects are immutable, but the + * underlying byte array which was used for constructing the value might be not. + * + * @version $Revision: 594315 $, $Date: 2007-11-12 17:10:44 -0500 (Mon, 12 Nov 2007) $ + */ +public class Value implements Comparable { + + protected final byte[] data; + protected final int pos; + protected final int len; + + /** + * Usually there is no need to create a copy of the value, since it is + * an immutable object. This constructor is mainly used to create + * key objects. + * + * @param value the value object which data will be used to construct this + * value. + */ + public Value(Value value) { + this.data = value.data; + this.pos = value.pos; + this.len = value.len; + } + + public Value(byte[] data) { + this.data = data; + this.pos = 0; + this.len = data.length; + } + + public Value(byte[] data, int pos, int len) { + if (pos >= data.length || pos < 0 || pos + len > data.length) { + throw new ArrayIndexOutOfBoundsException("Value cannot be created"); + } + + this.data = data; + this.pos = pos; + this.len = len; + } + + public Value(String data) { + try { + this.data = data.getBytes("utf-8"); + this.pos = 0; + this.len = this.data.length; + } catch (UnsupportedEncodingException e) { + throw new RuntimeException("Java doesn't support UTF-8 encoding", e); + } + } + + public boolean equals(Value value) { + return len == value.len && hashCode() == value.hashCode() && compareTo(value) == 0; + } + + public int hashCode() { + // modeled after String.hashCode() + int rc = 0; + for (int i = 0; i < len; i++) { + rc = 31 * rc + data[pos + i]; + } + return rc; + } + + public final int compareTo(Value value) { + byte[] ddata = value.data; + int dpos = value.pos; + int dlen = value.len; + + int stop = len > dlen ? dlen : len; + + for (int i = 0; i < stop; i++) { + byte b1 = data[pos + i]; + byte b2 = ddata[dpos + i]; + + if (b1 != b2) { + // get unsigned value + int s1 = ((int) b1) & 0xFF; + int s2 = ((int) b2) & 0xFF; + return s1 > s2 ? (i + 1) : -(i + 1); + } + } + + if (len == dlen) { + return 0; + } else { + return len > dlen ? stop + 1 : -(stop + 1); + } + } + + public final int compareTo(Object obj) { + return compareTo((Value) obj); + } + + public boolean equals(Object obj) { + if (this == obj) { + return true; + } + if( obj == null || obj.getClass() != getClass() ) { + return false; + } + return equals((Value) obj); + } + + + /** + * getLength retrieves the length of the data being stored by the Value. + * + * @return The Value length + */ + public final int getLength() { + return len; + } + + /** + * getData retrieves a copy of the data which is being stored + * by this value as a byte array. + * + *

Data copying is performed in order to ensure immutability of the Value. + * Avoid using this method if possible. + * + * @return The data + */ + public final byte[] getData() { + byte[] b = new byte[len]; + System.arraycopy(data, pos, b, 0, len); + return b; + } + + // + // Data extraction + // + + /** + * Returns the byte at the specified index. + * + * @param index byte index + * @return the byte at the specified index. + * @throws ArrayIndexOutOfBoundsException if index is negative number or + * is not less that the length of Value data + */ + public final byte byteAt(int index) { + if (index < 0 || index >= len) { + throw new ArrayIndexOutOfBoundsException(index); + } + return data[pos + index]; + } + + /** + * Returns the short value at the specified index. + * + * @param index short index + * @return the short at the specified index. + * @throws ArrayIndexOutOfBoundsException if index is negative number or + * is not less that the length of the data array + */ + public final short shortAt(int index) { + return (short) ((data[index += pos] << 8) | data[index + 1]); + } + + /** + * Returns the int value at the specified index. + * + * @param index int index + * @return the int at the specified index. + * @throws ArrayIndexOutOfBoundsException if index is negative number or + * is not less that the length of the data array + */ + public final int intAt(int index) { + return (short) ((data[index += pos] << 24) | (data[index + 1] << 16) | (data[index + 2] << 8) | data[index + 3]); + } + + /** + * Get a value that is part of this value object. + * + * @param start beginning index + * @param len length of the new value + * @return Value object + * @throws ArrayIndexOutOfBoundsException if start index is either negative + * or isn't less then length of original Value + */ + public final Value valueAt(int start, int len) { + return new Value(data, pos + start, len); + } + + /** + * Get a key that is part of this value object. + * + * @param start beginning index + * @param len length of the new key + * @return Key object + * @throws ArrayIndexOutOfBoundsException if start index is either negative + * or isn't less then length of original Value + */ + public final Key keyAt(int start, int len) { + return new Key(data, pos + start, len); + } + + // + // I/O + // + + /** + * Return an InputStream for the value. + * + * @return An InputStream + */ + public final InputStream getInputStream() { + return new ByteArrayInputStream(data, pos, len); + } + + /** + * Stream the content of the value into an OutputStream. + * + * @param out the OutputStream + * @throws IOException if write failed + */ + public final void streamTo(OutputStream out) throws IOException { + out.write(data, pos, len); + } + + /** + * Copy contents of the value into supplied byte array. + * + * @param tdata byte array for the value + * @param tpos starting position + */ + public final void copyTo(byte[] tdata, int tpos) { + System.arraycopy(data, pos, tdata, tpos, len); + } + + /** + * Copy len bytes of value's content into supplied + * byte array. + * + * @param tdata byte array for the value + * @param tpos starting position + * @param len count of bytes to copy + */ + public final void copyTo(byte[] tdata, int tpos, int len) { + System.arraycopy(data, pos, tdata, tpos, len); + } + + // + // Comparisons + // + + public final boolean startsWith(Value value) { + if (len < value.len) { + return false; + } + + byte[] ddata = value.data; + int dpos = value.pos; + + for (int i = 0; i < value.len; i++) { + if (data[i + pos] != ddata[i + dpos]) { + return false; + } + } + + return true; + } + + + public final String toString() { + try { + return new String(data, pos, len, "utf-8"); + } catch (UnsupportedEncodingException e) { + throw new RuntimeException("Java doesn't seem to support UTF-8!", e); + } + } +} Added: activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/xindice/btree/BTree.java URL: http://svn.apache.org/viewvc/activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/xindice/btree/BTree.java?rev=677944&view=auto ============================================================================== --- activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/xindice/btree/BTree.java (added) +++ activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/xindice/btree/BTree.java Fri Jul 18 08:49:48 2008 @@ -0,0 +1,1151 @@ +/* + * 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.kahadb.xindice.btree; + +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.kahadb.xindice.FaultCodes; +import org.apache.kahadb.xindice.IndexException; +import org.apache.kahadb.xindice.Key; +import org.apache.kahadb.xindice.page.Paged; + +/** + * 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 BTreeIndex} 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. + * + *
+ * 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. + * + *
+ * Also, the Variable Magnitude attribute means that the btree attempts + * to store as many values and pointers on one page as is possible. + * + *
+ * 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. + * + *

Cache contains weak references to the BTreeNode objects, keys + * are page numbers (Long objects). Access synchronized by this map + * object itself. + * + *

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 IndexException { + if (super.open()) { + long p = fileHeader.getRootPage(); + rootInfo = new BTreeRootInfo(p); + rootNode = getBTreeNode(p, null); + return true; + } else { + return false; + } + } + + public boolean create() throws IndexException { + 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 Key[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 IndexException { + boolean closed = super.close(); + if (closed) { + synchronized (cache) { + cache.clear(); + } + } + + return closed; + } + + /** + * addKey adds a Key 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 Key to add + * @return Pointer to the value + */ + public long addKey(Key value) throws IOException, IndexException { + return getRootNode().addKey(value); + } + + /** + * addValue adds a Key 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 Key to add + * @param pointer The pointer to associate with it + * @return The previous value for the pointer (or -1) + */ + public long addValue(Key value, long pointer) throws IOException, IndexException { + return getRootNode().addValue(value, pointer); + } + + /** + * addValue adds a Key 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 Key to add + * @param pointer The pointer to associate with it + * @return The previous value for the pointer (or -1) + */ + public long addValue(BTreeRootInfo root, Key value, long pointer) throws IOException, IndexException { + return getRootNode(root).addValue(value, pointer); + } + + /** + * removeValue removes a Key from the BTree and returns the + * associated pointer for it. + * + * @param value The Key to remove + * @return The pointer that was associated with it + */ + public long removeValue(Key value) throws IOException, IndexException { + return getRootNode().removeValue(value); + } + + /** + * removeValue removes a Key from the BTree and returns the + * associated pointer for it. + * + * @param root The BTree's root information (for nested trees) + * @param value The Key to remove + * @return The pointer that was associated with it + */ + public long removeValue(BTreeRootInfo root, Key value) throws IOException, IndexException { + return getRootNode(root).removeValue(value); + } + + /** + * findValue finds a Key in the BTree and returns the associated + * pointer for it. + * + * @param value The Key to find + * @return The pointer that was associated with it + */ + public long findValue(Key value) throws IOException, IndexException { + return getRootNode().findValue(value); + } + + /** + * findValue finds a Key in the BTree and returns the associated + * pointer for it. + * + * @param root The BTree's root information (for nested trees) + * @param value The Key to find + * @return The pointer that was associated with it + */ + public long findValue(BTreeRootInfo root, Key value) throws IOException, IndexException { + 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, IndexException { +// 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, IndexException { +// 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, IndexException { + 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, IndexException { + 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 Key to create + * @return The new BTreeRootInfo instance + */ + protected final BTreeRootInfo createBTreeRoot(Key v) throws IOException, IndexException { + 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 Key to create + * @return The new BTreeRootInfo instance + */ + protected final BTreeRootInfo createBTreeRoot(BTreeRootInfo root, Key v) throws IOException, IndexException { + 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 Key to search for + * @return The new BTreeRootInfo instance + */ + protected final BTreeRootInfo findBTreeRoot(Key v) throws IOException, IndexException { + 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 Key to search for + * @return The new BTreeRootInfo instance + */ + protected final BTreeRootInfo findBTreeRoot(BTreeRootInfo root, Key v) throws IOException, IndexException { + 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, IndexException { + 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, IndexException { + 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 Key[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 Key name; + private long page; + + public BTreeRootInfo(BTreeRootInfo parent, String name, long page) { + this.parent = parent; + this.name = new Key(name); + this.page = page; + } + + public BTreeRootInfo(BTreeRootInfo parent, Key name, long page) { + this.parent = parent; + this.name = name; + this.page = page; + } + + public BTreeRootInfo(String name, long page) { + this.parent = rootInfo; + this.name = new Key(name); + this.page = page; + } + + public BTreeRootInfo(Key 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 Key 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 Key[] 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, Key[] 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(Key[] keys, long[] ptrs) { + this.values = keys; + this.ph.setValueCount((short) keys.length); + this.ptrs = ptrs; + } + + /** + * Reads node only if it is not loaded yet + */ + public synchronized void read() throws IOException { + if (!this.loaded) { + Key v = new Key(readValue(page)); + DataInputStream is = new DataInputStream(v.getInputStream()); + + // Read in the Keys + values = new Key[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 Key(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 Keys + 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 Key(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) { + Key v = readValue(ptrs[idx]); + DataInputStream dis = new DataInputStream(v.getInputStream()); + stream.read(dis); + } + } + */ + + public synchronized long removeValue(Key value) throws IOException, IndexException { + 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("Key '" + 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(Key value, long pointer) throws IOException, IndexException { + if (value == null) { + throw new IndexException(FaultCodes.DBE_CANNOT_CREATE, "Can't add a null Key"); + } + + 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) { + // Key was found... Overwrite + long oldPtr = ptrs[idx]; + ptrs[idx] = pointer; + + set(values, ptrs); + + write(); + return oldPtr; + } else { + // Key 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(Key value) throws IOException, IndexException { + if (value == null) { + throw new IndexException(FaultCodes.DBE_CANNOT_CREATE, "Can't add a null Key"); + } + + 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 { + // Key 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(Key value, long rightPointer) throws IOException, IndexException { + // 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 Key getSeparator(Key value1, Key value2) { + int idx = value1.compareTo(value2); + byte[] b = new byte[Math.abs(idx)]; + value2.copyTo(b, 0, b.length); + return new Key(b); + } + + /** + * Do we need to split this node after adding one more value? + */ + private boolean needSplit(Key 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, IndexException { + Key[] leftVals; + Key[] rightVals; + long[] leftPtrs; + long[] rightPtrs; + Key separator; + + short vc = ph.getValueCount(); + int pivot = vc / 2; + + // Split the node into two nodes + switch (ph.getStatus()) { + case BRANCH: + leftVals = new Key[pivot]; + leftPtrs = new long[leftVals.length + 1]; + rightVals = new Key[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 Key[pivot]; + leftPtrs = new long[leftVals.length]; + rightVals = new Key[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 Key[] { + 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(Key value) throws IOException, IndexException { + if (value == null) { + throw new BTreeNotFoundException("Can't search on null Key"); + } + + 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("Key '" + 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, IndexException { +// if (query != null && query.getOperator() != IndexQuery.ANY) { +// Key[] 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/kahadb/src/main/java/org/apache/kahadb/xindice/btree/BTreeCallback.java URL: http://svn.apache.org/viewvc/activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/xindice/btree/BTreeCallback.java?rev=677944&view=auto ============================================================================== --- activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/xindice/btree/BTreeCallback.java (added) +++ activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/xindice/btree/BTreeCallback.java Fri Jul 18 08:49:48 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.kahadb.xindice.btree; + +import org.apache.kahadb.xindice.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/kahadb/src/main/java/org/apache/kahadb/xindice/btree/BTreeCorruptException.java URL: http://svn.apache.org/viewvc/activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/xindice/btree/BTreeCorruptException.java?rev=677944&view=auto ============================================================================== --- activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/xindice/btree/BTreeCorruptException.java (added) +++ activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/xindice/btree/BTreeCorruptException.java Fri Jul 18 08:49:48 2008 @@ -0,0 +1,44 @@ +/* + * 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.kahadb.xindice.btree; + +import org.apache.kahadb.xindice.FaultCodes; +import org.apache.kahadb.xindice.IndexException; + + +/** + * 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 IndexException { + 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/kahadb/src/main/java/org/apache/kahadb/xindice/btree/BTreeIndex.java URL: http://svn.apache.org/viewvc/activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/xindice/btree/BTreeIndex.java?rev=677944&view=auto ============================================================================== --- activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/xindice/btree/BTreeIndex.java (added) +++ activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/xindice/btree/BTreeIndex.java Fri Jul 18 08:49:48 2008 @@ -0,0 +1,327 @@ +/* + * 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.kahadb.xindice.btree; + +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.Iterator; +import java.util.List; + +import org.apache.commons.logging.Log; +import org.apache.commons.logging.LogFactory; +import org.apache.kahadb.xindice.FaultCodes; +import org.apache.kahadb.xindice.Index; +import org.apache.kahadb.xindice.IndexException; +import org.apache.kahadb.xindice.Key; +import org.apache.kahadb.xindice.Record; +import org.apache.kahadb.xindice.RecordSet; +import org.apache.kahadb.xindice.Value; + +/** + * BTreeFiler is a Filer implementation based on the BTree class. + * + *
+ * BTreeFiler has folowing configuration attributes: + *

    + *
  • pagesize: 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.
    • + *
  • pagecount: Number of pages filer will be created + * with.
    • + *
  • maxkeysize: Maximum allowed size of the key. + * Default maximum key size is 256 bytes.
    • + *
  • max-descriptors: 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).
    • + *
+ * + * @version $Revision: 541516 $, $Date: 2007-05-24 22:46:51 -0400 (Thu, 24 May 2007) $ + */ +public class BTreeIndex extends BTree + implements Index { + + private static final Log log = LogFactory.getLog(BTreeIndex.class); + + /** + * Record page status + */ + protected static final byte RECORD = 20; + + + private BTreeFilerHeader fileHeader; + + + public BTreeIndex() { + 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 IndexException { + return readRecord(key, false); + } + + public Record readRecord(Key key, boolean metaOnly) throws IndexException { + 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(); + return new Record(key, v); + } catch (BTreeNotFoundException e) { + if (log.isDebugEnabled()) { + log.debug("Record '" + key + "' not found: " + e); + } + } catch (IOException e) { + throw new IndexException(FaultCodes.DBE_CANNOT_READ, + "Can't read record '" + key + "': " + e.getMessage(), e); + } + return null; + } + + public Record writeRecord(Key key, Value value) throws IndexException { + if (key == null || key.getLength() == 0) { + throw new IndexException(FaultCodes.DBE_CANNOT_CREATE, "Invalid key: null or empty"); + } + if (value == null) { + throw new IndexException(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(); + + return new Record(key, value); + + } catch (IOException e) { + // FIXME: cleanup? + throw new IndexException(FaultCodes.DBE_CANNOT_CREATE, + "Can't write record '" + key + "': " + e.getMessage(), e); + } + } + + public boolean deleteRecord(Key key) throws IndexException { + 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 IndexException(FaultCodes.DBE_CANNOT_DROP, + "Can't delete record '" + key + "': " + e.getMessage(), e); + } + + return false; + } + + public long getRecordCount() throws IndexException { + checkOpened(); + return fileHeader.getRecordCount(); + } + + public RecordSet getRecordSet() throws IndexException { + checkOpened(); + return new BTreeFilerRecordSet(); + } + + /** + * BTreeFilerRecordSet + */ + private class BTreeFilerRecordSet implements RecordSet, BTreeCallback { + private List keys = new ArrayList(); + private Iterator iter; + + public BTreeFilerRecordSet() throws IndexException { + try { + iterate(this); + iter = keys.iterator(); + } catch (IOException e) { + throw new IndexException(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 IndexException { + return readRecord((Key) iter.next(), false); + } + + public synchronized Value getNextValue() throws IndexException { + 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/kahadb/src/main/java/org/apache/kahadb/xindice/btree/BTreeNotFoundException.java URL: http://svn.apache.org/viewvc/activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/xindice/btree/BTreeNotFoundException.java?rev=677944&view=auto ============================================================================== --- activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/xindice/btree/BTreeNotFoundException.java (added) +++ activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/xindice/btree/BTreeNotFoundException.java Fri Jul 18 08:49:48 2008 @@ -0,0 +1,44 @@ +/* + * 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.kahadb.xindice.btree; + +import org.apache.kahadb.xindice.FaultCodes; +import org.apache.kahadb.xindice.IndexException; + + +/** + * 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 IndexException { + 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/kahadb/src/main/java/org/apache/kahadb/xindice/fs/FileCache.java URL: http://svn.apache.org/viewvc/activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/xindice/fs/FileCache.java?rev=677944&view=auto ============================================================================== --- activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/xindice/fs/FileCache.java (added) +++ activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/xindice/fs/FileCache.java Fri Jul 18 08:49:48 2008 @@ -0,0 +1,100 @@ +/* + * 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: FileCache.java 541508 2007-05-25 01:54:12Z vgritsenko $ + */ + +package org.apache.kahadb.xindice.fs; + +import java.io.File; +import java.io.FileInputStream; +import java.io.IOException; +import java.util.Map; +import java.util.WeakHashMap; + +/** + * FileCache caches the content of files in memory. + * + * @version $Revision: 541508 $, $Date: 2007-05-24 21:54:12 -0400 (Thu, 24 May 2007) $ + */ +public class FileCache { + + /** + * Caches FileCacheInfo objects. Keys are File objects. + */ + private final Map cache = new WeakHashMap(); + + public FileCache() { + } + + public final boolean isInCache(File file) { + return (cache.get(file) != null); + } + + public final boolean isInCache(String name) { + return (cache.get(new File(name)) != null); + } + + public final boolean isModified(String name) { + return isModified(new File(name)); + } + + public final boolean isModified(File file) { + FileCacheInfo finfo = (FileCacheInfo) cache.get(file); + return !file.exists() + || finfo == null + || (file.lastModified() != finfo.lastModified); + } + + public final byte[] getFile(String name) throws IOException { + return getFile(new File(name)); + } + + public final byte[] getFile(File file) throws IOException { + if (!file.exists()) { + return null; + } + + FileCacheInfo finfo = (FileCacheInfo) cache.get(file); + long lastmod = file.lastModified(); + if (finfo == null || finfo.lastModified != lastmod) { + FileInputStream fis = new FileInputStream(file); + byte[] content = new byte[fis.available()]; + fis.read(content); + fis.close(); + finfo = new FileCacheInfo(file, lastmod, content); + cache.put(file, finfo); + return content; + } else { + return finfo.content; + } + } + + /** + * FileCacheInfo + */ + private class FileCacheInfo { + public File file; + public long lastModified = 0; + public byte[] content; + + public FileCacheInfo(File file, long lastModified, byte[] content) { + this.file = file; + this.lastModified = lastModified; + this.content = content; + } + } +} Added: activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/xindice/fs/FileSystemIndex.java URL: http://svn.apache.org/viewvc/activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/xindice/fs/FileSystemIndex.java?rev=677944&view=auto ============================================================================== --- activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/xindice/fs/FileSystemIndex.java (added) +++ activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/xindice/fs/FileSystemIndex.java Fri Jul 18 08:49:48 2008 @@ -0,0 +1,309 @@ +/* + * 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: FSIndex.java 541516 2007-05-25 02:46:51Z vgritsenko $ + */ + +package org.apache.kahadb.xindice.fs; + +import java.io.File; +import java.io.FileFilter; +import java.io.FileOutputStream; +import java.io.IOException; +import java.util.HashSet; +import java.util.Set; +import java.util.StringTokenizer; + +import org.apache.kahadb.xindice.FaultCodes; +import org.apache.kahadb.xindice.Index; +import org.apache.kahadb.xindice.IndexException; +import org.apache.kahadb.xindice.Key; +import org.apache.kahadb.xindice.Record; +import org.apache.kahadb.xindice.RecordSet; +import org.apache.kahadb.xindice.Value; + +/** + * FSIndex 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 FileSystemIndex implements Index { + + 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 extensionSet; + private String extensions; + + private File dir; + private boolean opened; + private boolean readOnly; + + + public FileSystemIndex() { + } + + public String getName() { + return "FSIndex"; + } + + public void setLocation(File root, String location) { + } + + private void checkOpened() throws IndexException { + if (!opened) { + throw new IndexException(FaultCodes.COL_COLLECTION_CLOSED, + "Index is closed"); + } + } + + private void checkReadOnly() throws IndexException { + if (readOnly) { + throw new IndexException(FaultCodes.COL_COLLECTION_READ_ONLY, + "Index 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 IndexException { + return readRecord(key, false); + } + + public Record readRecord(Key key, boolean metaOnly) throws IndexException { + 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); + + if (metaOnly && file.exists()) { + return new Record(key, null); + } else { + byte[] valueData = cache.getFile(file); + if (valueData != null) { + return new Record(key, new Value(valueData)); + } + } + } catch (IOException e) { + throw new IndexException(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 IndexException { + if (key == null || key.getLength() == 0) { + throw new IndexException(FaultCodes.DBE_CANNOT_CREATE, "Invalid key: '" + key + "'"); + } + if (value == null) { + throw new IndexException(FaultCodes.DBE_CANNOT_CREATE, "Invalid null value"); + } + + checkOpened(); + checkReadOnly(); + + String fname = key.toString(); + if (!isExtensionValid(fname)) { + throw new IndexException(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(); + return new Record(key, value); + } catch (IOException e) { + throw new IndexException(FaultCodes.DBE_CANNOT_CREATE, + "Can't write record '" + key + "': " + e.getMessage(), e); + } finally { + locks.releaseExclusiveLock(file); + } + } + + public boolean deleteRecord(Key key) throws IndexException { + 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 IndexException { + 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 IndexException { + 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 IndexException { + File file = files[pos++]; + return readRecord(new Key(file.getName()), false); + } + + public synchronized Value getNextValue() throws IndexException { + 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 getExtensionSet() { + return extensionSet; + } + + public void setExtensionSet(Set 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()); + } + } + } +}