goldbug1832
BAN USERpublic Node copyList(Node head) {
if (head == null)
return null;
//Create a new node for each node in the original list.
//Also, create two index arrays, one for original list, one for new list
Node curr = head;
ArrayList<Node> originIndexArray = new ArrayList<Node>();
ArrayList<Node> newIndexArray = new ArrayList<Node>();
while (curr != null) {
Node node = new Node();
node.data = curr.data;
newIndexArray.add(node);
originIndexArray.add(curr);
curr = curr.next;
}
//Set next pointer of each node in the new list
for (int i = 0; i < newIndexArray.size(); i++) {
Node node = (Node) newIndexArray.get(i);
if (i + 1 < newIndexArray.size()) {
Node nextNode = (Node) newIndexArray.get(i+1);
node.next = nextNode;
} else {
node.next = null;
}
}
//Set other pointer of each node in the new list
for (int i = 0; i < originIndexArray.size(); i++) {
Node oNode = (Node) originIndexArray.get(i);
Node nNode = (Node) newIndexArray.get(i);
if (oNode.other != null) {
int k = originIndexArray.indexOf(oNode.other);
Node otherNode = (Node) newIndexArray.get(k);
nNode.other = otherNode;
} else {
nNode.other = null;
}
}
return (Node) newIndexArray.get(0);
}
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) {
}
}
}
- goldbug1832 June 16, 2014