Re: Still more linked list magic :-)


deltaquattro@xxxxxxxxx wrote:
!Hello,

!I'm back again (-: no more bugs this time (thanks to your help),
!but I have a puzzling question on the way pointers work. As
!suggested by highegg, I write a complete working code (you can
!even cut and paste the complete post and compile it). The
!program is similar to the one Jugoslav wrote in post
!4hf5bbF1qde3vU1@xxxxxxxxxxxxxx, thread "Cannot deallocate a
!linked list". There are, however, some small but important
!differences.

MODULE linked_list


IMPLICIT NONE


SAVE


! Derived data types
TYPE :: my_pointer
REAL :: component ! data
TYPE(my_pointer), POINTER :: next => NULL() ! pointer to next
element
END TYPE my_pointer


! Module variables
TYPE(my_pointer), POINTER :: head, tail !head=>null(), tail=>null()
CONTAINS


SUBROUTINE dealloc_list(error) ! here it is the bad guy


IMPLICIT NONE


!calling parameters
INTEGER, INTENT(OUT) :: error ! 0 if deallocation succeeded
!local variables
INTEGER :: istat ! 0 if pointer deallocation succeeded
TYPE(my_pointer), POINTER :: current ! pointer to actual element
TYPE(my_pointer), POINTER :: temp ! used to keep track of the element
! following current before deallocating it


error = 0
! Check if the head of the list is allocated, otherwise exit
IF ( .NOT. ASSOCIATED(head) ) RETURN


current => head
DO
IF ( .NOT. ASSOCIATED(current) ) EXIT ! End of list reached


IF (ASSOCIATED(current%next)) THEN
temp => current%next
DEALLOCATE(current, STAT=istat)
IF ( istat /= 0 ) THEN
error = 1
RETURN
END IF
current => temp ! Proceed to next point
ELSE
DEALLOCATE(current, STAT=istat)
IF ( istat /= 0 ) THEN
error = 1
RETURN
END IF
END IF
END DO
!! FIRST DIFFERENCE
PRINT *, 'in dealloc_list, before explicit nullification of head:'
PRINT *, 'status of head'
PRINT *, ASSOCIATED(head)
PRINT *, 'status of head%next'
PRINT *, ASSOCIATED(head%next)
PRINT *, 'status of head%next%next'
PRINT *, ASSOCIATED(head%next%next)
!!
NULLIFY(head)


END SUBROUTINE dealloc_list


END MODULE linked_list




! LinkList.f90
!
! FUNCTIONS:
! LinkList - Entry point of console application.
!


!**************************************************************************­**

!
! PROGRAM: LinkList
!
! PURPOSE: Entry point for the console application.
!
!**************************************************************************­**



program LinkList


use linked_list


implicit none


integer:: i, j
TYPE(my_pointer), POINTER :: current ! pointer to actual element


! Variables
allocate(head)
current => head
current%component = 0


do i=1,10
allocate(current%next)
current%next%component = i
current=>current%next
end do

!! SECOND DIFFERENCE
print *, 'before calling dealloc_list:'
print *, 'status of head'
print *, associated(head)
!!
call dealloc_list(i)


print *, 'after calling dealloc_list:'
print *, 'status of head'
print *, associated(head)


! Body of LinkList


end program LinkList


!Now, if I compile and execute this code, the output is:

!before calling dealloc_list:
!status of head
!T
!in dealloc_list, before explicit nullification of head:
!status of head
!T
!status of head%next
!T
!status of head%next%next
!T
!after calling dealloc_list:
!status of head
!F

!That doesn't sound right to me. I agree that "head" should
!be still associated, *in* dealloc_list but *before* explicit
!nullification.

No, you're wrong. At that point, head's association status is
undefined, because
its target has been deallocated (in the very first cycle of the
previous loop).
You are deallocating your list starting from the head.

But why "head"'s followers are also still
!associated? We deallocated them before. However, the thing
!that I really cannot understand is this: try commenting out
!the second difference, i.e. instructions

! print *, 'before calling dealloc_list:'
! print *, 'status of head'
! print *, associated(head)

!in program LinkList. Well, guess what happens now??

Because you're reading random garbage from memory.

a simple version of your procedure would be:
SUBROUTINE dealloc_list(error) ! here it is the bad guy
IMPLICIT NONE
!calling parameters
INTEGER, INTENT(OUT) :: error ! 0 if deallocation succeeded
!local variables
INTEGER :: istat ! 0 if pointer deallocation succeeded
TYPE(my_pointer), POINTER :: temp

error = 0

DO WHILE(ASSOCIATED(head))
tmp => head
head => head%next
DEALLOCATE(tmp, STAT=istat)
IF (istat /= 0) THEN
error = 1
EXIT
END IF
END DO
END SUBROUTINE dealloc_list

.

Relevant Pages

  • Still more linked list magic :-)
    ... if pointer deallocation succeeded ... TYPE(my_pointer), POINTER:: current! ... Check if the head of the list is allocated, ... print *, 'before calling dealloc_list:' ...
    (comp.lang.fortran)
  • Re: Simple question, err... I think
    ... One assumption is then that client code should leak memory. ... Given that there's no deallocation for these RB trees, ... a pointer to an invalid tree and it might segfault. ...
    (comp.programming)
  • [RFC][PATCH] Improve readability by hiding read_barrier_depends() calls
    ... it is sometimes difficult to figure out which pointer is ... extern void rcu_check_callbacks(int cpu, int user); ... #define list_for_each_safe_rcu(pos, n, head) \ ... * Double linked lists with a single pointer list head. ...
    (Linux-Kernel)
  • Re: Skybucks Warrior: CleanTheHouseV2
    ... org head ... contains the pointer for clearing so when it overwrites the pointer ... trail of processes that makes your warrior stronger. ... Location 'gate' is incremented continuously, ...
    (rec.games.corewar)
  • Re: LinkedList Pointer (REPOST - diff version)
    ... > Here's the original problem. ... > struct node * next; ... > No problem until you are dealing with a pointer variable. ... > node** pointer to the head pointer), add a new node at the head of the ...
    (comp.lang.c)