Assignment • FAQ • Development Guide • Code • Checklist •

HW3 Star Point

Stack Infrastructure

Your array-based stack will be dynamically allocated from the heap. It will have the following structure:

       ———————————————————————————————————————————————————————————
       | Stack Count | Stack Size | Stack Pointer |   |   | ...
       ———————————————————————————————————————————————————————————
index:      -3                 -2                    -1               0   1   ...

The Stack Count is the stack number. The first stack created will have number 1, the second stack created will have number 2, etc.

The Stack Size is the capacity of the stack. This is determined by the value stacksize passed into new_Stack when the stack is created.

The Stack Pointer holds the index of the next available space in the stack. For empty stacks this would be 0.

You should use this guide to complete the Star Point portion of HW1. Students will also have the opportunity to additionally complete these assignments using C or C++ (depending on the assignment). Students will be awarded a percentage of a star based on the percentage of test cases their solution passes. Each assignment will award up to 1 star, with 9 stars to be awarded throughout the quarter. These stars do not count for extra credit, however, they will be used to help borderline grades, and they will be considered with your future tutor applications. For HW3, the Star Point is in C.

Before starting this assignment, make sure you are comfortable with using the following gdb commands: break, run, next, step, cont, print. You can also use their respective abbrevitations, b, r, n, s, c, p.

For all functions, we recommend that you include code to display the corresponding catastrophic error and debug messages before writing any other code in each empty method body. Once those messages are in place, you'll be ready to add the expected functionality for each function. In this assignment, you should use fprintf to print these messages.

Before writing each function, refer to its Hints: section on the assignment page. Start your development process by folowing the getting started section at the bottom of the assignment page.

Write the function new_Stack in the file stack.c
Add code to get ready for the 'a' and 'd' cases in the large switch statement in driver.c. When the user enters an 'a' at the driver's prompt, the new_Stack function will be called which dynamically creates a Stack to use to test and verify, and when the user enters a 'd', that stack will be deallocated. You should focus on implementing the 'a' functionality now and wait until later to implement the 'd' functionality. Ensure that the return value of new_Stack is a Stack * that points to the address of the array element that will hold the first value the user wants to store in the Stack.

Once you've done the following, compile your program using make new:
1) Add debug and catastrophic messages to all methods,
2) Add "return;" or "return 0;" to all empty method bodies,
3) Update the text of the user prompt in driver.c to match expected wording,
4) Write the code for the new_Stack function to allocate and initialize a Stack container.
If you get any compiler errors or warnings, resolve those identified problems and compile again.

To check that your new_Stack function works correctly, run your program through the debugger to create a Stack that will hold 3 numbers:

$ gdb driver
To begin, set a breakpoint at the start of your new_Stack function and execute your program until just before your new_Stack function begins. Once the debugger stops, enter the next command continuously until just after the line containing the call to malloc executes. Remember that the line displayed by the debugger is the line about to execute:
(gdb) break new_Stack
(gdb) run

Please enter a command:
(a)llocate, (d)eallocate, p(u)sh, (p)op, (t)op, (i)sempty, (e)mpty,
is(f)ull, (n)um_elements, (w)rite to stdout, (W)rite to stderr.
Please enter choice: a

Please enter the number of objects to be able to store: 3

(gdb) next
Assuming that the variable for the void * that holds the return value from malloc is named memory, print the address stored in memory:
(gdb) p/x memory
$1 = 0x604010
Make note of the address displayed so you can use it later to verify another part of your program. Now step through your program line by line until you execute the line of code that initializes your this_Stack variable:
(gdb) next
(gdb) print this_Stack
$2 = 0x604028
As is listed here in this development guide, note the difference between the value stored in this_Stack and the value stored in memory is 24. These 24 bytes are for the 3 long values of stack infrastructure that belong before user data will be stored:
0x604028 - 0x604010 = 0x18 = decimal 24
You should ensure that the values you displayed for these two addresses also are 24 apart. If that is not true, update your code, compile, run and examine your code again until these two values are 24 apart.
(gdb) next
Enter next as many times until you go back into the driver.c code
(gdb) p/x main_Stack
$3 = 0x604028
You should ensure the address stored in main_Stack is the same value as you stored in this_Stack when you examined this value when stepping through your new_Stack function.
(gdb) quit
If these values are different, be sure you are calculating the Stack pointer correctly by offsetting by the stack offset. Also be sure to return this Stack pointer to main and set it equal to the correct variable.

After you have confirmed these values to be the same, run the driver executable with the debug flag on to verify to the debug message is displayed as you expect. You should get the following results:
$ ./driver -x

