Problem with a linked list

[Mark McIntyre]

Chris Croughton wrote:

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

There's a theory that in fact its because you are often so very badly
wrong that most regulars prefer to keep you out of the killfiles, in
order to correct your errors.

Excuse me? C++ does not expose an equivalent to "realloc()" in their
new/delete concepts.

So C++ has a flaw.

So using malloc in C++ is not wrong, its just not
generally used for base-object memory management.

No, its bad style /and/ bad programming. Not wrong though.

 

[websnarf]

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.

So your irrationality is basically total. Just reread the statement.
gcc does not compile to the C99 standard with or without the "-std=c99"
switch. But it does accept "//" if you supply it that flag which,
among other things, makes it violate C89 -- so it just puts the
compiler into some strange non-standard mode.

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

Right, just making sure.

 

[Walter Roberson]

gcc does not compile to the C99 standard with or without the "-std=c99"
switch. But it does accept "//" if you supply it that flag which,
among other things, makes it violate C89 -- so it just puts the
compiler into some strange non-standard mode.

?? Isn't gcc almost -always- in "some strange non-standard mode" ??

 

[websnarf]

?? Isn't gcc almost -always- in "some strange non-standard mode" ??

Well the extensions (which all compilers have, whether they claim to be
ANSI compliant or not) generally don't intrude into successful
compilation of otherwise standards compliant code. There may be a few
exceptions like invalid invasions of namespace, but its generally not a
practical impedence to real world portability.

So gcc strays from the older standards in someone minor ways (by not
rejecting "extensions" as non-compliant, possibly some namespace
invasion, and certain weird things I've noticed wrt vsnprintf() in some
older versions.) You can get somewhat closer using the "-ansi" switch.

"-std=C99" truly makes some code just plain wrong that wasn't before
(there are other posts in this thread that show that mixing up
multiplication, division, line continuation and the two kinds of
comments means that this partial support of C99 definately makes some
C89 code invalid.) If it truly did the whole C99 standard, then we
would just call this just the correct natural evolution of C to the
next standard. But it does no such thing. So trying to use gcc in
"-std=c99" mode ... other compilers don't implement the same subset of
C99, there is no specified sub-standard, and it causes some C89 code to
break that wouldn't if you left off that switch.

Realistically you would only use "-std=C99" if:

1) you are *not* assuming C99 standard support.
2) you are *not* assuming C89 standard compliance.
3) you have no or extremely limited portability concerns.
4) you need or really want to use some particular feature that it adds.

These restrictions put you in an entirely different mode of operation
versus the default which is perfectly suitable for someone programming
to the C89 standard.

 

[Richard Bos]

Al Bowers wrote:
[...] 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.

If you can't see without my help why scribbling over a tail pointer,
which is potentially useful elsewhere, is inferior to returning a proper
error status from a function which now returns nothing at all, I'm
afraid I can explain all I want, but you're never going to get it.

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

Which is completely irrelevant to what the OP himself wanted. _You_
scribble over the tail pointer; this is a bad thing, because the OP
presumably wants to use it for something.

Richard

 

[Richard Bos]

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.

Apart from that, since when does gcc in any other mode compile to an
existing Standard not of Ganuck's own making?

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

No, you didn't. You said that a char array containing only a null
character is not a string. That is an at least _one_-length char array,
with space for at least the terminating null.
If you'd said that a non-existent block of no memory is not a string,
you'd have been correct. Since you claimed that a string with no content
except the terminating null is not a string ("as far as I was concerned"
is mere weaseling, since "as far as I am concerned" the moon may be made
of green cheese), you were plain wrong, since it contradicts the
Standard.

None of which contradicts the fact that you are still more reliable when
it comes to C than Mr. Hsieh, of course.

Richard

 

[pete]

Hi,

I am writing a linked list in the following way.

struct list
{
struct list *next;
char *mybuff;
};

struct list *myList = NULL;
struct list *endList = NULL;

