Buddy Memory Allocation Program how to delete

Hello Everyone,

I am writing a Linked List Buddy Memory Allocation Program.  It is more of a simulation of a buddy memory allocation program there is no actual memory tampering.  I have a list the size of 8 blocks.  One block is initialized to 256 which is the largest allocatable block.  I have two lists one is FreeList which is the block initialized with 256 and AllocatedList which will hold the numerical value that is allocated from the FreeList. Also the blocks are allocated by 2 to the power 0 - 2 to the power of 7(That is why there are 8 blocks).   If the user enter in some value the AllocatedList class will find the block in FreeList which has the closest value to the user input.  For example, if the user enter a value of 52 the allocated block size will be 64.  What I am stuck on is how can I let the user enter in a value to delete memory and free up the block size that is closest to the value and combine any other blocks that are free with the newly free block.  The thing is all of the blocks must have a number ranging from 1-32, 33-65.  For every block that is getting split the numbers should keep on increasing.  So the only values that can be combined are the numbers that are sequential next to each other.  I am confused on how I can implement this into my code.  Any help would be greatly appreciated.
``````FreeList.h-------------------------------------------------

#ifndef FREELIST_H
#define FREELIST_H

class FreeList
{

public:
FreeList(int, int);
FreeList(int);
FreeList();
int getBlockSize();
void setBlockSize(int);
void setOrderNumber(int);
int getOrderNumber();

void setLeftBlock(int);
void setRightBlock(int);

int getLeftBlock();
int getRightBlock();

bool operator<(FreeList&);
bool operator<=(FreeList&);
bool operator==(FreeList&);
bool operator==(int);

private:

int sizeOfBlock;
int orderNumber;
int leftBlock;
int rightBlock;

};
#endif

Freelist.cpp---------------------------------------------

#include<iostream>
#include<string>
#include<list>
#include<vector>

using namespace std;

#include"FreeList.h"

FreeList::FreeList(int size, int seqNumber)
{
setBlockSize(size);
setOrderNumber(seqNumber);

setLeftBlock(size);
setRightBlock(0);

}

FreeList::FreeList(int size)
{
sizeOfBlock = size;

}

FreeList::FreeList()
{
sizeOfBlock =0;

}

bool FreeList::operator<=(FreeList &list)
{

return getBlockSize() <= list.getBlockSize();
}

bool FreeList::operator==(FreeList &list)
{
return getBlockSize() == list.getBlockSize();

}

bool FreeList::operator==(int amountOfMemory)
{

return amountOfMemory == getBlockSize();

}

bool FreeList::operator<(FreeList &list)
{
return getBlockSize() < list.getBlockSize();
}

void FreeList::setBlockSize(int amountOfMemory)
{
sizeOfBlock = amountOfMemory;
}

int FreeList::getBlockSize()
{
return sizeOfBlock;
}

void FreeList::setOrderNumber(int seqNumber)
{
orderNumber = seqNumber;

}

int FreeList::getOrderNumber()
{
return orderNumber;
}

void FreeList::setLeftBlock(int size)
{
leftBlock = size;
}

void FreeList::setRightBlock(int size)
{
rightBlock = size;
}

int FreeList::getLeftBlock()
{
return leftBlock;
}

int FreeList::getRightBlock()
{
return rightBlock;
}

AllocatedList.h--------------------------------------------

#ifndef ALLOCATEDLIST_H
#define ALLOCATEDLIST_H

#include<iostream>
#include<string>
#include<list>

using namespace std;

#include"FreeList.h"

class AllocatedList
{
friend ostream &operator<<(ostream&,FreeList&);
public:
AllocatedList();
void checkMemory(int);
void deleteMemory(int);
static bool compareSizeOfBlocks(int&, FreeList&);

bool greater_than_amountOfMemory(int,FreeList);

private:
list<int>listOfMemory;
list<FreeList> listOfFreeList;
int totalMemory;
int memoryAllocated;
list<FreeList>allocatedList;

};
#endif

AllocatedList.cpp------------------------------------------

#include<iostream>
#include<vector>
#include<list>
#include<algorithm>

using namespace std;

#include"AllocatedList.h"

AllocatedList::AllocatedList()
{
totalMemory = 256;
memoryAllocated = 0;
//Defining the Free List
FreeList twoPow7(256,0);
FreeList twoPow6(0,1);
FreeList twoPow5(0,2);
FreeList twoPow4(0,3);
FreeList twoPow3(0,4);
FreeList twoPow2(0,5);
FreeList twoPow1(0,6);
FreeList twoPow0(0,7);

//Add each element to the Linked List
listOfFreeList.push_back(twoPow7);
listOfFreeList.push_back(twoPow6);
listOfFreeList.push_back(twoPow5);
listOfFreeList.push_back(twoPow4);
listOfFreeList.push_back(twoPow3);
listOfFreeList.push_back(twoPow2);
listOfFreeList.push_back(twoPow1);
listOfFreeList.push_back(twoPow0);

allocatedList.assign(8,0);

}

bool AllocatedList::compareSizeOfBlocks(int& amountOfMemory, FreeList& listOfFreeList)
{

return amountOfMemory <= listOfFreeList.getBlockSize();

}

