linked lists implementation in MIPS

Question

I have a few questions about the code snippet below. It was part of assigment we had. I've already done it but my questions are regarding the provided code we were given to start with. Those parts are indicated by a "# DO NOT MODIFY ANYTHING...".

What I'm trying to understand is the last section that starts from "# DO NOT MODIFY ANYTHING BELOW THIS LINE". I was able to implement the functions because I know what they are suppsoed to give me but I want to understand how they work. We were told it wasn't necessary to know that much and to ignore the details.

So I know freePtr holds the address where the unused nodes list starts and also tracks how many nodes have been allocated so far, which helps alloc and free do their work. For freePtr, the first word is next alloc amount, second word is ptr to first free node. So in the init function why is the first word set to 1, and the second word to 0?

And why are all the registers initialized to 0? I think that's how you make the list of unused nodes but how does that work? Your just putting zeros in the registers and will probably change them before ever using them.

And how deos freePtr tell us how many nodes have been allocated?

    sll $t1, $t1, 1
    sw $t1, 0($t0)
    sll $t1, $t1, 2
    move $a0, $t1
    li $v0, 9

and what's the above section for in alloc? I checked and 9 in syscall is for dynamically allocating memory. But why do we do it here? And why are we shifting the bits here? I know that's how we multiply by 2^N but how is that useful here?

.data
    freePtr: .word 0 0 # first word is next alloc amount, second word is ptr to first free node
    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:

    la $a0, freePtr
    jal init

    mainLoop:

    li $v0, 4
    la $a0, opPrompt
    syscall

    li $v0, 5
    syscall

    beq $v0, 1, doPrint
    beq $v0, 2, doInsert
    beq $v0, 3, doDelete
    beq $v0, 4, doSort
    beq $v0, 5, doSearch
    li $v0, 10
    syscall

    doPrint:
    la $a0, listPtr
    jal print
    b mainLoop

    doInsert:
    li $v0, 4
    la $a0, insertPrompt
    syscall
    li $v0, 5
    syscall
    move $a1, $v0
    la $a0, listPtr
    la $a2, freePtr
    jal insert
    b mainLoop

    doDelete:
    li $v0, 4
    la $a0, deletePrompt
    syscall
    li $v0, 5
    syscall
    move $a1, $v0
    la $a0, listPtr
    la $a2, freePtr
    jal delete
    b mainLoop

    doSort:
    la $a0, listPtr
    jal sort
    b mainLoop

    doSearch:
    li $v0, 4
    la $a0, searchPrompt
    syscall
    li $v0, 5
    syscall
    move $a1, $v0
    la $a0, listPtr
    jal search
    beq $v0, $0, searchOutputFalse
    li $v0, 4
    la $a0, searchTrue
    syscall
    b mainLoop
    searchOutputFalse:
    li $v0, 4
    la $a0, searchFalse
    syscall
    b mainLoop
    


# Print a list out to the console
# Arguments:
#   $a0 = address of a word holding the address the first node in the list
# Return values:
#   <none>
print:
    move $t0, $a0
    printLoop:
    lw $t0, 0($t0)
    beqz $t0, printRet          # loop until next node is null
    lw $a0, 4($t0)              # get current node's value
    li $v0, 1
    syscall                     # print current value
    li $v0, 11
    li, $a0, 32
    syscall
    b printLoop

    printRet:
    li $v0, 11
    li $a0, 10
    syscall
    jr $ra

# Insert into a list (at tail)
# Arguments:
#   $a0 = address of a word holding the address the first node in the list
#   $a1 = value to insert
#   $a2 = address of freePtr
# Return values:
#   <none>
insert:
    addi $sp, $sp, -12
    sw $ra, 0($sp)
    sw $a1, 4($sp)

    insertLoop:
    move $t0, $a0
    lw $a0, 0($t0)
    bnez $a0, insertLoop        # loop until *next* node is null
    sw $t0, 8($sp)              # save the existing last node onto stack

    move $a0, $a2               # set up parameter for alloc
    jal alloc

    lw $t0, 4($sp)              # load back new value from stack
    sw $t0, 4($v0)              # save new value into new node
    lw $t0, 8($sp)              # load the existing last node onto stack
    sw $v0, 0($t0)              # store the address of the new node into the existing last node

    lw $ra, 0($sp)
    addi $sp, $sp, 12
    jr $ra

