[Libclc-developers] Introducing the double linked list interface
Status: Planning
Brought to you by:
augestad
Menu
▾
▴
[Libclc-developers] Introducing the double linked list interface
|
From: <pha...@al...> - 2003-03-17 02:37:07
|
I submit the following for discussion and (hopefully) the approval of the
group. This may also serve as a first draft of the documentation for this
module.
I'll let you ponder this interface and suggest improvements before I post
the implementation of this module.
This document explains how to use the functions and data types defined by
the clc_dl module. This module implements a generic double linked list
system that is easy to use but flexible.
Data types:
===========
These are the data types defined by this module. They are defined in the
clc_dl.h header file. These types should generally not be touched directly
by users. Leave it to the module to manipulate these types. However, their
definitions are provided to users by defining CLC_DL_ADVANCED_FUNCS before
including the header. This allows extra flexibility and control.
typedef struct CLC_DL_NODE
{
struct CLC_DL_NODE *prev, *next;
int type; /* payload type */
size_t size; /* payload size */
void *payload; /* payload data */
void (*cleanup)(void *); /* cleanup function */
} CLC_DL_NODE;
CLC_DL_NODE is the basis of the system. It is the double linked list node
type. The members of this struct are as follows:
prev, next pointers to the previous and next nodes
type the payload type (in case of a linked list containing
more than one type of data
size size of the payload
payload pointer to the actual payload itself
cleanup pointer to a user supplied function to cleanup any extra
memory associated with a node's payload (but not the
node or payload itself - clc_dl_FreeNode() takes care of
that)
typedef struct CLC_DL_LIST
{
CLC_DL_NODE *head, *tail; /* first and last nodes */
size_t num; /* number of nodes */
int dyn; /* flag to indicate that this struct was
dynamically allocated */
} CLC_DL_LIST;
CLC_DL_LIST is a structure intended to store all data needed to access and
manipulate a linked list, currently comprising the following:
head, tail pointers to the first and last nodes in the list (NULL
if list is empty)
num number of nodes in the list
dyn flag to indicate whether this struct was dynamically
allocated with clc_dl_NewList() -
IMPORTANT NOTE: don't tamper with this member or memory
faults may occur!
Most accesses to a linked list use this struct. An object of this type may
be obtained (dynamically allocated) by using the clc_dl_NewList() function.
struct CLC_DL_SEARCH_DATA
{
CLC_DL_LIST *list; /* list the search applys to */
CLC_DL_NODE *lastnode; /* last node found by search */
int type; /* type of payload to search for */
size_t size; /* size of payload to search for */
void *find; /* payload data to search for */
int (*cmp)(int keytype, size_t keysize, const void *keydata,
int nodetype, size_t nodesize,
const void *nodedata); /* compare func */
int dir; /* direction of search:
CLC_DL_FORWARD = search forward,
CLC_DL_REVERSE = search backward */
};
CLC_DL_SEARCH_DATA is a structure used in linked list search operations.
Searching in the clc_dl module uses two functions; clc_dl_FindFirst(), which
takes (among other arguments) a pointer to this type, and clc_dl_FindNext()
which takes the same pointer. The former fills in the object this pointer
points to with values related to the search. These values are as follows:
list pointer to the CLC_DL_LIST the search pertains to
lastnode the last found node that matches the search criteria
(a null pointer if search failed)
type payload type of the node data to find
find pointer to data to find in the linked list
cmp pointer to a function that compares the key data, size
and type with a node's payload data, size and type,
returning 0 if they compare equal and non-zero
otherwise.
dir the direction of the search - use CLC_DL_FORWARD to
search forward from the start of the list or
CLC_DL_REVERSE to search backward from the end of the
list.
The clc_dl_FindNext() function uses this data to continue the search using
the same criteria, and updates the lastnode member each time it is called.
Users should obtain a pointer to a CLC_DL_SEARCH_DATA object, by using
clc_dl_NewSearch(), and pass it to clc_dl_FindFirst() and clc_dl_FindNext()
to search for nodes.
Basic functions:
================
The following are the "basic" functions, the ones most commonly used, in
the clc_dl module. These are defined in the clc_dl.c file. "Advanced"
functions, which provide extra flexibility but are less commonly used, are
described below this section.
CLC_DL_LIST *clc_dl_NewList(void)
The clc_dl_NewList() function is used to dynamically allocate and
initialise a CLC_DL_LIST structure. All fields are initialised to reflect an
empty linked list (one with no nodes).
CLC_DL_NODE *clc_dl_InsertData(CLC_DL_LIST *list,
int dir,
int type,
size_t size,
void *payload,
void (*cleanup)(void *));
The clc_dl_InsertData() function is used to create a new node and insert
new data into a linked list. It returns a pointer to the new node, or a null
pointer if memory could not be allocated for the node. The parameters are:
list a pointer indicating the linked to insert data into
dir direction of insertion: use CLC_DL_FRONT or CLC_DL_START
to insert at the start of the list or CLC_DL_END to
insert at the end of the list
type type of the payload (in case of a list containing more
than one type of data)
size size of the payload
payload the data to be copied to the new node's payload
cleanup pointer to a user supplied function to cleanup any extra
memory associated with a node's payload (but not the
node or payload itself - clc_dl_FreeNode() takes care of
that)
The last argument may be a null pointer, in which case no cleanup function
will be called, but the node and its payload will still be de-allocated
normally by clc_dl_FreeNode().
CLC_DL_SEARCH_DATA clc_dl_NewSearch(void);
void clc_dl_FreeSearch(CLC_DL_SEARCH_DATA *sd);
clc_dl_NewSearch() dynamically allocates a CLC_DL_SEARCH_DATA structure
that can be used by clc_dl_FindFirst() and clc_dl_FindNext().
clc_dl_FreeSearch() is used to de-allocate this structure.
CLC_DL_NODE *clc_dl_FindFirst(CLC_DL_LIST *list,
int type,
size_t size,
void *find,
int (*cmp)(int typekey,
const void *datakey,
int typenode,
const void *datanode),
int dir,
CLC_DL_SEARCH_DATA *srch);
CLC_DL_NODE *clc_dl_FindNext(CLC_DL_SEARCH_DATA *srch);
The clc_dl_FindFirst() and clc_dl_FindNext() functions are used to search
linearly for a node or nodes of a specified type containing a specified set
of data. The parameters of the former are:
list pointer indicating the linked list to search
type type of payload to search for
size size of payload to search for
find data to search for in payloads
cmp pointer to compare function (compares key type, size and
data to node's payload type, size and data - returns 0
if match, non-zero otherwise)
dir direction of search: use CLC_DL_FORWARD to search
forward from the start of the list or CLC_DL_REVERSE to
search backward from the end of the list
srch pointer to a structure containing data used in the
search process
clc_dl_FindFirst() searches for the first node that matches (according to
the comparison function passed as the fifth argument) the key data and its
type and size. clc_dl_FindNext(), using a CLC_DL_SEARCH_DATA * previously
passed to clc_dl_FindFirst(), searches for subsequent nodes that match the
search criteria specified in the clc_dl_FindFirst() call.
A special comparison function has been provided, which always compares
equal, called clc_dl_FindAll(). This can be used by clc_dl_FindFirst() and
clc_dl_FindNext() to "find" all nodes of a list in turn. This provides a way
to traverse the list node by node.
clc_dl_FindFirst() returns a pointer to the first node found that matches
the search criteria. clc_dl_FindNext() returns a pointer to the next node in
turn that matches the search criteria. Both functions return a null pointer
if a match is not found.
void clc_dl_FreeList(CLC_DL_LIST *list);
clc_dl_FreeList() removes all nodes and de-allocates all memory associated
with a linked list. Its single parameter, a pointer to CLC_DL_LIST,
indicates the linked list to de-allocate. The function calls
clc_dl_FreeNode() to de-allocate each node.
If the user supplied a cleanup function (when the node was created), then
that function is called before the payload of each node is de-allocated. If
the CLC_DL_LIST structure was allocated with clc_dl_NewList(), it will also
be de-allocated by clc_dl_FreeList().
void clc_dl_FreeNode(CLC_DL_LIST *list, CLC_DL_NODE *node);
clc_dl_FreeNode() removes a node from a linked list and de-allocates it.
The first parameter is a pointer to CLC_DL_LIST indicating the linked list
the node belongs to. If the node to be freed is not in a linked list (not
associated with a CLC_DL_LIST structure), the argument passed to this
parameter must be a null pointer. The second parameter is a pointer to the
node to free. If the user supplied a cleanup function (when the node was
created), then that function is called before the payload and node are
de-allocated.
void *clc_dl_Payload(CLC_DL_NODE *node, void *data);
clc_dl_Payload() stores a copy of a node's payload data in a user supplied
buffer, and returns a pointer to this copied data. The first parameter is a
pointer to the node whose payload data is to be copied. The second parameter
is a pointer to the buffer used to copy the data to. The return value is the
argument passed to the data parameter.
size_t clc_dl_NumNodes(CLC_DL_LIST *list);
int clc_dl_Type(CLC_DL_NODE *node);
size_t clc_dl_Size(CLC_DL_NODE *node);
clc_dl_NumNodes() returns the number of nodes in the linked list specified
by its only parameter, a pointer to CLC_DL_LIST.
clc_dl_Type() returns the payload type of the linked list node specified
by its only parameter, a pointer to CLC_DL_NODE.
clc_dl_Size() returns the payload size of the linked list node specified
by its only parameter, a pointer to CLC_DL_NODE.
int clc_dl_findall(int keytype, size_t keysize,
const void *keydata, int nodetype,
size_t nodesize, const void *nodedata);
clc_dl_findall() is a special function that can be used as the comparison
function for clc_dl_FindFirst() and clc_dl_FindNext(). It always returns 0,
indicating equality, regardless of the values passed to it. This is useful
when you want clc_dl_FindFirst() and clc_dl_FindNext() to "find" every
single node in the list; when, for example, you want to access each node in
turn, one at a time. This is the standard way of traversing the list node by
node.
Advanced functions:
===================
The following functions are defined in the clc_dl_a.c source file. Thier
prototypes are available by defining a macro called CLC_DL_ADVANCED_FUNCS
before the clc_dl.h header is included.
CLC_DL_NODE *clc_dl_NewNode(int type,
size_t size,
void *payload,
void (*cleanup)(void *));
clc_dl_NewNode() creates a new CLC_DL_NODE structure and fills it with
data. The parameters are:
type type of the data to store in the node's payload
size size of data to store in the node's payload
payload pointer to data to store in the node's (dynamically
allocated) payload
cleanup pointer to a user supplied function to cleanup any extra
memory associated with a node's payload (but not the
node or payload itself - clc_dl_FreeNode() takes care of
that)
The last argument may be a null pointer, in which case no cleanup function
will be called, but the node and its payload will still be de-allocated
normally by clc_dl_FreeNode().
void clc_dl_InsertNodes(CLC_DL_LIST *list,
CLC_DL_NODE *location,
CLC_DL_NODE *start,
int dir);
clc_dl_InsertNodes() inserts a "mini-list", a group of one or more linked
nodes that are not part of a linked list (ie., are not associated with a
CLC_DL_LIST structure), into a linked list. The parameters are:
list pointer to the list to insert the mini-list into
location pointer to "target node" where the mini-list will be
inserted (the mini-list will be inserted either before
or after this node)
start pointer to the first node in the mini-list
dir direction of insertion: use CLC_DL_BEFORE to insert
before the target node or CLC_DL_AFTER to insert after
the target node
CLC_DL_NODE *clc_dl_RemoveNode(CLC_DL_LIST *list, CLC_DL_NODE *node);
clc_dl_RemoveNode() removes a node from a linked list, but does not
de-allocate the it. The node is still available (via the returned pointer)
to manipulate as required. The first parameter is a pointer to the linked
list the node belongs to, while the second is a pointer to the node to be
removed.
CLC_DL_NODE *clc_dl_RemoveMultiNodes(CLC_DL_LIST *list,
CLC_DL_NODE *start,
size_t num);
clc_dl_RemoveMultiNodes() removes one or more nodes from a linked list,
but does not de-allocate them. The nodes removed remain linked, forming a
"mini-list", a group of one or more linked nodes that are not part of a
linked list (ie., are not associated with a CLC_DL_LIST structure). The
nodes are still available (via the returned pointer, which points to the
first node in the mini-list) to manipulate as required. The function
parameters are:
list pointer to the list to remove nodes from
start pointer to the first node to remove
num the number of nodes to remove
If the last argument is greater than the number of nodes from the node
indicated by the second argument to the end of the list, then all the nodes
from the start node to the end of the list are removed.
void *clc_dl_ModifyPayload(CLC_DL_NODE *node,
int newtype,
size_t newsize,
void *newpayload,
void (*newcleanup)(void *));
clc_dl_ModifyPayload() is used to change a CLC_DL_NODE's payload and
cleanup function. The original payload is de-allocated. If the user supplied
a cleanup function (when the node was created), then that function is called
before the payload is de-allocated. The parameters are:
node pointer to the node to modify
newtype the new payload type
newsize new payload size
newpayload pointer to data to copy to new payload
newcleanup pointer to a user supplied function to cleanup any extra
memory associated with a node's payload (but not the
node or payload itself - clc_dl_FreeNode() takes care of
that)
The last argument may be a null pointer, in which case no cleanup function
will be called, but the node and its payload will still be de-allocated
normally by clc_dl_FreeNode().
clc_dl_ModifyPayload() returns a pointer to the new payload on success. It
returns a null pointer if memory could not be allocated for the new payload,
in which case the old payload remains intact.
CLC_DL_NODE *clc_dl_GetHead(CLC_DL_LIST *list);
CLC_DL_NODE *clc_dl_GetTail(CLC_DL_LIST *list);
The clc_dl_GetHead() and clc_dl_GetTail() functions return pointers to the
first and last nodes (respectively) in a linked list. The solitary paramer
to each of these functions is a pointer to CLC_DL_LIST representing the
linked list whose head/tail node pointer will be returned.
User supplied functions:
========================
This section explains the purpose and requirements of user supplied
functions used by the clc_dl module. The user must follow these rules when
writing these functions.
Cleanup functions:
------------------
A cleanup function, as used by clc_dl_FreeNode(), clc_dl_FreeList() and
clc_dl_ModifyPayload(), is used to de-allocate any extra memory associated
with a node's payload - but not the payload itself nor the node.
(clc_dl_FreeNode() or clc_dl_FreeList() takes care of that.) Its prototype
must take the form:
void cleanup(void *);
The single parameter is a pointer to a node's payload data.
For example, suppose a node's payload is a struct containing a member
called some_ptr which is a pointer to some dynamically allocated memory. The
node's cleanup function could free the memory pointed to by this pointer
like so:
void cleanup(void *payload)
{
struct foo *bar = payload;
free(bar->some_ptr);
}
IMPORTANT NOTE: users should not de-allocate the payload themselves. This
should be left to clc_dl_FreeNode().
Comparison functions:
---------------------
A comparison function, as used by clc_dl_FindFirst() and
clc_dl_FindNext(), compares one payload type and data with another. It must
have the following prototype:
int cmp(int, size_t, const void *, int, size_t, const void *);
The first three parameters represent key values used to compare against the
node payload represented by the last three parameters. The int parameters
represent the payload type. This is useful in the case of a linked list that
contains more than one type of data. The comparison of data can be skipped
if the types don't match. The arguments passed to these parameters may
simply be ignored if the linked list only contains one type of data. The
size_t parameters represent the size of the data. The const void *
parameters are pointers to the data to be compared. The function must return
0 to indicate a match and non-zero to indicate no match.
For example, suppose you have a linked list containing strings, and you
want to search for a particular string in the list. The comparison function
passed to clc_dl_FindFirst() might look something like this:
int cmp(int keytype, size_t keysize, const void *keydata,
int nodetype, size_t nodesize, const void *nodedata)
{
/* first, make sure the types match */
if(keytype != nodetype)
return 1;
/* no need to compare strings if sizes don't match
(makes this function more efficient) */
if(keysize != nodesize)
return 1;
/* compare the strings */
return strcmp(keydata, nodedata);
}
A special comparison function is provided in the clc_dl module. Called
clc_dl_FindAll(), it always returns 0, indicating a match at every call.
This may be useful if you wish to use clc_dl_FindFirst() and
clc_dl_FindNext() to "find" every node in the list in turn. This is the
standard way of traversing the list node by node.
Eample of use:
==============
Normal use of this module is easy. The following program demonstrates how
simple it is.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "clc_dl.h"
#define PAYLOAD_TYPE_STRING 0
int cmp(int keytype, size_t keysize, const void *keydata,
int nodetype, size_t nodesize, const void *nodedata)
{
/* first, make sure the types match */
if(keytype != nodetype)
return 1;
/* no need to compare strings if sizes don't match
(makes this function more efficient) */
if(keysize != nodesize)
return 1;
/* compare the strings */
return strcmp(keydata, nodedata);
}
int main(void)
{
char *s[] = {"foo", "bar", "baz", "plonk", "baz", "bar", "foo"};
CLC_DL_NODE *node;
CLC_DL_LIST *list;
CLC_DL_SEARCH_DATA *srch;
int i;
char buf[10];
/* first, create the linked list */
list = clc_dl_NewList();
if(!list)
{
fprintf(stderr, "Memory allocation error.\n");
return EXIT_FAILURE;
}
/* next, fill it with data */
for(i = 0; i < (sizeof s / sizeof *s); i++)
{
node = clc_dl_InsertData(list, CLC_DL_START, PAYLOAD_TYPE_STRING,
1 + strlen(s[i]), s[i], NULL);
if(!node)
{
clc_dl_FreeList(list);
fprintf(stderr, "Memory allocation error.\n");
return EXIT_FAILURE;
}
}
/* now that we have filled the list, we can traverse it using
clc_dl_FindFirst() and clc_dl_FindNext() -
first we need a CLC_DL_SEARCH_DATA */
srch = clc_dl_NewSearch();
if(!srch)
{
clc_dl_FreeList(list);
fprintf(stderr, "Memory allocation error.\n");
return EXIT_FAILURE;
}
/* pass clc_dl_FindAll to clc_dl_FindFirst() to find first node */
node = clc_dl_FindFirst(list, 0, 0, NULL, clc_dl_FindAll,
CLC_DL_FORWARD, srch);
while(node)
{
/* we have the first node - now we extract the payload data */
clc_dl_Payload(node, buf);
printf("%s\n", buf);
/* find the next node */
node = clc_dl_FindNext(srch);
}
putchar('\n');
/* searching for data is just as simple - say you want to search for
all nodes containing "baz" */
node = clc_dl_FindFirst(list, PAYLOAD_TYPE_STRING, 1 + strlen(s[2]),
s[2], cmp, CLC_DL_FORWARD, srch);
while(node)
{
/* we have the first matching node -
now we extract the payload data */
clc_dl_Payload(node, buf);
printf("%s\n", buf);
/* find the next matching node */
node = clc_dl_FindNext(srch);
}
/* now we're done - we can clean up and quit */
clc_dl_FreeSearch(srch);
clc_dl_FreeList(list);
return 0;
}
Dig the sig!
_-/~~~~~~/\ |------ pha...@al... -------|
////| /^^\ |-----------------------------------------------|
||||||\ |()()|___ | name Peter Haywood | |
|||||||| | _---6|9- | alias Shaggy | Remove .NOSPAM to reply |
|||||||| |/ \_/| | alias Wolvaen | |
|||||||| | A | | alias HEY YOU! | |
|||||||| | (===/\\/ |-----------------------------------------------|
\||||/ /------\|/ | Dig my groovy web page! |
"""" " | http://alphalink.com.au.au/~phaywood/ |
- Aint I'm a Dawg! --|--------------- Shaggy was here! --------------|
(This sig best viewed with a fixed pitch font.)
|
