Help analyzing a linked list program

aijazbaig1 · #1 17-Jul-2007, 03:39

hello.
I have been trying to study some examples concerning the management of simple singly linked lists from the book: "mastering algorithms with C". Here are some of the questions that I have come across:

I am not able to follow some of the code given to manage a simple linked list. to be specific, the prototype for the function which initializes the list is as follows:

CPP / C++ / C Code:

void list_init(List *list,void (*destroy)(void *data));

here the struct list looks like:

CPP / C++ / C Code:

typdef struct Listelmt_ {
void *data;
struct ListElmt_ *nest;
} Listelmt;

typedef struct List_ {
int size;
int (*match)(const void *key1,const void *key2);
void (*destroy)(void *data);

Listelmt *head;
Listelmt *tail;
} List;

What I do not understand is the statement which reads:

Quote:

the destroy argument provides a way to free dynamically allocated data when List_destroy is called.for ex. if the list contains data dynamically alocated using malloc, destroy argument should be set to free to free the data as the list is destroyed........

Does it imply that one should call this function with one of the arguments being the standard free function which has a similar prototype as that of the destroy function pointer above? If yes then why are we declaring destroy as a function pointer and not a plain function?

next question:
there is a function used to remove an element after a given element in the linked list which is declared as:
CPP / C++ / C Code:
int list_rem_next(List *list, Listelmt *element, void **data);
where the typedefs for Listelmt and List hold from the above mentioned source code. As data in the definition of Listelmt was declared a pointer to void; it is obvious that in order to modify that pointer we need to pass a pointer to it which is exactly what the local variable data in the function prototype for list_rem_next above stands for.

Now this function is used in the definition of a certain function called list_destroy wherein it is called in the following way:
CPP / C++ / C Code:
if (list_rem_next(list, NULL, (void **)&data) == 0 && List -> Destroy != NULL)
now this function list_destroy actually has a variable called data which is actually a void pointer i.e.
CPP / C++ / C Code:
void *data;
From that one can conclude that , while calling the function list_rem_next he has casted this void pointer into a type which is a pointer to a void pointer; isn't it?

But when one appends the '&' sign with the 'data' variable, which has already been declared to be a void pointer, wouldn't it automatically mean that we need the address of 'data' and '&data' would automatically be of the type "pointer to a pointer to void" isn't it?

Why then has the author chose to cast it explicitly into that type when it happens automatically? Am i understanding it correctly or is it something else?

Waitin for comments from you,

dsmith · #2 17-Jul-2007, 08:36

Not sure how much help I can be, but here are some of my thoughts.

The destroy function is actually a function that needs to be written by the user of the list, as is the match function. Therefore when you use this list implementation, you need to pass a function that tells the list how to properly delete data.

This solves a problem in that the list can hold any type of data, allocated in a number of ways, ie malloc or new. This allows the user to properly free (or delete) this memory.

As for the type-casting, it may just be that the compiler gets confused. I am not sure on that. Your premise seems correct in that it should be a void** by default.

Have you implemented this list or are you just trying to dissect it right now?

aijazbaig1 · #3 17-Jul-2007, 10:08

Hi there and thanks for your comments.
In addition i would like to draw attention to ur quote:

Quote:

The destroy function is actually a function that needs to be written by the user of the list, as is the match function. Therefore when you use this list implementation, you need to pass a function that tells the list how to properly delete data.

as per the book (in its own words):

Quote:

if the list contains data dynamically allocated using malloc, destroy should be set to free in order to free the data as the linked list is destroyed. For structured data containing several dyamically allocated members, destroy should be set to a user defined function which calls free for each dynamically allocated member as well as for the structure itself. For a linked list that shouldn't be freed, destroy shd be set to NULL

Now according to the book, it can be interpreted that the free function that they are referring to is indeed the "standard" free function since it has the same prototype as the destroy function except that destroy is a pointer. What if I pass the said free function such that destroy now points to this free function. will that work?

Quote:

Have you implemented this list or are you just trying to dissect it right now?

I haven't implemented it yet but I am trying to get to grips with this program and then try to see if i could come up with something of my own on similar lines..albeit a bit more easier to read if not so compact(if at all this program is

).

davekw7x · #4 17-Jul-2007, 11:49

Quote:

Originally Posted by aijazbaig1

From that one can conclude that , while calling the function list_rem_next he has casted this void pointer into a type which is a pointer to a void pointer; isn't it?

