Pre-Alpha CLC Standard Container API Proposal...

W

William Ahern

Chris Thomasson said:
Here is some example code for a container API for this group to use:

http://appcore.home.comcast.net/web/
So far, it only has single/double linked list. Before I post any more
implementations, I want to see if we can agree on their API's.

Any thoughts?

Why are you re-creating the wheel:

http://cvsweb.netbsd.org/bsdweb.cgi/src/sys/sys/queue.h
http://cvsweb.netbsd.org/bsdweb.cgi/src/sys/sys/tree.h

The former is like 20 years old, and possibly one of the most widely re-used
source code in existence.

In all likely hood, if you're on a Unix or Unix derivative, you actually
have a file /usr/include/sys/queue.h. Point being, thought it's not standard
C per se, its about as close to a universal implementation in C as anybody
will ever get.
 
C

Chris Thomasson

William Ahern said:
Why are you re-creating the wheel:

It could possibly be a good resource for newbie's to learn how to define
API's and implementations of various collection primitives, in Standard C.
Also, it might soak up some of the complaints wrt C not having standard
container library. This seems to confuse people into thinking that C is
overly complicated...



Wow; Thats a lot of macros!

http://groups.google.com/group/comp.lang.c/msg/6600ced20ca06399

:^0



The former is like 20 years old, and possibly one of the most widely
re-used
source code in existence.
In all likely hood, if you're on a Unix or Unix derivative, you actually
have a file /usr/include/sys/queue.h. Point being, thought it's not
standard
C per se, its about as close to a universal implementation in C as anybody
will ever get.


Okay.
 
C

Chris Thomasson

Types:
clc_slist, clc_slink
clc_dlist, clc_dlink

API:
void* clc_slink_init(clc_slink*, clc_slink*);
void* clc_slink_next(clc_slink const*);
void* clc_slist_init(clc_slist*, clc_slink*);
void* clc_slist_head(clc_slist const*);
void* clc_slist_push(clc_slist*, clc_slink*);
void* clc_slist_pop(clc_slist*);
void* clc_dlink_init(clc_dlink*, clc_dlink*, clc_dlink*);
void* clc_dlink_next(clc_dlink const*);
void* clc_dlink_prev(clc_dlist const*);
void* clc_dlist_init(clc_dlist*, clc_dlink*, clc_dlink*);
void* clc_dlist_head(clc_dlist const*);
void* clc_dlist_tail(clc_dlist const*);
void* clc_dlist_push_head(clc_dlist*, clc_dlink*);
void* clc_dlist_push_tail(clc_dlist*, clc_dlink*);
void* clc_dlist_pop_head(clc_dlist*, clc_dlink*);
void* clc_dlist_pop_tail(clc_dlist*, clc_dlink*);
void* clc_dlist_pop(clc_dlist*);
 
W

William Ahern

Chris Thomasson said:
It could possibly be a good resource for newbie's to learn how to define
API's and implementations of various collection primitives, in Standard C.

Granted.
 
C

CBFalconer

Chris said:
Types:
clc_slist, clc_slink
clc_dlist, clc_dlink

API:
void* clc_slink_init(clc_slink*, clc_slink*);
void* clc_slink_next(clc_slink const*);
void* clc_slist_init(clc_slist*, clc_slink*);
void* clc_slist_head(clc_slist const*);
void* clc_slist_push(clc_slist*, clc_slink*);
void* clc_slist_pop(clc_slist*);
void* clc_dlink_init(clc_dlink*, clc_dlink*, clc_dlink*);
void* clc_dlink_next(clc_dlink const*);
void* clc_dlink_prev(clc_dlist const*);
void* clc_dlist_init(clc_dlist*, clc_dlink*, clc_dlink*);
void* clc_dlist_head(clc_dlist const*);
void* clc_dlist_tail(clc_dlist const*);
void* clc_dlist_push_head(clc_dlist*, clc_dlink*);
void* clc_dlist_push_tail(clc_dlist*, clc_dlink*);
void* clc_dlist_pop_head(clc_dlist*, clc_dlink*);
void* clc_dlist_pop_tail(clc_dlist*, clc_dlink*);
void* clc_dlist_pop(clc_dlist*);

What, if anything, is this?
 
C

Chris Torek


Not *that* old. <sys/queue.h> came out of me complaining[%] to Kirk
McKusick about the CMU macros, which the BSD code had picked up
along with the CMU Mach VM system. So, we did the usual Berkeley
thing, which has sometimes been referred to as "peeing on the code
to make it smell different". :)

