Generic linked list with internal storage?

[SG]

The easy answer to that question is, "use a different language",
*cough* C++ STL *cough*, that has better type safety built into the


language.  These questions have been around for a very long time,
and C has tended to remain the way that it is with respect to type
safety.  I think your criticisms are valid, and agree with them,
and if it was the only deciding factor, no one would choose C to
do anything of this sort. In fact, C was around when Stepanov was
working on his stuff, and he didn't use C.  Hmmm, is that a
coincidence?

Do you believe that this is a worthy pursuit in C at all?

Depends on what you mean exactly. Is it worth to invent a new
language feature for C to "fix" this? No, I don't think so. I also
think that "generic containers" (whatever they look like) don't belong
into future C standards as part of the library. But that's just my
opinion. Still, I _am_ interested in what people can come up with in
C and what die-hard C programmers consider to be "elegant" designs of
"generic linked lists".

You're not
alone if you don't think it is.  However, there are some people who do
think it is.

Cheers,
SG

 

[Seebs]

Taking the bait like a true DHCP: I think a generic linked
list package is about as useful as a generic array package.
The linked list is so simple a beast that the code to handle it
isn't complex or difficult enough to bother hiding away behind a
lot of genericized interfaces. Just stick a `struct node *next'
element in the data item of your choice and use open code.

I think the Linux kernel "embeddable list" may be a genuine
counterexample -- it allows things to be on multiple lists, for
one thing, with shared code.

But for
a plain vanilla linked list ... Why bother?

Generally, true. I don't even consciously notice adding a small
list implementation -- it's too trivial to notice.

-s

 

[Eric Sosman]

[...] I also
think that "generic containers" (whatever they look like) don't belong
into future C standards as part of the library. But that's just my
opinion. Still, I _am_ interested in what people can come up with in
C and what die-hard C programmers consider to be "elegant" designs of
"generic linked lists".

Taking the bait like a true DHCP: I think a generic linked
list package is about as useful as a generic array package.
The linked list is so simple a beast that the code to handle it
isn't complex or difficult enough to bother hiding away behind a
lot of genericized interfaces. Just stick a `struct node *next'
element in the data item of your choice and use open code.

If you've got a lot of linked lists of a lot of disparate
struct types, I could see putting a `struct linkstuff' at the
start of each "payload" struct and using functions that dealt
in `struct linkstuff' objects, casting as needed. This could
be handy with the more exotic flavors of linked list, like lists
built with self-relative offsets instead of pointers. But for
a plain vanilla linked list ... Why bother?

The principal benefits of generic "containers" are, IMHO,
two. For a complex or intricate container -- the AVL tree
that every CS student is forced to write and never uses again,
for example -- writing and debugging the code is enough labor
that it's worth capturing and re-using. But this consideration
doesn't apply for an ordinary linked list; it's more work to
learn the conventions of somebody's function suite than to just
diddle the links directly.

The other benefit is that a suitable package can "contain"
data items that are ignorant of their containment. You want to
put a bunch of `struct tm' instances in a list or a tree or some
such, fine: The list/tree/whatever package manages the navigation,
and the `struct tm' is untouched. In particular, the `struct tm'
can be contained in multiple different containers at the same
time, with its membership fluctuating as the program runs. But
if by "internal storage" you mean "one allocation for metadata
and payload," I don't think this can be made to work.

 

[Willem]

Eric Sosman wrote:
) The principal benefits of generic "containers" are, IMHO,
) two. For a complex or intricate container -- the AVL tree
) that every CS student is forced to write and never uses again,
) for example -- writing and debugging the code is enough labor
) that it's worth capturing and re-using. But this consideration
) doesn't apply for an ordinary linked list; it's more work to
) learn the conventions of somebody's function suite than to just
) diddle the links directly.
)
) The other benefit is that a suitable package can "contain"
) data items that are ignorant of their containment. You want to
) put a bunch of `struct tm' instances in a list or a tree or some
) such, fine: The list/tree/whatever package manages the navigation,
) and the `struct tm' is untouched. In particular, the `struct tm'
) can be contained in multiple different containers at the same
) time, with its membership fluctuating as the program runs. But
) if by "internal storage" you mean "one allocation for metadata
) and payload," I don't think this can be made to work.

