Reading 09: Memory and Data Structures

Everyone:

Next week, we will delve deeper into memory management and data structures in C. In particular, we will discuss how a typical address space is laid out, how to dynamically allocate memory using malloc (and how to release it with free), and how to create data structures with structs and unions.

TL;DR

The focus of this reading is to explore memory management and data structures in C and learn how to use valgrind and gdb.

Readings

The readings for this week are:

Optional References

Quiz

This week, the reading is split into two sections: the first part is a dredd quiz, while the second part involves one C program: str_title.c.

To test the C program, you will need to download the Makefile and test scripts:

$ git checkout master                 # Make sure we are in master branch
$ git pull --rebase                   # Make sure we are up-to-date with GitLab

$ git checkout -b reading09           # Create reading09 branch and check it out

$ cd reading09                        # Go into reading09 folder

# Download Reading 09 Makefile
$ curl -sLOk https://gitlab.com/nd-cse-20289-sp19/cse-20289-sp19-assignments/raw/master/reading09/Makefile

# Download, build, and execute tests
$ make test

Questions

Given the following C program, allocations.c, which simply declares a series of variables:

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    double x;
    double y;
} Point;

typedef union {
    char   c;
    int    i;
    float  f;
    double d;
} Block;

double GD = 3.14;

int main(int argc, char *argv[]) {
    int    a[]  = {4, 6, 6, 3, 7};
    char  *sp   = "Happy Kid";
    char   sa[] = "Frug";
    Block  b    = {0};

    Point   p0  = {0, 0};
    Point  *p1  = NULL;
    Point  *p2  = malloc(sizeof(Point));
    Point  *p3  = malloc(10*sizeof(Point));
    Point **p4  = malloc(10*sizeof(Point *));

    return 0;
}

And the following C program, str_title.c, which converts each command-line argument into title-case:

/* str_title: convert strings to title-case */

#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char *str_title(const char *s) {
    char *t = malloc(strlen(s));
    strncpy(t, s, strlen(t));

    char *c = t;
    while (*c) {
      *c = toupper(*c);
      while (*c && !isspace(*c++));
      while (*c &&  isspace(*c++));
    }

    return t;
}

int main(int argc, char *argv[]) {
    for (int i = 1; i <= argc; i++) {
      char *t = str_title(argv[i]);
      puts(t);
    }
    return 0;
}

Record the answers to the following Reading 09 Quiz questions in your reading09 branch:

Programs

Given the provided str_title.c and Makefile, you are to do the following:

Modify Makefile to include a rule for the str_title program. Be sure to use the CC and CFLAGS variables in your rule.

Note: Consider the use of automatic variables.
Modify str_title.c so that it no longer has any uninitialized memory accesses, memory leaks, invalid memory acceses, or logical errors.

Note: The str_title must not modify the original string (hence the const char *). Consider the use of strdup.

Debugging

Use this as an opportunity to utilize valgrind and gdb to debug str_title.c.

Once you have a working Makefile, you should be able to use the make command to run your recipes:

$ make clean                                  # Remove targets
rm -f str_title

$ make                                        # Build targets
gcc -Wall -std=gnu99 -g -o str_title str_title.c

$ ./str_title "harry potter"                  # Test manually
Harry Potter

$ make test                                   # Test scripts

Submission

To submit you work, follow the same process outlined in Reading 01:

$ git checkout master                 # Make sure we are in master branch
$ git pull --rebase                   # Make sure we are up-to-date with GitLab

$ git checkout -b reading09           # Create reading09 branch and check it out

$ cd reading09                        # Go into reading09 folder

$ $EDITOR answers.json                # Edit your answers.json file

$ ../.scripts/submit.py               # Check reading09 quiz
Submitting reading09 assignment ...
Submitting reading09 quiz ...
      Q1 2.00
      Q2 0.25
      Q3 0.25
   Score 2.50

$ git add answers.json                # Add answers.json to staging area
$ git commit -m "Reading 09: Quiz"    # Commit work

$ $EDITOR str_title.c                 # Edit source code

$ make test                           # Build and Run tests
Testing str_title ...
 str_title (no arguments)                 ... Success
 str_title (no arguments) (valgrind)      ... Success
 str_title  harry potter                  ... Success
 str_title  harry potter  (valgrind)      ... Success
 str_title 'harry potter'                 ... Success
 str_title 'harry potter' (valgrind)      ... Success
 str_title  a b c d                       ... Success
 str_title  a b c d  (valgrind)           ... Success
 str_title 'a b c d'                      ... Success
 str_title 'a b c d' (valgrind)           ... Success
   Score 1.50

$ git add Makefile                    # Add Makefile to staging area
$ git add str_title.c                 # Add source code to staging area
$ git commit -m "Reading 09: Code"    # Commit work

$ git push -u origin reading09        # Push branch to GitLab

Remember to create a merge request and assign the appropriate TA from the Reading 09 TA List.