The macros in NetBSD and FreeBSD are somewhat modified from the
original Berkeley versions, but the three "most basic" kinds of
lists-and-queues ("lists", "tail queues", and "circle queues") were
in the first released version.

[% In particular, I disliked the fact that one could provide the
"wrong" field names to the CMU macros, which would then run amok
without a peep from the compiler. The BSD ones are type-safe, if
used correctly at least. Also, the CMU macros came in just one
flavor, if I remember right. The queue(3) man page explains the
reason for the three kinds -- or now, six kinds, apparently -- in
BSD.]
 
M

Malcolm McLean

Chris Thomasson said:
Types:
clc_slist, clc_slink
clc_dlist, clc_dlink

API:
void* clc_slink_init(clc_slink*, clc_slink*);
void* clc_slink_next(clc_slink const*);
void* clc_slist_init(clc_slist*, clc_slink*);
void* clc_slist_head(clc_slist const*);
void* clc_slist_push(clc_slist*, clc_slink*);
void* clc_slist_pop(clc_slist*);
void* clc_dlink_init(clc_dlink*, clc_dlink*, clc_dlink*);
void* clc_dlink_next(clc_dlink const*);
void* clc_dlink_prev(clc_dlist const*);
void* clc_dlist_init(clc_dlist*, clc_dlink*, clc_dlink*);
void* clc_dlist_head(clc_dlist const*);
void* clc_dlist_tail(clc_dlist const*);
void* clc_dlist_push_head(clc_dlist*, clc_dlink*);
void* clc_dlist_push_tail(clc_dlist*, clc_dlink*);
void* clc_dlist_pop_head(clc_dlist*, clc_dlink*);
void* clc_dlist_pop_tail(clc_dlist*, clc_dlink*);
void* clc_dlist_pop(clc_dlist*);
Firstly, why not make that

ll_pop()
ll_next();

etc.

No one wants to write out all those words. Remember that quite often these
calls will be used in expressions. A for loop with three four-word
identifiers will rapidly get unreadable.

Also, if you are using the linked list as a queue, why not take void *s? Why
are you returning void *s when the returns in the code are clc_slink *consts
?

Finally, do we need singly linked lists? You seem to be doubling the size of
the api for no added functionality.

The snag you've got is that people want a linked list with data in it.
They want to go

for(ptr = head(list); ptr != 0; ptr = next(list))
{
/* forget all about linked lists, use ptr */
}

they also want

ptr = head(list);
while(ptr)
{
/* maybe we need to add something */
if( someconditon)
insertafter(list, ptr, newdata);
/* or maybe delete */
if( anothercodition )
delete(list, ptr);
/* and we want to trot through the list doing this in each place */
ptr = next(list);
}

unfortunately even one of these is difficult to provide. Supporting both
cleanly is virtually impossible. However the closer you get to it, the more
usable the library will be.
 
P

pete

Malcolm McLean wrote:
Finally, do we need singly linked lists?

I use singly linked lists to store lines of text files.

I've never used a doubley linked list for anything.
 
J

Joe Wright

pete said:
I use singly linked lists to store lines of text files.

I've never used a doubley linked list for anything.
Nor I. Singly linked fits my needs.
<nit>
That would be doubly linked..
</nit>
 
T

Tor Rustad

Chris Thomasson wrote:

[...]
So far, it only has single/double linked list. Before I post any more
implementations, I want to see if we can agree on their API's.

sorry, I didn't look
Any thoughts?

If I needed this, I would rather look at the Linux kernel sources.
 
C

Chris Thomasson

Malcolm McLean said:
Firstly, why not make that

ll_pop()
ll_next();

I need to prefix with a namespace.


[...]
Also, if you are using the linked list as a queue, why not take void *s?
Why are you returning void *s when the returns in the code are clc_slink
*consts [...]
The snag you've got is that people want a linked list with data in it.
They want to go
[...]

You can't figure out how to store data in the list? Easy:


typedef struct my_node_s {
clc_slink link;
[... data ...];
} my_node;


