refactoring and cleaning btree code, first pass
git-svn-id: https://hyracks.googlecode.com/svn/trunk/hyracks@94 123451ca-8445-de46-9d55-352943316053
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 1618b88..35e7eec 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
@@ -27,8 +27,6 @@
import edu.uci.ics.hyracks.storage.am.btree.interfaces.IBTreeFrameLeaf;
import edu.uci.ics.hyracks.storage.am.btree.interfaces.IBTreeFrameLeafFactory;
import edu.uci.ics.hyracks.storage.am.btree.interfaces.IBTreeFrameMeta;
-import edu.uci.ics.hyracks.storage.am.btree.interfaces.ISlotManager;
-import edu.uci.ics.hyracks.storage.am.btree.interfaces.ISlotManagerFactory;
import edu.uci.ics.hyracks.storage.am.btree.interfaces.SpaceStatus;
import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
@@ -46,9 +44,7 @@
private final IBufferCache bufferCache;
private int fileId;
private final IBTreeFrameInteriorFactory interiorFrameFactory;
- private final IBTreeFrameLeafFactory leafFrameFactory;
- private final ISlotManagerFactory interiorSlotManagerFactory;
- private final ISlotManagerFactory leafSlotManagerFactory;
+ private final IBTreeFrameLeafFactory leafFrameFactory;
private final MultiComparator cmp;
private final ReadWriteLock treeLatch;
@@ -84,13 +80,10 @@
}
public BTree(IBufferCache bufferCache, IBTreeFrameInteriorFactory interiorFrameFactory,
- IBTreeFrameLeafFactory leafFrameFactory, ISlotManagerFactory interiorSlotManagerFactory,
- ISlotManagerFactory leafSlotManagerFactory, MultiComparator cmp) {
+ IBTreeFrameLeafFactory leafFrameFactory, MultiComparator cmp) {
this.bufferCache = bufferCache;
this.interiorFrameFactory = interiorFrameFactory;
- this.leafFrameFactory = leafFrameFactory;
- this.interiorSlotManagerFactory = interiorSlotManagerFactory;
- this.leafSlotManagerFactory = leafSlotManagerFactory;
+ this.leafFrameFactory = leafFrameFactory;
this.cmp = cmp;
this.treeLatch = new ReentrantReadWriteLock(true);
}
@@ -593,7 +586,6 @@
rightNode.acquireWriteLatch();
writeLatchesAcquired++;
try {
- ISlotManager rightSlotManager = leafSlotManagerFactory.getSlotManager();
IBTreeFrameLeaf rightFrame = leafFrameFactory.getFrame();
rightFrame.setPage(rightNode);
rightFrame.initBuffer((byte) 0);
@@ -678,7 +670,6 @@
rightNode.acquireWriteLatch();
writeLatchesAcquired++;
try {
- ISlotManager rightSlotManager = interiorSlotManagerFactory.getSlotManager();
IBTreeFrame rightFrame = interiorFrameFactory.getFrame();
rightFrame.setPage(rightNode);
rightFrame.initBuffer((byte) ctx.interiorFrame.getLevel());
@@ -790,7 +781,6 @@
// will this leaf become empty?
if (ctx.leafFrame.getNumRecords() == 1) {
- ISlotManager siblingSlotManager = leafSlotManagerFactory.getSlotManager();
IBTreeFrameLeaf siblingFrame = leafFrameFactory.getFrame();
ICachedPage leftNode = null;
@@ -1301,15 +1291,7 @@
public IBTreeFrameLeafFactory getLeafFrameFactory() {
return leafFrameFactory;
}
-
- public ISlotManagerFactory getInteriorSlotManagerFactory() {
- return interiorSlotManagerFactory;
- }
-
- public ISlotManagerFactory getLeafSlotManagerFactory() {
- return leafSlotManagerFactory;
- }
-
+
public MultiComparator getMultiComparator() {
return cmp;
}
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeNSM.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeNSM.java
index 3daeba0..7a0a798 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeNSM.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeNSM.java
@@ -15,20 +15,37 @@
package edu.uci.ics.hyracks.storage.am.btree.impls;
-import edu.uci.ics.hyracks.storage.am.btree.interfaces.IBTreeFrame;
+import java.nio.ByteBuffer;
+import java.util.ArrayList;
+import java.util.Collections;
-public abstract class BTreeNSM extends NSMFrame implements IBTreeFrame {
+import edu.uci.ics.hyracks.storage.am.btree.interfaces.IBTreeFrame;
+import edu.uci.ics.hyracks.storage.am.btree.interfaces.ISlotManager;
+import edu.uci.ics.hyracks.storage.am.btree.interfaces.SpaceStatus;
+import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
+
+public abstract class BTreeNSM implements IBTreeFrame {
+ protected static final int pageLsnOff = 0; // 0
+ protected static final int numRecordsOff = pageLsnOff + 4; // 4
+ protected static final int freeSpaceOff = numRecordsOff + 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 static final byte smFlagOff = levelOff + 1;
+
+ protected ICachedPage page = null;
+ protected ByteBuffer buf = null;
+ protected ISlotManager slotManager;
public BTreeNSM() {
- super();
+ this.slotManager = new OrderedSlotManager();
}
@Override
public void initBuffer(byte level) {
- super.initBuffer(level);
+ buf.putInt(pageLsnOff, 0); // TODO: might to set to a different lsn during creation
+ buf.putInt(numRecordsOff, 0);
+ resetSpaceParams();
buf.put(levelOff, level);
buf.put(smFlagOff, (byte)0);
}
@@ -68,4 +85,178 @@
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 void compact(MultiComparator cmp) {
+ resetSpaceParams();
+
+ int numRecords = buf.getInt(numRecordsOff);
+ int freeSpace = buf.getInt(freeSpaceOff);
+ byte[] data = buf.array();
+
+ ArrayList<SlotOffRecOff> sortedRecOffs = new ArrayList<SlotOffRecOff>();
+ sortedRecOffs.ensureCapacity(numRecords);
+ for(int i = 0; i < numRecords; i++) {
+ int slotOff = slotManager.getSlotOff(i);
+ int recOff = slotManager.getRecOff(slotOff);
+ sortedRecOffs.add(new SlotOffRecOff(slotOff, recOff));
+ }
+ Collections.sort(sortedRecOffs);
+
+ for(int i = 0; i < sortedRecOffs.size(); i++) {
+ int recOff = sortedRecOffs.get(i).recOff;
+ int recSize = cmp.getRecordSize(data, recOff);
+ System.arraycopy(data, recOff, data, freeSpace, recSize);
+ slotManager.setSlot(sortedRecOffs.get(i).slotOff, freeSpace);
+ freeSpace += recSize;
+ }
+
+ buf.putInt(freeSpaceOff, freeSpace);
+ buf.putInt(totalFreeSpaceOff, buf.capacity() - freeSpace - numRecords * slotManager.getSlotSize());
+ }
+
+ @Override
+ public void delete(byte[] data, MultiComparator cmp, boolean exactDelete) throws Exception {
+ int slotOff = slotManager.findSlot(buf, data, cmp, true);
+ if(slotOff < 0) {
+ throw new BTreeException("Key to be deleted does not exist.");
+ }
+ else {
+ if(exactDelete) {
+ // check the non-key columns for equality by byte-by-byte comparison
+ int storedRecOff = slotManager.getRecOff(slotOff);
+ int storedRecSize = cmp.getRecordSize(buf.array(), storedRecOff);
+ if(data.length != storedRecSize) {
+ throw new BTreeException("Cannot delete record. Given record size does not match candidate record.");
+ }
+ for(int i = 0; i < storedRecSize; i++) {
+ if(data[i] != buf.array()[storedRecOff+i]) {
+ throw new BTreeException("Cannot delete record. Byte-by-byte comparison failed to prove equality.");
+ }
+ }
+ }
+
+ int recOff = slotManager.getRecOff(slotOff);
+ int recSize = cmp.getRecordSize(buf.array(), recOff);
+
+ // 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(numRecordsOff, buf.getInt(numRecordsOff) - 1);
+ buf.putInt(totalFreeSpaceOff, buf.getInt(totalFreeSpaceOff) + recSize + slotManager.getSlotSize());
+ }
+ }
+
+ @Override
+ public SpaceStatus hasSpaceInsert(byte[] data, MultiComparator cmp) {
+ if(data.length + slotManager.getSlotSize() <= buf.capacity() - buf.getInt(freeSpaceOff) - (buf.getInt(numRecordsOff) * slotManager.getSlotSize()) ) return SpaceStatus.SUFFICIENT_CONTIGUOUS_SPACE;
+ else if(data.length + slotManager.getSlotSize() <= buf.getInt(totalFreeSpaceOff)) return SpaceStatus.SUFFICIENT_SPACE;
+ else return SpaceStatus.INSUFFICIENT_SPACE;
+ }
+
+ @Override
+ public SpaceStatus hasSpaceUpdate(int rid, byte[] data, MultiComparator cmp) {
+ // TODO Auto-generated method stub
+ return SpaceStatus.INSUFFICIENT_SPACE;
+ }
+
+ protected void resetSpaceParams() {
+ buf.putInt(freeSpaceOff, totalFreeSpaceOff + 4);
+ buf.putInt(totalFreeSpaceOff, buf.capacity() - (totalFreeSpaceOff + 4));
+ }
+
+ @Override
+ public void insert(byte[] data, MultiComparator cmp) throws Exception {
+ int slotOff = slotManager.findSlot(buf, data, cmp, false);
+ slotOff = slotManager.insertSlot(slotOff, buf.getInt(freeSpaceOff));
+
+ int recOff = buf.getInt(freeSpaceOff);
+ System.arraycopy(data, 0, buf.array(), recOff, data.length);
+
+ buf.putInt(numRecordsOff, buf.getInt(numRecordsOff) + 1);
+ buf.putInt(freeSpaceOff, buf.getInt(freeSpaceOff) + data.length);
+ buf.putInt(totalFreeSpaceOff, buf.getInt(totalFreeSpaceOff) - data.length - slotManager.getSlotSize());
+ }
+
+ @Override
+ public void update(int rid, byte[] data) throws Exception {
+ // TODO Auto-generated method stub
+
+ }
+
+ @Override
+ public void printHeader() {
+ // TODO Auto-generated method stub
+
+ }
+
+ @Override
+ public int getNumRecords() {
+ return buf.getInt(numRecordsOff);
+ }
+
+ public ISlotManager getSlotManager() {
+ return slotManager;
+ }
+
+ @Override
+ public String printKeys(MultiComparator cmp) {
+ StringBuilder strBuilder = new StringBuilder();
+ int numRecords = buf.getInt(numRecordsOff);
+ for(int i = 0; i < numRecords; i++) {
+ int recOff = slotManager.getRecOff(slotManager.getSlotOff(i));
+ for(int j = 0; j < cmp.size(); j++) {
+ strBuilder.append(cmp.getFields()[j].print(buf.array(), recOff) + " ");
+ recOff += cmp.getFields()[j].getLength(buf.array(), recOff);
+ }
+ strBuilder.append(" | ");
+ }
+ strBuilder.append("\n");
+ return strBuilder.toString();
+ }
+
+ @Override
+ public int getRecordOffset(int slotNum) {
+ return slotManager.getRecOff(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;
+ }
}
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeNSMInterior.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeNSMInterior.java
index 165600f..96d2265 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeNSMInterior.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeNSMInterior.java
@@ -69,7 +69,7 @@
buf.putInt(totalFreeSpaceOff, buf.getInt(totalFreeSpaceOff) - recSize - slotManager.getSlotSize());
// did insert into the rightmost slot?
- if(slotOff == slotManager.getSlotStartOff()) {
+ if(slotOff == slotManager.getSlotEndOff()) {
System.arraycopy(data, recSize, buf.array(), rightLeafOff, childPtrSize);
}
else {
@@ -128,8 +128,8 @@
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().getSlotStartOff();
- int dest = rightFrame.getSlotManager().getSlotStartOff() + recordsToLeft * rightFrame.getSlotManager().getSlotSize();
+ int src = rightFrame.getSlotManager().getSlotEndOff();
+ int dest = rightFrame.getSlotManager().getSlotEndOff() + recordsToLeft * rightFrame.getSlotManager().getSlotSize();
int length = rightFrame.getSlotManager().getSlotSize() * recordsToRight;
System.arraycopy(right.array(), src, right.array(), dest, length);
right.putInt(numRecordsOff, recordsToRight);
@@ -142,12 +142,12 @@
System.arraycopy(data, 0, savedData, 0, data.length);
// set split key to be highest value in left page
- int recOff = slotManager.getRecOff(slotManager.getSlotStartOff());
+ int recOff = slotManager.getRecOff(slotManager.getSlotEndOff());
int splitKeySize = cmp.getKeySize(buf.array(), recOff);
splitKey.initData(splitKeySize);
System.arraycopy(buf.array(), recOff, splitKey.getData(), 0, splitKeySize);
- int deleteRecOff = slotManager.getRecOff(slotManager.getSlotStartOff());
+ int deleteRecOff = slotManager.getRecOff(slotManager.getSlotEndOff());
int deleteKeySize = cmp.getKeySize(buf.array(), deleteRecOff);
buf.putInt(rightLeafOff, buf.getInt(deleteRecOff + deleteKeySize));
buf.putInt(numRecordsOff, recordsToLeft - 1);
@@ -232,7 +232,7 @@
slotOff -= slotManager.getSlotSize();
}
else {
- int minSlotOff = slotManager.getSlotStartOff() - slotManager.getSlotSize();
+ int minSlotOff = slotManager.getSlotEndOff() - slotManager.getSlotSize();
slotOff -= slotManager.getSlotSize();
while(slotOff > minSlotOff) {
cmpRecOff = slotManager.getRecOff(slotOff);
@@ -254,7 +254,7 @@
int keySize;
if(slotOff < 0) {
- recOff = slotManager.getRecOff(slotManager.getSlotStartOff());
+ recOff = slotManager.getRecOff(slotManager.getSlotEndOff());
keySize = cmp.getKeySize(buf.array(), recOff);
// copy new rightmost pointer
System.arraycopy(buf.array(), recOff + keySize, buf.array(), rightLeafOff, childPtrSize);
@@ -263,7 +263,7 @@
recOff = slotManager.getRecOff(slotOff);
keySize = cmp.getKeySize(buf.array(), recOff);
// perform deletion (we just do a memcpy to overwrite the slot)
- int slotStartOff = slotManager.getSlotStartOff();
+ int slotStartOff = slotManager.getSlotEndOff();
int length = slotOff - slotStartOff;
System.arraycopy(buf.array(), slotStartOff, buf.array(), slotStartOff + slotManager.getSlotSize(), length);
}
@@ -281,7 +281,7 @@
@Override
public int getLeftmostChildPageId(MultiComparator cmp) {
- int recOff = slotManager.getRecOff(slotManager.getSlotEndOff());
+ int recOff = slotManager.getRecOff(slotManager.getSlotStartOff());
int childPageOff = getLeftChildPageOff(recOff, cmp);
return buf.getInt(childPageOff);
}
@@ -315,7 +315,7 @@
@Override
public void deleteGreatest(MultiComparator cmp) {
- int slotOff = slotManager.getSlotStartOff();
+ int slotOff = slotManager.getSlotEndOff();
int recOff = slotManager.getRecOff(slotOff);
int keySize = cmp.getKeySize(buf.array(), recOff);
System.arraycopy(buf.array(), recOff + keySize, buf.array(), rightLeafOff, childPtrSize);
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeNSMLeaf.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeNSMLeaf.java
index 835fe9d..c32c7a7 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeNSMLeaf.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeNSMLeaf.java
@@ -59,7 +59,7 @@
public void insert(byte[] data, MultiComparator cmp) throws Exception {
int slotOff = slotManager.findSlot(buf, data, cmp, false);
boolean isDuplicate = true;
-
+
if (slotOff < 0) isDuplicate = false; // greater than all existing keys
else if (cmp.compare(data, 0, buf.array(), slotManager.getRecOff(slotOff)) != 0) isDuplicate = false;
@@ -105,7 +105,7 @@
int recordsToLeft;
int mid = numRecords / 2;
IBTreeFrame targetFrame = null;
- if ((cmp.compare(data, 0, buf.array(), slotManager.getRecOff(slotManager.getSlotStartOff() + slotManager.getSlotSize() * mid))) >= 0) {
+ if ((cmp.compare(data, 0, buf.array(), slotManager.getRecOff(slotManager.getSlotEndOff() + slotManager.getSlotSize() * mid))) >= 0) {
recordsToLeft = mid + (numRecords % 2);
targetFrame = rightFrame;
} else {
@@ -118,8 +118,8 @@
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().getSlotStartOff();
- int dest = rightFrame.getSlotManager().getSlotStartOff() + recordsToLeft * rightFrame.getSlotManager().getSlotSize();
+ int src = rightFrame.getSlotManager().getSlotEndOff();
+ int dest = rightFrame.getSlotManager().getSlotEndOff() + recordsToLeft * rightFrame.getSlotManager().getSlotSize();
int length = rightFrame.getSlotManager().getSlotSize() * recordsToRight;
System.arraycopy(right.array(), src, right.array(), dest, length);
right.putInt(numRecordsOff, recordsToRight);
@@ -135,7 +135,7 @@
targetFrame.insert(data, cmp);
// set split key to be highest value in left page
- int recOff = slotManager.getRecOff(slotManager.getSlotStartOff());
+ int recOff = slotManager.getRecOff(slotManager.getSlotEndOff());
int keySize = cmp.getKeySize(buf.array(), recOff);
splitKey.initData(keySize);
System.arraycopy(buf.array(), recOff, splitKey.getData(), 0, keySize);
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/NSMFrame.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/NSMFrame.java
deleted file mode 100644
index 5e13113..0000000
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/NSMFrame.java
+++ /dev/null
@@ -1,223 +0,0 @@
-/*
- * 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.impls;
-
-import java.nio.ByteBuffer;
-import java.util.ArrayList;
-import java.util.Collections;
-
-import edu.uci.ics.hyracks.storage.am.btree.interfaces.IFrame;
-import edu.uci.ics.hyracks.storage.am.btree.interfaces.ISlotManager;
-import edu.uci.ics.hyracks.storage.am.btree.interfaces.SpaceStatus;
-import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
-
-public class NSMFrame implements IFrame {
-
- protected static final int pageLsnOff = 0; // 0
- protected static final int numRecordsOff = pageLsnOff + 4; // 4
- protected static final int freeSpaceOff = numRecordsOff + 4; // 8
- protected static final int totalFreeSpaceOff = freeSpaceOff + 4; // 16
-
- protected ICachedPage page = null;
- protected ByteBuffer buf = null;
- protected ISlotManager slotManager;
-
- public NSMFrame() {
- // TODO: hardcode slotManager for now...
- this.slotManager = new OrderedSlotManager();
- }
-
- @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 void compact(MultiComparator cmp) {
- resetSpaceParams();
-
- int numRecords = buf.getInt(numRecordsOff);
- int freeSpace = buf.getInt(freeSpaceOff);
- byte[] data = buf.array();
-
- ArrayList<SlotOffRecOff> sortedRecOffs = new ArrayList<SlotOffRecOff>();
- sortedRecOffs.ensureCapacity(numRecords);
- for(int i = 0; i < numRecords; i++) {
- int slotOff = slotManager.getSlotOff(i);
- int recOff = slotManager.getRecOff(slotOff);
- sortedRecOffs.add(new SlotOffRecOff(slotOff, recOff));
- }
- Collections.sort(sortedRecOffs);
-
- for(int i = 0; i < sortedRecOffs.size(); i++) {
- int recOff = sortedRecOffs.get(i).recOff;
- int recSize = cmp.getRecordSize(data, recOff);
- System.arraycopy(data, recOff, data, freeSpace, recSize);
- slotManager.setSlot(sortedRecOffs.get(i).slotOff, freeSpace);
- freeSpace += recSize;
- }
-
- buf.putInt(freeSpaceOff, freeSpace);
- buf.putInt(totalFreeSpaceOff, buf.capacity() - freeSpace - numRecords * slotManager.getSlotSize());
- }
-
- @Override
- public void delete(byte[] data, MultiComparator cmp, boolean exactDelete) throws Exception {
- int slotOff = slotManager.findSlot(buf, data, cmp, true);
- if(slotOff < 0) {
- throw new BTreeException("Key to be deleted does not exist.");
- }
- else {
- if(exactDelete) {
- // check the non-key columns for equality by byte-by-byte comparison
- int storedRecOff = slotManager.getRecOff(slotOff);
- int storedRecSize = cmp.getRecordSize(buf.array(), storedRecOff);
- if(data.length != storedRecSize) {
- throw new BTreeException("Cannot delete record. Given record size does not match candidate record.");
- }
- for(int i = 0; i < storedRecSize; i++) {
- if(data[i] != buf.array()[storedRecOff+i]) {
- throw new BTreeException("Cannot delete record. Byte-by-byte comparison failed to prove equality.");
- }
- }
- }
-
- int recOff = slotManager.getRecOff(slotOff);
- int recSize = cmp.getRecordSize(buf.array(), recOff);
-
- // perform deletion (we just do a memcpy to overwrite the slot)
- int slotStartOff = slotManager.getSlotStartOff();
- int length = slotOff - slotStartOff;
- System.arraycopy(buf.array(), slotStartOff, buf.array(), slotStartOff + slotManager.getSlotSize(), length);
-
- // maintain space information
- buf.putInt(numRecordsOff, buf.getInt(numRecordsOff) - 1);
- buf.putInt(totalFreeSpaceOff, buf.getInt(totalFreeSpaceOff) + recSize + slotManager.getSlotSize());
- }
- }
-
- @Override
- public SpaceStatus hasSpaceInsert(byte[] data, MultiComparator cmp) {
- if(data.length + slotManager.getSlotSize() <= buf.capacity() - buf.getInt(freeSpaceOff) - (buf.getInt(numRecordsOff) * slotManager.getSlotSize()) ) return SpaceStatus.SUFFICIENT_CONTIGUOUS_SPACE;
- else if(data.length + slotManager.getSlotSize() <= buf.getInt(totalFreeSpaceOff)) return SpaceStatus.SUFFICIENT_SPACE;
- else return SpaceStatus.INSUFFICIENT_SPACE;
- }
-
- @Override
- public SpaceStatus hasSpaceUpdate(int rid, byte[] data, MultiComparator cmp) {
- // TODO Auto-generated method stub
- return SpaceStatus.INSUFFICIENT_SPACE;
- }
-
- protected void resetSpaceParams() {
- buf.putInt(freeSpaceOff, totalFreeSpaceOff + 4);
- buf.putInt(totalFreeSpaceOff, buf.capacity() - (totalFreeSpaceOff + 4));
- }
-
- @Override
- public void initBuffer(byte level) {
- buf.putInt(pageLsnOff, 0); // TODO: might to set to a different lsn during creation
- buf.putInt(numRecordsOff, 0);
- resetSpaceParams();
- }
-
- @Override
- public void insert(byte[] data, MultiComparator cmp) throws Exception {
- int slotOff = slotManager.findSlot(buf, data, cmp, false);
- slotOff = slotManager.insertSlot(slotOff, buf.getInt(freeSpaceOff));
-
- int recOff = buf.getInt(freeSpaceOff);
- System.arraycopy(data, 0, buf.array(), recOff, data.length);
-
- buf.putInt(numRecordsOff, buf.getInt(numRecordsOff) + 1);
- buf.putInt(freeSpaceOff, buf.getInt(freeSpaceOff) + data.length);
- buf.putInt(totalFreeSpaceOff, buf.getInt(totalFreeSpaceOff) - data.length - slotManager.getSlotSize());
- }
-
- @Override
- public void update(int rid, byte[] data) throws Exception {
- // TODO Auto-generated method stub
-
- }
-
- @Override
- public void printHeader() {
- // TODO Auto-generated method stub
-
- }
-
- @Override
- public int getNumRecords() {
- return buf.getInt(numRecordsOff);
- }
-
- public ISlotManager getSlotManager() {
- return slotManager;
- }
-
- @Override
- public String printKeys(MultiComparator cmp) {
- StringBuilder strBuilder = new StringBuilder();
- int numRecords = buf.getInt(numRecordsOff);
- for(int i = 0; i < numRecords; i++) {
- int recOff = slotManager.getRecOff(slotManager.getSlotOff(i));
- for(int j = 0; j < cmp.size(); j++) {
- strBuilder.append(cmp.getFields()[j].print(buf.array(), recOff) + " ");
- recOff += cmp.getFields()[j].getLength(buf.array(), recOff);
- }
- strBuilder.append(" | ");
- }
- strBuilder.append("\n");
- return strBuilder.toString();
- }
-
- @Override
- public int getRecordOffset(int slotNum) {
- return slotManager.getRecOff(slotManager.getSlotEndOff() - 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;
- }
-}
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/OrderedSlotManager.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/OrderedSlotManager.java
index 23ee6c5..c6f06f4 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/OrderedSlotManager.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/OrderedSlotManager.java
@@ -17,41 +17,43 @@
import java.nio.ByteBuffer;
-import edu.uci.ics.hyracks.storage.am.btree.interfaces.IFrame;
+import edu.uci.ics.hyracks.storage.am.btree.interfaces.IBTreeFrame;
import edu.uci.ics.hyracks.storage.am.btree.interfaces.ISlotManager;
public class OrderedSlotManager implements ISlotManager {
private static final int slotSize = 4;
- private IFrame frame;
+ private IBTreeFrame frame;
// TODO: mix in interpolation search
@Override
public int findSlot(ByteBuffer buf, byte[] data, MultiComparator multiCmp, boolean exact) {
+ if(frame.getNumRecords() <= 0) return -1;
+
int mid;
- int begin = getSlotStartOff();
- int end = getSlotEndOff();
-
- // deal with first record insertion
- if(begin == buf.capacity()) return -1;
+ int begin = 0;
+ int end = frame.getNumRecords() - 1;
while(begin <= end) {
- mid = (begin + end) >> 1;
- mid -= mid % slotSize;
- int recOff = getRecOff(mid);
+ mid = (begin + end) / 2;
+ int slotOff = getSlotOff(mid);
+ int recOff = getRecOff(slotOff);
int cmp = multiCmp.compare(data, 0, buf.array(), recOff);
if(cmp < 0)
- begin = mid + slotSize;
+ end = mid - 1;
else if(cmp > 0)
- end = mid - slotSize;
+ begin = mid + 1;
else
- return mid;
+ return slotOff;
}
- if(exact) return -1;
- if(end < getSlotStartOff()) return -1;
- if(multiCmp.compare(data, 0, buf.array(), getRecOff(end)) < 0)
- return end;
+ if(exact) return -1;
+ if(begin > frame.getNumRecords() - 1) return -1;
+
+ int slotOff = getSlotOff(begin);
+ int recOff = getRecOff(slotOff);
+ if(multiCmp.compare(data, 0, buf.array(), recOff) < 0)
+ return slotOff;
else
return -1;
}
@@ -67,12 +69,12 @@
}
@Override
- public int getSlotStartOff() {
+ public int getSlotEndOff() {
return frame.getBuffer().capacity() - (frame.getNumRecords() * slotSize);
}
@Override
- public int getSlotEndOff() {
+ public int getSlotStartOff() {
return frame.getBuffer().capacity() - slotSize;
}
@@ -84,26 +86,26 @@
@Override
public int insertSlot(int slotOff, int recOff) {
if(slotOff < 0) {
- slotOff = getSlotStartOff() - slotSize;
+ slotOff = getSlotEndOff() - slotSize;
setSlot(slotOff, recOff);
return slotOff;
}
else {
- int slotStartOff = getSlotStartOff();
- int length = (slotOff - slotStartOff) + slotSize;
- System.arraycopy(frame.getBuffer().array(), slotStartOff, frame.getBuffer().array(), slotStartOff - slotSize, length);
+ int slotEndOff = getSlotEndOff();
+ int length = (slotOff - slotEndOff) + slotSize;
+ System.arraycopy(frame.getBuffer().array(), slotEndOff, frame.getBuffer().array(), slotEndOff - slotSize, length);
setSlot(slotOff, recOff);
return slotOff;
}
}
@Override
- public void setFrame(IFrame frame) {
+ public void setFrame(IBTreeFrame frame) {
this.frame = frame;
}
-
+
@Override
public int getSlotOff(int slotNum) {
- return getSlotEndOff() - slotNum * slotSize;
+ return getSlotStartOff() - slotNum * slotSize;
}
}
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/interfaces/IBTreeFrame.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/interfaces/IBTreeFrame.java
index acfabe6..78a8c81 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/interfaces/IBTreeFrame.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/interfaces/IBTreeFrame.java
@@ -15,10 +15,44 @@
package edu.uci.ics.hyracks.storage.am.btree.interfaces;
+import java.nio.ByteBuffer;
+
import edu.uci.ics.hyracks.storage.am.btree.impls.MultiComparator;
import edu.uci.ics.hyracks.storage.am.btree.impls.SplitKey;
+import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
-public interface IBTreeFrame extends IFrame {
+public interface IBTreeFrame {
+ public void setPage(ICachedPage page);
+ public ICachedPage getPage();
+ public ByteBuffer getBuffer();
+
+ public void insert(byte[] data, MultiComparator cmp) throws Exception;
+ public void update(int rid, byte[] data) throws Exception;
+ public void delete(byte[] data, MultiComparator cmp, boolean exactDelete) throws Exception;
+
+ public void compact(MultiComparator cmp);
+ public boolean compress(MultiComparator cmp) throws Exception;
+
+ public void initBuffer(byte level);
+
+ public int getNumRecords();
+
+ // assumption: page must be write-latched at this point
+ public SpaceStatus hasSpaceInsert(byte[] data, MultiComparator cmp);
+ public SpaceStatus hasSpaceUpdate(int rid, byte[] data, MultiComparator cmp);
+
+ public int getRecordOffset(int slotNum);
+
+ public int getTotalFreeSpace();
+
+ public void setPageLsn(int pageLsn);
+ public int getPageLsn();
+
+ // for debugging
+ public void printHeader();
+ public String printKeys(MultiComparator cmp);
+
+
// TODO; what if records more than half-page size?
public int split(IBTreeFrame rightFrame, byte[] data, MultiComparator cmp, SplitKey splitKey) throws Exception;
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/interfaces/IFrame.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/interfaces/IFrame.java
deleted file mode 100644
index 56bf9a9..0000000
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/interfaces/IFrame.java
+++ /dev/null
@@ -1,53 +0,0 @@
-/*
- * 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.interfaces;
-
-import java.nio.ByteBuffer;
-
-import edu.uci.ics.hyracks.storage.am.btree.impls.MultiComparator;
-import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
-
-public interface IFrame {
- public void setPage(ICachedPage page);
- public ICachedPage getPage();
- public ByteBuffer getBuffer();
-
- public void insert(byte[] data, MultiComparator cmp) throws Exception;
- public void update(int rid, byte[] data) throws Exception;
- public void delete(byte[] data, MultiComparator cmp, boolean exactDelete) throws Exception;
-
- public void compact(MultiComparator cmp);
- public boolean compress(MultiComparator cmp) throws Exception;
-
- public void initBuffer(byte level);
-
- public int getNumRecords();
-
- // assumption: page must be write-latched at this point
- public SpaceStatus hasSpaceInsert(byte[] data, MultiComparator cmp);
- public SpaceStatus hasSpaceUpdate(int rid, byte[] data, MultiComparator cmp);
-
- public int getRecordOffset(int slotNum);
-
- public int getTotalFreeSpace();
-
- public void setPageLsn(int pageLsn);
- public int getPageLsn();
-
- // for debugging
- public void printHeader();
- public String printKeys(MultiComparator cmp);
-}
\ No newline at end of file
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/interfaces/ISlotManager.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/interfaces/ISlotManager.java
index cf81316..a2d2305 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/interfaces/ISlotManager.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/interfaces/ISlotManager.java
@@ -21,7 +21,7 @@
public interface ISlotManager {
- public void setFrame(IFrame frame);
+ public void setFrame(IBTreeFrame frame);
// TODO: first argument can be removed. frame must be set and buffer can be gotten from there
public int findSlot(ByteBuffer buf, byte[] data, MultiComparator multiCmp, boolean exact);
diff --git a/hyracks-storage-am-btree/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeTest.java b/hyracks-storage-am-btree/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeTest.java
index 4fd1f2a..c585b29 100644
--- a/hyracks-storage-am-btree/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeTest.java
+++ b/hyracks-storage-am-btree/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeTest.java
@@ -36,7 +36,6 @@
import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeNSMLeafFactory;
import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeRangeSearchCursor;
import edu.uci.ics.hyracks.storage.am.btree.impls.MultiComparator;
-import edu.uci.ics.hyracks.storage.am.btree.impls.OrderedSlotManagerFactory;
import edu.uci.ics.hyracks.storage.am.btree.impls.RangePredicate;
import edu.uci.ics.hyracks.storage.am.btree.interfaces.IBTreeCursor;
import edu.uci.ics.hyracks.storage.am.btree.interfaces.IBTreeFrameInterior;
@@ -46,7 +45,6 @@
import edu.uci.ics.hyracks.storage.am.btree.interfaces.IBTreeFrameMeta;
import edu.uci.ics.hyracks.storage.am.btree.interfaces.IBTreeFrameMetaFactory;
import edu.uci.ics.hyracks.storage.am.btree.interfaces.IFieldAccessor;
-import edu.uci.ics.hyracks.storage.am.btree.interfaces.ISlotManagerFactory;
import edu.uci.ics.hyracks.storage.am.btree.types.Int32Accessor;
import edu.uci.ics.hyracks.storage.am.btree.types.StringAccessor;
import edu.uci.ics.hyracks.storage.common.buffercache.BufferCache;
@@ -102,8 +100,6 @@
FileInfo fi = new FileInfo(fileId, raf);
fileManager.registerFile(fi);
- ISlotManagerFactory leafSlotManagerFactory = new OrderedSlotManagerFactory();
- ISlotManagerFactory interiorSlotManagerFactory = new OrderedSlotManagerFactory();
IBTreeFrameLeafFactory leafFrameFactory = new BTreeNSMLeafFactory();
IBTreeFrameInteriorFactory interiorFrameFactory = new BTreeNSMInteriorFactory();
IBTreeFrameMetaFactory metaFrameFactory = new BTreeMetaFactory();
@@ -120,8 +116,8 @@
IBinaryComparator[] cmps = new IBinaryComparator[keyLen];
cmps[0] = IntegerBinaryComparatorFactory.INSTANCE.createBinaryComparator();
MultiComparator cmp = new MultiComparator(cmps, fields);
-
- BTree btree = new BTree(bufferCache, interiorFrameFactory, leafFrameFactory, interiorSlotManagerFactory, leafSlotManagerFactory, cmp);
+
+ BTree btree = new BTree(bufferCache, interiorFrameFactory, leafFrameFactory, cmp);
btree.create(fileId, leafFrame, metaFrame);
btree.open(fileId);
@@ -265,9 +261,7 @@
int fileId = 0;
FileInfo fi = new FileInfo(fileId, raf);
fileManager.registerFile(fi);
-
- ISlotManagerFactory leafSlotManagerFactory = new OrderedSlotManagerFactory();
- ISlotManagerFactory interiorSlotManagerFactory = new OrderedSlotManagerFactory();
+
IBTreeFrameLeafFactory leafFrameFactory = new BTreeNSMLeafFactory();
IBTreeFrameInteriorFactory interiorFrameFactory = new BTreeNSMInteriorFactory();
IBTreeFrameMetaFactory metaFrameFactory = new BTreeMetaFactory();
@@ -287,12 +281,7 @@
cmps[1] = IntegerBinaryComparatorFactory.INSTANCE.createBinaryComparator();
MultiComparator cmp = new MultiComparator(cmps, fields);
- BTree btree = new BTree(bufferCache,
- interiorFrameFactory,
- leafFrameFactory,
- interiorSlotManagerFactory,
- leafSlotManagerFactory,
- cmp);
+ BTree btree = new BTree(bufferCache, interiorFrameFactory, leafFrameFactory, cmp);
btree.create(fileId, leafFrame, metaFrame);
btree.open(fileId);
@@ -414,9 +403,7 @@
int fileId = 0;
FileInfo fi = new FileInfo(fileId, raf);
fileManager.registerFile(fi);
-
- ISlotManagerFactory leafSlotManagerFactory = new OrderedSlotManagerFactory();
- ISlotManagerFactory interiorSlotManagerFactory = new OrderedSlotManagerFactory();
+
IBTreeFrameLeafFactory leafFrameFactory = new BTreeNSMLeafFactory();
IBTreeFrameInteriorFactory interiorFrameFactory = new BTreeNSMInteriorFactory();
IBTreeFrameMetaFactory metaFrameFactory = new BTreeMetaFactory();
@@ -434,12 +421,7 @@
cmps[0] = UTF8StringBinaryComparatorFactory.INSTANCE.createBinaryComparator();
MultiComparator cmp = new MultiComparator(cmps, fields);
- BTree btree = new BTree(bufferCache,
- interiorFrameFactory,
- leafFrameFactory,
- interiorSlotManagerFactory,
- leafSlotManagerFactory,
- cmp);
+ BTree btree = new BTree(bufferCache, interiorFrameFactory, leafFrameFactory, cmp);
btree.create(fileId, leafFrame, metaFrame);
btree.open(fileId);
@@ -554,9 +536,7 @@
int fileId = 0;
FileInfo fi = new FileInfo(fileId, raf);
fileManager.registerFile(fi);
-
- ISlotManagerFactory leafSlotManagerFactory = new OrderedSlotManagerFactory();
- ISlotManagerFactory interiorSlotManagerFactory = new OrderedSlotManagerFactory();
+
IBTreeFrameLeafFactory leafFrameFactory = new BTreeNSMLeafFactory();
IBTreeFrameInteriorFactory interiorFrameFactory = new BTreeNSMInteriorFactory();
IBTreeFrameMetaFactory metaFrameFactory = new BTreeMetaFactory();
@@ -575,12 +555,7 @@
MultiComparator cmp = new MultiComparator(cmps, fields);
- BTree btree = new BTree(bufferCache,
- interiorFrameFactory,
- leafFrameFactory,
- interiorSlotManagerFactory,
- leafSlotManagerFactory,
- cmp);
+ BTree btree = new BTree(bufferCache, interiorFrameFactory, leafFrameFactory, cmp);
btree.create(fileId, leafFrame, metaFrame);
btree.open(fileId);
@@ -682,9 +657,7 @@
int fileId = 0;
FileInfo fi = new FileInfo(fileId, raf);
fileManager.registerFile(fi);
-
- ISlotManagerFactory leafSlotManagerFactory = new OrderedSlotManagerFactory();
- ISlotManagerFactory interiorSlotManagerFactory = new OrderedSlotManagerFactory();
+
IBTreeFrameLeafFactory leafFrameFactory = new BTreeNSMLeafFactory();
IBTreeFrameInteriorFactory interiorFrameFactory = new BTreeNSMInteriorFactory();
IBTreeFrameMetaFactory metaFrameFactory = new BTreeMetaFactory();
@@ -706,12 +679,7 @@
MultiComparator cmp = new MultiComparator(cmps, fields);
- BTree btree = new BTree(bufferCache,
- interiorFrameFactory,
- leafFrameFactory,
- interiorSlotManagerFactory,
- leafSlotManagerFactory,
- cmp);
+ BTree btree = new BTree(bufferCache, interiorFrameFactory, leafFrameFactory, cmp);
btree.create(fileId, leafFrame, metaFrame);
btree.open(fileId);
@@ -810,9 +778,7 @@
int fileId = 0;
FileInfo fi = new FileInfo(fileId, raf);
fileManager.registerFile(fi);
-
- ISlotManagerFactory leafSlotManagerFactory = new OrderedSlotManagerFactory();
- ISlotManagerFactory interiorSlotManagerFactory = new OrderedSlotManagerFactory();
+
IBTreeFrameLeafFactory leafFrameFactory = new BTreeNSMLeafFactory();
IBTreeFrameInteriorFactory interiorFrameFactory = new BTreeNSMInteriorFactory();
IBTreeFrameMetaFactory metaFrameFactory = new BTreeMetaFactory();
@@ -833,12 +799,7 @@
cmps[1] = IntegerBinaryComparatorFactory.INSTANCE.createBinaryComparator();
MultiComparator cmp = new MultiComparator(cmps, fields);
- BTree btree = new BTree(bufferCache,
- interiorFrameFactory,
- leafFrameFactory,
- interiorSlotManagerFactory,
- leafSlotManagerFactory,
- cmp);
+ BTree btree = new BTree(bufferCache, interiorFrameFactory, leafFrameFactory, cmp);
btree.create(fileId, leafFrame, metaFrame);
btree.open(fileId);