void AllocatedList::checkMemory(int amountOfMemory)
{
list<FreeList>::iterator current;
list<FreeList>::iterator next;
vector<int> vectorFreeList;

list<FreeList>::iterator IterFreeList;

for(IterFreeList=listOfFreeList.begin(); IterFreeList!=listOfFreeList.end(); IterFreeList++)
{
if(IterFreeList->getLeftBlock() >= amountOfMemory || IterFreeList->getRightBlock() >= amountOfMemory)
vectorFreeList.push_back(IterFreeList->getOrderNumber());
//Get the order number from the object

else
continue;
}

//sort vectorFreeList so the lowest order # object is first
sort(vectorFreeList.begin(), vectorFreeList.end());

reverse(vectorFreeList.begin(), vectorFreeList.end());

//Add the memory to the allocated list
listOfMemory.push_back(amountOfMemory);

//create a new iterator and advance it to the lowest
//order number object

current = listOfFreeList.begin();

next = current;

for(;next != listOfFreeList.end(); next++, current++)
{

if(current->getLeftBlock()> amountOfMemory && current->getRightBlock() < amountOfMemory)
{
//left side of the nodes

if((current->getLeftBlock()/2) >= amountOfMemory)
{
//current is pointing to the first object with an amount
//greater than amountOfMemory
current->setLeftBlock((current->getLeftBlock()/2));
current->setRightBlock((current->getLeftBlock()));

if(current->getRightBlock()/2 >= amountOfMemory)
{
next->setLeftBlock(current->getRightBlock());
next->setRightBlock(current->getRightBlock());
current->setRightBlock(0);
}

}

else if ((current->getLeftBlock()/2) < amountOfMemory)
{
memoryAllocated = current->getLeftBlock();

list<FreeList>::iterator iterAllocatedList=allocatedList.begin();

iterAllocatedList ->setLeftBlock(current->getLeftBlock());

current->setLeftBlock(0);

break;

}

}

//Right values for the nodes

if(current->getRightBlock()>= amountOfMemory)
{

if((current->getRightBlock()/2) >= amountOfMemory)
{
//current is pointing to the first object with an amount
//greater than amountOfMemory
current->setLeftBlock(current->getRightBlock()/2);
current->setRightBlock((current->getLeftBlock()));

if(current->getRightBlock()/2 >= amountOfMemory)
{
next->setLeftBlock(current->getRightBlock());
next->setRightBlock(current->getRightBlock());
current->setRightBlock(0);
}

}

else if ((current->getRightBlock()/2) < amountOfMemory)
{
memoryAllocated = current->getRightBlock();

list<FreeList>::iterator iterAllocatedList=allocatedList.begin();

iterAllocatedList ->setBlockSize(current->getRightBlock());

current->setRightBlock(0);

break;

}

}

else
{continue;}

}//END OF FOR

if(totalMemory != 0)
{
totalMemory -= memoryAllocated;
}

else
{
cout<<"You Must Free Up Some Memory!!!"<<endl;
}

vectorFreeList.erase(vectorFreeList.begin(), vectorFreeList.end());
}//end of function

void AllocatedList:: deleteMemory(int amountOfMemory)
{
list<FreeList>::iterator deleteIterator = listOfFreeList.begin();

}

ostream &operator<<(ostream& output , FreeList &list)
{
output<<list.getBlockSize()<<endl;

return output;

}

bool AllocatedList::greater_than_amountOfMemory(int amountOfMemory,FreeList list)
{
return amountOfMemory<= list.getBlockSize();

}

/*bool AllocatedList::compare_Order_Numbers(FreeList item1, FreeList item2)
{
return item1.getOrderNumber() < item2.getOrderNumber();

}*/

Main.cpp-------------------------------------------------

#include<iostream>
#include<vector>
#include<list>
#include<string>
#include<algorithm>

using namespace std;

#include"FreeList.h"
#include"AllocatedList.h"

int main()
{
string response;

AllocatedList allocatedList;

int memory;

cout<<"***********BUDDY MEMORY PROGRAM**********\n"<<endl;

while(response != "NO")
{

cout<<"Enter In The Amount Of Memory You Would Like To Allocate\n"<<endl;

cin>>memory;

if((memory <= 0) || (memory > 256))
{
while((memory <= 0) || (memory > 256))
{
cout<<"Oops, Please Enter In An Amount Between '2 - 256' \n"<<endl;

cin>>memory;

}//End Of While

}//End Of If

allocatedList.checkMemory(memory);

cout<<"Would You Like To Continue?\n"<<endl;

cout<<"Enter 'YES' Or 'NO'\n"<<endl;

cin>>response;

}//End of While

return 0;
}//End Of Main``````
Infinity08

Your description of the assignment is quite confusing. Could you post the exact text of the assignment please ?

For what follows, I'll assume the normal buddy allocation algorithm with a pool of 256 blocks of size 8kB (or whichever unit it is)

>> What I am stuck on is how can I let the user enter in a value to delete memory and free up the block size that is closest to the value and combine any other blocks that are free with the newly free block.

You don't have to calculate the block size that is closest.

Instead, the user will give you the IDENTIFIER of the allocated block. You can see that identifier as the address of the memory block. Using the identifier, you can easily retrieve it in the allocated list, and can easily figure out which block it corresponds to in the free list.

