supposed leak in a recursive algorithm

[Inso Haggath]

Good day,

Firstly, yes, i am a first year student,
and yes, i need help with my home work.
But i really want to learn something from it.

The task was to find all words in a file
that are equal to a certain degree (percentage of first letters).

I decided to make a recursive algorithm that is below.
It works, and works fast (at least i think so).
But i get a feeling that there is a major memory leak.
I will really appreciated it, if you point me to it,
or point me that there is no such thing.

And lastly, excuse me for any misspelling, English is not my native.

/*
* Recursive search
* A sorted list on entry
*/

list *do_search(list *l, const char percent) {
static int pos = 1; /* Symbol position */
static list *found = list_create(); /* result list */
char c, *ref;
int i, level;
list *n;

list_rewind(l);

/* Nothing to see here, move along.. */
if(list_getsize(l)<2) return NULL;

/* Until which symbol should we go on */
level = list_getmax(l)*percent / 100 ;

for(c='a'; c<='z'; c++) {

n = list_create();

while((ref = list_next(l)) != NULL){
if (ref[pos-1] == c) {
if(level > pos) {
/* Still unsatisfactory */
list_add(n,ref);
} else {
/* We`we already compared sufficient ammount
of symbols, so lets push it in result */
list_add(found,ref);
}
}
}

pos++;
do_search(n, percent);
pos--;
list_rewind(l);
}
return found;
}

The small list manipulation set below.

typedef struct list {
struct node *first;
struct node *last;
struct node *cur;

unsigned long size;
}list;

typedef struct node {
char *ref;
struct node *next;
}node;

typedef char *str;

void util_qsort(str *, int, int);
void util_swap(str *, int, int);


list *list_create() {
list *l = (list *) malloc(sizeof(list));
if(l) {
l->last = l->first = l->cur= NULL;
l->size = 0;
} else {
printf("\nMemory error\n");
}

return l;
}

char *list_next(list *l) {
node *p;
if(p = l->cur) {
l->cur = (l->cur)->next;
return p->ref;
} else return NULL;
}

void list_rewind(list *l) {
l->cur = l->first;
}

void list_add(list *l, char *ref) {
node *p = (node *) malloc(sizeof(node));

if(p) {
p->ref = ref;
p->next = NULL;

if(l->size) {
(l->last)->next = p;
l->last = p;

} else {
l->last = l->first = l->cur = p;
}
l->size++;
} else {
printf("\nMemory error\n");
}
}

void list_print(list *l) {
node *p = l->first;

while(p) {
printf("%s \n", p->ref);
p = p->next;
}
}

void list_delete(list *l) {
node *p = l->first;
node *tmp;

while(p) {
tmp = p;
p = tmp->next;
free(tmp);
}
free(l);
}

list *list_map(str map, int size) {
int i;
str p;
list *l = list_create();

for(i=0, p = map; i<size; i++) {
list_add(l,p);
p += (strlen(p) + 1);
}
return l;
}

int list_getmax(list *l) {
node *p = l->first;
int max = 0, cur;

while(p) {
cur = strlen(p->ref);
if(cur > max) max = cur;
p = p->next;
}
return max;
}

int list_getsize(list *l) {
return l->size;
}

 

[moosdau]

Is this your whole thing?
Do you compile it in any compiler?

it's mess-up----shouldn't the "typedef" statements be supposed on the
top?
and ,there are these statements in your code:
void util_qsort(str *, int, int);
void util_swap(str *, int, int);
where are the definitions?

you defined str as "char*", so str mean a pointer already, are you
surely
want to use a "pointer to pointer" parameter?

 

[Barry Schwarz]

Good day,

Firstly, yes, i am a first year student,
and yes, i need help with my home work.
But i really want to learn something from it.

The task was to find all words in a file
that are equal to a certain degree (percentage of first letters).

I decided to make a recursive algorithm that is below.
It works, and works fast (at least i think so).
But i get a feeling that there is a major memory leak.
I will really appreciated it, if you point me to it,
or point me that there is no such thing.

And lastly, excuse me for any misspelling, English is not my native.

/*
* Recursive search
* A sorted list on entry
*/

list *do_search(list *l, const char percent) {

Where is the definition of list?

static int pos = 1; /* Symbol position */
static list *found = list_create(); /* result list */
char c, *ref;
int i, level;
list *n;

list_rewind(l);

Is that an ell or a one? Where is the prototype for the function?

/* Nothing to see here, move along.. */
if(list_getsize(l)<2) return NULL;

/* Until which symbol should we go on */
level = list_getmax(l)*percent / 100 ;

for(c='a'; c<='z'; c++) {

Why do you think the letters of the alphabet are contiguous? They are
not on my system.

n = list_create();
snip
}

The small list manipulation set below.

typedef struct list {
struct node *first;
struct node *last;
struct node *cur;

unsigned long size;
}list;

It would be helpful if you posted your code in a format that let us
cut and paste it to our compiler for testing.

typedef struct node {
char *ref;
struct node *next;
}node;

typedef char *str;

void util_qsort(str *, int, int);
void util_swap(str *, int, int);

Where are these functions defined?

list *list_create() {
list *l = (list *) malloc(sizeof(list));

Don't cast the return from malloc. It doesn't help but does suppress
a useful message if you forget to include stdlib.h.

if(l) {
l->last = l->first = l->cur= NULL;
l->size = 0;
} else {
printf("\nMemory error\n");
}

return l;
}

snip


<<Remove the del for email>>