slist.h File Reference

Singly-linked list. More...


Data Structures

struct  _SListIterator
 Definition of a SListIterator. More...

Defines

#define SLIST_NULL   ((void *) 0)
 A null SListValue.

Typedefs

typedef struct _SListEntry SListEntry
 Represents an entry in a singly-linked list.
typedef struct _SListIterator SListIterator
 Structure used to iterate over a list.
typedef void * SListValue
 Value stored in a list.
typedef int(* SListCompareFunc )(SListValue value1, SListValue value2)
 Callback function used to compare values in a list when sorting.
typedef int(* SListEqualFunc )(SListValue value1, SListValue value2)
 Callback function used to determine of two values in a list are equal.

Functions

void slist_free (SListEntry *list)
 Free an entire list.
SListEntryslist_prepend (SListEntry **list, SListValue data)
 Prepend a value to the start of a list.
SListEntryslist_append (SListEntry **list, SListValue data)
 Append a value to the end of a list.
SListEntryslist_next (SListEntry *listentry)
 Retrieve the next entry in a list.
SListValue slist_data (SListEntry *listentry)
 Retrieve the value stored at a list entry.
SListEntryslist_nth_entry (SListEntry *list, int n)
 Retrieve the entry at a specified index in a list.
SListValue slist_nth_data (SListEntry *list, int n)
 Retrieve the value stored at a specified index in the list.
int slist_length (SListEntry *list)
 Find the length of a list.
SListValueslist_to_array (SListEntry *list)
 Create a C array containing the contents of a list.
int slist_remove_entry (SListEntry **list, SListEntry *entry)
 Remove an entry from a list.
int slist_remove_data (SListEntry **list, SListEqualFunc callback, SListValue data)
 Remove all occurrences of a particular value from a list.
void slist_sort (SListEntry **list, SListCompareFunc compare_func)
 Sort a list.
SListEntryslist_find_data (SListEntry *list, SListEqualFunc callback, SListValue data)
 Find the entry for a particular value in a list.
void slist_iterate (SListEntry **list, SListIterator *iter)
 Initialise a SListIterator structure to iterate over a list.
int slist_iter_has_more (SListIterator *iterator)
 Determine if there are more values in the list to iterate over.
SListValue slist_iter_next (SListIterator *iterator)
 Using a list iterator, retrieve the next value from the list.
void slist_iter_remove (SListIterator *iterator)
 Delete the current entry in the list (the value last returned from slist_iter_next).


Detailed Description

Singly-linked list.

A singly-linked list stores a collection of values. Each entry in the list (represented by a pointer to a SListEntry structure) contains a link to the next entry. It is only possible to iterate over entries in a singly linked list in one direction.

To create a new singly-linked list, create a variable which is a pointer to a SListEntry, and initialise it to NULL.

To destroy a singly linked list, use slist_free.

To add a new value at the start of a list, use slist_prepend. To add a new value at the end of a list, use slist_append.

To find the length of a list, use slist_length.

To access a value in a list by its index in the list, use slist_nth_data.

To search a list for a value, use slist_find_data.

To sort a list into an order, use slist_sort.

To find a particular entry in a list by its index, use slist_nth_entry.

To iterate over each value in a list, use slist_iterate to initialise a SListIterator structure, with slist_iter_next and slist_iter_has_more to retrieve each value in turn. slist_iter_remove can be used to efficiently remove the current entry from the list.

Given a particular entry in a list (SListEntry):


Typedef Documentation

typedef int(* SListCompareFunc)(SListValue value1, SListValue value2)

Callback function used to compare values in a list when sorting.

Returns:
A negative value if value1 should be sorted before value2, a positive value if value1 should be sorted after value2, zero if value1 and value2 are equal.

typedef struct _SListEntry SListEntry

Represents an entry in a singly-linked list.

The empty list is represented by a NULL pointer. To initialise a new singly linked list, simply create a variable of this type containing a pointer to NULL.

typedef int(* SListEqualFunc)(SListValue value1, SListValue value2)

Callback function used to determine of two values in a list are equal.

