Problem with a linked list

[websnarf]

I see. Do you avoid classes, "new", exceptions, and all other C++
features so that your C++ code can be compiled with a C compiler?

Who says I write C++ code? I *do* write code that other people
consume. I *do* know that C++ compilers are still being maintained
while C compilers are basically being relegated to legacy support --
meaning that the differences I see in performance today will only
increase over time.

 

[websnarf]

[...] It seems that the OP wants a pointer to the tail of the
list for some reason unknown.

Unknown?!?! Look closely. It causes the algorithm to stop
attempting to add nodes. It is essentially a simple feedback
that lets you know that you are out of memory (or more generally
that an add_item has failed).

Which is a wrong way to handle such situations. If add_item()
fails, it should return a failure status, not fiddle with a
pointer.

Explain how this is wrong.

Besides, the OP's code never even checks what happens to that
pointer. If malloc() returns a null pointer, it merrily writes
through it as if nothing untoward has happened.

You might have noticed I rewrote a lot of the OP's code.

Make add_item() an int function rather than void, return a
success value, and for heavens' sake, _check_ that malloc()
succeeded!

Ok, these semantics are so far almost isomorphic to what I have
provided. Of course I don't have additional concepts such as a "error
status" in there. You just compare the tail iterator against NULL
instead of checking for a particular error code, but its the same
thing.