Please enter a command:
(a)llocate, (d)eallocate, p(u)sh, (p)op, (t)op, (i)sempty, (e)mpty,
is(f)ull, (n)um_elements, (w)rite to stdout, (W)rite to stderr.
Please enter choice: a

Please enter the number of objects to be able to store: 3
[Stack 1 has been allocated]

Please enter a command:
(a)llocate, (d)eallocate, p(u)sh, (p)op, (t)op, (i)sempty, (e)mpty,
is(f)ull, (n)um_elements, (w)rite to stdout, (W)rite to stderr.
Please enter choice:
Write the functions isempty_Stack and isfull_Stack. Make sure to include any corresponding catastrophic error messages. Compile, test and run in the debugger to verify that these functions work as expected. Then run with the -x option to see the debug messages display as expected.

Write the function push, which will allow you to add items to the stack. Return 1 (TRUE) for a successful push, and 0 (FALSE) otherwise. Be sure to include the debug statement and error messages.

To confirm that your push function works, run gdb. The following steps are to understand how the stack maintains elements and keeps track of the top of the stack. You should get the following results:

$ gdb driver
(gdb) break push
(gdb) run

Please enter a command:
(a)llocate, (d)eallocate, p(u)sh, (p)op, (t)op, (i)sempty, (e)mpty,
is(f)ull, (n)um_elements, (w)rite to stdout, (W)rite to stderr.
Please enter choice: a

Please enter the number of objects to be able to store: 3

Please enter a command:
(a)llocate, (d)eallocate, p(u)sh, (p)op, (t)op, (i)sempty, (e)mpty,
is(f)ull, (n)um_elements, (w)rite to stdout, (W)rite to stderr.
Please enter choice: u

Please enter a number to push to stack: 10

Now step through your program line by line until you execute the line of code that pushes 10 to the stack.
(gdb) next
(gdb) print this_Stack[0]
$1 = 10
(gdb) continue
Enter continue so that your program resumes execution until a breakpoint is hit again.

Please enter a command:
(a)llocate, (d)eallocate, p(u)sh, (p)op, (t)op, (i)sempty, (e)mpty,
is(f)ull, (n)um_elements, (w)rite to stdout, (W)rite to stderr.
Please enter choice: u

Please enter a number to push to stack: 20

Now step through your program line by line until you execute the line of code that pushes 20 to the stack:
(gdb) next
(gdb) print this_Stack[1]
$2 = 20
This shows which element is at the top of the stack currently. If you would have printed the element at index 0 it should show you value 10. Try to understand why this is the case.
(gdb) quit
If any of these values are incorrect, check to see if your stack pointer index has the correct value that you want.

Test the code with the debug flag as follows:
$ ./driver -x

Please enter a command:
(a)llocate, (d)eallocate, p(u)sh, (p)op, (t)op, (i)sempty, (e)mpty,
is(f)ull, (n)um_elements, (w)rite to stdout, (W)rite to stderr.
Please enter choice: a

Please enter the number of objects to be able to store: 3
[Stack 1 has been allocated]

Please enter a command:
(a)llocate, (d)eallocate, p(u)sh, (p)op, (t)op, (i)sempty, (e)mpty,
is(f)ull, (n)um_elements, (w)rite to stdout, (W)rite to stderr.
Please enter choice: i
Stack is empty.

Please enter a command:
(a)llocate, (d)eallocate, p(u)sh, (p)op, (t)op, (i)sempty, (e)mpty,
is(f)ull, (n)um_elements, (w)rite to stdout, (W)rite to stderr.
Please enter choice: u

Please enter a number to push to stack: 1
[Stack 1 - Pushing 1]

Please enter a command:
(a)llocate, (d)eallocate, p(u)sh, (p)op, (t)op, (i)sempty, (e)mpty,
is(f)ull, (n)um_elements, (w)rite to stdout, (W)rite to stderr.
Please enter choice: u

Please enter a number to push to stack: 2
[Stack 1 - Pushing 2]

Please enter a command:
(a)llocate, (d)eallocate, p(u)sh, (p)op, (t)op, (i)sempty, (e)mpty,
is(f)ull, (n)um_elements, (w)rite to stdout, (W)rite to stderr.
Please enter choice: u

Please enter a number to push to stack: 3
[Stack 1 - Pushing 3]

Please enter a command:
(a)llocate, (d)eallocate, p(u)sh, (p)op, (t)op, (i)sempty, (e)mpty,
is(f)ull, (n)um_elements, (w)rite to stdout, (W)rite to stderr.
Please enter choice: u

Please enter a number to push to stack: 4
Pushing to a full stack!!!

