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-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-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexMetaDataFrame.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexMetaDataFrame.java
new file mode 100644
index 0000000..bbd03d6
--- /dev/null
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexMetaDataFrame.java
@@ -0,0 +1,44 @@
+/*
+ * 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.common.api;
+
+import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
+
+public interface ITreeIndexMetaDataFrame {
+ 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-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexMetaDataFrameFactory.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexMetaDataFrameFactory.java
new file mode 100644
index 0000000..8c05637
--- /dev/null
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexMetaDataFrameFactory.java
@@ -0,0 +1,21 @@
+/*
+ * 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.common.api;
+
+
+public interface ITreeIndexMetaDataFrameFactory {
+ public ITreeIndexMetaDataFrame getFrame();
+}
\ No newline at end of file
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/frames/LIFOMetaDataFrame.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/frames/LIFOMetaDataFrame.java
new file mode 100644
index 0000000..759efc3
--- /dev/null
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/frames/LIFOMetaDataFrame.java
@@ -0,0 +1,114 @@
+/*
+ * 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.common.frames;
+
+import java.nio.ByteBuffer;
+
+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
+// 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 LIFOMetaDataFrame implements ITreeIndexMetaDataFrame {
+
+ 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-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/frames/LIFOMetaDataFrameFactory.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/frames/LIFOMetaDataFrameFactory.java
new file mode 100644
index 0000000..eb56987
--- /dev/null
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/frames/LIFOMetaDataFrameFactory.java
@@ -0,0 +1,26 @@
+/*
+ * 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.common.frames;
+
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrame;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrameFactory;
+
+public class LIFOMetaDataFrameFactory implements ITreeIndexMetaDataFrameFactory {
+ @Override
+ 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);
+ }
+ }
+
+}