Degenerate Conic

Linked Lists

So, I want to have a basic linked list manager, written in modern Fortran (2003/2008). Of course, Fortran provides you with nothing like this out of the box, but it does provide the tools to create such a thing (within reason). Pointers (introduced in Fortran 90) allow for the creation of dynamic structures such as linked lists. In Fortran, you can do quite a lot without having to resort to pointers (say, compared to C, where you can't get away from them if you want to do anything nontrivial), but in this case, we need to use them. With the addition of unlimited polymorphic variables in Fortran 2003, we can now also create heterogeneous lists containing different types of variables, which is quite handy. There are some good Fortran linked-list implementations out there (see references below). But none seemed to do exactly what I wanted. Plus I wanted to learn about this stuff myself, so I went ahead and started from scratch. My requirements are that the code:

Accept any data type from the caller. I don't want to force the caller to stuff their data into some standard form, or make them have to extend an abstract derived type to contain it.
Accept data that may perhaps contain targets of pointers from other variables that are not in the list. This seems useful to me, but is an aspect that is missing from the implementations I have seen, as far as I can tell. If the data is being pointed to by something externally, doing a sourced allocation to create a copy is not acceptable, since the pointers will still be pointing to the original one and not the copy.
Allow for the list to manage the destruction of the variable (deallocation of the pointer, finalization if it is present), or let the user handle it. Perhaps the list is being used to collocate and access some data, but if the list goes out of scope, the data is intended to remain.
In general, limit the copying of data (some entries in the list may be very large and it is undesirable to make copies).
Allow the key to be an integer or string (or maybe other variable types as well)

For lack of a better name, I've called the resultant library FLIST (it's on GitHub). It's really just an experiment at this point, but I think it does everything I need. The node data type used to construct the linked list is this:

type :: node
    private
    class(*),allocatable :: key
    class(*),pointer :: value => null()
    logical :: destroy_on_delete = .true.
    type(node),pointer :: next => null()
    type(node),pointer :: previous => null()
    contains
    private
    procedure :: destroy => destroy_node_data
end type node

The data in the node is a CLASS(*),POINTER variable (i.e, a pointer to an unlimited polymorphic variable). This will be associated to the data that is added to the list. Data can be added as a pointer (in which case no copying is performed), or added as a clone (where a new instance of the node data is instantiated and a copy of the input data is made). If the data is added as a pointer, the user can also optionally specify if the data is to be destroyed when the list is destroyed or goes out of scope (or if the item is deleted from the list).

The key is also an unlimited polymorphic variable (in the user-accessible API, keys are limited to integers, character strings, or extensions of an abstract key_class):

type,abstract,public :: key_class
    contains
    procedure(key_equal_func),deferred :: key_equal
    generic :: operator(==) => key_equal
end type key_class

The key types have to be limited, since there has to be a way to check for equality among keys (the abstract key_class has a deferred == operator that must be specified). The Fortran SELECT TYPE construct is used to resolve the polymorphic variables in order to check for equality among keys.

A simple example use case is shown below. Here we have some derived type gravity_model that is potentially very large, and is initialized by reading a data file. The subroutine takes as input a character array of file names to read, loads them, and appends the resultant models to the list_of_models.

subroutine add_some_models(files,list_of_models)

use linked_list_module
use gravity_model_module

implicit none

character(len=:),dimension(:),intent(in) :: files
type(list),intent(inout) :: list_of_models

integer :: i
type(gravity_model),pointer :: g

do i=1,size(files)
    allocate(g)
    call g%initialize(files(i))
    call list_of_models%add_pointer(files(i),g)
    nullify(g)
end do

end subroutine add_some_models

In this example, all the models are allocated in the subroutine, and then added as pointers to the list (the file name is used as the key). When list_of_models goes out of scope, the models will be deallocated (and finalized if gravity_model contains a finalizer). A model can be removed from the list (which will also trigger finalization) using the key, like so:

call list_of_models%remove('blah.dat')

More complex use cases are also possible (see the code for more details). As usual, the license is BSD, so if anybody else finds it useful, let me know.

Algorithms • Modern Fortran Programming • Orbital Mechanics

Apr 05, 2016

Linked Lists

See also