The third benefit is that when you decide that a linked list isn't
giving enough performance, you can swap in a generic AVL tree or
whatever an hey presto! Instant performance win! You can even
test which kind of generic container implementation gives you the
best oerformance, all with just a single change, because the interface
to all the containers is the same.

I have no idea if this happens in practise, though. I sure have
never seen it happen.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

 

[Ben Pfaff]

[...] I also
think that "generic containers" (whatever they look like) don't belong
into future C standards as part of the library. But that's just my
opinion. Still, I _am_ interested in what people can come up with in
C and what die-hard C programmers consider to be "elegant" designs of
"generic linked lists".

Taking the bait like a true DHCP: I think a generic linked
list package is about as useful as a generic array package.
The linked list is so simple a beast that the code to handle it
isn't complex or difficult enough to bother hiding away behind a
lot of genericized interfaces. Just stick a `struct node *next'
element in the data item of your choice and use open code.

I find that the power of generic linked list packages is in
nontrivial operations. Yes, there are some. For example, I
consider ll_splice() and ll_swap_range() below to be in that
category, in that it would take me a few minutes to rewrite them,
and probably a few hours to write an exhaustive unit test. But
I've already done both, so I don't have to do so again.

/* Linked list node. */
struct ll
{
struct ll *next; /* Next node. */
struct ll *prev; /* Previous node. */
};

/* Linked list. */
struct ll_list
{
struct ll null; /* Null node. */
};

/* Returns the node preceding LL in its list,
or the null node if LL is the first node in its list.
(In an empty list, the null node precedes itself.) */
static inline struct ll *
ll_prev (const struct ll *ll)
{
return ll->prev;
}

/* Removes R0...R1 from their current list
and inserts them just before BEFORE. */
void
ll_splice (struct ll *before, struct ll *r0, struct ll *r1)
{
if (before != r0 && r0 != r1)
{
/* Change exclusive range to inclusive. */
r1 = ll_prev (r1);

/* Remove R0...R1 from its list. */
r0->prev->next = r1->next;
r1->next->prev = r0->prev;

/* Insert R0...R1 before BEFORE. */
r0->prev = before->prev;
r1->next = before;
before->prev->next = r0;
before->prev = r1;
}
}

/* Exchanges the positions of A0...A1 and B0...B1,
which may be in the same list or different lists but must not
overlap. */
void
ll_swap_range (struct ll *a0, struct ll *a1, struct ll *b0, struct ll *b1)
{
if (a0 == a1 || a1 == b0)
ll_splice (a0, b0, b1);
else if (b0 == b1 || b1 == a0)
ll_splice (b0, a0, a1);
else
{
struct ll *x0 = ll_prev (a0), *x1 = a1;
struct ll *y0 = ll_prev (b0), *y1 = b1;
a1 = ll_prev (a1);
b1 = ll_prev (b1);
x0->next = b0;
b0->prev = x0;
b1->next = x1;
x1->prev = b1;
y0->next = a0;
a0->prev = y0;
a1->next = y1;
y1->prev = a1;
}
}

 

[Eric Sosman]

Eric Sosman wrote:
) The principal benefits of generic "containers" are, IMHO,
) two. [...]

The third benefit is that when you decide that a linked list isn't
giving enough performance, you can swap in a generic AVL tree or
whatever an hey presto! Instant performance win! You can even
test which kind of generic container implementation gives you the
best oerformance, all with just a single change, because the interface
to all the containers is the same.

That would (or could) be true for a "generic containers"
package, but the O.P. specifically said "generic linked list."
A generic "sequenced container" with assorted common-interface
implementations (simple linked list, skip list, starboard list)
might be useful. A generic "random-access container" with
assorted implementations (simple array, Judy tree) might also
be useful. The interfaces can hide implementation detail, and
therein lies some benefit. But if the implementation detail
("it has to be a linked list" or "it has to be an array") is
already specified, where's the gain in hiding?

 

[jacob navia]

SG a écrit :

Depends on what you mean exactly. Is it worth to invent a new
language feature for C to "fix" this? No, I don't think so. I also
think that "generic containers" (whatever they look like) don't belong
into future C standards as part of the library. But that's just my
opinion. Still, I _am_ interested in what people can come up with in
C and what die-hard C programmers consider to be "elegant" designs of
"generic linked lists".

Look "SG":

In the other thread you asked:

> But how do you access the data stored in that node?

My answer is:

Very easy. You use an iterator


Iterator *it = newIterator(mylist);
double *d;
for (d = GetFirst(it);
d != NULL;
d = it->GetNext(it) {
// Work with *d here
}



I do.

I have today finished the implementation of scapegoat trees, that
together with AVL trees, and redblack trees round up the tree section of
my library.

I have added a heap object, that amortizes allocations by allocating a
bigger block and avoids allocating each time a new element is added to
the container.

I will add the template executable to the library. That code allows you
to write generic code and use that template for any data structure you
want. Obviously it is an external utility (whose code is provided by the
library). The compiler is notmodified.

What is fun of that utility is that it is so simple (a few hundred lines
of C) that you can customize template expansion as you wish.

Please remember:

Here is comp.lang.c

If you like C++ and think C is only for "die ahrds" note that
comp.lang.c++ is a group dedicated to your preferred monstruosity.

Thanks in advance for staying on topic within this group.

 

[Jef Driesen]

Taking the bait like a true DHCP: I think a generic linked
list package is about as useful as a generic array package.
The linked list is so simple a beast that the code to handle it
isn't complex or difficult enough to bother hiding away behind a
lot of genericized interfaces. Just stick a `struct node *next'
element in the data item of your choice and use open code.

