Memory leak problem

[Fernando Barsoba]

Hi,

After following the advice received in this list, I have isolated the
memory leak problem I am having. I am also using MEMWATCH and I think it
is working properly.

The program does some calculations and stores elements in a list. After
that, a sorting algorithm is used over that list.

Two functions are called before the sorting process:

List = initVoiceChannels(List, TempEvent);
List = SetTimerT1(List, TempEvent);

If I only execute these functions, no memory leak is produced. However,
if I call the sorting function *after* any of these functions, the
memory leak occurs.

Another test has been to store elements in list and then sorting them. I
used the following loop:
-----
typedef struct EVENT
{
double codeEvent;
char descEvent[80];
double TimeInit;
double TimeExpire;
} EVENT;
-----------
mwInit();
DLLIST *List = NULL;
EVENT *TempEvent;
TempEvent = malloc(1 * sizeof *TempEvent);
double i=0;
srand(1);
for( i = 0; i < 20000; i++ ) {
TempEvent->codeEvent = i + 1;
TempEvent->TimeExpire = rand()/1000000;
DLAddAfter(&List, 0, TempEvent, sizeof *TempEvent);
TempEvent->codeEvent);
}
List = sortElements(List);
DLDestroy(&List);
mwTerm();
exit(0);

And there was NO memory leak. So I believe the problem is not in the
sorting algorithm per se.

So, going back to the code that does fail. The log from memwatch is:


============= MEMWATCH 2.71 Copyright (C) 1992-1999 Johan Lindh
=============

Started at Sun Mar 12 12:52:19 2006

Modes: __STDC__ 64-bit mwDWORD==(unsigned long)
mwROUNDALLOC==8 sizeof(mwData)==32 mwDataSize==32


Stopped at Sun Mar 12 12:52:19 2006

unfreed: <7> ../dllist.c(51), 32 bytes at 0x470a30 {04 00 00 00 54 31
00 54 00 FE FE FE FE FE FE FE ....T1.T........}
unfreed: <6> ../dllist.c(45), 20 bytes at 0x4709e8 {00 00 00 00 A8 08
47 00 48 09 47 00 30 0A 47 00 ......G.H.G.0.G.}
unfreed: <5> ../dllist.c(51), 32 bytes at 0x470990 {01 00 00 00 49 4E
49 54 00 FE FE FE FE FE FE FE ....INIT........}
unfreed: <4> ../dllist.c(45), 20 bytes at 0x470948 {00 00 00 00 E8 09
47 00 00 00 00 00 90 09 47 00 ......G.......G.}
unfreed: <3> ../dllist.c(51), 32 bytes at 0x4708f0 {01 00 00 00 49 4E
49 54 00 FE FE FE FE FE FE FE ....INIT........}
unfreed: <2> ../dllist.c(45), 20 bytes at 0x4708a8 {00 00 00 00 00 00
00 00 E8 09 47 00 F0 08 47 00 ..........G...G.}

Memory usage statistics (global):
N)umber of allocations made: 13
L)argest memory usage : 344
T)otal of all alloc() calls: 344
U)nfreed bytes totals : 156
MEMWATCH detected 6 anomalies


And the code is the following. The list is from the book "C unleashed"
from Richard Heathfield et al. chapter 11.

Thanks a lot,

Fernando

#include "main.h"

// FUNCTIONS


// Generate intial event for 'Timer'
DLLIST * SetTimerT1(DLLIST *List, EVENT *TempEvent) {

TempEvent->codeEvent = 4;
strcpy(TempEvent->descEvent, "T1");
TempEvent->TimeInit = MC + Timer;
TempEvent->TimeExpire = 0;

DLAddAfter(&List, 0, TempEvent, sizeof *TempEvent);

MC = MC + Timer;

return List;
}


// Generate Random time
float generateRandomNumber(int intervalA, int intervalB, int incValues) {
float M = intervalA, N = intervalB;
float number = 0;

// incValues is: 0, for neither intervalA nor intervalB included
if( incValues == 0 ) {
do {

//number = M + rand() / (RAND_MAX / (N - M + 1) + 1);
number = M + (N - M) * rand() / ((float) RAND_MAX);
}
while( number == intervalA && number == intervalB );
}
return number;
}


int generateRandomPeriod(float randomNumber, int factor, int typeOfPeriod) {
int X = 0;
int talkspurt = typeOfPeriod;
switch( factor ) {
case 0:
break;
case 1:
X = -(talkspurt)*log(randomNumber);
break;
}
return X;
}

DLLIST * sortElements(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++;
}
List = floor;

return List;

}

// Generate first talkspurt for set of voice Channels
DLLIST * initVoiceChannels(DLLIST *Item, EVENT *TempEvent) {
/*
* Each voice call initiates its first talkspurt at a time Tb randomly
* chosen between (0,1000) msec
*/
int i = 0;
// temp random numbers
float r1, r2;


int Tb; // time first talkspurt
// for every Channel, generate intial talkspurt
for( i = 0; i < Channels; i++) {
// generate random number [0, 1];
r1 = generateRandomNumber(0, 1, 0);
// printf("generated: %f\n", r1);

// generate random start time (0, 1000)
r2 = generateRandomNumber(0, 1000, 0);
// printf("generated: %f\n", r2);

Tb = r1*r2;


TempEvent->codeEvent=NEWTALKSPURT;
strcpy(TempEvent->descEvent, "INIT");
TempEvent->TimeExpire = 0;

TempEvent->TimeInit = Tb;

DLAddAfter(&Item, 0, TempEvent, sizeof *TempEvent);
}

return Item;
}