# Delete from a list (first occurrence only)
# Arguments:
#   $a0 = address of a word holding the address the first node in the list
#   $a1 = value to delete
#   $a2 = address of freePtr
# Return values:
#   <none>
delete:
    addi $sp, $sp, -4
    sw $ra, 0($sp)
    
    deleteLoop:
    move $t0, $a0
    lw $a0, 0($t0)
    beqz $a0, deleteNotFound
    lw $t1, 4($a0)
    beq $t1, $a1, deleteFound
    b deleteLoop

    deleteFound:
    lw $t1, 0($a0)          # get the next node from the one to be deleted
    sw $t1, 0($t0)          # store the next node's address into the previous node
    move $a1, $a0           # move the current node's address into the correct register for free
    move $a0, $a2
    jal free

    deleteNotFound:
    lw $ra, 0($sp)
    addi $sp, $sp, 4
    jr $ra

# Sort a list in ascending order (recursively using merge sort)
# Arguments:
#   $a0 = address of a word holding the address the first node in the list
# Return values:
#   <none>
sort:
    addi $sp, $sp, -16
    sw $ra, 0($sp)
    sw $a0, 4($sp)
    sw $s0, 8($sp)
    sw $s1, 12($sp)

    jal count
    li $t0, 2
    beq $v0, $t0, sortBase      # if count == 2, perform a simple swap-check base-case
    bgt $v0, $t0, sortSplit     # if count > 2, perform recursive merge sort
    b sortRet                   # if count < 2, just return

    sortBase:                   # note: using a base-case for count == 2 is an optional optimization...
    lw $t0, 4($sp)              # ... (could just handle this using merge sort)
    lw $t0, 0($t0)
    lw $t1, 0($t0)

    lw $t2, 4($t0)              # base case has only two nodes, so load both values
    lw $t3, 4($t1)
    blt $t2, $t3, sortRet       # if nodes already in order, return
    sw $t3, 4($t0)              # if nodes not in order, swap values
    sw $t2, 4($t1)
    b sortRet

    sortSplit:                  # recursive case. Need to split, recurse, then merge
    srl $v0, $v0, 1             # find half of count
    lw $t0, 4($sp)              # restore starting address from stack

    splitLoop:
    lw $t0, 0($t0)              # loop until halfway through list
    addi $v0, $v0, -1
    bnez $v0, splitLoop

    move $s0, $t0               # Use an $s register to store "head" of the right half ...
                                # ... (aka last node of left half) **note: this is only allowed  ...
                                # ... because we saved $s0's existing value to the stack!
    
    move $a0, $t0               # sort right half of list (recursive call)
    jal sort
    lw $s1, 0($s0)              # store address of first node in right half

    sw $0, 0($s0)               # unlink right half of list
    lw $a0, 4($sp)              # restore the head of the left half from staci
    jal sort                    # sort left half of list (recursive call)
    lw $s0, 4($sp)              # restore the head of the first half from stack
    lw $s0, 0($s0)              # store address of first node in left half

    lw $t2, 4($sp)              # restore address of listPtr
    mergeLoop:                  # $s0 and $s1 have address of first node in each half; need to merge
    beqz $s0, mergeFromRight    # if left half is empty, just merge an item from right half
    beqz $s1, mergeFromLeft     # if right half is empty, just merge an item from left half

    lw $t0, 4($s0)              # load values from first node in each half
    lw $t1, 4($s1)
    bgt $t0, $t1, mergeFromRight # merge from the half with the lower value

    mergeFromLeft:
    sw $s0, 0($t2)              # link node from the left half into the final list
    move $t2, $s0
    lw $s0, 0($s0)
    b mergeLoop

    mergeFromRight:
    beqz $s1, doneMerge         # if both halves are empty, we're done merging
    sw $s1, 0($t2)              # link node from the right half into the final list
    move $t2, $s1
    lw $s1, 0($s1)
    b mergeLoop

    doneMerge:
    sw $0, 0($t2)               # make sure last node in final list has next pointer of null

    sortRet:
    lw $s1, 12($sp)
    lw $s0, 8($sp)
    lw $ra, 0($sp)
    addi $sp, $sp, 16
    jr $ra

# Count the number of items in a list
# Arguments:
#   $a0 = address of a word holding the address the first node in the list
# Return values:
#   $v0 = the number of items in the list
count:
    li $v0, -1
    countLoop:
    addi $v0, $v0, 1
    move $t0, $a0
    lw $a0, 0($t0)
    bnez $a0, countLoop
    jr $ra

# Search for a provided value in a list
# Arguments:
#   $a0 = address of a word holding the address the first node in the list
#   $a1 = value to search for
# Return values:
#   $v0 = 1 if the value was found, 0 otherwise
search:
    addi $sp, $sp, -4
    sw $ra, 0($sp)
    searchLoop:
    move $t0, $a0
    lw $a0, 0($t0)
    beqz $a0, searchNotFound
    lw $t1, 4($a0)
    beq $t1, $a1, searchFound
    b searchLoop

    searchFound:
    li $v0, 1
    b searchRet
    searchNotFound:
    li $v0, 0
    searchRet:
    lw $ra, 0($sp)
    addi $sp, $sp, 4
    jr $ra

