| 0,0 → 1,138 |
|---|
| // Class for managing the linked list of free blocks |
| public class DoubleLinkedList { |
| |
| private LinkedListEntry head; // Start of linked list |
| |
| public void insert(LinkedListEntry 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; |
| } |
| |
| LinkedListEntry 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 |
| LinkedListEntry newEntry = new LinkedListEntry(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 |
| LinkedListEntry newEntry = new LinkedListEntry(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 |
| LinkedListEntry 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(int address) { |
| // First check if list is empty |
| if (head == null) { |
| return false; |
| } else { |
| // Otherwise loop through and fine entry |
| LinkedListEntry 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) |
| LinkedListEntry 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 LinkedListEntry getFirstEntry() { |
| // First check if list is empty |
| if (head == null) { |
| return null; |
| } else { |
| // Otherwise return head entry |
| return head; |
| } |
| } |
| } |