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/api/IBTreeMetaDataFrame.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeMetaDataFrame.java
deleted file mode 100644
index 58739e2..0000000
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeMetaDataFrame.java
+++ /dev/null
@@ -1,44 +0,0 @@
-/*
- * Copyright 2009-2010 by The Regents of the University of California
- * Licensed 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 from
- *
- * 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.
- */
-
-package edu.uci.ics.hyracks.storage.am.btree.api;
-
-import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
-
-public interface IBTreeMetaDataFrame {
- public void initBuffer(int level);
-
- public void setPage(ICachedPage page);
-
- public ICachedPage getPage();
-
- public byte getLevel();
-
- public void setLevel(byte level);
-
- public int getNextPage();
-
- public void setNextPage(int nextPage);
-
- public int getMaxPage();
-
- public void setMaxPage(int maxPage);
-
- public int getFreePage();
-
- public boolean hasSpace();
-
- public void addFreePage(int freePage);
-}
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeMetaDataFrameFactory.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeMetaDataFrameFactory.java
deleted file mode 100644
index 2912cf9..0000000
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeMetaDataFrameFactory.java
+++ /dev/null
@@ -1,20 +0,0 @@
-/*
- * Copyright 2009-2010 by The Regents of the University of California
- * Licensed 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 from
- *
- * 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.
- */
-
-package edu.uci.ics.hyracks.storage.am.btree.api;
-
-public interface IBTreeMetaDataFrameFactory {
- public IBTreeMetaDataFrame getFrame();
-}
\ No newline at end of file
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/frames/MetaDataFrame.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/MetaDataFrame.java
deleted file mode 100644
index a219dd6..0000000
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/MetaDataFrame.java
+++ /dev/null
@@ -1,114 +0,0 @@
-/*
- * Copyright 2009-2010 by The Regents of the University of California
- * Licensed 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 from
- *
- * 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.
- */
-
-package edu.uci.ics.hyracks.storage.am.btree.frames;
-
-import java.nio.ByteBuffer;
-
-import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeMetaDataFrame;
-import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
-
-// all meta pages of this kind have a negative level
-// the first meta page has level -1, all other meta pages have level -2
-// 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 {
-
- protected static final int tupleCountOff = 0;
- protected static final int freeSpaceOff = tupleCountOff + 4;
- protected static final int maxPageOff = freeSpaceOff + 4;
- protected static final byte levelOff = maxPageOff + 1;
- protected static final byte nextPageOff = maxPageOff + 8;
-
- protected ICachedPage page = null;
- protected ByteBuffer buf = null;
-
- public int getMaxPage() {
- return buf.getInt(maxPageOff);
- }
-
- public void setMaxPage(int maxPage) {
- buf.putInt(maxPageOff, maxPage);
- }
-
- public int getFreePage() {
- int tupleCount = buf.getInt(tupleCountOff);
- if (tupleCount > 0) {
- // return the last page from the linked list of free pages
- // TODO: this is a dumb policy, but good enough for now
- int lastPageOff = buf.getInt(freeSpaceOff) - 4;
- buf.putInt(freeSpaceOff, lastPageOff);
- buf.putInt(tupleCountOff, tupleCount - 1);
- return buf.getInt(lastPageOff);
- } else {
- return -1;
- }
- }
-
- // must be checked before adding free page
- // user of this class is responsible for getting a free page as a new meta
- // page, latching it, etc. if there is no space on this page
- public boolean hasSpace() {
- return buf.getInt(freeSpaceOff) + 4 < buf.capacity();
- }
-
- // on bounds checking is done, there must be free space
- public void addFreePage(int freePage) {
- int freeSpace = buf.getInt(freeSpaceOff);
- buf.putInt(freeSpace, freePage);
- buf.putInt(freeSpaceOff, freeSpace + 4);
- buf.putInt(tupleCountOff, buf.getInt(tupleCountOff) + 1);
- }
-
- @Override
- public byte getLevel() {
- return buf.get(levelOff);
- }
-
- @Override
- public void setLevel(byte level) {
- buf.put(levelOff, level);
- }
-
- @Override
- public ICachedPage getPage() {
- return page;
- }
-
- @Override
- public void setPage(ICachedPage page) {
- this.page = page;
- this.buf = page.getBuffer();
- }
-
- @Override
- public void initBuffer(int level) {
- buf.putInt(freeSpaceOff, nextPageOff + 4);
- buf.putInt(tupleCountOff, 0);
- buf.putInt(levelOff, level);
- buf.putInt(nextPageOff, -1);
- }
-
- @Override
- public int getNextPage() {
- return buf.getInt(nextPageOff);
- }
-
- @Override
- public void setNextPage(int nextPage) {
- buf.putInt(nextPageOff, nextPage);
- }
-}
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/MetaDataFrameFactory.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/MetaDataFrameFactory.java
deleted file mode 100644
index 9896bf9..0000000
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/MetaDataFrameFactory.java
+++ /dev/null
@@ -1,26 +0,0 @@
-/*
- * Copyright 2009-2010 by The Regents of the University of California
- * Licensed 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 from
- *
- * 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.
- */
-
-package edu.uci.ics.hyracks.storage.am.btree.frames;
-
-import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeMetaDataFrame;
-import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeMetaDataFrameFactory;
-
-public class MetaDataFrameFactory implements IBTreeMetaDataFrameFactory {
- @Override
- public IBTreeMetaDataFrame getFrame() {
- return new MetaDataFrame();
- }
-}
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;