WARNING: push FAILED
Write the function get_occupancy. Make sure to include a validity check and the catastrophic error messages, if needed. Test the get_occupancy function as follows:
$ ./driver -x

Please enter a command:
(a)llocate, (d)eallocate, p(u)sh, (p)op, (t)op, (i)sempty, (e)mpty,
is(f)ull, (n)um_elements, (w)rite to stdout, (W)rite to stderr.
Please enter choice: a

Please enter the number of objects to be able to store: 3
[Stack 1 has been allocated]

Please enter a command:
(a)llocate, (d)eallocate, p(u)sh, (p)op, (t)op, (i)sempty, (e)mpty,
is(f)ull, (n)um_elements, (w)rite to stdout, (W)rite to stderr.
Please enter choice: n
Number of elements on the stack is: 0

Please enter a command:
(a)llocate, (d)eallocate, p(u)sh, (p)op, (t)op, (i)sempty, (e)mpty,
is(f)ull, (n)um_elements, (w)rite to stdout, (W)rite to stderr.
Please enter choice: u

Please enter a number to push to stack: 3
[Stack 1 - Pushing 3]

Please enter a command:
(a)llocate, (d)eallocate, p(u)sh, (p)op, (t)op, (i)sempty, (e)mpty,
is(f)ull, (n)um_elements, (w)rite to stdout, (W)rite to stderr.
Please enter choice: n
Number of elements on the stack is: 1

Please enter a command:
(a)llocate, (d)eallocate, p(u)sh, (p)op, (t)op, (i)sempty, (e)mpty,
is(f)ull, (n)um_elements, (w)rite to stdout, (W)rite to stderr.
Please enter choice: u

Please enter a number to push to stack: 4
[Stack 1 - Pushing 4]

Please enter a command:
(a)llocate, (d)eallocate, p(u)sh, (p)op, (t)op, (i)sempty, (e)mpty,
is(f)ull, (n)um_elements, (w)rite to stdout, (W)rite to stderr.
Please enter choice: n
Number of elements on the stack is: 2

Please enter a command:
(a)llocate, (d)eallocate, p(u)sh, (p)op, (t)op, (i)sempty, (e)mpty,
is(f)ull, (n)um_elements, (w)rite to stdout, (W)rite to stderr.
Please enter choice: u

Please enter a number to push to stack: 5
[Stack 1 - Pushing 5]

Please enter a command:
(a)llocate, (d)eallocate, p(u)sh, (p)op, (t)op, (i)sempty, (e)mpty,
is(f)ull, (n)um_elements, (w)rite to stdout, (W)rite to stderr.
Please enter choice: n
Number of elements on the stack is: 3
Write the empty_Stack function. Add code to handle the 'e' case in the large switch statement in driver.c. When the user chooses 'e' the stack should be emptied.

Test with gdb as follows. Here you will be checking how the values in the stack change when you delete all elements that you previously entered in the stack using the empty command.
$ gdb driver
(gdb) break empty_Stack
This will ensure gdb stops at the beginning of the empty_Stack function

Please enter a command:
(a)llocate, (d)eallocate, p(u)sh, (p)op, (t)op, (i)sempty, (e)mpty,
is(f)ull, (n)um_elements, (w)rite to stdout, (W)rite to stderr.
Please enter choice: a

Please enter the number of objects to be able to store: 3

Please enter a command:
(a)llocate, (d)eallocate, p(u)sh, (p)op, (t)op, (i)sempty, (e)mpty,
is(f)ull, (n)um_elements, (w)rite to stdout, (W)rite to stderr.
Please enter choice: u

Please enter a number to push to stack: 10

Please enter a command:
(a)llocate, (d)eallocate, p(u)sh, (p)op, (t)op, (i)sempty, (e)mpty,
is(f)ull, (n)um_elements, (w)rite to stdout, (W)rite to stderr.
Please enter choice: u

Please enter a number to push to stack: 20

Now you should have two elements in the stack and the next step is to test program by running empty command

Please enter a command:
(a)llocate, (d)eallocate, p(u)sh, (p)op, (t)op, (i)sempty, (e)mpty,
is(f)ull, (n)um_elements, (w)rite to stdout, (W)rite to stderr.
Please enter choice: e

(gdb) print this_Stack[-1]
$1 = 2
This is correct since you have pushed two elements into your stack
(gdb) next
Enter next until you reach the end of your empty_Stack function
(gdb) print this_Stack[-1]
$2 = 0
This also makes sense since now you have an empty stack with 0 elements in it (we initialize your empty stack to 0)
(gdb) quit

If your second print does not equal 0, you did not successfully empty the stack. Make sure you are resetting your stack pointer index correctly.

Now you can test with the debug flag as follows:

