代码之家 › 专栏 › 技术社区 › ptb

将Torvalds的“好品味”应用于Fortran链表

iteration fortran linked-list recursion c

ptb · 技术社区 · 7 年前

几年前,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的引用调用语义:

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

1 回复 | 直到 7 年前

IanH 7 年前

在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