\documentclass[11pt]{article}
\usepackage[left=1in,right=1in,top=0.75in,bottom=0.75in]{geometry}
\usepackage[svgnames]{xcolor}
\usepackage[colorlinks,urlcolor=DarkRed]{hyperref}
\usepackage{url}
\usepackage{upquote}
\usepackage{fancyvrb}
\usepackage{textcomp}

\pagestyle{myheadings}
\markright{MAT 4370: Programming Assignment 10}

\begin{document}
\thispagestyle{empty}
\begin{center}
{\Large  MAT 4370: Programming Assignment 10}\\
Due: Friday, March 22
\end{center}


\subsection*{Checking for Memory Leaks}
As discussed in class, having a memory leak in a C program is a
serious bug --- yet it can be challenging to find these
leaks.  Fortunately, there are software tools which help us locate
leaks.  For the first part of this assignment, you will install one
such tool and then use it on a program known to have a leak.

\subsection*{Installing Valgrind}
The tool we will use is known as Valgrind, described at
its website, \url{http://valgrind.org/}.  Here is a brief summary of
how to install this tool in the Macintosh lab. (Installation for other
Unix-like systems is similar.) 

\begin{enumerate}
\item Download the source code for the current release of the
  software, a file named: 
\begin{quote}
{\tt valgrind-3.8.1.tar.bz2}
\end{quote}
The suffix {\tt .bz2} indicates it is a compressed file and {\tt .tar}
indicates it is an archive.  In the Unix world, both of these are
quite common.

\item Using the Finder, move this file to your home directory.

\item Again with the Finder, uncompress and extract the files in the
  archive by double clicking on its icon.  This will produce a folder
  named {\tt valgrind-3.8.1}.  (The compressed version you downloaded
  can now be discarded.)

\item In the {\tt valgrind-3.8.1} directory there is a file named {\tt
    README}. (Open that file and read it.)  Of particular importance is
  the section ``to install from a tar.bz2 distribution.''  Don't do
  what it says just yet --- these steps are described below.

\item Open a terminal window and change directories to {\tt
    valgrind-3.8.1}.

\item Determine your home directory:
\begin{quote}
\verb!echo !$\mathtt{\sim}$
\end{quote}
In response, this should give you something like:
\verb!/external/Users/jcollege!, assuming your name is Joe College.   

\item Configure Valgrind, by giving a command similar to the following:
\begin{quote}
\verb!./configure --prefix=/external/Users/jcollege/valgrind!
\end{quote}
(Use your home directory, not Joe's!)

\item In response, you will receive a number of confirmations and see
  evidence of a number of actions.

\item Compile the Valgrind software suite:
\begin{quote}
\verb!make!
\end{quote}
In response, the \verb!gcc! compiler will be used to compile a number
of C source files, which will take a few minutes.  You will see
hundreds of lines of text scroll past your terminal window.  

\item Install the Valgrind software suite:
\begin{quote}
\verb!make install!
\end{quote}
If all went well, you will now have an installation of Valgrind stored
in a folder named {\tt valgrind}.  Using the Finder, go look for this
now.  When you find it, descend along the following path:
\begin{quote}
\verb!valgrind/share/doc/valgrind!
\end{quote}
There you will find extensive documentation for this software.

\item Now that you have the Valgrind software, you need to adjust your
  \verb!PATH! so the system can find it.  To do this:
\begin{enumerate}
\item Edit the file named \verb!.profile!, found in your home
  directory.  If you don't already have such a file, then
  create it.  As the final line in this file, add the following:
\begin{quote}
\verb!PATH=$PATH:!$\mathtt{\sim}$\verb!/bin:!$\mathtt{\sim}$\verb!/valgrind/bin!
\end{quote}
You are asking for two directories to be added to your \verb!PATH!:
one for your own personal binaries, and one for those of Valgrind.

\item After editing this file, open a new terminal window and check
  the value of \verb!PATH!:
\begin{quote}
\verb!echo $PATH!
\end{quote}
In response, you should see a sequence of paths, ending with the
directory where the Valgrind programs are stored.

\item Check it out.  Try this:
\begin{quote}
\verb!valgrind ls -l!
\end{quote}
You should get a summary which shows 0 leaks and 0 errors.
\end{enumerate}
\end{enumerate}

\subsection*{Using Valgrind}
As a first  application of Valgrind, do the following:
\begin{enumerate}
\item Get a copy of \verb!incorrect-readfile5.c! from the course
  website, found in the Homework~9 code examples.  Put it and a copy of your {\tt words} file in some
  convenient place. Compile (with the \verb!-g! debugging switch,
  saving the executable output in \verb!irf!)
 and run this program.  It should produce correct output,
  although we know that it has two places that cause memory leaks.

\item Use Valgrind to check the execution.  To use Valgrind, give the following commmand:
\begin{quote}
\verb!valgrind ./irf!
\end{quote}
For more informative output, use this command instead, carefully observing the results:
\begin{quote}
  \verb!valgrind --leak-check=full ./irf!
\end{quote}

\item Redirect the results of Valgrind to a file named
  \verb!valgrind-results!:
  \begin{quote}
    \verb!valgrind --leak-check=full ./irf 2> valgrind-results!
  \end{quote}
You will submit this file as evidence that you have
successfully installed and executed Valgrind.

\item Add Valgrind to your future workflow.  In addition to your own
  careful implementation and testing effort, you should now run all of
  your C programs with Valgrind to help detect any memory leaks.
\end{enumerate}

\newpage
\subsection*{Extending Past Work}
We want to remove some of the deficiencies of the ``poor man's sort''
program you recently implemented.  To do this, use the following
outline:
\begin{enumerate}
\item Download a copy of the source files for this assignment.  When
  you expand this archive, you will find a previous solution to the problem of
  reading lines from a text file --- organized in a more modular
  fashion.  Examine the contents of each file.

\item In addition to the modularization, there is now a {\tt Makefile}
  which streamlines the compilation process.  To build the program,
  use the following command:
\begin{quote}
\verb!make readfile!
\end{quote}
In response to this command, notice that \verb!gcc! is used first to
compile \verb!util.c! and \verb!readfile.c! and then again, but this
time it links the object files \verb!util.o! and \verb!readfile.o! to
create the executable file \verb!readfile!.

\item Run the compiled program to see if it behaves as you expect.
  After this, run it again with Valgrind to check for memory leaks.

\item We are using \verb!readfile.c! as a stepping stone to the poor
  man's sorting program.  Notice that \verb!readfile.c! does not store more
  than one line at a time.  That's fine for this application, but
  ultimately we want to be able to store all of the lines.  We have
  done this before, but the lines were stored in a fixed-size
  array. We can do better.

  To improve upon this, implement a function with the following
  prototype:
\begin{quote}
\verb!char **read_lines(FILE *fp);!
\end{quote}
The idea is that this function should read all lines in a
given file and store them in a NULL-terminated array of strings.  The
array should grow in an efficient way (by doubling) and upon return
should be adjusted to the correct size.  Put the prototype in
\verb!util.h!, put its implementation in \verb!util.c!, then modify
\verb!main()! so it uses this function.  

\item Implement three additional utility functions, with the following
  prototypes:
\begin{quote}
\begin{verbatim}
int count_lines(char *p[ ]);
void display_lines(char *p[ ]);
void display_lines_in_reverse(char *p[ ]);
\end{verbatim}
\end{quote}
The first of these returns the number of strings stored in a given
array; the other two display the strings on the standard output file
--- either from the first to last, or the other way around.  As
before, put the prototypes in \verb!util.h! file and the
implementations in \verb!util.c!.

\item To prove to yourself that these functions are working correctly,
  modify \verb!readfile.c! so it displays the contents of the file
  twice:  once in each direction.  (Of course, it now goes without saying that you will
  use Valgrind to test for memory leaks.)

\item When you have convinced yourself that \verb!read_lines()!
  function is working, you can move on to the poor man's sort
  revision.  Revise code as necessary in order to simplify the code,
  making use of the utility functions.  At this point in time,
  continue to use selection sort for the sorting process:  as before,
  it is the file I/O and string manipulation that is most important.
  Add a \verb!pmsort! target to the \verb!Makefile! to allow for
  compilation and linking to occur. Test your work.

\item If we are serious about systems programming, we need to realize
  that other people will be using our programs, so efficiency
  matters.  To get a sense of just how bad selection sort is for large
  files, let's time how long it takes to sort a file with
  approximately 200,000 lines.
 
To measure the time it takes your program, use the following command:
\begin{quote}
\verb!time ./pmsort words200K!
\end{quote}
Be prepared to wait!  I won't spoil the surprise and tell you how long
it takes, but this might be a good time to relax or think about the
next step.  When your program finishes, it is the ``user'' time
that is of most interest.  Record this time in a file named {\tt my-time1}.

\item You may recall from a course on data structures that there are
  many known sorting algorithms.  The C standard library includes a
  particularly efficient algorithm, \verb!qsort()!, an optimized
  version of the famous Quicksort algorithm.  Modify your sort program
  to make use of this function.  A discussion of \verb!qsort()! begins
  on page 440 of our textbook.  How much time does it take your
  revised sort program to process the system dictionary file?  Record
  the user time in a file named {\tt my-time2}. 
\end{enumerate} 

\subsection*{What to Submit}
When you have completed all the assigned work, put the following files
in a folder named {\tt hw10} and submit it in the usual way.  You
only need to submit the most up-to-date sorting program --- I don't
need to see the version which uses selection sort.

\begin{quote}
\begin{verbatim}
Makefile
util.h
util.c
readfile.c
pmsort.c
my-time1
my-time2
valgrind-results
\end{verbatim}
\end{quote}


\end{document}