$ ./driver -x

Please enter a command:
(a)llocate, (d)eallocate, p(u)sh, (p)op, (t)op, (i)sempty, (e)mpty,
is(f)ull, (n)um_elements, (w)rite to stdout, (W)rite to stderr.
Please enter choice: a

Please enter the number of objects to be able to store: 5
[Stack 1 has been allocated]

Please enter a command:
(a)llocate, (d)eallocate, p(u)sh, (p)op, (t)op, (i)sempty, (e)mpty,
is(f)ull, (n)um_elements, (w)rite to stdout, (W)rite to stderr.
Please enter choice: u

Please enter a number to push to stack: 1
[Stack 1 - Pushing 1]

Please enter a command:
(a)llocate, (d)eallocate, p(u)sh, (p)op, (t)op, (i)sempty, (e)mpty,
is(f)ull, (n)um_elements, (w)rite to stdout, (W)rite to stderr.
Please enter choice: u

Please enter a number to push to stack: 2
[Stack 1 - Pushing 2]

Please enter a command:
(a)llocate, (d)eallocate, p(u)sh, (p)op, (t)op, (i)sempty, (e)mpty,
is(f)ull, (n)um_elements, (w)rite to stdout, (W)rite to stderr.
Please enter choice: u

Please enter a number to push to stack: 3
[Stack 1 - Pushing 3]

Please enter a command:
(a)llocate, (d)eallocate, p(u)sh, (p)op, (t)op, (i)sempty, (e)mpty,
is(f)ull, (n)um_elements, (w)rite to stdout, (W)rite to stderr.
Please enter choice: u

Please enter a number to push to stack: 4
[Stack 1 - Pushing 4]

Please enter a command:
(a)llocate, (d)eallocate, p(u)sh, (p)op, (t)op, (i)sempty, (e)mpty,
is(f)ull, (n)um_elements, (w)rite to stdout, (W)rite to stderr.
Please enter choice: w

The Stack contains:
1 2 3 4
Please enter a command:
(a)llocate, (d)eallocate, p(u)sh, (p)op, (t)op, (i)sempty, (e)mpty,
is(f)ull, (n)um_elements, (w)rite to stdout, (W)rite to stderr.
Please enter choice: e
Stack is empty.

Please enter a command:
(a)llocate, (d)eallocate, p(u)sh, (p)op, (t)op, (i)sempty, (e)mpty,
is(f)ull, (n)um_elements, (w)rite to stdout, (W)rite to stderr.
Please enter choice: n
Number of elements on the stack is: 0

Please enter a command:
(a)llocate, (d)eallocate, p(u)sh, (p)op, (t)op, (i)sempty, (e)mpty,
is(f)ull, (n)um_elements, (w)rite to stdout, (W)rite to stderr.
Please enter choice: w

The Stack contains:

Write the functions pop and top. These functions should be similar, except that pop removes an item, while top does not. Be sure to add debug statements and error messages for these functions.

Now try running gdb on your own by breaking in your pop and top functions. Check to see that pop is changing the stack pointer index and that top is not. Print the stack values at these indices to see if they point to the correct values. If you are having trouble with the commands, refer to the gdb commands listed in the previous steps! You should be checking for the values at top and how the variables of the stack change when you do top or pop and how they should differ from each other.

After confirming this has the correct functionality, test as follows with the debug flag:
$ ./driver -x

Please enter a command:
(a)llocate, (d)eallocate, p(u)sh, (p)op, (t)op, (i)sempty, (e)mpty,
is(f)ull, (n)um_elements, (w)rite to stdout, (W)rite to stderr.
Please enter choice: a

Please enter the number of objects to be able to store: 5
[Stack 1 has been allocated]

Please enter a command:
(a)llocate, (d)eallocate, p(u)sh, (p)op, (t)op, (i)sempty, (e)mpty,
is(f)ull, (n)um_elements, (w)rite to stdout, (W)rite to stderr.
Please enter choice: u

Please enter a number to push to stack: 1
[Stack 1 - Pushing 1]

Please enter a command:
(a)llocate, (d)eallocate, p(u)sh, (p)op, (t)op, (i)sempty, (e)mpty,
is(f)ull, (n)um_elements, (w)rite to stdout, (W)rite to stderr.
Please enter choice: u

Please enter a number to push to stack: 2
[Stack 1 - Pushing 2]

Please enter a command:
(a)llocate, (d)eallocate, p(u)sh, (p)op, (t)op, (i)sempty, (e)mpty,
is(f)ull, (n)um_elements, (w)rite to stdout, (W)rite to stderr.
Please enter choice: u

Please enter a number to push to stack: 3
[Stack 1 - Pushing 3]