DLLIST * storeEvent(int typeEvent, int timeEvent, int timeEventExp,
DLLIST *List, EVENT *TempEvent) {

// Event: Set Talkspurt expiration time
if( typeEvent == 2 ) {
TempEvent->codeEvent = typeEvent;
strcpy(TempEvent->descEvent, "TALKSPURT");
TempEvent->TimeExpire = 0;
TempEvent->TimeInit = timeEvent;

DLLIST *ListP = List;
ListP = DLGetLast(List);

DLAddAfter(&ListP, 0, TempEvent, sizeof *TempEvent);
}

// Event: 5 msec period expires
if( typeEvent == 3 ) {
TempEvent->codeEvent = typeEvent;
strcpy(TempEvent->descEvent, "5MSEC");
TempEvent->TimeInit = timeEvent;
TempEvent->TimeExpire = timeEventExp;

DLAddAfter(&List, 0, TempEvent, sizeof *TempEvent);
}

// Event: talkspurt expires
if( typeEvent == 5 ) {
TempEvent->codeEvent = typeEvent;
strcpy(TempEvent->descEvent, "SILENCE");
TempEvent->TimeInit = timeEvent;
TempEvent->TimeExpire = timeEventExp;

DLAddAfter(&List, 0, TempEvent, sizeof *TempEvent);
}


return List;
}


// ***
int main(int argc, char *argv[]) {

mwInit();

if( argc < 3)
printf("Params are not enough");

// check param validity ***

// assign parameters

int param1 = atoi(argv[1]);
int param2 = atoi(argv[2]);


Channels = param1;
Timer = param2;
// ***


// event handling
DLLIST *List = NULL;
EVENT *TempEvent = NULL;

TempEvent = malloc(1 * sizeof *TempEvent);

// initialize voice channels
srand(1);
List = initVoiceChannels(List, TempEvent);

// generate T1 event (variable is 'Timer')
// MC = MC + Timer (2 ms by default)
List = SetTimerT1(List, TempEvent);
printf("Elements in list: %d\n", DLCount(List));
List = sortElements(List);

printf("Elements in list: %d\n", DLCount(List));
free(TempEvent);

/* Destroy the list */
DLDestroy(&List);
mwTerm();
exit(0);
}

#ifndef MAIN_H_
#define MAIN_H_

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <ctype.h>
#include <math.h>
#include <assert.h>

#include "dllist.h"



#include "memwatch.h"



#define NEWTALKSPURT 1;
#define TALKSPURT 2;
#define MEANTALKSPURT 400;
#define MEANSILENCE 600;
#define MAXMC 100;

typedef struct EVENT
{
int codeEvent;
char descEvent[10];
double TimeInit;
double TimeExpire;
} EVENT;


// GLOBAL VARIABLES

double MC = 0;

int Timer;
int Channels;


// ***


DLLIST * SetTimerT1(DLLIST *, EVENT *);
float generateRandomNumber(int, int, int);
int generateRandomPeriod(float, int, int);
DLLIST * sortElements(DLLIST *);
DLLIST * initVoiceChannels(DLLIST *, EVENT *);


#endif /*MAIN_H_*/


/* dllist.c - Double linked list library source
*
* DLLIST - Double-Linked List Library
*
* Copyright (C) 2000 Richard Heathfield
* Eton Computer Systems Ltd
* Macmillan Computer Publishing
*
* This program is free software; you can redistribute it
* and/or modify it under the terms of the GNU General
* Public License as published by the Free Software
* Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will
* be useful, but WITHOUT ANY WARRANTY; without even the
* implied warranty of MERCHANTABILITY or FITNESS FOR A
* PARTICULAR PURPOSE. See the GNU General Public License
* for more details.
*
* You should have received a copy of the GNU General
* Public License along with this program; if not, write
* to the Free Software Foundation, Inc., 675 Mass Ave,
* Cambridge, MA 02139, USA.
*
* Richard Heathfield may be contacted by email at:
* (e-mail address removed)
*
*/

#include <stdlib.h>
#include <string.h>
#include <assert.h>

#include "dllist.h"





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

int DLInsertBefore(DLLIST *ExistingItem, DLLIST *NewItem)
{
int Result = DL_SUCCESS;

if(ExistingItem != NULL && NewItem != NULL)
{
NewItem->Next = ExistingItem;
NewItem->Prev = ExistingItem->Prev;
ExistingItem->Prev = NewItem;
if(NewItem->Prev != NULL)
{
NewItem->Prev->Next = NewItem;
}
}
else
{
Result = DL_NULL_POINTER;
}

return Result;
}

int DLInsertAfter(DLLIST *ExistingItem, DLLIST *NewItem)
{
int Result = DL_SUCCESS;

if(ExistingItem != NULL && NewItem != NULL)
{
NewItem->Prev = ExistingItem;
NewItem->Next = ExistingItem->Next;
ExistingItem->Next = NewItem;
if(NewItem->Next != NULL)
{
NewItem->Next->Prev = NewItem;
}
}
else
{
Result = DL_NULL_POINTER;
}

return Result;
}

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

