This is the delete method :

# procedure delete removes an integer value from a sorted linked list # procedure arguments as follows: # $a0 - integer to be removed # $a1 - address of word containing address of first node in sorted list # $a2 - address of word containing address of first node in the free list delete: lw $t0,0($a1) beqz $t0,d_done # if have reached end of list, nothing to do lw $t1,0($t0) beq $a0,$t1,d_here # if matching integer, have found node to unlink addiu $a1,$t0,4 j delete # keep traversing list until find node to unlink d_here: lw $t2,4($t0) # have found node to unlink sw $t2,0($a1) # node is now unlinked from list addi $sp,$sp,-4 sw $ra,0($sp) move $a0,$a2 move $a1,$t0 jal free lw $ra,0($sp) addi $sp,$sp,4 d_done: jr $ra

This is the free.asm

# procedure free returns a node to the free list # procedure arguments as follows: # $a0 - address of word containing the address of the first node in free list # $a1 - address of node that should be added to free list free: lw $t0,0($a0) sw $a1,0($a0) sw $zero,0($a1) sw $t0,4($a1) jr $ra

This is the alloc.asm

# procedure alloc gets a node from the free list # procedure argument as follows: # $a0 - address of word containing the address of the first node in free list # procedure returns pointer to unlinked node alloc: lw $v0,0($a0) beq $v0,$zero,alloc_r #if free list is empty, return 0 lw $t0,4($v0) sw $t0,0($a0) sw $zero,4($v0) alloc_r: jr $ra

This is init.asm

# procedure init initializes the free list # procedure arguments as follows: # $a0 - address of block of memory to be used for free list # $a1 - desired size of free list (number of nodes) # procedure returns pointer to first node in free list init: move $v0,$a0 blez $a1,init_r init_l: sw $zero,0($a0) addi $a0,$a0,8 sw $a0,-4($a0) addi $a1,$a1,-1 bne $zero,$a1,init_l sw $zero,-4($a0) init_r: jr $ra

5. (10 marks) In this question you are to write a MIPS assembly language insert procedure for a sorted linked list, and a main program to test it. Each node in the linked list should be implemented with two consecutive words of memory, as shown below: \begin{tabular}{|c|c|} \hline integer value & address of next node \\ \hline address a & address a+4 \\ \hline \end{tabular} The "address of next node" pointer gives the memory address of the first word of the next node in the list. A pointer (memory address) of zero indicates that we're at the end of the linked list and there is no next node. The linked list should be maintained so that the node with the smallest integer value is at the head of the list, and each subsequent node contains a larger integer value than the node before it. In addition to adding nodes to the linked list using your insert procedure, you will also be removing nodes using a delete procedure provided on the class Canvas site. Your linked list of integers will grow and shrink over time, so some way is needed to dynamically allocate (and free) the memory that nodes are using. In a C program, for example, dynamic allocation and freeing of memory can be done using the C library functions malloc and free. In this question, you will allocate and free from a big block of memory obtained using ".space". Your main program should use ".space 200 " to allocate memory sufficient for 25 nodes ( 25 nodes x2 wordsode x4 bytes/word = 200 bytes). On the class Canvas site, you will find procedures init, alloc, and free. These procedures can be used to keep track of what portions of this memory are not in use (i.e., not currently being used for a node in your linked list of integers), and to allocate/free node-sized chunks of it. For simplicity, these procedures support only allocation and freeing of node-sized chunks, by maintaining a free list of such nodesized chunks, but of course dynamic storage allocation in real systems must accommodate requests for, and releases of, varying-sized blocks of memory. Your insert procedure should take three parameters: the integer value to be added to your sorted linked list, the address of a memory word that contains the address of the first node in your sorted linked list (if the list is not empty, otherwise the memory word would contain zero), and the address of a memory word containing the address of the first node in the free list. If there is already a node in the sorted linked list that contains that integer value, the list should not be changed. Otherwise, your procedure should attempt to allocate a node from your free list using alloc, and, if successful (the free list wasn't empty), store the integer value in that node and insert the node into your sorted linked list in a position that maintains the sorted ordering. Your insert procedure should return 0 unless it was unable to add the integer to the linked list because the free list The delete procedure on the class Canvas site also takes three parameters: the integer value to be removed from your sorted linked list, the address of a memory word that contains the address of the first node in your sorted linked list (if the list is not empty, otherwise the memory word would contain zero), and the address of a memory word containing the address of the first node in the free list. If there isn't a node in the sorted linked list that contains that integer value, the list is not be changed. Otherwise, the node containing the integer value is unlinked from your sorted linked list and returned to the free list (using free). Your main program should prompt the user for an input line consisting of a single character ("I" for insert, "D" for delete) followed by an integer for which the respective operation is to be performed (e.g., I30 to insert the integer 30 ). This should be repeated until the user enters a character other than "I" or "D", at which point the integers in your sorted linked list should be output, in order, and your program should terminate. Your code must use the "standard" conventions covered in class for passing parameters and returning results. The .asm or .s file that you submit for this question should include your main program, your insert procedure, and the delete, init, alloc, and free procedures from the course Canvas site