Please enter a command:
(a)llocate, (d)eallocate, p(u)sh, (p)op, (t)op, (i)sempty, (e)mpty,
is(f)ull, (n)um_elements, (w)rite to stdout, (W)rite to stderr.
Please enter choice: w

The Stack contains:
1 2 3
Please enter a command:
(a)llocate, (d)eallocate, p(u)sh, (p)op, (t)op, (i)sempty, (e)mpty,
is(f)ull, (n)um_elements, (w)rite to stdout, (W)rite to stderr.
Please enter choice: t
[Stack 1 - Topping 3]
Number at top of the stack is: 3

Please enter a command:
(a)llocate, (d)eallocate, p(u)sh, (p)op, (t)op, (i)sempty, (e)mpty,
is(f)ull, (n)um_elements, (w)rite to stdout, (W)rite to stderr.
Please enter choice: p
[Stack 1 - Popping 3]
Number popped from the stack is: 3

Please enter a command:
(a)llocate, (d)eallocate, p(u)sh, (p)op, (t)op, (i)sempty, (e)mpty,
is(f)ull, (n)um_elements, (w)rite to stdout, (W)rite to stderr.
Please enter choice: t
[Stack 1 - Topping 2]
Number at top of the stack is: 2

Please enter a command:
(a)llocate, (d)eallocate, p(u)sh, (p)op, (t)op, (i)sempty, (e)mpty,
is(f)ull, (n)um_elements, (w)rite to stdout, (W)rite to stderr.
Please enter choice: p
[Stack 1 - Popping 2]
Number popped from the stack is: 2

Please enter a command:
(a)llocate, (d)eallocate, p(u)sh, (p)op, (t)op, (i)sempty, (e)mpty,
is(f)ull, (n)um_elements, (w)rite to stdout, (W)rite to stderr.
Please enter choice: t
[Stack 1 - Topping 1]
Number at top of the stack is: 1

Please enter a command:
(a)llocate, (d)eallocate, p(u)sh, (p)op, (t)op, (i)sempty, (e)mpty,
is(f)ull, (n)um_elements, (w)rite to stdout, (W)rite to stderr.
Please enter choice: p
[Stack 1 - Popping 1]
Number popped from the stack is: 1

Please enter a command:
(a)llocate, (d)eallocate, p(u)sh, (p)op, (t)op, (i)sempty, (e)mpty,
is(f)ull, (n)um_elements, (w)rite to stdout, (W)rite to stderr.
Please enter choice: t
Topping from an empty stack!!!

WARNING: top FAILED

Please enter a command:
(a)llocate, (d)eallocate, p(u)sh, (p)op, (t)op, (i)sempty, (e)mpty,
is(f)ull, (n)um_elements, (w)rite to stdout, (W)rite to stderr.
Please enter choice: p
Popping from an empty stack!!!

WARNING: pop FAILED
Write the function delete_Stack and add a 'd' case to the large switch statement in main. Return TRUE for a successfull deallocation, FALSE otherwise. Be sure to add debug messages and error messages to delete_Stack. As part of testing this code, answer the questions below and include the answers in a comment block at the top of the driver.c file.

1. Set a breakpoint in new_Stack. What is the address returned by malloc()?
2. What is the address returned by new_Stack?
3. Is this address on the stack, heap, text, or data?
4. Now set a breakpoint in delete_Stack. What is the value of spp? Is
this value on the stack, heap, text, or data?
5. What is the value of *spp? Is this an address on the stack, heap, text
or data?
6. What is the value of the parameter being passed to free()?
7. Is this parameter to free the same address that was returned from malloc
(Your answer to question 1)? If it isn't, then the address you are passing
is incorrect, and you should modify your code to fix this problem.
To partially confirm the correctness of your solution, let's run your program with gdb again. We will run a simple test on push and pop. We want to make sure that the Stack Pointer is being updated correctly. Remember that the Stack Pointer holds the index of the next available space in the stack.
$ gdb ./driver
(gdb) break stack.c:push
(gdb) break stack.c:pop
(gdb) run
Please enter a command:
(a)llocate, (d)eallocate, p(u)sh, (p)op, (t)op, (i)sempty, (e)mpty,
is(f)ull, (n)um_elements, (w)rite to stdout, (W)rite to stderr.
Please enter choice: a

Please enter the number of objects to be able to store: 5

Please enter a command:
(a)llocate, (d)eallocate, p(u)sh, (p)op, (t)op, (i)sempty, (e)mpty,
is(f)ull, (n)um_elements, (w)rite to stdout, (W)rite to stderr.
Please enter choice: u

Please enter a number to push to stack: 10

