Merged hyracks_dev_next into trunk
git-svn-id: https://hyracks.googlecode.com/svn/trunk@531 123451ca-8445-de46-9d55-352943316053
diff --git a/hyracks/hyracks-storage-am-common/.classpath b/hyracks/hyracks-storage-am-common/.classpath
new file mode 100644
index 0000000..1f3c1ff
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/.classpath
@@ -0,0 +1,7 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<classpath>
+ <classpathentry kind="src" output="target/classes" path="src/main/java"/>
+ <classpathentry kind="con" path="org.eclipse.jdt.launching.JRE_CONTAINER/org.eclipse.jdt.internal.debug.ui.launcher.StandardVMType/JavaSE-1.6"/>
+ <classpathentry kind="con" path="org.maven.ide.eclipse.MAVEN2_CLASSPATH_CONTAINER"/>
+ <classpathentry kind="output" path="target/classes"/>
+</classpath>
diff --git a/hyracks/hyracks-storage-am-common/.project b/hyracks/hyracks-storage-am-common/.project
new file mode 100644
index 0000000..ec47f6b
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/.project
@@ -0,0 +1,23 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<projectDescription>
+ <name>hyracks-storage-am-common</name>
+ <comment></comment>
+ <projects>
+ </projects>
+ <buildSpec>
+ <buildCommand>
+ <name>org.eclipse.jdt.core.javabuilder</name>
+ <arguments>
+ </arguments>
+ </buildCommand>
+ <buildCommand>
+ <name>org.maven.ide.eclipse.maven2Builder</name>
+ <arguments>
+ </arguments>
+ </buildCommand>
+ </buildSpec>
+ <natures>
+ <nature>org.eclipse.jdt.core.javanature</nature>
+ <nature>org.maven.ide.eclipse.maven2Nature</nature>
+ </natures>
+</projectDescription>
diff --git a/hyracks/hyracks-storage-am-common/.settings/org.eclipse.jdt.core.prefs b/hyracks/hyracks-storage-am-common/.settings/org.eclipse.jdt.core.prefs
new file mode 100644
index 0000000..b37b3bb
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/.settings/org.eclipse.jdt.core.prefs
@@ -0,0 +1,6 @@
+#Thu Jul 07 12:23:56 PDT 2011
+eclipse.preferences.version=1
+org.eclipse.jdt.core.compiler.codegen.targetPlatform=1.6
+org.eclipse.jdt.core.compiler.compliance=1.6
+org.eclipse.jdt.core.compiler.problem.forbiddenReference=warning
+org.eclipse.jdt.core.compiler.source=1.6
diff --git a/hyracks/hyracks-storage-am-common/.settings/org.maven.ide.eclipse.prefs b/hyracks/hyracks-storage-am-common/.settings/org.maven.ide.eclipse.prefs
new file mode 100644
index 0000000..7b5e618
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/.settings/org.maven.ide.eclipse.prefs
@@ -0,0 +1,8 @@
+#Thu Jul 07 12:23:53 PDT 2011
+activeProfiles=
+eclipse.preferences.version=1
+fullBuildGoals=process-test-resources
+resolveWorkspaceProjects=true
+resourceFilterGoals=process-resources resources\:testResources
+skipCompilerPlugin=true
+version=1
diff --git a/hyracks/hyracks-storage-am-common/pom.xml b/hyracks/hyracks-storage-am-common/pom.xml
new file mode 100644
index 0000000..0d20126
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/pom.xml
@@ -0,0 +1,56 @@
+<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.7-SNAPSHOT</version>
+
+ <parent>
+ <groupId>edu.uci.ics.hyracks</groupId>
+ <artifactId>hyracks</artifactId>
+ <version>0.1.7-SNAPSHOT</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.7-SNAPSHOT</version>
+ <type>jar</type>
+ <scope>compile</scope>
+ </dependency>
+ <dependency>
+ <groupId>edu.uci.ics.hyracks</groupId>
+ <artifactId>hyracks-storage-common</artifactId>
+ <version>0.1.7-SNAPSHOT</version>
+ <type>jar</type>
+ <scope>compile</scope>
+ </dependency>
+ <dependency>
+ <groupId>edu.uci.ics.hyracks</groupId>
+ <artifactId>hyracks-dataflow-common</artifactId>
+ <version>0.1.7-SNAPSHOT</version>
+ <type>jar</type>
+ <scope>compile</scope>
+ </dependency>
+ <dependency>
+ <groupId>edu.uci.ics.hyracks</groupId>
+ <artifactId>hyracks-dataflow-std</artifactId>
+ <version>0.1.7-SNAPSHOT</version>
+ <type>jar</type>
+ <scope>compile</scope>
+ </dependency>
+ </dependencies>
+</project>
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ICursorInitialState.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ICursorInitialState.java
new file mode 100644
index 0000000..5f7c88d
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ICursorInitialState.java
@@ -0,0 +1,24 @@
+/*
+ * 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 ICursorInitialState {
+ public ICachedPage getPage();
+
+ public void setPage(ICachedPage page);
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/IFreePageManager.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/IFreePageManager.java
new file mode 100644
index 0000000..7abc0e3
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/IFreePageManager.java
@@ -0,0 +1,25 @@
+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;
+
+ public ITreeIndexMetaDataFrameFactory getMetaDataFrameFactory();
+
+ // required to return negative values
+ public byte getMetaPageLevelIndicator();
+
+ public byte getFreePageLevelIndicator();
+
+ // determined by examining level indicator
+ public boolean isMetaPage(ITreeIndexMetaDataFrame metaFrame);
+
+ public boolean isFreePage(ITreeIndexMetaDataFrame metaFrame);
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/IIndexBulkLoadContext.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/IIndexBulkLoadContext.java
new file mode 100644
index 0000000..a896d80
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/IIndexBulkLoadContext.java
@@ -0,0 +1,4 @@
+package edu.uci.ics.hyracks.storage.am.common.api;
+
+public interface IIndexBulkLoadContext {
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ISearchPredicate.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ISearchPredicate.java
new file mode 100644
index 0000000..f4836e0
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ISearchPredicate.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.api;
+
+import java.io.Serializable;
+
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+
+public interface ISearchPredicate extends Serializable {
+ public MultiComparator getLowKeyComparator();
+
+ public MultiComparator getHighKeyComparator();
+}
\ No newline at end of file
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ISlotManager.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ISlotManager.java
new file mode 100644
index 0000000..29646e7
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ISlotManager.java
@@ -0,0 +1,42 @@
+/*
+ * 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.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.FindTupleMode;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.FindTupleNoExactMatchPolicy;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+
+public interface ISlotManager {
+ public void setFrame(ITreeIndexFrame frame);
+
+ public int findTupleIndex(ITupleReference searchKey, ITreeIndexTupleReference frameTuple, MultiComparator multiCmp,
+ FindTupleMode mode, FindTupleNoExactMatchPolicy matchPolicy);
+
+ public int insertSlot(int tupleIndex, int tupleOff);
+
+ public int getSlotStartOff();
+
+ public int getSlotEndOff();
+
+ public int getTupleOff(int slotOff);
+
+ public void setSlot(int slotOff, int value);
+
+ public int getSlotOff(int tupleIndex);
+
+ public int getSlotSize();
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ISplitKey.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ISplitKey.java
new file mode 100644
index 0000000..246c09d
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ISplitKey.java
@@ -0,0 +1,25 @@
+package edu.uci.ics.hyracks.storage.am.common.api;
+
+import java.nio.ByteBuffer;
+
+public interface ISplitKey {
+ public void initData(int keySize);
+
+ public void reset();
+
+ public ByteBuffer getBuffer();
+
+ public ITreeIndexTupleReference getTuple();
+
+ public int getLeftPage();
+
+ public int getRightPage();
+
+ public void setLeftPage(int leftPage);
+
+ public void setRightPage(int rightPage);
+
+ public void setPages(int leftPage, int rightPage);
+
+ public ISplitKey duplicate(ITreeIndexTupleReference copyTuple);
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndex.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndex.java
new file mode 100644
index 0000000..2d77f06
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndex.java
@@ -0,0 +1,52 @@
+package edu.uci.ics.hyracks.storage.am.common.api;
+
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.IndexOp;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.IndexOpContext;
+
+public interface ITreeIndex {
+ // init:
+
+ public void create(int indexFileId, ITreeIndexFrame leafFrame, ITreeIndexMetaDataFrame metaFrame) throws Exception;
+
+ public void open(int indexFileId);
+
+ // operations:
+
+ public void insert(ITupleReference tuple, IndexOpContext ictx) throws Exception;
+
+ public void update(ITupleReference tuple, IndexOpContext ictx) throws Exception;
+
+ public void delete(ITupleReference tuple, IndexOpContext ictx) throws Exception;
+
+ public IndexOpContext createOpContext(IndexOp op, ITreeIndexFrame leafFrame, ITreeIndexFrame interiorFrame,
+ ITreeIndexMetaDataFrame metaFrame);
+
+ // bulk loading:
+
+ public IIndexBulkLoadContext beginBulkLoad(float fillFactor, ITreeIndexFrame leafFrame,
+ ITreeIndexFrame interiorFrame, ITreeIndexMetaDataFrame metaFrame) throws HyracksDataException;
+
+ public void bulkLoadAddTuple(IIndexBulkLoadContext ictx, ITupleReference tuple) throws HyracksDataException;
+
+ public void endBulkLoad(IIndexBulkLoadContext ictx) throws HyracksDataException;
+
+ // search:
+ public void diskOrderScan(ITreeIndexCursor icursor, ITreeIndexFrame leafFrame, ITreeIndexMetaDataFrame metaFrame,
+ IndexOpContext ictx) throws HyracksDataException;
+
+ // utility:
+
+ public IFreePageManager getFreePageManager();
+
+ public int getRootPageId();
+
+ public ITreeIndexFrameFactory getLeafFrameFactory();
+
+ public ITreeIndexFrameFactory getInteriorFrameFactory();
+
+ public int getFieldCount();
+
+ public IndexType getIndexType();
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexCursor.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexCursor.java
new file mode 100644
index 0000000..22b2b6f
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexCursor.java
@@ -0,0 +1,40 @@
+/*
+ * 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.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
+import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
+
+public interface ITreeIndexCursor {
+ public void reset();
+
+ public boolean hasNext() throws Exception;
+
+ public void next() throws Exception;
+
+ public void open(ICursorInitialState initialState, ISearchPredicate searchPred) throws Exception;
+
+ public ICachedPage getPage();
+
+ public void close() throws Exception;
+
+ public void setBufferCache(IBufferCache bufferCache);
+
+ public void setFileId(int fileId);
+
+ public ITupleReference getTuple();
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexFrame.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexFrame.java
new file mode 100644
index 0000000..246efe4
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexFrame.java
@@ -0,0 +1,104 @@
+/*
+ * 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 java.nio.ByteBuffer;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.storage.am.common.frames.FrameOpSpaceStatus;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
+
+public interface ITreeIndexFrame {
+ public void setPage(ICachedPage page);
+
+ public ICachedPage getPage();
+
+ public ByteBuffer getBuffer();
+
+ public int findTupleIndex(ITupleReference tuple, MultiComparator cmp) throws Exception;
+
+ public void insert(ITupleReference tuple, MultiComparator cmp, int tupleIndex) throws Exception;
+
+ public void update(int rid, ITupleReference tuple) throws Exception;
+
+ public void delete(ITupleReference tuple, MultiComparator cmp, boolean exactDelete) throws Exception;
+
+ // returns true if slots were modified, false otherwise
+ public boolean compact(MultiComparator cmp);
+
+ public boolean compress(MultiComparator cmp) throws HyracksDataException;
+
+ public void initBuffer(byte level);
+
+ public int getTupleCount();
+
+ // assumption: page must be write-latched at this point
+ public FrameOpSpaceStatus hasSpaceInsert(ITupleReference tuple, MultiComparator cmp);
+
+ public FrameOpSpaceStatus hasSpaceUpdate(int rid, ITupleReference tuple, MultiComparator cmp);
+
+ public int getTupleOffset(int slotNum);
+
+ public int getTotalFreeSpace();
+
+ public void setPageLsn(int pageLsn);
+
+ public int getPageLsn();
+
+ // for debugging
+ public void printHeader();
+
+ public String printKeys(MultiComparator cmp, ISerializerDeserializer[] fields) throws HyracksDataException;
+
+ // TODO; what if tuples more than half-page size?
+ public int split(ITreeIndexFrame rightFrame, ITupleReference tuple, MultiComparator cmp, ISplitKey splitKey)
+ throws Exception;
+
+ public ISlotManager getSlotManager();
+
+ // ATTENTION: in b-tree operations it may not always be possible to
+ // determine whether an ICachedPage is a leaf or interior node
+ // a compatible interior and leaf implementation MUST return identical
+ // values when given the same ByteBuffer for the functions below
+ public boolean isLeaf();
+
+ public boolean isInterior();
+
+ public byte getLevel();
+
+ public void setLevel(byte level);
+
+ public boolean getSmFlag(); // structure modification flag
+
+ public void setSmFlag(boolean smFlag);
+
+ public int getSlotSize();
+
+ // TODO: should be removed after new tuple format
+ public void setPageTupleFieldCount(int fieldCount);
+
+ // for debugging
+ public int getFreeSpaceOff();
+
+ public void setFreeSpaceOff(int freeSpace);
+
+ public ITreeIndexTupleWriter getTupleWriter();
+
+ public int getPageHeaderSize();
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexFrameFactory.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexFrameFactory.java
new file mode 100644
index 0000000..83b95b6
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexFrameFactory.java
@@ -0,0 +1,7 @@
+package edu.uci.ics.hyracks.storage.am.common.api;
+
+import java.io.Serializable;
+
+public interface ITreeIndexFrameFactory extends Serializable {
+ public ITreeIndexFrame createFrame();
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexMetaDataFrame.java b/hyracks/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/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/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexMetaDataFrameFactory.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexMetaDataFrameFactory.java
new file mode 100644
index 0000000..6fd88e8
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexMetaDataFrameFactory.java
@@ -0,0 +1,20 @@
+/*
+ * 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 createFrame();
+}
\ No newline at end of file
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexTupleReference.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexTupleReference.java
new file mode 100644
index 0000000..d2c2df4
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexTupleReference.java
@@ -0,0 +1,30 @@
+/*
+ * 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 java.nio.ByteBuffer;
+
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+
+public interface ITreeIndexTupleReference extends ITupleReference {
+ public void setFieldCount(int fieldCount);
+
+ public void setFieldCount(int fieldStartIndex, int fieldCount);
+
+ public void resetByTupleOffset(ByteBuffer buf, int tupleStartOffset);
+
+ public void resetByTupleIndex(ITreeIndexFrame frame, int tupleIndex);
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexTupleWriter.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexTupleWriter.java
new file mode 100644
index 0000000..39577ea
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexTupleWriter.java
@@ -0,0 +1,37 @@
+/*
+ * 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 java.nio.ByteBuffer;
+
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+
+public interface ITreeIndexTupleWriter {
+ public int writeTuple(ITupleReference tuple, ByteBuffer targetBuf, int targetOff);
+
+ public int bytesRequired(ITupleReference tuple);
+
+ public int writeTupleFields(ITupleReference tuple, int startField, int numFields, ByteBuffer targetBuf,
+ int targetOff);
+
+ public int bytesRequired(ITupleReference tuple, int startField, int numFields);
+
+ // return a tuplereference instance that can read the tuple written by this
+ // writer
+ // the main idea is that the format of the written tuple may not be the same
+ // as the format written by this writer
+ public ITreeIndexTupleReference createTupleReference();
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexTupleWriterFactory.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexTupleWriterFactory.java
new file mode 100644
index 0000000..bd7bfda
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexTupleWriterFactory.java
@@ -0,0 +1,22 @@
+/*
+ * 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 java.io.Serializable;
+
+public interface ITreeIndexTupleWriterFactory extends Serializable {
+ public ITreeIndexTupleWriter createTupleWriter();
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/IndexType.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/IndexType.java
new file mode 100644
index 0000000..d5f9f44
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/IndexType.java
@@ -0,0 +1,5 @@
+package edu.uci.ics.hyracks.storage.am.common.api;
+
+public enum IndexType {
+ BTREE, RTREE, INVERTED
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/TreeIndexException.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/TreeIndexException.java
new file mode 100644
index 0000000..ad3db58
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/TreeIndexException.java
@@ -0,0 +1,38 @@
+/*
+ * 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 class TreeIndexException extends Exception {
+
+ private static final long serialVersionUID = 1L;
+ private boolean handled = false;
+
+ public TreeIndexException(Exception e) {
+ super(e);
+ }
+
+ public TreeIndexException(String message) {
+ super(message);
+ }
+
+ public void setHandled(boolean handled) {
+ this.handled = handled;
+ }
+
+ public boolean getHandled() {
+ return handled;
+ }
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/AbstractTreeIndexOperatorDescriptor.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/AbstractTreeIndexOperatorDescriptor.java
new file mode 100644
index 0000000..c905eb2
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/AbstractTreeIndexOperatorDescriptor.java
@@ -0,0 +1,110 @@
+/*
+ * 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.dataflow;
+
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTrait;
+import edu.uci.ics.hyracks.api.dataflow.value.RecordDescriptor;
+import edu.uci.ics.hyracks.api.job.JobSpecification;
+import edu.uci.ics.hyracks.dataflow.std.base.AbstractSingleActivityOperatorDescriptor;
+import edu.uci.ics.hyracks.dataflow.std.file.IFileSplitProvider;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
+import edu.uci.ics.hyracks.storage.common.IStorageManagerInterface;
+
+public abstract class AbstractTreeIndexOperatorDescriptor extends AbstractSingleActivityOperatorDescriptor implements
+ ITreeIndexOperatorDescriptorHelper {
+
+ private static final long serialVersionUID = 1L;
+
+ protected final IFileSplitProvider fileSplitProvider;
+
+ protected final IBinaryComparatorFactory[] comparatorFactories;
+
+ protected final ITreeIndexFrameFactory interiorFrameFactory;
+ protected final ITreeIndexFrameFactory leafFrameFactory;
+
+ protected final IStorageManagerInterface storageManager;
+ protected final IIndexRegistryProvider<ITreeIndex> treeIndexRegistryProvider;
+
+ protected final ITypeTrait[] typeTraits;
+
+ protected final ITreeIndexOpHelperFactory opHelperFactory;
+
+ public AbstractTreeIndexOperatorDescriptor(JobSpecification spec, int inputArity, int outputArity,
+ RecordDescriptor recDesc, IStorageManagerInterface storageManager,
+ IIndexRegistryProvider<ITreeIndex> treeIndexRegistryProvider, IFileSplitProvider fileSplitProvider,
+ ITreeIndexFrameFactory interiorFrameFactory, ITreeIndexFrameFactory leafFrameFactory,
+ ITypeTrait[] typeTraits, IBinaryComparatorFactory[] comparatorFactories,
+ ITreeIndexOpHelperFactory opHelperFactory) {
+ super(spec, inputArity, outputArity);
+ this.fileSplitProvider = fileSplitProvider;
+ this.storageManager = storageManager;
+ this.treeIndexRegistryProvider = treeIndexRegistryProvider;
+ this.interiorFrameFactory = interiorFrameFactory;
+ this.leafFrameFactory = leafFrameFactory;
+ this.typeTraits = typeTraits;
+ this.comparatorFactories = comparatorFactories;
+ this.opHelperFactory = opHelperFactory;
+ if (outputArity > 0)
+ recordDescriptors[0] = recDesc;
+ }
+
+ @Override
+ public IFileSplitProvider getTreeIndexFileSplitProvider() {
+ return fileSplitProvider;
+ }
+
+ @Override
+ public IBinaryComparatorFactory[] getTreeIndexComparatorFactories() {
+ return comparatorFactories;
+ }
+
+ @Override
+ public ITypeTrait[] getTreeIndexTypeTraits() {
+ return typeTraits;
+ }
+
+ @Override
+ public ITreeIndexFrameFactory getTreeIndexInteriorFactory() {
+ return interiorFrameFactory;
+ }
+
+ @Override
+ public ITreeIndexFrameFactory getTreeIndexLeafFactory() {
+ return leafFrameFactory;
+ }
+
+ @Override
+ public IStorageManagerInterface getStorageManager() {
+ return storageManager;
+ }
+
+ @Override
+ public IIndexRegistryProvider<ITreeIndex> getTreeIndexRegistryProvider() {
+ return treeIndexRegistryProvider;
+ }
+
+ @Override
+ public RecordDescriptor getRecordDescriptor() {
+ return recordDescriptors[0];
+ }
+
+ @Override
+ public ITreeIndexOpHelperFactory getTreeIndexOpHelperFactory() {
+ return opHelperFactory;
+ }
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/IIndexRegistryProvider.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/IIndexRegistryProvider.java
new file mode 100644
index 0000000..aadcaf9
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/IIndexRegistryProvider.java
@@ -0,0 +1,24 @@
+/*
+ * 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.dataflow;
+
+import java.io.Serializable;
+
+import edu.uci.ics.hyracks.api.context.IHyracksStageletContext;
+
+public interface IIndexRegistryProvider<IndexType> extends Serializable {
+ public IndexRegistry<IndexType> getRegistry(IHyracksStageletContext ctx);
+}
\ No newline at end of file
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/ITreeIndexOpHelperFactory.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/ITreeIndexOpHelperFactory.java
new file mode 100644
index 0000000..fa37fab
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/ITreeIndexOpHelperFactory.java
@@ -0,0 +1,10 @@
+package edu.uci.ics.hyracks.storage.am.common.dataflow;
+
+import java.io.Serializable;
+
+import edu.uci.ics.hyracks.api.context.IHyracksStageletContext;
+
+public interface ITreeIndexOpHelperFactory extends Serializable {
+ public TreeIndexOpHelper createTreeIndexOpHelper(ITreeIndexOperatorDescriptorHelper opDesc,
+ final IHyracksStageletContext ctx, int partition, IndexHelperOpenMode mode);
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/ITreeIndexOperatorDescriptorHelper.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/ITreeIndexOperatorDescriptorHelper.java
new file mode 100644
index 0000000..6ca4529
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/ITreeIndexOperatorDescriptorHelper.java
@@ -0,0 +1,30 @@
+package edu.uci.ics.hyracks.storage.am.common.dataflow;
+
+import edu.uci.ics.hyracks.api.dataflow.IActivityNode;
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTrait;
+import edu.uci.ics.hyracks.api.dataflow.value.RecordDescriptor;
+import edu.uci.ics.hyracks.dataflow.std.file.IFileSplitProvider;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
+import edu.uci.ics.hyracks.storage.common.IStorageManagerInterface;
+
+public interface ITreeIndexOperatorDescriptorHelper extends IActivityNode {
+ public IFileSplitProvider getTreeIndexFileSplitProvider();
+
+ public IBinaryComparatorFactory[] getTreeIndexComparatorFactories();
+
+ public ITypeTrait[] getTreeIndexTypeTraits();
+
+ public ITreeIndexFrameFactory getTreeIndexInteriorFactory();
+
+ public ITreeIndexFrameFactory getTreeIndexLeafFactory();
+
+ public IStorageManagerInterface getStorageManager();
+
+ public IIndexRegistryProvider<ITreeIndex> getTreeIndexRegistryProvider();
+
+ public RecordDescriptor getRecordDescriptor();
+
+ public ITreeIndexOpHelperFactory getTreeIndexOpHelperFactory();
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/IndexHelperOpenMode.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/IndexHelperOpenMode.java
new file mode 100644
index 0000000..aa41184
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/IndexHelperOpenMode.java
@@ -0,0 +1,5 @@
+package edu.uci.ics.hyracks.storage.am.common.dataflow;
+
+public enum IndexHelperOpenMode {
+ OPEN, CREATE, ENLIST
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/IndexRegistry.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/IndexRegistry.java
new file mode 100644
index 0000000..de00d5a
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/IndexRegistry.java
@@ -0,0 +1,53 @@
+/*
+ * 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.dataflow;
+
+import java.util.HashMap;
+import java.util.concurrent.locks.Lock;
+import java.util.concurrent.locks.ReentrantLock;
+
+public class IndexRegistry<IndexType> {
+
+ private HashMap<Integer, IndexType> map = new HashMap<Integer, IndexType>();
+ private Lock registryLock = new ReentrantLock();
+
+ public IndexType get(int fileId) {
+ return map.get(fileId);
+ }
+
+ public void lock() {
+ registryLock.lock();
+ }
+
+ public void unlock() {
+ registryLock.unlock();
+ }
+
+ public void register(int fileId, IndexType index) {
+ map.put(fileId, index);
+ }
+
+ public void unregister(int fileId) {
+ try {
+ map.remove(fileId);
+ } catch (Exception e) {
+ }
+ }
+
+ public int size() {
+ return map.size();
+ }
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/PermutingFrameTupleReference.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/PermutingFrameTupleReference.java
new file mode 100644
index 0000000..3db9db2
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/PermutingFrameTupleReference.java
@@ -0,0 +1,65 @@
+/*
+ * 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.dataflow;
+
+import edu.uci.ics.hyracks.api.comm.IFrameTupleAccessor;
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.IFrameTupleReference;
+
+public class PermutingFrameTupleReference implements IFrameTupleReference {
+ private IFrameTupleAccessor fta;
+ private int tIndex;
+ private int[] fieldPermutation;
+
+ public void setFieldPermutation(int[] fieldPermutation) {
+ this.fieldPermutation = fieldPermutation;
+ }
+
+ public void reset(IFrameTupleAccessor fta, int tIndex) {
+ this.fta = fta;
+ this.tIndex = tIndex;
+ }
+
+ @Override
+ public IFrameTupleAccessor getFrameTupleAccessor() {
+ return fta;
+ }
+
+ @Override
+ public int getTupleIndex() {
+ return tIndex;
+ }
+
+ @Override
+ public int getFieldCount() {
+ return fieldPermutation.length;
+ }
+
+ @Override
+ public byte[] getFieldData(int fIdx) {
+ return fta.getBuffer().array();
+ }
+
+ @Override
+ public int getFieldStart(int fIdx) {
+ return fta.getTupleStartOffset(tIndex) + fta.getFieldSlotsLength()
+ + fta.getFieldStartOffset(tIndex, fieldPermutation[fIdx]);
+ }
+
+ @Override
+ public int getFieldLength(int fIdx) {
+ return fta.getFieldLength(tIndex, fieldPermutation[fIdx]);
+ }
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexBulkLoadOperatorDescriptor.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexBulkLoadOperatorDescriptor.java
new file mode 100644
index 0000000..7d585b3
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexBulkLoadOperatorDescriptor.java
@@ -0,0 +1,54 @@
+/*
+ * 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.dataflow;
+
+import edu.uci.ics.hyracks.api.context.IHyracksStageletContext;
+import edu.uci.ics.hyracks.api.dataflow.IOperatorNodePushable;
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+import edu.uci.ics.hyracks.api.dataflow.value.IRecordDescriptorProvider;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTrait;
+import edu.uci.ics.hyracks.api.job.IOperatorEnvironment;
+import edu.uci.ics.hyracks.api.job.JobSpecification;
+import edu.uci.ics.hyracks.dataflow.std.file.IFileSplitProvider;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
+import edu.uci.ics.hyracks.storage.common.IStorageManagerInterface;
+
+public class TreeIndexBulkLoadOperatorDescriptor extends AbstractTreeIndexOperatorDescriptor {
+
+ private static final long serialVersionUID = 1L;
+
+ private final int[] fieldPermutation;
+ private final float fillFactor;
+
+ public TreeIndexBulkLoadOperatorDescriptor(JobSpecification spec, IStorageManagerInterface storageManager,
+ IIndexRegistryProvider<ITreeIndex> treeIndexRegistryProvider, IFileSplitProvider fileSplitProvider,
+ ITreeIndexFrameFactory interiorFrameFactory, ITreeIndexFrameFactory leafFrameFactory,
+ ITypeTrait[] typeTraits, IBinaryComparatorFactory[] comparatorFactories, int[] fieldPermutation,
+ float fillFactor, ITreeIndexOpHelperFactory opHelperFactory) {
+ super(spec, 1, 0, null, storageManager, treeIndexRegistryProvider, fileSplitProvider, interiorFrameFactory,
+ leafFrameFactory, typeTraits, comparatorFactories, opHelperFactory);
+ this.fieldPermutation = fieldPermutation;
+ this.fillFactor = fillFactor;
+ }
+
+ @Override
+ public IOperatorNodePushable createPushRuntime(IHyracksStageletContext ctx, IOperatorEnvironment env,
+ IRecordDescriptorProvider recordDescProvider, int partition, int nPartitions) {
+ return new TreeIndexBulkLoadOperatorNodePushable(this, ctx, partition, fieldPermutation, fillFactor,
+ recordDescProvider);
+ }
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexBulkLoadOperatorNodePushable.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexBulkLoadOperatorNodePushable.java
new file mode 100644
index 0000000..2001039
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexBulkLoadOperatorNodePushable.java
@@ -0,0 +1,90 @@
+/*
+ * 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.dataflow;
+
+import java.nio.ByteBuffer;
+
+import edu.uci.ics.hyracks.api.context.IHyracksStageletContext;
+import edu.uci.ics.hyracks.api.dataflow.value.IRecordDescriptorProvider;
+import edu.uci.ics.hyracks.api.dataflow.value.RecordDescriptor;
+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.common.api.IIndexBulkLoadContext;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrame;
+import edu.uci.ics.hyracks.storage.am.common.frames.LIFOMetaDataFrame;
+
+public class TreeIndexBulkLoadOperatorNodePushable extends AbstractUnaryInputSinkOperatorNodePushable {
+ private float fillFactor;
+ private final TreeIndexOpHelper treeIndexOpHelper;
+ private FrameTupleAccessor accessor;
+ private IIndexBulkLoadContext bulkLoadCtx;
+
+ private IRecordDescriptorProvider recordDescProvider;
+
+ private PermutingFrameTupleReference tuple = new PermutingFrameTupleReference();
+
+ public TreeIndexBulkLoadOperatorNodePushable(AbstractTreeIndexOperatorDescriptor opDesc,
+ IHyracksStageletContext ctx, int partition, int[] fieldPermutation, float fillFactor,
+ IRecordDescriptorProvider recordDescProvider) {
+ treeIndexOpHelper = opDesc.getTreeIndexOpHelperFactory().createTreeIndexOpHelper(opDesc, ctx, partition,
+ IndexHelperOpenMode.CREATE);
+ this.fillFactor = fillFactor;
+ this.recordDescProvider = recordDescProvider;
+ tuple.setFieldPermutation(fieldPermutation);
+ }
+
+ @Override
+ public void open() throws HyracksDataException {
+ AbstractTreeIndexOperatorDescriptor opDesc = (AbstractTreeIndexOperatorDescriptor) treeIndexOpHelper
+ .getOperatorDescriptor();
+ RecordDescriptor recDesc = recordDescProvider.getInputRecordDescriptor(opDesc.getOperatorId(), 0);
+ accessor = new FrameTupleAccessor(treeIndexOpHelper.getHyracksStageletContext().getFrameSize(), recDesc);
+ ITreeIndexMetaDataFrame metaFrame = new LIFOMetaDataFrame();
+ try {
+ treeIndexOpHelper.init();
+ treeIndexOpHelper.getTreeIndex().open(treeIndexOpHelper.getIndexFileId());
+ bulkLoadCtx = treeIndexOpHelper.getTreeIndex().beginBulkLoad(fillFactor, treeIndexOpHelper.getLeafFrame(),
+ treeIndexOpHelper.getInteriorFrame(), metaFrame);
+ } catch (Exception e) {
+ // cleanup in case of failure
+ treeIndexOpHelper.deinit();
+ throw new HyracksDataException(e);
+ }
+ }
+
+ @Override
+ public void nextFrame(ByteBuffer buffer) throws HyracksDataException {
+ accessor.reset(buffer);
+ int tupleCount = accessor.getTupleCount();
+ for (int i = 0; i < tupleCount; i++) {
+ tuple.reset(accessor, i);
+ treeIndexOpHelper.getTreeIndex().bulkLoadAddTuple(bulkLoadCtx, tuple);
+ }
+ }
+
+ @Override
+ public void close() throws HyracksDataException {
+ try {
+ treeIndexOpHelper.getTreeIndex().endBulkLoad(bulkLoadCtx);
+ } finally {
+ treeIndexOpHelper.deinit();
+ }
+ }
+
+ @Override
+ public void flush() throws HyracksDataException {
+ }
+}
\ No newline at end of file
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexDiskOrderScanOperatorDescriptor.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexDiskOrderScanOperatorDescriptor.java
new file mode 100644
index 0000000..73b5323
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexDiskOrderScanOperatorDescriptor.java
@@ -0,0 +1,47 @@
+/*
+ * 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.dataflow;
+
+import edu.uci.ics.hyracks.api.context.IHyracksStageletContext;
+import edu.uci.ics.hyracks.api.dataflow.IOperatorNodePushable;
+import edu.uci.ics.hyracks.api.dataflow.value.IRecordDescriptorProvider;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTrait;
+import edu.uci.ics.hyracks.api.dataflow.value.RecordDescriptor;
+import edu.uci.ics.hyracks.api.job.IOperatorEnvironment;
+import edu.uci.ics.hyracks.api.job.JobSpecification;
+import edu.uci.ics.hyracks.dataflow.std.file.IFileSplitProvider;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
+import edu.uci.ics.hyracks.storage.common.IStorageManagerInterface;
+
+public class TreeIndexDiskOrderScanOperatorDescriptor extends AbstractTreeIndexOperatorDescriptor {
+
+ private static final long serialVersionUID = 1L;
+
+ public TreeIndexDiskOrderScanOperatorDescriptor(JobSpecification spec, RecordDescriptor recDesc,
+ IStorageManagerInterface storageManager, IIndexRegistryProvider<ITreeIndex> treeIndexRegistryProvider,
+ IFileSplitProvider fileSplitProvider, ITreeIndexFrameFactory interiorFrameFactory,
+ ITreeIndexFrameFactory leafFrameFactory, ITypeTrait[] typeTraits, ITreeIndexOpHelperFactory opHelperFactory) {
+ super(spec, 0, 1, recDesc, storageManager, treeIndexRegistryProvider, fileSplitProvider, interiorFrameFactory,
+ leafFrameFactory, typeTraits, null, opHelperFactory);
+ }
+
+ @Override
+ public IOperatorNodePushable createPushRuntime(IHyracksStageletContext ctx, IOperatorEnvironment env,
+ IRecordDescriptorProvider recordDescProvider, int partition, int nPartitions) {
+ return new TreeIndexDiskOrderScanOperatorNodePushable(this, ctx, partition);
+ }
+}
\ No newline at end of file
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexDiskOrderScanOperatorNodePushable.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexDiskOrderScanOperatorNodePushable.java
new file mode 100644
index 0000000..415b9e3
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexDiskOrderScanOperatorNodePushable.java
@@ -0,0 +1,104 @@
+/*
+ * 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.dataflow;
+
+import java.io.DataOutput;
+import java.nio.ByteBuffer;
+
+import edu.uci.ics.hyracks.api.context.IHyracksStageletContext;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.dataflow.common.comm.io.ArrayTupleBuilder;
+import edu.uci.ics.hyracks.dataflow.common.comm.io.FrameTupleAppender;
+import edu.uci.ics.hyracks.dataflow.common.comm.util.FrameUtils;
+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.common.api.ITreeIndexCursor;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrame;
+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.ophelpers.IndexOp;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.IndexOpContext;
+
+public class TreeIndexDiskOrderScanOperatorNodePushable extends AbstractUnaryOutputSourceOperatorNodePushable {
+ private final TreeIndexOpHelper treeIndexOpHelper;
+
+ public TreeIndexDiskOrderScanOperatorNodePushable(AbstractTreeIndexOperatorDescriptor opDesc,
+ IHyracksStageletContext ctx, int partition) {
+ treeIndexOpHelper = opDesc.getTreeIndexOpHelperFactory().createTreeIndexOpHelper(opDesc, ctx, partition,
+ IndexHelperOpenMode.OPEN);
+ }
+
+ @Override
+ public void initialize() throws HyracksDataException {
+
+ ITreeIndexFrame cursorFrame = treeIndexOpHelper.getOperatorDescriptor().getTreeIndexLeafFactory().createFrame();
+ ITreeIndexCursor cursor = treeIndexOpHelper.createDiskOrderScanCursor(cursorFrame);
+ ITreeIndexMetaDataFrame metaFrame = new LIFOMetaDataFrame();
+
+ IndexOpContext diskOrderScanOpCtx = treeIndexOpHelper.getTreeIndex().createOpContext(IndexOp.DISKORDERSCAN,
+ cursorFrame, null, null);
+ try {
+
+ treeIndexOpHelper.init();
+
+ try {
+ treeIndexOpHelper.getTreeIndex().diskOrderScan(cursor, cursorFrame, metaFrame, diskOrderScanOpCtx);
+
+ int fieldCount = treeIndexOpHelper.getTreeIndex().getFieldCount();
+ ByteBuffer frame = treeIndexOpHelper.getHyracksStageletContext().allocateFrame();
+ FrameTupleAppender appender = new FrameTupleAppender(treeIndexOpHelper.getHyracksStageletContext()
+ .getFrameSize());
+ appender.reset(frame, true);
+ ArrayTupleBuilder tb = new ArrayTupleBuilder(fieldCount);
+ DataOutput dos = tb.getDataOutput();
+
+ while (cursor.hasNext()) {
+ tb.reset();
+ cursor.next();
+
+ ITupleReference frameTuple = cursor.getTuple();
+ for (int i = 0; i < frameTuple.getFieldCount(); i++) {
+ dos.write(frameTuple.getFieldData(i), frameTuple.getFieldStart(i), frameTuple.getFieldLength(i));
+ tb.addFieldEndOffset();
+ }
+
+ if (!appender.append(tb.getFieldEndOffsets(), tb.getByteArray(), 0, tb.getSize())) {
+ FrameUtils.flushFrame(frame, writer);
+ appender.reset(frame, true);
+ if (!appender.append(tb.getFieldEndOffsets(), tb.getByteArray(), 0, tb.getSize())) {
+ throw new IllegalStateException();
+ }
+ }
+ }
+
+ if (appender.getTupleCount() > 0) {
+ FrameUtils.flushFrame(frame, writer);
+ }
+ } finally {
+ cursor.close();
+ writer.close();
+ }
+
+ } catch (Exception e) {
+ deinitialize();
+ throw new HyracksDataException(e);
+ }
+ }
+
+ @Override
+ public void deinitialize() throws HyracksDataException {
+ treeIndexOpHelper.deinit();
+ }
+}
\ No newline at end of file
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexDropOperatorDescriptor.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexDropOperatorDescriptor.java
new file mode 100644
index 0000000..2cfa905
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexDropOperatorDescriptor.java
@@ -0,0 +1,50 @@
+/*
+ * 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.dataflow;
+
+import edu.uci.ics.hyracks.api.context.IHyracksStageletContext;
+import edu.uci.ics.hyracks.api.dataflow.IOperatorNodePushable;
+import edu.uci.ics.hyracks.api.dataflow.value.IRecordDescriptorProvider;
+import edu.uci.ics.hyracks.api.job.IOperatorEnvironment;
+import edu.uci.ics.hyracks.api.job.JobSpecification;
+import edu.uci.ics.hyracks.dataflow.std.base.AbstractSingleActivityOperatorDescriptor;
+import edu.uci.ics.hyracks.dataflow.std.file.IFileSplitProvider;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
+import edu.uci.ics.hyracks.storage.common.IStorageManagerInterface;
+
+public class TreeIndexDropOperatorDescriptor extends AbstractSingleActivityOperatorDescriptor {
+
+ private static final long serialVersionUID = 1L;
+
+ private IStorageManagerInterface storageManager;
+ private IIndexRegistryProvider<ITreeIndex> treeIndexRegistryProvider;
+ private IFileSplitProvider fileSplitProvider;
+
+ public TreeIndexDropOperatorDescriptor(JobSpecification spec, IStorageManagerInterface storageManager,
+ IIndexRegistryProvider<ITreeIndex> treeIndexRegistryProvider, IFileSplitProvider fileSplitProvider) {
+ super(spec, 0, 0);
+ this.storageManager = storageManager;
+ this.treeIndexRegistryProvider = treeIndexRegistryProvider;
+ this.fileSplitProvider = fileSplitProvider;
+ }
+
+ @Override
+ public IOperatorNodePushable createPushRuntime(IHyracksStageletContext ctx, IOperatorEnvironment env,
+ IRecordDescriptorProvider recordDescProvider, int partition, int nPartitions) {
+ return new TreeIndexDropOperatorNodePushable(ctx, storageManager, treeIndexRegistryProvider, fileSplitProvider,
+ partition);
+ }
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexDropOperatorNodePushable.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexDropOperatorNodePushable.java
new file mode 100644
index 0000000..71346f7
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexDropOperatorNodePushable.java
@@ -0,0 +1,108 @@
+/*
+ * 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.dataflow;
+
+import java.util.logging.Level;
+import java.util.logging.Logger;
+
+import edu.uci.ics.hyracks.api.comm.IFrameWriter;
+import edu.uci.ics.hyracks.api.context.IHyracksStageletContext;
+import edu.uci.ics.hyracks.api.dataflow.value.RecordDescriptor;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.api.io.FileReference;
+import edu.uci.ics.hyracks.dataflow.std.base.AbstractOperatorNodePushable;
+import edu.uci.ics.hyracks.dataflow.std.file.IFileSplitProvider;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
+import edu.uci.ics.hyracks.storage.common.IStorageManagerInterface;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
+import edu.uci.ics.hyracks.storage.common.file.IFileMapProvider;
+
+public class TreeIndexDropOperatorNodePushable extends AbstractOperatorNodePushable {
+ private static final Logger LOGGER = Logger.getLogger(TreeIndexDropOperatorNodePushable.class.getName());
+
+ private final IHyracksStageletContext ctx;
+ private IIndexRegistryProvider<ITreeIndex> treeIndexRegistryProvider;
+ private IStorageManagerInterface storageManager;
+ private IFileSplitProvider fileSplitProvider;
+ private int partition;
+
+ public TreeIndexDropOperatorNodePushable(IHyracksStageletContext ctx, IStorageManagerInterface storageManager,
+ IIndexRegistryProvider<ITreeIndex> treeIndexRegistryProvider, IFileSplitProvider fileSplitProvider,
+ int partition) {
+ this.ctx = ctx;
+ this.storageManager = storageManager;
+ this.treeIndexRegistryProvider = treeIndexRegistryProvider;
+ this.fileSplitProvider = fileSplitProvider;
+ this.partition = partition;
+ }
+
+ @Override
+ public void deinitialize() throws HyracksDataException {
+ }
+
+ @Override
+ public int getInputArity() {
+ return 0;
+ }
+
+ @Override
+ public IFrameWriter getInputFrameWriter(int index) {
+ return null;
+ }
+
+ @Override
+ public void initialize() throws HyracksDataException {
+ try {
+
+ IndexRegistry<ITreeIndex> treeIndexRegistry = treeIndexRegistryProvider.getRegistry(ctx);
+ IBufferCache bufferCache = storageManager.getBufferCache(ctx);
+ IFileMapProvider fileMapProvider = storageManager.getFileMapProvider(ctx);
+
+ FileReference f = fileSplitProvider.getFileSplits()[partition].getLocalFile();
+
+ boolean fileIsMapped = fileMapProvider.isMapped(f);
+ if (!fileIsMapped) {
+ throw new HyracksDataException("Cannot drop Tree with name " + f.toString()
+ + ". No file mapping exists.");
+ }
+
+ int indexFileId = fileMapProvider.lookupFileId(f);
+
+ // unregister tree instance
+ treeIndexRegistry.lock();
+ try {
+ treeIndexRegistry.unregister(indexFileId);
+ } finally {
+ treeIndexRegistry.unlock();
+ }
+
+ // remove name to id mapping
+ bufferCache.deleteFile(indexFileId);
+ }
+ // TODO: for the time being we don't throw,
+ // with proper exception handling (no hanging job problem) we should
+ // throw
+ catch (Exception e) {
+ if (LOGGER.isLoggable(Level.WARNING)) {
+ LOGGER.warning("Tree Drop Operator Failed Due To Exception: " + e.getMessage());
+ }
+ }
+ }
+
+ @Override
+ public void setOutputFrameWriter(int index, IFrameWriter writer, RecordDescriptor recordDesc) {
+ }
+}
\ No newline at end of file
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexFileEnlistmentOperatorDescriptor.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexFileEnlistmentOperatorDescriptor.java
new file mode 100644
index 0000000..0961a4f
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexFileEnlistmentOperatorDescriptor.java
@@ -0,0 +1,56 @@
+/*
+ * 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.dataflow;
+
+import edu.uci.ics.hyracks.api.context.IHyracksStageletContext;
+import edu.uci.ics.hyracks.api.dataflow.IOperatorNodePushable;
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+import edu.uci.ics.hyracks.api.dataflow.value.IRecordDescriptorProvider;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTrait;
+import edu.uci.ics.hyracks.api.dataflow.value.RecordDescriptor;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.api.job.IOperatorEnvironment;
+import edu.uci.ics.hyracks.api.job.JobSpecification;
+import edu.uci.ics.hyracks.dataflow.std.file.IFileSplitProvider;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
+import edu.uci.ics.hyracks.storage.common.IStorageManagerInterface;
+
+// re-create in-memory state for a tree index that has already been built (i.e., the file exists):
+// 1. register files in file manager (FileManager)
+// 2. create file mappings (FileMappingProvider)
+// 3. register tree index instance (IndexRegistry)
+
+public class TreeIndexFileEnlistmentOperatorDescriptor extends AbstractTreeIndexOperatorDescriptor {
+
+ private static final long serialVersionUID = 1L;
+
+ public TreeIndexFileEnlistmentOperatorDescriptor(JobSpecification spec, RecordDescriptor recDesc,
+ IStorageManagerInterface storageManager, IIndexRegistryProvider<ITreeIndex> treeIndexRegistryProvider,
+ IFileSplitProvider fileSplitProvider, ITreeIndexFrameFactory interiorFrameFactory,
+ ITreeIndexFrameFactory leafFrameFactory, ITypeTrait[] typeTraits,
+ IBinaryComparatorFactory[] comparatorFactories, ITreeIndexOpHelperFactory opHelperFactory) {
+ super(spec, 0, 0, recDesc, storageManager, treeIndexRegistryProvider, fileSplitProvider, interiorFrameFactory,
+ leafFrameFactory, typeTraits, comparatorFactories, opHelperFactory);
+ }
+
+ @Override
+ public IOperatorNodePushable createPushRuntime(IHyracksStageletContext ctx, IOperatorEnvironment env,
+ IRecordDescriptorProvider recordDescProvider, int partition, int partitions) throws HyracksDataException {
+ return new TreeIndexFileEnlistmentOperatorNodePushable(this, ctx, partition);
+ }
+
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexFileEnlistmentOperatorNodePushable.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexFileEnlistmentOperatorNodePushable.java
new file mode 100644
index 0000000..8ff6586
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexFileEnlistmentOperatorNodePushable.java
@@ -0,0 +1,60 @@
+/*
+ * 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.dataflow;
+
+import edu.uci.ics.hyracks.api.comm.IFrameWriter;
+import edu.uci.ics.hyracks.api.context.IHyracksStageletContext;
+import edu.uci.ics.hyracks.api.dataflow.value.RecordDescriptor;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.dataflow.std.base.AbstractOperatorNodePushable;
+
+public class TreeIndexFileEnlistmentOperatorNodePushable extends AbstractOperatorNodePushable {
+
+ private final TreeIndexOpHelper treeIndexOpHelper;
+
+ public TreeIndexFileEnlistmentOperatorNodePushable(AbstractTreeIndexOperatorDescriptor opDesc,
+ IHyracksStageletContext ctx, int partition) {
+ treeIndexOpHelper = opDesc.getTreeIndexOpHelperFactory().createTreeIndexOpHelper(opDesc, ctx, partition,
+ IndexHelperOpenMode.ENLIST);
+ }
+
+ @Override
+ public void deinitialize() throws HyracksDataException {
+ }
+
+ @Override
+ public int getInputArity() {
+ return 0;
+ }
+
+ @Override
+ public IFrameWriter getInputFrameWriter(int index) {
+ return null;
+ }
+
+ @Override
+ public void initialize() throws HyracksDataException {
+ try {
+ treeIndexOpHelper.init();
+ } finally {
+ treeIndexOpHelper.deinit();
+ }
+ }
+
+ @Override
+ public void setOutputFrameWriter(int index, IFrameWriter writer, RecordDescriptor recordDesc) {
+ }
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexInsertUpdateDeleteOperatorDescriptor.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexInsertUpdateDeleteOperatorDescriptor.java
new file mode 100644
index 0000000..c8141b9
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexInsertUpdateDeleteOperatorDescriptor.java
@@ -0,0 +1,58 @@
+/*
+ * 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.dataflow;
+
+import edu.uci.ics.hyracks.api.context.IHyracksStageletContext;
+import edu.uci.ics.hyracks.api.dataflow.IOperatorNodePushable;
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+import edu.uci.ics.hyracks.api.dataflow.value.IRecordDescriptorProvider;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTrait;
+import edu.uci.ics.hyracks.api.dataflow.value.RecordDescriptor;
+import edu.uci.ics.hyracks.api.job.IOperatorEnvironment;
+import edu.uci.ics.hyracks.api.job.JobSpecification;
+import edu.uci.ics.hyracks.dataflow.std.file.IFileSplitProvider;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.IndexOp;
+import edu.uci.ics.hyracks.storage.common.IStorageManagerInterface;
+
+public class TreeIndexInsertUpdateDeleteOperatorDescriptor extends AbstractTreeIndexOperatorDescriptor {
+
+ private static final long serialVersionUID = 1L;
+
+ private final int[] fieldPermutation;
+
+ private IndexOp op;
+
+ public TreeIndexInsertUpdateDeleteOperatorDescriptor(JobSpecification spec, RecordDescriptor recDesc,
+ IStorageManagerInterface storageManager, IIndexRegistryProvider<ITreeIndex> treeIndexRegistryProvider,
+ IFileSplitProvider fileSplitProvider, ITreeIndexFrameFactory interiorFrameFactory,
+ ITreeIndexFrameFactory leafFrameFactory, ITypeTrait[] typeTraits,
+ IBinaryComparatorFactory[] comparatorFactories, int[] fieldPermutation, IndexOp op,
+ ITreeIndexOpHelperFactory opHelperFactory) {
+ super(spec, 1, 1, recDesc, storageManager, treeIndexRegistryProvider, fileSplitProvider, interiorFrameFactory,
+ leafFrameFactory, typeTraits, comparatorFactories, opHelperFactory);
+ this.fieldPermutation = fieldPermutation;
+ this.op = op;
+ }
+
+ @Override
+ public IOperatorNodePushable createPushRuntime(IHyracksStageletContext ctx, IOperatorEnvironment env,
+ IRecordDescriptorProvider recordDescProvider, int partition, int nPartitions) {
+ return new TreeIndexInsertUpdateDeleteOperatorNodePushable(this, ctx, partition, fieldPermutation,
+ recordDescProvider, op);
+ }
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexInsertUpdateDeleteOperatorNodePushable.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexInsertUpdateDeleteOperatorNodePushable.java
new file mode 100644
index 0000000..74a9efc
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexInsertUpdateDeleteOperatorNodePushable.java
@@ -0,0 +1,119 @@
+/*
+ * 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.dataflow;
+
+import java.nio.ByteBuffer;
+
+import edu.uci.ics.hyracks.api.context.IHyracksStageletContext;
+import edu.uci.ics.hyracks.api.dataflow.value.IRecordDescriptorProvider;
+import edu.uci.ics.hyracks.api.dataflow.value.RecordDescriptor;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+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.common.api.ITreeIndex;
+import edu.uci.ics.hyracks.storage.am.common.frames.LIFOMetaDataFrame;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.IndexOp;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.IndexOpContext;
+
+public class TreeIndexInsertUpdateDeleteOperatorNodePushable extends AbstractUnaryInputUnaryOutputOperatorNodePushable {
+ private final TreeIndexOpHelper treeIndexOpHelper;
+ private FrameTupleAccessor accessor;
+ private final IRecordDescriptorProvider recordDescProvider;
+ private final IndexOp op;
+ private final PermutingFrameTupleReference tuple = new PermutingFrameTupleReference();
+ private ByteBuffer writeBuffer;
+ private IndexOpContext opCtx;
+
+ public TreeIndexInsertUpdateDeleteOperatorNodePushable(AbstractTreeIndexOperatorDescriptor opDesc,
+ IHyracksStageletContext ctx, int partition, int[] fieldPermutation,
+ IRecordDescriptorProvider recordDescProvider, IndexOp op) {
+ treeIndexOpHelper = opDesc.getTreeIndexOpHelperFactory().createTreeIndexOpHelper(opDesc, ctx, partition,
+ IndexHelperOpenMode.OPEN);
+ this.recordDescProvider = recordDescProvider;
+ this.op = op;
+ tuple.setFieldPermutation(fieldPermutation);
+ }
+
+ @Override
+ public void open() throws HyracksDataException {
+ AbstractTreeIndexOperatorDescriptor opDesc = (AbstractTreeIndexOperatorDescriptor) treeIndexOpHelper
+ .getOperatorDescriptor();
+ RecordDescriptor inputRecDesc = recordDescProvider.getInputRecordDescriptor(opDesc.getOperatorId(), 0);
+ accessor = new FrameTupleAccessor(treeIndexOpHelper.getHyracksStageletContext().getFrameSize(), inputRecDesc);
+ writeBuffer = treeIndexOpHelper.getHyracksStageletContext().allocateFrame();
+ try {
+ treeIndexOpHelper.init();
+ treeIndexOpHelper.getTreeIndex().open(treeIndexOpHelper.getIndexFileId());
+ opCtx = treeIndexOpHelper.getTreeIndex().createOpContext(op, treeIndexOpHelper.getLeafFrame(),
+ treeIndexOpHelper.getInteriorFrame(), new LIFOMetaDataFrame());
+ } catch (Exception e) {
+ // cleanup in case of failure
+ treeIndexOpHelper.deinit();
+ throw new HyracksDataException(e);
+ }
+ }
+
+ @Override
+ public void nextFrame(ByteBuffer buffer) throws HyracksDataException {
+ final ITreeIndex treeIndex = treeIndexOpHelper.getTreeIndex();
+ accessor.reset(buffer);
+
+ int tupleCount = accessor.getTupleCount();
+ for (int i = 0; i < tupleCount; i++) {
+ tuple.reset(accessor, i);
+ try {
+ switch (op) {
+
+ case INSERT: {
+ treeIndex.insert(tuple, opCtx);
+ }
+ break;
+
+ case DELETE: {
+ treeIndex.delete(tuple, opCtx);
+ }
+ break;
+
+ default: {
+ throw new HyracksDataException("Unsupported operation " + op
+ + " in tree index InsertUpdateDelete operator");
+ }
+
+ }
+
+ } catch (Exception e) {
+ e.printStackTrace();
+ }
+ }
+
+ // pass a copy of the frame to next op
+ System.arraycopy(buffer.array(), 0, writeBuffer.array(), 0, buffer.capacity());
+ FrameUtils.flushFrame(writeBuffer, writer);
+ }
+
+ @Override
+ public void close() throws HyracksDataException {
+ try {
+ writer.close();
+ } finally {
+ treeIndexOpHelper.deinit();
+ }
+ }
+
+ @Override
+ public void flush() throws HyracksDataException {
+ }
+}
\ No newline at end of file
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexOpHelper.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexOpHelper.java
new file mode 100644
index 0000000..fca6d8d
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexOpHelper.java
@@ -0,0 +1,176 @@
+/*
+ * 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.dataflow;
+
+import edu.uci.ics.hyracks.api.context.IHyracksStageletContext;
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparator;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.api.io.FileReference;
+import edu.uci.ics.hyracks.dataflow.std.file.IFileSplitProvider;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexCursor;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrame;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrame;
+import edu.uci.ics.hyracks.storage.am.common.impls.TreeDiskOrderScanCursor;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
+import edu.uci.ics.hyracks.storage.common.file.IFileMapProvider;
+
+public abstract class TreeIndexOpHelper {
+
+ protected ITreeIndexFrame interiorFrame;
+ protected ITreeIndexFrame leafFrame;
+ protected MultiComparator cmp;
+
+ protected ITreeIndex treeIndex;
+ protected int indexFileId = -1;
+ protected int partition;
+
+ protected ITreeIndexOperatorDescriptorHelper opDesc;
+ protected IHyracksStageletContext ctx;
+
+ protected IndexHelperOpenMode mode;
+
+ public TreeIndexOpHelper(ITreeIndexOperatorDescriptorHelper opDesc, final IHyracksStageletContext ctx,
+ int partition, IndexHelperOpenMode mode) {
+ this.opDesc = opDesc;
+ this.ctx = ctx;
+ this.mode = mode;
+ this.partition = partition;
+ }
+
+ public void init() throws HyracksDataException {
+ IBufferCache bufferCache = opDesc.getStorageManager().getBufferCache(ctx);
+ IFileMapProvider fileMapProvider = opDesc.getStorageManager().getFileMapProvider(ctx);
+ IFileSplitProvider fileSplitProvider = opDesc.getTreeIndexFileSplitProvider();
+
+ FileReference f = fileSplitProvider.getFileSplits()[partition].getLocalFile();
+ boolean fileIsMapped = fileMapProvider.isMapped(f);
+
+ switch (mode) {
+
+ case OPEN: {
+ if (!fileIsMapped) {
+ throw new HyracksDataException("Trying to open tree index from unmapped file " + f.toString());
+ }
+ }
+ break;
+
+ case CREATE:
+ case ENLIST: {
+ if (!fileIsMapped) {
+ bufferCache.createFile(f);
+ }
+ }
+ break;
+
+ }
+
+ int fileId = fileMapProvider.lookupFileId(f);
+ try {
+ bufferCache.openFile(fileId);
+ } catch (HyracksDataException e) {
+ // revert state of buffer cache since file failed to open
+ if (!fileIsMapped) {
+ bufferCache.deleteFile(fileId);
+ }
+ throw e;
+ }
+
+ // only set indexFileId member when openFile() succeeds,
+ // otherwise deinit() will try to close the file that failed to open
+ indexFileId = fileId;
+
+ interiorFrame = opDesc.getTreeIndexInteriorFactory().createFrame();
+ leafFrame = opDesc.getTreeIndexLeafFactory().createFrame();
+
+ IndexRegistry<ITreeIndex> treeIndexRegistry = opDesc.getTreeIndexRegistryProvider().getRegistry(ctx);
+ treeIndex = treeIndexRegistry.get(indexFileId);
+ if (treeIndex == null) {
+
+ // create new tree and register it
+ treeIndexRegistry.lock();
+ try {
+ // check if tree has already been registered by another thread
+ treeIndex = treeIndexRegistry.get(indexFileId);
+ if (treeIndex == null) {
+ // this thread should create and register the tree
+
+ IBinaryComparator[] comparators = new IBinaryComparator[opDesc.getTreeIndexComparatorFactories().length];
+ for (int i = 0; i < opDesc.getTreeIndexComparatorFactories().length; i++) {
+ comparators[i] = opDesc.getTreeIndexComparatorFactories()[i].createBinaryComparator();
+ }
+
+ cmp = new MultiComparator(opDesc.getTreeIndexTypeTraits(), comparators);
+
+ treeIndex = createTreeIndex();
+ if (mode == IndexHelperOpenMode.CREATE) {
+ ITreeIndexMetaDataFrame metaFrame = treeIndex.getFreePageManager().getMetaDataFrameFactory()
+ .createFrame();
+ try {
+ treeIndex.create(indexFileId, leafFrame, metaFrame);
+ } catch (Exception e) {
+ throw new HyracksDataException(e);
+ }
+ }
+ treeIndex.open(indexFileId);
+ treeIndexRegistry.register(indexFileId, treeIndex);
+ }
+ } finally {
+ treeIndexRegistry.unlock();
+ }
+ }
+ }
+
+ // MUST be overridden
+ public ITreeIndex createTreeIndex() throws HyracksDataException {
+ throw new HyracksDataException("createTreeIndex Operation not implemented.");
+ }
+
+ public ITreeIndexCursor createDiskOrderScanCursor(ITreeIndexFrame leafFrame) throws HyracksDataException {
+ return new TreeDiskOrderScanCursor(leafFrame);
+ }
+
+ public void deinit() throws HyracksDataException {
+ if (indexFileId != -1) {
+ IBufferCache bufferCache = opDesc.getStorageManager().getBufferCache(ctx);
+ bufferCache.closeFile(indexFileId);
+ }
+ }
+
+ public ITreeIndex getTreeIndex() {
+ return treeIndex;
+ }
+
+ public IHyracksStageletContext getHyracksStageletContext() {
+ return ctx;
+ }
+
+ public ITreeIndexOperatorDescriptorHelper getOperatorDescriptor() {
+ return opDesc;
+ }
+
+ public ITreeIndexFrame getLeafFrame() {
+ return leafFrame;
+ }
+
+ public ITreeIndexFrame getInteriorFrame() {
+ return interiorFrame;
+ }
+
+ public int getIndexFileId() {
+ return indexFileId;
+ }
+}
\ No newline at end of file
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexStatsOperatorDescriptor.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexStatsOperatorDescriptor.java
new file mode 100644
index 0000000..574e727
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexStatsOperatorDescriptor.java
@@ -0,0 +1,33 @@
+package edu.uci.ics.hyracks.storage.am.common.dataflow;
+
+import edu.uci.ics.hyracks.api.context.IHyracksStageletContext;
+import edu.uci.ics.hyracks.api.dataflow.IOperatorNodePushable;
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+import edu.uci.ics.hyracks.api.dataflow.value.IRecordDescriptorProvider;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTrait;
+import edu.uci.ics.hyracks.api.job.IOperatorEnvironment;
+import edu.uci.ics.hyracks.api.job.JobSpecification;
+import edu.uci.ics.hyracks.dataflow.std.file.IFileSplitProvider;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
+import edu.uci.ics.hyracks.storage.common.IStorageManagerInterface;
+
+public class TreeIndexStatsOperatorDescriptor extends AbstractTreeIndexOperatorDescriptor {
+
+ private static final long serialVersionUID = 1L;
+
+ public TreeIndexStatsOperatorDescriptor(JobSpecification spec, IStorageManagerInterface storageManager,
+ IIndexRegistryProvider<ITreeIndex> treeIndexRegistryProvider, IFileSplitProvider fileSplitProvider,
+ ITreeIndexFrameFactory interiorFrameFactory, ITreeIndexFrameFactory leafFrameFactory,
+ ITypeTrait[] typeTraits, IBinaryComparatorFactory[] comparatorFactories,
+ ITreeIndexOpHelperFactory opHelperFactory) {
+ super(spec, 0, 0, null, storageManager, treeIndexRegistryProvider, fileSplitProvider, interiorFrameFactory,
+ leafFrameFactory, typeTraits, comparatorFactories, opHelperFactory);
+ }
+
+ @Override
+ public IOperatorNodePushable createPushRuntime(IHyracksStageletContext ctx, IOperatorEnvironment env,
+ IRecordDescriptorProvider recordDescProvider, int partition, int nPartitions) {
+ return new TreeIndexStatsOperatorNodePushable(this, ctx, partition);
+ }
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexStatsOperatorNodePushable.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexStatsOperatorNodePushable.java
new file mode 100644
index 0000000..f47855f
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexStatsOperatorNodePushable.java
@@ -0,0 +1,78 @@
+/*
+ * 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.dataflow;
+
+import edu.uci.ics.hyracks.api.comm.IFrameWriter;
+import edu.uci.ics.hyracks.api.context.IHyracksStageletContext;
+import edu.uci.ics.hyracks.api.dataflow.value.RecordDescriptor;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.dataflow.std.base.AbstractOperatorNodePushable;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
+import edu.uci.ics.hyracks.storage.am.common.utility.TreeIndexStats;
+import edu.uci.ics.hyracks.storage.am.common.utility.TreeIndexStatsGatherer;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
+
+public class TreeIndexStatsOperatorNodePushable extends AbstractOperatorNodePushable {
+ private final TreeIndexOpHelper treeIndexOpHelper;
+ private final IHyracksStageletContext ctx;
+ private TreeIndexStatsGatherer statsGatherer;
+
+ public TreeIndexStatsOperatorNodePushable(AbstractTreeIndexOperatorDescriptor opDesc, IHyracksStageletContext ctx,
+ int partition) {
+ treeIndexOpHelper = opDesc.getTreeIndexOpHelperFactory().createTreeIndexOpHelper(opDesc, ctx, partition,
+ IndexHelperOpenMode.CREATE);
+ this.ctx = ctx;
+ }
+
+ @Override
+ public void deinitialize() throws HyracksDataException {
+ }
+
+ @Override
+ public int getInputArity() {
+ return 0;
+ }
+
+ @Override
+ public IFrameWriter getInputFrameWriter(int index) {
+ return null;
+ }
+
+ @Override
+ public void initialize() throws HyracksDataException {
+ try {
+ treeIndexOpHelper.init();
+ treeIndexOpHelper.getTreeIndex().open(treeIndexOpHelper.getIndexFileId());
+
+ ITreeIndex treeIndex = treeIndexOpHelper.getTreeIndex();
+ IBufferCache bufferCache = treeIndexOpHelper.getOperatorDescriptor().getStorageManager()
+ .getBufferCache(ctx);
+
+ statsGatherer = new TreeIndexStatsGatherer(bufferCache, treeIndex.getFreePageManager(),
+ treeIndexOpHelper.getIndexFileId(), treeIndex.getRootPageId());
+ TreeIndexStats stats = statsGatherer.gatherStats(treeIndex.getLeafFrameFactory().createFrame(), treeIndex
+ .getInteriorFrameFactory().createFrame(), treeIndex.getFreePageManager().getMetaDataFrameFactory()
+ .createFrame());
+ System.err.println(stats.toString());
+ } catch (Exception e) {
+ treeIndexOpHelper.deinit();
+ throw new HyracksDataException(e);
+ }
+ }
+
+ @Override
+ public void setOutputFrameWriter(int index, IFrameWriter writer, RecordDescriptor recordDesc) {
+ }
+}
\ No newline at end of file
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/frames/AbstractSlotManager.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/frames/AbstractSlotManager.java
new file mode 100644
index 0000000..87fea47
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/frames/AbstractSlotManager.java
@@ -0,0 +1,60 @@
+/*
+ * 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.ISlotManager;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrame;
+
+public abstract class AbstractSlotManager implements ISlotManager {
+
+ protected static final int slotSize = 4;
+ protected ITreeIndexFrame frame;
+
+ @Override
+ public int getTupleOff(int offset) {
+ return frame.getBuffer().getInt(offset);
+ }
+
+ @Override
+ public void setSlot(int offset, int value) {
+ frame.getBuffer().putInt(offset, value);
+ }
+
+ @Override
+ public int getSlotEndOff() {
+ return frame.getBuffer().capacity() - (frame.getTupleCount() * slotSize);
+ }
+
+ @Override
+ public int getSlotStartOff() {
+ return frame.getBuffer().capacity() - slotSize;
+ }
+
+ @Override
+ public int getSlotSize() {
+ return slotSize;
+ }
+
+ @Override
+ public void setFrame(ITreeIndexFrame frame) {
+ this.frame = frame;
+ }
+
+ @Override
+ public int getSlotOff(int tupleIndex) {
+ return getSlotStartOff() - tupleIndex * slotSize;
+ }
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/frames/FrameOpSpaceStatus.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/frames/FrameOpSpaceStatus.java
new file mode 100644
index 0000000..97a4730
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/frames/FrameOpSpaceStatus.java
@@ -0,0 +1,20 @@
+/*
+ * 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;
+
+public enum FrameOpSpaceStatus {
+ INSUFFICIENT_SPACE, SUFFICIENT_CONTIGUOUS_SPACE, SUFFICIENT_SPACE
+}
\ No newline at end of file
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/frames/LIFOMetaDataFrame.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/frames/LIFOMetaDataFrame.java
new file mode 100644
index 0000000..b621b89
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/frames/LIFOMetaDataFrame.java
@@ -0,0 +1,115 @@
+/*
+ * 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 int dummyFieldOff = maxPageOff + 4;
+ protected static final byte levelOff = dummyFieldOff + 4;
+ protected static final byte nextPageOff = levelOff + 1;
+
+ 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/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/frames/LIFOMetaDataFrameFactory.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/frames/LIFOMetaDataFrameFactory.java
new file mode 100644
index 0000000..409c8b2
--- /dev/null
+++ b/hyracks/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 createFrame() {
+ return new LIFOMetaDataFrame();
+ }
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/frames/TreeIndexNSMFrame.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/frames/TreeIndexNSMFrame.java
new file mode 100644
index 0000000..af1e337
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/frames/TreeIndexNSMFrame.java
@@ -0,0 +1,324 @@
+/*
+ * 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.io.ByteArrayInputStream;
+import java.io.DataInput;
+import java.io.DataInputStream;
+import java.nio.ByteBuffer;
+import java.util.ArrayList;
+import java.util.Collections;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.storage.am.common.api.ISlotManager;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrame;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleReference;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleWriter;
+import edu.uci.ics.hyracks.storage.am.common.api.TreeIndexException;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.FindTupleMode;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.FindTupleNoExactMatchPolicy;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.SlotOffTupleOff;
+import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
+
+public abstract class TreeIndexNSMFrame implements ITreeIndexFrame {
+
+ protected static final int pageLsnOff = 0; // 0
+ protected static final int tupleCountOff = pageLsnOff + 4; // 4
+ protected static final int freeSpaceOff = tupleCountOff + 4; // 8
+ protected static final int totalFreeSpaceOff = freeSpaceOff + 4; // 16
+ protected static final byte levelOff = totalFreeSpaceOff + 4;
+ protected static final byte smFlagOff = levelOff + 1;
+
+ protected ICachedPage page = null;
+ protected ByteBuffer buf = null;
+ protected ISlotManager slotManager;
+
+ protected ITreeIndexTupleWriter tupleWriter;
+ protected ITreeIndexTupleReference frameTuple;
+
+ public TreeIndexNSMFrame(ITreeIndexTupleWriter tupleWriter, ISlotManager slotManager) {
+ this.tupleWriter = tupleWriter;
+ this.frameTuple = tupleWriter.createTupleReference();
+ this.slotManager = slotManager;
+ }
+
+ @Override
+ public void initBuffer(byte level) {
+ buf.putInt(pageLsnOff, 0); // TODO: might to set to a different lsn
+ // during creation
+ buf.putInt(tupleCountOff, 0);
+ resetSpaceParams();
+ buf.put(levelOff, level);
+ buf.put(smFlagOff, (byte) 0);
+ }
+
+ @Override
+ public boolean isLeaf() {
+ return buf.get(levelOff) == 0;
+ }
+
+ @Override
+ public boolean isInterior() {
+ return buf.get(levelOff) > 0;
+ }
+
+ @Override
+ public byte getLevel() {
+ return buf.get(levelOff);
+ }
+
+ @Override
+ public void setLevel(byte level) {
+ buf.put(levelOff, level);
+ }
+
+ @Override
+ public boolean getSmFlag() {
+ return buf.get(smFlagOff) != 0;
+ }
+
+ @Override
+ public void setSmFlag(boolean smFlag) {
+ if (smFlag)
+ buf.put(smFlagOff, (byte) 1);
+ else
+ buf.put(smFlagOff, (byte) 0);
+ }
+
+ @Override
+ public int getFreeSpaceOff() {
+ return buf.getInt(freeSpaceOff);
+ }
+
+ @Override
+ public void setFreeSpaceOff(int freeSpace) {
+ buf.putInt(freeSpaceOff, freeSpace);
+ }
+
+ @Override
+ public void setPage(ICachedPage page) {
+ this.page = page;
+ this.buf = page.getBuffer();
+ slotManager.setFrame(this);
+ }
+
+ @Override
+ public ByteBuffer getBuffer() {
+ return page.getBuffer();
+ }
+
+ @Override
+ public ICachedPage getPage() {
+ return page;
+ }
+
+ @Override
+ public boolean compact(MultiComparator cmp) {
+ resetSpaceParams();
+ frameTuple.setFieldCount(cmp.getFieldCount());
+
+ int tupleCount = buf.getInt(tupleCountOff);
+ int freeSpace = buf.getInt(freeSpaceOff);
+
+ ArrayList<SlotOffTupleOff> sortedTupleOffs = new ArrayList<SlotOffTupleOff>();
+ sortedTupleOffs.ensureCapacity(tupleCount);
+ for (int i = 0; i < tupleCount; i++) {
+ int slotOff = slotManager.getSlotOff(i);
+ int tupleOff = slotManager.getTupleOff(slotOff);
+ sortedTupleOffs.add(new SlotOffTupleOff(i, slotOff, tupleOff));
+ }
+ Collections.sort(sortedTupleOffs);
+
+ for (int i = 0; i < sortedTupleOffs.size(); i++) {
+ int tupleOff = sortedTupleOffs.get(i).tupleOff;
+ frameTuple.resetByTupleOffset(buf, tupleOff);
+
+ int tupleEndOff = frameTuple.getFieldStart(frameTuple.getFieldCount() - 1)
+ + frameTuple.getFieldLength(frameTuple.getFieldCount() - 1);
+ int tupleLength = tupleEndOff - tupleOff;
+ System.arraycopy(buf.array(), tupleOff, buf.array(), freeSpace, tupleLength);
+
+ slotManager.setSlot(sortedTupleOffs.get(i).slotOff, freeSpace);
+ freeSpace += tupleLength;
+ }
+
+ buf.putInt(freeSpaceOff, freeSpace);
+ buf.putInt(totalFreeSpaceOff, buf.capacity() - freeSpace - tupleCount * slotManager.getSlotSize());
+
+ return false;
+ }
+
+ @Override
+ public void delete(ITupleReference tuple, MultiComparator cmp, boolean exactDelete) throws Exception {
+
+ frameTuple.setFieldCount(cmp.getFieldCount());
+ int tupleIndex = slotManager.findTupleIndex(tuple, frameTuple, cmp, FindTupleMode.FTM_EXACT,
+ FindTupleNoExactMatchPolicy.FTP_HIGHER_KEY);
+ int slotOff = slotManager.getSlotOff(tupleIndex);
+ if (tupleIndex < 0) {
+ throw new TreeIndexException("Key to be deleted does not exist.");
+ } else {
+ if (exactDelete) {
+ // check the non-key columns for equality by byte-by-byte
+ // comparison
+ int tupleOff = slotManager.getTupleOff(slotOff);
+ frameTuple.resetByTupleOffset(buf, tupleOff);
+
+ int comparison = cmp.fieldRangeCompare(tuple, frameTuple, cmp.getKeyFieldCount() - 1,
+ cmp.getFieldCount() - cmp.getKeyFieldCount());
+ if (comparison != 0) {
+ throw new TreeIndexException(
+ "Cannot delete tuple. Byte-by-byte comparison failed to prove equality.");
+ }
+ }
+
+ int tupleOff = slotManager.getTupleOff(slotOff);
+ frameTuple.resetByTupleOffset(buf, tupleOff);
+ int tupleSize = tupleWriter.bytesRequired(frameTuple);
+
+ // perform deletion (we just do a memcpy to overwrite the slot)
+ int slotStartOff = slotManager.getSlotEndOff();
+ int length = slotOff - slotStartOff;
+ System.arraycopy(buf.array(), slotStartOff, buf.array(), slotStartOff + slotManager.getSlotSize(), length);
+
+ // maintain space information
+ buf.putInt(tupleCountOff, buf.getInt(tupleCountOff) - 1);
+ buf.putInt(totalFreeSpaceOff, buf.getInt(totalFreeSpaceOff) + tupleSize + slotManager.getSlotSize());
+ }
+ }
+
+ @Override
+ public FrameOpSpaceStatus hasSpaceInsert(ITupleReference tuple, MultiComparator cmp) {
+ int bytesRequired = tupleWriter.bytesRequired(tuple);
+ if (bytesRequired + slotManager.getSlotSize() <= buf.capacity() - buf.getInt(freeSpaceOff)
+ - (buf.getInt(tupleCountOff) * slotManager.getSlotSize()))
+ return FrameOpSpaceStatus.SUFFICIENT_CONTIGUOUS_SPACE;
+ else if (bytesRequired + slotManager.getSlotSize() <= buf.getInt(totalFreeSpaceOff))
+ return FrameOpSpaceStatus.SUFFICIENT_SPACE;
+ else
+ return FrameOpSpaceStatus.INSUFFICIENT_SPACE;
+ }
+
+ @Override
+ public FrameOpSpaceStatus hasSpaceUpdate(int rid, ITupleReference tuple, MultiComparator cmp) {
+ // TODO Auto-generated method stub
+ return FrameOpSpaceStatus.INSUFFICIENT_SPACE;
+ }
+
+ protected void resetSpaceParams() {
+ buf.putInt(freeSpaceOff, smFlagOff + 1);
+ buf.putInt(totalFreeSpaceOff, buf.capacity() - (smFlagOff + 1));
+ }
+
+ @Override
+ public int findTupleIndex(ITupleReference tuple, MultiComparator cmp) throws Exception {
+ frameTuple.setFieldCount(cmp.getFieldCount());
+ return slotManager.findTupleIndex(tuple, frameTuple, cmp, FindTupleMode.FTM_INCLUSIVE,
+ FindTupleNoExactMatchPolicy.FTP_HIGHER_KEY);
+ }
+
+ @Override
+ public void insert(ITupleReference tuple, MultiComparator cmp, int tupleIndex) throws Exception {
+ slotManager.insertSlot(tupleIndex, buf.getInt(freeSpaceOff));
+ int bytesWritten = tupleWriter.writeTuple(tuple, buf, buf.getInt(freeSpaceOff));
+ buf.putInt(tupleCountOff, buf.getInt(tupleCountOff) + 1);
+ buf.putInt(freeSpaceOff, buf.getInt(freeSpaceOff) + bytesWritten);
+ buf.putInt(totalFreeSpaceOff, buf.getInt(totalFreeSpaceOff) - bytesWritten - slotManager.getSlotSize());
+ }
+
+ @Override
+ public void update(int rid, ITupleReference tuple) throws Exception {
+ // TODO Auto-generated method stub
+
+ }
+
+ @Override
+ public void printHeader() {
+ // TODO Auto-generated method stub
+
+ }
+
+ @Override
+ public int getTupleCount() {
+ return buf.getInt(tupleCountOff);
+ }
+
+ public ISlotManager getSlotManager() {
+ return slotManager;
+ }
+
+ @Override
+ public String printKeys(MultiComparator cmp, ISerializerDeserializer[] fields) throws HyracksDataException {
+ StringBuilder strBuilder = new StringBuilder();
+ int tupleCount = buf.getInt(tupleCountOff);
+ frameTuple.setFieldCount(fields.length);
+ for (int i = 0; i < tupleCount; i++) {
+ frameTuple.resetByTupleIndex(this, i);
+ for (int j = 0; j < cmp.getKeyFieldCount(); j++) {
+ ByteArrayInputStream inStream = new ByteArrayInputStream(frameTuple.getFieldData(j),
+ frameTuple.getFieldStart(j), frameTuple.getFieldLength(j));
+ DataInput dataIn = new DataInputStream(inStream);
+ Object o = fields[j].deserialize(dataIn);
+ strBuilder.append(o.toString() + " ");
+ }
+ strBuilder.append(" | ");
+ }
+ strBuilder.append("\n");
+ return strBuilder.toString();
+ }
+
+ @Override
+ public int getTupleOffset(int slotNum) {
+ return slotManager.getTupleOff(slotManager.getSlotStartOff() - slotNum * slotManager.getSlotSize());
+ }
+
+ @Override
+ public int getPageLsn() {
+ return buf.getInt(pageLsnOff);
+ }
+
+ @Override
+ public void setPageLsn(int pageLsn) {
+ buf.putInt(pageLsnOff, pageLsn);
+ }
+
+ @Override
+ public int getTotalFreeSpace() {
+ return buf.getInt(totalFreeSpaceOff);
+ }
+
+ @Override
+ public boolean compress(MultiComparator cmp) {
+ return false;
+ }
+
+ @Override
+ public int getSlotSize() {
+ return slotManager.getSlotSize();
+ }
+
+ @Override
+ public void setPageTupleFieldCount(int fieldCount) {
+ frameTuple.setFieldCount(fieldCount);
+ }
+
+ public ITreeIndexTupleWriter getTupleWriter() {
+ return tupleWriter;
+ }
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/freepage/LinkedListFreePageManager.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/freepage/LinkedListFreePageManager.java
new file mode 100644
index 0000000..42bf70f
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/freepage/LinkedListFreePageManager.java
@@ -0,0 +1,187 @@
+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.am.common.api.ITreeIndexMetaDataFrameFactory;
+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 static final byte META_PAGE_LEVEL_INDICATOR = -1;
+ private static final byte FREE_PAGE_LEVEL_INDICATOR = -2;
+ private final IBufferCache bufferCache;
+ private final int fileId;
+ private final int headPage;
+ private final ITreeIndexMetaDataFrameFactory metaDataFrameFactory;
+
+ public LinkedListFreePageManager(IBufferCache bufferCache, int fileId, int headPage,
+ ITreeIndexMetaDataFrameFactory metaDataFrameFactory) {
+ this.bufferCache = bufferCache;
+ this.fileId = fileId;
+ this.headPage = headPage;
+ this.metaDataFrameFactory = metaDataFrameFactory;
+ }
+
+ @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(META_PAGE_LEVEL_INDICATOR);
+ 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), true);
+
+ metaNode.acquireWriteLatch();
+ try {
+ metaFrame.setPage(metaNode);
+ metaFrame.initBuffer(META_PAGE_LEVEL_INDICATOR);
+ metaFrame.setMaxPage(currentMaxPage);
+ } finally {
+ metaNode.releaseWriteLatch();
+ bufferCache.unpin(metaNode);
+ }
+ }
+
+ @Override
+ public ITreeIndexMetaDataFrameFactory getMetaDataFrameFactory() {
+ return metaDataFrameFactory;
+ }
+
+ @Override
+ public byte getFreePageLevelIndicator() {
+ return FREE_PAGE_LEVEL_INDICATOR;
+ }
+
+ @Override
+ public byte getMetaPageLevelIndicator() {
+ return META_PAGE_LEVEL_INDICATOR;
+ }
+
+ @Override
+ public boolean isFreePage(ITreeIndexMetaDataFrame metaFrame) {
+ return metaFrame.getLevel() == FREE_PAGE_LEVEL_INDICATOR;
+ }
+
+ @Override
+ public boolean isMetaPage(ITreeIndexMetaDataFrame metaFrame) {
+ return metaFrame.getLevel() == META_PAGE_LEVEL_INDICATOR;
+ }
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/impls/TreeDiskOrderScanCursor.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/impls/TreeDiskOrderScanCursor.java
new file mode 100644
index 0000000..2c2cb5e
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/impls/TreeDiskOrderScanCursor.java
@@ -0,0 +1,150 @@
+/*
+ * 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.impls;
+
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.storage.am.common.api.ICursorInitialState;
+import edu.uci.ics.hyracks.storage.am.common.api.ISearchPredicate;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexCursor;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrame;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleReference;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+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 TreeDiskOrderScanCursor implements ITreeIndexCursor {
+
+ private int tupleIndex = 0;
+ private int fileId = -1;
+ int currentPageId = -1;
+ int maxPageId = -1;
+ private ICachedPage page = null;
+ private ITreeIndexFrame frame = null;
+ private IBufferCache bufferCache = null;
+
+ private ITreeIndexTupleReference frameTuple;
+
+ public TreeDiskOrderScanCursor(ITreeIndexFrame frame) {
+ this.frame = frame;
+ this.frameTuple = frame.getTupleWriter().createTupleReference();
+ }
+
+ @Override
+ public void close() throws Exception {
+ page.releaseReadLatch();
+ bufferCache.unpin(page);
+ page = null;
+ }
+
+ @Override
+ public ITreeIndexTupleReference getTuple() {
+ return frameTuple;
+ }
+
+ @Override
+ public ICachedPage getPage() {
+ return page;
+ }
+
+ private boolean positionToNextLeaf(boolean skipCurrent) throws HyracksDataException {
+ while ((frame.getLevel() != 0 || skipCurrent) && (currentPageId <= maxPageId) || (frame.getTupleCount() == 0)) {
+ currentPageId++;
+
+ ICachedPage nextPage = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, currentPageId), false);
+ nextPage.acquireReadLatch();
+
+ page.releaseReadLatch();
+ bufferCache.unpin(page);
+
+ page = nextPage;
+ frame.setPage(page);
+ tupleIndex = 0;
+ skipCurrent = false;
+ }
+ if (currentPageId <= maxPageId)
+ return true;
+ else
+ return false;
+ }
+
+ @Override
+ public boolean hasNext() throws Exception {
+ if (tupleIndex >= frame.getTupleCount()) {
+ boolean nextLeafExists = positionToNextLeaf(true);
+ if (nextLeafExists) {
+ frameTuple.resetByTupleIndex(frame, tupleIndex);
+ return true;
+ } else {
+ return false;
+ }
+ }
+
+ frameTuple.resetByTupleIndex(frame, tupleIndex);
+ return true;
+ }
+
+ @Override
+ public void next() throws Exception {
+ tupleIndex++;
+ }
+
+ @Override
+ public void open(ICursorInitialState initialState, ISearchPredicate searchPred) throws HyracksDataException {
+ // in case open is called multiple times without closing
+ if (page != null) {
+ page.releaseReadLatch();
+ bufferCache.unpin(page);
+ }
+
+ page = initialState.getPage();
+ tupleIndex = 0;
+ frame.setPage(page);
+ MultiComparator lowKeyCmp = searchPred.getLowKeyComparator();
+ frameTuple.setFieldCount(lowKeyCmp.getFieldCount());
+ boolean leafExists = positionToNextLeaf(false);
+ if (!leafExists) {
+ throw new HyracksDataException(
+ "Failed to open disk-order scan cursor for tree index. Traget tree index has no leaves.");
+ }
+ }
+
+ @Override
+ public void reset() {
+ tupleIndex = 0;
+ currentPageId = -1;
+ maxPageId = -1;
+ page = null;
+ }
+
+ @Override
+ public void setBufferCache(IBufferCache bufferCache) {
+ this.bufferCache = bufferCache;
+ }
+
+ @Override
+ public void setFileId(int fileId) {
+ this.fileId = fileId;
+ }
+
+ public void setCurrentPageId(int currentPageId) {
+ this.currentPageId = currentPageId;
+ }
+
+ public void setMaxPageId(int maxPageId) {
+ this.maxPageId = maxPageId;
+ }
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/FindTupleMode.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/FindTupleMode.java
new file mode 100644
index 0000000..cea2500
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/FindTupleMode.java
@@ -0,0 +1,20 @@
+/*
+ * 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.ophelpers;
+
+public enum FindTupleMode {
+ FTM_INCLUSIVE, FTM_EXCLUSIVE, FTM_EXACT
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/FindTupleNoExactMatchPolicy.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/FindTupleNoExactMatchPolicy.java
new file mode 100644
index 0000000..0d534ed
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/FindTupleNoExactMatchPolicy.java
@@ -0,0 +1,20 @@
+/*
+ * 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.ophelpers;
+
+public enum FindTupleNoExactMatchPolicy {
+ FTP_LOWER_KEY, FTP_HIGHER_KEY
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/IndexOp.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/IndexOp.java
new file mode 100644
index 0000000..e40c5c8
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/IndexOp.java
@@ -0,0 +1,20 @@
+/*
+ * 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.ophelpers;
+
+public enum IndexOp {
+ INSERT, DELETE, UPDATE, SEARCH, DISKORDERSCAN
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/IndexOpContext.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/IndexOpContext.java
new file mode 100644
index 0000000..4f6e656
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/IndexOpContext.java
@@ -0,0 +1,5 @@
+package edu.uci.ics.hyracks.storage.am.common.ophelpers;
+
+public interface IndexOpContext {
+ void reset();
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/IntArrayList.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/IntArrayList.java
new file mode 100644
index 0000000..46551dd
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/IntArrayList.java
@@ -0,0 +1,89 @@
+/*
+ * 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.ophelpers;
+
+public class IntArrayList {
+ private int[] data;
+ private int size;
+ private int first;
+ private final int growth;
+
+ public IntArrayList(int initialCapacity, int growth) {
+ data = new int[initialCapacity];
+ size = 0;
+ first = 0;
+ this.growth = growth;
+ }
+
+ public int size() {
+ return size;
+ }
+
+ public int first() {
+ return first;
+ }
+
+ public void add(int i) {
+ if (size == data.length) {
+ int[] newData = new int[data.length + growth];
+ System.arraycopy(data, 0, newData, 0, data.length);
+ data = newData;
+ }
+
+ data[size++] = i;
+ }
+
+ public void removeLast() {
+ if (size > 0)
+ size--;
+ }
+
+ // WARNING: caller is responsible for checking size > 0
+ public int getLast() {
+ return data[size - 1];
+ }
+
+ public int get(int i) {
+ return data[i];
+ }
+
+ // WARNING: caller is responsible for checking i < size
+ public void set(int i, int value) {
+ data[i] = value;
+
+ }
+
+ public int getFirst() {
+ return data[first];
+ }
+
+ public void moveFirst() {
+ first++;
+ }
+
+ public void clear() {
+ size = 0;
+ first = 0;
+ }
+
+ public boolean isLast() {
+ return size == first;
+ }
+
+ public boolean isEmpty() {
+ return size == 0;
+ }
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/MultiComparator.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/MultiComparator.java
new file mode 100644
index 0000000..1842bf8
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/MultiComparator.java
@@ -0,0 +1,102 @@
+/*
+ * 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.ophelpers;
+
+import java.io.ByteArrayInputStream;
+import java.io.DataInput;
+import java.io.DataInputStream;
+
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparator;
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTrait;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.dataflow.common.data.comparators.IntegerBinaryComparatorFactory;
+
+public class MultiComparator {
+
+ private static final long serialVersionUID = 1L;
+
+ private IBinaryComparator[] cmps = null;
+ private ITypeTrait[] typeTraits;
+
+ private IBinaryComparator intCmp = IntegerBinaryComparatorFactory.INSTANCE.createBinaryComparator();
+
+ public IBinaryComparator getIntCmp() {
+ return intCmp;
+ }
+
+ public MultiComparator(ITypeTrait[] typeTraits, IBinaryComparator[] cmps) {
+ this.typeTraits = typeTraits;
+ this.cmps = cmps;
+ }
+
+ public int compare(ITupleReference tupleA, ITupleReference tupleB) {
+ for (int i = 0; i < cmps.length; i++) {
+ int cmp = cmps[i].compare(tupleA.getFieldData(i), tupleA.getFieldStart(i), tupleA.getFieldLength(i),
+ tupleB.getFieldData(i), tupleB.getFieldStart(i), tupleB.getFieldLength(i));
+ if (cmp < 0)
+ return -1;
+ else if (cmp > 0)
+ return 1;
+ }
+ return 0;
+ }
+
+ public int fieldRangeCompare(ITupleReference tupleA, ITupleReference tupleB, int startFieldIndex, int numFields) {
+ for (int i = startFieldIndex; i < startFieldIndex + numFields; i++) {
+ int cmp = cmps[i].compare(tupleA.getFieldData(i), tupleA.getFieldStart(i), tupleA.getFieldLength(i),
+ tupleB.getFieldData(i), tupleB.getFieldStart(i), tupleB.getFieldLength(i));
+ if (cmp < 0)
+ return -1;
+ else if (cmp > 0)
+ return 1;
+ }
+ return 0;
+ }
+
+ public String printTuple(ITupleReference tuple, ISerializerDeserializer[] fields) throws HyracksDataException {
+ StringBuilder strBuilder = new StringBuilder();
+ for (int i = 0; i < tuple.getFieldCount(); i++) {
+ ByteArrayInputStream inStream = new ByteArrayInputStream(tuple.getFieldData(i), tuple.getFieldStart(i),
+ tuple.getFieldLength(i));
+ DataInput dataIn = new DataInputStream(inStream);
+ Object o = fields[i].deserialize(dataIn);
+ strBuilder.append(o.toString() + " ");
+ }
+ return strBuilder.toString();
+ }
+
+ public IBinaryComparator[] getComparators() {
+ return cmps;
+ }
+
+ public int getKeyFieldCount() {
+ return cmps.length;
+ }
+
+ public void setComparators(IBinaryComparator[] cmps) {
+ this.cmps = cmps;
+ }
+
+ public int getFieldCount() {
+ return typeTraits.length;
+ }
+
+ public ITypeTrait[] getTypeTraits() {
+ return typeTraits;
+ }
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/SlotOffTupleOff.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/SlotOffTupleOff.java
new file mode 100644
index 0000000..4fc1861
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/SlotOffTupleOff.java
@@ -0,0 +1,33 @@
+/*
+ * 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.ophelpers;
+
+public class SlotOffTupleOff implements Comparable<SlotOffTupleOff> {
+ public int tupleIndex;
+ public int slotOff;
+ public int tupleOff;
+
+ public SlotOffTupleOff(int tupleIndex, int slotOff, int recOff) {
+ this.tupleIndex = tupleIndex;
+ this.slotOff = slotOff;
+ this.tupleOff = recOff;
+ }
+
+ @Override
+ public int compareTo(SlotOffTupleOff o) {
+ return tupleOff - o.tupleOff;
+ }
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/tuples/SimpleTupleReference.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/tuples/SimpleTupleReference.java
new file mode 100644
index 0000000..f9e00ac
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/tuples/SimpleTupleReference.java
@@ -0,0 +1,94 @@
+/*
+ * 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.tuples;
+
+import java.nio.ByteBuffer;
+
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrame;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleReference;
+
+public class SimpleTupleReference implements ITreeIndexTupleReference {
+
+ protected ByteBuffer buf;
+ protected int fieldStartIndex;
+ protected int fieldCount;
+ protected int tupleStartOff;
+ protected int nullFlagsBytes;
+ protected int fieldSlotsBytes;
+
+ @Override
+ public void resetByTupleOffset(ByteBuffer buf, int tupleStartOff) {
+ this.buf = buf;
+ this.tupleStartOff = tupleStartOff;
+ }
+
+ @Override
+ public void resetByTupleIndex(ITreeIndexFrame frame, int tupleIndex) {
+ resetByTupleOffset(frame.getBuffer(), frame.getTupleOffset(tupleIndex));
+ }
+
+ @Override
+ public void setFieldCount(int fieldCount) {
+ this.fieldCount = fieldCount;
+ nullFlagsBytes = getNullFlagsBytes();
+ fieldSlotsBytes = getFieldSlotsBytes();
+ fieldStartIndex = 0;
+ }
+
+ @Override
+ public void setFieldCount(int fieldStartIndex, int fieldCount) {
+ this.fieldCount = fieldCount;
+ this.fieldStartIndex = fieldStartIndex;
+ }
+
+ @Override
+ public int getFieldCount() {
+ return fieldCount;
+ }
+
+ @Override
+ public byte[] getFieldData(int fIdx) {
+ return buf.array();
+ }
+
+ @Override
+ public int getFieldLength(int fIdx) {
+ if (fIdx == 0) {
+ return buf.getShort(tupleStartOff + nullFlagsBytes);
+ } else {
+ return buf.getShort(tupleStartOff + nullFlagsBytes + fIdx * 2)
+ - buf.getShort(tupleStartOff + nullFlagsBytes + ((fIdx - 1) * 2));
+ }
+ }
+
+ @Override
+ public int getFieldStart(int fIdx) {
+ if (fIdx == 0) {
+ return tupleStartOff + nullFlagsBytes + fieldSlotsBytes;
+ } else {
+ return tupleStartOff + nullFlagsBytes + fieldSlotsBytes
+ + buf.getShort(tupleStartOff + nullFlagsBytes + ((fIdx - 1) * 2));
+ }
+ }
+
+ protected int getNullFlagsBytes() {
+ return (int) Math.ceil(fieldCount / 8.0);
+ }
+
+ protected int getFieldSlotsBytes() {
+ return fieldCount * 2;
+ }
+}
\ No newline at end of file
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/tuples/SimpleTupleWriter.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/tuples/SimpleTupleWriter.java
new file mode 100644
index 0000000..1730c4a
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/tuples/SimpleTupleWriter.java
@@ -0,0 +1,110 @@
+/*
+ * 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.tuples;
+
+import java.nio.ByteBuffer;
+
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleReference;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleWriter;
+
+public class SimpleTupleWriter implements ITreeIndexTupleWriter {
+
+ @Override
+ public int bytesRequired(ITupleReference tuple) {
+ int bytes = getNullFlagsBytes(tuple) + getFieldSlotsBytes(tuple);
+ for (int i = 0; i < tuple.getFieldCount(); i++) {
+ bytes += tuple.getFieldLength(i);
+ }
+ return bytes;
+ }
+
+ @Override
+ public int bytesRequired(ITupleReference tuple, int startField, int numFields) {
+ int bytes = getNullFlagsBytes(tuple, startField, numFields) + getFieldSlotsBytes(tuple, startField, numFields);
+ for (int i = startField; i < startField + numFields; i++) {
+ bytes += tuple.getFieldLength(i);
+ }
+ return bytes;
+ }
+
+ @Override
+ public ITreeIndexTupleReference createTupleReference() {
+ return new SimpleTupleReference();
+ }
+
+ @Override
+ public int writeTuple(ITupleReference tuple, ByteBuffer targetBuf, int targetOff) {
+ int runner = targetOff;
+ int nullFlagsBytes = getNullFlagsBytes(tuple);
+ int fieldSlotsBytes = getFieldSlotsBytes(tuple);
+ for (int i = 0; i < nullFlagsBytes; i++) {
+ targetBuf.put(runner++, (byte) 0);
+ }
+ runner += fieldSlotsBytes;
+
+ int fieldEndOff = 0;
+ for (int i = 0; i < tuple.getFieldCount(); i++) {
+ System.arraycopy(tuple.getFieldData(i), tuple.getFieldStart(i), targetBuf.array(), runner,
+ tuple.getFieldLength(i));
+ fieldEndOff += tuple.getFieldLength(i);
+ runner += tuple.getFieldLength(i);
+ targetBuf.putShort(targetOff + nullFlagsBytes + i * 2, (short) fieldEndOff);
+ }
+
+ return runner - targetOff;
+ }
+
+ @Override
+ public int writeTupleFields(ITupleReference tuple, int startField, int numFields, ByteBuffer targetBuf,
+ int targetOff) {
+ int runner = targetOff;
+ int nullFlagsBytes = getNullFlagsBytes(tuple, startField, numFields);
+ for (int i = 0; i < nullFlagsBytes; i++) {
+ targetBuf.put(runner++, (byte) 0);
+ }
+ runner += getFieldSlotsBytes(tuple, startField, numFields);
+
+ int fieldEndOff = 0;
+ int fieldCounter = 0;
+ for (int i = startField; i < startField + numFields; i++) {
+ System.arraycopy(tuple.getFieldData(i), tuple.getFieldStart(i), targetBuf.array(), runner,
+ tuple.getFieldLength(i));
+ fieldEndOff += tuple.getFieldLength(i);
+ runner += tuple.getFieldLength(i);
+ targetBuf.putShort(targetOff + nullFlagsBytes + fieldCounter * 2, (short) fieldEndOff);
+ fieldCounter++;
+ }
+
+ return runner - targetOff;
+ }
+
+ protected int getNullFlagsBytes(ITupleReference tuple) {
+ return (int) Math.ceil((double) tuple.getFieldCount() / 8.0);
+ }
+
+ protected int getFieldSlotsBytes(ITupleReference tuple) {
+ return tuple.getFieldCount() * 2;
+ }
+
+ protected int getNullFlagsBytes(ITupleReference tuple, int startField, int numFields) {
+ return (int) Math.ceil((double) numFields / 8.0);
+ }
+
+ protected int getFieldSlotsBytes(ITupleReference tuple, int startField, int numFields) {
+ return numFields * 2;
+ }
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/tuples/SimpleTupleWriterFactory.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/tuples/SimpleTupleWriterFactory.java
new file mode 100644
index 0000000..ebb2905
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/tuples/SimpleTupleWriterFactory.java
@@ -0,0 +1,30 @@
+/*
+ * 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.tuples;
+
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleWriter;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleWriterFactory;
+
+public class SimpleTupleWriterFactory implements ITreeIndexTupleWriterFactory {
+
+ private static final long serialVersionUID = 1L;
+
+ @Override
+ public ITreeIndexTupleWriter createTupleWriter() {
+ return new SimpleTupleWriter();
+ }
+
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/tuples/TypeAwareTupleReference.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/tuples/TypeAwareTupleReference.java
new file mode 100644
index 0000000..4f571b3
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/tuples/TypeAwareTupleReference.java
@@ -0,0 +1,120 @@
+/*
+ * 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.tuples;
+
+import java.nio.ByteBuffer;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTrait;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrame;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleReference;
+
+public class TypeAwareTupleReference implements ITreeIndexTupleReference {
+ protected ByteBuffer buf;
+ protected int fieldStartIndex;
+ protected int fieldCount;
+ protected int tupleStartOff;
+ protected int nullFlagsBytes;
+ protected int dataStartOff;
+
+ protected ITypeTrait[] typeTraits;
+ protected VarLenIntEncoderDecoder encDec = new VarLenIntEncoderDecoder();
+ protected int[] decodedFieldSlots;
+
+ public TypeAwareTupleReference(ITypeTrait[] typeTraits) {
+ this.typeTraits = typeTraits;
+ this.fieldStartIndex = 0;
+ }
+
+ @Override
+ public void resetByTupleOffset(ByteBuffer buf, int tupleStartOff) {
+ this.buf = buf;
+ this.tupleStartOff = tupleStartOff;
+
+ // decode field slots
+ int field = 0;
+ int cumul = 0;
+ int end = fieldStartIndex + fieldCount;
+ encDec.reset(buf.array(), tupleStartOff + nullFlagsBytes);
+ for (int i = fieldStartIndex; i < end; i++) {
+ int staticDataLen = typeTraits[i].getStaticallyKnownDataLength();
+ if (staticDataLen == ITypeTrait.VARIABLE_LENGTH) {
+ cumul += encDec.decode();
+ decodedFieldSlots[field++] = cumul;
+ } else {
+ cumul += staticDataLen;
+ decodedFieldSlots[field++] = cumul;
+ }
+ }
+ dataStartOff = encDec.getPos();
+ }
+
+ @Override
+ public void resetByTupleIndex(ITreeIndexFrame frame, int tupleIndex) {
+ resetByTupleOffset(frame.getBuffer(), frame.getTupleOffset(tupleIndex));
+ }
+
+ @Override
+ public void setFieldCount(int fieldCount) {
+ this.fieldCount = fieldCount;
+ if (decodedFieldSlots == null) {
+ decodedFieldSlots = new int[fieldCount];
+ } else {
+ if (fieldCount > decodedFieldSlots.length) {
+ decodedFieldSlots = new int[fieldCount];
+ }
+ }
+ nullFlagsBytes = getNullFlagsBytes();
+ this.fieldStartIndex = 0;
+ }
+
+ @Override
+ public void setFieldCount(int fieldStartIndex, int fieldCount) {
+ setFieldCount(fieldCount);
+ this.fieldStartIndex = fieldStartIndex;
+ }
+
+ @Override
+ public int getFieldCount() {
+ return fieldCount;
+ }
+
+ @Override
+ public byte[] getFieldData(int fIdx) {
+ return buf.array();
+ }
+
+ @Override
+ public int getFieldLength(int fIdx) {
+ if (fIdx == 0) {
+ return decodedFieldSlots[0];
+ } else {
+ return decodedFieldSlots[fIdx] - decodedFieldSlots[fIdx - 1];
+ }
+ }
+
+ @Override
+ public int getFieldStart(int fIdx) {
+ if (fIdx == 0) {
+ return dataStartOff;
+ } else {
+ return dataStartOff + decodedFieldSlots[fIdx - 1];
+ }
+ }
+
+ protected int getNullFlagsBytes() {
+ return (int) Math.ceil(fieldCount / 8.0);
+ }
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/tuples/TypeAwareTupleWriter.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/tuples/TypeAwareTupleWriter.java
new file mode 100644
index 0000000..81b48e5
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/tuples/TypeAwareTupleWriter.java
@@ -0,0 +1,148 @@
+/*
+ * 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.tuples;
+
+import java.nio.ByteBuffer;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTrait;
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleReference;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleWriter;
+
+public class TypeAwareTupleWriter implements ITreeIndexTupleWriter {
+
+ protected ITypeTrait[] typeTraits;
+ protected VarLenIntEncoderDecoder encDec = new VarLenIntEncoderDecoder();
+
+ public TypeAwareTupleWriter(ITypeTrait[] typeTraits) {
+ this.typeTraits = typeTraits;
+ }
+
+ @Override
+ public int bytesRequired(ITupleReference tuple) {
+ int bytes = getNullFlagsBytes(tuple) + getFieldSlotsBytes(tuple);
+ for (int i = 0; i < tuple.getFieldCount(); i++) {
+ bytes += tuple.getFieldLength(i);
+ }
+ return bytes;
+ }
+
+ @Override
+ public int bytesRequired(ITupleReference tuple, int startField, int numFields) {
+ int bytes = getNullFlagsBytes(numFields) + getFieldSlotsBytes(tuple, startField, numFields);
+ for (int i = startField; i < startField + numFields; i++) {
+ bytes += tuple.getFieldLength(i);
+ }
+ return bytes;
+ }
+
+ @Override
+ public ITreeIndexTupleReference createTupleReference() {
+ return new TypeAwareTupleReference(typeTraits);
+ }
+
+ @Override
+ public int writeTuple(ITupleReference tuple, ByteBuffer targetBuf, int targetOff) {
+ int runner = targetOff;
+ int nullFlagsBytes = getNullFlagsBytes(tuple);
+ // write null indicator bits
+ for (int i = 0; i < nullFlagsBytes; i++) {
+ targetBuf.put(runner++, (byte) 0);
+ }
+
+ // write field slots for variable length fields
+ encDec.reset(targetBuf.array(), runner);
+ for (int i = 0; i < tuple.getFieldCount(); i++) {
+ if (typeTraits[i].getStaticallyKnownDataLength() == ITypeTrait.VARIABLE_LENGTH) {
+ encDec.encode(tuple.getFieldLength(i));
+ }
+ }
+ runner = encDec.getPos();
+
+ // write data fields
+ for (int i = 0; i < tuple.getFieldCount(); i++) {
+ System.arraycopy(tuple.getFieldData(i), tuple.getFieldStart(i), targetBuf.array(), runner,
+ tuple.getFieldLength(i));
+ runner += tuple.getFieldLength(i);
+ }
+
+ return runner - targetOff;
+ }
+
+ @Override
+ public int writeTupleFields(ITupleReference tuple, int startField, int numFields, ByteBuffer targetBuf,
+ int targetOff) {
+ int runner = targetOff;
+ int nullFlagsBytes = getNullFlagsBytes(numFields);
+ // write null indicator bits
+ for (int i = 0; i < nullFlagsBytes; i++) {
+ targetBuf.put(runner++, (byte) 0);
+ }
+
+ // write field slots for variable length fields
+ encDec.reset(targetBuf.array(), runner);
+ for (int i = startField; i < startField + numFields; i++) {
+ if (typeTraits[i].getStaticallyKnownDataLength() == ITypeTrait.VARIABLE_LENGTH) {
+ encDec.encode(tuple.getFieldLength(i));
+ }
+ }
+ runner = encDec.getPos();
+
+ for (int i = startField; i < startField + numFields; i++) {
+ System.arraycopy(tuple.getFieldData(i), tuple.getFieldStart(i), targetBuf.array(), runner,
+ tuple.getFieldLength(i));
+ runner += tuple.getFieldLength(i);
+ }
+
+ return runner - targetOff;
+ }
+
+ protected int getNullFlagsBytes(ITupleReference tuple) {
+ return (int) Math.ceil((double) tuple.getFieldCount() / 8.0);
+ }
+
+ protected int getFieldSlotsBytes(ITupleReference tuple) {
+ int fieldSlotBytes = 0;
+ for (int i = 0; i < tuple.getFieldCount(); i++) {
+ if (typeTraits[i].getStaticallyKnownDataLength() == ITypeTrait.VARIABLE_LENGTH) {
+ fieldSlotBytes += encDec.getBytesRequired(tuple.getFieldLength(i));
+ }
+ }
+ return fieldSlotBytes;
+ }
+
+ protected int getNullFlagsBytes(int numFields) {
+ return (int) Math.ceil((double) numFields / 8.0);
+ }
+
+ protected int getFieldSlotsBytes(ITupleReference tuple, int startField, int numFields) {
+ int fieldSlotBytes = 0;
+ for (int i = startField; i < startField + numFields; i++) {
+ if (typeTraits[i].getStaticallyKnownDataLength() == ITypeTrait.VARIABLE_LENGTH) {
+ fieldSlotBytes += encDec.getBytesRequired(tuple.getFieldLength(i));
+ }
+ }
+ return fieldSlotBytes;
+ }
+
+ public ITypeTrait[] getTypeTraits() {
+ return typeTraits;
+ }
+
+ public void setTypeTraits(ITypeTrait[] typeTraits) {
+ this.typeTraits = typeTraits;
+ }
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/tuples/TypeAwareTupleWriterFactory.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/tuples/TypeAwareTupleWriterFactory.java
new file mode 100644
index 0000000..82072ae
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/tuples/TypeAwareTupleWriterFactory.java
@@ -0,0 +1,36 @@
+/*
+ * 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.tuples;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTrait;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleWriter;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleWriterFactory;
+
+public class TypeAwareTupleWriterFactory implements ITreeIndexTupleWriterFactory {
+
+ private static final long serialVersionUID = 1L;
+ private ITypeTrait[] typeTraits;
+
+ public TypeAwareTupleWriterFactory(ITypeTrait[] typeTraits) {
+ this.typeTraits = typeTraits;
+ }
+
+ @Override
+ public ITreeIndexTupleWriter createTupleWriter() {
+ return new TypeAwareTupleWriter(typeTraits);
+ }
+
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/tuples/VarLenIntEncoderDecoder.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/tuples/VarLenIntEncoderDecoder.java
new file mode 100644
index 0000000..d266d41
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/tuples/VarLenIntEncoderDecoder.java
@@ -0,0 +1,88 @@
+/*
+ * 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.tuples;
+
+// encodes positive integers in a variable-byte format
+
+public class VarLenIntEncoderDecoder {
+ public static final int ENCODE_MASK = 0x0000007F;
+ public static final byte CONTINUE_CHUNK = (byte) 0x80;
+ public static final byte DECODE_MASK = (byte) 0x7F;
+
+ private byte[] encTmp = new byte[5];
+
+ private int pos;
+ private byte[] bytes;
+
+ public void reset(byte[] bytes, int pos) {
+ this.bytes = bytes;
+ this.pos = pos;
+ }
+
+ public int encode(int val) {
+ int origPos = 0;
+ int tmpPos = 0;
+ while (val > ENCODE_MASK) {
+ encTmp[tmpPos++] = (byte) (val & ENCODE_MASK);
+ val = val >>> 7;
+ }
+ encTmp[tmpPos++] = (byte) (val);
+
+ // reverse order to optimize for decoding speed
+ for (int i = 0; i < tmpPos - 1; i++) {
+ bytes[pos++] = (byte) (encTmp[tmpPos - 1 - i] | CONTINUE_CHUNK);
+ }
+ bytes[pos++] = encTmp[0];
+
+ return pos - origPos;
+ }
+
+ public int decode() {
+ int sum = 0;
+ while ((bytes[pos] & CONTINUE_CHUNK) == CONTINUE_CHUNK) {
+ sum = (sum + (bytes[pos] & DECODE_MASK)) << 7;
+ pos++;
+ }
+ sum += bytes[pos++];
+ return sum;
+ }
+
+ // calculate the number of bytes needed for encoding
+ public int getBytesRequired(int val) {
+ int byteCount = 0;
+ while (val > ENCODE_MASK) {
+ val = val >>> 7;
+ byteCount++;
+ }
+ return byteCount + 1;
+ }
+
+ public int getPos() {
+ return pos;
+ }
+
+ // fast encoding, slow decoding version
+ /*
+ * public void encode(int val) { while(val > ENCODE_MASK) { bytes[pos++] =
+ * (byte)(((byte)(val & ENCODE_MASK)) | CONTINUE_CHUNK); val = val >>> 7; }
+ * bytes[pos++] = (byte)(val); }
+ *
+ * public int decode() { int sum = 0; int shift = 0; while( (bytes[pos] &
+ * CONTINUE_CHUNK) == CONTINUE_CHUNK) { sum = (sum + (bytes[pos] &
+ * DECODE_MASK)) << 7 * shift++; pos++; } sum += bytes[pos++] << 7 * shift;
+ * return sum; }
+ */
+}
\ No newline at end of file
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/utility/TreeIndexBufferCacheWarmup.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/utility/TreeIndexBufferCacheWarmup.java
new file mode 100644
index 0000000..eb261da
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/utility/TreeIndexBufferCacheWarmup.java
@@ -0,0 +1,84 @@
+package edu.uci.ics.hyracks.storage.am.common.utility;
+
+import java.util.ArrayList;
+import java.util.Random;
+
+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.ITreeIndexFrame;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrame;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.IntArrayList;
+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 TreeIndexBufferCacheWarmup {
+ private final IBufferCache bufferCache;
+ private final IFreePageManager freePageManager;
+ private final int fileId;
+ private final ArrayList<IntArrayList> pagesByLevel = new ArrayList<IntArrayList>();
+ private final Random rnd = new Random();
+
+ public TreeIndexBufferCacheWarmup(IBufferCache bufferCache, IFreePageManager freePageManager, int fileId) {
+ this.bufferCache = bufferCache;
+ this.freePageManager = freePageManager;
+ this.fileId = fileId;
+ }
+
+ public void warmup(ITreeIndexFrame frame, ITreeIndexMetaDataFrame metaFrame, int[] warmupTreeLevels,
+ int[] warmupRepeats) throws HyracksDataException {
+ bufferCache.openFile(fileId);
+
+ // scan entire file to determine pages in each level
+ int maxPageId = freePageManager.getMaxPage(metaFrame);
+ for (int pageId = 0; pageId <= maxPageId; pageId++) {
+ ICachedPage page = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
+ page.acquireReadLatch();
+ try {
+ frame.setPage(page);
+ byte level = frame.getLevel();
+ while (level >= pagesByLevel.size()) {
+ pagesByLevel.add(new IntArrayList(100, 100));
+ }
+ if (level >= 0) {
+ // System.out.println("ADDING: " + level + " " + pageId);
+ pagesByLevel.get(level).add(pageId);
+ }
+ } finally {
+ page.releaseReadLatch();
+ bufferCache.unpin(page);
+ }
+ }
+
+ // pin certain pages again to simulate frequent access
+ for (int i = 0; i < warmupTreeLevels.length; i++) {
+ if (warmupTreeLevels[i] < pagesByLevel.size()) {
+ int repeats = warmupRepeats[i];
+ IntArrayList pageIds = pagesByLevel.get(warmupTreeLevels[i]);
+ int[] remainingPageIds = new int[pageIds.size()];
+ for (int r = 0; r < repeats; r++) {
+ for (int j = 0; j < pageIds.size(); j++) {
+ remainingPageIds[j] = pageIds.get(j);
+ }
+
+ int remainingLength = pageIds.size();
+ for (int j = 0; j < pageIds.size(); j++) {
+ int index = Math.abs(rnd.nextInt()) % remainingLength;
+ int pageId = remainingPageIds[index];
+
+ // pin & latch then immediately unlatch & unpin
+ ICachedPage page = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
+ page.acquireReadLatch();
+ page.releaseReadLatch();
+ bufferCache.unpin(page);
+
+ remainingPageIds[index] = remainingPageIds[remainingLength - 1];
+ remainingLength--;
+ }
+ }
+ }
+ }
+
+ bufferCache.closeFile(fileId);
+ }
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/utility/TreeIndexStats.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/utility/TreeIndexStats.java
new file mode 100644
index 0000000..5b01b2d
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/utility/TreeIndexStats.java
@@ -0,0 +1,134 @@
+package edu.uci.ics.hyracks.storage.am.common.utility;
+
+import java.text.DecimalFormat;
+
+import edu.uci.ics.hyracks.storage.am.common.api.IFreePageManager;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrame;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrame;
+
+public class TreeIndexStats {
+
+ private TreeIndexNodeTypeStats rootStats = new TreeIndexNodeTypeStats();
+ private TreeIndexNodeTypeStats interiorStats = new TreeIndexNodeTypeStats();
+ private TreeIndexNodeTypeStats leafStats = new TreeIndexNodeTypeStats();
+
+ private int freePages = 0;
+ private int metaPages = 0;
+ private int treeLevels = 0;
+
+ public void begin() {
+ rootStats.clear();
+ interiorStats.clear();
+ leafStats.clear();
+ freePages = 0;
+ metaPages = 0;
+ treeLevels = 0;
+ }
+
+ public void addRoot(ITreeIndexFrame frame) {
+ treeLevels = frame.getLevel() + 1;
+ rootStats.add(frame);
+ }
+
+ public void add(ITreeIndexFrame frame) {
+ if (frame.isLeaf()) {
+ leafStats.add(frame);
+ } else if (frame.isInterior()) {
+ interiorStats.add(frame);
+ }
+ }
+
+ public void add(ITreeIndexMetaDataFrame metaFrame, IFreePageManager freePageManager) {
+ if (freePageManager.isFreePage(metaFrame)) {
+ freePages++;
+ } else if (freePageManager.isMetaPage(metaFrame)) {
+ metaPages++;
+ }
+ }
+
+ public void end() {
+ // nothing here currently
+ }
+
+ @Override
+ public String toString() {
+ StringBuilder strBuilder = new StringBuilder();
+ DecimalFormat df = new DecimalFormat("#####.##");
+
+ strBuilder.append("TREE LEVELS: " + treeLevels + "\n");
+ strBuilder.append("FREE PAGES : " + freePages + "\n");
+ strBuilder.append("META PAGES : " + metaPages + "\n");
+ long totalPages = interiorStats.getNumPages() + leafStats.getNumPages() + freePages + metaPages;
+ strBuilder.append("TOTAL PAGES : " + totalPages + "\n");
+
+ strBuilder.append("\n");
+ strBuilder.append("ROOT STATS" + "\n");
+ strBuilder.append("NUM TUPLES: " + rootStats.getNumTuples() + "\n");
+ strBuilder.append("FILL FACTOR : " + df.format(rootStats.getAvgFillFactor()) + "\n");
+
+ if (interiorStats.getNumPages() > 0) {
+ strBuilder.append("\n");
+ strBuilder.append("INTERIOR STATS" + "\n");
+ strBuilder.append("NUM PAGES: " + interiorStats.getNumPages() + "\n");
+ strBuilder.append("NUM TUPLES: " + interiorStats.getNumTuples() + "\n");
+ strBuilder.append("AVG TUPLES/PAGE: " + df.format(interiorStats.getAvgNumTuples()) + "\n");
+ strBuilder.append("AVG FILL FACTOR: " + df.format(interiorStats.getAvgFillFactor()) + "\n");
+ }
+
+ if (leafStats.getNumPages() > 0) {
+ strBuilder.append("\n");
+ strBuilder.append("LEAF STATS" + "\n");
+ strBuilder.append("NUM PAGES: " + df.format(leafStats.getNumPages()) + "\n");
+ strBuilder.append("NUM TUPLES: " + df.format(leafStats.getNumTuples()) + "\n");
+ strBuilder.append("AVG TUPLES/PAGE: " + df.format(leafStats.getAvgNumTuples()) + "\n");
+ strBuilder.append("AVG FILL FACTOR: " + df.format(leafStats.getAvgFillFactor()) + "\n");
+ }
+
+ return strBuilder.toString();
+ }
+
+ public class TreeIndexNodeTypeStats {
+ private long numTuples;
+ private long sumTuplesSizes;
+ private long numPages;
+ private double sumFillFactors;
+
+ public void clear() {
+ numTuples = 0;
+ sumTuplesSizes = 0;
+ numPages = 0;
+ }
+
+ public void add(ITreeIndexFrame frame) {
+ numPages++;
+ numTuples += frame.getTupleCount();
+ sumFillFactors += (double) (frame.getBuffer().capacity() - frame.getTotalFreeSpace())
+ / (double) frame.getBuffer().capacity();
+ }
+
+ public long getNumTuples() {
+ return numTuples;
+ }
+
+ public long getSumTupleSizes() {
+ return sumTuplesSizes;
+ }
+
+ public long getNumPages() {
+ return numPages;
+ }
+
+ public double getAvgNumTuples() {
+ return (double) numTuples / (double) numPages;
+ }
+
+ public double getAvgTupleSize() {
+ return (double) sumTuplesSizes / (double) numTuples;
+ }
+
+ public double getAvgFillFactor() {
+ return sumFillFactors / numPages;
+ }
+ }
+
+}
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/utility/TreeIndexStatsGatherer.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/utility/TreeIndexStatsGatherer.java
new file mode 100644
index 0000000..fc0ab5e
--- /dev/null
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/utility/TreeIndexStatsGatherer.java
@@ -0,0 +1,70 @@
+package edu.uci.ics.hyracks.storage.am.common.utility;
+
+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.ITreeIndexFrame;
+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 TreeIndexStatsGatherer {
+
+ private final TreeIndexStats treeIndexStats = new TreeIndexStats();
+ private final IBufferCache bufferCache;
+ private final IFreePageManager freePageManager;
+ private final int fileId;
+ private final int rootPage;
+
+ public TreeIndexStatsGatherer(IBufferCache bufferCache, IFreePageManager freePageManager, int fileId, int rootPage) {
+ this.bufferCache = bufferCache;
+ this.freePageManager = freePageManager;
+ this.fileId = fileId;
+ this.rootPage = rootPage;
+ }
+
+ public TreeIndexStats gatherStats(ITreeIndexFrame leafFrame, ITreeIndexFrame interiorFrame,
+ ITreeIndexMetaDataFrame metaFrame) throws HyracksDataException {
+
+ bufferCache.openFile(fileId);
+
+ treeIndexStats.begin();
+
+ int maxPageId = freePageManager.getMaxPage(metaFrame);
+ for (int pageId = 0; pageId <= maxPageId; pageId++) {
+ ICachedPage page = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
+ page.acquireReadLatch();
+ try {
+ metaFrame.setPage(page);
+ leafFrame.setPage(page);
+ interiorFrame.setPage(page);
+
+ if (leafFrame.isLeaf()) {
+ if (pageId == rootPage) {
+ treeIndexStats.addRoot(leafFrame);
+ } else {
+ treeIndexStats.add(leafFrame);
+ }
+ } else if (interiorFrame.isInterior()) {
+ if (pageId == rootPage) {
+ treeIndexStats.addRoot(interiorFrame);
+ } else {
+ treeIndexStats.add(interiorFrame);
+ }
+ } else {
+ treeIndexStats.add(metaFrame, freePageManager);
+ }
+
+ } finally {
+ page.releaseReadLatch();
+ bufferCache.unpin(page);
+ }
+ }
+
+ treeIndexStats.end();
+
+ bufferCache.closeFile(fileId);
+
+ return treeIndexStats;
+ }
+}