The LevAWC Project
 All Data Structures Files Functions Variables Typedefs Enumerations Macros Pages
Macros | Typedefs | Functions
dlist.h File Reference
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
#include <assert.h>

Go to the source code of this file.

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

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.