(gdb) print this_Stack[-1]
$1 = 0

Notice that you used -1 instead of STACK_POINTER_INDEX, since in gdb you don't have access to constants defined with #define

(gdb) next
Execute as many times as needed until you reach the return statement
(gdb) print this_Stack[-1]
$2 = 1
(gdb) continue
Continuing.

Please enter a command:
(a)llocate, (d)eallocate, p(u)sh, (p)op, (t)op, (i)sempty, (e)mpty,
is(f)ull, (n)um_elements, (w)rite to stdout, (W)rite to stderr.
Please enter choice: p

(gdb) print this_Stack[-1]
$3 = 1
(gdb) next
Execute as many times as needed until you reach the return statement
(gdb) print this_Stack[-1]
$4 = 0
(gdb) continue

OVERLOOK REMAINING OUTPUT
Make sure that you extensively test your program!

To further test this code, you should use valgrind. This will tell you if you are deallocating all the memory you are supposed to. To run your program with valgrind, type make valgrind instead of make into the command prompt. To test with -x, type make valgrind DEBUG=-x. Test as follows:

$ make valgrind DEBUG=-x
valgrind --leak-check=full --read-var-info=yes \
--show-reachable=yes ./driver -x
==22521== Memcheck, a memory error detector
==22521== Copyright (C) 2002-2012, and GNU GPL'd, by Julian Seward et al.
==22521== Using Valgrind-3.8.1 and LibVEX; rerun with -h for copyright info
==22521== Command: ./driver -x
==22521==

Please enter a command:
(a)llocate, (d)eallocate, p(u)sh, (p)op, (t)op, (i)sempty, (e)mpty,
is(f)ull, (n)um_elements, (w)rite to stdout, (W)rite to stderr.
Please enter choice: a

Please enter the number of objects to be able to store: 3
[Stack 1 has been allocated]

Please enter a command:
(a)llocate, (d)eallocate, p(u)sh, (p)op, (t)op, (i)sempty, (e)mpty,
is(f)ull, (n)um_elements, (w)rite to stdout, (W)rite to stderr.
Please enter choice: a

Please enter the number of objects to be able to store: 4
[Stack 1 has been deallocated]
[Stack 1 has been allocated]

Please enter a command:
(a)llocate, (d)eallocate, p(u)sh, (p)op, (t)op, (i)sempty, (e)mpty,
is(f)ull, (n)um_elements, (w)rite to stdout, (W)rite to stderr.
Please enter choice: d
[Stack 1 has been deallocated]
Stack has been deleted.

Please enter a command:
(a)llocate, (d)eallocate, p(u)sh, (p)op, (t)op, (i)sempty, (e)mpty,
is(f)ull, (n)um_elements, (w)rite to stdout, (W)rite to stderr.
Please enter choice: ^D
==22521==
==22521== HEAP SUMMARY:
==22521== in use at exit: 0 bytes in 0 blocks
==22521== total heap usage: 2 allocs, 2 frees, 104 bytes allocated
==22521==
==22521== All heap blocks were freed -- no leaks are possible
==22521==
==22521== For counts of detected and suppressed errors, rerun with: -v
==22521== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 12 from 8)

The valgrind output should report no errors or leaked memory.

At this point, you should test your assignment extensively by coming up with your own test cases. Be sure to test it with and without the "-x" option. To verify that your program behaves correctly, check the output against the solution's output. To run the solution program, type

$ ~/../public/hw3/driver [-x]

Make sure that you have fully commented your program and added function and file headers. Make sure your style follows the Style Outline for CSE 12. Then turn in your program by following The Turnin Procedure.

Note that, for your homework to be collected correctly, you must name your files stack.c and driver.c and the files must be located in a folder called hw3 in your home directory.

stack.h

#ifndef STACK_H
#define STACK_H

/* DO NOT CHANGE:  This file is used in evaluation */

#include <stdio.h>

/* This array implementation of stack is an array of longs (words), the
stack count is the first element in the array,the stack size is the second
element in the array, and the stack pointer is the third element in the
array.  The stack pointer has the value of an index into the array to denote
the next available space in the stack. */

typedef long Stack;

long delete_Stack (Stack **);   /* deallocates memory allocated in new_Stack.
                                   Assigns incoming pointer to NULL. */
void empty_Stack (Stack *);     /* empties the stack */
long isempty_Stack (Stack *);   /* returns 0 or non-0 value indicating
                                   whether or not the stack is empty */
long isfull_Stack (Stack *);    /* returns 0 or non-0 value indicating
                                   whether or not the stack is full */
