Re: linked list library

[Ben Pfaff]

John Darrington <address@hidden> writes:

> On Thu, Jun 29, 2006 at 09:23:18PM -0700, Ben Pfaff wrote:
>      I added a patch containing a linked list implementation that I
>      would like to check in to libpspp.  I'd appreciate some review,
>      if you guys have time:
>      http://savannah.gnu.org/patch/index.php?func=detailitem&item_id=5216
>
> It seems to have everything that a linked list could want (and more!).
>
> 1.  Some of the headers have got the 59 Temple Place address.

Oops!  Thanks--fixed.

> 2.  I ran gcov on the tests.  All lines of code are indeed exercised,
>     but not quite all branches.  I don't know if you're worried about that.

I hadn't noticed the branch counting option to gcov.  Thanks for
pointing it out--I adjusted the tests so that all branches are
now exercised.  (In one case, there was a test that never *could*
be true, and in another case the test was redundant, so this
turned out to be a chance to drop some branches.)

> 3.  The OFFSETOF macro seems to be a GNU builtin.  So far as I'm
>     aware, it's not part of any C standard.  Will this be portable
>     enough?  Maybe it's in gnulib; I haven't looked.

It's in the standard C library, since C90.  Here's what C99 says
about it (the C90 version is the same, but I have a plain text
version of C99 that is thus easier to quote from):

         7.17 Common definitions <stddef.h>
    [...]
    3    The macros are [...]
                offsetof(type, member-designator)
         which expands to an integer constant expression that has
         type size_t, the value of which is the offset in bytes, to
         the structure member (designated by member-designator), from
         the beginning of its structure (designated by type).  The
         type and member designator shall be such that given
                static type t;
         then the expression &(t.member-designator) evaluates to an
         address constant. (If the specified member is a bit-field,
         the behavior is undefined.)

Occasionally, it is invaluable, so it is a good macro to be aware
of.

It is also used in the PSPP pool code.

> 4.  It might be useful to have a const version of ll[x]_apply.

I was hesitant even to include ll[x]_apply.  I am not sure it is
actually useful, because it is normally so much more convenient
to write an explicit loop instead of writing a separate function
to do what you want and then calling ll[x]_apply.  But a const
version, to my mind, would be even less useful, because it would
only be useful if it could communicate back to the caller or if
it modified static data.  The former is inconvenient (you have to
use the void * "aux" parameter) and the latter is inelegant at
best.

What do you think?

> 5.  How about an assertion to ensure the requirement that
>     llx_set_allocator is called before any other llx_ function ?

The allocation routines were an afterthought, and I think that
the concept is wrong.  Some lists will want to be allocated on
the heap, some from pools, some possibly from custom allocators.
So for the revised version I introduced a "memory manager" type,
and the routines that allocate or release nodes take a memory
manager argument.

I posted the revised library in the patch:
        http://savannah.gnu.org/patch/download.php?file_id=10286

About the "review policy", I posted hastily about that.  I want
to say more, but I'm sleepy now and so I'll start a new thread
about it in the morning.  Summary: don't panic, I don't want to
be nefarious or bureaucratic.
-- 
"I don't want to learn the constitution and the declaration of
 independence (marvelous poetry though it be) by heart, and worship the
 flag and believe that there is a god and the dollar is its prophet."
--Maarten Wiltink in the Monastery