Btw : is having two separate lists a requirement that you were given ? Or can you keep everything in one list ? I think I'd prefer the latter.

>> The thing is all of the blocks must have a number ranging from 1-32, 33-65.

That's one of the confusing aspects in your description. It doesn't seem to match the values you gave earlier. So it would be good to post the exact text of the assignment here.
brich744

Here is the actual assignment description:

Buddy Memory Allocation Algorithm

In this programming assignment we will implement a variant of the buddy memory allocation algorithm/technique. The buddy memory allocation technique is one of the memory allocation techniques used by operating systems to allocate memory to programs for storing variables, etc. You can read more about the buddy memory allocation technique in any operating systems textbook. Some websites discussing this topic are:
•      http://www.memorymanagement.org/articles/alloc.html
•      http://en.wikipedia.org/wiki/Buddy_memory_allocation
•      http://www.economicexpert.com/a/Memory:allocation.htm
•      https://umdrive.memphis.edu/blstuart/htdocs/excerpt3.pdf

The buddy memory allocation technique allocates memory in blocks of sizes in powers of 2. If the system has 300KB of physical memory, then the largest allocatable block size is 256KB.Therefore, for the purposes of this homework, we will assume that when the program starts there is a single block of memory of size 256KB which is the largest allocatable block size. Let the smallest allocatable block size be 2KB. Block sizes will be in powers of 2.

Usually the buddy memory allocation algorithm is implemented using binary trees. However, in this homework we will implement the buddy memory allocation algorithm using an array of free lists having one entry for each allowable block size. Therefore the size of this array is 8. Similarly, we will also have an array of allocated lists. Array entry at index i in the array of free lists points to a linked list of free blocks of size 2i+1; array entry at index i in the array of allocated lists points to a linked list of allocated blocks of size 2i+1.

If a program requests memory of size x KB, find the smallest k such that x < 2k. If such a block is free, allocate it. If not, find the next larger block that is free and split it. If the split block is of size 2k allocate it, otherwise repeat the steps until you get a free block of size 2k. If a block of size 2k cannot be allocated print an appropriate message. When blocks are split, add them to the appropriate linked list in the array.

Your program must ask the user to input the request for memory in the range 1-256KB – be forgiving of erroneous input from the user. You must custom-design your own linked list class and any additional classes that you wish; however, you may refer to the author’s implementation for guidance. Before the user enters his/her request, output the array of free lists and after processing the user’s request output the array of allocated lists. Your display format should be user friendly. The user must be allowed to enter as many requests as (s)he wishes – one at a time.

Extra Credit (100 points): Allow for blocks to be coalesced when the requesting programs free the memory allotted to them. For additional details on this part, talk to the instructor.
Ok, that's slightly different from how your initial post described it :)

So, you have a total memory size of 256kB, and a minimal block size of 2kB.

Other than those values, the advice in my first post is still valid.

For de-allocating a block of allocated memory, ask the user for the identifier for that block of memory, and then move it back to the free list.

I have changed the code around but I am still having a hard time figuring out how to give each block a numerical range of 32  for each block of memory allocated.  I am trying to do this so when the user delete memory that the blocks can be combined if the numerical range of 32 are in sequential order.  I have figured out the worst case of different numerical range of 32 blocks are need.  The number range is 1-80,167.  For every node in the linked list I have already put the range  of each node.

FreeList twoPow7(256,0, 256,1, 32 );
FreeList twoPow6(0,1, 128, 33, 97 );
FreeList twoPow5(0,2, 64, 98, 226);
FreeList twoPow4(0,3,32, 227, 483 );
FreeList twoPow3(0,4,16, 484, 996 );
FreeList twoPow2(0,5,8,997, 2021 );
FreeList twoPow1(0,6,4,2022, 4070);
FreeList twoPow0(0,7,2,4076, 80167);

The last two parameters are the ranges that I am talking about.  I am stuck on this part I am trying to figure out how to get past this part.  It is the extra credit in the description.
``````FreeList.h---------------------------------------------------------

#ifndef FREELIST_H
#define FREELIST_H

class FreeList
{

public:
FreeList(int, int, int, int, int);
FreeList(int);
FreeList();
int getBlockSize();
void setBlockSize(int);
void setOrderNumber(int);
int getOrderNumber();

void setBlockValue(int);
int getBlockValue();
int getSizeOfList();
void setSizeOfList(int);

static void setBlockRange();

bool operator<(FreeList&);
bool operator<=(FreeList&);
bool operator==(FreeList&);
bool operator==(int);

list<FreeList> quantiyOfValue;

private:

int sizeOfBlock;
int orderNumber;
int blockValue;

int begin_rangeOfBlocks;
int end_rangeOfBlocks;

};
#endif

FreeList.cpp-----------------------------------------------------

#include<iostream>
#include<string>
#include<list>
#include<vector>

using namespace std;

#include"FreeList.h"

FreeList::FreeList(int size, int seqNumber, int value, int begin, int end)
{
setBlockSize(size);
setOrderNumber(seqNumber);

setBlockValue(value);

begin_rangeOfBlocks = begin;
end_rangeOfBlocks = end;

}

FreeList::FreeList(int size)
{
sizeOfBlock = size;

}

FreeList::FreeList()
{
sizeOfBlock =0;

}

