3

I have a generic linked-list that holds data of type void* I am trying to populate my list with type struct employee, eventually I would like to destruct the object struct employee as well.

Consider this generic linked-list header file (i have tested it with type char*):

struct accListNode //the nodes of a linked-list for any data type { void *data; //generic pointer to any data type struct accListNode *next; //the next node in the list }; struct accList //a linked-list consisting of accListNodes { struct accListNode *head; struct accListNode *tail; int size; }; void accList_allocate(struct accList *theList); //allocate the accList and set to NULL void appendToEnd(void *data, struct accList *theList); //append data to the end of the accList void removeData(void *data, struct accList *theList); //removes data from accList --------------------------------------------------------------------------------------

Consider the employee structure

struct employee { char name[20]; float wageRate; }

Now consider this sample testcase that will be called from main():

 void test2() { struct accList secondList; struct employee *emp = Malloc(sizeof(struct employee)); emp->name = "Dan"; emp->wageRate =.5; struct employee *emp2 = Malloc(sizeof(struct employee)); emp2->name = "Stan"; emp2->wageRate = .3; accList_allocate(&secondList); appendToEnd(emp, &secondList); appendToEnd(emp2, &secondList); printf("Employee: %s\n", ((struct employee*)secondList.head->data)->name); //cast to type struct employee printf("Employee2: %s\n", ((struct employee*)secondList.tail->data)->name); }

Why does the answer that I posted below solve my problem? I believe it has something to do with pointers and memory allocation. The function Malloc() that i use is a custom malloc that checks for NULL being returned.

Here is a link to my entire generic linked list implementation: https://codereview.stackexchange.com/questions/13007/c-linked-list-implementation

Improve this question
9
  • 6
    If you run this in the debugger, you will learn which line causes the error. Commented Jun 23, 2012 at 22:33
  • @CodeKingPlusPlus: emp->name = "Dan";???? Shouldn't it be strcpy(emp->name, "Dan")? Commented Jun 23, 2012 at 22:35
  • 1
    @Oli Charlesworth: Ted? A guaranteed "Exercise in Poor Taste" ;) Commented Jun 23, 2012 at 22:38
  • @Oli Charlesworth good suggestion with the strcpy... I will never be entirely used to C... Commented Jun 24, 2012 at 0:57
  • 3
    "Shouldn't it be strcpy(emp->name, "Dan")? " -- only if you're intent on writing into unallocated memory. Commented Jun 24, 2012 at 9:45

4 Answers 4

Reset to default
6
+100

The problem is this accList_allocate() and your use of it.

struct accList secondList; accList_allocate(&secondList);

In the original test2() secondList is memory on the stack. &secondList is a pointer to that memory. When you call accList_allocate() a copy of the pointer is passed in pointing at the stack memory. Malloc() then returns a chunk of memory and assigns it to the copy of the pointer, not the original secondList.

Coming back out, secondList is still pointing at uninitialised memory on the stack so the call to appendToEnd() fails.

The same happens with the answer except secondList just happens to be free of junk. Possibly by chance, possibly by design of the compiler. Either way it is not something you should rely on.

Either:

struct accList *secondList = NULL; accList_allocate(&secondList);

And change accList_allocate()

accList_allocate(struct accList **theList) { *theList = Malloc(sizeof(struct accList)); (*theList)->head = NULL; (*theList)->tail = NULL; (*theList)->size = 0; }

OR

struct accList secondList; accList_initialise(secondList);

With accList_allocate() changed to accList_initialise() because it does not allocate

accList_initialise(struct accList *theList) { theList->head = NULL; theList->tail = NULL; theList->size = 0; }
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

