Last Updated: 2019-06-17 Mon 13:19

CSCI 2021 Lab02: C Memory Management

CODE DISTRIBUTION: lab02-code.zip

  • Download the code distribution every lab
  • See further setup instructions below

CHANGELOG:

Mon Feb 4 10:18:15 CST 2019
The original distribution of list_main.c lacked the command echoing that is mentioned in the associated questions. This has been added to the code pack or you can downloaded the updated copy here: list_main.c

1 Rationale

This lab covers the basics of memory layout, C structs, allocation/deallocation, string processing, and their use in some basic program solving.

Associated Reading / Preparation

From any good C resource review:

  • struct declarations
  • String processing / comparison
  • malloc() and free()

Grading Policy

Credit for this lab is earned by taking the associate Lab Quiz which is linked under Canvas / Quizzes. The quiz will ask that you upload your completed QUESTIONS.txt document and then take a short quiz on the material covered in the lab.

See the full policy in the syllabus.

2 Codepack

The codepack for the lab contains the following files:

File Description
QUESTIONS.txt Questions to answer
diagram.c C file for Problem 1
list_main.c C file for Problem 2/3
list_funcs.c C file for Problem 2/3
list.h C file for Problem 2/3

3 Questions

Analyze the files in the provided codepack and answer the questions given in QUESTIONS.txt.

                           __________________

                            LAB 02 QUESTIONS
                           __________________


- Name: (FILL THIS in)
- NetID: (THE kauf0095 IN kauf0095@umn.edu)

Answer the questions below according to the lab specification. Write
your answers directly in this text file and submit it to complete the
lab.


PROBLEM 1: Memory in `diagram.c'
================================

  For each of the C blocks below, give a memory diagram of the block
  indicating memory locations and contents of cells. These blocks appear
  in the file `diagram.c' which you can modify to print results if you
  want to verify your answers.

  MAKE SURE to accurately express the standard sizes for each of the
  kinds of variables ON A 64-BIT MACHINE in your diagrams by placing
  them at appropriate memory addresses that are tightly packed. A
  reminder: on 64-bit machines, all pointers are 64 bits / 8 bytes.


A
~

  ,----
  |   // BLOCK A
  |   int a = 5;
  |   int b = 7;
  |   double x = 4.5;
  |   int *ip = &a;
  |   ip = &b;
  |   int c = *ip;
  |   *ip = 19;
  |   // DRAW MEMORY HERE 
  `----

   ADDR   SYMB  VAL 
  ------------------
   #1048  a         
   #1044  b         


B
~

  ,----
  |   // BLOCK B
  |   int arr[4] = {12, 14, 16, 18};
  |   int *arp = arr;
  |   int brr = 11;
  |   arr[1] = 23;
  |   arp[3] = 29;
  |   arp = &arr[2];
  |   *arp = brr;
  |   // DRAW MEMORY HERE 
  `----

   ADDR   SYMB    VAL 
  --------------------
   #2020  arr[3]   29 
   #2016  arr[2]   11 


C
~

  ,----
  |   // BLOCK C
  |   char str[8] = "hello";
  |   str[5] = 'w';
  |   char *cp = str + 6;
  |   *cp = '\0';
  |   str[0] = 'y';
  |   // DRAW MEMORY HERE 
  `----

   ADDR   SYMB    VAL 
  --------------------
   #3107  str[7]  ?   
   #3106  str[6]  ?   
   #3105  str[5]  \0  
   #3104  str[4]  o   
   #3103  str[3]  l   
   #3102  str[2]  l   
   #3101  str[1]  e   
   #3100  str[0]  h   


PROBLEM 2: Linked List Application
==================================

  This problem deals with small application spread across three files:
  - list.h declares types and functions
  - list_funcs.c defines linked list functions
  - list_main.c has a usable main() function
  You will need to compile the two C files together to produce an
  executable program as in
  ,----
  | gcc list_main.c list_funcs.c
  `----

  Study the code in these and answer the following questions.


A
~

  In `list_main.c', a function related to `scanf()' is used to read
  input. Look up this function and describe its first argument. Also
  mention what else this function is good for and what it returns when
  the end of input is reached.


B
~

  In `list_main.c', a function from the standard C library is used to
  compare strings (character arrays). Describe this function, how to
  call it, and its return value. Describe how it is used to identify
  commands typed by a user in list_main.c. Also determine whether this
  function gives any guidance on the sorting order of strings.


C
~

  Examine where a `list_t' variable is declared in `list_main.c'.  Is
  the list a stack variable or one that has memory dynamically allocated
  with malloc() and then subsequently free()'d?  Examine the convention
  of the `list_init()' function in `list_funcs.c'.  Does this function
  allocate any memory or simply operate on an existing list_t? How is it
  used with the `list_t' declared in `main()'?


D
~

  Examine the `list.h' header file. Describe the C structs that you see
  there. What fields does a `list_t' have? What fields does a `node_t'
  have?  What is the maximum length of strings that can be stored in the
  linked list according to the definitions of the types?


E
~

  Examine functions such as `list_insert()' in `list_funcs.c' which
  allocate nodes. How are they allocated?  How is the size of nodes
  determined so that the correct amount of space is allocated? Where and
  how is the space allocated for nodes de-allocated (which function)?


