Linked List in Assembly Language Homework Sample

The provided code builds a linked list, and inserts values into it. You need to write a routine to print all the values in the list (separated by commas). You also need to write a routine, to search for a value in the list and remove it. The printList routine takes the head of the list as a parameter, and it is guaranteed to not be null. The printList function should be recursive rather than looping. The removeElement routine takes 2 parameters, the address of the list and the value to remove. It should return the new head of the list, and only needs to remove the first instance of the value. For more assembly language programming help contact us for details.

Solution:

listnode.asm

# A note on choice of instructions:
# For pedagogical purposes, we avoided using instructions in the pseudoinstruction set
# as much as possible. Mostly, instead of li and move, we are using addiu and addu, and instead
# of bge/blt, we are using slt/slti with beq/bne.

# These below are declarations of constants.
# So, anywhere in my MIPS program where we use NEXT_OFFSET, it will be replaced
# exactly by a 4.
# Do not confuse these constants with things in the .data section. The assembler
# substitutes constant symbols for constant values during assembly.
# Constants DO NOT exist in the memory of your running program.
.eqv DATA_OFFSET 0 # the first field
.eqv NEXT_OFFSET 4 # the second field
.eqv SIZEOF_LISTNODE 8 # = sizeof(int)+sizeof(reference) = 4 + 4 = 8
.eqv TESTVALUES_LEN 4 # change if you change the testvalues below

# data section is where global data goes
.data

# int[] testvalues = {2,6,3,0}
testvalues: .word 2 6 3 0 # we use .word to mean each number should be 4 bytes, i.e. size of one int
.globl main

# text section is where the code goes
.text
j main

# Call this procedure to allocate
# and initialize a new ListNode
#
# Recall “new” in Java gets translated
# to two steps
# 1. allocate memory for the object
# 2. call the constructor to initialize the memory
#
# arguments:
# data: value for the ListNode’s data field
#
# return address of the new ListNode object
newListNode:
# prolog
addiu $sp,$sp,-8 # allocate space on the stack for two integers
sw $ra, 0($sp) # save the return address (because $ra will get overwritten by “syscall” below)
sw $s0, 4($sp) # save $s0, because we are writing a new value to it below

# 1.
addu $s0, $zero, $a0 # save the argument because we need it later
addiu $v0, $zero, 9 # call sbrk(SIZEOF_LISTNODE)
addiu $a0, $zero, SIZEOF_LISTNODE
syscall
addu $t0, $zero, $v0 # t0 = address of the ListNode, i.e. “this”

# 2.
sw $s0, DATA_OFFSET($t0) # this.data = data
# exactly equivalent to sw $s0, 0($t0); go look at the assebled code!
sw $zero, NEXT_OFFSET($t0) # this.next = null
# recall that we represent null with the address 0.
# again, exactly equivalent to sw $s0, 4($t0), just more convenient to write it with constants

# “new” has a return value: a reference to the allocated object, which is in t0
addu $v0, $zero, $t0

# epilog
lw $ra, 0($sp) # restore value of $ra we had during the prolog
lw $s0, 4($sp) # restore value of $s0 we had during the prolog
addiu $sp,$sp,8 # give back stack space
jr $ra # jump back to caller

# Append a new ListNode with the given data value to the end of the linked list
#
# arguments
# this: the address of the node we called .append on. Notice that this is an implicit argument in Java
# data: the data of the new node
#
# returns nothing
append:
# prolog
addiu $sp,$sp,-8 # allocate space on the stack for two integers
sw $ra, 0($sp) # save the return address because we will overwrite it when we recursively call append
sw $s0, 4($sp) # save $s0 because we need to use that register

addu $s0, $zero, $a0 # s0 = this
lw $t0, NEXT_OFFSET($s0) # t0 = this.next
bne $t0,$zero,we_have_not_reached_the_end # if (this.next==null)
# the base case, we are at the end of the list
addu $a0, $zero, $a1 # v0 = newListNode(data)
jal newListNode #
sw $v0, NEXT_OFFSET($s0)# this.next = v0
j append_end # nothing left to do except return