bool FreeList::operator<=(FreeList &list)
{

return getBlockSize() <= list.getBlockSize();
}

bool FreeList::operator==(FreeList &list)
{
return getBlockSize() == list.getBlockSize();

}

bool FreeList::operator==(int amountOfMemory)
{

return amountOfMemory == getBlockSize();

}

bool FreeList::operator<(FreeList &list)
{
return getBlockSize() < list.getBlockSize();
}

void FreeList::setBlockSize(int amountOfMemory)
{
sizeOfBlock = amountOfMemory;
}

int FreeList::getBlockSize()
{
return sizeOfBlock;
}

void FreeList::setOrderNumber(int seqNumber)
{
orderNumber = seqNumber;

}

int FreeList::getOrderNumber()
{
return orderNumber;
}

void FreeList::setBlockValue(int value)
{
blockValue = value;

}

int FreeList::getBlockValue()
{

return blockValue;
}

int FreeList::getSizeOfList()
{

return quantiyOfValue.size();
}

void FreeList::setBlockRange()
{

}

AllocatedList.h-------------------------------------------------

#ifndef ALLOCATEDLIST_H
#define ALLOCATEDLIST_H

#include<iostream>
#include<string>
#include<list>

using namespace std;

#include"FreeList.h"

class AllocatedList
{
friend ostream &operator<<(ostream&,FreeList&);
public:
AllocatedList();
void checkMemory(int);
void deleteMemory(int);
static bool compareSizeOfBlocks(int&, FreeList&);
bool availableMemory(int);
bool greater_than_amountOfMemory(int,FreeList);

private:
list<int>listOfMemory;
list<FreeList> listOfFreeList;
int totalMemory;
int memoryAllocated;
list<FreeList>allocatedList;

};
#endif

AllocatedList.cpp----------------------------------------------

#include<iostream>
#include<vector>
#include<list>
#include<algorithm>

using namespace std;

#include"AllocatedList.h"

AllocatedList::AllocatedList()
{
totalMemory = 256;
memoryAllocated = 0;
//Defining the Free List
FreeList twoPow7(256,0, 256,1, 32 );
FreeList twoPow6(0,1, 128, 33, 97 );
FreeList twoPow5(0,2, 64, 98, 226);
FreeList twoPow4(0,3,32, 227, 483 );
FreeList twoPow3(0,4,16, 484, 996 );
FreeList twoPow2(0,5,8,997, 2021 );
FreeList twoPow1(0,6,4,2022, 4070);
FreeList twoPow0(0,7,2,4076, 80167);

//Add each element to the Linked List
listOfFreeList.push_back(twoPow7);
listOfFreeList.push_back(twoPow6);
listOfFreeList.push_back(twoPow5);
listOfFreeList.push_back(twoPow4);
listOfFreeList.push_back(twoPow3);
listOfFreeList.push_back(twoPow2);
listOfFreeList.push_back(twoPow1);
listOfFreeList.push_back(twoPow0);

allocatedList.assign(8,0);

}

bool AllocatedList::compareSizeOfBlocks(int& amountOfMemory, FreeList& listOfFreeList)
{

return amountOfMemory <= listOfFreeList.getBlockSize();

}

void AllocatedList::checkMemory(int amountOfMemory)
{
list<FreeList>::iterator current;
list<FreeList>::iterator next;
vector<int> vectorFreeList;

list<FreeList>::iterator IterFreeList;

for(IterFreeList=listOfFreeList.begin(); IterFreeList!=listOfFreeList.end(); IterFreeList++)
{
if(IterFreeList->getBlockValue() >= amountOfMemory)
vectorFreeList.push_back(IterFreeList->getOrderNumber());
//Get the order number from the object

else
continue;
}

//sort vectorFreeList so the lowest order # object is first
sort(vectorFreeList.begin(), vectorFreeList.end());

reverse(vectorFreeList.begin(), vectorFreeList.end());

//Add the memory to the allocated list
listOfMemory.push_back(amountOfMemory);

//create a new iterator and advance it to the lowest
//order number object

current = listOfFreeList.begin();

current->quantiyOfValue.push_back(current->getBlockValue());

memoryAllocated = current->getBlockValue();

list<FreeList>::iterator allocatedIter;
allocatedIter = allocatedList.begin();

allocatedIter->setBlockValue(current->getBlockValue());

if(totalMemory != 0)
{
totalMemory -= memoryAllocated;
}

else
{
cout<<"You Must Free Up Some Memory!!!"<<endl;
}

vectorFreeList.erase(vectorFreeList.begin(), vectorFreeList.end());
}//end of function

ostream &operator<<(ostream& output , FreeList &list)
{
output<<list.getBlockSize()<<endl;

return output;

}

bool AllocatedList::greater_than_amountOfMemory(int amountOfMemory,FreeList list)
{
return amountOfMemory<= list.getBlockSize();

}

bool AllocatedList::availableMemory(int memory)
{
}

