A short overview of the dbll library contained in jlib.lib - created by John Findlay
library version 1.00
Current list and bookmarks for library functions
Linked lists are implemented using an object of TYPE DBLL to hold pointers to other objects of the same type. Each object is called a node. This implementation is not a circular linked list.
The classic 'double linked list' object uses a pointer to the next object, a pointer to the previous object and a place holder for the data. The object Type would be something like the following.
As each node is allocated the the data member receives the value passed by the callee and the members for next and prev are also filled in so that each node is connected to the next and previous nodes. The very first node (we will call it the root node, sometimes called the sentinel) does not hold data; the root node's prev pointer is NULL marking the beginning of the list and the next member points to the first node that will hold data. The last node in the list points to its previous node and its next pointer is NULL marking the end of the list.
This implementation of a double linked list also uses one other member within the object, 'index', this allows for some embellishments to the classic implementation. When linked lists were first invented RAM was generally in short supply so the idea was to have an object that would use the minimum memory space. Today, the P.C. running Windows generally has plenty of memory so this extra object member should not be a problem. Also, the minimum amount one can allocate is 16 bytes, which is the size of the DBLL Type so nothing would be gained by allocating only 12 bytes. The root node has an index of zero, the first data node has an index of '1', the next '2', etc.
Each item is separately allocated and de-allocated so the double linked list acts like an open-ended store where nodes can be deleted or added at will whilst still maintaining links to the previous and next nodes.
Care must be taken when accessing the nodes because after some operations your node pointer can point to NULL when you have traversed to either end of the list for example. See the example listing (testdbll.c) for details.
The member named 'data' is a generic pointer (void*) which allows the use of any other pointer type. One can convert any pointer to and from a void pointer without casting. If one needs to store integers one can cast the data to (void*).
Examples:
Integer
Pointer
double db = 9.90f;
double * pdb = &db;
node = dbll_append(node, pdb);
Traversing the list with functions like dbll_count(), dbll_findindex() and dbll_findnode() is quite fast. On my machine traversing 500,000 nodes takes 95ms. When passing a node to DBLL library functions one can use any valid node, this is for convenience but certain functions will be faster when passing the root node - see the following explanations for details.
syntax:
dbll_append adds a new node to the end of the double linked list. This method of adding nodes carries the least overhead.
Example:
Use the returned node to sequentially add nodes to the list:
for (int i =0;
i<5; i++){
if (NULL == (node = dbll_append( node, data
))){
return 0; // error
}
}
The variable 'node' (of type pointer to DBLL) will always point to the last appended node in the above example.
Return values:
The return if successful is a pointer to a new node, if failed it returns NULL. The failure could only be no free memory.
syntax:
dbll_count returns the total number of data nodes currently in the double linked list. If the passed variable DBLL is the root node this operation will be faster.
Return values:
Total number of data nodes.
syntax:
dbll_delete_all will delete all nodes of a list including the root node. If the passed variable DBLL is the root node this operation will be faster.
void dbll_delete_index( DBLL node, int index ); // delete one node
void dbll_delete_data( DBLL node, void * data ); // delete one node
Return values:
No return value.
syntax:
dbll_delete_data will delete the node which has the specified data. If more than one node has the same data only the first will be delted. If the passed variable DBLL is the root node this operation will be faster.
Return values:
No return value.
syntax:
dbll_delete_index will delete the node with the specified index.
Return values:
No return value.
syntax:
Function dbll_delete_node deletes a particular node from the list and frees the memory associated with that node. The index's are re-sequenced after this function has been called.
Return Values:
No return value.
syntax:
dbll_findindex searches through the list for the first match to 'data'. If a match is found the function returns the index of that node. The passed variable DBLL can be any node but it is advisable to pass the root node.
Return Values:
If found the index of the node that contains the value data. If not found zero is returned.
syntax:
dbll_findnode searches through the list for the first match to 'data'. If a match is found the function returns the node. If the passed variable DBLL is the root node this operation will be faster.
Return Values:
If found the node that contains the value data, if not found NULL is returned.
syntax:
dbll_getdata retrieves the data associated with a particular node.
Return Values:
The data value contained in the node.
syntax:
dbll_getfirst returns the first node in the list that contains data. If the passed variable DBLL is the root node this operation will be faster.
Return Values:
The first data node. If there are no data nodes it will return NULL.
syntax:
dbll_getindex returns the index of a particular node. The root node has an index of zero '0'. The first node has an index of one '1', all other nodes are sequentially numbered.
Return Values:
The index of the node.
syntax:
dbll_getlast returns the last node in the double linked list. This function walks through the list from the supplied node until the last node is found. If the root node is passed and no nodes have been added to the list the function returns the root node.
Return Values:
The last node in the list.
syntax:
dbll_getnext returns the next node in the list after passed node 'node'.
Return Values:
The next node in the list. If the root node is passed and no nodes have been added after the root node NULL will be returned. If the passed var 'node' is the last node, NULL will be returned.
syntax:
dbll_getnode returns the node that has a index value, 'index'. Any node can be passed as the function will search in either direction until the index is found.
Return Values:
The node in position index will be returned.
syntax:
dbll_getprev returns the previous node.
Return Values:
Returns the previous node. If 'node' is the root node, NULL is returned, if 'node' is the first data node, the root node will be returned.
syntax:
dbll_insert will insert a new node with value data at index position 'index'.
Return Values:
Returns the new node if successful. If no nodes have been added to the root node dbll_insert will fail and return NULL. If 'index' is greater than the total number of nodes dbll_insert will fail and return NULL.
syntax:
dbll_msort will sort the double linked list using a merge sort algorithm adapted for sorting linked lists. dbll_msort sorts the entries in a list by repeatedly calling the user-defined comparison function pointed to by (comp). The function comp must accept two pointers to void as their arguments.
The user defined function decides the comparison between values. For strings the following function could be used. In this example case one would reverse the sort order by passing the negative -strcmp( a, b ).
Example:
root = dbll_msort( root, compare );
int compare( const void * a, const void
* b)
{
return strcmp( a, b ); //
}
This function excepts any node as the parameter but passing the root node is an advantage. The return will always be the root node.
syntax:
dbll_new create the new list object or root node. This node is often called the sentinel node and serves as the starting point. When first created the root node has it's next pointer and previous pointers both set to NULL.
Example of creating a list:
DBLL
root; // our root node
DBLL node; //
working node
syntax:
dbll_prepend_sorted will insert a new node with value data in the position determined by the user supplied sort function (comp). See dbll_msort for details.
Using dbll_prepend_sorted only makes sense if the double linked list is already sorted.
Return Values:
Returns the new node if successful. If no nodes have been added to the root node dbll_prepend_sorted will fail and return NULL.
syntax:
dbll_libvers displays the library version number.