Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #7623 > unrolled thread

Linked-list problem - compiles but segfaults

Back to article view | Back to comp.lang.c

Contents

  Linked-list problem - compiles but segfaults Andy Elvey <neptune.poseidon789@gmail.com> - 2011-07-04 17:53 -0700
    Re: Linked-list problem - compiles but segfaults "Morris Keesan" <mkeesan@post.harvard.edu> - 2011-07-04 22:18 -0400
      Re: Linked-list problem - compiles but segfaults Andy Elvey <neptune.poseidon789@gmail.com> - 2011-07-04 19:31 -0700
    Re: Linked-list problem - compiles but segfaults gordonb.bxelr@burditt.org (Gordon Burditt) - 2011-07-04 21:39 -0500
      Re: Linked-list problem - compiles but segfaults Andy Elvey <neptune.poseidon789@gmail.com> - 2011-07-04 20:00 -0700
        Re: Linked-list problem - compiles but segfaults gordonb.tu82f@burditt.org (Gordon Burditt) - 2011-07-05 00:11 -0500
    Re: Linked-list problem - compiles but segfaults pete <pfiland@mindspring.com> - 2011-07-05 00:13 -0400
      Re: Linked-list problem - compiles but segfaults Andy Elvey <neptune.poseidon789@gmail.com> - 2011-07-04 21:20 -0700
        Re: Linked-list problem - compiles but segfaults pete <pfiland@mindspring.com> - 2011-07-05 01:04 -0400
    Re: Linked-list problem - compiles but segfaults "christian.bau" <christian.bau@cbau.wanadoo.co.uk> - 2011-07-05 08:42 -0700
      Re: Linked-list problem - compiles but segfaults Keith Thompson <kst-u@mib.org> - 2011-07-05 09:04 -0700
    Re: Linked-list problem - compiles but segfaults Paul N <gw7rib@aol.com> - 2011-07-05 14:51 -0700
      Re: Linked-list problem - compiles but segfaults Todd Carnes <toddcarnes@gmail.com> - 2011-07-06 03:20 +0000
        Re: Linked-list problem - compiles but segfaults Shao Miller <sha0.miller@gmail.com> - 2011-07-05 23:37 -0400
          Re: Linked-list problem - compiles but segfaults Shao Miller <sha0.miller@gmail.com> - 2011-07-05 23:41 -0400
            Re: Linked-list problem - compiles but segfaults Shao Miller <sha0.miller@gmail.com> - 2011-07-05 23:44 -0400
            Re: Linked-list problem - compiles but segfaults Shao Miller <sha0.miller@gmail.com> - 2011-07-05 23:54 -0400
          Re: Linked-list problem - compiles but segfaults "Morris Keesan" <mkeesan@post.harvard.edu> - 2011-07-06 07:51 -0400
            Re: Linked-list problem - compiles but segfaults Shao Miller <sha0.miller@gmail.com> - 2011-07-06 09:50 -0400

#7623 — Linked-list problem - compiles but segfaults

Hi all -
  I've been poking around with C for a while, but I have big problems
with linked lists. This seems to be mainly around the "declaration,
initialisation, iterating" area.  Anyway, I have the code below, which
compiles but gives a segfault (and I have no idea why), so hoping that
someone may be able to help.
( I have three puts statements at the end because I'm unsure how to
iterate along a list. )
[code]
/* This code is released to the public domain  */
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/stat.h>

/* Linked list implementation */
typedef struct _List List;

struct _List {
	void *data;
	List *next;
};

static List *list_malloc (void)
{
   return (List *) malloc (sizeof (List));
}

List *list_prepend (List *list, void *data)
{
	List *ret = list_malloc ();
	ret->data = data;
	ret->next = list;
	return ret;
}

List *list_append (List *list, void *data)
{
	List *ret;
	if (list == NULL) return list_prepend (list, data);
	ret = list;
	for (; list->next; list = list->next);
	list->next = list_malloc ();
	list->next->data = data;
	list->next->next = NULL;
	return ret;
}

void list_free (List *list)
{
	List *next;
	while (list)
	{
		next = list->next;
		free (list);
		list = next;
	}
}

/* End linked list implementation */

int main()
{
/* Declare a list */
List *mylist = NULL;
list_append(mylist, "foo");
puts(mylist->data);
list_append(mylist, (int*) 42);
puts(mylist->data);
list_append(mylist, "baz");
puts(mylist->data);
return 0;
}
[/code]
Very many thanks if you can get this code working...... :)
- Andy

[toc] | [next] | [standalone]

#7626

On Mon, 04 Jul 2011 20:53:29 -0400, Andy Elvey  
<neptune.poseidon789@gmail.com> wrote:
...
> ( I have three puts statements at the end because I'm unsure how to
> iterate along a list. )
> [code]
> /* This code is released to the public domain  */
> #include <ctype.h>
> #include <stdio.h>
> #include <stdlib.h>
> #include <string.h>
> #include <sys/stat.h>
>
> /* Linked list implementation */
> typedef struct _List List;

Don't use leading underscores in your type names.  These identifiers
are reserved.  If you're copying the style of names that you've seen
in standard headers, those names begin with underscores specifically
because they're reserved for the implementation, and the implementation
of the standard header would avoid conflicting with your names, if you
weren't going out of your way like this to remove that protection.

