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

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


as-per the following posts:

http://groups.google.com/group/comp....2427988fd2d7ba

http://groups.google.com/group/comp....5b682969ce746d


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?

Chris Thomasson <cristom@comcast.net> wrote:
> Here is some example code for a container API for this group to use:
>
> http://appcore.home.comcast.net/web/
<snip>
> 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.

"William Ahern" <william@wilbur.25thandClement.com> wrote in message
news:gdefu4-82q.ln1@wilbur.25thandClement.com...
> Chris Thomasson <cristom@comcast.net> wrote:
>> Here is some example code for a container API for this group to use:
>>
>> http://appcore.home.comcast.net/web/
> <snip>
>> 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:

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



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

Wow; Thats a lot of macros!

http://groups.google.com/group/comp....00ced20ca06399

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

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

Chris Thomasson <cristom@comcast.net> wrote:
> "William Ahern" <william@wilbur.25thandClement.com> wrote in message
> news:gdefu4-82q.ln1@wilbur.25thandClement.com...
> > Chris Thomasson <cristom@comcast.net> wrote:
> >> Here is some example code for a container API for this group to use:
> >>
> >> http://appcore.home.comcast.net/web/
> > <snip>
> >> 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:
>
> 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.

Chris Thomasson wrote:
>
> 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?

--
Chuck F (cbfalconer at maineline dot net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net>



--
Posted via a free Usenet account from http://www.teranews.com

>Chris Thomasson <cristom@comcast.net> wrote:
>> Here is some example code for a container API ...

In article <gdefu4-82q.ln1@wilbur.25thandClement.com>
William Ahern <william@wilbur.25thandClement.com> wrote:
>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 ...

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.]
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
email: forget about it http://web.torek.net/torek/index.html
Reading email is like searching for food in the garbage, thanks to spammers.

"Chris Thomasson" <cristom@comcast.net> wrote in message
news:w--dnVMAB78xyojanZ2dnUVZ_t6onZ2d@comcast.com...
> 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.

--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm

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.

--
pete

pete wrote:
> 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.
>
Nor I. Singly linked fits my needs.
<nit>
That would be doubly linked..
</nit>

--
Joe Wright
"Everything should be made as simple as possible, but not simpler."
--- Albert Einstein ---

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.

--
Tor <torust [at] online [dot] no>

C-FAQ: http://c-faq.com/

"Malcolm McLean" <regniztar@btinternet.com> wrote in message
news:37ydnTyP4pHk4YvanZ2dneKdnZylnZ2d@bt.com...
>
> "Chris Thomasson" <cristom@comcast.net> wrote in message
> news:w--dnVMAB78xyojanZ2dnUVZ_t6onZ2d@comcast.com...
>> 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();

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) {
[...]
}

"Tor Rustad" <tor_rustad@hotmail.com> wrote in message
news:loudnTECII5BMIvaRVnzvQA@telenor.com...
> 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.

Fine.

"Chris Thomasson" <cristom@comcast.net> wrote in message
news:1PCdnWf3abfSIIvanZ2dnUVZ_rGrnZ2d@comcast.com. ..
[...]
> typedef struct my_node_s {
> clc_slink link;
> [... data ...];
> } my_node;
>
>

Yikes! Forgot a parenthesis:


> my_node* const _this =
> clc_slist_push(..., malloc(sizeof(*_this));
^^^^^^^^^^^^^^^^^^^^^^^^^^^


my_node* const _this =
clc_slist_push(..., malloc(sizeof(*_this)));


> if (_this) {
> [...]
> }

"Malcolm McLean" <regniztar@btinternet.com> wrote in message
news:37ydnTyP4pHk4YvanZ2dneKdnZylnZ2d@bt.com...
>
> "Chris Thomasson" <cristom@comcast.net> wrote in message
> news:w--dnVMAB78xyojanZ2dnUVZ_t6onZ2d@comcast.com...
[...]
> 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*);



