The Globus List Data Type

This is a document to specify the globus_list data type API and implementation as included in the globus_common library.

The globus_list data type provides an abstract list representation and operations on such lists. These lists can contain arbitrary data in the form of a void pointer for each datum. It is the user's responsibility to provide and interpret data of the correct type.

The globus_list API implementation assumes volatile storage for the list nodes and is therefore appropriate for use as shared-data in multithreaded programming.

Basic List Manipulation

typedef globus_list_t

A structure representing a node containing a single datum and a reference to additional elements in the list.

globus_list_t * NULL

The special value NULL is used to represent a list with zero elements, also called an empty list.

int
globus_list_empty (
    globus_list_t *    list )

The predicate globus_list_empty returns non-zero iff list==NULL, otherwise returns zero (0).

globus_list_t *
globus_list_cons (
    void *    datum ,
    globus_list_t *    rest )

The constructor globus_list_cons returns a freshly allocated list node initialized to contain datum and to refer to rest as the remainder of the new list, or returns NULL if a new node could not be allocated.

All list nodes constructed by globus_list_cons should eventually be destroyed using globus_list_remove or globus_list_free.

int
globus_list_insert (
    globus_list_t * volatile *    list_ref ,
    void *    datum )

The constructor globus_list_insert mutates the list reference in place to contain a newly allocated list node holding datum and using the original value named by the list reference as the remainder of the list. This routine returns zero (0) on success, or non-zero on failure.

All list nodes constructed by globus_list_cons should eventually be destroyed using globus_list_remove or globus_list_free.

globus_list_t *
globus_list_copy (
    globus_list_t *    source )

The globus_list_copy constructor creates a newly allocated list containing the same data as the source list.

All list nodes constructed by globus_list_copy should eventually be destroyed using globus_list_remove or globus_list_free .

void *
globus_list_first (
    globus_list_t *    list )

The accessor globus_list_first returns the datum at the head of the list; this datum is the one provided to the globus_list_cons call that constructed the head of the list.

It is an error to call this routine on the empty list (NULL). extern void * globus_list_replace_first (globus_list_t * head, void *datum);

void *
globus_list_replace_first (
    globus_list_t *    list ,
    void *    datum )

The mutator globus_list_replace_first returns the datum at the head of the list and modifies the list to contain the provided datum instead.

It is an error to call this routine on the empty list (NULL).

globus_list_t *
globus_list_rest (
    globus_list_t *    list )

The accessor globus_list_rest returns the remainder of the list elements, containing all data except the datum returned by globus_list_first (list) .

It is an error to call this routine on the empty list (NULL).

int
globus_list_size (
    globus_list_t *    list )

The routine globus_list_size computes and returns the total number of data contained in the list, and an empty list has zero elements.

It is an error to call this routine on the empty list (NULL).

void *
globus_list_remove (
    globus_list_t * volatile *    list_ref ,
    globus_list_t *    entry )

The globus_list_remove routine searches a list provided by reference, mutating the list in place to remove the specified entry and deallocate its resources. If the entry is found, it is removed and its datum is returned; if the entry is not found no effects are done and NULL is returned.

void
globus_list_free (
    globus_list_t *    list )

The globus_list_free routine deallocates an entire list, abandoning its data.

List Algorithms

globus_list_t *
globus_list_search (
    globus_list_t *    list ,
    void *    datum )

The routine globus_list_search traverses the elements in list until a sub-list is found with datum as the first element. If such a sub-list is found, it is returned, otherwise the empty list (NULL) is returned.

typedef int
(* globus_list_pred_t) (
    void *    datum ,
    void *    args )

An anonymous predicate that evaluates a datum as true or false in the context of user-provided args. These predicates are used for example in general searches with globus_list_search_pred , and the args field is used to implement in C something approximating closures in a functional language by encapsulating instance-specific search criteria.

These predicates return non-zero for truth and zero (0) for falsity so they can be used in C conditional expressions.

globus_list_t *
globus_list_search_pred (
    globus_list_t *    list ,
    globus_list_pred_t    predicate ,
    void *    pred_args )

The routine globus_list_search_pred traverses the elements in list until a sub-list is found with datum as the first element such that predicate (datum, pred_args) evaluates true. If such a sub-list is found, it is returned, otherwise the empty list (NULL) is returned.

It is an error to provide a predicate value of NULL.

typedef int
(* globus_list_relation_t) (
    void *    low_datum ,
    void *    high_datum ,
    void *    relation_args )

An anonymous predicate that defines a partial ordering of data. Such ordering predicates evaluate true if low_datum is ``less than'' (or ``comes before'') high_datum in the ordering, and false otherwise. These predicates are used for example in general sorts with globus_list_sort , and the relation_args field is used to implement in C something approximating closures in a functional language by encapsulating instance-specific ordering criteria.

These predicates return non-zero for truth and zero (0) for falsity so they can be used in C conditional expressions.

globus_list_t *
globus_list_min (
    globus_list_t *    list ,
    globus_list_relation_t    relation ,
    void *    relation_args )

The globus_list_min routine traverses the list and returns the first minimum valued datum, as determined by the order defined by the given relation.

It is an error to provide a relation value of NULL.

globus_list_t *
globus_list_sort (
    globus_list_t *    list ,
    globus_list_relation_t    relation ,
    void *    relation_args )

The globus_list_sort routine returns a new copy of the list where the elements have been reordered to satisfy the provided relation, or returns NULL if the list cannot be created. This sort is currently implemented as a fast merge sort.

It is an error to provide a relation value of NULL.