MIPS linked list

Question

I'm confused exactly about how to create structures in MIPS. I want to create a linked list implementation which computes the length of the strings stored, and sorts them in stored-order. Here is my code so far:

# Global symbols
#
    # string routines
    .globl read_string
    .globl strcmp
    .globl strlen
    .globl trim
    .globl strloop
    .globl replace

    # list routines
    .globl insert
    .globl insert_here
    .globl print_list

    .globl  main

    # pseudo-standard library
    .globl get_string
    .globl malloc
    .globl print_newline
    .globl print_string


##################################################
# Constants
#
        .data
MAX_STR_LEN: .word 50
STR_NEWLINE: .asciiz "
"
STR_ENTER:   .asciiz "enter a string: "



#################################################################
#################################################################
# Code
#
    .text


##################################################
# main: repeatedly gets strings from user and enters them in list
# until a string of length less than two is entered;
# prints list in order when done
#
main:   
#   lines commented out - not needed in simulation:
#   addi $sp, $sp, -12
#   sw   $ra, 0($sp)
#   sw   $s0, 4($sp) #$s0 will be linked list
#   sw   $s1, 8($sp) #$s1 will be the current string
    li      $s0, 0  # initialize the list to NULL

Loop_main:
    la      $a0, STR_ENTER
    jal     print_string
    jal     read_string
    move    $s1, $v0
    jal     trim
    jal     strlen
    addi    $t0, $zero, 2
    beq     $v0, $t0, Exit_loop_main
    jal     strcmp
    jal     insert
    # replace newline with null terminator
    # ...

    # check string length; exit loop if less than 2
    # ...

    # insert string into list
    # ...
    # reassign front of list
    j       Loop_main

Exit_loop_main:
    move    $a0, $s0
    jal     print_list
    jal     print_newline
#   lines commented out - not needed in simulation:
#   lw   $s1, 8($sp)
#   lw   $s0, 4($sp)
#   lw   $ra, 0($sp)
#   addi $sp, $sp, 12
#   jr   $ra        
    # exit simulation via syscall
    li      $v0, 10
    syscall



##################################################
# String routines
#

# read_string: allocates MAX_STR_LEN bytes for a string
# and then reads a string from standard input into that memory address
# and returns the address in $v0
read_string:
    addi    $sp, $sp, -8            #allocate space for 2 items on the stack
    sw      $ra, 0($sp)             #push the jump register onto the stack
    sw      $s0, 4($sp)             #push the head of the list onto the stack
    add     $t0, $t0, $zero         #$t0 gets 0  
    la      $t1, MAX_STR_LEN        #$a0 gets MAX_STR_LEN
    lw      $a0, 0($t1)             #move MAX_STR_LEN from $t1 into $a0 
    jal     malloc                  #jump to malloc to allocate space for string
    move    $a0, $v0                #move pointer to allocated memory to $a0
    add     $t1, $t1, $zero         #get zero
    move    $a1, $t1                #move zero to a1
    la      $a1, MAX_STR_LEN        #$a1 gets MAX_STR_LEN
    jal     get_string              #get the string into $v0
    lw      $s0, 4($sp)             #load the head of the list
    lw      $ra, 0($sp)             #load the jump address
    addi    $sp, $sp, 8             #push onto the stack space for 2 elements
    jr      $ra                     #jump back to caller function


# trim: modifies string stored at address in $a0 so that
# first occurrence of a newline is replaced by null terminator
trim:
    li      $t0, 10                 #$t1 gets 10, ASCII value for newline
strloop:   
    lb      $t1, 0($a0)             #get byte of character of string and loop 
    beq     $t1, $t0, replace       #if $a0 = go to replace
    addi    $a0, $a0, 8             #increment $a0 by 8 to piont to first bit of next char
    j       strloop                 #jump back to beginning
replace:    
    add     $t2, $t2, $zero         #$t2 is set to zero, ASCII value for null terminator
    sb      $t2, 0($a0)             #$t2 is stored into the byte starting at $a0
    jr      $ra                     #jump back to caller

# strlen: given string stored at address in $a0
# returns its length in $v0
strlen: 
    add     $t0, $t0, $zero         #$t0 gets zero
lenloop:    
    lb      $t1, 0($a0)             #get the first byte for first char in $a0
    beq     $t1, $zero, exitline    #if $t1 == 0 (null terminator), jump to exit
    addi    $a0, $a0, 8             #else, increment to next byte of string for next char
    addi    $t0, $t0, 1             #increment $t0 for each character in string
    j       lenloop                 #jump back up to loop 
