Linked lists

      #include <gandalf/common/linked_list.h>

Gandalf linked lists are stored in Gan_List structures. The underlying structure is a doubly-linked list, so Gandalf lists can be traversed both forwards and backwards. A new empty list can be created using

      Gan_List List;

      gan_list_form(&List);

Note that to detect errors the return value of gan_list_form() should be compared with NULL, invoking the Gandalf error package (see Sections 2.10 and 2.9) and returning an error condition if NULL is returned. Here and elsewhere we omit these tests for the sake of clarity, but many examples of this testing can be found in the Gandalf source.

To insert a new list node at the start of the list, use

      gan_list_insert_first ( &List, ptr );

where ptr is the data item (pointer) to be stored. By repetitively called this function, a list can be built up, with the last item added as the first node in the list. A Gandalf list stores pointers in an ordered way, while still transparently allowing pseudo-random access to the list nodes. As well as the stored data, the list maintains a state variable indicating a position within the list, from 0 to $N-1$ for a list of $N$ nodes. The normal way to traverse a list is to use the following sequence:

      int iCount;
      Gan_Matrix *pMatrix;

      gan_list_goto_head ( &List );
      for ( iCount = gan_list_get_size(&List)-1; iCount >= 0; iCount-- )
      {
         pMatrix = gan_list_get_next ( &List, Gan_Matrix );
         ... [ do something with pMatrix ] ...
      }

gan_list_goto_head() sets the position state variable to -1, i.e. the position just before the start of the list. gan_list_get_size() returns the number of nodes in a list. So the above loop runs through each node of the list, calling gan_list_get_next() to provide each data item in turn, in this case matrix structure pointers. gan_list_get_next() increments the position state variable by one each time it is called, so on the first call in the above loop, the position is increment from -1 to 0, and the node at position 0 returned.

To free the list use

      gan_list_free ( &List, NULL );

which frees the list nodes but not the data they point to. If you wanted to free the data as well, for the above list you would use

      gan_list_free ( &List, (Gan_FreeFunc) gan_mat_free );

which calls gan_mat_free() on each matrix in the list.

Note that pointers to lists may be used instead of directly using the structures. To create a list using pointers use

      Gan_List *pList;

      pList = gan_list_new();

and at the end call

      gan_list_free ( pList, NULL );

In this and other examples Gandalf keeps track of which parts of a structure were dynamically allocated, and only frees those which were.

Other ways to build and access linked lists are provided in the reference documentation.