incomplete type problem c

trashcat · 2010-03-15 23:42:14

hey all,

I'm getting a rather inexplicable error in this linkedlist c program I'm writing.
When I try to compile it gives me the error "[trashcat@Phaedo csci241]$ gcc -lm -o lltest lltest.c linkedlist.c
~lltest.c: In function 'main':
~lltest.c:27: error: dereferencing pointer to incomplete type

the code in the library is as follows:

#include<stdio.h>
#include<stdlib.h>
#include "linkedlist.h"


//this defines a node for the linked list


struct node{
    Item data;
    struct node *next;
};

struct linked_list{
   struct node *head;
   struct node *cursor;
   struct node *tail;
};

void append(linkedlist l, Item i){
   //creating a pointer to a new node
   struct node *p;
   
   //allocating memory for a new node and making p point to it
   p = (struct node *) malloc(sizeof(struct node));
   
   //setting the data part of p
   p->data = i;
   
   //appending p to the end of the list
   l->tail->next = p;
   //making the end of the list point to p
   l->tail = p;
}

//returns 1 if there is a next, 0 otherwise
int next(linkedlist l){
   if(l->cursor->next != NULL){
      l->cursor = l->cursor->next;
      return 1;
   }
   return 0;
}

void reset(linkedlist l){
   l->cursor = l->head;
}

void insert(linkedlist l, Item data){
   struct node *p;

   p = (struct node *) malloc(sizeof(struct node));

   p->next = l->cursor->next;
   l->cursor->next = p;
}

Item getcursor(linkedlist l){
   return l->cursor->data;
}

//returns 1 if there is an element to remove, 0 otherwise
int delete(linkedlist l){
   if(l->cursor != NULL){
      l->cursor = l->cursor->next;
      return 1;
   }
   return 0;  
}

linkedlist create(Item d){
   linkedlist l = malloc(sizeof(struct linked_list));
   l->head->data = d;
   l->tail = l->head;
   l->cursor = l->head;
   return l;
}

the code in the testing program is:

#include<stdio.h>
#include<stdlib.h>
#include "linkedlist.h"


int main(){
   Item i = 2;
    linkedlist l = create(i);
   printf("%d", l->cursor->data);

   return 0;
}

the header is as follows:

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

typedef int Item;

typedef struct linked_list *linkedlist;

/*****************************************
 *our functions:
 ****************************************/
void append(linkedlist l, Item i);
int next(linkedlist l);
void reset(linkedlist l);
void insert(linkedlist l, Item i);
Item getcursor(linkedlist l);
int delete(linkedlist l);
linkedlist create(Item d);



#endif

...I apologize for the lack of comments. The problem isn't in the code though (not the functions). If I try to instantiate a node struct the compiler complains about it being an incomplete type. Can anyone tell me why...any node I've ever written for any other program has had the exact same definition.

I've been running: gcc -o lltest lltest.c linkedlist.c to compile the program.

falconindy · 2010-03-16 00:19:35

A few problems, as I see it:

* You're allocating memory for the list itself, but not for the new node itself.
* Your head and tail should be pointers to a node, not nodes of their own.
* You're never freeing the memory you malloc.

You've got a perfectly good insert function that properly allocates memory for a node and inserts it. Check for the existance of a null head/tail in there, and deal with creating a new list in that function. Also, given that this is a singly linked list you really don't need a tail and a head pointer. When adding a node, just link the new node to the head and reset your head pointer. Your cursor is also arguably superfluous. Singly linked lists should be built for speed.

Amusing, I just did this over the weekend. I was bored of the BS homework I was getting in Java and C++ and decided to get back to the one true religion. The GitHub link in my sig shows the data structures I threw together, including a singly and doubly linked list.

Trent · 2010-03-16 01:02:36

Line numbers don't help me to diagnose the problem unless your code has appropriate line numbering as well. By my count, line 27 is a comment.

Question: how are you deciding what code to put in the header file and what to put in the others? It seems a bit, well, confusing.

Bralkein · 2010-03-16 01:11:59

Hi, my C is a bit rusty but I managed to get your code to compile by rearranging what goes into the header file.

