linked list

[Alexo]

hello everyone.
Who can help me telling me what's wrong in the following code?

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

typedef struct datum
{
char *name;
int data;
struct datum *next;
}NODE;

void print(NODE *);

int main(void)
{
NODE *head = (NODE *) malloc(sizeof(NODE));
head->name = (char *) malloc( strlen("head"));
strcpy( "head", head->name);
head->data = 0;
head->next = NULL;

print(head);

return 0;
}

void print(NODE *head)
{
puts("the content of the list:");
while( head != NULL)
{
printf("%s\t%d\n", head->name, head->data);
head = head->next;
}
}

 

[Alexo]

I got it!
I must exchange the source and dest string in the strcpy call and add
#include <stdlib.h> so the correct version is the following:

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

typedef struct datum
{
char *name;
int data;
struct datum *next;
}NODE;

void print(NODE *);

int main(void)
{
NODE *head = (NODE *) malloc(sizeof(NODE));
head->name = (char *) malloc( strlen("head"));
strcpy(head->name, "head");
head->data = 0;
head->next = NULL;

print(head);

return 0;
}

void print(NODE *head)
{
puts("the content of the list:");
while( head != NULL)
{
printf("%s\t%d\n", head->name, head->data);
head = head->next;
}
}

 

[Ike Naar]

NODE *head = (NODE *) malloc(sizeof(NODE));

You don't need the cast:

NODE *head = malloc(sizeof *head);

head->name = (char *) malloc( strlen("head"));
strcpy(head->name, "head");

Since you're going to copy 5 characters into head->name
('h', 'e', 'a', 'd', '\0'), you need to allocate at least that much:

head->name = malloc(strlen("head") + 1);
strcpy(head->name, "head");

or, alternatively

head->name = malloc(sizeof "head");
strcpy(head->name, "head");

 

[Eric Sosman]

hello everyone.
Who can help me telling me what's wrong in the following code?

Almost anyone.

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

typedef struct datum
{
char *name;
int data;
struct datum *next;
}NODE;

void print(NODE *);