my_node* const _this =
clc_slist_push(..., malloc(sizeof(*_this));
if (_this) {
[...]
}
 
C

Chris Thomasson

Malcolm McLean said:
news:[email protected]... [...]
Firstly, why not make that

ll_pop()
ll_next();

etc.

No one wants to write out all those words. Remember that quite often these
calls will be used in expressions. A for loop with three four-word
identifiers will rapidly get unreadable.


Is this better:



Types:
clc_slist, clc_slink
clc_dlist, clc_dlink

API:
void* clc_slinit(clc_slink*, clc_slink*);
void* clc_slnext(clc_slink const*);
void* clc_slinit(clc_slist*, clc_slink*);
void* clc_slhead(clc_slist const*);
void* clc_slpush(clc_slist*, clc_slink*);
void* clc_slpop(clc_slist*);
void* clc_dlinit(clc_dlink*, clc_dlink*, clc_dlink*);
void* clc_dlnext(clc_dlink const*);
void* clc_dlprev(clc_dlist const*);
void* clc_dlinit(clc_dlist*, clc_dlink*, clc_dlink*);
void* clc_dlhead(clc_dlist const*);
void* clc_dltail(clc_dlist const*);
void* clc_dlpushhead(clc_dlist*, clc_dlink*);
void* clc_dlpushtail(clc_dlist*, clc_dlink*);
void* clc_dlpophead(clc_dlist*, clc_dlink*);
void* clc_dlpoptail(clc_dlist*, clc_dlink*);
void* clc_dlpop(clc_dlist*);



?
 
J

jaysome


Indeed.

What strikes me as curious is the reason why the authors of this code
decided to use macros instead of functions (in this day and age, you
should never choose to use macros over functions, especially since we
have inline capability with the C99 standard).

Macros are arguably prodigiously harder to maintain than functions.
Macros lead to increased code size compared to functions. The only
reason I can think of for using macros over functions is speed--and
that is only acceptable if it has been shown that:

1. The code was implemented with functions first.
2. Profiling results showed that the use of functions had a
substantial negative impact on program throughput.
3. Profiling results showed that using macros instead of functions had
a substantial positive impact on program throughput.

I'd be curious to hear from the authors whether the above steps were
followed. I suspect the authors "assumed" that the use of macros was a
forgiven conclusion and they didn't even consider using functions
instead, without considering the ramifications of their decision. As
always, I could be wrong.

Best regards
 
R

Richard Heathfield

Tor Rustad said:
Chris Thomasson wrote:

[...]
So far, it only has single/double linked list. Before I post any more
implementations, I want to see if we can agree on their API's.

sorry, I didn't look
Any thoughts?

If I needed this, I would rather look at the Linux kernel sources.

Indeed. And I'd rather gnaw off my own leg than look at the Linux kernel
sources (again).
 
J

jaysome

Tor Rustad said:
Chris Thomasson wrote:

[...]
So far, it only has single/double linked list. Before I post any more
implementations, I want to see if we can agree on their API's.

sorry, I didn't look
Any thoughts?

If I needed this, I would rather look at the Linux kernel sources.

Indeed. And I'd rather gnaw off my own leg than look at the Linux kernel
sources (again).

And I'd rather tear out my right eyeball and replace it with a wood
one than to look at said source.

<joke>
jaysome: "Hi Richard, would you like to dance with me?"
Richard: "Would I, would I!"
jaysome: "Peg leg, peg leg." (jaysome walks away, incensed that the
target of his invitation would have the nerve to not just accept it
and instead make fun of jaysome's wood eye).
</joke>
 
P

Philip Potter

Richard said:
Tor Rustad said:
Chris Thomasson wrote:

[...]
So far, it only has single/double linked list. Before I post any more
implementations, I want to see if we can agree on their API's.
sorry, I didn't look
Any thoughts?
If I needed this, I would rather look at the Linux kernel sources.

Indeed. And I'd rather gnaw off my own leg than look at the Linux kernel
sources (again).

*brandishes kernel sources menacingly*

Phil

PS I feel the word "brandish" doesn't get enough usage.
 
B

Ben Pfaff

Chris Thomasson said:
Here is some example code for a container API for this group to use:

http://appcore.home.comcast.net/web/

I have a very complete and well-tested linked-list API available
here:

Header:
http://cvs.savannah.gnu.org/viewvc/...oot=pspp&revision=1.5&content-type=text/plain

Implementation:
http://cvs.savannah.gnu.org/viewvc/...oot=pspp&revision=1.5&content-type=text/plain

Tests:
http://cvs.savannah.gnu.org/viewvc/...oot=pspp&revision=1.8&content-type=text/plain

I think that the code is almost, but not quite, "comp.lang.c
acceptable". Also, at some point I should benchmark and possibly
rewrite the list sorting implementation.

Sorry about the excessively long URLs.

There's also a version that uses "void *"s at similar URLs to the
above.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top