void AllocatedList::deleteMemory(int memory)
{

list<FreeList>::iterator current;

vector<int> vectorFreeList;

list<FreeList>::iterator IterFreeList;

for(IterFreeList=listOfFreeList.begin(); IterFreeList!=listOfFreeList.end(); IterFreeList++)
{
if(IterFreeList->getBlockValue() >= memory)
vectorFreeList.push_back(IterFreeList->getOrderNumber());
//Get the order number from the object

else
continue;
}

//sort vectorFreeList so the lowest order # object is first
sort(vectorFreeList.begin(), vectorFreeList.end());

reverse(vectorFreeList.begin(), vectorFreeList.end());

//create a new iterator and advance it to the lowest
//order number object

current = listOfFreeList.begin();

if(current->quantiyOfValue.size() > 0)
current->quantiyOfValue.pop_back();

else
{
reverse(vectorFreeList.begin(), vectorFreeList.end());
list<FreeList>::iterator deleteIterator = allocatedList.begin();

deleteIterator->setBlockValue(0);

memoryAllocated = current->getBlockValue();

if(totalMemory <= 256)
{
totalMemory += memoryAllocated;
}

}}

Main.cpp-------------------------------------------------------

#include<vector>
#include<list>
#include<string>
#include<algorithm>

using namespace std;

#include"FreeList.h"
#include"AllocatedList.h"

int main()
{
string response;

AllocatedList allocatedList;

int memory;
int choice;

while(response != "NO")
{
cout<<"***********BUDDY MEMORY PROGRAM**********\n"<<endl;

cout<<"1. Allocate Memory"<<endl;
cout<<"2. Delete Memory"<<endl;
cout<<"Enter in corresponding number"<<endl;
cin>>choice;

if(choice == 1)
{
cout<<"Enter In The Amount Of Memory You Would Like To Allocate\n"<<endl;

cin>>memory;

if(allocatedList.availableMemory(memory))
{
allocatedList.checkMemory(memory);

if((memory <= 0) || (memory > 256))
{
while((memory <= 0) || (memory > 256))
{
cout<<"Oops, Please Enter In An Amount Between '2 - 256' \n"<<endl;

cin>>memory;

}//End Of While

}//End Of If

}

else

cout<<"You Must Free Up Space To Allocate A Block Size Of  "<<memory<<endl;
}

else if(choice==2)
{
cout<<"How Much Memory Would You Like To Delete"<<endl;
cin>>memory;

if((memory <= 0) || (memory > 256))
{
while((memory <= 0) || (memory > 256))
{
cout<<"Oops, Please Enter In An Amount Between '2 - 256' \n"<<endl;

cin>>memory;
}}

allocatedList.deleteMemory(memory);

}

cout<<"Would You Like To Continue?\n"<<endl;

cout<<"Enter 'YES' Or 'NO'\n"<<endl;

cin>>response;

}//End of While

return 0;
}//End Of Main``````
>> I have changed the code around but I am still having a hard time figuring out how to give each block a numerical range of 32  for each block of memory allocated.

Ok. Look at the identifiers as addresses eg.

So, if you split up the 256kB of memory into 2kB blocks, then you have 128 different blocks. You can give each of these blocks a numerical identifier (its address if you wish). The first would have identifier 0, the second 1, etc. until the last one which has identifier 127.

For bigger memory blocks, you can use the same addresses. For example :

the blocks of 4kB would have identifiers 0, 2, 4, 6, etc. up till 126.
the blocks of 8kB would have identifiers 0, 4, 8, 12, etc. up till 124.
the blocks of 16kB would have identifiers 0, 8, 16, 24, etc. up till 120.
etc.
the two blocks of 128kB would have identifiers 0 and 64.
the single block of 256kB would have identifier 0.

So, given two values (the identifier and the size of the block), you can uniquely identify which block it is. For example, you could say : the 8kB block with identifier 12.

I'm not sure whether that is what your instructor is referring to, but that's how I would do it. (actually I'd use a single tree rather than two lists, but that's clearly a constraint imposed by the assignment).

Ok, what I am having trouble with is how to dynamically allocate the identifiers to each blocks.  I could do it by brute force but I know my professor would take off considerably.  Here is my revised code.  I have changed the AllocatedList.cpp, and added a function called setBlockRange().

``````FreeList.h--------------------------------------------------------

#ifndef FREELIST_H
#define FREELIST_H

class FreeList
{

public:
FreeList(int, int, int, int, int);
FreeList(int, int, int);
FreeList(int);
FreeList();

int getBlockSize();
void setBlockSize(int);
void setOrderNumber(int);
int getOrderNumber();

void setBlockValue(int);
int getBlockValue();
int getSizeOfList();
void setSizeOfList(int);

int setBlockRange();

bool operator<(FreeList&);
bool operator<=(FreeList&);
bool operator==(FreeList&);
bool operator==(int);

list<int> quantiyOfValue;

private:

int sizeOfBlock;
int orderNumber;
int blockValue;

int begin_rangeOfBlocks;
int end_rangeOfBlocks;

};
#endif

FreeList.cpp-----------------------------------------------------

#include<iostream>
#include<string>
#include<list>
#include<vector>
#include<stack>

using namespace std;

#include"FreeList.h"

FreeList::FreeList(int size, int seqNumber, int value, int begin, int end)
{
setBlockSize(size);
setOrderNumber(seqNumber);

setBlockValue(value);

begin_rangeOfBlocks = begin;
end_rangeOfBlocks = end;

}

FreeList::FreeList(int value, int begin, int end)
{
begin_rangeOfBlocks = begin;
end_rangeOfBlocks = end;

setBlockValue(value);

setBlockRange();
}

