stack.h is the header file. It declares the functions that will be defined in stack.c, the implementation file. Those functions will be used in test_stack.c, the test file. It also includes the struct type definitions for Stack and BlockNode, and a constant MIN_NODE_BLOCK_SIZE_BYTES.

You also have two more files, stack_utils.c and stack_utils.h. Those are used only in the test file (test_stack.c), to make testing easier. Do not use them in stack.c or stack.h.

Test-driven development

You will use a very simplified adaptation of test-driven development (TDD), a popular software engineering process. We have provided you with several pre-written tests to start with, but the overall flow should be the same.

1. Start with a test.
2. Write just enough code to pass that test—without trying to solve anything else.
3. Run your test(s).
4. If the test failed, fix your code until your test(s) pass(es).
5. Repeat, adding one new test each time. At every stage, run all of your tests to make sure you have not broken functionality that worked previously.

Always start with a very easy test case. Get it working perfectly, tested, and submitted before you move on to another test case. Do not start by trying to solve the most interesting part of the assignment.

Your code should never be in a "broken" state for more than about 10-15 minutes. That way, if something is broken, it is very likely due to something you changed in the last 10-15 minutes. It makes it easier to find. Also, you will always be working from a position of strength. With each piece you build, you will be starting from something that works.

If you get stuck and are looking at a mess of code that doesn't work that you've been hacking on for over an hour, our advice will often be to go back to the last time it did work. If you have not been following TDD, then that means starting over from the beginning.

Here's another way to look at it. If you somehow lost your mind and do not finish the rest, you should have something that will likely get at least some credit. With each test you add and get working, you will have more of the ultimate functionality working. That tends to yield more partial credit. (Of course, 100% credit should always be your target, and it is definitely attainable by anyone in this class.)

Normally, you would use a unit-test framework to structure your tests. For simplicity, we will rely on assert(…). You will notice that whenver an assert(…) fails (i.e., condition is false), your executable prints the line number of the assert(…) that failed, and the text of the condition that failed. (Note: If you ever see (void*)0), it is referring to NULL.)

Requirement: incremental submissions

You are required to submit at least 6 times, at least 10 minutes apart with significant differences in the code—and the amount of working functionality—between these submissions. You are strongly encouraged to submit more often than that. But if we check all of your submissions, assuming we are testing thoroughly, we should get at least 6 different scores. (The number of unique scores is not an explicit requirement. As long as you make a good faith effort to do incremental submissions, as you go, we will make sure you get the credit.)

This is to help you. We know that many students have an ingrained habit of focusing on the interesting part of an assignment first. We also know that trying to finish everything in one chunk leads to bad things (e.g., difficult bugs, code spaghetti, all-nighters, low scores, etc.). The further you go as a programmer, the bigger the projects will be. Trying to finish big chunks all at once becomes increasingly difficult and prone to risk. We are trying to guide you.

In addition, we hope that this requirement gives a bit of resistance to inappropriate uses of GenAI (i.e., ChatGPT, etc.) so that at the end of the semester. Those tools are designed to make fully working code. We want to always know for sure that people who do well in Purdue ECE programming courses are good programmers.

Compile

To compile:

Writing the code

Follow the test-driven development process described above. We have made this easy for you by giving you a set of starter test cases (test_stack.c), as well as some utilities to help with testing (stack_utils.c and stack_utils.h).

