Tombstones Assignment

Unlike most modern object-oriented languages, C++ does not provide automatic garbage collection, and indeed completely accurate collection is not possible given the lack of complete type safety inherited from C. 

As mentioned in the text, it is possible in C or C++ to implement conservative collection, which reclaims any object whose address does not appear as a bit pattern in any global variable, stack variable, or potentally reachable heap variable. 

In this assignment we will explore a different approach, which leverages templates and operator overloading in C++ to implement tombstones (described on pages C-144–C-146 of the PLP companion site, and again briefly on page 389 and 391 of the main text).  The programmer remains responsible for manual storage reclamation, but the library package catches all dangling references and all memory leaks of noncircular structures.  (There’s no good way to catch leaks of cycles, given that C++ is not type safe.)  Such a library can be valuable during development and testing.  If performance is critical, tombstones can then be turned off during production use.  (This approach to checking, famously likened to the sailing enthusiast who takes off his life jacket when heading out to sea, isn’t necessarily a good idea, but it’s certainly common practice.)

The details

Your task is to build a template class that behaves much like a pointer, but uses tombstones for error checking: 

template <class T>
class Pointer {
    Pointer<T>();                               // default constructor
    Pointer<T>(Pointer<T>&);                    // copy constructor
    Pointer<T>(T*);                             // bootstrapping constructor
        // argument should always be a call to new
    ~Pointer<T>();                              // destructor
    T& operator*() const;                       // deferencing
    T* operator->() const;                      // field dereferencing
    Pointer<T>& operator=(const Pointer<T>&);   // assignment
    friend void free(Pointer<T>&);              // delete pointed-at object
        // This is essentially the inverse of the new inside the call to
        // the bootstrapping constructor.  It should delete the pointed-to
        // object (which should in turn call its destructor).
    // equality comparisons:
    bool operator==(const Pointer<T>&) const;
    bool operator!=(const Pointer<T>&) const;
    bool operator==(const int) const;
        // true iff Pointer is null and int is zero
    bool operator!=(const int) const;
        // false iff Pointer is null and int is zero
You’ll probably also want the following, to allow int-to-Pointer comparisons (not just Pointer-to-int). 
template <class T>
bool operator==(const int n, const Pointer<T>& t) { return t == n; }
template <class T>
bool operator!=(const int n, const Pointer<T>& t) { return t != n; }
Please name your source files tombstones.h and (if you need it)  Programmers should be able to use your Pointer class via
    #include "tombstones.h"

Ideally, you should like to be able to take an arbitrary (correct) pointer-based program, replace instances of T* with Pointer<T>, and have it compile and run correctly (it may run a bit slower, and use a bit more memory).  If the program uses a dangling reference, however, you should get a good run-time error message instead of bizarre behavior of a segmentation fault or unexpected behavior.  You should get a similar message if your program leaks memory (at least as long as that memory doesn’t contain internal circular references).  You should reference count your tombstones so you can reclaim them when they are no longer needed. 

Some aspects of the emulation of pointers are a good bit more difficult to implement (and understand!) than others.  You must implement the operators shown above.  Other useful features are listed under “Extra Credit” below. 

Division of labor and writeup

As in previous assignments, you may work alone or in teams of two.  Be sure to follow all the rules on the Grading page.  As with all assignments, use the turn-in script:  ~cs254/bin/TURN_IN.  Put your write-up in a README.txt or README.pdf file in the directory in which you run the script.  Be sure to describe any features of your code that the TAs might not immediately notice.  Also include copies of whatever test programs you have used to exercise your code.


You will almost certainly find it helpful to read up on the C++ smart pointer idiom.  One good source is the article by Andrei Alexandrescu.  You may also want to consult one of the many C++ template tutorials on the web.  Be sure to read section 8.5.2 on the companion site

The TAs have provided a set of test files that you can use to see if your solution is on track.  Unpack them using the tar utility: 

prompt> tar xf a5samples.tar

Extra Credit suggestions

  1. Make inheritance work correctly.  That is, if A is derived from B, then it should be acceptable to use Pointer<A> in any context expecting Pointer<B>

  2. Make arrays work correctly.  You should be able to allocate an array of objects of class T with a single tombstone.  Pointers should then be extended to indicate which element of an array they point to.  You should support subscripting, pointer arithmetic (add or subtract an integer, subtract a Pointer), and comparison for ordering (<, >, <=, >=). 

  3. Should T* and Pointer<T> be interoperable?  Should you be able to use one in a context that expects the other?  Should you be able to assign one into the other?  If not, explain why.  If so, implement the necessary support routines.  If Pointer<T> interoperates with T*, how about T&

  4. Extend your code so that Pointer checking can be turned off at compile time.  When checking is turned off, your code should run as fast as it would with ordinary T* types.  (Hint:  this is actually pretty easy.  You will probably want to use an extra template parameter.)

  5. As an alternative to the (unenforced) suggestion that arguments to the T* copy constructor for Pointers, define a make_Pointer method that takes T constructor arguments (whatever they are) as parameters.  (This is quite tricky: you’ll have to learn about variadic templates and forwarding of rvalue references.)

Trivia Assignment

Before the beginning of class on Monday, November 13, each student should complete the T5 trivia assignment found on Blackboard


Wednesday November 22, at noon; no extensions. 

Last Change: 14 October 2019 / Michael Scott's email address