The goal of your next project is to simulate the C heap manager which is used to

Question

The goal of your next project is to simulate the C heap manager which is used to allocate and deallocate dynamic memory. The “heap” is a large pool of memory set aside by the runtime system for a program to use for dynamic variables.

The two main functions are

- malloc, used to satisfy a request for a specific number of consecutive bytes;

- free, used to make allocated blocks available for future malloc requests (i.e., return them to the pool of available memory).

•Our simulation uses an initially allocated large block of unsigned chars as our memory pool for dynamic allocation (the heap)

•As memory is allocated (by calls to malloc) and deallocated (by calls to free), the heap will be made up of consecutive blocks of memory that are either available for allocation (free) or currently allocated.

•To keep track of the allocated and available blocks of memory, we will use a doubly-linked list of blocknodes which will use header and trailer nodes.

---------------------------------------------------------------------------------------------------------------------

blockdata.cpp

---------------------------------------------------------------------------------------------------------------------

#include "blockdata.h"
#include
using namespace std;

blockdata::blockdata(unsigned int s, unsigned char *p, bool f)
{
blocksize = s;
blockptr = p;
free = f;
}

ostream &operator << (ostream &out, const blockdata &B)
{
out << "[" << B.blocksize << ",";
if (B.free)
out << "free";
else
out << "allocated";
out << "]";
return out;
}

---------------------------------------------------------------------------------------------------------------------

blockdata.h

---------------------------------------------------------------------------------------------------------------------

#ifndef _BLOCKDATA_
#define _BLOCKDATA_

#include

using namespace std;

struct blockdata {
friend ostream& operator << (ostream&, const blockdata &);
int blocksize;
bool free;
unsigned char *blockptr;  
blockdata(unsigned int s = 0, unsigned char * p= nullptr, bool f = false);
};

#endif

---------------------------------------------------------------------------------------------------------------------

dlList.h

---------------------------------------------------------------------------------------------------------------------

#ifndef __DLLIST__
#define __DLLIST__

#include
#include
#include "dlNode.h"

template
class dlList {
public:
dlList(T headerData = T(), T trailerData = T() );
bool empty();
void insertAfter(dlNode *current, T newval);
void insertBefore(dlNode *current, T newval);
void deleteNext(dlNode *q);
~dlList();
void deletePrevious(dlNode *q);
void deleteNode(dlNode *q);
void print(const char *sep);
dlNode *header;
dlNode *trailer;
};

template
bool dlList::empty()
{
return header->next == trailer;
}
  
template
dlList::~dlList()
{
while(header->next != trailer) {
dlNode *hold = header->next;
header->next = hold->next;
delete hold;
}
delete header;
delete trailer;

}

template
dlList:: dlList(T headerData, T trailerData)
{
header = new (std::nothrow) dlNode(headerData);
trailer = new(std::nothrow) dlNode(trailerData);
trailer->prev = header;
header->next = trailer;
}

template
void dlList::print(const char *sep)
{
assert(header != nullptr && header->next != nullptr);
if(header->next == trailer) {
std::cout << "Empty list" << std::endl;
return;
}
dlNode *cursor = header->next;
  
while(cursor->next != trailer) {
std::cout << cursor->info << sep;
cursor = cursor->next;
}
std::cout << cursor->info << std::endl;
}

template
void dlList::insertAfter(dlNode *current, T newval)
{
assert(current != trailer);
current->next = new dlNode(newval,current,current->next);
current = current->next;
current->next->prev = current;
}

template
void dlList::insertBefore(dlNode *current, T newval)
{
assert(current != header);
insertAfter(header,trailer,current->prev,newval);
}

template
void dlList::deleteNext(dlNode *current)
{
assert(current != trailer && current->next != trailer);
dlNode *hold = current->next;
current->next = hold->next;
if (current->next != nullptr)
current->next->prev = current;
delete hold;
}

template
void dlList::deletePrevious(dlNode *current)
{
assert(current != header && current->prev != header);
dlNode *hold = current->prev;
current->prev = hold->prev;
current->prev->next = current;
delete hold;
}

template
void dlList::deleteNode(dlNode* current)
{
assert(current != header && current != trailer);
  
dlNode *hold = current;
current->prev->next = current->next;
current->next->prev = current->prev;
delete hold;
}

---------------------------------------------------------------------------------------------------------------------

dlNode.h

---------------------------------------------------------------------------------------------------------------------

#ifndef __DLNODE__
#define __DLNODE__

#include
#include

template
class dlNode {
public:
T info;
dlNode *prev;
dlNode *next;
dlNode(T val, dlNode *p = nullptr, dlNode *n = nullptr) : info(val),
prev(p), next(n) {}
};

#endif

---------------------------------------------------------------------------------------------------------------------

MemoryManager.h

---------------------------------------------------------------------------------------------------------------------

#ifndef __MM__
#define __MM__

#include
#include
#include "blockdata.h"
#include "dlList.h"

using namespace std;

class MemoryManager
{
public:
MemoryManager(unsigned int memtotal);
unsigned char * malloc(unsigned int request);
void free(unsigned char * ptr2block);
void showBlockList();

private:
dlList blocklist;
unsigned int memsize;
unsigned char *baseptr;

void mergeForward(dlNode *p);
void mergeBackward(dlNode *p);
void splitBlock(dlNode *p,unsigned int chunksize);
};

#endif

---------------------------------------------------------------------------------------------------------------------

testMemMgr.cpp

---------------------------------------------------------------------------------------------------------------------

#include
#include "MemoryManager.h"
using namespace std;

