Subversion Repositories Code-Repo

// 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;
                }
        }
}