[Libclc-developers] Introducing the double linked list interface

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

From: Bryan Donlan <bd...@bd...>
Subject: Re: [Libclc-developers] Introducing the double linked list
 interface

>On Sunday 16 March 2003 10:39 pm, Peter "Shaggy" Haywood wrote:
>>   I submit the following for discussion and (hopefully) the approval of t=
>he
>> 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 po=
>st
>> 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:
>> =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
>>   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
>
>I don't think struct of typedef names should be uppercase. IMO, only enums =
>and=20
>#defines should be uppercase.

  I disagree. But this is open for discussion. If enough people agree with
you, I can change it.

>> 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
>
>How about inserting after a given node?

  I've been thinking about that. Perhaps we need a clc_dl_InsertDataAt()
function, which has an extra parameter, a pointer to a CLC_DL_NODE and
inserts the new node before or after (depending on the dir argument) the
indicated node.

>>   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)
>
>Why can't the caller do that? Unless you'll cann it with the payload, of=20
>course. But it dosen't say that.

  I want to free the user from the burden of freeing nodes and lists.
Basically, the user shouldn't even have to deal with nodes directly. They
can if they want to, by defining CLC_DL_ADVANCED_FUNCS. But they shouldn't
be forced to mess about with the internals of the data types. That's the
whole point of a library, really; to free the user from such responsibilities.
  Of course, there will be some things the library simply can't forsee, such
as the fact that a node's payload contains pointers (for example), and the
memory they point at must be freed. That's why a user defined cleanup
function is needed. But for the above reason, it is best to have the lib
call this function, rather than force the user to access the node or its
payload directly.

>> 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 sear=
>ch
>> linearly for a node or nodes of a specified type containing a specified s=
>et
>> 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 match=
>es
>> 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.
>
>How about FindPrev to walk the list backwards?

  That's what the dir member (of CLC_DL_SEARCH_DATA) is for. This indicates
whether to search forward or backward, and is set by clc_dl_FIND_FIRST().

> What about removing arbitrar=
>y=20
>nodes and replacing them during such a search?

  Huh? I don't understand.

>> Advanced functions:
>> =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
>>   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.
>
>What about GetNext and GetPrev?

  Good idea! Those might be useful. I'll add them.


From: Michael B.Allen <mb...@io...>
Subject: Re: [Libclc-developers] Introducing the double linked list
 interface

>On Mon, 17 Mar 2003 19:37:01 -0500
>Bryan Donlan <bd...@bd...> wrote:
>
>> > typedef struct CLC_DL_NODE
>> 
>> I don't think struct of typedef names should be uppercase. IMO, only
enums and 
>> #defines should be uppercase.
>
>I second that. It appears we need a style document or a consistent
>codebase to model the code after.

  I asked about this in comp.lang.c, but the only response I got seemed to
indicate that it should be left up to the author whether type names would be
upper or lower case. I agree that there should be a reasonably consistent
look to the libclc code. I prefer to have upper case type names, but I can
live with lower case ones. If the consensus is to have lower case names,
then I'll change the names to lower case.

>> > 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);
>
>This is far too complicated. Also these callback interfaces are less
>pleasant than a simple iterator interface because you frequently operate
>on variable on the stack.

  I don't see what's complicated about it. The first three parameters
represent the search key. The callback is analogous to that used by
bsearch() and qsort(). The next parameter represents the direction of
searching (forward or backward). And the last parameter is for saving the
search data for clc_dl_FindNext() to use. All this seems perfectly simple to me.

>I would just have an iterate function that initializes the search context
>object and a next object that returns each element. I don't see the
>advantage of returning the first element with the initial call. It's
>a little awkward programatically actually.

  Not to me. I don't see why you have a problem with it.