C Strings: malloc & free

Review

  1. Functions to allocate and free memory at part of the standard library that is included thus:
    #include <stdlib.h>

  2. Also included is the symbolic identifier NULL for the pointer to nothing (like null in Java):
    #define NULL ((void) 0)
    Note that NULL is a form of 0, meaning a NULL pointer is false and all other pointer values are true.

  3. Space is allocated by calling malloc with the number of bytes needed (for strings this is always one more than the maximum length of the string to be stored):
    char *pc = malloc(MAXSTR + 1) ;     // can hold a string of up to MAXSTR characters.
    pc = malloc(strlen("Hello!") + 1) ; // can hold a copy of "Hello" with terminating NUL.

  4. The size given to malloc is always in bytes; the sizeof operator allows us to get the size in bytes of any type:
    double *pd ;
    pd = malloc(100 * sizeof(double)) ; // can hold up to 100 double precision numbers.

    double pi = 3.14159 ;
    pd = malloc(100 * sizeof(pi)) ;     // can hold up to 100 double precision numbers.

  5. BE CAREFUL: If p is a pointer, then sizeof(p) is the number of bytes to hold a pointer, not what p points to!:
    int *ip ;
    ip = malloc( sizeof(ip) ) ;   // WRONG! allocate space for an integer pointer.
    ip = malloc( sizeof(*ip) ) ;  // CORRECT! allocate space for an integer.
    ip = malloc( sizeof(int) ) ;  // ALSO CORRECT: take the size of the type.

  6. Space no longer needed must be returned to the memory allocator using free():
    pc = malloc(MAXSTR+1) ;           // get space for a string
    // . . . use the allocated space . . .
    free(pc) ;                        // free up the space associated with pc

  7. Orphaned storage:
    char buf[MAXSTR+1] ;
    pc = malloc(MAXSTR + 1) ;
    pc = buf ;                 // we just lost the space allocated forever.

  8. Dangling references:
    pc = malloc(MAXSTR + 1) ;
    char *pc1 = pc ;
    // . . . use the allocated space . . .
    free(pc) ;
    // . . . work without changing pc or pc1 . . .
    *pc = 'X' ;   // PROBLEM: space was freed - may have been reallocated
    *pc1 = 'Z' ;  // PROBLEM: pc1 aliased pc, so its space was also freed

  9. Spidey says: With great power comes great responsibility.

Setup

For this activity you will implement three versions of a basic filter function to filter (remove) elements from a string; in two of the three cases you will implement both an array version with indexing and a pointer version using malloc() and free().

  1. Create a directory Filter at the top level of your git repository.Download the file filter.zip into this directory, extract the archive contents, and remove the zip file:
    unzip filter.zip
    rm filter.zip

  2. At this point the directory should contain the following files:
    ActivityJournal.txt
    Makefile
    filter.h
    filter.c
    test_filter.c

  3. Make the executable test_filter (the default target of the Makefile) and execute the result:
    make
    ./test_filter

  4. Obviously most of the assertions will fail as the bodies of the functions in filter.c are all skeletons, but if you see the following output you'll know that you downloaded and compiled the skeleton successfully:
    ** Tests of filter_ch_index **
    Assertion failure (test_filter.c @ 96)
    filter_ch_index("abccba", result, 'a')
        Want: "bccb"
        Have: ""
    Assertion failure (test_filter.c @ 100)
    filter_ch_index("abccba", result, 'b')
        Want: "acca"
        Have: ""
    Assertion failure (test_filter.c @ 104)
    filter_ch_index("abccba", result, 'c')
        Want: "abba"
        Have: ""
    Assertion failure (test_filter.c @ 110)
    filter_ch_index("abccba", result, 'z')
        Want: "abccba"
        Have: ""
    ** Test failed - exiting **
    *** TEST SUMMARY ***
    1 test, 8 assertions (4 passed/4 failed)

  5. At this point, use git to add, commit, and push the skeleton. This will show that you at least were able to initialize the project.

Activities

Overview

File filter.h declares the interfaces for five variants of a filter function using both character arrays and character pointers, file filter.c contains skeleton implementations of these functions, and test_filter.c contains unit tests for the functions (you may assume any arguments to the functions are not NULL, are properly terminated, and are large enough for the task at hand):

void filter_ch_index(char string[], char result[], char ch)
Copy string to result while removing all occurrences of ch. You must properly terminate result.

char *filter_ch_ptr(char *string, char ch)
Return a pointer to a copy of string after removing all occurrences of the first occurrence of ch in the string, while ensuring the minimum amount of space is allocated for result string. Of course the resulting string must be properly NUL terminated.
Pseudo-code:
  1. Declare a local char *p_copy variable and allocate enough space to hold the string (the resulting filtered string cannot be any larger, right?). Be careful to make space for a terminating NUL.
  2. Using a second char *p, initalized to p_copy, and use it to copy over all characters from string except those being filtered; ensure the copied string is properly terminated.
  3. Assign to p newly allocated space sufficient to hold the final contents associated with p_copy. Note that this will in general be less space than that originally allocated for p_copy.
  4. Use strcpy() to copy p_copy to the space allocated to p.
  5. Free the space associated with p_copy.
  6. Return p to the caller.
void filter_any_index(char string[], char result[], char remove[])
Copy string to result while removing all occurrences of any character in remove. You must properly terminate result.
char *filter_any_ptr(char *string, char *remove)
Return a pointer to a copy of string after removing all occurrences of any character remove in the string, while ensuring the minimum amount of space is allocated for result string. Of course the resulting string must be properly NUL terminated.

char *filter_substr(char *string, char *substr)
Return a pointer to a copy of string after removing all occurrences of substring substr, while ensuring the minimum amount of space is allocated for result string. You may assume that substr is not the empty string ("").
Example:
   filter_substr("lady gaga's home.", "ga") will return a pointer to the string "lady 's home."

Implementation and Testing

  1. The unit tests in test_filter.c exercise the five functions in filter.c in the order given in the Overview above.
  2. If an assertion within any function's tests fails, then no tests of the following functions will be run.
  3. For this reason, you should implement, test, debug, and fix the functions in the order given.
  4. Use the make command to build your executable test_filter program:
    make
             Creates and up-to-date version of test_filter.
    make clean
             Removes out any cruft (backup files, object files, executable, etc.)
  5. Execute the tests:
    ./test_filter
  6. Test for heap usage errors using:
    valgrind ./test_filter
  7. After you have a version of a function that passes the tests, do a git add / commit / push before going on to the next function. This will ensure you receive credit for all the functions you are able to complete.

Activity Journal

As always, complete the Activity Journal, including your estimated time, your plan, your actual time, and observations.

Assessment (100 points)

We will pull your repository after the due date; the assessment is in terms of this pulled information. We will compile and link your program using the simple command:
    make
If this does not create a program test_filter without syntax or linking errors you cannot receive a grade above 35, and your grade will almost certainly be less than this.