Weird link list problem

[sieg1974]

Hi,

I have a linked list with 705 nodes, and the functions getContact and
listContact to deal with it. listContact works properly, and prints all
some debug information about each node. On the other hand, getContact
breaks when it reaches the 580th node although it's almost identical to
listContact .
Does anyone have any idea about what is wrong?

Thanks,

Andre

#define MAX_STR 127

typedef struct
{
char ContactName[MAX_STR + 1];

}CONTACT_ENTRY;

struct ContactNode
{
struct ContactNode * Next;
struct ContactNode * Previous;
CONTACT_ENTRY Contact;
};

void listContact( struct ContactNode * ContactListHead, unsigned int
counter )
{
FILE * pFile = fopen("./test.txt", "a");
fprintf( pFile, "%04d %07X %07X %07X\n",
counter,
ContactListHead->Previous,
ContactListHead,
ContactListHead->Next);
fflush(pFile);
fclose(pFile);

if( ContactListHead->Next != 0 )
{
listContact( ContactListHead->Next, ++counter );
}
}

CONTACT_ENTRY getContact( struct ContactNode * ContactListHead,
unsigned int counter )
{
FILE * pFile = fopen("./test.txt", "a");
fprintf( pFile, "%04d %07X %07X %07X\n",
counter,
ContactListHead->Previous,
ContactListHead,
ContactListHead->Next);
fflush(pFile);
fclose(pFile);

if( ContactListHead->Next != 0 )
{
getContact( ContactListHead->Next, ++counter );
}

return ContactListHead->Contact;
}

 

[sieg1974]

Hi,

Forgot to post my addContact function just in case.

Thanks,

Andre

struct ContactNode * addContact( struct ContactNode *
ContactListPrevious,
struct ContactNode * ContactListHead,
CONTACT_ENTRY * Contact )
{
if( !ContactListHead )
{
struct ContactNode * tempContactNode =
( struct ContactNode * ) malloc( sizeof( struct ContactNode )
);

memcpy( &tempContactNode->Contact, Contact, sizeof( CONTACT_ENTRY
) );

tempContactNode->Previous = ContactListPrevious;
tempContactNode->Next = 0;

return tempContactNode;
}
else
{
ContactListHead->Next = addContact( ContactListHead,
ContactListHead->Next, Contact );

return ContactListHead;
}
}

 

[Eric Sosman]

Hi,

I have a linked list with 705 nodes, and the functions getContact and
listContact to deal with it. listContact works properly, and prints all
some debug information about each node. On the other hand, getContact
breaks when it reaches the 580th node although it's almost identical to
listContact .
Does anyone have any idea about what is wrong?
[code snipped; see up-thread]

You didn't describe the manner in which it "breaks,"
but I'll make a guess: Are you getting some kind of stack
overflow?

A function in C needs to keep track of the location it
will return to, and the mechanism to do this is often
implemented as a stack. Also, a function that returns a
value (especially an aggregate value) may use additional
stack space in the caller to hold the returned value.

Now, you're using recursion to traverse your linked
list, and this means you need as many "stack frames" as
there are list nodes (plus or minus a few, depending on
how you detect end-of-list, and plus whatever is used by
the functions "above" the traversal and the functions
called during the traversal). Your listContact() function
returns nothing, and thus probably uses very little stack
space per call. However, getContact() returns a struct of
128 bytes or more, so each call needs to set aside some
space where that struct can be returned. Therefore, you
can expect getContact() to use at least 90KB more stack
space than listContact(), and if you're close to the edge
already this may well push you over it.

(All these calculations should be treated with some
caution. Different C implementations on different machines
do things differently out of necessity, and they'll have
different mechanisms for returning structs, using different
amounts of stack space. There might not even be a "stack"
at all! Still, the mechanisms I'm describing are fairly
typical, and the size penalty on your machine isn't likely
to differ from my calculations by more than a few multiples
of Finagle's Variable Constant.)

The problem (or *a* problem) with your approach is that
you're using recursion for a task that is more naturally
iterative. Think about it for a moment: in an iterative
solution, you'll just sit inside one function level instead
of descending and descending and descending. You won't need
to pass that `counter' as an argument in every call; it can
just be a local variable in the function. And you won't
need to keep opening, writing, closing, reopening, rewriting,
and reclosing that output file time and time and time again;
you'll just open it once near the beginning of the function,
loop through the list writing out each node, and close the
file once when you've reached the end. Lots less overhead.

By the way, "%d" is not the right way to print an unsigned
value: use "%u". And "%X" is not the right way to print a
pointer: use "%p" and apply a `(void*)' cast to the value.