exitline:   
    sw      $t0, 0($v0)             #store $t0 into $v0 to return lenght of string
    jr      $ra                     #jump back to caller 



# strcmp: given strings s, t stored at addresses in $a0, $a1
# returns -1 if s < t; 0 if s == t, 1 if s > t
strcmp:
    lb      $t0, 0($a0)             #get byte of first char in string s 
    lb      $t1, 0($a1)             #get byte of first char in string t
  #  lb         $t3, 0($t0)
    #lb         $t4, 0($t1)
    addi    $t3, $t3, 1             #get 1 to compare
    slt     $t2, $t0, $t1           #if s[0] < t[0] $t2 = 1, else $t2 = 0
    bne     $t2, $t3, lessthan      #if $t2  == 1, jump to lessthan
    slt     $t2, $t1, $t0           #if t[0] < s[1], $t2 = 1, else $t2 = 0
    beq     $t2, $t3, greaterthan   #if $t2 == 1, jump to greaterthan
    sw      $zero, 0($v0)           #$v0 gets zero 
    j       end
lessthan: 
    addi    $t4, $t4, -1            #$t4 gets -1
    sw      $t4, 0($v0)             #$v0 gets -1 
    j       end                     #jump to end
greaterthan: 
    addi    $t4, $t4, 1             #$t4 gets 1
    sw      $t4, 0($v0)             #$v0 gets 1
    j       end                     #jump to end
end:      
    jr      $ra

# insert_here: given address of front of list in $a0 
# and address of string to insert in $a1, 
# inserts new linked-list node in front of list;
# returns address of new front of list in $v0
insert_here:
    lw      $t0, 0($a0)             #$t0 get $a0
    lw      $t1, 0($a1)             #$t1 gets $a1
    addi    $t2, $zero, 8           #$t2 gets 8 
    sw      $t2, 0($a0)             #$t2 gets stored into $a0
    jal     malloc                  #allocate 1 byte for the memory
    move    $t3, $v0                #get address of new memory from $v0 and move to $t3
    sw      $t1, 0($t3)             #store the string pointer into bytes 0-3 of the new memory
    sw      $t0, 4($t3)             #store the pointer to the original front of the list 
    sw      $t3, 0($s0)             #store the new node into $s0
    lw      $ra, 0($sp)             #pop the register to jump back to off the stack 
    addi    $sp, $sp, 4             #add to the stack
    jr      $ra                     #jump back to caller



##################################################
# List routines
#


# insert: given address of front of list in $a0 
# and address of string to insert in $a1, 
# inserts new linked-list node in appropriate place in list 
# ...
# returns address of new front of list in $v0 (which may be same as old)
insert: 
    addi    $sp, $sp, 4             #add space on the stack
    sw      $ra, 0($sp)             #store jump register onto the stack 
    lw      $t9, 0($a0)             #load head of the list for later use
    lw      $t0, 0($a0)             #load head of list into $t0
    andi    $t0, $t0, 240           #bitwise and with 240 (1111 0000) to extract first 4 bits for pointer to string
    sw      $t0, 0($a0)             #store $t0 into $a0 for strcmp call
    lb      $t6, 0($t0)             #get the byte of the first string char in the list
    lw      $t7, 0($a1)             #get address of string 
    lb      $t1, 0($t7)             #get the byte of the first char of the string
    addi    $t3, $zero, 1           #$t3 gets 1
    addi    $t4, $zero, -1          #$t3 gets -1
alphloop:                           #be careful in this function may have a bug with front of the list 
#   slt     $t2, $t1, $t0           #if $t1 < $t0, then $t2 = 1, else $t2 = 0 
#   beq     $t2, $t3, put           #if 
#   beq     $t2, $zero, nextchar
    jal     strcmp                  #compare the strings in $a0 and $a1 
    move    $t5, $v0                #move the value returned from strcmp into $t5
    beq     $t5, $t4, put           #if $t5 = -1, then value is less and then put new string at head of list
    beq     $t5, $t3, nextstring    #if $t5 = 1, then the head of the list is larger than the string and go to next string
    beq     $t5, $zero, close       #check if it is zero, if so it is already in the list so step out 
nextstring:
    lw      $t2, 0($a0)             #store pointer to next node in $t2
    andi    $t8, $t9, 15            #get address of next node string
    beq     $t8, $zero, put         #if it points to null then add node at the end
    sw      $t8, 0($a0)             #store into $a0 
    j       alphloop                #check against the next string in loop
