Linked List. More...

Data Structures
struct	globus_list
	List data type. More...

Typedefs
typedef struct globus_list	globus_list_t
	List data type. More...

typedef int(*	globus_list_pred_t )(void datum, void arg)
	List search predicate. More...

typedef int(*	globus_list_relation_t )(void low_datum, void high_datum, void *relation_arg)
	Relation predicate. More...

Functions
void *	globus_list_first (globus_list_t *head)
	Retrieve head datum. More...

globus_list_t *	globus_list_rest (globus_list_t *head)
	Get the remainder of the list. More...

int	globus_list_empty (globus_list_t *head)
	List empty predicate. More...

int	globus_list_size (globus_list_t *head)
	Get the number of elements in a list. More...

void *	globus_list_replace_first (globus_list_t head, void datum)
	Replace first datum. More...

globus_list_t *	globus_list_search (globus_list_t head, void datum)
	Search a list for a datum. More...

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. More...

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. More...

globus_list_t *	globus_list_sort (globus_list_t head, globus_list_relation_t relation, void relation_args)
	Sort a list. More...

int	globus_list_insert (globus_list_t volatile headp, void *datum)
	Insert an item in a list. More...

globus_list_t *	globus_list_cons (void datum, globus_list_t rest)
	List constructor. More...

globus_list_t *	globus_list_copy (globus_list_t *head)
	Copy constructor. More...

void *	globus_list_remove (globus_list_t volatile headp, globus_list_t *entry)
	Remove a datum from a list. More...

void	globus_list_free (globus_list_t *head)
	Free a list. More...

Detailed Description

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

Data Structures

Typedefs

Functions

Detailed Description

Typedef Documentation

Function Documentation