FreeList::FreeList(int size)
{
sizeOfBlock = size;

}

FreeList::FreeList()
{
sizeOfBlock =0;

}

bool FreeList::operator<=(FreeList &list)
{

return getBlockSize() <= list.getBlockSize();
}

bool FreeList::operator==(FreeList &list)
{
return getBlockSize() == list.getBlockSize();

}

bool FreeList::operator==(int amountOfMemory)
{

return amountOfMemory == getBlockSize();

}

bool FreeList::operator<(FreeList &list)
{
return getBlockSize() < list.getBlockSize();
}

void FreeList::setBlockSize(int amountOfMemory)
{
sizeOfBlock = amountOfMemory;
}

int FreeList::getBlockSize()
{
return sizeOfBlock;
}

void FreeList::setOrderNumber(int seqNumber)
{
orderNumber = seqNumber;

}

int FreeList::getOrderNumber()
{
return orderNumber;
}

void FreeList::setBlockValue(int value)
{
blockValue = value;

}

int FreeList::getBlockValue()
{

return blockValue;
}

int FreeList::getSizeOfList()
{

return quantiyOfValue.size();
}

int FreeList::setBlockRange()
{
begin_rangeOfBlocks += (32 * quantiyOfValue.size())-1;

return begin_rangeOfBlocks;

}

AllocatedList.h-------------------------------------------------

#ifndef ALLOCATEDLIST_H
#define ALLOCATEDLIST_H

#include<iostream>
#include<string>
#include<list>

using namespace std;

#include"FreeList.h"

class AllocatedList
{
friend ostream &operator<<(ostream&,FreeList&);
public:
AllocatedList();
void checkMemory(int);
void deleteMemory(int);
static bool compareSizeOfBlocks(int&, FreeList&);
bool availableMemory(int);
bool greater_than_amountOfMemory(int,FreeList);

private:
list<int>listOfMemory;
list<FreeList> listOfFreeList;
int totalMemory;

list<FreeList>allocatedList;

};
#endif

AllocatedList.cpp-------------------------------------------------

#include<iostream>
#include<vector>
#include<list>
#include<stack>
#include<algorithm>

using namespace std;

#include"AllocatedList.h"
#include"FreeList.h"

AllocatedList::AllocatedList()
{
totalMemory = 256;

//Defining the Free List
FreeList twoPow7(256,0, 256,1, 32 );
FreeList twoPow6(0,1, 128, 33, 97 );
FreeList twoPow5(0,2, 64, 98, 226);
FreeList twoPow4(0,3,32, 227, 483 );
FreeList twoPow3(0,4,16, 484, 996 );
FreeList twoPow2(0,5,8,997, 2021 );
FreeList twoPow1(0,6,4,2022, 4070);
FreeList twoPow0(0,7,2,4076, 80167);

//Add each element to the Linked List
listOfFreeList.push_back(twoPow7);
listOfFreeList.push_back(twoPow6);
listOfFreeList.push_back(twoPow5);
listOfFreeList.push_back(twoPow4);
listOfFreeList.push_back(twoPow3);
listOfFreeList.push_back(twoPow2);
listOfFreeList.push_back(twoPow1);
listOfFreeList.push_back(twoPow0);

allocatedList.push_back(twoPow7);
allocatedList.push_back(twoPow6);
allocatedList.push_back(twoPow5);
allocatedList.push_back(twoPow4);
allocatedList.push_back(twoPow3);
allocatedList.push_back(twoPow2);
allocatedList.push_back(twoPow1);
allocatedList.push_back(twoPow0);

}

bool AllocatedList::compareSizeOfBlocks(int& amountOfMemory, FreeList& listOfFreeList)
{

return amountOfMemory <= listOfFreeList.getBlockSize();

}

void AllocatedList::checkMemory(int amountOfMemory)
{
list<FreeList>::iterator current;
list<FreeList>::iterator next;
vector<int> vectorFreeList;

int memoryAllocated=0;

list<FreeList>::iterator IterFreeList;

for(IterFreeList=listOfFreeList.begin(); IterFreeList!=listOfFreeList.end(); IterFreeList++)
{
if(IterFreeList->getBlockValue() >= amountOfMemory)
vectorFreeList.push_back(IterFreeList->getOrderNumber());
//Get the order number from the object

else
continue;
}

//sort vectorFreeList so the lowest order # object is first
sort(vectorFreeList.begin(), vectorFreeList.end());

reverse(vectorFreeList.begin(), vectorFreeList.end());

//Add the memory to the allocated list
listOfMemory.push_back(amountOfMemory);

//create a new iterator and advance it to the lowest
//order number object

current = listOfFreeList.begin();

//Add to inner list

current->quantiyOfValue.push_back(current->setBlockRange());

memoryAllocated = current->getBlockValue();

list<FreeList>::iterator allocatedIter;
allocatedIter = allocatedList.begin();

allocatedIter->setBlockValue(current->getBlockValue());

if(totalMemory != 0)
{
totalMemory -= current->getBlockValue();
}

else
{
cout<<"You Must Free Up Some Memory!!!"<<endl;
}

vectorFreeList.erase(vectorFreeList.begin(), vectorFreeList.end());
}//end of function