int DLUpdate(DLLIST *Item,
int NewTag,
void *NewObject,
size_t NewSize)
{
int Result = DL_SUCCESS;

void *p;

if(NewSize > 0)
{
p = realloc(Item->Object, NewSize);
if(NULL != p)
{
Item->Object = p;
memmove(Item->Object, NewObject, NewSize);
Item->Tag = NewTag;
Item->Size = NewSize;
}
else
{
Result = DL_NO_MEM;
}
}
else
{
Result = DL_ZERO_SIZE;
}

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

DLLIST *DLExtract(DLLIST *Item)
{
if(Item != NULL)
{
if(Item->Prev != NULL)
{
Item->Prev->Next = Item->Next;
}
if(Item->Next != NULL)
{
Item->Next->Prev = Item->Prev;
}
Item->Prev = Item->Next = NULL;
}
return Item;
}

void DLDelete(DLLIST *Item)
{
if(Item != NULL)
{
DLExtract(Item);

if(Item->Object != NULL)
{
free(Item->Object);
}
free(Item);
}
}

/* Exchange two items. Both must be non-NULL. */
int DLExchange(DLLIST *ItemA, DLLIST *ItemB)
{
int Result = DL_SUCCESS;
DLLIST *t0;
DLLIST *t1;
DLLIST *t2;
DLLIST *t3;

if(ItemA != NULL && ItemB != NULL)
{
if(ItemA->Next == ItemB)
{
DLExtract(ItemA);
DLInsertAfter(ItemB, ItemA);
}
else if(ItemB->Next == ItemA)
{
DLExtract(ItemB);
DLInsertAfter(ItemA, ItemB);
}
else
{
t0 = ItemA->Prev;
t1 = ItemA->Next;
t2 = ItemB->Prev;
t3 = ItemB->Next;

DLExtract(ItemA);
DLExtract(ItemB);

if(t2 != NULL)
{
DLInsertAfter(t2, ItemA);
}
else
{
DLInsertBefore(t3, ItemA);
}

if(t0 != NULL)
{
DLInsertAfter(t0, ItemB);
}
else
{
DLInsertBefore(t1, ItemB);
}
}
}
else
{
Result = DL_NULL_POINTER;
}

return Result;
}

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 *DLGetPrev(DLLIST *List)
{
if(List != NULL)
{
List = List->Prev;
}

return List;
}

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

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


DLLIST *DLJoin(DLLIST *Left, DLLIST *Right)
{
if(Left != NULL && Right != NULL)
{
Left = DLGetLast(Left);
Right = DLGetFirst(Right);

Left->Next = Right;
Right->Prev = Left;
}

return DLGetFirst(Left);
}

int DLCount(DLLIST *List)
{
int Items = 0;

DLLIST *Prev = List;
DLLIST *Next = List;

if(List != NULL)
{
++Items;
while((Prev = DLGetPrev(Prev)) != NULL)
{
++Items;
}
while((Next = DLGetNext(Next)) != NULL)
{
++Items;
}
}

return Items;
}

int DLWalk(DLLIST *List,
int(*Func)(int, void *, void *),
void *Args)
{
DLLIST *ThisItem = List;
int Result = 0;

if(List != NULL)
{
for(ThisItem = DLGetFirst(List);
0 == Result && ThisItem != NULL;
ThisItem = ThisItem->Next)
{
Result = (*Func)(ThisItem->Tag,
ThisItem->Object,
Args);
}
}
return Result;
}

/* end of dllist.c */

 

[Richard Heathfield]

Fernando Barsoba said:

TempEvent = malloc(1 * sizeof *TempEvent);

Allocations can fail. You don't test this, so...

double i=0;
srand(1);
for( i = 0; i < 20000; i++ ) {
TempEvent->codeEvent = i + 1;

....this statement invokes undefined behaviour if the memory allocation did
indeed fail. Now, if I recall correctly, you're experiencing problems with
your code only when you are dealing with lots of data - and it's precisely
at such a point that you are more likely to suffer from memory shortage. So
it's well worth paying attention to such details.

TempEvent->TimeExpire = rand()/1000000;
DLAddAfter(&List, 0, TempEvent, sizeof *TempEvent);

DLAddAfter() requires memory allocation and, again, this can fail. If so, it
will return DL_NO_MEM, which is defined in "dllist.h" as 1. Since you don't
check for this return value, you don't know whether the allocation
succeeded.

// Generate intial event for 'Timer'
DLLIST * SetTimerT1(DLLIST *List, EVENT *TempEvent) {

TempEvent->codeEvent = 4;
strcpy(TempEvent->descEvent, "T1");
TempEvent->TimeInit = MC + Timer;
TempEvent->TimeExpire = 0;

DLAddAfter(&List, 0, TempEvent, sizeof *TempEvent);

Same applies here.

<snip>

 

[Michael Mair]

Hi,

After following the advice received in this list, I have isolated the
memory leak problem I am having. I am also using MEMWATCH and I think it
is working properly.

The program does some calculations and stores elements in a list. After
that, a sorting algorithm is used over that list.

Two functions are called before the sorting process:

List = initVoiceChannels(List, TempEvent);
List = SetTimerT1(List, TempEvent);

If I only execute these functions, no memory leak is produced. However,
if I call the sorting function *after* any of these functions, the
memory leak occurs.

Another test has been to store elements in list and then sorting them. I
used the following loop:
-----
typedef struct EVENT
{
double codeEvent;
char descEvent[80];
double TimeInit;
double TimeExpire;
} EVENT;
-----------
mwInit();
DLLIST *List = NULL;
EVENT *TempEvent;
TempEvent = malloc(1 * sizeof *TempEvent);
double i=0;
srand(1);
for( i = 0; i < 20000; i++ ) {
TempEvent->codeEvent = i + 1;
TempEvent->TimeExpire = rand()/1000000;
DLAddAfter(&List, 0, TempEvent, sizeof *TempEvent);
TempEvent->codeEvent);
}
List = sortElements(List);
DLDestroy(&List);
mwTerm();
exit(0);

And there was NO memory leak. So I believe the problem is not in the
sorting algorithm per se.

So, going back to the code that does fail. The log from memwatch is:

And the code is the following. The list is from the book "C unleashed"
from Richard Heathfield et al. chapter 11.

<snip: several hundred lines of code>

Your post including the dllist code was about nine hundred lines long;
this is a little bit much for usenet.
In addition, people have to piece together the files in question.
It is usually easier if you provide a web page where you have put
up all the files; then people may have a look at them or download
them as they like and "quote" the relevant aspects back here.

I will have a closer look at your code later on but here are some
first remarks:
- As long as your computer's memory is sufficiently large, there
is no reason to use floats instead of doubles -- with floats you
are only guaranteed to have 6 digits (i.e. you cannot resolve
milliseconds over a one hour interval) and doubles are in no way
slower on modern host PCs.
- If you post code here, indicate if you are using C89 or C99 (or
K&R C) -- your code seems to indicate C99 but could also be C89
plus compiler extensions (frowned upon here because all bets are
off and only people with your compiler and compiler version can
help you in every respect) or C++ code restricted to mostly C
features (which opens a can of worms of its own). Even if you do
use C99, be careful with line comments -- they can break which
can have unforeseen consequences.
- Your code seems to be split into "main.c" and "main.h".
Consider using another file structure, e.g. "main.c", "event.c",
"event.h" -- this makes things easier if you want to reuse the
code; you may even want to consider using "main.c", "event.c",
"event.h", "sortdllist.c", "sortdllist.h", ...


Cheers
Michael

 

[Michael Mair]

Hi,

After following the advice received in this list, I have isolated the
memory leak problem I am having. I am also using MEMWATCH and I think
it is working properly.

The program does some calculations and stores elements in a list.
After that, a sorting algorithm is used over that list.

Two functions are called before the sorting process:

List = initVoiceChannels(List, TempEvent);
List = SetTimerT1(List, TempEvent);

If I only execute these functions, no memory leak is produced.
However, if I call the sorting function *after* any of these
functions, the memory leak occurs.

Another test has been to store elements in list and then sorting them.
I used the following loop:
-----
typedef struct EVENT
{
double codeEvent;
char descEvent[80];
double TimeInit;
double TimeExpire;
} EVENT;
-----------
mwInit();
DLLIST *List = NULL;
EVENT *TempEvent;
TempEvent = malloc(1 * sizeof *TempEvent);
double i=0;
srand(1);
for( i = 0; i < 20000; i++ ) {
TempEvent->codeEvent = i + 1;
TempEvent->TimeExpire = rand()/1000000;
DLAddAfter(&List, 0, TempEvent, sizeof *TempEvent);
TempEvent->codeEvent);
}
List = sortElements(List);
DLDestroy(&List);
mwTerm();
exit(0);

And there was NO memory leak. So I believe the problem is not in the
sorting algorithm per se.

So, going back to the code that does fail. The log from memwatch is:

And the code is the following. The list is from the book "C unleashed"
from Richard Heathfield et al. chapter 11.

<snip: several hundred lines of code>

Your post including the dllist code was about nine hundred lines long;
this is a little bit much for usenet.
In addition, people have to piece together the files in question.
It is usually easier if you provide a web page where you have put
up all the files; then people may have a look at them or download
them as they like and "quote" the relevant aspects back here.

I will have a closer look at your code later on but here are some
first remarks:
- As long as your computer's memory is sufficiently large, there
is no reason to use floats instead of doubles -- with floats you
are only guaranteed to have 6 digits (i.e. you cannot resolve
milliseconds over a one hour interval) and doubles are in no way
slower on modern host PCs.
- If you post code here, indicate if you are using C89 or C99 (or
K&R C) -- your code seems to indicate C99 but could also be C89
plus compiler extensions (frowned upon here because all bets are
off and only people with your compiler and compiler version can
help you in every respect) or C++ code restricted to mostly C
features (which opens a can of worms of its own). Even if you do
use C99, be careful with line comments -- they can break which
can have unforeseen consequences.
- Your code seems to be split into "main.c" and "main.h".
Consider using another file structure, e.g. "main.c", "event.c",
"event.h" -- this makes things easier if you want to reuse the
code; you may even want to consider using "main.c", "event.c",
"event.h", "sortdllist.c", "sortdllist.h", ...

You forgot to include "dllist.h".
Not all people have memwatch.
Your main.h include list could read like that now:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "dllist.h"

#ifdef USE_MEMWATCH
# include "memwatch.h"
#endif

and in main(), you do
#ifdef USE_MEMWATCH
mwInit();
#endif
and
#ifdef USE_MEMWATCH
mwTerm();
#endif

As a first step, I have looked at your random number generation
and suggest "random.c" and "random.h", where you #include "random.h"
in "main.h".
Your original implementation contained
if( incValues == 0 ) {
do {

//number = M + rand() / (RAND_MAX / (N - M + 1) + 1);
number = M + (N - M) * rand() / ((float) RAND_MAX);
}
while( number == intervalA && number == intervalB );
}
This means you do not generate a random number for other
incValues values than 0.
In addition, for intervalA != intervalB, the continuation
condition never can be met; you probably wanted an || instead
of an &&.
Note that for 32 bit ints and 32 bit floats, N and M may not be
exactly representable in float.

--- random.h ---
#ifndef RANDOM_H_
#define RANDOM_H_

enum EgenRandNumBoundInclusion {
EGrnIncludeNone,
EGrnIncludeUpper,
EGrnIncludeLower,
EGrnIncludeBoth,
};

void initRandom (void);
double generateRandomNumber (int intervalA, int intervalB, int incValues);

#endif
----------------

--- random.c ---
#include "random.h"
#include <stdlib.h>

#ifdef TIME_BASED_RANDOM
# include "time.h"
#endif

void initRandom (void)
{
#ifdef TIME_BASED_RANDOM
srand(time(NULL));
#else
srand(1);
#endif
}

/*
** Generate Random time
** incValues is: EGrnIncludeNone, for neither intervalA nor intervalB
included
*/
double generateRandomNumber (int intervalA, int intervalB, int incValues)
{
double lower = intervalA;
double upper = intervalB;
double diff = lower - upper;
double result = 0;
int matchBnd = 0;

do {
result = lower + diff * rand() / ((double) RAND_MAX);
switch (incValues) {
case EGrnIncludeNone:
matchBnd = (result != lower) && (result != upper);
break;
case EGrnIncludeUpper:
matchBnd = (result != lower);
break;
case EGrnIncludeLower:
matchBnd = (result != upper);
break;
case EGrnIncludeBoth:
default:
matchBnd = 1;
break;
}
} while( !matchBnd );

return result;
}
----------------

Changes in main():
#ifdef USE_MEMWATCH
mwInit();
#endif
initRandom();
and no explicit call to srand() in main().
As soon as you want "really random" random numbers, you can
just #define TIME_BASED_RANDOM.

The function generateRandomPeriod() is not used and can thus be
removed from main.c, too.

Cheers
Michael

 

[Fernando Barsoba]

Michael Mair schrieb:

You forgot to include "dllist.h".
Not all people have memwatch.
Your main.h include list could read like that now:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "dllist.h"

#ifdef USE_MEMWATCH
# include "memwatch.h"
#endif

and in main(), you do
#ifdef USE_MEMWATCH
mwInit();
#endif
and
#ifdef USE_MEMWATCH
mwTerm();
#endif

As a first step, I have looked at your random number generation
and suggest "random.c" and "random.h", where you #include "random.h"
in "main.h".
Your original implementation contained
if( incValues == 0 ) {
do {

//number = M + rand() / (RAND_MAX / (N - M + 1) + 1);
number = M + (N - M) * rand() / ((float) RAND_MAX);
}
while( number == intervalA && number == intervalB );
}
This means you do not generate a random number for other
incValues values than 0.
In addition, for intervalA != intervalB, the continuation
condition never can be met; you probably wanted an || instead
of an &&.
Note that for 32 bit ints and 32 bit floats, N and M may not be
exactly representable in float.

--- random.h ---
#ifndef RANDOM_H_
#define RANDOM_H_

enum EgenRandNumBoundInclusion {
EGrnIncludeNone,
EGrnIncludeUpper,
EGrnIncludeLower,
EGrnIncludeBoth,
};

void initRandom (void);
double generateRandomNumber (int intervalA, int intervalB, int incValues);

#endif
----------------

--- random.c ---
#include "random.h"
#include <stdlib.h>

#ifdef TIME_BASED_RANDOM
# include "time.h"
#endif

void initRandom (void)
{
#ifdef TIME_BASED_RANDOM
srand(time(NULL));
#else
srand(1);
#endif
}

/*
** Generate Random time
** incValues is: EGrnIncludeNone, for neither intervalA nor intervalB
included
*/
double generateRandomNumber (int intervalA, int intervalB, int incValues)
{
double lower = intervalA;
double upper = intervalB;
double diff = lower - upper;
double result = 0;
int matchBnd = 0;

do {
result = lower + diff * rand() / ((double) RAND_MAX);
switch (incValues) {
case EGrnIncludeNone:
matchBnd = (result != lower) && (result != upper);
break;
case EGrnIncludeUpper:
matchBnd = (result != lower);
break;
case EGrnIncludeLower:
matchBnd = (result != upper);
break;
case EGrnIncludeBoth:
default:
matchBnd = 1;
break;
}
} while( !matchBnd );

return result;
}
----------------

Changes in main():
#ifdef USE_MEMWATCH
mwInit();
#endif
initRandom();
and no explicit call to srand() in main().
As soon as you want "really random" random numbers, you can
just #define TIME_BASED_RANDOM.

The function generateRandomPeriod() is not used and can thus be
removed from main.c, too.

Cheers
Michael

Hi,

Thanks for your help. I am reviewing and implementing the changes
suggested.

I have put the complete list code in:

http://www4.ncsu.edu/~fbarsob/dllist.c
http://www4.ncsu.edu/~fbarsob/dllist.h

Thanks!

Fernando

 

[Michael Mair]

Thanks for your help. I am reviewing and implementing the changes
suggested.

I have put the complete list code in:

http://www4.ncsu.edu/~fbarsob/dllist.c
http://www4.ncsu.edu/~fbarsob/dllist.h

Okay, let's do the next step: Break the list/event thing away from
main(); I took the event list initialisation into an appropriate
init function and provided a term function.
The allocation of the temporary event was not necessary, so I eliminated
it.

--- main.c ---
#include <stdio.h>
#include <stdlib.h>
#include "event.h"

#ifdef USE_MEMWATCH
# include "memwatch.h"
#endif

int main (int argc, char **argv)
{
int param1, param2;
DLLIST *List;

#ifdef USE_MEMWATCH
mwInit();
#endif
if( argc < 3) {
printf("Params are not enough\n"
"Invokation: %s numberOfEvents dunno\n",
argc > 0 ? argv[0] : "<program>");
exit(EXIT_SUCCESS);
}

// check param validity ***

// assign parameters

param1 = atoi(argv[1]);
param2 = atoi(argv[2]);


// event handling
initEvent (param1, param2, &List);

displayEventListInfo(List);
// generate T1 event (variable is 'Timer')
List = setTimerT1(List);
displayEventList(List);
List = sortElements(List);
displayEventList(List);

termEvent(&List);

#ifdef USE_MEMWATCH
mwTerm();
#endif

exit(0);
}
--------------
"event.h" basically is what has become of "main.h"; I eliminated the
declaration of the global variables from event.h; note that the
proper way would be
double MC = 0.0;
in event.c and
extern double MC;
in event.h -- otherwise you cannot use multiple events.

--- event.h ---
#ifndef EVENT_H_
#define EVENT_H_

#include "stddef.h"
#include "dllist.h"

#define NEWTALKSPURT 1
#define TALKSPURT 2
#define MEANTALKSPURT 400
#define MEANSILENCE 600
#define MAXMC 100

#define DESCLEN 9

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


/* PROTOTYPES */

void initEvent (int channels, int timer, DLLIST **ppList);
void termEvent (DLLIST **ppList);
void displayEventListInfo (DLLIST *pList);
void displayEventList (DLLIST *pList);
DLLIST * setTimerT1 (DLLIST *List);
DLLIST * sortElements (DLLIST *List);

#endif
--------------

Now, only "event.c" remains; I threw out the storeEvent function
as it was not needed here.
I could not see any real problem here, so I introduced a MEM_CHECK
macro and inserted it wherever DL_NO_MEM could be returned.
It is possible that you really just run out of memory; if the
segfault still occurs, then we have to review the algorithms more
closely.
If you do not like the changes in the sorting routine, throw them
out but for the memcheck -- I introduced them for myself.

--- event.c ---
#include "event.h"
#include "random.h"
#include <string.h>
#include <stdio.h>
#include <stdlib.h>

#define MEM_CHECK(ret, list, where, action) \
if (DL_NO_MEM == (ret)) { \
fprintf(stderr, "%s, %d: malloc in " where " failed\n", \
__FILE__, __LINE__); \
fprintf(stderr, "Elements in list: %d\n", DLCount(list)); \
action; \
}


// GLOBAL VARIABLES

static double MC = 0.0;
static int Timer = 0;
static int Channels = 0;

static DLLIST * initVoiceChannels (DLLIST *Item);


void initEvent (int channels, int timer, DLLIST **ppList)
{
DLLIST *pList = NULL;
if (ppList == NULL) {
fprintf(stderr, "%s, %d: ppList NULL, aborting\n",
__FILE__, __LINE__);
exit(EXIT_FAILURE);
}

initRandom();

Channels = channels;
Timer = timer;

// initialize voice channels
pList = initVoiceChannels(pList);

*ppList = pList;
}

void termEvent (DLLIST **ppList)
{
/* Destroy the list */
DLDestroy(ppList);
}

void displayEventListInfo (DLLIST *pList)
{
printf("Elements in list: %d\n", DLCount(pList));
}

void displayEventList (DLLIST *pList)
{
DLLIST *pItem;
displayEventListInfo(pList);

for (pItem = DLGetFirst(pList); pItem != NULL; pItem =
DLGetNext(pItem)) {
EVENT *pEvent = DLGetData(pItem, NULL, NULL);
printf("<%g> ", pEvent->TimeInit);
}
putchar('\n');
}

/*
** Generate intial event for 'Timer'
** MC = MC + Timer (2 ms by default)
*/

DLLIST * setTimerT1 (DLLIST *List)
{
int ret;
EVENT TempEvent = { 4, "T1", 0.0, 0.0 };
TempEvent.TimeInit = MC + Timer;

ret = DLAddAfter(&List, 0, &TempEvent, sizeof TempEvent);
MEM_CHECK(ret, List, "DLAddAfter", return NULL);

MC = MC + Timer;

return List;
}

DLLIST * sortElements (DLLIST *List)
{
EVENT *Event;
double basketElem1 = 0, basketElem2 = 0;
DLLIST *floor = NULL, *floorP = NULL, *currItem = NULL;
int success;

currItem = DLGetFirst(List);
Event = DLGetData(currItem, NULL, NULL);

while(currItem != NULL) {
basketElem1 = Event->TimeInit;
if( floor != NULL ) {
floorP = floor;
do {
basketElem2 = ((EVENT *)DLGetData(floorP, NULL, NULL))->TimeInit;
if (basketElem1 <= basketElem2) {
success = DLAddBefore(&floorP, 0, Event, sizeof *Event);
MEM_CHECK(success, List, "DLAddBefore", (void)0);
break;
} else if (DLGetNext(floorP) == NULL) {
success = DLAddAfter(&floorP, 0, Event, sizeof *Event);
MEM_CHECK(success, List, "DLAddAfter", (void)0);
break;
} else {
floorP = DLGetNext(floorP);
}
} while( floorP != NULL);

floor = DLGetFirst(floor);
} else {
success = DLPrepend(&floor, 0, Event, sizeof *Event);
MEM_CHECK(success, List, "DLPrepend", (void)0);
}

currItem = DLGetNext(currItem);
Event = DLGetData(currItem, NULL, NULL);
}
List = floor;

return List;
}

/*
** Generate first talkspurt for set of voice Channels
*/
static DLLIST * initVoiceChannels (DLLIST *Item) {
/*
* Each voice call initiates its first talkspurt at a time Tb randomly
* chosen between (0,1000) msec
*/
EVENT TempEvent = { NEWTALKSPURT, "INIT", 0.0, 0.0};
int i;

// for every Channel, generate intial talkspurt
for( i = 0; i < Channels; i++) {
double r1, r2;
int success;
r1 = generateRandomNumber(0, 1, EGrnIncludeBoth);
r2 = generateRandomNumber(0, 1000, EGrnIncludeNone);

TempEvent.TimeInit = (int)(r1*r2);

success = DLAddAfter(&Item, 0, &TempEvent, sizeof TempEvent);
MEM_CHECK(success, Item, "DLAddAfter",
{termEvent(&Item); return NULL;});
}

return Item;
}

 

[Fernando Barsoba]

Fernando Barsoba schrieb:

Okay, let's do the next step: Break the list/event thing away from
main(); I took the event list initialisation into an appropriate
init function and provided a term function.
The allocation of the temporary event was not necessary, so I eliminated
it.

--- main.c ---
#include <stdio.h>
#include <stdlib.h>
#include "event.h"

#ifdef USE_MEMWATCH
# include "memwatch.h"
#endif

int main (int argc, char **argv)
{
int param1, param2;
DLLIST *List;

#ifdef USE_MEMWATCH
mwInit();
#endif
if( argc < 3) {
printf("Params are not enough\n"
"Invokation: %s numberOfEvents dunno\n",
argc > 0 ? argv[0] : "<program>");
exit(EXIT_SUCCESS);
}

// check param validity ***

// assign parameters

param1 = atoi(argv[1]);
param2 = atoi(argv[2]);


// event handling
initEvent (param1, param2, &List);

displayEventListInfo(List);
// generate T1 event (variable is 'Timer')
List = setTimerT1(List);
displayEventList(List);
List = sortElements(List);
displayEventList(List);

termEvent(&List);

#ifdef USE_MEMWATCH
mwTerm();
#endif

exit(0);
}
--------------
"event.h" basically is what has become of "main.h"; I eliminated the
declaration of the global variables from event.h; note that the
proper way would be
double MC = 0.0;
in event.c and
extern double MC;
in event.h -- otherwise you cannot use multiple events.

--- event.h ---
#ifndef EVENT_H_
#define EVENT_H_

#include "stddef.h"
#include "dllist.h"

#define NEWTALKSPURT 1
#define TALKSPURT 2
#define MEANTALKSPURT 400
#define MEANSILENCE 600
#define MAXMC 100

#define DESCLEN 9

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


/* PROTOTYPES */

void initEvent (int channels, int timer, DLLIST **ppList);
void termEvent (DLLIST **ppList);
void displayEventListInfo (DLLIST *pList);
void displayEventList (DLLIST *pList);
DLLIST * setTimerT1 (DLLIST *List);
DLLIST * sortElements (DLLIST *List);

#endif
--------------

Now, only "event.c" remains; I threw out the storeEvent function
as it was not needed here.
I could not see any real problem here, so I introduced a MEM_CHECK
macro and inserted it wherever DL_NO_MEM could be returned.
It is possible that you really just run out of memory; if the
segfault still occurs, then we have to review the algorithms more
closely.
If you do not like the changes in the sorting routine, throw them
out but for the memcheck -- I introduced them for myself.

--- event.c ---
#include "event.h"
#include "random.h"
#include <string.h>
#include <stdio.h>
#include <stdlib.h>

#define MEM_CHECK(ret, list, where, action) \
if (DL_NO_MEM == (ret)) { \
fprintf(stderr, "%s, %d: malloc in " where " failed\n", \
__FILE__, __LINE__); \
fprintf(stderr, "Elements in list: %d\n", DLCount(list)); \
action; \
}


// GLOBAL VARIABLES

static double MC = 0.0;
static int Timer = 0;
static int Channels = 0;

static DLLIST * initVoiceChannels (DLLIST *Item);


void initEvent (int channels, int timer, DLLIST **ppList)
{
DLLIST *pList = NULL;
if (ppList == NULL) {
fprintf(stderr, "%s, %d: ppList NULL, aborting\n",
__FILE__, __LINE__);
exit(EXIT_FAILURE);
}

initRandom();

Channels = channels;
Timer = timer;

// initialize voice channels
pList = initVoiceChannels(pList);

*ppList = pList;
}

void termEvent (DLLIST **ppList)
{
/* Destroy the list */
DLDestroy(ppList);
}

void displayEventListInfo (DLLIST *pList)
{
printf("Elements in list: %d\n", DLCount(pList));
}

void displayEventList (DLLIST *pList)
{
DLLIST *pItem;
displayEventListInfo(pList);

for (pItem = DLGetFirst(pList); pItem != NULL; pItem =
DLGetNext(pItem)) {
EVENT *pEvent = DLGetData(pItem, NULL, NULL);
printf("<%g> ", pEvent->TimeInit);
}
putchar('\n');
}

/*
** Generate intial event for 'Timer'
** MC = MC + Timer (2 ms by default)
*/

DLLIST * setTimerT1 (DLLIST *List)
{
int ret;
EVENT TempEvent = { 4, "T1", 0.0, 0.0 };
TempEvent.TimeInit = MC + Timer;

ret = DLAddAfter(&List, 0, &TempEvent, sizeof TempEvent);
MEM_CHECK(ret, List, "DLAddAfter", return NULL);

MC = MC + Timer;

return List;
}

DLLIST * sortElements (DLLIST *List)
{
EVENT *Event;
double basketElem1 = 0, basketElem2 = 0;
DLLIST *floor = NULL, *floorP = NULL, *currItem = NULL;
int success;

currItem = DLGetFirst(List);
Event = DLGetData(currItem, NULL, NULL);

while(currItem != NULL) {
basketElem1 = Event->TimeInit;
if( floor != NULL ) {
floorP = floor;
do {
basketElem2 = ((EVENT *)DLGetData(floorP, NULL, NULL))->TimeInit;
if (basketElem1 <= basketElem2) {
success = DLAddBefore(&floorP, 0, Event, sizeof *Event);
MEM_CHECK(success, List, "DLAddBefore", (void)0);
break;
} else if (DLGetNext(floorP) == NULL) {
success = DLAddAfter(&floorP, 0, Event, sizeof *Event);
MEM_CHECK(success, List, "DLAddAfter", (void)0);
break;
} else {
floorP = DLGetNext(floorP);
}
} while( floorP != NULL);

floor = DLGetFirst(floor);
} else {
success = DLPrepend(&floor, 0, Event, sizeof *Event);
MEM_CHECK(success, List, "DLPrepend", (void)0);
}

currItem = DLGetNext(currItem);
Event = DLGetData(currItem, NULL, NULL);
}
List = floor;

return List;
}

/*
** Generate first talkspurt for set of voice Channels
*/
static DLLIST * initVoiceChannels (DLLIST *Item) {
/*
* Each voice call initiates its first talkspurt at a time Tb randomly
* chosen between (0,1000) msec
*/
EVENT TempEvent = { NEWTALKSPURT, "INIT", 0.0, 0.0};
int i;

// for every Channel, generate intial talkspurt
for( i = 0; i < Channels; i++) {
double r1, r2;
int success;
r1 = generateRandomNumber(0, 1, EGrnIncludeBoth);
r2 = generateRandomNumber(0, 1000, EGrnIncludeNone);

TempEvent.TimeInit = (int)(r1*r2);

success = DLAddAfter(&Item, 0, &TempEvent, sizeof TempEvent);
MEM_CHECK(success, Item, "DLAddAfter",
{termEvent(&Item); return NULL;});
}

return Item;
}

Thanks a lot for the comments... good way to learn..

Looking at my code and comparing it with yours, I saw the following:

> displayEventListInfo(List);
> // generate T1 event (variable is 'Timer')
> List = setTimerT1(List);

This 'List' is pointing to some memory space..

> displayEventList(List);

> List = sortElements(List);

Here (!) .. List#2 returned by sortElements(List#1) is a different
pointer.. The List#1 pointer is lost, but the memory remains allocated ...

MEMWATCH shows no memory leak now, after doing the ugly thing:

> List = setTimerT1(List);

List2 = List;
List = sortElements(List2);
DLDestroy(&List2);

Does it make sense?

Thanks,

Fernando

 

[Michael Mair]

Thanks a lot for the comments... good way to learn..

Looking at my code and comparing it with yours, I saw the following:


This 'List' is pointing to some memory space..


Here (!) .. List#2 returned by sortElements(List#1) is a different
pointer.. The List#1 pointer is lost, but the memory remains allocated ...

MEMWATCH shows no memory leak now, after doing the ugly thing:


List2 = List;
List = sortElements(List2);
DLDestroy(&List2);

Does it make sense?

I have not looked at it in-depth; consider outputting all
addresses of list nodes in displayEventList() -- maybe the
returned node does not belong to the sorted list at all.
Work your way backwards from there.

Cheers
Michael