在 MIPS 中迭代链表

Question

我是第一次使用汇编，我正在尝试实现一个链表。每个节点都是 2 个字——第一个是节点的值，第二个是列表中下一个节点的地址。对于最后一个节点，next 为零。列表的基数是包含第一个节点地址的字，如果列表为空则为 0。

我正在尝试实现“添加项”函数，其中第一个参数（$a0）是列表基址的地址，$a1 是存储我要添加的值的地址到我的名单。为此，我尝试遍历列表并找到最后一项，因此我将其“下一个”值设置为我创建的新节点。

我觉得这很丑陋（我同时使用“循环”和“增加”）并且我错过了一种更简单的遍历列表的方法，但我有点困惑如何使用一个循环正确执行此操作，因为我想在列表结束前停止 1 步实现此目标的更好方法是什么？

谢谢！！

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

Answer 1

你的遍历列表的代码没问题，看起来有点像这样：

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

至于改进，这里：

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

这个条件分支，围绕一个无条件分支分支。这是不必要的，因为我们可以反转条件并交换分支目标：

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

您将能够删除 j addItem 并且标签 increase 也将不再需要。

为了进一步改进，您的主列表对象可以保留指向列表末尾的指针。虽然在列表中添加和删除节点时需要更多维护，但它将消除查找列表末尾的搜索循环。

就您的内存分配而言，您正在为保留函数实例化的数据结构节点分配堆栈上的节点。这可能在短期内有效，但从长远来看，在运行时堆栈上分配持久数据结构非常容易出错。函数应该 return 到它的调用者，堆栈顶部（即堆栈指针的值）与调用时的位置相同。如果此函数的任何调用者以正常方式使用堆栈，他们将无法找到他们基于堆栈的 variables/storage.

MARS 和 QTSPIM 没有适当的 malloc 和 free 函数，但这些应该用于持久内存分配。这些模拟器有sbrk可以替代malloc但是没有相应的free操作。（我们可以说适当的 malloc 和 free 留作 reader 的练习；）

您可以更改堆栈的头部，但必须将其恢复到 returning 时的位置。通过这种方式，堆栈可用于其生命周期与函数调用持续时间相匹配的任何存储需求。

例如，假设 main 调用 A，A 调用 B，B 调用 C。因此，当 main 使用 jal A 时，它会在 $ra 中传递 A 一个（对 C 隐藏的）参数，它告诉 A 如何 return回到 main。但是，在 A 完成之前，它使用 jal B 调用 B。 jal 将重新调整 $ra 寄存器的用途，现在作为 B 到 return 到 A 的参数。如果没有缓解，A 的 $ra 参数（到 return 到 main）将被清除。因此，在A使用jal调用B之前，它保存了原来的$ra值。它最后需要这个值，所以它可以 return 到 main。因此，在调用 A 期间，A 将其 $ra 值存储在堆栈中。这在逻辑上释放了 $ra 寄存器以重新用于调用 B。类似的情况发生在 B。如果 C 是我们所说的叶函数（不进行任何函数调用），那么 C 将简单地留下 $ra 并在最后使用它。 Creturns到B，B从它分配的栈内存中取出它的return地址，释放它分配的栈内存，returns 到 A。 A 还获取存储在堆栈分配内存中的 return 地址，它可以找到该地址，因为堆栈指针与存储 return 地址时具有相同的值： jal B 操作，就 A 而言，并没有改变堆栈顶部，它在调用 B 之后位于同一个地方——即使 B 也分配（并释放）了一些内存.

总而言之，在许多情况下，函数需要一些本地存储，其生命周期与函数调用的持续时间完全匹配。堆栈是满足这些需求的廉价内存分配机制。

在 MIPS 中迭代链表

Iterating over a Linked List in MIPS

assembly

mips