void getline(char s[], int lim)
{
int c, i;

for(i=0; ((i<lim-1) && ((c=getchar()) != '\n')); i++)
s = c;

s ='\0';
} // end method getline

void add_item(char *data)
{
if (!endList)
{
endList = (struct list *)malloc(sizeof(struct list));

myList = endList;
endList->mybuff = data;
endList->next = NULL;
} // end if
else
{
endList->next = (struct list *)malloc(sizeof(struct list));
endList = endList>next;
endList->mybuff = data;
endList->next = NULL;
} // end else
}

void printList()
{
struct list *current = myList;

while(current)
{
printf("%s\n", current->mybuff);
current = current->next;
}
}

int main()
{
char buff[50];

// called for a n times
getline(buff, 50);
add_item(buff);

printList();
}

Now in the printList method, the nothing is being printed, but just a
simple blank line for each item.

Can someone help me solve this problem out.
Thanks in Advance

/* BEGIN new.c */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define LINE_LEN 50
#define str(s) # s
#define xstr(s) str(s)

struct list {
struct list *next;
void *data;
};

int get_line(FILE *fd, char *line);
struct list *add_item(char *string, struct list *tail);
void print_list(struct list *head);
void list_free(struct list *node, void (*free_data)(void *));

int main(void)
{
char buff[LINE_LEN + 1];
struct list *head;
struct list *tail;

puts("Enter a string. Enter an empty string to end.");
if (get_line(stdin, buff) == 1) {
head = add_item(buff, NULL);
if (head != NULL) {
tail = head;
do {
puts(
"Enter another string. "
"Enter an empty string to end."
);
} while (get_line(stdin, buff) == 1
&& (tail = add_item(buff, tail)) != NULL);
if (tail == NULL) {
fputs("\ntail equals NULL\n\n", stderr);
}
print_list(head);
list_free(head, free);
} else {
fputs("head equals NULL\n", stderr);
}
}
return 0;
}

int get_line(FILE *fd, char *line)
{
int rc = fscanf(fd, "%" xstr(LINE_LEN) "[^\n]%*[^\n]", line);

if (!feof(fd)) {
getc(fd);
}
return rc;
}

struct list *add_item(char *string, struct list *tail)
{
if (tail == NULL) {
tail = malloc(sizeof *tail);
} else {
tail -> next = malloc(sizeof *tail -> next);
tail = tail -> next;
}
if (tail != NULL) {
tail -> next = NULL;
tail -> data = malloc(strlen(string) + 1);
if (tail -> data != NULL) {
strcpy(tail -> data, string);
} else {
free(tail);
tail = NULL;
}
}
return tail;
}

void print_list(struct list *head)
{
while (head != NULL) {
printf("%s\n", (char *)head -> data);
head = head -> next;
}
}

void list_free(struct list *node, void (*free_data)(void *))
{
struct list *next_node;

while (node != NULL) {
next_node = node -> next;
free_data(node -> data);
free(node);
node = next_node;
}
}

/* END new.c */

 

[Mark McIntyre]

So your irrationality is basically total.

Feel free to become Dan Pop's alter ego.

Just reread the statement.
gcc does not compile to the C99 standard with or without the "-std=c99"
switch.

I doubt any compiler has ever complied perfectly with any C standard,
past or present, so its futile to have a go at gcc for some
nonconformance to the present one.

But it does accept "//" if you supply it that flag which,
among other things, makes it violate C89 -- so it just puts the
compiler into some strange non-standard mode.

only to you.

 

[Nils Weller]

(Not going to join this pointless discussion, but just one comment ...)

Apart from that, since when does gcc in any other mode compile to an
existing Standard not of Ganuck's own making?

Have you ever really used gcc? If you had, you'd know that a
combination of the ``-ansi'' (or -std=c89) and ``-pedantic'' options is
what you're looking for.

