in hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/frames/BTreeFieldPrefixNSMLeafFrame.java [575:705]
public void split(ITreeIndexFrame rightFrame, ITupleReference tuple, ISplitKey splitKey)
throws HyracksDataException {
BTreeFieldPrefixNSMLeafFrame rf = (BTreeFieldPrefixNSMLeafFrame) rightFrame;
ByteBuffer right = rf.getBuffer();
int tupleCount = getTupleCount();
int prefixTupleCount = getPrefixTupleCount();
// Find split point, and determine into which frame the new tuple should
// be inserted into.
int tuplesToLeft;
int midSlotNum = tupleCount / 2;
ITreeIndexFrame targetFrame = null;
frameTuple.resetByTupleIndex(this, midSlotNum);
int comparison = cmp.compare(tuple, frameTuple);
if (comparison >= 0) {
tuplesToLeft = midSlotNum + (tupleCount % 2);
targetFrame = rf;
} else {
tuplesToLeft = midSlotNum;
targetFrame = this;
}
int tuplesToRight = tupleCount - tuplesToLeft;
// copy entire page
System.arraycopy(buf.array(), 0, right.array(), 0, buf.capacity());
// determine how many slots go on left and right page
int prefixesToLeft = prefixTupleCount;
for (int i = tuplesToLeft; i < tupleCount; i++) {
int tupleSlotOff = rf.slotManager.getTupleSlotOff(i);
int tupleSlot = right.getInt(tupleSlotOff);
int prefixSlotNum = rf.slotManager.decodeFirstSlotField(tupleSlot);
if (prefixSlotNum != FieldPrefixSlotManager.TUPLE_UNCOMPRESSED) {
prefixesToLeft = prefixSlotNum;
break;
}
}
// if we are splitting in the middle of a prefix both pages need to have the prefix slot and tuple
int boundaryTupleSlotOff = rf.slotManager.getTupleSlotOff(tuplesToLeft - 1);
int boundaryTupleSlot = buf.getInt(boundaryTupleSlotOff);
int boundaryPrefixSlotNum = rf.slotManager.decodeFirstSlotField(boundaryTupleSlot);
int prefixesToRight = prefixTupleCount - prefixesToLeft;
if (boundaryPrefixSlotNum == prefixesToLeft
&& boundaryPrefixSlotNum != FieldPrefixSlotManager.TUPLE_UNCOMPRESSED) {
prefixesToLeft++; // tuples on both pages share one prefix
}
// move prefix tuples on right page to beginning of page and adjust prefix slots
if (prefixesToRight > 0 && prefixesToLeft > 0 && prefixTupleCount > 1) {
int freeSpace = rf.getOrigFreeSpaceOff();
int lastPrefixSlotNum = -1;
for (int i = tuplesToLeft; i < tupleCount; i++) {
int tupleSlotOff = rf.slotManager.getTupleSlotOff(i);
int tupleSlot = right.getInt(tupleSlotOff);
int prefixSlotNum = rf.slotManager.decodeFirstSlotField(tupleSlot);
if (prefixSlotNum != FieldPrefixSlotManager.TUPLE_UNCOMPRESSED) {
framePrefixTuple.resetByTupleIndex(this, prefixSlotNum);
int bytesWritten = 0;
if (lastPrefixSlotNum != prefixSlotNum) {
bytesWritten = tupleWriter.writeTuple(framePrefixTuple, right.array(), freeSpace);
int newPrefixSlot = rf.slotManager
.encodeSlotFields(framePrefixTuple.getFieldCount(), freeSpace);
int prefixSlotOff = rf.slotManager.getPrefixSlotOff(prefixSlotNum);
right.putInt(prefixSlotOff, newPrefixSlot);
lastPrefixSlotNum = prefixSlotNum;
}
int tupleOff = rf.slotManager.decodeSecondSlotField(tupleSlot);
int newTupleSlot = rf.slotManager.encodeSlotFields(prefixSlotNum
- (prefixTupleCount - prefixesToRight), tupleOff);
right.putInt(tupleSlotOff, newTupleSlot);
freeSpace += bytesWritten;
}
}
}
// move the modified prefix slots on the right page
int prefixSrc = rf.slotManager.getPrefixSlotEndOff();
int prefixDest = rf.slotManager.getPrefixSlotEndOff() + (prefixTupleCount - prefixesToRight)
* rf.slotManager.getSlotSize();
int prefixLength = rf.slotManager.getSlotSize() * prefixesToRight;
System.arraycopy(right.array(), prefixSrc, right.array(), prefixDest, prefixLength);
// on right page we need to copy rightmost tuple slots to left
int src = rf.slotManager.getTupleSlotEndOff();
int dest = rf.slotManager.getTupleSlotEndOff() + tuplesToLeft * rf.slotManager.getSlotSize()
+ (prefixTupleCount - prefixesToRight) * rf.slotManager.getSlotSize();
int length = rf.slotManager.getSlotSize() * tuplesToRight;
System.arraycopy(right.array(), src, right.array(), dest, length);
right.putInt(tupleCountOff, tuplesToRight);
right.putInt(prefixTupleCountOff, prefixesToRight);
// on left page move slots to reflect possibly removed prefixes
src = slotManager.getTupleSlotEndOff() + tuplesToRight * slotManager.getSlotSize();
dest = slotManager.getTupleSlotEndOff() + tuplesToRight * slotManager.getSlotSize()
+ (prefixTupleCount - prefixesToLeft) * slotManager.getSlotSize();
length = slotManager.getSlotSize() * tuplesToLeft;
System.arraycopy(buf.array(), src, buf.array(), dest, length);
buf.putInt(tupleCountOff, tuplesToLeft);
buf.putInt(prefixTupleCountOff, prefixesToLeft);
// compact both pages
compact();
rightFrame.compact();
// insert last key
int targetTupleIndex;
// it's safe to catch this exception since it will have been caught before reaching here
try {
targetTupleIndex = ((IBTreeLeafFrame) targetFrame).findInsertTupleIndex(tuple);
} catch (TreeIndexException e) {
throw new IllegalStateException(e);
}
targetFrame.insert(tuple, targetTupleIndex);
// set split key to be highest value in left page
frameTuple.resetByTupleIndex(this, getTupleCount() - 1);
int splitKeySize = tupleWriter.bytesRequired(frameTuple, 0, cmp.getKeyFieldCount());
splitKey.initData(splitKeySize);
tupleWriter.writeTupleFields(frameTuple, 0, cmp.getKeyFieldCount(), splitKey.getBuffer().array(), 0);
splitKey.getTuple().resetByTupleOffset(splitKey.getBuffer(), 0);
}