put:    
    li      $t5, 8                  #$t5 gets 8 
    move    $a0, $t5                #$t5 moved into $a0 
    jal     malloc                  #allocate size for node 
    move    $t5, $v0                #move address returned by malloc to $t5
    sw      $a1, 0($t5)             #store $a1 into address allocated
    beq     $t2, $zero, front       #node is at front of the list, so there is no need to update pointer
    sw      $t2, 4($t5)             #store pointer to current node into new node
    addi    $t0, $a0, -8            #subtract from the current node back one 
    sw      $t5, 0($t0)             #store new pointer into the node
    jr      $ra
front: 
    sw      $t5, 0($s0)             #make global reference to front of the node the new node if its at the front
close:    
    jr      $ra                     #jump back 


# print_list: given address of front of list in $a0
# prints each string in list, one per line, in order
print_list:
    addi    $sp, $sp, -8
    sw      $ra, 0($sp)
    sw      $s0, 4($sp)
    move    $s0, $a0
    beq     $s0, $zero, Exit_print_list
Loop_print_list:
    lw      $a0, 0($s0)
    jal     print_string
    jal     print_newline
    lw      $s0, 4($s0) # node = node->next
    bne     $s0, $zero, Loop_print_list
Exit_print_list:
    lw      $s0, 4($sp)
    lw      $ra, 0($sp)
    addi    $sp, $sp, 8
    jr      $ra



##################################################
# Pseudo-standard library routines:
#   wrappers around SPIM/MARS syscalls
#

# assumes buffer to read into is in $a0, and max length is in $a1
get_string:
    li      $v0, 8
            syscall
    jr      $ra

# malloc: takes one argument (in $a0) which indicates how many bytes
# to allocate; returns a pointer to the allocated memory (in $v0)
malloc: 
    li      $v0, 9  # SPIM/MARS code for "sbrk" memory allocation
            syscall
    jr      $ra

# print_newline: displays newline to standard output
print_newline:
    li      $v0, 4
    la      $a0, STR_NEWLINE
            syscall
    jr      $ra

# print_string: displays supplied string (in $a0) to standard output
print_string:
    li      $v0, 4
            syscall  
    jr      $ra

Where should I go from here? My code assembles but does not do anything after reading in two inputs.

Answer 1

You did a great job with your level of commenting, style, and the program layout. Some of the best I've seen on SO. Overall, a good effort.

However, there were bugs.

I've produced an annotated version of your code and a refactored one. See below.

---

There were a number of bugs throughout the code, not related to the struct or insert code [there were at least 26 such bugs].

A frequent one was often repeating a wrong single instruction. This was often wanting to set a register with a constant. Your code used (e.g.) addi $t3,$t3,7 instead of the correct addi $t3,$zero,7. I replaced those with li $t3,7. In a few places, you did use the correct version, so I'd call this a "typo" bug, but there were a lot of them.

Your strcmp only compared the first character and not the whole string.