we_have_not_reached_the_end: # the case that we are not yet at the end of the list
addu $a0, $zero, $t0 # call this.next.append; a0 = this.next; a1 is still set to data
jal append #
# when recursive call returns, we just continue executing the next instruction,
# which happens to be the epilog below

append_end:
# epilog
lw $ra, 0($sp) # restore registers
lw $s0, 4($sp) #
addiu $sp,$sp,8 # give back stack frame
jr $ra # return to caller

# Print data field in order in the given list;
# e.g., if the list contains [2,6,3,0], then this
# procedure should print
# 2,6,3,0,
#
# Assume it will never be called on a NULL value
#
# exercise for the student; refer to append code for hints
printlist:

#
# YOUR SOLUTION HERE

# prolog
addiu $sp,$sp,-8 # allocate space on the stack for two integers
sw $ra, 0($sp) # save the return address because we will overwrite it when we recursively call append
sw $s0, 4($sp) # save $s0 because we need to use that register

addu $s0, $zero, $a0 # s0 = this

lw $a0, DATA_OFFSET($s0) # a0 = this.data
li $v0, 1 # print data number
syscall
li $a0, ‘,’ # print separator
li $v0, 11 # syscall to print character
syscall

lw $a0, NEXT_OFFSET($s0) # a0 = this.next
beq $a0,$zero,print_end # if this.next ==null, exit
jal printlist # else, recurse to printlist(this.next)
print_end:

# epilog
lw $ra, 0($sp) # restore registers
lw $s0, 4($sp) #
addiu $sp,$sp,8 # give back stack frame
jr $ra

# Remove a data field in order in the given list;
# e.g., if the list contains [2,6,3,0] and data parameter is 3, then this
# procedure should change the list to [2,6,0]
# only need to worry about the first ocurrence (if exists)
#
# Assume it will never be called on a NULL value
#
# exercise for the student; refer to append code for hints
remove:

#
# YOUR SOLUTION HERE
addiu $sp,$sp,-8 # allocate space on the stack for two integers
sw $ra, 0($sp) # save the return address because we will overwrite it when we recursively call append
sw $s0, 4($sp) # save $s0 because we need to use that register

addu $s0, $zero, $a0 # s0 = this
addu $s1, $zero, $zero # s1 = null (s1 will point to previous node)
rm_loop:
lw $t0, DATA_OFFSET($s0) # t0 = this.data
beq $t0, $a1, rm_found # if the data we search, remove
addu $s1, $zero, $s0 # s1 = this
lw $s0, NEXT_OFFSET($s0) # s0 = this.next
bne $s0,$zero,rm_loop # repeat if this.next !=null
j rm_return # if not found, return
rm_found:
beq $s1, $zero, rm_return # if trying to remove head, do nothing

lw $t0, NEXT_OFFSET($s0) # t0 = found.next
sw $t0, NEXT_OFFSET($s1) # prev.next = t0

rm_return:
# epilog
lw $ra, 0($sp) # restore registers
lw $s0, 4($sp) #
addiu $sp,$sp,8 # give back stack frame

jr $ra

main:
la $t0, testvalues # (REMEMBER that la is a pseudo instruction; go see what it turns into!)
lw $a0, 0($t0) # v0 = newListNode(testvalues[0])
jal newListNode #
addu $s0, $zero, $v0 # s0 = v0 = head

addiu $s1,$zero,1 # s1 is i

testloop:
slti $t0, $s1,TESTVALUES_LEN # i < TESTVALUES
beq $t0,$zero,testdone #
la $t0, testvalues # a1=testvalues[i]
sll $t1,$s1,2 #
addu $t0,$t0,$t1 #
lw $a1, 0($t0) #
addu $a0,$zero,$s0 # a0 = head
jal append
addiu $s1,$s1,1 # i++
j testloop

testdone:

addu $a0,$zero,$s0 # head node
jal printlist # print original list

addu $a0,$zero,$s0 # head node
li $a1, 3 # data = 3
jal remove # remove data

# new line
li $a0, ‘\n’
li $v0, 11
syscall

addu $a0,$zero,$s0 # head node
jal printlist # print new list

exit:
addiu $v0,$zero,10
syscall