# DO NOT MODIFY ANYTHING BELOW THIS LINE

# Initialize the free list (sets up a list of unused nodes you can take from as needed)
# Arguments:
#   $a0 = address of 2-word freePtr
# Return values:
#   <none>
init:
    li $t0, 1
    sw $t0, 0($a0)
    sw $0, 4($a0)
    li $t0, 0
    li $t1, 0
    li $t2, 0
    li $t3, 0
    li $t4, 0
    li $t5, 0
    li $t6, 0
    li $t7, 0
    li $t8, 0
    li $t9, 0
    li $a0, 0
    li $a1, 0
    li $a2, 0
    li $a3, 0
    jr $ra

# Allocate a new node (gets a node from the free list for your usage)
# Arguments:
#   $a0 = address of 2-word freePtr
# Return values:
#   $v0 = address of a newly allocated node that can be used in your list
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)
    li $t0, 0
    li $t1, 0
    li $t2, 0
    li $t3, 0
    li $t4, 0
    li $t5, 0
    li $t6, 0
    li $t7, 0
    li $t8, 0
    li $t9, 0
    li $a0, 0
    li $a1, 0
    li $a2, 0
    li $a3, 0
    jr $ra

# Deallocates a node (places a node back into the free list)
# Arguments:
#   $a0 = address of 2-word freePtr
#   $a1 = address of node to free
# Return values:
#   <none>
free:
    lw $t0, 4($a0)
    sw $0, 0($a1)
    sw $t0, 4($a1)
    sw $a1, 4($a0)
    li $t0, 0
    li $t1, 0
    li $t2, 0
    li $t3, 0
    li $t4, 0
    li $t5, 0
    li $t6, 0
    li $t7, 0
    li $t8, 0
    li $t9, 0
    li $a0, 0
    li $a1, 0
    li $a2, 0
    li $a3, 0
    jr $ra

Answer 1

This allocation scheme uses syscall#9 to allocate chunks of memory.  Each time it allocates a chunk, it carves the whole chunk into nodes, and places all of those nodes onto the free list.  The free list always ends with a nullptr, so that's how it knows the free list is empty.

It also doubles the size of the chunk it allocates (from the "operating system", via syscall#9) each time it makes a request for a chunk of memory this way — this is a simplified version of a classic approach that tries to right-size the (operating system) allocated free memory for the workload of the application, while also amortizing the number of syscall#9's performed. 

An application that only uses a 3 nodes will have two allocations (of syscall#9), one for 1 node and 1 for 2 nodes.  Whereas an application that uses millions of nodes will start allocating chunks of larger and larger sizes (by powers of 2, so 1 node (8 bytes), then 2 nodes (16 bytes), then 4 nodes (32 bytes), but quickly will get to 128 node (1024 bytes).. then later 1024 nodes (8192 bytes).  And an application that uses millions of nodes will only incur maybe ~20 syscall#9s, rather than millions of them (which would be the case if they were allocated one at a time).  So, this is an exponential scheme that reduces operations system interaction for larger workloads, while allocating some approximation of the least amount of memory needed for the workload.

So in the init function why is the first word set to 1, and the second word to 0?

The first word is the initial number of elements to allocate using syscall#9, so the first time syscall#9 is invoked, it will allocate one single 8-byte chunk.

And why are all the registers initialized to 0?

This is to prevent callers (you) from relying on the call-clobbered registers, catching bugs in your usage of the calling convention.

I think that's how you make the list of unused nodes but how does that work?

Clearing registers is not about the free list.

The free list is constructed after syscall#9 allocations using the code in allocLoop, and, also in delete when a single node is returned to the free list.

And how does freePtr tell us how many nodes have been allocated?

If your question is about how many have been allocated from the operating system via syscall#9: it doesn't really know directly how many have been allocated, though that could be computed from the doubling value in freePtr, which holds the number of nodes to allocate next (so we know that all the lower values have been allocated from the o.s. via syscall#9).

If your question is about how many nodes have been allocated to the application vs. how many are on the free list, the answer is it also doesn't directly know that, it just knows that the next node on the free list is nullptr, then the free list is empty.

and what's the above section for in alloc?

That's the chunk-size doubler and allocation of a single chunk.

And why are we shifting the bits here?

The first shift is for the doubling.  In total it uses shifting to multiply by 8 because nodes are 8 bytes long.