Author: chirino
Date: Mon Aug 25 15:01:06 2008
New Revision: 688895
URL: http://svn.apache.org/viewvc?rev=688895&view=rev
Log:
- BTree leaf nodes are now linked for efficient iteration purposes.
- Added an iterator() method to the Index interface.
Modified:
activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/BTreeIndex.java
activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/BTreeNode.java
activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/HashIndex.java
activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/Index.java
activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/PageFile.java
activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/Transaction.java
activemq/sandbox/kahadb/src/test/java/org/apache/kahadb/page/BTreeIndexTest.java
Modified:
activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/BTreeIndex.java
URL:
http://svn.apache.org/viewvc/activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/BTreeIndex.java?rev=688895&r1=688894&r2=688895&view=diff
==============================================================================
---
activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/BTreeIndex.java
(original)
+++
activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/BTreeIndex.java
Mon Aug 25 15:01:06 2008
@@ -22,6 +22,8 @@
import java.io.PrintWriter;
import java.io.StringWriter;
import java.io.Writer;
+import java.util.Iterator;
+import java.util.Map;
import java.util.concurrent.atomic.AtomicBoolean;
import org.apache.commons.logging.Log;
@@ -31,7 +33,8 @@
/**
* BTreeIndex represents a Variable Magnitude B+Tree in a Page File.
* A BTree is a bit flexible in that it can be used for set or
- * map-based indexing.
+ * map-based indexing. Leaf nodes are linked together for faster
+ * iteration of the values.
*
* <br>
* The Variable Magnitude attribute means that the BTree attempts
@@ -59,23 +62,6 @@
private static final Log LOG = LogFactory.getLog(BTreeIndex.class);
/**
- * BTreeCallback is a callback interface for BTree queries.
- *
- * @version $Revision: 541508 $, $Date: 2007-05-24 21:54:12 -0400 (Thu, 24
May 2007) $
- */
- static public interface BTreeCallback<Key,Value> {
-
- /**
- * 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 onEntry(Key key, Value pointer);
- }
-
- /**
* Interface used to determine the simple prefix of two keys.
*
* @version $Revision: 541508 $, $Date: 2007-05-24 21:54:12 -0400 (Thu, 24
May 2007) $
@@ -204,14 +190,9 @@
}
synchronized public void clear(Transaction tx) throws IOException {
- throw new RuntimeException("Not implemented...");
+ root.clear(tx);
}
-
- synchronized public int size(Transaction tx) {
- throw new RuntimeException("Not implemented...");
- }
-
synchronized public int getMinLeafDepth(Transaction tx) throws IOException
{
return root.getMinLeafDepth(tx, 0);
}
@@ -230,6 +211,10 @@
pw.flush();
}
+ synchronized public Iterator<Map.Entry<Key,Value>> iterator(final
Transaction tx) throws IOException {
+ return root.iterator(tx);
+ }
+
synchronized Value getFirst(Transaction tx) throws IOException {
return root.getFirst(tx);
}
Modified:
activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/BTreeNode.java
URL:
http://svn.apache.org/viewvc/activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/BTreeNode.java?rev=688895&r1=688894&r2=688895&view=diff
==============================================================================
--- activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/BTreeNode.java
(original)
+++ activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/BTreeNode.java
Mon Aug 25 15:01:06 2008
@@ -21,6 +21,10 @@
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Arrays;
+import java.util.Iterator;
+import java.util.Map;
+import java.util.NoSuchElementException;
+import java.util.Map.Entry;
import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;
@@ -47,6 +51,8 @@
private Value[] values;
// nodeId pointers to children BTreeNodes. Null if this is a leaf node.
private long[] children;
+ // The next leaf node after this one. Used for fast iteration of the
entries.
+ private long next = -1;
/**
* The Marshaller is used to store and load the data in the BTreeNode into
a Page.
@@ -90,6 +96,7 @@
for (int i = 0; i < count; i++) {
index.getValueMarshaller().writePayload(node.values[i],
os);
}
+ os.writeLong(node.next);
}
}
@@ -113,6 +120,7 @@
for (int i = 0; i < count; i++) {
node.values[i] =
index.getValueMarshaller().readPayload(is);
}
+ node.next = is.readLong();
}
return node;
}
@@ -140,42 +148,53 @@
return null;
}
}
-
+
public Value remove(Transaction tx, Key key) throws IOException {
if(isBranch()) {
int idx = Arrays.binarySearch(keys, key);
idx = idx < 0 ? -(idx + 1) : idx + 1;
- BTreeNode<Key, Value> node = getChild(tx, idx);
- if( node.getPageId() == index.getRootPageId() ) {
+ BTreeNode<Key, Value> child = getChild(tx, idx);
+ if( child.getPageId() == index.getRootPageId() ) {
throw new IOException("BTree corrupted: Cylce detected.");
}
- Value rc = node.remove(tx, key);
+ Value rc = child.remove(tx, key);
- // Leaf is empty.. remove it from the branch node.
- if( node.keys.length == 0 ) {
- // If the empty node is branch, promote
- if( node.isBranch() ) {
- children[idx] = node.children[0];
+ // child node is now empty.. remove it from the branch node.
+ if( child.keys.length == 0 ) {
+
+ // If the child node is a branch, promote
+ if( child.isBranch() ) {
+ // This is cause branches are never really empty.. they
just go down to 1 child..
+ children[idx] = child.children[0];
} else {
- // If it's not the last child
+
+ // The child was a leaf. Then we need to actually remove
it from this branch node..
+
+ // We need to update the previous child's next pointer to
skip over the child being removed....
+ if( idx > 0 && children.length > 1) {
+ BTreeNode<Key, Value> previousChild = getChild(tx,
idx-1);
+ previousChild.next = child.next;
+ index.storeNode(tx, previousChild, true);
+ }
+
if( idx < children.length-1 ) {
- // Then delete it and key to the right.
+ // Delete it and key to the right.
setBranchData(arrayDelete(keys, idx),
arrayDelete(children, idx));
} else {
- // Then delete it and key to the left
+ // It was the last child.. Then delete it and key to
the left
setBranchData(arrayDelete(keys, idx-1),
arrayDelete(children, idx));
}
// If we are the root node, and only have 1 child left.
Then
// make the root be the leaf node.
if( children.length == 1 && parent==null ) {
- node = getChild(tx, 0);
- keys = node.keys;
- children = node.children;
- values = node.values;
+ child = getChild(tx, 0);
+ keys = child.keys;
+ children = child.children;
+ values = child.values;
// free up the page..
- tx.free(node.getPage());
+ tx.free(child.getPage());
}
}
@@ -332,11 +351,13 @@
} else {
BTreeNode<Key,Value> rNode = this.index.createNode(tx, parent);
-
+
if( isBranch() ) {
setBranchData(leftKeys, leftChildren);
rNode.setBranchData(rightKeys, rightChildren);
} else {
+ rNode.setNext(next);
+ next = rNode.getPageId();
setLeafData(leftKeys, leftValues);
rNode.setLeafData(rightKeys, rightValues);
}
@@ -422,6 +443,103 @@
return null;
}
}
+
+ public BTreeNode<Key,Value> getFirstLeafNode(Transaction tx) throws
IOException {
+ BTreeNode<Key, Value> node = this;
+ while( node .isBranch() ) {
+ node = node.getChild(tx, 0);
+ }
+ return node;
+ }
+
+
+ public Iterator<Map.Entry<Key,Value>> iterator(final Transaction tx)
throws IOException {
+
+ return new Iterator<Map.Entry<Key,Value>>() {
+
+ BTreeNode<Key,Value> current = getFirstLeafNode(tx);
+ int nextIndex;
+
+ Map.Entry<Key,Value> nextEntry;
+
+ synchronized private void findNextPage() {
+ if( nextEntry!=null ) {
+ return;
+ }
+
+ try {
+ while( current!=null ) {
+ if( nextIndex >= current.keys.length ) {
+ // we need to roll to the next leaf..
+ if( current.next >= 0 ) {
+ current = index.loadNode(tx, current.next,
null);
+ nextIndex=0;
+ } else {
+ break;
+ }
+ } else {
+ nextEntry = new Map.Entry<Key, Value>() {
+ private final Key key =
current.keys[nextIndex];
+ private final Value value =
current.values[nextIndex];
+
+ public Key getKey() {
+ return key;
+ }
+ public Value getValue() {
+ return value;
+ }
+ public Value setValue(Value value) {
+ throw new UnsupportedOperationException();
+ }
+ };
+ nextIndex++;
+ break;
+ }
+
+ }
+ } catch (IOException e) {
+ }
+ }
+
+ public boolean hasNext() {
+ findNextPage();
+ return nextEntry !=null;
+ }
+
+ public Entry<Key, Value> next() {
+ findNextPage();
+ if( nextEntry !=null ) {
+ Entry<Key, Value> lastEntry = nextEntry;
+ nextEntry=null;
+ return lastEntry;
+ } else {
+ throw new NoSuchElementException();
+ }
+ }
+
+ public void remove() {
+ throw new UnsupportedOperationException();
+ }
+
+ };
+ }
+
+ public void clear(Transaction tx) throws IOException {
+ if( isBranch() ) {
+ for (int i = 0; i < children.length; i++) {
+ BTreeNode<Key, Value> node = index.loadNode(tx, children[i],
this);
+ node.clear(tx);
+ tx.free(node.getPage());
+ }
+ }
+ // Reset the root node to be a leaf.
+ if( parent == null ) {
+ setLeafData(createKeyArray(0), createValueArray(0));
+ next=-1;
+ index.storeNode(tx, this, true);
+ }
+ }
+
private static <Key,Value> BTreeNode<Key, Value> getLeafNode(Transaction
tx, final BTreeNode<Key, Value> node, Key key) throws IOException {
BTreeNode<Key, Value> current = node;
@@ -461,18 +579,6 @@
}
}
- void iterate(Transaction tx, BTreeIndex.BTreeCallback<Key,Value> callback)
throws IOException {
- if(isBranch()) {
- for (int i = 0; i < children.length; i++) {
- getChild(tx, i).iterate(tx, callback);
- }
- } else {
- for (int i = 0; i < keys.length; i++) {
- callback.onEntry(keys[i], values[i]);
- }
- }
- }
-
///////////////////////////////////////////////////////////////////
// Implementation methods
///////////////////////////////////////////////////////////////////
@@ -583,6 +689,13 @@
this.page = page;
}
+ public long getNext() {
+ return next;
+ }
+
+ public void setNext(long next) {
+ this.next = next;
+ }
}
Modified:
activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/HashIndex.java
URL:
http://svn.apache.org/viewvc/activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/HashIndex.java?rev=688895&r1=688894&r2=688895&view=diff
==============================================================================
--- activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/HashIndex.java
(original)
+++ activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/HashIndex.java
Mon Aug 25 15:01:06 2008
@@ -22,7 +22,9 @@
import java.io.DataOutputStream;
import java.io.Externalizable;
import java.io.IOException;
+import java.util.Iterator;
import java.util.Map;
+import java.util.Map.Entry;
import java.util.concurrent.atomic.AtomicBoolean;
import org.apache.commons.logging.Log;
@@ -338,6 +340,11 @@
metadata.size = 0;
metadata.binsActive = 0;
}
+
+ public Iterator<Entry<Key, Value>> iterator(Transaction tx) throws
IOException, UnsupportedOperationException {
+ throw new UnsupportedOperationException();
+ }
+
/**
* @param tx
Modified:
activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/Index.java
URL:
http://svn.apache.org/viewvc/activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/Index.java?rev=688895&r1=688894&r2=688895&view=diff
==============================================================================
--- activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/Index.java
(original)
+++ activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/Index.java Mon
Aug 25 15:01:06 2008
@@ -17,6 +17,8 @@
package org.apache.kahadb.page;
import java.io.IOException;
+import java.util.Iterator;
+import java.util.Map;
import org.apache.kahadb.Marshaller;
import org.apache.kahadb.StoreEntry;
@@ -98,11 +100,14 @@
* @return true if the index is transient
*/
boolean isTransient();
-
-
+
/**
- * return the size of the index
+ * @param tx
* @return
+ * @throws IOException
+ * @trhows UnsupportedOperationException
+ * if the index does not support fast iteration of the elements.
*/
- int size(Transaction tx);
+ Iterator<Map.Entry<Key,Value>> iterator(final Transaction tx) throws
IOException, UnsupportedOperationException;
+
}
Modified:
activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/PageFile.java
URL:
http://svn.apache.org/viewvc/activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/PageFile.java?rev=688895&r1=688894&r2=688895&view=diff
==============================================================================
--- activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/PageFile.java
(original)
+++ activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/PageFile.java
Mon Aug 25 15:01:06 2008
@@ -634,14 +634,14 @@
/**
* @see org.apache.kahadb.page.Transaction#iterator(boolean)
*/
- public <T> Iterator<Page<T>> iterator(final boolean includeFreePages) {
+ public Iterator<Page> iterator(final boolean includeFreePages) {
assertLoaded();
- return new Iterator<Page<T>>() {
+ return new Iterator<Page>() {
long nextId;
- Page<T> nextPage;
- Page<T> lastPage;
+ Page nextPage;
+ Page lastPage;
private void findNextPage() {
if( !loaded.get() ) {
@@ -655,7 +655,7 @@
try {
while( nextId < PageFile.this.nextFreePageId ) {
- Page<T> page = load(nextId, null);
+ Page page = load(nextId, null);
if( includeFreePages ||
page.getType()!=Page.PAGE_FREE_TYPE ) {
nextPage = page;
@@ -673,7 +673,7 @@
return nextPage !=null;
}
- public Page<T> next() {
+ public Page next() {
findNextPage();
if( nextPage !=null ) {
lastPage = nextPage;
Modified:
activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/Transaction.java
URL:
http://svn.apache.org/viewvc/activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/Transaction.java?rev=688895&r1=688894&r2=688895&view=diff
==============================================================================
---
activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/Transaction.java
(original)
+++
activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/page/Transaction.java
Mon Aug 25 15:01:06 2008
@@ -219,7 +219,7 @@
* @throws IllegalStateException
* if the PageFile is not loaded
*/
- public <T> Iterator<Page<T>> iterator();
+ public Iterator<Page> iterator();
/**
* Allows you to iterate through all active Pages in this object. You can
optionally include free pages in the pages
Modified:
activemq/sandbox/kahadb/src/test/java/org/apache/kahadb/page/BTreeIndexTest.java
URL:
http://svn.apache.org/viewvc/activemq/sandbox/kahadb/src/test/java/org/apache/kahadb/page/BTreeIndexTest.java?rev=688895&r1=688894&r2=688895&view=diff
==============================================================================
---
activemq/sandbox/kahadb/src/test/java/org/apache/kahadb/page/BTreeIndexTest.java
(original)
+++
activemq/sandbox/kahadb/src/test/java/org/apache/kahadb/page/BTreeIndexTest.java
Mon Aug 25 15:01:06 2008
@@ -18,6 +18,8 @@
import java.io.PrintWriter;
import java.text.NumberFormat;
+import java.util.Iterator;
+import java.util.Map;
import org.apache.kahadb.LongMarshaller;
import org.apache.kahadb.StringMarshaller;
@@ -82,9 +84,8 @@
public void testPruning() throws Exception {
createPageFileAndIndex(100);
- BTreeIndex index = ((BTreeIndex)this.index);
+ BTreeIndex<String,Long> index = ((BTreeIndex<String,Long>)this.index);
- String keyRoot = "key:";
this.index.load();
int minLeafDepth = index.getMinLeafDepth(tx);
@@ -110,7 +111,35 @@
this.index.unload();
}
+ public void testIteration() throws Exception {
+ createPageFileAndIndex(100);
+ BTreeIndex<String,Long> index = ((BTreeIndex<String,Long>)this.index);
+ this.index.load();
+
+ // Insert in reverse order..
+ doInsertReverse(1000);
+
+ this.index.unload();
+ this.index.load();
+
+ // BTree should iterate it in sorted order.
+ int counter=0;
+ for (Iterator<Map.Entry<String,Long>> i = index.iterator(tx);
i.hasNext();) {
+ Map.Entry<String,Long> entry = (Map.Entry<String,Long>)i.next();
+ assertEquals(key(counter),entry.getKey());
+ assertEquals(counter,(long)entry.getValue());
+ counter++;
+ }
+
+ this.index.unload();
+ }
+ void doInsertReverse(int count) throws Exception {
+ for (int i = count-1; i >= 0; i--) {
+ index.put(tx, key(i), (long)i);
+ tx.commit();
+ }
+ }
/**
* Overriding so that this generates keys that are the worst case for the
BTree. Keys that
* always insert to the end of the BTree.