If you've got a lot of linked lists of a lot of disparate
struct types, I could see putting a `struct linkstuff' at the
start of each "payload" struct and using functions that dealt
in `struct linkstuff' objects, casting as needed. This could
be handy with the more exotic flavors of linked list, like lists
built with self-relative offsets instead of pointers. But for
a plain vanilla linked list ... Why bother?

Writing a linked list isn't very complex, but I prefer to spend my time
on the main program I'm writing, rather than having to rewrite the low
level data structures every time I need one. It's just more practical to
have a toolbox with well tested code that can be reused every time you
need it. Performance might be a little worse compared to a custom made
data structure, but if that's a problem you can always switch to a
better implementation.

 

[SG]

My answer is:

Very easy. You use an iterator

Iterator *it = newIterator(mylist);
double *d;
for (d = GetFirst(it);
d != NULL;
d = it->GetNext(it) {
// Work with *d here
}

You've posted this fragment already. It sure looks nice. But I was
actually more interested in what you do in GetFirst and GetNext and
how you derive the double pointer with respect to possible alignment
problems. In this case you could argue that after two pointers (next/
prev) it's likely that the char buffer is well-aligned for storing
objects of many possible types and this would probably work on many
platforms already. But unless you have taken special care (manual
padding if necessary) this might break as far as I can tell -- that
is, assuming the double pointer points directly into the char buffer
of your node struct objects.

I will add the template executable to the library. That code allows you
to write generic code and use that template for any data structure you
want. Obviously it is an external utility (whose code is provided by the
library). The compiler is notmodified.
Interesting.

If you like C++ and think C is only for "die ahrds" note that
comp.lang.c++ is a group dedicated to your preferred monstruosity.

I didn't say "C is only for die-hards". But I did use -- actually, I
seem to have /misused/ -- the term "die-hard". I'm not a native
speaker. I picked "die-hard" because it felt right. It turns out that
it doesn't convey what I /meant/ to say, at all. For a lack of a
better term please just ignore it.

But it does strike me as a little odd, that you combined a plea for
staying on-topic with the "monstruosity" comment.

Cheers,
SG

 

[Eric Sosman]

[...]

If you've got a lot of linked lists of a lot of disparate
struct types, I could see putting a `struct linkstuff' at the
start of each "payload" struct and using functions that dealt
in `struct linkstuff' objects, casting as needed. This could
be handy with the more exotic flavors of linked list, like lists
built with self-relative offsets instead of pointers. But for
a plain vanilla linked list ... Why bother?

Writing a linked list isn't very complex, but I prefer to spend my time
on the main program I'm writing, rather than having to rewrite the low
level data structures every time I need one. It's just more practical to
have a toolbox with well tested code that can be reused every time you
need it. Performance might be a little worse compared to a custom made
data structure, but if that's a problem you can always switch to a
better implementation.

Tastes differ, obviously. But ponder this: Suppose you
have a pointer `listnode' to a node in a linked list, and
another pointer `newnode' to a free-floating node you'd like
to insert, right after the existing node. Which of

insertAfter(listnode, newnode);

or

insertAfter(newnode, listnode);

is correct, and which is a bug? Is there any possible way
to declare insertAfter() so the compiler can spot the incorrect
usage? (Note that both parameters will be of the same type,
and neither can be `const'.) In short, is there any defense
against silly mistakes other than "RTFM?"

If instead you were looking at the open-code fragments

newnode->next = listnode->next;
listnode->next = newnode;

and

listnode->next = newnode->next;
newnode->next = listnode;

would it be easier to spot the error? More to the point,
perhaps, would it be harder to get it wrong in the first place?

Don't commit canaricide by cannon.

 

[Tim Rentsch]

A typical (double) linked list is implemented with these two data
structures:

typedef struct node_t {
node_t *prev;
node_t *next;
void *data;
} node_t;

typedef struct list_t {
node_t *head;
node_t *tail;
} list_t;

typedef struct mydata_t {
...
} mydata_t;

The major disadvantage of this approach is that the data contents of
the list needs to be stored outside of the list data structures. Thus
if you want to store some user defined data in the list, you end up
with two memory allocations per node: one for the node_t structure,
and one for the user defined mydata_t structure.

Is there a way to avoid this additional allocation, but without
loosing the ability to store custom data? Thus I don't want to tie my
list to the mydata_t structure like this:

typedef struct node_t {
node_t *prev;
node_t *next;
mydata_t data;
} node_t;

Maybe allocate storage for the node_t and the mydata_t structure in a
single block. Something like this:

node_t *node = malloc (sizeof (node_t) + sizeof (mydata_t));
mydata_t *data = node + sizeof (node_t);

But I think this might cause trouble due to alignment issues?

Yes, it might. In fact, almost certainly will, if the code has
any significant longevity.

It is possible to do something along the lines of what you're
asking about. Very briefly, the list "header" has an additional
member that stores a byte offset of where the node value is
stored, and what numeric value is stored in this offset member is
computed using one of the standard techniques for determining
alignment of a type. Doing this reliably and portably requires a
lot of attention to details regarding not only alignment but also
the rules about storing into structure members and padding bytes.
(There are some other details about what type is being used and
what interface to supply to read or store the data, but I'm
skipping over these.)

A more significant question, I think, is are you really sure you
want to do this, given that it seems like you aren't completely
sure of how to do it so it works? It's easy to sidestep all the
difficulties, just by doing two allocations. Until you know how
to avoid the problems, and avoid them reliably, you're probably
not in the best position to decide whether the single allocation
approach is a good one. So I would suggest either just doing
two allocations, or making learning how to implement a "data
and list header together" approach a pre-requisite to deciding
whether you do, in fact, actually want to use such an approach
in your program(s).

 

[jacob navia]

Eric Sosman a écrit :

[snip]

Which of

insertAfter(listnode, newnode);

or

insertAfter(newnode, listnode);

is correct, and which is a bug?

Which of

strcpy(dst,src);

or
for (int = 0; i<=strlen(src);i++)
dst = src;

is clearer?

You will notice that for somebody that has never used strcpy the second
form is clearer, following your argument.

Fact is, strcpy is a *standard* function, i.e. one which is part of the
standard language and everybody uses it.

That is why I insist that a STANDARD list library would be a progress
for the language.

 

[Willem]

jacob navia wrote:
) Which of
)
) strcpy(dst,src);
)
) or
) for (int = 0; i<=strlen(src);i++)
) dst = src;
)
) is clearer?

You're missing the point, which would have been illustrated
by the following:

Which of

strcpy(src, dst);

or

for (i = 0; dst != 0; i++)
src = dst;

is clearer ?


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

 

[ImpalerCore]

I think the Linux kernel "embeddable list" may be a genuine
counterexample -- it allows things to be on multiple lists, for
one thing, with shared code.


Generally, true.  I don't even consciously notice adding a small
list implementation -- it's too trivial to notice.

I'm curious what you consider a plain vanilla linked list? Perhaps if
you could describe the vanilla list feature subset, maybe by listing
functions of an existing implementation like GLib or the C++ STL list,
or is there even a function interface to it?

Do you feel that adding a c_compare_function_t makes it a 'chocolate
twist with jimmies' linked list?

Best regards,
John D.

 

[ImpalerCore]

Depends on what you mean exactly.  Is it worth to invent a new
language feature for C to "fix" this?  No, I don't think so.  I also
think that "generic containers" (whatever they look like) don't belong
into future C standards as part of the library.  But that's just my
opinion.  Still, I _am_ interested in what people can come up with in
C and what die-hard C programmers consider to be "elegant" designs of
"generic linked lists".

That's pretty much my feelings as well. I personally don't have an
interest in pushing for any library feature into the standard,
although there is evidence that it can be a benefit a la C++ STL. The
downside is if a library feature becomes standard, and later discover
it was a mistake (gets), it complicates things.

Best regards,
John D.

 

[ImpalerCore]

[...]

If you've got a lot of linked lists of a lot of disparate
struct types, I could see putting a `struct linkstuff' at the
start of each "payload" struct and using functions that dealt
in `struct linkstuff' objects, casting as needed. This could
be handy with the more exotic flavors of linked list, like lists
built with self-relative offsets instead of pointers. But for
a plain vanilla linked list ... Why bother?

Writing a linked list isn't very complex, but I prefer to spend my time
on the main program I'm writing, rather than having to rewrite the low
level data structures every time I need one. It's just more practical to
have a toolbox with well tested code that can be reused every time you
need it. Performance might be a little worse compared to a custom made
data structure, but if that's a problem you can always switch to a
better implementation.

     Tastes differ, obviously.  But ponder this: Suppose you
have a pointer `listnode' to a node in a linked list, and
another pointer `newnode' to a free-floating node you'd like
to insert, right after the existing node.  Which of

        insertAfter(listnode, newnode);

or

        insertAfter(newnode, listnode);

That's a problem with any function that has identical arguments. Are
you going to stop using the C string library functions because of this
(rhetorical)?

is correct, and which is a bug?  Is there any possible way
to declare insertAfter() so the compiler can spot the incorrect
usage?  (Note that both parameters will be of the same type,
and neither can be `const'.)  In short, is there any defense
against silly mistakes other than "RTFM?"

     If instead you were looking at the open-code fragments

        newnode->next = listnode->next;
        listnode->next = newnode;

and

        listnode->next = newnode->next;
        newnode->next = listnode;

would it be easier to spot the error?  More to the point,
perhaps, would it be harder to get it wrong in the first place?

     Don't commit canaricide by cannon.

And how would you redesign the C string interface to solve your
conundrum?

I don't view the argument as strong since the C library itself has
that problem, and there isn't a lot of complaint about it either that
I've seen. Like all the str* functions, using a linked list library
would take a while to learn the feel of. Whether you continue to use
depends on how easy or hard it makes your life. One thing that lacks
in GLib's documentation is a good set of examples that demonstrate how
to use the list in certain use cases. The examples are tedious and
difficult to make relevant, so I can understand why they aren't
there. Contrast this with the std::list where several books have been
written to document usage, pitfalls, and the like.

I still go back and forth between whether I want to use the GLib style
where you have something like.

1. c_list_t* c_list_remove( c_list_t* list, c_list_t* node,
c_free_function_t free_fn );

\code fragment
node = c_list_search( list, "Find Me", c_vstrcmp );
if ( node ) {
list = c_list_remove( list, node, c_free );
}
\endcode

If you forget the 'list =' and instead have

\code fragment
node = c_list_search( list, "Find Me", c_vstrcmp );
if ( node ) {
c_list_remove( list, node, c_free );
}
\endcode

You introduce a subtle bug where if 'node' is the head of the list,
you've got serious problems.

If I use a c_list_t** instead, I don't need to make the user assign
the result back into the list. Does this make the interface bad? I'm
not sure. But I still think that a function interface that abstracts
the complicated stuff in a linked list is worthwhile.

Best regards,
John D.

 

[bartc]

Writing a linked list isn't very complex, but I prefer to spend my time on
the main program I'm writing, rather than having to rewrite the low level
data structures every time I need one.

If I had access to such a generic linked list library, I'm not even sure I
would what to do with it.

I use linked lists a fair bit, but mostly each node exists in several
different linked lists simultaneously. Usually there are some up/down links
as well (the list forms part of a tree).

In the few cases I have a list forming a single chain, that tends to be a
'tight' structure that needs to be super-efficient, or that is somehow
special (for example part of a memory allocator; then the generic routine
can't allocate or free the memory for it; it *is* the memory!)

I also rarely use doubly-linked lists, so a 'prev' field would be wasted in
a generic routine.

And since it seems that custom create()/free() routines might be required
anyway, it's a simple matter to also do a couple of custom routines to do
whatever it is your generic code might do, but without the headaches of
making them fit into an awkward generic framework, and working out how to
get the data in or out, or even where it's located!

In short, I agree with Eric...

It's just more practical to
have a toolbox with well tested code that can be reused every time you
need it.

But offset by the extra difficulties of trying to make generic routines fit
every situation. Perhaps have the tested, generic code, but in
pseudo-language pinned up near your desk. Then it can be adapted as
required. A bit like templates..

 

[jacob navia]

bartc a écrit :

If I had access to such a generic linked list library, I'm not even sure I
would what to do with it.

I use linked lists a fair bit, but mostly each node exists in several
different linked lists simultaneously. Usually there are some up/down links
as well (the list forms part of a tree).

In the case of a custom data structure the generic list can't be OK.

I agree.

In the few cases I have a list forming a single chain, that tends to be a
'tight' structure that needs to be super-efficient, or that is somehow
special (for example part of a memory allocator; then the generic routine
can't allocate or free the memory for it; it *is* the memory!)

In the container library in this case you would use a list of pointers.
A list of pointers allocates just memory for a pointer at each addition.

In case you want to avoid ANY allocation, you write a custom allocator
that allocates from a fixed pool for instance.

I also rarely use doubly-linked lists, so a 'prev' field would be wasted in
a generic routine.

The container library offers single and double linked lists for that
reason.

And since it seems that custom create()/free() routines might be required
anyway, it's a simple matter to also do a couple of custom routines to do
whatever it is your generic code might do, but without the headaches of
making them fit into an awkward generic framework, and working out how to
get the data in or out, or even where it's located!

Yes. That is why we find many hastily written list routines in each
application, all full of bugs because testing them was skipped because
they are so 'trivial' to write.

Then, the lack of standards makes each of them incompatible and needing
an adapter to work with other lists, etc etc.

In short, I agree with Eric...




But offset by the extra difficulties of trying to make generic routines
fit every situation. Perhaps have the tested, generic code, but in
pseudo-language pinned up near your desk. Then it can be adapted as
required. A bit like templates..

Much better to write them in C and expand them at each occasion with a
simple utility.

 

[Phil Carmody]

jacob navia wrote:
) Which of
)
) strcpy(dst,src);
)
) or
) for (int i = 0; i<=strlen(src);i++) // [I added an 'i']
) dst = src;
)
) is clearer?

Given that they do different things, you can't compare clarity.

You're missing the point, which would have been illustrated
by the following:

Which of

strcpy(src, dst);

or

for (i = 0; dst != 0; i++)
src = dst;

is clearer ?

Well, both clearly have issues, so does that make them
equally clear?

Phil

 

[jacob navia]

Phil Carmody a écrit :

jacob navia wrote:
) Which of
)
) strcpy(dst,src);
)
) or
) for (int i = 0; i<=strlen(src);i++) // [I added an 'i']
) dst = src;
)
) is clearer?

Given that they do different things, you can't compare clarity.

Step 0: The first character of src is copied into dst. If src
has length zero, the terminating zero is copied
Step 1: If the length of the source is greater than zero
the second character is copied.

etc


You are wrong (again) carmody.

Note the <=, that means that the terminating zero is copied.
Note that neither src nor dst are touched: they point always to
the start of the source and destination buffers.