Stack * new_Stack (unsigned long); /* allocates stack array, and initializes
                                   stack pointer.  Result is a pointer in the
                                   array where user data allotment begins */
long get_occupancy (Stack *);     /* returns the number of elements stored
                                   on the stack. */
long pop (Stack *, long *);     /* removes and sends back the top element of
                                   the stack.  Result is 0 or non-0,
                                   indicating failure or success,
                                   respectively */
long push (Stack *, long);      /* places one value on the specified stack.
                                   Result is 0 or non-0 indicating failure
                                   or success, respectively */
long top (Stack *, long *);     /* sends back the top element of the stack.
                                   Stack is left unaffected. Result is 0
                                   or non-0 indicating failure or success,
                                   respectively. */
FILE * write_Stack (Stack *, FILE *); /* prints out the contents of the stack
                                   to the parameter specified FILE */

void debug_on (void);     /* turns stack debugging on */
void debug_off (void);    /* turns stack debugging off */

#endif

stack.c.empty

#include <malloc.h>
#include <stdio.h>
#include "mylib.h"
#include "stack.h"

#define STACK_POINTER_INDEX (-1)        /* Index of next available space */
#define STACK_SIZE_INDEX (-2)           /* Index of size of the stack */
#define STACK_COUNT_INDEX (-3)          /* Index of which stack allocated */
#define STACK_OFFSET 3  /* offset from allocation to where user info begins */

/* catastrophic error messages */
static const char DELETE_NONEXIST[] = "Deleting a non-existent stack!!!\n";
static const char EMPTY_NONEXIST[] = "Emptying a non-existent stack!!!\n";
static const char INCOMING_NONEXIST[] = 
                        "Incoming parameter does not exist!!!\n";
static const char ISEMPTY_NONEXIST[] = 
                        "Isempty check from a non-existent stack!!!\n";
static const char ISFULL_NONEXIST[] = 
                        "Isfull check from a non-existent stack!!!\n";
static const char NUM_NONEXIST[] = 
                        "get_occupancy check from a non-existent stack!!!\n";
static const char POP_NONEXIST[] = "Popping from a non-existent stack!!!\n";
static const char POP_EMPTY[] = "Popping from an empty stack!!!\n"; 
static const char PUSH_NONEXIST[] = "Pushing to a non-existent stack!!!\n";
static const char PUSH_FULL[] = "Pushing to a full stack!!!\n";
static const char TOP_NONEXIST[] = "Topping from a non-existent stack!!!\n";
static const char TOP_EMPTY[] = "Topping from an empty stack!!!\n";
static const char WRITE_NONEXIST_FILE[] = 
                        "Attempt to write using non-existent file pointer!!!\n";
static const char WRITE_NONEXIST_STACK[] = 
                        "Attempt to write to a non-existent stack!!!\n";

/* Debug messages */
static const char ALLOCATED[] = "[Stack %ld has been allocated]\n";
static const char DEALLOCATE[] = "[Stack %ld has been deallocated]\n";
static const char HEXPOP[] = "[Stack %ld - Popping 0x%lx]\n";
static const char HEXPUSH[] = "[Stack %ld - Pushing 0x%lx]\n";
static const char HEXTOP[] = "[Stack %ld - Topping 0x%lx]\n";
static const char POP[] = "[Stack %ld - Popping %ld]\n";
static const char PUSH[] = "[Stack %ld - Pushing %ld]\n";
static const char TOP[] = "[Stack %ld - Topping %ld]\n";

/* static variable allocation */
static int debug = FALSE; /* allocation of debug flag */
static int stack_counter = 0; /* number of stacks allocated so far */

/* Debug state methods */
void debug_off (void) {
        debug = FALSE;
}

void debug_on (void) {
        debug = TRUE;
}

/* start of true stack code */
long delete_Stack (Stack ** spp) {
    /* YOUR CODE GOES HERE */
}

void empty_Stack (Stack * this_Stack) {
    /* YOUR CODE GOES HERE */
}
        
long isempty_Stack (Stack * this_Stack) {
    /* YOUR CODE GOES HERE */
}

long isfull_Stack (Stack * this_Stack) {
    /* YOUR CODE GOES HERE */
}

Stack * new_Stack (unsigned long stacksize) {
    /* YOUR CODE GOES HERE */
}

long get_occupancy (Stack * this_Stack) {
    /* YOUR CODE GOES HERE */
}

long pop (Stack * this_Stack, long * item) {
    /* YOUR CODE GOES HERE */
}

long push (Stack * this_Stack, long item) {
    /* YOUR CODE GOES HERE */
}

long top (Stack * this_Stack, long * item) {
    /* YOUR CODE GOES HERE */
}

