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