-ansi turns off GNU C extensions that aren't compatible with C89
-pedantic turns off GNU C extensions that are compatible with C89 and
turns on diagnostics that are required by C89 but omitted by GNU C

It seems like your strong feelings about this compiler (``Ganuck'') have
no technical basis.

 

[websnarf]

(e-mail address removed) wrote:
Al Bowers wrote:
[...] 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.

If you can't see without my help why scribbling over a tail pointer,
which is potentially useful elsewhere, is inferior to returning a
proper error status from a function which now returns nothing at
all, I'm afraid I can explain all I want, but you're never going to
get it.

The "reference to tail link" is overwritten when you are out of memory.
True it would be nice to have all sorts of O(1) assistance to deal
with whatever you are going to do about an out-of-memory situation, but
a scenario where this truly matters escapes my imagination at the
moment.

Your approach complexifies the main case in order to make dealing with
marginal cases faster. Trust me, the understanding problem is not
mine.

Which is completely irrelevant to what the OP himself wanted.

The code I wrote is plug-in compatible with what the OP wrote (without
changing his intended semantics.)

[...] _You_
scribble over the tail pointer; this is a bad thing, because the OP
presumably wants to use it for something.

He wants to use it to add_item(). I only "scribble over" the reference
to the tail link when an extremely marginal situation has occurred
which needs drastic attention and special case code to deal with. And
unlike the other suggestions posted, mine doesn't tie down the
implementation by *forcing* it to have a tail pointer.

There isn't a real sense in which the tail pointer is not available.
Think about it, suppose we were both to implement the failed malloc
scenario in our respective solutions:

1. If we decide that the list just must be destroyed and all further
processing to stop, then knowing the tail doesn't help.

2. If we decide that the upper level code should just stop adding items
and leave the list as is, and furthermore that add_item()/pop_iten()
are the only list manipulation functions, then again knowing the tail
doesn't help. My solution intrinsically stops add_item() from further
action no matter what, so you can defer the error check until the end
after your loop (and thus collect your error checking all in one
place). With your solution you must deal with the error from *INSIDE*
the inner loop.

