[solved]-Given File Data Freeptr Word 0 0 Listptr Word 0 Listptr Word C1 C1 Word C3 2 C2 Word 0 4 C Q39078081

# Given file

.data
freePtr: .word 0 0
listPtr: .word 0
# listPtr: .word c1; c1: .word c3 2; c2: .word 0 4; c3: .word c2,-2
opPrompt: .asciiz “Select an op (1: print, 2: insert, 3: delete, 4:sort, 5: search, other: quit): “
insertPrompt: .asciiz “Enter a value to insert: “
deletePrompt: .asciiz “Enter a value to delete: “
searchPrompt: .asciiz “Enter a value to search for: “
searchTrue: .asciiz “The value was in the list.n”
searchFalse: .asciiz “The value was not in the list.n”

.text

# DO NOT MODIFY ANYTHING ABOVE THIS LINE

main:
# your code here

# Print a list out to the console
# Arguments:
# $a0 = address of a word holding the address the first node in thelist
# Return values:
# <none>
print:
# your code here

# Insert into a list (at tail)
# Arguments:
# $a0 = address of a word holding the address the first node in thelist
# $a1 = value to insert
# $a2 = address of freePtr
# Return values:
# <none>
insert:
# your code here

# Delete from a list (first occurrence only)
# Arguments:
# $a0 = address of a word holding the address the first node in thelist
# $a1 = value to delete
# $a2 = address of freePtr
# Return values:
# <none>
delete:
# your code here

# Sort a list in ascending order (recursively using mergesort)
# Arguments:
# $a0 = address of a word holding the address the first node in thelist
# Return values:
# <none>
sort:
# your code here

# Search for a provided value in a list
# Arguments:
# $a0 = address of a word holding the address the first node in thelist
# $a1 = value to search for
# Return values:
# $v0 = 1 if the value was found, 0 otherwise
search:
# your code here

# DO NOT MODIFY ANYTHING BELOW THIS LINE

# initialize the free list
# $a0 = address of 2-word freePtr
init:
li $t0, 1
sw $t0, 0($a0)
sw $0, 4($a0)
jr $ra

# allocates a node (from the free list)
# $a0 = address of 2-word freePtr
alloc:
move $t0, $a0
lw $v0, 4($t0)
bne $v0, $0, allocRet

lw $t1, 0($t0)
sll $t1, $t1, 1
sw $t1, 0($t0)
sll $t1, $t1, 2
move $a0, $t1
li $v0, 9
syscall
move $t2, $v0
allocLoop:
sw $0, 0($t2)
addi $t2, $t2, 8
sw $t2, -4($t2)
addi $t1, $t1, -8
bnez $t1, allocLoop
sw $0, -4($t2)

allocRet:
lw $t1, 4($v0)
sw $0, 0($v0)
sw $t1, 4($t0)
jr $ra

# deallocates a node (places it back on the free list)
# $a0 = address of 2-word freePtr
# $a1 = address of node to free
free:
lw $t0, 4($a0)
sw $0, 0($a1)
sw $t0, 4($a1)
sw $a1, 4($a0)
jr $ra

