Thread: [Joafip-svn] SF.net SVN: joafip:[3031] trunk/joafip-btreeplus/src
Brought to you by:
luc_peuvrier
Menu
▾
▴
joafip-svn
|
From: <luc...@us...> - 2012-04-25 08:29:49
|
Revision: 3031
http://joafip.svn.sourceforge.net/joafip/?rev=3031&view=rev
Author: luc_peuvrier
Date: 2012-04-25 08:29:40 +0000 (Wed, 25 Apr 2012)
Log Message:
-----------
WIP btree plus, tests in progress. NonTerminalPage tests ok. split test was missing
Modified Paths:
--------------
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/INonTerminalPage.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/NonTerminalPage.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/NonTerminalPageTest.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/mock/MockDataBlock.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/mock/MockLeafPage.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/mock/MockNonTerminalPage.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/mock/MockPageRecordable.java
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
|
From: <luc...@us...> - 2012-04-25 08:29:49
|
Revision: 3031
http://joafip.svn.sourceforge.net/joafip/?rev=3031&view=rev
Author: luc_peuvrier
Date: 2012-04-25 08:29:40 +0000 (Wed, 25 Apr 2012)
Log Message:
-----------
WIP btree plus, tests in progress. NonTerminalPage tests ok. split test was missing
Modified Paths:
--------------
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/INonTerminalPage.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/NonTerminalPage.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/NonTerminalPageTest.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/mock/MockDataBlock.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/mock/MockLeafPage.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/mock/MockNonTerminalPage.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/mock/MockPageRecordable.java
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/INonTerminalPage.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/INonTerminalPage.java 2012-04-25 04:28:28 UTC (rev 3030)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/INonTerminalPage.java 2012-04-25 08:29:40 UTC (rev 3031)
@@ -23,6 +23,7 @@
*/
package net.sf.joafip.btreeplus.entity;
+import net.sf.joafip.kvstore.record.entity.DataRecordIdentifier;
import net.sf.joafip.kvstore.service.HeapException;
/**
@@ -37,4 +38,10 @@
long getPositionInFile();
+ int getNumberOfKeyEntries();
+
+ long getPagePointer(int index);
+
+ DataRecordIdentifier getKey(int index);
+
}
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/NonTerminalPage.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/NonTerminalPage.java 2012-04-25 04:28:28 UTC (rev 3030)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/NonTerminalPage.java 2012-04-25 08:29:40 UTC (rev 3031)
@@ -131,14 +131,17 @@
return xbyteSize;
}
+ @Override
public int getNumberOfKeyEntries() {
return numberOfKeyEntries;
}
+ @Override
public long getPagePointer(final int index) {
return pagePositions[index];
}
+ @Override
public DataRecordIdentifier getKey(final int index) {
return keys[index];
}
Modified: trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/NonTerminalPageTest.java
===================================================================
--- trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/NonTerminalPageTest.java 2012-04-25 04:28:28 UTC (rev 3030)
+++ trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/NonTerminalPageTest.java 2012-04-25 08:29:40 UTC (rev 3031)
@@ -335,15 +335,62 @@
}
public void testSplit() {
+ final int maxNumberOfEntries = maxNumberOfEntries() + 1;
+ final NonTerminalPage nonTerminalPage = new NonTerminalPage(
+ maxNumberOfEntries);
+ for (int index = 0; index < maxNumberOfEntries; index++) {
+ nonTerminalPage.setEntry(index, index * 1000,
+ new DataRecordIdentifier(index));
+ }
+ nonTerminalPage.setEntry(maxNumberOfEntries, maxNumberOfEntries * 1000,
+ null);
+ nonTerminalPage.updateByteSize();
- }
+ final int splitIndex = maxNumberOfEntries / 2;
+ final int leftNumberOfEntries = splitIndex;
+ final int rightNumberOfEntries = maxNumberOfEntries
+ - leftNumberOfEntries - 1;
+ final INonTerminalPage rightPage = nonTerminalPage.split();
- public void testSetEntry() {
+ final DataRecordIdentifier middleKey = nonTerminalPage
+ .getAndClearMiddleKey();
+ assertEquals("", leftNumberOfEntries,
+ nonTerminalPage.getNumberOfKeyEntries());
+ assertEquals("", rightNumberOfEntries,
+ rightPage.getNumberOfKeyEntries());
+
+ for (int count = 0; count < leftNumberOfEntries; count++) {
+ assertEquals("bad page pointer for #" + count, count * 1000,
+ nonTerminalPage.getPagePointer(count));
+ assertEquals("bad key #" + count, new DataRecordIdentifier(count),
+ nonTerminalPage.getKey(count));
+ }
+ assertEquals("bad page pointer for #" + leftNumberOfEntries,
+ leftNumberOfEntries * 1000,
+ nonTerminalPage.getPagePointer(leftNumberOfEntries));
+ assertEquals("bad middle key", new DataRecordIdentifier(splitIndex),
+ middleKey);
+ int index = splitIndex + 1;
+ for (int count = 0; count < rightNumberOfEntries; count++) {
+ assertEquals("bad page pointer for #" + count, index * 1000,
+ rightPage.getPagePointer(count));
+ assertEquals("bad key #" + count, new DataRecordIdentifier(index),
+ rightPage.getKey(count));
+ index++;
+ }
+ assertEquals("bad page pointer for #" + rightNumberOfEntries,
+ index * 1000, rightPage.getPagePointer(rightNumberOfEntries));
}
- public void testSetParentPage() {
-
+ public void testSetParentPage() throws HeapException {
+ final NonTerminalPage nonTerminalPage = new NonTerminalPage();
+ final IPageRecordable parentPage = new NonTerminalPage();
+ nonTerminalPage.setParentPage(parentPage, 10);
+ assertSame("bad parent page", parentPage,
+ nonTerminalPage.getParentPage());
+ assertEquals("bad index in parent", 10,
+ nonTerminalPage.getInParentIndex());
}
private void checkState(final NonTerminalPage nonTerminalPage,
Modified: trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/mock/MockDataBlock.java
===================================================================
--- trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/mock/MockDataBlock.java 2012-04-25 04:28:28 UTC (rev 3030)
+++ trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/mock/MockDataBlock.java 2012-04-25 08:29:40 UTC (rev 3031)
@@ -37,14 +37,10 @@
@Override
public void setValueIsChangedValueToSave() throws HeapException {
- // TODO Auto-generated method stub
-
}
@Override
public void setValueIsNotChanged() {
- // TODO Auto-generated method stub
-
}
public void setPosition(final long position) {
@@ -58,57 +54,45 @@
@Override
public void setData(byte[] data) throws HeapException {
- // TODO Auto-generated method stub
-
}
@Override
public byte[] getData() {
- // TODO Auto-generated method stub
return null;
}
@Override
public void setNextFreeDataBlockPosition(long nextFreeDataBlockPosition)
throws HeapException {
- // TODO Auto-generated method stub
-
}
@Override
public long getNextFreeDataBlockPosition() {
- // TODO Auto-generated method stub
return 0;
}
@Override
public byte[] getDataHolder() {
- // TODO Auto-generated method stub
return null;
}
@Override
public int getMinSize() {
- // TODO Auto-generated method stub
return 0;
}
@Override
public int getMaxSize() {
- // TODO Auto-generated method stub
return 0;
}
@Override
public byte getBits() {
- // TODO Auto-generated method stub
return 0;
}
@Override
public int getIndexInDataBlockPage() {
- // TODO Auto-generated method stub
return 0;
}
-
}
Modified: trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/mock/MockLeafPage.java
===================================================================
--- trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/mock/MockLeafPage.java 2012-04-25 04:28:28 UTC (rev 3030)
+++ trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/mock/MockLeafPage.java 2012-04-25 08:29:40 UTC (rev 3031)
@@ -43,50 +43,39 @@
@Override
public EnumRecordType getRecordType() {
- // TODO Auto-generated method stub
return null;
}
@Override
public int getNumberOfPage() {
- // TODO Auto-generated method stub
return 0;
}
@Override
public int getByteSize() {
- // TODO Auto-generated method stub
return 0;
}
@Override
public void updateByteSize() {
- // TODO Auto-generated method stub
-
}
@Override
public IPageRecord getPageRecord() throws HeapException {
- // TODO Auto-generated method stub
return null;
}
@Override
public void setPageRecord(IPageRecord pageRecord) throws HeapException {
- // TODO Auto-generated method stub
-
}
@Override
public void setParentPage(IPageRecordable parentPage, int inParentIndex)
throws HeapException {
- // TODO Auto-generated method stub
-
}
@Override
public IPageRecordable getParentPage() throws HeapException {
- // TODO Auto-generated method stub
return null;
}
@@ -101,14 +90,10 @@
@Override
public void setValueIsChangedValueToSave() throws HeapException {
- // TODO Auto-generated method stub
-
}
@Override
public void setValueIsNotChanged() {
- // TODO Auto-generated method stub
-
}
public void setLastKey(final DataRecordIdentifier lastKey) {
Modified: trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/mock/MockNonTerminalPage.java
===================================================================
--- trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/mock/MockNonTerminalPage.java 2012-04-25 04:28:28 UTC (rev 3030)
+++ trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/mock/MockNonTerminalPage.java 2012-04-25 08:29:40 UTC (rev 3031)
@@ -27,6 +27,7 @@
import net.sf.joafip.btreeplus.entity.INonTerminalPage;
import net.sf.joafip.btreeplus.entity.IPageRecord;
import net.sf.joafip.btreeplus.entity.IPageRecordable;
+import net.sf.joafip.kvstore.record.entity.DataRecordIdentifier;
import net.sf.joafip.kvstore.service.HeapException;
/**
@@ -118,4 +119,21 @@
return positionInFile;
}
+ @Override
+ public int getNumberOfKeyEntries() {
+ // TODO Auto-generated method stub
+ return 0;
+ }
+
+ @Override
+ public long getPagePointer(int index) {
+ // TODO Auto-generated method stub
+ return 0;
+ }
+
+ @Override
+ public DataRecordIdentifier getKey(int index) {
+ // TODO Auto-generated method stub
+ return null;
+ }
}
Modified: trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/mock/MockPageRecordable.java
===================================================================
--- trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/mock/MockPageRecordable.java 2012-04-25 04:28:28 UTC (rev 3030)
+++ trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/mock/MockPageRecordable.java 2012-04-25 08:29:40 UTC (rev 3031)
@@ -37,69 +37,52 @@
@Override
public void setValueIsChangedValueToSave() throws HeapException {
- // TODO Auto-generated method stub
-
}
@Override
public void setValueIsNotChanged() {
- // TODO Auto-generated method stub
-
}
@Override
public EnumRecordType getRecordType() {
- // TODO Auto-generated method stub
return null;
}
@Override
public int getNumberOfPage() {
- // TODO Auto-generated method stub
return 0;
}
@Override
public int getByteSize() {
- // TODO Auto-generated method stub
return 0;
}
@Override
public void updateByteSize() {
- // TODO Auto-generated method stub
-
}
@Override
public IPageRecord getPageRecord() throws HeapException {
- // TODO Auto-generated method stub
return null;
}
@Override
public void setPageRecord(IPageRecord pageRecord) throws HeapException {
- // TODO Auto-generated method stub
-
}
@Override
public void setParentPage(IPageRecordable parentPage, int inParentIndex)
throws HeapException {
- // TODO Auto-generated method stub
-
}
@Override
public IPageRecordable getParentPage() throws HeapException {
- // TODO Auto-generated method stub
return null;
}
@Override
public int getInParentIndex() throws HeapException {
- // TODO Auto-generated method stub
return 0;
}
-
}
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
|
From: <luc...@us...> - 2012-04-26 02:39:16
|
Revision: 3032
http://joafip.svn.sourceforge.net/joafip/?rev=3032&view=rev
Author: luc_peuvrier
Date: 2012-04-26 02:39:10 +0000 (Thu, 26 Apr 2012)
Log Message:
-----------
WIP btree plus, tests in progress. DataBlockPage and DataBlock tests ok
Modified Paths:
--------------
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/AbstractElement.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/DataBlock.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/DataBlockPage.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/IDataBlock.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/LeafPage.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/NonTerminalPage.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusDataManager.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgr.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/LeafPageTest.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/NonTerminalPageTest.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/mock/MockDataBlock.java
Added Paths:
-----------
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/DataBlockPageTest.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/mock/MockPageRecord.java
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
|
From: <luc...@us...> - 2012-04-26 02:39:17
|
Revision: 3032
http://joafip.svn.sourceforge.net/joafip/?rev=3032&view=rev
Author: luc_peuvrier
Date: 2012-04-26 02:39:10 +0000 (Thu, 26 Apr 2012)
Log Message:
-----------
WIP btree plus, tests in progress. DataBlockPage and DataBlock tests ok
Modified Paths:
--------------
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/AbstractElement.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/DataBlock.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/DataBlockPage.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/IDataBlock.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/LeafPage.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/NonTerminalPage.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusDataManager.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgr.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/LeafPageTest.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/NonTerminalPageTest.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/mock/MockDataBlock.java
Added Paths:
-----------
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/DataBlockPageTest.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/mock/MockPageRecord.java
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/AbstractElement.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/AbstractElement.java 2012-04-25 08:29:40 UTC (rev 3031)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/AbstractElement.java 2012-04-26 02:39:10 UTC (rev 3032)
@@ -35,7 +35,7 @@
private IPageRecord pageRecord;
- public void setPageRecord(IPageRecord pageRecord) {
+ public void setPageRecord(final IPageRecord pageRecord) {
this.pageRecord = pageRecord;
}
@@ -46,15 +46,21 @@
@Override
public void setValueIsChangedValueToSave() throws HeapException {
- pageRecord.setValueIsChangedValueToSave();
+ if (pageRecord != null) {
+ pageRecord.setValueIsChangedValueToSave();
+ }
}
@Override
public void setValueIsNotChanged() {
- pageRecord.setValueIsNotChanged();
+ if (pageRecord != null) {
+ pageRecord.setValueIsNotChanged();
+ }
}
public long getPositionInFile() {
+ // ASSERTX
+ assert pageRecord != null;
return pageRecord.getPositionInFile();
}
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/DataBlock.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/DataBlock.java 2012-04-25 08:29:40 UTC (rev 3031)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/DataBlock.java 2012-04-26 02:39:10 UTC (rev 3032)
@@ -136,13 +136,13 @@
/**/((((long) data[4]) & 0xff) << 24) |
/**/((((long) data[5]) & 0xff) << 16) |
/**/((((long) data[6]) & 0xff) << 8) |
- /**/(((long) data[0]) & 0xff);
+ /**/(((long) data[7]) & 0xff);
}
@Override
- public long getPosition() {
+ public long getPositionInFile() {
if (position == -1) {
- position = dataBlockPage.position(indexInDataBlockPage);
+ position = dataBlockPage.getPositionInFile(indexInDataBlockPage);
}
return position;
}
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/DataBlockPage.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/DataBlockPage.java 2012-04-25 08:29:40 UTC (rev 3031)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/DataBlockPage.java 2012-04-26 02:39:10 UTC (rev 3032)
@@ -32,10 +32,9 @@
*/
public class DataBlockPage extends AbstractElement {
- private static final int FIX_VALUE_SIZE =
+ public static final int HEAD_SIZE =
/**/1/* byte size for record type */+
- /**/1/* byte size for bits */+
- /**/4/* int size for crc32 */;
+ /**/1/* byte size for bits */;
private byte bits;
@@ -45,33 +44,41 @@
private final IDataBlock[] dataBlocks;
+ private final int numberOfBlock;
+
+ public static byte bitsForLength(int length) throws HeapException {
+ for (byte bits = PageConstant.MIN_DATA_BLOCK_BITS; bits <= PageConstant.MAX_DATA_BLOCK_BITS; bits++) {
+ if (length < (1 << bits)) {
+ return bits;
+ }
+ }
+ throw new HeapException("length " + length + " to big for "
+ + PageConstant.MAX_DATA_BLOCK_BITS + " bits storage");
+ }
+
public DataBlockPage(final byte bits) {
super();
this.bits = bits;
dataBlockDataSize = 1 << bits;
- // the less numberOfPageValue which for
- // numberOfPage * PAGE_SIZE >= FIX_VALUE_SIZE + numberOfBlock *
- // dataBlockDataSize
- // numberOfBlock=1 if dataBlockDataSize > PAGE_SIZE - FIX_VALUE_SIZE
- //
- final int numberOfBlock;
- if (dataBlockDataSize > PageConstant.PAGE_SIZE - FIX_VALUE_SIZE) {
+ if (dataBlockDataSize > PageConstant.PAGE_SIZE - HEAD_SIZE - 4/* crc32 */) {
// one data block on one or more pages
numberOfBlock = 1;
- final int totalSize = FIX_VALUE_SIZE
- + /* numberOfBlock* */dataBlockDataSize;
+ final int totalSize = HEAD_SIZE + dataBlockDataSize + 4/* crc32 */;
final int n = totalSize >> PageConstant.PAGE_BITS;
if ((totalSize & PageConstant.IN_PAGE_POSITION_MASK) == 0) {
numberOfPage = n;
} else {
numberOfPage = n + 1;
}
+ // FIXMELUC ____________waste space, see below
+ // dataBlockDataSize=(numberOfPage<<PageConstant.PAGE_BITS)-
+ // HEAD_SIZE - 4/* crc32 */
} else {
// more than one block in one page
numberOfPage = 1;
// numberOfBlock = ((int)PageConstant.PAGE_SIZE - FIX_VALUE_SIZE)
// / dataBlockDataSize;
- numberOfBlock = ((int) PageConstant.PAGE_SIZE - FIX_VALUE_SIZE) >> bits;
+ numberOfBlock = ((int) PageConstant.PAGE_SIZE - HEAD_SIZE - 4/* crc32 */) >> bits;
}
final int minSize = bits == PageConstant.MIN_DATA_BLOCK_BITS ? 0
: ((1 << (bits - 1)) + 1);
@@ -105,30 +112,36 @@
@Override
public int getByteSize() {
return numberOfPage * (int) PageConstant.PAGE_SIZE;
+ // FIXMELUC _____________use <<
+ // return numberOfPage <<PageConstant.PAGE_BITS
}
+ public int getNumberOfBlock() {
+ return numberOfBlock;
+ }
+
public IDataBlock[] getDataBlocks() {
return dataBlocks;
}
public IDataBlock getDataBlock(final long dataBlockPosition) {
// >> bits as divide by data block size
- final int index = ((int) (dataBlockPosition - getPositionInFile()) - FIX_VALUE_SIZE) >> bits;
+ final int index = ((int) (dataBlockPosition - getPositionInFile()) - HEAD_SIZE) >> bits;
return dataBlocks[index];
}
- public long position(final int index) {
- return getPositionInFile() + FIX_VALUE_SIZE + (index << bits);
+ public long getPositionInFile(final int index) {
+ return getPositionInFile() + HEAD_SIZE + (index << bits);
}
public void setAllFree() throws HeapException {
- long nextPosition = getPositionInFile() + FIX_VALUE_SIZE
- + dataBlockDataSize;
+ long nextPosition = getPositionInFile() + HEAD_SIZE + dataBlockDataSize;
for (int index = 0; index < dataBlocks.length - 1; index++) {
dataBlocks[index].setNextFreeDataBlockPosition(nextPosition);
nextPosition += dataBlockDataSize;
}
dataBlocks[dataBlocks.length - 1].setNextFreeDataBlockPosition(-1L);
+ setValueIsChangedValueToSave();
}
@Override
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/IDataBlock.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/IDataBlock.java 2012-04-25 08:29:40 UTC (rev 3031)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/IDataBlock.java 2012-04-26 02:39:10 UTC (rev 3032)
@@ -32,7 +32,7 @@
*/
public interface IDataBlock extends IStateStored {
- long getPosition();
+ long getPositionInFile();
void setData(byte[] data) throws HeapException;
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/LeafPage.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/LeafPage.java 2012-04-25 08:29:40 UTC (rev 3031)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/LeafPage.java 2012-04-26 02:39:10 UTC (rev 3032)
@@ -114,15 +114,17 @@
return next;
}
- public void setNext(final long next) {
+ public void setNext(final long next) throws HeapException {
this.next = next;
+ setValueIsChangedValueToSave();
}
public void setEntry(final int index, final long pagePointer,
- final DataRecordIdentifier key) {
+ final DataRecordIdentifier key) throws HeapException {
dataBlockPosition[index] = pagePointer;
keys[index] = key;
byteSize = 0;// unknown size because key size change
+ setValueIsChangedValueToSave();
}
@Override
@@ -169,7 +171,8 @@
public void setDataBlock(final int index, final IDataBlock dataBlock)
throws HeapException {
- dataBlockPosition[index] = dataBlock.getPosition();
+ dataBlockPosition[index] = dataBlock.getPositionInFile();
+ setValueIsChangedValueToSave();
}
/**
@@ -197,7 +200,8 @@
insertBeforeIndex);
System.arraycopy(keys, 0, newKeys, 0, insertBeforeIndex);
}
- newDataBlockPosition[insertBeforeIndex] = dataBlock.getPosition();
+ newDataBlockPosition[insertBeforeIndex] = dataBlock
+ .getPositionInFile();
newKeys[insertBeforeIndex] = dataRecordIdentifier;
if (afterLength != 0) {
System.arraycopy(dataBlockPosition, insertBeforeIndex,
@@ -212,6 +216,7 @@
// ASSERTX
assert byteSize == computeByteSize() : byteSize + " for "
+ computeByteSize() + " computed";
+ setValueIsChangedValueToSave();
}
return canAdd;
}
@@ -235,6 +240,7 @@
final LeafPage newLeafPage = new LeafPage(
newLeafPageNumberOfKeyEntries, newLeafPageDataBlockPosition,
newLeafPageKeys);
+ newLeafPage.setParentPage(getParentPage(), getInParentIndex() + 1);
dataBlockPosition = newDataBlockPosition;
keys = newKeys;
numberOfKeyEntries = newNumberOfKeyEntries;
@@ -248,6 +254,7 @@
throw new HeapException("failed add in splitted leaf page");
}
}
+ setValueIsChangedValueToSave();
return newLeafPage;
}
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/NonTerminalPage.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/NonTerminalPage.java 2012-04-25 08:29:40 UTC (rev 3031)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/NonTerminalPage.java 2012-04-26 02:39:10 UTC (rev 3032)
@@ -100,11 +100,12 @@
}
public void setEntry(final int index, final long pagePointer,
- final DataRecordIdentifier key) {
+ final DataRecordIdentifier key) throws HeapException {
pagePositions[index] = pagePointer;
if (key != null) {
keys[index] = key;
}
+ setValueIsChangedValueToSave();
}
@Override
@@ -197,6 +198,7 @@
byteSize += entrySize;
// ASSERTX
assert byteSize == computeByteSize();
+ setValueIsChangedValueToSave();
return byteSize < PageConstant.PAGE_SIZE;
}
@@ -238,10 +240,11 @@
byteSize += entrySize;
// ASSERTX
assert byteSize == computeByteSize();
+ setValueIsChangedValueToSave();
return byteSize < PageConstant.PAGE_SIZE;
}
- public INonTerminalPage split() {
+ public INonTerminalPage split() throws HeapException {
final int splitIndex = numberOfKeyEntries / 2;
middleKey = keys[splitIndex];
final int newNumberOfKeyEntries = splitIndex;
@@ -262,6 +265,7 @@
pagePositions = newPagePosition;
numberOfKeyEntries = newNumberOfKeyEntries;
updateByteSize();
+ setValueIsChangedValueToSave();
return nonTerminalPage;
}
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusDataManager.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusDataManager.java 2012-04-25 08:29:40 UTC (rev 3031)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusDataManager.java 2012-04-26 02:39:10 UTC (rev 3032)
@@ -255,6 +255,7 @@
LeafPage newLeafPage = leafPage.split(dataRecordIdentifier,
dataBlock);
btreePlusElementMgr.appendPageRecordable(newLeafPage);
+ newLeafPage.setValueIsChangedValueToSave();
leafPage.setNext(newLeafPage.getPositionInFile());
NonTerminalPage nonTerminalPage = (NonTerminalPage) leafPage
@@ -269,6 +270,8 @@
do {
btreePlusElementMgr
.appendPageRecordable(newNonTerminalPage);
+ newNonTerminalPage
+ .setValueIsChangedValueToSave();
DataRecordIdentifier middleKey = nonTerminalPage
.getAndClearMiddleKey();
NonTerminalPage parent = (NonTerminalPage) nonTerminalPage
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgr.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgr.java 2012-04-25 08:29:40 UTC (rev 3031)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgr.java 2012-04-26 02:39:10 UTC (rev 3032)
@@ -262,7 +262,7 @@
}
public IDataBlock createDataBlock(final byte[] data) throws HeapException {
- final byte bits = bitsForLength(data.length);
+ final byte bits = DataBlockPage.bitsForLength(data.length);
final long freeDataBlockPosition = header
.getFreeDataBlockPosition(bits);
final IDataBlock dataBlock;
@@ -286,20 +286,10 @@
final long freeDataBlockPosition = header
.getFreeDataBlockPosition(bits);
dataBlock.setNextFreeDataBlockPosition(freeDataBlockPosition);
- final long position = dataBlock.getPosition();
+ final long position = dataBlock.getPositionInFile();
header.setFreeDataBlockPosition(bits, position);
}
- private byte bitsForLength(final int length) throws HeapException {
- for (byte bits = PageConstant.MIN_DATA_BLOCK_BITS; bits <= PageConstant.MAX_DATA_BLOCK_BITS; bits++) {
- if (length < (1 << bits)) {
- return bits;
- }
- }
- throw new HeapException("length " + length + " to big for "
- + PageConstant.MAX_DATA_BLOCK_BITS + " bits storage");
- }
-
public void appendPageRecordable(IPageRecordable pageRecordable)
throws HeapException {
long pageNumber = header.getFileSizeAsNumberOfPage() + 1;
Added: trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/DataBlockPageTest.java
===================================================================
--- trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/DataBlockPageTest.java (rev 0)
+++ trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/DataBlockPageTest.java 2012-04-26 02:39:10 UTC (rev 3032)
@@ -0,0 +1,109 @@
+/*
+ * Copyright 2012 Luc Peuvrier
+ * All rights reserved.
+ *
+ * This file is a part of JOAFIP.
+ *
+ * JOAFIP is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License.
+ *
+ * Licensed under the GNU LESSER GENERAL PUBLIC LICENSE
+ * Licensed under the LGPL License, Version 3, 29 June 2007 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.gnu.org/licenses/lgpl.html
+ *
+ * JOAFIP is distributed in the hope that it will be useful, but
+ * 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 net.sf.joafip.btreeplus.entity;
+
+import net.sf.joafip.AbstractJoafipCommonTestCase;
+import net.sf.joafip.NoStorableAccess;
+import net.sf.joafip.NotStorableClass;
+import net.sf.joafip.TestException;
+import net.sf.joafip.btreeplus.entity.mock.MockPageRecord;
+import net.sf.joafip.kvstore.service.HeapException;
+
+/**
+ *
+ * @author luc peuvrier
+ *
+ */
+@NotStorableClass
+@NoStorableAccess
+public class DataBlockPageTest extends AbstractJoafipCommonTestCase {
+
+ public DataBlockPageTest() throws TestException {
+ super();
+ }
+
+ public DataBlockPageTest(final String name) throws TestException {
+ super(name);
+ }
+
+ public void testCreation() throws HeapException {
+ for (byte bits = PageConstant.MIN_DATA_BLOCK_BITS; bits < PageConstant.MAX_DATA_BLOCK_BITS; bits++) {
+ checkCreationState(bits);
+ }
+ }
+
+ private void checkCreationState(final byte bits) throws HeapException {
+ final DataBlockPage dataBlockPage = new DataBlockPage(bits);
+ final MockPageRecord pageRecord = new MockPageRecord();
+ pageRecord.setPositionInFile(1545);
+ dataBlockPage.setPageRecord(pageRecord);
+
+ final int numberOfBlock = dataBlockPage.getNumberOfBlock();
+ final int blockByteSize = 1 << bits;
+ final long dataAreaSize = PageConstant.PAGE_SIZE
+ - DataBlockPage.HEAD_SIZE;
+ final int numberOfPage = (int) ((blockByteSize <= dataAreaSize) ? 1
+ : ((blockByteSize + DataBlockPage.HEAD_SIZE)
+ / PageConstant.PAGE_SIZE + (((blockByteSize + DataBlockPage.HEAD_SIZE)
+ % PageConstant.PAGE_SIZE == 0) ? 0 : 1)));
+
+ final int dataBlockPageByteSize = (int) (numberOfPage * PageConstant.PAGE_SIZE);
+
+ assertEquals("bad record type", EnumRecordType.DATA_BLOCK,
+ dataBlockPage.getRecordType());
+ assertEquals("bad number of bits", bits, dataBlockPage.getBits());
+ assertEquals("bad position in file", 1545,
+ dataBlockPage.getPositionInFile());
+ assertEquals("bad number of page (bits" + bits + ")", numberOfPage,
+ dataBlockPage.getNumberOfPage());
+ assertEquals("bad byte size", dataBlockPageByteSize,
+ dataBlockPage.getByteSize());
+ dataBlockPage.setAllFree();
+ IDataBlock[] dataBlocks = dataBlockPage.getDataBlocks();
+ assertEquals("number of block missmatch", numberOfBlock,
+ dataBlocks.length);
+ int index = 0;
+ long expectedCurrentPositionInFile = dataBlockPage.getPositionInFile()
+ + DataBlockPage.HEAD_SIZE;
+ long nextFreeDataBlockPosition = dataBlockPage.getPositionInFile()
+ + DataBlockPage.HEAD_SIZE;
+ for (IDataBlock dataBlock : dataBlocks) {
+ assertEquals("bad number of bits", bits, dataBlock.getBits());
+ final long positionInFile = dataBlock.getPositionInFile();
+ assertEquals("bad position in file", expectedCurrentPositionInFile,
+ positionInFile);
+ assertSame("bad block in block page", dataBlock,
+ dataBlockPage.getDataBlock(positionInFile));
+ assertEquals("data block #" + index + " (bits " + bits
+ + ") bad free link", positionInFile,
+ nextFreeDataBlockPosition);
+ nextFreeDataBlockPosition = dataBlock
+ .getNextFreeDataBlockPosition();
+ index++;
+ expectedCurrentPositionInFile += blockByteSize;
+ }
+ assertEquals("data block #" + index + " (bits " + bits
+ + ") bad free link", -1L, nextFreeDataBlockPosition);
+ }
+}
Modified: trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/LeafPageTest.java
===================================================================
--- trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/LeafPageTest.java 2012-04-25 08:29:40 UTC (rev 3031)
+++ trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/LeafPageTest.java 2012-04-26 02:39:10 UTC (rev 3032)
@@ -24,9 +24,11 @@
package net.sf.joafip.btreeplus.entity;
import net.sf.joafip.AbstractJoafipCommonTestCase;
+import net.sf.joafip.NoStorableAccess;
import net.sf.joafip.NotStorableClass;
import net.sf.joafip.TestException;
import net.sf.joafip.btreeplus.entity.mock.MockDataBlock;
+import net.sf.joafip.btreeplus.entity.mock.MockPageRecord;
import net.sf.joafip.btreeplus.entity.mock.MockPageRecordable;
import net.sf.joafip.kvstore.record.entity.DataRecordIdentifier;
import net.sf.joafip.kvstore.service.HeapException;
@@ -37,8 +39,11 @@
*
*/
@NotStorableClass
+@NoStorableAccess
public class LeafPageTest extends AbstractJoafipCommonTestCase {
+ private final static IPageRecord PAGE_RECORD = new MockPageRecord();
+
public LeafPageTest() throws TestException {
super();
}
@@ -49,6 +54,7 @@
public void testCreation() {
LeafPage leafPage = new LeafPage();
+ leafPage.setPageRecord(PAGE_RECORD);
assertEquals("must be empty", 0, leafPage.getNumberOfKeyEntries());
assertEquals("must be one page", 1, leafPage.getNumberOfPage());
assertEquals("bad record type", EnumRecordType.LEAF_PAGE,
@@ -58,6 +64,7 @@
public void testAdd() throws HeapException {
LeafPage leafPage = new LeafPage();
+ leafPage.setPageRecord(PAGE_RECORD);
addToLeafPage(leafPage, 1000/* position */, 10/* key value */, 10, 1);
addToLeafPage(leafPage, 2000/* position */, 5/* key value */, 10, 2);
addToLeafPage(leafPage, 3000/* position */, 15/* key value */, 15, 3);
@@ -101,7 +108,7 @@
numberOfKeyEntries, leafPage.getNumberOfKeyEntries());
assertEquals("bad byte size", byteSize(numberOfKeyEntries),
leafPage.getByteSize());
- assertEquals("must find", dataBlock.getPosition(),
+ assertEquals("must find", dataBlock.getPositionInFile(),
leafPage.getDataBlockPosition(dataRecordIdentifier));
assertEquals("must not find", -1L,
leafPage.getDataBlockPosition(new DataRecordIdentifier(0)));
@@ -111,6 +118,7 @@
public void testSetDataBlock() throws HeapException {
final LeafPage leafPage = new LeafPage(1);
+ leafPage.setPageRecord(PAGE_RECORD);
final MockDataBlock dataBlock = new MockDataBlock();
final long position = 1000;
dataBlock.setPosition(position);
@@ -120,8 +128,9 @@
leafPage.getBlockPointer(index));
}
- public void testSetEntry() {
+ public void testSetEntry() throws HeapException {
final LeafPage leafPage = new LeafPage(1);
+ leafPage.setPageRecord(PAGE_RECORD);
final int index = 0;
final long pagePointer = 2000;
final int keyValue = 10;
@@ -135,7 +144,8 @@
public void testSetParentPage() throws HeapException {
final LeafPage leafPage = new LeafPage();
- IPageRecordable parentPage = new MockPageRecordable();
+ leafPage.setPageRecord(PAGE_RECORD);
+ final IPageRecordable parentPage = new MockPageRecordable();
final int inParentIndex = 5;
leafPage.setParentPage(parentPage, inParentIndex);
assertEquals("bad parent page", parentPage, leafPage.getParentPage());
@@ -143,8 +153,9 @@
leafPage.getInParentIndex());
}
- public void testSetNext() {
+ public void testSetNext() throws HeapException {
final LeafPage leafPage = new LeafPage();
+ leafPage.setPageRecord(PAGE_RECORD);
final long next = 5000;
leafPage.setNext(next);
assertEquals("bad next value", next, leafPage.getNext());
@@ -152,6 +163,7 @@
public void testSplit1() throws HeapException {
final LeafPage leafPage = new LeafPage();
+ leafPage.setPageRecord(PAGE_RECORD);
final int maxNumberOfEntries = maxNumberOfEntries();
int count = 0;
while (leafPage.getNumberOfKeyEntries() != maxNumberOfEntries) {
@@ -170,6 +182,7 @@
public void testSplit2() throws HeapException {
final LeafPage leafPage = new LeafPage();
+ leafPage.setPageRecord(PAGE_RECORD);
final int maxNumberOfEntries = maxNumberOfEntries();
int count = 1;
while (leafPage.getNumberOfKeyEntries() != maxNumberOfEntries) {
Modified: trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/NonTerminalPageTest.java
===================================================================
--- trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/NonTerminalPageTest.java 2012-04-25 08:29:40 UTC (rev 3031)
+++ trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/NonTerminalPageTest.java 2012-04-26 02:39:10 UTC (rev 3032)
@@ -24,11 +24,12 @@
package net.sf.joafip.btreeplus.entity;
import net.sf.joafip.AbstractJoafipCommonTestCase;
+import net.sf.joafip.NoStorableAccess;
import net.sf.joafip.NotStorableClass;
-import net.sf.joafip.StorableAccess;
import net.sf.joafip.TestException;
import net.sf.joafip.btreeplus.entity.mock.MockLeafPage;
import net.sf.joafip.btreeplus.entity.mock.MockNonTerminalPage;
+import net.sf.joafip.btreeplus.entity.mock.MockPageRecord;
import net.sf.joafip.kvstore.record.entity.DataRecordIdentifier;
import net.sf.joafip.kvstore.service.HeapException;
@@ -38,9 +39,11 @@
*
*/
@NotStorableClass
-@StorableAccess
+@NoStorableAccess
public class NonTerminalPageTest extends AbstractJoafipCommonTestCase {
+ private final static IPageRecord PAGE_RECORD = new MockPageRecord();
+
public NonTerminalPageTest() throws TestException {
super();
}
@@ -63,10 +66,11 @@
public void testAddLeafPage() throws HeapException {
// A 10 B
final NonTerminalPage nonTerminalPage = new NonTerminalPage(1);
- final MockLeafPage leafPageA = new MockLeafPage();
+ nonTerminalPage.setPageRecord(PAGE_RECORD);
+ final MockLeafPage leafPageA = newMockLeafPage();
final long pageAPositionInFile = 1000;
leafPageA.setPositionInFile(pageAPositionInFile);
- final MockLeafPage leafPageB = new MockLeafPage();
+ final MockLeafPage leafPageB = newMockLeafPage();
final long pageBPositionInFile = 2000;
leafPageB.setPositionInFile(pageBPositionInFile);
final DataRecordIdentifier key10 = new DataRecordIdentifier(10);
@@ -82,7 +86,7 @@
nonTerminalPage.getIndex(new DataRecordIdentifier(11)));
// A 10 B -> A 5 C 10 B
- final MockLeafPage leafPageC = new MockLeafPage();
+ final MockLeafPage leafPageC = newMockLeafPage();
final long pageCPositionInFile = 3000;
leafPageC.setPositionInFile(pageCPositionInFile);
final DataRecordIdentifier key5 = new DataRecordIdentifier(5);
@@ -101,7 +105,7 @@
nonTerminalPage.getIndex(new DataRecordIdentifier(11)));
// A 5 C 10 B -> A 5 C 10 B 15 D
- final MockLeafPage leafPageD = new MockLeafPage();
+ final MockLeafPage leafPageD = newMockLeafPage();
final long pageDPositionInFile = 4000;
leafPageD.setPositionInFile(pageDPositionInFile);
final DataRecordIdentifier key15 = new DataRecordIdentifier(15);
@@ -121,7 +125,7 @@
nonTerminalPage.getIndex(new DataRecordIdentifier(16)));
// A 5 C 10 B 15 D -> A 5 C 7 E 10 B 15 D
- final MockLeafPage leafPageE = new MockLeafPage();
+ final MockLeafPage leafPageE = newMockLeafPage();
final long pageEPositionInFile = 5000;
leafPageE.setPositionInFile(pageEPositionInFile);
final DataRecordIdentifier key7 = new DataRecordIdentifier(7);
@@ -144,7 +148,7 @@
nonTerminalPage.getIndex(new DataRecordIdentifier(16)));
// A 5 C 7 E 10 B 15 D -> A 5 C 7 E 10 B 15 D 17 F
- final MockLeafPage leafPageF = new MockLeafPage();
+ final MockLeafPage leafPageF = newMockLeafPage();
final long pageFPositionInFile = 6000;
leafPageF.setPositionInFile(pageFPositionInFile);
final DataRecordIdentifier key17 = new DataRecordIdentifier(17);
@@ -172,10 +176,11 @@
public void testAddLeafPageNeedSplit() throws HeapException {
// A 10 B
final NonTerminalPage nonTerminalPage = new NonTerminalPage(1);
- final MockLeafPage leafPageA = new MockLeafPage();
+ nonTerminalPage.setPageRecord(PAGE_RECORD);
+ final MockLeafPage leafPageA = newMockLeafPage();
final long pageAPositionInFile = 1000;
leafPageA.setPositionInFile(pageAPositionInFile);
- final MockLeafPage leafPageB = new MockLeafPage();
+ final MockLeafPage leafPageB = newMockLeafPage();
final long pageBPositionInFile = 2000;
leafPageB.setPositionInFile(pageBPositionInFile);
final DataRecordIdentifier key10 = new DataRecordIdentifier(10);
@@ -186,14 +191,14 @@
MockLeafPage leftPage = leafPageB;
final int maxNumberOfEntries = maxNumberOfEntries();
while (nonTerminalPage.getNumberOfKeyEntries() < maxNumberOfEntries) {
- final MockLeafPage rightPage = new MockLeafPage();
+ final MockLeafPage rightPage = newMockLeafPage();
leftPage.setInParentIndex(nonTerminalPage.getNumberOfKeyEntries() - 1);
leftPage.setLastKey(key10);
assertTrue("must not need split",
nonTerminalPage.add(leftPage, rightPage));
leftPage = rightPage;
}
- final MockLeafPage rightPage = new MockLeafPage();
+ final MockLeafPage rightPage = newMockLeafPage();
leftPage.setInParentIndex(nonTerminalPage.getNumberOfKeyEntries() - 1);
leftPage.setLastKey(key10);
assertFalse("must need split", nonTerminalPage.add(leftPage, rightPage));
@@ -202,10 +207,11 @@
public void testAddNonTerminalPage() throws HeapException {
// A 10 B
final NonTerminalPage nonTerminalPage = new NonTerminalPage(1);
- final MockNonTerminalPage pageA = new MockNonTerminalPage();
+ nonTerminalPage.setPageRecord(PAGE_RECORD);
+ final MockNonTerminalPage pageA = newMockNonTerminalPage();
final long pageAPositionInFile = 1000;
pageA.setPositionInFile(pageAPositionInFile);
- final MockNonTerminalPage pageB = new MockNonTerminalPage();
+ final MockNonTerminalPage pageB = newMockNonTerminalPage();
final long pageBPositionInFile = 2000;
pageB.setPositionInFile(pageBPositionInFile);
final DataRecordIdentifier key10 = new DataRecordIdentifier(10);
@@ -221,7 +227,7 @@
nonTerminalPage.getIndex(new DataRecordIdentifier(11)));
// A 10 B -> A 5 C 10 B
- final MockNonTerminalPage pageC = new MockNonTerminalPage();
+ final MockNonTerminalPage pageC = newMockNonTerminalPage();
final long pageCPositionInFile = 3000;
pageC.setPositionInFile(pageCPositionInFile);
final DataRecordIdentifier key5 = new DataRecordIdentifier(5);
@@ -239,7 +245,7 @@
// ------------
// A 5 C 10 B -> A 5 C 10 B 15 D
- final MockNonTerminalPage pageD = new MockNonTerminalPage();
+ final MockNonTerminalPage pageD = newMockNonTerminalPage();...
[truncated message content] |
|
From: <luc...@us...> - 2012-04-28 07:54:08
|
Revision: 3035
http://joafip.svn.sourceforge.net/joafip/?rev=3035&view=rev
Author: luc_peuvrier
Date: 2012-04-28 07:54:02 +0000 (Sat, 28 Apr 2012)
Log Message:
-----------
WIP btree plus, tests in progress. BtreePlusElementMgr test in development, added data block tests
Modified Paths:
--------------
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/DataBlock.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/DataBlockPage.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/IDataBlock.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/IPageRecord.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/PageRecord.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgr.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/DataBlockPageTest.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/mock/MockDataBlock.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/mock/MockPageRecord.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgrTest.java
Added Paths:
-----------
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/TestDataBlockContext.java
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
|
From: <luc...@us...> - 2012-04-28 07:54:09
|
Revision: 3035
http://joafip.svn.sourceforge.net/joafip/?rev=3035&view=rev
Author: luc_peuvrier
Date: 2012-04-28 07:54:02 +0000 (Sat, 28 Apr 2012)
Log Message:
-----------
WIP btree plus, tests in progress. BtreePlusElementMgr test in development, added data block tests
Modified Paths:
--------------
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/DataBlock.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/DataBlockPage.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/IDataBlock.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/IPageRecord.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/PageRecord.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgr.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/DataBlockPageTest.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/mock/MockDataBlock.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/mock/MockPageRecord.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgrTest.java
Added Paths:
-----------
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/TestDataBlockContext.java
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/DataBlock.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/DataBlock.java 2012-04-27 20:29:42 UTC (rev 3034)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/DataBlock.java 2012-04-28 07:54:02 UTC (rev 3035)
@@ -115,7 +115,7 @@
}
@Override
- public void setNextFreeDataBlockPosition(
+ public void setNextFreeDataBlockPositionOfFree(
final long nextFreeDataBlockPosition) throws HeapException {
data[0] = (byte) (nextFreeDataBlockPosition >> 56);
data[1] = (byte) (nextFreeDataBlockPosition >> 48);
@@ -129,7 +129,7 @@
}
@Override
- public long getNextFreeDataBlockPosition() {
+ public long getNextFreeDataBlockPositionOfFree() {
return
/**/((((long) data[0]) & 0xff) << 56) |
/**/((((long) data[1]) & 0xff) << 48) |
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/DataBlockPage.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/DataBlockPage.java 2012-04-27 20:29:42 UTC (rev 3034)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/DataBlockPage.java 2012-04-28 07:54:02 UTC (rev 3035)
@@ -139,10 +139,11 @@
public void setAllFree() throws HeapException {
long nextPosition = getPositionInFile() + HEAD_SIZE + dataBlockDataSize;
for (int index = 0; index < dataBlocks.length - 1; index++) {
- dataBlocks[index].setNextFreeDataBlockPosition(nextPosition);
+ dataBlocks[index].setNextFreeDataBlockPositionOfFree(nextPosition);
nextPosition += dataBlockDataSize;
}
- dataBlocks[dataBlocks.length - 1].setNextFreeDataBlockPosition(-1L);
+ dataBlocks[dataBlocks.length - 1]
+ .setNextFreeDataBlockPositionOfFree(-1L);
setValueIsChangedValueToSave();
}
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/IDataBlock.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/IDataBlock.java 2012-04-27 20:29:42 UTC (rev 3034)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/IDataBlock.java 2012-04-28 07:54:02 UTC (rev 3035)
@@ -38,10 +38,22 @@
byte[] getData();
- void setNextFreeDataBlockPosition(long nextFreeDataBlockPosition)
+ /**
+ * the next free data block position is wrote on data, must be call only if
+ * this is a free data block
+ *
+ * @param nextFreeDataBlockPosition
+ * @throws HeapException
+ */
+ void setNextFreeDataBlockPositionOfFree(long nextFreeDataBlockPosition)
throws HeapException;
- long getNextFreeDataBlockPosition();
+ /**
+ * make sense to be call only if this is a free data block
+ *
+ * @return next free data block position
+ */
+ long getNextFreeDataBlockPositionOfFree();
byte[] getDataHolder();
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/IPageRecord.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/IPageRecord.java 2012-04-27 20:29:42 UTC (rev 3034)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/IPageRecord.java 2012-04-28 07:54:02 UTC (rev 3035)
@@ -57,4 +57,6 @@
@Override
boolean isValueChangedToSave();
+ int getNumberOfPage();
+
}
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/PageRecord.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/PageRecord.java 2012-04-27 20:29:42 UTC (rev 3034)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/PageRecord.java 2012-04-28 07:54:02 UTC (rev 3035)
@@ -67,6 +67,11 @@
}
@Override
+ public int getNumberOfPage() {
+ return pageRecordable.getNumberOfPage();
+ }
+
+ @Override
public long getPreviousRecordPositionInFile() throws HeapException {
return -1L;
}
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgr.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgr.java 2012-04-27 20:29:42 UTC (rev 3034)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgr.java 2012-04-28 07:54:02 UTC (rev 3035)
@@ -224,9 +224,11 @@
*/
public IDataBlock getDataBlock(final long dataBlockPosition)
throws HeapException {
- DataBlockPage dataBlockPage = (DataBlockPage) heapElementManager
+ final PageRecord pageRecord = (PageRecord) heapElementManager
.readHeapFileDataRecord(dataBlockPosition
& PageConstant.START_PAGE_POSITION_MASK);
+ final DataBlockPage dataBlockPage = (DataBlockPage) pageRecord
+ .getPageRecordable();
final IDataBlock datablock = dataBlockPage
.getDataBlock(dataBlockPosition);
return datablock;
@@ -278,14 +280,14 @@
final IDataBlock dataBlock;
if (freeDataBlockPosition == -1L) {
DataBlockPage dataBlockPage = new DataBlockPage(bits);
- appendPageRecordable(dataBlockPage);
+ internalAppendPageRecordable(dataBlockPage);
dataBlockPage.setAllFree();
dataBlock = dataBlockPage.getDataBlocks()[0];
} else {
dataBlock = getDataBlock(freeDataBlockPosition);
}
final long nextFreeDataBlockPosition = dataBlock
- .getNextFreeDataBlockPosition();
+ .getNextFreeDataBlockPositionOfFree();
header.setFreeDataBlockPosition(bits, nextFreeDataBlockPosition);
dataBlock.setData(data);
return dataBlock;
@@ -295,7 +297,7 @@
final byte bits = dataBlock.getBits();
final long freeDataBlockPosition = header
.getFreeDataBlockPosition(bits);
- dataBlock.setNextFreeDataBlockPosition(freeDataBlockPosition);
+ dataBlock.setNextFreeDataBlockPositionOfFree(freeDataBlockPosition);
final long position = dataBlock.getPositionInFile();
header.setFreeDataBlockPosition(bits, position);
}
@@ -304,10 +306,16 @@
throws HeapException {
// ASSERTX
assert notInternalyManagedPage(pageRecordable);
+ internalAppendPageRecordable(pageRecordable);
+ }
+
+ private void internalAppendPageRecordable(
+ final IPageRecordable pageRecordable) throws HeapException {
long pageNumber = header.getFileSizeAsNumberOfPage();
- header.setFileSizeAsNumberOfPage(pageNumber + 1);
final IPageRecord pageRecord = new PageRecord(fileForStorable,
pageRecordable, pageNumber);
+ header.setFileSizeAsNumberOfPage(pageNumber
+ + pageRecord.getNumberOfPage());
pageRecordable.setPageRecord(pageRecord);
heapElementManager.appendHeapFileRecord(pageRecord);
}
Modified: trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/DataBlockPageTest.java
===================================================================
--- trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/DataBlockPageTest.java 2012-04-27 20:29:42 UTC (rev 3034)
+++ trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/DataBlockPageTest.java 2012-04-28 07:54:02 UTC (rev 3035)
@@ -99,7 +99,7 @@
+ ") bad free link", positionInFile,
nextFreeDataBlockPosition);
nextFreeDataBlockPosition = dataBlock
- .getNextFreeDataBlockPosition();
+ .getNextFreeDataBlockPositionOfFree();
index++;
expectedCurrentPositionInFile += blockByteSize;
}
Added: trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/TestDataBlockContext.java
===================================================================
--- trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/TestDataBlockContext.java (rev 0)
+++ trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/TestDataBlockContext.java 2012-04-28 07:54:02 UTC (rev 3035)
@@ -0,0 +1,113 @@
+/*
+ * Copyright 2012 Luc Peuvrier
+ * All rights reserved.
+ *
+ * This file is a part of JOAFIP.
+ *
+ * JOAFIP is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License.
+ *
+ * Licensed under the GNU LESSER GENERAL PUBLIC LICENSE
+ * Licensed under the LGPL License, Version 3, 29 June 2007 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.gnu.org/licenses/lgpl.html
+ *
+ * JOAFIP is distributed in the hope that it will be useful, but
+ * 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 net.sf.joafip.btreeplus.entity;
+
+import java.util.ArrayList;
+import java.util.Deque;
+import java.util.List;
+
+import net.sf.joafip.NoStorableAccess;
+import net.sf.joafip.NotStorableClass;
+
+/**
+ *
+ * @author luc peuvrier
+ *
+ */
+@NotStorableClass
+@NoStorableAccess
+public class TestDataBlockContext {
+
+ private static class DataBlockInfo {
+
+ private final byte contentValue;
+
+ private final long position;
+
+ public DataBlockInfo(final DataBlock dataBlock, final byte contentValue) {
+ super();
+ this.contentValue = contentValue;
+ this.position = dataBlock.getPositionInFile();
+ }
+
+ public byte getContentValue() {
+ return contentValue;
+ }
+
+ public long getPosition() {
+ return position;
+ }
+ }
+
+ private final byte bits;
+
+ private final List<DataBlockInfo> dataBlockInfoList = new ArrayList<DataBlockInfo>();
+
+ private long position;
+
+ private Deque<Long> positionDeque;
+
+ public TestDataBlockContext(final byte bits) {
+ super();
+ this.bits = bits;
+ }
+
+ public byte getBits() {
+ return bits;
+ }
+
+ public long getPosition() {
+ return position;
+ }
+
+ public void setPosition(final long position) {
+ this.position = position;
+ }
+
+ public void addDataBlock(final DataBlock dataBlock, final byte contentValue) {
+ final DataBlockInfo dataBlockInfo = new DataBlockInfo(dataBlock,
+ contentValue);
+ dataBlockInfoList.add(dataBlockInfo);
+ }
+
+ public int size() {
+ return dataBlockInfoList.size();
+ }
+
+ public byte getContentValue(final int index) {
+ return dataBlockInfoList.get(index).getContentValue();
+ }
+
+ public long getPosition(final int index) {
+ return dataBlockInfoList.get(index).getPosition();
+ }
+
+ public void setPositionDeque(final Deque<Long> positionDeque) {
+ this.positionDeque = positionDeque;
+ }
+
+ public Deque<Long> getPositionDeque() {
+ return positionDeque;
+ }
+}
Modified: trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/mock/MockDataBlock.java
===================================================================
--- trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/mock/MockDataBlock.java 2012-04-27 20:29:42 UTC (rev 3034)
+++ trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/mock/MockDataBlock.java 2012-04-28 07:54:02 UTC (rev 3035)
@@ -66,12 +66,12 @@
}
@Override
- public void setNextFreeDataBlockPosition(long nextFreeDataBlockPosition)
- throws HeapException {
+ public void setNextFreeDataBlockPositionOfFree(
+ long nextFreeDataBlockPosition) throws HeapException {
}
@Override
- public long getNextFreeDataBlockPosition() {
+ public long getNextFreeDataBlockPositionOfFree() {
return 0;
}
Modified: trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/mock/MockPageRecord.java
===================================================================
--- trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/mock/MockPageRecord.java 2012-04-27 20:29:42 UTC (rev 3034)
+++ trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/mock/MockPageRecord.java 2012-04-28 07:54:02 UTC (rev 3035)
@@ -39,6 +39,11 @@
return 0;
}
+ @Override
+ public int getNumberOfPage() {
+ return 0;
+ }
+
public void setPositionInFile(final long positionInFile) {
this.positionInFile = positionInFile;
}
Modified: trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgrTest.java
===================================================================
--- trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgrTest.java 2012-04-27 20:29:42 UTC (rev 3034)
+++ trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgrTest.java 2012-04-28 07:54:02 UTC (rev 3035)
@@ -23,15 +23,25 @@
*/
package net.sf.joafip.btreeplus.service;
+import java.util.Arrays;
+import java.util.Deque;
+import java.util.Iterator;
+import java.util.LinkedList;
+
import net.sf.joafip.AbstractJoafipCommonTestCase;
import net.sf.joafip.NoStorableAccess;
import net.sf.joafip.NotStorableClass;
import net.sf.joafip.TestException;
+import net.sf.joafip.btreeplus.entity.DataBlock;
+import net.sf.joafip.btreeplus.entity.DataBlockPage;
+import net.sf.joafip.btreeplus.entity.HeaderPage;
+import net.sf.joafip.btreeplus.entity.IDataBlock;
import net.sf.joafip.btreeplus.entity.IPageRecord;
import net.sf.joafip.btreeplus.entity.IPageRecordable;
import net.sf.joafip.btreeplus.entity.LeafPage;
import net.sf.joafip.btreeplus.entity.NonTerminalPage;
import net.sf.joafip.btreeplus.entity.PageConstant;
+import net.sf.joafip.btreeplus.entity.TestDataBlockContext;
import net.sf.joafip.kvstore.record.entity.DataRecordIdentifier;
import net.sf.joafip.kvstore.record.service.mock.MockHeapElementManager;
import net.sf.joafip.kvstore.service.HeapException;
@@ -50,6 +60,7 @@
private static final String MUST_BE_STORED = "must be stored";
private static final String MUST_BE_NOT_STORED = "must be not stored";
private BtreePlusElementMgr btreePlusElementMgr;
+ private MockHeapElementManager heapElementManager;
public BtreePlusElementMgrTest() throws TestException {
super();
@@ -62,8 +73,9 @@
@Override
protected void setUp() throws Exception {
super.setUp();
- btreePlusElementMgr = new BtreePlusElementMgr(
- new MockHeapElementManager((int) (10 * PageConstant.PAGE_SIZE)));
+ heapElementManager = new MockHeapElementManager(
+ (int) (10000 * PageConstant.PAGE_SIZE));
+ btreePlusElementMgr = new BtreePlusElementMgr(heapElementManager);
btreePlusElementMgr.startService();
}
@@ -79,7 +91,8 @@
} catch (Exception exception) {
// ignore error
}
- btreePlusElementMgr = null;
+ btreePlusElementMgr = null;// NOPMD
+ heapElementManager = null;// NOPMD
super.tearDown();
}
@@ -151,11 +164,165 @@
btreePlusElementMgr.closeTransactionDiscardChange();
}
- public void testDataBlock() {
+ public void testDataBlock() throws HeapException {
+ TestDataBlockContext[] contextByBits = new TestDataBlockContext[PageConstant.NUMBER_OF_BLOCK_TYPE];
+ // add test when no free data record available, create new data record
+ // first add data
+ btreePlusElementMgr.openTransaction();
+ int index = 0;
+ long position = PageConstant.PAGE_SIZE;
+ for (byte bits = PageConstant.MIN_DATA_BLOCK_BITS; bits < PageConstant.MAX_DATA_BLOCK_BITS; bits++) {
+ TestDataBlockContext context = new TestDataBlockContext(bits);
+ contextByBits[index] = context;
+ context.setPosition(position);
+ addDataBlock(context, bits);
+ position = context.getPosition();
+ index++;
+ }
+ btreePlusElementMgr.closeTransaction();
+
+ // add test
+ // secondly check added
+ btreePlusElementMgr.openTransaction();
+ index = 0;
+ for (byte bits = PageConstant.MIN_DATA_BLOCK_BITS; bits < PageConstant.MAX_DATA_BLOCK_BITS; bits++) {
+ final TestDataBlockContext context = contextByBits[index];
+ for (int dataBlockIndex = 0; dataBlockIndex < context.size(); dataBlockIndex++) {
+ final long dataBlockPosition = context
+ .getPosition(dataBlockIndex);
+ final byte[] data = btreePlusElementMgr
+ .getData(dataBlockPosition);
+ final byte[] expectedData = createData(data.length,
+ context.getContentValue(dataBlockIndex));
+ assertTrue("bad content", Arrays.equals(expectedData, data));
+ final IDataBlock dataBlock = btreePlusElementMgr
+ .getDataBlock(dataBlockPosition);
+ assertEquals("bad data block type", bits, dataBlock.getBits());
+ }
+ index++;
+ }
+ btreePlusElementMgr.closeTransaction();
+
+ // remove test
+ btreePlusElementMgr.openTransaction();
+ index = 0;
+ for (byte bits = PageConstant.MIN_DATA_BLOCK_BITS; bits < PageConstant.MAX_DATA_BLOCK_BITS; bits++) {
+ final TestDataBlockContext context = contextByBits[index];
+ final Deque<Long> positionDeque = new LinkedList<Long>();
+ for (int dataBlockIndex = 0; dataBlockIndex < context.size(); dataBlockIndex++) {
+ final long dataBlockPosition = context
+ .getPosition(dataBlockIndex);
+ final IDataBlock dataBlock = btreePlusElementMgr
+ .getDataBlock(dataBlockPosition);
+ btreePlusElementMgr.remove(dataBlock);
+ assertEquals("header not updated", dataBlockPosition,
+ getHeapHeader().getFreeDataBlockPosition(bits));
+ positionDeque.addFirst(dataBlockPosition);
+ }
+ context.setPositionDeque(positionDeque);
+ index++;
+ }
+ btreePlusElementMgr.closeTransaction();
+
+ // check removed state
+ btreePlusElementMgr.openTransaction();
+ index = 0;
+ for (byte bits = PageConstant.MIN_DATA_BLOCK_BITS; bits < PageConstant.MAX_DATA_BLOCK_BITS; bits++) {
+ final TestDataBlockContext context = contextByBits[index];
+ final Deque<Long> positionDeque = context.getPositionDeque();
+ long expectedPosition = getHeapHeader().getFreeDataBlockPosition(
+ bits);
+ for (Long currentPosition : positionDeque) {
+ assertEquals("bad free position (bits=" + bits + ")",
+ expectedPosition, currentPosition.longValue());
+ expectedPosition = btreePlusElementMgr.getDataBlock(
+ expectedPosition).getNextFreeDataBlockPositionOfFree();
+ }
+ assertEquals("bad free position", -1, expectedPosition);
+ index++;
+ }
+ btreePlusElementMgr.closeTransaction();
+
+ // add test when free record available
+ btreePlusElementMgr.openTransaction();
+ index = 0;
+ for (byte bits = PageConstant.MIN_DATA_BLOCK_BITS; bits < PageConstant.MAX_DATA_BLOCK_BITS; bits++) {
+ final TestDataBlockContext context = contextByBits[index];
+ final Iterator<Long> iterator = context.getPositionDeque()
+ .iterator();
+ final DataBlock dataBlock = createDataBlock(bits, (byte) 0);
+ assertEquals("bad allocation", iterator.next().longValue(),
+ dataBlock.getPositionInFile());
+ assertEquals("bad new free", iterator.next().longValue(),
+ getHeapHeader().getFirstFreeBlock(bits));
+ index++;
+ }
+ btreePlusElementMgr.closeTransaction();
}
+ private void addDataBlock(final TestDataBlockContext context,
+ final byte bits) throws HeapException {
+ long position = context.getPosition();
+ byte contentValue = 0;
+ int index = 0;
+ long nextFreeDataBlockPosition;
+ DataBlock dataBlock = createDataBlock(bits, contentValue);
+ context.addDataBlock(dataBlock, contentValue);
+ DataBlockPage dataBlockPage = dataBlock.getDataBlockPage();
+ do {
+ final long dataBlockPosition = dataBlock.getPositionInFile();
+ assertEquals("data block not in expected page (bits " + bits
+ + ", contentValue " + contentValue + ")", position,
+ dataBlockPosition & PageConstant.START_PAGE_POSITION_MASK);
+ assertEquals("bad index", index,
+ dataBlock.getIndexInDataBlockPage());
+ nextFreeDataBlockPosition = getHeapHeader().getFirstFreeBlock(bits);
+ if (nextFreeDataBlockPosition != -1L) {
+ contentValue++;
+ index++;
+ dataBlock = createDataBlock(bits, contentValue);
+ assertSame("bad data block page", dataBlockPage,
+ dataBlock.getDataBlockPage());
+ }
+ } while (nextFreeDataBlockPosition != -1L);
+ final int numberOfBlockCreated = index + 1;
+ assertEquals("number of block missmatch", numberOfBlockCreated,
+ dataBlockPage.getNumberOfBlock());
+ final int numberOfPageOfBlockPage = dataBlockPage.getNumberOfPage();
+ position += numberOfPageOfBlockPage * PageConstant.PAGE_SIZE;
+
+ contentValue++;
+ for (int count = 0; count < numberOfBlockCreated; count++) {
+ dataBlock = createDataBlock(bits, contentValue);
+ context.addDataBlock(dataBlock, contentValue);
+ contentValue++;
+ }
+ position += numberOfPageOfBlockPage * PageConstant.PAGE_SIZE;
+ context.setPosition(position);
+ }
+
+ private DataBlock createDataBlock(final byte bits, final byte contentValue)
+ throws HeapException {
+ final int dataSize = (1 << bits) * 3 / 4;
+ final byte[] data = createData(dataSize, contentValue);
+ final DataBlock dataBlock = (DataBlock) btreePlusElementMgr
+ .createDataBlock(data);
+ assertEquals("bad data block type", bits, dataBlock.getBits());
+ return dataBlock;
+ }
+
+ private byte[] createData(final int dataSize, final byte contentValue) {
+ byte[] data = new byte[dataSize];
+ Arrays.fill(data, contentValue);
+ return data;
+ }
+
public void testDataRecordIdentifier() {
}
+
+ public HeaderPage getHeapHeader() throws HeapException {
+ return (HeaderPage) heapElementManager.getHeapHeader();
+ }
}
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
|
From: <luc...@us...> - 2012-04-29 04:09:21
|
Revision: 3038
http://joafip.svn.sourceforge.net/joafip/?rev=3038&view=rev
Author: luc_peuvrier
Date: 2012-04-29 04:09:15 +0000 (Sun, 29 Apr 2012)
Log Message:
-----------
WIP btree plus, tests in progress. leaf page equilibrate and non terminal page remove added, tests ok
Modified Paths:
--------------
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/DataBlock.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/DataBlockPage.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/IDataBlock.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/LeafPage.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/NonTerminalPage.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusDataManager.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgr.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/LeafPageTest.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/NonTerminalPageTest.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/mock/MockDataBlock.java
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
|
From: <luc...@us...> - 2012-04-29 04:53:56
|
Revision: 3039
http://joafip.svn.sourceforge.net/joafip/?rev=3039&view=rev
Author: luc_peuvrier
Date: 2012-04-29 04:53:50 +0000 (Sun, 29 Apr 2012)
Log Message:
-----------
WIP btree plus, tests in progress. BtreePlusElementMgr added free page management, tests ok
Modified Paths:
--------------
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/IPageRecord.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/PageRecord.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgr.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/mock/MockPageRecord.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgrTest.java
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
|
From: <luc...@us...> - 2012-04-29 04:53:56
|
Revision: 3039
http://joafip.svn.sourceforge.net/joafip/?rev=3039&view=rev
Author: luc_peuvrier
Date: 2012-04-29 04:53:50 +0000 (Sun, 29 Apr 2012)
Log Message:
-----------
WIP btree plus, tests in progress. BtreePlusElementMgr added free page management, tests ok
Modified Paths:
--------------
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/IPageRecord.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/PageRecord.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgr.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/mock/MockPageRecord.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgrTest.java
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/IPageRecord.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/IPageRecord.java 2012-04-29 04:09:15 UTC (rev 3038)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/IPageRecord.java 2012-04-29 04:53:50 UTC (rev 3039)
@@ -59,4 +59,6 @@
int getNumberOfPage();
+ long getPageNumber();
+
}
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/PageRecord.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/PageRecord.java 2012-04-29 04:09:15 UTC (rev 3038)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/PageRecord.java 2012-04-29 04:53:50 UTC (rev 3039)
@@ -40,6 +40,8 @@
private IPageRecordable pageRecordable;
+ private final long pageNumber;
+
/**
* creation for reading
*
@@ -49,11 +51,13 @@
public PageRecord(final IFileForStorable fileForStorable,
final long pageNumber) {
super(fileForStorable, pageNumber << PageConstant.PAGE_BITS);
+ this.pageNumber = pageNumber;
}
public PageRecord(final IFileForStorable fileForStorable,
final IPageRecordable pageRecordable, final long pageNumber) {
super(fileForStorable, pageNumber << PageConstant.PAGE_BITS);
+ this.pageNumber = pageNumber;
this.pageRecordable = pageRecordable;
this.recordType = pageRecordable.getRecordType();
}
@@ -62,6 +66,11 @@
return recordType;
}
+ @Override
+ public long getPageNumber() {
+ return pageNumber;
+ }
+
public IPageRecordable getPageRecordable() {
return pageRecordable;
}
@@ -210,6 +219,7 @@
assert pageRecordable.getByteSize() <= PageConstant.PAGE_SIZE;
final FreePage freePage = (FreePage) pageRecordable;
writeLong(freePage.getNextFreePage());
+ writeCrc32();
}
private void unmarshallFreePage() throws HeapException {
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgr.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgr.java 2012-04-29 04:09:15 UTC (rev 3038)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgr.java 2012-04-29 04:53:50 UTC (rev 3039)
@@ -26,6 +26,7 @@
import net.sf.joafip.Fortest;
import net.sf.joafip.NotStorableClass;
import net.sf.joafip.btreeplus.entity.DataBlockPage;
+import net.sf.joafip.btreeplus.entity.FreePage;
import net.sf.joafip.btreeplus.entity.HeaderPage;
import net.sf.joafip.btreeplus.entity.IDataBlock;
import net.sf.joafip.btreeplus.entity.ILeafPage;
@@ -120,6 +121,7 @@
public IFileStorable createHeapRecord(
final IHeapElementManager heapElementManager,
final long positionInFile) throws HeapException {
+ // ASSERTX
assert (positionInFile & PageConstant.IN_PAGE_POSITION_MASK) == 0;
return new PageRecord(fileForStorable,
(int) (positionInFile >> PageConstant.PAGE_BITS));
@@ -152,17 +154,6 @@
return heapElementManager.backup(identifier, maxBackup);
}
- @Fortest
- public long getRecordPositionInfile(final DataRecordIdentifier identifier) {
- throw new UnsupportedOperationException("not implemented");
- }
-
- @Fortest
- public long getLastRecordPositionInFile() throws HeapException {
- return (header.getFileSizeAsNumberOfPage() - 1)
- * PageConstant.PAGE_SIZE;
- }
-
public long getNextFreeDataRecordIdentifier() {
return header.getNextFreeDataRecordIdentifier();
}
@@ -311,11 +302,27 @@
private void internalAppendPageRecordable(
final IPageRecordable pageRecordable) throws HeapException {
- long pageNumber = header.getFileSizeAsNumberOfPage();
+ long pageNumber = header.getPageNumberOfFirstFreePage();
+ boolean newPage;
+ if (pageNumber == -1) {
+ newPage = true;
+ pageNumber = header.getFileSizeAsNumberOfPage();
+ } else {
+ newPage = false;
+ final FreePage freePage = (FreePage) ((PageRecord) heapElementManager
+ .readHeapFileDataRecord(pageNumber << PageConstant.PAGE_BITS))
+ .getPageRecordable();
+ header.setPageNumberOfFirstFreePage(freePage.getNextFreePage());
+ }
final IPageRecord pageRecord = new PageRecord(fileForStorable,
pageRecordable, pageNumber);
- header.setFileSizeAsNumberOfPage(pageNumber
- + pageRecord.getNumberOfPage());
+ if (newPage) {
+ header.setFileSizeAsNumberOfPage(pageNumber
+ + pageRecord.getNumberOfPage());
+ } else {
+ // ASSERTX
+ assert pageRecord.getNumberOfPage() == 1;
+ }
pageRecordable.setPageRecord(pageRecord);
heapElementManager.appendHeapFileRecord(pageRecord);
}
@@ -325,8 +332,26 @@
|| pageRecordable instanceof NonTerminalPage;
}
- public void freePage(IPageRecord pageRecord) {
- // FIXMELUC _______________to implement
+ public void freePage(final IPageRecord pageRecord) throws HeapException {
+ final long freePageNumber = header.getPageNumberOfFirstFreePage();
+ FreePage freePage = new FreePage(freePageNumber);
+ final long newFreePageNumber = pageRecord.getPageNumber();
+ PageRecord pageRecord2 = new PageRecord(fileForStorable, freePage,
+ newFreePageNumber);
+ freePage.setPageRecord(pageRecord2);
+ freePage.setValueIsChangedValueToSave();
+ heapElementManager.appendHeapFileRecord(pageRecord2);
+ header.setPageNumberOfFirstFreePage(newFreePageNumber);
+ }
+ @Fortest
+ public long getRecordPositionInfile(final DataRecordIdentifier identifier) {
+ throw new UnsupportedOperationException("not implemented");
}
+
+ @Fortest
+ public long getLastRecordPositionInFile() throws HeapException {
+ return (header.getFileSizeAsNumberOfPage() - 1)
+ * PageConstant.PAGE_SIZE;
+ }
}
Modified: trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/mock/MockPageRecord.java
===================================================================
--- trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/mock/MockPageRecord.java 2012-04-29 04:09:15 UTC (rev 3038)
+++ trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/mock/MockPageRecord.java 2012-04-29 04:53:50 UTC (rev 3039)
@@ -40,6 +40,11 @@
}
@Override
+ public long getPageNumber() {
+ return 0;
+ }
+
+ @Override
public int getNumberOfPage() {
return 0;
}
Modified: trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgrTest.java
===================================================================
--- trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgrTest.java 2012-04-29 04:09:15 UTC (rev 3038)
+++ trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgrTest.java 2012-04-29 04:53:50 UTC (rev 3039)
@@ -165,6 +165,44 @@
btreePlusElementMgr.closeTransactionDiscardChange();
}
+ public void testFreePage() throws HeapException {
+ btreePlusElementMgr.openTransaction();
+ assertEquals("must not has free page", -1, getHeapHeader()
+ .getPageNumberOfFirstFreePage());
+ IPageRecordable pageRecordable = new LeafPage();
+ btreePlusElementMgr.appendPageRecordable(pageRecordable);
+ pageRecordable.setValueIsChangedValueToSave();
+ pageRecordable = new LeafPage();
+ btreePlusElementMgr.appendPageRecordable(pageRecordable);
+ pageRecordable.setValueIsChangedValueToSave();
+ final long pageNumber = pageRecordable.getPageRecord().getPageNumber();
+ pageRecordable = new LeafPage();
+ btreePlusElementMgr.appendPageRecordable(pageRecordable);
+ pageRecordable.setValueIsChangedValueToSave();
+ btreePlusElementMgr.closeTransaction();
+
+ btreePlusElementMgr.openTransaction();
+ assertEquals("must not has free page", -1, getHeapHeader()
+ .getPageNumberOfFirstFreePage());
+ final IPageRecord pageRecord = btreePlusElementMgr
+ .getPage(pageNumber << PageConstant.PAGE_BITS,
+ null/* parentPage */, -1/* index */).getPageRecord();
+ btreePlusElementMgr.freePage(pageRecord);
+ btreePlusElementMgr.closeTransaction();
+
+ btreePlusElementMgr.openTransaction();
+ assertEquals("must has free page", pageNumber, getHeapHeader()
+ .getPageNumberOfFirstFreePage());
+ pageRecordable = new LeafPage();
+ btreePlusElementMgr.appendPageRecordable(pageRecordable);
+ pageRecordable.setValueIsChangedValueToSave();
+ final long pageNumber2 = pageRecordable.getPageRecord().getPageNumber();
+ assertEquals("must reuse", pageNumber, pageNumber2);
+ assertEquals("must not has free page", -1, getHeapHeader()
+ .getPageNumberOfFirstFreePage());
+ btreePlusElementMgr.closeTransaction();
+ }
+
public void testDataBlock() throws HeapException {
TestDataBlockContext[] contextByBits = new TestDataBlockContext[PageConstant.NUMBER_OF_BLOCK_TYPE];
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
|
From: <luc...@us...> - 2012-04-29 04:09:22
|
Revision: 3038
http://joafip.svn.sourceforge.net/joafip/?rev=3038&view=rev
Author: luc_peuvrier
Date: 2012-04-29 04:09:15 +0000 (Sun, 29 Apr 2012)
Log Message:
-----------
WIP btree plus, tests in progress. leaf page equilibrate and non terminal page remove added, tests ok
Modified Paths:
--------------
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/DataBlock.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/DataBlockPage.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/IDataBlock.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/LeafPage.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/NonTerminalPage.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusDataManager.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgr.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/LeafPageTest.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/NonTerminalPageTest.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/mock/MockDataBlock.java
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/DataBlock.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/DataBlock.java 2012-04-28 22:10:12 UTC (rev 3037)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/DataBlock.java 2012-04-29 04:09:15 UTC (rev 3038)
@@ -52,6 +52,10 @@
private long position = -1;
+ private LeafPage parentLeafPage;
+
+ private int indexInLeafPage;
+
public DataBlock(final DataBlockPage dataBlockPage,
final int indexInDataBlockPage, final byte bits, final int minSize,
final int maxSize) {
@@ -148,4 +152,21 @@
}
return position;
}
+
+ @Override
+ public void setParent(final LeafPage parentLeafPage,
+ final int indexInLeafPage) {
+ this.parentLeafPage = parentLeafPage;
+ this.indexInLeafPage = indexInLeafPage;
+ }
+
+ @Override
+ public LeafPage getParentLeafPage() {
+ return parentLeafPage;
+ }
+
+ @Override
+ public int getIndexInLeafPage() {
+ return indexInLeafPage;
+ }
}
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/DataBlockPage.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/DataBlockPage.java 2012-04-28 22:10:12 UTC (rev 3037)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/DataBlockPage.java 2012-04-29 04:09:15 UTC (rev 3038)
@@ -38,6 +38,8 @@
/**/1/* byte size for record type */+
/**/1/* byte size for bits */;
+ public static final int HEAD_TAIL_SIZE = HEAD_SIZE + 4/* crc32 */;
+
private byte bits;
private final int numberOfPage;
@@ -62,17 +64,17 @@
super();
this.bits = bits;
dataBlockDataSize = 1 << bits;
- if (dataBlockDataSize > PageConstant.PAGE_SIZE - HEAD_SIZE - 4/* crc32 */) {
+ if (dataBlockDataSize > PageConstant.PAGE_SIZE - HEAD_TAIL_SIZE) {
// one data block on one or more pages
numberOfBlock = 1;
- final int totalSize = HEAD_SIZE + dataBlockDataSize + 4/* crc32 */;
+ final int totalSize = HEAD_TAIL_SIZE + dataBlockDataSize;
final int n = totalSize >> PageConstant.PAGE_BITS;
if ((totalSize & PageConstant.IN_PAGE_POSITION_MASK) == 0) {
numberOfPage = n;
} else {
numberOfPage = n + 1;
}
- // FIXMELUC ____________waste space, see below
+ // FIXMELUC ________waste space, see below
// dataBlockDataSize=(numberOfPage<<PageConstant.PAGE_BITS)-
// HEAD_SIZE - 4/* crc32 */
} else {
@@ -80,7 +82,7 @@
numberOfPage = 1;
// numberOfBlock = ((int)PageConstant.PAGE_SIZE - FIX_VALUE_SIZE)
// / dataBlockDataSize;
- numberOfBlock = ((int) PageConstant.PAGE_SIZE - HEAD_SIZE - 4/* crc32 */) >> bits;
+ numberOfBlock = ((int) PageConstant.PAGE_SIZE - HEAD_TAIL_SIZE) >> bits;
}
final int minSize = bits == PageConstant.MIN_DATA_BLOCK_BITS ? 0
: ((1 << (bits - 1)) + 1);
@@ -114,7 +116,7 @@
@Override
public int getByteSize() {
return numberOfPage * (int) PageConstant.PAGE_SIZE;
- // FIXMELUC _____________use <<
+ // FIXMELUC ________use <<
// return numberOfPage <<PageConstant.PAGE_BITS
}
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/IDataBlock.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/IDataBlock.java 2012-04-28 22:10:12 UTC (rev 3037)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/IDataBlock.java 2012-04-29 04:09:15 UTC (rev 3038)
@@ -65,4 +65,9 @@
int getIndexInDataBlockPage();
+ void setParent(LeafPage parentLeafPage, int indexInLeafPage);
+
+ LeafPage getParentLeafPage();
+
+ int getIndexInLeafPage();
}
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/LeafPage.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/LeafPage.java 2012-04-28 22:10:12 UTC (rev 3037)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/LeafPage.java 2012-04-29 04:09:15 UTC (rev 3038)
@@ -37,6 +37,11 @@
@NotStorableClass
public class LeafPage extends AbstractElement implements ILeafPage {
+ public static int HEAD_TAIL_SIZE = 1/* byte size for record type */+
+ /**/4/* int size for number of entries */+
+ /**/4/* int size for crc32 */+
+ /**/8/* for next */;
+
private long[] dataBlockPosition;
private DataRecordIdentifier[] keys;
@@ -51,6 +56,8 @@
private int inParentIndex;
+ private int index;
+
public LeafPage() {
this(0);
updateByteSize();
@@ -144,11 +151,8 @@
}
private int computeByteSize() {
- int xbyteSize = 1/* byte size for record type */+
- /**/4/* int size for number of entries */+
- /**/4/* int size for crc32 */+
- /**/8/* for next */;
- // FIXMELUC ______speedup if long value key
+ int xbyteSize = HEAD_TAIL_SIZE;
+ // FIXMELUC ________speedup if long value key
for (int index = 0; index < numberOfKeyEntries; index++) {
xbyteSize += entrySize(keys[index]);
}
@@ -163,9 +167,9 @@
*/
public long getDataBlockPosition(
final DataRecordIdentifier dataRecordIdentifier) {
- // FIXMELUC _______dichotomic search
+ // FIXMELUC _________dichotomic search
long position = -1;
- for (int index = 0; position == -1L && index < numberOfKeyEntries; index++) {
+ for (index = 0; position == -1L && index < numberOfKeyEntries; index++) {
if (keys[index].compareTo(dataRecordIdentifier) == 0) {
position = dataBlockPosition[index];
}
@@ -173,6 +177,10 @@
return position;
}
+ public int getIndex() {
+ return index;
+ }
+
public void setDataBlock(final int index, final IDataBlock dataBlock)
throws HeapException {
dataBlockPosition[index] = dataBlock.getPositionInFile();
@@ -262,6 +270,40 @@
return newLeafPage;
}
+ public void remove(final int index) throws HeapException {
+ DataRecordIdentifier dataRecordIdentifier = keys[index];
+ final int entrySize = entrySize(dataRecordIdentifier);
+ // ASSERTX
+ assert byteSize != 0 : "unknow current byte size";
+ final int afterLength = numberOfKeyEntries - (index + 1);
+ numberOfKeyEntries--;
+ final long[] newDataBlockPosition = new long[numberOfKeyEntries];
+ final DataRecordIdentifier[] newKeys = new DataRecordIdentifier[numberOfKeyEntries];
+ if (index != 0) {
+ System.arraycopy(dataBlockPosition, 0, newDataBlockPosition, 0,
+ index);
+ System.arraycopy(keys, 0, newKeys, 0, index);
+ }
+ if (afterLength != 0) {
+ System.arraycopy(dataBlockPosition, index + 1,
+ newDataBlockPosition, index, afterLength);
+ System.arraycopy(keys, index + 1, newKeys, index, afterLength);
+ }
+ keys = newKeys;
+ dataBlockPosition = newDataBlockPosition;
+ byteSize -= entrySize;
+ // ASSERTX
+ assert byteSize == computeByteSize() : byteSize + " for "
+ + computeByteSize() + " computed";
+ setValueIsChangedValueToSave();
+ }
+
+ public boolean wellFilled() {
+ // ASSERTX
+ assert byteSize != 0 : "unknow current byte size";
+ return byteSize >= (PageConstant.PAGE_SIZE >> 1);
+ }
+
private int computeInsertBeforeIndex(
final DataRecordIdentifier dataRecordIdentifier) {
int index;
@@ -274,4 +316,83 @@
public DataRecordIdentifier getLastKey() {
return keys[numberOfKeyEntries - 1];
}
+
+ /**
+ *
+ * @param leafPage
+ * @return true if merge in this page, leafPage is to be destroyed
+ */
+ public boolean equilibrate(final LeafPage leafPage) {
+ // ASSERTX
+ assert byteSize != 0 : "unknow current byte size";
+ final int leafPageByteSize = leafPage.getByteSize();
+ final int leafPageNumberOfKeyEntries = leafPage.numberOfKeyEntries;
+ final int totalNumberOfEntries = numberOfKeyEntries
+ + leafPageNumberOfKeyEntries;
+ final boolean merged;
+ if (byteSize + leafPageByteSize - HEAD_TAIL_SIZE <= PageConstant.PAGE_SIZE) {
+ merged = true;
+ dataBlockPosition = Arrays.copyOf(dataBlockPosition,
+ totalNumberOfEntries);
+ keys = Arrays.copyOf(keys, totalNumberOfEntries);
+ System.arraycopy(leafPage.dataBlockPosition, 0, dataBlockPosition,
+ numberOfKeyEntries, leafPageNumberOfKeyEntries);
+ System.arraycopy(leafPage.keys, 0, keys, numberOfKeyEntries,
+ leafPageNumberOfKeyEntries);
+ numberOfKeyEntries = totalNumberOfEntries;
+ // can merge
+ byteSize += leafPageByteSize - HEAD_TAIL_SIZE;
+ // ASSERTX
+ assert byteSize == computeByteSize() : byteSize + " for "
+ + computeByteSize() + " computed";
+ } else {
+ merged = false;
+ final int newNumberOfEntries = totalNumberOfEntries / 2;
+ final int newLeafPageNumberOfEntries = totalNumberOfEntries
+ - newNumberOfEntries;
+ if (newNumberOfEntries > numberOfKeyEntries) {
+ dataBlockPosition = Arrays.copyOf(dataBlockPosition,
+ newNumberOfEntries);
+ keys = Arrays.copyOf(keys, newNumberOfEntries);
+ final int length = newNumberOfEntries - numberOfKeyEntries;
+ System.arraycopy(leafPage.dataBlockPosition, 0,
+ dataBlockPosition, numberOfKeyEntries, length);
+ System.arraycopy(leafPage.keys, 0, keys, numberOfKeyEntries,
+ length);
+ leafPage.dataBlockPosition = Arrays.copyOfRange(
+ leafPage.dataBlockPosition, length,
+ leafPageNumberOfKeyEntries);
+ leafPage.keys = Arrays.copyOfRange(leafPage.keys, length,
+ leafPageNumberOfKeyEntries);
+ numberOfKeyEntries = newNumberOfEntries;
+ leafPage.numberOfKeyEntries = newLeafPageNumberOfEntries;
+ updateByteSize();
+ leafPage.updateByteSize();
+ } else if (newLeafPageNumberOfEntries > leafPageNumberOfKeyEntries) {
+ long[] newLeafPageDataBlockPosition = new long[newLeafPageNumberOfEntries];
+ DataRecordIdentifier[] newLeafPageKeys = new DataRecordIdentifier[newLeafPageNumberOfEntries];
+ final int length = newLeafPageNumberOfEntries
+ - leafPageNumberOfKeyEntries;
+ System.arraycopy(dataBlockPosition, newNumberOfEntries,
+ newLeafPageDataBlockPosition, 0, length);
+ System.arraycopy(keys, newNumberOfEntries, newLeafPageKeys, 0,
+ length);
+ System.arraycopy(leafPage.dataBlockPosition, 0,
+ newLeafPageDataBlockPosition, length,
+ leafPageNumberOfKeyEntries);
+ System.arraycopy(leafPage.keys, 0, newLeafPageKeys, length,
+ leafPageNumberOfKeyEntries);
+ dataBlockPosition = Arrays.copyOf(dataBlockPosition,
+ newNumberOfEntries);
+ keys = Arrays.copyOf(keys, newNumberOfEntries);
+ leafPage.dataBlockPosition = newLeafPageDataBlockPosition;
+ leafPage.keys = newLeafPageKeys;
+ numberOfKeyEntries = newNumberOfEntries;
+ leafPage.numberOfKeyEntries = newLeafPageNumberOfEntries;
+ updateByteSize();
+ leafPage.updateByteSize();
+ }// else no changes
+ }
+ return merged;
+ }
}
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/NonTerminalPage.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/NonTerminalPage.java 2012-04-28 22:10:12 UTC (rev 3037)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/NonTerminalPage.java 2012-04-29 04:09:15 UTC (rev 3038)
@@ -38,6 +38,11 @@
public class NonTerminalPage extends AbstractElement implements
INonTerminalPage {
+ public static int HEAD_TAIL_SIZE = 1/* byte size for record type */+
+ /**/4/* int size for number of entries */+
+ /**/4/* int size for crc32 */+
+ /**/8/* last pointer long size */;
+
private long[] pagePositions;
private DataRecordIdentifier[] keys;
@@ -112,6 +117,25 @@
setValueIsChangedValueToSave();
}
+ /**
+ * change key
+ *
+ * @param index
+ * @param key
+ * @return true if not need to split (not too big)
+ * @throws HeapException
+ */
+ public boolean setKey(final int index, final DataRecordIdentifier key)
+ throws HeapException {
+ DataRecordIdentifier oldKey = keys[index];
+ keys[index] = key;
+ byteSize = byteSize - entrySize(oldKey) + entrySize(key);
+ // ASSERTX
+ assert byteSize == computeByteSize();
+ setValueIsChangedValueToSave();
+ return byteSize < PageConstant.PAGE_SIZE;
+ }
+
@Override
public int getByteSize() {
// ASSERTX
@@ -125,11 +149,8 @@
}
private int computeByteSize() {
- int xbyteSize = 1/* byte size for record type */+
- /**/4/* int size for number of entries */+
- /**/4/* int size for crc32 */+
- /**/8/* last pointer long size */;
- // FIXMELUC ______speedup if long value key
+ int xbyteSize = HEAD_TAIL_SIZE;
+ // FIXMELUC ________speedup if long value key
for (int index = 0; index < numberOfKeyEntries; index++) {
xbyteSize += entrySize(keys[index]);
}
@@ -157,7 +178,7 @@
* @return sub page index for data record identifier
*/
public int getIndex(final DataRecordIdentifier dataRecordIdentifier) {
- // FIXMELUC _______dichotomic search
+ // FIXMELUC _________dichotomic search
int index;
for (index = 0; index < numberOfKeyEntries; index++) {
if (keys[index].compareTo(dataRecordIdentifier) >= 0) {
@@ -283,4 +304,37 @@
middleKey = null;
return result;
}
+
+ public void remove(int leafPageInParentIndex) {
+ final DataRecordIdentifier key = keys[leafPageInParentIndex];
+ numberOfKeyEntries--;
+ DataRecordIdentifier[] newKeys = new DataRecordIdentifier[numberOfKeyEntries];
+ long[] newPagePositions = new long[numberOfKeyEntries + 1];
+ if (leafPageInParentIndex != 0) {
+ System.arraycopy(keys, 0, newKeys, 0, leafPageInParentIndex);
+ System.arraycopy(pagePositions, 0, newPagePositions, 0,
+ leafPageInParentIndex);
+ }
+ final int length = numberOfKeyEntries - leafPageInParentIndex;
+ if (length != 0) {
+ System.arraycopy(keys, leafPageInParentIndex + 1, newKeys,
+ leafPageInParentIndex, length);
+ }
+ System.arraycopy(pagePositions, leafPageInParentIndex + 1,
+ newPagePositions, leafPageInParentIndex, length + 1);
+ keys = newKeys;
+ pagePositions = newPagePositions;
+ // ASSERTX
+ assert byteSize != 0 : "unknow current byte size";
+ byteSize -= entrySize(key);
+ // ASSERTX
+ assert byteSize == computeByteSize() : "byteSize=" + byteSize
+ + ", computed=" + computeByteSize();
+ }
+
+ public boolean wellFilled() {
+ // ASSERTX
+ assert byteSize != 0 : "unknow current byte size";
+ return byteSize >= (PageConstant.PAGE_SIZE >> 1);
+ }
}
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusDataManager.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusDataManager.java 2012-04-28 22:10:12 UTC (rev 3037)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusDataManager.java 2012-04-29 04:09:15 UTC (rev 3038)
@@ -35,6 +35,7 @@
import net.sf.joafip.btreeplus.entity.IPageRecordable;
import net.sf.joafip.btreeplus.entity.LeafPage;
import net.sf.joafip.btreeplus.entity.NonTerminalPage;
+import net.sf.joafip.btreeplus.entity.PageConstant;
import net.sf.joafip.kvstore.entity.HeapFileSetup;
import net.sf.joafip.kvstore.record.entity.DataRecordIdentifier;
import net.sf.joafip.kvstore.record.service.HeapElementManagerFactory;
@@ -198,39 +199,6 @@
return dataBlockPosition != -1L;
}
- private long dataBlockPosition(final IPageRecordable root,
- final DataRecordIdentifier dataRecordIdentifier)
- throws HeapException {
- final long dataBlockPosition;
- final LeafPage leafPage = leafPage(root, dataRecordIdentifier);
- if (leafPage == null) {
- dataBlockPosition = -1L;
- } else {
- dataBlockPosition = leafPage
- .getDataBlockPosition(dataRecordIdentifier);
- }
- return dataBlockPosition;
- }
-
- private LeafPage leafPage(final IPageRecordable root,
- final DataRecordIdentifier dataRecordIdentifier)
- throws HeapException {
- IPageRecordable page;
- if (root == null) {
- page = null;
- } else {
- page = root;
- while (!EnumRecordType.LEAF_PAGE.equals(page)) {
- final NonTerminalPage nonTerminalPage = (NonTerminalPage) page;
- final int index = nonTerminalPage
- .getIndex(dataRecordIdentifier);
- final long pagePosition = nonTerminalPage.getPagePointer(index);
- page = btreePlusElementMgr.getPage(pagePosition, page, index);
- }
- }
- return (LeafPage) page;
- }
-
@Override
protected boolean writeDataRecordImpl(
final DataRecordIdentifier dataRecordIdentifier, final byte[] data)
@@ -246,6 +214,7 @@
btreePlusElementMgr
.newRootLeafPage(dataRecordIdentifier, dataBlock);
} else {
+ // existing data
long dataBlockPosition = leafPage
.getDataBlockPosition(dataRecordIdentifier);
if (dataBlockPosition == -1) {
@@ -254,6 +223,7 @@
final IDataBlock dataBlock = btreePlusElementMgr
.createDataBlock(data);
if (!leafPage.add(dataRecordIdentifier, dataBlock)) {
+ // FIXMELUC ________rotation, dispatch on sibling
LeafPage newLeafPage = leafPage.split(dataRecordIdentifier,
dataBlock);
btreePlusElementMgr.appendPageRecordable(newLeafPage);
@@ -267,31 +237,7 @@
newLeafPage);
} else {
if (!nonTerminalPage.add(leafPage, newLeafPage)) {
- INonTerminalPage newNonTerminalPage = nonTerminalPage
- .split();
- do {
- btreePlusElementMgr
- .appendPageRecordable(newNonTerminalPage);
- newNonTerminalPage
- .setValueIsChangedValueToSave();
- DataRecordIdentifier middleKey = nonTerminalPage
- .getAndClearMiddleKey();
- NonTerminalPage parent = (NonTerminalPage) nonTerminalPage
- .getParentPage();
- if (parent == null) {
- btreePlusElementMgr.newRootNonTerminalPage(
- nonTerminalPage, middleKey,
- newNonTerminalPage);
- } else {
- if (parent.add(nonTerminalPage, middleKey,
- newNonTerminalPage)) {
- newNonTerminalPage = null;
- } else {
- newNonTerminalPage = nonTerminalPage
- .split();
- }
- }
- } while (newNonTerminalPage != null);
+ equilibrateFull(nonTerminalPage);
}
}
}
@@ -315,14 +261,118 @@
return created;
}
+ /**
+ *
+ * @param nonTerminalPage
+ * a too big page
+ * @throws HeapException
+ */
+ private void equilibrateFull(NonTerminalPage nonTerminalPage)
+ throws HeapException {
+ // FIXMELUC ________rotation, dispatch on sibling
+ INonTerminalPage newNonTerminalPage = nonTerminalPage.split();
+ do {
+ btreePlusElementMgr.appendPageRecordable(newNonTerminalPage);
+ newNonTerminalPage.setValueIsChangedValueToSave();
+ DataRecordIdentifier middleKey = nonTerminalPage
+ .getAndClearMiddleKey();
+ NonTerminalPage parent = (NonTerminalPage) nonTerminalPage
+ .getParentPage();
+ if (parent == null) {
+ btreePlusElementMgr.newRootNonTerminalPage(nonTerminalPage,
+ middleKey, newNonTerminalPage);
+ } else {
+ if (parent.add(nonTerminalPage, middleKey, newNonTerminalPage)) {
+ newNonTerminalPage = null;
+ } else {
+ newNonTerminalPage = nonTerminalPage.split();
+ }
+ }
+ } while (newNonTerminalPage != null);
+ }
+
@Override
protected boolean deleteDataRecordImpl(
final DataRecordIdentifier dataRecordIdentifier)
throws HeapException {
- // FIXMELUC ________to implement
- throw new HeapException("not implemented");
+ final boolean deleted;
+ final IDataBlock dataBlock = dataBlock(dataRecordIdentifier);
+ if (dataBlock == null) {
+ deleted = false;
+ } else {
+ deleted = true;
+ LeafPage leafPage = dataBlock.getParentLeafPage();
+ int indexInLeafPage = dataBlock.getIndexInLeafPage();
+ btreePlusElementMgr.remove(dataBlock);
+ leafPage.remove(indexInLeafPage);
+ final NonTerminalPage nonTerminalPage = (NonTerminalPage) leafPage
+ .getParentPage();
+ final int leafPageInParentIndex = leafPage.getInParentIndex();
+ if (leafPage.wellFilled()) {
+ if (leafPageInParentIndex != nonTerminalPage
+ .getNumberOfKeyEntries()) {
+ if (!nonTerminalPage.setKey(leafPageInParentIndex,
+ leafPage.getLastKey())) {
+ equilibrateFull(nonTerminalPage);
+ }
+ }
+ } else if (leafPageInParentIndex != 0) {
+ final int leftLeafPageInParentIndex = leafPageInParentIndex - 1;
+ final long leftLeafPagePosition = nonTerminalPage
+ .getPagePointer(leftLeafPageInParentIndex);
+ final LeafPage leftLeafPage = (LeafPage) btreePlusElementMgr
+ .getPage(leftLeafPagePosition, nonTerminalPage,
+ leftLeafPageInParentIndex);
+ if (leftLeafPage.equilibrate(leafPage)) {
+ // leaf page merged in left leaf page
+ btreePlusElementMgr.freePage(leafPage.getPageRecord());
+ nonTerminalPage.remove(leafPageInParentIndex);
+ if (nonTerminalPage.setKey(leftLeafPageInParentIndex,
+ leftLeafPage.getLastKey())) {
+ equilibrate(nonTerminalPage);
+ } else {
+ equilibrateFull(nonTerminalPage);
+ }
+ } else {
+ if (!nonTerminalPage.setKey(leftLeafPageInParentIndex,
+ leftLeafPage.getLastKey())) {
+ equilibrateFull(nonTerminalPage);
+ }
+ }
+ } else if (leafPageInParentIndex != nonTerminalPage
+ .getNumberOfKeyEntries() - 1) {
+ final int rightLeafPageinParentIndex = leafPageInParentIndex + 1;
+ final long rightLeafPagePosition = nonTerminalPage
+ .getPagePointer(rightLeafPageinParentIndex);
+ final LeafPage rightLeafPage = (LeafPage) btreePlusElementMgr
+ .getPage(rightLeafPagePosition, nonTerminalPage,
+ rightLeafPageinParentIndex);
+ if (leafPage.equilibrate(rightLeafPage)) {
+ // right leaf page merged in leaf page
+ btreePlusElementMgr.freePage(rightLeafPage.getPageRecord());
+ nonTerminalPage.remove(rightLeafPageinParentIndex);
+ if (nonTerminalPage.setKey(leafPageInParentIndex,
+ leafPage.getLastKey())) {
+ equilibrate(nonTerminalPage);
+ } else {
+ equilibrateFull(nonTerminalPage);
+ }
+ } else {
+
+ }
+ }
+ }
+ return deleted;
}
+ private void equilibrate(final NonTerminalPage nonTerminalPage) {
+ // FIXMELUC __________________to implement
+ if (nonTerminalPage.wellFilled()) {
+
+ }
+
+ }
+
@Override
protected DataRecordIdentifier removeFirstDataRecordImpl()
throws HeapException {
@@ -342,20 +392,62 @@
throw new HeapException("not implemented");
}
- @Override
- protected Set<DataRecordIdentifier> getDataRecordIdentifierSetImpl()
+ private long dataBlockPosition(final IPageRecordable root,
+ final DataRecordIdentifier dataRecordIdentifier)
throws HeapException {
- // FIXMELUC ________to implement
- throw new HeapException("not implemented");
+ final long dataBlockPosition;
+ final LeafPage leafPage = leafPage(root, dataRecordIdentifier);
+ if (leafPage == null) {
+ dataBlockPosition = -1L;
+ } else {
+ dataBlockPosition = leafPage
+ .getDataBlockPosition(dataRecordIdentifier);
+ }
+ return dataBlockPosition;
}
- @Override
- protected Iterator<DataRecordIdentifier> dataRecordIteratorImpl()
+ private IDataBlock dataBlock(final DataRecordIdentifier dataRecordIdentifier)
throws HeapException {
- // FIXMELUC ________to implement
- throw new HeapException("not implemented");
+ final IPageRecordable root = btreePlusElementMgr.getRoot();
+ return dataBlock(root, dataRecordIdentifier);
}
+ private IDataBlock dataBlock(final IPageRecordable root,
+ final DataRecordIdentifier dataRecordIdentifier)
+ throws HeapException {
+ final IDataBlock dataBlock;
+ final LeafPage leafPage = leafPage(root, dataRecordIdentifier);
+ if (leafPage == null) {
+ dataBlock = null;
+ } else {
+ final long dataBlockPosition = leafPage
+ .getDataBlockPosition(dataRecordIdentifier);
+ final int indexinLeafPage = leafPage.getIndex();
+ dataBlock = btreePlusElementMgr.getDataBlock(dataBlockPosition);
+ dataBlock.setParent(leafPage, indexinLeafPage);
+ }
+ return dataBlock;
+ }
+
+ private LeafPage leafPage(final IPageRecordable root,
+ final DataRecordIdentifier dataRecordIdentifier)
+ throws HeapException {
+ IPageRecordable page;
+ if (root == null) {
+ page = null;
+ } else {
+ page = root;
+ while (!EnumRecordType.LEAF_PAGE.equals(page)) {
+ final NonTerminalPage nonTerminalPage = (NonTerminalPage) page;
+ final int index = nonTerminalPage
+ .getIndex(dataRecordIdentifier);
+ final long pagePosition = nonTerminalPage.getPagePointer(index);
+ page = btreePlusElementMgr.getPage(pagePosition, page, index);
+ }
+ }
+ return (LeafPage) page;
+ }
+
@Override
protected long heapSizeImpl() throws HeapException {
return btreePlusElementMgr.heapSize();
@@ -371,8 +463,26 @@
return btreePlusElementMgr.usedSize();
}
+ // --------------------------------------------
+
@Fortest
@Override
+ protected Set<DataRecordIdentifier> getDataRecordIdentifierSetImpl()
+ throws HeapException {
+ // FIXMELUC ________to implement
+ throw new HeapException("not implemented");
+ }
+
+ @Fortest
+ @Override
+ protected Iterator<DataRecordIdentifier> dataRecordIteratorImpl()
+ throws HeapException {
+ // FIXMELUC ________to implement
+ throw new HeapException("not implemented");
+ }
+
+ @Fortest
+ @Override
public long getRecordPositionInfile(final DataRecordIdentifier identifier)
throws HeapException {
return btreePlusElementMgr.getRecordPositionInfile(identifier);
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgr.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgr.java 2012-04-28 22:10:12 UTC (rev 3037)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgr.java 2012-04-29 04:09:15 UTC (rev 3038)
@@ -324,4 +324,9 @@
return pageRecordable instanceof ILeafPage
|| pageRecordable instanceof NonTerminalPage;
}
+
+ public void freePage(IPageRecord pageRecord) {
+ // FIXMELUC _______________to implement
+
+ }
}
Modified: trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/LeafPageTest.java
===================================================================
--- trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/LeafPageTest.java 2012-04-28 22:10:12 UTC (rev 3037)
+++ trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/LeafPageTest.java 2012-04-29 04:09:15 UTC (rev 3038)
@@ -66,26 +66,27 @@
LeafPage leafPage = new LeafPage();
leafPage.setPageRecord(PAGE_RECORD);
addToLeafPage(leafPage, 1000/* position */, 10/* key value */, 10, 1);
+ checkContent(leafPage,
+ /**/new int[] { 10 },
+ /**/new long[] { 1000 });
addToLeafPage(leafPage, 2000/* position */, 5/* key value */, 10, 2);
+ checkContent(leafPage,
+ /**/new int[] { 5, 10 },
+ /**/new long[] { 2000, 1000 });
addToLeafPage(leafPage, 3000/* position */, 15/* key value */, 15, 3);
+ checkContent(leafPage,
+ /**/new int[] { 5, 10, 15 },
+ /**/new long[] { 2000, 1000, 3000 });
addToLeafPage(leafPage, 4000/* position */, 7/* key value */, 15, 4);
+ checkContent(leafPage,
+ /**/new int[] { 5, 7, 10, 15 },
+ /**/new long[] { 2000, 4000, 1000, 3000 });
addToLeafPage(leafPage, 5000/* position */, 17/* key value */, 17, 5);
- assertEquals("bad #0 key", new DataRecordIdentifier(5),
- leafPage.getKey(0));
- assertEquals("bad #0 position", 2000, leafPage.getBlockPointer(0));
- assertEquals("bad #1 key", new DataRecordIdentifier(7),
- leafPage.getKey(1));
- assertEquals("bad #1 position", 4000, leafPage.getBlockPointer(1));
- assertEquals("bad #2 key", new DataRecordIdentifier(10),
- leafPage.getKey(2));
- assertEquals("bad #2 position", 1000, leafPage.getBlockPointer(2));
- assertEquals("bad #3 key", new DataRecordIdentifier(15),
- leafPage.getKey(3));
- assertEquals("bad #3 position", 3000, leafPage.getBlockPointer(3));
- assertEquals("bad #4 key", new DataRecordIdentifier(17),
- leafPage.getKey(4));
- assertEquals("bad #4 position", 5000, leafPage.getBlockPointer(4));
+ checkContent(leafPage,
+ /**/new int[] { 5, 7, 10, 15, 17 },
+ /**/new long[] { 2000, 4000, 1000, 3000, 5000 });
+ // test no more add possible
final int maxNumberOfEntries = maxNumberOfEntries();
final MockDataBlock dataBlock = new MockDataBlock();
while (leafPage.getNumberOfKeyEntries() != maxNumberOfEntries) {
@@ -221,6 +222,117 @@
}
}
+ public void testRemove() throws HeapException {
+ final LeafPage leafPage = new LeafPage();
+ addToLeafPage(leafPage,
+ /**/new int[] { 5, 7, 10, 15, 17 },
+ /**/new long[] { 2000, 4000, 1000, 3000, 5000 });
+
+ leafPage.remove(0);
+ checkContent(leafPage,
+ /**/new int[] { 7, 10, 15, 17 },
+ /**/new long[] { 4000, 1000, 3000, 5000 });
+
+ leafPage.remove(3);
+ checkContent(leafPage,
+ /**/new int[] { 7, 10, 15 },
+ /**/new long[] { 4000, 1000, 3000 });
+
+ leafPage.remove(1);
+ checkContent(leafPage,
+ /**/ne...
[truncated message content] |
|
From: <luc...@us...> - 2012-04-29 12:38:58
|
Revision: 3040
http://joafip.svn.sourceforge.net/joafip/?rev=3040&view=rev
Author: luc_peuvrier
Date: 2012-04-29 12:38:52 +0000 (Sun, 29 Apr 2012)
Log Message:
-----------
WIP btree plus, tests in progress. non terminal page equilibrate, tests ok
Modified Paths:
--------------
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/NonTerminalPage.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusDataManager.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/NonTerminalPageTest.java
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/NonTerminalPage.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/NonTerminalPage.java 2012-04-29 04:53:50 UTC (rev 3039)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/NonTerminalPage.java 2012-04-29 12:38:52 UTC (rev 3040)
@@ -337,4 +337,106 @@
assert byteSize != 0 : "unknow current byte size";
return byteSize >= (PageConstant.PAGE_SIZE >> 1);
}
+
+ /**
+ * update {@link this#middleKey} if do not merge
+ *
+ * @param middleKey
+ * @param rightNonTerminalPage
+ * @return true if merge in this page, nonTerminalPage is to be destroyed
+ */
+ public boolean equilibrate(final DataRecordIdentifier middleKey,
+ final NonTerminalPage rightNonTerminalPage) {
+ assert byteSize != 0 : "unknow current byte size";
+ final int rightPageByteSize = rightNonTerminalPage.getByteSize();
+ final int middleKeySize = entrySize(middleKey);
+ final int rightPageNumberOfKeyEntries = rightNonTerminalPage.numberOfKeyEntries;
+ final int totalNumberOfEntries = numberOfKeyEntries
+ + rightPageNumberOfKeyEntries;
+ final boolean merged;
+ if (byteSize + middleKeySize + rightPageByteSize - HEAD_TAIL_SIZE <= PageConstant.PAGE_SIZE) {
+ // can merge
+ merged = true;
+ pagePositions = Arrays.copyOf(pagePositions,
+ totalNumberOfEntries + 1 + 1);
+ keys = Arrays.copyOf(keys, totalNumberOfEntries + 1);
+ System.arraycopy(rightNonTerminalPage.pagePositions, 0,
+ pagePositions, numberOfKeyEntries + 1,
+ rightPageNumberOfKeyEntries + 1);
+ keys[numberOfKeyEntries] = middleKey;
+ System.arraycopy(rightNonTerminalPage.keys, 0, keys,
+ numberOfKeyEntries + 1, rightPageNumberOfKeyEntries);
+ numberOfKeyEntries = totalNumberOfEntries + 1;
+ byteSize += middleKeySize + rightPageByteSize - HEAD_TAIL_SIZE;
+ // ASSERTX
+ assert byteSize == computeByteSize() : "byteSize=" + byteSize
+ + ", computed=" + computeByteSize();
+ } else {
+ merged = false;
+ final int newNumberOfEntries = totalNumberOfEntries / 2;
+ final int newRightPageNumberOfEntries = totalNumberOfEntries
+ - newNumberOfEntries;
+ if (newNumberOfEntries > numberOfKeyEntries) {
+ int length = newNumberOfEntries - numberOfKeyEntries;
+ pagePositions = Arrays.copyOf(pagePositions,
+ newNumberOfEntries + 1);
+ System.arraycopy(rightNonTerminalPage.pagePositions, 0,
+ pagePositions, numberOfKeyEntries + 1, length);
+ keys = Arrays.copyOf(keys, newNumberOfEntries);
+ keys[numberOfKeyEntries] = middleKey;
+ System.arraycopy(rightNonTerminalPage.keys, 0, keys,
+ numberOfKeyEntries + 1, length - 1);
+ this.middleKey = rightNonTerminalPage.keys[length - 1];
+ numberOfKeyEntries = newNumberOfEntries;
+ updateByteSize();
+ length = rightPageNumberOfKeyEntries
+ - newRightPageNumberOfEntries;
+ rightNonTerminalPage.pagePositions = Arrays.copyOfRange(
+ rightNonTerminalPage.pagePositions, length,
+ rightPageNumberOfKeyEntries + 1);
+ rightNonTerminalPage.keys = Arrays.copyOfRange(
+ rightNonTerminalPage.keys, length,
+ rightPageNumberOfKeyEntries);
+ rightNonTerminalPage.numberOfKeyEntries = newRightPageNumberOfEntries;
+ rightNonTerminalPage.updateByteSize();
+ } else if (newRightPageNumberOfEntries > rightPageNumberOfKeyEntries) {
+ final int length = newRightPageNumberOfEntries
+ - rightPageNumberOfKeyEntries;
+ long[] newPagePositions = Arrays.copyOf(pagePositions,
+ newNumberOfEntries + 1);
+ DataRecordIdentifier[] newKeys = Arrays.copyOf(keys,
+ newNumberOfEntries);
+ this.middleKey = keys[newNumberOfEntries];
+ long[] newRightPagePositions = new long[newRightPageNumberOfEntries + 1];
+ DataRecordIdentifier[] newRightKeys = new DataRecordIdentifier[newRightPageNumberOfEntries];
+ System.arraycopy(pagePositions, newNumberOfEntries + 1,
+ newRightPagePositions, 0, length);
+ System.arraycopy(keys, newNumberOfEntries + 1, newRightKeys, 0,
+ length - 1);
+ newRightKeys[length - 1] = middleKey;
+ System.arraycopy(rightNonTerminalPage.pagePositions, 0,
+ newRightPagePositions, length,
+ rightPageNumberOfKeyEntries + 1);
+ System.arraycopy(rightNonTerminalPage.keys, 0, newRightKeys,
+ length, rightPageNumberOfKeyEntries);
+ rightNonTerminalPage.numberOfKeyEntries = newRightPageNumberOfEntries;
+ rightNonTerminalPage.keys = newRightKeys;
+ rightNonTerminalPage.pagePositions = newRightPagePositions;
+ rightNonTerminalPage.updateByteSize();
+ numberOfKeyEntries = newNumberOfEntries;
+ keys = newKeys;
+ pagePositions = newPagePositions;
+ updateByteSize();
+ }
+ }
+ return merged;
+ }
+
+ public DataRecordIdentifier getLastKey() {
+ return keys[numberOfKeyEntries - 1];
+ }
+
+ public long getLastPagePosition() {
+ return pagePositions[numberOfKeyEntries];
+ }
}
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusDataManager.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusDataManager.java 2012-04-29 04:53:50 UTC (rev 3039)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusDataManager.java 2012-04-29 12:38:52 UTC (rev 3040)
@@ -35,7 +35,6 @@
import net.sf.joafip.btreeplus.entity.IPageRecordable;
import net.sf.joafip.btreeplus.entity.LeafPage;
import net.sf.joafip.btreeplus.entity.NonTerminalPage;
-import net.sf.joafip.btreeplus.entity.PageConstant;
import net.sf.joafip.kvstore.entity.HeapFileSetup;
import net.sf.joafip.kvstore.record.entity.DataRecordIdentifier;
import net.sf.joafip.kvstore.record.service.HeapElementManagerFactory;
@@ -358,19 +357,96 @@
equilibrateFull(nonTerminalPage);
}
} else {
-
+ if (!nonTerminalPage.setKey(leafPageInParentIndex,
+ leafPage.getLastKey())) {
+ equilibrateFull(nonTerminalPage);
+ }
}
}
}
return deleted;
}
- private void equilibrate(final NonTerminalPage nonTerminalPage) {
- // FIXMELUC __________________to implement
- if (nonTerminalPage.wellFilled()) {
+ private void equilibrate(final NonTerminalPage nonTerminalPage)
+ throws HeapException {
+ if (!nonTerminalPage.wellFilled()) {
+ NonTerminalPage parentNonterminal = (NonTerminalPage) nonTerminalPage
+ .getParentPage();
+ if (parentNonterminal != null) {
+ int inParentIndex = nonTerminalPage.getInParentIndex();
+ if (inParentIndex != 0) {
+ final int leftPageInParentIndex = inParentIndex - 1;
+ final long leftPagePosition = nonTerminalPage
+ .getPagePointer(leftPageInParentIndex);
+ final NonTerminalPage leftPage = (NonTerminalPage) btreePlusElementMgr
+ .getPage(leftPagePosition, nonTerminalPage,
+ leftPageInParentIndex);
+ final DataRecordIdentifier middleKey = middleKey(leftPage);
+ if (leftPage.equilibrate(middleKey, nonTerminalPage)) {
+ // page merged in left page
+ btreePlusElementMgr.freePage(nonTerminalPage
+ .getPageRecord());
+ parentNonterminal.remove(inParentIndex);
+ if (parentNonterminal.setKey(leftPageInParentIndex,
+ leftPage.getAndClearMiddleKey())) {
+ equilibrate(parentNonterminal);
+ } else {
+ equilibrateFull(nonTerminalPage);
+ }
+ } else {
+ if (!nonTerminalPage.setKey(leftPageInParentIndex,
+ leftPage.getAndClearMiddleKey())) {
+ equilibrateFull(nonTerminalPage);
+ }
+ }
+ } else if (inParentIndex != nonTerminalPage
+ .getNumberOfKeyEntries() - 1) {
+ final int rightPageinParentIndex = inParentIndex + 1;
+ final long rightPagePosition = nonTerminalPage
+ .getPagePointer(rightPageinParentIndex);
+ final NonTerminalPage rightPage = (NonTerminalPage) btreePlusElementMgr
+ .getPage(rightPagePosition, nonTerminalPage,
+ rightPageinParentIndex);
+ final DataRecordIdentifier middleKey = middleKey(nonTerminalPage);
+ if (nonTerminalPage.equilibrate(middleKey, rightPage)) {
+ // right leaf page merged in leaf page
+ btreePlusElementMgr.freePage(rightPage.getPageRecord());
+ parentNonterminal.remove(rightPageinParentIndex);
+ if (parentNonterminal.setKey(inParentIndex,
+ nonTerminalPage.getAndClearMiddleKey())) {
+ equilibrate(parentNonterminal);
+ } else {
+ equilibrateFull(nonTerminalPage);
+ }
+ } else {
+ if (!nonTerminalPage.setKey(inParentIndex,
+ nonTerminalPage.getAndClearMiddleKey())) {
+ equilibrateFull(nonTerminalPage);
+ }
+ }
+ }
+ }
+ }
+ }
+ private DataRecordIdentifier middleKey(final NonTerminalPage nonTerminalPage)
+ throws HeapException {
+ final long position = nonTerminalPage.getLastPagePosition();
+ IPageRecordable pageRecordable = btreePlusElementMgr.getPage(position,
+ nonTerminalPage, nonTerminalPage.getNumberOfKeyEntries());
+ final DataRecordIdentifier result;
+ switch (pageRecordable.getRecordType()) {
+ case NON_TERMINAL_PAGE:
+ result = ((NonTerminalPage) pageRecordable).getLastKey();
+ break;
+ case LEAF_PAGE:
+ result = ((LeafPage) pageRecordable).getLastKey();
+ break;
+ default:
+ throw new HeapException(pageRecordable.getRecordType()
+ + " unexpected page type");
}
-
+ return result;
}
@Override
Modified: trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/NonTerminalPageTest.java
===================================================================
--- trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/NonTerminalPageTest.java 2012-04-29 04:53:50 UTC (rev 3039)
+++ trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/NonTerminalPageTest.java 2012-04-29 12:38:52 UTC (rev 3040)
@@ -422,6 +422,59 @@
/**/new long[] { 1000, 2000, 3000, 5000, 6000, 7000, 8000, 10000 });
}
+ public void testEquilibrateMerge() throws HeapException {
+ final NonTerminalPage leftPage = new NonTerminalPage(5);
+ final NonTerminalPage rightPage = new NonTerminalPage(5);
+ addToNonTerminalPage(leftPage,
+ /**/new int[] { 5, 7, 10, 15, 17 },
+ /**/new long[] { 2000, 4000, 1000, 3000, 5000, 6000 });
+ leftPage.updateByteSize();
+ addToNonTerminalPage(rightPage,
+ /**/new int[] { 50, 70, 100, 150, 170 },
+ /**/new long[] { 20000, 40000, 10000, 30000, 50000, 60000 });
+ rightPage.updateByteSize();
+ assertTrue("must merge",
+ leftPage.equilibrate(new DataRecordIdentifier(25), rightPage));
+ checkState(leftPage,
+ /**/new int[] { 5, 7, 10, 15, 17, 25, 50, 70, 100, 150, 170 },
+ /**/new long[] { 2000, 4000, 1000, 3000, 5000, 6000, 20000, 40000,
+ 10000, 30000, 50000, 60000 });
+ }
+
+ public void testEquilibrateRightToLeft() throws HeapException {
+ final NonTerminalPage leftPage = new NonTerminalPage(128 + 32);
+ final NonTerminalPage rightPage = new NonTerminalPage(128 + 64);
+ addToNonTerminalPage(leftPage, createKeys(1, 128 + 32),
+ createPointers(1, 128 + 32 + 1));
+ leftPage.updateByteSize();
+ addToNonTerminalPage(rightPage, createKeys(2 + 128 + 32, 128 + 64),
+ createPointers(1 + 128 + 32 + 1, 128 + 64 + 1));
+ rightPage.updateByteSize();
+ assertFalse("must not merge", leftPage.equilibrate(
+ new DataRecordIdentifier(128 + 32 + 1), rightPage));
+ checkState(leftPage, createKeys(1, 176), createPointers(1, 177));
+ assertEquals("bad middle key", 177,
+ leftPage.getAndClearMiddleKey().value);
+ checkState(rightPage, createKeys(178, 176), createPointers(178, 177));
+ }
+
+ public void testEquilibrateLeftToRight() throws HeapException {
+ final NonTerminalPage leftPage = new NonTerminalPage(128 + 64);
+ final NonTerminalPage rightPage = new NonTerminalPage(128 + 32);
+ addToNonTerminalPage(leftPage, createKeys(1, 128 + 64),
+ createPointers(1, 128 + 64 + 1));
+ leftPage.updateByteSize();
+ addToNonTerminalPage(rightPage, createKeys(2 + 128 + 64, 128 + 32),
+ createPointers(1 + 128 + 64 + 1, 128 + 32 + 1));
+ rightPage.updateByteSize();
+ assertFalse("must not merge", leftPage.equilibrate(
+ new DataRecordIdentifier(1 + 128 + 64), rightPage));
+ checkState(leftPage, createKeys(1, 176), createPointers(1, 177));
+ assertEquals("bad middle key", 177,
+ leftPage.getAndClearMiddleKey().value);
+ checkState(rightPage, createKeys(178, 176), createPointers(178, 177));
+ }
+
private void checkState(final NonTerminalPage nonTerminalPage,
final int[] keys, final long[] pointers) {
final int numberOfEntries = keys.length;
@@ -441,8 +494,38 @@
assertEquals("bad #" + numberOfEntries + " page pointer",
pointers[numberOfEntries],
nonTerminalPage.getPagePointer(numberOfEntries));
+ assertEquals("bad last key", keys[numberOfEntries - 1],
+ nonTerminalPage.getLastKey().value);
}
+ private void addToNonTerminalPage(final NonTerminalPage nonTerminalPage,
+ final int[] keys, final long[] pointers) throws HeapException {
+ int index;
+ for (index = 0; index < keys.length; index++) {
+ nonTerminalPage.setEntry(index, pointers[index],
+ new DataRecordIdentifier(keys[index]));
+ }
+ nonTerminalPage.setEntry(index, pointers[index], null);
+ }
+
+ private int[] createKeys(final int start, final int length) {
+ final int[] keys = new int[length];
+ int value = start;
+ for (int index = 0; index < length; index++) {
+ keys[index] = value++;
+ }
+ return keys;
+ }
+
+ private long[] createPointers(final long start, final int length) {
+ final long[] pointers = new long[length];
+ long value = start;
+ for (int index = 0; index < length; index++) {
+ pointers[index] = value++;
+ }
+ return pointers;
+ }
+
private MockLeafPage newMockLeafPage() throws HeapException {
final MockLeafPage mockLeafPage = new MockLeafPage();
mockLeafPage.setPageRecord(PAGE_RECORD);
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
|
From: <luc...@us...> - 2012-04-29 12:38:58
|
Revision: 3040
http://joafip.svn.sourceforge.net/joafip/?rev=3040&view=rev
Author: luc_peuvrier
Date: 2012-04-29 12:38:52 +0000 (Sun, 29 Apr 2012)
Log Message:
-----------
WIP btree plus, tests in progress. non terminal page equilibrate, tests ok
Modified Paths:
--------------
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/NonTerminalPage.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusDataManager.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/NonTerminalPageTest.java
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
|
From: <luc...@us...> - 2012-04-29 23:06:22
|
Revision: 3049
http://joafip.svn.sourceforge.net/joafip/?rev=3049&view=rev
Author: luc_peuvrier
Date: 2012-04-29 23:06:16 +0000 (Sun, 29 Apr 2012)
Log Message:
-----------
WIP btree plus: correction to make test pass, kept some problems, not yet stable
Modified Paths:
--------------
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/AbstractPageRecord.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/DataBlock.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/DataBlockPage.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/HeaderPage.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/IDataBlock.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/PageRecord.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusDataManager.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgr.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/DataBlockPageTest.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/mock/MockDataBlock.java
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/AbstractPageRecord.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/AbstractPageRecord.java 2012-04-29 21:13:04 UTC (rev 3048)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/AbstractPageRecord.java 2012-04-29 23:06:16 UTC (rev 3049)
@@ -24,13 +24,13 @@
package net.sf.joafip.btreeplus.entity;
import net.sf.joafip.NotStorableClass;
-import net.sf.joafip.kvstore.record.entity.DataRecordKey;
import net.sf.joafip.kvstore.entity.AbstractFileStorable;
import net.sf.joafip.kvstore.record.entity.DataRecordIdentifier;
+import net.sf.joafip.kvstore.record.entity.DataRecordKey;
import net.sf.joafip.kvstore.record.entity.IDataRecordKey;
import net.sf.joafip.kvstore.record.service.IDataRecordKeyManager;
+import net.sf.joafip.kvstore.record.service.IHeapElementManager;
import net.sf.joafip.kvstore.service.HeapException;
-import net.sf.joafip.kvstore.service.IFileForStorable;
/**
*
@@ -40,16 +40,14 @@
@NotStorableClass
public abstract class AbstractPageRecord extends AbstractFileStorable {
- public AbstractPageRecord(final IFileForStorable fileForStorable,
+ protected final IHeapElementManager heapElementManager;
+
+ public AbstractPageRecord(final IHeapElementManager heapElementManager,
final long positionInFile) {
- super(fileForStorable, positionInFile);
+ super(heapElementManager.getFileForStorable(), positionInFile);
+ this.heapElementManager = heapElementManager;
}
- @Override
- protected void valueChangedAction() throws HeapException {
- // no implementation
- }
-
protected EnumRecordType readRecordType() throws HeapException {
final int typeIdentifier = readByte() & 0xff;
return EnumRecordType.get(typeIdentifier);
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/DataBlock.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/DataBlock.java 2012-04-29 21:13:04 UTC (rev 3048)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/DataBlock.java 2012-04-29 23:06:16 UTC (rev 3049)
@@ -98,6 +98,16 @@
}
@Override
+ public int getSize() {
+ return size;
+ }
+
+ @Override
+ public void setSize(final int size) {
+ this.size = size;
+ }
+
+ @Override
public void setData(final byte[] data) throws HeapException {
System.arraycopy(data, 0, this.data, 0, size = data.length);
setValueIsChangedValueToSave();
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/DataBlockPage.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/DataBlockPage.java 2012-04-29 21:13:04 UTC (rev 3048)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/DataBlockPage.java 2012-04-29 23:06:16 UTC (rev 3049)
@@ -44,7 +44,7 @@
private final int numberOfPage;
- private final int dataBlockDataSize;
+ private final int dataBlockSize;
private final IDataBlock[] dataBlocks;
@@ -63,11 +63,12 @@
public DataBlockPage(final byte bits) {
super();
this.bits = bits;
- dataBlockDataSize = 1 << bits;
- if (dataBlockDataSize > PageConstant.PAGE_SIZE - HEAD_TAIL_SIZE) {
+ final int maxSize = 1 << bits;
+ dataBlockSize = maxSize + 4/* for data size */;
+ if (dataBlockSize > PageConstant.PAGE_SIZE - HEAD_TAIL_SIZE) {
// one data block on one or more pages
numberOfBlock = 1;
- final int totalSize = HEAD_TAIL_SIZE + dataBlockDataSize;
+ final int totalSize = HEAD_TAIL_SIZE + dataBlockSize;
final int n = totalSize >> PageConstant.PAGE_BITS;
if ((totalSize & PageConstant.IN_PAGE_POSITION_MASK) == 0) {
numberOfPage = n;
@@ -82,14 +83,15 @@
numberOfPage = 1;
// numberOfBlock = ((int)PageConstant.PAGE_SIZE - FIX_VALUE_SIZE)
// / dataBlockDataSize;
- numberOfBlock = ((int) PageConstant.PAGE_SIZE - HEAD_TAIL_SIZE) >> bits;
+ numberOfBlock = ((int) PageConstant.PAGE_SIZE - HEAD_TAIL_SIZE)
+ / dataBlockSize;
}
final int minSize = bits == PageConstant.MIN_DATA_BLOCK_BITS ? 0
: ((1 << (bits - 1)) + 1);
dataBlocks = new DataBlock[numberOfBlock];
for (int dataBlockIndex = 0; dataBlockIndex < numberOfBlock; dataBlockIndex++) {
dataBlocks[dataBlockIndex] = new DataBlock(this, dataBlockIndex,
- bits, minSize, dataBlockDataSize);
+ bits, minSize, maxSize);
}
}
@@ -115,9 +117,7 @@
@Override
public int getByteSize() {
- return numberOfPage * (int) PageConstant.PAGE_SIZE;
- // FIXMELUC ________use <<
- // return numberOfPage <<PageConstant.PAGE_BITS
+ return numberOfPage << PageConstant.PAGE_BITS;
}
public int getNumberOfBlock() {
@@ -129,20 +129,20 @@
}
public IDataBlock getDataBlock(final long dataBlockPosition) {
- // >> bits as divide by data block size
- final int index = ((int) (dataBlockPosition - getPositionInFile()) - HEAD_SIZE) >> bits;
+ final int index = ((int) (dataBlockPosition - getPositionInFile()) - HEAD_SIZE)
+ / dataBlockSize;
return dataBlocks[index];
}
public long getPositionInFile(final int index) {
- return getPositionInFile() + HEAD_SIZE + (index << bits);
+ return getPositionInFile() + HEAD_SIZE + index * dataBlockSize;
}
public void setAllFree() throws HeapException {
- long nextPosition = getPositionInFile() + HEAD_SIZE + dataBlockDataSize;
+ long nextPosition = getPositionInFile() + HEAD_SIZE + dataBlockSize;
for (int index = 0; index < dataBlocks.length - 1; index++) {
dataBlocks[index].setNextFreeDataBlockPositionOfFree(nextPosition);
- nextPosition += dataBlockDataSize;
+ nextPosition += dataBlockSize;
}
dataBlocks[dataBlocks.length - 1]
.setNextFreeDataBlockPositionOfFree(-1L);
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/HeaderPage.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/HeaderPage.java 2012-04-29 21:13:04 UTC (rev 3048)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/HeaderPage.java 2012-04-29 23:06:16 UTC (rev 3049)
@@ -26,8 +26,8 @@
import java.util.Arrays;
import net.sf.joafip.NotStorableClass;
+import net.sf.joafip.kvstore.record.service.IHeapElementManager;
import net.sf.joafip.kvstore.service.HeapException;
-import net.sf.joafip.kvstore.service.IFileForStorable;
/**
*
@@ -48,10 +48,15 @@
private long nextDataRecordIdentifier;
- public HeaderPage(final IFileForStorable fileForStorable) {
- super(fileForStorable, 0L);
+ public HeaderPage(final IHeapElementManager heapElementManager) {
+ super(heapElementManager, 0L);
}
+ @Override
+ protected void valueChangedAction() throws HeapException {
+ // no implementation
+ }
+
public long getFileSizeAsNumberOfPage() {
return fileSizeAsNumberOfPage;
}
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/IDataBlock.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/IDataBlock.java 2012-04-29 21:13:04 UTC (rev 3048)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/IDataBlock.java 2012-04-29 23:06:16 UTC (rev 3049)
@@ -70,4 +70,8 @@
LeafPage getParentLeafPage();
int getIndexInLeafPage();
+
+ int getSize();
+
+ void setSize(int size);
}
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/PageRecord.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/PageRecord.java 2012-04-29 21:13:04 UTC (rev 3048)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/PageRecord.java 2012-04-29 23:06:16 UTC (rev 3049)
@@ -25,8 +25,8 @@
import net.sf.joafip.NotStorableClass;
import net.sf.joafip.kvstore.record.entity.DataRecordIdentifier;
+import net.sf.joafip.kvstore.record.service.IHeapElementManager;
import net.sf.joafip.kvstore.service.HeapException;
-import net.sf.joafip.kvstore.service.IFileForStorable;
/**
*
@@ -45,23 +45,31 @@
/**
* creation for reading
*
- * @param fileForStorable
+ * @param heapElementManager
* @param pageNumber
*/
- public PageRecord(final IFileForStorable fileForStorable,
+ public PageRecord(final IHeapElementManager heapElementManager,
final long pageNumber) {
- super(fileForStorable, pageNumber << PageConstant.PAGE_BITS);
+ super(heapElementManager, pageNumber << PageConstant.PAGE_BITS);
this.pageNumber = pageNumber;
}
- public PageRecord(final IFileForStorable fileForStorable,
+ public PageRecord(final IHeapElementManager heapElementManager,
final IPageRecordable pageRecordable, final long pageNumber) {
- super(fileForStorable, pageNumber << PageConstant.PAGE_BITS);
+ super(heapElementManager, pageNumber << PageConstant.PAGE_BITS);
this.pageNumber = pageNumber;
this.pageRecordable = pageRecordable;
this.recordType = pageRecordable.getRecordType();
}
+ @Override
+ protected void valueChangedAction() throws HeapException {
+ /*
+ * is to be saved
+ */
+ heapElementManager.appendHeapFileRecord(this);
+ }
+
public EnumRecordType getRecordType() {
return recordType;
}
@@ -240,6 +248,7 @@
* PageConstant.PAGE_SIZE;
final IDataBlock[] dataBlocks = dataBlockPage.getDataBlocks();
for (IDataBlock dataBlock : dataBlocks) {
+ writeInteger(dataBlock.getSize());
writeBytes(dataBlock.getDataHolder());
}
writeCrc32();
@@ -258,6 +267,7 @@
}
final IDataBlock[] dataBlocks = dataBlockPage.getDataBlocks();
for (IDataBlock dataBlock : dataBlocks) {
+ dataBlock.setSize(readInteger());
readBytes(dataBlock.getDataHolder());
}
readAndCheckCrc32();
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusDataManager.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusDataManager.java 2012-04-29 21:13:04 UTC (rev 3048)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusDataManager.java 2012-04-29 23:06:16 UTC (rev 3049)
@@ -513,7 +513,7 @@
page = null;
} else {
page = root;
- while (!EnumRecordType.LEAF_PAGE.equals(page)) {
+ while (!EnumRecordType.LEAF_PAGE.equals(page.getRecordType())) {
final NonTerminalPage nonTerminalPage = (NonTerminalPage) page;
final int index = nonTerminalPage
.getIndex(dataRecordIdentifier);
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgr.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgr.java 2012-04-29 21:13:04 UTC (rev 3048)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgr.java 2012-04-29 23:06:16 UTC (rev 3049)
@@ -67,7 +67,7 @@
throws HeapException {
super();
this.heapElementManager = heapElementManager;
- header = new HeaderPage(heapElementManager.getFileForStorable());
+ header = new HeaderPage(heapElementManager);
heapElementManager.setHeapRecordFactory(this);
heapElementManager.setHeapHeader(header);
fileForStorable = heapElementManager.getFileForStorable();
@@ -123,7 +123,7 @@
final long positionInFile) throws HeapException {
// ASSERTX
assert (positionInFile & PageConstant.IN_PAGE_POSITION_MASK) == 0;
- return new PageRecord(fileForStorable,
+ return new PageRecord(heapElementManager,
(int) (positionInFile >> PageConstant.PAGE_BITS));
}
@@ -230,7 +230,9 @@
final IDataBlock dataBlock) throws HeapException {
final LeafPage leafPage = new LeafPage(1);
appendPageRecordable(leafPage);
- leafPage.setDataBlock(0, dataBlock);
+ // leafPage.setDataBlock(0, dataBlock);
+ leafPage.setEntry(0, dataBlock.getPositionInFile(),
+ dataRecordIdentifier);
leafPage.setNext(-1L);
leafPage.updateByteSize();
leafPage.setValueIsChangedValueToSave();
@@ -314,7 +316,7 @@
.getPageRecordable();
header.setPageNumberOfFirstFreePage(freePage.getNextFreePage());
}
- final IPageRecord pageRecord = new PageRecord(fileForStorable,
+ final IPageRecord pageRecord = new PageRecord(heapElementManager,
pageRecordable, pageNumber);
if (newPage) {
header.setFileSizeAsNumberOfPage(pageNumber
@@ -336,7 +338,7 @@
final long freePageNumber = header.getPageNumberOfFirstFreePage();
FreePage freePage = new FreePage(freePageNumber);
final long newFreePageNumber = pageRecord.getPageNumber();
- PageRecord pageRecord2 = new PageRecord(fileForStorable, freePage,
+ PageRecord pageRecord2 = new PageRecord(heapElementManager, freePage,
newFreePageNumber);
freePage.setPageRecord(pageRecord2);
freePage.setValueIsChangedValueToSave();
Modified: trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/DataBlockPageTest.java
===================================================================
--- trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/DataBlockPageTest.java 2012-04-29 21:13:04 UTC (rev 3048)
+++ trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/DataBlockPageTest.java 2012-04-29 23:06:16 UTC (rev 3049)
@@ -60,7 +60,7 @@
dataBlockPage.setPageRecord(pageRecord);
final int numberOfBlock = dataBlockPage.getNumberOfBlock();
- final int blockByteSize = 1 << bits;
+ final int blockByteSize = (1 << bits) + 4/* int for data length */;
final long dataAreaSize = PageConstant.PAGE_SIZE
- DataBlockPage.HEAD_SIZE;
final int numberOfPage = (int) ((blockByteSize <= dataAreaSize) ? 1
Modified: trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/mock/MockDataBlock.java
===================================================================
--- trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/mock/MockDataBlock.java 2012-04-29 21:13:04 UTC (rev 3048)
+++ trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/mock/MockDataBlock.java 2012-04-29 23:06:16 UTC (rev 3049)
@@ -115,4 +115,13 @@
public int getIndexInLeafPage() {
return 0;
}
+
+ @Override
+ public int getSize() {
+ return 0;
+ }
+
+ @Override
+ public void setSize(final int size) {
+ }
}
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
|
From: <luc...@us...> - 2012-04-29 23:06:22
|
Revision: 3049
http://joafip.svn.sourceforge.net/joafip/?rev=3049&view=rev
Author: luc_peuvrier
Date: 2012-04-29 23:06:16 +0000 (Sun, 29 Apr 2012)
Log Message:
-----------
WIP btree plus: correction to make test pass, kept some problems, not yet stable
Modified Paths:
--------------
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/AbstractPageRecord.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/DataBlock.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/DataBlockPage.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/HeaderPage.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/IDataBlock.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/PageRecord.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusDataManager.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgr.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/DataBlockPageTest.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/mock/MockDataBlock.java
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
|
From: <luc...@us...> - 2012-05-03 03:37:49
|
Revision: 3064
http://joafip.svn.sourceforge.net/joafip/?rev=3064&view=rev
Author: luc_peuvrier
Date: 2012-05-03 03:37:42 +0000 (Thu, 03 May 2012)
Log Message:
-----------
byte size computing optimization in case of long key usage
refactoring best name
Modified Paths:
--------------
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/AbstractElement.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/AbstractPageRecord.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/LeafPage.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/NonTerminalPage.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/PageRecord.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusDataManager.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgr.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/LeafPageTest.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/NonTerminalPageTest.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgrTest.java
Added Paths:
-----------
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/AbstractNodePage.java
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
|
From: <luc...@us...> - 2012-05-03 03:37:49
|
Revision: 3064
http://joafip.svn.sourceforge.net/joafip/?rev=3064&view=rev
Author: luc_peuvrier
Date: 2012-05-03 03:37:42 +0000 (Thu, 03 May 2012)
Log Message:
-----------
byte size computing optimization in case of long key usage
refactoring best name
Modified Paths:
--------------
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/AbstractElement.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/AbstractPageRecord.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/LeafPage.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/NonTerminalPage.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/PageRecord.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusDataManager.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgr.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/LeafPageTest.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/NonTerminalPageTest.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgrTest.java
Added Paths:
-----------
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/AbstractNodePage.java
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/AbstractElement.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/AbstractElement.java 2012-05-03 03:36:50 UTC (rev 3063)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/AbstractElement.java 2012-05-03 03:37:42 UTC (rev 3064)
@@ -24,7 +24,6 @@
package net.sf.joafip.btreeplus.entity;
import net.sf.joafip.NotStorableClass;
-import net.sf.joafip.kvstore.record.entity.DataRecordIdentifier;
import net.sf.joafip.kvstore.service.HeapException;
/**
@@ -69,13 +68,4 @@
public long getPreviousRecordPositionInFile() throws HeapException {
return pageRecord.getPreviousRecordPositionInFile();
}
-
- protected int entrySize(final DataRecordIdentifier key) {
- int entryByteSize = 8/* long size for pointer */+ 8/* long size for value */;
- final int dataSize = key.getKeyDataSize();
- if (dataSize != 0) {
- entryByteSize += 4/* int size for data size */+ dataSize;
- }
- return entryByteSize;
- }
}
Added: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/AbstractNodePage.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/AbstractNodePage.java (rev 0)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/AbstractNodePage.java 2012-05-03 03:37:42 UTC (rev 3064)
@@ -0,0 +1,54 @@
+/*
+ * Copyright 2012 Luc Peuvrier
+ * All rights reserved.
+ *
+ * This file is a part of JOAFIP.
+ *
+ * JOAFIP is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License.
+ *
+ * Licensed under the GNU LESSER GENERAL PUBLIC LICENSE
+ * Licensed under the LGPL License, Version 3, 29 June 2007 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.gnu.org/licenses/lgpl.html
+ *
+ * JOAFIP is distributed in the hope that it will be useful, but
+ * 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 net.sf.joafip.btreeplus.entity;
+
+import net.sf.joafip.NotStorableClass;
+import net.sf.joafip.kvstore.record.entity.DataRecordIdentifier;
+
+/**
+ *
+ * @author luc peuvrier
+ *
+ */
+@NotStorableClass
+public abstract class AbstractNodePage extends AbstractElement {
+
+ protected final boolean longKey;
+
+ public AbstractNodePage(final boolean longKey) {
+ super();
+ this.longKey = longKey;
+ }
+
+ protected int entrySize(final DataRecordIdentifier key) {
+ int entryByteSize = 8/* long size for pointer */+ 8/* long size for value */;
+ if (!longKey) {
+ final int dataSize = key.getKeyDataSize();
+ if (dataSize != 0) {
+ entryByteSize += 4/* int size for data size */+ dataSize;
+ }
+ }
+ return entryByteSize;
+ }
+}
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/AbstractPageRecord.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/AbstractPageRecord.java 2012-05-03 03:36:50 UTC (rev 3063)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/AbstractPageRecord.java 2012-05-03 03:37:42 UTC (rev 3064)
@@ -58,14 +58,14 @@
writeByte((byte) recordType.getTypeIdentifier());
}
- private IDataRecordKeyManager dataRecordKeyManager;
-
protected DataRecordIdentifier readKey() throws HeapException {
final long value = readLong();
final DataRecordIdentifier dataRecordIdentifier;
if (value == -1) {
final int keySize = readInteger();
final byte[] keyData = readBytes(keySize);
+ final IDataRecordKeyManager dataRecordKeyManager = heapElementManager
+ .getDataRecordKeyManager();
final IDataRecordKey dataRecordKey = new DataRecordKey(
dataRecordKeyManager, keyData);
dataRecordIdentifier = new DataRecordIdentifier(dataRecordKey);
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/LeafPage.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/LeafPage.java 2012-05-03 03:36:50 UTC (rev 3063)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/LeafPage.java 2012-05-03 03:37:42 UTC (rev 3064)
@@ -35,7 +35,7 @@
*
*/
@NotStorableClass
-public class LeafPage extends AbstractElement implements ILeafPage {
+public class LeafPage extends AbstractNodePage implements ILeafPage {
public static int HEAD_TAIL_SIZE =
/**/8/* byte size for previous record position */+
@@ -60,13 +60,13 @@
private int index;
- public LeafPage() {
- this(0);
+ public LeafPage(final boolean longKey) {
+ this(0, longKey);
updateByteSize();
}
- public LeafPage(final int numberOfKeyEntries) {
- super();
+ public LeafPage(final int numberOfKeyEntries, final boolean longKey) {
+ super(longKey);
this.numberOfKeyEntries = numberOfKeyEntries;
keys = new DataRecordIdentifier[numberOfKeyEntries];
dataBlockPosition = new long[numberOfKeyEntries];
@@ -74,8 +74,9 @@
}
public LeafPage(final int numberOfKeyEntries,
- final long[] dataBlockPosition, final DataRecordIdentifier[] keys) {
- super();
+ final long[] dataBlockPosition, final DataRecordIdentifier[] keys,
+ final boolean longKey) {
+ super(longKey);
assert numberOfKeyEntries == dataBlockPosition.length
&& numberOfKeyEntries == keys.length;
this.numberOfKeyEntries = numberOfKeyEntries;
@@ -153,10 +154,16 @@
}
private int computeByteSize() {
- int xbyteSize = HEAD_TAIL_SIZE;
- // FIXMELUC ________speedup if long value key
- for (int index = 0; index < numberOfKeyEntries; index++) {
- xbyteSize += entrySize(keys[index]);
+ int xbyteSize;
+ if (longKey) {
+ // <<4 for *16: 8 (long size for pointer) + 8 (long size for value)
+ xbyteSize = HEAD_TAIL_SIZE + (numberOfKeyEntries << 4);
+ } else {
+ xbyteSize = HEAD_TAIL_SIZE;
+ // FIXMELUC ________speedup if long value key
+ for (int index = 0; index < numberOfKeyEntries; index++) {
+ xbyteSize += entrySize(keys[index]);
+ }
}
return xbyteSize;
}
@@ -253,7 +260,7 @@
final LeafPage newLeafPage = new LeafPage(
newLeafPageNumberOfKeyEntries, newLeafPageDataBlockPosition,
- newLeafPageKeys);
+ newLeafPageKeys, longKey);
newLeafPage.setParentPage(getParentPage(), getInParentIndex() + 1);
dataBlockPosition = newDataBlockPosition;
keys = newKeys;
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/NonTerminalPage.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/NonTerminalPage.java 2012-05-03 03:36:50 UTC (rev 3063)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/NonTerminalPage.java 2012-05-03 03:37:42 UTC (rev 3064)
@@ -35,7 +35,7 @@
*
*/
@NotStorableClass
-public class NonTerminalPage extends AbstractElement implements
+public class NonTerminalPage extends AbstractNodePage implements
INonTerminalPage {
public static int HEAD_TAIL_SIZE =
@@ -59,13 +59,13 @@
private DataRecordIdentifier middleKey;
- public NonTerminalPage() {
- this(0);
+ public NonTerminalPage(final boolean longKey) {
+ this(0, longKey);
updateByteSize();
}
- public NonTerminalPage(final int numberOfKeyEntries) {
- super();
+ public NonTerminalPage(final int numberOfKeyEntries, final boolean longKey) {
+ super(longKey);
this.numberOfKeyEntries = numberOfKeyEntries;
keys = new DataRecordIdentifier[numberOfKeyEntries];
pagePositions = new long[numberOfKeyEntries + 1];
@@ -73,8 +73,9 @@
}
public NonTerminalPage(final int numberOfKeyEntries,
- final DataRecordIdentifier[] keys, final long[] pagePosition) {
- super();
+ final DataRecordIdentifier[] keys, final long[] pagePosition,
+ final boolean longKey) {
+ super(longKey);
assert numberOfKeyEntries == keys.length
&& numberOfKeyEntries + 1 == pagePosition.length;
this.numberOfKeyEntries = numberOfKeyEntries;
@@ -151,10 +152,16 @@
}
private int computeByteSize() {
- int xbyteSize = HEAD_TAIL_SIZE;
- // FIXMELUC ________speedup if long value key
- for (int index = 0; index < numberOfKeyEntries; index++) {
- xbyteSize += entrySize(keys[index]);
+ int xbyteSize;
+ if (longKey) {
+ // <<4 for *16: 8 (long size for pointer) + 8 (long size for value)
+ xbyteSize = HEAD_TAIL_SIZE + (numberOfKeyEntries << 4);
+ } else {
+ xbyteSize = HEAD_TAIL_SIZE;
+ // FIXMELUC ________speedup if long value key
+ for (int index = 0; index < numberOfKeyEntries; index++) {
+ xbyteSize += entrySize(keys[index]);
+ }
}
return xbyteSize;
}
@@ -287,7 +294,7 @@
pagePositions, splitIndex + 1, numberOfKeyEntries + 1);
final INonTerminalPage nonTerminalPage = new NonTerminalPage(
newNonTerminalPageNumberOfKeyEntries, newNonTerminalKeys,
- newNonTerminalPagePosition);
+ newNonTerminalPagePosition, longKey);
keys = newKeys;
pagePositions = newPagePosition;
numberOfKeyEntries = newNumberOfKeyEntries;
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/PageRecord.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/PageRecord.java 2012-05-03 03:36:50 UTC (rev 3063)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/PageRecord.java 2012-05-03 03:37:42 UTC (rev 3064)
@@ -44,6 +44,8 @@
private long previousRecordPositionInFile;
+ private final boolean longKey;
+
/**
* creation for reading
*
@@ -55,6 +57,7 @@
super(heapElementManager, pageNumber << PageConstant.PAGE_BITS);
this.pageNumber = pageNumber;
this.previousRecordPositionInFile = -1L;
+ longKey = heapElementManager.getDataRecordKeyManager() == null;
}
public PageRecord(final IHeapElementManager heapElementManager,
@@ -65,6 +68,7 @@
this.pageNumber = pageNumber;
this.pageRecordable = pageRecordable;
this.recordType = pageRecordable.getRecordType();
+ longKey = heapElementManager.getDataRecordKeyManager() == null;
}
@Override
@@ -206,7 +210,7 @@
private void unmarshallNonTerminalPage() throws HeapException {
final int numberOfKeyEntries = readInteger();
final NonTerminalPage nonTerminalPage = new NonTerminalPage(
- numberOfKeyEntries);
+ numberOfKeyEntries, longKey);
nonTerminalPage.setPageRecord(this);
for (int index = 0; index < numberOfKeyEntries; index++) {
final long pagePointer = readLong();
@@ -235,7 +239,7 @@
private void unmarshallLeafPage() throws HeapException {
final int numberOfKeyEntries = readInteger();
- final LeafPage leafPage = new LeafPage(numberOfKeyEntries);
+ final LeafPage leafPage = new LeafPage(numberOfKeyEntries, longKey);
leafPage.setPageRecord(this);
for (int index = 0; index < numberOfKeyEntries; index++) {
final DataRecordIdentifier key = readKey();
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusDataManager.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusDataManager.java 2012-05-03 03:36:50 UTC (rev 3063)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusDataManager.java 2012-05-03 03:37:42 UTC (rev 3064)
@@ -85,9 +85,9 @@
}
@Override
- public void setDataRecordKeyComparator(
- IDataRecordKeyManager dataRecordKeyComparator) throws HeapException {
- btreePlusElementMgr.setDataRecordKeyManager(dataRecordKeyComparator);
+ public void setDataRecordKeyManager(
+ IDataRecordKeyManager dataRecordKeyManager) throws HeapException {
+ btreePlusElementMgr.setDataRecordKeyManager(dataRecordKeyManager);
}
@Override
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgr.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgr.java 2012-05-03 03:36:50 UTC (rev 3063)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgr.java 2012-05-03 03:37:42 UTC (rev 3064)
@@ -63,6 +63,8 @@
private final IFileForStorable fileForStorable;
+ private final boolean longKey;
+
public BtreePlusElementMgr(final IHeapElementManager heapElementManager)
throws HeapException {
super();
@@ -77,6 +79,7 @@
+ " and file cache page size is "
+ fileForStorable.getCachePageSize());
}
+ longKey = heapElementManager.getDataRecordKeyManager() == null;
}
public void setDataRecordKeyManager(
@@ -228,7 +231,7 @@
public void newRootLeafPage(
final DataRecordIdentifier dataRecordIdentifier,
final IDataBlock dataBlock) throws HeapException {
- final LeafPage leafPage = new LeafPage(1);
+ final LeafPage leafPage = new LeafPage(1, longKey);
appendPageRecordable(leafPage);
// leafPage.setDataBlock(0, dataBlock);
leafPage.setEntry(0, dataBlock.getPositionInFile(),
@@ -241,7 +244,7 @@
public void newRootNonTerminalPage(final LeafPage leftLeafPage,
final LeafPage rightLeafPage) throws HeapException {
- final NonTerminalPage nonTerminalPage = new NonTerminalPage(1);
+ final NonTerminalPage nonTerminalPage = new NonTerminalPage(1, longKey);
nonTerminalPage.setEntry(0, leftLeafPage.getPositionInFile(),
leftLeafPage.getLastKey());
nonTerminalPage.setEntry(1, rightLeafPage.getPositionInFile(), null);
@@ -255,7 +258,7 @@
final INonTerminalPage leftNonTerminalPage,
final DataRecordIdentifier middleKey,
final INonTerminalPage rightNonTerminalPage) throws HeapException {
- final NonTerminalPage nonTerminalPage = new NonTerminalPage(1);
+ final NonTerminalPage nonTerminalPage = new NonTerminalPage(1, longKey);
nonTerminalPage.setEntry(0, leftNonTerminalPage.getPositionInFile(),
middleKey);
nonTerminalPage.setEntry(1, rightNonTerminalPage.getPositionInFile(),
Modified: trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/LeafPageTest.java
===================================================================
--- trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/LeafPageTest.java 2012-05-03 03:36:50 UTC (rev 3063)
+++ trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/LeafPageTest.java 2012-05-03 03:37:42 UTC (rev 3064)
@@ -53,7 +53,7 @@
}
public void testCreation() {
- LeafPage leafPage = new LeafPage();
+ LeafPage leafPage = new LeafPage(true);
leafPage.setPageRecord(PAGE_RECORD);
assertEquals("must be empty", 0, leafPage.getNumberOfKeyEntries());
assertEquals("must be one page", 1, leafPage.getNumberOfPage());
@@ -63,7 +63,7 @@
}
public void testAdd() throws HeapException {
- LeafPage leafPage = new LeafPage();
+ LeafPage leafPage = new LeafPage(true);
leafPage.setPageRecord(PAGE_RECORD);
addToLeafPage(leafPage, 1000/* position */, 10/* key value */, 10, 1);
checkContent(leafPage,
@@ -118,7 +118,7 @@
}
public void testSetDataBlock() throws HeapException {
- final LeafPage leafPage = new LeafPage(1);
+ final LeafPage leafPage = new LeafPage(1, true);
leafPage.setPageRecord(PAGE_RECORD);
final MockDataBlock dataBlock = new MockDataBlock();
final long position = 1000;
@@ -130,7 +130,7 @@
}
public void testSetEntry() throws HeapException {
- final LeafPage leafPage = new LeafPage(1);
+ final LeafPage leafPage = new LeafPage(1, true);
leafPage.setPageRecord(PAGE_RECORD);
final int index = 0;
final long pagePointer = 2000;
@@ -144,7 +144,7 @@
}
public void testSetParentPage() throws HeapException {
- final LeafPage leafPage = new LeafPage();
+ final LeafPage leafPage = new LeafPage(true);
leafPage.setPageRecord(PAGE_RECORD);
final IPageRecordable parentPage = new MockPageRecordable();
final int inParentIndex = 5;
@@ -155,7 +155,7 @@
}
public void testSetNext() throws HeapException {
- final LeafPage leafPage = new LeafPage();
+ final LeafPage leafPage = new LeafPage(true);
leafPage.setPageRecord(PAGE_RECORD);
final long next = 5000;
leafPage.setNext(next);
@@ -163,7 +163,7 @@
}
public void testSplit1() throws HeapException {
- final LeafPage leafPage = new LeafPage();
+ final LeafPage leafPage = new LeafPage(true);
leafPage.setPageRecord(PAGE_RECORD);
final int maxNumberOfEntries = maxNumberOfEntries();
int count = 0;
@@ -182,7 +182,7 @@
}
public void testSplit2() throws HeapException {
- final LeafPage leafPage = new LeafPage();
+ final LeafPage leafPage = new LeafPage(true);
leafPage.setPageRecord(PAGE_RECORD);
final int maxNumberOfEntries = maxNumberOfEntries();
int count = 1;
@@ -223,7 +223,7 @@
}
public void testRemove() throws HeapException {
- final LeafPage leafPage = new LeafPage();
+ final LeafPage leafPage = new LeafPage(true);
addToLeafPage(leafPage,
/**/new int[] { 5, 7, 10, 15, 17 },
/**/new long[] { 2000, 4000, 1000, 3000, 5000 });
@@ -245,8 +245,8 @@
}
public void testEquilibrateMerge() throws HeapException {
- final LeafPage leftLeafPage = new LeafPage();
- final LeafPage rightLeafPage = new LeafPage();
+ final LeafPage leftLeafPage = new LeafPage(true);
+ final LeafPage rightLeafPage = new LeafPage(true);
addToLeafPage(leftLeafPage,
/**/new int[] { 5, 7, 10, 15, 17 },
/**/new long[] { 2000, 4000, 1000, 3000, 5000 });
@@ -261,10 +261,10 @@
}
public void testEquilibrateRightToLeft() throws HeapException {
- final LeafPage leftLeafPage = new LeafPage();
+ final LeafPage leftLeafPage = new LeafPage(true);
addToLeafPage(leftLeafPage, createKeys(1, 128 + 32),
createPointers(1000, 128 + 32));
- final LeafPage rightLeafPage = new LeafPage();
+ final LeafPage rightLeafPage = new LeafPage(true);
addToLeafPage(rightLeafPage, createKeys(1 + 128 + 32, 128 + 64),
createPointers(1000 + 128 + 32, 128 + 64));
assertFalse("must not merge", leftLeafPage.equilibrate(rightLeafPage));
@@ -275,10 +275,10 @@
}
public void testEquilibrateLeftToRight() throws HeapException {
- final LeafPage leftLeafPage = new LeafPage();
+ final LeafPage leftLeafPage = new LeafPage(true);
addToLeafPage(leftLeafPage, createKeys(1, 128 + 64),
createPointers(1000, 128 + 64));
- final LeafPage rightLeafPage = new LeafPage();
+ final LeafPage rightLeafPage = new LeafPage(true);
addToLeafPage(rightLeafPage, createKeys(1 + 128 + 64, 128 + 32),
createPointers(1000 + 128 + 64, 128 + 32));
assertFalse("must not merge", leftLeafPage.equilibrate(rightLeafPage));
Modified: trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/NonTerminalPageTest.java
===================================================================
--- trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/NonTerminalPageTest.java 2012-05-03 03:36:50 UTC (rev 3063)
+++ trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/NonTerminalPageTest.java 2012-05-03 03:37:42 UTC (rev 3064)
@@ -53,7 +53,7 @@
}
public void testCreation() {
- final NonTerminalPage nonTerminalPage = new NonTerminalPage();
+ final NonTerminalPage nonTerminalPage = new NonTerminalPage(true);
assertEquals("must be empty", 0,
nonTerminalPage.getNumberOfKeyEntries());
assertEquals("must be one page", 1, nonTerminalPage.getNumberOfPage());
@@ -65,7 +65,7 @@
public void testAddLeafPage() throws HeapException {
// A 10 B
- final NonTerminalPage nonTerminalPage = new NonTerminalPage(1);
+ final NonTerminalPage nonTerminalPage = new NonTerminalPage(1, true);
nonTerminalPage.setPageRecord(PAGE_RECORD);
final MockLeafPage leafPageA = newMockLeafPage();
final long pageAPositionInFile = 1000;
@@ -172,7 +172,7 @@
public void testAddLeafPageNeedSplit() throws HeapException {
// A 10 B
- final NonTerminalPage nonTerminalPage = new NonTerminalPage(1);
+ final NonTerminalPage nonTerminalPage = new NonTerminalPage(1, true);
nonTerminalPage.setPageRecord(PAGE_RECORD);
final MockLeafPage leafPageA = newMockLeafPage();
final long pageAPositionInFile = 1000;
@@ -203,7 +203,7 @@
public void testAddNonTerminalPage() throws HeapException {
// A 10 B
- final NonTerminalPage nonTerminalPage = new NonTerminalPage(1);
+ final NonTerminalPage nonTerminalPage = new NonTerminalPage(1, true);
nonTerminalPage.setPageRecord(PAGE_RECORD);
final MockNonTerminalPage pageA = newMockNonTerminalPage();
final long pageAPositionInFile = 1000;
@@ -307,7 +307,7 @@
public void testAddNonTerminalPageNeedSplit() throws HeapException {
// A 10 B
- final NonTerminalPage nonTerminalPage = new NonTerminalPage(1);
+ final NonTerminalPage nonTerminalPage = new NonTerminalPage(1, true);
nonTerminalPage.setPageRecord(PAGE_RECORD);
final MockNonTerminalPage pageA = newMockNonTerminalPage();
final long pageAPositionInFile = 1000;
@@ -382,7 +382,7 @@
private NonTerminalPage createFilledNonterminalPage(
final int numberOfEntries) throws HeapException {
final NonTerminalPage nonTerminalPage = new NonTerminalPage(
- numberOfEntries);
+ numberOfEntries, true);
nonTerminalPage.setPageRecord(PAGE_RECORD);
for (int index = 0; index < numberOfEntries; index++) {
nonTerminalPage.setEntry(index, index * 1000,
@@ -393,8 +393,8 @@
}
public void testSetParentPage() throws HeapException {
- final NonTerminalPage nonTerminalPage = new NonTerminalPage();
- final IPageRecordable parentPage = new NonTerminalPage();
+ final NonTerminalPage nonTerminalPage = new NonTerminalPage(true);
+ final IPageRecordable parentPage = new NonTerminalPage(true);
nonTerminalPage.setParentPage(parentPage, 10);
assertSame("bad parent page", parentPage,
nonTerminalPage.getParentPage());
@@ -423,8 +423,8 @@
}
public void testEquilibrateMerge() throws HeapException {
- final NonTerminalPage leftPage = new NonTerminalPage(5);
- final NonTerminalPage rightPage = new NonTerminalPage(5);
+ final NonTerminalPage leftPage = new NonTerminalPage(5, true);
+ final NonTerminalPage rightPage = new NonTerminalPage(5, true);
addToNonTerminalPage(leftPage,
/**/new int[] { 5, 7, 10, 15, 17 },
/**/new long[] { 2000, 4000, 1000, 3000, 5000, 6000 });
@@ -442,8 +442,8 @@
}
public void testEquilibrateRightToLeft() throws HeapException {
- final NonTerminalPage leftPage = new NonTerminalPage(128 + 32);
- final NonTerminalPage rightPage = new NonTerminalPage(128 + 64);
+ final NonTerminalPage leftPage = new NonTerminalPage(128 + 32, true);
+ final NonTerminalPage rightPage = new NonTerminalPage(128 + 64, true);
addToNonTerminalPage(leftPage, createKeys(1, 128 + 32),
createPointers(1, 128 + 32 + 1));
leftPage.updateByteSize();
@@ -459,8 +459,8 @@
}
public void testEquilibrateLeftToRight() throws HeapException {
- final NonTerminalPage leftPage = new NonTerminalPage(128 + 64);
- final NonTerminalPage rightPage = new NonTerminalPage(128 + 32);
+ final NonTerminalPage leftPage = new NonTerminalPage(128 + 64, true);
+ final NonTerminalPage rightPage = new NonTerminalPage(128 + 32, true);
addToNonTerminalPage(leftPage, createKeys(1, 128 + 64),
createPointers(1, 128 + 64 + 1));
leftPage.updateByteSize();
Modified: trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgrTest.java
===================================================================
--- trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgrTest.java 2012-05-03 03:36:50 UTC (rev 3063)
+++ trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgrTest.java 2012-05-03 03:37:42 UTC (rev 3064)
@@ -99,7 +99,7 @@
public void testAppendPageRecordable() throws HeapException {
btreePlusElementMgr.openTransaction();
- IPageRecordable pageRecordable = new LeafPage();
+ IPageRecordable pageRecordable = new LeafPage(true);
assertNull(MUST_BE_NOT_STORED, pageRecordable.getPageRecord());
btreePlusElementMgr.appendPageRecordable(pageRecordable);
pageRecordable.setValueIsChangedValueToSave();
@@ -110,7 +110,7 @@
assertEquals(BAD_LAST_RECORD_POSITION, PageConstant.PAGE_SIZE * 1,
btreePlusElementMgr.getLastRecordPositionInFile());
- pageRecordable = new NonTerminalPage();
+ pageRecordable = new NonTerminalPage(true);
assertNull(MUST_BE_NOT_STORED, pageRecordable.getPageRecord());
btreePlusElementMgr.appendPageRecordable(pageRecordable);
pageRecordable.setValueIsChangedValueToSave();
@@ -130,7 +130,7 @@
0) };
final long[] pagePosition = new long[] { 0, 1 };
pageRecordable = new NonTerminalPage(numberOfKeyEntries, keys,
- pagePosition);
+ pagePosition, true);
assertNull(MUST_BE_NOT_STORED, pageRecordable.getPageRecord());
btreePlusElementMgr.appendPageRecordable(pageRecordable);
pageRecordable.setValueIsChangedValueToSave();
@@ -169,14 +169,14 @@
btreePlusElementMgr.openTransaction();
assertEquals("must not has free page", -1, getHeapHeader()
.getPageNumberOfFirstFreePage());
- IPageRecordable pageRecordable = new LeafPage();
+ IPageRecordable pageRecordable = new LeafPage(true);
btreePlusElementMgr.appendPageRecordable(pageRecordable);
pageRecordable.setValueIsChangedValueToSave();
- pageRecordable = new LeafPage();
+ pageRecordable = new LeafPage(true);
btreePlusElementMgr.appendPageRecordable(pageRecordable);
pageRecordable.setValueIsChangedValueToSave();
final long pageNumber = pageRecordable.getPageRecord().getPageNumber();
- pageRecordable = new LeafPage();
+ pageRecordable = new LeafPage(true);
btreePlusElementMgr.appendPageRecordable(pageRecordable);
pageRecordable.setValueIsChangedValueToSave();
btreePlusElementMgr.closeTransaction();
@@ -193,7 +193,7 @@
btreePlusElementMgr.openTransaction();
assertEquals("must has free page", pageNumber, getHeapHeader()
.getPageNumberOfFirstFreePage());
- pageRecordable = new LeafPage();
+ pageRecordable = new LeafPage(true);
btreePlusElementMgr.appendPageRecordable(pageRecordable);
pageRecordable.setValueIsChangedValueToSave();
final long pageNumber2 = pageRecordable.getPageRecord().getPageNumber();
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
|
From: <luc...@us...> - 2012-05-03 04:01:35
|
Revision: 3065
http://joafip.svn.sourceforge.net/joafip/?rev=3065&view=rev
Author: luc_peuvrier
Date: 2012-05-03 04:01:29 +0000 (Thu, 03 May 2012)
Log Message:
-----------
WIP btree plus: tests OK : WIP check and optimization : dichotomic search to speed up
Modified Paths:
--------------
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/LeafPage.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/NonTerminalPage.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/NonTerminalPageTest.java
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/LeafPage.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/LeafPage.java 2012-05-03 03:37:42 UTC (rev 3064)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/LeafPage.java 2012-05-03 04:01:29 UTC (rev 3065)
@@ -160,7 +160,6 @@
xbyteSize = HEAD_TAIL_SIZE + (numberOfKeyEntries << 4);
} else {
xbyteSize = HEAD_TAIL_SIZE;
- // FIXMELUC ________speedup if long value key
for (int index = 0; index < numberOfKeyEntries; index++) {
xbyteSize += entrySize(keys[index]);
}
@@ -176,13 +175,27 @@
*/
public long getDataBlockPosition(
final DataRecordIdentifier dataRecordIdentifier) {
- // FIXMELUC _________________LONG dichotomic search
long position = -1;
- for (index = 0; position == -1L && index < numberOfKeyEntries; index++) {
- if (keys[index].compareTo(dataRecordIdentifier) == 0) {
- position = dataBlockPosition[index];
+ int begin = 0;
+ int end = numberOfKeyEntries - 1;
+ while (position == -1 && end >= begin) {
+ final int middle = (begin + end) >> 1;
+ final int compareto = dataRecordIdentifier.compareTo(keys[middle]);
+ if (compareto < 0) {
+ end = middle - 1;
+ } else if (compareto > 0) {
+ begin = middle + 1;
+ } else {
+ position = dataBlockPosition[middle];
}
}
+ // below was "simpler" implementation
+ // for (index = 0; position == -1L && index < numberOfKeyEntries;
+ // index++) {
+ // if (keys[index].compareTo(dataRecordIdentifier) == 0) {
+ // position = dataBlockPosition[index];
+ // }
+ // }
return position;
}
@@ -315,12 +328,23 @@
private int computeInsertBeforeIndex(
final DataRecordIdentifier dataRecordIdentifier) {
- // FIXMELUC _________________LONG
- int index;
- for (index = 0; index < numberOfKeyEntries
- && dataRecordIdentifier.compareTo(keys[index]) > 0; index++)
- ;
- return index;
+ int begin = 0;
+ int end = numberOfKeyEntries - 1;
+ while (end >= begin) {
+ final int middle = (begin + end) >> 1;
+ final int compareto = dataRecordIdentifier.compareTo(keys[middle]);
+ if (compareto <= 0) {
+ end = middle - 1;
+ } else {
+ begin = middle + 1;
+ }
+ }
+ return begin;
+ // below was "simpler" implementation
+ // for (index = 0; index < numberOfKeyEntries
+ // && dataRecordIdentifier.compareTo(keys[index]) > 0; index++)
+ // ;
+ // return index;
}
public DataRecordIdentifier getLastKey() {
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/NonTerminalPage.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/NonTerminalPage.java 2012-05-03 03:37:42 UTC (rev 3064)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/NonTerminalPage.java 2012-05-03 04:01:29 UTC (rev 3065)
@@ -158,7 +158,6 @@
xbyteSize = HEAD_TAIL_SIZE + (numberOfKeyEntries << 4);
} else {
xbyteSize = HEAD_TAIL_SIZE;
- // FIXMELUC ________speedup if long value key
for (int index = 0; index < numberOfKeyEntries; index++) {
xbyteSize += entrySize(keys[index]);
}
@@ -187,14 +186,26 @@
* @return sub page index for data record identifier
*/
public int getIndex(final DataRecordIdentifier dataRecordIdentifier) {
- // FIXMELUC _________dichotomic search
- int index;
- for (index = 0; index < numberOfKeyEntries; index++) {
- if (keys[index].compareTo(dataRecordIdentifier) >= 0) {
- return index;
+ int begin = 0;
+ int end = numberOfKeyEntries - 1;
+ while (end >= begin) {
+ final int middle = (begin + end) >> 1;
+ final int compareto = dataRecordIdentifier.compareTo(keys[middle]);
+ if (compareto <= 0) {
+ end = middle - 1;
+ } else {
+ begin = middle + 1;
}
}
- return index;
+ return begin;
+ // below was "simpler" implementation
+ // int index;
+ // for (index = 0; index < numberOfKeyEntries; index++) {
+ // if (keys[index].compareTo(dataRecordIdentifier) >= 0) {
+ // return index;
+ // }
+ // }
+ // return index;
}
/**
Modified: trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/NonTerminalPageTest.java
===================================================================
--- trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/NonTerminalPageTest.java 2012-05-03 03:37:42 UTC (rev 3064)
+++ trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/NonTerminalPageTest.java 2012-05-03 04:01:29 UTC (rev 3065)
@@ -546,7 +546,6 @@
/**/4/* int size for crc32 */+
/**/numberOfKeyEntries * 8/* key entries */+
/**/(numberOfKeyEntries + 1) * 8/* pointers entries */;
- // FIXMELUC ________speedup if long value key
return xbyteSize;
}
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
|
From: <luc...@us...> - 2012-05-03 04:01:35
|
Revision: 3065
http://joafip.svn.sourceforge.net/joafip/?rev=3065&view=rev
Author: luc_peuvrier
Date: 2012-05-03 04:01:29 +0000 (Thu, 03 May 2012)
Log Message:
-----------
WIP btree plus: tests OK : WIP check and optimization : dichotomic search to speed up
Modified Paths:
--------------
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/LeafPage.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/NonTerminalPage.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/NonTerminalPageTest.java
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
|
From: <luc...@us...> - 2012-05-04 05:07:37
|
Revision: 3066
http://joafip.svn.sourceforge.net/joafip/?rev=3066&view=rev
Author: luc_peuvrier
Date: 2012-05-04 05:07:30 +0000 (Fri, 04 May 2012)
Log Message:
-----------
WIP btree plus: tests OK : WIP check and optimization : fixed arrays
Modified Paths:
--------------
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/LeafPage.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/NonTerminalPage.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/NonTerminalPageTest.java
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
|
From: <luc...@us...> - 2012-05-04 05:07:37
|
Revision: 3066
http://joafip.svn.sourceforge.net/joafip/?rev=3066&view=rev
Author: luc_peuvrier
Date: 2012-05-04 05:07:30 +0000 (Fri, 04 May 2012)
Log Message:
-----------
WIP btree plus: tests OK : WIP check and optimization : fixed arrays
Modified Paths:
--------------
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/LeafPage.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/NonTerminalPage.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/NonTerminalPageTest.java
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/LeafPage.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/LeafPage.java 2012-05-03 04:01:29 UTC (rev 3065)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/LeafPage.java 2012-05-04 05:07:30 UTC (rev 3066)
@@ -23,8 +23,6 @@
*/
package net.sf.joafip.btreeplus.entity;
-import java.util.Arrays;
-
import net.sf.joafip.NotStorableClass;
import net.sf.joafip.kvstore.record.entity.DataRecordIdentifier;
import net.sf.joafip.kvstore.service.HeapException;
@@ -44,10 +42,19 @@
/**/4/* int size for crc32 */+
/**/8/* for next */;
- private long[] dataBlockPosition;
+ private static int MAX_NUMBER_OF_ENTRIES =
+ /**/(int) ((PageConstant.PAGE_SIZE - HEAD_TAIL_SIZE) / (8/*
+ * long size for
+ * pointer
+ */+ 8/*
+ * long size for
+ * value
+ */));
- private DataRecordIdentifier[] keys;
+ private final long[] dataBlockPosition = new long[MAX_NUMBER_OF_ENTRIES];
+ private final DataRecordIdentifier[] keys = new DataRecordIdentifier[MAX_NUMBER_OF_ENTRIES];
+
private int numberOfKeyEntries;
private int byteSize;
@@ -68,23 +75,9 @@
public LeafPage(final int numberOfKeyEntries, final boolean longKey) {
super(longKey);
this.numberOfKeyEntries = numberOfKeyEntries;
- keys = new DataRecordIdentifier[numberOfKeyEntries];
- dataBlockPosition = new long[numberOfKeyEntries];
byteSize = 0;
}
- public LeafPage(final int numberOfKeyEntries,
- final long[] dataBlockPosition, final DataRecordIdentifier[] keys,
- final boolean longKey) {
- super(longKey);
- assert numberOfKeyEntries == dataBlockPosition.length
- && numberOfKeyEntries == keys.length;
- this.numberOfKeyEntries = numberOfKeyEntries;
- this.dataBlockPosition = dataBlockPosition;
- this.keys = keys;
- updateByteSize();
- }
-
@Override
public EnumRecordType getRecordType() {
return EnumRecordType.LEAF_PAGE;
@@ -227,25 +220,15 @@
final int insertBeforeIndex = computeInsertBeforeIndex(dataRecordIdentifier);
final int afterLength = numberOfKeyEntries - insertBeforeIndex;
numberOfKeyEntries++;
- final long[] newDataBlockPosition = new long[numberOfKeyEntries];
- final DataRecordIdentifier[] newKeys = new DataRecordIdentifier[numberOfKeyEntries];
- if (insertBeforeIndex != 0) {
- System.arraycopy(dataBlockPosition, 0, newDataBlockPosition, 0,
- insertBeforeIndex);
- System.arraycopy(keys, 0, newKeys, 0, insertBeforeIndex);
- }
- newDataBlockPosition[insertBeforeIndex] = dataBlock
- .getPositionInFile();
- newKeys[insertBeforeIndex] = dataRecordIdentifier;
if (afterLength != 0) {
System.arraycopy(dataBlockPosition, insertBeforeIndex,
- newDataBlockPosition, insertBeforeIndex + 1,
- afterLength);
- System.arraycopy(keys, insertBeforeIndex, newKeys,
+ dataBlockPosition, insertBeforeIndex + 1, afterLength);
+ System.arraycopy(keys, insertBeforeIndex, keys,
insertBeforeIndex + 1, afterLength);
}
- dataBlockPosition = newDataBlockPosition;
- keys = newKeys;
+ dataBlockPosition[insertBeforeIndex] = dataBlock
+ .getPositionInFile();
+ keys[insertBeforeIndex] = dataRecordIdentifier;
byteSize += entrySize;
// ASSERTX
assert byteSize == computeByteSize() : byteSize + " for "
@@ -262,21 +245,16 @@
final int newLeafPageNumberOfKeyEntries = numberOfKeyEntries
- newNumberOfKeyEntries;
- final long[] newDataBlockPosition = Arrays.copyOf(dataBlockPosition,
- newNumberOfKeyEntries);
- final DataRecordIdentifier[] newKeys = Arrays.copyOf(keys,
- newNumberOfKeyEntries);
- final long[] newLeafPageDataBlockPosition = Arrays.copyOfRange(
- dataBlockPosition, newNumberOfKeyEntries, numberOfKeyEntries);
- final DataRecordIdentifier[] newLeafPageKeys = Arrays.copyOfRange(keys,
- newNumberOfKeyEntries, numberOfKeyEntries);
-
final LeafPage newLeafPage = new LeafPage(
- newLeafPageNumberOfKeyEntries, newLeafPageDataBlockPosition,
- newLeafPageKeys, longKey);
+ newLeafPageNumberOfKeyEntries, longKey);
+ System.arraycopy(dataBlockPosition, newNumberOfKeyEntries,
+ newLeafPage.dataBlockPosition, 0, newLeafPageNumberOfKeyEntries);
+ System.arraycopy(keys, newNumberOfKeyEntries, newLeafPage.keys, 0,
+ newLeafPageNumberOfKeyEntries);
+
+ newLeafPage.updateByteSize();
+
newLeafPage.setParentPage(getParentPage(), getInParentIndex() + 1);
- dataBlockPosition = newDataBlockPosition;
- keys = newKeys;
numberOfKeyEntries = newNumberOfKeyEntries;
updateByteSize();
if (insertBeforeIndex >= newNumberOfKeyEntries) {
@@ -299,20 +277,11 @@
assert byteSize != 0 : "unknow current byte size";
final int afterLength = numberOfKeyEntries - (index + 1);
numberOfKeyEntries--;
- final long[] newDataBlockPosition = new long[numberOfKeyEntries];
- final DataRecordIdentifier[] newKeys = new DataRecordIdentifier[numberOfKeyEntries];
- if (index != 0) {
- System.arraycopy(dataBlockPosition, 0, newDataBlockPosition, 0,
- index);
- System.arraycopy(keys, 0, newKeys, 0, index);
- }
if (afterLength != 0) {
- System.arraycopy(dataBlockPosition, index + 1,
- newDataBlockPosition, index, afterLength);
- System.arraycopy(keys, index + 1, newKeys, index, afterLength);
+ System.arraycopy(dataBlockPosition, index + 1, dataBlockPosition,
+ index, afterLength);
+ System.arraycopy(keys, index + 1, keys, index, afterLength);
}
- keys = newKeys;
- dataBlockPosition = newDataBlockPosition;
byteSize -= entrySize;
// ASSERTX
assert byteSize == computeByteSize() : byteSize + " for "
@@ -366,9 +335,6 @@
final boolean merged;
if (byteSize + leafPageByteSize - HEAD_TAIL_SIZE <= PageConstant.PAGE_SIZE) {
merged = true;
- dataBlockPosition = Arrays.copyOf(dataBlockPosition,
- totalNumberOfEntries);
- keys = Arrays.copyOf(keys, totalNumberOfEntries);
System.arraycopy(leafPage.dataBlockPosition, 0, dataBlockPosition,
numberOfKeyEntries, leafPageNumberOfKeyEntries);
System.arraycopy(leafPage.keys, 0, keys, numberOfKeyEntries,
@@ -385,42 +351,37 @@
final int newLeafPageNumberOfEntries = totalNumberOfEntries
- newNumberOfEntries;
if (newNumberOfEntries > numberOfKeyEntries) {
- dataBlockPosition = Arrays.copyOf(dataBlockPosition,
- newNumberOfEntries);
- keys = Arrays.copyOf(keys, newNumberOfEntries);
final int length = newNumberOfEntries - numberOfKeyEntries;
System.arraycopy(leafPage.dataBlockPosition, 0,
dataBlockPosition, numberOfKeyEntries, length);
System.arraycopy(leafPage.keys, 0, keys, numberOfKeyEntries,
length);
- leafPage.dataBlockPosition = Arrays.copyOfRange(
- leafPage.dataBlockPosition, length,
+
+ System.arraycopy(leafPage.dataBlockPosition, length,
+ leafPage.dataBlockPosition, 0,
leafPageNumberOfKeyEntries);
- leafPage.keys = Arrays.copyOfRange(leafPage.keys, length,
+ System.arraycopy(leafPage.keys, length, leafPage.keys, 0,
leafPageNumberOfKeyEntries);
+
numberOfKeyEntries = newNumberOfEntries;
leafPage.numberOfKeyEntries = newLeafPageNumberOfEntries;
updateByteSize();
leafPage.updateByteSize();
} else if (newLeafPageNumberOfEntries > leafPageNumberOfKeyEntries) {
- long[] newLeafPageDataBlockPosition = new long[newLeafPageNumberOfEntries];
- DataRecordIdentifier[] newLeafPageKeys = new DataRecordIdentifier[newLeafPageNumberOfEntries];
final int length = newLeafPageNumberOfEntries
- leafPageNumberOfKeyEntries;
- System.arraycopy(dataBlockPosition, newNumberOfEntries,
- newLeafPageDataBlockPosition, 0, length);
- System.arraycopy(keys, newNumberOfEntries, newLeafPageKeys, 0,
- length);
+
System.arraycopy(leafPage.dataBlockPosition, 0,
- newLeafPageDataBlockPosition, length,
+ leafPage.dataBlockPosition, length,
leafPageNumberOfKeyEntries);
- System.arraycopy(leafPage.keys, 0, newLeafPageKeys, length,
+ System.arraycopy(leafPage.keys, 0, leafPage.keys, length,
leafPageNumberOfKeyEntries);
- dataBlockPosition = Arrays.copyOf(dataBlockPosition,
- newNumberOfEntries);
- keys = Arrays.copyOf(keys, newNumberOfEntries);
- leafPage.dataBlockPosition = newLeafPageDataBlockPosition;
- leafPage.keys = newLeafPageKeys;
+
+ System.arraycopy(dataBlockPosition, newNumberOfEntries,
+ leafPage.dataBlockPosition, 0, length);
+ System.arraycopy(keys, newNumberOfEntries, leafPage.keys, 0,
+ length);
+
numberOfKeyEntries = newNumberOfEntries;
leafPage.numberOfKeyEntries = newLeafPageNumberOfEntries;
updateByteSize();
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/NonTerminalPage.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/NonTerminalPage.java 2012-05-03 04:01:29 UTC (rev 3065)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/NonTerminalPage.java 2012-05-04 05:07:30 UTC (rev 3066)
@@ -23,8 +23,7 @@
*/
package net.sf.joafip.btreeplus.entity;
-import java.util.Arrays;
-
+import net.sf.joafip.Fortest;
import net.sf.joafip.NotStorableClass;
import net.sf.joafip.kvstore.record.entity.DataRecordIdentifier;
import net.sf.joafip.kvstore.service.HeapException;
@@ -45,10 +44,21 @@
/**/4/* int size for crc32 */+
/**/8/* last pointer long size */;
- private long[] pagePositions;
+ private static int MAX_NUMBER_OF_ENTRIES =
+ /**/(int) ((PageConstant.PAGE_SIZE - HEAD_TAIL_SIZE) / (8/*
+ * long size for
+ * pointer
+ */+ 8/*
+ * long size for
+ * value
+ */));
- private DataRecordIdentifier[] keys;
+ /** +1 for last pointer and +1 for add before split */
+ private final long[] pagePositions = new long[MAX_NUMBER_OF_ENTRIES + 1 + 1];
+ /** +1 for add before split */
+ private final DataRecordIdentifier[] keys = new DataRecordIdentifier[MAX_NUMBER_OF_ENTRIES + 1];
+
private int numberOfKeyEntries;
private int byteSize;
@@ -67,11 +77,10 @@
public NonTerminalPage(final int numberOfKeyEntries, final boolean longKey) {
super(longKey);
this.numberOfKeyEntries = numberOfKeyEntries;
- keys = new DataRecordIdentifier[numberOfKeyEntries];
- pagePositions = new long[numberOfKeyEntries + 1];
byteSize = 0;
}
+ @Fortest
public NonTerminalPage(final int numberOfKeyEntries,
final DataRecordIdentifier[] keys, final long[] pagePosition,
final boolean longKey) {
@@ -79,8 +88,9 @@
assert numberOfKeyEntries == keys.length
&& numberOfKeyEntries + 1 == pagePosition.length;
this.numberOfKeyEntries = numberOfKeyEntries;
- this.keys = keys;
- this.pagePositions = pagePosition;
+ System.arraycopy(keys, 0, this.keys, 0, numberOfKeyEntries);
+ System.arraycopy(pagePosition, 0, this.pagePositions, 0,
+ numberOfKeyEntries + 1);
updateByteSize();
}
@@ -222,22 +232,14 @@
final int entrySize = entrySize(key);
final int afterLength = numberOfKeyEntries - index;
numberOfKeyEntries++;
- DataRecordIdentifier[] newKeys = new DataRecordIdentifier[numberOfKeyEntries];
- long[] newPagePosition = new long[numberOfKeyEntries + 1];
- if (index != 0) {
- System.arraycopy(keys, 0, newKeys, 0, index);
- }
- System.arraycopy(pagePositions, 0, newPagePosition, 0, index + 1);
- newKeys[index] = key;
- newPagePosition[index + 1] = newRightILeafPage.getPositionInFile();
- System.arraycopy(pagePositions, index + 1, newPagePosition, index + 2,
+ System.arraycopy(pagePositions, index + 1, pagePositions, index + 2,
afterLength);
if (afterLength != 0) {
- System.arraycopy(keys, index, newKeys, index + 1, afterLength);
+ System.arraycopy(keys, index, keys, index + 1, afterLength);
}
- keys = newKeys;
- pagePositions = newPagePosition;
+ keys[index] = key;
+ pagePositions[index + 1] = newRightILeafPage.getPositionInFile();
// ASSERTX
assert byteSize != 0 : "unknow current byte size";
byteSize += entrySize;
@@ -263,23 +265,14 @@
final int entrySize = entrySize(middleKey);
final int afterLength = numberOfKeyEntries - index;
numberOfKeyEntries++;
- DataRecordIdentifier[] newKeys = new DataRecordIdentifier[numberOfKeyEntries];
- long[] newPagePositions = new long[numberOfKeyEntries + 1];
- if (index != 0) {
- System.arraycopy(keys, 0, newKeys, 0, index);
- }
- System.arraycopy(pagePositions, 0, newPagePositions, 0, index + 1);
- newKeys[index] = middleKey;
- newPagePositions[index + 1] = rightSonNonTerminalPage
- .getPositionInFile();
-
if (afterLength != 0) {
- System.arraycopy(keys, index, newKeys, index + 1, afterLength);
- System.arraycopy(pagePositions, index + 1, newPagePositions,
+ System.arraycopy(keys, index, keys, index + 1, afterLength);
+ System.arraycopy(pagePositions, index + 1, pagePositions,
index + 2, afterLength);
}
- keys = newKeys;
- pagePositions = newPagePositions;
+ keys[index] = middleKey;
+ pagePositions[index + 1] = rightSonNonTerminalPage.getPositionInFile();
+
// ASSERTX
assert byteSize != 0 : "unknow current byte size";
byteSize += entrySize;
@@ -295,19 +288,15 @@
final int newNumberOfKeyEntries = splitIndex;
final int newNonTerminalPageNumberOfKeyEntries = numberOfKeyEntries
- (splitIndex + 1);
- final DataRecordIdentifier[] newKeys = Arrays.copyOf(keys,
+
+ final NonTerminalPage nonTerminalPage = new NonTerminalPage(
+ newNonTerminalPageNumberOfKeyEntries, longKey);
+ System.arraycopy(keys, splitIndex + 1, nonTerminalPage.keys, 0,
newNumberOfKeyEntries);
- final long[] newPagePosition = Arrays.copyOf(pagePositions,
- newNumberOfKeyEntries + 1);
- final DataRecordIdentifier[] newNonTerminalKeys = Arrays.copyOfRange(
- keys, splitIndex + 1, numberOfKeyEntries);
- final long[] newNonTerminalPagePosition = Arrays.copyOfRange(
- pagePositions, splitIndex + 1, numberOfKeyEntries + 1);
- final INonTerminalPage nonTerminalPage = new NonTerminalPage(
- newNonTerminalPageNumberOfKeyEntries, newNonTerminalKeys,
- newNonTerminalPagePosition, longKey);
- keys = newKeys;
- pagePositions = newPagePosition;
+ System.arraycopy(pagePositions, splitIndex + 1,
+ nonTerminalPage.pagePositions, 0, newNumberOfKeyEntries + 1);
+
+ nonTerminalPage.updateByteSize();
numberOfKeyEntries = newNumberOfKeyEntries;
updateByteSize();
setValueIsChangedValueToSave();
@@ -328,22 +317,13 @@
public void remove(int leafPageInParentIndex) {
final DataRecordIdentifier key = keys[leafPageInParentIndex];
numberOfKeyEntries--;
- DataRecordIdentifier[] newKeys = new DataRecordIdentifier[numberOfKeyEntries];
- long[] newPagePositions = new long[numberOfKeyEntries + 1];
- if (leafPageInParentIndex != 0) {
- System.arraycopy(keys, 0, newKeys, 0, leafPageInParentIndex);
- System.arraycopy(pagePositions, 0, newPagePositions, 0,
- leafPageInParentIndex);
- }
final int length = numberOfKeyEntries - leafPageInParentIndex;
if (length != 0) {
- System.arraycopy(keys, leafPageInParentIndex + 1, newKeys,
+ System.arraycopy(keys, leafPageInParentIndex + 1, keys,
leafPageInParentIndex, length);
}
System.arraycopy(pagePositions, leafPageInParentIndex + 1,
- newPagePositions, leafPageInParentIndex, length + 1);
- keys = newKeys;
- pagePositions = newPagePositions;
+ pagePositions, leafPageInParentIndex, length + 1);
// ASSERTX
assert byteSize != 0 : "unknow current byte size";
byteSize -= entrySize(key);
@@ -377,9 +357,6 @@
if (byteSize + middleKeySize + rightPageByteSize - HEAD_TAIL_SIZE <= PageConstant.PAGE_SIZE) {
// can merge
merged = true;
- pagePositions = Arrays.copyOf(pagePositions,
- totalNumberOfEntries + 1 + 1);
- keys = Arrays.copyOf(keys, totalNumberOfEntries + 1);
System.arraycopy(rightNonTerminalPage.pagePositions, 0,
pagePositions, numberOfKeyEntries + 1,
rightPageNumberOfKeyEntries + 1);
@@ -398,11 +375,8 @@
- newNumberOfEntries;
if (newNumberOfEntries > numberOfKeyEntries) {
int length = newNumberOfEntries - numberOfKeyEntries;
- pagePositions = Arrays.copyOf(pagePositions,
- newNumberOfEntries + 1);
System.arraycopy(rightNonTerminalPage.pagePositions, 0,
pagePositions, numberOfKeyEntries + 1, length);
- keys = Arrays.copyOf(keys, newNumberOfEntries);
keys[numberOfKeyEntries] = middleKey;
System.arraycopy(rightNonTerminalPage.keys, 0, keys,
numberOfKeyEntries + 1, length - 1);
@@ -411,41 +385,36 @@
updateByteSize();
length = rightPageNumberOfKeyEntries
- newRightPageNumberOfEntries;
- rightNonTerminalPage.pagePositions = Arrays.copyOfRange(
- rightNonTerminalPage.pagePositions, length,
+ System.arraycopy(rightNonTerminalPage.pagePositions, length,
+ rightNonTerminalPage.pagePositions, 0,
rightPageNumberOfKeyEntries + 1);
- rightNonTerminalPage.keys = Arrays.copyOfRange(
- rightNonTerminalPage.keys, length,
+ System.arraycopy(rightNonTerminalPage.keys, length,
+ rightNonTerminalPage.keys, 0,
rightPageNumberOfKeyEntries);
rightNonTerminalPage.numberOfKeyEntries = newRightPageNumberOfEntries;
rightNonTerminalPage.updateByteSize();
} else if (newRightPageNumberOfEntries > rightPageNumberOfKeyEntries) {
final int length = newRightPageNumberOfEntries
- rightPageNumberOfKeyEntries;
- long[] newPagePositions = Arrays.copyOf(pagePositions,
- newNumberOfEntries + 1);
- DataRecordIdentifier[] newKeys = Arrays.copyOf(keys,
- newNumberOfEntries);
this.middleKey = keys[newNumberOfEntries];
- long[] newRightPagePositions = new long[newRightPageNumberOfEntries + 1];
- DataRecordIdentifier[] newRightKeys = new DataRecordIdentifier[newRightPageNumberOfEntries];
- System.arraycopy(pagePositions, newNumberOfEntries + 1,
- newRightPagePositions, 0, length);
- System.arraycopy(keys, newNumberOfEntries + 1, newRightKeys, 0,
- length - 1);
- newRightKeys[length - 1] = middleKey;
+
System.arraycopy(rightNonTerminalPage.pagePositions, 0,
- newRightPagePositions, length,
+ rightNonTerminalPage.pagePositions, length,
rightPageNumberOfKeyEntries + 1);
- System.arraycopy(rightNonTerminalPage.keys, 0, newRightKeys,
- length, rightPageNumberOfKeyEntries);
+ System.arraycopy(rightNonTerminalPage.keys, 0,
+ rightNonTerminalPage.keys, length,
+ rightPageNumberOfKeyEntries);
+
+ System.arraycopy(pagePositions, newNumberOfEntries + 1,
+ rightNonTerminalPage.pagePositions, 0, length);
+ System.arraycopy(keys, newNumberOfEntries + 1,
+ rightNonTerminalPage.keys, 0, length - 1);
+
+ rightNonTerminalPage.keys[length - 1] = middleKey;
+
rightNonTerminalPage.numberOfKeyEntries = newRightPageNumberOfEntries;
- rightNonTerminalPage.keys = newRightKeys;
- rightNonTerminalPage.pagePositions = newRightPagePositions;
rightNonTerminalPage.updateByteSize();
numberOfKeyEntries = newNumberOfEntries;
- keys = newKeys;
- pagePositions = newPagePositions;
updateByteSize();
}
}
Modified: trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/NonTerminalPageTest.java
===================================================================
--- trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/NonTerminalPageTest.java 2012-05-03 04:01:29 UTC (rev 3065)
+++ trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/NonTerminalPageTest.java 2012-05-04 05:07:30 UTC (rev 3066)
@@ -460,13 +460,15 @@
public void testEquilibrateLeftToRight() throws HeapException {
final NonTerminalPage leftPage = new NonTerminalPage(128 + 64, true);
- final NonTerminalPage rightPage = new NonTerminalPage(128 + 32, true);
addToNonTerminalPage(leftPage, createKeys(1, 128 + 64),
createPointers(1, 128 + 64 + 1));
leftPage.updateByteSize();
+
+ final NonTerminalPage rightPage = new NonTerminalPage(128 + 32, true);
addToNonTerminalPage(rightPage, createKeys(2 + 128 + 64, 128 + 32),
createPointers(1 + 128 + 64 + 1, 128 + 32 + 1));
rightPage.updateByteSize();
+
assertFalse("must not merge", leftPage.equilibrate(
new DataRecordIdentifier(1 + 128 + 64), rightPage));
checkState(leftPage, createKeys(1, 176), createPointers(1, 177));
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
|
From: <luc...@us...> - 2012-05-08 06:54:32
|
Revision: 3076
http://joafip.svn.sourceforge.net/joafip/?rev=3076&view=rev
Author: luc_peuvrier
Date: 2012-05-08 06:54:26 +0000 (Tue, 08 May 2012)
Log Message:
-----------
WIP btree plus: added iterator
Modified Paths:
--------------
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/HeaderPage.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/LeafPage.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusDataManager.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusDataMgrIntegrityChecker.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgr.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/service/BtreePlusLeafPageBalanceMergeTest.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/service/BtreePlusNonTerminalPageBalanceMergeTest.java
Added Paths:
-----------
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusIterator.java
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
|
From: <luc...@us...> - 2012-05-08 06:54:32
|
Revision: 3076
http://joafip.svn.sourceforge.net/joafip/?rev=3076&view=rev
Author: luc_peuvrier
Date: 2012-05-08 06:54:26 +0000 (Tue, 08 May 2012)
Log Message:
-----------
WIP btree plus: added iterator
Modified Paths:
--------------
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/HeaderPage.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/LeafPage.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusDataManager.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusDataMgrIntegrityChecker.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgr.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/service/BtreePlusLeafPageBalanceMergeTest.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/service/BtreePlusNonTerminalPageBalanceMergeTest.java
Added Paths:
-----------
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusIterator.java
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/HeaderPage.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/HeaderPage.java 2012-05-08 05:55:35 UTC (rev 3075)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/HeaderPage.java 2012-05-08 06:54:26 UTC (rev 3076)
@@ -52,6 +52,8 @@
private int numberOfDataRecord;
+ private long firstLeafPagePosition = -1L;
+
public HeaderPage(final IHeapElementManager heapElementManager) {
super(heapElementManager, 0L);
}
@@ -103,6 +105,14 @@
return freeDataBlocks[blockBits - PageConstant.MIN_DATA_BLOCK_BITS];
}
+ public long getFirstLeafPagePosition() {
+ return firstLeafPagePosition;
+ }
+
+ public void setFirstLeafPagePosition(final long firstLeafPagePosition) {
+ this.firstLeafPagePosition = firstLeafPagePosition;
+ }
+
public void clear() {
super.clear();
fileSizeAsNumberOfPage = 1L;
@@ -112,6 +122,7 @@
nextDataRecordIdentifier = 0;
lastRecordPositionInFile = -1L;
numberOfDataRecord = 0;
+ firstLeafPagePosition = -1L;
}
@Override
@@ -148,6 +159,7 @@
writeLong(nextDataRecordIdentifier);
writeLong(lastRecordPositionInFile);
writeInteger(numberOfDataRecord);
+ writeLong(firstLeafPagePosition);
initializeFreeDataBlock();
for (int index = 0; index < PageConstant.NUMBER_OF_BLOCK_TYPE; index++) {
writeLong(freeDataBlocks[index]);
@@ -173,6 +185,7 @@
nextDataRecordIdentifier = readLong();
lastRecordPositionInFile = readLong();
numberOfDataRecord = readInteger();
+ firstLeafPagePosition = readLong();
initializeFreeDataBlock();
for (int index = 0; index < PageConstant.NUMBER_OF_BLOCK_TYPE; index++) {
freeDataBlocks[index] = readLong();
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/LeafPage.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/LeafPage.java 2012-05-08 05:55:35 UTC (rev 3075)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/LeafPage.java 2012-05-08 06:54:26 UTC (rev 3076)
@@ -57,7 +57,7 @@
private int byteSize;
- private long next;
+ private long next = -1L;
private IPageRecordable parentPage;
@@ -367,6 +367,7 @@
// ASSERTX
assert byteSize == computeByteSize() : byteSize + " for "
+ computeByteSize() + " computed";
+ next = leafPage.getNext();
} else {
final int newNumberOfEntries = totalNumberOfEntries / 2;
final int newLeafPageNumberOfEntries = totalNumberOfEntries
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusDataManager.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusDataManager.java 2012-05-08 05:55:35 UTC (rev 3075)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusDataManager.java 2012-05-08 06:54:26 UTC (rev 3076)
@@ -276,6 +276,7 @@
LeafPage newLeafPage = leafPage.split(dataRecordIdentifier, dataBlock);
btreePlusElementMgr.appendPageRecordable(newLeafPage);
newLeafPage.setValueIsChangedValueToSave();
+ newLeafPage.setNext(leafPage.getNext());
leafPage.setNext(newLeafPage.getPositionInFile());
if (nonTerminalPage == null) {
@@ -670,8 +671,7 @@
@Override
protected Iterator<DataRecordIdentifier> dataRecordIteratorImpl()
throws HeapException {
- // FIXMELUC ________to implement
- throw new HeapException("not implemented");
+ return new BtreePlusIterator(btreePlusElementMgr);
}
@Fortest
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusDataMgrIntegrityChecker.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusDataMgrIntegrityChecker.java 2012-05-08 05:55:35 UTC (rev 3075)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusDataMgrIntegrityChecker.java 2012-05-08 06:54:26 UTC (rev 3076)
@@ -77,13 +77,13 @@
final BtreePlusElementMgr elementMgr = btreePlusDataManager
.getBtreePlusElementMgr();
IPageRecordable pageRecordable = elementMgr.getRoot();
+ long currentLeafPagePosition = elementMgr.getFirstLeafPagePosition();
int index = 0;
int currentDepth = 0;
int depth = -1;
int entriesCount = 0;
int leafPageCount = 0;
int nonTerminalPageCount = 0;
- // FIXMELUC _____________leaf page chain
// System.out.println("--- begin ---");
while (pageRecordable != null) {
elementMgr.clearReadCache();
@@ -120,12 +120,23 @@
+ lastKey + "(last key value) <=" + state.maxKey
+ "(max value)");
}
+
// check well formed
// if (currentDepth != 0 && !leafPage.wellFilled()) {
// throw new
// HeapException("not well filled "+leafPage.getByteSize());
// }
+ // check chaining
+ if (currentLeafPagePosition != leafPage.getPositionInFile()) {
+ throw new HeapException(
+ "bad current leaf page position\nexpected="
+ + currentLeafPagePosition
+ + ", currentLeafPage="
+ + leafPage.getPositionInFile());
+ }
+ currentLeafPagePosition = leafPage.getNext();
+
// check depth, all leaf page must be at same depth
if (depth == -1) {
depth = currentDepth;
@@ -224,6 +235,9 @@
throw new HeapException("bad record type " + recordType);
}
}
+ if (currentLeafPagePosition != -1L) {
+ throw new HeapException("bad current leaf page position");
+ }
// System.out.println("--- end ---");
return new IntegrityCheckResult(depth, entriesCount, leafPageCount,
nonTerminalPageCount);
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgr.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgr.java 2012-05-08 05:55:35 UTC (rev 3075)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgr.java 2012-05-08 06:54:26 UTC (rev 3076)
@@ -240,7 +240,9 @@
leafPage.setNext(-1L);
leafPage.updateByteSize();
leafPage.setValueIsChangedValueToSave();
- header.setRootPagePosition(leafPage.getPositionInFile());
+ final long firstLeafPagePosition = leafPage.getPositionInFile();
+ header.setRootPagePosition(firstLeafPagePosition);
+ header.setFirstLeafPagePosition(firstLeafPagePosition);
}
public void newRootNonTerminalPage(final LeafPage leftLeafPage,
@@ -302,6 +304,7 @@
public void removeRoot() throws HeapException {
header.setRootPagePosition(-1L);
+ header.setFirstLeafPagePosition(-1L);
}
public void remove(final IDataBlock dataBlock) throws HeapException {
@@ -390,4 +393,8 @@
public void clearReadCache() {
heapElementManager.clearReadCache();
}
+
+ public long getFirstLeafPagePosition() {
+ return header.getFirstLeafPagePosition();
+ }
}
Added: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusIterator.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusIterator.java (rev 0)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusIterator.java 2012-05-08 06:54:26 UTC (rev 3076)
@@ -0,0 +1,90 @@
+/*
+ * Copyright 2012 Luc Peuvrier
+ * All rights reserved.
+ *
+ * This file is a part of JOAFIP.
+ *
+ * JOAFIP is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License.
+ *
+ * Licensed under the GNU LESSER GENERAL PUBLIC LICENSE
+ * Licensed under the LGPL License, Version 3, 29 June 2007 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.gnu.org/licenses/lgpl.html
+ *
+ * JOAFIP is distributed in the hope that it will be useful, but
+ * 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 net.sf.joafip.btreeplus.service;
+
+import java.util.Iterator;
+
+import net.sf.joafip.NotStorableClass;
+import net.sf.joafip.btreeplus.entity.LeafPage;
+import net.sf.joafip.kvstore.record.entity.DataRecordIdentifier;
+
+/**
+ *
+ * @author luc peuvrier
+ *
+ */
+@NotStorableClass
+public class BtreePlusIterator implements Iterator<DataRecordIdentifier> {
+
+ private long nextPosition;
+
+ private int nextIndex;
+
+ private DataRecordIdentifier next;
+
+ private final BtreePlusElementMgr btreePlusElementMgr;
+
+ public BtreePlusIterator(final BtreePlusElementMgr btreePlusElementMgr) {
+ super();
+ this.btreePlusElementMgr = btreePlusElementMgr;
+ nextPosition = btreePlusElementMgr.getFirstLeafPagePosition();
+ nextIndex = 0;
+ computeNext();
+ }
+
+ @Override
+ public boolean hasNext() {
+ return next != null;
+ }
+
+ @Override
+ public DataRecordIdentifier next() {
+ final DataRecordIdentifier result = next;
+ computeNext();
+ return result;
+ }
+
+ private void computeNext() {
+ try {
+ if (nextPosition == -1L) {
+ next = null;
+ } else {
+ final LeafPage leafPage = (LeafPage) btreePlusElementMgr
+ .getPage(nextPosition, null, -1);
+ next = leafPage.getKey(nextIndex++);
+ if (nextIndex == leafPage.getNumberOfKeyEntries()) {
+ nextPosition = leafPage.getNext();
+ nextIndex = 0;
+ }
+ }
+ } catch (Exception exception) {
+ throw new IllegalStateException("computing next", exception);
+ }
+ }
+
+ @Override
+ public void remove() {
+ throw new UnsupportedOperationException();
+ }
+}
Modified: trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/service/BtreePlusLeafPageBalanceMergeTest.java
===================================================================
--- trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/service/BtreePlusLeafPageBalanceMergeTest.java 2012-05-08 05:55:35 UTC (rev 3075)
+++ trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/service/BtreePlusLeafPageBalanceMergeTest.java 2012-05-08 06:54:26 UTC (rev 3076)
@@ -25,6 +25,7 @@
import java.io.File;
import java.util.Arrays;
+import java.util.Iterator;
import net.sf.joafip.AbstractCommonDeleteFileTestCase;
import net.sf.joafip.NoStorableAccess;
@@ -99,6 +100,7 @@
assertTrue("bad value", Arrays.equals(createData(k), data));
}
}
+ iterate(max);
}
public void testBalanceLeftToRight() throws HeapException {
@@ -114,8 +116,20 @@
assertTrue("bad value", Arrays.equals(createData(k), data));
}
}
+ iterate(max);
}
+ private void iterate(final int max) throws HeapException {
+ final Iterator<DataRecordIdentifier> iterator = dataManager
+ .dataRecordIterator();
+ for (int identifier = 0; identifier < max; identifier++) {
+ assertTrue("must has next", iterator.hasNext());
+ assertEquals("bad value", new DataRecordIdentifier(identifier),
+ iterator.next());
+ }
+ assertFalse("must not has next", iterator.hasNext());
+ }
+
private byte[] createData(final int identifier) {
final byte[] data = new byte[8];
data[0] = (byte) identifier;
Modified: trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/service/BtreePlusNonTerminalPageBalanceMergeTest.java
===================================================================
--- trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/service/BtreePlusNonTerminalPageBalanceMergeTest.java 2012-05-08 05:55:35 UTC (rev 3075)
+++ trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/service/BtreePlusNonTerminalPageBalanceMergeTest.java 2012-05-08 06:54:26 UTC (rev 3076)
@@ -25,6 +25,7 @@
import java.io.File;
import java.util.Arrays;
+import java.util.Iterator;
import net.sf.joafip.AbstractCommonDeleteFileTestCase;
import net.sf.joafip.NoStorableAccess;
@@ -131,6 +132,7 @@
assertTrue("bad value", Arrays.equals(createData(k), data));
}
}
+ iterate(max);
}
public void testBalanceLeftToRight() throws HeapException {
@@ -157,8 +159,21 @@
assertTrue("bad value", Arrays.equals(createData(k), data));
}
}
+ iterate(max);
}
+ private void iterate(final int max) throws HeapException {
+ final Iterator<DataRecordIdentifier> iterator = dataManager
+ .dataRecordIterator();
+ for (int identifier = 0; identifier < max; identifier++) {
+ assertTrue("must has next", iterator.hasNext());
+ assertEquals("bad value",
+ DATA_RECORD_KEY_MANAGER.createKey(new BigKey(identifier)),
+ iterator.next());
+ }
+ assertFalse("must not has next", iterator.hasNext());
+ }
+
private byte[] createData(final int identifier) {
final byte[] data = new byte[8];
data[0] = (byte) identifier;
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
|
From: <luc...@us...> - 2012-05-09 04:56:46
|
Revision: 3082
http://joafip.svn.sourceforge.net/joafip/?rev=3082&view=rev
Author: luc_peuvrier
Date: 2012-05-09 04:56:39 +0000 (Wed, 09 May 2012)
Log Message:
-----------
WIP btree plus: data block access optimization
Modified Paths:
--------------
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/DataBlock.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/DataBlockPage.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/IDataBlock.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/LeafPage.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/NonTerminalPage.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/PageRecord.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusDataManager.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgr.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/DataBlockPageTest.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/LeafPageTest.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/NonTerminalPageTest.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/mock/MockDataBlock.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgrTest.java
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/DataBlock.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/DataBlock.java 2012-05-09 02:32:21 UTC (rev 3081)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/DataBlock.java 2012-05-09 04:56:39 UTC (rev 3082)
@@ -23,8 +23,6 @@
*/
package net.sf.joafip.btreeplus.entity;
-import java.util.Arrays;
-
import net.sf.joafip.NotStorableClass;
import net.sf.joafip.kvstore.service.HeapException;
@@ -38,18 +36,14 @@
private final DataBlockPage dataBlockPage;
- private final byte[] data;
-
private final int indexInDataBlockPage;
private final byte bits;
- private final int minSize;
+ private final int minDataSize;
- private final int maxSize;
+ private final int maxDataSize;
- private int size;
-
private long position = -1;
private LeafPage parentLeafPage;
@@ -57,25 +51,24 @@
private int indexInLeafPage;
public DataBlock(final DataBlockPage dataBlockPage,
- final int indexInDataBlockPage, final byte bits, final int minSize,
- final int maxSize) {
+ final int indexInDataBlockPage, final byte bits,
+ final int minDataSize, final int maxDataSize) {
super();
this.dataBlockPage = dataBlockPage;
this.indexInDataBlockPage = indexInDataBlockPage;
this.bits = bits;
- this.minSize = minSize;
- this.maxSize = maxSize;
- data = new byte[maxSize];
+ this.minDataSize = minDataSize;
+ this.maxDataSize = maxDataSize;
}
@Override
- public int getMinSize() {
- return minSize;
+ public int getMinDataSize() {
+ return minDataSize;
}
@Override
- public int getMaxSize() {
- return maxSize;
+ public int getMaxDataSize() {
+ return maxDataSize;
}
@Override
@@ -93,67 +86,26 @@
}
@Override
- public byte[] getDataHolder() {
- return data; // NOPMD i want this to make arrays accessible for
- // modification
- }
-
- @Override
- public int getSize() {
- return size;
- }
-
- @Override
- public void setSize(final int size) {
- this.size = size;
- }
-
- @Override
public void setData(final byte[] data) throws HeapException {
- System.arraycopy(data, 0, this.data, 0, size = data.length);
- setValueIsChangedValueToSave();
+ dataBlockPage.setData(indexInDataBlockPage, data);
}
@Override
- public byte[] getData() {
- return Arrays.copyOf(data, size);
+ public byte[] getData() throws HeapException {
+ return dataBlockPage.getData(indexInDataBlockPage);
}
@Override
- public void setValueIsChangedValueToSave() throws HeapException {
- dataBlockPage.setValueIsChangedValueToSave();
- }
-
- @Override
- public void setValueIsNotChanged() {
- dataBlockPage.setValueIsNotChanged();
- }
-
- @Override
public void setNextFreeDataBlockPositionOfFree(
final long nextFreeDataBlockPosition) throws HeapException {
- data[0] = (byte) (nextFreeDataBlockPosition >> 56);
- data[1] = (byte) (nextFreeDataBlockPosition >> 48);
- data[2] = (byte) (nextFreeDataBlockPosition >> 40);
- data[3] = (byte) (nextFreeDataBlockPosition >> 32);
- data[4] = (byte) (nextFreeDataBlockPosition >> 24);
- data[5] = (byte) (nextFreeDataBlockPosition >> 16);
- data[6] = (byte) (nextFreeDataBlockPosition >> 8);
- data[7] = (byte) (nextFreeDataBlockPosition);
- setValueIsChangedValueToSave();
+ dataBlockPage.setNextFreeDataBlockPositionOfFree(indexInDataBlockPage,
+ nextFreeDataBlockPosition);
}
@Override
- public long getNextFreeDataBlockPositionOfFree() {
- return
- /**/((((long) data[0]) & 0xff) << 56) |
- /**/((((long) data[1]) & 0xff) << 48) |
- /**/((((long) data[2]) & 0xff) << 40) |
- /**/((((long) data[3]) & 0xff) << 32) |
- /**/((((long) data[4]) & 0xff) << 24) |
- /**/((((long) data[5]) & 0xff) << 16) |
- /**/((((long) data[6]) & 0xff) << 8) |
- /**/(((long) data[7]) & 0xff);
+ public long getNextFreeDataBlockPositionOfFree() throws HeapException {
+ return dataBlockPage
+ .getNextFreeDataBlockPositionOfFree(indexInDataBlockPage);
}
@Override
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/DataBlockPage.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/DataBlockPage.java 2012-05-09 02:32:21 UTC (rev 3081)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/DataBlockPage.java 2012-05-09 04:56:39 UTC (rev 3082)
@@ -47,10 +47,18 @@
private final int dataBlockSize;
+ private final int numberOfBlock;
+
+ private final byte[] allData;
+
+ private int inAllDataIndex;
+
private final IDataBlock[] dataBlocks;
- private final int numberOfBlock;
+ private final int maxDataBlockDataSize;
+ private final int minDataBlockDataSize;
+
public static byte bitsForLength(final int length) throws HeapException {
for (byte bits = PageConstant.MIN_DATA_BLOCK_BITS; bits <= PageConstant.MAX_DATA_BLOCK_BITS; bits++) {
if (length < (1 << bits)) {
@@ -64,8 +72,8 @@
public DataBlockPage(final byte bits) {
super();
this.bits = bits;
- final int maxSize = 1 << bits;
- dataBlockSize = maxSize + 4/* for data size */;
+ maxDataBlockDataSize = 1 << bits;
+ dataBlockSize = maxDataBlockDataSize + 4/* for data content size */;
if (dataBlockSize > PageConstant.PAGE_SIZE - HEAD_TAIL_SIZE) {
// one data block on one or more pages
numberOfBlock = 1;
@@ -87,14 +95,10 @@
numberOfBlock = ((int) PageConstant.PAGE_SIZE - HEAD_TAIL_SIZE)
/ dataBlockSize;
}
- final int minSize = bits == PageConstant.MIN_DATA_BLOCK_BITS ? 0
+ minDataBlockDataSize = bits == PageConstant.MIN_DATA_BLOCK_BITS ? 0
: ((1 << (bits - 1)) + 1);
dataBlocks = new DataBlock[numberOfBlock];
- for (int dataBlockIndex = 0; dataBlockIndex < numberOfBlock; dataBlockIndex++) {
- dataBlocks[dataBlockIndex] = new DataBlock(this, dataBlockIndex, // NOPMD
- bits, minSize, maxSize);
-
- }
+ allData = new byte[numberOfBlock * dataBlockSize];
}
@Override
@@ -125,14 +129,23 @@
return numberOfBlock;
}
- public IDataBlock[] getDataBlocks() {
- return dataBlocks;// NOPMD
+ public byte[] getAllData() {
+ return allData; // NOPMD
}
+ public IDataBlock getDataBlock(final int index) {
+ IDataBlock dataBlock = dataBlocks[index];
+ if (dataBlock == null) {
+ dataBlock = dataBlocks[index] = new DataBlock(this, index, bits,
+ /* dataBlockSize, */minDataBlockDataSize, maxDataBlockDataSize);
+ }
+ return dataBlock;
+ }
+
public IDataBlock getDataBlock(final long dataBlockPosition) {
final int index = ((int) (dataBlockPosition - getPositionInFile()) - HEAD_SIZE)
/ dataBlockSize;
- return dataBlocks[index];
+ return getDataBlock(index);
}
public long getPositionInFile(final int index) {
@@ -140,13 +153,14 @@
}
public void setAllFree() throws HeapException {
- long nextPosition = getPositionInFile() + HEAD_SIZE + dataBlockSize;
- for (int index = 0; index < dataBlocks.length - 1; index++) {
- dataBlocks[index].setNextFreeDataBlockPositionOfFree(nextPosition);
- nextPosition += dataBlockSize;
+ long nextFreeDataBlockPosition = getPositionInFile() + HEAD_SIZE
+ + dataBlockSize;
+ for (int indexInDataBlockPage = 0; indexInDataBlockPage < numberOfBlock - 1; indexInDataBlockPage++) {
+ setNextFreeDataBlockPositionOfFree(indexInDataBlockPage,
+ nextFreeDataBlockPosition);
+ nextFreeDataBlockPosition += dataBlockSize;
}
- dataBlocks[dataBlocks.length - 1]
- .setNextFreeDataBlockPositionOfFree(-1L);
+ setNextFreeDataBlockPositionOfFree(numberOfBlock - 1, -1L);
setValueIsChangedValueToSave();
}
@@ -165,4 +179,87 @@
public int getInParentIndex() throws HeapException {
throw new HeapException("unsupported");
}
+
+ public void setData(final int indexInDataBlockPage, final byte[] data)
+ throws HeapException {
+ inAllDataIndex = indexInDataBlockPage * dataBlockSize;
+ final int size = data.length;
+ writeInteger(size);
+ writeBytes(data);
+ setValueIsChangedValueToSave();
+ }
+
+ public byte[] getData(final int indexInDataBlockPage) throws HeapException {
+ inAllDataIndex = indexInDataBlockPage * dataBlockSize;
+ final int size = readInteger();
+ final byte[] data = new byte[size];
+ readBytes(data);
+ return data;
+ }
+
+ public void setNextFreeDataBlockPositionOfFree(
+ final int indexInDataBlockPage, final long nextFreeDataBlockPosition)
+ throws HeapException {
+ inAllDataIndex = indexInDataBlockPage * dataBlockSize;
+ writeLong(nextFreeDataBlockPosition);
+ setValueIsChangedValueToSave();
+ }
+
+ public long getNextFreeDataBlockPositionOfFree(
+ final int indexInDataBlockPage) throws HeapException {
+ inAllDataIndex = indexInDataBlockPage * dataBlockSize;
+ return readLong();
+ }
+
+ protected int readInteger() throws HeapException {
+ int value = 0;
+ for (int byteIndex = 3; byteIndex >= 0; byteIndex--) {
+ final byte byteValue = allData[inAllDataIndex + byteIndex];
+ value = (value << 8) | (((int) byteValue) & 0xff);
+ }
+ inAllDataIndex += 4;
+ return value;
+ }
+
+ protected byte readByte() throws HeapException {
+ return allData[inAllDataIndex++];
+ }
+
+ protected void readBytes(final byte[] destination) throws HeapException {
+ final int length = destination.length;
+ System.arraycopy(allData, inAllDataIndex, destination, 0, length);
+ inAllDataIndex += length;
+ }
+
+ protected long readLong() throws HeapException {
+ long value = 0;
+ for (int byteIndex = 7; byteIndex >= 0; byteIndex--) {
+ final byte byteValue = allData[inAllDataIndex + byteIndex];
+ value = (value << 8) | (((long) byteValue) & 0xff);
+ }
+ inAllDataIndex += 8;
+ return value;
+ }
+
+ protected void writeBytes(final byte[] dataByteArray) throws HeapException {
+ System.arraycopy(dataByteArray, 0, allData, inAllDataIndex,
+ dataByteArray.length);
+ inAllDataIndex += dataByteArray.length;
+ }
+
+ protected void writeLong(final long value) throws HeapException {
+ long localValue = value;
+ for (int byteIndex = 0; byteIndex < 8; byteIndex++) {
+ allData[inAllDataIndex++] = (byte) localValue;
+ localValue >>= 8;
+ }
+ }
+
+ protected void writeInteger(final int value) throws HeapException {
+ int localValue = value;
+ for (int byteIndex = 0; byteIndex < 4; byteIndex++) {
+ allData[inAllDataIndex++] = (byte) localValue;
+ localValue >>= 8;
+ }
+ }
}
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/IDataBlock.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/IDataBlock.java 2012-05-09 02:32:21 UTC (rev 3081)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/IDataBlock.java 2012-05-09 04:56:39 UTC (rev 3082)
@@ -30,13 +30,13 @@
* @author luc peuvrier
*
*/
-public interface IDataBlock extends IStateStored {
+public interface IDataBlock {
long getPositionInFile();
void setData(byte[] data) throws HeapException;
- byte[] getData();
+ byte[] getData() throws HeapException;
/**
* the next free data block position is wrote on data, must be call only if
@@ -52,15 +52,14 @@
* make sense to be call only if this is a free data block
*
* @return next free data block position
+ * @throws HeapException
*/
- long getNextFreeDataBlockPositionOfFree();
+ long getNextFreeDataBlockPositionOfFree() throws HeapException;
- byte[] getDataHolder();
+ int getMinDataSize();
- int getMinSize();
+ int getMaxDataSize();
- int getMaxSize();
-
byte getBits();
int getIndexInDataBlockPage();
@@ -70,8 +69,4 @@
LeafPage getParentLeafPage();
int getIndexInLeafPage();
-
- int getSize();
-
- void setSize(int size);
}
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/LeafPage.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/LeafPage.java 2012-05-09 02:32:21 UTC (rev 3081)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/LeafPage.java 2012-05-09 04:56:39 UTC (rev 3082)
@@ -65,11 +65,6 @@
private int index;
- public LeafPage(final boolean longKey) throws HeapException {
- this(0, longKey);
- updateByteSize();
- }
-
public LeafPage(final int numberOfKeyEntries, final boolean longKey) {
super(longKey);
this.numberOfKeyEntries = numberOfKeyEntries;
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/NonTerminalPage.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/NonTerminalPage.java 2012-05-09 02:32:21 UTC (rev 3081)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/NonTerminalPage.java 2012-05-09 04:56:39 UTC (rev 3082)
@@ -69,12 +69,6 @@
private DataRecordIdentifier middleKey;
- @Fortest
- public NonTerminalPage(final boolean longKey) throws HeapException {
- this(0, longKey);
- updateByteSize();
- }
-
/**
* not static set creation
*
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/PageRecord.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/PageRecord.java 2012-05-09 02:32:21 UTC (rev 3081)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/PageRecord.java 2012-05-09 04:56:39 UTC (rev 3082)
@@ -36,6 +36,8 @@
@NotStorableClass
public class PageRecord extends AbstractPageRecord implements IPageRecord {
+ private static final String BAD_NUMBER_OF_ENTRIES = "bad number of entries ";
+
private EnumRecordType recordType;
private IPageRecordable pageRecordable;
@@ -207,6 +209,10 @@
assert pageRecordable.getByteSize() <= PageConstant.PAGE_SIZE;
final NonTerminalPage nonTerminalPage = (NonTerminalPage) pageRecordable;
final int numberOfKeyEntries = nonTerminalPage.getNumberOfKeyEntries();
+ if (numberOfKeyEntries <= 0
+ || numberOfKeyEntries > NonTerminalPage.MAX_NUMBER_OF_ENTRIES) {
+ throw new HeapException(BAD_NUMBER_OF_ENTRIES + numberOfKeyEntries);
+ }
writeInteger(numberOfKeyEntries);
for (int index = 0; index < numberOfKeyEntries; index++) {
writeLong(nonTerminalPage.getPagePointer(index));
@@ -218,6 +224,10 @@
private void unmarshallNonTerminalPage() throws HeapException {
final int numberOfKeyEntries = readInteger();
+ if (numberOfKeyEntries <= 0
+ || numberOfKeyEntries > NonTerminalPage.MAX_NUMBER_OF_ENTRIES) {
+ throw new HeapException(BAD_NUMBER_OF_ENTRIES + numberOfKeyEntries);
+ }
final NonTerminalPage nonTerminalPage = new NonTerminalPage(
numberOfKeyEntries, longKey);
nonTerminalPage.setPageRecord(this);
@@ -237,6 +247,10 @@
assert pageRecordable.getByteSize() <= PageConstant.PAGE_SIZE;
final LeafPage leafPage = (LeafPage) pageRecordable;
final int numberOfKeyEntries = leafPage.getNumberOfKeyEntries();
+ if (numberOfKeyEntries <= 0
+ || numberOfKeyEntries > LeafPage.MAX_NUMBER_OF_ENTRIES) {
+ throw new HeapException(BAD_NUMBER_OF_ENTRIES + numberOfKeyEntries);
+ }
writeInteger(numberOfKeyEntries);
for (int index = 0; index < numberOfKeyEntries; index++) {
writeKey(leafPage.getKey(index));
@@ -248,6 +262,10 @@
private void unmarshallLeafPage() throws HeapException {
final int numberOfKeyEntries = readInteger();
+ if (numberOfKeyEntries <= 0
+ || numberOfKeyEntries > LeafPage.MAX_NUMBER_OF_ENTRIES) {
+ throw new HeapException(BAD_NUMBER_OF_ENTRIES + numberOfKeyEntries);
+ }
final LeafPage leafPage = new LeafPage(numberOfKeyEntries, longKey);
leafPage.setPageRecord(this);
for (int index = 0; index < numberOfKeyEntries; index++) {
@@ -284,11 +302,8 @@
// ASSERTX
assert pageRecordable.getByteSize() <= numberOfPage
* PageConstant.PAGE_SIZE;
- final IDataBlock[] dataBlocks = dataBlockPage.getDataBlocks();
- for (IDataBlock dataBlock : dataBlocks) {
- writeInteger(dataBlock.getSize());
- writeBytes(dataBlock.getDataHolder());
- }
+ final byte[] allData = dataBlockPage.getAllData();
+ writeBytes(allData);
writeCrc32(0);
}
@@ -303,11 +318,8 @@
throw new HeapException("failed to get " + newSize
+ ", total read size is " + totalReadSize);
}
- final IDataBlock[] dataBlocks = dataBlockPage.getDataBlocks();
- for (IDataBlock dataBlock : dataBlocks) {
- dataBlock.setSize(readInteger());
- readBytes(dataBlock.getDataHolder());
- }
+ final byte[] allData = dataBlockPage.getAllData();
+ readBytes(allData);
readAndCheckCrc32(0);
pageRecordable = dataBlockPage;
}
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusDataManager.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusDataManager.java 2012-05-09 02:32:21 UTC (rev 3081)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusDataManager.java 2012-05-09 04:56:39 UTC (rev 3082)
@@ -248,8 +248,8 @@
created = false;
final IDataBlock dataBlock = btreePlusElementMgr
.getDataBlock(dataBlockPosition);
- if (data.length >= dataBlock.getMinSize()
- && data.length <= dataBlock.getMaxSize()) {
+ if (data.length >= dataBlock.getMinDataSize()
+ && data.length <= dataBlock.getMaxDataSize()) {
dataBlock.setData(data);
} else {
final int index = dataBlock.getIndexInDataBlockPage();
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgr.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgr.java 2012-05-09 02:32:21 UTC (rev 3081)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgr.java 2012-05-09 04:56:39 UTC (rev 3082)
@@ -292,7 +292,7 @@
heapElementManager.appendHeapFileRecord(pageRecord);
dataBlockPage.setAllFree();
header.incrementNumberOfFreeRecord(dataBlockPage.getNumberOfBlock());
- dataBlock = dataBlockPage.getDataBlocks()[0];
+ dataBlock = dataBlockPage.getDataBlock(0);
} else {
dataBlock = getDataBlock(freeDataBlockPosition);
}
Modified: trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/DataBlockPageTest.java
===================================================================
--- trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/DataBlockPageTest.java 2012-05-09 02:32:21 UTC (rev 3081)
+++ trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/DataBlockPageTest.java 2012-05-09 04:56:39 UTC (rev 3082)
@@ -80,15 +80,18 @@
assertEquals("bad byte size", dataBlockPageByteSize,
dataBlockPage.getByteSize());
dataBlockPage.setAllFree();
- final IDataBlock[] dataBlocks = dataBlockPage.getDataBlocks();
- assertEquals("number of block missmatch", numberOfBlock,
- dataBlocks.length);
+ // final IDataBlock[] dataBlocks = dataBlockPage.getDataBlocks();
+ // assertEquals("number of block missmatch", numberOfBlock,
+ // dataBlocks.length);
int index = 0;
long expectedCurrentPositionInFile = dataBlockPage.getPositionInFile()
+ DataBlockPage.HEAD_SIZE;
long nextFreeDataBlockPosition = dataBlockPage.getPositionInFile()
+ DataBlockPage.HEAD_SIZE;
- for (IDataBlock dataBlock : dataBlocks) {
+ // for (IDataBlock dataBlock : dataBlocks) {
+ for (int dataBlockIndex = 0; dataBlockIndex < numberOfBlock; dataBlockIndex++) {
+ final IDataBlock dataBlock = dataBlockPage
+ .getDataBlock(dataBlockIndex);
assertEquals("bad number of bits", bits, dataBlock.getBits());
final long positionInFile = dataBlock.getPositionInFile();
assertEquals("bad position in file", expectedCurrentPositionInFile,
Modified: trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/LeafPageTest.java
===================================================================
--- trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/LeafPageTest.java 2012-05-09 02:32:21 UTC (rev 3081)
+++ trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/LeafPageTest.java 2012-05-09 04:56:39 UTC (rev 3082)
@@ -54,7 +54,8 @@
}
public void testCreation() throws HeapException {
- final LeafPage leafPage = new LeafPage(true);
+ final LeafPage leafPage = new LeafPage(0, true);
+ leafPage.updateByteSize();
leafPage.setPageRecord(PAGE_RECORD);
assertEquals("must be empty", 0, leafPage.getNumberOfKeyEntries());
assertEquals("must be one page", 1, leafPage.getNumberOfPage());
@@ -64,7 +65,8 @@
}
public void testAdd() throws HeapException {
- final LeafPage leafPage = new LeafPage(true);
+ final LeafPage leafPage = new LeafPage(0, true);
+ leafPage.updateByteSize();
leafPage.setPageRecord(PAGE_RECORD);
addToLeafPage(leafPage, 1000/* position */, 10/* key value */, 10, 1);
checkContent(leafPage,
@@ -150,7 +152,7 @@
}
public void testSetParentPage() throws HeapException {
- final LeafPage leafPage = new LeafPage(true);
+ final LeafPage leafPage = new LeafPage(0, true);
leafPage.setPageRecord(PAGE_RECORD);
final IPageRecordable parentPage = new MockPageRecordable();
final int inParentIndex = 5;
@@ -161,7 +163,7 @@
}
public void testSetNext() throws HeapException {
- final LeafPage leafPage = new LeafPage(true);
+ final LeafPage leafPage = new LeafPage(0, true);
leafPage.setPageRecord(PAGE_RECORD);
final long next = 5000;
leafPage.setNext(next);
@@ -169,7 +171,8 @@
}
public void testSplit1() throws HeapException {
- final LeafPage leafPage = new LeafPage(true);
+ final LeafPage leafPage = new LeafPage(0, true);
+ leafPage.updateByteSize();
leafPage.setPageRecord(PAGE_RECORD);
final int maxNumberOfEntries = maxNumberOfEntries();
int count = 0;
@@ -188,7 +191,8 @@
}
public void testSplit2() throws HeapException {
- final LeafPage leafPage = new LeafPage(true);
+ final LeafPage leafPage = new LeafPage(0, true);
+ leafPage.updateByteSize();
leafPage.setPageRecord(PAGE_RECORD);
final int maxNumberOfEntries = maxNumberOfEntries();
int count = 1;
@@ -229,7 +233,8 @@
}
public void testRemove() throws HeapException {// NOPMD
- final LeafPage leafPage = new LeafPage(true);
+ final LeafPage leafPage = new LeafPage(0, true);
+ leafPage.updateByteSize();
addToLeafPage(leafPage,
/**/new int[] { 5, 7, 10, 15, 17 },
/**/new long[] { 2000, 4000, 1000, 3000, 5000 });
@@ -251,8 +256,10 @@
}
public void testEquilibrateMerge() throws HeapException {
- final LeafPage leftLeafPage = new LeafPage(true);
- final LeafPage rightLeafPage = new LeafPage(true);
+ final LeafPage leftLeafPage = new LeafPage(0, true);
+ leftLeafPage.updateByteSize();
+ final LeafPage rightLeafPage = new LeafPage(0, true);
+ rightLeafPage.updateByteSize();
addToLeafPage(leftLeafPage,
/**/new int[] { 5, 7, 10, 15, 17 },
/**/new long[] { 2000, 4000, 1000, 3000, 5000 });
@@ -268,10 +275,12 @@
}
public void testEquilibrateRightToLeft() throws HeapException {
- final LeafPage leftLeafPage = new LeafPage(true);
+ final LeafPage leftLeafPage = new LeafPage(0, true);
+ leftLeafPage.updateByteSize();
addToLeafPage(leftLeafPage, createKeys(1, 128 + 32),
createPointers(1000, 128 + 32));
- final LeafPage rightLeafPage = new LeafPage(true);
+ final LeafPage rightLeafPage = new LeafPage(0, true);
+ rightLeafPage.updateByteSize();
addToLeafPage(rightLeafPage, createKeys(1 + 128 + 32, 128 + 64),
createPointers(1000 + 128 + 32, 128 + 64));
assertEquals("must balance", 1,
@@ -283,10 +292,12 @@
}
public void testEquilibrateLeftToRight() throws HeapException {
- final LeafPage leftLeafPage = new LeafPage(true);
+ final LeafPage leftLeafPage = new LeafPage(0, true);
+ leftLeafPage.updateByteSize();
addToLeafPage(leftLeafPage, createKeys(1, 128 + 64),
createPointers(1000, 128 + 64));
- final LeafPage rightLeafPage = new LeafPage(true);
+ final LeafPage rightLeafPage = new LeafPage(0, true);
+ rightLeafPage.updateByteSize();
addToLeafPage(rightLeafPage, createKeys(1 + 128 + 64, 128 + 32),
createPointers(1000 + 128 + 64, 128 + 32));
assertEquals("must balance", 1,
Modified: trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/NonTerminalPageTest.java
===================================================================
--- trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/NonTerminalPageTest.java 2012-05-09 02:32:21 UTC (rev 3081)
+++ trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/NonTerminalPageTest.java 2012-05-09 04:56:39 UTC (rev 3082)
@@ -53,13 +53,14 @@
}
public void testCreation() throws HeapException {
- final NonTerminalPage nonTerminalPage = new NonTerminalPage(true);
- assertEquals("must be empty", 0,
+ final NonTerminalPage nonTerminalPage = new NonTerminalPage(1, true);
+ nonTerminalPage.updateByteSize();
+ assertEquals("bad number of entries", 1,
nonTerminalPage.getNumberOfKeyEntries());
assertEquals("must be one page", 1, nonTerminalPage.getNumberOfPage());
assertEquals("bad record type", EnumRecordType.NON_TERMINAL_PAGE,
nonTerminalPage.getRecordType());
- assertEquals("bad byte size", byteSize(0),
+ assertEquals("bad byte size", byteSize(1),
nonTerminalPage.getByteSize());
}
@@ -407,8 +408,8 @@
}
public void testSetParentPage() throws HeapException {
- final NonTerminalPage nonTerminalPage = new NonTerminalPage(true);
- final IPageRecordable parentPage = new NonTerminalPage(true);
+ final NonTerminalPage nonTerminalPage = new NonTerminalPage(1, true);
+ final IPageRecordable parentPage = new NonTerminalPage(1, true);
nonTerminalPage.setParentPage(parentPage, 10);
assertSame("bad parent page", parentPage,
nonTerminalPage.getParentPage());
Modified: trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/mock/MockDataBlock.java
===================================================================
--- trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/mock/MockDataBlock.java 2012-05-09 02:32:21 UTC (rev 3081)
+++ trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/mock/MockDataBlock.java 2012-05-09 04:56:39 UTC (rev 3082)
@@ -40,16 +40,6 @@
private long position;
- @Override
- public void setValueIsChangedValueToSave() throws HeapException {
- // no implementation
- }
-
- @Override
- public void setValueIsNotChanged() {
- // no implementation
- }
-
public void setPosition(final long position) {
this.position = position;
}
@@ -83,19 +73,13 @@
}
@Override
- public byte[] getDataHolder() {// NOPMD
+ public int getMinDataSize() {
// no implementation
- return null;
- }
-
- @Override
- public int getMinSize() {
- // no implementation
return 0;
}
@Override
- public int getMaxSize() {
+ public int getMaxDataSize() {
// no implementation
return 0;
}
@@ -129,15 +113,4 @@
// no implementation
return 0;
}
-
- @Override
- public int getSize() {
- // no implementation
- return 0;
- }
-
- @Override
- public void setSize(final int size) {
- // no implementation
- }
}
Modified: trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgrTest.java
===================================================================
--- trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgrTest.java 2012-05-09 02:32:21 UTC (rev 3081)
+++ trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgrTest.java 2012-05-09 04:56:39 UTC (rev 3082)
@@ -99,7 +99,10 @@
public void testAppendPageRecordable() throws HeapException {
btreePlusElementMgr.openTransaction();
- IPageRecordable pageRecordable = new LeafPage(true);
+ final LeafPage leafPage = new LeafPage(1, true);
+ leafPage.setEntry(0, 0, new DataRecordIdentifier());
+ leafPage.updateByteSize();
+ IPageRecordable pageRecordable = leafPage;
assertNull(MUST_BE_NOT_STORED, pageRecordable.getPageRecord());
btreePlusElementMgr.appendPageRecordable(pageRecordable);
pageRecordable.setValueIsChangedValueToSave();
@@ -110,7 +113,10 @@
assertEquals(BAD_LAST_RECORD_POSITION, PageConstant.PAGE_SIZE * 1,
btreePlusElementMgr.getLastRecordPositionInFile());
- pageRecordable = new NonTerminalPage(true);
+ NonTerminalPage nonTerminalPage = new NonTerminalPage(1, true);
+ nonTerminalPage.setKey(0, new DataRecordIdentifier());
+ pageRecordable = nonTerminalPage;
+ pageRecordable.updateByteSize();
assertNull(MUST_BE_NOT_STORED, pageRecordable.g...
[truncated message content] |
|
From: <luc...@us...> - 2012-05-09 04:56:46
|
Revision: 3082
http://joafip.svn.sourceforge.net/joafip/?rev=3082&view=rev
Author: luc_peuvrier
Date: 2012-05-09 04:56:39 +0000 (Wed, 09 May 2012)
Log Message:
-----------
WIP btree plus: data block access optimization
Modified Paths:
--------------
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/DataBlock.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/DataBlockPage.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/IDataBlock.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/LeafPage.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/NonTerminalPage.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/PageRecord.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusDataManager.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgr.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/DataBlockPageTest.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/LeafPageTest.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/NonTerminalPageTest.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/mock/MockDataBlock.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgrTest.java
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
Thanks for helping keep SourceForge clean.
X