CPSC 1430 Programming and Problem Solving IIProgramming Assignment #5: “Typed Arena Allocator”This assignment focuses on linked lists and memory concepts.Project LoreYou have decided to leave your job...

CPSC 1430 Programming and Problem Solving II

Programming Assignment #5: “Typed Arena Allocator”

This assignment focuses on linked lists and memory concepts.

Project Lore

You have decided to leave your job atSilly Little Games, but first you want to work on a project that will look good on your resume. You hear that a division of the company wants a typed arena allocator for an upcoming project, and decide to take on the task.

Typed Arena Allocators

Anallocatoris a module which provides an interface for allocating and deallocating memory. Generally speaking, a call to one of an allocator's allocation functions returns a pointer to storage that will not be returned by any other allocation function until a pointer to that storage is passed to one of the allocator's free functions. For example, the standard allocator provided by C has the allocation functionmallocand the freeing functionfree.

Atyped allocatoris an allocator that only allocates storage for a specific type. In other words, the pointers returned by its allocating functions only ever identify storage meant for a specific type of data.

Anarena allocatoris an allocator that only allocates storage held within a pre-allocated range of memory called anarena. All pointers returned by its allocating functions only ever identify storage that exists within this arena.

Hence, atyped arena allocatoris an allocator that only returns pointers to storage meant for one type of data, and that storage must only exist in a pre-allocated range of memory.

With these restrictions, it is relatively straightforward to implement a memory allocator. Because all storage from such an allocator must be from a predetermined pool of storage and with a predetermined type,it can be served from array where each element contains that associated type.

Implementation Requirements

This project requires the implementation of five types, all of which should be defined inallocator.h, with the associated methods defined inallocator.cpp.

1. Three classes, respectively calledoutOfMemory,outOfBounds, anddoubleFree. While these classes must be defined, all that is required is that they can be constructed, destructed, and thrown as errors. An empty definition block for these classes should suffice.
2. A struct calledlink, which stores an instance of a pre-defined type calleditem, as well as alink*which is used to join togetherlinkinstances into a linked list.Theitemmembermustbe the first member declared in this struct.You can add additional members to this struct, if you like.
   
3. A class calledarenaAllocator, which serves as atyped arena allocatorfor the typeitem, using an array of typelinkas an arena, and alinked listto represent which link's items are not currently allocated.

1. 1. Members:
      • bool safety: represents whether or not memory safety checks occur for allocation and deallocation operations
      • link* arenaPointer: identifies the arena (array) which thearenaAllocatorinstance serves storage from. This arena should be allocated during the construction of the owning instance and deleted only on the destruction of the instance.
      • link* head: identifies the head of the linked list which contains all links in the arena
      • More members may be added, butALL data members must be private.
   2. Methods:
      
      • void setSafety(): sets the value of the membersafety
      • bool inBounds(item*): returnstrueif and only if the input identifies storage in the arena (this one is given to you for free - look below).
      • item* alloc(): removes a link from the instance's free list and returns a pointer to its item member. If the free list is empty, the method's behavior depends upon the value ofsafety:
        • ifsafetyistrue, then an instance ofoutOfMemoryis thrown
        • ifsafetyisfalse, thennullptris returned.
      • void free(item*): adds the link containing the identified item to the instance's free list. If the input points outside of the arena or if the input is already free, the method's behavior depends upon the value of safety:
        
        • ifsafetyistrue, then an instance ofoutOfBoundsis thrown if the input points outside of the arena and an instance ofdoubleFreeis thrown if the input is already free
        • ifsafetyisfalse, then checks for out-of-bounds errors and double-frees do not occur, and no errors are thrown.
      • arenaAllocator(int size): constructs anarenaAllocatorinstance with an arena of capacitysizeandsafetyset tofalse
      • ~arenaAllocator(): destructs anarenaAllocatorinstance, freeing the arena used to serve its allocations. If safety istrue, the destructing instance should print the addresses of any items that were not freed at the moment of destruction.
      • More methods may be added, butthe methods listed above must be public.

For the purposes of checking that your code properly compiles upon submission, a test driver must be submitted alongside this class code in a file namedp5.cpp.This driver code will NOT be tested against buggy allocator implementations, but I will provide partial credit to submissions which fail to implement allocator requirements and which catch those failures with a well-designed unit test.

Additionally, a file nameditem.h should be submitted alongsidep5.cpp,allocator.h, andallocator.cpp. This file must define anitemtype that works with the submitted allocator and test driver code.

Useful Pointer Arithmetic

The fact thatitemis the first member oflinkis very important. If a struct/class doesn't use any advanced OOP features, the C++ standard guarantees that the first member of a struct has the same address as the struct itself. Hence, we can directly cast between pointers to links and pointers to the contained items:

struct link{
item data;
link* next;
};
item* linkToItem(link* theLink){
return (item*) theLink;
}
link* itemToLink(item* theItem)
{
return (link*) theItem;
}

You should use this property when converting betweenlink*anditem*for theallocandfreemethods.

For checking if a pointer identifies storage in an array, you should usestd::lessandstd::greater to determine the address's position relative to the array bounds. This is because the normal inequality operators don't work 100% correct if the input points outside of the arena. Since this is very non-obvious, below is an implementation you can use forinBounds.

// be sure to #include 
bool arenaAllocator::inBounds(item* thePointer)
{
bool afterEnd  = std::greater{}(thePointer, (arenaPtr+size));
bool beforeStart = std::less  {}(thePointer, arenaPtr   );
return ! ( afterEnd || beforeStart );
}

Getting Started

An initial version ofitem.handp5.cppis available to help get you started. You can copy it to your current directory on the cs1 server using the following command:

cp /home/fac/bcuneo/class/cs1430/p5/* .

The test driver code in this initial version of p5.cpp is not comprehensive, but it should detect most errors in your allocation/deallocation logic.

Testing for Memory Bugs

The programvalgrindcan tell if another program has leaks memory or performs improper memory accesses.

You can testp4by running the commandvalgrind --leak-check=full ./p5. The program will behave normally until it finishes, at which pointvalgrindwill print diagnostic information about how your P5 executable used memory.

Your program has no memory leaks ifvalgrindprints the messageAll heap blocks were freed -- no leaks are possible.

If other memory errors occurred during execution,valgrindwill report them to you as they occur.

Building the Project

This program must build with a Makefile.

To use a Makefile, place it in your project directory (with the file nameMakefile) and runmake. A default Makefile is provided with the starter code (see above). You may edit the Makefile, if you choose.

The content of this Makefile should look like the block below. If you copy/paste from this block, ensure that the indentation is still a single tab character after pasting.

Makefile Contents:

p5: p5.cpp allocator.o item.h
g++ p5.cpp allocator.o -std=c++11 -Wall -g -o p5
allocator.o: allocator.h allocator.cpp item.h
g++ allocator.cpp    -std=c++11 -Wall -g -c

Submitting the Project

The source code files must be namedMakefile,p5.cpp, allocator.h,allocator.cpp, and item.h.