If I remember correctly, you have to imagine that the #include statement copy-pastes the contents of the header file straight in. Then the separate files are compiled and linked together. So in your main file, the compiler knows that "linkedlist" type is a typedef to a struct linked_list pointer... but it doesn't know what the struct linked_list is, because there is no information about it in the linkedlist.h header. So when you start doing stuff with your linkedlist type by accessing its members and whatnot, it doesn't know what to make of it.

If you rearrange what is in the header then you will find that it compiles. It segfaults when you run it though, probably due to the issues mentioned by falconindy.

That's my take anyway, sorry though cause my C is rusty as I said.

trashcat · 2010-03-16 02:29:01

yeah, thing is I copied that header almost word for word from a textbook on creating a stack...and the form of the linkedlist.c (from a stack.c file).
So I assumed it would work. The reason that the test file knows (should know) what the linked_list is is because it is defined in linkedlist.c, and the incomplete type is allowed in the .h (because it is left unassigned).

...the reason for not defining the linked_list in the header is that when you go to write another list, like an arraylist, you should be able to leave the header alone. theoretically anyway. (or so the textbook claims).

In defense of my linkedlist structure having a head and a tail--I know that these are superfluous in a more limited linked list, but I couldn't think of any better way to have an append function than to keep track of the tail. It's really slightly more complicated than a simple linked list.

Thanks for the help guys. sorry about not including line numbers.

Last edited by trashcat (2010-03-16 02:35:18)

the_isz · 2010-03-16 06:53:19

Is this solved already? Because if not, here's my suggestion: Though I've never
programmed plain C, I suspect this line to be the problem:

p = (struct node *) malloc(sizeof(struct node));

Shouldn't this be more like

p = (node*) malloc(sizeof(node));

? Because using the struct keyword here would create a forward declaration to a
locally defined struct node, which overrides the globally defined one, resulting
in an incomplete type when dereferencing p.

But I could be totally wrong. Like I said, I never used plain C

Good luck, anyway.

falconindy · 2010-03-16 11:36:42

the_isz wrote:

Is this solved already? Because if not, here's my suggestion: Though I've never
programmed plain C, I suspect this line to be the problem:
p = (struct node *) malloc(sizeof(struct node));
Shouldn't this be more like
p = (node*) malloc(sizeof(node));
? Because using the struct keyword here would create a forward declaration to a
locally defined struct node, which overrides the globally defined one, resulting
in an incomplete type when dereferencing p.
But I could be totally wrong. Like I said, I never used plain C
Good luck, anyway.

In order to reference a struct by its name alone, you have to declare a typedef for it. I prefer to do the malloc at the time of declaration:

struct node *p = malloc(sizeof(struct node));

As long as you're writing plain C, you don't need to coerce the return from malloc. That's a C++ thing.

trashcat · 2010-03-16 12:29:25

It's resolved. It turned out that the header was correct and that I merely had to allocate memory for the head pointer in the create() function, and that I cannot manipulate the nodes themselves from the lltest.c because of the way that everything is set up (which is kinda what you want with an ADT anyway). So the textbook was right, and I just screwed up by trying to access the nodes directly and not allocating memory for the head node.

It's just one of those things that if you don't ask someone else you'll go on staring at the code forever.

thanks,
trashcat

the_isz · 2010-03-16 13:40:20

falconindy wrote:

In order to reference a struct by its name alone, you have to declare a typedef for it. I prefer to do the malloc at the time of declaration:
struct node *p = malloc(sizeof(struct node));
As long as you're writing plain C, you don't need to coerce the return from malloc. That's a C++ thing.

Thanks for the explanation. Good that I know understanding C++ is by far not the
same as understanding C

Arch Linux

#1 2010-03-15 23:42:14

incomplete type problem c

#2 2010-03-16 00:19:35

Re: incomplete type problem c

#3 2010-03-16 01:02:36

Re: incomplete type problem c

#4 2010-03-16 01:11:59

Re: incomplete type problem c

#5 2010-03-16 02:29:01

Re: incomplete type problem c

#6 2010-03-16 06:53:19

Re: incomplete type problem c

#7 2010-03-16 11:36:42

Re: incomplete type problem c

#8 2010-03-16 12:29:25

Re: incomplete type problem c

#9 2010-03-16 13:40:20

Re: incomplete type problem c

Board footer