Double-Linked Lists

    #include <mplib1/dl_list.h>

    struct Node_struct
    {
    struct Node_struct *ln_Succ;
    struct Node_struct *ln_Pred;
    const  char *ln_Name;
    const  void *ln_Item;
    struct List_struct *ln_List;
    };

    struct List_struct
    {
    struct Node_struct ln_Head;
    struct Node_struct ln_Tail;
    int    ln_Flags;
    };

    typedef struct Node_struct Node_t;
    typedef struct List_struct List_t;

The dl_list routines are a full suite of double-linked list functions.

Instead of the normal rigmarole of having to produce a set of routines for each type of data structure these routines provide a standard list header structure and a node structure which is attached to the list. Nodes have two properties which are used by the programmer, an item pointer and a name pointer.

Initialisation Routines

The List and Node must be initialised before they can be used.

    List_t *Init_List ( List_t *list, int flags );

This function initialises a list structure for subsequent use. The flags parameter should be 0 or LN_IGNORECASE. This affects whether the searches for items by name should be case-independant or not.

    Node_t *Init_Node( Node_t *node,
			const char *name,
			const void *item );

This function initialises a node structure for use in a list. The name parameter should be either a name for search purposes or NULL. The item pointer is normally the pointer to the structure containing the user data and the node.

Add functions

The two main add functions are as follows.

    Node_t *Add_Head( List_t *list, Node_t *node );

    Node_t *Add_Tail( List_t *list, Node_t *node );

These functions add the supplied node to the head and tail of the supplied list respectively.

There are other add functions but they are for more complex situations and would not normally be used. For details click here.

Remove Functions

There are three remove functions.

    void *Remove_Head_Item( List_t *list );
    
    void *Remove_Tail_Item( List_t *list );
    

    Node_t *Remove_Node( Node_t *node1 );

The first two are related to the add functions above, except that they return a pointer to the item as stored in the node structure.

The Remove_Node function is used to remove a given node from a list.

As with the add functions there are some primitives that are not commonly used. For details, click here.

Find Functions

    void *Find_Item_By_Name( List_t *list, const char *name );
    void *Find_Next_Item_By_Name( Node_t *node, const char *name );

Find_Item_By_Name searchs the given list for an item with the supplied name (matching according to the case flag set when initialising the list). If it find it the item pointer is returned, and if not found NULL is returned.

The function does a similar search to that performed by Find_Item_By_Name except that it starts from a given node. This would typically be the node of an item previsouly found using one of the above functions. The search actually commences from the node following the one supplied.

Found items are not removed from the list.

Yet again, there is a a function that is not commonly used. For details, click here.

Walk Functions

    typedef void (* Walk_List_t)( void *, void *);
    typedef int (* Walk_List2_t)( void *, void *);
    typedef int (* Walk_List_Name_t)( void *, void *);
    typedef int (* Walk_List_Node_t)( Node_t *, void *);

    int Walk_List( List_t *l_ptr,
		    Walk_List_t disp,
		    void *param );

    int Walk_List2( List_t *l_ptr,
		    Walk_List2_t disp,
		    void *param );

    int Walk_List_Name( List_t *l_ptr,
			const char *name,
			Walk_List_Name_t disp,
			void *param );

    int Walk_List_By_Node( List_t *l_ptr,
			Walk_List_Node_t disp,
			void *param );

These functions walk the list provided and call the supplied function with a pointer to each suitable item together with the user supplied paramter.

The Walk_List function calls the disp routine for every item in the list.

The Walk_List function calls the disp routine for every item in the list whilst the disp routine returns 0. Should the disp routine return non-zero the traversal of the list finishes and the non-zero value is returned to the caller.

The Walk_List_Name function is similar to the Walk_List routine except that the disp routine is only called for items whose name matches that supplied (given the list's case matching rule).

The Walk_List_By_Node function is similar to the Walk_List routine except that the disp routine is passed the Node pointer of each member rather than the item pointer.

Note In all the above Walk_ routines.

: The Walk_ routines do not remove any items from the list.
: Whilst within the disp function the only possible manipulation of the list being walked which is permitted is to perform Remove_Node for the current item.

Sort Functions

    typedef int (* dl_sort_i_t)( const void *, const void *);

    int dl_sort_i( List_t *sort_list, dl_sort_i_t compar );

    int dl_sort_n( List_t *sort_list );

These functions sort the supplied lists using either a supplied comparison function or by name (taking into account the list's matching rule). The sort algorithm is actually lmsort but adapted for use with these double linked lists.

Miscelleaneous Functions

    int Transfer_Lists( List_t *from_list, List_t *to_list );

This function simply transfers all items on the from_list onto the to_list. It returns the number of items transferred.

    int Any_In_List( List_t *list );

This function returns non-zero if there are any items in the list or 0 if the list is empty.

    void dl_Free_List( List_t *list, int flags );

    void dl_Free_Node( Node_t *node, int flags );

where the flags are a bit-wise or of the following defines

    DL_REMOVE_NODES
    DL_FREE_NODES
    DL_FREE_ITEMS
    DL_FREE_NAMES

The dl_Free_List function provides a mechanism to free up the various elements of items on a list. It is, not surprisingly, implemented as a call to Walk_List with dl_Free_Node as the supplied function.

The dl_Free_Node function takes a pointer to a node and a set of flags. It then performs the following operations

If DL_REMOVE_NODES or DL_FREE_NODES is set the node is removed from the list.
If DL_FREE_NAMES is set any name pointed to by the node is freed and the pointer cleared.
If DL_FREE_ITEMS is set any item pointed to by the node is freed and the pointer cleared.
If DL_FREE_NODES is set the node is freed.

    int dl_Free_List_Contents( List_t *fl_ptr );

This deprecated function walks the given list, removing each Node in turn and calling free() for each item pointer.