3. If we have a way of coercing malloc to start functioning once more
(maybe we'll free memory from somewhere else or something like that)
then indeed your solution has a slight advantage. For my solution you
could copy the reference to tail link to an extra variable just before
calling add_item(), then recover it from inside the if(NULL == ...)
error case. But if you don't want to pay mainline inner loop
penalties, you can alternatively, just regenerate the reference to tail
link from scratch inside the error case (the reasoning being that this
case is so marginal that the high cost just doesn't matter.)

So I don't see that your complaint about my preference (I'm sure I'm
not the first person to have thought of this) as being seriously
legitimate. Your preference assumes the existence of a completely
artifical "tail entry" which aliases NULL with "there is no nail entry"
and requires you to handle two cases. In my solution there is *ALWAYS*
a reference to tail link -- there is no distinction between empty, one
entry or any other cases of linked lists.

Now if we add deletion into the mix, which of our solutions do you
think will be easier to test, design and implement?

 

[Al Bowers]

Your approach complexifies the main case in order to make dealing with
marginal cases faster. Trust me, the understanding problem is not
mine.

You ever heard of the phrase "a horse of a different color"?
You are using a word "complexifies" that has no overt meaning
that I am aware. I mean, to me, the word could mean, making a:
difficulty
maze
problem
quandary
entanglement

for some, your approach may be an entanglement(complexifies)
because it requires the use of the return value to work
correctly. The other approach makes no such requirement.
One can check the return value if they have cause or simply
ignore it. For example, using standard function printf, I
often omit checking it's return value. I would prefer
to built a data model that uses the concept that
encapsulates ( as much as C langugate allows). You can do this
by building a struct, ie,
struct node
{
struct node *next;
char data[50];
}
typedef struct LIST
{
struct node *head;
struct node *tail;
} LIST;
LIST mylist = {NULL}; /* the declaration */
You would write functions that manipulated the data
object using pointers to the data object. I would generally
write the "user" functions that would not require you to
use the return value for the manipulation of the data object
to work correctly. Of course, you may write "utility" functions
that will require the use of the return value. The user will
have no need to use the utility functions unless he were going
to write modifications or additions to the library of functions.
To me, that would be the least entanglement for the general
user.

For some, the use of "&((*tail)->next", may be a
quandary(complexifies) in debugging a "problem", because of
their lack of a keen understanding of precedence or associative.

If the word has meaning of "problem", then your approach, as posted,
complexifies my compiler.

I took your code, which is incomplete, and to make it complete,
I added the OP's definition of the struct list and of the
function getline. I a few minor changes in that I provide
a prompt in the loop in function main and removed variable cur
which is unused. Below is the resulting code. I compiled and
ran the code. It crashed. My compiler indicated an Accessed
Violation in function destroylist. Since you wrote the
definition, perhaps you can easily pinpoint what is at fault.

The code I wrote is plug-in compatible with what the OP wrote (without
changing his intended semantics.)

Yes. You deleted the OP's concept of struct list *endList and
added variable struct list **tailptr in making a model that is
not working.

[ The Code }

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

struct list
{
struct list *next;
char *mybuff;
};

void getline(char s[], int lim)
{
int c, i;

for(i=0; ((i<lim-1) && ((c=getchar()) != '\n')); i++)
s = c;

s ='\0';
} // end method getline

static char * copystr (const char * data) {
int l = strlen(data) + 1;
char * s = (char *) malloc (sizeof (char) * l);
if (s) memcpy (s, data, l);
return s;
}

struct list ** add_item (struct list ** tail, char * data) {
if (NULL == tail ||
NULL != *tail ||
(NULL == (*tail = (struct list *) malloc(sizeof(struct list))))
)
return NULL;
(*tail)->mybuff = copystr (data);
(*tail)->next = NULL;
return &((*tail)->next);
}

void printlist (struct list * head) {
while (head) {
printf ("%s\n", head->mybuff);
head = head->next;
}
}

void destroylist (struct list ** tail) {
if (NULL == tail) return;
while (*tail) {
struct list ** next = &((*tail)->next);
(*tail)->next = NULL;
free ((*tail)->mybuff);
free (*tail);
tail = next;
}
}

int main (void) {
int i;
char buff[51];
struct list * top = NULL, ** tailptr;


for (tailptr = &top, i=0; i < 3; i++) {
printf("Enter line %d: ",i+1);
fflush(stdout);
getline (buff, 50);
tailptr = add_item (tailptr, buff);
}

printlist (top);
destroylist (&top);
return 0;
}

 

[Lawrence Kirby]

On Tue, 10 May 2005 19:18:12 +0000, Keith Thompson wrote:

....

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

The issue here is not one of diagnostics, it is which output the program
above generates. If the compiler recognises // comments it will generate
code that produces output that is not valid for C90. You could have a rule
that the compiler ignores // comments where doing so results in valid C90
code. That strikes me a fairly nasty rule and you'd have to think hard
about whether you have covered all of the possibilities.

Lawrence

 

[websnarf]

You ever heard of the phrase "a horse of a different color"?
You are using a word "complexifies" that has no overt meaning
that I am aware. I mean, to me, the word could mean, making a:
difficulty
Yes.


No.


Yes.


Yes.

entanglement

Yes. I just used one word to describe it.

for some, your approach may be an entanglement(complexifies)
because it requires the use of the return value to work
correctly.

What? Paying attention to the return value is usually a requirement
for correctness ... I have no idea *WHAT* you are talking about. If as
a programmer you think paying attention to the return value of function
you are going to have real serious problems dealing with the C
programming language.

[...] The other approach makes no such requirement.

Uh ... yes it *DOES*. If you ignore the return value with the other
approach (which presumably is telling you if you've run out of memory)
then you can easily get into a situation where some entries are added
and some are not, because different amounts of memory may be available
at different times, and the size of memory required for different
entries might be different.

One can check the return value if they have cause or simply
ignore it.

No! If you ignore the return value (using the integer status return
method) then the code is just technically wrong. That is not true with
my reference to tail link method -- you actually can ignore the return
value using my method in the inner loop (and I in fact recommend this)
and check for errors *OUTSIDE* the inner loop. This improves
performance.

[...] For example, using standard function printf, I
often omit checking it's return value. I would prefer
to built a data model that uses the concept that
encapsulates (as much as C langugate allows).

You should encapsulate things at the appropriate level. A "tail"
pointer might not exist -- setting it to NULL is redundant with the
fact that the "top pointer" is already pointing to NULL. This is
fundamentally why this approach needs to split off the empty case
differently, even though there is nothing intrinsically different about
that case.

You can do this
by building a struct, ie,
struct node
{
struct node *next;
char data[50];
}

Ok, first if all, if your data is a string you shouldn't do this.
Allocate as much memory as you need, not some arbitrary fix value which
is almost always inappropriate.

typedef struct LIST
{
struct node *head;
struct node *tail;
} LIST;

[...]
LIST mylist = {NULL}; /* the declaration */

Yeah nice declaration ... like that sort of implicit declaration is
never a maintenance problem.

You would write functions that manipulated the data
object using pointers to the data object.

But you have to do this no matter what. Both programs potentially
modify the top-pointer directly. Using a "reference to tail link"
always tries to point exactly to the actual link location that will be
updates. By pointing to the "tail node" your approach just convolutes
matters, but in the end updates the exactly same link location.

[...] I would generally
write the "user" functions that would not require you to
use the return value for the manipulation of the data object
to work correctly. Of course, you may write "utility" functions
that will require the use of the return value. The user will
have no need to use the utility functions unless he were going
to write modifications or additions to the library of functions.
To me, that would be the least entanglement for the general
user.

But you are misunderstanding the situation. A linked list *HAS* to
have a top pointer. It does not *HAVE* to have a tail pointer. Notice
that the "printlist" function does not use the tail pointer -- because
its just not an intrinsic part of the linked list (you reach the end
when it points to NULL, not when it matches a tail pointer). Having a
tail pointer is very much tied to "appending" operations -- no other
operations on linked lists requires a tail pointer.

 

[Keith Thompson]

On Tue, 10 May 2005 19:18:12 +0000, Keith Thompson wrote:

...


The issue here is not one of diagnostics, it is which output the program
above generates. If the compiler recognises // comments it will generate
code that produces output that is not valid for C90. You could have a rule
that the compiler ignores // comments where doing so results in valid C90
code. That strikes me a fairly nasty rule and you'd have to think hard
about whether you have covered all of the possibilities.

Actually, I think diagnostics and behavior are both significant.

In most cases, a // comment is a syntax error in C90:

int main(void)
{
return 0; // comment?
}

A conforming C90 compiler must issue a diagnostic, but it's not
required to reject the program. In this case, if the compiler issues
a diagnostic, then discards the comment and generates an executable,
its behavior is still conforming to C90. (It's also conforming to
C99, since extraneous diagnostics aren't forbidden.)

In an odd case where a // is not a C90 syntax error, such a compiler
must implement the C90 semantics; for example, the above program must
print -5, not 8. A diagnostic is not required, since it's a perfectly
legal C90 program -- but as a QoI issue, a warning would be a good
idea, since the compiler purports to support // comments as an
extension but is unable to do so in this case.

(I think I covered all this in my previous posting, quoted above; if I
didn't, I meant to.)

All the C compilers I've seen either don't support // comments at all
(which is perfectly appropriate for a C90 compiler), or support //
comments as an extension and therefore fail to be completely C90
conforming. Since the general trend is a migration to C99 (slow
though it is), I doubt that an implementer would bother to go through
the contortions necessary to support // comments while maintaining
absolute C90 conformance.

It *might* be sensible for a C99 compiler to issue a warning for cases
like the one above, but it's not clear that it's worth the effort. I
doubt that anyone would write code like that unless they're
deliberately trying to create an ambiguity.

 

[Richard Bos]

(Not going to join this pointless discussion, but just one comment ...)



Have you ever really used gcc? If you had, you'd know that a
combination of the ``-ansi'' (or -std=c89) and ``-pedantic'' options is
what you're looking for.

No. I have, and I know that it's almost, but not entirely, conforming.
To name but a trivial example, IIRC even in that mode gcc doesn't
support trigraphs; those need yet another CL option.

To be fair, "perfectly ISO" is not necessarily what I'm looking for; I
don't like trigraphs any more than the GNU complex does. But this does
not make embrace-and-extend any less an omnipresent GNU policy.

Richard

 

[Nils Weller]

[...]

Have you ever really used gcc? If you had, you'd know that a
combination of the ``-ansi'' (or -std=c89) and ``-pedantic'' options is
what you're looking for.

No. I have, and I know that it's almost, but not entirely, conforming.
To name but a trivial example, IIRC even in that mode gcc doesn't
support trigraphs; those need yet another CL option.

Sorry, but that's not true, -ansi actually enables trigraphs.

/home/nils [0]> gcc --version
gcc (GCC) 3.3 20030226 (prerelease) (SuSE Linux)
Copyright (C) 2002 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

/home/nils [0]> cat >new.c
??=include <stdio.h>

int
main(void) {
puts("hello world!");
return 0;
}
/home/nils [0]> gcc new.c -o new
new.c:1: error: parse error before '?' token
/home/nils [1]> gcc new.c -o new -ansi
/home/nils [0]> ./new
hello world!
/home/nils [0]>

 

[Chris Croughton]

No. I have, and I know that it's almost, but not entirely, conforming.
To name but a trivial example, IIRC even in that mode gcc doesn't
support trigraphs; those need yet another CL option.

That isn't true, gcc has supported trigraphs at least since 2.95.3 (the
oldest I have on my system). But since you said "another CL option"
perhaps you weren't thinking of gcc but of Some Commercial Compiler
which certainly didn't support standard C (or C++ for that matter) at
least up to version 6...

To be fair, "perfectly ISO" is not necessarily what I'm looking for; I
don't like trigraphs any more than the GNU complex does. But this does
not make embrace-and-extend any less an omnipresent GNU policy.

GCC has extensions, yes (is there any compiler which doesn't? As
discussed before, some C99 headers are impossible to implement without
extensions). However, they are (apart from library deficiencies, about
which gcc can't do much because it uses the 'native' library, although
it does try to get rid of some of the worst ones in header files) either
removable or are in the implementation namespace. Or they are known
bugs / incompatibilities / old features which they are eliminating (but
they, like the standard, have the problem of legacy code).

I will take "close enough to be useful" over "unobtainable on most
platforms" any day. The Real World(tm) is not perfect, even for
Plato...

Chris C

 

[Chris Torek]

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

Ah, in that case, perhaps you should write your C code such that
it can be compiled with Fortran and Ada compilers as well.

I *do* know that C++ compilers are still being maintained
while C compilers are basically being relegated to legacy support ...

As Mark Twain said, "It's not what we don't know that hurts us,
it's what we know for certain that just ain't so."

Wind River, for instance, still actively maintains the Diab suite.
Diab includes both C and C++ compilers, which (as far as I know --
I do not work on them myself) share a single back end, like many
modern compilers.

To touch on another ongoing thread, one of the items on the list
of "things to be supported" is C99 (Diab is not 100% there yet, I
believe, but is getting closer). C99 support is certainly not
yet ubiquitous, and I would say that both "full" and "nearly full"
C99 support is not even common -- but it is getting closer, and
I suspect it *will* be common enough in a few more years.