The actual insertion code was a bit convoluted and much more complicated than it needed to be (e.g. insert_here wasn't used). It also had some severe logic/implementation bugs. You were on the right track, but, after fixing so many other unrelated bugs, I decided to rewrite it rather than try to patch it.

---

Here's the annotated version [stripped down for SO space limits] where I fixed most of the one line bugs [annotated with "BUG"], but the code is still not yet runnable and no fixes to the struct/insert logic. I tried to remain faithful to your original code [please pardon the gratuitous style cleanup]:

main:
    # BUGBAD: this is the list pointer but it is _never_ set to a non-null
    # value but things get stored relative to it
    li      $s0,0                   # initialize the list to NULL

Loop_main:
    la      $a0,STR_ENTER
    jal     print_string
    jal     read_string
    move    $s1,$v0

    # BUG: trim uses and trashes a0 but strlen needs the original value
    jal     trim
    jal     strlen
    addi    $t0,$zero,2
    beq     $v0,$t0,Exit_loop_main

    # BUG: this strcmp serves _no_ purpose
    jal     strcmp

    jal     insert
    # replace newline with null terminator
    # ...

    # check string length; exit loop if less than 2
    # ...

    # insert string into list
    # ...
    # reassign front of list
    j       Loop_main

Exit_loop_main:
    move    $a0,$s0
    jal     print_list
    jal     print_newline

    li      $v0,10
    syscall

read_string:
    addi    $sp,$sp,-8
    sw      $ra,0($sp)
    sw      $s0,4($sp)

    # BUG: this does _not_ set t0 = 0
    ###add      $t0,$t0,$zero       # $t0 gets 0
    li      $t0,0
    # BUGFIX

    # BUG: MAX_STR_LEN should be a _constant_ (e.g. 80) but this is an _address_
    ###la       $t1,MAX_STR_LEN         # $a0 gets MAX_STR_LEN
    lw      $t1,MAX_STR_LEN         # $a0 gets MAX_STR_LEN
    # BUGFIX

    lw      $a0,0($t1)              # move MAX_STR_LEN from $t1 into $a0
    jal     malloc                  # allocate space for string
    move    $a0,$v0                 # move pointer to allocated memory to $a0

    # BUG: this does _not_ set t1 = 0
    ###add      $t1,$t1,$zero           # get zero
    li      $t1,0                   # get zero
    # BUGFIX

    move    $a1,$t1                 # move zero to a1

    # BUG: this does not set a1 = 50
    ###la       $a1,MAX_STR_LEN         # $a1 gets MAX_STR_LEN
    lw      $a1,MAX_STR_LEN         # $a1 gets MAX_STR_LEN
    # BUGFIX
    jal     get_string              # get the string into $v0

    lw      $s0,4($sp)
    lw      $ra,0($sp)
    addi    $sp,$sp,8
    jr      $ra

# trim: modifies string stored at address in $a0 so that
# first occurrence of a newline is replaced by null terminator
trim:
    # NOTE: using hex for this would be better (e.g. 0x0A)
    li      $t0,10                  # $t1 gets 10, ASCII value for newline

strloop:
    lb      $t1,0($a0)              # get byte of char of string and loop
    beq     $t1,$t0,replace         # if $a0 = go to replace
    # BUG: the increment should be 1
    ###addi $a0,$a0,8               # increment $a0 by 8 to piont to first bit of next char
    addi    $a0,$a0,1               # increment $a0 by 1 to point to next char
    # BUGFIX
    j       strloop                 # jump back to beginning

replace:
    # BUG: this does _not_ set t2 to 0
    ###add      $t2,$t2,$zero           # $t2 is set to zero, ASCII value for null terminator
    li      $t2,0                   # t2 = zero, ASCII value for EOS
    # BUGFIX

    sb      $t2,0($a0)              # $t2 is stored into byte at $a0
    jr      $ra                     # jump back to caller

# strlen: given string stored at address in $a0
# returns its length in $v0
strlen:
    # BUG: this does _not_ set t0 to zero
    ###add      $t0,$t0,$zero           # $t0 gets zero
    li      $t0,0
    # BUGFIX

lenloop:
    lb      $t1,0($a0)              # get the first byte for first char in $a0
    beq     $t1,$zero,exitline      # if $t1 == 0 (null terminator), exit

    # BUG: the increment here is wrong -- it should be 1
    ###addi $a0,$a0,8               # else, increment to next byte of string for next char
    addi    $a0,$a0,4               # else, increment to next byte of string
    # BUGFIX

    addi    $t0,$t0,1               # increment $t0 for each char in string
    j       lenloop                 # jump back up to loop

exitline:
    # BUG: this stores the length at the _address_ pointed to in v0
    ###sw       $t0,0($v0)              # store $t0 into $v0 to return lenght of string
    move    $v0,$t0
    # BUGFIX
    jr      $ra                     # jump back to caller

# BUG: this only compares the first character
# strcmp: given strings s, t stored at addresses in $a0, $a1
# returns -1 if s < t; 0 if s == t, 1 if s > t
strcmp:
    lb      $t0,0($a0)              # get byte of first char in string s
    lb      $t1,0($a1)              # get byte of first char in string t
    #  lb         $t3, 0($t0)
    # lb         $t4, 0($t1)
    # BUG: this does not set t3 = 1
    ###addi $t3,$t3,1               # get 1 to compare
    li      $t3,1
    # BUGFIX
    slt     $t2,$t0,$t1             # if s[0] < t[0] $t2 = 1, else $t2 = 0
    bne     $t2,$t3,lessthan        # if $t2  == 1, jump to lessthan
    slt     $t2,$t1,$t0             # if t[0] < s[1], $t2 = 1, else $t2 = 0
    beq     $t2,$t3,greaterthan     # if $t2 == 1, jump to greaterthan
    # BUG: this does not set v0 = 0
    ###sw       $zero,0($v0)            # $v0 gets zero
    li      $v0,0
    # BUGFIX
    j       end

lessthan:
    # BUG: this does _not_ set t4 = -1
    ###addi $t4,$t4,-1              # $t4 gets -1
    li      $t4,-1
    # BUGFIX
    # BUG: this does not set v0
    ###sw       $t4,0($v0)              # $v0 gets -1
    move    $v0,$t4
    # BUGFIX
    j       end                     # jump to end

greaterthan:
    # BUG: this does _not_ set t4 = 1
    ###addi $t4,$t4,1               # $t4 gets 1
    li      $t4,1
    # BUGFIX
    # BUG: this does not set v0
    ###sw       $t4,0($v0)              # $v0 gets 1
    move    $v0,$t4
    # BUGFIX
    j       end                     # jump to end

end:
    jr      $ra

# BUG: the front of the list is _always_ s0
# insert: given address of front of list in $a0
# and address of string to insert in $a1,
# inserts new linked-list node in appropriate place in list
# ...
# returns address of new front of list in $v0 (which may be same as old)
insert:
    # BUG: should be -4
    ###addi $sp,$sp,4
    addi    $sp,$sp,-4
    # BUGFIX
    sw      $ra,0($sp)

    lw      $t9,0($a0)              # load head of the list for later use
    lw      $t0,0($a0)              # load head of list into $t0

    # BUG: anding a _pointer_ against 0xF0 makes _no_ sense
    # NOTE: better to use hex for bit patterns
    ###andi $t0,$t0,240             # bitwise and with 240 (1111 0000) to extract first 4 bits for pointer to string
    # BUGFIX

    # BUG: this block of code is on the right track, but, wrong
    # storing into a0 (the struct) for strcmp makes _no_ sense
    sw      $t0,0($a0)              # store $t0 into $a0 for strcmp call
    lb      $t6,0($t0)              # get the byte of the first string char in the list
    lw      $t7,0($a1)              # get address of string
    lb      $t1,0($t7)              # get the byte of the first char of the string

    # NOTE: while we can set these here, we're burning two regs across the
    # strcmp call -- cleaner to move this below the call
    addi    $t3,$zero,1             # $t3 gets 1
    addi    $t4,$zero,-1            # $t3 gets -1

# be careful in this function may have a bug with front of the list
alphloop:
    #   slt     $t2, $t1, $t0           #if $t1 < $t0, then $t2 = 1, else $t2 = 0
    #   beq     $t2, $t3, put           #if
    #   beq     $t2, $zero, nextchar

    # BUG: strcmp destroys the values of a0 and a1, so the second time through
    # here they have bogus values
    # BUGBAD: strcmp uses them as pointers to the _strings_ but here, we're using
    # a0 as a _struct_ pointer!!!
    jal     strcmp                  # compare the strings in $a0 and $a1
    move    $t5,$v0                 # move the value returned from strcmp into $t5
    beq     $t5,$t4,put             # if $t5 == -1, then value is less and then put new string at head of list
    beq     $t5,$t3,nextstring      # if $t5 == 1, then the head of the list is larger than the string and go to next string
    beq     $t5,$zero,close         # check if it is zero, if so it is already in the list so step out

nextstring:
    lw      $t2,0($a0)              # store pointer to next node in $t2

    # NOTE: use hex for bit masks (e.g. 0x0F)
    # BUG: this makes no sense
    andi    $t8,$t9,15              # get address of next node string

    beq     $t8,$zero,put           # if it points to null then add node at the end
    sw      $t8,0($a0)              # store into $a0
    j       alphloop                # check against the next string in loop

put:
    # NOTE: what is 8??? obviously, it's the size in bytes of a node, so the
    # comment should say that
    li      $t5,8                   # $t5 gets 8
    move    $a0,$t5                 # $t5 moved into $a0
    jal     malloc                  # allocate size for node
    move    $t5,$v0                 # move address returned by malloc to $t5

    sw      $a1,0($t5)              # store $a1 into address allocated
    beq     $t2,$zero,front         # node is at front of the list, so there is no need to update pointer
    sw      $t2,4($t5)              # store pointer to current node into new node
    addi    $t0,$a0,-8              # subtract from the current node back one
    sw      $t5,0($t0)              # store new pointer into the node
    jr      $ra

front:
    sw      $t5,0($s0)              # make global reference to front of the node the new node if its at the front

close:
    jr      $ra

---

Here's the cleaned up, refactored, corrected, and runnable code.

A few things I recommend:

(1) For labels within a function, to avoid conflicts with other functions, the labels should be prefixed with the function name (e.g. for your trim function [which I renamed to nltrim], you had a label strloop [which I renamed to nltrim_loop])

(2) Comments should describe intent in real world terms and not just describe the actual asm instruction.

I realize you're just starting out, but (e.g.) this:

addi $t3,$zero,7  # sets the value of $t3 to 7