0,0 → 1,138 |
// Class for managing the linked list of free blocks |
public class DoubleLinkedList { |
|
private LinkedListBlock head; // Start of linked list |
|
public void insert(LinkedListBlock entry) { |
|
boolean adjacencyFound = false; // Adjacency flag |
|
// Create the first entry if there are none existing |
if (head == null) { |
head = entry; |
head.setNextBlock(null); |
head.setPrevBlock(null); |
return; |
} |
|
LinkedListBlock current = head; |
// Check to see if adjacent entries exist |
while (current != null) { |
if (current.getStartAddress() == entry.getEndAddress() + 1) { |
// Entry is adjacent to start of current |
LinkedListBlock newEntry = new LinkedListBlock(entry.getStartAddress(), |
current.getEndAddress(), entry.getSize() + current.getSize()); |
remove(current.getStartAddress()); |
insert(newEntry); |
adjacencyFound = true; |
break; |
} |
if (current.getEndAddress() == entry.getStartAddress() - 1) { |
// Entry is adjacent to end of current |
LinkedListBlock newEntry = new LinkedListBlock(current.getStartAddress(), |
entry.getEndAddress(), current.getSize() + entry.getSize()); |
remove(current.getStartAddress()); |
insert(newEntry); |
adjacencyFound = true; |
break; |
} |
current = current.getNextBlock(); |
} |
|
// Otherwise insert entry into sorted list (by size) |
current = head; |
if (!adjacencyFound && (entry.getSize() > current.getSize())) { |
// Insert into beginning of list if size is largest |
entry.setNextBlock(current); |
current.setPrevBlock(entry); |
head = entry; |
return; |
} else if (!adjacencyFound) { |
// Otherwise find location to insert into |
LinkedListBlock prev = head; |
while (prev.getNextBlock() != null) { |
current = prev.getNextBlock(); |
if (entry.getSize() == current.getSize()) { |
// Sort by address location in accending order |
if (entry.getStartAddress() < current.getStartAddress()) { |
// Insert before current |
entry.setNextBlock(current); |
entry.setPrevBlock(prev); |
prev.setNextBlock(entry); |
current.setPrevBlock(entry); |
return; |
} else { |
// Insert after current |
prev = current; |
if (prev.getNextBlock() != null) { |
current = prev.getNextBlock(); |
entry.setNextBlock(current); |
current.setPrevBlock(entry); |
} |
entry.setPrevBlock(prev); |
prev.setNextBlock(entry); |
return; |
} |
} else if (entry.getSize() > current.getSize()) { |
// Insert block between prev and current |
entry.setNextBlock(current); |
entry.setPrevBlock(prev); |
prev.setNextBlock(entry); |
current.setPrevBlock(entry); |
return; |
} else { |
// Otherwise continue searching |
prev = current; |
} |
} |
// Insert into end of list |
entry.setPrevBlock(prev); |
prev.setNextBlock(entry); |
} |
} |
|
// Deletes an entry from the list, returns true if address is found |
public boolean remove(long address) { |
// First check if list is empty |
if (head == null) { |
return false; |
} else { |
// Otherwise loop through and fine entry |
LinkedListBlock entry = head; |
do { |
if (entry.getStartAddress() == address) { |
if (entry.getPrevBlock() == null && entry.getNextBlock() == null) { |
// Deletes entry (only entry in list) |
head = null; |
} else if (entry.getPrevBlock() == null && entry.getNextBlock() != null) { |
// Deletes entry (first in list) |
head = entry.getNextBlock(); |
head.setPrevBlock(null); |
} else if (entry.getPrevBlock() != null && entry.getNextBlock() == null) { |
// Deletes entry (last in list) |
entry.getPrevBlock().setNextBlock(null); |
} else { |
// Deletes entry (in between two entries) |
LinkedListBlock prev = entry.getPrevBlock(); |
prev.setNextBlock(entry.getNextBlock()); |
entry.getNextBlock().setPrevBlock(prev); |
} |
return true; |
} |
entry = entry.getNextBlock(); |
} while (entry != null); |
} |
return false; |
} |
|
// Returns an entry from the list with the passed address |
public LinkedListBlock getFirstEntry() { |
// First check if list is empty |
if (head == null) { |
return null; |
} else { |
// Otherwise return head entry |
return head; |
} |
} |
} |