CareerCup

Looks like an coding test question?

One simple way to implement would be using linked lists.
Every time TinyAlloc and TinyFree is done, have a LL node point to the mem allocated and the next chunk of available mem.
One thing to watch out here for is fragmentation.

class Block {
	public int start;
	public int size;
	public Block(int start, int size) {
		this.start = start;
		this.size = size;
	}
}

class TinyHeap {
	private LinkedList<Block> allocated;
	private LinkedList<Block> free;
	private Lock lock;
	
	public TinyHeap(int size) {
		allocated = new LinkedList<Block>();
		free = new LinkedList<Block>();
		
		free.add(new Block(0, size));
		
		this.lock = new ReentrantLock();
	}
	
	public Block alloc(int size) throws Exception{
		if (size <= 0)
			throw new Exception("zero or negative size");

		this.lock.lock();
		
		try {
			Iterator it = free.iterator();
			Block allocatedBlock = null;
			
			boolean done = false;
			while (!done && it.hasNext()) {
				Block freeBlock = (Block)it.next();
				if (freeBlock.size >= size) {
					//Allocate from the free block
					allocatedBlock = new Block(freeBlock.start, size);
					freeBlock.start += size;
					freeBlock.size -= size;
					
					//keep allocated in sorted order
					ListIterator<Block> listIter = allocated.listIterator();
					boolean found = false;
					while (!found && listIter.hasNext()) {
						Block curr = (Block)listIter.next();
						//Search for block with start address greater than block to free's
						if (curr.start > allocatedBlock.start) {
							found = true;
						}
					}
					//insert at current iterator position
					listIter.add(allocatedBlock);
					done = true;
				}

			}
			return allocatedBlock;
			
		} finally {
			this.lock.unlock();
		}
			
	}
	
	public void free(Block blockToFree) throws Exception {
		if (blockToFree == null)
			throw new Exception("null block");

		this.lock.lock();
		
		try {
			
			//Search the allocated block list for the block
			Iterator it = allocated.iterator();
			boolean found = false;
			while (!found && it.hasNext()) {
				Block block = (Block)it.next();
				if (block.start == blockToFree.start && block.size == blockToFree.size) {
					found = true;
					//Remove the block from allocated list
					it.remove();
				}
			}
			
			if (!found)
				throw new Exception("block not exist in allocated list");
			
			ListIterator<Block> listIter = free.listIterator();
			found = false;
			while (!found && listIter.hasNext()) {
				
				//peek at the next block
				int i = listIter.nextIndex();
				Block nextBlock = (Block)free.get(i);
				
				//Search for block with start address greater than block to free's
				if (nextBlock.start > blockToFree.start) {
					//Check if the block to be freed is adjacent to the next free block
					//if so, merge them
					if (blockToFree.start + blockToFree.size == nextBlock.start) {
						nextBlock.start = blockToFree.start;
						nextBlock.size += blockToFree.size;
					} else {
						//insert at current iterator position
						listIter.add(blockToFree);
					}

					return;
				}
				listIter.next();
			}
			
			if (!found) {
				//insert at the end
				listIter.add(blockToFree);
				return;
			}
			
		} finally {
			this.lock.unlock();
		}
	}

	public void defrag() {
		this.lock.lock();
		try {
			System.out.println("Defragger running...");
			
			ListIterator<Block> listIter = free.listIterator();

			Block prevBlock = null;
			while (listIter.hasNext()) {
				
				//get the next block
				Block currBlock = (Block)listIter.next();
				
				//Check if currBlock is adjacent to prevBlock
				//if so, merge them
				if ((prevBlock != null) &&
					(prevBlock.start + prevBlock.size == currBlock.start)) {
						prevBlock.size += currBlock.size;
						//Remove currBlock
						listIter.remove();
						//prevBlock stay the same because we just removed currBlock

				} else {				
				    prevBlock = currBlock;
				}			    
			}
			
		} finally {
			this.lock.unlock();
			printLists();
		}
	}
	
	public void printLists() {
		this.lock.lock();
		
		try {
			Iterator it = allocated.iterator();
			System.out.println("Allocated");
			while (it.hasNext()) {
				Block block = (Block)it.next();
				System.out.printf("start=%d,  size=%d\n", block.start, block.size);
			}
			
			it = free.iterator();
			System.out.println("Free");
			while (it.hasNext()) {
				Block block = (Block)it.next();
				System.out.printf("start=%d,  size=%d\n", block.start, block.size);
			}
		} finally {
			this.lock.unlock();
		}
	}
}


class ARunnable implements Runnable{
	private TinyHeap heap;
	private int id;
	
	public ARunnable(int id, TinyHeap heap) {
		this.id = id;
		this.heap = heap;
	}
	
	public void run() {
		Block block;
		
		while (true) {
			try {
				int size = (int)(Math.random() * 10000) % 256;
				System.out.println("Thread " + id + " try to allocate " + size);
				block = heap.alloc(size);
				heap.printLists();
				Thread.sleep(1000);
				
				if (block != null) {
					heap.free(block);
					heap.printLists();
					Thread.sleep(1000);
				}
			} catch (Exception e) {
				System.out.println("Thread " + id + " exiting");
			}
		}
	}
}

class Defragger implements Runnable{
	private TinyHeap heap;
	
	public Defragger(TinyHeap heap) {
		this.heap = heap;
	}
	
	public void run() {	
		while (true) {
			try {
				//Runs every 60 secs
				Thread.sleep(60 * 1000);
				heap.defrag();
			} catch (Exception e) {

			}
		}
	}
}

	@Test
	public void tinyHeapTest() {
		/*
		 */
		
		TinyHeap heap = new TinyHeap(1024);
		
		Thread[] threads = new Thread[4];
		for (int i = 0; i < threads.length; i++) {
			ARunnable r = new ARunnable(i, heap);
			Thread t = new Thread(r);
			t.start();
			threads[i] = t;
		}

		//Start defragger
		Defragger r = new Defragger(heap);
		Thread t = new Thread(r);
		t.start();
		
		for (int i = 0; i < threads.length; i++) {
			try {
				threads[i].join();
			} catch (Exception e) {
				
			}
		}
	}