This is C++ data structure assignment. DO NOT take it until you fully read the instructions and know if you can make it the right way or not. if anything wrong, I will request a refund

 

 

The Memory Manager Project Objectives
• The goal of your next project is to simulate the C heap
manager
• A runtime module used to allocate and de-allocate
dynamic memory.
• The "heap" is a large "pool" of memory set aside by the
runtime system
• The two main functions are
– malloc, used to satisfy a request for a specific number of
consecutive blocks;
– free, used to make allocated blocks available f
2 Description
• Our simulation uses
– a large block of unsigned chars as our memory pool; and
– a doubly-linked list to keep track of allocated and available
blocks of unsigned char.
– We will refer to the nodes of this list as blocknodes • The info field of each node is of type blockdata
• An object of type blockdata has attributes
– blocksize number of bytes in the block – free a Boolean flag indicating the status of a block – blockptr a pointer to the first byte of the block 3 malloc
• The malloc algorithm has an int parameter request
• request is the size of the block to be allocated
• request scans the list until it finds the first blocknode B
such that
– B.free == true
– B.size ≥ request • If no such block is found, malloc returns NULL (0) 4 malloc
• If B.size is larger than request, the block is broken up
into two blocks
– The first block's size: request – The second's size: B.size-request • This requires that we insert a new blocknode C after B to
reference the second block (which is free)
• Then, whether we split the block or not, we
– set B.free to false
– set B.size to request
– return the address B.bptr
5 free
• To implement free(unsigned char *p) we must find
the blocknode whose bptr field equals p
• This is done by traversing the blocknode list
• If this fails, we terminate the program
• Otherwise we change the blocknode's free field to true
• But we don't stop there 6 Merging Consecutive free Blocks
• It should be clear that we want to maximize the size of the
free blocks
• This means there should never be consecutive free blocks
• Whenever consecutive free blocks occur, they should be
merged
• When we free a block, we need to check the previous and
next blocks to see if they are free
• If so, we must merge the blocks into one big block
• This may involve the deletion of one or two blocknodes from
our list
7 Doubly-Linked List Utilities
• To manage doubly-linked lists, we will use a collection of
templated functions
• We will not need the apparatus of a class here, a struct
suffices
• The definition of dlNode and associated functions will be
supplied in the file dlListUtils.h
• We will take the approach used in the text for doubly-linked
lists
• Namely, we will use dummy header and trailer nodes
• This simplifies the code for many list operations
8 Project Files
• The files used in this project are
• dlListUtils.h
• blockdata.h
• blockdata.cpp Do not modify, do not submit • MemoryManager.h
• MemoryManager.cpp Complete and submit • testMemMgr.cpp Modify and use for testing;
Do not submit
9 Source Code dlUtils.h
#include <iostream>
#include <cassert>
template <class T>
struct dlNode {
T info;
dlNode<T> *prev;
dlNode<T> *next;
dlNode<T>(T val, dlNode<T> *p,
dlNode<T> *n)
:info(val),prev(p),next(n){};
};
11 dlUtils.h
template <class T>
void insertAfter(dlNode<T> *trailer,
dlNode<T> *current, T newval)
{
assert(current != trailer);
current->next =
prev
next
new dlNode<T>(newval,current,current->next);
current = current->next;
current->next->prev = current;
} 12 dlUtils.h
template <class T>
void printDlList(dlNode<T>* header,
dlNode<T> *trailer,
const char *sep)
{
assert(header != NULL && trailer != NULL);
dlNode<T> *cursor = header->next;
while(cursor->next != trailer) {
std::cout << cursor->info << sep;
cursor = cursor->next;
}
if (cursor->next = trailer)
std::cout << cursor->info << std::endl;
}
13 dlUtils.h
template <class T>
void deleteNode(dlNode<T>* header,
dlNode<T>* trailer,
dlNode<T>* current)
{
assert(current!= header &&
current != trailer);
dlNode<T> *hold = current;
current->prev->next = current->next;
current->next->prev = current->prev;
delete hold;
} 14 dlUtils.h
template <class T>
void deleteNext(dlNode<T>* header,
dlNode<T>* trailer,
dlNode<T> *current)
{
assert(current != trailer &&
current->next != trailer);
deleteNode(header,trailer, current->next);
} 15 dlUtils.h
template <class T>
void deletePrevious(dlNode<T> * header,
dlNode<T> * trailer,
dlNode<T> *current)
{
assert(current != header &&
current->prev != header);
deleteNode(header, trailer,current->prev);
} 16 dlUtils.h
template <class T>
void clearList(dlNode<T> *p)
{
dlNode<T> *hold = p;
while(p != NULL) {
p = p->next;
delete hold;
hold = p;
}
} 17 The blockdata Definition
// blockdata.h
#include <iostream>
class blockdata {
friend ostream& operator<<(ostream&
const blockdata &);
public:
blockdata(unsigned int s, bool f,
unsigned char *p);
int blocksize;
bool free;
unsigned char *blockptr;
};
18 The blockdata Implementation
// blockdata.cpp
#include "dlUtils.h"
#include "blockdata.h"
#include <iostream>
using namespace std;
blockdata::blockdata(unsigned int s, bool f,
unsigned char *p)
{
blocksize = s;
free = f;
blockptr = p;
}
19 The blockdata Implementation
// blockdata.cpp
ostream &operator << (ostream &out, const
blockdata &B)
{
out << "[" << B.blocksize << ",";
if (B.free)
out << "free";
else
out << "allocated";
out << "]";
return out;
}
20 The MemoryManager Definition
class MemoryManager
{
public:
MemoryManager(unsigned int memsize);
~MemoryManager();
unsigned char *
malloc(unsigned int request);
void free(unsigned char * ptr2block);
void showBlockList(); 21 The MemoryManager Definition
private:
unsigned int memsize;
unsigned char *baseptr;
dlNode<blockdata>* header;
dlNode<blockdata>* trailer; void mergeForward(dlNode<blockdata> *p);
void mergeBackward(dlNode<blockdata> *p);
void splitBlock(dlNode<blockdata> *p,
unsigned int chunksize);
}; 22 The MemoryManager Implementation
MemoryManager::MemoryManager(unsigned int memtotal)
: memsize(memtotal)
{
baseptr = new unsigned char[memsize];
blockdata dummyBlock(0,false,0);
blockdata originalBlock(memsize,true,baseptr);
header = new
dlNode<blockdata>(dummyBlock,nullptr,nullptr);
trailer = new
dlNode<blockdata>(dummyBlock,nullptr,nullptr);
header->next = new
dlNode<blockdata>(originalBlock,header,trailer);
trailer->prev = header->next;
}
23 The MemoryManager Implementation (partial)
void MemoryManager::showBlockList()
{
printDlList(firstBlock,"->");
} 24 The MemoryManager Implementation (partial)
void
MemoryManager::mergeForward(dlNode<blockdata> *p)
{ // Put your code here }
void
MemoryManager::mergeBackward(dlNode<blockdata> *p)
{ // Put your code here } void
MemoryManager::free(unsigned char *ptr2block)
{ // Put your code here } 25 The MemoryManager Implementation (partial)
void
MemoryManager::splitBlock(dlNode<blockdata> *p,
unsigned int chunksize)
{ // Put your code here } unsigned char *
MemoryManager::malloc(unsigned int request)
{ // Put your code here } 26 Visual Trace of Operations The MemoryManager Constructor MemoryManager M(2048);
hea de r p re v b s iz e t ra ile r b p tr 0 next p re v b s iz e 2048
0 0
fr e e fre e f a ls e tr u e b p tr next p re v b s iz e b p tr next 0 0 0
fr e e f a ls e he ad er
t ra ile r
b ase ptr
m e m s iz e 2 048 28 q pre v splitBlock Example
bsize bp tr ne xt 35
true Me m ory Po ol splitBlock(q,20);
q prev bs iz e bptr next pre v bsize 20 15 true true Me m ory Po ol bp tr ne xt hea de r p re v b s iz e t ra ile r bp tr next p re v 0 b s iz e b p tr next p re v 2048 fr e e f re e f a ls e tr u e b p tr next 0 0 0 0 0 b s iz e fr e e f a ls e he ad er
t ra ile r
b ase ptr
m e m s iz e 2 048 unsigned char *p1 = M.malloc(10);
header p re v b s iz e t r a il e r b p tr n e x t 0 p re v b s iz e 10
0 0 b p tr n e x t p re v b s iz e b p tr n e x t p re v b s iz e 20 38 0 fr e e fr e e fr e e fre e fa ls e t ru e fa ls e fa l s e header
tr a il e r
b a s e p tr
m e m siz e 2048 b p tr n e x t 0 0 prev to
header bsize bptr next prev bsize 10 2038 false true bptr next 0 0 to
trailer firstBlock
memsize 2048 baseptr
Memory Pool M unsigned char *p2 = M.malloc(20);
prev bsize bptr next prev bsize bptr next prev bsize 10 20 2018 false false true 0 0 firstBlock
memsize 2048 baseptr
M bptr next Memory Pool p1 = M.malloc(15);
pre v bsize
10 bp tr ne xt prev bs iz e bptr next pre v bsize 20 15 fa ls e false bp tr ne xt prev bs iz e
2003 0 0
true firs tBloc k
m em size 2048 b asep tr
M bptr next Me m ory Po ol true When free is called on p1, we must
merge the resulting consecutive free
blocks to one Block allocated to p1 pre v bsize bp tr ne xt prev 10 bs iz e bptr next pre v bsize 20 15 fa ls e false bp tr ne xt prev bs iz e
2003 0 0
true true firs tBloc k
m em size 2048 b asep tr
Me m ory Po ol M M.free(p1);
prev bsize bptr next prev bsize 10 20 true false bptr next prev bsize 2018
2033 0
true firstBlock
memsize 2048 baseptr
M bptr next Memory Pool bptr next Testing Code #include <iostream>
#include <cassert>
#include "MemoryManager.h"
const char * startlist =
"\n---------BlockList start--------------\n"
const char * endlist =
"\n---------BlockList end-------------\n"
int main()
{
MemoryManager heaper(2048);
cout << "heap initialized\n";
cout << startlist;
cout << heaper << endl;
cout << endlist; 35 cout << "Doing first malloc:\n";
unsigned char * p1 = heaper.malloc(10);
cout << "malloc done\n";
cout << startlist;
cout << heaper << endl;
cout << endlist;
cout << "On to the second malloc\n";
unsigned char *p2 = heaper.malloc(20);
cout << "malloc done\n";
cout << startlist;
cout << heaper << endl;
cout << endlist; 36 cout << "Next free the first pointer\n";
heaper.free(p1);
cout << startlist;
cout << heaper << endl;
cout << endlist;
cout << "Now do a malloc for a block too big for "
<< "the initial open block\n";
p1 = heaper.malloc(15);
cout << "malloc done\n";
cout << startlist;
cout << heaper << endl; n\n";
cout << endlist; 37 cout << "Next free the most recently "
<< "allocated pointer\n";
heaper.free(p1);
cout << startlist;
cout << heaper << endl;
cout << endlist;
cout << "Next free the middle pointer\n";
heaper.free(p2);
cout << startlist;
cout << heaper << endl;
cout << endlist;
return 0;
} 38 Test Output heap initialized
-------------BlockList start-----------------[2048,free]
-------------BlockList end-----------------Executing p1 = malloc(10):
malloc done
-------------BlockList start-----------------[10,allocated] -> [2038,free]
-------------BlockList end-----------------Executing p2 = malloc(20):
malloc done
-------------BlockList start-----------------[10,allocated] -> [20,allocated] -> [2018,free]
-------------BlockList end-----------------40 Executing free(p1):
-------------BlockList start-----------------[10,free] -> [20,allocated] -> [2018,free]
-------------BlockList end-----------------malloc for a block too big for the initial open block
Executing p1 = malloc(15)
malloc done
-------------BlockList start-----------------[10,free] -> [20,allocated] -> [15,allocated]
[2003,free]
-------------BlockList end------------------ -> 41 Next free the most recently allocated pointer (p1)
-------------BlockList start-----------------[10,free] -> [20,allocated] -> [2018,free]
-------------BlockList end-----------------Next free p2
-------------BlockList start-----------------[2048,free]
-------------BlockList end------------------ 42

 

The Memory Manager Project Objectives • The goal of your next project is to simulate the
runtime module used to allocate and de-allocate
dynamic memory.
• This module is known as the "heap manager"
• The "heap" is a large "pool" of memory set aside by
the runtime system
• The two main functions are
– malloc, used to satisfy a request for a specific
number of consecutive blocks;
– free, used to make allocated blocks available f
2 Objectives • The two main heap manager functions are
– malloc, used to satisfy a request for a specific
number of consecutive blocks
malloc returns the address of the first byte of the
allocated memory block
– free, used to make allocated blocks available for use
in future calls to malloc 3 Description
• Our simulation uses
– a large block of unsigned chars as our memory pool; and
– a doubly-linked list to keep track of allocated and
available blocks of unsigned char.
– We will refer to the nodes of this list as blocknodes • The info field of each node is of type blockdata
• An object of type blockdata has attributes
– blocksize number of bytes in the block
– free
a Boolean flag indicating the status of a block
– blockptr a pointer to the first byte of the block 4 malloc
• The malloc algorithm has an int parameter request
• request is the size of the block to be allocated
• request scans the list until it finds the first blocknode
B such that
– B.free == true; and
– B.size request • If no such block is found, malloc returns NULL (0) 5 malloc
• If B.size is larger than request, the block is broken
up into two blocks
– The first block's size: request
– The second's size: B.size-request • This requires that we insert a new blocknode C after B
to reference the second block (which is free)
• Then, whether we split the block or not, we
– set B.free to false
– set B.size to request
– return the address B.bptr 6 malloc
• To create a new blocknode C after B,you must
– create a blockdata object x with the desired values of
free, size and bptr
– call the doubly-linked list function insertAfter(B,x) 7 free
• To implement free(unsigned char *p) we must
find the blocknode whose bptr field equals p
• This is done by traversing the blocknode list
• If this fails, we return NULL (or nullptr)
• Otherwise we change the blocknode's free field to
true
• But we don't stop there 8 Merging Consecutive free Blocks
• It should be clear that we want to maximize the size of
the free blocks
• This means there should never be consecutive free
blocks
• Whenever consecutive free blocks occur, they should
be merged
• When we free a block, we need to check the previous
and next blocks to see if they are free
• If so, we must merge the blocks into one big block
• This may involve the deletion of one or two blocknodes
from our list
9 Merging Consecutive free Blocks
• When checking a previous block to see if it is free, be
sure to check whether there is such a block (not the
first)
• Similarly, when checking a following block, be sure to
check that there is such a block (not the last)
• The MemoryManager class has two methods that you
should implement:
– mergeBackwards
– mergeForward 10 Doubly-Linked List Utilities
• To manage doubly-linked lists, we will use a collection
of templated functions
• We will not need the apparatus of a class here, a
struct suffices
• The definition of dlNode and associated functions will
be supplied in the file dlUtils.h 11 Project Files
• The files used in this project are
•
•
•
• dlUtils.h
blockdata.h
blockdata.cpp
MemoryManager.h Do not modify, do not submit • MemoryManager.cpp
• testMemMgr.cpp Complete and submit
Modify and use for testing;
Do not submit
12 Source Code dlUtils.h
template <class T>
struct dlNode {
T info;
dlNode<T> *prev;
dlNode<T> *next;
dlNode<T>(T val, dlNode<T> *p,
dlNode<T> *n)
:info(val),prev(p),next(n)
{};
};
14 dlUtils.h
template <class T>
void insertAfter(dlNode<T> *first,
dlNode<T> *current, T
newval)
{
assert(first != NULL && current !=
NULL);
current->next = new
dlNode<T>(newval,current,current>next);
current = current->next;
if (current->next != nullptr) 15 dlUtils.h
template <class T>
void deleteNode(DNode<T>* &first, DNode<T>* current)
{
assert(first != NULL && current != NULL);
DNode<T> *hold = current;
if (current == first) {
first = first->next;
first->prev = NULL;
current = first;
} else { // we know that current->prev is not NULL
current->prev->next = current->next;
// But current->next might be NULL
if(current->next != NULL)
current->next->prev = current->prev;
}
delete hold;
} 16 dlUtils.h
template <class T>
void printDlList(DNode<T>* first,
const char *sep )
{
DNode<T> *cursor = first;
while(cursor != NULL && cursor->next!=
NULL)
{
std::cout << cursor->info << sep;
cursor = cursor->next;
}
if (cursor != NULL)
std::cout << cursor->info <<
std::endl; 17 dlUtils.h
template <class T>
void deletePrevious(dlNode<T>* &first,
dlNode<T> *current)
{
assert(first != NULL && current != NULL);
deleteNode(first, current->next);
}
template <class T>
void deletePrevious(DNode<T> * &first,
DNode<T> *current)
{
assert(first != NULL && current != NULL);
deleteNode(first, current->prev);
} 18 The blockdata Definition
#include <iostream>
class blockdata {
friend ostream& operator<<(ostream&
const blockdata
&);
public:
blockdata(int s, bool f, unsigned char
*p);
int blocksize;
bool free;
// pointer to the first byte of the
block:
19
unsigned char* blockptr; The blockdata Implementation
// blockdata.cpp
blockdata::blockdata(int s, bool f,
unsigned char *p)
{
blocksize = s;
free = f;
blockptr = p;
} 20 The blockdata Implementation
// blockdata.cpp
std::ostream &operator<<(std::ostream
&out,
const blockdata
&B)
{
std::out << "[" << B.blocksize << ",";
if (B.free)
std::out << "free";
else
out << "allocated";
out << "]"; 21 The MemoryManager Definition
class MemoryManager
{
public:
MemoryManager(unsigned int memsize);
unsigned char * malloc(unsigned int request);
// On failure, returns nullptr or NULL
void free(unsigned char * memptr);
void showBlockList(); 22 private:
unsigned int memsize; // Heap size
// pointer to the first byte of the
heap:
unsigned char *baseptr;
dlNode<blockdata> *firstBlock;
// Utility methods for free function:
void mergeBackward(dlNode<blockdata>
*p);
void mergeForward(dlNode<blockdata> *p);
// Utility method for malloc function:
void splitBlock(dlNode<blockdata> *p,
23
unsigned int chunksize); The MemoryManager Implementation
#include
#include
#include
#include <cassert>
<iostream>
"dlUtils.h“
"MemoryManager.h" MemoryManager::MemoryManager(
unsigned int memtotal): memsize(memtotal)
{
baseptr = new unsigned char[memsize];
blockdata originalBlock(memsize,true,baseptr);
firstBlock = new dlNode<blockdata>(
originalBlock,nullptr,nullptr);
} 24 The MemoryManager Implementation (partial)
void MemoryManager::showBlockList()
{
printDlList(firstBlock,"->");
}
void
MemoryManager::mergeBackward(dlNode<blockdata> *p)
{ // Put your code here }
void
MemoryManager::mergeForward(dlNode<blockdata> *p)
{ // Put your code here }
void
MemoryManager::free(unsigned char *ptr2block)
{// Put your code here }
25 The MemoryManager Implementation (partial)
void
MemoryManager::splitBlock(dlNode<blockdata> *p,
unsigned int chunksize)
{ // Put your code here }
unsigned char *
MemoryManager::malloc(unsigned int request)
{ // Put your code here } 26 Visual Trace of Operations The MemoryManager Constructor MemoryManager M(2048);
prev bsize
2048 0 bptr next
0 true
free
firstBlock
memsize 2048 baseptr
M Memory Pool 28 q pre v splitBlock Example
bsize bp tr ne xt 35
true Me m ory P o ol splitBlock(q,20);
q prev bs iz e bptr next pre v bsize 20 15 true true Me m ory Po ol bp tr ne xt prev bsize
2048 0 bptr next
0 true
free
firstBlock
memsize 2048 baseptr
Memory Pool M unsigned char *p1 = M.malloc(10);
prev bsize bptr next prev bsize 10 2038 false true 0 bpt r next
0 firstBlock
memsize 2048 baseptr
M Memory Pool prev bsize bptr next prev 10 bsize bptr next 2038 0 0
false true firstBlock
memsize 2048 baseptr
Memory Pool M unsigned char *p2 = M.malloc(20);
prev bsize
10 bptr next prev bsize bptr next prev 20 bsize
2018 0 0
false false true firstBlock
memsize 2048 baseptr
M bptr next Memory Pool p1 = M.malloc(15);
pre v
0 bsize
10
true bp tr ne xt prev bs iz e bptr next pre v 20 15 fa ls e false firs tBloc k
m em size 2048 b asep tr
M bsize Me m ory Po ol bp tr ne xt prev bs iz e
2003
true bptr next
0 When free is called on p1, we must
merge the resulting consecutive free
blocks to one Block allocated to p1 pre v
0 bsize bp tr ne xt prev 10
true bs iz e bptr next pre v bsize 20 15 fa ls e false bp tr ne xt true 2048 b asep tr
Me m ory Po ol M M.free(p1);
prev bsize bptr next prev bsize 10 20 true false bptr next prev bsize 2018
2033 0
true firstBlock
memsize 2048 baseptr
M Memory Pool bs iz e
2003 firs tBloc k
m em size prev bptr next bptr next
0 Testing Code #include <iostream>
#include <cassert>
#include "MemoryManager.h"
const char * startlist =
"\n---------BlockList start--------------\n"
const char * endlist =
"\n---------BlockList end-------------\n"
int main()
{
MemoryManager heaper(2048);
cout << "heap initialized\n";
cout << startlist;
cout << heaper << endl;
cout << endlist; 35 cout << "Doing first malloc:\n";
unsigned char * p1 = heaper.malloc(10);
cout << "malloc done\n";
cout << startlist;
cout << heaper << endl;
cout << endlist;
cout << "On to the second malloc\n";
unsigned char *p2 = heaper.malloc(20);
cout << "malloc done\n";
cout << startlist;
cout << heaper << endl;
cout << endlist; 36 cout << "Next free the first pointer\n";
heaper.free(p1);
cout << startlist;
cout << heaper << endl;
cout << endlist;
cout << "Now do a malloc for a block too big for "
<< "the initial open block\n";
p1 = heaper.malloc(15);
cout << "malloc done\n";
cout << startlist;
cout << heaper << endl; n\n";
cout << endlist; 37 cout << "Next free the most recently "
<< "allocated pointer\n";
heaper.free(p1);
cout << startlist;
cout << heaper << endl;
cout << endlist;
cout << "Next free the middle pointer\n";
heaper.free(p2);
cout << startlist;
cout << heaper << endl;
cout << endlist;
return 0;
} 38 Test Output heap initialized
-------------BlockList start-----------------[2048,free]
-------------BlockList end-----------------Executing p1 = malloc(10):
malloc done
-------------BlockList start-----------------[10,allocated] -> [2038,free]
-------------BlockList end-----------------Executing p2 = malloc(20):
malloc done
-------------BlockList start-----------------[10,allocated] -> [20,allocated] -> [2018,free]
-------------BlockList end-----------------40 Executing free(p1):
-------------BlockList start-----------------[10,free] -> [20,allocated] -> [2018,free]
-------------BlockList end-----------------malloc for a block too big for the initial open block
Executing p1 = malloc(15)
malloc done
-------------BlockList start-----------------[10,free] -> [20,allocated] -> [15,allocated]
[2003,free]
-------------BlockList end------------------ -> 41 Next free the most recently allocated pointer (p1)
-------------BlockList start-----------------[10,free] -> [20,allocated] -> [2018,free]
-------------BlockList end-----------------Next free p2
-------------BlockList start-----------------[2048,free]
-------------BlockList end------------------ 42

Attachments:

• 1493718869-MemoryManagerCode.zip
• 1493718871-06_MemoryManagerProject.pdf