?

On Tue, 16 Oct 2007 17:06:41 -0700, "Chris Thomasson"
<cristom@comcast.net> wrote:

>"William Ahern" <william@wilbur.25thandClement.com> wrote in message

[snip]

>> http://cvsweb.netbsd.org/bsdweb.cgi/src/sys/sys/queue.h
>> http://cvsweb.netbsd.org/bsdweb.cgi/src/sys/sys/tree.h
>
>Wow; Thats a lot of macros!

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

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

On Thu, 18 Oct 2007 05:56:09 +0000, Richard Heathfield
<rjh@see.sig.invalid> wrote:

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

--
jaysome

Richard Heathfield wrote:
> 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.

--
Philip Potter pgp <at> doc.ic.ac.uk

"Chris Thomasson" <cristom@comcast.net> writes:

> 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/*...e=text%2Fplain

Implementation:
http://cvs.savannah.gnu.org/viewvc/*...e=text%2Fplain

Tests:
http://cvs.savannah.gnu.org/viewvc/*...e=text%2Fplain

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.
--
Ben Pfaff
http://benpfaff.org

On Wed, 17 Oct 2007 21:52:40 -0700, jaysome wrote:

> On Tue, 16 Oct 2007 17:06:41 -0700, "Chris Thomasson"
> <cristom@comcast.net> wrote:
>
>>"William Ahern" <william@wilbur.25thandClement.com> wrote in message
>
> [snip]
>
>>> http://cvsweb.netbsd.org/bsdweb.cgi/src/sys/sys/queue.h
>>> http://cvsweb.netbsd.org/bsdweb.cgi/src/sys/sys/tree.h
>>
>>Wow; Thats a lot of macros!
>
> 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:
>
<snip>

I guess the consideration was nothing to do with speed, but rather to
provide polymorphism without resorting to void*s.

Ben Pfaff wrote:
> Header:
> http://cvs.savannah.gnu.org/viewvc/*...e=text%2Fplain
>

i expected much briefer api
imho
find_equal
find_if
find_adjacent
(and a few more)
is not needed if a simple way is provided to walk through the list
it seems to designed with c++ stl in mind, but that's not a desired
approach here imho

(who would use find_if(arr, len, pred) when we can 'for(..) if
(pred(arr[i])) ..' which is much more flexible)

also a linkedlist with locking would be more attractive (eg for
multithread comminication queue)
(so there are practical aspects, not just the academic pure form of
datastructures)

Szabolcs Nagy <nszabolcs@gmail.com> writes:

> Ben Pfaff wrote:
>> Header:
>> http://cvs.savannah.gnu.org/viewvc/*...e=text%2Fplain
>
> i expected much briefer api
> imho
> find_equal
> find_if
> find_adjacent
> (and a few more)
> is not needed if a simple way is provided to walk through the list
> it seems to designed with c++ stl in mind, but that's not a desired
> approach here imho

You're not required to use every function in the API. Certainly
'for' statements are superior to such functions in many cases.

> also a linkedlist with locking would be more attractive (eg for
> multithread comminication queue)

I really don't expect that it will ever be possible to get
everyone in comp.lang.c to agree on a single API for anything,
let alone for anything as complicated as a linked list.
--
"Large amounts of money tend to quench any scruples I might be having."
-- Stephan Wilms

Richard Heathfield wrote:
> 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).

The advantage of looking there, is that several clever people actually
have used the this API, so it will be more mature than something homegrown.

The generated doc is available e.g. here:

http://www.gelato.unsw.edu.au/~dsw/p...cs/kernel-api/

--
Tor <torust [at] online [dot] no>

C-FAQ: http://c-faq.com/

Tor Rustad said:

<snip>

> The advantage of looking there, is that several clever people actually
> have used the this API, so it will be more mature than something
> homegrown.

I thought you weren't keen on clever people? :-)

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999