I think that your problem is this:

  1. You've allocated secondList on the stack in your original test2 function.
  2. The stack memory is probably dirty, so secondList requires initialization
  3. Your accList_allocate function takes a pointer to the list, but then overwrites it with the Malloc call. This means that the pointer you passed in is never initialized.
  4. When test2 tries to run, it hits a bad pointer (because the memory isn't initialized).

The reason that it works when you allocate it in main is that your C compiler probably zeros the stack when the program starts. When main allocates a variable on the stack, that allocation is persistent (until the program ends), so secondList is actually, and accidentally, properly initialized when you allocate it in main.

Your current accList_allocate doesn't actually initialize the pointer that's been passed in, and the rest of your code will never see the pointer that it allocates with Malloc. To solve your problem, I would create a new function: accList_initialize whose only job is to initialize the list:

void accList_initialize(struct accList* theList) { // NO malloc theList->head = NULL; theList->tail = NULL; theList->size = 0; }

Use this, instead of accList_allocate in your original test2 function. If you really want to allocate the list on the heap, then you should do so (and not mix it with a struct allocated on the stack). Have accList_allocate return a pointer to the allocated structure:

struct accList* accList_allocate(void) { struct accList* theList = Malloc( sizeof(struct accList) ); accList_initialize(theList); return theList; }
Improve this answer

1 Comment

One way to verify that this is correct is to print the data structures out after allocating them on the stack, but before calling accList_allocate. Use something like printf("size=%lu head=%p tail=%p\n", secondList->size, secondList->head, secondList->tail);.
0

Two things I see wrong here based on the original code, in the above question,

What you've seen is undefined behaviour and arose from that is the bus error message as you were assigning a string literal to the variable, when in fact you should have been using the strcpy function, you've edited your original code accordinly so.. something to keep in mind in the future :)

The usage of the word Malloc is going to cause confusion, especially in peer-review, the reviewers are going to have a brain fart and say "whoa, what's this, should that not be malloc?" and very likely raise it up. (Basically, do not call custom functions that have similar sounding names as the C standard library functions)

You're not checking for the NULL, what if your souped up version of Malloc failed then emp is going to be NULL! Always check it no matter how trivial or your thinking is "Ah sher the platform has heaps of memory on it, 4GB RAM no problem, will not bother to check for NULL"

Have a look at this question posted elsewhere to explain what is a bus error.

Edit: Using linked list structures, in how the parameters in the function is called is crucial to the understanding of it. Notice the usage of &, meaning take the address of the variable that points to the linked list structure, and passing it by reference, not passing by value which is a copy of the variable. This same rule applies to usage of pointers also in general :)

You've got the parameters slightly out of place in the first code in your question, if you were using double-pointers in the parameter list then yes, using &secondList would have worked.

Improve this answer

2 Comments

I just posted what Malloc does, it just checks for NULL. Read the text underneath the bounty and relay your answer to that text...
No, this is so I can have generic linked lists and for practice. The next step will be deallocating 'object types' in the list when I free a node in the list. I was going to use a function pointer to the objects deallocate function.
0

It may depend on how your Employee structure is designed, but you should note that

strcpy(emp->name, "Dan");

and

emp->name = "Dan";

function differently. In particular, the latter is a likely source of bus errors because you generally cannot write to string literals in this way. Especially if your code has something like

name = "NONE"

or the like.

EDIT: Okay, so with the design of the employee struct, the problem is this:

You can't assign to arrays. The C Standard includes a list of modifiable lvalues and arrays are not one of them.

char name[20]; name = "JAMES" //illegal

strcpy is fine - it just goes to the memory address dereferenced by name[0] and copies "JAMES\0" into the memory there, one byte at a time.

Improve this answer

3 Comments

My answer uses strcpy. I am looking for why my answer solves my problem. I believe it has something to do with pointers and allocation. 'My answer' is posted as a literal stack overflow answer.
I'm trying to answer that question but you left the critical part (the design of the employee structure) out. Your answer also implies that the fix came from re-arranging the scope of the memory allocations ("When I place the declaration and allocation of secondList in main() and put the rest in a function it works").
Okay, the format of the structure you have makes the problem more clear.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.