#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
#include <assert.h>

Macros
#define	DLIST_FWD 1

#define	DLIST_BWD -1

Typedefs
typedef struct DList_ *	Dlist

typedef struct DListElmt_ *	DlistNode

Functions
Dlist	DLISTinit (void(destroy)(void data))

void	DLISTdestroy (Dlist list)

int	DLISTinsnext (Dlist list, DlistNode node, const void *data)

int	DLISTinsprev (Dlist list, DlistNode node, const void *data)

int	DLISTremove (Dlist list, DlistNode node, void **data)

int	DLISTsize (Dlist list)

DlistNode	DLISThead (Dlist list)

DlistNode	DLISTtail (Dlist list)

int	DLISTishead (Dlist list, DlistNode node)

int	DLISTistail (Dlist list, DlistNode node)

void *	DLISTdata (DlistNode node)

DlistNode	DLISTnext (DlistNode node)

DlistNode	DLISTprev (DlistNode node)

DlistNode	DLISTfindnode (Dlist list, const void *data)

void	DLISTsetmatch (Dlist list, int(match)(const void key1, const void *key2))

int	DLISTfind_remove (Dlist list, void **data)

void	DLISTsort (Dlist list, int(cmp)(const void key1, const void *key2))

void	DLISTtraverse (Dlist list, void(callback)(const void data), int direction)

Macro Definition Documentation

#define DLIST_BWD -1

Macro for backward traversal of the list

Definition at line 50 of file dlist.h.

#define DLIST_FWD 1

Macro for forward traversal of the list

Definition at line 45 of file dlist.h.

Typedef Documentation

typedef struct DList_* Dlist

Use a typedef - to hide the interior of DList_ - in the implementation file. This is how data hiding can be done in C.

Definition at line 57 of file dlist.h.

typedef struct DListElmt_* DlistNode

Another typedef - for hiding the interior of DListElmt_ - in the implementation file.

Definition at line 64 of file dlist.h.

Function Documentation

void* DLISTdata ( DlistNode node )

Get a reference to data stored in a node.

Parameters

[in] node - a reference to the current node.

Returns: Generic reference to data - stored in parameter node.

Definition at line 224 of file dlist.c.

void DLISTdestroy ( Dlist list )

Destroy the list.

The list is destroyed - that is, all the memory occupied by the nodes is deallocated. The user-defined callback function destroy, given as an argument to DLISTinit(), is responsible for freeing dynamically allocated node data, when this function is called. When all nodes and data have been deallocated - the list header is deallocated, too.

Parameters

[in] list - a reference to current list.

Returns: Nothing.

See Also: DLISTinit()

Definition at line 66 of file dlist.c.

int DLISTfind_remove	(	Dlist	list,
		void **	data
	)

Search - and remove a node - by using an in/out parameter.

When called, the 2nd parameter of this function, data, should reference a pointer, that points to the search key data. Moreover, a user-defined callback function responsible for doing the matching of node data - and data referenced by parameter data - must exist for this function to work - otherwise -2 will be returned - always. This user-supplied match-callback is set into the list with a call to another function, DLISTsetmatch().

After the call - an (external) pointer referenced by parameter data, has been redirected to point to data of the removed node - if the call was succesful. The caller is responsible for the future of this memory - deallocating it, if needed, for example.

Parameters

[in]	list	- reference to current list.
[in,out]	data	- reference to an external pointer, that initially shall point to the search key data - when this function is called. After the call, this referenced (external) pointer, has been redirected - to point to node data of the removed node - if the call was successful. The caller is responsible for the future of this memory - deallocating it, for example.

Returns: Value 0 – if the call was OK - that is, node found and removed.
Value 1 – node not found.
Value -2 – if match-callback is not set.
Value -1 – otherwise (implies fatal error).

See Also: DLISTsetmatch()

Definition at line 261 of file dlist.c.

DlistNode DLISTfindnode	(	Dlist	list,
		const void *	data
	)

Find the first node - with node data matching data referenced by parameter data.

Search the list sequentially for a node, whose data matches the data referenced by parameter data. A reference to the node with the first match will be returned - NULL otherwise. A user-defined callback function, responsible for doing the matching of node data - with data referenced by parameter data - must exist for this function to work - otherwise NULL will be returned - always. This user-supplied match-callback is set into the list with another function - DLISTsetmatch().

Parameters

[in]	list	- reference to the current list.
[in]	data	- reference to the search key data.

Returns: Reference to the first node with a match to data referenced by parameter data - if found - NULL otherwise

See Also: DLISTsetmatch()

Definition at line 239 of file dlist.c.

DlistNode DLISThead ( Dlist list )

Get a reference to the head node of the list.

Parameters

[in] list - a reference to the current list.

Returns: A reference to the first node in the list.

Definition at line 204 of file dlist.c.

Dlist DLISTinit ( void(*)(void *data) destroy )

Initiate the list.

Parameters

[in] destroy - A reference to a user-made function, reponsible for freeing node data, when the list is deleted. If destroy is NULL - then node data will be left untouched when the list is destroyed.

Returns: A reference - to a new, empty list - if dynamic memory allocation for the ADT was successful - or NULL otherwise. Take really good care of this return value, since it will be needed as a parameter in subsequent calls - to the majority of other list handling functions in this function interface - i.e. a sort of "handle" to the list.

