blob: 4856595e08217002e347ef62f4608a24cfda59f0 [file] [log] [blame]
/*
* Copyright 2009-2010 by The Regents of the University of California
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* you may obtain a copy of the License from
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package edu.uci.ics.hyracks.storage.am.btree.frames;
import java.nio.ByteBuffer;
import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeLeafFrame;
import edu.uci.ics.hyracks.storage.am.btree.exceptions.BTreeDuplicateKeyException;
import edu.uci.ics.hyracks.storage.am.btree.exceptions.BTreeNonExistentKeyException;
import edu.uci.ics.hyracks.storage.am.common.api.ISplitKey;
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.frames.TreeIndexNSMFrame;
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 class BTreeNSMLeafFrame extends TreeIndexNSMFrame implements IBTreeLeafFrame {
protected static final int prevLeafOff = smFlagOff + 1;
protected static final int nextLeafOff = prevLeafOff + 4;
private MultiComparator cmp;
public BTreeNSMLeafFrame(ITreeIndexTupleWriter tupleWriter) {
super(tupleWriter, new OrderedSlotManager());
}
@Override
public void initBuffer(byte level) {
super.initBuffer(level);
buf.putInt(prevLeafOff, -1);
buf.putInt(nextLeafOff, -1);
}
@Override
public void setNextLeaf(int page) {
buf.putInt(nextLeafOff, page);
}
@Override
public void setPrevLeaf(int page) {
buf.putInt(prevLeafOff, page);
}
@Override
public int getNextLeaf() {
return buf.getInt(nextLeafOff);
}
@Override
public int getPrevLeaf() {
return buf.getInt(prevLeafOff);
}
@Override
public int findInsertTupleIndex(ITupleReference tuple) throws TreeIndexException {
int tupleIndex = slotManager.findTupleIndex(tuple, frameTuple, cmp, FindTupleMode.EXCLUSIVE_ERROR_IF_EXISTS,
FindTupleNoExactMatchPolicy.HIGHER_KEY);
// Error indicator is set if there is an exact match.
if (tupleIndex == slotManager.getErrorIndicator()) {
throw new BTreeDuplicateKeyException("Trying to insert duplicate key into leaf node.");
}
return tupleIndex;
}
@Override
public int findUpdateTupleIndex(ITupleReference tuple) throws TreeIndexException {
int tupleIndex = slotManager.findTupleIndex(tuple, frameTuple, cmp, FindTupleMode.EXACT,
FindTupleNoExactMatchPolicy.HIGHER_KEY);
// Error indicator is set if there is no exact match.
if (tupleIndex == slotManager.getErrorIndicator()) {
throw new BTreeNonExistentKeyException("Trying to update a tuple with a nonexistent key in leaf node.");
}
return tupleIndex;
}
@Override
public int findDeleteTupleIndex(ITupleReference tuple) throws TreeIndexException {
int tupleIndex = slotManager.findTupleIndex(tuple, frameTuple, cmp, FindTupleMode.EXACT,
FindTupleNoExactMatchPolicy.HIGHER_KEY);
// Error indicator is set if there is no exact match.
if (tupleIndex == slotManager.getErrorIndicator()) {
throw new BTreeNonExistentKeyException("Trying to delete a tuple with a nonexistent key in leaf node.");
}
return tupleIndex;
}
@Override
public void insert(ITupleReference tuple, int tupleIndex) {
int freeSpace = buf.getInt(freeSpaceOff);
slotManager.insertSlot(tupleIndex, freeSpace);
int bytesWritten = tupleWriter.writeTuple(tuple, buf.array(), freeSpace);
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 insertSorted(ITupleReference tuple) {
insert(tuple, slotManager.getGreatestKeyIndicator());
}
@Override
public void split(ITreeIndexFrame rightFrame, ITupleReference tuple, ISplitKey splitKey) throws TreeIndexException {
ByteBuffer right = rightFrame.getBuffer();
int tupleCount = getTupleCount();
// Find split point, and determine into which frame the new tuple should be inserted into.
int tuplesToLeft;
int mid = tupleCount / 2;
ITreeIndexFrame targetFrame = null;
int tupleOff = slotManager.getTupleOff(slotManager.getSlotEndOff() + slotManager.getSlotSize() * mid);
frameTuple.resetByTupleOffset(buf, tupleOff);
if (cmp.compare(tuple, frameTuple) >= 0) {
tuplesToLeft = mid + (tupleCount % 2);
targetFrame = rightFrame;
} else {
tuplesToLeft = mid;
targetFrame = this;
}
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 the 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 only change the tupleCount indicator.
buf.putInt(tupleCountOff, tuplesToLeft);
// Compact both pages.
rightFrame.compact();
compact();
// Insert the new tuple.
int targetTupleIndex = ((BTreeNSMLeafFrame)targetFrame).findInsertTupleIndex(tuple);
targetFrame.insert(tuple, targetTupleIndex);
// Set the split key to be highest key in the left page.
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);
}
@Override
protected void resetSpaceParams() {
buf.putInt(freeSpaceOff, nextLeafOff + 4);
buf.putInt(totalFreeSpaceOff, buf.capacity() - (nextLeafOff + 4));
}
@Override
public ITreeIndexTupleReference createTupleReference() {
return tupleWriter.createTupleReference();
}
@Override
public int findTupleIndex(ITupleReference searchKey, ITreeIndexTupleReference pageTuple, MultiComparator cmp,
FindTupleMode ftm, FindTupleNoExactMatchPolicy ftp) {
return slotManager.findTupleIndex(searchKey, pageTuple, cmp, ftm, ftp);
}
@Override
public int getPageHeaderSize() {
return nextLeafOff;
}
@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;
}
}