Customization of memory class C++

Question

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;
        }
    }
}

Answer 1

Try to be more consistent with naming

I'm seeing camelCase, PascalCase and snake_case all mixed together. Pick one style and stick with it. Furthermore, I see redundant things in names like Data_type_T, inconsistent use of the underscore suffix for private member variables, sometimes even using an underscore prefix which you should avoid.

I would suggest that you stick with the style used in the standard library, so that you can use one style throughout programs that use both your custom allocator and functions and classes from the standard library. So:

• Data_type_T -> data_type
• Flags_T -> flags_type
• poolSize_ -> pool_size
• Bits_needed -> bits_needed
• _vertex -> vertex
• ...

Also avoid unnecessary abbreviations. For example, instead of flag_chk, just write flag_check, or even better flags_to_check.

Naming things

Names should clearly express what something is about. When I look at some of the names in your code, I have some questions:

• namespace Ns: what does "Ns" mean? Is it an abbreviation for "namespace"? That would be very redundant. Is it even necessary to put things into a namespace here?
• Flags_T: this is not really a set of flags, but rather the type of the bit mask to use to keep track of allocated elements, as you already say in the comments. So perhaps name it bit_mask_type.
• N_allocator: what does the "N" mean? I think pool_allocator might be a better name for this class.
• linkedList: yes, this variable's type is a linked list, but wat does it actually do? It's there to keep track of the pools you have, so I would instead just name it pools.
• N_pointer: again, the "N" doesn't mean anything to me. I would not create an alias here at all, if you want something that is a pointer to a data element, then data_type * is perfectly clear.
• bitsInPool: this is a bit mask that keeps track of which elements in this pool are allocated. Since the type of the variable is already bit_mask_type, you shouldn't repeat that in the name. So perhaps allocated_elements, or in this case I think you can shorten it to allocated, as this is clear enough from the context.
• size_avail: this is not the size of how much is available, it is rather a count of the number of elements the caller wants to allocate. Since the fact that it's about allocation is already clear from the context, I would name this count.
• countOfE: what's an "E"? This variable holds the number of times you have to shift to find a free range in a pool. Maybe number_of_shifts, or more shortly n_shifts would be appropriate.
• flag_chk: that should be something like mask_to_check, or candidate_mask, as it is the bit mask that you want to check whether it would fit into the pool.
• condition: this variable is probably not necessary, see below.

Avoid using std::endl

Use "\n" instead of std::endl, the latter forces the output to be flushed, which can be inefficient. See this question for more details.

Remove debug statements

I see a lot of messages being printed to std::cout that are just debug statements. They should not end up in production code, so remove them.

Remove redundant comments

Comments should only be added if the code itself is unclear. Comments that merely repeat exactly what the code does are unhelpful. For example:

for (Pool& pool : linkedList)
{
    ...
    //iterator to next block
}

The comment there is redundant, of course you will iterate to the next element at the end of the body of a for-loop. Similarly:

//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 }{}

It is obvious from the code that you are declaring constructors here, the type is already in the name of the constructor function, and whether it's a default constructor is obvious from the fact that the first one doesn't take parameters while the second does.

And here you just repeat literally what the code does:

//size_t offset = addr - root; 
size_t offset = (size_t)(pv - pool.Pool_data_);

Simplify the check for free space in a pool

Instead of inverting the bitsInPool, and checking if the result of that ANDed with the candidate bit mask is still the same as the bit mask, you can just write this:

if ((flag_chk & pool.bitsInPool) == 0) {
    // it fits, add it to this pool
}

Since if there is no overlap between the bits set in flag_chk and the bits set in bitsInPool, the result of the AND operation will be zero.

Improve Bits_needed()

The problem with your version of Bits_needed() is that it expects the type of bit mask to be 32 bits or less. But what if I use an uint64_t as the bit mask type, and want to allocate more that 32 bits? It will fail. The function can be rewritten like this:

Flags_T Bits_needed(size_t sz)
{
    return ~Flags_T{} >> (poolSize_ - sz)
}

First, it creates a zero of the right type, inverts all the bits, and then shifts it right by the right amount.

Remove redundant static_casts

I see a lot of static_cast<Flags_T> that look completely redundant. For example:

flag_chk = static_cast<Flags_T>(flag_chk << 1);

Why? The type doesn't change here, and even if it did, assigning the value back to flag_chk would implicitly cast it for you. And in this case, you can even write this to:

flag_chk <<= 1;

Use more auto

There are a lot of places where you can use auto to reduce the number of times you have to repeat type names. For example:

• for (Pool& pool : linkedList) -> for (auto& pool : linkedList)
• Flags_T flags = Bits_needed(sz) -> auto flags = Bits_needed(sz)

Redundant use of ? true : false

It is almost always redundant to write some_condition ? true : false, since the condition itself will be a boolean, or it can be cast implicitly to a boolean, otherwise the ternary operator wouldn't work. So:

bool checkRemoval = (pool.bitsInPool == 0) ? true : false;

Can just be written as:

bool checkRemoval = pool.bitsInPool == 0;

But then the whole call to remove_if can be simplified to:

linkedList.remove_if([](Pool& pool){ return pool.bitsInPool == 0; });

Note that you don't needed to capture anything in the lambda here, so use [] instead of [&].

Invalid assumptions about pointer ordering in dealloc()

Your dealloc() function contains the following code:

size_t offset = (size_t)(pv - pool.Pool_data_);
//if memory offset less than pool size
if (offset < poolSize_)
{
    ...

Here you assume that the first pool's Pool_data_ will always have the lowest address. But there is absolutely no guarantee that newly allocated pools will always have an address that is higher than the previously allocated pool. But it gets even worse, it is actually undefined behaviour in C++ to do pointer comparison between two pointers that point to different arrays. But, if you are willing to assume that pointer comparisons do actually work as expected on your platform, then you should write:

if (pv >= pool.Pool_data_ && pv < pool.Pool_data_ + poolSize_)
{
    // pv is inside this pool

Simplify clearing bits in dealloc()

You have four lines of code to just unset a few bits in one variable, making it more complicated than necessary. You can simplify it to:

pool.bitsInPool &= ~(Bits_needed(sz) << (pv - pool.Pool_data_));