Returns:
A non-zero value if value1 and value2 are equal, zero if they are not equal.


Function Documentation

SListEntry* slist_append ( SListEntry **  list,
SListValue  data 
)

Append a value to the end of a list.

Parameters:
list Pointer to the list to append to.
data The value to append.
Returns:
The new entry in the list, or NULL if it was not possible to allocate a new entry.

SListValue slist_data ( SListEntry listentry  ) 

Retrieve the value stored at a list entry.

Parameters:
listentry Pointer to the list entry.
Returns:
The value at the list entry.

SListEntry* slist_find_data ( SListEntry list,
SListEqualFunc  callback,
SListValue  data 
)

Find the entry for a particular value in a list.

Parameters:
list The list to search.
callback Callback function to be invoked to determine if values in the list are equal to the value to be searched for.
data The value to search for.
Returns:
The list entry of the value being searched for, or NULL if not found.

void slist_free ( SListEntry list  ) 

Free an entire list.

Parameters:
list The list to free.

int slist_iter_has_more ( SListIterator iterator  ) 

Determine if there are more values in the list to iterate over.

Parameters:
iterator The list iterator.
Returns:
Zero if there are no more values in the list to iterate over, non-zero if there are more values to read.

SListValue slist_iter_next ( SListIterator iterator  ) 

Using a list iterator, retrieve the next value from the list.

Parameters:
iterator The list iterator.
Returns:
The next value from the list, or SLIST_NULL if there are no more values in the list.

void slist_iter_remove ( SListIterator iterator  ) 

Delete the current entry in the list (the value last returned from slist_iter_next).

Parameters:
iterator The list iterator.

void slist_iterate ( SListEntry **  list,
SListIterator iter 
)

Initialise a SListIterator structure to iterate over a list.

Parameters:
list Pointer to the list to iterate over.
iter Pointer to a SListIterator structure to initialise.

int slist_length ( SListEntry list  ) 

Find the length of a list.

Parameters:
list The list.
Returns:
The number of entries in the list.

SListEntry* slist_next ( SListEntry listentry  ) 

Retrieve the next entry in a list.

Parameters:
listentry Pointer to the list entry.
Returns:
The next entry in the list.

SListValue slist_nth_data ( SListEntry list,
int  n 
)

Retrieve the value stored at a specified index in the list.

Parameters:
list The list.
n The index into the list.
Returns:
The value stored at the specified index, or SLIST_NULL if unsuccessful.

SListEntry* slist_nth_entry ( SListEntry list,
int  n 
)

Retrieve the entry at a specified index in a list.

Parameters:
list The list.
n The index into the list .
Returns:
The entry at the specified index, or NULL if out of range.

SListEntry* slist_prepend ( SListEntry **  list,
SListValue  data 
)

Prepend a value to the start of a list.

Parameters:
list Pointer to the list to prepend to.
data The value to prepend.
Returns:
The new entry in the list, or NULL if it was not possible to allocate a new entry.

int slist_remove_data ( SListEntry **  list,
SListEqualFunc  callback,
SListValue  data 
)

Remove all occurrences of a particular value from a list.

Parameters:
list Pointer to the list.
callback Callback function to invoke to compare values in the list with the value to remove.
data The value to remove from the list.
Returns:
The number of entries removed from the list.

int slist_remove_entry ( SListEntry **  list,
SListEntry entry 
)

Remove an entry from a list.

Parameters:
list Pointer to the list.
entry The list entry to remove.
Returns:
If the entry is not found in the list, returns zero, else returns non-zero.

void slist_sort ( SListEntry **  list,
SListCompareFunc  compare_func 
)

Sort a list.

Parameters:
list Pointer to the list to sort.
compare_func Function used to compare values in the list.

SListValue* slist_to_array ( SListEntry list  ) 

Create a C array containing the contents of a list.

Parameters:
list The list.
Returns:
A newly-allocated C array containing all values in the list, or NULL if it was not possible to allocate the memory for the array. The length of the array is equal to the length of the list (see slist_length).


Generated on Sun Sep 14 03:08:02 2008 for C Algorithms by  doxygen 1.5.5