Finished cleaning up the BTreeNSMInteriorNode.
git-svn-id: https://hyracks.googlecode.com/svn/branches/hyracks_btree_updates_next@644 123451ca-8445-de46-9d55-352943316053
diff --git a/hyracks-dataflow-common/src/main/java/edu/uci/ics/hyracks/dataflow/common/util/TupleUtils.java b/hyracks-dataflow-common/src/main/java/edu/uci/ics/hyracks/dataflow/common/util/TupleUtils.java
index d95d8a5..093d17a 100644
--- a/hyracks-dataflow-common/src/main/java/edu/uci/ics/hyracks/dataflow/common/util/TupleUtils.java
+++ b/hyracks-dataflow-common/src/main/java/edu/uci/ics/hyracks/dataflow/common/util/TupleUtils.java
@@ -78,7 +78,7 @@
if (i != fields.length - 1) {
strBuilder.append(" ");
}
- }
+ }
return strBuilder.toString();
}
}
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeFrame.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeFrame.java
index f6c9455..7d981cb 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeFrame.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeFrame.java
@@ -1,5 +1,6 @@
package edu.uci.ics.hyracks.storage.am.btree.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.api.ITreeIndexFrame;
import edu.uci.ics.hyracks.storage.am.common.api.TreeIndexException;
@@ -9,6 +10,7 @@
public int findUpdateTupleIndex(ITupleReference tuple, MultiComparator cmp) throws TreeIndexException;
public int findInsertTupleIndex(ITupleReference tuple, MultiComparator cmp) throws TreeIndexException;
public int findDeleteTupleIndex(ITupleReference tuple, MultiComparator cmp) throws TreeIndexException;
+ public void insertSorted(ITupleReference tuple, MultiComparator cmp) throws HyracksDataException;
public boolean getSmFlag();
public void setSmFlag(boolean smFlag);
public void setMultiComparator(MultiComparator cmp);
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeInteriorFrame.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeInteriorFrame.java
index 09af783..23fdcf5 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeInteriorFrame.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeInteriorFrame.java
@@ -15,21 +15,16 @@
package edu.uci.ics.hyracks.storage.am.btree.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.btree.impls.RangePredicate;
-import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
public interface IBTreeInteriorFrame extends IBTreeFrame {
- public void insertSorted(ITupleReference tuple, MultiComparator cmp) throws HyracksDataException;
-
- public int getChildPageId(RangePredicate pred, MultiComparator srcCmp);
+ public int getChildPageId(RangePredicate pred);
- public int getLeftmostChildPageId(MultiComparator cmp);
+ public int getLeftmostChildPageId();
- public int getRightmostChildPageId(MultiComparator cmp);
+ public int getRightmostChildPageId();
public void setRightmostChildPageId(int pageId);
- public void deleteGreatest(MultiComparator cmp);
+ public void deleteGreatest();
}
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeLeafFrame.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeLeafFrame.java
index 3429ba6..a079527 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeLeafFrame.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeLeafFrame.java
@@ -23,8 +23,6 @@
import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
public interface IBTreeLeafFrame extends IBTreeFrame {
- public void insertSorted(ITupleReference tuple, MultiComparator cmp) throws HyracksDataException;
-
public void setNextLeaf(int nextPage);
public int getNextLeaf();
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMInteriorFrame.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMInteriorFrame.java
index 09aadb8..05b9cf1 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMInteriorFrame.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMInteriorFrame.java
@@ -15,16 +15,13 @@
package edu.uci.ics.hyracks.storage.am.btree.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.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeInteriorFrame;
import edu.uci.ics.hyracks.storage.am.btree.impls.RangePredicate;
import edu.uci.ics.hyracks.storage.am.common.api.ISplitKey;
@@ -42,13 +39,13 @@
public class BTreeNSMInteriorFrame extends TreeIndexNSMFrame implements IBTreeInteriorFrame {
private static final int rightLeafOff = smFlagOff + 1;
- private static final int childPtrSize = 4;
-
+ private static final int childPtrSize = 4;
+
private final ITreeIndexTupleReference cmpFrameTuple;
private MultiComparator cmp;
-
- public BTreeNSMInteriorFrame(ITreeIndexTupleWriter tupleWriter) {
- super(tupleWriter, new OrderedSlotManager());
+
+ public BTreeNSMInteriorFrame(ITreeIndexTupleWriter tupleWriter) {
+ super(tupleWriter, new OrderedSlotManager());
cmpFrameTuple = tupleWriter.createTupleReference();
}
@@ -59,9 +56,15 @@
}
@Override
+ public int findInsertTupleIndex(ITupleReference tuple, MultiComparator cmp) throws TreeIndexException {
+ return slotManager.findTupleIndex(tuple, frameTuple, cmp, FindTupleMode.INCLUSIVE,
+ FindTupleNoExactMatchPolicy.HIGHER_KEY);
+ }
+
+ @Override
public FrameOpSpaceStatus hasSpaceInsert(ITupleReference tuple) {
- // Tuple bytes + child pointer + slot.
- int bytesRequired = tupleWriter.bytesRequired(tuple) + childPtrSize + slotManager.getSlotSize();
+ // Tuple bytes + child pointer + slot.
+ int bytesRequired = tupleWriter.bytesRequired(tuple) + childPtrSize + slotManager.getSlotSize();
if (bytesRequired <= getFreeContiguousSpace()) {
return FrameOpSpaceStatus.SUFFICIENT_CONTIGUOUS_SPACE;
}
@@ -72,23 +75,6 @@
}
@Override
- public int findInsertTupleIndex(ITupleReference tuple, MultiComparator cmp) throws TreeIndexException {
- return slotManager.findTupleIndex(tuple, frameTuple, cmp, FindTupleMode.INCLUSIVE,
- FindTupleNoExactMatchPolicy.HIGHER_KEY);
- }
-
- @Override
- public int findDeleteTupleIndex(ITupleReference tuple, MultiComparator cmp) throws TreeIndexException {
- return slotManager.findTupleIndex(tuple, frameTuple, cmp, FindTupleMode.INCLUSIVE,
- FindTupleNoExactMatchPolicy.HIGHER_KEY);
- }
-
- @Override
- public int findUpdateTupleIndex(ITupleReference tuple, MultiComparator cmp) throws TreeIndexException {
- throw new UnsupportedOperationException("Cannot update tuples in interior node.");
- }
-
- @Override
public void insert(ITupleReference tuple, int tupleIndex) {
int slotOff = slotManager.insertSlot(tupleIndex, buf.getInt(freeSpaceOff));
int freeSpace = buf.getInt(freeSpaceOff);
@@ -96,22 +82,20 @@
System.arraycopy(tuple.getFieldData(tuple.getFieldCount() - 1), getLeftChildPageOff(tuple), buf.array(),
freeSpace + bytesWritten, childPtrSize);
int tupleSize = bytesWritten + childPtrSize;
-
buf.putInt(tupleCountOff, buf.getInt(tupleCountOff) + 1);
buf.putInt(freeSpaceOff, buf.getInt(freeSpaceOff) + tupleSize);
buf.putInt(totalFreeSpaceOff, buf.getInt(totalFreeSpaceOff) - tupleSize - slotManager.getSlotSize());
-
- // did insert into the rightmost slot?
+ // Did we insert into the rightmost slot?
if (slotOff == slotManager.getSlotEndOff()) {
- System.arraycopy(tuple.getFieldData(tuple.getFieldCount() - 1), getLeftChildPageOff(tuple)
- + childPtrSize, buf.array(), rightLeafOff, childPtrSize);
+ System.arraycopy(tuple.getFieldData(tuple.getFieldCount() - 1), getLeftChildPageOff(tuple) + childPtrSize,
+ buf.array(), rightLeafOff, childPtrSize);
} else {
- // if slotOff has a right (slot-)neighbor then update its child
- // pointer
- // the only time when this is NOT the case, is when this is the
- // first tuple
- // (or when the splitkey goes into the rightmost slot but that
- // case was handled in the if above)
+ // If slotOff has a right (slot-)neighbor then update its child
+ // pointer.
+ // The only time when this is NOT the case, is when this is the
+ // very first tuple (or when the splitkey goes into the rightmost
+ // slot but that
+ // case is handled in the if above).
if (buf.getInt(tupleCountOff) > 1) {
int rightNeighborOff = slotOff - slotManager.getSlotSize();
frameTuple.resetByTupleOffset(buf, slotManager.getTupleOff(rightNeighborOff));
@@ -120,191 +104,11 @@
}
}
}
-
+
@Override
- public void insertSorted(ITupleReference tuple, MultiComparator cmp) throws HyracksDataException {
- int freeSpace = buf.getInt(freeSpaceOff);
- slotManager.insertSlot(-1, freeSpace);
- int bytesWritten = tupleWriter.writeTupleFields(tuple, 0, cmp.getKeyFieldCount(), buf, freeSpace);
- System.arraycopy(tuple.getFieldData(cmp.getKeyFieldCount() - 1), getLeftChildPageOff(tuple), buf.array(),
- freeSpace + bytesWritten, childPtrSize);
- int tupleSize = bytesWritten + childPtrSize;
- buf.putInt(tupleCountOff, buf.getInt(tupleCountOff) + 1);
- buf.putInt(freeSpaceOff, buf.getInt(freeSpaceOff) + tupleSize);
- buf.putInt(totalFreeSpaceOff, buf.getInt(totalFreeSpaceOff) - tupleSize - slotManager.getSlotSize());
- System.arraycopy(tuple.getFieldData(0), getLeftChildPageOff(tuple) + childPtrSize, buf.array(),
- rightLeafOff, childPtrSize);
- }
-
- @Override
- public int split(ITreeIndexFrame rightFrame, ITupleReference tuple, ISplitKey splitKey) throws TreeIndexException {
- ByteBuffer right = rightFrame.getBuffer();
- int tupleCount = buf.getInt(tupleCountOff);
-
- int tuplesToLeft = (tupleCount / 2) + (tupleCount % 2);
- ITreeIndexFrame targetFrame = null;
- frameTuple.resetByTupleIndex(this, tuplesToLeft - 1);
- if (cmp.compare(tuple, frameTuple) <= 0) {
- targetFrame = this;
- } else {
- targetFrame = rightFrame;
- }
- int tuplesToRight = tupleCount - tuplesToLeft;
-
- // copy entire page
- System.arraycopy(buf.array(), 0, right.array(), 0, buf.capacity());
-
- // on right page we need to copy rightmost slots to left
- int src = rightFrame.getSlotManager().getSlotEndOff();
- int dest = rightFrame.getSlotManager().getSlotEndOff() + tuplesToLeft
- * rightFrame.getSlotManager().getSlotSize();
- int length = rightFrame.getSlotManager().getSlotSize() * tuplesToRight;
- System.arraycopy(right.array(), src, right.array(), dest, length);
- right.putInt(tupleCountOff, tuplesToRight);
-
- // on left page, remove highest key and make its childpointer the
- // rightmost childpointer
- buf.putInt(tupleCountOff, tuplesToLeft);
-
- // copy data to be inserted, we need this because creating the splitkey
- // will overwrite the data param (data points to same memory as
- // splitKey.getData())
- ISplitKey savedSplitKey = splitKey.duplicate(tupleWriter.createTupleReference());
-
- // set split key to be highest value in left page
- int tupleOff = slotManager.getTupleOff(slotManager.getSlotEndOff());
- frameTuple.resetByTupleOffset(buf, tupleOff);
- int splitKeySize = tupleWriter.bytesRequired(frameTuple, 0, cmp.getKeyFieldCount());
- splitKey.initData(splitKeySize);
- tupleWriter.writeTupleFields(frameTuple, 0, cmp.getKeyFieldCount(), splitKey.getBuffer(), 0);
- splitKey.getTuple().resetByTupleOffset(splitKey.getBuffer(), 0);
-
- int deleteTupleOff = slotManager.getTupleOff(slotManager.getSlotEndOff());
- frameTuple.resetByTupleOffset(buf, deleteTupleOff);
- buf.putInt(rightLeafOff, buf.getInt(getLeftChildPageOff(frameTuple)));
- buf.putInt(tupleCountOff, tuplesToLeft - 1);
-
- // compact both pages
- rightFrame.compact();
- compact();
-
- // insert key
- int targetTupleIndex = ((BTreeNSMInteriorFrame)targetFrame).findInsertTupleIndex(savedSplitKey.getTuple(), cmp);
- targetFrame.insert(savedSplitKey.getTuple(), targetTupleIndex);
-
- return 0;
- }
-
- @Override
- public boolean compact() {
- resetSpaceParams();
-
- 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 + childPtrSize;
- 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 int getChildPageId(RangePredicate pred, MultiComparator srcCmp) {
- // check for trivial case where there is only a child pointer (and no
- // key)
- if (buf.getInt(tupleCountOff) == 0) {
- return buf.getInt(rightLeafOff);
- }
-
- cmpFrameTuple.setFieldCount(srcCmp.getKeyFieldCount());
- frameTuple.setFieldCount(srcCmp.getKeyFieldCount());
-
- // check for trivial cases where no low key or high key exists (e.g.
- // during an index scan)
- ITupleReference tuple = null;
- FindTupleMode fsm = null;
- MultiComparator targetCmp = null;
- if (pred.isForward()) {
- tuple = pred.getLowKey();
- if (tuple == null) {
- return getLeftmostChildPageId(srcCmp);
- }
- if (pred.isLowKeyInclusive())
- fsm = FindTupleMode.INCLUSIVE;
- else
- fsm = FindTupleMode.EXCLUSIVE;
- targetCmp = pred.getLowKeyComparator();
- } else {
- tuple = pred.getHighKey();
- if (tuple == null) {
- return getRightmostChildPageId(srcCmp);
- }
- if (pred.isHighKeyInclusive())
- fsm = FindTupleMode.EXCLUSIVE;
- else
- fsm = FindTupleMode.INCLUSIVE;
- targetCmp = pred.getHighKeyComparator();
- }
-
- int tupleIndex = slotManager.findTupleIndex(tuple, frameTuple, targetCmp, fsm,
+ public int findDeleteTupleIndex(ITupleReference tuple, MultiComparator cmp) throws TreeIndexException {
+ return slotManager.findTupleIndex(tuple, frameTuple, cmp, FindTupleMode.INCLUSIVE,
FindTupleNoExactMatchPolicy.HIGHER_KEY);
- int slotOff = slotManager.getSlotOff(tupleIndex);
- if (tupleIndex == slotManager.getGreatestKeyIndicator()) {
- return buf.getInt(rightLeafOff);
- } else {
- int origTupleOff = slotManager.getTupleOff(slotOff);
- cmpFrameTuple.resetByTupleOffset(buf, origTupleOff);
- int cmpTupleOff = origTupleOff;
- if (pred.isForward()) {
- int maxSlotOff = buf.capacity();
- slotOff += slotManager.getSlotSize();
- while (slotOff < maxSlotOff) {
- cmpTupleOff = slotManager.getTupleOff(slotOff);
- frameTuple.resetByTupleOffset(buf, cmpTupleOff);
- if (targetCmp.compare(cmpFrameTuple, frameTuple) != 0)
- break;
- slotOff += slotManager.getSlotSize();
- }
- slotOff -= slotManager.getSlotSize();
- } else {
- int minSlotOff = slotManager.getSlotEndOff() - slotManager.getSlotSize();
- slotOff -= slotManager.getSlotSize();
- while (slotOff > minSlotOff) {
- cmpTupleOff = slotManager.getTupleOff(slotOff);
- frameTuple.resetByTupleOffset(buf, cmpTupleOff);
- if (targetCmp.compare(cmpFrameTuple, frameTuple) != 0)
- break;
- slotOff -= slotManager.getSlotSize();
- }
- slotOff += slotManager.getSlotSize();
- }
-
- frameTuple.resetByTupleOffset(buf, slotManager.getTupleOff(slotOff));
- int childPageOff = getLeftChildPageOff(frameTuple);
- return buf.getInt(childPageOff);
- }
}
@Override
@@ -316,24 +120,242 @@
tupleOff = slotManager.getTupleOff(slotManager.getSlotEndOff());
frameTuple.resetByTupleOffset(buf, tupleOff);
keySize = tupleWriter.bytesRequired(frameTuple, 0, tuple.getFieldCount());
-
- // copy new rightmost pointer
+ // Copy new rightmost pointer.
System.arraycopy(buf.array(), tupleOff + keySize, buf.array(), rightLeafOff, childPtrSize);
} else {
tupleOff = slotManager.getTupleOff(slotOff);
frameTuple.resetByTupleOffset(buf, tupleOff);
keySize = tupleWriter.bytesRequired(frameTuple, 0, tuple.getFieldCount());
- // perform deletion (we just do a memcpy to overwrite the slot)
+ // 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
+ // Maintain space information.
buf.putInt(tupleCountOff, buf.getInt(tupleCountOff) - 1);
buf.putInt(totalFreeSpaceOff,
buf.getInt(totalFreeSpaceOff) + keySize + childPtrSize + slotManager.getSlotSize());
}
+
+ @Override
+ public void deleteGreatest() {
+ int slotOff = slotManager.getSlotEndOff();
+ int tupleOff = slotManager.getTupleOff(slotOff);
+ frameTuple.resetByTupleOffset(buf, tupleOff);
+ int keySize = tupleWriter.bytesRequired(frameTuple);
+ System.arraycopy(buf.array(), tupleOff + keySize, buf.array(), rightLeafOff, childPtrSize);
+ // Maintain space information.
+ buf.putInt(tupleCountOff, buf.getInt(tupleCountOff) - 1);
+ buf.putInt(totalFreeSpaceOff,
+ buf.getInt(totalFreeSpaceOff) + keySize + childPtrSize + slotManager.getSlotSize());
+ int freeSpace = buf.getInt(freeSpaceOff);
+ if (freeSpace == tupleOff + keySize + childPtrSize) {
+ buf.putInt(freeSpace, freeSpace - (keySize + childPtrSize));
+ }
+ }
+
+ @Override
+ public FrameOpSpaceStatus hasSpaceUpdate(ITupleReference tuple, int oldTupleIndex) {
+ throw new UnsupportedOperationException("Cannot update tuples in interior node.");
+ }
+
+ @Override
+ public int findUpdateTupleIndex(ITupleReference tuple, MultiComparator cmp) throws TreeIndexException {
+ throw new UnsupportedOperationException("Cannot update tuples in interior node.");
+ }
+
+ @Override
+ public void insertSorted(ITupleReference tuple, MultiComparator cmp) throws HyracksDataException {
+ int freeSpace = buf.getInt(freeSpaceOff);
+ slotManager.insertSlot(slotManager.getGreatestKeyIndicator(), freeSpace);
+ int bytesWritten = tupleWriter.writeTuple(tuple, buf, freeSpace);
+ System.arraycopy(tuple.getFieldData(tuple.getFieldCount() - 1), getLeftChildPageOff(tuple), buf.array(),
+ freeSpace + bytesWritten, childPtrSize);
+ int tupleSize = bytesWritten + childPtrSize;
+ buf.putInt(tupleCountOff, buf.getInt(tupleCountOff) + 1);
+ buf.putInt(freeSpaceOff, buf.getInt(freeSpaceOff) + tupleSize);
+ buf.putInt(totalFreeSpaceOff, buf.getInt(totalFreeSpaceOff) - tupleSize - slotManager.getSlotSize());
+ System.arraycopy(tuple.getFieldData(0), getLeftChildPageOff(tuple) + childPtrSize, buf.array(), rightLeafOff,
+ childPtrSize);
+ }
+
+ @Override
+ public int split(ITreeIndexFrame rightFrame, ITupleReference tuple, ISplitKey splitKey) throws TreeIndexException {
+ ByteBuffer right = rightFrame.getBuffer();
+ int tupleCount = getTupleCount();
+ int tuplesToLeft = (tupleCount / 2) + (tupleCount % 2);
+ ITreeIndexFrame targetFrame = null;
+ frameTuple.resetByTupleIndex(this, tuplesToLeft - 1);
+ if (cmp.compare(tuple, frameTuple) <= 0) {
+ targetFrame = this;
+ } else {
+ targetFrame = rightFrame;
+ }
+ int tuplesToRight = tupleCount - tuplesToLeft;
+
+ // Copy entire page.
+ System.arraycopy(buf.array(), 0, right.array(), 0, buf.capacity());
+
+ // On the right page we need to copy rightmost slots to left.
+ int src = rightFrame.getSlotManager().getSlotEndOff();
+ int dest = rightFrame.getSlotManager().getSlotEndOff() + tuplesToLeft
+ * rightFrame.getSlotManager().getSlotSize();
+ int length = rightFrame.getSlotManager().getSlotSize() * tuplesToRight;
+ System.arraycopy(right.array(), src, right.array(), dest, length);
+ right.putInt(tupleCountOff, tuplesToRight);
+
+ // On the left page, remove the highest key and make its child pointer
+ // the rightmost child pointer.
+ buf.putInt(tupleCountOff, tuplesToLeft);
+
+ // Copy the split key to be inserted.
+ // We must do so because setting the new split key will overwrite the
+ // old split key, and we cannot insert the existing split key at this point.
+ ISplitKey savedSplitKey = splitKey.duplicate(tupleWriter.createTupleReference());
+
+ // Set split key to be highest value in left page.
+ int tupleOff = slotManager.getTupleOff(slotManager.getSlotEndOff());
+ frameTuple.resetByTupleOffset(buf, tupleOff);
+ int splitKeySize = tupleWriter.bytesRequired(frameTuple, 0, cmp.getKeyFieldCount());
+ splitKey.initData(splitKeySize);
+ tupleWriter.writeTuple(frameTuple, splitKey.getBuffer(), 0);
+ splitKey.getTuple().resetByTupleOffset(splitKey.getBuffer(), 0);
+
+ int deleteTupleOff = slotManager.getTupleOff(slotManager.getSlotEndOff());
+ frameTuple.resetByTupleOffset(buf, deleteTupleOff);
+ buf.putInt(rightLeafOff, buf.getInt(getLeftChildPageOff(frameTuple)));
+ buf.putInt(tupleCountOff, tuplesToLeft - 1);
+
+ // Compact both pages.
+ rightFrame.compact();
+ compact();
+
+ // Insert the saved split key.
+ int targetTupleIndex = ((BTreeNSMInteriorFrame) targetFrame)
+ .findInsertTupleIndex(savedSplitKey.getTuple(), cmp);
+ targetFrame.insert(savedSplitKey.getTuple(), targetTupleIndex);
+
+ return 0;
+ }
+
+ @Override
+ public boolean compact() {
+ resetSpaceParams();
+ int tupleCount = buf.getInt(tupleCountOff);
+ int freeSpace = buf.getInt(freeSpaceOff);
+ // Sort the slots by the tuple offset they point to.
+ 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);
+ // Iterate over the sorted slots, and move their corresponding tuples to
+ // the left, reclaiming free space.
+ 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 + childPtrSize;
+ System.arraycopy(buf.array(), tupleOff, buf.array(), freeSpace, tupleLength);
+ slotManager.setSlot(sortedTupleOffs.get(i).slotOff, freeSpace);
+ freeSpace += tupleLength;
+ }
+ // Update contiguous free space pointer and total free space indicator.
+ buf.putInt(freeSpaceOff, freeSpace);
+ buf.putInt(totalFreeSpaceOff, buf.capacity() - freeSpace - tupleCount * slotManager.getSlotSize());
+ return false;
+ }
+
+ @Override
+ public int getChildPageId(RangePredicate pred) {
+ // Trivial case where there is only a child pointer (and no key).
+ if (buf.getInt(tupleCountOff) == 0) {
+ return buf.getInt(rightLeafOff);
+ }
+ // Trivial cases where no low key or high key was given (e.g.
+ // during an index scan).
+ ITupleReference tuple = null;
+ FindTupleMode fsm = null;
+ // The target comparator may be on a prefix of the BTree key fields.
+ MultiComparator targetCmp = null;
+ if (pred.isForward()) {
+ tuple = pred.getLowKey();
+ if (tuple == null) {
+ return getLeftmostChildPageId();
+ }
+ if (pred.isLowKeyInclusive()) {
+ fsm = FindTupleMode.INCLUSIVE;
+ } else {
+ fsm = FindTupleMode.EXCLUSIVE;
+ }
+ targetCmp = pred.getLowKeyComparator();
+ } else {
+ tuple = pred.getHighKey();
+ if (tuple == null) {
+ return getRightmostChildPageId();
+ }
+ if (pred.isHighKeyInclusive()) {
+ fsm = FindTupleMode.EXCLUSIVE;
+ } else {
+ fsm = FindTupleMode.INCLUSIVE;
+ }
+ targetCmp = pred.getHighKeyComparator();
+ }
+ // Search for a matching key.
+ int tupleIndex = slotManager.findTupleIndex(tuple, frameTuple, targetCmp, fsm,
+ FindTupleNoExactMatchPolicy.HIGHER_KEY);
+ int slotOff = slotManager.getSlotOff(tupleIndex);
+ // Follow the rightmost (greatest) child pointer.
+ if (tupleIndex == slotManager.getGreatestKeyIndicator()) {
+ return buf.getInt(rightLeafOff);
+ }
+ // Deal with prefix searches.
+ // slotManager.findTupleIndex() will return an arbitrary tuple matching
+ // the given field prefix (according to the target comparator).
+ // To make sure we traverse the right path, we must find the
+ // leftmost or rightmost tuple that matches the prefix.
+ int origTupleOff = slotManager.getTupleOff(slotOff);
+ cmpFrameTuple.resetByTupleOffset(buf, origTupleOff);
+ int cmpTupleOff = origTupleOff;
+ if (pred.isForward()) {
+ // The answer set begins with the lowest key matching the prefix.
+ // We must follow the child pointer of the lowest (leftmost) key
+ // matching the given prefix.
+ int maxSlotOff = buf.capacity();
+ slotOff += slotManager.getSlotSize();
+ while (slotOff < maxSlotOff) {
+ cmpTupleOff = slotManager.getTupleOff(slotOff);
+ frameTuple.resetByTupleOffset(buf, cmpTupleOff);
+ if (targetCmp.compare(cmpFrameTuple, frameTuple) != 0) {
+ break;
+ }
+ slotOff += slotManager.getSlotSize();
+ }
+ slotOff -= slotManager.getSlotSize();
+ } else {
+ // The answer set begins with the highest key matching the prefix.
+ // We must follow the child pointer of the highest (rightmost) key
+ // matching the given prefix.
+ int minSlotOff = slotManager.getSlotEndOff() - slotManager.getSlotSize();
+ slotOff -= slotManager.getSlotSize();
+ while (slotOff > minSlotOff) {
+ cmpTupleOff = slotManager.getTupleOff(slotOff);
+ frameTuple.resetByTupleOffset(buf, cmpTupleOff);
+ if (targetCmp.compare(cmpFrameTuple, frameTuple) != 0) {
+ break;
+ }
+ slotOff -= slotManager.getSlotSize();
+ }
+ slotOff += slotManager.getSlotSize();
+ }
+ frameTuple.resetByTupleOffset(buf, slotManager.getTupleOff(slotOff));
+ int childPageOff = getLeftChildPageOff(frameTuple);
+ return buf.getInt(childPageOff);
+ }
@Override
protected void resetSpaceParams() {
@@ -342,16 +364,15 @@
}
@Override
- public int getLeftmostChildPageId(MultiComparator cmp) {
+ public int getLeftmostChildPageId() {
int tupleOff = slotManager.getTupleOff(slotManager.getSlotStartOff());
- frameTuple.setFieldCount(cmp.getKeyFieldCount());
frameTuple.resetByTupleOffset(buf, tupleOff);
int childPageOff = getLeftChildPageOff(frameTuple);
return buf.getInt(childPageOff);
}
@Override
- public int getRightmostChildPageId(MultiComparator cmp) {
+ public int getRightmostChildPageId() {
return buf.getInt(rightLeafOff);
}
@@ -360,7 +381,37 @@
buf.putInt(rightLeafOff, pageId);
}
- // for debugging
+ @Override
+ public int getPageHeaderSize() {
+ return rightLeafOff;
+ }
+
+ private int getLeftChildPageOff(ITupleReference tuple) {
+ return tuple.getFieldStart(tuple.getFieldCount() - 1) + tuple.getFieldLength(tuple.getFieldCount() - 1);
+ }
+
+ @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 void setMultiComparator(MultiComparator cmp) {
+ this.cmp = cmp;
+ cmpFrameTuple.setFieldCount(cmp.getKeyFieldCount());
+ frameTuple.setFieldCount(cmp.getKeyFieldCount());
+ }
+
+ // For debugging.
public ArrayList<Integer> getChildren(MultiComparator cmp) {
ArrayList<Integer> ret = new ArrayList<Integer>();
frameTuple.setFieldCount(cmp.getKeyFieldCount());
@@ -368,7 +419,7 @@
for (int i = 0; i < tupleCount; i++) {
int tupleOff = slotManager.getTupleOff(slotManager.getSlotOff(i));
frameTuple.resetByTupleOffset(buf, tupleOff);
- int intVal = getInt(
+ int intVal = IntegerSerializerDeserializer.getInt(
buf.array(),
frameTuple.getFieldStart(frameTuple.getFieldCount() - 1)
+ frameTuple.getFieldLength(frameTuple.getFieldCount() - 1));
@@ -381,80 +432,4 @@
}
return ret;
}
-
- @Override
- public void deleteGreatest(MultiComparator cmp) {
- int slotOff = slotManager.getSlotEndOff();
- int tupleOff = slotManager.getTupleOff(slotOff);
- frameTuple.setFieldCount(cmp.getKeyFieldCount());
- frameTuple.resetByTupleOffset(buf, tupleOff);
- int keySize = tupleWriter.bytesRequired(frameTuple, 0, cmp.getKeyFieldCount());
- System.arraycopy(buf.array(), tupleOff + keySize, buf.array(), rightLeafOff, childPtrSize);
-
- // maintain space information
- buf.putInt(tupleCountOff, buf.getInt(tupleCountOff) - 1);
- buf.putInt(totalFreeSpaceOff,
- buf.getInt(totalFreeSpaceOff) + keySize + childPtrSize + slotManager.getSlotSize());
-
- int freeSpace = buf.getInt(freeSpaceOff);
- if (freeSpace == tupleOff + keySize + childPtrSize) {
- buf.putInt(freeSpace, freeSpace - (keySize + childPtrSize));
- }
- }
-
- private int getInt(byte[] bytes, int offset) {
- return ((bytes[offset] & 0xff) << 24) + ((bytes[offset + 1] & 0xff) << 16) + ((bytes[offset + 2] & 0xff) << 8)
- + ((bytes[offset + 3] & 0xff) << 0);
- }
-
- @Override
- public String printKeys(MultiComparator cmp, ISerializerDeserializer[] fields) throws HyracksDataException {
- StringBuilder strBuilder = new StringBuilder();
- int tupleCount = buf.getInt(tupleCountOff);
- frameTuple.setFieldCount(cmp.getKeyFieldCount());
- 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 getPageHeaderSize() {
- return rightLeafOff;
- }
-
- private int getLeftChildPageOff(ITupleReference tuple) {
- return tuple.getFieldStart(tuple.getFieldCount() - 1) + tuple.getFieldLength(tuple.getFieldCount() - 1);
- }
-
- // TODO: can we put these into a common AbstractFrame or something?
- @Override
- public boolean getSmFlag() {
- return buf.get(smFlagOff) != 0;
- }
-
- // TODO: can we put these into a common AbstractFrame or something?
- @Override
- public void setSmFlag(boolean smFlag) {
- if (smFlag)
- buf.put(smFlagOff, (byte) 1);
- else
- buf.put(smFlagOff, (byte) 0);
- }
-
- @Override
- public void setMultiComparator(MultiComparator cmp) {
- this.cmp = cmp;
- cmpFrameTuple.setFieldCount(cmp.getKeyFieldCount());
- frameTuple.setFieldCount(cmp.getKeyFieldCount());
- }
}
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTree.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTree.java
index 2895686..995c447 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTree.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTree.java
@@ -706,7 +706,7 @@
// the descent.
boolean repeatOp = true;
while (repeatOp && ctx.opRestarts < MAX_RESTARTS) {
- int childPageId = ctx.interiorFrame.getChildPageId(ctx.pred, cmp);
+ int childPageId = ctx.interiorFrame.getChildPageId(ctx.pred);
performOp(childPageId, node, ctx);
if (!ctx.pageLsns.isEmpty() && ctx.pageLsns.getLast() == RESTART_OP) {
@@ -908,7 +908,7 @@
ctx.splitKey.getTuple().resetByTupleOffset(ctx.splitKey.getBuffer(), 0);
ctx.splitKey.setLeftPage(frontier.pageId);
- ctx.interiorFrame.deleteGreatest(cmp);
+ ctx.interiorFrame.deleteGreatest();
frontier.page.releaseWriteLatch();
bufferCache.unpin(frontier.page);
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexStatsOperatorNodePushable.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexStatsOperatorNodePushable.java
index 4b53453..82b1b38 100644
--- a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexStatsOperatorNodePushable.java
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/TreeIndexStatsOperatorNodePushable.java
@@ -20,8 +20,8 @@
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.am.common.util.TreeIndexStats;
+import edu.uci.ics.hyracks.storage.am.common.util.TreeIndexStatsGatherer;
import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
public class TreeIndexStatsOperatorNodePushable extends
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/frames/TreeIndexNSMFrame.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/frames/TreeIndexNSMFrame.java
index 5e5360a..5f15c2f 100644
--- a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/frames/TreeIndexNSMFrame.java
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/frames/TreeIndexNSMFrame.java
@@ -117,7 +117,7 @@
resetSpaceParams();
int tupleCount = buf.getInt(tupleCountOff);
int freeSpace = buf.getInt(freeSpaceOff);
-
+ // Sort the slots by the tuple offset they point to.
ArrayList<SlotOffTupleOff> sortedTupleOffs = new ArrayList<SlotOffTupleOff>();
sortedTupleOffs.ensureCapacity(tupleCount);
for (int i = 0; i < tupleCount; i++) {
@@ -126,23 +126,21 @@
sortedTupleOffs.add(new SlotOffTupleOff(i, slotOff, tupleOff));
}
Collections.sort(sortedTupleOffs);
-
+ // Iterate over the sorted slots, and move their corresponding tuples to
+ // the left, reclaiming free space.
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;
}
-
+ // Update contiguous free space pointer and total free space indicator.
buf.putInt(freeSpaceOff, freeSpace);
buf.putInt(totalFreeSpaceOff, buf.capacity() - freeSpace - tupleCount * slotManager.getSlotSize());
-
return false;
}
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/utility/TreeIndexBufferCacheWarmup.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/util/TreeIndexBufferCacheWarmup.java
similarity index 97%
rename from hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/utility/TreeIndexBufferCacheWarmup.java
rename to hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/util/TreeIndexBufferCacheWarmup.java
index 8179d58..65ea8de 100644
--- a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/utility/TreeIndexBufferCacheWarmup.java
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/util/TreeIndexBufferCacheWarmup.java
@@ -1,4 +1,4 @@
-package edu.uci.ics.hyracks.storage.am.common.utility;
+package edu.uci.ics.hyracks.storage.am.common.util;
import java.util.ArrayList;
import java.util.Random;
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/utility/TreeIndexStats.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/util/TreeIndexStats.java
similarity index 98%
rename from hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/utility/TreeIndexStats.java
rename to hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/util/TreeIndexStats.java
index 2754743..d5d9b5d 100644
--- a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/utility/TreeIndexStats.java
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/util/TreeIndexStats.java
@@ -1,4 +1,4 @@
-package edu.uci.ics.hyracks.storage.am.common.utility;
+package edu.uci.ics.hyracks.storage.am.common.util;
import java.text.DecimalFormat;
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/utility/TreeIndexStatsGatherer.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/util/TreeIndexStatsGatherer.java
similarity index 97%
rename from hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/utility/TreeIndexStatsGatherer.java
rename to hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/util/TreeIndexStatsGatherer.java
index 9167732..eeacccd 100644
--- a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/utility/TreeIndexStatsGatherer.java
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/util/TreeIndexStatsGatherer.java
@@ -1,4 +1,4 @@
-package edu.uci.ics.hyracks.storage.am.common.utility;
+package edu.uci.ics.hyracks.storage.am.common.util;
import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
import edu.uci.ics.hyracks.storage.am.common.api.IFreePageManager;
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/util/TreeIndexUtils.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/util/TreeIndexUtils.java
new file mode 100644
index 0000000..5c16665
--- /dev/null
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/util/TreeIndexUtils.java
@@ -0,0 +1,39 @@
+/*
+ * 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.util;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.dataflow.common.util.TupleUtils;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrame;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleReference;
+
+@SuppressWarnings("rawtypes")
+public class TreeIndexUtils {
+ public static String printFrameTuples(ITreeIndexFrame frame, ISerializerDeserializer[] fieldSerdes) throws HyracksDataException {
+ StringBuilder strBuilder = new StringBuilder();
+ ITreeIndexTupleReference tuple = frame.createTupleReference();
+ for (int i = 0; i < frame.getTupleCount(); i++) {
+ tuple.resetByTupleIndex(frame, i);
+ String tupleString = TupleUtils.printTuple(tuple, fieldSerdes);
+ strBuilder.append(tupleString);
+ if (i != tuple.getFieldCount() - 1) {
+ strBuilder.append(" | ");
+ }
+ }
+ return strBuilder.toString();
+ }
+}
diff --git a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeStatsTest.java b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeStatsTest.java
index f696615..222a039 100644
--- a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeStatsTest.java
+++ b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeStatsTest.java
@@ -39,9 +39,9 @@
import edu.uci.ics.hyracks.storage.am.common.ophelpers.IndexOp;
import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
import edu.uci.ics.hyracks.storage.am.common.tuples.TypeAwareTupleWriterFactory;
-import edu.uci.ics.hyracks.storage.am.common.utility.TreeIndexBufferCacheWarmup;
-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.am.common.util.TreeIndexBufferCacheWarmup;
+import edu.uci.ics.hyracks.storage.am.common.util.TreeIndexStats;
+import edu.uci.ics.hyracks.storage.am.common.util.TreeIndexStatsGatherer;
import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
import edu.uci.ics.hyracks.storage.common.file.IFileMapProvider;
import edu.uci.ics.hyracks.test.support.TestStorageManagerComponentHolder;
diff --git a/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeTest.java b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeTest.java
index 0fefd3d..0a04eca 100644
--- a/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeTest.java
+++ b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeTest.java
@@ -51,8 +51,8 @@
import edu.uci.ics.hyracks.storage.am.common.impls.TreeDiskOrderScanCursor;
import edu.uci.ics.hyracks.storage.am.common.ophelpers.IndexOp;
import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
-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.am.common.util.TreeIndexStats;
+import edu.uci.ics.hyracks.storage.am.common.util.TreeIndexStatsGatherer;
import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeFrame;
import edu.uci.ics.hyracks.storage.am.rtree.frames.RTreeNSMInteriorFrameFactory;
import edu.uci.ics.hyracks.storage.am.rtree.frames.RTreeNSMLeafFrameFactory;