I'm trying to implement a best-fit heap manager model in Java. I think I'm close, but the allocate method in the following code does not return proper results. (It usually either hangs when an integer is entered, or it runs indefinitely returning the same block as being free. Sometimes, however, it throws an OutOfMemoryError like it should when there is no free block remaining that is large enough.) Any ideas on how to fix this?

UPDATE: This is a standalone homework question. The original question is as follows (original Java code was provided using a first-fit instead of a best-fit model):

"Implement a version of HeapManager class with a best-fit mechanism. Start with a renamed copy of the HeapManager class, and then modify the allocate method to implement a best-fit search."

The code below is my attempt to do so. It doesn't work quite properly when implemented using a test class. I have a generic algorithm for a best-fit mechanism (and I understand the overall mechanism), but I keep getting lost in the variables when trying to implement it. I'm trying to figure out where the problem is.

------code------

public class HeapManagerBestFit { static private final int NULL = -1; // our null link public int[] memory; // the memory we manage private int freeStart; // start of the free list

/** * HeapManager constructor. * @param initialMemory the int[] of memory to manage */ public HeapManagerBestFit(int[] initialMemory) { memory = initialMemory; memory[0] = memory.length; // one big free block memory[1] = NULL; // free list ends with it freeStart = 0; // free list starts with it }

/** * Allocate a block and return its address. * @param requestSize int size of block, > 0 * @return block address * @throws OutOfMemoryError if no block big enough */ public int allocate(int requestSize) { int size = requestSize + 1; // size including header

// Do best-fit search: linear search of the free // list for the first block of sufficient size.

int p = freeStart; // head of free list int lag = NULL; int max = NULL; int maxP = NULL; while (p != NULL) { // search all blocks and find the one with the maximum available allocation lag = p; // lag is previous p if(memory[p] > max && memory[p] >= size) { // if current block has more size than the currentMax store // store this as max and store p as maxP max = memory[p]; maxP = p; } p = memory[p + 1]; // link to next block } p = maxP; // set p to maxP if (p == NULL) // no block large enough { throw new OutOfMemoryError(); } int nextFree = memory[p + 1]; // block after p

// Now p is the index of a block of sufficient size, // lag is the index of p's predecessor in the // free list, or NULL, and nextFree is the index of // p's successor in the free list, or NULL.

// If the block has more space than we need, carve // out what we need from the front and return the // unused end part to the free list.

int unused = memory[p]-size; // extra space in block if (unused > 1) { // if more than a header's worth nextFree = p + size; // index of the unused piece memory[nextFree] = unused; // fill in size memory[nextFree+1] = memory[p+1]; // fill in link memory[p] = size; // reduce p's size accordingly }

// Link out the block we are allocating and done.

if (lag == NULL) freeStart = nextFree; else memory[lag + 1] = nextFree; return p+1; // index of useable word (after header) }

/** * Deallocate an allocated block. This works only if * the block address is one that was returned by * allocate and has not yet been deallocated. * @param address int address of the block */ public void deallocate(int address) { int addr = address - 1; // real start of the block

// Find the insertion point in the sorted free list // for this block.

int p = freeStart; int lag = NULL; while (p != NULL && p < addr) { lag = p; p = memory[p + 1]; }

// Now p is the index of the block to come after // ours in the free list, or NULL, and lag is the // index of the block to come before ours in the // free list, or NULL.

// If the one to come after ours is adjacent to it, // merge it into ours and restore the property // described above.

if (addr + memory[addr] == p) { memory[addr] += memory[p]; // add its size to ours p = memory[p + 1]; // }

if (lag == NULL) { // ours will be first free freeStart = addr; memory[addr + 1] = p; } else if (lag+memory[lag]==addr) { // block before is // adjacent to ours memory[lag] += memory[addr]; // merge ours into it memory[lag + 1] = p; } else { // neither, just a simple insertion memory[lag + 1] = addr; memory[addr + 1] = p; } } }