Linked Lists

linked-listSo, 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.

See also

  1. T. Dunn, fortran-linked-list [GitHub]
  2. T. Degawa, LinkedList [GitHub]
  3. libAtoms/QUIP [GitHub]
  4. N. R. Papior, fdict [GitHub]
  5. C. MacMackin, FIAT [GitHub]
  6. J. R. Blevins, A Generic Linked List Implementation in Fortran 95, ACM Fortran Forum 28(3), 2–7, 2009.
Tagged with:
5 comments on “Linked Lists
  1. Stefano says:

    Great Jacob!

    I think that FIAT (one of the latest Chris’ “diamonds”) is very promising… however you list is very nice!

    See you soon.

  2. Chris MacMackin says:

    I just wanted to explain why I chose to require you to extend an abstract derived type to contain non-intrinsic data-types. If you are only looking to return an unlimited polymorphic pointer then such an approach is unnecessary. However, I wanted to automate the whole process of testing that the return type is what is expected and to make placing it in an actual variable of that type automatic. To do the latter you need a `select type` construct somewhere and it can either be done by the user every time they access a list item, or once when they extend the abstract container type.

  3. Jacob says:

    Chris, yes indeed yours is a fine approach. FIAT looks awesome, way more powerful and comprehensive than what I was aiming for here.

    You are correct, the choice is to either make the caller use a `select type` or make them extend an abstract container type. I was OK with the former in my case. If I think about it some more, I’ll probably come around to your way.

    • Chris MacMackin says:

      What I will concede as an advantage to your implementation is the fact that it allows pointers to be stored. FIAT’s approach (at present) can only work by actually copying the data. This, of course, means that you can end up using far more memory (as you point out) and also that you can’t edit a list member ‘in place’. You would have to retrieve it from the list, modify the retrieved copy, and then place a copy of that back into the list. I may put some thought into how FIAT’s approach could work with pointers. I’ve avoided them as much as possible so far just because I wanted to minimize the chance of memory leaks.

  4. Mohammad says:

    Is it possible to get the list items by some ordinal number?

    call list%get(i, item)

Leave a Reply

Your email address will not be published. Required fields are marked *

*