PROBLEM 3: Linked List Extension
================================

  The files for the linked list application have places indicating where
  a `list_contains()' function and a `contains' command should be
  implemented.  Complete this implementation which will require you to
  write some C code in both `list_funcs.c' and `list_main.c'.  It will
  also require you to do some string comparisons.

  Paste the following below for you answer
  1. Your code for list_contains()
  2. Code you added to main() to enable the "contains" command to work
  3. A sample session of the main application where several inserts are
     done and contains is used to show some items are present and not
     present


PROBLEM 4: Command Echoing
==========================

  Interactive applications like `list_main' are made greatly more useful
  if they can be "scripted": made to perform without the need of human
  interaction.  A common means of doing this is provide a file with
  commands to read in it rather than typing directly.  While nothing in
  `list_main' appears to allow for this, with a few command line tricks
  we can replace typed input with the contents of the file. Such as
  below where a *pipe |* is used.

  ,----
  | > gcc -o list_main list_funcs.c list_main.c
  | 
  | > cat commands.txt              # show contents of commands.txt file
  | insert rolf
  | insert kermit
  | insert fozzy
  | print
  | get 2
  | get 7
  | contains kermit
  | contains scooter
  | delete scooter
  | exit
  | 
  | > cat commands.txt | ./list_main     # use commands.txt as input for list_main
  | Linked List Demo
  | Commands:
  |   print:          shows the current contents of the list
  |   clear:          eliminates all elements from the list
  |   exit:           exit the program
  |   insert thing:   inserts the given string into the list
  |   get index:      get the item at the given index
  |   contains thing: determine if the given thing is in the list
  |                   (NOT YET IMPLEMENTED)
  | 
  | list> list> list> list> 0: fozzy    # several commands read, start of output
  | 1: kermit
  | 2: rolf
  | 
  | list> 2: rolf                       # another command read but not printed
  | 
  | list> index 7 out of bounds for list size 3
  | out of bounds
  | 
  | list> 'kermit' is present
  | 
  | list> not found
  | 
  | list> unknown command delete
  | 
  | list> unknown command scooter
  `----

  Clearly `list_main' is doing something above but it is hard to
  determine what because the commands being read are not printed, a
  feature known as *command echoing*.

  Sprinkled throughout the `list_main.c' code are `printf' statements
  based on the variable `echo' declared near the top of `main'.  This
  `echo' variable is set at the top of `main' based on whether command
  line argument 1 is `-echo'.  When it is, all commands are printed as
  they are read. This is extremely useful in the present case as
  illustrated below.

  ,----
  | > gcc -o list_main list_funcs.c list_main.c    # compile
  | 
  | > cat commands.txt                             # show commands
  | insert rolf
  | insert kermit
  | insert fozzy
  | print
  | get 2
  | get 7
  | contains kermit
  | contains scooter
  | delete scooter
  | exit
  | 
  | > cat commands.txt | ./list_main -echo         # use file as input, echo commands
  | Linked List Demo
  | Commands:
  |   print:          shows the current contents of the list
  |   clear:          eliminates all elements from the list
  |   exit:           exit the program
  |   insert thing:   inserts the given string into the list
  |   get index:      get the item at the given index
  |   contains thing: determine if the given thing is in the list
  |                   (NOT YET IMPLEMENTED)
  | 
  | list> insert rolf                              # commands are echoed
  | 
  | list> insert kermit
  | 
  | list> insert fozzy
  | 
  | list> print                                    # makes understanding behavior easier
  | 0: fozzy
  | 1: kermit
  | 2: rolf
  | 
  | list> get 2
  | 2: rolf
  | 
  | list> get 7
  | index 7 out of bounds for list size 3
  | out of bounds
  | 
  | list> contains kermit
  | 'kermit' is present
  | 
  | list> contains scooter
  | not found
  | 
  | list> delete
  | unknown command delete
  | 
  | list> scooter
  | unknown command scooter
  | 
  | list> exit
  `----

  *You will need to know how to use command echoing in an assignment* so
  study how commands are printed carefully.

  Create another text file with commands in it for `list_main'.  Make
  this file at least 10 lines long with different commands such as
  `insert' and `get'.  Use the pipe technique shown to feed your
  commands to the `list_main' with the `-echo' option set. Show your
  results below.


OPTIONAL PROBLEM
================

  For fun but no extra credit, add a `int list_remove(list_t *list, char
  *query)' function and associated `remove' command to the list
  application.  Keep the following in mind.
  - Follow the convention that `list_remove()' returns an integer
    indicating no change was made (0) or something was removed (1)
  - Do not forget to alter the size of the `list_t' struct on removal.
  - You will need to call `free()' on the removed node to get rid of it
    but do so AFTER re-arranging pointers associated with it.
  - Don't forget special cases such as removing the first node in the
    list.
  This is a surprisingly tricky exercise to get the memory use
  right. You may wish to use valgrind to test whether your program has
  memory leaks or not. Ask a TA for help with this if it has not been
  discussed in class yet (valgrind WILL be discussed later).

4 What to Understand

Ensure that you understand

  • Basics of memory layout on the stack
  • Declaration of structs
  • Basics of strings in C
  • malloc() and free() when using dynamic structures
  • Basic command loops in which a user enters commands which manipulate internal program data

Author: Chris Kauffman (kauffman@umn.edu)
Date: 2019-06-17 Mon 13:19