Continuing to cleanup the BTree.
git-svn-id: https://hyracks.googlecode.com/svn/branches/hyracks_btree_updates_next@608 123451ca-8445-de46-9d55-352943316053
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeFieldPrefixNSMLeafFrame.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeFieldPrefixNSMLeafFrame.java
index 02ad3a1..0ad8b68 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeFieldPrefixNSMLeafFrame.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeFieldPrefixNSMLeafFrame.java
@@ -31,7 +31,6 @@
import edu.uci.ics.hyracks.storage.am.btree.api.IPrefixSlotManager;
import edu.uci.ics.hyracks.storage.am.btree.compressors.FieldPrefixCompressor;
import edu.uci.ics.hyracks.storage.am.btree.exceptions.BTreeDuplicateKeyException;
-import edu.uci.ics.hyracks.storage.am.btree.exceptions.BTreeException;
import edu.uci.ics.hyracks.storage.am.btree.exceptions.BTreeNonExistentKeyException;
import edu.uci.ics.hyracks.storage.am.btree.impls.FieldPrefixPrefixTupleReference;
import edu.uci.ics.hyracks.storage.am.btree.impls.FieldPrefixSlotManager;
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 aaf9845..93b7ea7 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
@@ -82,23 +82,8 @@
@Override
public int findInsertTupleIndex(ITupleReference tuple, MultiComparator cmp) throws TreeIndexException {
frameTuple.setFieldCount(cmp.getKeyFieldCount());
- int tupleIndex = slotManager.findTupleIndex(tuple, frameTuple, cmp, FindTupleMode.INCLUSIVE,
+ return slotManager.findTupleIndex(tuple, frameTuple, cmp, FindTupleMode.INCLUSIVE,
FindTupleNoExactMatchPolicy.HIGHER_KEY);
- int slotOff = slotManager.getSlotOff(tupleIndex);
- boolean isDuplicate = true;
-
- // TODO: We may not need to check for duplicates in interior nodes.
- if (tupleIndex < 0)
- isDuplicate = false; // greater than all existing keys
- else {
- frameTuple.resetByTupleOffset(buf, slotManager.getTupleOff(slotOff));
- if (cmp.compare(tuple, frameTuple) != 0)
- isDuplicate = false;
- }
- if (isDuplicate) {
- throw new BTreeNonExistentKeyException("Trying to delete a tuple with a nonexistent key in leaf node.");
- }
- return tupleIndex;
}
@Override
@@ -303,7 +288,7 @@
int tupleIndex = slotManager.findTupleIndex(tuple, frameTuple, targetCmp, fsm,
FindTupleNoExactMatchPolicy.HIGHER_KEY);
int slotOff = slotManager.getSlotOff(tupleIndex);
- if (tupleIndex < 0) {
+ if (slotManager.isHighestTupleIndex(tupleIndex)) {
return buf.getInt(rightLeafOff);
} else {
int origTupleOff = slotManager.getTupleOff(slotOff);
@@ -342,13 +327,10 @@
@Override
public void delete(ITupleReference tuple, MultiComparator cmp, int tupleIndex) {
frameTuple.setFieldCount(cmp.getKeyFieldCount());
- //int tupleIndex = slotManager.findTupleIndex(tuple, frameTuple, cmp, FindTupleMode.INCLUSIVE,
- // FindTupleNoExactMatchPolicy.FTP_HIGHER_KEY);
int slotOff = slotManager.getSlotOff(tupleIndex);
int tupleOff;
int keySize;
-
- if (tupleIndex < 0) {
+ if (slotManager.isHighestTupleIndex(tupleIndex)) {
tupleOff = slotManager.getTupleOff(slotManager.getSlotEndOff());
frameTuple.resetByTupleOffset(buf, tupleOff);
keySize = tupleWriter.bytesRequired(frameTuple, 0, cmp.getKeyFieldCount());
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMLeafFrame.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMLeafFrame.java
index 02adb01..9b75843 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMLeafFrame.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMLeafFrame.java
@@ -70,22 +70,10 @@
@Override
public int findInsertTupleIndex(ITupleReference tuple, MultiComparator cmp) throws TreeIndexException {
frameTuple.setFieldCount(cmp.getFieldCount());
- int tupleIndex = slotManager.findTupleIndex(tuple, frameTuple, cmp, FindTupleMode.INCLUSIVE,
+ int tupleIndex = slotManager.findTupleIndex(tuple, frameTuple, cmp, FindTupleMode.EXCLUSIVE_ERROR_IF_EXISTS,
FindTupleNoExactMatchPolicy.HIGHER_KEY);
- int slotOff = slotManager.getSlotOff(tupleIndex);
- // TODO: Push this check into findSlot, and distinguish between greatest slot and errors.
- boolean isDuplicate = true;
- if (tupleIndex < 0) {
- // Greater than all existing keys.
- isDuplicate = false;
- }
- else {
- frameTuple.resetByTupleOffset(buf, slotManager.getTupleOff(slotOff));
- if (cmp.compare(tuple, frameTuple) != 0) {
- isDuplicate = false;
- }
- }
- if (isDuplicate) {
+ // Error indicator is set if there is an exact match.
+ if (slotManager.isErrorTupleIndex(tupleIndex)) {
throw new BTreeDuplicateKeyException("Trying to insert duplicate key into leaf node.");
}
return tupleIndex;
@@ -96,8 +84,8 @@
frameTuple.setFieldCount(cmp.getFieldCount());
int tupleIndex = slotManager.findTupleIndex(tuple, frameTuple, cmp, FindTupleMode.EXACT,
FindTupleNoExactMatchPolicy.HIGHER_KEY);
- // TODO: Push this check into findSlot, and distinguish between greatest slot and errors.
- if (tupleIndex < 0) {
+ // Error indicator is set if there is no exact match.
+ if (slotManager.isErrorTupleIndex(tupleIndex)) {
throw new BTreeNonExistentKeyException("Trying to update a tuple with a nonexistent key in leaf node.");
}
return tupleIndex;
@@ -108,8 +96,8 @@
frameTuple.setFieldCount(cmp.getFieldCount());
int tupleIndex = slotManager.findTupleIndex(tuple, frameTuple, cmp, FindTupleMode.EXACT,
FindTupleNoExactMatchPolicy.HIGHER_KEY);
- // TODO: Push this check into findSlot, and distinguish between greatest slot and errors.
- if (tupleIndex < 0) {
+ // Error indicator is set if there is no exact match.
+ if (slotManager.isErrorTupleIndex(tupleIndex)) {
throw new BTreeNonExistentKeyException("Trying to delete a tuple with a nonexistent key in leaf node.");
}
return tupleIndex;
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/OrderedSlotManager.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/OrderedSlotManager.java
index 1f62f30..4a07fa4 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/OrderedSlotManager.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/OrderedSlotManager.java
@@ -24,11 +24,15 @@
public class OrderedSlotManager extends AbstractSlotManager {
+ private final int HIGHEST_TUPLE_INDEX = -1;
+ private final int ERROR_TUPLE_INDEX = -2;
+
@Override
public int findTupleIndex(ITupleReference searchKey, ITreeIndexTupleReference frameTuple, MultiComparator multiCmp,
FindTupleMode mode, FindTupleNoExactMatchPolicy matchPolicy) {
- if (frame.getTupleCount() <= 0)
+ if (frame.getTupleCount() <= 0) {
return -1;
+ }
int mid;
int begin = 0;
@@ -45,42 +49,52 @@
begin = mid + 1;
} else {
if (mode == FindTupleMode.EXCLUSIVE) {
- if (matchPolicy == FindTupleNoExactMatchPolicy.HIGHER_KEY)
+ if (matchPolicy == FindTupleNoExactMatchPolicy.HIGHER_KEY) {
begin = mid + 1;
- else
+ } else {
end = mid - 1;
+ }
} else {
- return mid;
+ if (mode == FindTupleMode.EXCLUSIVE_ERROR_IF_EXISTS) {
+ return ERROR_TUPLE_INDEX;
+ } else {
+ return mid;
+ }
}
}
}
- if (mode == FindTupleMode.EXACT)
- return -1;
+ if (mode == FindTupleMode.EXACT) {
+ return ERROR_TUPLE_INDEX;
+ }
if (matchPolicy == FindTupleNoExactMatchPolicy.HIGHER_KEY) {
- if (begin > frame.getTupleCount() - 1)
- return -1;
+ if (begin > frame.getTupleCount() - 1) {
+ return HIGHEST_TUPLE_INDEX;
+ }
frameTuple.resetByTupleIndex(frame, begin);
- if (multiCmp.compare(searchKey, frameTuple) < 0)
+ if (multiCmp.compare(searchKey, frameTuple) < 0) {
return begin;
- else
- return -1;
+ } else {
+ return HIGHEST_TUPLE_INDEX;
+ }
} else {
- if (end < 0)
- return -1;
+ if (end < 0) {
+ return HIGHEST_TUPLE_INDEX;
+ }
frameTuple.resetByTupleIndex(frame, end);
- if (multiCmp.compare(searchKey, frameTuple) > 0)
+ if (multiCmp.compare(searchKey, frameTuple) > 0) {
return end;
- else
- return -1;
+ } else {
+ return HIGHEST_TUPLE_INDEX;
+ }
}
}
@Override
public int insertSlot(int tupleIndex, int tupleOff) {
int slotOff = getSlotOff(tupleIndex);
- if (tupleIndex < 0) {
+ if (tupleIndex == HIGHEST_TUPLE_INDEX) {
slotOff = getSlotEndOff() - slotSize;
setSlot(slotOff, tupleOff);
return slotOff;
@@ -93,4 +107,14 @@
return slotOff;
}
}
+
+ @Override
+ public boolean isHighestTupleIndex(int tupleIndex) {
+ return tupleIndex == HIGHEST_TUPLE_INDEX;
+ }
+
+ @Override
+ public boolean isErrorTupleIndex(int tupleIndex) {
+ return tupleIndex == ERROR_TUPLE_INDEX;
+ }
}
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 0d3c35e..9a47d7b 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
@@ -125,12 +125,18 @@
ICachedPage page = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, currentPageId), false);
page.acquireReadLatch();
- cursor.setBufferCache(bufferCache);
- cursor.setFileId(fileId);
- cursor.setCurrentPageId(currentPageId);
- cursor.setMaxPageId(maxPageId);
- ctx.cursorInitialState.setPage(page);
- cursor.open(ctx.cursorInitialState, diskOrderScanPredicate);
+ try {
+ cursor.setBufferCache(bufferCache);
+ cursor.setFileId(fileId);
+ cursor.setCurrentPageId(currentPageId);
+ cursor.setMaxPageId(maxPageId);
+ ctx.cursorInitialState.setPage(page);
+ cursor.open(ctx.cursorInitialState, diskOrderScanPredicate);
+ } catch (Exception e) {
+ page.releaseReadLatch();
+ bufferCache.unpin(page);
+ throw new HyracksDataException(e);
+ }
}
public void search(ITreeIndexCursor cursor, RangePredicate pred, BTreeOpContext ctx) throws Exception {
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ISlotManager.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ISlotManager.java
index a6102ab..93f3cf0 100644
--- a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ISlotManager.java
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ISlotManager.java
@@ -27,6 +27,10 @@
ITreeIndexTupleReference frameTuple, MultiComparator multiCmp,
FindTupleMode mode, FindTupleNoExactMatchPolicy matchPolicy);
+ public boolean isHighestTupleIndex(int tupleIndex);
+
+ public boolean isErrorTupleIndex(int tupleIndex);
+
public int insertSlot(int tupleIndex, int tupleOff);
public int getSlotStartOff();
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 bec3418..e9f5ebc 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
@@ -29,9 +29,6 @@
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;
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/impls/TreeDiskOrderScanCursor.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/impls/TreeDiskOrderScanCursor.java
index e1a0dd6..c3c256e 100644
--- a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/impls/TreeDiskOrderScanCursor.java
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/impls/TreeDiskOrderScanCursor.java
@@ -15,9 +15,7 @@
package edu.uci.ics.hyracks.storage.am.common.impls;
-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.marshalling.IntegerSerializerDeserializer;
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;
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/FindTupleMode.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/FindTupleMode.java
index 11ac257..5002189 100644
--- a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/FindTupleMode.java
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/FindTupleMode.java
@@ -16,5 +16,5 @@
package edu.uci.ics.hyracks.storage.am.common.ophelpers;
public enum FindTupleMode {
- FTM_INCLUSIVE, FTM_EXCLUSIVE, FTM_EXACT
+ INCLUSIVE, EXCLUSIVE, EXCLUSIVE_ERROR_IF_EXISTS, EXACT
}