[Joafip-svn] SF.net SVN: joafip:[3075] trunk
Brought to you by:
luc_peuvrier
Menu
▾
▴
[Joafip-svn] SF.net SVN: joafip:[3075] trunk
|
From: <luc...@us...> - 2012-05-08 05:55:44
|
Revision: 3075
http://joafip.svn.sourceforge.net/joafip/?rev=3075&view=rev
Author: luc_peuvrier
Date: 2012-05-08 05:55:35 +0000 (Tue, 08 May 2012)
Log Message:
-----------
WIP btree plus: new tests and corrections, rotation optimization
Modified Paths:
--------------
trunk/joafip-4test/src/main/java/net/sf/joafip/performance/items/service/AbstractInserter.java
trunk/joafip-4test/src/main/java/net/sf/joafip/performance/items/service/DeleterBtreePlus.java
trunk/joafip-4test/src/main/java/net/sf/joafip/performance/items/service/InserterBtreePlusIntigrityCheck.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/AbstractNodePage.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/IPageRecordable.java
trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/IntegrityCheckResult.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/PageNode.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/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/TestBtreePlusDataManager.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/service/TestBtreePlusDataManagerBackup.java
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/service/TestBtreePlusDataMgrWithScenario.java
trunk/joafip-kvstore/src/main/java/net/sf/joafip/kvstore/record/entity/DataRecordIdentifier.java
trunk/joafip-kvstore/src/main/java/net/sf/joafip/kvstore/record/entity/DataRecordKey.java
trunk/joafip-kvstore/src/main/java/net/sf/joafip/kvstore/record/service/HeapElementManager.java
trunk/joafip-testsuite/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusServiceTests.java
Added Paths:
-----------
trunk/joafip-btreeplus/logs/
trunk/joafip-btreeplus/src/main/resources/log4j.properties
trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/BigKey.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
Property Changed:
----------------
trunk/joafip-btreeplus/
Modified: trunk/joafip-4test/src/main/java/net/sf/joafip/performance/items/service/AbstractInserter.java
===================================================================
--- trunk/joafip-4test/src/main/java/net/sf/joafip/performance/items/service/AbstractInserter.java 2012-05-07 02:28:12 UTC (rev 3074)
+++ trunk/joafip-4test/src/main/java/net/sf/joafip/performance/items/service/AbstractInserter.java 2012-05-08 05:55:35 UTC (rev 3075)
@@ -171,8 +171,8 @@
final int identifier = Integer.parseInt(reader.readLine());
addItem(session, identifier);
+ // consistencyCheck();
insertLogWriter.println(identifier);
- // consistencyCheck();
if (count % BATCH_SIZE == BATCH_SIZE - 1) {
Modified: trunk/joafip-4test/src/main/java/net/sf/joafip/performance/items/service/DeleterBtreePlus.java
===================================================================
--- trunk/joafip-4test/src/main/java/net/sf/joafip/performance/items/service/DeleterBtreePlus.java 2012-05-07 02:28:12 UTC (rev 3074)
+++ trunk/joafip-4test/src/main/java/net/sf/joafip/performance/items/service/DeleterBtreePlus.java 2012-05-08 05:55:35 UTC (rev 3075)
@@ -33,6 +33,7 @@
import net.sf.joafip.file.service.HelperFileUtil;
import net.sf.joafip.kvstore.entity.EnumFileAccessMode;
import net.sf.joafip.kvstore.entity.HeapFileSetup;
+import net.sf.joafip.kvstore.record.entity.DataRecordIdentifier;
import net.sf.joafip.kvstore.service.HeapException;
import net.sf.joafip.kvstore.service.IHeapDataManager;
import net.sf.joafip.logger.JoafipLogger;
@@ -57,7 +58,9 @@
protected void consistencyCheck() throws HeapException,
FilePersistenceException {
final IntegrityCheckResult result = BtreePlusDataMgrIntegrityChecker
- .getInstance().checkIntegrity(getDataManager());
+ .getInstance().checkIntegrity(getDataManager(),
+ new DataRecordIdentifier(-1),
+ new DataRecordIdentifier(Long.MAX_VALUE));
System.out.println("depth " + result.getDepth());
System.out.println("entriesCount " + result.getEntriesCount());
System.out.println("leafPageCount " + result.getLeafPageCount());
Modified: trunk/joafip-4test/src/main/java/net/sf/joafip/performance/items/service/InserterBtreePlusIntigrityCheck.java
===================================================================
--- trunk/joafip-4test/src/main/java/net/sf/joafip/performance/items/service/InserterBtreePlusIntigrityCheck.java 2012-05-07 02:28:12 UTC (rev 3074)
+++ trunk/joafip-4test/src/main/java/net/sf/joafip/performance/items/service/InserterBtreePlusIntigrityCheck.java 2012-05-08 05:55:35 UTC (rev 3075)
@@ -2,6 +2,7 @@
import net.sf.joafip.btreeplus.entity.IntegrityCheckResult;
import net.sf.joafip.btreeplus.service.BtreePlusDataMgrIntegrityChecker;
+import net.sf.joafip.kvstore.record.entity.DataRecordIdentifier;
import net.sf.joafip.kvstore.service.HeapException;
import net.sf.joafip.logger.JoafipLogger;
import net.sf.joafip.service.FilePersistenceException;
@@ -16,7 +17,9 @@
protected void consistencyCheck() throws HeapException,
FilePersistenceException {
final IntegrityCheckResult result = BtreePlusDataMgrIntegrityChecker
- .getInstance().checkIntegrity(getDataManager());
+ .getInstance().checkIntegrity(getDataManager(),
+ new DataRecordIdentifier(-1),
+ new DataRecordIdentifier(Long.MAX_VALUE));
System.out.println("depth " + result.getDepth());
System.out.println("entriesCount " + result.getEntriesCount());
System.out.println("leafPageCount " + result.getLeafPageCount());
Property changes on: trunk/joafip-btreeplus
___________________________________________________________________
Modified: svn:ignore
- .settings
.classpath
.project
+ .settings
.classpath
.project
runtime
Modified: 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 2012-05-07 02:28:12 UTC (rev 3074)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/AbstractNodePage.java 2012-05-08 05:55:35 UTC (rev 3075)
@@ -41,6 +41,8 @@
this.longKey = longKey;
}
+ public abstract DataRecordIdentifier getLastKey();
+
protected int entrySize(final DataRecordIdentifier key) {
int entryByteSize = 8/* long size for pointer */+ 8/* long size for value */;
if (!longKey) {
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-07 02:28:12 UTC (rev 3074)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/DataBlockPage.java 2012-05-08 05:55:35 UTC (rev 3075)
@@ -76,7 +76,7 @@
} else {
numberOfPage = n + 1;
}
- // FIXMELUC ________waste space, see below
+ // FIXMELUC ____waste space, see below
// dataBlockDataSize=(numberOfPage<<PageConstant.PAGE_BITS)-
// HEAD_SIZE - 4/* crc32 */
} else {
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/IPageRecordable.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/IPageRecordable.java 2012-05-07 02:28:12 UTC (rev 3074)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/IPageRecordable.java 2012-05-08 05:55:35 UTC (rev 3075)
@@ -47,7 +47,7 @@
*/
int getByteSize();
- void updateByteSize();
+ void updateByteSize() throws HeapException;
IPageRecord getPageRecord() throws HeapException;
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/IntegrityCheckResult.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/IntegrityCheckResult.java 2012-05-07 02:28:12 UTC (rev 3074)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/IntegrityCheckResult.java 2012-05-08 05:55:35 UTC (rev 3075)
@@ -59,4 +59,19 @@
public int getNonTerminalPageCount() {
return nonTerminalPageCount;
}
+
+ @Override
+ public String toString() {
+ StringBuilder builder = new StringBuilder();
+ builder.append("IntegrityCheckResult [depth=");
+ builder.append(depth);
+ builder.append(", entriesCount=");
+ builder.append(entriesCount);
+ builder.append(", leafPageCount=");
+ builder.append(leafPageCount);
+ builder.append(", nonTerminalPageCount=");
+ builder.append(nonTerminalPageCount);
+ builder.append("]");
+ return builder.toString();
+ }
}
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-07 02:28:12 UTC (rev 3074)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/LeafPage.java 2012-05-08 05:55:35 UTC (rev 3075)
@@ -42,7 +42,7 @@
/**/4/* int size for crc32 */+
/**/8/* for next */;
- private static int MAX_NUMBER_OF_ENTRIES =
+ public static int MAX_NUMBER_OF_ENTRIES =
/**/(int) ((PageConstant.PAGE_SIZE - HEAD_TAIL_SIZE) / (8/*
* long size for
* pointer
@@ -65,7 +65,7 @@
private int index;
- public LeafPage(final boolean longKey) {
+ public LeafPage(final boolean longKey) throws HeapException {
this(0, longKey);
updateByteSize();
}
@@ -139,11 +139,11 @@
}
@Override
- public void updateByteSize() {
+ public void updateByteSize() throws HeapException {
byteSize = computeByteSize();
}
- private int computeByteSize() {
+ private int computeByteSize() throws HeapException {
int xbyteSize;
if (longKey) {
// <<4 for *16: 8 (long size for pointer) + 8 (long size for value)
@@ -153,10 +153,29 @@
for (int index = 0; index < numberOfKeyEntries; index++) {
xbyteSize += entrySize(nodes[index].dataRecordIdentifier);
}
+ if (xbyteSize > PageConstant.PAGE_SIZE) {
+ throw new HeapException("too much data " + xbyteSize
+ + " bytes for maximum of " + PageConstant.PAGE_SIZE);
+ }
}
return xbyteSize;
}
+ private int computeByteSize(final int offset, final int length) {
+ int xbyteSize;
+ if (longKey) {
+ // <<4 for *16: 8 (long size for pointer) + 8 (long size for value)
+ xbyteSize = HEAD_TAIL_SIZE + (length << 4);
+ } else {
+ xbyteSize = HEAD_TAIL_SIZE;
+ int index = offset;
+ for (int count = 0; count < length; count++) {
+ xbyteSize += entrySize(nodes[index++].dataRecordIdentifier);
+ }
+ }
+ return xbyteSize;
+ }
+
/**
*
* @param dataRecordIdentifier
@@ -236,6 +255,15 @@
return canAdd;
}
+ /**
+ *
+ * @param dataRecordIdentifier
+ * key to add
+ * @param dataBlock
+ * added data for the key
+ * @return
+ * @throws HeapException
+ */
public LeafPage split(final DataRecordIdentifier dataRecordIdentifier,
final IDataBlock dataBlock) throws HeapException {
final int insertBeforeIndex = computeInsertBeforeIndex(dataRecordIdentifier);
@@ -318,18 +346,19 @@
/**
*
* @param leafPage
- * @return true if merge in this page, leafPage is to be destroyed
+ * @return 0 if merged, 1 if balanced, or 2 if no changes
+ * @throws HeapException
*/
- public boolean equilibrate(final LeafPage leafPage) {
+ public int tryBalanceOrMerge(final LeafPage leafPage) throws HeapException {
// 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;
+ final int result;
if (byteSize + leafPageByteSize - HEAD_TAIL_SIZE <= PageConstant.PAGE_SIZE) {
- merged = true;
+ result = 0;// merged
System.arraycopy(leafPage.nodes, 0, nodes, numberOfKeyEntries,
leafPageNumberOfKeyEntries);
numberOfKeyEntries = totalNumberOfEntries;
@@ -339,39 +368,58 @@
assert byteSize == computeByteSize() : byteSize + " for "
+ computeByteSize() + " computed";
} else {
- merged = false;
final int newNumberOfEntries = totalNumberOfEntries / 2;
final int newLeafPageNumberOfEntries = totalNumberOfEntries
- newNumberOfEntries;
if (newNumberOfEntries > numberOfKeyEntries) {
- final int length = newNumberOfEntries - numberOfKeyEntries;
- System.arraycopy(leafPage.nodes, 0, nodes, numberOfKeyEntries,
- length);
-
- System.arraycopy(leafPage.nodes, length, leafPage.nodes, 0,
- leafPageNumberOfKeyEntries);
-
- numberOfKeyEntries = newNumberOfEntries;
- leafPage.numberOfKeyEntries = newLeafPageNumberOfEntries;
- updateByteSize();
- leafPage.updateByteSize();
+ // right to left
+ if (longKey) {
+ result = 1;
+ } else {
+ final int newLeftSize = byteSize
+ + leafPage.computeByteSize(0,
+ leafPageNumberOfKeyEntries
+ - newLeafPageNumberOfEntries);
+ result = newLeftSize > PageConstant.PAGE_SIZE ? 2 : 1;
+ }
+ if (result == 1) {
+ final int length = newNumberOfEntries - numberOfKeyEntries;
+ System.arraycopy(leafPage.nodes, 0, nodes,
+ numberOfKeyEntries, length);
+ System.arraycopy(leafPage.nodes, length, leafPage.nodes, 0,
+ newLeafPageNumberOfEntries);
+ numberOfKeyEntries = newNumberOfEntries;
+ leafPage.numberOfKeyEntries = newLeafPageNumberOfEntries;
+ updateByteSize();
+ leafPage.updateByteSize();
+ }
} else if (newLeafPageNumberOfEntries > leafPageNumberOfKeyEntries) {
- final int length = newLeafPageNumberOfEntries
- - leafPageNumberOfKeyEntries;
-
- System.arraycopy(leafPage.nodes, 0, leafPage.nodes, length,
- leafPageNumberOfKeyEntries);
-
- System.arraycopy(nodes, newNumberOfEntries, leafPage.nodes, 0,
- length);
-
- numberOfKeyEntries = newNumberOfEntries;
- leafPage.numberOfKeyEntries = newLeafPageNumberOfEntries;
- updateByteSize();
- leafPage.updateByteSize();
- }// else no changes
+ // left to right
+ if (longKey) {
+ result = 1;
+ } else {
+ final int newRightSize = leafPageByteSize
+ + computeByteSize(newNumberOfEntries,
+ numberOfKeyEntries - newNumberOfEntries);
+ result = newRightSize > PageConstant.PAGE_SIZE ? 2 : 1;
+ }
+ if (result == 1) {
+ final int length = newLeafPageNumberOfEntries
+ - leafPageNumberOfKeyEntries;
+ System.arraycopy(leafPage.nodes, 0, leafPage.nodes, length,
+ leafPageNumberOfKeyEntries);
+ System.arraycopy(nodes, newNumberOfEntries, leafPage.nodes,
+ 0, length);
+ numberOfKeyEntries = newNumberOfEntries;
+ leafPage.numberOfKeyEntries = newLeafPageNumberOfEntries;
+ updateByteSize();
+ leafPage.updateByteSize();
+ }
+ } else {
+ result = 2; // no changes
+ }
}
- return merged;
+ return result;
}
public DataRecordIdentifier getFirstKey() {
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-07 02:28:12 UTC (rev 3074)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/NonTerminalPage.java 2012-05-08 05:55:35 UTC (rev 3075)
@@ -44,7 +44,7 @@
/**/4/* int size for crc32 */+
/**/8/* last pointer long size */;
- private static int MAX_NUMBER_OF_ENTRIES =
+ public static int MAX_NUMBER_OF_ENTRIES =
/**/(int) ((PageConstant.PAGE_SIZE - HEAD_TAIL_SIZE) / (8/*
* long size for
* pointer
@@ -69,11 +69,18 @@
private DataRecordIdentifier middleKey;
- public NonTerminalPage(final boolean longKey) {
+ @Fortest
+ public NonTerminalPage(final boolean longKey) throws HeapException {
this(0, longKey);
updateByteSize();
}
+ /**
+ * not static set creation
+ *
+ * @param numberOfKeyEntries
+ * @param longKey
+ */
public NonTerminalPage(final int numberOfKeyEntries, final boolean longKey) {
super(longKey);
this.numberOfKeyEntries = numberOfKeyEntries;
@@ -83,7 +90,7 @@
@Fortest
public NonTerminalPage(final int numberOfKeyEntries,
final DataRecordIdentifier[] keys, final long[] pagePosition,
- final boolean longKey) {
+ final boolean longKey) throws HeapException {
super(longKey);
assert numberOfKeyEntries == keys.length
&& numberOfKeyEntries + 1 == pagePosition.length;
@@ -92,6 +99,8 @@
System.arraycopy(pagePosition, 0, this.pagePositions, 0,
numberOfKeyEntries + 1);
updateByteSize();
+ // ASSERTX
+ assert checkKeys();
}
@Override
@@ -128,6 +137,9 @@
keys[index] = key;
}
setValueIsChangedValueToSave();
+ // no because us for state setting
+ // //ASSERTX
+ // assert checkKeys();
}
/**
@@ -140,13 +152,23 @@
*/
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;
+ if (longKey) {
+ keys[index] = key;
+ // ASSERTX
+ assert checkKeys();
+ setValueIsChangedValueToSave();
+ return true;
+ } else {
+ DataRecordIdentifier oldKey = keys[index];
+ keys[index] = key;
+ // ASSERTX
+ assert checkKeys();
+ byteSize = byteSize - entrySize(oldKey) + entrySize(key);
+ // ASSERTX
+ assert byteSize == computeByteSize();
+ setValueIsChangedValueToSave();
+ return byteSize < PageConstant.PAGE_SIZE;
+ }
}
@Override
@@ -157,11 +179,16 @@
}
@Override
- public void updateByteSize() {
+ public void updateByteSize() throws HeapException {
byteSize = computeByteSize();
}
- private int computeByteSize() {
+ @Fortest
+ public void updateByteSizeAcceptBigger() throws HeapException {
+ byteSize = computeByteSizeAcceptBigger();
+ }
+
+ private int computeByteSize() throws HeapException {
int xbyteSize;
if (longKey) {
// <<4 for *16: 8 (long size for pointer) + 8 (long size for value)
@@ -172,9 +199,51 @@
xbyteSize += entrySize(keys[index]);
}
}
+ if (xbyteSize > PageConstant.PAGE_SIZE) {
+ throw new HeapException("too much data " + xbyteSize
+ + " bytes for maximum of " + PageConstant.PAGE_SIZE);
+ }
return xbyteSize;
}
+ private int computeByteSizeAcceptBigger() {
+ 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;
+ for (int index = 0; index < numberOfKeyEntries; index++) {
+ xbyteSize += entrySize(keys[index]);
+ }
+ }
+ return xbyteSize;
+ }
+
+ private int computeByteSize(final int offset, final int length)
+ throws HeapException {
+ int xbyteSize;
+ if (longKey) {
+ // <<4 for *16: 8 (long size for pointer) + 8 (long size for value)
+ xbyteSize = HEAD_TAIL_SIZE + (length << 4);
+ } else {
+ xbyteSize = HEAD_TAIL_SIZE;
+ int index = offset;
+ for (int count = 0; count < length; count++) {
+ xbyteSize += entrySize(keys[index++]);
+ }
+ }
+ return xbyteSize;
+ }
+
+ private int computeByteSizeForAssert() {
+ try {
+ return computeByteSize();
+ } catch (HeapException exception) {
+ throw new AssertionError(exception);
+ }
+ }
+
@Override
public int getNumberOfKeyEntries() {
return numberOfKeyEntries;
@@ -241,10 +310,12 @@
keys[index] = key;
pagePositions[index + 1] = newRightILeafPage.getPositionInFile();
// ASSERTX
+ assert checkKeys();
+ // ASSERTX
assert byteSize != 0 : "unknow current byte size";
byteSize += entrySize;
// ASSERTX
- assert byteSize == computeByteSize();
+ assert byteSize == computeByteSizeAcceptBigger();
setValueIsChangedValueToSave();
return byteSize < PageConstant.PAGE_SIZE;
}
@@ -274,10 +345,12 @@
pagePositions[index + 1] = rightSonNonTerminalPage.getPositionInFile();
// ASSERTX
+ assert checkKeys();
+ // ASSERTX
assert byteSize != 0 : "unknow current byte size";
byteSize += entrySize;
// ASSERTX
- assert byteSize == computeByteSize();
+ assert byteSize == computeByteSizeAcceptBigger();
setValueIsChangedValueToSave();
return byteSize < PageConstant.PAGE_SIZE;
}
@@ -296,6 +369,10 @@
System.arraycopy(pagePositions, splitIndex + 1,
nonTerminalPage.pagePositions, 0, newNumberOfKeyEntries + 1);
+ // ASSERTX
+ assert checkKeys();
+ assert nonTerminalPage.checkKeys();
+
nonTerminalPage.updateByteSize();
numberOfKeyEntries = newNumberOfKeyEntries;
updateByteSize();
@@ -325,11 +402,13 @@
System.arraycopy(pagePositions, leafPageInParentIndex + 1,
pagePositions, leafPageInParentIndex, length + 1);
// ASSERTX
+ assert checkKeys();
+ // ASSERTX
assert byteSize != 0 : "unknow current byte size";
byteSize -= entrySize(key);
// ASSERTX
- assert byteSize == computeByteSize() : "byteSize=" + byteSize
- + ", computed=" + computeByteSize();
+ assert byteSize == computeByteSizeForAssert() : "byteSize=" + byteSize
+ + ", computed=" + computeByteSizeForAssert();
}
public boolean wellFilled() {
@@ -343,20 +422,21 @@
*
* @param middleKey
* @param rightNonTerminalPage
- * @return true if merge in this page, nonTerminalPage is to be destroyed
+ * @return 0 if merged, 1 if balanced, or 2 if no changes
+ * @throws HeapException
*/
- public boolean equilibrate(final DataRecordIdentifier middleKey,
- final NonTerminalPage rightNonTerminalPage) {
+ public int tryBalanceOrMerge(final DataRecordIdentifier middleKey,
+ final NonTerminalPage rightNonTerminalPage) throws HeapException {
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;
+ final int result;
if (byteSize + middleKeySize + rightPageByteSize - HEAD_TAIL_SIZE <= PageConstant.PAGE_SIZE) {
// can merge
- merged = true;
+ result = 0;
System.arraycopy(rightNonTerminalPage.pagePositions, 0,
pagePositions, numberOfKeyEntries + 1,
rightPageNumberOfKeyEntries + 1);
@@ -366,59 +446,94 @@
numberOfKeyEntries = totalNumberOfEntries + 1;
byteSize += middleKeySize + rightPageByteSize - HEAD_TAIL_SIZE;
// ASSERTX
+ assert checkKeys();
+ // 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;
- System.arraycopy(rightNonTerminalPage.pagePositions, 0,
- pagePositions, numberOfKeyEntries + 1, length);
- 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;
- System.arraycopy(rightNonTerminalPage.pagePositions, length,
- rightNonTerminalPage.pagePositions, 0,
- rightPageNumberOfKeyEntries + 1);
- System.arraycopy(rightNonTerminalPage.keys, length,
- rightNonTerminalPage.keys, 0,
- rightPageNumberOfKeyEntries);
- rightNonTerminalPage.numberOfKeyEntries = newRightPageNumberOfEntries;
- rightNonTerminalPage.updateByteSize();
+ // right to left
+ if (longKey) {
+ result = 1;
+ } else {
+ final int newLeftSize = byteSize
+ + middleKeySize
+ + rightNonTerminalPage.computeByteSize(0,
+ rightPageNumberOfKeyEntries
+ - newRightPageNumberOfEntries);
+ result = newLeftSize > PageConstant.PAGE_SIZE ? 2 : 1;
+ }
+ if (result == 1) {
+ int length = newNumberOfEntries - numberOfKeyEntries;
+ System.arraycopy(rightNonTerminalPage.pagePositions, 0,
+ pagePositions, numberOfKeyEntries + 1, length);
+ keys[numberOfKeyEntries] = middleKey;
+ System.arraycopy(rightNonTerminalPage.keys, 0, keys,
+ numberOfKeyEntries + 1, length - 1);
+ this.middleKey = rightNonTerminalPage.keys[length - 1];
+ numberOfKeyEntries = newNumberOfEntries;
+ // ASSERTX
+ assert checkKeys();
+ updateByteSize();
+ length = rightPageNumberOfKeyEntries
+ - newRightPageNumberOfEntries;
+ System.arraycopy(rightNonTerminalPage.pagePositions,
+ length, rightNonTerminalPage.pagePositions, 0,
+ newRightPageNumberOfEntries + 1);
+ System.arraycopy(rightNonTerminalPage.keys, length,
+ rightNonTerminalPage.keys, 0,
+ newRightPageNumberOfEntries);
+ rightNonTerminalPage.numberOfKeyEntries = newRightPageNumberOfEntries;
+ rightNonTerminalPage.updateByteSize();
+ // ASSERTX
+ assert rightNonTerminalPage.checkKeys();
+ }
} else if (newRightPageNumberOfEntries > rightPageNumberOfKeyEntries) {
- final int length = newRightPageNumberOfEntries
- - rightPageNumberOfKeyEntries;
- this.middleKey = keys[newNumberOfEntries];
+ // left to right
+ if (longKey) {
+ result = 1;
+ } else {
+ final int newRightSize = rightPageByteSize
+ + middleKeySize
+ + computeByteSize(newNumberOfEntries,
+ numberOfKeyEntries - newNumberOfEntries);
+ result = newRightSize > PageConstant.PAGE_SIZE ? 2 : 1;
+ }
+ if (result == 1) {
+ final int length = newRightPageNumberOfEntries
+ - rightPageNumberOfKeyEntries;
+ this.middleKey = keys[newNumberOfEntries];
- System.arraycopy(rightNonTerminalPage.pagePositions, 0,
- rightNonTerminalPage.pagePositions, length,
- rightPageNumberOfKeyEntries + 1);
- System.arraycopy(rightNonTerminalPage.keys, 0,
- rightNonTerminalPage.keys, length,
- rightPageNumberOfKeyEntries);
+ System.arraycopy(rightNonTerminalPage.pagePositions, 0,
+ rightNonTerminalPage.pagePositions, length,
+ rightPageNumberOfKeyEntries + 1);
+ 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);
+ 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.keys[length - 1] = middleKey;
- rightNonTerminalPage.numberOfKeyEntries = newRightPageNumberOfEntries;
- rightNonTerminalPage.updateByteSize();
- numberOfKeyEntries = newNumberOfEntries;
- updateByteSize();
+ rightNonTerminalPage.numberOfKeyEntries = newRightPageNumberOfEntries;
+ rightNonTerminalPage.updateByteSize();
+ numberOfKeyEntries = newNumberOfEntries;
+ updateByteSize();
+ // ASSERTX
+ assert checkKeys();
+ assert rightNonTerminalPage.checkKeys();
+ }
+ } else {
+ result = 2;
}
}
- return merged;
+ return result;
}
public DataRecordIdentifier getLastKey() {
@@ -432,4 +547,20 @@
public DataRecordIdentifier getFirstKey() {
return keys[0];
}
+
+ /**
+ * for assertion
+ *
+ * @return true if keys ok
+ */
+ public boolean checkKeys() {
+ DataRecordIdentifier currentKey = keys[0];
+ boolean ok = true;
+ for (int index = 1; ok && index < numberOfKeyEntries; index++) {
+ final DataRecordIdentifier nextKey = keys[index];
+ ok = currentKey.compareTo(nextKey) < 0;
+ currentKey = nextKey;
+ }
+ return ok;
+ }
}
Modified: trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/PageNode.java
===================================================================
--- trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/PageNode.java 2012-05-07 02:28:12 UTC (rev 3074)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/entity/PageNode.java 2012-05-08 05:55:35 UTC (rev 3075)
@@ -43,4 +43,15 @@
this.dataRecordIdentifier = dataRecordIdentifier;
this.pointer = pointer;
}
+
+ @Override
+ public String toString() {
+ final StringBuilder builder = new StringBuilder();
+ builder.append("PageNode [dataRecordIdentifier=");
+ builder.append(dataRecordIdentifier);
+ builder.append(", pointer=");
+ builder.append(pointer);
+ builder.append("]");
+ return builder.toString();
+ }
}
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-07 02:28:12 UTC (rev 3074)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusDataManager.java 2012-05-08 05:55:35 UTC (rev 3075)
@@ -201,10 +201,10 @@
final DataRecordIdentifier dataRecordIdentifier, final byte[] data)
throws HeapException {
final IPageRecordable root = btreePlusElementMgr.getRoot();
- LeafPage leafPage = leafPage(root, dataRecordIdentifier);
+ final LeafPage leafPage = leafPage(root, dataRecordIdentifier);
final boolean created;
if (leafPage == null) {
- // no existing data
+ // no existing data because no leaf page for key
created = true;
final IDataBlock dataBlock = btreePlusElementMgr
.createDataBlock(data);
@@ -212,7 +212,7 @@
.newRootLeafPage(dataRecordIdentifier, dataBlock);
btreePlusElementMgr.incrementNumberOfDataRecord();
} else {
- // existing data
+ // existing leaf page for key
long dataBlockPosition = leafPage
.getDataBlockPosition(dataRecordIdentifier);
if (dataBlockPosition == -1) {
@@ -221,22 +221,19 @@
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);
- newLeafPage.setValueIsChangedValueToSave();
- leafPage.setNext(newLeafPage.getPositionInFile());
-
- NonTerminalPage nonTerminalPage = (NonTerminalPage) leafPage
+ final NonTerminalPage nonTerminalPage = (NonTerminalPage) leafPage
.getParentPage();
if (nonTerminalPage == null) {
- btreePlusElementMgr.newRootNonTerminalPage(leafPage,
- newLeafPage);
+ splitLeafPage(leafPage, dataRecordIdentifier,
+ nonTerminalPage, dataBlock);
+ } else if (tryBalanceOrMerge(leafPage, nonTerminalPage)) {
+ if (!leafPage.add(dataRecordIdentifier, dataBlock)) {
+ splitLeafPage(leafPage, dataRecordIdentifier,
+ nonTerminalPage, dataBlock);
+ }
} else {
- if (!nonTerminalPage.add(leafPage, newLeafPage)) {
- equilibrateFull(nonTerminalPage);
- }
+ splitLeafPage(leafPage, dataRecordIdentifier,
+ nonTerminalPage, dataBlock);
}
}
btreePlusElementMgr.incrementNumberOfDataRecord();
@@ -262,38 +259,32 @@
/**
*
+ * @param leafPage
+ * in which split and add
+ * @param dataRecordIdentifier
+ * key to add
* @param nonTerminalPage
- * a too big page
+ * parent page
+ * @param dataBlock
+ * added data for the key
* @throws HeapException
*/
- private void equilibrateFull(NonTerminalPage nonTerminalPage)
+ private void splitLeafPage(final LeafPage leafPage,
+ final DataRecordIdentifier dataRecordIdentifier,
+ final NonTerminalPage nonTerminalPage, final IDataBlock dataBlock)
throws HeapException {
- // FIXMELUC ________rotation, dispatch on sibling
- INonTerminalPage newNonTerminalPage = nonTerminalPage.split();
- DataRecordIdentifier middleKey = nonTerminalPage.getAndClearMiddleKey();
- // ASSERTX
- assert middleKey != null;
- do {
- btreePlusElementMgr.appendPageRecordable(newNonTerminalPage);
- newNonTerminalPage.setValueIsChangedValueToSave();
- NonTerminalPage parent = (NonTerminalPage) nonTerminalPage
- .getParentPage();
- if (parent == null) {
- btreePlusElementMgr.newRootNonTerminalPage(nonTerminalPage,
- middleKey, newNonTerminalPage);
- newNonTerminalPage = null;
- } else {
- if (parent.add(nonTerminalPage, middleKey, newNonTerminalPage)) {
- newNonTerminalPage = null;
- } else {
- newNonTerminalPage = parent.split();
- middleKey = parent.getAndClearMiddleKey();
- // ASSERTX
- assert middleKey != null;
- nonTerminalPage = parent;
- }
+ LeafPage newLeafPage = leafPage.split(dataRecordIdentifier, dataBlock);
+ btreePlusElementMgr.appendPageRecordable(newLeafPage);
+ newLeafPage.setValueIsChangedValueToSave();
+ leafPage.setNext(newLeafPage.getPositionInFile());
+
+ if (nonTerminalPage == null) {
+ btreePlusElementMgr.newRootNonTerminalPage(leafPage, newLeafPage);
+ } else {
+ if (!nonTerminalPage.add(leafPage, newLeafPage)) {
+ split(nonTerminalPage);
}
- } while (newNonTerminalPage != null);
+ }
}
@Override
@@ -306,7 +297,7 @@
deleted = false;
} else {
deleted = true;
- LeafPage leafPage = dataBlock.getParentLeafPage();
+ final LeafPage leafPage = dataBlock.getParentLeafPage();
int indexInLeafPage = dataBlock.getIndexInLeafPage();
btreePlusElementMgr.remove(dataBlock);
leafPage.remove(indexInLeafPage);
@@ -318,63 +309,18 @@
btreePlusElementMgr.removeRoot();
}
} else {
- final int leafPageInParentIndex = leafPage.getInParentIndex();
if (leafPage.wellFilled()) {
+ final int leafPageInParentIndex = leafPage
+ .getInParentIndex();
if (leafPageInParentIndex != nonTerminalPage
.getNumberOfKeyEntries()) {
if (!nonTerminalPage.setKey(leafPageInParentIndex,
leafPage.getLastKey())) {
- equilibrateFull(nonTerminalPage);
+ split(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 {
- if (!nonTerminalPage.setKey(leafPageInParentIndex,
- leafPage.getLastKey())) {
- equilibrateFull(nonTerminalPage);
- }
- }
+ } else {
+ tryBalanceOrMerge(leafPage, nonTerminalPage);
}
}
btreePlusElementMgr.decrementNumberOfDataRecord();
@@ -382,87 +328,224 @@
return deleted;
}
- private void equilibrate(final NonTerminalPage nonTerminalPage)
+ /**
+ *
+ * @param leafPage
+ * @param leafPageParentNonTerminalPage
+ * @return true if balancing done
+ * @throws HeapException
+ */
+ private boolean tryBalanceOrMerge(final LeafPage leafPage,
+ final NonTerminalPage leafPageParentNonTerminalPage)
throws HeapException {
- if (!nonTerminalPage.wellFilled()) {
- NonTerminalPage parentNonterminal = (NonTerminalPage) nonTerminalPage
+ final int leafPageInParentIndex = leafPage.getInParentIndex();
+ int result;
+ if (leafPageInParentIndex == 0) {
+ result = 2;
+ } else {
+ final int leftLeafPageInParentIndex = leafPageInParentIndex - 1;
+ final long leftLeafPagePosition = leafPageParentNonTerminalPage
+ .getPagePointer(leftLeafPageInParentIndex);
+ final LeafPage leftLeafPage = (LeafPage) btreePlusElementMgr
+ .getPage(leftLeafPagePosition,
+ leafPageParentNonTerminalPage,
+ leftLeafPageInParentIndex);
+ result = leftLeafPage.tryBalanceOrMerge(leafPage);
+ if (result == 0) {
+ // leaf page merged in left leaf page
+ btreePlusElementMgr.freePage(leafPage.getPageRecord());
+ leafPageParentNonTerminalPage.remove(leafPageInParentIndex);
+ if (leafPageParentNonTerminalPage.setKey(
+ leftLeafPageInParentIndex, leftLeafPage.getLastKey())) {
+ if (!leafPageParentNonTerminalPage.wellFilled()) {
+ tryBalance(leafPageParentNonTerminalPage);
+ }
+ } else {
+ split(leafPageParentNonTerminalPage);
+ }
+ } else if (result == 1) {
+ if (!leafPageParentNonTerminalPage.setKey(
+ leftLeafPageInParentIndex, leftLeafPage.getLastKey())) {
+ split(leafPageParentNonTerminalPage);
+ }
+ }
+ }
+
+ if (result == 2
+ && leafPageInParentIndex != leafPageParentNonTerminalPage
+ .getNumberOfKeyEntries()) {
+ final int rightLeafPageinParentIndex = leafPageInParentIndex + 1;
+ final long rightLeafPagePosition = leafPageParentNonTerminalPage
+ .getPagePointer(rightLeafPageinParentIndex);
+ final LeafPage rightLeafPage = (LeafPage) btreePlusElementMgr
+ .getPage(rightLeafPagePosition,
+ leafPageParentNonTerminalPage,
+ rightLeafPageinParentIndex);
+ result = leafPage.tryBalanceOrMerge(rightLeafPage);
+ if (result == 0) {
+ // right leaf page merged in leaf page
+ btreePlusElementMgr.freePage(rightLeafPage.getPageRecord());
+ leafPageParentNonTerminalPage
+ .remove(rightLeafPageinParentIndex);
+ if (leafPageParentNonTerminalPage.setKey(leafPageInParentIndex,
+ leafPage.getLastKey())) {
+ if (!leafPageParentNonTerminalPage.wellFilled()) {
+ tryBalance(leafPageParentNonTerminalPage);
+ }
+ } else {
+ split(leafPageParentNonTerminalPage);
+ }
+ } else if (result == 1) {
+ if (!leafPageParentNonTerminalPage.setKey(
+ leafPageInParentIndex, leafPage.getLastKey())) {
+ split(leafPageParentNonTerminalPage);
+ }
+ }
+ }
+ return result != 2;
+ }
+
+ /**
+ *
+ * @param nonTerminalPage
+ * a too big page
+ * @throws HeapException
+ */
+ private void split(NonTerminalPage nonTerminalPage) throws HeapException {
+ if (!tryBalance(nonTerminalPage)) {
+ final INonTerminalPage newNonTerminalPage = nonTerminalPage.split();
+ final DataRecordIdentifier middleKey = nonTerminalPage
+ .getAndClearMiddleKey();
+ // ASSERTX
+ assert middleKey != null;
+ btreePlusElementMgr.appendPageRecordable(newNonTerminalPage);
+ newNonTerminalPage.setValueIsChangedValueToSave();
+ final NonTerminalPage parent = (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);
+ if (parent == null) {
+ btreePlusElementMgr.newRootNonTerminalPage(nonTerminalPage,
+ middleKey, newNonTerminalPage);
+ } else if (!parent.add(nonTerminalPage, middleKey,
+ newNonTerminalPage)) {
+ split(parent);
+ }
+ }
+ }
+
+ /**
+ *
+ * @param nonTerminalPage
+ * @return true if change made
+ * @throws HeapException
+ */
+ private boolean tryBalance(final NonTerminalPage nonTerminalPage)
+ throws HeapException {
+ final NonTerminalPage parentNonterminal = (NonTerminalPage) nonTerminalPage
+ .getParentPage();
+ int result;
+ if (parentNonterminal == null) {
+ result = 2;
+ } else {
+ int inParentIndex = nonTerminalPage.getInParentIndex();
+ if (inParentIndex == 0) {
+ result = 2;
+ } else {
+ final int leftPageInParentIndex = inParentIndex - 1;
+ final long leftPagePosition = parentNonterminal
+ .getPagePointer(leftPageInParentIndex);
+ final NonTerminalPage leftPage = (NonTerminalPage) btreePlusElementMgr
+ .getPage(leftPagePosition, parentNonterminal,
+ leftPageInParentIndex);
+ // final long middlePagePosition =
+ // leftPage.getLastPagePosition();
+ // final AbstractNodePage middlePage = (AbstractNodePage)
+ // btreePlusElementMgr.getPage(middlePagePosition, null,-1);
+ // final DataRecordIdentifier middleKey=middlePage.getLastKey();
+ final DataRecordIdentifier middleKey = parentNonterminal
+ .getKey(leftPageInParentIndex);
+ result = leftPage.tryBalanceOrMerge(middleKey, nonTerminalPage);
+ if (result == 0) {
+ // page merged in left page
+ btreePlusElementMgr.freePage(nonTerminalPage
+ .getPageRecord());
+ parentNonterminal.remove(inParentIndex);
+ if (parentNonterminal.setKey(leftPageInParentIndex,
+ leftPage.getAndClearMiddleKey())) {
+ if (!parentNonterminal.wellFilled()) {
+ tryBalance(parentNonterminal);
}
} else {
- if (!nonTerminalPage.setKey(leftPageInParentIndex,
- leftPage.getAndClearMiddleKey())) {
- equilibrateFull(nonTerminalPage);
- }
+ split(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 (result == 1) {
+ if (!parentNonterminal.setKey(leftPageInParentIndex,
+ leftPage.getAndClearMiddleKey())) {
+ split(nonTerminalPage);
+ }
+ }
+ }
+
+ if (result == 2
+ && inParentIndex != parentNonterminal
+ .getNumberOfKeyEntries()) {
+ final int rightPageinParentIndex = inParentIndex + 1;
+ final long rightPagePosition = parentNonterminal
+ .getPagePointer(rightPageinParentIndex);
+ final NonTerminalPage rightPage = (NonTerminalPage) btreePlusElementMgr
+ .getPage(rightPagePosition, parentNonterminal,
+ rightPageinParentIndex);
+ // final long middlePagePosition =
+ // nonTerminalPage.getLastPagePosition();
+ // final AbstractNodePage middlePage = (AbstractNodePage)
+ // btreePlusElementMgr.getPage(middlePagePosition, null,-1);
+ // final DataRecordIdentifier middleKey=middlePage.getLastKey();
+ final DataRecordIdentifier middleKey = parentNonterminal
+ .getKey(inParentIndex);
+ result = nonTerminalPage
+ .tryBalanceOrMerge(middleKey, rightPage);
+ if (result == 0) {
+ // right leaf page merged in leaf page
+ btreePlusElementMgr.freePage(rightPage.getPageRecord());
+ parentNonterminal.remove(rightPageinParentIndex);
+ if (parentNonterminal.setKey(inParentIndex,
+ nonTerminalPage.getAndClearMiddleKey())) {
+ if (!parentNonterminal.wellFilled()) {
+ tryBalance(parentNonterminal);
}
} else {
- if (!nonTerminalPage.setKey(inParentIndex,
- nonTerminalPage.getAndClearMiddleKey())) {
- equilibrateFull(nonTerminalPage);
- }
+ split(nonTerminalPage);
}
+ } else if (result == 1) {
+ if (!parentNonterminal.setKey(inParentIndex,
+ nonTerminalPage.getAndClearMiddleKey())) {
+ split(nonTerminalPage);
+ }
}
}
}
+ return result != 2;
}
- 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;
- }
+ // 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
protected DataRecordIdentifier removeFirstDataRecordImpl()
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-07 02:28:12 UTC (rev 3074)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusDataMgrIntegrityChecker.java 2012-05-08 05:55:35 UTC (rev 3075)
@@ -32,6 +32,7 @@
import net.sf.joafip.btreeplus.entity.IntegrityCheckResult;
import net.sf.joafip.btreeplus.entity.LeafPage;
import net.sf.joafip.btreeplus.entity.NonTerminalPage;
+import net.sf.joafip.kvstore.record.entity.DataRecordIdentifier;
import net.sf.joafip.kvstore.service.HeapException;
import net.sf.joafip.kvstore.service.IHeapDataManager;
@@ -44,6 +45,8 @@
public class BtreePlusDataMgrIntegrityChecker {
private final static BtreePlusDataMgrIntegrityChecker INSTANCE = new BtreePlusDataMgrIntegrityChecker();
+ private DataRecordIdentifier lessThanMinKey;
+ private DataRecordIdentifier maxKey;
private BtreePlusDataMgrIntegrityChecker() {
super();
@@ -54,10 +57,14 @@
}
public IntegrityCheckResult checkIntegrity(
- final IHeapDataManager dataManager) throws HeapException {
+ final IHeapDataManager dataManager,
+ final DataRecordIdentifier lessThanMinKey,
+ final DataRecordIdentifier maxKey) throws HeapException {
if (!BtreePlusDataManager.class.equals(dataManager.getClass())) {
throw new HeapException("bad class " + dataManager.getClass());
}
+ this.lessThanMinKey = lessThanMinKey;
+ this.maxKey = maxKey;
return checkIntegrity((BtreePlusDataManager) dataManager);
}
@@ -65,7 +72,7 @@
final BtreePlusDataManager btreePlusDataManager)
throws HeapException {
final Deque<State> stack = new LinkedList<State>();
- State state = new State(-1, Long.MAX_VALUE);
+ State state = new State(lessThanMinKey, maxKey);
stack.push(state);
final BtreePlusElementMgr elementMgr = btreePlusDataManager
.getBtreePlusElementMgr();
@@ -76,6 +83,7 @@
int entriesCount = 0;
int leafPageCount = 0;
int nonTerminalPageCount = 0;
+ // FIXMELUC _____________leaf page chain
// System.out.println("--- begin ---");
while (pageRecordable != null) {
elementMgr.clearReadCache();
@@ -83,22 +91,41 @@
switch (recordType) {
case LEAF_PAGE: {
final LeafPage leafPage = (LeafPage) pageRecordable;
+
+ // check keys
+ DataRecordIdentifier currentKey = leafPage.getKey(0);
+ for (int kindex = 1; kindex < leafPage.getNumberOfKeyEntries(); kindex++) {
+ final DataRecordIdentifier nextKey = leafPage
+ .getKey(kindex);
+ if (compare(currentKey, nextKey) >= 0) {
+ throw new HeapException("bad keys");
+ }
+ currentKey = nextKey;
+ }
+
// check leaf page value range
- final long firstKeyValue = leafPage.getFirstKey().value;
- final long lastKeyValue = leafPage.getLastKey().value;
+ final DataRecordIdentifier firstKey = leafPage.getFirstKey();
+ // final long firstKeyValue = leafPage.getFirstKey().value;
+ final DataRecordIdentifier lastKey = leafPage.getLastKey();
+ // final long lastKeyValue = leafPage.getLastKey().value;
state = stack.peek();
- if (state.minValue > firstKeyValue
- || state.maxValue < lastKeyValue) {
- throw new HeapException("not have " + state.minValue
- + "(min value)<=" + firstKeyValue
- + "(first key value) " + lastKeyValue
- + "(last key value) <=" + state.maxValue
+ if (/* state.minValue >= firstKeyValue */
+ compare(state.minKey, firstKey) >= 0 || /*
+ * state.maxValue <
+ * lastKeyValue
+ */
+ compare(state.maxKey, lastKey) < 0) {
+ throw new HeapException("not have " + state.minKey
+ + "(min value)<" + firstKey + "(first key value) "
+ + lastKey + "(last key value) <=" + state.maxKey
+ "(max value)");
}
// check well formed
- if (currentDepth != 0 && !leafPage.wellFilled()) {
- throw new HeapException("not well filled");
- }
+ // if (currentDepth != 0 && !leafPage.wellFilled()) {
+ // throw new
+ // HeapException("not well filled "+leafPage.getByteSize());
+ // }
+
// check depth, all leaf page must be at same depth
if (depth == -1) {
depth = currentDepth;
@@ -108,9 +135,12 @@
+ depth);
}
+ // count entries
entriesCount += leafPage.getNumberOfKeyEntries();
+
// count leaf page
leafPageCount++;
+
// go up
pageRecordable = leafPage.getParentPage();
index = leafPage.getInParentIndex() + 1;
@@ -121,22 +151,44 @@
case NON_TERMINAL_PAGE: {
final NonTerminalPage nonTerminalPage = (NonTerminalPage) pageRecordable;
if (index == 0) {
+
+ // check keys
+ DataRecordIdentifier currentKey = nonTerminalPage.getKey(0);
+ for (int kindex = 1; kindex < nonTerminalPage
+ .getNumberOfKeyEntries(); kindex++) {
+ final DataRecordIdentifier nextKey = nonTerminalPage
+ .getKey(kindex);
+ if (compare(currentKey, nextKey) >= 0) {
+ throw new HeapException("bad keys");
+ }
+ currentKey = nextKey;
+ }
+
// check non terminal page value range
- final long firstKeyValue = nonTerminalPage.getFirstKey().value;
- final long lastKeyValue = nonTerminalPage.getLastKey().value;
+ final DataRecordIdentifier firstKey = nonTerminalPage
+ .getFirstKey();
+ final DataRecordIdentifier lastKey = nonTerminalPage
+ .getLastKey();
state = stack.peek();
- if (state.minValue > firstKeyValue
- || state.maxValue < lastKeyValue) {
- throw new HeapException("not have " + state.minValue
- + "(min value)<=" + firstKeyValue
- + "(first key value) " + lastKeyValue
- + "(last key value) <=" + state.maxValue
- + "(max value)");
+ if (/* state.minValue > firstKeyValue */
+ compare(state.minKey, firstKey) >= 0 || /*
+ * state.maxValue <
+ * lastKeyValue
+ */
+ compare(state.maxKey, lastKey) < 0) {
+ throw new HeapException("not have " + state.minKey
+ + "(min value)<" + firstKey
+ + "(first key value) " + lastKey
+ + "(last key value) <=" + state.maxKey
+ + "(max value)\nnon terminal page at "
+ + nonTerminalPage.getPositionInFile());
}
- // check well formed
- if (currentDepth != 0 && !nonTerminalPage.wellFilled()) {
- throw new HeapException("not well filled");
- }
+
+ // // check well formed
+ // if (currentDepth != 0 && !nonTerminalPage.wellFilled()) {
+ // throw new HeapException("not well filled");
+ // }
+
// count non terminal page
nonTerminalPageCount++;
}
@@ -157,12 +209,12 @@
if (state == null) {
throw new HeapException("stack must not be empty");
}
- final long minValue = index == 0 ? state.minValue
- : nonTerminalPage.getFirstKey().value;
- final long maxValue = index == nonTerminalPage
- .getNumberOfKeyEntries() ? state.maxValue
- : nonTerminalPage.getLastKey().value;
- stack.push(new State(minValue, maxValue));
+ final DataRecordIdentifier minKey = index == 0 ? state.minKey
+ : nonTerminalPage.getKey(index - 1);
+ final DataRecordIdentifier maxKey = index == nonTerminalPage
+ .getNumberOfKeyEntries() ? state.maxKey
+ : nonTerminalPage.getKey(index);
+ stack.push(new State(minKey, maxKey));
index = 0;
currentDepth++;
}
@@ -177,14 +229,20 @@
nonTerminalPageCount);
}
+ private int compare(final DataRecordIdentifier keyA,
+ final DataRecordIdentifier keyB) {
+ return keyA.compareTo(keyB);
+ }
+
private class State {
- private long minValue;
- private long maxValue;
+ private DataRecordIdentifier minKey;
+ private DataRecordIdentifier maxKey;
- public State(final long minValue, final long maxValue) {
+ public State(final DataRecordIdentifier minKey,
+ final DataRecordIdentifier maxKey) {
super();
- this.minValue = minValue;
- this.maxValue = maxValue;
+ this.minKey = minKey;
+ this.maxKey = maxKey;
}
}
}
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-07 02:28:12 UTC (rev 3074)
+++ trunk/joafip-btreeplus/src/main/java/net/sf/joafip/btreeplus/service/BtreePlusElementMgr.java 2012-05-08 05:55:35 UTC (rev 3075)
@@ -63,7 +63,7 @@
private final IFileForStorable fileForStorable;
- private final boolean longKey;
+ private boolean longKey;
public BtreePlusElementMgr(final IHeapElementManager heapElementManager)
throws HeapException {
@@ -79,13 +79,14 @@
+ " and file cache page size is "
+ fileForStorable.getCachePageSize());
}
- longKey = heapElementManager.getDataRecordKeyManager() == null;
+ longKey = true;
}
public void setDataRecordKeyManager(
final IDataRecordKeyManager dataRecordKeyManager)
throws HeapException {
heapElementManager.setDataRecordKeyManager(dataRecordKeyManager);
+ longKey = false;
}
public void startService() throws HeapException {
Added: trunk/joafip-btreeplus/src/main/resources/log4j.properties
===================================================================
--- trunk/joafip-btreeplus/src/main/resources/log4j.properties (rev 0)
+++ trunk/joafip-btreeplus/src/main/resources/log4j.properties 2012-05-08 05:55:35 UTC (rev 3075)
@@ -0,0 +1,24 @@
+
+
+log4j.rootLogger=WARN,CONSOLE,FILE
+
+log4j.appender.CONSOLE=org.apache.log4j.ConsoleAppender
+log4j.appender.CONSOLE.Target=System.out
+log4j.appender.CONSOLE.layout=org.apache.log4j.PatternLayout
+#log4j.appender.CONSOLE.layout.conversionPattern=[%p,%c{1},%t] %m%n
+#log4j.appender.CONSOLE.layout.ConversionPattern=[%5p] - %d [%t] %c (%F:%M:%L) %n %m%n%n
+log4j.appender.CONSOLE.layout.ConversionPattern=[%5p] - %d [%t] (%c.java:%M:%L) %n %m%n%n
+
+log4j.appender.FILE=org.apache.log4j.RollingFileAppender
+#log4j.appender.FILE.File=${webapp.root}/WEB-INF/log4j.log
+log4j.appender.FILE.File=logs/joafip.log
+log4j.appender.FILE.MaxFileSize=1024KB
+log4j.appender.FILE.MaxBackupIndex=3
+log4j.appender.FILE.layout=org.apache.log4j.PatternLayout
+#log4j.appender.FILE.layout.conversionPattern=%d{ABSOLUTE} %5p %c{1},%t:%L - %m%n
+log4j.appender.FILE.layout.ConversionPattern=[%5p] - %d [%t] (%c.java:%M:%L) %n %m%n%n
+
+log4j.logger.net.sf.joafip=warn
+log4j.logger.net.sf.joafip.HelperMemoryUse=info
+log4j.logger.net.sf.joafip.meminspector=warn
+log4j.logger.net.sf.joafip.java.util=warn
Added: trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/BigKey.java
===================================================================
--- trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/BigKey.java (rev 0)
+++ trunk/joafip-btreeplus/src/test/java/net/sf/joafip/btreeplus/entity/BigKey.java 2012-05-08 05:55:35 UTC (rev 3075)
@@ -0,0 +1,105 @@
+/*
+ * Copyright 2012 Luc Peuvrier
+ *
+ * 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 Licens...
[truncated message content] |
