In this lab, you will get to create a linked list class that uses reference counting to automatically free the storage for list nodes that cannot be reached.
We will model this list type on lisp lists, as we did in class: A list is either empty (a null pointer) or points to a "cons_cell" made up of a first element and a list of remaining elements. We will provide the same operations that were available for the list class created in lecture, but use a different rule to manage storage allocation:
Cons cells exist only in class list, and nothing other than a list ever points to a cons cell. Cons cells are created only on the heap (via new), and each cons cell records the number of "list" pointers that point to it, so we can delete the cons cell when this "reference count" falls to 0.
You should create this list class in the RCList project. Use "cvs_create 245 RCList" to get the set of starting files for this project. These are basically the the files I created for my list class in lecture, except that I have removed the bodies of many of the functions (most of them will need to be changed for the new imprementation), and renamed "list_element" to be "cons_cell", and finally managed to hide the cons_cell structure inside the implementation section of "list", as I should have done all along. If you want to see the complete code for the old list class, before I removed the bodies of the functions, it's in the directory /home/unixmail/dwonnaco/CS245/Lists-2-better.
You should then modify whatever is necessary in the list class and cons_cell struct (in list.cc), and fill in the missing function bodies, to make sure the lists use correct reference counting. You can test your class with the main function provided in default.cc, or modify this function to perform more extensive testing.
Your list should represent a list elements of type int, as shown in my header file. If you wish to extend it to allow lists of any type, using the "template" features of C++, that is ok, but you should only attempt this after you have committed a working version that allows only elements containing data of type int. (I have not been able to make templated lists compile on this system yet.)
Use cvs add (if necessary) and cvs commit, or try out the "cvs_submit" program, to hand in your completed lab.