Beginning refactoring of BTree code to allow cleaner sharing with RTree. Factored out the free page manager in this commit.
git-svn-id: https://hyracks.googlecode.com/svn/branches/hyracks_indexes@366 123451ca-8445-de46-9d55-352943316053
diff --git a/hyracks-storage-am-btree/pom.xml b/hyracks-storage-am-btree/pom.xml
index 1e1bc8d..207954f 100644
--- a/hyracks-storage-am-btree/pom.xml
+++ b/hyracks-storage-am-btree/pom.xml
@@ -23,10 +23,10 @@
</plugin>
</plugins>
</build>
- <dependencies>
+ <dependencies>
<dependency>
<groupId>edu.uci.ics.hyracks</groupId>
- <artifactId>hyracks-storage-common</artifactId>
+ <artifactId>hyracks-storage-am-common</artifactId>
<version>0.1.4</version>
<type>jar</type>
<scope>compile</scope>
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/dataflow/BTreeBulkLoadOperatorNodePushable.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/dataflow/BTreeBulkLoadOperatorNodePushable.java
index 6e13ed7..f2f347f 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/dataflow/BTreeBulkLoadOperatorNodePushable.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/dataflow/BTreeBulkLoadOperatorNodePushable.java
@@ -22,9 +22,9 @@
import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
import edu.uci.ics.hyracks.dataflow.common.comm.io.FrameTupleAccessor;
import edu.uci.ics.hyracks.dataflow.std.base.AbstractUnaryInputSinkOperatorNodePushable;
-import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeMetaDataFrame;
-import edu.uci.ics.hyracks.storage.am.btree.frames.MetaDataFrame;
import edu.uci.ics.hyracks.storage.am.btree.impls.BTree;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrame;
+import edu.uci.ics.hyracks.storage.am.common.frames.LIFOMetaDataFrame;
public class BTreeBulkLoadOperatorNodePushable extends
AbstractUnaryInputSinkOperatorNodePushable {
@@ -56,7 +56,7 @@
opDesc.getOperatorId(), 0);
accessor = new FrameTupleAccessor(btreeOpHelper
.getHyracksStageletContext().getFrameSize(), recDesc);
- IBTreeMetaDataFrame metaFrame = new MetaDataFrame();
+ ITreeIndexMetaDataFrame metaFrame = new LIFOMetaDataFrame();
try {
btreeOpHelper.init();
btreeOpHelper.getBTree().open(btreeOpHelper.getBTreeFileId());
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/dataflow/BTreeDiskOrderScanOperatorNodePushable.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/dataflow/BTreeDiskOrderScanOperatorNodePushable.java
index c362183..279a0c3 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/dataflow/BTreeDiskOrderScanOperatorNodePushable.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/dataflow/BTreeDiskOrderScanOperatorNodePushable.java
@@ -25,10 +25,10 @@
import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
import edu.uci.ics.hyracks.dataflow.std.base.AbstractUnaryOutputSourceOperatorNodePushable;
import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeLeafFrame;
-import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeMetaDataFrame;
-import edu.uci.ics.hyracks.storage.am.btree.frames.MetaDataFrame;
import edu.uci.ics.hyracks.storage.am.btree.impls.DiskOrderScanCursor;
import edu.uci.ics.hyracks.storage.am.btree.impls.MultiComparator;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrame;
+import edu.uci.ics.hyracks.storage.am.common.frames.LIFOMetaDataFrame;
public class BTreeDiskOrderScanOperatorNodePushable extends AbstractUnaryOutputSourceOperatorNodePushable {
private final BTreeOpHelper btreeOpHelper;
@@ -43,7 +43,7 @@
IBTreeLeafFrame cursorFrame = btreeOpHelper.getOperatorDescriptor().getLeafFactory().getFrame();
DiskOrderScanCursor cursor = new DiskOrderScanCursor(cursorFrame);
- IBTreeMetaDataFrame metaFrame = new MetaDataFrame();
+ ITreeIndexMetaDataFrame metaFrame = new LIFOMetaDataFrame();
try {
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/dataflow/BTreeInsertUpdateDeleteOperatorNodePushable.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/dataflow/BTreeInsertUpdateDeleteOperatorNodePushable.java
index acb7d0f..733cb88 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/dataflow/BTreeInsertUpdateDeleteOperatorNodePushable.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/dataflow/BTreeInsertUpdateDeleteOperatorNodePushable.java
@@ -23,10 +23,10 @@
import edu.uci.ics.hyracks.dataflow.common.comm.io.FrameTupleAccessor;
import edu.uci.ics.hyracks.dataflow.common.comm.util.FrameUtils;
import edu.uci.ics.hyracks.dataflow.std.base.AbstractUnaryInputUnaryOutputOperatorNodePushable;
-import edu.uci.ics.hyracks.storage.am.btree.frames.MetaDataFrame;
import edu.uci.ics.hyracks.storage.am.btree.impls.BTree;
import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeOp;
import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeOpContext;
+import edu.uci.ics.hyracks.storage.am.common.frames.LIFOMetaDataFrame;
public class BTreeInsertUpdateDeleteOperatorNodePushable extends AbstractUnaryInputUnaryOutputOperatorNodePushable {
private final BTreeOpHelper btreeOpHelper;
@@ -56,7 +56,7 @@
btreeOpHelper.init();
btreeOpHelper.getBTree().open(btreeOpHelper.getBTreeFileId());
opCtx = btreeOpHelper.getBTree().createOpContext(op, btreeOpHelper.getLeafFrame(),
- btreeOpHelper.getInteriorFrame(), new MetaDataFrame());
+ btreeOpHelper.getInteriorFrame(), new LIFOMetaDataFrame());
} catch(Exception e) {
// cleanup in case of failure
btreeOpHelper.deinit();
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/dataflow/BTreeOpHelper.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/dataflow/BTreeOpHelper.java
index 880cc25..51826ce 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/dataflow/BTreeOpHelper.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/dataflow/BTreeOpHelper.java
@@ -21,9 +21,12 @@
import edu.uci.ics.hyracks.dataflow.std.file.IFileSplitProvider;
import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeInteriorFrame;
import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeLeafFrame;
-import edu.uci.ics.hyracks.storage.am.btree.frames.MetaDataFrame;
import edu.uci.ics.hyracks.storage.am.btree.impls.BTree;
import edu.uci.ics.hyracks.storage.am.btree.impls.MultiComparator;
+import edu.uci.ics.hyracks.storage.am.common.api.IFreePageManager;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrame;
+import edu.uci.ics.hyracks.storage.am.common.frames.LIFOMetaDataFrame;
+import edu.uci.ics.hyracks.storage.am.common.freepage.LinkedListFreePageManager;
import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
import edu.uci.ics.hyracks.storage.common.file.IFileMapProvider;
@@ -109,10 +112,12 @@
MultiComparator cmp = new MultiComparator(opDesc
.getTypeTraits(), comparators);
- btree = new BTree(bufferCache, opDesc.getInteriorFactory(),
+ // TODO: abstract away in some kind of factory
+ IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, btreeFileId, 0);
+ btree = new BTree(bufferCache, freePageManager, opDesc.getInteriorFactory(),
opDesc.getLeafFactory(), cmp);
if (mode == BTreeMode.CREATE_BTREE) {
- MetaDataFrame metaFrame = new MetaDataFrame();
+ ITreeIndexMetaDataFrame metaFrame = new LIFOMetaDataFrame();
try {
btree.create(btreeFileId, leafFrame, metaFrame);
btree.open(btreeFileId);
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTree.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTree.java
index 7a8ee73..1902572 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTree.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTree.java
@@ -28,22 +28,24 @@
import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeInteriorFrameFactory;
import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeLeafFrame;
import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeLeafFrameFactory;
-import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeMetaDataFrame;
import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeTupleWriter;
import edu.uci.ics.hyracks.storage.am.btree.frames.NSMInteriorFrame;
+import edu.uci.ics.hyracks.storage.am.common.api.IFreePageManager;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrame;
import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
import edu.uci.ics.hyracks.storage.common.file.BufferedFileHandle;
public class BTree {
-
+
private final static int RESTART_OP = Integer.MIN_VALUE;
private final static int MAX_RESTARTS = 10;
+
+ // the root page never changes
+ private final int rootPage = 1;
- private final int metaDataPage = 0; // page containing meta data, e.g.,
- // maxPage
- private final int rootPage = 1; // the root page never changes
-
+ private final IFreePageManager freePageManager;
+
private boolean created = false;
private boolean loaded = false;
@@ -90,17 +92,18 @@
return strBuilder.toString();
}
- public BTree(IBufferCache bufferCache, IBTreeInteriorFrameFactory interiorFrameFactory,
+ public BTree(IBufferCache bufferCache, IFreePageManager freePageManager, IBTreeInteriorFrameFactory interiorFrameFactory,
IBTreeLeafFrameFactory leafFrameFactory, MultiComparator cmp) {
this.bufferCache = bufferCache;
this.interiorFrameFactory = interiorFrameFactory;
this.leafFrameFactory = leafFrameFactory;
this.cmp = cmp;
+ this.freePageManager = freePageManager;
this.treeLatch = new ReentrantReadWriteLock(true);
this.diskOrderScanPredicate = new RangePredicate(true, null, null, true, true, cmp, cmp);
}
- public void create(int fileId, IBTreeLeafFrame leafFrame, IBTreeMetaDataFrame metaFrame) throws Exception {
+ public void create(int fileId, IBTreeLeafFrame leafFrame, ITreeIndexMetaDataFrame metaFrame) throws Exception {
if (created)
return;
@@ -111,24 +114,9 @@
// check if another thread beat us to it
if (created)
return;
-
- // initialize meta data page
- ICachedPage metaNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, metaDataPage), false);
- pins++;
-
- metaNode.acquireWriteLatch();
- writeLatchesAcquired++;
- try {
- metaFrame.setPage(metaNode);
- metaFrame.initBuffer((byte) -1);
- metaFrame.setMaxPage(rootPage);
- } finally {
- metaNode.releaseWriteLatch();
- writeLatchesReleased++;
- bufferCache.unpin(metaNode);
- unpins++;
- }
-
+
+ freePageManager.init(metaFrame, rootPage);
+
// initialize root page
ICachedPage rootNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, rootPage), true);
pins++;
@@ -159,159 +147,17 @@
public void close() {
fileId = -1;
}
-
- private int getFreePage(IBTreeMetaDataFrame metaFrame) throws HyracksDataException {
- ICachedPage metaNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, metaDataPage), false);
- pins++;
-
- metaNode.acquireWriteLatch();
- writeLatchesAcquired++;
-
- int freePage = -1;
- try {
- metaFrame.setPage(metaNode);
- freePage = metaFrame.getFreePage();
- if (freePage < 0) { // no free page entry on this page
- int nextPage = metaFrame.getNextPage();
- if (nextPage > 0) { // sibling may have free pages
- ICachedPage nextNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, nextPage), false);
- pins++;
-
- nextNode.acquireWriteLatch();
- writeLatchesAcquired++;
- // we copy over the free space entries of nextpage into the
- // first meta page (metaDataPage)
- // we need to link the first page properly to the next page
- // of nextpage
- try {
- // remember entries that remain unchanged
- int maxPage = metaFrame.getMaxPage();
-
- // copy entire page (including sibling pointer, free
- // page entries, and all other info)
- // after this copy nextPage is considered a free page
- System.arraycopy(nextNode.getBuffer().array(), 0, metaNode.getBuffer().array(), 0, nextNode
- .getBuffer().capacity());
-
- // reset unchanged entry
- metaFrame.setMaxPage(maxPage);
-
- freePage = metaFrame.getFreePage();
- // sibling also has no free pages, this "should" not
- // happen, but we deal with it anyway just to be safe
- if (freePage < 0) {
- freePage = nextPage;
- } else {
- metaFrame.addFreePage(nextPage);
- }
- } finally {
- nextNode.releaseWriteLatch();
- writeLatchesReleased++;
- bufferCache.unpin(nextNode);
- unpins++;
- }
- } else {
- freePage = metaFrame.getMaxPage();
- freePage++;
- metaFrame.setMaxPage(freePage);
- }
- }
- } finally {
- metaNode.releaseWriteLatch();
- writeLatchesReleased++;
- bufferCache.unpin(metaNode);
- unpins++;
- }
-
- return freePage;
- }
-
+
private void addFreePages(BTreeOpContext ctx) throws Exception {
for (int i = 0; i < ctx.freePages.size(); i++) {
- addFreePage(ctx.metaFrame, ctx.freePages.get(i));
+ // root page is special, don't add it to free pages
+ if(ctx.freePages.get(i) != rootPage) {
+ freePageManager.addFreePage(ctx.metaFrame, ctx.freePages.get(i));
+ }
}
ctx.freePages.clear();
}
-
- private void addFreePage(IBTreeMetaDataFrame metaFrame, int freePage) throws Exception {
- // root page is special, don't add it to free pages
- if (freePage == rootPage)
- return;
-
- ICachedPage metaNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, metaDataPage), false);
- pins++;
-
- metaNode.acquireWriteLatch();
- writeLatchesAcquired++;
-
- metaFrame.setPage(metaNode);
-
- try {
- if (metaFrame.hasSpace()) {
- metaFrame.addFreePage(freePage);
- } else {
- // allocate a new page in the chain of meta pages
- int newPage = metaFrame.getFreePage();
- if (newPage < 0) {
- throw new Exception("Inconsistent Meta Page State. It has no space, but it also has no entries.");
- }
-
- ICachedPage newNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, newPage), false);
- pins++;
-
- newNode.acquireWriteLatch();
- writeLatchesAcquired++;
-
- try {
- int metaMaxPage = metaFrame.getMaxPage();
-
- // copy metaDataPage to newNode
- System.arraycopy(metaNode.getBuffer().array(), 0, newNode.getBuffer().array(), 0, metaNode
- .getBuffer().capacity());
-
- metaFrame.initBuffer(-1);
- metaFrame.setNextPage(newPage);
- metaFrame.setMaxPage(metaMaxPage);
- metaFrame.addFreePage(freePage);
- } finally {
- newNode.releaseWriteLatch();
- writeLatchesReleased++;
-
- bufferCache.unpin(newNode);
- unpins++;
- }
- }
- } catch (Exception e) {
- e.printStackTrace();
- } finally {
- metaNode.releaseWriteLatch();
- writeLatchesReleased++;
-
- bufferCache.unpin(metaNode);
- unpins++;
- }
- }
-
- public int getMaxPage(IBTreeMetaDataFrame metaFrame) throws HyracksDataException {
- ICachedPage metaNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, metaDataPage), false);
- pins++;
-
- metaNode.acquireWriteLatch();
- writeLatchesAcquired++;
- int maxPage = -1;
- try {
- metaFrame.setPage(metaNode);
- maxPage = metaFrame.getMaxPage();
- } finally {
- metaNode.releaseWriteLatch();
- writeLatchesReleased++;
- bufferCache.unpin(metaNode);
- unpins++;
- }
-
- return maxPage;
- }
-
+
public void printTree(IBTreeLeafFrame leafFrame, IBTreeInteriorFrame interiorFrame, ISerializerDeserializer[] fields)
throws Exception {
printTree(rootPage, null, false, leafFrame, interiorFrame, fields);
@@ -374,28 +220,11 @@
}
}
- public void diskOrderScan(DiskOrderScanCursor cursor, IBTreeLeafFrame leafFrame, IBTreeMetaDataFrame metaFrame)
+ public void diskOrderScan(DiskOrderScanCursor cursor, IBTreeLeafFrame leafFrame, ITreeIndexMetaDataFrame metaFrame)
throws HyracksDataException {
int currentPageId = rootPage + 1;
- int maxPageId = -1;
-
- ICachedPage metaNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, metaDataPage), false);
- pins++;
-
- metaNode.acquireReadLatch();
- readLatchesAcquired++;
-
- try {
- metaFrame.setPage(metaNode);
- maxPageId = metaFrame.getMaxPage();
- } finally {
- metaNode.releaseReadLatch();
- readLatchesAcquired++;
-
- bufferCache.unpin(metaNode);
- unpins++;
- }
-
+ int maxPageId = freePageManager.getMaxPage(metaFrame);
+
ICachedPage page = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, currentPageId), false);
page.acquireReadLatch();
cursor.setBufferCache(bufferCache);
@@ -481,7 +310,7 @@
// is really required
writeLatchesAcquired++;
try {
- int newLeftId = getFreePage(ctx.metaFrame);
+ int newLeftId = freePageManager.getFreePage(ctx.metaFrame);
ICachedPage newLeftNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, newLeftId), true);
pins++;
newLeftNode.acquireWriteLatch(); // TODO: think about whether
@@ -620,7 +449,7 @@
treeLatchesAcquired++;
try {
- int rightPageId = getFreePage(ctx.metaFrame);
+ int rightPageId = freePageManager.getFreePage(ctx.metaFrame);
ICachedPage rightNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, rightPageId), true);
pins++;
rightNode.acquireWriteLatch();
@@ -708,7 +537,7 @@
switch (spaceStatus) {
case INSUFFICIENT_SPACE: {
splitsByLevel[ctx.interiorFrame.getLevel()]++; // debug
- int rightPageId = getFreePage(ctx.metaFrame);
+ int rightPageId = freePageManager.getFreePage(ctx.metaFrame);
ICachedPage rightNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, rightPageId), true);
pins++;
rightNode.acquireWriteLatch();
@@ -1182,18 +1011,18 @@
private final ArrayList<NodeFrontier> nodeFrontiers = new ArrayList<NodeFrontier>();
private final IBTreeLeafFrame leafFrame;
private final IBTreeInteriorFrame interiorFrame;
- private final IBTreeMetaDataFrame metaFrame;
+ private final ITreeIndexMetaDataFrame metaFrame;
private final IBTreeTupleWriter tupleWriter;
public BulkLoadContext(float fillFactor, IBTreeLeafFrame leafFrame, IBTreeInteriorFrame interiorFrame,
- IBTreeMetaDataFrame metaFrame) throws HyracksDataException {
+ ITreeIndexMetaDataFrame metaFrame) throws HyracksDataException {
splitKey = new SplitKey(leafFrame.getTupleWriter().createTupleReference());
tupleWriter = leafFrame.getTupleWriter();
NodeFrontier leafFrontier = new NodeFrontier(leafFrame.createTupleReference());
- leafFrontier.pageId = getFreePage(metaFrame);
+ leafFrontier.pageId = freePageManager.getFreePage(metaFrame);
leafFrontier.page = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, leafFrontier.pageId), bulkNewPage);
leafFrontier.page.acquireWriteLatch();
@@ -1216,7 +1045,7 @@
private void addLevel() throws HyracksDataException {
NodeFrontier frontier = new NodeFrontier(tupleWriter.createTupleReference());
- frontier.pageId = getFreePage(metaFrame);
+ frontier.pageId = freePageManager.getFreePage(metaFrame);
frontier.page = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, frontier.pageId), bulkNewPage);
frontier.page.acquireWriteLatch();
frontier.lastTuple.setFieldCount(cmp.getKeyFieldCount());
@@ -1258,7 +1087,7 @@
frontier.page.releaseWriteLatch();
bufferCache.unpin(frontier.page);
- frontier.pageId = getFreePage(ctx.metaFrame);
+ frontier.pageId = freePageManager.getFreePage(ctx.metaFrame);
ctx.splitKey.setRightPage(frontier.pageId);
propagateBulk(ctx, level + 1);
@@ -1280,7 +1109,7 @@
// assumes btree has been created and opened
public BulkLoadContext beginBulkLoad(float fillFactor, IBTreeLeafFrame leafFrame,
- IBTreeInteriorFrame interiorFrame, IBTreeMetaDataFrame metaFrame) throws HyracksDataException {
+ IBTreeInteriorFrame interiorFrame, ITreeIndexMetaDataFrame metaFrame) throws HyracksDataException {
if (loaded)
throw new HyracksDataException("Trying to bulk-load BTree but has BTree already been loaded.");
@@ -1313,7 +1142,7 @@
ctx.splitKey.getTuple().resetByOffset(ctx.splitKey.getBuffer(), 0);
ctx.splitKey.setLeftPage(leafFrontier.pageId);
int prevPageId = leafFrontier.pageId;
- leafFrontier.pageId = getFreePage(ctx.metaFrame);
+ leafFrontier.pageId = freePageManager.getFreePage(ctx.metaFrame);
leafFrame.setNextLeaf(leafFrontier.pageId);
leafFrontier.page.releaseWriteLatch();
@@ -1365,7 +1194,7 @@
}
public BTreeOpContext createOpContext(BTreeOp op, IBTreeLeafFrame leafFrame, IBTreeInteriorFrame interiorFrame,
- IBTreeMetaDataFrame metaFrame) {
+ ITreeIndexMetaDataFrame metaFrame) {
// TODO: figure out better tree-height hint
return new BTreeOpContext(op, leafFrame, interiorFrame, metaFrame, 6);
}
@@ -1381,4 +1210,8 @@
public MultiComparator getMultiComparator() {
return cmp;
}
+
+ public IFreePageManager getFreePageManager() {
+ return freePageManager;
+ }
}
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeOpContext.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeOpContext.java
index 84c11a2..fb59d07 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeOpContext.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeOpContext.java
@@ -18,13 +18,13 @@
import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeCursor;
import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeInteriorFrame;
import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeLeafFrame;
-import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeMetaDataFrame;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrame;
public final class BTreeOpContext {
public final BTreeOp op;
public final IBTreeLeafFrame leafFrame;
public final IBTreeInteriorFrame interiorFrame;
- public final IBTreeMetaDataFrame metaFrame;
+ public final ITreeIndexMetaDataFrame metaFrame;
public IBTreeCursor cursor;
public RangePredicate pred;
public final SplitKey splitKey;
@@ -34,7 +34,7 @@
public final IntArrayList freePages;
public BTreeOpContext(BTreeOp op, IBTreeLeafFrame leafFrame, IBTreeInteriorFrame interiorFrame,
- IBTreeMetaDataFrame metaFrame, int treeHeightHint) {
+ ITreeIndexMetaDataFrame metaFrame, int treeHeightHint) {
this.op = op;
this.leafFrame = leafFrame;
this.interiorFrame = interiorFrame;
diff --git a/hyracks-storage-am-common/pom.xml b/hyracks-storage-am-common/pom.xml
new file mode 100644
index 0000000..5271eae
--- /dev/null
+++ b/hyracks-storage-am-common/pom.xml
@@ -0,0 +1,42 @@
+<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd">
+ <modelVersion>4.0.0</modelVersion>
+ <groupId>edu.uci.ics.hyracks</groupId>
+ <artifactId>hyracks-storage-am-common</artifactId>
+ <version>0.1.4</version>
+
+ <parent>
+ <groupId>edu.uci.ics.hyracks</groupId>
+ <artifactId>hyracks</artifactId>
+ <version>0.1.4</version>
+ </parent>
+
+ <build>
+ <plugins>
+ <plugin>
+ <groupId>org.apache.maven.plugins</groupId>
+ <artifactId>maven-compiler-plugin</artifactId>
+ <version>2.0.2</version>
+ <configuration>
+ <source>1.6</source>
+ <target>1.6</target>
+ </configuration>
+ </plugin>
+ </plugins>
+ </build>
+ <dependencies>
+ <dependency>
+ <groupId>edu.uci.ics.hyracks</groupId>
+ <artifactId>hyracks-api</artifactId>
+ <version>0.1.4</version>
+ <type>jar</type>
+ <scope>compile</scope>
+ </dependency>
+ <dependency>
+ <groupId>edu.uci.ics.hyracks</groupId>
+ <artifactId>hyracks-storage-common</artifactId>
+ <version>0.1.4</version>
+ <type>jar</type>
+ <scope>compile</scope>
+ </dependency>
+ </dependencies>
+</project>
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/IFreePageManager.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/IFreePageManager.java
new file mode 100644
index 0000000..0c2bcfa
--- /dev/null
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/IFreePageManager.java
@@ -0,0 +1,10 @@
+package edu.uci.ics.hyracks.storage.am.common.api;
+
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+
+public interface IFreePageManager {
+ public int getFreePage(ITreeIndexMetaDataFrame metaFrame) throws HyracksDataException;
+ public void addFreePage(ITreeIndexMetaDataFrame metaFrame, int freePage) throws HyracksDataException;
+ public int getMaxPage(ITreeIndexMetaDataFrame metaFrame) throws HyracksDataException;
+ public void init(ITreeIndexMetaDataFrame metaFrame, int currentMaxPage) throws HyracksDataException;
+}
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeMetaDataFrame.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexMetaDataFrame.java
similarity index 91%
rename from hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeMetaDataFrame.java
rename to hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexMetaDataFrame.java
index 58739e2..bbd03d6 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeMetaDataFrame.java
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexMetaDataFrame.java
@@ -13,11 +13,11 @@
* limitations under the License.
*/
-package edu.uci.ics.hyracks.storage.am.btree.api;
+package edu.uci.ics.hyracks.storage.am.common.api;
import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
-public interface IBTreeMetaDataFrame {
+public interface ITreeIndexMetaDataFrame {
public void initBuffer(int level);
public void setPage(ICachedPage page);
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeMetaDataFrameFactory.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexMetaDataFrameFactory.java
similarity index 80%
rename from hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeMetaDataFrameFactory.java
rename to hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexMetaDataFrameFactory.java
index 2912cf9..8c05637 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeMetaDataFrameFactory.java
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexMetaDataFrameFactory.java
@@ -13,8 +13,9 @@
* limitations under the License.
*/
-package edu.uci.ics.hyracks.storage.am.btree.api;
+package edu.uci.ics.hyracks.storage.am.common.api;
-public interface IBTreeMetaDataFrameFactory {
- public IBTreeMetaDataFrame getFrame();
+
+public interface ITreeIndexMetaDataFrameFactory {
+ public ITreeIndexMetaDataFrame getFrame();
}
\ No newline at end of file
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/MetaDataFrame.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/frames/LIFOMetaDataFrame.java
similarity index 94%
rename from hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/MetaDataFrame.java
rename to hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/frames/LIFOMetaDataFrame.java
index a219dd6..759efc3 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/MetaDataFrame.java
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/frames/LIFOMetaDataFrame.java
@@ -13,11 +13,11 @@
* limitations under the License.
*/
-package edu.uci.ics.hyracks.storage.am.btree.frames;
+package edu.uci.ics.hyracks.storage.am.common.frames;
import java.nio.ByteBuffer;
-import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeMetaDataFrame;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrame;
import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
// all meta pages of this kind have a negative level
@@ -25,7 +25,7 @@
// the first meta page is special because it guarantees to have a correct max page
// other meta pages (i.e., with level -2) have junk in the max page field
-public class MetaDataFrame implements IBTreeMetaDataFrame {
+public class LIFOMetaDataFrame implements ITreeIndexMetaDataFrame {
protected static final int tupleCountOff = 0;
protected static final int freeSpaceOff = tupleCountOff + 4;
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/MetaDataFrameFactory.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/frames/LIFOMetaDataFrameFactory.java
similarity index 63%
rename from hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/MetaDataFrameFactory.java
rename to hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/frames/LIFOMetaDataFrameFactory.java
index 9896bf9..eb56987 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/MetaDataFrameFactory.java
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/frames/LIFOMetaDataFrameFactory.java
@@ -13,14 +13,14 @@
* limitations under the License.
*/
-package edu.uci.ics.hyracks.storage.am.btree.frames;
+package edu.uci.ics.hyracks.storage.am.common.frames;
-import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeMetaDataFrame;
-import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeMetaDataFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrame;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrameFactory;
-public class MetaDataFrameFactory implements IBTreeMetaDataFrameFactory {
+public class LIFOMetaDataFrameFactory implements ITreeIndexMetaDataFrameFactory {
@Override
- public IBTreeMetaDataFrame getFrame() {
- return new MetaDataFrame();
+ public ITreeIndexMetaDataFrame getFrame() {
+ return new LIFOMetaDataFrame();
}
}
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/freepage/LinkedListFreePageManager.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/freepage/LinkedListFreePageManager.java
new file mode 100644
index 0000000..286acda
--- /dev/null
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/freepage/LinkedListFreePageManager.java
@@ -0,0 +1,171 @@
+package edu.uci.ics.hyracks.storage.am.common.freepage;
+
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.storage.am.common.api.IFreePageManager;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrame;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
+import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
+import edu.uci.ics.hyracks.storage.common.file.BufferedFileHandle;
+
+public class LinkedListFreePageManager implements IFreePageManager {
+
+ private final IBufferCache bufferCache;
+ private final int fileId;
+ private final int headPage;
+
+ public LinkedListFreePageManager(IBufferCache bufferCache, int fileId,
+ int headPage) {
+ this.bufferCache = bufferCache;
+ this.fileId = fileId;
+ this.headPage = headPage;
+ }
+
+ @Override
+ public void addFreePage(ITreeIndexMetaDataFrame metaFrame, int freePage)
+ throws HyracksDataException {
+
+ ICachedPage metaNode = bufferCache.pin(BufferedFileHandle
+ .getDiskPageId(fileId, headPage), false);
+ metaNode.acquireWriteLatch();
+
+ try {
+ metaFrame.setPage(metaNode);
+
+ if (metaFrame.hasSpace()) {
+ metaFrame.addFreePage(freePage);
+ } else {
+ // allocate a new page in the chain of meta pages
+ int newPage = metaFrame.getFreePage();
+ if (newPage < 0) {
+ throw new Exception(
+ "Inconsistent Meta Page State. It has no space, but it also has no entries.");
+ }
+
+ ICachedPage newNode = bufferCache.pin(BufferedFileHandle
+ .getDiskPageId(fileId, newPage), false);
+ newNode.acquireWriteLatch();
+
+ try {
+ int metaMaxPage = metaFrame.getMaxPage();
+
+ // copy metaDataPage to newNode
+ System.arraycopy(metaNode.getBuffer().array(), 0, newNode
+ .getBuffer().array(), 0, metaNode.getBuffer()
+ .capacity());
+
+ metaFrame.initBuffer(-1);
+ metaFrame.setNextPage(newPage);
+ metaFrame.setMaxPage(metaMaxPage);
+ metaFrame.addFreePage(freePage);
+ } finally {
+ newNode.releaseWriteLatch();
+ bufferCache.unpin(newNode);
+ }
+ }
+ } catch (Exception e) {
+ e.printStackTrace();
+ } finally {
+ metaNode.releaseWriteLatch();
+ bufferCache.unpin(metaNode);
+ }
+ }
+
+ @Override
+ public int getFreePage(ITreeIndexMetaDataFrame metaFrame)
+ throws HyracksDataException {
+ ICachedPage metaNode = bufferCache.pin(BufferedFileHandle
+ .getDiskPageId(fileId, headPage), false);
+
+ metaNode.acquireWriteLatch();
+
+ int freePage = -1;
+ try {
+ metaFrame.setPage(metaNode);
+ freePage = metaFrame.getFreePage();
+ if (freePage < 0) { // no free page entry on this page
+ int nextPage = metaFrame.getNextPage();
+ if (nextPage > 0) { // sibling may have free pages
+ ICachedPage nextNode = bufferCache.pin(BufferedFileHandle
+ .getDiskPageId(fileId, nextPage), false);
+
+ nextNode.acquireWriteLatch();
+ // we copy over the free space entries of nextpage into the
+ // first meta page (metaDataPage)
+ // we need to link the first page properly to the next page
+ // of nextpage
+ try {
+ // remember entries that remain unchanged
+ int maxPage = metaFrame.getMaxPage();
+
+ // copy entire page (including sibling pointer, free
+ // page entries, and all other info)
+ // after this copy nextPage is considered a free page
+ System.arraycopy(nextNode.getBuffer().array(), 0,
+ metaNode.getBuffer().array(), 0, nextNode
+ .getBuffer().capacity());
+
+ // reset unchanged entry
+ metaFrame.setMaxPage(maxPage);
+
+ freePage = metaFrame.getFreePage();
+ // sibling also has no free pages, this "should" not
+ // happen, but we deal with it anyway just to be safe
+ if (freePage < 0) {
+ freePage = nextPage;
+ } else {
+ metaFrame.addFreePage(nextPage);
+ }
+ } finally {
+ nextNode.releaseWriteLatch();
+ bufferCache.unpin(nextNode);
+ }
+ } else {
+ freePage = metaFrame.getMaxPage();
+ freePage++;
+ metaFrame.setMaxPage(freePage);
+ }
+ }
+ } finally {
+ metaNode.releaseWriteLatch();
+ bufferCache.unpin(metaNode);
+ }
+
+ return freePage;
+ }
+
+ @Override
+ public int getMaxPage(ITreeIndexMetaDataFrame metaFrame)
+ throws HyracksDataException {
+ ICachedPage metaNode = bufferCache.pin(BufferedFileHandle
+ .getDiskPageId(fileId, headPage), false);
+ metaNode.acquireWriteLatch();
+ int maxPage = -1;
+ try {
+ metaFrame.setPage(metaNode);
+ maxPage = metaFrame.getMaxPage();
+ } finally {
+ metaNode.releaseWriteLatch();
+ bufferCache.unpin(metaNode);
+ }
+ return maxPage;
+ }
+
+ @Override
+ public void init(ITreeIndexMetaDataFrame metaFrame, int currentMaxPage)
+ throws HyracksDataException {
+ // initialize meta data page
+ ICachedPage metaNode = bufferCache.pin(BufferedFileHandle
+ .getDiskPageId(fileId, headPage), false);
+
+ metaNode.acquireWriteLatch();
+ try {
+ metaFrame.setPage(metaNode);
+ metaFrame.initBuffer((byte) -1);
+ metaFrame.setMaxPage(currentMaxPage);
+ } finally {
+ metaNode.releaseWriteLatch();
+ bufferCache.unpin(metaNode);
+ }
+ }
+
+}
diff --git a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeTest.java b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeTest.java
index 2985601..e12b5b7 100644
--- a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeTest.java
+++ b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeTest.java
@@ -44,9 +44,6 @@
import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeInteriorFrameFactory;
import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeLeafFrame;
import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeLeafFrameFactory;
-import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeMetaDataFrame;
-import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeMetaDataFrameFactory;
-import edu.uci.ics.hyracks.storage.am.btree.frames.MetaDataFrameFactory;
import edu.uci.ics.hyracks.storage.am.btree.frames.NSMInteriorFrameFactory;
import edu.uci.ics.hyracks.storage.am.btree.frames.NSMLeafFrameFactory;
import edu.uci.ics.hyracks.storage.am.btree.impls.BTree;
@@ -59,6 +56,11 @@
import edu.uci.ics.hyracks.storage.am.btree.impls.RangeSearchCursor;
import edu.uci.ics.hyracks.storage.am.btree.tuples.SimpleTupleWriterFactory;
import edu.uci.ics.hyracks.storage.am.btree.tuples.TypeAwareTupleWriterFactory;
+import edu.uci.ics.hyracks.storage.am.common.api.IFreePageManager;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrame;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.frames.LIFOMetaDataFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.freepage.LinkedListFreePageManager;
import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
import edu.uci.ics.hyracks.storage.common.buffercache.ICacheMemoryAllocator;
import edu.uci.ics.hyracks.storage.common.file.IFileMapProvider;
@@ -126,13 +128,15 @@
tupleWriterFactory);
IBTreeInteriorFrameFactory interiorFrameFactory = new NSMInteriorFrameFactory(
tupleWriterFactory);
- IBTreeMetaDataFrameFactory metaFrameFactory = new MetaDataFrameFactory();
+ ITreeIndexMetaDataFrameFactory metaFrameFactory = new LIFOMetaDataFrameFactory();
IBTreeLeafFrame leafFrame = leafFrameFactory.getFrame();
IBTreeInteriorFrame interiorFrame = interiorFrameFactory.getFrame();
- IBTreeMetaDataFrame metaFrame = metaFrameFactory.getFrame();
+ ITreeIndexMetaDataFrame metaFrame = metaFrameFactory.getFrame();
- BTree btree = new BTree(bufferCache, interiorFrameFactory,
+ IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, fileId, 0);
+
+ BTree btree = new BTree(bufferCache, freePageManager, interiorFrameFactory,
leafFrameFactory, cmp);
btree.create(fileId, leafFrame, metaFrame);
btree.open(fileId);
@@ -201,7 +205,7 @@
// btree.printTree(leafFrame, interiorFrame);
// System.out.println();
- int maxPage = btree.getMaxPage(metaFrame);
+ int maxPage = btree.getFreePageManager().getMaxPage(metaFrame);
System.out.println("MAXPAGE: " + maxPage);
String stats = btree.printStats();
@@ -362,13 +366,15 @@
tupleWriterFactory);
IBTreeInteriorFrameFactory interiorFrameFactory = new NSMInteriorFrameFactory(
tupleWriterFactory);
- IBTreeMetaDataFrameFactory metaFrameFactory = new MetaDataFrameFactory();
+ ITreeIndexMetaDataFrameFactory metaFrameFactory = new LIFOMetaDataFrameFactory();
IBTreeLeafFrame leafFrame = leafFrameFactory.getFrame();
IBTreeInteriorFrame interiorFrame = interiorFrameFactory.getFrame();
- IBTreeMetaDataFrame metaFrame = metaFrameFactory.getFrame();
+ ITreeIndexMetaDataFrame metaFrame = metaFrameFactory.getFrame();
- BTree btree = new BTree(bufferCache, interiorFrameFactory,
+ IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, fileId, 0);
+
+ BTree btree = new BTree(bufferCache, freePageManager, interiorFrameFactory,
leafFrameFactory, cmp);
btree.create(fileId, leafFrame, metaFrame);
btree.open(fileId);
@@ -567,13 +573,15 @@
tupleWriterFactory);
IBTreeInteriorFrameFactory interiorFrameFactory = new NSMInteriorFrameFactory(
tupleWriterFactory);
- IBTreeMetaDataFrameFactory metaFrameFactory = new MetaDataFrameFactory();
+ ITreeIndexMetaDataFrameFactory metaFrameFactory = new LIFOMetaDataFrameFactory();
IBTreeLeafFrame leafFrame = leafFrameFactory.getFrame();
IBTreeInteriorFrame interiorFrame = interiorFrameFactory.getFrame();
- IBTreeMetaDataFrame metaFrame = metaFrameFactory.getFrame();
+ ITreeIndexMetaDataFrame metaFrame = metaFrameFactory.getFrame();
- BTree btree = new BTree(bufferCache, interiorFrameFactory,
+ IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, fileId, 0);
+
+ BTree btree = new BTree(bufferCache, freePageManager, interiorFrameFactory,
leafFrameFactory, cmp);
btree.create(fileId, leafFrame, metaFrame);
btree.open(fileId);
@@ -765,13 +773,15 @@
tupleWriterFactory);
IBTreeInteriorFrameFactory interiorFrameFactory = new NSMInteriorFrameFactory(
tupleWriterFactory);
- IBTreeMetaDataFrameFactory metaFrameFactory = new MetaDataFrameFactory();
+ ITreeIndexMetaDataFrameFactory metaFrameFactory = new LIFOMetaDataFrameFactory();
IBTreeLeafFrame leafFrame = leafFrameFactory.getFrame();
IBTreeInteriorFrame interiorFrame = interiorFrameFactory.getFrame();
- IBTreeMetaDataFrame metaFrame = metaFrameFactory.getFrame();
+ ITreeIndexMetaDataFrame metaFrame = metaFrameFactory.getFrame();
- BTree btree = new BTree(bufferCache, interiorFrameFactory,
+ IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, fileId, 0);
+
+ BTree btree = new BTree(bufferCache, freePageManager, interiorFrameFactory,
leafFrameFactory, cmp);
btree.create(fileId, leafFrame, metaFrame);
btree.open(fileId);
@@ -950,13 +960,15 @@
tupleWriterFactory);
IBTreeInteriorFrameFactory interiorFrameFactory = new NSMInteriorFrameFactory(
tupleWriterFactory);
- IBTreeMetaDataFrameFactory metaFrameFactory = new MetaDataFrameFactory();
+ ITreeIndexMetaDataFrameFactory metaFrameFactory = new LIFOMetaDataFrameFactory();
IBTreeLeafFrame leafFrame = leafFrameFactory.getFrame();
IBTreeInteriorFrame interiorFrame = interiorFrameFactory.getFrame();
- IBTreeMetaDataFrame metaFrame = metaFrameFactory.getFrame();
+ ITreeIndexMetaDataFrame metaFrame = metaFrameFactory.getFrame();
- BTree btree = new BTree(bufferCache, interiorFrameFactory,
+ IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, fileId, 0);
+
+ BTree btree = new BTree(bufferCache, freePageManager, interiorFrameFactory,
leafFrameFactory, cmp);
btree.create(fileId, leafFrame, metaFrame);
btree.open(fileId);
@@ -1124,13 +1136,15 @@
tupleWriterFactory);
IBTreeInteriorFrameFactory interiorFrameFactory = new NSMInteriorFrameFactory(
tupleWriterFactory);
- IBTreeMetaDataFrameFactory metaFrameFactory = new MetaDataFrameFactory();
+ ITreeIndexMetaDataFrameFactory metaFrameFactory = new LIFOMetaDataFrameFactory();
IBTreeLeafFrame leafFrame = leafFrameFactory.getFrame();
IBTreeInteriorFrame interiorFrame = interiorFrameFactory.getFrame();
- IBTreeMetaDataFrame metaFrame = metaFrameFactory.getFrame();
+ ITreeIndexMetaDataFrame metaFrame = metaFrameFactory.getFrame();
- BTree btree = new BTree(bufferCache, interiorFrameFactory,
+ IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, fileId, 0);
+
+ BTree btree = new BTree(bufferCache, freePageManager, interiorFrameFactory,
leafFrameFactory, cmp);
btree.create(fileId, leafFrame, metaFrame);
btree.open(fileId);
diff --git a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/RangeSearchCursorTest.java b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/RangeSearchCursorTest.java
index 12371be..d9736ce 100644
--- a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/RangeSearchCursorTest.java
+++ b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/RangeSearchCursorTest.java
@@ -50,10 +50,7 @@
import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeInteriorFrameFactory;
import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeLeafFrame;
import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeLeafFrameFactory;
-import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeMetaDataFrame;
-import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeMetaDataFrameFactory;
import edu.uci.ics.hyracks.storage.am.btree.frames.FieldPrefixNSMLeafFrameFactory;
-import edu.uci.ics.hyracks.storage.am.btree.frames.MetaDataFrameFactory;
import edu.uci.ics.hyracks.storage.am.btree.frames.NSMInteriorFrameFactory;
import edu.uci.ics.hyracks.storage.am.btree.frames.NSMLeafFrameFactory;
import edu.uci.ics.hyracks.storage.am.btree.impls.BTree;
@@ -64,6 +61,11 @@
import edu.uci.ics.hyracks.storage.am.btree.impls.RangePredicate;
import edu.uci.ics.hyracks.storage.am.btree.impls.RangeSearchCursor;
import edu.uci.ics.hyracks.storage.am.btree.tuples.TypeAwareTupleWriterFactory;
+import edu.uci.ics.hyracks.storage.am.common.api.IFreePageManager;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrame;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.frames.LIFOMetaDataFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.freepage.LinkedListFreePageManager;
import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
import edu.uci.ics.hyracks.storage.common.buffercache.ICacheMemoryAllocator;
import edu.uci.ics.hyracks.storage.common.file.IFileMapProvider;
@@ -96,11 +98,11 @@
tupleWriterFactory);
IBTreeInteriorFrameFactory interiorFrameFactory = new NSMInteriorFrameFactory(
tupleWriterFactory);
- IBTreeMetaDataFrameFactory metaFrameFactory = new MetaDataFrameFactory();
+ ITreeIndexMetaDataFrameFactory metaFrameFactory = new LIFOMetaDataFrameFactory();
IBTreeLeafFrame leafFrame = leafFrameFactory.getFrame();
IBTreeInteriorFrame interiorFrame = interiorFrameFactory.getFrame();
- IBTreeMetaDataFrame metaFrame = metaFrameFactory.getFrame();
+ ITreeIndexMetaDataFrame metaFrame = metaFrameFactory.getFrame();
IHyracksStageletContext ctx = TestUtils.create(HYRACKS_FRAME_SIZE);
ByteBuffer frame = ctx.allocateFrame();
@@ -146,7 +148,9 @@
MultiComparator cmp = new MultiComparator(typeTraits, cmps);
- BTree btree = new BTree(bufferCache, interiorFrameFactory,
+ IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, fileId, 0);
+
+ BTree btree = new BTree(bufferCache, freePageManager, interiorFrameFactory,
leafFrameFactory, cmp);
btree.create(fileId, leafFrame, metaFrame);
btree.open(fileId);
@@ -251,7 +255,9 @@
MultiComparator cmp = new MultiComparator(typeTraits, cmps);
- BTree btree = new BTree(bufferCache, interiorFrameFactory,
+ IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, fileId, 0);
+
+ BTree btree = new BTree(bufferCache, freePageManager, interiorFrameFactory,
leafFrameFactory, cmp);
btree.create(fileId, leafFrame, metaFrame);
btree.open(fileId);
@@ -358,7 +364,9 @@
MultiComparator cmp = new MultiComparator(typeTraits, cmps);
- BTree btree = new BTree(bufferCache, interiorFrameFactory,
+ IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, fileId, 0);
+
+ BTree btree = new BTree(bufferCache, freePageManager, interiorFrameFactory,
leafFrameFactory, cmp);
btree.create(fileId, leafFrame, metaFrame);
btree.open(fileId);
diff --git a/hyracks-tests/hyracks-storage-am-invertedindex-test/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/searchers/SimpleConjunctiveSearcherTest.java b/hyracks-tests/hyracks-storage-am-invertedindex-test/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/searchers/SimpleConjunctiveSearcherTest.java
index f61249b..f70092c 100644
--- a/hyracks-tests/hyracks-storage-am-invertedindex-test/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/searchers/SimpleConjunctiveSearcherTest.java
+++ b/hyracks-tests/hyracks-storage-am-invertedindex-test/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/searchers/SimpleConjunctiveSearcherTest.java
@@ -47,9 +47,6 @@
import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeInteriorFrameFactory;
import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeLeafFrame;
import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeLeafFrameFactory;
-import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeMetaDataFrame;
-import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeMetaDataFrameFactory;
-import edu.uci.ics.hyracks.storage.am.btree.frames.MetaDataFrameFactory;
import edu.uci.ics.hyracks.storage.am.btree.frames.NSMInteriorFrameFactory;
import edu.uci.ics.hyracks.storage.am.btree.frames.NSMLeafFrameFactory;
import edu.uci.ics.hyracks.storage.am.btree.impls.BTree;
@@ -57,6 +54,11 @@
import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeOpContext;
import edu.uci.ics.hyracks.storage.am.btree.impls.MultiComparator;
import edu.uci.ics.hyracks.storage.am.btree.tuples.TypeAwareTupleWriterFactory;
+import edu.uci.ics.hyracks.storage.am.common.api.IFreePageManager;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrame;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.frames.LIFOMetaDataFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.freepage.LinkedListFreePageManager;
import edu.uci.ics.hyracks.storage.am.invertedindex.api.IBinaryTokenizer;
import edu.uci.ics.hyracks.storage.am.invertedindex.api.IInvertedIndexResultCursor;
import edu.uci.ics.hyracks.storage.am.invertedindex.impls.SimpleConjunctiveSearcher;
@@ -124,13 +126,15 @@
// IBTreeLeafFrameFactory leafFrameFactory = new
// FieldPrefixNSMLeafFrameFactory(tupleWriterFactory);
IBTreeInteriorFrameFactory interiorFrameFactory = new NSMInteriorFrameFactory(tupleWriterFactory);
- IBTreeMetaDataFrameFactory metaFrameFactory = new MetaDataFrameFactory();
+ ITreeIndexMetaDataFrameFactory metaFrameFactory = new LIFOMetaDataFrameFactory();
IBTreeLeafFrame leafFrame = leafFrameFactory.getFrame();
IBTreeInteriorFrame interiorFrame = interiorFrameFactory.getFrame();
- IBTreeMetaDataFrame metaFrame = metaFrameFactory.getFrame();
+ ITreeIndexMetaDataFrame metaFrame = metaFrameFactory.getFrame();
- BTree btree = new BTree(bufferCache, interiorFrameFactory, leafFrameFactory, cmp);
+ IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, fileId, 0);
+
+ BTree btree = new BTree(bufferCache, freePageManager, interiorFrameFactory, leafFrameFactory, cmp);
btree.create(fileId, leafFrame, metaFrame);
btree.open(fileId);
@@ -188,7 +192,7 @@
}
}
- int numPages = btree.getMaxPage(metaFrame);
+ int numPages = btree.getFreePageManager().getMaxPage(metaFrame);
System.out.println("NUMPAGES: " + numPages);
// build query as tuple reference
diff --git a/pom.xml b/pom.xml
index 0b5ed07..619c635 100644
--- a/pom.xml
+++ b/pom.xml
@@ -61,6 +61,7 @@
<module>hyracks-control-nc</module>
<module>hyracks-cli</module>
<module>hyracks-storage-common</module>
+ <module>hyracks-storage-am-common</module>
<module>hyracks-storage-am-btree</module>
<module>hyracks-storage-am-invertedindex</module>
<module>hyracks-test-support</module>