int main(void)
{
NODE *head = (NODE *) malloc(sizeof(NODE));

Another current thread has degenerated into a useless
squabble about whether the (NODE*) cast is or is not a good
idea. Here is an instance where it is demonstrably a *bad*
idea, because it *did* hide an error that would otherwise
have been caught. Try removing the cast, and see what your
compiler tells you. (Even with the cast in place, some
compilers will warn about the error if their diagnostic
sensitivity is "dialed up" a bit. Check your compiler's
documentation to see if there's a way you can do so, because
warnings can be helpful in many other circumstances, too.)

There's also the little matter that malloc() might fail
to find enough memory for your request, in which case it will
return NULL. If you then try things like `head->name=...'
when `head' is NULL, there will be trouble. True, in a toy
program like this it is overwhelmingly likely that malloc()
will find enough memory and return a non-NULL, but *do* *not*
get into the habit of forgetting to inspect what you get!

head->name = (char *) malloc( strlen("head"));
strcpy( "head", head->name);

An absolutely classic beginner C mistake. Questions:
(1) What is the value of strlen("head")? (2) How many
bytes of memory does "head" occupy? (3) If the answers
to (1) and (2) are different, what should you do about it?

 

[Alexo]

Done!
In the meanwhile the program has grown a bit.
But on my machine I have troubles executing it.
What's wrong now?

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

typedef struct datum
{
char *name;
int data;
struct datum *next;
}NODE;

NODE *make_list(void);
void add(NODE* , char*, int);
void print(NODE *);


int main(void)
{
NODE *head = make_list();

add(head, "Alessandro", 1976);
add(head, "Alessandra", 1980);
add(head, "Valentina", 1977);
add(head, "Federico", 1977);
add(head, "Fabrizio", 1980);

print(head);
getchar();
return 0;
}

void print(NODE *head)
{
puts("the content of the list:\n");
while( head != NULL)
{
printf("%-15s anno di nascita: %d\n", head->name, head->data);
head = head->next;
}
}

NODE *make_list()
{
NODE *head = malloc(sizeof(NODE));
assert(head);
head->name = malloc( strlen("head" + 1));
assert(head->name);
strcpy( head->name, "head");
head->data = 0;
head->next = NULL;
return head;
}

void add(NODE *head, char *name, int data)
{
NODE *tail = NULL;

while( head != NULL)
{
tail = head;
head = head->next;
}

NODE *element = malloc(sizeof(NODE));
assert(element);
element->name = malloc( strlen(name + 1));
assert(element->name);
strcpy( element->name, name);
element->data = data;
tail->next = element;
element->next = NULL;
}

 

[Ben Bacarisse]

Done!
In the meanwhile the program has grown a bit.
But on my machine I have troubles executing it.
What's wrong now?

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

typedef struct datum
{
char *name;
int data;
struct datum *next;
}NODE;

NODE *make_list(void);
void add(NODE* , char*, int);
void print(NODE *);


int main(void)
{
NODE *head = make_list();

add(head, "Alessandro", 1976);
add(head, "Alessandra", 1980);
add(head, "Valentina", 1977);
add(head, "Federico", 1977);
add(head, "Fabrizio", 1980);

print(head);
getchar();
return 0;
}

void print(NODE *head)
{
puts("the content of the list:\n");
while( head != NULL)
{
printf("%-15s anno di nascita: %d\n", head->name, head->data);
head = head->next;
}
}

NODE *make_list()
{
NODE *head = malloc(sizeof(NODE));
assert(head);
head->name = malloc( strlen("head" + 1));
assert(head->name);

You shouldn't use assert for run-time checks of this sort. Roughly
speaking you should use it to check that things that can't happen
haven't happened!

strcpy( head->name, "head");
head->data = 0;
head->next = NULL;
return head;
}

void add(NODE *head, char *name, int data)
{
NODE *tail = NULL;

while( head != NULL)
{
tail = head;
head = head->next;
}

NODE *element = malloc(sizeof(NODE));
assert(element);
element->name = malloc( strlen(name + 1));
assert(element->name);
strcpy( element->name, name);
element->data = data;
tail->next = element;

tail can be NULL. The loop above does not always set tail.

element->next = NULL;
}

You have quite a lot of duplicated code. Creating the initial dummy
list element (not my favourite way to do this, but that is just a
matter of taste) can be done with almost the same code used to add an
element.

 

[BGB / cr88192]

Almost anyone.


Another current thread has degenerated into a useless
squabble about whether the (NODE*) cast is or is not a good
idea. Here is an instance where it is demonstrably a *bad*
idea, because it *did* hide an error that would otherwise
have been caught. Try removing the cast, and see what your
compiler tells you. (Even with the cast in place, some
compilers will warn about the error if their diagnostic
sensitivity is "dialed up" a bit. Check your compiler's
documentation to see if there's a way you can do so, because
warnings can be helpful in many other circumstances, too.)

yep, in my case it depends on the code, as in, whether I might consider
compiling it as C++ rather than as C...

in a few rare cases, I have had code which had started out as C but was then
later transitioned to C++, and in general try to write code which is fairly
neutral between them.

so, alas, casting malloc is one of those things:
some people like it, others despise it;
it is much like the whole "()" vs "(void)" issue...

There's also the little matter that malloc() might fail
to find enough memory for your request, in which case it will
return NULL. If you then try things like `head->name=...'
when `head' is NULL, there will be trouble. True, in a toy
program like this it is overwhelmingly likely that malloc()
will find enough memory and return a non-NULL, but *do* *not*
get into the habit of forgetting to inspect what you get!

assuming this much works as expected in a modern OS...

it is also very possible that:
the malloc does not fail to allocate memory until all the address space is
used (say 2GB or 3GB for a 32-bit process);
either the OS kills the process, or something crashes within the C library,
before this point.

yeah, I actually did have a program at one point which exhausted the entire
address space via little more than 'strdup' and allocating 'node'
structures. granted, it was also implementing an HMM, I think order-5 (or
similar) and for a fairly big chunk of text...

some time later, in 64 bit land, I allocated enough memory that, although
things never returned NULL, the OS ground to a halt and I was half afraid
that the OS would crash instead (resulting mostly from allocating around 5GB
of memory on a computer with 2GB of RAM...).

so, yes, the powers of virtual memory...
the C library may not know anymore when is a reasonable limit, or when
memory is exhausted, it may well just keep going until something more
fundamental breaks (such as the amazing BSOD...).

 

[Ralf Damaschke]

What's wrong now?

head->name = malloc( strlen("head" + 1));

element->name = malloc( strlen(name + 1));

You are effectively subtracting one from strlen(name)
rather than adding one.

-- Ralf

 

[Jean-Christophe]

What's wrong now?

void add( NODE *head, char *name, int data )
{
NODE *tail = NULL;
...
element->next = element->tail = NULL;
}

 

[Seebs]

hello everyone.
Who can help me telling me what's wrong in the following code?
Hah.

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

You didn't include a header which declares malloc.

int main(void)
{
NODE *head = (NODE *) malloc(sizeof(NODE));

So your compiler probably assumed "malloc" returned int, and dutifully
generated code to convert that int into a pointer, rather than correctly
identifying that malloc returned a pointer.

While that may not be your only problem, it's certainly a problem.

1. Include <stdlib.h> when using malloc.
2. Don't cast the return of malloc.
3. Always run with warnings/errors such that the compiler will reject
code which calls a function which has not been declared.

head->name = (char *) malloc( strlen("head"));
strcpy( "head", head->name);

This is another likely candidate for your problem.
strcpy(dest, src);

Think about it.

Note also that to hold a string with four characters, you need five characters
of storage -- you need an extra one for the trailing null. strlen() tells
you the number of non-null characters. So use strlen(...) + 1 as your size.
(Do not use strlen(foo + 1), as that'll get you something most often two
bytes too small rather than just one.)

-s

 

[Eric Sosman]

yep, in my case it depends on the code, as in, whether I might consider
compiling it as C++ rather than as C...

in a few rare cases, I have had code which had started out as C but was then
later transitioned to C++, and in general try to write code which is fairly
neutral between them.

so, alas, casting malloc is one of those things:
some people like it, others despise it;
it is much like the whole "()" vs "(void)" issue...

My point, which seems to have escaped you, is that if
you had *not* used the cast, the compiler would have told
you about your mistake.

Intending no offense, you seem to be at a level of C
proficiency where many mistakes can be expected. That
being the case, discouraging the compiler from helping you
find the errors is not a productive tactic.

assuming this much works as expected in a modern OS...

I don't understand what you mean by this.

it is also very possible that:
the malloc does not fail to allocate memory until all the address space is
used (say 2GB or 3GB for a 32-bit process);

It has been proved that even if all the requests are of only
two sizes, malloc() can run out of memory when 1/3 of the total
space is still unused. (See TAOCP volume 1 for details.)

 

[Antoninus Twink]

An absolutely classic beginner C mistake. Questions:
(1) What is the value of strlen("head")? (2) How many
bytes of memory does "head" occupy? (3) If the answers
to (1) and (2) are different, what should you do about it?

Read again, Eric.

You too have made an absolutely classic beginner C mistake.

The first argument to strcpy is the *destination* pointer. Forget off by
one errors, the call is doomed anyway because it tries to write to a
string literal, which will typically be placed in read-only memory.

 

[Barry Schwarz]

yep, in my case it depends on the code, as in, whether I might consider
compiling it as C++ rather than as C...

Since stdlib.h is not included, I think this is a violation in C++ and
C99 since there is no prototype in scope for malloc.

In C89, it simply invokes undefined behavior because the compiler is
required to assume malloc returns an int which is obviously not the
case. If I'm wrong about C99 above, then this applies to C99 also.

in a few rare cases, I have had code which had started out as C but was then
later transitioned to C++, and in general try to write code which is fairly
neutral between them.

so, alas, casting malloc is one of those things:
some people like it, others despise it;
it is much like the whole "()" vs "(void)" issue...



assuming this much works as expected in a modern OS...

it is also very possible that:
the malloc does not fail to allocate memory until all the address space is
used (say 2GB or 3GB for a 32-bit process);
either the OS kills the process, or something crashes within the C library,
before this point.

While the OS is entitled to kill any process it wants, the fact that
malloc has a failure return strongly implies that this is not the
intent.

 

[Barry Schwarz]

I got it!
I must exchange the source and dest string in the strcpy call and add
#include <stdlib.h> so the correct version is the following:

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

typedef struct datum
{
char *name;
int data;
struct datum *next;
}NODE;

void print(NODE *);

int main(void)
{
NODE *head = (NODE *) malloc(sizeof(NODE));

Now the cast is merely superfluous.

head->name = (char *) malloc( strlen("head"));
strcpy(head->name, "head");

Of course, this still invokes undefined behavior since the memory
head->name points to is one byte too short to hold the string. You
really wanted sizeof instead of strlen in the call to malloc.

 

[Nick]

head->name = (char *) malloc( strlen("head"));
strcpy(head->name, "head");

In addition to everything everyone else has said, using the same
explicit string like this isn't necessarily a good thing to do
(particularly when you're using one instance of it to allocate memory
[others have commented on the fact that you're not allocating enough
memory]).

I'd recommend a #define for this - add at the top of your code
#define HEAD_MARKER "head"
and using HEAD_MARKER where you've got head in the code.

Otherwise, sooner or later someone will come along and change your code
and miss one:

head->name = (char *) malloc( strlen("head"));
strcpy(head->name, "cabeza");

 

[Antoninus Twink]

void add(NODE *head, char *name, int data)
{
if (head != NULL) {
NODE *const element = malloc(sizeof *element);

if (element != NULL) {
while (head -> next != NULL) {
head = head -> next;
}
head -> next = element;
element -> next = NULL;
element -> data = data;
element -> name = malloc(strlen(name) + 1);
if (element -> name != NULL) {
strcpy(element -> name, name);
}
}
}
}

Are you really putting this forward as an example of best practise?

If the caller wants to detect a failure in this function, it has to
search through the whole linked list looking for an element whose name
field is NULL.

Why not return a NODE *, and if the string malloc fails, free(element)
before returning NULL?

You've also implemented insertion into a linked list as an O(n)
operation rather than O(1) - that's the sort of needless inefficiency
that you'd normally expect to find from the likes of Heathfield!

Earlier in the code, you used assert() to deal with malloc failure. This
is also poor practise. Assertions help make code self-documenting by
pointing out assumptions the code is making about the data it has
received from elsewhere in the same program, and the calculations it is
performing. This purpose is orthogonal to checks for failure of library
functions.

 

[Moi]

Antoninus Twink wrote:

static NODE *
merge_lists(NODE *head,
NODE *tail,
int (*compar)(const void *, const void *))
{
NODE *list, *sorted, **node;

node = compar(head -> data, tail -> data) > 0 ? &tail : &head; list
= sorted = *node;
while ((*node = sorted -> next) != NULL) {
node = compar(head->data, tail->data) > 0 ? &tail : &head;
sorted -> next = *node;
sorted = *node;
}
sorted -> next = tail != NULL ? tail : head; return list;
}

/* END new.c */

Neat.

This one is shorter:

***/

#include <stdlib.h>


struct list *list_merge(struct list *one, struct list *two)
{
struct list *new= NULL, **hnd;

for (hnd = &new; one && two; ) {
if (rand() & 1) { *hnd = one; hnd = &one->next; one=one->next; }
else { *hnd = two; hnd = & two->next; two = two->next; }
}
*hnd = one ? one : two;

return new;
}




AvK

 

[Nick Keighley]

   element->name = malloc( strlen(name + 1));

this doesn't do what you think it does

 

[Herbert Rosenau]

hello everyone.
Who can help me telling me what's wrong in the following code?

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

typedef struct datum
{
char *name;
int data;
struct datum *next;
}NODE;

void print(NODE *);

int main(void)
{
NODE *head = (NODE *) malloc(sizeof(NODE));
head->name = (char *) malloc( strlen("head"));

error: unneeded and superflous cast to hide an diagnostic that shows
the real cause that an #include is missing.

Don't lie to the compiler (here the cast) or the compiler will get its
revange - here wrong value casted to struct NODE*. The wrong vaue is
the int the compiler thinks malloc returns instead of the pointer
because you've not declared the right prototype.

--
Tschau/Bye
Herbert

Visit http://www.ecomstation.de the home of german eComStation
eComStation 1.2R Deutsch ist da!

 

[Eric Sosman]

error: unneeded and superflous cast to hide an diagnostic that shows
the real cause that an #include is missing.

If you dislike redundancy, perhaps you should remove at
least one of "unneeded" and "superflous" [sic] from your
message text's verbiage words. ;-)

Don't lie to the compiler (here the cast) or the compiler will get its
revange - here wrong value casted to struct NODE*. The wrong vaue is
the int the compiler thinks malloc returns instead of the pointer
because you've not declared the right prototype.

Although I agree that the cast is unnecessary and (with
some C90 compilers) may hide an error -- and I have said as much
to the O.P. -- it is in no sense an error to cast, nor a lie to
the compiler. It's unnecessary, that's all.

State your case, but don't overstate it.