[Libclc-developers] Double linked list module update

[<pha...@al...>]

  I've been busy implementing many of the changes to the double linked list
module suggested by you all, and I include the latest draft of the interface
documentation here for your consideration. If I have not taken a suggestion
you feel is warrented, don't worry. I may still do so. I'm still trying to
figure out the best way to go about some things and just didn't get around
to other things yet.
  I do have a question, though. There has been talk of including other
container types in libclc (single linked lists, trees, deques, etc.). Are we
going to have one module for each of these, or would it make more sense to
put these all in one module?
  Now, what have I done to the double linked list interface? Well, I've
added functions that return a node's next and prev pointers. I've added a
function that iterates through the list and calls a user defined function
for each node. There's also a new search function that goes "backward", as
suggested by Bryan Donlan. I think it was Bryan who also suggested a
function to insert a new node at a given location, which was something I was
already thinking about. I have implemented that function. I've also changed
type names to lower case, as several people have suggested. I added a copy
node function a couple of people suggested. Other changes: well, you can see
for yourself.

  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 */
}   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

Most accesses to a linked list use this struct. An object of this type
is 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:
                                                  >= 0 means forward,
                                                < 0 means 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 a value >= 0 to search
              forward from the start of the list, or a value < 0 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.
  The macros CLC_DL_FORWARD and CLC_DL_REVERSE are provided as a
convenience for the dir member. Use the former to search forward or the
latter to search backward.


typedef int clc_dl_cmpfunc(
  int keytype,                /* type of key data */
  size_t keysize,             /* size of key data */
  const void *keydata,        /* key data */
  int nodetype,               /* type of node payload data */
  size_t nodesize,            /* size of node payload data */
  const void *nodedata);      /* node payload data */
  
  The clc_dl_cmpfunc type is defined merely to make clc_dl module code
easier to read. It is the type of user defined comparison functions
(see below).


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 value < 0 to insert at the
              start of the list, ora value >= 0 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().
  The macros CLC_DL_FRONT, CLC_DL_START and CLC_DL_END are provided as a
convenience for the dir argument. Use either of the first two to insert
at the start of the list or the last to insert at the end.


clc_dl_node *clc_dl_InsertDataAt(clc_dl_list *list,
                                 int dir,
                                 clc_dl_node *location,
                                 int type,
                                 size_t size,
                                 void *payload,
                                 void (*cleanup)(void *));

  clc_dl_InsertDataAt() is very similar to clc_dl_InsertData(). It
creates a new double linked list node and stored data in it the same was
as clc_dl_InsertData(). The difference is that this function allows the
user to specify where the node will be inserted. The new node is
inserted before or after (depending on the dir argument) a given node
(location). 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 a value < 0 to insert before
              the specified node, or a value >= 0 to insert after the
              specified node

  location    the node to insert the new node before or after

  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 macros CLC_DL_BEFORE and CLC_DL_END are provided as a convenience
for the dir argument. Use the former to insert before the given location
or the latter to insert after it.


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,
                              clc_dl_cmpfunc *cmp,
                              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.
  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.
  The macros CLC_DL_FORWARD and CLC_DL_REVERSE are provided as a
convenience for clc_dl_FindFirst()'s dir argument. Use the former to
search forward or the latter to search backward.

void clc_dl_FreeList(clc_dl_list *list);

  clc_dl_FreeList() removes all nodes and de-allocates all memory
associated with a linked list, including the clc_dl_list structure. 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.


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.


clc_dl_node *clc_dl_NextNode(clc_dl_node *node);
clc_dl_node *clc_dl_PrevNode(clc_dl_node *node);
clc_dl_node *clc_dl_Link(clc_dl_node *node, int dir);

  clc_dl_NextNode() returns the "next" pointer of the double linked list
node pointed to by its single argument.
  clc_dl_PrevNode() returns the "prev" pointer of the double linked list
node pointed to by its single argument.
  clc_dl_Link() returns the "next" (if dir >= 0) or "prev" (if dir < 0)
pointer of the node pointed to by its node argument. The macros
CLC_DL_NEXT and CLC_DL_PREV are provided for the dir argument as a
convenience.


