CMSC-341H Fall 2004

Project 2

Assigned	6 Oct 2004
Due	19 Oct 2004 at 11:59PM

Background

It is difficult to overstate the importance of the list abstract data type. This project will give you experience working with lists in the context of a dynamic memory allocation system.

Being comfortable with pointers and pointer arithemetic are important to any programmer. This project will give you two opportunities to work with pointers at an abstract or low level.

Description

Your assignment is to implement one of the following variations of that project. You may implement both variations for extra credit. Submit a file named ReadMe.txt so I know which variation(s) you are implementing.

Variation 1 - Using Smart Pointers

One of the fundamental problems with the use of pointers to dynamically allocated memory is one of "ownership". When you write code such as Car *p1 = new Car;, the variable p1 not only points to, but also "owns" the memory that was allocated. You must eventually write delete p1;. If we never execute delete p1;, we're created a memory leak. If p1 is ever copied to another pointer (say p2) either explicitly (p2 = p1;) or implicitly (say by being passed as a parameter), we now have two pointers that "own" the same memory and you must be very careful about managing the pointers, since executing both delete p1; AND delete p2; will cause some kind of abnormal program termination.

One solution to these kinds of pointer problem is the introduction of a "SmartPointer" class. A quick search on Google will reveal much material that discusses smart pointers in great detail. I found this one http://www.informit.com/articles/article.asp?p=31529 helpful.

This class is a "wrapper" around the actual pointer -- the pointer is a data member of the SmartPointer class. Since we would like to be able to point to any kind of object, the SmartPointer is implemented as a template, where 'T' is the type of object to which the SmartPointer points. A typical implementation of a SmartPointer will have the "feel" of real pointer by supporting the usual pointer operations , "*" and "->". Assignment, copy constrcutors etc are also supported and are an important aspect of correct SmartPointer implementation. A SmartPointer will typically not have any "named" member functions.

Your assignment is to implement a SmartPointer class and modify the author's linked list code (LinkedList.cpp and LinkedList.h - available in Dr. Oates' public directory) to use your SmartPointer. Your implementation can be as relatively simple or as complex as you want, as long as the typical operations mentioned above are supported and your class supports proper object "ownership" so that there is no chance for memory leaks or double deletion.

Then do one of the following

Write a test program for your linked list. Be sure that your test program adequately tests all linked-list functions. Your program should produced labelled output that shows the results of each test.
Implement project 2

Variation 2 - Modified MemBlock and FreeBin

This is a variation of Project 2 assigned to all other CMSC 341 sections. You should read and understand that project description before continuing.

In project 2, the MemBlock class contains two integers which represent the starting and ending "addresses" of a contiguous piece of memory. The MemoryManager contains a list of FreeBins, each of which is a list of MemBlocks and a list of MemBlocks that represent the allocated memory.
Your assignment is to implement the following variations of MemBlock and FreeBins.

Each FreeBin is a list of MemBlocks as described above. However, since each FreeBin consists of memory block which are all the same size, the information in the MemBlock (start/end addresses) is redundant -- only the starting address is necessary.

Assignment Part A
Design the FreeBins as a list of actual pointers into the memory block rather than a list of MemBlocks.

The "addresses" in a MemBlock are really indices into the memory block being allocated by the MemoryManger -- they're not real pointers. Real programmers use real pointers!

Assignment Part B
Implement the MemBlock class to contain a pointer into the memory block and the size of allocated memory block rather than the pair of indices. Since the MemBlock now contains a pointer as a data member, you must implement its default constructor, copy constructor, assignment operator and destructor.

Sample Output

The following Proj2.cpp file:

#include <iostream.h>
#include "MemoryManager.h"

using namespace std;

int main(int argc, char **argv) {
  MemoryManager m;

  m.initialize(1, 32);

  cout << m;
  cout << endl << endl;

  addr_t p1, p2, p3, p4;

  p1 = m.alloc(1);
  p2 = m.alloc(1);
  p3 = m.alloc(1);
  p4 = m.alloc(1);

  m.free(p1);
  m.free(p3);
  
  cout << m << endl << endl;

  m.free(p2);

  cout << m << endl << endl;

  m.free(p4);

  cout << m << endl << endl;
}

Creates the following output:

Memory Manager
--------------

FreeBins
--------
FreeBin: size = 8

FreeBin: size = 16

FreeBin: size = 32
MemBlock: 1 - 32


Allocated
---------


Memory Manager
--------------

FreeBins
--------
FreeBin: size = 8

FreeBin: size = 16
MemBlock: 1 - 16

FreeBin: size = 32


Allocated
---------
MemBlock: 17 - 24
MemBlock: 25 - 32


Memory Manager
--------------

FreeBins
--------
FreeBin: size = 8
MemBlock: 25 - 32

FreeBin: size = 16
MemBlock: 1 - 16

FreeBin: size = 32


Allocated
---------
MemBlock: 17 - 24


Memory Manager
--------------

FreeBins
--------
FreeBin: size = 8

FreeBin: size = 16

FreeBin: size = 32
MemBlock: 1 - 32


Allocated
---------

Variation 3 - Extra Credit

Implement both variation 1 and variation 2 by implementing a SmartPointer, modifying the author's code to use it and modify the MemBlock to contain a pointer and size.

Files To Be Submitted

Submit all files required to build an executable named Proj2 by running make. For variation 2, remember that you should not submit a file named Proj2.cpp, as we will write one to test your code.

Submit the files using the procedure given to you for your section of the course.
If your makefile is set up correctly, you should be able to execute the command make submit.

Submit Tools

There are a number of tools available to you to check on your submittal. It is your responsibility to ensure that the submittal is correct and will result in a successful
compilation of your project. Do not wait till the last minute to submit your files. Give yourself enough time to check that your submittal is correct.

If you don't submit a project correctly, you will not get credit for it. Why throw away all that hard work you did to write the project? Check your
submittals. Make sure they work. Do this before the due date.

Documentation for the submit program is on the web at http://www.gl.umbc.edu/submit/. One of the tools provided by the submit program is
submitls. It lists the names of the files you have submitted.

Additionally, there are two programs for use only by CMSC-341 students (not part of the UCS submit program). They are in the directory
/afs/umbc.edu/users/d/e/dennis/pub/CMSC341/ and are named submitmake and submitrun. You can use these programs to
make or run your submitted projects.

The syntax is similar to that for submit:

submitmake <class> <project>

Example: submitmake cs341h Proj1

This makes the project, and shows you the report from the make utility. It cleans up the directory after making the project (removes .o and ii_files), but leaves the
executable in place.

submitrun <class> <project> [command-line args]

Example: submitrun cs341h Proj1 checkers checkfile.dat

This runs the project, assuming there is an executable (i.e. submitmake was run successfully).

Grading and Academic Integrity

Your project will be tested using a variety of command lines, some of which will be invalid.
Your project will also be tested using a variety of command files which will test various conditions which your code should handle.

Project grading is described in the Project Policy handout.

For variation 2, Your answers to 341-Fall04-proj2_questions.txt are worth 10% of your project grade.

Cheating in any form will not be tolerated. Please re-read the Project Policy handout for further details on honesty in doing projects for this course.

Remember, the due date is firm. Submittals made after midnight of the due date will not be accepted. Do not submit any files after that time.