> struct _List {
> 	void *data;
> 	List *next;
> };
>
> static List *list_malloc (void)
> {
>    return (List *) malloc (sizeof (List));
This cast is unnecessary.  Because malloc returns a (void *), it is
automatically converted to the right kind of pointer by the return
statement, without the need of the cast operator.  Also, either here
...

> }
>
> List *list_prepend (List *list, void *data)
> {
> 	List *ret = list_malloc ();
... or here, you need to check to make sure the malloc() hasn't returned
NULL.  This is almost certainly not the source of your current problem,
but will cause you trouble in larger programs in the future.  You must
always check to make sure malloc succeeded, before you try using a
pointer which was returned by malloc.

> 	ret->data = data;
> 	ret->next = list;
> 	return ret;
> }
>
> List *list_append (List *list, void *data)
> {
> 	List *ret;
> 	if (list == NULL) return list_prepend (list, data);
> 	ret = list;
> 	for (; list->next; list = list->next);
This for loop is okay, but odd looking.  In my opinion, it would be
more readable as
         while (list->next != NULL) list = list->next;

> 	list->next = list_malloc ();
> 	list->next->data = data;
> 	list->next->next = NULL;
> 	return ret;
> }
>
> void list_free (List *list)
> {
> 	List *next;
> 	while (list)
> 	{
> 		next = list->next;
> 		free (list);
> 		list = next;
> 	}
> }
>
> /* End linked list implementation */

Except for the small issues I've mentioned, your linked list
implementation looks okay.

>
> int main()
> {
> /* Declare a list */
> List *mylist = NULL;
> list_append(mylist, "foo");

Okay.  Right here, mylist is still null, because you haven't modified it.
list_append returns the newly-allocated list, but because you don't use
the return value of list_append, the allocation is lost.  So

> puts(mylist->data);

is the same as "puts(NULL->data);".  I hope you can now see where your
segfault is coming from.  If you didn't have the "mylist->data" expression
here causing a crash, then the next call to list_append() would create a
new list, instead of appending a new node to an existing list, because
you're passing a null pointer to list_append for the second time.

Here is another problem:
> list_append(mylist, (int*) 42);
You try to convert the number 42 to an (int *), and in list_append it will
get converted to a (void *).  Whether this is meaningful is implementation-
defined.  Most likely, you'll get a pointer whose bit pattern matches the
number 42, i.e. something that appears to be pointing to the whatever is
at the address "42", whatever that address means.  Depending on your
implementation, attempting to convert the number 42 to an (int *) may
be causing the segfault, since if your platform requires ints to be on
4-byte boundaries, 42 is not a valid (int *), even if it were within
the range of user-addressable memory.
   If you want to store the number 42 in the linked list as you've
implemented it, the way to do this would be something like
    int fortytwo = 42; list_append(mylist, &fortytwo);
but then you would have to have some way of knowing that the data in that
particular list node is an integer, and not a string.

Note that since nothing in your code modifies mylist, all three of these
puts calls should display the same data.  In this case, that's a good  
thing,
because if you were displaying each subsequent added data, this next
puts call would be equivalent to puts((char *)(void *)(int *)42), which is
meaningless, and which would probably cause a crash.
> puts(mylist->data);
> list_append(mylist, "baz");
> puts(mylist->data);
> return 0;
> }
> [/code]
> Very many thanks if you can get this code working...... :)
> - Andy

As far as iterating along the list: if you knew that the data in all  
members
of the list, you could do it this way:

for (List *p = mylist; p != NULL; p = p->next) puts(p->data);


-- 
Morris Keesan -- mkeesan@post.harvard.edu

[toc] | [prev] | [next] | [standalone]

#7629

On Jul 5, 2:18 pm, "Morris Keesan" <mkee...@post.harvard.edu> wrote:
> On Mon, 04 Jul 2011 20:53:29 -0400, Andy Elvey  <neptune.poseidon...@gmail.com> wrote:
> (snip)
> As far as iterating along the list: if you knew that the data in all  
> members
> of the list, you could do it this way:
>
> for (List *p = mylist; p != NULL; p = p->next) puts(p->data);
>
> --
> Morris Keesan -- mkee...@post.harvard.edu
Hi Morris -
 Thanks very much for your reply!  I'll have a good look at what
you've suggested, and will do what you've said. Many thanks - bye for
now -
- Andy

[toc] | [prev] | [next] | [standalone]

#7630

>  I've been poking around with C for a while, but I have big problems
> with linked lists. This seems to be mainly around the "declaration,
> initialisation, iterating" area.  Anyway, I have the code below, which
> compiles but gives a segfault (and I have no idea why), so hoping that
> someone may be able to help.

Your functions list_prepend and list_append return the new list
head pointer.  list_prepend *always* changes the list head pointer.
list_append changes the list head pointer if it is originally NULL.
You need to actually *USE* those return values in main().  As coded,
mylist in main() is always NULL, and puts(mylist->data) is begging
for a segfault.


> ( I have three puts statements at the end because I'm unsure how to
> iterate along a list. )

This kind of iteration is typically done by (list is the list head pointer):
	List *foo;

	for (foo = list; foo != NULL; foo = foo->next)
	{
		... do something with foo->data ...;
	}

