如何在x86汇编中从单链表中删除所有节点

Question

目前我给出了一个链表，只有一个下一个指针，但不是一个前一个指针。对于遍历列表，这是相对容易的。

    movl NEXT(%ebx), %ebx # ebx is the current node

然而，当我试图从最后一个一个地删除列表时，我似乎无法制定一个解决方案。目前，我想到了1。保存文件

    subl $4, %esp # reserve space to put in the prev pointer
    movl %ebx, -4(%ebp) # store current pointer into prev pointer 
    movl NEXT(%ebx), %ebx # walk down the list

然后是

    movl -4(%ebp), %edx # putting the prev pointer into edx
    pushl (%edx) # two pushes to give parameters for func call
    pushl (%ebx)
    call remove_func

和remove函数

    movl 12(%ebp), %edx # store prev pointer to edx
    movl 8(%ebp), %ebx # store current pointer aka node to be deleted at ebx
    movl NEXT(%ebx), %eax # temporarily store curr->next to eax
    movl %eax, NEXT(%edx) # prev->next=eax
    movl $0, (%ebx) # curr=NULL
    pushl %ebx # pushes params for func call
    call free_node

你大概知道我在这里要做什么。实际上，在使用NEXT遍历列表的过程中，将prev指针压入堆栈。然而，有了这个实现，我仍然不确定它是否会工作，因为我不知道它是否可以递归地走向顶部，或者它会在第一次删除时停止。我的第二种方法是将prev指针存储在寄存器中，而不将其压入堆栈。说% edi

    movl %ebx,%edi
    movl NEXT(%ebx), %ebx
    call remove_func

谢谢你的帮助。对不起，我的问题很长。编辑:该列表需要按倒序删除。这是经典的导弹命令游戏，我试图实现。

Answer 1

我不确定你到底遇到了什么问题，但我有一个有趣的想法来实现这一点，在向前遍历时利用调用堆栈作为堆栈数据结构，并在返回时使用它进行参数传递，而无需在任何地方复制任何内容。

假设:在释放列表节点时不需要修改它们。这是一个free-everything函数，所以我们可以设置HEAD=NULL，这样链表的任何其他用户(例如在信号处理程序或其他线程中)在我们仍然通过节点释放它们时将看到它为空。

# gas AT&T syntax, x86 32-bit, SysV calling convention
# untested
.globl list_free
list_free:       # void list_free(struct node **phead)
    mov    4(%esp), %eax     # phead:   node**
    mov    (%eax), %edx      # p=head:  node*  (points to the first node)
    # p (pointer to old head) in %edx
    test   %edx,%edx            # check that head wasn't NULL to start
    jz     .Llist_was_empty     # free(NULL) is safe, but we would also try to dereference
    xor    %ecx,%ecx         # count = 0
    mov    %ecx, (%eax)      # *phead=NULL   (chop the list off at the head)
# loop over the list, pushing the address of each node on the stack
.Lforward_loop               # do {
    push   %edx              #  push p
    mov    NEXT(%edx), %edx  #  p=p->next
    inc    %ecx              #  count++
    test   %edx,%edx
    jnz   .Lforward_loop     # } while(p)
# walk back up the stack, using each pointer as an arg to free()
.Lbackward_loop              # do {
    call   free              #   free takes one arg, which is already on the stack
    add    $4, %esp          #   or just pop %edx, which will run faster on Intel CPUs: doesn't force a stack-sync uop
    dec    %ecx              # } while(--count);
    jnz    .Lbackward_loop
.Llist_was_empty:
    ret

我故意没有"保持简单"之类的，因为我不知道你真正需要什么样的帮助。在思考了你的问题后，我基本上是为了自己的娱乐而写的。指令越少，需要理解的就越少。:)

我只需要三个寄存器，所以我不需要保存/恢复任何寄存器。而且我不需要任何局部变量，所以我也没有使用ebp创建堆栈框架。

---

在64位代码中(AMD64 SysV调用约定，其中第一个参数在%rdi中)，向后循环将是:

.Lbackward_loop              # do {
    pop    %rdi
    call   free              #   free(p)
    dec    %ecx              # } while(--count);
    jnz    .Lbackward_loop