Project: Stack Variations

This project will give you practice with stacks and with the difference between accessing the field of a variable passed to a function as a pointer to a struct vs. as a copy of a struct.

Preparation

Copy the source files to your own working directory, perhaps as follows. These commands will copy the stacks directory from johnsonba to your account, copying all of the files within the directory to a new directory..
cd ~/csc161/projects
cp -i -R  /home/johnsonba/public_html/CSC161/2019F/modules/pointers-stacks-queues/src/stacks ./

Part A: Code Analysis

Examine each of the four implementation approaches in the accompanying reading. For each approach, identify:

In each case, briefly justify your conclusions based on the code. You are encouraged to draw diagrams for each approach.

For this part, you do not need to compile or run the code. Simply read through the code given in the reading for each of the 4 approaches. Note that these approaches may give different results and even give results that might be considered errors. This is by design. Explain what would happen and why.

Part B: Experimentation

You will compile 4 programs with one command: make project. This will produce four executable programs, each corresponding to one of the 4 stack implementation approaches.

The program stack-project.c creates a single stack myStack and then uses the standard stack operations in the following sequence:

Review the output obtained with each of the four stack implementation approaches. Explain the results obtained (e.g., what variables remain the same, what changes and how/why). Write down this explanation as part B of the material you will hand in for grading.

Part C: Functional Stacks

The reading on stacks compared two stack interfaces: one that relies entirely on pointers and one that does not. You will explore the implications of this distinction in this part of the project. You will create a new stack handling program in step 1. Then, you will run performance comparisons and analyze the results in Steps 2 and 3.

  1. First we must adapt one of the stack implementations so that it does not pass a pointer when the stack will not be changed by the function. To do so, we will construct an entirely new and complete stack interface and implementation as follows. In all your work, be sure to carefully document the authors of the source code.
    • Copy stack.h to a file called stack-func.h and change the declarations of all functions except initialize, push and pop to take simply a struct string_stack as a parameter, rather than a pointer to a struct string_stack.
    • Copy the declarations and definition from stack-buffer.h (do not include the include guard) to your stack-func.h header.
    • Copy stack.c to a file called stack-func.c and change the implementations of the functions there to reflect the declarations from stack.h. Note: you will need to change the function header declarations and modify how the fields of the stack are accessed within the function.
    • Copy the implementations of push, pop, top, and get from stack-2.c to your stack-func.c file and update the implementations to match the declarations of your stack-func.h header.
    • Add an entry to the Makefile to compile the object file stack-func.o. (Note that it is not yet linked into an executable. If you need a refresher on Makefiles, refer back to the Program Management reading.)
  2. Next we will want to examine quantitatively the performance ramifications of these changes to the interface. You will be first running the original pointer-based code and then the modified version.
    • Copy program stack-project-compare.c. Inspect, compile (see the Makefile), and run the program to be sure you understand what it does.
    • The small stacks and strings are not likely to yield any insights. Change MAX_STACK_SIZE to 1024 and MAX_STRING_LENGTH to 1024 by providing these definitions during compilation:
      make clean
      make stack-project-compare CPPFLAGS="-DMAX_STRING_LENGTH=256 -DMAX_STACK_SIZE=1024"
    • Use the Bash shell's time command to determine how long it takes to run the program with the original interface. For example,
      time ./stack-project-compare
      real    0m0.036s
      user    0m0.018s
      sys     0m0.015s
      To dissipate disk or network effects, you will likely want to run the command a few times until the numbers are approximately consistent. Record the user time, which indicates the amount of time the operating system spent running your code or library code (e.g., strcpy), rather than waiting for other programs or running priviledged instructions.
    • Now copy stack-project-compare.c to stack-project-compare-func.c and modify it to include your stack-func.h file and update the necessary stack function calls to use the alternative interface, rather than pointers. (Note: I had to add assert.h and string.h to the #include preprocessor directives and remove references to stack.h and stack-buffer.h while cleaning up files before compiling. You will get some warnings about size_t vs. int types, but so long as they are warnings and not errors, you should be fine. )
    • The Makefile should have a new target (stack-project-compare-func) near the bottom of the file that compiles stack-project-compare-func.c and links it with stack-func.o. (Make sure you clean the old object files first and then rebuild with the larger string length and stack size definitions!)
    • Compile the program and time how long it takes to run the program with the functional interface. To dissipate disk or network effects, you will likely want to run the command a few times until the numbers are approximately consistent. Make a note of the new user time.
    • To help you gain some perspective, add the following lines to the end of main in stack-project-compare-func.c
        /* compare argument sizes */
        printf("Stack argument size:         %ld\n", sizeof(*pStack));
        printf("Stack pointer argument size: %ld\n", sizeof(struct stack *));
  3. What differences in performance do you notice between the original pointer-based and your updated, more functional stack interface? In particular, what is the ratio of the user times? Explain the likely cause of these differences.

Grading

Files to Submit

You should submit the following files both printed and emailed to the grader account:

In particular, no separate testing beyond C.1 and C.2 is necessary.

Rubric

The project is worth 20 points.