Thread: Where do I call free() to prevent memory leakes for this C program

  1. #1
    Registered User
    Join Date
    May 2011
    Posts
    12

    Where do I call free() to prevent memory leakes for this C program

    Hi,

    I believe I need to call free on Hash Table, List Elements and Unique words (htable, result etc). I am not sure where and how to call free as pointers are being used. Sorry program is big but its all working except I am getting some "still reachable" error messages in Valgrind indicating memory leaks.

    Code:
    int wcnt = 0;
    int ucnt = 0;
    int mcnt = 0;
    int scnt = 0; 
    char *mstring = ""; 
    int llen = 0; 
    char *lstring = ""; 
    int lcnt = 0;  
    
    // Hash table
    
    h_ptr *htable;
    int tsize;
    
    // Convert string to lower case
    void lowercase(char *s)
    {
      int i;
      int len = strlen(s);
    
      for (i = 0; i < len; i++)
        {
          if (s[i] >= 'A' && s[i] <= 'Z')
        s[i] -= ('A' - 'a');
        }
    }
    
    
    // Hash table functions
    void new_table(int size)
    {
        tsize = size;
        htable = (h_ptr *) calloc(size, sizeof(h_ptr));
        if (!htable) {
        fprintf(stderr, "Couldn't allocate hash array, exiting\n");
        exit(1);
        }
    
        // At the beginning, each element in the hash table
        // is a NULL pointer
        for(int i=0; i<size; i++)
          {
        htable[i]=NULL;
          }
    }
    
    // Allocate new element to store in hash table
    h_ptr new_element(char *s)
    {
        h_ptr result = (h_ptr) malloc(sizeof(h_rec));
        int wlen = strlen(s);
        if (wlen > llen) {
        lstring = s;
        llen = wlen;
        lcnt = 1;
        } else if (wlen == llen)
        lcnt++;
        if (!result) {
        fprintf(stderr, "Couldn't allocate hash element, exiting\n");
        exit(1);
        }
    
        result->word = s;
        result->freq = 1;
        result->next = NULL; // JAS: Fixed Valgrind report of un-init variable use later
        //free(result);
        return result;
    }
    
    
    // Add characters together
    unsigned hash_function(char *s)
    {
      unsigned val = 0;
      int c;
    
      // String ends in null character: \0
      // Step through string character by character
      // adding the ASCI codes together. Use modular
      // division at end to wrap to hash table size.
      c = *s;
      while(c != '\0')
        {
          val = val + c;
          s++;
          c = *s;
        }
    
      return val % tsize;
    }
    
    
    // Allocate space for string (to be stored in hash table)
    char *save_string(char *s)
    {
      char *result = (char *) malloc(strlen(s)+1);
      if (!result)
        {
          fprintf(stderr, "Couldn't allocate space for string, exiting\n");
          exit(1);
        }
      strcpy(result,s);
      return result;
    }
    
    
    // *Recursively* find string in list.  Add to end if not found
    h_ptr find_element(h_ptr ls, char *s)
    {
      if (!ls) 
        {
          // Come to end of list.  Insert this one 
          ucnt++;
          return new_element(save_string(s));
        }
    
      if (strcmp(s,ls->word) == 0) 
        {
          ls->freq++;
          if (ls->freq > mcnt)
        {
          mcnt = ls->freq;
          mstring = ls->word;
        }
          return ls;
        }
    
      ls->next = find_element(ls->next, s);
    
      return ls;
    }
    
    
    h_ptr sort_words()
    {
        h_ptr ls = NULL;
        h_ptr ele;
        h_ptr *array = calloc(ucnt, sizeof(h_ptr));
        int i, j;
        int cnt = 0;
        scnt = 0; // Count singletons
    
        // Sort hash table elements and save as pointers in 'array'
        for (i = 0; i < tsize; i++)
           for (ele = htable[i]; ele != NULL; ele = ele->next) {
            if (ele->freq == 1)
            scnt++;
    
            for (j = cnt; j > 0 && ele->freq > array[j-1]->freq; j--)
              array[j] = array[j-1];
    
            array[j] = ele;
            cnt++;
        }
    
        // Convert the hash table into a big linked list
        // based on the order in 'array'
        ls = array[0];
        for (j = 0; j < cnt-1; j++)
        array[j]->next = array[j+1];
        array[cnt-1]->next = NULL;
        free ((void *) array);
    
        return ls;
    }
    
    // Insert string into hash table at correct location
    void insert_string(char *s)
    {
        int index;
        lowercase(s);
        index = hash_function(s);
        htable[index] = find_element(htable[index], s);  
    
    }
    
    // Extract word from file
    #define BSIZE 1024
    char buf[BSIZE];
    int bufvalid = 0;
    FILE *infile;
    
    void init_token(FILE *in) {
        bufvalid = 0;
        infile = in;
    }
    
    // Added some non-ASCII characters encountered in European parliament corpus
    static char *skipchar = " \t\n\r.,:;/<>()[]{}?!\"-'\0xc2\0xa0";
    
    // Keep getting tokens.  Return NULL when no more
    char *get_word()
    {
        char *s = NULL;
        while (1) {
        if (bufvalid) {
            s = strtok(NULL, skipchar);
            if (s)
            break;
        }
        if (!fgets(buf, BSIZE, infile))
            return NULL;
        bufvalid = 1;
        s = strtok(buf, skipchar);
        if (s)
            break;
        }
        wcnt++;
        return s;
    }
    
    
    #define MAXNG 10
    
    char *get_token(int ngram)
    {
        /* Buffer of last ngram-1 tokens */
        static char token_buf[MAXNG][BSIZE];
        static int first = 1;
        static int bindex = 0; /* In which buffer to insert next token */
        static char sbuf[BSIZE];
        char *nextpos = sbuf;
        int i; int index;
    
        if (ngram == 1)
        return get_word();
        if (first) {
        /* Get ngram-1 tokens */
        while (bindex < ngram-1) {
            char *word = get_word();
            if (!word) {
            return NULL; /* Document doesn't have enough tokens */
            }
            strcpy(token_buf[bindex++], word);
        }
        first = 0;
        }
        /* Get new token */
        char *word = get_word();
        if (!word) {
        return NULL; /* No more ngrams */
        }
        strcpy (token_buf[bindex++], word);
        if (bindex >= MAXNG)
        bindex = 0;
        /* Generate string of last ngram-1 tokens */
        index = bindex - ngram;
        if (index < 0)
        index += MAXNG;
        for (i = 0; i < ngram; i++) {
        if (i != 0)
            *nextpos++ = ' ';
        word = token_buf[index];
        strcpy(nextpos, word);
        nextpos += strlen(word);
        index++;
        if (index >= MAXNG)
            index = 0;
        }
    #if 0
         printf("Next n-gram = '%s'\n", sbuf);
    #endif
        return sbuf;
    }
    
    
    
    // Find statistics of word frequency in document
    void word_freq(FILE *src, int details, int ngram, int size)
    {
        char *s;
        h_ptr list_head, ptr;
    
        printf(" Initializing hash table...\n");
        init_token(src);
        new_table(size);
    
        printf(" Inserting all n-grams into hash table in lowercase form...\n");
        while ((s = get_token(ngram)))
          {
        insert_string(s);
          }
    
        printf(" Sorting all hash table elements according to frequency...\n");
        list_head = sort_words();
    
        if (details > 0) {
        printf("\nAnalysis Details:\n(Top %i list of n-grams)\n", details);
        ptr = list_head;
        while (ptr && details--) {
            printf("%d\t'%s'\n", ptr->freq, ptr->word);
            ptr = ptr->next;
        }
        }
    
        printf("\nAnalysis Summary:\n");
        printf("%d total n-grams\n", wcnt);
        printf("%d unique n-grams\n", ucnt);
        printf("%d singleton n-grams (occur only once)\n", scnt);
        printf("Most common n-gram (with %d occurrences) is '%s' \nLongest n-gram (%d have length %d) is '%s'\n",
           mcnt, mstring, lcnt, llen, lstring);
    
    }
    
    int main(int argc, char *argv[])
    {
        int details = 10;
        int hash_table_size = 1024;
        int ngram = 1;
        char *fname = NULL;
        FILE *infile = stdin;
    
        printf("Running analysis program...\n");
    
        add_string_option("file", &fname);
        add_int_option("ngram", &ngram);
        add_int_option("details", &details);
        add_int_option("hash-table-size", &hash_table_size);
    
        printf("\nOptions used when running program:\n");
        parse_options(argc, argv, NULL);
        show_options(stdout);
    
        printf("N-gram size %d\n", ngram);
        if (fname) {
        infile = fopen(fname, "r");
        if (!infile) {
            fprintf(stderr, "Couldn't open file '%s'\n", fname);
            exit(1);
        }
        }
    
        printf("\nRunning analysis... (This can take several minutes or more!)\n");
        word_freq(infile, details, ngram, hash_table_size);
        printf("Total time = %f seconds\n", (double) clock() / CLOCKS_PER_SEC);  
    
        fclose(infile);
    
        **//free ((void *) htable);**
    
    
        return 0;
    }
    Thanks
    Last edited by redworker; 03-08-2013 at 08:14 PM.

  2. #2
    Registered User
    Join Date
    Oct 2006
    Posts
    3,445
    generally, the rule is to free memory/resources as soon as they are no longer in use.

  3. #3
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    Quote Originally Posted by Elkvis View Post
    generally, the rule is to free memory/resources as soon as they are no longer in use.
    A consequence of this is that, if you can't tell when a resource is no longer needed, you need to redesign so you can tell.
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Buttercup, and read this, this, and this before posting again.

  4. #4
    Registered User
    Join Date
    May 2011
    Posts
    12
    Yeah, I though I knew where should i call free() but it didn't work. For example, what do you think when should I call free() on results variable. I tried it on several places and it made it worse. Any thoughts?

    Thanks

  5. #5
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    Quote Originally Posted by redworker View Post
    Yeah, I though I knew where should i call free() but it didn't work. For example, what do you think when should I call free() on results variable. I tried it on several places and it made it worse. Any thoughts?
    Yeah, you need to redesign from scratch. Your basic problem is that you are trying to eliminate memory leaks from code that you hacked together without giving any thought to resource management. The thing is, resource management needs to be a primary design consideration: it is virtually impossible to get memory management right when you add it as an afterthought. Which is exactly what you have done.



    The main problem I see in your code is that the functions which use calloc() and realloc() return those pointers to the caller. Therefore you need to look at the logic of the caller (or callers) to decide when that memory is no longer needed. When a function obtains memory using malloc/calloc/realloc, and then returns that pointer to the caller, it forces EVERY caller to be responsible for releasing that memory.

    Just trying to add calls of free() in "several places" doesn't cut it, because you will also leave some leaks unattended or (probably worse since it introduces undefined behaviour) deallocate some blocks of memory more than once.

    As I said before, if you can't describe unambiguously when a resource is no longer needed, you can't hope to be able to release it safely.
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Buttercup, and read this, this, and this before posting again.

  6. #6
    Registered User
    Join Date
    May 2011
    Posts
    12
    @grumpy
    Can't really redesign as I am doing an exercise to detect and fix memory leaks. This code was all given and I just want to get rid of memory leaks to get some experience with memory management. I was able to fix some but I am stuck with couple that are using pointers and have weird syntax. I hate pointers and they usually confuse me. Not sure where to call free() for results and htables. I tried several places that seemed logical but it didn't work.

  7. #7
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Well the code is basically
    - build hash table
    - use hash table
    - free hash table

    > **//free ((void *) htable);**
    So you need to implement a function like
    freeHash ( htable );

    All this needs is a bit of study of how the hash table is build, and then you write the code to follow all the arrays and lists of pointers, freeing things as you go.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  8. #8
    Registered User
    Join Date
    May 2011
    Posts
    12
    So, I need to create a function that iterates (for loop) through the list and then call free()? I will do some research on hash tables and will try if I can do it.

    Thanks for the help

  9. #9
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Here's an example
    Code:
    int **arr;
    int rows = 5, cols = 10;
    
    arr = malloc( rows * sizeof(*arr) );
    for ( r = 0 ; r < rows ; r++ ) arr[r] = malloc( cols * sizeof(*arr[r]) );
    
    // more code
    
    
    // go through the nested hierarchy of allocations
    // free inner things before outer things.
    for ( r = 0 ; r < rows ; r++ ) free( arr[r] );
    free( arr );
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  10. #10
    Registered User
    Join Date
    May 2011
    Posts
    12
    How does this look:

    Code:
    void freeHash(htable) 
    {      
      if (!htable) return;
      for (int i=0; i<tsize; i++)
        free(htable[i]);
      free(htable);
    }
    Is it correct, its not making big difference in memory leaks though. Maybe I need to free results too? Any ideas on how to free results?

    Thanks
    Last edited by redworker; 03-09-2013 at 12:14 PM.

  11. #11
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by redworker View Post
    Yeah, I though I knew where should i call free() but it didn't work.
    I'm curious as to what "didn't work" means.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  12. #12
    Registered User
    Join Date
    May 2011
    Posts
    12
    By didn't work I mean it didn't make any difference with my memory leaks errors. I think I need to call free() on results as well to get rid of errors. Tried several things but it making error even more worse.

    Thanks

  13. #13
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > How does this look:
    What about all the results of calling save_string() as well?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  14. #14
    Registered User
    Join Date
    May 2011
    Posts
    12
    Ok, I was able to make some memory leaks go away by calling free on htable. How do I call free() on resluts?

    Code:
    h_ptr new_element(char *s)
    {
        h_ptr result = (h_ptr) malloc(sizeof(h_rec));
        int wlen = strlen(s);
        if (wlen > llen) {
    	lstring = s;
    	llen = wlen;
    	lcnt = 1;
        } else if (wlen == llen)
    	lcnt++;
        if (!result) {
    	fprintf(stderr, "Couldn't allocate hash element, exiting\n");
    	exit(1);
        }
    
        result->word = s;
        result->freq = 1;
        result->next = NULL; 
        
        return result;
    }
    
    char *save_string(char *s)
    {
      char *result = (char *) malloc(strlen(s)+1);
      if (!result)
        {
          fprintf(stderr, "Couldn't allocate space for string, exiting\n");
          exit(1);
        }
      strcpy(result,s);
      return result;
    }
    I tried free(results); but that breaks the program as its returning results as well. Where do I call it then?

  15. #15
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by redworker View Post
    By didn't work I mean it didn't make any difference with my memory leaks errors. I think I need to call free() on results as well to get rid of errors. Tried several things but it making error even more worse.
    Okay, cool thanks. This needs to be mentioned because we often get people on here who complain that "free" isn't working because they can access the memory after calling free.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 16
    Last Post: 12-28-2012, 04:07 PM
  2. Program that displays amount of free memory
    By trancedeejay in forum Linux Programming
    Replies: 3
    Last Post: 01-13-2006, 01:27 PM
  3. Making a program to free up Ram memory
    By cfrost in forum Windows Programming
    Replies: 1
    Last Post: 10-03-2004, 06:52 AM
  4. How to prevent exiting from running program
    By scorpio_IITR in forum Linux Programming
    Replies: 5
    Last Post: 01-18-2004, 04:15 AM
  5. How to free memory in this program
    By Coconut in forum C Programming
    Replies: 1
    Last Post: 10-26-2002, 10:57 PM

Tags for this Thread