See Also: DLISTdestroy()

Definition at line 50 of file dlist.c.

int DLISTinsnext	(	Dlist	list,
		DlistNode	node,
		const void *	data
	)

Insert a new node - after parameter node.

This function inserts an new node, with a reference to node data given by parameter data - after the node referenced by parameter node - into list. If list is empty - the function should be called with node set to NULL - to avoid confusion.

Parameters

[in]	list	- reference to current list
[in]	node	- the node after which the new node is to be inserted. Should be set to NULL - if the list is empty.
[in]	data	- reference to data to be stored in the new node, that is inserted into the list.

Returns: Value 0 - if everything went OK - or value -1 otherwise.

Definition at line 81 of file dlist.c.

int DLISTinsprev	(	Dlist	list,
		DlistNode	node,
		const void *	data
	)

Insert a new node - before parameter node.

This function inserts an new node, with a reference to node data given by parameter data - before the node referenced by parameter node - into list. If list is empty - the function should be called with node set to NULL - to avoid confusion.

Parameters

[in]	list	- reference to current list
[in]	node	- the node before which the new node is to be inserted. Should be set to NULL - if the list is empty.
[in]	data	- reference to data to be stored in the new node, that is inserted into the list.

Returns: Value 0 - if everything went OK - or value -1 otherwise.

Definition at line 121 of file dlist.c.

int DLISTishead	(	Dlist	list,
		DlistNode	node
	)

Determine if a certain node is the head node of the list - or not.

Parameters

[in]	list	- a reference to the current list.
[in]	node	- a reference to the node to be tested.

Returns: Value 1 - if node indeed is the first node of the list - or 0 otherwise.

Definition at line 214 of file dlist.c.

int DLISTistail	(	Dlist	list,
		DlistNode	node
	)

Determine if a certain node is the tail node of the list - or not.

Parameters

[in]	list	- a reference to the current list.
[in]	node	- a reference to the node to be tested.

Returns: Value 1 - if node indeed is the last node of the list - or 0 otherwise.

Definition at line 219 of file dlist.c.

DlistNode DLISTnext ( DlistNode node )

Get a reference to the next node in the list.

Parameters

[in] node - a reference to current node.

Returns: A reference to the next node - following parameter node - in the list.

Definition at line 229 of file dlist.c.

DlistNode DLISTprev ( DlistNode node )

Get a reference to the previous node in the list.

Parameters

[in] node - a reference to current node.

Returns: A reference to the previous node - directly prior to parameter node - in the list.

Definition at line 234 of file dlist.c.

int DLISTremove	(	Dlist	list,
		DlistNode	node,
		void **	data
	)

Remove the node referenced by parameter node.

After the call - an (external) pointer referenced by parameter data, has been redirected to point to data of the removed node - if the call was succesful. The caller is responsible for the future of this memory - deallocating it, if needed, for example.

Parameters

[in]	list	- reference to current list.
[in]	node	- the node to be removed.
[out]	data	- reference to a pointer, that will point to data of the removed node - after the call, if successful.

Returns: Value 0 - if the call was OK - or value -1 otherwise.

Definition at line 161 of file dlist.c.

void DLISTsetmatch	(	Dlist	list,
		int()(const void key1, const void *key2)	match
	)

Set a valid match callback function for sequentially searching the list

Parameters

[in]	list	- reference to current list.
[in]	match	- a reference to a user-defined function that receives references to node data - and search key data - via its parameters key1 and key2 - and thereby can make the actual matching. This match-callback shall return 1 - in case of a hit - or 0 otherwise.

Returns: Nothing.

Definition at line 256 of file dlist.c.

int DLISTsize ( Dlist list )

Get the list size.

Parameters

[in] list - a reference to the current list.

Returns: The size, that is, the number of nodes in the list.

Definition at line 199 of file dlist.c.

void DLISTsort	(	Dlist	list,
		int()(const void key1, const void *key2)	cmp
	)

Sort a list according to the Selection Sort Algorithm - with complexity Θ(n²)).

Parameters

[in]	list	- reference to current list.
[in]	cmp	- reference to a user-defined callback function responsible for comparing node data. This callback function should return a value of -1 if data referenced by key1 is less than data referenced by key2 - or 0 if they are equal - or 1 otherwise. This will produce an ascending sort order. If a descending order is what you want - just swap the return values -1 and 1 for the comparisons made above.

Returns: Nothing.

Definition at line 279 of file dlist.c.

DlistNode DLISTtail ( Dlist list )

Get a reference to the tail node of the list.

Parameters

[in] list - a reference to the current list.

Returns: A reference to the last node in the list.

Definition at line 209 of file dlist.c.

void DLISTtraverse	(	Dlist	list,
		void()(const void data)	callback,
		int	direction
	)

Traverse the list from the beginning or the end - and have a user-defined function called - for each node in the list.

Parameters

[in]	list	- reference to current list.
[in]	callback	- reference to user-defined callback function, that gets read access to node data via its parameter data - to do whatever is relevant. Print data, for example.
[in]	direction	- direction of traversal. Set to DLIST_FWD for forward traversal - and DLIST_BWD for traversing backwards.

Returns: Nothing.

Definition at line 311 of file dlist.c.

Macros

Typedefs

Functions

Macro Definition Documentation

Typedef Documentation

Function Documentation