int main()
{
MemoryManager heaper(50);
cout << "After initializing" << endl;
heaper.showBlockList();
unsigned char * p1 = heaper.malloc(10);

cout << "After the first malloc ";
heaper.showBlockList();

unsigned char *p2 = heaper.malloc(20);
cout << "After the second malloc ";
heaper.showBlockList();

cout << "Asking for an un-allocatable block ";
unsigned char *p8 = heaper.malloc(30);
if (p8 == 0)
cout << "Good. The call to malloc returned NULL ";
else
cout << "Uh-oh. Call to malloc did not return NULL as it should have ";

cout << "Free the second block ";
heaper.free(p1);
heaper.showBlockList();

cout << "Allocate a block too big for the initial open block ";
p1 = heaper.malloc(15);
// cout << "malloc done ";
heaper.showBlockList();

cout << "Free the most recently allocated pointer ";
heaper.free(p1);
heaper.showBlockList();

cout << "Free the middle block ";
heaper.free(p2);
heaper.showBlockList();

return 0;
}

---------------------------------------------------------------------------------------------------------------------

MemoryManager.cpp FILE TO BE COMPLETED

---------------------------------------------------------------------------------------------------------------------

#include
#include
#include "MemoryManager.h"

MemoryManager::MemoryManager(unsigned int memtotal)
{
memsize = memtotal;
baseptr = new unsigned char[memsize];
blockdata originalBlock(memsize,baseptr,true);
blocklist.insertAfter(blocklist.header,originalBlock);
assert(!blocklist.empty());
}

void MemoryManager::showBlockList()
{
// cout << " -------------BlockList start------------------ ";
blocklist.print("->");
cout << endl;
// cout << " -------------BlockList end------------------ ";
}

void MemoryManager::splitBlock(dlNode *p, unsigned int chunksize)
{
// Fill in the missing code and delete this comment

}

unsigned char * MemoryManager::malloc(unsigned int request)
{
// Fill in the missing code and delete this comment

}

void MemoryManager::mergeForward(dlNode *p)
{
// Fill in the missing code and delete this comment

}

void MemoryManager::mergeBackward(dlNode *p)
{
// Fill in the missing code and delete this comment

}

void MemoryManager::free(unsigned char *ptr2block)
{
// Fill in the missing code and delete this comment

}

---------------------------------------------------------------------------------------------------------------------

SAMPLE OUTPUT

---------------------------------------------------------------------------------------------------------------------

After initializing

[50,free]

After the first malloc

[10,allocated]->[40,free]

After the second malloc

[10,allocated]->[20,allocated]->[20,free]

Asking for an un-allocatable block

Good. The call to malloc returned NULL

Free the second block

[10,free]->[20,allocated]->[20,free]

Allocate a block too big for the initial open block

[10,free]->[20,allocated]->[15,allocated]->[5,free]

Free the most recently allocated pointer

[10,free]->[20,allocated]->[20,free]

Free the middle block

[50,free]

Explanation / Answer

Given below is the completed code for MemoryManager.cpp with output. Please don't forget to rate the answer if it helped. Thank you.

#include <cassert>
#include <iostream>
#include "MemoryManager.h"
MemoryManager::MemoryManager(unsigned int memtotal)
{
memsize = memtotal;
baseptr = new unsigned char[memsize];
blockdata originalBlock(memsize,baseptr,true);
blocklist.insertAfter(blocklist.header,originalBlock);
assert(!blocklist.empty());
}
void MemoryManager::showBlockList()
{
// cout << " -------------BlockList start------------------ ";
blocklist.print("->");
cout << endl;
// cout << " -------------BlockList end------------------ ";
}
void MemoryManager::splitBlock(dlNode<blockdata> *p, unsigned int chunksize)
{
blockdata newblock(p->info.blocksize - chunksize, p->info.blockptr + chunksize, true);
p->info.blocksize = chunksize;
blocklist.insertAfter(p, newblock);
}
unsigned char * MemoryManager::malloc(unsigned int request)
{
dlNode<blockdata>* current = blocklist.header->next;
while(current != blocklist.trailer)
{
//searches the 1st free block enough to satisfy the request
if(current->info.free && current->info.blocksize >= request)
{
splitBlock(current, request);
current->info.free = false;
return current->info.blockptr;
}
current = current->next;
}
return nullptr;

}
void MemoryManager::mergeForward(dlNode<blockdata> *p)
{
//merges this free block with previous block if previous block was free. Deallocates dlnode of this
//block
if(p->next->info.free)
{
p->info.blocksize += p->next->info.blocksize;
blocklist.deleteNext(p);
}
}
void MemoryManager::mergeBackward(dlNode<blockdata> *p)
{
if(p->prev->info.free)
{
p->prev->info.blocksize += p->info.blocksize;
blocklist.deleteNode(p);
}
}
void MemoryManager::free(unsigned char *ptr2block)
{
dlNode<blockdata>* current = blocklist.header->next;
while(current != blocklist.trailer)
{
//search for the block matching the pointer and make sure it was allocated
if(current->info.blockptr == ptr2block && current->info.free == false)
{
current->info.free = true;
mergeForward(current);
mergeBackward(current);
return;
}
current = current->next;
}

}

output

After initializing
[50,free]

After the first malloc
[10,allocated]->[40,free]

After the second malloc
[10,allocated]->[20,allocated]->[20,free]

Asking for an un-allocatable block
Good. The call to malloc returned NULL

Free the second block
[10,free]->[20,allocated]->[20,free]

Allocate a block too big for the initial open block
[10,free]->[20,allocated]->[15,allocated]->[5,free]

Free the most recently allocated pointer
[10,free]->[20,allocated]->[20,free]

Free the middle block
[50,free]

Program ended with exit code: 0

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.