Problem with sorting algorithm and double linked lists

[FBM]

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

[Michael Mair]

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.

[Richard Heathfield]

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]

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)

[Ben Pfaff]

"FBM" <fb******@gmail.com> 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