I have implemented a customized memory allocation class template for an assignment. Codes are commented; Hopefully it's clear. I would love to know if there is any way to make the code more optimized.
Note: int main()
should not be modified. From the requirements of my school (Must be adhered to):
Implement an alloc class template for the purpose of memory management inside of vector objects;
It is necessary that I use std::forward_list as an allocator to store the allocated memory;
No other headers allowed
It is necessary that I use bitwise operations for this assignment (Which I have); Note: use of std::bitset not allowed.
It is necessary that I use std::forward_list::remove_if() (Which I did), to check if there are anymore elements in the block, otherwise, remove it; Implementation for this could change if it can be more optimized, but have to make sure to stick with the use of std::forward_list::remove_if()
Struct vector and union _vertex should remain the way they are, since it was given as part of the assignment
Code must be implemented using c++17. Implementation that is compatible with g++ is only required.
Output for the code should not change.
#include<iostream>
#include<forward_list>
namespace Ns
{
// Elements of Data_type_T, bit mask of type Flags_T
template <typename Data_type_T, typename Flags_T>
class N_allocator
{
static const size_t poolSize_ = sizeof(Flags_T) * 8;
//To generate a bitflag according to the no. of bits required
Flags_T Bits_needed(size_t sz)
{
uint32_t mask = 0xFFFFFFFF >> (32 - sz);
return (Flags_T)(mask);
}
struct Pool
{
//buffer for pool
Data_type_T Pool_data_[poolSize_];
Flags_T bitsInPool;
};
std::forward_list<Pool> linkedList;
//For the allocation of a new memory block & adds to the list of blocks
Data_type_T* create_pool(size_t size)
{
std::cout << " Allocating new pool." << std::endl;
Pool pool;
pool.bitsInPool = Bits_needed(size);
linkedList.push_front(pool);
std::cout << " The pool found for " << size
<< " elements @ index 0." << std::endl;
return linkedList.front().Pool_data_;
}
public:
using N_pointer = Data_type_T*;
//To find a continuous memory of N size & returns a pointer to 1st
//element, then allocates a new block if a suitable slot is not found
N_pointer alloc(size_t size_avail)
{
std::cout << std::endl
<< " Allocator alloc " << size_avail
<< " elements. " << std::endl;
if (size_avail > poolSize_)
{
throw std::bad_alloc();
}
if (!linkedList.empty())
{
//for shifting bitsinpool by 'countOfE' no.of times
size_t countOfE = poolSize_ - size_avail;
for (Pool& pool : linkedList)
{
Flags_T flag_chk = Bits_needed(size_avail);
//for running a check against the bit flag of current to see if a suitable slot
//is found
for (size_t i=0; i < countOfE; i++)
{
Flags_T condition = static_cast<Flags_T>
((flag_chk & (~pool.bitsInPool)));
//check if element at i was allocated previously,
//otherwise, don't set
if (condition == flag_chk)
{
std::cout << " The pool found for "
<< size_avail << " elements @ index "
<< i << "." << std::endl;
//only do set if element at the index i in the
//pool is allocated
pool.bitsInPool |= flag_chk;
//return the address of the element corresponding
//to the index of the first bit found
return (&pool.Pool_data_[i]);
}
//shift flag for nxt round of bit checking
flag_chk = static_cast<Flags_T>(flag_chk << 1);
}
std::cout << " Can't find space in pool."
<< std::endl
<< " Searching for next avail pool..."
<< std::endl;
}
//if slots have run out, alloc a new pool
return create_pool(size_avail);
}
else
{ //If no pool exist, alloc new pool
return create_pool(size_avail);
}
}
//To find the matching block that the pointer belongs to, marks N bits
//after the pointer's index as unused. Removes block from list if all
//elements are unused
void dealloc(N_pointer pv, size_t sz)
{
std::cout << " Deallocate "
<< sz << " elements. " << std::endl;
for (Pool& pool : linkedList)
{
//size_t offset = addr - root;
size_t offset = (size_t)(pv - pool.Pool_data_);
//if memory offset less than pool size
if (offset < poolSize_)
{
Flags_T flag = Bits_needed(sz);
flag = static_cast<Flags_T>(flag << offset);
//Mark deallocation of element by flipping
//then Or-ing bit then flip result again
Flags_T n_flag = static_cast<Flags_T>
((flag | (~pool.bitsInPool)));
pool.bitsInPool = static_cast<Flags_T>(~n_flag);
std::cout << " Have found " << sz
<< " elements in a pool." << std::endl;
break;
}//iterate to next block
std::cout << " Searching next existing pool..."
<< std::endl;
}
//if there are no elements used in a memory block
//after deallocation, the pool should be removed
linkedList.remove_if([&](Pool& pool)
{
bool checkRemoval = (pool.bitsInPool == 0) ? true : false;
if (checkRemoval)
std::cout << " Remove empty pool." << std::endl;
return checkRemoval;
});
}
};
struct vector
{
//A default ctor for a vector type
float x;float y;float z;float w;
vector() : x{ 0 },y{ 0 },z{ 0 },w{ 0 }{}
//A non Default ctor for vector type
vector(float ax1, float ay, float az, float aw) :
x{ ax1 },y{ ay },z{ az },w{ aw }{}
};
union _vertex
{
vector vertex_coord;
float axisCoordinates[sizeof(vector) / sizeof(float)];
//A default ctor for vertex type
_vertex() :
vertex_coord{}{}
//A non-default ctor for vertex type
_vertex(float ax1, float ay, float az, float aw) :
vertex_coord{ ax1, ay, az, aw }{}
};
}
void test4()
{
std::cout << "Allocator_:\n-----" << std::endl;
Ns::N_allocator<Ns::_vertex, short> N_allocator;
using N_pointer = decltype(N_allocator)::N_pointer;
N_pointer p1 = N_allocator.alloc(10);
N_pointer p2 = N_allocator.alloc(4);
N_allocator.dealloc(p1, 10);
N_pointer p3 = N_allocator.alloc(16);
N_pointer p4 = N_allocator.alloc(8);
N_allocator.dealloc(p4, 8);
N_allocator.dealloc(p3, 16);
N_allocator.dealloc(p2, 4);
N_pointer pv5 = N_allocator.alloc(32);
N_allocator.dealloc(pv5, 32);
std::cout << std::endl;
}
int main()
{
using test_ = void (*)();
test_ tests[] =
{
test4
};
int i = 0;
for (const test_& test : tests)
{
try
{
std::cout << (++i) << ". ";
test();
std::cout << std::endl;
}
catch (std::exception& e)
{
std::cout << "\nError: " << e.what() << std::endl;
}
catch (...)
{
std::cout << "\nUnknown error occurred." << std::endl;
}
}
}