> [code]
> /* This code is released to the public domain  */
> #include <ctype.h>
> #include <stdio.h>
> #include <stdlib.h>
> #include <string.h>
> #include <sys/stat.h>
> 
> /* Linked list implementation */
> typedef struct _List List;
> 
> struct _List {
>        void *data;
>        List *next;
> };
> 
> static List *list_malloc (void)
> {
>   return (List *) malloc (sizeof (List));
> }
> 
> List *list_prepend (List *list, void *data)
> {
>        List *ret = list_malloc ();
>        ret->data = data;
>        ret->next = list;
>        return ret;
> }
> 
> List *list_append (List *list, void *data)
> {
>        List *ret;
>        if (list == NULL) return list_prepend (list, data);
>        ret = list;
>        for (; list->next; list = list->next);
>        list->next = list_malloc ();
>        list->next->data = data;
>        list->next->next = NULL;
>        return ret;
> }
> 
> void list_free (List *list)
> {
>        List *next;
>        while (list)
>        {
>                next = list->next;
>                free (list);
>                list = next;
>        }
> }
> 
> /* End linked list implementation */
> 
> int main()
> {
> /* Declare a list */
> List *mylist = NULL;
> list_append(mylist, "foo");
> puts(mylist->data);

Casting 42 to an (int *), then using it in place of a char * in the
puts() below it, is also begging for a segmentation fault.  You may use
various data types for the data pointer, but you need to figure out
some way of identifying what type it is before trying to print it.
puts((int *) 42) is trouble.

> list_append(mylist, (int*) 42);
> puts(mylist->data);
> list_append(mylist, "baz");
> puts(mylist->data);
> return 0;
> }
> [/code]
> Very many thanks if you can get this code working...... :)

Please send me the email address of your instructor, so I can
send the corrected code directly to him.

[toc] | [prev] | [next] | [standalone]

#7632

On Jul 5, 2:39 pm, gordonb.bx...@burditt.org (Gordon Burditt) wrote:
> >  I've been poking around with C for a while, but I have big problems
> > with linked lists. This seems to be mainly around the "declaration,
> > initialisation, iterating" area.  Anyway, I have the code below, which
> > compiles but gives a segfault (and I have no idea why), so hoping that
> > someone may be able to help.
>
> Your functions list_prepend and list_append return the new list
> head pointer.  list_prepend *always* changes the list head pointer.
> list_append changes the list head pointer if it is originally NULL.
> You need to actually *USE* those return values in main().  As coded,
> mylist in main() is always NULL, and puts(mylist->data) is begging
> for a segfault.
>
> > ( I have three puts statements at the end because I'm unsure how to
> > iterate along a list. )
>
> This kind of iteration is typically done by (list is the list head pointer):
>         List *foo;
>
>         for (foo = list; foo != NULL; foo = foo->next)
>         {
>                 ... do something with foo->data ...;
>         }
>
> > [code]
> > /* This code is released to the public domain  */
> > #include <ctype.h>
> > #include <stdio.h>
> > #include <stdlib.h>
> > #include <string.h>
> > #include <sys/stat.h>
>
> > /* Linked list implementation */
> > typedef struct _List List;
>
> > struct _List {
> >        void *data;
> >        List *next;
> > };
>
> > static List *list_malloc (void)
> > {
> >   return (List *) malloc (sizeof (List));
> > }
>
> > List *list_prepend (List *list, void *data)
> > {
> >        List *ret = list_malloc ();
> >        ret->data = data;
> >        ret->next = list;
> >        return ret;
> > }
>
> > List *list_append (List *list, void *data)
> > {
> >        List *ret;
> >        if (list == NULL) return list_prepend (list, data);
> >        ret = list;
> >        for (; list->next; list = list->next);
> >        list->next = list_malloc ();
> >        list->next->data = data;
> >        list->next->next = NULL;
> >        return ret;
> > }
>
> > void list_free (List *list)
> > {
> >        List *next;
> >        while (list)
> >        {
> >                next = list->next;
> >                free (list);
> >                list = next;
> >        }
> > }
>
> > /* End linked list implementation */
>
> > int main()
> > {
> > /* Declare a list */
> > List *mylist = NULL;
> > list_append(mylist, "foo");
> > puts(mylist->data);
>
> Casting 42 to an (int *), then using it in place of a char * in the
> puts() below it, is also begging for a segmentation fault.  You may use
> various data types for the data pointer, but you need to figure out
> some way of identifying what type it is before trying to print it.
> puts((int *) 42) is trouble.
>
> > list_append(mylist, (int*) 42);
> > puts(mylist->data);
> > list_append(mylist, "baz");
> > puts(mylist->data);
> > return 0;
> > }
> > [/code]
> > Very many thanks if you can get this code working...... :)
>
> Please send me the email address of your instructor, so I can
> send the corrected code directly to him.

Hi Gordon - thanks for your help, much appreciated!
Um.... I don't have an instructor, I'm doing this on my own. I got the
code from here -
http://adamhooper.com/code?path=mcgill-se%2FCOMP206%2Fass2%2Fproducts.c
Anyway.... I'd really appreciate it if you were able to either email
or post the corrected code. I've been stuck on linked-lists for ages,
and there are so many (confusing) implementations that make them more
confusing than they should be.... :)
Thanks again -
- Andy

[toc] | [prev] | [next] | [standalone]

#7648

> http://adamhooper.com/code?path=mcgill-se%2FCOMP206%2Fass2%2Fproducts.c
> Anyway.... I'd really appreciate it if you were able to either email
> or post the corrected code. I've been stuck on linked-lists for ages,
> and there are so many (confusing) implementations that make them more
> confusing than they should be.... :)

If you cannot figure out what the correct code should be based on
my post and others pointing out exactly where the error is, or at
least figure out some changes to get a little farther, you're not
going to get it, and you need an instructor, or a good textbook.

Do you know what the return value of a function is?
Do you know which lines of code are in main()?
Do you understand why "mylist in main() is always NULL"?
What function do you call in main() to add an element to the list?
Why should the variable mylist change from NULL after you add
an element to the list?
Do you understand why mylist being NULL is a problem when
you reach the puts(mylist->data); statement?
Do you understand which lines of code in main() call list_append()?
Do you understand what *use the return value* of list_append() means?
What variable might you use to hold the return value of list_append()?
(What variable in main() has the wrong value at times?)

You should at least be able to make some changes based on that
and try again.  If it doesn't work, post the modified code to show
you're making some progress.  If you can't figure out how to modify
the code to at least try to fix it, then you probably need a lot
more studying of the basics.  Maybe you aren't ready for linked lists
yet.

