链接列表在MIPS中实现

Question

我对下面的代码段有一些问题。这是我们所拥有的一部分。我已经做到了，但是我的问题是关于我们提供的提供的代码。这些零件由“＃请勿修改任何东西...”表示。

我要理解的是最后一节，它是从“＃不要修改此行以下的任何内容”开始的。我能够实施这些功能，因为我知道他们提供的东西可以给我什么，但我想了解它们的工作方式。有人告诉我们，不必知道这么多并忽略细节。

因此，我知道Freeptr拥有未使用的节点列表开始的地址，还跟踪到目前为止分配了多少个节点，这有助于Alloc和Free完成工作。对于freeptr，第一个单词是下一个Alloc量，第二个单词是第一个免费节点的PTR。 因此，在INIT函数中，为什么第一个单词将一个单词设置为1，而将第二个单词设置为0？

为什么所有的寄存器都将最初的寄存器最初为0？我认为这就是您如何列出未使用的节点的列表，但是它如何工作？您只是将零放入寄存器中，并且可能会在使用它们之前将其更改。

Deos Freeptr如何告诉我们分配了多少个节点？

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

上述部分在Alloc中是什么？我检查了SYSCALL中的9个用于动态分配内存。但是为什么我们在这里做呢？ 为什么我们要在这里移动碎屑？我知道这就是我们乘以2^n的方式，但是在这里有用吗？

.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

该分配方案使用SYSCALL＃9来分配大量内存。＆nbsp;每次分配块时，它都会将整个块雕刻成节点，然后将所有这些节点置于免费列表中。免费列表始终以nullptr结尾，因此知道免费列表是空的。

它还每次要求以这种方式要求进行大量内存的要求，将其分配的块大小（从“操作系统”）增加一倍 - 这是经典方法的简化版本，试图右 - 大小为应用程序工作负载分配的（操作系统）分配的免费内存，同时还摊销了执行的SYSCALL＃9的数量。＆nbsp;

仅使用3个节点的应用程序将具有两个分配（SYSCALL＃9），一个是1个节点，1个节点为2个节点。＆nbsp;而使用数百万节点的应用程序将开始分配较大和较大尺寸的块（通过2个功率，因此1个节点（8个字节），然后是2个节点（16个字节）（16个字节），然后是4个节点（32个字节），但是很快将会到达128个节点（1024个字节）。然后稍后1024个节点（8192个字节）。如果他们一次分配一个）。

因此，在init函数中，为什么将第一个单词设置为1，而第二个单词为0？

第一个单词是使用SYSCALL＃9分配的初始元素，因此首次调用Syscall＃9，它将分配一个8字节块。

为什么所有寄存器都将所有寄存器初始化为0？

这是为了防止呼叫者（您）依靠呼叫通话寄存器，从而在您使用呼叫约定中捕获错误。

我认为这就是您如何列出未使用的节点的列表，但是如何工作？

清算寄存器与免费列表无关。

免费列表是在SYSCALL＃9之后使用Allocloop中的代码分配后构建的，并且当单个节点返回到免费列表时，也会在删除中构建。

freeptr如何告诉我们已经分配了多少个节点？

如果您的问题是关于通过SYSCALL＃9从操作系统中分配了多少的问题：它并不直接知道有多少已分配，尽管可以从Freeptr中的倍增值中计算出来，该价值容纳节点数量要分配下一步（因此，我们知道所有较低的值都通过SYSCALL＃9从OS分配）。

如果您的问题是关于将多少个节点分配给应用程序的节点，而免费列表中有多少个节点，那么答案也不直接知道，它只是知道免费列表上的下一个节点是nullptr，然后免费列表为空。

和上述部分是什么？

那就是块大小的加倍和单个块的分配。

，为什么我们在这里移动碎片？

第一班是加倍的。＆nbsp;总共使用转移乘以8个，因为节点长8个字节。