Re: [Libclc-developers] Introducing the double linked list interface

[<bo...@me...>]

Peter Shaggy Haywood wrote:
>   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.

Thanks for a very well documented submission, Peter.

Here are my comments, questions and misunderstandings :-)

- Have you considered to provide the cleanup function (dtor) to the 
delete-functions instead of storing the dtor in the list? I guess that 
you currently store it since we need a per-node dtor right now.

- Why do we need the size of the payload?


>   I'll let you ponder this interface and suggest improvements before I post
> the implementation of this module.

The plan is to add the list to the June release of libclc. We may want 
to discuss other "container classes" as well as the list so that common 
container concepts gets the same solution. This means that we won't 
finish this discussion in a long time...

> 
>   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.

IMO, the CLC_DL_ADVANCED_FUNCS macro should be removed. All 
functionality should always be available, just like the standard C library.

> 
> 
> 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;

Does CLC_DL_NODE and CLC_DL_LIST have to be in the header?

> 
>   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

How likely is it that we have more than one type in the same list? If it 
isn't used a lot, maybe we can have more than one list type? CLC_DL_LIST 
and CLC_DL_MULTILIST, where the latter 'knows' about types?

Even if we have more than one type in the list, does the list have to 
know? A user can easily create a wrapper for the data.
	struct type_wrapper {
		int type;
		void *data;
	};
and store this in the list.


> 
>   size        size of the payload

Why do we need the size? If it is needed for copying, what about pointer 
members in 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 */

Aren't CLC_DL_LIST objects always 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 */

How about "int forward" instead of "int dir". If forward == 0, then it 
is backward. It removes the need for CLC_DL_FORWARD and CLC_DL_REVERSE.

> };
[snip]

> 
> 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.

I, as everyone else, have my own list :-) This list adt has a concept of 
sublists. A sublist can be created in different ways, e.g. as a result 
set from a search within the original list. Then the user can traverse 
the sublist. IMHO this is better than FindFirst/Next since the user can 
manipulate the result set. The sublist can for example be sorted before 
traversal.

See http://www.metasystems.no/metalib/list_8h.html#_details for more 
details.

> 
> 
> 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 *));

clc_dl_add() or clc_dl_insert()?

[snip]

> CLC_DL_SEARCH_DATA clc_dl_NewSearch(void);
> void clc_dl_FreeSearch(CLC_DL_SEARCH_DATA *sd);

What if we want to search in e.g. a clc_map, clc_deque or some other 
container? Is it possible to create a common descriptor for all/most 
searchable modules?


> 
>   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);

Later you have clc_dl_findall(). How about clc_dl_findfirst() and 
clc_dl_findnext(), or just clc_dl_first(), clc_dl_next() and clc_dl_all()?


[snip]

> void *clc_dl_ModifyPayload(CLC_DL_NODE *node,
>                            int newtype,
>                            size_t newsize,
>                            void *newpayload,
>                            void (*newcleanup)(void *));

clc_dl_replace()?
It doesn't really modify the existing payload, but replaces an existing 
payload with a new.

[snip]

> 
> 
> 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.

How about -1, 0 and 1 for less than, equal and greater than? Then we can 
sort the list using the same function.

[snip]

I miss a few functions. copy(), merge(), foreach(),



BTW, I spent 5 hours on a train yesterday thinking about libclc. One of 
the things I thought of was a general object adaptor which could be used 
in "advanced" modules. Such an object adaptor would know enough about an 
object to allocate, free, compare, copy and clone any object. I do *not* 
recommend that we use such an adaptor in clc_list as the concept will 
probably be too odd for most people. Maybe it can be used in another 
list, clc_objlist?

We should probably spend more time designing libclc. :-)

-- 
boa

Please join the libclc-developers list
at http://lists.sourceforge.net/lists/listinfo/libclc-developers