[toc] | [prev] | [next] | [standalone]

#7639

Andy Elvey wrote:
> 
> Hi all -
>   I've been poking around with C for a while, but I have big problems
> with linked lists. This seems to be mainly around the "declaration,
> initialisation, iterating" area.  Anyway, I have the code below, which
> compiles but gives a segfault (and I have no idea why), so hoping that
> someone may be able to help.
> ( I have three puts statements at the end because I'm unsure how to
> iterate along a list. )
> [code]
> /* This code is released to the public domain  */
> #include <ctype.h>
> #include <stdio.h>
> #include <stdlib.h>
> #include <string.h>
> #include <sys/stat.h>
> 
> /* Linked list implementation */
> typedef struct _List List;
> 
> struct _List {
>         void *data;
>         List *next;
> };
> 
> static List *list_malloc (void)
> {
>    return (List *) malloc (sizeof (List));
> }
> 
> List *list_prepend (List *list, void *data)
> {
>         List *ret = list_malloc ();
>         ret->data = data;
>         ret->next = list;
>         return ret;
> }
> 
> List *list_append (List *list, void *data)
> {
>         List *ret;
>         if (list == NULL) return list_prepend (list, data);
>         ret = list;
>         for (; list->next; list = list->next);
>         list->next = list_malloc ();
>         list->next->data = data;
>         list->next->next = NULL;
>         return ret;
> }
> 
> void list_free (List *list)
> {
>         List *next;
>         while (list)
>         {
>                 next = list->next;
>                 free (list);
>                 list = next;
>         }
> }
> 
> /* End linked list implementation */
> 
> int main()
> {
> /* Declare a list */
> List *mylist = NULL;
> list_append(mylist, "foo");
> puts(mylist->data);
> list_append(mylist, (int*) 42);
> puts(mylist->data);
> list_append(mylist, "baz");
> puts(mylist->data);
> return 0;
> }
> [/code]
> Very many thanks if you can get this code working...... :)
> - Andy

/* BEGIN new.c */

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

/* Linked list implementation */
typedef struct LIST {
    struct LIST *next;
    void *data;
} List;

List *
list_append(List **head,
            List *tail,
            const void *data,
            size_t size)
{
    List *node;

    node = malloc(sizeof *node);
    if (node != NULL) {
        node -> next = NULL;
        node -> data = malloc(size);
        if (node -> data != NULL) {
            memcpy(node -> data, data, size);
            if (*head != NULL) {
                tail -> next = node;  
            } else {
                *head = node;
            }
        } else {
            free(node);
            node = NULL;
        }
    }
    return node;
}

void 
list_free(List *node, void (*free_data)(void *))
{
    List *next_node;

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

int 
list_fputs(List *node, FILE *stream)
{
    int rc = 0;
    
    while (node != NULL
        && (rc = fputs(node -> data, stream)) != EOF
        && (rc =  putc(        '\n', stream)) != EOF) 
    {
        node = node -> next; 
    }
    return rc;
}

/* End linked list implementation */

int 
main(void)
{
    /* Declare a list */
    List *mylist = NULL;
    List *tail = NULL;
    char *w[] = {"foo", "bar", "bazooka"};
    char **p = w;

    do {
        tail = list_append(&mylist, tail, *p, 1 + strlen(*p));
    } while(tail != NULL && ++p != w + sizeof w / sizeof *w);
    puts("/* BEGIN new.c output */\n");
    list_fputs(mylist, stdout);
    list_free(mylist, free);
    puts("\n/* END new.c output */");
    return 0;
}

/* END new.c */

-- 
pete

[toc] | [prev] | [next] | [standalone]

#7641

On Jul 5, 4:13 pm, pete <pfil...@mindspring.com> wrote:
> Andy Elvey wrote:
>
> > Hi all -
> >   I've been poking around with C for a while, but I have big problems
> > with linked lists. This seems to be mainly around the "declaration,
> > initialisation, iterating" area.  Anyway, I have the code below, which
> > compiles but gives a segfault (and I have no idea why), so hoping that
> > someone may be able to help.
> > ( I have three puts statements at the end because I'm unsure how to
> > iterate along a list. )
> > [code]
> > /* This code is released to the public domain  */
> > #include <ctype.h>
> > #include <stdio.h>
> > #include <stdlib.h>
> > #include <string.h>
> > #include <sys/stat.h>
>
> > /* Linked list implementation */
> > typedef struct _List List;
>
> > struct _List {
> >         void *data;
> >         List *next;
> > };
>
> > static List *list_malloc (void)
> > {
> >    return (List *) malloc (sizeof (List));
> > }
>
> > List *list_prepend (List *list, void *data)
> > {
> >         List *ret = list_malloc ();
> >         ret->data = data;
> >         ret->next = list;
> >         return ret;
> > }
>
> > List *list_append (List *list, void *data)
> > {
> >         List *ret;
> >         if (list == NULL) return list_prepend (list, data);
> >         ret = list;
> >         for (; list->next; list = list->next);
> >         list->next = list_malloc ();
> >         list->next->data = data;
> >         list->next->next = NULL;
> >         return ret;
> > }
>
> > void list_free (List *list)
> > {
> >         List *next;
> >         while (list)
> >         {
> >                 next = list->next;
> >                 free (list);
> >                 list = next;
> >         }
> > }
>
> > /* End linked list implementation */
>
> > int main()
> > {
> > /* Declare a list */
> > List *mylist = NULL;
> > list_append(mylist, "foo");
> > puts(mylist->data);
> > list_append(mylist, (int*) 42);
> > puts(mylist->data);
> > list_append(mylist, "baz");
> > puts(mylist->data);
> > return 0;
> > }
> > [/code]
> > Very many thanks if you can get this code working...... :)
> > - Andy
>
> /* BEGIN new.c */
>
> #include <stdio.h>
> #include <stdlib.h>
> #include <string.h>
>
> /* Linked list implementation */
> typedef struct LIST {
>     struct LIST *next;
>     void *data;
>
> } List;
>
> List *
> list_append(List **head,
>             List *tail,
>             const void *data,
>             size_t size)
> {
>     List *node;
>
>     node = malloc(sizeof *node);
>     if (node != NULL) {
>         node -> next = NULL;
>         node -> data = malloc(size);
>         if (node -> data != NULL) {
>             memcpy(node -> data, data, size);
>             if (*head != NULL) {
>                 tail -> next = node;  
>             } else {
>                 *head = node;
>             }
>         } else {
>             free(node);
>             node = NULL;
>         }
>     }
>     return node;
>
> }
>
> void
> list_free(List *node, void (*free_data)(void *))
> {
>     List *next_node;
>
>     while (node != NULL) {
>         next_node = node -> next;
>         free_data(node -> data);
>         free(node);
>         node = next_node;
>     }
>
> }
>
> int
> list_fputs(List *node, FILE *stream)
> {
>     int rc = 0;
>
>     while (node != NULL
>         && (rc = fputs(node -> data, stream)) != EOF
>         && (rc =  putc(        '\n', stream)) != EOF)
>     {
>         node = node -> next;
>     }
>     return rc;
>
> }
>
> /* End linked list implementation */
>
> int
> main(void)
> {
>     /* Declare a list */
>     List *mylist = NULL;
>     List *tail = NULL;
>     char *w[] = {"foo", "bar", "bazooka"};
>     char **p = w;
>
>     do {
>         tail = list_append(&mylist, tail, *p, 1 + strlen(*p));
>     } while(tail != NULL && ++p != w + sizeof w / sizeof *w);
>     puts("/* BEGIN new.c output */\n");
>     list_fputs(mylist, stdout);
>     list_free(mylist, free);
>     puts("\n/* END new.c output */");
>     return 0;
>
> }
>
> /* END new.c */
>
> --
> pete

