Weird link list problem

Discussion in 'C Programming' started by sieg1974@yahoo.com, Nov 3, 2006.

  1. Guest

    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;
    }
    , Nov 3, 2006
    #1
    1. Advertising

  2. Guest

    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;
    }
    }

    wrote:
    > 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;
    > }
    , Nov 3, 2006
    #2
    1. Advertising

  3. Eric Sosman Guest

    wrote On 11/03/06 15:52,:
    > 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.

    --
    Eric Sosman, Nov 3, 2006
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Kevin Spencer

    Re: Link Link Link DANGER WILL ROBINSON!!!

    Kevin Spencer, May 17, 2005, in forum: ASP .Net
    Replies:
    0
    Views:
    792
    Kevin Spencer
    May 17, 2005
  2. dorayme
    Replies:
    1
    Views:
    602
    richard
    Jan 21, 2011
  3. richard
    Replies:
    0
    Views:
    570
    richard
    Jan 21, 2011
  4. richard
    Replies:
    0
    Views:
    604
    richard
    Jan 21, 2011
  5. will
    Replies:
    6
    Views:
    390
    Phrogz
    Dec 27, 2006
Loading...

Share This Page