ostream &operator<<(ostream& output , FreeList &list)
{
output<<list.getBlockSize()<<endl;

return output;

}

bool AllocatedList::greater_than_amountOfMemory(int amountOfMemory,FreeList list)
{
return amountOfMemory<= list.getBlockSize();

}

bool AllocatedList::availableMemory(int memory)
{
}

void AllocatedList::deleteMemory(int memory)
{
int memoryAllocated = 0;

list<FreeList>::iterator current;

vector<int> vectorFreeList;

list<FreeList>::iterator IterFreeList;

for(IterFreeList=listOfFreeList.begin(); IterFreeList!=listOfFreeList.end(); IterFreeList++)
{
if(IterFreeList->getBlockValue() >= memory && IterFreeList->quantiyOfValue.size()!= 0)
vectorFreeList.push_back(IterFreeList->getOrderNumber());
//Get the order number from the object

else
continue;
}

//sort vectorFreeList so the lowest order # object is first
sort(vectorFreeList.begin(), vectorFreeList.end());

reverse(vectorFreeList.begin(), vectorFreeList.end());

//create a new iterator and advance it to the lowest
//order number object

current = allocatedList.begin();

if(current->quantiyOfValue.size() > 0)
current->quantiyOfValue.pop_back();

else
{

list<FreeList>::iterator deleteIterator = allocatedList.begin();

memoryAllocated = deleteIterator->getBlockValue();

reverse(vectorFreeList.begin(), vectorFreeList.end());

current = listOfFreeList.begin();

current->quantiyOfValue.push_back(current->getBlockValue());

deleteIterator->setBlockValue(0);

totalMemory += memoryAllocated;

}}

Main.cpp-----------------------------------------------------

#include<iostream>
#include<vector>
#include<list>
#include<string>
#include<algorithm>

using namespace std;

#include"FreeList.h"
#include"AllocatedList.h"

int main()
{
string response;

AllocatedList allocatedList;

int memory;
int choice;

while(response != "NO")
{
cout<<"***********BUDDY MEMORY PROGRAM**********\n"<<endl;

cout<<"1. Allocate Memory"<<endl;
cout<<"2. Delete Memory"<<endl;
cout<<"Enter in corresponding number"<<endl;
cin>>choice;

if(choice == 1)
{
cout<<"Enter In The Amount Of Memory You Would Like To Allocate\n"<<endl;

cin>>memory;

if(allocatedList.availableMemory(memory))
{
allocatedList.checkMemory(memory);

if((memory <= 0) || (memory > 256))
{
while((memory <= 0) || (memory > 256))
{
cout<<"Oops, Please Enter In An Amount Between '2 - 256' \n"<<endl;

cin>>memory;

}//End Of While

}//End Of If

}

else

cout<<"You Must Free Up Space To Allocate A Block Size Of  "<<memory<<endl;
}

else if(choice==2)
{
cout<<"How Much Memory Would You Like To Delete"<<endl;
cin>>memory;

if((memory <= 0) || (memory > 256))
{
while((memory <= 0) || (memory > 256))
{
cout<<"Oops, Please Enter In An Amount Between '2 - 256' \n"<<endl;

cin>>memory;
}}

allocatedList.deleteMemory(memory);

}

cout<<"Would You Like To Continue?\n"<<endl;

cout<<"Enter 'YES' Or 'NO'\n"<<endl;

cin>>response;

}//End of While

return 0;
}//End Of Main``````
Infinity08

membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.

Ok, so I am having a problem with current->quantiyOfValue.pop_back();.  It works just fine the first time that the user enter input.  But, on the second time of allocating memory the current->quantiyOfValue.pop_back(); throws an error. List iterator is not decrementable.  I debugged the code and the second time I allocated memory the current->quantiyOfValue.pop_back(); is still on the 256 block.  Therefore it has already been pop an nothing is in the quantiyOfValue list.  I cannot figure out why the current iterator is not moving.  Here is the code.
``````#include<iostream>
#include<vector>
#include<list>
#include<stack>
#include<algorithm>

using namespace std;

#include"AllocatedList.h"
#include"FreeList.h"

AllocatedList::AllocatedList()
{
totalMemory = 256;

//Defining the Free List
FreeList twoPow7(1,0, 256,1, 32 );	//Start out with 1 '256' in the quanity value
FreeList twoPow6(0,1, 128, 33, 97 );	//0
FreeList twoPow5(0,2, 64, 98, 226);		//0
FreeList twoPow4(0,3,32, 227, 483 );	//0
FreeList twoPow3(0,4,16, 484, 996 );	//0
FreeList twoPow2(0,5,8,997, 2021 );		//0
FreeList twoPow1(0,6,4,2022, 4070);		//0
FreeList twoPow0(0,7,2,4076, 80167);	//0

//Add each element to the Linked List
listOfFreeList.push_back(twoPow7);
listOfFreeList.push_back(twoPow6);
listOfFreeList.push_back(twoPow5);
listOfFreeList.push_back(twoPow4);
listOfFreeList.push_back(twoPow3);
listOfFreeList.push_back(twoPow2);
listOfFreeList.push_back(twoPow1);
listOfFreeList.push_back(twoPow0);

FreeList two_Pow_7(256,0);
FreeList two_Pow_6(128,1);
FreeList two_Pow_5(64,2);
FreeList two_Pow_4(32,3);
FreeList two_Pow_3(16,4);
FreeList two_Pow_2(8,5);
FreeList two_Pow_1(4,6);
FreeList two_Pow_0(2,7);

allocatedList.push_back(two_Pow_7);
allocatedList.push_back(two_Pow_6);
allocatedList.push_back(two_Pow_5);
allocatedList.push_back(two_Pow_4);
allocatedList.push_back(two_Pow_3);
allocatedList.push_back(two_Pow_2);
allocatedList.push_back(two_Pow_1);
allocatedList.push_back(two_Pow_0);

}

