Segmentation errors in Fortran recursive tree implementation
I need to implement a tree structure in Fortran for a project, so I read various tutorials on the internet explaining how to do this. However, I keep getting errors or strange results.
Let's say I want to build a binary tree where each node stores an integer value. I also want to be able to insert new values into the tree and print the tree nodes. So I wrote a tree type that contains an integer, two pointers to child subtrees, and a boolean value that I set for .true. if there are no child subtrees:
module class_tree
implicit none
type tree
logical :: isleaf
integer :: value
type (tree), pointer :: left,right
end type tree
interface new
module procedure newleaf
end interface
interface insert
module procedure inserttree
end interface
interface print
module procedure printtree
end interface
contains
subroutine newleaf(t,n)
implicit none
type (tree), intent (OUT) :: t
integer, intent (IN) :: n
t % isleaf = .true.
t % value = n
nullify (t % left)
nullify (t % right)
end subroutine newleaf
recursive subroutine inserttree(t,n)
implicit none
type (tree), intent (INOUT) :: t
integer, intent (IN) :: n
type (tree), target :: tleft,tright
if (t % isleaf) then
call newleaf(tleft,n)
call newleaf(tright,n)
t % isleaf = .false.
t % left => tleft
t % right => tright
else
call inserttree(t % left,n)
endif
end subroutine inserttree
recursive subroutine printtree(t)
implicit none
type (tree), intent (IN) :: t
if (t % isleaf) then
write(*,*) t % value
else
write(*,*) t % value
call printtree(t % left)
call printtree(t % right)
endif
end subroutine printtree
end module class_tree
Insertion is always done in the left subtree, unless you try to insert it into the sheet. In this case, insertion is done for both subtrees to make sure the node always has 0 or 2 children. Printing is performed by bypassing the prefix.
Now if I try to run the following program:
program main
use class_tree
implicit none
type (tree) :: t
call new(t,0)
call insert(t,1)
call insert(t,2)
call print(t)
end program main
I get the output I want 0 1 2 2 1. But if I add "call insert (t, 3)" after "call insert (t, 2)" and run again, the output will be 0 1 2 0 and then I get a segfault.
I tried to find out if there was an error during insert or print, so I tried to run:
program main
use class_tree
implicit none
type (tree) :: t
call new(t,0)
call insert(t,1)
call insert(t,2)
write(*,*) 'A'
call insert(t,3)
write(*,*) 'B'
call print(t)
end program main
This makes the segfault go away, but I get very strange AB output 0 1 2673568 6 1566250180.
When searching the web for similar errors, I got results like here where it says it might be due to too many recursive calls. However, the call to insert (t, 3) should only contain 3 recursive calls ... I also tried to compile with gfortran with -g -Wall -pedantic -fbounds-check and run with the debugger. The error seems to be happening on the "if (t% isleaf)" line in the print routine, but I have no idea how.
Edit:
Following the comments, I compiled with -g -fbacktrace -fcheck=all -Wall
gfortran and tried to check the memory status. I'm completely new to this, so I'm not sure if I'm using my debugger (gdb) correctly.
After three inserts and before the call print
, everything seems to have gone well: for example, when I type p t % left % left % right % value
in gdb, I get the expected output (i.e. 3). If I just type p t
, the output is (.FALSE., 0, x, y) where x and y are hexadecimal numbers (memory addresses, I think). However, if I try p t % left
, I get something like a "description" of the pointer:
PTR TO -> (Type tree
logical(kind=4) :: isleaf
integer(kind=4) :: value
which is repeated a lot since each pointer points to a tree containing two pointers. I would expect output similar to the results p t
, but I have no idea if this is normal.
I also tried looking into memory: for example, if I type x/4uw t % left
, I get 4 words, the first 2 words seem to match isleaf
and value
, the last two memory addresses. Following memory addresses like this, I was able to visit all the nodes and I didn't find anything wrong.
Segfault occurs as part of the print procedure. If after the error enter p t
, it says that I cannot access address 0x0. Does this mean that my tree has been modified in some way when I try to print it?
source to share
The reason for your problems is the fact that out-of-scope variables are no longer valid. This is in contrast to languages like Python, where the number of existing pointers (refcount) is relevant.
In your particular case, this means that calls to newleaf(left, n)
and newleaf(right, n)
set the values left
and right
respectively, but those variables get the ouf of the scope and are therefore invalid.
The best approach is to select each sheet as needed (except the first one, since it is already selected and will not go out of scope until the end of the program).
recursive subroutine inserttree(t,n)
implicit none
type (tree), intent (INOUT) :: t
integer, intent (IN) :: n
if (t % isleaf) then
allocate(t%left)
allocate(t%right)
call newleaf(t%left,n)
call newleaf(t%right,n)
t % isleaf = .false.
else
call inserttree(t % left,n)
endif
end subroutine inserttree
source to share