Linked List
[Globus Common API]

Data Structures

struct  globus_list
 List data type. More...

Typedefs

typedef struct globus_list globus_list_t
 List data type.
typedef int(* globus_list_pred_t )(void *datum, void *arg)
 List search predicate.
typedef int(* globus_list_relation_t )(void *low_datum, void *high_datum, void *relation_arg)
 Relation predicate.

Functions

void * globus_list_first (globus_list_t *head)
 Retrieve head datum.
globus_list_tglobus_list_rest (globus_list_t *head)
 Get the remainder of the list.
int globus_list_empty (globus_list_t *head)
 List empty predicate.
int globus_list_size (globus_list_t *head)
 Get the number of elements in a list.
void * globus_list_replace_first (globus_list_t *head, void *datum)
 Replace first datum.
globus_list_tglobus_list_search (globus_list_t *head, void *datum)
 Search a list for a datum.
globus_list_tglobus_list_search_pred (globus_list_t *head, globus_list_pred_t predicate, void *pred_args)
 Search a list with a predicate.
globus_list_tglobus_list_min (globus_list_t *head, globus_list_relation_t relation, void *relation_args)
 Find the minimum value of a list.
globus_list_tglobus_list_sort (globus_list_t *head, globus_list_relation_t relation, void *relation_args)
 Sort a list.
int globus_list_insert (globus_list_t *volatile *headp, void *datum)
 Insert an item in a list.
globus_list_tglobus_list_cons (void *datum, globus_list_t *rest)
 List constructor.
globus_list_tglobus_list_copy (globus_list_t *head)
 Copy constructor.
void * globus_list_remove (globus_list_t *volatile *headp, globus_list_t *entry)
 Remove a datum from a list.
void globus_list_free (globus_list_t *head)
 Free a list.

Typedef Documentation

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

List search predicate.

An anonymous predicate that evaluates a datum as true or false in the context of user-provided arg. These predicates are used for example in general searches with globus_list_search_pred(), and the arg 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 for falsity so they can be used in C conditional expressions.

Parameters:
datum Datum of the list item to compute the predicate against.
arg Parameter supplied to globus_list_search_pred()
typedef int(* globus_list_relation_t)(void *low_datum, void *high_datum, void *relation_arg)

Relation predicate.

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_arg 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 for falsity so they can be used in C conditional expressions.

Parameters:
low_datum Datum to compare
high_datum Datum to compare
relation_arg Parameter supplied to globus_list_sort()
typedef struct globus_list globus_list_t

List data type.

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

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


Function Documentation

globus_list_t* globus_list_cons ( void *  datum,
globus_list_t rest 
)

List constructor.

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().

Parameters:
datum Item to add to the list
rest List to set as the remainder of the new list.
Returns:
List node.
globus_list_t* globus_list_copy ( globus_list_t head  ) 

Copy constructor.

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().

Parameters:
head List to copy
Returns:
Copy of the list
int globus_list_empty ( globus_list_t head  ) 

List empty predicate.

The predicate globus_list_empty returns non-zero if list==NULL, otherwise returns 0.

void* globus_list_first ( globus_list_t head  ) 

Retrieve head datum.

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.

Parameters:
head List to retrieve from
Returns:
The list datum.
void globus_list_free ( globus_list_t head  ) 

Free a list.

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

Parameters:
head Head of the list to free
int globus_list_insert ( globus_list_t *volatile *  headp,
void *  datum 
)

Insert an item in a list.

The constructor globus_list_insert() mutates the list reference headp 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.

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

Parameters:
headp List reference to insert into.
datum Datum to add to the list.
Returns:
This routine returns zero on success, or non-zero on failure.
globus_list_t* globus_list_min ( globus_list_t head,
globus_list_relation_t  relation,
void *  relation_args 
)

Find the minimum value of a list.

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.

Parameters:
head List to search
relation Relation predicate
relation_args Argument passed to the relation
Returns:
This routine returns a list node whose first node is the minimum of the values in the original list to search, or NULL of the list was empty.
void* globus_list_remove ( globus_list_t *volatile *  headp,
globus_list_t entry 
)

Remove a datum from a list.

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.

Parameters:
headp Reference to the head of the list
entry List entry to remove from the list
Returns:
Either the datum which is removed from the list, or NULL if it isn't present.
void* globus_list_replace_first ( globus_list_t head,
void *  datum 
)

Replace first 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).

Parameters:
head List to modify
datum New datum
Returns:
The old value of the first datum in the list.
globus_list_t* globus_list_rest ( globus_list_t head  ) 

Get the remainder of the list.

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

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

Parameters:
head Head of the list
Returns:
Remainder of the list
globus_list_t* globus_list_search ( globus_list_t head,
void *  datum 
)

Search a list for a 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 is returned.

Parameters:
head Head of the list to search
datum Datum to search for in the list
Returns:
The first list node found which contains the datum, or NULL if not found.
globus_list_t* globus_list_search_pred ( globus_list_t head,
globus_list_pred_t  predicate,
void *  pred_args 
)

Search a list with a predicate.

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 is returned.

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

Parameters:
head List to search
predicate Predicate function
pred_args Parameter to pass to the predicate function
int globus_list_size ( globus_list_t head  ) 

Get the number of elements in a list.

The routine globus_list_size() computes and returns the total number of data contained in the list. An empty list has zero elements.

Parameters:
head Head of the list
Returns:
Number of data items in the list
globus_list_t* globus_list_sort ( globus_list_t head,
globus_list_relation_t  relation,
void *  relation_args 
)

Sort a list.

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.

Parameters:
head List to sort
relation Predicate relation to use for the sort
relation_args Parameter to relation
Returns:
This routine returns a new list whose data items are the same as the old list. The list must be freed with globus_list_free().
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Defines

Generated on 6 May 2016 for globus_common by  doxygen 1.6.1