实现数据结构中的Stack，练习GDB的使用。
Introduction
For many reasons, a programmer might not want to use statically defined memory. So, in this assignment you will be learning to write and debug code that manages its own dynamically allocated memory. Specifically we will use the standard allocators to create or remove memory on the Heap.
The Heap is a large area of memory, a range of addresses, set aside by the compiler and operating systems which is free for arbitrary use. In other words there is no other part of you program’s variables or code placed within the Heap.
The C standard library provides a Heap memory allocator called the malloc package. C programs allocate a block of memory by calling the “malloc” function, and free a block by calling the “free” function.
A block of memory is simple a contiguous set of bytes starting at a specific address and ending at a specific address.
As your program executes it can use the function malloc to request a new block of memory of a particular size. malloc will return the starting address of a block that is at least as big as the size requested. If it cannot find enough space it returns NULL, the zero address. malloc ensures that the block it returns does not overlap with any other allocated or free blocks. In this way your program can safely use this memory to store whatever it likes. Similarly, your program can free a block it has previously allocated by calling the free function passing the starting address of a block it allocated with malloc earlier.
Dynamically allocated memory is very powerful and the heart of how most real programs work. Most languages like Java, python, ruby, javascript, etc are really just programs themselves that make heavy use dynamic memory in their operation. These languages, however, largely hide the details of dynamic memory management from the programmer.
While dynamically allocated memory is very powerful it can be very tricky to get right. Many bugs can occur if you don’t fully understand how things work. For example, if your program allocates memory for something that is temporary, for some operation it has been requested to do, and then never frees that memory it creates what’s called a ‘leak’. Given how fast a computer can operate, in time such leaks can exhaust the memory capacity of your computer and things will begin to fail. Or perhaps your program attempts to use memory, read or write it, that it has already freed. This can lead to very difficult bugs as there will be no immediate error. In fact, it may have no noticeable affect for a very long time until one day some other part of your program reallocates a block that ends up overlapping with the free memory that is being still actively used. All of a sudden your data structures seem to be magically changing for no apparent reason. Another common bug, is freeing memory that you already freed before, this too can lead to nasty bugs. Unfortunately there are many more mistakes one can make.
In order to write powerful programs such as new programming languages, operating systems, databases, and high performance programs one must learn to program with dynamic memory and perhaps more importantly become familiar with debugging the bugs that can arise from the common mistakes made. Remember despite other languages hiding it from you someone wrote the dynamic memory management code in that language and they too had to learn how to properly use dynamic memory and debug the code they wrote.
In this assignment, we will explore programming and debugging with dynamic memory in the construction of an infix calculator. We will build a calculator that uses two types of stacks, data and operator stacks that store items on it. The stacks and the items will use dynamically allocated memory. Additionally, we will use this assignment to explore how large more complex programs, composed of multiple source files are constructed. In Part A of the assignment you will construct a Stack Abstract Data Type (StackADT) module, in a separate set of files, that you will use in Part B to implement the actual calculator.
Careful analysis of your code, defensive programming and knowledge of the debugger is critical to getting dynamic memory management code working correctly.
You can also read Chapter 19 for more details about the Heap and how it grows.
Logistics
The only “hand-in” will be electronic. Any clarifications and revisions to the assignment will be posted on the course Piazza site.
Background
Some building blocks are needed to understand this assignment.
Linked Lists
A linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes which together represent a sequence. So, each node, contains the data and also a pointer to the next node, as shown in Fig. ??. Linked lists are great tools to master as they can be used to not just create uni-directional lists but bi-directional, circular or any fun shape you can imagine. As they have no fixed size, when a new node is added memory needs to be dynamically initialized for that node via C code and later when we remove the node it should be freed as to not run out of memory.
Stack
A Stack is a data structure that is used to store information in a distinct order.
Two key operations on a stack are, (1) push operation which inserts an element into the stack, and (2) pop operation which removes the last element that was added into the stack. The way a stack grows is, last in first out (LIFO), i.e. when a push occurs the element is added to the top of the list and when it is popped is the first to be removed. We are using a one directional linked list implementation for the stack.
Looking at figure, the first element that created the stack was 2, hence it is at the bottom and does not have a pointer to another node but has null. Then 7 is pushed and last element to be pushed onto the stack is 4. Hence the stack pointer is pointing to memory address 709. If pull was called on this stack. The node with data 4 and addr. pointer 351 will be deleted by freeing the memory and moving the stack pointer to point at address 351 as the top should now me element 6.
Part A: StackADT
Readings:
- Please read Chapter 19 of your text. This introduces the concept of dynamically allocated memory. Also provides various implementation of STack Data Structure that will be useful in part A of the homework assignment.
- Chapter 15 will help you understand how the various files of this assignment are used to create the program. It helps understand the use of header files and building a makefile.
- You will also likely find it useful to review the material of chapter 17.
Part A of this assignment is essentially programming project 4 on page 506 of your textbook. However, we have provided some additional support and guidance.
Details
Begin by clone a copy of the your assignment-5A repository from you cs210-gitlab account. In the repository you will find several files.
- Makefile
This file describes how to construct your program from the other files. In particular when you run the program called make it will read this file and run the compiler on the various files to produce intermediate fragments called object files. It then uses the compiler again to link them together to produce the executables. See chapter 15 for more information on make and makefiles. In partA the makefile will direct make to try and build two executables stackclient and stackclient memtrace (discussed below). Initially, make will not work as the solution in stackADT4.c is not implemented. - stackADT.h This is the header file on page 496 of the textbook. We have modified the names by prefixing them with Stack . We have also modified. as per programming project 4 to remove the use of the Item typedef. Instead it is written around the idea of using void *. You should not have to modify this but you should carefully review in context of the material in Chapter 19 so you understand what it is you are trying to write.
- stackADT4.c this is the file that you will spend most of your effort on. We have seeded the file with some includes that you should not have to modify. You main goal is to write implementations of the functions listed in stackADT.h. As suggested in the textbook you should use stackADT3.c on page 500 as your starting point. You will need to type this in and modify as you go. Be very careful to analyze and understand what you are doing. Remember dynamic memory bugs find their way into code very easily.
- stackclient.c to make your life easier we are providing you with a version of the stackclient.c code on page 494 that has been modified to exercise the new version of the stackADT that you are writing in stackADT4.c. You should carefully study this code!. By understanding it you can better understand what you stack code has to do. In it you can see examples of the client code using malloc and free to create memory items that it uses the stack code to store and recall. It is careful to free the memory when it is done with an item. Pay attention to this as this will be used in part B when you have to manage the stacks for the calculator!
- memtrace.h This is a header file that must be included to use the memory tracing infrastructure. This is required for the tests and will aid in your debugging. You should not have to modify it and by default it is already included in the necessary c files. See the appendix on memtrace for more information.
- memtrace.c This is the implementation associated with memtrace.h. You should not have to modify it.
- uthash.h This is hashtable code used by the memtrace code to track the each malloc and match up the frees. You should not have to modify it. test.sh As always, use this file to see how your code is working. There is a slight modification as to how you run it. Now test.sh takes an argument. Type ./test.sh 1 to run the test. It take stackclient.c and use your implementation in stackADT4.c to test the code.
- stackclient This should just be the executable version of stackclient.c. If you run ./reference stackclient, the output should match for both if your implementation of the stack code is correct.
- stackcient_memtrace This is another executable that can be executed by typing ./stackclient memtrace. This will help you know if you are leaking memory in your code. The full potential of this is explained in the Appendix. This along with GDB will be the most useful tools for debugging your code.
Tips and Hints
- You may find it useful to simply get the code from the textbook working first by creating your own copy of stackclient.c and stackADT3.c from the textbook. To do this you might create two new files (bookstackclient.c and stackADT3.c). Then add lines to the makefile so that you can compile these into a new binary eg. bookstackclient that you can then play with. This will also be good practice in managing big projects.
- Learn to use the debugger! See appendix GDB.
- Be careful to think about what Stack make empty should do given that the stack is now storing items that are dynamically allocated.
- Figure out how to use the memtrace infrastructure we have provided. See appendix memtrace.
- It is very important you see how the stack data type has been changed from Item to void *. How does this change each individual function?
- Read stackclient.c, it has comments to explain how having a void * type changes use of malloc for using an int vs char.
Evaluation
Auto-grader will be grading most of the assignment, but as always there will be points for comments, gitlog and coding style.