6. In this question, you will implement several operations to create a basic linked list in MIPS assembly language. Every node in the linked list is made up of 2 words, the first word holds the address of the next node (or null if there is no next node) and the second word holds an integer (the value of the node). The provided code for this question includes a complete .data section, placeholders for main and the five procedures which you will implement (print, insert, delete, sort, and search), and three fully implemented memory-management procedures (init, alloc, and free). Do not modify or add to the data section or the memory-management procedures. You code should manage memory by using the provided init, alloc, and free procedures and passing the address of freePtr. Your main procedure should begin by calling the init procedure, passing the address of freePtr. It should then repeatedly prompt the user for an operation to perform. Each time the user chooses an operation, it should then call the corresponding procedure which you will implement. If the corresponding procedure requires a parameter from the user (e.g., a value to insert), you must prompt for the additional input within main then pass the input to your procedure using standard procedure calling conventions. When an invalid operation number is entered, your program should terminate. (10 marks for main) Each of the five procedures you will implement must use the “standard” conventions discussed in class for passing parameters and returning results. One consequence of this is that console I/O should only be done in main and the print function. While implementing the five procedures, you may also create additional procedures (e.g., isEmpty, count, etc.) if this is helpful. (10 marks for each of the five procedures) a. Implement the procedure, print, that outputs the elements in the list. The procedure should take one parameter: the address of a word containing the address of the first element in the list (Sa). Use the print character syscal to add spaces between elements and a newline character at the end of your output. In order to test this procedure before insert is implemented, you can comment out the first definition of listPtr in the data section, then uncomment the second definition of listPtr, which provides a statically defined list with three elements: 2,-2, and 4. b. Implement the procedure, insert, that adds an element to the tail of the list. The procedure should take three parameters: the address of a word containing the address of the first element in the list (Sao), the value to insert (Sal), and the address of free Ptr ($a 2). Your insert procedure must call the provided alloc function, passing the address of free Ptr, to retrieve an unused node from the free list. c. Implement the procedure, delete, that removes an element from the list. The procedure should take three parameters: the address of a word containing the address of the first element in the list (Sa0), the value to delete (Sal), and the address of freePtr (Sa2). If the value occurs multiple times, only the first occurrence should be removed. Your delete procedure must call the provided free function, passing the address of free Ptr, to return the newly unused node to the free list. d. Implement the procedure, sort, that sorts the elements in the list in ascending order. The procedure should take one parameter: the address of a word containing the address of the first element in the list (SaO). Your implementation must use the merge sort algorithm and must be implemented recursively. e. Implement the procedure, search, that checks if an element is in the list. The procedure should take two parameters: the address of a word containing the address of the first element in the list (Sao) and the value to search for (Sa 1). Your procedure must return 1 if the element is in the list, and otherwise, Show transcribed image text 6. In this question, you will implement several operations to create a basic linked list in MIPS assembly language. Every node in the linked list is made up of 2 words, the first word holds the address of the next node (or null if there is no next node) and the second word holds an integer (the value of the node). The provided code for this question includes a complete .data section, placeholders for main and the five procedures which you will implement (print, insert, delete, sort, and search), and three fully implemented memory-management procedures (init, alloc, and free). Do not modify or add to the data section or the memory-management procedures. You code should manage memory by using the provided init, alloc, and free procedures and passing the address of freePtr. Your main procedure should begin by calling the init procedure, passing the address of freePtr. It should then repeatedly prompt the user for an operation to perform. Each time the user chooses an operation, it should then call the corresponding procedure which you will implement. If the corresponding procedure requires a parameter from the user (e.g., a value to insert), you must prompt for the additional input within main then pass the input to your procedure using standard procedure calling conventions. When an invalid operation number is entered, your program should terminate. (10 marks for main) Each of the five procedures you will implement must use the “standard” conventions discussed in class for passing parameters and returning results. One consequence of this is that console I/O should only be done in main and the print function. While implementing the five procedures, you may also create additional procedures (e.g., isEmpty, count, etc.) if this is helpful. (10 marks for each of the five procedures)
a. Implement the procedure, print, that outputs the elements in the list. The procedure should take one parameter: the address of a word containing the address of the first element in the list (Sa). Use the print character syscal to add spaces between elements and a newline character at the end of your output. In order to test this procedure before insert is implemented, you can comment out the first definition of listPtr in the data section, then uncomment the second definition of listPtr, which provides a statically defined list with three elements: 2,-2, and 4. b. Implement the procedure, insert, that adds an element to the tail of the list. The procedure should take three parameters: the address of a word containing the address of the first element in the list (Sao), the value to insert (Sal), and the address of free Ptr ($a 2). Your insert procedure must call the provided alloc function, passing the address of free Ptr, to retrieve an unused node from the free list. c. Implement the procedure, delete, that removes an element from the list. The procedure should take three parameters: the address of a word containing the address of the first element in the list (Sa0), the value to delete (Sal), and the address of freePtr (Sa2). If the value occurs multiple times, only the first occurrence should be removed. Your delete procedure must call the provided free function, passing the address of free Ptr, to return the newly unused node to the free list. d. Implement the procedure, sort, that sorts the elements in the list in ascending order. The procedure should take one parameter: the address of a word containing the address of the first element in the list (SaO). Your implementation must use the merge sort algorithm and must be implemented recursively. e. Implement the procedure, search, that checks if an element is in the list. The procedure should take two parameters: the address of a word containing the address of the first element in the list (Sao) and the value to search for (Sa 1). Your procedure must return 1 if the element is in the list, and otherwise,

Expert Answer

---

Answer to # Given file .data freePtr: .word 0 0 listPtr: .word 0 # listPtr: .word c1; c1: .word c3 2; c2: .word 0 4; c3: .word c2… . . .