Thread: Reverse Linked list

  1. #1
    Registered User
    Join Date
    Sep 2016
    Posts
    41

    Reverse Linked list

    I keep getting this error:

    Code:
    main.c:55:8: error: dereferencing pointer to incomplete type ‘struct structptr’
         toe->ptr = malloc(sizeof(structptr));
            ^~

    From this code.



    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <stdbool.h>
    
    
    typedef struct {
        
    } blank;
    
    
    typedef struct {
        
        struct blank *ptr;
        struct data_node *data; 
        
    } structptr;
    
    
    typedef struct {
        
        int val;
        float x;
        float y;
        char test;
        
    } data_node;
    
    
    struct structptr *toe = NULL;
    struct structptr *curr = NULL;
    struct structptr *node_t = NULL;
    struct blank *ptr = NULL;
    struct data_node *data = NULL;
    
    
    struct structptr  *create_rootfn(){
        
        toe = malloc(sizeof(structptr));
        if(toe == NULL){
            return NULL;
            printf("%s", "create_rootfn failed");
        }
        
        //toe->ptr = NULL;
        toe->ptr = malloc(sizeof(structptr));
        toe->ptr = NULL;
        
        toe->data = malloc(sizeof(structptr));
        toe->data->val = 0;
        toe->data->x = 0;
        toe->data->y = 0;
        toe->data->test = 1;
    
    
        printf("create_rootfn completed\n toe address = %p\n float = %f\n", toe, toe->data->x);    
        return toe;    
    }

    Nevermind what I'm doing and why there is a blank struct, that is irrelevant. Trust me, I've moved things around and the blank struct has no bearing on the outcome. I know it's 'not-standard', but this is an experiment into writing linked lists in reverse. Either way, doesn't matter. I have declared the appropriate structs and nothing seems to work.

    I also thought the sizeof parameter might be causing the issue:

    Code:
    toe->data = malloc(sizeof(structptr));
    So I tried to dereference toe, like this:

    Code:
    toe->data = malloc(sizeof(*toe));

    But that throws the same error.

    Interestingly enough, I CAN use toe as parameter to sizeof here:

    Code:
    toe = malloc(sizeof(toe));
        if(toe == NULL){
            return NULL;
            printf("%s", "create_rootfn failed");
        }
    And it works...

    Any advice as to why this error is thrown would be greatly appreciated. Please refrain from commenting on the validity of the experiment or better ways to write linked lists.

    If viewing the entire code would help in solving this quandary, then you have only to ask.

    Cheers,
    MedicineMan25

  2. #2
    Registered User
    Join Date
    Sep 2016
    Posts
    41
    I have had a play around and it seems to be related to the way I declare, I can't seem to declare a global struct pointer. I have to declare it straight then and there before use, so this half works:

    Code:
    struct structptr *toe = malloc(sizeof(toe)); <<<<<<<<<<<<<<
        if(toe == NULL){
            return NULL;
            printf("%s", "create_rootfn failed");
        }
            
        toe->data = malloc(sizeof(data_node));
        toe->data->val = 0;
        toe->data->x = 0;
        toe->data->y = 0;
        toe->data->test = 1;
    but this part still throws an error:

    Code:
    struct structptr *toe = malloc(sizeof(toe)); 
        if(toe == NULL){
            return NULL;
            printf("%s", "create_rootfn failed");
        }
            
        toe->data = malloc(sizeof(data_node)); <<<<<<<<<<<<<<<<<<<
        toe->data->val = 0;
        toe->data->x = 0;
        toe->data->y = 0;
        toe->data->test = 1;
    I can't seem to allocate memory to struct members of structs. But that can't be true... then we wouldn't be able to implement linked lists in the first place.

  3. #3
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    38,068
    > struct structptr *toe = malloc(sizeof(toe));
    You're allocating the size of the pointer, not the size of what it points to.

    In fact, most of your sizeof's seem to be chosen at random.

    Stick to this form:
    p = malloc( sizeof(*p) );
    Let the compiler dereference the type information at compile time.

    > toe->ptr = malloc(sizeof(structptr));
    > toe->ptr = NULL;
    This leaks memory, and gives you a nice segfault if you try and use toe->ptr later on.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  4. #4
    Registered User
    Join Date
    Sep 2014
    Posts
    364
    Quote Originally Posted by MedicineMan25 View Post
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <stdbool.h>
    
    typedef struct {
        
    } blank;
    
    typedef struct {
        struct blank *ptr;
        struct data_node *data; 
    } structptr;
    
    typedef struct {
        int val;
        float x;
        float y;
        char test;
    } data_node;
    …
    You define type's, not struct's.
    Your type 'structptr' include a member with the type 'struct blank *'.
    But this type is unknown. Also the member data is a unknown type 'struct data_node *'.
    Second, the type 'data_node' is not known at the time you define 'structptr'.
    So, the correct way is:
    Code:
    …
    typedef struct {
        
    } blank;
    
    typedef struct {
        int val;
        float x;
        float y;
        char test;
    } data_node;
    
    typedef struct {
        blank *ptr;
        data_node *data; 
    } structptr;
    …
    Also your global variables are type's, not struct's:

    Code:
    structptr *toe = NULL;
    structptr *curr = NULL;
    structptr *node_t = NULL;
    blank *ptr = NULL;
    data_node *data = NULL;
    The function should then look like this:
    Code:
    structptr *create_rootfn(void) {
        
        if ((toe = malloc(sizeof(*toe))) == NULL) {
            printf("no memory for toe!\n");
            return NULL;
        }
    
        if ((toe->ptr = malloc(sizeof(*(toe->ptr)))) == NULL) {
            printf("no memory for toe->ptr!\n");
            free(toe);
            return NULL;
        }
    
        if ((toe->data = malloc(sizeof(*(toe->data)))) == NULL) {
            printf("no memory for toe->data!\n");
            free(toe->ptr);
            free(toe);
            return NULL;
        }
    
        toe->data->val = 0;
        toe->data->x = 0.1;
        toe->data->y = 0.2;
        toe->data->test = 'A';
    
        printf("create_rootfn completed\ntoe address = %p\nfloat = %f\n", (void *) toe, toe->data->x);    
        return toe;
    }
    As you can see, the function returns now a 'structptr *' and not a 'struct structptr *'.
    I have also optimized the check for memory allocation.
    If you write a function to allocate memory (like the above), its a good practice to write also a function to free all the memory in one call.

    Code:
    void free_rootfn(structptr **x) {
        structptr *y = *x;
        free(y->ptr);
        free(y->data);
        free(y);
        *x = NULL;
    }
    Last edited by WoodSTokk; 10-12-2016 at 05:56 PM.
    Other have classes, we are class

  5. #5
    Registered User
    Join Date
    Sep 2016
    Posts
    41

    > struct structptr *toe = malloc(sizeof(toe));
    You're allocating the size of the pointer, not the size of what it points to.

    In fact, most of your sizeof's seem to be chosen at random.

    Stick to this form:
    p = malloc( sizeof(*p) );
    Let the compiler dereference the type information at compile time.

    > toe->ptr = malloc(sizeof(structptr));
    > toe->ptr = NULL;
    This leaks memory, and gives you a nice segfault if you try and use toe->ptr later on.


    Yes I remembered that from out last lesson, but I tried to allocate the size of the pointer by dereferencing and it wouldn't even compile. I guess I should have been asking other questions at that point.

    Hence why I tried to just allocate with the type.


    Code:
    
    
    Code:
    Code:
    [COLOR=white !important]?
    
    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
    #include <stdio.h> #include <stdlib.h> #include <string.h> #include <stdbool.h> typedef struct { } blank; typedef struct { struct blank *ptr; struct data_node *data; } structptr; typedef struct { int val; float x; float y; char test; } data_node; …
    [/COLOR]


    You define type's, not struct's.

    Your type 'structptr' include a member with the type 'struct blank *'.
    But this type is unknown.


    But I thought that I had defined them and thus made them a known type. Ok, I will look more into using typedef properly. I have obviously done something incorrectly here.


    Code:
    The function should then look like this:
    Code:
    Code:
    [COLOR=white !important]?
    
    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
    structptr *create_rootfn(void) { if ((toe = malloc(sizeof(*toe))) == NULL) { printf("no memory for toe!\n"); return NULL; } if ((toe->ptr = malloc(sizeof(*(toe->ptr)))) == NULL) { printf("no memory for toe->ptr!\n"); free(toe); return NULL; } if ((toe->data = malloc(sizeof(*(toe->data)))) == NULL) { printf("no memory for toe->data!\n"); free(toe->ptr); free(toe); return NULL; } toe->data->val = 0; toe->data->x = 0.1; toe->data->y = 0.2; toe->data->test = 'A'; printf("create_rootfn completed\ntoe address = %p\nfloat = %f\n", (void *) toe, toe->data->x); return toe; }
    [/COLOR]
    This still does not compile. It throws the same error as before. Still the same problem of not being about to allocate memory to members of the struct. Even with all the corrections you suggested. The only way this compiles is if I allocate sizeof(*toe), but that's not the right size and may cause memory leaks. The deference operator seems to break everything.

    As you can see, the function returns now a 'structptr *' and not a 'struct structptr *'.
    I honestly can't see the difference here. You may have to spell that out for me.

    I have also optimized the check for memory allocation.
    Good call on the memory allocation, something I haven't gotten around to just yet with this code coz im lazy, should really stop doing that as it's a stupid-bad habit.


    I will try and use a simple struct definition rather than typedef and see if that makes this a little easier. Will still look into typedefs in depth.

  6. #6
    Registered User
    Join Date
    Sep 2016
    Posts
    41
    Ok, so I figured all of my mess out. I did a silly.

    Code:
    typedef struct{
        
    }blank;
    Like you said; this declares blank as an instance of 'something that wasn't defined', type 'struct'. I should have done this:

    Code:
    typedef struct blank{
        
    };


    That would then defined blank as type struct. After that I could declare instances as I saw fit. But I didn't do that. Silly.

    That led to other issues of dereferencing to the appropriate size (it would dereference to structptr; an instance of an undefined type. All of which makes complete sense now) , @Salem; I had remembered what you taught me and it really confused me why it didn't work. As I said earlier: I should have been asking other questions at that point, I will of course stick to letting the compiler dereference. That is the good path to many happiness. Other issues were the undefined type. The answer really is in the title there; 'you didn't define the type, derr'.

    Everything makes sense now.

    Thanks guys for your time and attention, much appreciated.

    MedicineMan25


  7. #7
    Registered User
    Join Date
    Sep 2014
    Posts
    364
    Quote Originally Posted by MedicineMan25 View Post
    Ok, so I figured all of my mess out. I did a silly.

    Code:
    typedef struct{
        
    }blank;
    Like you said; this declares blank as an instance of 'something that wasn't defined', type 'struct'. I should have done this:

    Code:
    typedef struct blank{
        
    };


    That would then defined blank as type struct. After that I could declare instances as I saw fit. But I didn't do that. Silly.

    That led to other issues of dereferencing to the appropriate size (it would dereference to structptr; an instance of an undefined type. All of which makes complete sense now) , @Salem; I had remembered what you taught me and it really confused me why it didn't work. As I said earlier: I should have been asking other questions at that point, I will of course stick to letting the compiler dereference. That is the good path to many happiness. Other issues were the undefined type. The answer really is in the title there; 'you didn't define the type, derr'.

    Everything makes sense now.

    Thanks guys for your time and attention, much appreciated.

    MedicineMan25

    If I define struct's and type's, I added allways a prefix.
    struct become the prefix '_s'.
    type become the prefix '_t'.
    With this naming it is harder to confuse your self.

    This define a struct named 'foo_s'. There is no type defined.
    Code:
    struct foo_s {
        …
    }
    
    // using with
    struct foo_s bla;
    This define a struct named 'foo_s' and define a type named 'foo_t'.
    Code:
    typedef struct foo_s {
        …
    } foo_t;
    
    // using with one of
    struct foo_s bla;
    foo_t bla;
    This define a type named 'foo_t' based on an unnamed struct.
    Code:
    typedef struct {
        …
    } foo_t;
    
    // using with
    foo_t bla;
    Last edited by WoodSTokk; 10-13-2016 at 07:07 PM.
    Other have classes, we are class

  8. #8
    Registered User
    Join Date
    Sep 2016
    Posts
    41
    ah yes.. now I understand why there is wchar_t and other such typedef names. I will utilise your tip of extending this convention to structs and other types. Thanks!!!

  9. #9
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,784
    Quote Originally Posted by WoodSTokk
    This define a struct named 'foo_s'. There is no type defined.
    Code:
    struct foo_s {
        …
    }
     
    // using with
    struct foo_s bla;
    Not quite: "a structure is a type consisting of a sequence of members", i.e., the struct declaration declares a struct type named struct foo_s (and borrowing from C++ terminology we could say this is a definition of the struct type), and then the later declaration declares (and defines, at least tentatively since there is no extern specifier) an object named bla of type struct foo_s. foo_s itself is not a struct, whether in the sense of a struct type or an object; foo_s is a struct tag name.

    Quote Originally Posted by WoodSTokk
    This define a struct named 'foo_s' and define a type named 'foo_t'.
    Code:
    typedef struct foo_s {
        …
    } foo_t;
     
    // using with one of
    struct foo_s bla;
    foo_t bla;
    No, that defines a struct named struct foo_s, while also defining foo_t as an alias of that struct type. As before, foo_s by itself is only a struct tag name.

    I don't see any value in adding a _s suffix (not prefix: that would go in the front portion of the name, whereas a suffix goes at the back) to struct tag names. The type name will already be prefixed by struct, making it obvious that it is a struct type. If you are using a typedef to declare an alias for the struct type name (or to name an anonymous struct type), a _t suffix might be useful so you can declare a "generic" object of that type using the same name without conflict, but then if you are programming with respect to the POSIX standard, such names are reserved to the implementation (and even if you are not, the C standard does reserve a few patterns of such names, though you're unlikely to conflict).
    Last edited by laserlight; 10-26-2016 at 06:40 AM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. reverse linked list
    By telmo_d in forum C Programming
    Replies: 7
    Last Post: 10-31-2015, 06:08 AM
  2. Linked list reverse recursively
    By gaurav_13191 in forum C Programming
    Replies: 4
    Last Post: 12-07-2011, 09:32 AM
  3. how to reverse items in linked list?
    By ilikeapplepie in forum C Programming
    Replies: 8
    Last Post: 04-09-2011, 11:15 PM
  4. Reverse function for linked list
    By Brigs76 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2006, 10:01 AM
  5. reverse a singly linked list
    By ivandn in forum C Programming
    Replies: 15
    Last Post: 12-18-2001, 05:33 PM

Tags for this Thread