时间戳

首页 > 解决方案 > 将 Torvalds 的“Good Taste”应用于 Fortran 链表

c - 将 Torvalds 的“Good Taste”应用于 Fortran 链表

问题描述

几年前，Linus Torvalds 做了一个 ted 演讲，他展示了一个链表实现，该实现通过使用指向指针的指针来删除无关的 if 测试，他认为这是“好品味”。一个简单的例子如下：

#include <stdio.h>
#include <stdlib.h>

struct list_entry {
    int val;
    struct list_entry *next;
};

void list_insert(struct list_entry **head, int val)
{
    while (*head)
        head = &(*head)->next;

    *head = calloc(1, sizeof(**head));
    (*head)->val = val;
}

int main(int argc, char *argv[])
{
    struct list_entry *head = NULL;

    list_insert(&head, 0);
    list_insert(&head, 1);

    printf("Entry 1: %d\n", head->val);
    printf("Entry 2: %d\n", head->next->val);      
}

list_insert通过使用递归和 fortran 的引用调用语义，我能够在 fortran 中进行类似的工作：

module list_type
    implicit none

    type :: list
        integer :: val
        type(list), pointer :: next => null()
    end type list

contains

    recursive subroutine list_insert(lst, val)
        type(list), pointer, intent(inout) :: lst
        integer :: val
        !-
        if (associated(lst)) then
            call list_insert(lst%next, val)
            return
        else
            allocate(lst)
            lst%val = val
        end if
    end subroutine list_insert

end module list_type

program list_test
    use list_type
    implicit none

    type(list), pointer :: head => null()

    call list_insert(head, 0)
    call list_insert(head, 1)
    call list_insert(head, 2)

    print *, head%val
    print *, head%next%val
    print *, head%next%next%val
end program list_test

有没有办法在不诉诸递归的情况下完成这项工作？到目前为止，我所有的尝试都以失败告终。

编辑：这是我的迭代方法不起作用的示例

module list_type
    ...

    type :: list_ptr
        type(list), pointer :: p
    end type list_ptr

contains
    ...

    subroutine list_insert_iter(lst, val)
        type(list), pointer, intent(inout) :: lst
        integer :: val
        !-
        type(list_ptr)  :: walker

        walker%p => lst
        do while (associated(walker%p))
            walker%p => lst%next
        end do
        allocate(walker%p)
        walker%p%val = val
    end subroutine list_insert_iter

end module list_type

program list_test
    use list_type
    implicit none

    type(list), pointer :: head => null()

    call list_insert_iter(head, 0)   
    if (.not.associated(head)) stop "FAIL"

end program list_test

标签： crecursionlinked-listfortraniteration

解决方案

在 Fortran 中处理指针时，通常需要使用中间包装类型。这种包装器类型的语义更接近于 C 指针的语义，而不是纯 Fortran 指针。

举个例子：

module list_type
    implicit none

    type :: list_ref
      type(list), pointer :: ref => null()
    end type list_ref

    type :: list
        integer :: val
        type(list_ref) :: next
    end type list
contains
    subroutine list_insert(lst_arg, val)
      type(list_ref), intent(inout), target :: lst_arg
      integer, intent(in) :: val

      type(list_ref), pointer :: lst

      lst => lst_arg

      do while (associated(lst%ref))
        lst => lst%ref%next
      end do

      allocate(lst%ref)
      lst%ref%val = val
    end subroutine list_insert
end module list_type

program list_test
    use list_type
    implicit none

    type(list_ref) :: head

    call list_insert(head, 0)
    call list_insert(head, 1)
    call list_insert(head, 2)

    print *, head%ref%val
    print *, head%ref%next%ref%val
    print *, head%ref%next%ref%next%ref%val
end program list_test

推荐阅读