```
#include "free_list.h"
#include <iostream>
node::node()
{
SetSize(0);
SetOffset(0);
}
node::node(int n_size, int n_offset)
{
SetSize(n_size);
SetOffset(n_offset);
}
node::node(const node & n)
{
SetSize(n.GetSize());
SetOffset(n.GetOffset());
}
void node::SetSize(int s)
{
size = s;
}
void node::SetOffset(int o)
{
offset = o;
}
int node::GetSize() const
{
return size;
}
int node::GetOffset() const
{
return offset;
}
void node::operator = (const node & right)
{
SetSize(right.GetSize());
SetOffset(right.GetOffset());
}
bool node::operator == (const node & right)
{
return GetOffset() == right.GetOffset();
}
bool node::operator != (const node & right)
{
return GetOffset() != right.GetOffset();
}
bool node::operator < (const node & right)
{
return GetOffset() < right.GetOffset();
}
bool node::operator > (const node & right)
{
return GetOffset() > right.GetOffset();
}
bool node::operator <= (const node & right)
{
return GetOffset() <= right.GetOffset();
}
bool node::operator >= (const node & right)
{
return GetOffset() >= right.GetOffset();
}
std::ostream & operator << (std::ostream & out, node & n)
{
using namespace std;
out << "NODE" << endl;
out << "SIZE: " << n.GetSize() << " OFFSET: " << n.GetOffset() << endl;
return out;
}
free_list::free_list()
{
using namespace fl_const;
node * new_node = new node(DEFAULT_SIZE,DEFAULT_OFFSET);
f_list.resize(0);
f_list.push_back(*new_node);
delete new_node;
}
free_list::free_list(int size, int offset)
{
node * new_node = new node(size,offset);
f_list.resize(0);
f_list.push_back(*new_node);
delete new_node;
}
fl_itr free_list::GetBegin()
{
return f_list.begin();
}
fl_itr free_list::GetEnd()
{
return f_list.end();
}
size_t free_list::Size() const
{
return f_list.size();
}
int free_list::f_malloc(int size, int fit)
{
switch (fit)
{
case 1:
return FirstFit(size);
break;
case 2:
return NextFit(size);
break;
case 3:
return BestFit(size);
break;
case 4:
return WorstFit(size);
break;
default:
return FirstFit(size);
break;
}
}
void free_list::f_dmalloc(int size, int offset)
{
using namespace std;
node * new_node = new node(size,offset);
add_fl(*new_node);
delete new_node;
CombineNodes();
}
void free_list::add_fl(node & n)
{
f_list.push_back(n);
}
void free_list::delete_fl(node & n)
{
f_list.remove(n);
}
int free_list::FirstFit(int size)
{
using namespace std;
int offset = -1;
fl_itr begin = f_list.begin();
fl_itr end = f_list.end();
for (; begin != end; ++begin)
{
if (begin->GetSize() >= size)
{
offset = begin->GetOffset();
begin->SetOffset(begin->GetOffset()+size);
begin->SetSize(begin->GetSize()-size);
if (begin->GetSize() == 0)
f_list.erase(begin);
return offset;
}
}
return offset;
}
int free_list::NextFit(int size)
{
using namespace std;
int current_offset = -1;
fl_itr begin = f_list.begin();
fl_itr end = f_list.end();
fl_itr match = f_list.begin();
for (; begin != end; ++begin)
{
if (begin->GetSize() >= size)
{
if (current_offset > -1)
{
current_offset = begin->GetOffset();
begin->SetOffset(begin->GetOffset()+size);
begin->SetSize(begin->GetSize()-size);
if (begin->GetSize() == 0)
f_list.erase(begin);
return current_offset;
}
current_offset = begin->GetOffset();
match = begin;
}
}
if (current_offset > -1)
{
current_offset = match->GetOffset();
match->SetOffset(match->GetOffset()+size);
match->SetSize(match->GetSize()-size);
if (match->GetSize() == 0)
f_list.erase(match);
return current_offset;
}
return current_offset;
}
int free_list::BestFit(int size)
{
using namespace std;
int offset = -1;
fl_itr begin = f_list.begin();
fl_itr end = f_list.end();
fl_itr best = f_list.begin();
for (; begin != end; ++begin)
{
if (begin->GetSize() >= size)
{
offset = begin->GetOffset();
if (begin->GetSize() < best->GetSize())
best = begin;
}
}
if (offset > -1)
{
offset = best->GetOffset();
best->SetOffset(best->GetOffset()+size);
best->SetSize(best->GetSize()-size);
if (best->GetSize() == 0)
f_list.erase(best);
return offset;
}
return offset;
}
int free_list::WorstFit(int size)
{
using namespace std;
int offset = -1;
fl_itr begin = f_list.begin();
fl_itr end = f_list.end();
fl_itr worst = f_list.begin();
for (; begin != end; ++begin)
{
if (begin->GetSize() >= size)
{
offset = begin->GetOffset();
if (begin->GetSize() > worst->GetSize())
worst = begin;
}
}
if (offset > -1)
{
offset = worst->GetOffset();
worst->SetOffset(worst->GetOffset()+size);
worst->SetSize(worst->GetSize()-size);
if (worst->GetSize() == 0)
f_list.erase(worst);
return offset;
}
return offset;
}
void free_list::Resize(size_t size)
{
f_list.resize(size);
}
void free_list::CombineNodes()
{
using namespace std;
if (f_list.size() > 1)
{
f_list.sort();
fl_itr current = f_list.begin();
fl_itr next = f_list.begin();
fl_itr end = f_list.end();
++next;
for (; next != end; ++next)
{
if ((current->GetOffset() + current->GetSize()) == (next->GetOffset()))
{
next->SetSize(current->GetSize() + next->GetSize());
next->SetOffset(current->GetOffset());
f_list.erase(current);
current = next;
}
else
++current;
}
}
}
std::ostream & operator << (std::ostream & out, free_list & fl)
{
using namespace std;
list<node>::iterator begin = fl.GetBegin();
list<node>::iterator end = fl.GetEnd();
for (; begin != end; ++begin)
out << *begin << endl;
return out;
}
int main(void) {
return 0;
}
```