FILE * write_Stack (Stack * this_Stack, FILE * stream) {

        long index = 0;         /* index into the stack */

        if (this_Stack == NULL) {
                fprintf (stderr, WRITE_NONEXIST_STACK);
                return stream;
        }

        if (stream == NULL) {
                fprintf (stderr, WRITE_NONEXIST_FILE);
                return stream;
        }
                
        if (stream == stderr)
                fprintf (stream, "Stack has %ld items in it.\n",
                        get_occupancy (this_Stack));

        for (index = STACK_COUNT_INDEX + STACK_OFFSET;
                index < get_occupancy (this_Stack); index++) {

                if (stream == stderr)
                        fprintf (stream, "Value on stack is |0x%lx|\n",
                                this_Stack[index]);
                else {
                        if (this_Stack[index] < 0)
                                fprintf (stream, "%c ",
                                        (char) this_Stack[index]);
                        else
                                fprintf (stream, "%ld ", this_Stack[index]);
                }
        }

        return stream;
}

driver.c.empty

#include <stdio.h>
#include <stdlib.h>
#include "mylib.h"
#include "stack.h"

int main (int argc, char * const * argv) {

        Stack * main_Stack = 0;         /* the test stack */
        unsigned long amount;        /* numbers of items possible go on stack */
        long command;                   /* stack command entered by user */
        long item = 0;                  /* item to go on stack */
        char option;                    /* the command line option */
        long status;                    /* return status of stack functions */
        
        /* initialize debug states */
        debug_off ();

        /* check command line options for debug display */
        while ((option = getopt (argc, argv, "x")) != EOF) {
                
                switch (option) {
                        case 'x': debug_on (); break;
                }
        }

        while (1) {
                command = 0;            /* initialize command, need for loops */
                writeline ("\nPlease enter a command:", stdout);
                writeline ("\n\t(a)llocate, (d)eallocate, ", stdout);
                writeline ("p(u)sh, (p)op, (t)op, (i)sempty, (e)mpty, ",stdout);
                writeline ("\n\tis(f)ull, (n)um_elements, (w)rite to stdout, "
                                                                , stdout);
                writeline ("(W)rite to stderr.\n", stdout);
                writeline ("Please enter choice:  ", stdout);
                command = getchar ();
                if (command == EOF)     /* are we done? */
                        break;
                clrbuf (command);       /* get rid of extra characters */

                switch (command) {      /* process commands */

                /* YOUR CODE GOES HERE */

                case 'f':               /* isfull */
                        if (isfull_Stack (main_Stack))
                                writeline ("Stack is full.\n",stdout);
                        else
                                writeline ("Stack is not full.\n", stdout);
                        break;

                case 'i':               /* isempty */
                        if (isempty_Stack (main_Stack))
                                writeline ("Stack is empty.\n", stdout);
                        else
                                writeline ("Stack is not empty.\n", stdout);
                        break;

                case 'n':               /* get_occupancy */
                        writeline ("Number of elements on the stack is:  ",
                                                                    stdout);
                        decout (get_occupancy (main_Stack));
                        newline (stdout);
                        break;

                case 'p':               /* pop */
                        status = pop (main_Stack, &item);
                        if (! status)
                                fprintf (stderr,"\nWARNING:  pop FAILED\n");
                        else {
                                writeline (
                                        "Number popped from the stack is:  ",
                                                                    stdout);
                                decout (item);
                                newline (stdout);
                        }
                        break;

                case 't':               /* top */
                        status = top (main_Stack, &item);
                        if (! status)
                                fprintf (stderr,"\nWARNING:  top FAILED\n");
                        else {
                                writeline (
                                        "Number at top of the stack is:  ",
                                                                    stdout);
                                decout (item);
                                newline (stdout);
                        }
                        break;

                case 'u':               /* push */
                        writeline (
                                "\nPlease enter a number to push to stack:  ",
                                                                    stdout);
                        item = decin ();
                        clrbuf (0);     /* get rid of extra characters */
                        status = push (main_Stack, item);
                        if (! status)
                                fprintf(stderr,"\nWARNING:  push FAILED\n");
                        break;

                case 'w':               /* write */
                        writeline ("\nThe Stack contains:\n", stdout);
                        write_Stack (main_Stack, stdout);
                        break;

                case 'W':               /* write */
                        writeline ("\nThe Stack contains:\n", stdout);
                        write_Stack (main_Stack, stderr);
                        break;
                }

                if (item == EOF) /* check if done */
                        break;
        }

        if (main_Stack)
                delete_Stack (&main_Stack);     /* deallocate stack */
        newline (stdout);
        return 0;
}

Assignment • FAQ • Development Guide • Code • Checklist