Many thanks for that, Pete!  That code is the best that I've seen for
a linked list!
It's good to see some code that's easy to understand.
Thanks again - bye for now -
- Andy

[toc] | [prev] | [next] | [standalone]

#7647

Andy Elvey wrote:
> 
> On Jul 5, 4:13 pm, pete <pfil...@mindspring.com> wrote:
> > Andy Elvey wrote:
> >
> > > Hi all -
> > >   I've been poking around with C for a while, but I have big problems
> > > with linked lists. This seems to be mainly around the "declaration,
> > > initialisation, iterating" area.  Anyway, I have the code below, which
> > > compiles but gives a segfault (and I have no idea why), so hoping that
> > > someone may be able to help.
> > > ( I have three puts statements at the end because I'm unsure how to
> > > iterate along a list. )
> > > [code]
> > > /* This code is released to the public domain  */
> > > #include <ctype.h>
> > > #include <stdio.h>
> > > #include <stdlib.h>
> > > #include <string.h>
> > > #include <sys/stat.h>
> >
> > > /* Linked list implementation */
> > > typedef struct _List List;
> >
> > > struct _List {
> > >         void *data;
> > >         List *next;
> > > };
> >
> > > static List *list_malloc (void)
> > > {
> > >    return (List *) malloc (sizeof (List));
> > > }
> >
> > > List *list_prepend (List *list, void *data)
> > > {
> > >         List *ret = list_malloc ();
> > >         ret->data = data;
> > >         ret->next = list;
> > >         return ret;
> > > }
> >
> > > List *list_append (List *list, void *data)
> > > {
> > >         List *ret;
> > >         if (list == NULL) return list_prepend (list, data);
> > >         ret = list;
> > >         for (; list->next; list = list->next);
> > >         list->next = list_malloc ();
> > >         list->next->data = data;
> > >         list->next->next = NULL;
> > >         return ret;
> > > }
> >
> > > void list_free (List *list)
> > > {
> > >         List *next;
> > >         while (list)
> > >         {
> > >                 next = list->next;
> > >                 free (list);
> > >                 list = next;
> > >         }
> > > }
> >
> > > /* End linked list implementation */
> >
> > > int main()
> > > {
> > > /* Declare a list */
> > > List *mylist = NULL;
> > > list_append(mylist, "foo");
> > > puts(mylist->data);
> > > list_append(mylist, (int*) 42);
> > > puts(mylist->data);
> > > list_append(mylist, "baz");
> > > puts(mylist->data);
> > > return 0;
> > > }
> > > [/code]
> > > Very many thanks if you can get this code working...... :)
> > > - Andy
> >
> > /* BEGIN new.c */
> >
> > #include <stdio.h>
> > #include <stdlib.h>
> > #include <string.h>
> >
> > /* Linked list implementation */
> > typedef struct LIST {
> >     struct LIST *next;
> >     void *data;
> >
> > } List;
> >
> > List *
> > list_append(List **head,
> >             List *tail,
> >             const void *data,
> >             size_t size)
> > {
> >     List *node;
> >
> >     node = malloc(sizeof *node);
> >     if (node != NULL) {
> >         node -> next = NULL;
> >         node -> data = malloc(size);
> >         if (node -> data != NULL) {
> >             memcpy(node -> data, data, size);
> >             if (*head != NULL) {
> >                 tail -> next = node;
> >             } else {
> >                 *head = node;
> >             }
> >         } else {
> >             free(node);
> >             node = NULL;
> >         }
> >     }
> >     return node;
> >
> > }
> >
> > void
> > list_free(List *node, void (*free_data)(void *))
> > {
> >     List *next_node;
> >
> >     while (node != NULL) {
> >         next_node = node -> next;
> >         free_data(node -> data);
> >         free(node);
> >         node = next_node;
> >     }
> >
> > }
> >
> > int
> > list_fputs(List *node, FILE *stream)
> > {
> >     int rc = 0;
> >
> >     while (node != NULL
> >         && (rc = fputs(node -> data, stream)) != EOF
> >         && (rc =  putc(        '\n', stream)) != EOF)
> >     {
> >         node = node -> next;
> >     }
> >     return rc;
> >
> > }
> >
> > /* End linked list implementation */
> >
> > int
> > main(void)
> > {
> >     /* Declare a list */
> >     List *mylist = NULL;
> >     List *tail = NULL;
> >     char *w[] = {"foo", "bar", "bazooka"};
> >     char **p = w;
> >
> >     do {
> >         tail = list_append(&mylist, tail, *p, 1 + strlen(*p));
> >     } while(tail != NULL && ++p != w + sizeof w / sizeof *w);
> >     puts("/* BEGIN new.c output */\n");
> >     list_fputs(mylist, stdout);
> >     list_free(mylist, free);
> >     puts("\n/* END new.c output */");
> >     return 0;
> >
> > }
> >
> > /* END new.c */
> >
> > --
> > pete
> 
> Many thanks for that, Pete!  That code is the best that I've seen for
> a linked list!
> It's good to see some code that's easy to understand.
> Thanks again - bye for now -