1. Get test_minimum_block_size_empty_stack() working. You will need to implement a little bit of create_empty_stack(…). At this point, your create_empty_stack(…) need only work for empty stack. For .num_values_per_node, just use 1. You can figure out the calculation of .num_values_per_node later.
2. Submit.
3. Get test_minimum_block_size_1_value() working. This should require no changes to create_empty_stack(…). At this point, it only needs to work for stacks with one value, where each BlockNode can hold at most one value. This will require implementing push(…) and one call to malloc(…), but there will be no non-trivial calculations. You don't need to worry about adding additional nodes (beyond the first one), yet.
4. Submit.
5. Get test_minimum_block_size_1_value_peek() working. You will simply implement the peek_value_from_top_node(…) function. It returns the value of the top node in the conceptual stack.
6. Submit.
7. Get test_32_bytes_per_block_node_empty_stack() working. Now you can figure out the calculations. At this point, all you need to do is have create_empty_stack(…) calculate the right value of .num_values_per_node, given the max_block_size_bytes given. Do not use sizeof(BlockNode), sizeof(Stack), sizeof(int), or any constants (except for NULL and MIN_NODE_BLOCK_SIZE_BYTES). Also, do not initialize (or otherwise set) the fields of the Stack object using ->; use either designated initializer (See Q&A.) or compound literal (See Q&A.).
8. Submit.
9. Get test_32_bytes_per_block_node_1_value() working.
10. Submit.
11. Get test_32_bytes_per_block_node_3_values() working.
12. Submit.
13. Get test_32_bytes_per_block_node_8_values() working.
14. Submit.
15. Get test_32_bytes_per_block_node_12_values() working.
16. Submit.

How much work is this?

Relative to the provided skeleton (stack.c), the instructor's solution adds/modifies 31 source lines of code (SLOC), excluding assertions. This code follows all code quality standards and uses no advanced methods or C language features.

“Source lines of code (SLOC)” always excludes comment lines and blank lines.

👌 Okay to copy/adapt anything in this screenshot.

Requirements

Submit

To submit HW02 from within your hw02 directory, type 368submit HW02 stack.c

Q&A

1. Do we need to check if malloc(…) returned NULL?

   No. Although many C courses teach that, we do not require it because ① we are not covering good ways of handling run-time errors in this class; ② we have no easy way to force that error to happen in order to test if your error handling code works, and ③ it is extremely rare. (Prof. Quinn has never seen malloc(…) fail.)

2. How can I use a designated initializer to initialize a struct object?

   Example:
   

   typedef struct Point {
     int x;
     int y;
   }
   
   Point make_point_on_stack(int x, int y) {
       Point new_point = { .x = x, .y = y };
       return new_point;
   }
   

3. How can I use a compound literal to initialize and return a struct object in one step?

   Example:
   

   typedef struct Point {
     int x;
     int y;
   }
   
   Point make_point_on_stack(int x, int y) {
       return (Point) { .x = x, .y = y };
   }
   

4. How can I use a compound literal to initialize a struct object on the heap?

   Example:
   

   typedef struct Point {
     int x;
     int y;
   }
   
   Point make_point_on_heap(int x, int y) {
       Point* a_new_point = malloc(sizeof(*a_new_point));
       *a_new_point = (Point) { .x = x, .y = y };
       return a_new_point;  // caller is responsible for freeing
   }
   

5. What does it mean that an assert condition may have no side effects?

   Example:
   • ✘ assert(pop(&a_stack) == 5) modifies the stack (bad).
   • ✔ assert(peek_value_from_top_node(&a_stack) == 5) examines the stack without modifying it (good).

6. What is the purpose of the Stack type? Why not just use the top of the stack to refer to the stack?

   Putting these in a single struct object makes your module easier to use. Someone using it does not need to know how it works internally. Moreover, if you make something like this and then decide later to change how it works internally (e.g., to use something other than a linked list), you can do so without having to modify the code that uses it.

7. How can I get the number of byte per value in create_empty_stack(…) without using sizeof(int) or hard coding (4)?

   Here is an ugly way that some people use to get the size of a struct type field when you don't have an object to refer to.

   size_t num_bytes_per_value = sizeof(((struct BlockNode*)NULL) -> values[0]):
   

   Here is another way that you might find more readable.

   BlockNode dummy_block_node;  // no need to initialize; we will not use this for anything
   size_t num_bytes_per_value = sizeof(dummy_block_node.values[0]);
   

   👌 Okay to copy/adapt code from this Q&A item.

Updates