supposed leak in a recursive algorithm

Discussion in 'C Programming' started by Inso Haggath, Dec 29, 2005.

  1. Inso Haggath

    Inso Haggath Guest

    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;
    }
    Inso Haggath, Dec 29, 2005
    #1
    1. Advertising

  2. Inso Haggath

    moosdau Guest

    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?
    moosdau, Dec 29, 2005
    #2
    1. Advertising

  3. On Thu, 29 Dec 2005 05:07:15 +0300, Inso Haggath <>
    wrote:

    >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>>
    Barry Schwarz, Dec 29, 2005
    #3
    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. index
    Replies:
    18
    Views:
    2,548
    opalinski from opalpaweb
    May 11, 2006
  2. Replies:
    0
    Views:
    3,102
  3. Richard Heathfield

    Leak or no leak ??

    Richard Heathfield, Jul 10, 2006, in forum: C Programming
    Replies:
    4
    Views:
    336
    Richard Heathfield
    Jul 10, 2006
  4. n00m
    Replies:
    12
    Views:
    1,094
  5. vamsi
    Replies:
    21
    Views:
    2,033
    Keith Thompson
    Mar 9, 2009
Loading...

Share This Page