Loading...
Searching...
No Matches
Linked List
Globus Common API

Linked List. More...

## 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_t * | globus_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_t * | globus_list_search (globus_list_t *head, void *datum)
| Search a list for a datum.
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.
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.
globus_list_t * | globus_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_t * | globus_list_cons (void *datum, globus_list_t *rest)
| List constructor.
globus_list_t * | globus_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.

## Detailed Description

Linked List.

## Typedef Documentation

## globus_list_pred_t

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

## globus_list_relation_t

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

## globus_list_t

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

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

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

## globus_list_empty()

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.

## globus_list_first()

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.

## globus_list_free()

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

## globus_list_insert()

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

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.

## globus_list_remove()

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.

## globus_list_replace_first()

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

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

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

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

## globus_list_size()

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

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