int clc_dl_ForEach(clc_dl_list *list,
                   int (*func)(clc_dl_node *),
                   int dir);

  clc_dl_ForEach() is a function that iterates over all the nodes in a
double linked list, passing (a pointer to) each node to a user supplied
function. The first parameter is a pointer to the linked list whose
nodes are to be iterated over. The (user supplied) function specified by
the second parameter is called and passed the address of each node in
the list in turn. The third parameter is the direction of iteration;
>= 0 means iterate forward, while < 0 means iterate backward. The macros
CLC_DL_FORWARD and CLC_DL_BACKWARD have been supplied for convenience.
  Iteration can be stopped prematurely by returning non-zero from the
called function, in which case the value returned by that function will
also be returned by clc_dl_ForEach(). Otherwise clc_dl_ForEach() returns
0.


void clc_dl_Sort(clc_dl_list *list, clc_dl_cmpfunc *cmp);

  The clc_dl_Sort() function sorts the nodes of a double linked list
according to a user supplied comarison function.


  I came up with two versions of the following function. The first one
here is the original version. After writing it, I re-thought the
possible needs of users, and thought a slightly more versatile version
would be better. So I rewrote it (with an extra function for even more
versatility). But the new version uses variable argument lists, and may
be overkill. What do you all think? Should I keep the variable args
version or go back to the original? Or should I rename one of the
versions and keep both of them?

Original version:
clc_dl_list *clc_dl_MergeLists(clc_dl_list *list1, clc_dl_list *list2);

  clc_dl_MergeLists() creates a new double linked list and copies the
nodes (and their payloads) of two source linked lists, as specified by
its two arguments, into it. The nodes are not sorted. On success, the
function returns a pointer to the new linked list. On failure, it
returns a null pointer. In either case the source lists are not
modified.

Variable args version:
clc_dl_list *clc_dl_vMergeLists(size_t num, va_list arg);
clc_dl_list *clc_dl_MergeLists(size_t num, ...);

  The clc_dl_vMergeLists() and clc_dl_MergeLists() functions create a
new double linked list and copies the nodes from a number of existing
lists into it. The first parameter represents the number of lists to be
merged into the new list. The second parameter represents pointers to
the lists to merge. On success, these functions return a pointer to the
new list. On failure they return a null pointer. In either case the
source lists are not modified.


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 the first node or 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 that
the two data items are equal, < 0 to indicate that the first data item
(or key) is less than the second or > 0 to indicate that the first data
item (or key) is greater than the second.
  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);
}


clc_dl_ForEach()'s second parameter:
------------------------------------
  The second parameter of clc_dl_ForEach() is a pointer to a user
defined function that has the following format:

int func(clc_dl_node *node);

This function can be used for almost any purpose pertaining to a double
linked list node. Iteration can be stopped prematurely by returning
non-zero from this user supplied function, in which case the value
returned by this function will also be returned by clc_dl_ForEach().


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;

  /* compare the strings */
  return strcmp(keydata, nodedata);
}

/* a function to be passed to clc_dl_ForEach() to print the list */
int printnode(clc_dl_node *node)
{
  char buf[10];
  if(0 > printf("%s ", clc_dl_Payload(node, buf)))
    return EOF;
  else
    return 0;
}

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_ForEach() */
  clc_dl_ForEach(list, printnode, CLC_DL_FORWARD);
  putchar('\n');

  /* searching for data is just as simple - say you want to search for
    all nodes containing "baz" - first we need a search structure */
  srch = clc_dl_NewSearch();
  if(!srch)
  {
    clc_dl_FreeList(list);
    fprintf(stderr, "Memory allocation error!\n");
    return EXIT_FAILURE;
  }

  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 ", buf);

    /* find the next matching node */
    node = clc_dl_FindNext(srch);
  }
  putchar('\n');

  /* sorting the list is also easy - just use clc_dl_Sort() */
  clc_dl_Sort(list, cmp);

  clc_dl_ForEach(list, printnode, CLC_DL_FORWARD);
  putchar('\n');

  /* 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.)