bool AllocatedList::compareSizeOfBlocks(int& amountOfMemory, FreeList& listOfFreeList)
{

return amountOfMemory <= listOfFreeList.getBlockValue();

}

void AllocatedList::checkMemory(int amountOfMemory)
{
list<FreeList>::iterator current;
list<FreeList>::iterator next;
vector<int> vectorFreeList;
vector<int> anotherFreeList;

int memoryAllocated=0;

list<FreeList>::iterator IterFreeList;
//Check the values that the nodes hold
for(IterFreeList=listOfFreeList.begin(); IterFreeList!=listOfFreeList.end(); IterFreeList++)
{
//If the value that the node holds is greater than or equal to the
//user input than store the node in vectorFreeList
if(IterFreeList->getBlockValue() >= amountOfMemory && IterFreeList->getListSize()>0 )
vectorFreeList.push_back(IterFreeList->getOrderNumber());
//Get the order number from the object

else
continue;
}

list<FreeList>::iterator anotherIter;

for(anotherIter=listOfFreeList.begin(); anotherIter!=listOfFreeList.end(); anotherIter++)
{
//If the value that the node holds is greater than or equal to the
//user input than store the node in vectorFreeList
if(anotherIter->getBlockValue() >= amountOfMemory)
anotherFreeList.push_back(anotherIter->getOrderNumber());
//Get the order number from the object

else
continue;
}

//sort vectorFreeList so the lowest order # object is first
sort(vectorFreeList.begin(), vectorFreeList.end());
sort(anotherFreeList.begin(), anotherFreeList.end());

reverse(vectorFreeList.begin(), vectorFreeList.end());
reverse(anotherFreeList.begin(), anotherFreeList.end());
//reverse so that the lowest block value will be first;

//Test: purpose of this list -> it will hold all of the user input
listOfMemory.push_back(amountOfMemory);

//create a new iterator and advance it to the lowest
//order number object

current = listOfFreeList.begin();

next = listOfFreeList.begin();

//Add a node to the list witin the current node
//Set the number range for the new node
//current->quantiyOfValue.push_back(current->getBlockRange());
current->quantiyOfValue.pop_back(); //ERROR: No item to pop second time around

//Divide the current and next values to get the temp to pushback the
//quantiy size
int temp = current->getBlockValue()/next->getBlockValue();

//Set memory Allocated to equal the block size
memoryAllocated = current->getBlockValue();

//Adding the block range to the quantiyOfValue
for(int i =0; i< temp; i++)
{
next->setBlockRange();
next->quantiyOfValue.push_back(next->getBlockRange());
}

//Create a new iterator to place the block range in the allocatedList
list<FreeList>::iterator allocatedIter;
allocatedIter = allocatedList.begin();

allocatedIter->setBlockValue(next->getBlockValue());

if(totalMemory != 0)
{
totalMemory -= next->getBlockValue();
}

else
{
cout<<"You Must Free Up Some Memory!!!"<<endl;
}

vectorFreeList.erase(vectorFreeList.begin(), vectorFreeList.end());
anotherFreeList.erase(anotherFreeList.begin(), anotherFreeList.end());
}//end of function

ostream &operator<<(ostream& output , FreeList &list)
{
output<<list.getBlockValue()<<endl;

return output;

}

bool AllocatedList::greater_than_amountOfMemory(int amountOfMemory,FreeList list)
{
return amountOfMemory<= list.getBlockValue();

}

bool AllocatedList::availableMemory(int memory)
{
}

void AllocatedList::deleteMemory(int memory)
{
int memoryAllocated = 0;

list<FreeList>::iterator current;

vector<int> vectorFreeList;

list<FreeList>::iterator IterFreeList;

for(IterFreeList=listOfFreeList.begin(); IterFreeList!=listOfFreeList.end(); IterFreeList++)
{
if(IterFreeList->getBlockValue() >= memory && IterFreeList->quantiyOfValue.size()!= 0)
vectorFreeList.push_back(IterFreeList->getOrderNumber());
//Get the order number from the object

else
continue;
}

//sort vectorFreeList so the lowest order # object is first
sort(vectorFreeList.begin(), vectorFreeList.end());

reverse(vectorFreeList.begin(), vectorFreeList.end());

//create a new iterator and advance it to the lowest
//order number object

current = allocatedList.begin();

if(current->quantiyOfValue.size() > 0)
current->quantiyOfValue.pop_back();

else
{

list<FreeList>::iterator deleteIterator = allocatedList.begin();

memoryAllocated = deleteIterator->getBlockValue();

reverse(vectorFreeList.begin(), vectorFreeList.end());

current = listOfFreeList.begin();