Problem with sorting algorithm and double linked lists

Discussion in 'C Programming' started by FBM, Mar 11, 2006.

  1. FBM

    FBM Guest

    Hi,

    I am working on a program that simulates one of the elements of ATM.
    The simulation stores events which occurs every some milliseconds for a
    certain amount of time. Every time that an event is stored in a double
    linked list, the whole list is sorted for the next round.

    My problem appears when subjecting the program to heavy load, that is,
    when I run the simulation for more than 10,000 miliseconds (every event
    occurs in 5-millisecond intervals). Through Eclipse I could find that
    my sorting algorithm is not working properly..

    Printing some control information I see that before crashing, the speed
    of what is shown on the screen increases just before stopping and then
    showing the segmentation fault error.

    I could trace the origin of the problem to this function:

    // Sort events
    DLLIST * sortEvents(DLLIST *List) {
    EVENT *First, *Second;
    double basketElem1 = 0, basketElem2 = 0;
    DLLIST *floor = NULL, *floorP = NULL;
    EVENT *floorElem;
    int counter1 = 0, counter2 = 0;
    List = DLGetFirst(List);
    First = DLGetData(List, NULL, NULL);
    while(List != NULL) {
    basketElem1 = First->TimeInit;
    if( floor != NULL ) {
    floorP = floor;
    do {
    floorElem = DLGetData(floorP, NULL, NULL);
    basketElem2 = floorElem->TimeInit;
    if( basketElem1 < basketElem2 || basketElem1 == basketElem2) {
    DLAddBefore(&floorP, 0, First, sizeof *First);
    break;
    }
    if( DLGetNext(floorP) == NULL && basketElem1 > basketElem2 ) {
    DLAddAfter(&floorP, 0, First, sizeof *First);
    break;
    }
    floorP = DLGetNext(floorP);
    counter2++;
    } while( floorP != NULL);

    floor = DLGetFirst(floor);
    } else
    DLPrepend(&floor, 0, First, sizeof *First);

    List = DLGetNext(List);
    Second = DLGetData(List, NULL, NULL);
    First = Second;
    counter1++;
    }
    DLDestroy(&List);
    return floor;
    }

    This the implementation of linear insertion sort. I found this on "C
    Unleashed" (the algorithm, not the implementation).

    The stack dump showed me that the exact place where the program crashes
    is here:
    if( DLGetNext(floorP) == NULL && basketElem1 > basketElem2 ) {
    DLAddAfter(&floorP, 0, First, sizeof *First); **

    ** and inside this function DLAddAfter, the instruction:
    p = DLCreate(Tag, Object, Size);

    which is precisely where you obtain new memory..

    The program uses lists from "C unleashed" too. Below is the relevant
    code:

    Thanks a lot for your help,

    Fernando

    +---------------------------------------------------------------+
    typedef struct EVENT
    {
    int codeEvent;
    char descEvent[80];
    double TimeInit;
    double TimeExpire;
    } EVENT;

    +-----------------------------------------+
    DLLIST *DLCreate(int Tag, void *Object, size_t Size)
    {
    DLLIST *NewItem;

    NewItem = malloc(sizeof *NewItem);
    if(NewItem != NULL)
    {
    NewItem->Prev = NewItem->Next = NULL;
    NewItem->Tag = Tag;
    NewItem->Size = Size;
    NewItem->Object = malloc(Size);
    if(NULL != NewItem->Object)
    {
    memcpy(NewItem->Object, Object, Size);
    }
    else
    {
    free(NewItem);
    NewItem = NULL;
    }
    }

    return NewItem;
    }

    void DLDestroy(DLLIST **List)
    {
    DLLIST *Marker;
    DLLIST *Prev;
    DLLIST *Next;

    if(*List != NULL)
    {
    /* First, destroy all previous items */
    Prev = (*List)->Prev;
    while(Prev != NULL)
    {
    Marker = Prev->Prev;
    DLDelete(Prev);
    Prev = Marker;
    }

    Next = *List;
    do
    {
    Marker = Next->Next;
    DLDelete(Next);
    Next = Marker;
    } while(Next != NULL);
    *List = NULL;
    }
    }

    DLLIST *DLGetNext(DLLIST *List)
    {
    if(List != NULL)
    {
    List = List->Next;
    }

    return List;
    }

    DLLIST *DLGetFirst(DLLIST *List)
    {
    if(List != NULL)
    {
    while(List->Prev != NULL)
    {
    List = List->Prev;
    }
    }
    return List;
    }

    int DLPrepend(DLLIST **Item,
    int Tag,
    void *Object,
    size_t Size)
    {
    int Result = DL_SUCCESS;

    DLLIST *p;
    DLLIST *Start;

    assert(Item != NULL);

    p = DLCreate(Tag, Object, Size);

    if(p != NULL)
    {
    if(NULL == *Item)
    {
    *Item = p;
    }
    else
    {
    Start = DLGetFirst(*Item);
    DLInsertBefore(Start, p);
    }
    }
    else
    {
    Result = DL_NO_MEM;
    }

    return Result;
    }

    int DLAppend(DLLIST **Item,
    int Tag,
    void *Object,
    size_t Size)
    {
    int Result = DL_SUCCESS;

    DLLIST *p;
    DLLIST *End;

    assert(Item != NULL);

    p = DLCreate(Tag, Object, Size);

    if(p != NULL)
    {
    if(NULL == *Item)
    {
    *Item = p;
    }
    else
    {
    End = DLGetLast(*Item);
    DLInsertAfter(End, p);
    }
    }
    else
    {
    Result = DL_NO_MEM;
    }

    return Result;
    }


    /* Add new item immediately after current item */
    int DLAddAfter(DLLIST **Item,
    int Tag,
    void *Object,
    size_t Size)
    {
    int Result = DL_SUCCESS;
    DLLIST *p;

    assert(Item != NULL);

    p = DLCreate(Tag, Object, Size);

    if(p != NULL)
    {
    if(NULL == *Item)
    {
    *Item = p;
    }
    else
    {
    DLInsertAfter(*Item, p);
    }
    }
    else
    {
    Result = DL_NO_MEM;
    }

    return Result;
    }

    /* Add new item immediately before current item */
    int DLAddBefore(DLLIST **Item,
    int Tag,
    void *Object,
    size_t Size)
    {
    int Result = DL_SUCCESS;
    DLLIST *p;

    assert(Item != NULL);

    p = DLCreate(Tag, Object, Size);

    if(p != NULL)
    {
    if(NULL == *Item)
    {
    *Item = p;
    }
    else
    {
    DLInsertBefore(*Item, p);
    }
    }
    else
    {
    Result = DL_NO_MEM;
    }

    return Result;
    }

    void *DLGetData(DLLIST *Item,
    int *Tag,
    size_t *Size)
    {
    void *p = NULL;

    if(Item != NULL)
    {
    if(Tag != NULL)
    {
    *Tag = Item->Tag;
    }
    if(Size != NULL)
    {
    *Size = Item->Size;
    }
    p = Item->Object;
    }

    return p;
    }


    +--------------------------------------+
    FBM, Mar 11, 2006
    #1
    1. Advertising

  2. "FBM"posted the following on 2006-03-11:

    > Hi,
    >
    > I am working on a program that simulates one of the elements of ATM.
    > The simulation stores events which occurs every some milliseconds for a
    > certain amount of time. Every time that an event is stored in a double
    > linked list, the whole list is sorted for the next round.


    More programming than a C language issue, but maybe a certain approach
    might help?

    >
    > My problem appears when subjecting the program to heavy load, that is,
    > when I run the simulation for more than 10,000 miliseconds (every event
    > occurs in 5-millisecond intervals). Through Eclipse I could find that
    > my sorting algorithm is not working properly..
    >
    > Printing some control information I see that before crashing, the speed
    > of what is shown on the screen increases just before stopping and then
    > showing the segmentation fault error.


    I dont really understand this. A crash could well have caused a
    log/printf buffer to be flushed - thus appearing as "faster
    printing". But I'm not sure if this is what you mean.

    >
    > I could trace the origin of the problem to this function:
    >

    *snip*

    Is it constantly reproducible? Origin of the problem or the FINALE of
    the problem?

    I'll suggest one problem finding technique : theres too much code
    there for me to take in in one go and suggest whats causing the bug
    other than the obviouc catch all of "memory leak".

    Stick a static counter in the function which continually crashes and
    log it to a file or a console : see if you can get a reproducible item
    count before the crash. If you can, run your code in a debugger with a
    break point set for when that counter reaches that number. Step
    through. * Get that number when running it ON the debugger * since the
    debugger can alter memory usage : you want to calculate the
    pre-crash "count" under the wings of the debugger to keep the
    environment as similar as possible.

    The fact that you insert x thousand elements before the crash suggest
    something memory orientated at first glance. But get a reproducible
    case first and then your call stack and data displays will reveal all.

    Good luck!
    Richard G. Riley, Mar 11, 2006
    #2
    1. Advertising

  3. FBM

    Michael Mair Guest

    FBM schrieb:
    > Hi,
    >
    > I am working on a program that simulates one of the elements of ATM.


    A teacher? The targetting system? Part of an enzyme? Something to do
    with fonts? The cash store?
    http://en.wikipedia.org/wiki/Atm
    Please be concise.

    > The simulation stores events which occurs every some milliseconds for a
    > certain amount of time. Every time that an event is stored in a double
    > linked list, the whole list is sorted for the next round.


    Question: Do you mean "exactly one event" when you write "an event"?
    In this case, I'd rather look for the right place to insert the event.
    If you mean "at least one event", consider keeping the new events in
    a doubly linked list of their own, sorting them and inserting them
    between rounds.
    This insertion even can be done by the insertion sort you mention
    later on, as it is a good algorithm for nearly-sorted lists. However,
    knowing more about the property of the presorted list can lead to
    a significant speed-up.
    Note: If you keep track of certain list elements, say every Nth or so,
    you can maybe speed up the insertion as well -- however, this needs
    to be done carefully if it should give you a gain in every possible
    constellation. Ask about this in a more appropriate place, e.g. the
    comp.programming newsgroup.


    > My problem appears when subjecting the program to heavy load, that is,
    > when I run the simulation for more than 10,000 miliseconds (every event
    > occurs in 5-millisecond intervals). Through Eclipse I could find that
    > my sorting algorithm is not working properly..
    >
    > Printing some control information I see that before crashing, the speed
    > of what is shown on the screen increases just before stopping and then
    > showing the segmentation fault error.
    >
    > I could trace the origin of the problem to this function:


    Your analysis may be right or it may not be. General remarks:
    1) Do not rely on the debugger and printed-out information (you
    did use fflush(NULL), yes?) alone.
    2) Even if performance is critical here, nonetheless replace your
    sorting algorithm with a checked one (e.g. qsort from the C library)
    and see whether the problem goes away.
    3) Then build a test frame for your sorting algorithm.
    4) Even if it costs time: Your sorting algorithm should do nothing
    but sorting -- at first.

    Another remark: You refer to the place where you found the algorithm,
    "C Unleashed". You can make it even easier for us to help you by
    saying where you found it (not the page but at least the chapter).

    > // Sort events
    > DLLIST * sortEvents(DLLIST *List) {
    > EVENT *First, *Second;
    > double basketElem1 = 0, basketElem2 = 0;
    > DLLIST *floor = NULL, *floorP = NULL;
    > EVENT *floorElem;
    > int counter1 = 0, counter2 = 0;
    > List = DLGetFirst(List);
    > First = DLGetData(List, NULL, NULL);
    > while(List != NULL) {
    > basketElem1 = First->TimeInit;
    > if( floor != NULL ) {
    > floorP = floor;
    > do {
    > floorElem = DLGetData(floorP, NULL, NULL);
    > basketElem2 = floorElem->TimeInit;
    > if( basketElem1 < basketElem2 || basketElem1 == basketElem2) {

    Unnecessary obscurity: If you mean
    <=
    then write it as such.
    > DLAddBefore(&floorP, 0, First, sizeof *First);
    > break;
    > }
    > if( DLGetNext(floorP) == NULL && basketElem1 > basketElem2 ) {


    Note, the second part of the check is unnecessary:
    You already are in the case of >
    > DLAddAfter(&floorP, 0, First, sizeof *First);
    > break;
    > }
    > floorP = DLGetNext(floorP);
    > counter2++;


    Consider making your logic more explicitly visible:
    if (basketElem1 <= basketElem2) {
    ....
    } else if (NULL == DLGetNext(floorP)) {
    ....
    } else {
    floorP = DLGetNext(floorP);
    counter2++;
    }

    > } while( floorP != NULL);
    >
    > floor = DLGetFirst(floor);
    > } else
    > DLPrepend(&floor, 0, First, sizeof *First);
    >
    > List = DLGetNext(List);
    > Second = DLGetData(List, NULL, NULL);
    > First = Second;
    > counter1++;
    > }
    > DLDestroy(&List);
    > return floor;


    Note: floor() is a function from the standard library.
    Hiding an identifier when it can easily be avoided can lead
    to trouble.

    > }
    >
    > This the implementation of linear insertion sort. I found this on "C
    > Unleashed" (the algorithm, not the implementation).
    >
    > The stack dump showed me that the exact place where the program crashes
    > is here:
    > if( DLGetNext(floorP) == NULL && basketElem1 > basketElem2 ) {
    > DLAddAfter(&floorP, 0, First, sizeof *First); **
    >
    > ** and inside this function DLAddAfter, the instruction:
    > p = DLCreate(Tag, Object, Size);
    >
    > which is precisely where you obtain new memory..


    I admit that I have not looked into your implementation for logic
    correctness but allocating and freeing memory inside a _sorting_
    algorithm is not necessarily a good idea.
    >
    > The program uses lists from "C unleashed" too. Below is the relevant
    > code:
    >
    > Thanks a lot for your help,
    >
    > Fernando
    >
    > +---------------------------------------------------------------+
    > typedef struct EVENT
    > {
    > int codeEvent;
    > char descEvent[80];
    > double TimeInit;
    > double TimeExpire;
    > } EVENT;
    >
    > +-----------------------------------------+
    > DLLIST *DLCreate(int Tag, void *Object, size_t Size)
    > {
    > DLLIST *NewItem;
    >
    > NewItem = malloc(sizeof *NewItem);
    > if(NewItem != NULL)
    > {
    > NewItem->Prev = NewItem->Next = NULL;
    > NewItem->Tag = Tag;
    > NewItem->Size = Size;
    > NewItem->Object = malloc(Size);
    > if(NULL != NewItem->Object)
    > {
    > memcpy(NewItem->Object, Object, Size);
    > }
    > else
    > {
    > free(NewItem);
    > NewItem = NULL;
    > }
    > }
    >
    > return NewItem;
    > }
    >
    > void DLDestroy(DLLIST **List)
    > {
    > DLLIST *Marker;
    > DLLIST *Prev;
    > DLLIST *Next;
    >
    > if(*List != NULL)
    > {
    > /* First, destroy all previous items */
    > Prev = (*List)->Prev;
    > while(Prev != NULL)
    > {
    > Marker = Prev->Prev;
    > DLDelete(Prev);
    > Prev = Marker;
    > }
    >
    > Next = *List;
    > do
    > {
    > Marker = Next->Next;
    > DLDelete(Next);
    > Next = Marker;
    > } while(Next != NULL);
    > *List = NULL;
    > }
    > }
    >
    > DLLIST *DLGetNext(DLLIST *List)
    > {
    > if(List != NULL)
    > {
    > List = List->Next;
    > }
    >
    > return List;
    > }
    >
    > DLLIST *DLGetFirst(DLLIST *List)
    > {
    > if(List != NULL)
    > {
    > while(List->Prev != NULL)
    > {
    > List = List->Prev;
    > }
    > }
    > return List;
    > }
    >
    > int DLPrepend(DLLIST **Item,
    > int Tag,
    > void *Object,
    > size_t Size)
    > {
    > int Result = DL_SUCCESS;
    >
    > DLLIST *p;
    > DLLIST *Start;
    >
    > assert(Item != NULL);
    >
    > p = DLCreate(Tag, Object, Size);
    >
    > if(p != NULL)
    > {
    > if(NULL == *Item)
    > {
    > *Item = p;
    > }
    > else
    > {
    > Start = DLGetFirst(*Item);
    > DLInsertBefore(Start, p);
    > }
    > }
    > else
    > {
    > Result = DL_NO_MEM;
    > }
    >
    > return Result;
    > }
    >
    > int DLAppend(DLLIST **Item,
    > int Tag,
    > void *Object,
    > size_t Size)
    > {
    > int Result = DL_SUCCESS;
    >
    > DLLIST *p;
    > DLLIST *End;
    >
    > assert(Item != NULL);
    >
    > p = DLCreate(Tag, Object, Size);
    >
    > if(p != NULL)
    > {
    > if(NULL == *Item)
    > {
    > *Item = p;
    > }
    > else
    > {
    > End = DLGetLast(*Item);
    > DLInsertAfter(End, p);
    > }
    > }
    > else
    > {
    > Result = DL_NO_MEM;
    > }
    >
    > return Result;
    > }
    >
    >
    > /* Add new item immediately after current item */
    > int DLAddAfter(DLLIST **Item,
    > int Tag,
    > void *Object,
    > size_t Size)
    > {
    > int Result = DL_SUCCESS;
    > DLLIST *p;
    >
    > assert(Item != NULL);
    >
    > p = DLCreate(Tag, Object, Size);
    >
    > if(p != NULL)
    > {
    > if(NULL == *Item)
    > {
    > *Item = p;
    > }
    > else
    > {
    > DLInsertAfter(*Item, p);
    > }
    > }
    > else
    > {
    > Result = DL_NO_MEM;
    > }
    >
    > return Result;
    > }
    >
    > /* Add new item immediately before current item */
    > int DLAddBefore(DLLIST **Item,
    > int Tag,
    > void *Object,
    > size_t Size)
    > {
    > int Result = DL_SUCCESS;
    > DLLIST *p;
    >
    > assert(Item != NULL);
    >
    > p = DLCreate(Tag, Object, Size);
    >
    > if(p != NULL)
    > {
    > if(NULL == *Item)
    > {
    > *Item = p;
    > }
    > else
    > {
    > DLInsertBefore(*Item, p);
    > }
    > }
    > else
    > {
    > Result = DL_NO_MEM;
    > }
    >
    > return Result;
    > }
    >
    > void *DLGetData(DLLIST *Item,
    > int *Tag,
    > size_t *Size)
    > {
    > void *p = NULL;
    >
    > if(Item != NULL)
    > {
    > if(Tag != NULL)
    > {
    > *Tag = Item->Tag;
    > }
    > if(Size != NULL)
    > {
    > *Size = Item->Size;
    > }
    > p = Item->Object;
    > }
    >
    > return p;
    > }
    >
    > +--------------------------------------+


    You are only inserting First, why go through with the whole
    insertion sort?
    Why are you not moving First within in the list but copy it?
    Why are you not immediately destroying first after having copied
    it but destroy it only once at the end?
    Why are you not checking the return values of DLAddBefore()
    and DLAddAfter()?


    Cheers
    Michael
    --
    E-Mail: Mine is an /at/ gmx /dot/ de address.
    Michael Mair, Mar 11, 2006
    #3
  4. FBM said:

    > Printing some control information I see that before crashing, the speed
    > of what is shown on the screen increases just before stopping and then
    > showing the segmentation fault error.


    What did the backtrace show you?

    > I could trace the origin of the problem to this function:
    >
    > // Sort events
    > DLLIST * sortEvents(DLLIST *List) {
    > EVENT *First, *Second;


    First comment - I note that my newsreader has stripped out all your
    indenting. I guess that's the price you pay for using tabs.

    > double basketElem1 = 0, basketElem2 = 0;
    > DLLIST *floor = NULL, *floorP = NULL;


    floor is the name of a standard library function (prototyped in the <math.h>
    header), and it's therefore a good idea to avoid it as an object name in
    your own code.

    > EVENT *floorElem;
    > int counter1 = 0, counter2 = 0;
    > List = DLGetFirst(List);


    This "rewinds" the list, such that List points to the first element in the
    linked list. (I know you know this. I'm just thinking out loud!)

    > First = DLGetData(List, NULL, NULL);


    This yields a pointer to the data stored in the list node.

    > while(List != NULL) {
    > basketElem1 = First->TimeInit;
    > if( floor != NULL ) {
    > floorP = floor;
    > do {
    > floorElem = DLGetData(floorP, NULL, NULL);


    First time in, floor is NULL, so floorP is NULL, so this is passing NULL to
    DLGetData(). So floorElem will be NULL (because DLGetData() returns NULL if
    you pass it NULL as its first parameter)...

    > basketElem2 = floorElem->TimeInit;


    ....and therefore this is going to segfault.

    --
    Richard Heathfield
    "Usenet is a strange place" - dmr 29/7/1999
    http://www.cpax.org.uk
    email: rjh at above domain (but drop the www, obviously)
    Richard Heathfield, Mar 11, 2006
    #4
  5. Michael Mair said:

    > Another remark: You refer to the place where you found the algorithm,
    > "C Unleashed". You can make it even easier for us to help you by
    > saying where you found it (not the page but at least the chapter).


    The sorting stuff is in Chapter 13, and was written by Dann Corbit.

    The list stuff is in Chapter 8.

    <snip>

    > Why are you not checking the return values of DLAddBefore()
    > and DLAddAfter()?


    <grin width="smug">
    Because he didn't read the example code on page 408 carefully enough.
    </grin>

    --
    Richard Heathfield
    "Usenet is a strange place" - dmr 29/7/1999
    http://www.cpax.org.uk
    email: rjh at above domain (but drop the www, obviously)
    Richard Heathfield, Mar 11, 2006
    #5
  6. FBM

    Ben Pfaff Guest

    "FBM" <> writes:

    > I am working on a program that simulates one of the elements of ATM.
    > The simulation stores events which occurs every some milliseconds for a
    > certain amount of time. Every time that an event is stored in a double
    > linked list, the whole list is sorted for the next round.
    >
    > My problem appears when subjecting the program to heavy load, that is,
    > when I run the simulation for more than 10,000 miliseconds (every event
    > occurs in 5-millisecond intervals). Through Eclipse I could find that
    > my sorting algorithm is not working properly..


    Don't try to test a separable unit of code as part of a larger
    whole before you've tested it in isolation. In other words, you
    should write a comprehensive test harness for your linked list
    and sorting routines. Once you're sure that they work in
    isolation, combine it into the larger program. Then you know
    that any problem is in the interface or in the rest of the
    program, not in the linked list.
    --
    "I should killfile you where you stand, worthless human." --Kaz
    Ben Pfaff, Mar 11, 2006
    #6
    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. Chris Ritchey
    Replies:
    7
    Views:
    463
    emerth
    Jul 10, 2003
  2. Sydex
    Replies:
    12
    Views:
    6,443
    Victor Bazarov
    Feb 17, 2005
  3. Chris Ritchey

    Generating a char* from a linked list of linked lists

    Chris Ritchey, Jul 9, 2003, in forum: C Programming
    Replies:
    7
    Views:
    452
    emerth
    Jul 10, 2003
  4. Joerg Schoen

    Mergesort algorithm for linked lists

    Joerg Schoen, Jan 22, 2007, in forum: C Programming
    Replies:
    51
    Views:
    1,570
    Richard Harter
    Jan 30, 2007
  5. jawdoc
    Replies:
    9
    Views:
    731
    Chris Thomasson
    Mar 10, 2008
Loading...

Share This Page