You're welcome.
You can also use the same list_append() and list_free()
functions for other data types as well.

/* BEGIN new.c */

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

/* Linked list implementation */
typedef struct LIST {
    struct LIST *next;
    void *data;
} List;

List *
list_append(List **head,
            List *tail,
            const void *data,
            size_t size)
{
    List *node;

    node = malloc(sizeof *node);
    if (node != NULL) {
        node -> next = NULL;
        node -> data = malloc(size);
        if (node -> data != NULL) {
            memcpy(node -> data, data, size);
            if (*head != NULL) {
                tail -> next = node;  
            } else {
                *head = node;
            }
        } else {
            free(node);
            node = NULL;
        }
    }
    return node;
}

void 
list_free(List *node, void (*free_data)(void *))
{
    List *next_node;

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

int 
list_int_fprintf(List *node, FILE *stream)
{
    int rc = 0;
    
    while (node != NULL
        && (rc = fprintf(stream, "%d\n", *(int *)node->data)) > 0) 
    {
        node = node -> next; 
    }
    return rc;
}

/* End linked list implementation */

int 
main(void)
{
    /* Declare a list */
    List *mylist = NULL;
    List *tail = NULL;
    int i[] = {1, 2, 42};
    int *p = i;

    do {
        tail = list_append(&mylist, tail, p, sizeof *p);
    } while(tail != NULL && ++p != i + sizeof i / sizeof *i);
    puts("/* BEGIN new.c output */\n");
    list_int_fprintf(mylist, stdout);
    list_free(mylist, free);
    puts("\n/* END new.c output */");
    return 0;
}

/* END new.c */

-- 
pete

[toc] | [prev] | [next] | [standalone]

#7667

On Jul 5, 1:53 am, Andy Elvey <neptune.poseidon...@gmail.com> wrote:

> int main()
> {
> /* Declare a list */
> List *mylist = NULL;
> list_append(mylist, "foo");
> puts(mylist->data);

Look at the documentation of your compiler and how to turn warnings
on. You should get a compiler warning on the last line and your
program will crash  there; no need even to read the code for
list_append.

[toc] | [prev] | [next] | [standalone]

#7669

"christian.bau" <christian.bau@cbau.wanadoo.co.uk> writes:
> On Jul 5, 1:53 am, Andy Elvey <neptune.poseidon...@gmail.com> wrote:
>> int main()
>> {
>> /* Declare a list */
>> List *mylist = NULL;
>> list_append(mylist, "foo");
>> puts(mylist->data);
>
> Look at the documentation of your compiler and how to turn warnings
> on. You should get a compiler warning on the last line and your
> program will crash  there; no need even to read the code for
> list_append.

You'd get a warning on the puts() call only if the compiler performs
enough dataflow analysis to infer that mylist->data will be a
null pointer at that point.  Typically that's done only when you
enable optimization (because the same analysis that allows certain
optimizations to be performed safely can also reveal such errors).

And there's no guarantee that it would crash.  There have been plenty
of systems on which dereferencing a null pointer doesn't cause any
obvious problems; for example, it might simply read whatever is at
address 0, which might be a zero byte.  (Of course on many systems
it will crash.)

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Nokia
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#7683

On Jul 5, 1:53 am, Andy Elvey <neptune.poseidon...@gmail.com> wrote:
> Hi all -
>   I've been poking around with C for a while, but I have big problems
> with linked lists.

Other people have helped with your specific problems, but I thought it
might help if I made a few general comments. There are two different
ways to go about linked lists, and you don't seem to be aware that
you've made a decision about which to use.

Let's start with this definition:

> struct _List {
>         void *data;
>         List *next;
> };

This is not, actually, a list. It is a node. It stores a pointer to
some data, and a pointer to the next node. Conceptually, a linked list
is a collection of such nodes, each pointing to the next with the last
one pointing to NULL.

You have two options. One is to create a struct that represents a
list. This would be slightly less efficient that what you've done, and
take a bit more writing in the first place, but would probably be
easier to use once you've got it. The other option, the one you are
going for at present, is to treat a pointer to the first node of a
list as being a pointer to the list itself. You need to be careful
using such an approach.

[By way of an analogy - C doesn't really have a type for strings,
unlike many other languages. What is does have is pointers to
characters. When you deal with a "string", you actually have a pointer
to the first character - but a function that is expected that can find
the second character in the next location, the third in the one after
that, etc, until it hits a 0 showing the end of the string. But this
means that you can't, for instance, compare two strings using ==, you
need to call a function. In a similar manner, a pointer to a first
node of a list can be treated as a pointer to the list itself, as long
as that's what the relevant function is expecting.]

So with this approach, when calling a function like this one:

> List *list_prepend (List *list, void *data)
> {
>         List *ret = list_malloc ();
>         ret->data = data;
>         ret->next = list;
>         return ret;
>
> }

you need to do something like:

list = list_prepend(list, data);

ie you need to "catch" the value coming out, and you also need to
"lose" the value of list going in. If you did:

list = list_prepend(list2, data);

then things are likely to go wrong if you ever use list2 again.

If you want to try using the first approach, you will need a struct
for a list which is different from a struct for a node. This may only
need to contain a member "head" pointing to the first node.

If you've seen code using both approaches and not spotted the
difference it's no wonder you're a little confused!

Hope this helps.
Paul.

[toc] | [prev] | [next] | [standalone]

#7695

On Tue, 05 Jul 2011 14:51:34 -0700, Paul N wrote:

> On Jul 5, 1:53 am, Andy Elvey <neptune.poseidon...@gmail.com> wrote:
>> Hi all -
>>   I've been poking around with C for a while, but I have big problems
>> with linked lists.
> 
> Other people have helped with your specific problems, but I thought it
> might help if I made a few general comments. There are two different
> ways to go about linked lists, and you don't seem to be aware that
> you've made a decision about which to use.
> 
> Let's start with this definition:
> 
>> struct _List {
>>         void *data;
>>         List *next;
>> };
> 
> This is not, actually, a list. It is a node. It stores a pointer to some
> data, and a pointer to the next node. Conceptually, a linked list is a
> collection of such nodes, each pointing to the next with the last one
> pointing to NULL.
> 
> You have two options. One is to create a struct that represents a list.
> This would be slightly less efficient that what you've done, and take a
> bit more writing in the first place, but would probably be easier to use
> once you've got it. The other option, the one you are going for at
> present, is to treat a pointer to the first node of a list as being a
> pointer to the list itself. You need to be careful using such an
> approach.
> 
> [By way of an analogy - C doesn't really have a type for strings, unlike
> many other languages. What is does have is pointers to characters. When
> you deal with a "string", you actually have a pointer to the first
> character - but a function that is expected that can find the second
> character in the next location, the third in the one after that, etc,
> until it hits a 0 showing the end of the string. But this means that you
> can't, for instance, compare two strings using ==, you need to call a
> function. In a similar manner, a pointer to a first node of a list can
> be treated as a pointer to the list itself, as long as that's what the
> relevant function is expecting.]
> 
> So with this approach, when calling a function like this one:
> 
>> List *list_prepend (List *list, void *data) {
>>         List *ret = list_malloc ();
>>         ret->data = data;
>>         ret->next = list;
>>         return ret;
>>
>> }
> 
> you need to do something like:
> 
> list = list_prepend(list, data);
> 
> ie you need to "catch" the value coming out, and you also need to "lose"
> the value of list going in. If you did:
> 
> list = list_prepend(list2, data);
> 
> then things are likely to go wrong if you ever use list2 again.
> 
> If you want to try using the first approach, you will need a struct for
> a list which is different from a struct for a node. This may only need
> to contain a member "head" pointing to the first node.
> 
> If you've seen code using both approaches and not spotted the difference
> it's no wonder you're a little confused!
> 
> Hope this helps.
> Paul.

Thanks for the clear explanation. I don't know about the OP, but you 
certainly helped to clear a few things about linked lists up for me. One 
question, is it not possible to have the last node in the list point to 
the first node (instead of NULL), so that traversing past the last node 
will simply cause you to wrap back around to the start of the list?

Todd

[toc] | [prev] | [next] | [standalone]

#7700

On Wed, 6 Jul 2011 03:20:22 +0000 (UTC), Todd Carnes 
<toddcarnes@gmail.com> wrote:
> Thanks for the clear explanation. I don't know about the OP, but 
you 
> certainly helped to clear a few things about linked lists up for 
me. One 
> question, is it not possible to have the last node in the list 
point to 
> the first node (instead of NULL), so that traversing past the last 
node 
> will simply cause you to wrap back around to the start of the list?

That is common for some linked lists that I've seen, but it means 
that walking the list can look like:

  xxx * walker = ..., * head = ...;

  while ((walker = head->next) != head) {
      /* Work with 'walker' */
      /* ...*/
    }

Where head is distinct from other nodes and isn't "worked with" in 
the same way as non-head nodes.

[toc] | [prev] | [next] | [standalone]

#7701

On Tue, 05 Jul 2011 23:37:30 -0400, Shao Miller 
<sha0.miller@gmail.com> wrote:
> On Wed, 6 Jul 2011 03:20:22 +0000 (UTC), Todd Carnes 
> <toddcarnes@gmail.com> wrote:
> > Thanks for the clear explanation. I don't know about the OP, but 
> you 
> > certainly helped to clear a few things about linked lists up for 
> me. One 
> > question, is it not possible to have the last node in the list 
> point to 
> > the first node (instead of NULL), so that traversing past the 
last 
> node 
> > will simply cause you to wrap back around to the start of the 
list?


> That is common for some linked lists that I've seen, but it means 
> that walking the list can look like:


>   xxx * walker = ..., * head = ...;


>   while ((walker = head->next) != head) {

Uhh...  Make that:

  walker = head;
  while ((walker = walker->next) != head) {

>       /* Work with 'walker' */
>       /* ...*/
>     }


> Where head is distinct from other nodes and isn't "worked with" in 
> the same way as non-head nodes.

Sorry!  That was an error.

[toc] | [prev] | [next] | [standalone]

#7703

On Tue, 05 Jul 2011 23:41:32 -0400, Shao Miller 
<sha0.miller@gmail.com> wrote:
> On Tue, 05 Jul 2011 23:37:30 -0400, Shao Miller 
> <sha0.miller@gmail.com> wrote:
> > Where head is distinct from other nodes and isn't "worked with" 
in 
> > the same way as non-head nodes.


> Sorry!  That was an error.

(Not the quoted part, above, though.  Fooey on Usenet-posting from a 
tiny device!)

[toc] | [prev] | [next] | [standalone]

#7704

Or a slightly longer line and a 'for' loop.  Sheesh it's time for 
sleep.  (Excuses, excuses.)

  for (walker = head->next; walker != head; walker = walker->next) {
       /* Work with 'walker' */
       /* ...*/
     }

[toc] | [prev] | [next] | [standalone]

#7748

On Tue, 05 Jul 2011 23:37:30 -0400, Shao Miller <sha0.miller@gmail.com>  
wrote:

> On Wed, 6 Jul 2011 03:20:22 +0000 (UTC), Todd Carnes  
> <toddcarnes@gmail.com> wrote:
>> Thanks for the clear explanation. I don't know about the OP, but
>> you certainly helped to clear a few things about linked lists up
>> for me. One question, is it not possible to have the last node in
>> the list point to the first node (instead of NULL), so that traversing
>> past the last node will simply cause you to wrap back around to the
>> start of the list?
>
> That is common for some linked lists that I've seen, but it means that  
> walking the list can look like:
>
>   xxx * walker = ..., * head = ...;
>
>   while ((walker = head->next) != head) {
>       /* Work with 'walker' */
>       /* ...*/
>     }
>
> Where head is distinct from other nodes and isn't "worked with" in the  
> same way as non-head nodes.

Or, more commonly if you actually have a use for this kind of list
(called a "circular list"), you don't actually distinguish the head
of the list from any other node, and the list doesn't have a "first"
or "last" node.  You would use this, for example, if you wanted to
have a fixed number of buffers for something, and re-use them when
necessary.  Instead of a "head" pointer for this list, you would have
a "newest", or "oldest", or "current" pointer.  If you have a "newest"
or "most_recent" pointer, then oldest == newest->next.

This is beyond the specifics of the C language.  Find a book on data
structures.  The one I used when learning this stuff many years ago was
"Data Structures + Algorithms = Programs", by Niklaus Wirth, which
expressed the concepts in Pascal.
-- 
Morris Keesan -- mkeesan@post.harvard.edu

[toc] | [prev] | [next] | [standalone]

#7757

On 7/6/2011 07:51, Morris Keesan wrote:
> On Tue, 05 Jul 2011 23:37:30 -0400, Shao Miller <sha0.miller@gmail.com>
> wrote:
>
>> On Wed, 6 Jul 2011 03:20:22 +0000 (UTC), Todd Carnes
>> <toddcarnes@gmail.com> wrote:
>>> Thanks for the clear explanation. I don't know about the OP, but
>>> you certainly helped to clear a few things about linked lists up
>>> for me. One question, is it not possible to have the last node in
>>> the list point to the first node (instead of NULL), so that traversing
>>> past the last node will simply cause you to wrap back around to the
>>> start of the list?
>>
>> That is common for some linked lists that I've seen, but it means that
>> walking the list can look like:
>>
>>   xxx * head = ..., * walker = head;
>>
>>   while ((walker = walker->next) != head) {
>>       /* Work with 'walker' */
>>       /* ...*/
>>     }
>>

(Code changed, as elsethread.)

>> Where head is distinct from other nodes and isn't "worked with" in the
>> same way as non-head nodes.
>
> Or, more commonly if you actually have a use for this kind of list
> (called a "circular list"), you don't actually distinguish the head
> of the list from any other node, and the list doesn't have a "first"
> or "last" node. You would use this, for example, if you wanted to
> have a fixed number of buffers for something, and re-use them when
> necessary. Instead of a "head" pointer for this list, you would have
> a "newest", or "oldest", or "current" pointer. If you have a "newest"
> or "most_recent" pointer, then oldest == newest->next.
>
> [...]

Are you sure that's more common?  Are you suggesting that a fixed-count 
list of nodes is a more common use case for a circular list than a 
variable-count list of nodes, or was that example not intended to 
suggest that?

The storage for the "newest" pointer strikes me as akin to a head node; 
it's distinct from the nodes in the list, its lifetime (not to be 
confused with the Standard term) is most likely at least the lifetime of 
the list, and it points to within the list.  No?

If the simplest node in a singly-linked list is:

   struct node { struct node * next; };

then the object representation for a head node might exactly correspond 
to the object representation for a "newest" pointer.  Right?  A "head" 
node needn't suggest that a circular list has a "beginning" and an 
"end," need it?  It can just be a "point of interest," I think.  Perhaps 
"head" isn't the best term, though it's a means to "head into" the list. ;)

(This "simplest" 'struct node' is an example of where a function working 
with such a node knows the location of the relevant data, given the 
location of the node, perhaps using 'offsetof' or derivatives such as 
'container_of' or 'CONTAINING_RECORD'.  As in: 'struct some_data { int 
ia[10]; struct node node; };')

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.c

csiph-web