Применение «хорошего вкуса» Торвальдса к связанному списку на Фортране - PullRequest
Новая
       25

Применение «хорошего вкуса» Торвальдса к связанному списку на Фортране

0 голосов
/ 05 мая 2018

Несколько лет назад Линус Торвальдс выступил с речью Теда, где продемонстрировал реализацию связанного списка, в которой удаляются посторонние тесты с использованием указателей на указатели, которые он считает «хорошим вкусом». Простой пример ниже: 

#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 и семантики вызова по фортрану: 

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 Ответ

0 голосов
/ 05 мая 2018

При работе с указателями в Фортране часто требуется использование промежуточного типа оболочки. Семантика этого типа оболочки ближе к семантике указателя 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
...