Linked list

[fskrillex]

Hi guys, I'm a guy learning C, and I have a problems doing something simple like traversing a linked list.

The list is defined by these files: (no need to read all of that really, the problem is at the end of the post)

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




/*
 * List implementation
 */
 
typedef struct listnode node_t;
struct listnode {
    node_t    *next;
    void        *item;
};


struct list {
    node_t     *head;
    int     numitems;
};




// Create new list
list_t *list_create(void)
{
    list_t *list;


    list = (list_t*)malloc(sizeof(list_t));
    if (list == NULL)
        goto error;
    list->head = NULL;
    list->numitems = 0;


    return list;
 error:
    return NULL;
}


// Free list. items not freed.
void list_destroy(list_t *list)
{
    node_t *node, *tmp;


    node = list->head;
    while (node != NULL) {
        tmp = node->next;
        free(node);
        node = tmp;
    }
    free(list);
}




// Create new list node.  Function declared static => only visible within this file
static node_t *list_newnode(void *item)
{ 
    node_t *node;


    node = (node_t*)malloc(sizeof(node_t));
    if (node == NULL)
        goto error;
    node->next = NULL;
    node->item = item;


    return node;
 error:
    return NULL;
}


// Free list node. Return node item
static void *list_destroynode(node_t *node)
{
    void *item;
    
    item = node->item;
    free(node);
    return item;
}


// Insert item first in list
int list_addfirst(list_t *list, void *item)
{
    node_t *node;


    node = list_newnode(item);
    if (node == NULL)
        goto error;


    if (list->head != NULL)
        node->next = list->head;
    list->head = node;
    list->numitems++;


    return 0;
 error:
    return -1;
}




// Insert item last in list.
int list_addlast(list_t *list, void *item)
{
    node_t *node, *current;


    node = list_newnode(item);
    if (node == NULL)
        goto error;


    current = list->head;
    if (current == NULL) {
    // Empty list, insert first
        list->head = node;
    } else if (current->next == NULL) {
    // List contains one item, insert after head
        current->next = node;
    } else {
    // Traverse until current points to node before last node
        while (current->next->next != NULL) {
            current = current->next;
    }
        current->next->next = node;
    }
    list->numitems++;


    return 0;
 error:
    return -1;
}




void *list_removefirst(list_t *list)
{
    node_t    *node;


    if (list->head == NULL)
        return NULL;
    node = list->head;
    list->head = node->next;
    list->numitems--;
    return list_destroynode(node);
}






// Remove item from list
int list_remove(list_t *list, void *item)
{
    node_t *current;
    node_t *node;


    node = NULL;
    if (list->head == NULL) {
    // Empty list
        goto error;
    } else if (list->head->item == item) {
    // Remove head
    node = list->head;
        list->head = node->next;
    } else {
    // Search for item
    // NOTE: AND conditions (&&) inside for/while/if are evaluated from left to right. 
    //     If one fails, the remaining conditions are not evaluated.
    current = list->head;
        while (current->next != NULL && current->next->item != item)
      current = current->next;
    if (current->next == NULL)
      goto error;
    node = current->next;
    current->next = node->next;
    }
    
    list_destroynode(node);
    list->numitems--;
    return 0;
error:
    return -1;
}








// Return # of items in list
int list_size(list_t *list)
{
    return list->numitems;   
}






/*
 * Iterator implementation
 */
 


struct list_iterator {
    node_t *next;
    list_t *list;
};




// Create new list iterator
list_iterator_t *list_createiterator(list_t *list)
{
    list_iterator_t *iter;


    iter = (list_iterator_t*)malloc(sizeof(list_iterator_t));
    if (iter == NULL)
        goto error;
    iter->list = list;
    iter->next = list->head;


    return iter;
 error:
    return NULL;
}




// Free iterator
void list_destroyiterator(list_iterator_t *iter)
{
    free(iter);
}




// Move iterator to next item in list and return current.
void *list_next(list_iterator_t *iter)
{
    void *item;


    item = NULL;
    if (iter->next != NULL) {
        item = iter->next->item;
        iter->next = iter->next->next;
    }


    return item;
}




// Let iterator point to first item in list again
void list_resetiterator(list_iterator_t *iter)
{
    iter->next = iter->list->head;   
}

#ifndef LIST_H_#define LIST_H_


/*
 * List interface
 */


struct list;
typedef struct list list_t;


// Create new list
list_t *list_create(void);


// Free list. All nodes are freed, but not items pointed to by nodes.
void list_destroy(list_t *list);


// Insert item first in list
int list_addfirst(list_t *list, void *item);


// Insert item last in list
int list_addlast(list_t *list, void *item);


// Remove first item in list
void *list_removefirst(list_t *list);


// Remove item from list
int list_remove(list_t *list, void *item);


// Return # of items in list
int list_size(list_t *list);






/*
 * List iterator interface
 */
 
struct list_iterator;
typedef struct list_iterator list_iterator_t;


// Create new list iterator
list_iterator_t *list_createiterator(list_t *list);


// Free iterator
void list_destroyiterator(list_iterator_t *iter);


// Move iterator to next item and return current
void *list_next(list_iterator_t *iter);


// Let iterator point to first item in list
void list_resetiterator(list_iterator_t *iter);


#endif /*LIST_H_*/

Now in my main.c, I have this bunch of objects, which are just geometrical data. (triangles and stuff). They are defined through object_t.

My plan is that each of these objects should be placed in the linked list, and then I could loop through the list and send each object to a function called DrawObject().

//It calls a function CreateObject that basically initializes some of it's values. The parameters are just (SDL_surface, model, number of  triangles in the model)
object_t *testobject1 = CreateObject(screen, triangle_model, 3);
object_t *testobject2 = CreateObject(screen, triangle_model, 3);
object_t *testobject3 = CreateObject(screen, triangle_model, 3);

list_t *geoList = list_create();
list_addfirst(geoList, testobject1);
list_addlast(geoList, testobject2);
list_addlast(geoList, testobject3);

list_iterator_t *iterator = list_createiterator(geoList);

int j = 0; 
while (j < list_size(geoList))
{
            DrawObject(geoList);
            geoList = list_next(iterator)
            j++; 
}
SDL_UpdateRect(screen, 0, 0, screen->w, screen->h);

The program hangs and nothing is drawn, and I get the following error message: warning: passing arg 1 of `DrawObject' from incompatible pointer type.

The drawobject function is supposed to recieve a parameter or type DrawObject(object_t *object);.
So I assume it's something wrong with the way I try to pass the list elements to it. Any suggestions are appreciated.

[anduril462]

Of course you're getting that error. You pass geoList to DrawObject, but geoList is a pointer to list_t, not a pointer to object_t or a void pointer, so the types are incompatible. list_next returns the item, which is of void * type (but actually contains an object_t pointer since that's what you added). You assign that to geoList, which is of type list_t pointer. Then, you call list_size(geoList) on the next iteration of the loop, but geoList no longer points to a valid list_t object, it points to an object_t, so list_size is operating on bogus data. This also trashes geoList, so you can't free it when you're done. You need another pointer to hold the return value from list_next:

list_iterator_t *iterator = list_createiterator(geoList);
void *item;

for (j = 0; j < list_size(geoList); j++) {
    item = list_next(iterator);
    // do something with item
}