Your analysis is correct: Since data is a pointer to void, &data is a pointer to pointer to void. So the cast is redundant.

Quote:

Originally Posted by aijazbaig1

Why then has the author chose to cast it explicitly into that type when it happens automatically?

I have no idea. But it's not a Bad Thing to wonder about.

Lots of times (not in this case, I'm thinking) people use casts to suppress a compiler warning or error message about some suspicious usage. Use of seemingly superfluous casts is always a red flag to me (well, maybe a yellow flag). If a program has to use a cast where none should be required, maybe it's because a function prototype is missing or incorrect.

Quote:

Originally Posted by aijazbaig1

What if I pass the said free function such that destroy now points to this free function. will that work?

Yes. Whatever pointer value that you got from malloc() can be passed to free(). Instead of using a special function you can simply declare a pointer to a function with the same prototype as the standard library function and set its value to the address of the standard library function.

An illustration in a stand-alone program:

CPP / C++ / C Code:

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

int main()
{
  /* same prototype as the standard library function malloc()
   * myMalloc is a pointer to a function.
   * The function's return type is pointer to void
   * The function has a single argument, whose type
   * is size_t (probably unsigned int)
   */
  void *(*myMalloc)(size_t size);

  /* same prototype as the standard library function free()
   * myFree is a pointer to a function.
   * The function's return type is void.
   * The function has a single argument, whose
   * type is a pointer to void
   */
  void (*myFree)(void *ptr);

  int *iPoint;

  /* Set myMalloc and myFree to the addresses
   * of the standard library functions
   */
  myMalloc = &malloc; /* in C you don't really need the & */
  myFree   = &free;

  iPoint = myMalloc(100 * sizeof(int));
  /*
   * do whatever you want in the memory block iPoint[0]..iPoint[99],
   * but don't change the value of iPoint
   */
  myFree(iPoint);

  return 0;
}

I got the prototypes from <stdlib.h>

Regards,

Dave

davekw7x · #5 17-Jul-2007, 17:19

Quote:

Originally Posted by aijazbaig1

will that work?

Quote:

Originally Posted by davekw7x

Yes.

Upon rereading the question, I think that I gave the right answer to a question that you didn't ask. It just wasn't the answer to the question about "destroy" for the entire list, which was what you were asking about. Sorry.

If you are freeing a single item, then you can make a pointer whose address is that of the standard library function free(), as I showed in my example.

For a function to free every element in list, assuming that each of the elements was dynamically allocated by malloc(), then you need a loop that traverses the list and calls free() for each element. The List function pointer "destroy" is set to the address of this function.

If you just called the standard library function free() with the value of the "head" pointer, it would only deallocate storage for the first element.

CPP / C++ / C Code:

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

typedef struct Listelmt_ {
    void *data;
    struct Listelmt_ *nest;
} Listelmt;

typedef struct List_ {
    int size;
    int (*match) (const void *key1, const void *key2);
    void (*destroy) (void *data);

    Listelmt *head;
    Listelmt *tail;
} List;

int main()
{
    void deallocateList(void *);
    int listcmp(const void *key1,const void *key2);

    /* initialize the list: empty.
     * set "match" and "destroy" to point to our functions
     * to compare key values and to deallocate everything
     */
    List myList = {0,              /* Initially: size = 0 */
                   listcmp,        /* "match" function    */
                   deallocateList, /* "destroy function   */
                   NULL,           /* "head" pointer      */
                   NULL};          /* "tail" pointer      */
    /* put stuff in the list 
     * New elements are obtained by malloc(), and Listelmt->nest
     * is set to value returned by malloc each time (or some
     * such thing).
     */

    return 0;
}


void deallocateList(void *ptr)
{
    Listelmt *temp;
    Listelmt *head = ptr;
    while (head) {
        temp = head->nest;
        free(head);
        head = temp;
    }
}

int listcmp(const void *key1,const void *key2)
{
    int retval;
    /* do whatever you have to do to compare key values */
    return retval;
}

Obviously, to be useful, there has to be at least one other function: to allocate storage and set values for "nest" pointers. Insertion at beginning or end of list will also change list "head" and/or "tail" pointers.

Regards,

Dave

aijazbaig1 · #6 18-Jul-2007, 05:25

Hello Everybody.
thanks for taking a look at my questions and putting the time and the effort to answer them. A special thanks to dave for having such a great sense of pedagogy!

Referring to the first reply by dave, can I now save with certainty that "whenever i have a function pointer as one of the arguments in a given function, I can pass a function which confirms to the prototype specified by that function pointer to that pointer and all will be good" ?.

Quote:

myMalloc = &malloc; /* in C you don't really need the & */

I do not need to precede the function with the '&' sign as you said it is the same in C. If I do include the sign, it makes no difference right?

Referring to your second reply,I suppose that the function deallocatelist does the job of removing all the elements in the list by checking if the head is a NULL. So during the initialization phase of the list, you have just made the function pointers match and destroy to point to listcmp and deallocatelist respectively.

But in the process of initialization does making those pointers point to these functions result in these functions being executed? Because if it does then we haven't passed any arguments to those functions. Does that mean that passing no arguments to those functions result in them assuming that they (the arguments) are NULL pointers?

I just made a very simple addition to the listcmp function whch is here:

CPP / C++ / C Code:

int listcmp(const void *key1,const void *key2)
{
    int retval;
    /* do whatever you have to do to compare key values */
    if (*key1 == *key2) retval = 1;
    else retval = 0;
    return retval;
}

the rest of the program remaining the same. However when i tried to compile the program above using a simple makefile shown below, as expected i encountered some errors which are shown further below:

makefile:

CPP / C++ / C Code:

CC=gcc
CFLAGS=-Wall
list_init: list_init.o

clean:
	rm -f *.o list_init

Code:

bash-3.00# make
gcc -Wall   -c -o list_init.o list_init.c
list_init.c: In function `main':
list_init.c:27: warning: unused variable `myList'
list_init.c: In function `listcmp':
list_init.c:57: warning: dereferencing `void *' pointer
list_init.c:57: warning: dereferencing `void *' pointer
list_init.c:57: error: void value not ignored as it ought to be
list_init.c:57: error: void value not ignored as it ought to be
make: ***[list_init.o] Error 1
bash-3.00# emacs list_init.c &
[3] 908
bash-3.00#

If at all, if anything may depend on my platform or the gcc version here is the output of the gcc -v command:

Code:

Reading specs from /usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/specs
Configured with:
 ../configure --with-as=/usr/ccs/bin/as --with-ld=/usr/ccs/bin/ld --enable-shared --enable-languages=c,c++,f77
Thread model: posix
gcc version 3.4.6

So this had made me think that one has to pass some arguments to the listcmp function inorder for it to work or else it wont compile or so it seems.

I would read further in that book and perhaps im missing something here. Your comments are always welcome.
Look to hear from you guys,

davekw7x · #7 18-Jul-2007, 10:14

Quote:

Originally Posted by aijazbaig1

I do not need to precede the function with the '&' sign as you said it is the same in C. If I do include the sign, it makes no difference right?

The reason that I said that is that, in C, the name of the function by itself (no parentheses) is taken to be a pointer whose value is the address in memory where that function is loaded. I put the '&' there because you may see usage like that, where the '&' is just for emphasis.
Try it:

CPP / C++ / C Code:

#include <stdio.h>
#include <stdlib.h>
int main()
{
    void *(*myMalloc)(size_t size);
    myMalloc = malloc;
    printf("After setting equal to  malloc, myMalloc = %p\n", myMalloc);
    myMalloc = &malloc;
    printf("After setting equal to &malloc, myMalloc = %p\n", myMalloc);
    return 0;
}

Quote:

Originally Posted by aijazbaig1

But in the process of initialization does making those pointers point to these functions result in these functions being executed?

No.
Use of an initializer list generates code that assigns values of the members of the struct to the values in the initializer list in the declaration statement. The result would have been the same if I had written something like the following, where there is no initializer list. The struct members are assigned values by separate assignment statements. It's a matter of style. Either way is OK by me.

CPP / C++ / C Code:

    List myList;
    myList.size    = 0;              /* Initially: size = 0 */
    myList.match   = listcmp;        /* "match" function    */
    myList.destroy = deallocateList; /* "destroy function   */
    myList.head    = NULL;           /* "head" pointer      */
    myList.tail    = NULL;           /* "tail" pointer      */

As I mentioned above, when the compiler sees a function name by itself (no parentheses), it is treated as a pointer whose value is the address where the function is loaded. Assigning a value to a pointer does not invoke the function.

Quote:

Originally Posted by aijazbaig1

Because if it does then we haven't passed any arguments to those functions. Does that mean that passing no arguments to those functions result in them assuming that they (the arguments) are NULL pointers?

Not even close. When you invoke a function, you write the parentheses, and inside the parentheses there is a list of arguments corresponding to the parameters in the function definition. There is no such thing as "default" arguments in C.

Quote:

Originally Posted by aijazbaig1

makefile:

Code:

.
.
.
CFLAGS=-Wall
.
.
.

I would suggest CFLAGS = -Wall -W -pedantic to get maximum information from the compiler.

Quote:

Originally Posted by aijazbaig1

Code:

list_init.c:27: warning: unused variable `myList'
list_init.c: In function `listcmp':
list_init.c:57: warning: dereferencing `void *' pointer
list_init.c:57: warning: dereferencing `void *' pointer
list_init.c:57: error: void value not ignored as it ought to be
list_init.c:57: error: void value not ignored as it ought to be
make: ***[list_init.o] Error 1

The first is a warning, and is obviously not a problem.
For the next two: Why can't you dereference a 'void *' pointer? Well, in order to dereference a pointer, the code must know what kind of variable to look at. So the code must use types appropriate to the values that it is comparing. Now, the data pointer in the definition of the struct is a pointer to void. (I guess that was the original author's attempt to make the list stuff as general as possible.) In order to get some data values into the list, you would write a function that would allocate storage and get data values of a particular type into memory. Let's say that for the particular list we are dealing with that the actual data values are ints. Then one way to make the listcmp function work would be:

CPP / C++ / C Code:

int listcmp(const void *key1,const void *key2)
{
    int retval;
    int *k1 = key1; /* In C, the pointer is automatically cast by assignment */
    int *k2 = key2; /* In C, the pointer is automatically cast by assignment */

    /* do whatever you have to do to compare key values */
    if (*k1 == *k2) {
        retval = 1;
    }
    else {
        retval = 0;
    }
    return retval;
}

Note that in C++, the pointer to void is not automatically cast by assignment, so you might write something like

CPP / C++ / C Code:

    int *k1 = (int *)key1; /* In C++, the pointer is not automatically cast by assignment */
    int *k2 = (int *)key2; /* In C++, the pointer is not automatically cast by assignment */

You don't have to make separate variables to do the job and you could write something like:

CPP / C++ / C Code:

int listcmp(const void *key1,const void *key2)
{
    int retval;

    if (*(int *)key1 == *(int *)key2) {
        retval = 1;
    }
    else {
        retval = 0;
    }
    return retval;
}

See? Each cast (int *) tells the code to cast the void pointer to something that can be dereferenced, and the '*' in front tells the code to dereference the pointer to int, thereby obtaining an int to use in the comparison.

Anyhow, doing it "right" gets rid of all of the error messages.

Quote:

Originally Posted by aijazbaig1

So this had made me think that one has to pass some arguments to the listcmp function inorder for it to work or else it wont compile or so it seems.

If you have more than one kind of list in your program, using the same generic struct (with data defined by void pointers), then your individual functions to add data elements to the list and to compare them must have some way of knowing what type of variables to use, and one way (probably the "best" way in C), would to do exactly what you said.

If a given program has only one type of list, then the individual functions to add elements to the list and to compare elements could be specialized for whatever data type the list uses. (Like the listcmp function that I showed above.)

Since I don't have your book, I have no way of knowing where the author is going with this (or how you got to this point in the exposition), but I was using the prototypes that you started with. Since the pointer to the struct "match" function has no argument that could be used to indicate data type, that is what I demonstrated.

Regards,

Dave

aijazbaig1 · #8 19-Jul-2007, 17:45

hello there.
found some more time to monkey around with the various great suggestions. I tried writing a simple header file which I would then include with the actual C file.

This header file contains the declarations of the various functions that i wish to use in the C file and it also contains the function-like macros.

First these macros are flagging errors when i try to compile the whole program. Actually there are a lot of other errors but id like to point out the ones generated by the header file as they are seemingly less in number and hopefully easy to fix.

So heres my header file called "list.h" :

CPP / C++ / C Code:

#ifndef LIST_H
#define LIST_H

#include <stdlib.h>

typedef struct Listelmt_ {
  void *data;
  struct Listelmt_ *next;
}
Listelmt;

typedef struct List_ {
  int size;
  int (*match)(const void *key1, const void *key2);
  void (*destroy)(void *data);

  Listelmt *head;
  Listelmt *tail;
}
List;

void deallocatelist(void *ptr);
void list_init(List *list, void (*destroy)(void *data));
void list_destroy(List *list);
int list_ins_nxt(List *list, Listelmt *elmt, const void *data);
int list_rem_nxt(List *list, Listelmt *elmt, void **data);

#define list_sze(const List *list) (list->size)
#define list_head(const List *list) (list->head)
#define list_tail(const List *list) (list->tail)
#define list_is_head(const List *list,const Listelmt *elmt) (list->head == elmt ? 1:0)
#define list_is_tail(const List *list,const Listelmt *elmt) (list->tail == elmt ? 1:0)
#define list_data(const Listelmt *elmt) (elmt->data)
#define list_next(const Listelmt *elmt) (elmt->next)

#endif

And then there is the C file called list.c which contains the definition of all these functions. Heres that file(viz. list.c):

CPP / C++ / C Code:

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

#include "list.h"

void deallocatelist(void *ptr)
{
    Listelmt *tmp;
    Listelmt *head = ptr;

    while (head) {
        temp = head -> next;
        free(head);
        head = temp;
    }
}

void list_init(List *list, void (*destroy)(void *data))
{
  list -> size = 0;
  list -> destroy = destroy;
  list -> head = NULL;
  list -> tail = NULL;
}

void list_destroy(List *list);
{
    if list -> size = 0 
	  return -1;
    else if list -> destroy != NULL
                 deallocatelist(list -> head);

    memset(list, 0, sizeof(list));
    return;
}

int list_ins_nxt(List *list, Listelmt *elmt, const void *data)
{
    Listelmt *new_element;
    new_element = (Listelmt *)malloc(sizeof(Listelmt));

    if new_element == NULL
                   return -1;
    else
        {
            new_element -> data = data;
            if list -> size = 0 //the list is empty
                {
                list_init(list,NULL);
                list -> head = new_element;
                list -> tail = new_element;
                new_element -> next = NULL;
                }
            else
                {
                    if elmt == NULL //insert new element at the start of the list
                        {
                            new_element -> next = list -> head;
                            list -> head = new_element;
                        }
                    else if elmt -> next == NULL //insert new element at the end of the list
                        {
                            elmt -> next = new_element;
                            new_element -> next = NULL;
                            list -> tail = new_element;
                        }
                    else 
                        {
                            new_element -> next = elmt -> next;
                            elmt -> next = new_element;
                        }
                    (list -> size)++;

                }
        }
    return 0;
}

int list_rem_nxt(List *list, Listelmt *elmt, void **data)
{
    Listelmt *old_element;

    if list -> size == 0 return -1;//list is empty..nothin 2 remove
    else if elmt == NULL //remove the head of the list
        {
            old_element = list -> head;
            data =  &(old_element -> data);
            list -> head = old_element -> next;
        }
    else if elmt -> next == NULL //remove the tail of the list
        {
            old_element = list -> tail;
            data = &(old_element -> data);
            list -> tail = elmt;
        }
    else 
        {
            old_element = elmt -> next;
            data = &(old_element -> data);
            elmt -> next = old_element -> next;
        }
    free(old_element);
    (list -> size)--;
    return 0;
}

Now this C file could be a hot bed of errors and it sure is. However it would be easier for me to first fix the errors in the header file. So comments on that file are welcome and they could even be on some other issues besides the syntactic accuracy of the code, i mean stuff like my coding style or something similar that i would be better off with.

So here are the errors the compiler flagged in the list.h file (as suggested by dave, i've turned on the Wall, W and the pedantic flags in the makefile) :

Code:

bash-3.00# make
gcc -Wall -W -pedantic   -c -o list.o list.c
In file included from list.c:4:
list.h:28:24: macro parameters must be comma-separated
list.h:29:25: macro parameters must be comma-separated
list.h:30:25: macro parameters must be comma-separated
list.h:31:28: macro parameters must be comma-separated
list.h:32:28: macro parameters must be comma-separated
list.h:33:25: macro parameters must be comma-separated
list.h:34:25: macro parameters must be comma-separated

So what is the compiler complaining about here. I would want those macros to act like functions but since they are too tiny to be functions in their own sense, i thought of making them macros.
Additionally what does the compiler say when it refers to 28:24..does it mean line 24 to 28? now thats kinda confusing too!

Anyways..id love to hear from you guys!!

davekw7x · #9 19-Jul-2007, 19:01

Quote:

Originally Posted by aijazbaig1

In file included from list.c:4:
list.h:28:24: macro parameters must be comma-separated
list.h:29:25: macro parameters must be comma-separated
list.h:30:25: macro parameters must be comma-separated
list.h:31:28: macro parameters must be comma-separated
list.h:32:28: macro parameters must be comma-separated
list.h:33:25: macro parameters must be comma-separated
list.h:34:25: macro parameters must be comma-separated
[/code]
So what is the compiler complaining about here.

It is trying (really hard) to tell you that macro parameters must be comma-separated.
Macros are not functions.

Macros are not C, but they are C-aware. They make text substitutions for C identifiers defined in the macro.

Macros are a way of redefining input text to make stuff that's not C look enough like C to be acceptable to a compiler.

Your macros only have one parameter. The data type information that you would use in a function definition have no place in the text-substitution macro. Period.

My advice: don't use macros unless you really (really) need them.
If you decide that you really (really) need a macro that accepts your input as though it were a function, then you could try something like:

CPP / C++ / C Code:

#define list_sze(list) (list->size)

Now, anywhere you have something that looks like a function call to list_sze, it will just evaluate the expression as list->size.

The problem: By making it a macro instead of a function the compiler is completely incapable of doing any type checking. If you use something as an argument to the macro that is not a pointer to some kind of struct that has an element names "size", you might get some very confusing error message. Or, worse than that, depending on how the macro is actually defined, the compiler might accept it but do something completely, utterly different than what you had in mind and give you no indication that something is wrong, but at run time might cause some bad behavior, or might give a wrong answer without any clue that it went wild.

I hate to repeat myself, but I really, really recommend that you not use macros unless you really, really need them

In this case, why not just write xxx->size whereever you want to find the value of the size element of the struct to which xxx is pointing? I think it would be silly (but not "wrong") to make a function that does something as fundamental as dereference a pointer to struct to get a member. I think it is bordering on pathological to make a macro to do so.

But that's just my opinion. Do whatever the heck you want to in your programs. However, if you ever find yourself in a work environment where other people look at your code (code reviews), and maybe have to maintain it, you should consider getting one of those fireman protective suits and wearing it all of the time, because you will be flamed. Seriously.

Quote:

Originally Posted by aijazbaig1

Additionally what does the compiler say when it refers to 28:24..does it mean line 24 to 28? now thats kinda confusing too!

Sometimes compiler error and warning messages are very hard to understand. Sometimes an error on one line triggers a strange-looking message (looks strange to us mere humans) several lines later in the program (or, in the case of errors in header files, the error might be flagged in the file that includes the header, and not give a clue that the error is actually in a different file).

In this case, the errors are quite explicit:
The first one is telling you that it doesn't like what it sees at character position 24 on line number 28 of the file list.h. Etc.

Regards,

Dave

aijazbaig1 · #10 20-Jul-2007, 04:24

Hi there.
thanks for the helpful comments..before proceeding any further...do u know if it would be possible for me to archive some of the threads that I have started for future reference.

Because it contains some very valuable information for me and id hate to ask those questions again and again. so if u know of a way to keep them in the safe somehow..please do let me know..

ok..here we go!

so i removed all those macros as u suggested and i instead plan to use them directly whenever i need any of that information. So heres the C file again (with minor modifications of course) and the errors i get when i try to compile the C file:

CPP / C++ / C Code:

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

#include "list.h"

void deallocatelist(void *ptr)
{
    Listelmt *temp;
    Listelmt *head = ptr;

    while (head) {
        temp = head -> next;
        free(head);
        head = temp;
    }
}

void list_init(List *list, void (*destroy)(void *data))
{
  list -> size = 0;
  list -> destroy = destroy;
  list -> head = NULL;
  list -> tail = NULL;
}

void list_destroy(List *list)
{
    if (list -> size == 0) 
	  return;
    else if (list -> destroy != NULL)
                 deallocatelist(list -> head);

    memset(list, 0, sizeof(list));
    return;
}

int list_ins_nxt(List *list, Listelmt *elmt, const void *data)
{
    Listelmt *new_element;
    new_element = (Listelmt *)malloc(sizeof(Listelmt));

    if (new_element == NULL)
                   return -1;
    else
        {
            new_element->data = data;
            if (list -> size == 0 && elmt == NULL) /*the list is empty*/
                {
                list_init(list,NULL);
                list -> head = new_element;
                list -> tail = new_element;
                new_element -> next = NULL;
                }
            else
                {
                    if (elmt == NULL) /*insert new element at the start of the list*/
                        {
                            new_element -> next = list -> head;
                            list -> head = new_element;
                        }
                    else if (elmt -> next == NULL) //insert new element at the end of the list
                        {
                            elmt -> next = new_element;
                            new_element -> next = NULL;
                            list -> tail = new_element;
                        }
                    else 
                        {
                            new_element -> next = elmt -> next;
                            elmt -> next = new_element;
                        }
                    (list -> size)++;

                }
        }
    return 0;
}

int list_rem_nxt(List *list, Listelmt *elmt, void **data)
{
    Listelmt *old_element;

    if (list -> size == 0) return -1;//list is empty..nothin 2 remove
    else if (elmt == NULL) //remove the head of the list
        {
            old_element = list -> head;
            data =  &(old_element -> data);
            list -> head = old_element -> next;
        }
    else if elmt -> next == NULL /*remove the tail of the list*/
        {
            old_element = list -> tail;
            data = &(old_element -> data);
            list -> tail = elmt;
        }
    else 
        {
            old_element = elmt -> next;
            data = &(old_element -> data);
            elmt -> next = old_element -> next;
        }
    free(old_element);
    (list -> size)--;
    return 0;
}

Code:

list.c: In function `list_ins_nxt':
list.c:46: warning: assignment discards qualifiers from pointer target type
list.c:47: warning: suggest parentheses around assignment used as truth value
list.c:61:52: warning: C++ style comments are not allowed in ISO C90
list.c:61:52: warning: (this will be reported only once per input file)
list.c: In function `list_rem_nxt':
list.c:90: error: syntax error before "elmt"
list.c:91: error: syntax error before '{' token
list.c: At top level:
list.c:96: error: syntax error before "else"
list.c:99: warning: type defaults to `int' in declaration of `data'
list.c:99: error: `old_element' undeclared here (not in a function)
list.c:99: error: ISO C forbids data definition with no type or storage class
list.c:100: error: syntax error before '->' token
list.c:102: warning: type defaults to `int' in declaration of `free'
list.c:102: warning: parameter names (without types) in function declaration
list.c:102: error: conflicting types for 'free'
/usr/include/iso/stdlib_iso.h:125: error: previous declaration of 'free' was here
list.c:102: error: conflicting types for 'free'
/usr/include/iso/stdlib_iso.h:125: error: previous declaration of 'free' was here
list.c:102: error: ISO C forbids data definition with no type or storage class
list.c:103: error: syntax error before '->' token
make: ***[list.o] Error 1
bash-3.00# emacs list.h &
[2] 850

some very intriguing thing is about the conditions for the if statements. Since most of my if statements only had 1 single value to evaluate i did not put parenthesis around them. However, it flagged it as "syntax errror before so and so" where 'so and so' refers to the first variable in the conditional expression. As an example, i left the second to last 'else-if' statement intact without adding any parenthesis around the conditional expression and it again flags an error there as

Code:

list.c : 90 : syntax error before "elmt"

Then again there are some strange errors like the one on line 99 saying that old_element is not declared which i did and it is local to that function. is it flagging that error because im assigning the pointer to some externally passed variable and once the function exits this automatic variable becomes meaningless?

also what can be made of errors like the one on line 96? which is the very last else if the program.

Hope to hear from you guys!

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Airport Log program using 3D linked List : problem reading from file	batrsau	C Programming Language	11	29-Feb-2008 08:44
[Include] Doubly-linked List	dsmith	C Programming Language	6	14-Apr-2006 14:12
linked list error message	Krandygrl00	C++ Forum	4	22-Jun-2005 15:13
search linked list	itsmecathys	C++ Forum	20	18-Apr-2005 02:34

Help analyzing a linked list program

Re: help analyzing a linked list program

Re: help analyzing a linked list program

Re: help analyzing a linked list program

Re: help analyzing a linked list program

Re: help analyzing a linked list program

Re: help analyzing a linked list program

Re: Help analyzing a linked list program

Re: Help analyzing a linked list program

Re: Help analyzing a linked list program