CODEWITHSUNDEEP
assemblymips
ronihm
ronihm

Reputation: 65

Iterating over a Linked List in MIPS

It's my first time using assembly and I'm trying to implement a linked list. Each node is 2 words - the first one is the value of the node, and the second one is the address of the next node in the list. For the last node, next is zero. The base of the list is a word containing the address of the first node, or 0 if the list is empty.

I'm trying to implement the function "add item", where the first parameter ($a0) is the address of the base of the list, and $a1 is an address which stores the value I want to add to my list. In order to do that, I'm trying to iterate through the list and fins the last item so I set its "next" value to be the new node I created.

I feel like this is very ugly (I'm using both "loop" and "increase") and I'm missing out an easier way to iterate through the list, but I'm a bit confused how to do that properly using one loop, since I want to stop 1 step before the end of the list What's a better way to achieve this?

Thank you!!

AddItem:
    # first I make the new node:
    addi $sp,$sp,-8         # we make room in stack for the new item
    lw $t0,0($a1)           # load new item's value from its address
    sw $t0,0($sp)           # set new node's value
    sw $zero,4($sp)         # set new node's next to 0 because it's now the last item
    # now I want to find where to put it:
    lw $t2,0($a0)           # $t2 contains the address of the first node in the list
    beq $t2,$zero,AddFirstItem  # in case the list is empty and we add the first item
    # if the list is not empty we need to find the last item:
    add $t0,$zero,$t2       # initialize $t0 to point to first node
    loop:
    lw $t1,4($t0)           # $t1 is the address of next item
    bne $t1,$zero,increase
    j addItem           # when we reach here, $t0 is the last item of the list
    increase:           # we iterate on the items in the list using both "loop" and "increase"
    add $t0,$t1,$zero       # $t0 which is the current item is now updates to current item's next
    j loop
    
    addItem:
    sw $sp,4($t0)           # set current item ($t0) next to be the node we created 
    j EndAddItem
    
    AddFirstItem:
    sw $sp,0($a0)       # setting the base of the list to the node we created
    
    EndAddItem:
    jr $ra

Upvotes: 1

Views: 977

Answers (1)

Erik Eidt
Erik Eidt

Reputation: 26656

Your code for traversing the list is ok, and looks a bit like this:

...
while ( node != null ) {
    prev = node;
    node = node -> next;
}
// node is null and prev is the last non-null pointer

As far as improvements, here:

    bne $t1,$zero,increase
    j addItem           # when we reach here, $t0 is the last item of the list
increase:

This conditional branch, branches around an unconditional branch.  This is unnecessary, as we can reverse the condition and swap the branch targets:

    beq $t1,$zero,addItem
    # j addItem           # when we reach here, $t0 is the last item of the list
#increase:

You'll be able to eliminate the j addItem and the label increase will no longer be needed as well.

To improve things further, your primary list object can keep a pointer to the end of the list.  While that will require more maintenance as nodes are added and removed from the list, it will eliminate the search loop to find the end of the list.

As far as your memory allocation, you're allocating the nodes on the stack for a data structure node that persists the function's instantiation.  This may work in the short term, but for the long term, allocating persistent data structures on the runtime stack is super error prone.  A function is supposed to return to its caller with the top of the stack (i.e. the value of the stack pointer) in the same position as when it was called.  If any of the callers of this function have used the stack in the normal way, they won't be able to find their stack-based variables/storage.

MARS & QTSPIM don't have proper malloc and free functions, but those are what should be used for persistent memory allocation. These simulators have sbrk which can substitute for malloc but there's no corresponding free operation.  (We could say that a proper malloc and free are left as an exercise for the reader ;)

You can change the head of the stack, but must restore it to where it was upon returning.  In this way, the stack is used for any storage needs whose lifetime matches the function invocation's duration.

For example, let's say that main calls A and that A calls B and that B calls C.  So, when main uses jal A, it passes A a (hidden from C) parameter in $ra, which tells A how to return back to main.  However, before A is finished, it calls B, using jal B.  That jal will repurpose the $ra register, now as a parameter for B to return to A.  Without mitigation, A's $ra parameter (to return to main) is wiped out.  Therefore, before A uses jal to call B, it saves the original $ra value.  It needs this value at the end so it can return to main.  So, for the duration of the invocation of A, A stores its $ra value on the stack.  This logically frees up the $ra register to be repurposed to call B.  Similar happens in B.  If C is what we call a leaf function (doesn't make any function calls), then C will simply leave $ra alone and use it at the end.  C returns to B, and B fetches its return address from the stack memory it allocated, releases the stack memory it allocated, and returns to A. A also fetches the return address it stored in stack allocated memory, which it can find because the stack pointer has the same value as when it stored the return address: the jal B operation, as far as A is concerned, did not change the stack top, it is in the same place after calling B — even though B also allocated (and released) some memory.

In summary, there are a number of scenarios where a function needs some local storage whose lifetime exactly matches the duration of the function invocation.  The stack is the mechanism for inexpensive memory allocation to meet these needs.

Upvotes: 3

Related Questions