But there's a slight advantage to my method -- you can *ignore* the
error in your inner loops, and no harm will come of it, while retaining
this error condition that you can check after your inner loop is done.
This helps solve the common problem of control-code spaghetti when
dealing with errors (since C doesn't have exception handling.)

Alternatively, make add_item() return a struct list *, to
the added member if succesful, null if not.

Ok, go back and review my design. The iteration happens by taking an
iterator as input, and giving the iterator back as output. In this
case I chose the address of the last link pointer because its trivial
to initialize, allows you to avoid the "empty case" differentiation,
and is a single parameter the can be efficiently returned or passed as
a single parameter.

If I point to something artificial like the last entry after its been
added (the fact that this is artificial is the point I was trying to
make), then this complicates either initialization, or requires more
input parameters, or more output parameters, etc.

My way is less code, fewer sematics, and really exposes the core
functionality required to support linked lists with an append
operation. This should be more conducive to learning how linked lists
work, which I surmised that the OP would be helped by.

And ditto on malloc().

Huh? There is no "unchecked dereferencing" in the code I supplied
(except for the strlen() call, but by being "static" I assumed that the
programmer would limit the exposure, and "coddle" that function
correctly.)

 

[Chris Croughton]

Nobody else brought it up either. This doesn't tell you something?

It could tell you that most people aren't interested in arguing with you
and have you in their killfiles. Or that it's Tuesday and people are
worrying about the weather, or lots of other things...

[...] CBFalconer's "On the contrary" was in response to your
claim that portability is not an issue in this newsgroup. In fact,
portability is an always has been an extremely important issue in
this newsgroup.

I simply don't think that's the case.

Have you read comp.lang.c? It often seems that portability is the only
thing which matters in clc...

That's not true. Many people who write C++ code, also really write a
lot of C code.

Interesting assertion, I seem to be about the only one I know
personally. In my experience most people who write C++ don't write C
unless they have to do so.

And therefore also consume C code written by others.

When they do, it is usually compiled as C and then linked (often as a
library), just as they use code written in Fortran, Pascal, assembler,
etc.

Its not rare at all. C++ people don't use entirely different concepts
to implement linked lists.

Yes they do, C++ programmers use the STL list template (or the Boost
ones). Real C++ programmers, that is, rather than people who just use
it as a dialect of C. Try making that comment on comp.lang.c++ and
watch the flames.

[...] That's what C compilers are for. Code compiled with C++
compilers is called C++; there are several newsgroups dedicated to
it.

Just because you decide to live in a small little cubby hole doesn't
mean that other people have chosen to do the same. The WATCOM C++
compiler, often produces substantially faster code than their C
compiler, BTW.

There are Fortran compilers which probably produse faster code than
both. So?

Not casting malloc() masks the error of not being able to compile with
a C++ compiler. Of the two points of view, which do you think is more
aligned to the issue of portability?

Casting malloc() masks the much bigger error of using malloc() in C++ at
all (C++ programmers would call it evil). But then you aren't a C++
programmer, are you?

Portability is not about being able to compile code written for one
language with a compiler designed for a different language, it's about
being able to compile and use the /same/ language on different
implementations and systems.

Chris C

 

[CBFalconer]

Who says I write C++ code? I *do* write code that other people
consume.

So? There are hamburger chains that produce food out of bad meat,
and whose consumers become sick. Some die. No extra charge for
ptomaine.

I *do* know that C++ compilers are still being maintained
while C compilers are basically being relegated to legacy support --
meaning that the differences I see in performance today will only
increase over time.

FYI compilers generally do not require revision unless the language
changes. The modern practice is to compile to an intermediate
form, which is then fed to the optimizers and code generators.
This area is undergoing continuous revision to improve optimization
and adapt to new hardware. It is also language independant by
design. It works best when the compiler front end has been able to
diagnose and reject any errors. Foolish techniques such as useless
casts (in C) prevent this.

 

[Mark McIntyre]

Which basically dont exist. Therefore its not portable. Just how
shallow are your powers of reasoning?

Apparently deeper than yours. I know of almost no compiler that won't
accept // comments, and several even do so when in fully compliant
mode.
Are you stuck in a timewarp?

 

[Ben Pfaff]

Apparently deeper than yours. I know of almost no compiler that won't
accept // comments, and several even do so when in fully compliant
mode.

That's a contradiction in terms. Support for // comments means
that a compiler is not fully compliant (to C89).

 

[Old Wolf]

Not casting malloc() masks the error of not being able to compile
with a C++ compiler. Of the two points of view, which do you
think is more aligned to the issue of portability?

Your entire program has the error of not being able to compile
with a Java compiler. You'd better delete the code (I sure have).

 

[Keith Thompson]

That's a contradiction in terms. Support for // comments means
that a compiler is not fully compliant (to C89).

Not necessarily. A conforming C89 compiler is free to accept //
comments, as long as it issues a diagnostic for them. (Though I think
there may be some obscure cases where recognizing // as a comment
delimiter makes the difference between two different interpretations
of some code.)

 

[websnarf]

Apparently deeper than yours. I know of almost no compiler that won't
accept // comments, and several even do so when in fully compliant
mode.
Are you stuck in a timewarp?

No. But perhaps gcc is. You need to pass it a "-std=c99" (which puts
it into this meaningless mode, where it compiles to no existing
standard) to trick it into accepting the //s.

Remind me ... you are the one who suggested me that empty strings are
illegal right?

 

[websnarf]

It could tell you that most people aren't interested in arguing with you
and have you in their killfiles.

Oh yeah I certainly noticed this ... you can tell by who everyone is
replying to in this thread.

[...] CBFalconer's "On the contrary" was in response to your
claim that portability is not an issue in this newsgroup. In fact,
portability is an always has been an extremely important issue in
this newsgroup.

I simply don't think that's the case.

Have you read comp.lang.c?

Only on and off for about 15 years.

[...] It often seems that portability is the only thing which
matters in clc...

You are mistaking standards lawyering for concern for portability.
There's a question of supporting what's there, and there's what you
*believe* is supposed to be there.

Interesting assertion, I seem to be about the only one I know
personally.

Well I don't know who you know personally, but interesting that you
didn't have to look far to find one.

[...] In my experience most people who write C++ don't write C
unless they have to do so.

Really? I've seemed to see a lot of beginners in C++ who don't
understand that distinction who end up writing a lot of C code,
unknowingly, because they happen to not need to the C++ machinery for
some of their code.

When they do, it is usually compiled as C and then linked (often as a
library), just as they use code written in Fortran, Pascal, assembler,
etc.

That only works in C if you are willing to write 'extern "C"' around
all your C .h files. A much simpler way is to recompile the C code
with your C++ compiler.

Yes they do, C++ programmers use the STL list template (or the Boost
ones).

For a linked list? Maybe a vector, which is a different thing. But
not for a linked list.

[...] Real C++ programmers, that is, rather than people who just use
it as a dialect of C. Try making that comment on comp.lang.c++ and
watch the flames.

Well, they will tell me to use a "stack" or a "deque" depending on
which I want to use.

[...] That's what C compilers are for. Code compiled with C++
compilers is called C++; there are several newsgroups dedicated to
it.

Just because you decide to live in a small little cubby hole doesn't
mean that other people have chosen to do the same. The WATCOM C++
compiler, often produces substantially faster code than their C
compiler, BTW.

There are Fortran compilers which probably produse faster code than
both. So?

It costs a lot to port your code between Fortran and C. Making your
code C and C++ compatible is fairly straightforward, and you get the
speed increases from upgrading compilers at much more reasonable cost.

C as a language is clearly in decline, while C++ is not (though a lot
of its mindshare got robbed by Java.) And vendors who make C compilers
generally make C and C++ combined products. That means in the long
run, the vendor will treat their C compiler as a "checkmark" while
treating their C++ compiler as the focus of all serious future
development.

Its just practical considerations. If you write code with works in C
and C++, then your code gets faster without changes just by waiting for
compilers to get better. If you make it C-only, then it stays at the
current performance level, and can only improve by paying for hardware
upgrades.

Casting malloc() masks the much bigger error of using malloc() in C++ at
all (C++ programmers would call it evil). But then you aren't a C++
programmer, are you?

Excuse me? C++ does not expose an equivalent to "realloc()" in their
new/delete concepts. So using malloc in C++ is not wrong, its just not
generally used for base-object memory management.

Portability is not about being able to compile code written for one
language with a compiler designed for a different language, it's about
being able to compile and use the /same/ language on different
implementations and systems.

You must be from the Scott McClelland/Ari Fliescher school of
definitionism. Portability refers to using one code based on many
different platforms (and compilers) when talking about code, and making
sure the semantics are equivalent on different platforms when talking
about whole applications.

Making sure a language works on multiple platforms? In what universe
is that not just "standardization"?

 

[Walter Roberson]

C as a language is clearly in decline, while C++ is not (though a lot
of its mindshare got robbed by Java.) And vendors who make C compilers
generally make C and C++ combined products. That means in the long
run, the vendor will treat their C compiler as a "checkmark" while
treating their C++ compiler as the focus of all serious future
development.

My understanding (perhaps incorrect) is that most serious
development for procedural compilers these days is based upon
having a parser layer that produces intermediate code, with all
the optimization done at the intermediate code level. The
bulk of the work is in the optimization phases, so even if the
parsers get tuned differently, the optimization phases and generated
code grow at the same rate for all the compilers implimented
on the common platform.

There could certainly be differences in the prioritization of
library implementations, or of prioritization of feature change
implementation, but the effect is somewhat different than implied
by your paragraph.


I am not convinced that "C as a language is clearly in decline".
It might perhaps have a lower percentage of the market than it once
did, but the market is expanding.

I think whether I implemented in C or C++ would depend a fair bit
upon political factors (for stuff I'm paid to do); but when given
the choice of languages, my determination would depend on
tradeoffs between efficiency and program structure. There are an
amazing number of applications that don't *need* classes.

C++ as a development methodology is based upon the premise that
you will put together a library of objects and that the world will
rejoice and yeah verity the virtual classes will be fruitful
all the days of thy life. The reality is somewhat different:
yup, there are definitely some things that get implimented
over and over again that can be shared, but there is so much
application-specific logic that (according to some material I
was reading) -most- classes get used for at most 2 or 3 projects
and then get left behind. That's a lot of time spent finding
beautiful abstractions, that doesn't end up going very far...

So bring on the C for projects where one actually knows what one
is doing ahead of time, where one wants to write non-bloated code
to get in, do something, and get out again.

 

[Al Bowers]

Al Bowers wrote:

[...] It seems strange that you
would define a function add_item that will would adultrate
that precious tail pointer should function malloc return NULL.

Strange how?

I sorry, I meant adulterate.
By this I meant 'to tamper with'. Your "tail" and "tailptr"
are type struct list **, which you use as a pointer to the
pointer to the last node in the list. Now, should the malloc
fail some nodes into the the list construct,
the way you have written the code, variable tail and tailptr
become value NULL. This means you no longer have a pointer
to the end of the list. This is not a problem with the code
you have written because you simply prohibit any further
attempts to continue building the list and that you do
not need a valid tailptr for anything else. If one wanted to
attempt to free other memory areas and retry building, one
whould have to first traverse the list again to get a pointer
to the last node. My preference would be to have the tailptr
always point to the last node in the list or have value NULL
should there be no list.

However the above is not the reason the posted example is
broken. That involves another function.

 

[websnarf]

My understanding (perhaps incorrect) is that most serious
development for procedural compilers these days is based upon
having a parser layer that produces intermediate code, with all
the optimization done at the intermediate code level. The
bulk of the work is in the optimization phases, so even if the
parsers get tuned differently, the optimization phases and
generated code grow at the same rate for all the compilers
implimented on the common platform.

Yes, but it still takes quite a bit of work to translate from the
langauge level to this intermediate level. And it takes a lot of
testing to make sure its all working correctly. And different
languages will have different emphasis on optimization.

If a language vendor is not getting feedback about C, but is about C++,
and really cannot see C as anything other than "legacy support", then
regardless of how "modularly" they could do it, what would justify them
spending effort, going forward, on the older C compiler outside of
optimizing a few benchmarks?

There could certainly be differences in the prioritization of
library implementations, or of prioritization of feature change
implementation, but the effect is somewhat different than
implied by your paragraph.

This is what I mean. Any serious compiler vendor cannot view C as
anything other than an opportunity on a few fixed benchmarks, as well
as possible bug fix requests. This is why basically no vendor is
rushing to support the "C99" standard. Of the serious vendors, only
the gcc people (who are not beholden to a market driven considerations)
even made a serious go at full support. If you read the recent
slashdot article on gcc 4.0 you will see that C performance has not
changed at all -- in fact, the majority of the effort has gone towards
better C++ support.

I am not convinced that "C as a language is clearly in decline".

Ok ... about 10 years ago, there would be no question that C was the
dominant language. The best measures I have seen regarding mindshare
of C today is at about 30% (matched equally by C++ and Java.) The
direction of these trends is obvious. Look at schools today. They
don't teach C as a fundamental language -- they teach either C++ or
Java (or C# if they've been bribed by certain entities in the Pacific
Northwest.)

It might perhaps have a lower percentage of the market than it once
did, but the market is expanding.

That's like saying Apple's market is growing, even though their
percentage is going down. (By itself,) Its not a convincing argument
for software vendors to switch to just supporting the Mac.

Most new development is not done in C, unless for some reason, that's
the only thing the programmers know. At my previous place of
employment, we started with a C project, but as we started hiring more
developers, we concluded that there was enough C++ expertise amongst
them that we simply shifted the project into C++. I mean -- knowing C
is basically a subset of knowing C++, and we started in C -- and even
*that* was not enough of an argument to stay in C.

I think whether I implemented in C or C++ would depend a fair bit
upon political factors (for stuff I'm paid to do); but when given
the choice of languages, my determination would depend on
tradeoffs between efficiency and program structure. There are an
amazing number of applications that don't *need* classes.

Well, in fact, no applications need classes. That's not the point.
Most modern developers today simply *believe* programming with classes
is better. This causes a shift in mindshare, which causes a shift in
compiler development efforts etc.

C++ as a development methodology is based upon the premise that
you will put together a library of objects and that the world will
rejoice and yeah verity the virtual classes will be fruitful
all the days of thy life. The reality is somewhat different:
yup, there are definitely some things that get implimented
over and over again that can be shared, but there is so much
application-specific logic that (according to some material I
was reading) -most- classes get used for at most 2 or 3 projects
and then get left behind. That's a lot of time spent finding
beautiful abstractions, that doesn't end up going very far...

Trust me, I'm the last person on earth who would defend C++ as a
language. That isn't the point I was trying to make.

We are in a unique situation where C++ is starting to dominate over C,
certainly compiler development is shifting in that direction (and has
been for some years now), but we have the opportunity to take advantage
of the interesting fact that C++ is an approximation of a superset of
the C language. If you make your code compilable in C or C++, then you
get to leverage the ongoing improvements of C++ compilers while not
shifting your actual language and still remaining portable to C
compilers.

 

[Flash Gordon]

Yes, but it still takes quite a bit of work to translate from the
langauge level to this intermediate level. And it takes a lot of
testing to make sure its all working correctly. And different
languages will have different emphasis on optimization.

That work has *already* been done by the compiler vendors who know what
they are doing and therefore produce products worth using. They don't
need to redo it unless they change the definition of the intermediate
language, something that happens only rarely. On the rare occasions they
do change the intermediate language, they will change all the front ends
(including C) to use it so they only have one optimiser and code
generator to maintain. So that is completely irrelevant. So all
languages get the benefit of improvements to the optimiser.

If a language vendor is not getting feedback about C, but is about C++,
and really cannot see C as anything other than "legacy support", then
regardless of how "modularly" they could do it, what would justify them
spending effort, going forward, on the older C compiler outside of
optimizing a few benchmarks?

It has already been done on every compiler I've check since at least
'95. So there is no additional effort.

This is what I mean. Any serious compiler vendor cannot view C as
anything other than an opportunity on a few fixed benchmarks, as well
as possible bug fix requests. This is why basically no vendor is
rushing to support the "C99" standard. Of the serious vendors, only
the gcc people (who are not beholden to a market driven considerations)
even made a serious go at full support. If you read the recent
slashdot article on gcc 4.0 you will see that C performance has not
changed at all -- in fact, the majority of the effort has gone towards
better C++ support.

C still gets any changes to the optimiser since it uses the *same*
optimiser. It would be far more work to maintain a separate optimiser
for C. Support of C99 is a separate issue to the optimiser.

GNU have improved the speed of *compiling* C++. However, the C front end
does not have the same level of complexity and is more mature than the
C++ from end, so it does not have the same performance issues as the C++
front end. The same will apply to the libraries.

Ok ... about 10 years ago, there would be no question that C was the
dominant language. The best measures I have seen regarding mindshare
of C today is at about 30% (matched equally by C++ and Java.) The
direction of these trends is obvious. Look at schools today. They
don't teach C as a fundamental language -- they teach either C++ or
Java (or C# if they've been bribed by certain entities in the Pacific
Northwest.)


That's like saying Apple's market is growing, even though their
percentage is going down. (By itself,) Its not a convincing argument
for software vendors to switch to just supporting the Mac.

No one is suggesting that compiler vendors are, or should be, switching
to just supporting C. They support all languages they consider to be of
interest *including* C.

Most new development is not done in C, unless for some reason, that's
the only thing the programmers know. At my previous place of
employment, we started with a C project, but as we started hiring more
developers, we concluded that there was enough C++ expertise amongst
them that we simply shifted the project into C++. I mean -- knowing C
is basically a subset of knowing C++, and we started in C -- and even
*that* was not enough of an argument to stay in C.

Embedded work I used to be involved in was done in C rather than C++ for
a number of reasons which had absolutely nothing to do with the
languages known by the developers. I know this because as the first
developer in that section to start programming in C there I had to
actually learn C to do the job. We did not want the additional overheads
of an OO language or large libraries, we wanted something simple,
efficient, and supported on the widest range of HW possible including
small processors and DSPs.

Well, in fact, no applications need classes. That's not the point.
Most modern developers today simply *believe* programming with classes
is better. This causes a shift in mindshare, which causes a shift in
compiler development efforts etc.

The work to try to efficiently implement classes etc. does not break
efficient implementation of C. It just tries to bring C++ to the level C
has already reached.

Trust me, I'm the last person on earth who would defend C++ as a
language. That isn't the point I was trying to make.

We are in a unique situation where C++ is starting to dominate over C,
certainly compiler development is shifting in that direction (and has
been for some years now), but we have the opportunity to take advantage
of the interesting fact that C++ is an approximation of a superset of
the C language. If you make your code compilable in C or C++, then you
get to leverage the ongoing improvements of C++ compilers while not
shifting your actual language and still remaining portable to C
compilers.

The C front ends are in maintenance because they are mature products
that don't need major work unless you want to implement C99. The C++
front ends are still working towards that level of maturity. As to the
optimisers, as has been stated already they are common and so
improvements benefit both languages.

 

[Lawrence Kirby]

Not necessarily. A conforming C89 compiler is free to accept //
comments, as long as it issues a diagnostic for them. (Though I think
there may be some obscure cases where recognizing // as a comment
delimiter makes the difference between two different interpretations
of some code.)

Exactly, a conforming C90 compiler cannot accept // comments as doing so
would cause it to misinterpret some strictly conforming programs. The
cases aren't likely to occur in practice but that doesn't stop it being a
conformance issue. E.g.

#include <stdio.h>

int main(void)
{
printf ("%d\n", 10 //*
/**/ -2);
return 0;
}

should output -5 in C90 and 8 in C99.

Lawrence

 

[Default User]

Apparently deeper than yours. I know of almost no compiler that won't
accept // comments, and several even do so when in fully compliant
mode.

We ran the problem on the last project I worked on, the compiler (as
configured) didn't accept them. It's the cross-compiler for Tornado
AE653, with a PowerPC target. The makefile just calls the it ccppc, but
I'm sure it's some sort of gnu product, as pretty much all Tornado
stuff is.

Caused problems for some of the guys used to using // comments even in
C.




Brian

 

[Keith Thompson]

Exactly, a conforming C90 compiler cannot accept // comments as doing so
would cause it to misinterpret some strictly conforming programs. The
cases aren't likely to occur in practice but that doesn't stop it being a
conformance issue. E.g.

#include <stdio.h>

int main(void)
{
printf ("%d\n", 10 //*
/**/ -2);
return 0;
}

should output -5 in C90 and 8 in C99.

Yes, that's the kind of example I was trying (and failing) to
construct. (I didn't get the trick of using "-" as both a unary and a
binary operator.)

But a conforming C90 compiler could accept // comments as long as it
checks for cases like the above. If it sees a // comment that would
make the program illegal in C90, it can issue a diagnostic and accept
it. If it sees a // comment that would not make the program illegal
in C90, it can implement the C90 semantics (with or without a
diagnostic).

I doubt that any real-world compiler bothers to do this.

 

[Mark McIntyre]

That's a contradiction in terms.

Notice that there's a difference between a compilers 'compliant mode'
and 'being compliant '....

Support for // comments means
that a compiler is not fully compliant (to C89).

I didn't say it made sense, I just said they did it.

 

[Mark McIntyre]

a conforming C90 compiler cannot accept // comments as doing so
would cause it to misinterpret some strictly conforming programs.

IMHO this isn't strictly true, since....

printf ("%d\n", 10 //*
/**/ -2);
return 0;

....the compiler can spot this sort of issue pretty easily, and could
issue a warning about ambiguity, while still issuing an informational
message the rest of the time, along the lines of

VAXC-I-PSYCHIC double-slash comments may cause ambiguities

 

[Mark McIntyre]

No. But perhaps gcc is. You need to pass it a "-std=c99" (which puts
it into this meaningless mode, where it compiles to no existing
standard) to trick it into accepting the //s.

Curious. I'm pretty sure I have a copy of the C99 standard in my
desk... yup, definitely do. So what on earth do you mean.

Remind me ... you are the one who suggested me that empty strings are
illegal right?

No, I'm the one who said that zero-length char arrays were not strings
as far as I was concerned.