org.eclipse.jdt.core.tests.model/src/org/eclipse/jdt/core/tests/nd/LargeBlockTest.java - objectteams/org.eclipse.objectteams - Git at Google

 /*******************************************************************************
  * Copyright (c) 2005, 2016 QNX Software Systems and others.
  *
  * This program and the accompanying materials
  * are made available under the terms of the Eclipse Public License 2.0
  * which accompanies this distribution, and is available at
  * https://www.eclipse.org/legal/epl-2.0/
  *
  * SPDX-License-Identifier: EPL-2.0
  *
  * Contributors:
  *     QNX Software Systems - initial API and implementation
  *     Andrew Ferguson (Symbian)
  *     Markus Schorn (Wind River Systems)
  *******************************************************************************/
 package org.eclipse.jdt.core.tests.nd;

 import org.eclipse.jdt.core.tests.nd.util.BaseTestCase;
 import org.eclipse.jdt.internal.core.nd.Nd;
 import org.eclipse.jdt.internal.core.nd.db.Database;

 import junit.framework.Test;

 /**
  * Tests for the {@link Database} class.
  */
 public class LargeBlockTest extends BaseTestCase {
 	private Nd nd;
 	protected Database db;

 	@Override
 	protected void setUp() throws Exception {
 		super.setUp();
 		String testName = getName();
 		this.nd = DatabaseTestUtil.createWithoutNodeRegistry(testName);
 		this.db = this.nd.getDB();
 		this.db.setExclusiveLock();
 		this.db.flush();
 	}

 	public static Test suite() {
 		return BaseTestCase.suite(LargeBlockTest.class);
 	}

 	@Override
 	protected void tearDown() throws Exception {
 		DatabaseTestUtil.deleteDatabase(this.db);
 		this.db = null;
 	}

 	private long mallocChunks(int chunks) {
 		return malloc(Database.getBytesThatFitInChunks(chunks));
 	}

 	private long malloc(long bytes) {
 		return this.db.malloc(bytes, Database.POOL_MISC);
 	}

 	private void free(long address) {
 		this.db.free(address, Database.POOL_MISC);
 	}

 	/**
 	 * Allocate the maximum number of bytes that can fit in 3 chunks and verify
 	 * that it doesn't overflow.
 	 */
 	public void testAllocationThatFillsMultipleChunksDoesntOverflow() throws Exception {
 		int chunkCount = this.db.getChunkCount();

 		int numChunks = 5;
 		mallocChunks(numChunks);

 		assertEquals("The database should not allocate more (or less) memory than is needed", numChunks + chunkCount,
 				this.db.getChunkCount());
 	}

 	/**
 	 * Allocates a few blocks, frees them, then allocates more blocks. Verifies
 	 * that the database reuses the chunks from the first allocation when it
 	 * tries to allocate the larger block later.
 	 */
 	public void testLastChunkIsReused() throws Exception {
 		int chunkCount = this.db.getChunkCount();

 		int numChunks = 10;
 		long temporaryBlockAddress = mallocChunks(3);
 		free(temporaryBlockAddress);
 		mallocChunks(numChunks);

 		assertEquals("If the last chunk is free, it should be resized if necessary when a new chunk is requested",
 				numChunks + chunkCount, this.db.getChunkCount());
 	}

 	/**
 	 * Tests that if there is a single large free block available, that block
 	 * will be split and reused if necessary to satisfy a number of smaller
 	 * requests.
 	 *
 	 * @throws Exception
 	 */
 	public void testLargeAllocationIsSplitAndReused() throws Exception {
 		long tempAddress = malloc(Database.getBytesThatFitInChunks(10));
 		// Use some space at the end of the database to prevent the allocator
 		// from using the end of the database, where stuff can be easily resized
 		mallocChunks(1);
 		free(tempAddress);

 		// Keep track of how much memory we are currently using, so we can
 		// ensure that any further allocations come from the freed block rather
 		// than the end of the database.
 		int chunkCount = this.db.getChunkCount();

 		long firstAllocation = mallocChunks(7);

 		assertEquals("The freed chunk should be reused (there should be 10 chunks available)", chunkCount,
 				this.db.getChunkCount());

 		long secondAllocation = mallocChunks(1);

 		assertEquals("The freed chunk should be reused (there should be 3 chunks available)", chunkCount,
 				this.db.getChunkCount());

 		long thirdAllocation = mallocChunks(2);

 		assertEquals("The freed chunk should be reused (there should be exactly 2 chunks available)", chunkCount,
 				this.db.getChunkCount());
 		assertTrue(
 				"Allocations should happen from the start of the database if it makes no difference to fragmentation",
 				secondAllocation > firstAllocation);
 		assertTrue("Free space should have been kept next to the largest block for as long as possible",
 				secondAllocation > thirdAllocation);

 		// Do another allocation when there are no free chunks
 		mallocChunks(1);

 		assertEquals("New chunks should be allocated when the database is out of free blocks", chunkCount + 1,
 				this.db.getChunkCount());
 	}

 	/**
 	 * Verifies that if a block is freed and the previous block is also free,
 	 * the two free blocks will be combined into a single larger block.
 	 */
 	public void testFreeBlockMergesWithPrevious() throws Exception {
 		long firstBlock = mallocChunks(1);
 		long secondBlock = mallocChunks(1);
 		mallocChunks(1);

 		free(firstBlock);
 		free(secondBlock);

 		int chunkCount = this.db.getChunkCount();

 		mallocChunks(2);
 		assertEquals("The merged block should have been used", chunkCount, this.db.getChunkCount());
 	}

 	/**
 	 * Verifies that if a block is freed and the next block is also free, the
 	 * two free blocks will be combined into a single larger block.
 	 */
 	public void testFreeBlockMergesWithNext() throws Exception {
 		long firstBlock = mallocChunks(1);
 		long secondBlock = mallocChunks(1);
 		mallocChunks(1);

 		free(secondBlock);
 		free(firstBlock);

 		int chunkCount = this.db.getChunkCount();

 		mallocChunks(2);
 		assertEquals("The merged block should have been used", chunkCount, this.db.getChunkCount());
 	}

 	/**
 	 * Verifies that if a block is freed and the blocks on both sides are also
 	 * free, the three free blocks will be combined into a single larger block.
 	 */
 	public void testFreeBlockMergesWithBothNextAndPrevious() throws Exception {
 		long firstBlock = mallocChunks(1);
 		long secondBlock = mallocChunks(1);
 		long thirdBlock = mallocChunks(1);
 		mallocChunks(1);

 		free(firstBlock);
 		free(thirdBlock);
 		free(secondBlock);

 		int chunkCount = this.db.getChunkCount();

 		mallocChunks(3);
 		assertEquals("The merged block should have been used", chunkCount, this.db.getChunkCount());
 	}

 	/**
 	 * Tests removal of a chunk from the free space trie when there are
 	 * duplicate free space nodes with the same size and the node being removed
 	 * isn't the one with the embedded trie node.
 	 */
 	public void testRemoveFreeSpaceNodeFromDuplicateList() throws Exception {
 		long chunk1 = mallocChunks(1);
 		mallocChunks(1);
 		long chunk3 = mallocChunks(1);
 		long chunk4 = mallocChunks(1);
 		mallocChunks(1);

 		int chunkCount = this.db.getChunkCount();

 		free(chunk1);
 		free(chunk3);
 		// At this point chunks 1 and 3 should be in the same linked list. Chunk
 		// 1 contains the embedded trie.

 		free(chunk4);
 		// Should merge with chunk3, causing it to be removed from the list

 		// Verify that we can allocate the merged chunk 3+4
 		mallocChunks(2);

 		assertEquals("Chunks 3 and 4 should have been merged", chunkCount, this.db.getChunkCount());
 	}

 	/**
 	 * Tests removal of a chunk from the free space trie when the node being
 	 * removed was part of the embedded trie and it has a non-empty list of
 	 * other nodes of the same size.
 	 */
 	public void testRemoveFreeSpaceNodeFromTrieWithDuplicates() throws Exception {
 		long chunk1 = mallocChunks(1);
 		mallocChunks(1);
 		long chunk3 = mallocChunks(1);
 		long chunk4 = mallocChunks(1);
 		mallocChunks(1);

 		int chunkCount = this.db.getChunkCount();

 		free(chunk3);
 		free(chunk1);
 		// At this point chunks 1 and 3 should be in the same linked list. Chunk
 		// 3 contains the embedded trie.

 		free(chunk4);
 		// Should merge with chunk3, causing it to be removed from the list

 		// Verify that we can allocate the merged chunk 3+4
 		mallocChunks(2);

 		assertEquals("Chunks 3 and 4 should have been merged", chunkCount, this.db.getChunkCount());
 	}

 	/**
 	 * Tests reusing a chunk from the free space trie when it contains
 	 * duplicates.
 	 */
 	public void testReuseDeallocatedChunksWithMultipleFreeSpaceNodesOfTheSameSize() throws Exception {
 		long chunk1 = mallocChunks(2);
 		mallocChunks(1);
 		long chunk3 = mallocChunks(2);
 		mallocChunks(1);
 		long chunk5 = mallocChunks(2);
 		mallocChunks(1);

 		int chunkCount = this.db.getChunkCount();

 		free(chunk1);
 		free(chunk3);
 		free(chunk5);

 		mallocChunks(2);

 		assertEquals("A chunk should have been reused", chunkCount, this.db.getChunkCount());
 	}

 	public void testEndOfFreeBlockIsUsedIfThePreviousBlockIsLargerThanTheNextBlock() throws Exception {
 		long prevChunk = mallocChunks(4);
 		long middleChunk = mallocChunks(4);
 		long nextChunk = mallocChunks(2);

 		free(middleChunk);
 		// This should be taken from the end of "middleChunk", since that's closer to the smaller neighbor
 		long smallChunk1 = mallocChunks(1);
 		// This should also be taken from the end of the remaining portion of "middleChunk"
 		long smallChunk2 = mallocChunks(1);

 		assertTrue("The small chunks should have been allocated from space after 'prevChunk'",
 				prevChunk < smallChunk2);
 		assertTrue("The small chunks should have been allocated from the end of the free block",
 				smallChunk2 < smallChunk1);
 		assertTrue("The small chunks should have been allocated from space before 'nextChunk'",
 				smallChunk1 < nextChunk);
 	}

 	/**
 	 * Tests various corner cases in the trie map.
 	 */
 	public void testTriesOfVariousSize() throws Exception {
 		long chunk1 = mallocChunks(1);
 		mallocChunks(1);
 		long chunk2 = mallocChunks(2);
 		mallocChunks(1);
 		long chunk3 = mallocChunks(3);
 		mallocChunks(1);
 		long chunk4 = mallocChunks(5);
 		mallocChunks(1);
 		long chunk5 = mallocChunks(6);
 		mallocChunks(1);
 		long chunk6 = mallocChunks(6);
 		mallocChunks(1);
 		long chunk7 = mallocChunks(10);
 		mallocChunks(1);
 		long chunk8 = mallocChunks(20);
 		mallocChunks(1);

 		int chunkCount = this.db.getChunkCount();

 		free(chunk7);
 		free(chunk4);
 		free(chunk1);
 		free(chunk3);
 		free(chunk8);
 		free(chunk5);
 		free(chunk2);
 		free(chunk6);

 		mallocChunks(4);
 		mallocChunks(10);

 		assertEquals("A chunk should have been reused", chunkCount, this.db.getChunkCount());
 	}

 	/**
 	 * Tests that if there are multiple free blocks of different sizes and of
 	 * exactly one of the requested size, that one is always selected.
 	 */
 	public void testBestBlockIsAlwaysSelected() throws Exception {
 		int[] sizes = { 11, 2, 6, 1, 9, 10, 7, 8, 12, 20, 15, 3 };
 		long[] pointers = new long[sizes.length];

 		for (int idx = 0; idx < sizes.length; idx++) {
 			pointers[idx] = mallocChunks(sizes[idx]);
 			mallocChunks(1);
 		}

 		int chunkCount = this.db.getChunkCount();

 		for (int idx = 0; idx < pointers.length; idx++) {
 			free(pointers[idx]);
 		}

 		for (int idx = 0; idx < sizes.length; idx++) {
 			long nextPointer = mallocChunks(sizes[idx]);
 			assertEquals("Returned wrong pointer for malloc of " + sizes[idx] + " chunks", pointers[idx], nextPointer);
 			assertEquals("A chunk should have been reused", chunkCount, this.db.getChunkCount());
 		}
 	}

 	/**
 	 * Tests removals from the large chunk sibling list. Ensures that such removals don't interfere with
 	 * the trie itself.
 	 */
 	public void testUnlinkedBlockNotInTrieGetsRelinked() throws Exception {
 		long rootChunk = mallocChunks(1);
 		mallocChunks(1);
 		long unusedChunk = mallocChunks(1);
 		mallocChunks(1);
 		long chunkToBeMerged = mallocChunks(1);
 		long chunkThatWillCauseMerging = mallocChunks(1);
 		mallocChunks(1);
 		long followingChunkInFreeSpaceList = mallocChunks(1);
 		mallocChunks(1);
 		long chunkOfSize2 = mallocChunks(2);
 		mallocChunks(1);

 		int chunkCount = this.db.getChunkCount();

 		free(rootChunk);
 		free(unusedChunk);
 		free(chunkToBeMerged);
 		free(followingChunkInFreeSpaceList);
 		free(chunkOfSize2);

 		// At this point, the free space trie looks like this:
 		//
 		// size 1: rootChunk -> unusedChunk -> chunkToBeMerged -> followingChunkInFreeSpaceList
 		//                   -> size 2: chunkOfSize2
 		//
 		// By freeing chunkThatWillCauseMerging, chunkToBeMerged will be removed from the
 		// list of size 1 and inserted into the list of size 2. This test verifies that the
 		// code won't mess with the root pointer by inserting unusedChunk or chunk into the root

 		// This call will corrupt the database if we don't do the removal correctly
 		free(chunkThatWillCauseMerging);

 		// Now reallocate the original chunks to ensure they can all be found in the list
 		long firstDoubleChunk = mallocChunks(2);
 		long secondDoubleChunk = mallocChunks(2);

 		mallocChunks(1);
 		mallocChunks(1);
 		mallocChunks(1);

 		assertEquals("A chunk should have been reused", chunkCount, this.db.getChunkCount());
 		assertNotSame("Both new chunks should have been unique", firstDoubleChunk, secondDoubleChunk);
 		assertNotSame("The first chunk should not be null", 0, firstDoubleChunk);
 		assertNotSame("The second chunk should not be null", 0, secondDoubleChunk);
 		this.db.validateFreeSpace();
 	}
 }
	/*******************************************************************************
	* Copyright (c) 2005, 2016 QNX Software Systems and others.
	*
	* This program and the accompanying materials
	* are made available under the terms of the Eclipse Public License 2.0
	* which accompanies this distribution, and is available at
	* https://www.eclipse.org/legal/epl-2.0/
	*
	* SPDX-License-Identifier: EPL-2.0
	*
	* Contributors:
	* QNX Software Systems - initial API and implementation
	* Andrew Ferguson (Symbian)
	* Markus Schorn (Wind River Systems)
	*******************************************************************************/
	package org.eclipse.jdt.core.tests.nd;

	import org.eclipse.jdt.core.tests.nd.util.BaseTestCase;
	import org.eclipse.jdt.internal.core.nd.Nd;
	import org.eclipse.jdt.internal.core.nd.db.Database;

	import junit.framework.Test;

	/**
	* Tests for the {@link Database} class.
	*/
	public class LargeBlockTest extends BaseTestCase {
	private Nd nd;
	protected Database db;

	@Override
	protected void setUp() throws Exception {
	super.setUp();
	String testName = getName();
	this.nd = DatabaseTestUtil.createWithoutNodeRegistry(testName);
	this.db = this.nd.getDB();
	this.db.setExclusiveLock();
	this.db.flush();
	}

	public static Test suite() {
	return BaseTestCase.suite(LargeBlockTest.class);
	}

	@Override
	protected void tearDown() throws Exception {
	DatabaseTestUtil.deleteDatabase(this.db);
	this.db = null;
	}

	private long mallocChunks(int chunks) {
	return malloc(Database.getBytesThatFitInChunks(chunks));
	}

	private long malloc(long bytes) {
	return this.db.malloc(bytes, Database.POOL_MISC);
	}

	private void free(long address) {
	this.db.free(address, Database.POOL_MISC);
	}

	/**
	* Allocate the maximum number of bytes that can fit in 3 chunks and verify
	* that it doesn't overflow.
	*/
	public void testAllocationThatFillsMultipleChunksDoesntOverflow() throws Exception {
	int chunkCount = this.db.getChunkCount();

	int numChunks = 5;
	mallocChunks(numChunks);

	assertEquals("The database should not allocate more (or less) memory than is needed", numChunks + chunkCount,
	this.db.getChunkCount());
	}

	/**
	* Allocates a few blocks, frees them, then allocates more blocks. Verifies
	* that the database reuses the chunks from the first allocation when it
	* tries to allocate the larger block later.
	*/
	public void testLastChunkIsReused() throws Exception {
	int chunkCount = this.db.getChunkCount();

	int numChunks = 10;
	long temporaryBlockAddress = mallocChunks(3);
	free(temporaryBlockAddress);
	mallocChunks(numChunks);

	assertEquals("If the last chunk is free, it should be resized if necessary when a new chunk is requested",
	numChunks + chunkCount, this.db.getChunkCount());
	}

	/**
	* Tests that if there is a single large free block available, that block
	* will be split and reused if necessary to satisfy a number of smaller
	* requests.
	*
	* @throws Exception
	*/
	public void testLargeAllocationIsSplitAndReused() throws Exception {
	long tempAddress = malloc(Database.getBytesThatFitInChunks(10));
	// Use some space at the end of the database to prevent the allocator
	// from using the end of the database, where stuff can be easily resized
	mallocChunks(1);
	free(tempAddress);

	// Keep track of how much memory we are currently using, so we can
	// ensure that any further allocations come from the freed block rather
	// than the end of the database.
	int chunkCount = this.db.getChunkCount();

	long firstAllocation = mallocChunks(7);

	assertEquals("The freed chunk should be reused (there should be 10 chunks available)", chunkCount,
	this.db.getChunkCount());

	long secondAllocation = mallocChunks(1);

	assertEquals("The freed chunk should be reused (there should be 3 chunks available)", chunkCount,
	this.db.getChunkCount());

	long thirdAllocation = mallocChunks(2);

	assertEquals("The freed chunk should be reused (there should be exactly 2 chunks available)", chunkCount,
	this.db.getChunkCount());
	assertTrue(
	"Allocations should happen from the start of the database if it makes no difference to fragmentation",
	secondAllocation > firstAllocation);
	assertTrue("Free space should have been kept next to the largest block for as long as possible",
	secondAllocation > thirdAllocation);

	// Do another allocation when there are no free chunks
	mallocChunks(1);

	assertEquals("New chunks should be allocated when the database is out of free blocks", chunkCount + 1,
	this.db.getChunkCount());
	}

	/**
	* Verifies that if a block is freed and the previous block is also free,
	* the two free blocks will be combined into a single larger block.
	*/
	public void testFreeBlockMergesWithPrevious() throws Exception {
	long firstBlock = mallocChunks(1);
	long secondBlock = mallocChunks(1);
	mallocChunks(1);

	free(firstBlock);
	free(secondBlock);

	int chunkCount = this.db.getChunkCount();

	mallocChunks(2);
	assertEquals("The merged block should have been used", chunkCount, this.db.getChunkCount());
	}

	/**
	* Verifies that if a block is freed and the next block is also free, the
	* two free blocks will be combined into a single larger block.
	*/
	public void testFreeBlockMergesWithNext() throws Exception {
	long firstBlock = mallocChunks(1);
	long secondBlock = mallocChunks(1);
	mallocChunks(1);

	free(secondBlock);
	free(firstBlock);

	int chunkCount = this.db.getChunkCount();

	mallocChunks(2);
	assertEquals("The merged block should have been used", chunkCount, this.db.getChunkCount());
	}

	/**
	* Verifies that if a block is freed and the blocks on both sides are also
	* free, the three free blocks will be combined into a single larger block.
	*/
	public void testFreeBlockMergesWithBothNextAndPrevious() throws Exception {
	long firstBlock = mallocChunks(1);
	long secondBlock = mallocChunks(1);
	long thirdBlock = mallocChunks(1);
	mallocChunks(1);

	free(firstBlock);
	free(thirdBlock);
	free(secondBlock);

	int chunkCount = this.db.getChunkCount();

	mallocChunks(3);
	assertEquals("The merged block should have been used", chunkCount, this.db.getChunkCount());
	}

	/**
	* Tests removal of a chunk from the free space trie when there are
	* duplicate free space nodes with the same size and the node being removed
	* isn't the one with the embedded trie node.
	*/
	public void testRemoveFreeSpaceNodeFromDuplicateList() throws Exception {
	long chunk1 = mallocChunks(1);
	mallocChunks(1);
	long chunk3 = mallocChunks(1);
	long chunk4 = mallocChunks(1);
	mallocChunks(1);

	int chunkCount = this.db.getChunkCount();

	free(chunk1);
	free(chunk3);
	// At this point chunks 1 and 3 should be in the same linked list. Chunk
	// 1 contains the embedded trie.

	free(chunk4);
	// Should merge with chunk3, causing it to be removed from the list

	// Verify that we can allocate the merged chunk 3+4
	mallocChunks(2);

	assertEquals("Chunks 3 and 4 should have been merged", chunkCount, this.db.getChunkCount());
	}

	/**
	* Tests removal of a chunk from the free space trie when the node being
	* removed was part of the embedded trie and it has a non-empty list of
	* other nodes of the same size.
	*/
	public void testRemoveFreeSpaceNodeFromTrieWithDuplicates() throws Exception {
	long chunk1 = mallocChunks(1);
	mallocChunks(1);
	long chunk3 = mallocChunks(1);
	long chunk4 = mallocChunks(1);
	mallocChunks(1);

	int chunkCount = this.db.getChunkCount();

	free(chunk3);
	free(chunk1);
	// At this point chunks 1 and 3 should be in the same linked list. Chunk
	// 3 contains the embedded trie.

	free(chunk4);
	// Should merge with chunk3, causing it to be removed from the list

	// Verify that we can allocate the merged chunk 3+4
	mallocChunks(2);

	assertEquals("Chunks 3 and 4 should have been merged", chunkCount, this.db.getChunkCount());
	}

	/**
	* Tests reusing a chunk from the free space trie when it contains
	* duplicates.
	*/
	public void testReuseDeallocatedChunksWithMultipleFreeSpaceNodesOfTheSameSize() throws Exception {
	long chunk1 = mallocChunks(2);
	mallocChunks(1);
	long chunk3 = mallocChunks(2);
	mallocChunks(1);
	long chunk5 = mallocChunks(2);
	mallocChunks(1);

	int chunkCount = this.db.getChunkCount();

	free(chunk1);
	free(chunk3);
	free(chunk5);

	mallocChunks(2);

	assertEquals("A chunk should have been reused", chunkCount, this.db.getChunkCount());
	}

	public void testEndOfFreeBlockIsUsedIfThePreviousBlockIsLargerThanTheNextBlock() throws Exception {
	long prevChunk = mallocChunks(4);
	long middleChunk = mallocChunks(4);
	long nextChunk = mallocChunks(2);

	free(middleChunk);
	// This should be taken from the end of "middleChunk", since that's closer to the smaller neighbor
	long smallChunk1 = mallocChunks(1);
	// This should also be taken from the end of the remaining portion of "middleChunk"
	long smallChunk2 = mallocChunks(1);

	assertTrue("The small chunks should have been allocated from space after 'prevChunk'",
	prevChunk < smallChunk2);
	assertTrue("The small chunks should have been allocated from the end of the free block",
	smallChunk2 < smallChunk1);
	assertTrue("The small chunks should have been allocated from space before 'nextChunk'",
	smallChunk1 < nextChunk);
	}

	/**
	* Tests various corner cases in the trie map.
	*/
	public void testTriesOfVariousSize() throws Exception {
	long chunk1 = mallocChunks(1);
	mallocChunks(1);
	long chunk2 = mallocChunks(2);
	mallocChunks(1);
	long chunk3 = mallocChunks(3);
	mallocChunks(1);
	long chunk4 = mallocChunks(5);
	mallocChunks(1);
	long chunk5 = mallocChunks(6);
	mallocChunks(1);
	long chunk6 = mallocChunks(6);
	mallocChunks(1);
	long chunk7 = mallocChunks(10);
	mallocChunks(1);
	long chunk8 = mallocChunks(20);
	mallocChunks(1);

	int chunkCount = this.db.getChunkCount();

	free(chunk7);
	free(chunk4);
	free(chunk1);
	free(chunk3);
	free(chunk8);
	free(chunk5);
	free(chunk2);
	free(chunk6);

	mallocChunks(4);
	mallocChunks(10);

	assertEquals("A chunk should have been reused", chunkCount, this.db.getChunkCount());
	}

	/**
	* Tests that if there are multiple free blocks of different sizes and of
	* exactly one of the requested size, that one is always selected.
	*/
	public void testBestBlockIsAlwaysSelected() throws Exception {
	int[] sizes = { 11, 2, 6, 1, 9, 10, 7, 8, 12, 20, 15, 3 };
	long[] pointers = new long[sizes.length];

	for (int idx = 0; idx < sizes.length; idx++) {
	pointers[idx] = mallocChunks(sizes[idx]);
	mallocChunks(1);
	}

	int chunkCount = this.db.getChunkCount();

	for (int idx = 0; idx < pointers.length; idx++) {
	free(pointers[idx]);
	}

	for (int idx = 0; idx < sizes.length; idx++) {
	long nextPointer = mallocChunks(sizes[idx]);
	assertEquals("Returned wrong pointer for malloc of " + sizes[idx] + " chunks", pointers[idx], nextPointer);
	assertEquals("A chunk should have been reused", chunkCount, this.db.getChunkCount());
	}
	}

	/**
	* Tests removals from the large chunk sibling list. Ensures that such removals don't interfere with
	* the trie itself.
	*/
	public void testUnlinkedBlockNotInTrieGetsRelinked() throws Exception {
	long rootChunk = mallocChunks(1);
	mallocChunks(1);
	long unusedChunk = mallocChunks(1);
	mallocChunks(1);
	long chunkToBeMerged = mallocChunks(1);
	long chunkThatWillCauseMerging = mallocChunks(1);
	mallocChunks(1);
	long followingChunkInFreeSpaceList = mallocChunks(1);
	mallocChunks(1);
	long chunkOfSize2 = mallocChunks(2);
	mallocChunks(1);

	int chunkCount = this.db.getChunkCount();

	free(rootChunk);
	free(unusedChunk);
	free(chunkToBeMerged);
	free(followingChunkInFreeSpaceList);
	free(chunkOfSize2);

	// At this point, the free space trie looks like this:
	//
	// size 1: rootChunk -> unusedChunk -> chunkToBeMerged -> followingChunkInFreeSpaceList
	// -> size 2: chunkOfSize2
	//
	// By freeing chunkThatWillCauseMerging, chunkToBeMerged will be removed from the
	// list of size 1 and inserted into the list of size 2. This test verifies that the
	// code won't mess with the root pointer by inserting unusedChunk or chunk into the root

	// This call will corrupt the database if we don't do the removal correctly
	free(chunkThatWillCauseMerging);

	// Now reallocate the original chunks to ensure they can all be found in the list
	long firstDoubleChunk = mallocChunks(2);
	long secondDoubleChunk = mallocChunks(2);

	mallocChunks(1);
	mallocChunks(1);
	mallocChunks(1);

	assertEquals("A chunk should have been reused", chunkCount, this.db.getChunkCount());
	assertNotSame("Both new chunks should have been unique", firstDoubleChunk, secondDoubleChunk);
	assertNotSame("The first chunk should not be null", 0, firstDoubleChunk);
	assertNotSame("The second chunk should not be null", 0, secondDoubleChunk);
	this.db.validateFreeSpace();
	}
	}