Making my own heap allocation with buckets.

[26q2b7Xj]

I did an exercise and I would like for it to be checked if done correctly. Here is the exercise:

Create a LargeBucket class that can store up to 1MB of data. Extend the Heap class so it gives out a LargeBucket for allocations greater than 4096 bytes. Make sure that you still throw std::bad_alloc whenever the Heap is unable to allocate an appropriately sized bucket.

   #include <iostream>
#include <cstddef>

constexpr std::size_t small_size{ 4036 };
constexpr std::size_t large_size{ 1'000'000 };

struct Bucket
{
    const static std::size_t data_size{ small_size };
    std::byte data[data_size];
};

struct LargeBucket
{
    using byte = std::byte;

    const static std::size_t data_size{ large_size };
    byte data[data_size];
};

struct Heap
{
    void* allocate(std::size_t bytes)
    {
        if (bytes > Bucket::data_size)
        {
            if (bytes > LargeBucket::data_size)
                throw std::bad_alloc{};
            else
            {
                for (int i{}; i < n_heap_buckets; ++i)
                {
                    if (!buckets_used[i])
                    {
                        buckets_used[i] = true;
                        return buckets[i].data;
                    }
                }
            }
        }
        throw std::bad_alloc{};
    }

    void free(void *p)
    {
        for(std::size_t i{}; i < n_heap_buckets; ++i)
        {
            if(buckets[i].data == p)
            {
                buckets_used[i] = false;
                return;
            }
        }
    }

    const static std::size_t  n_heap_buckets{10};
    Bucket buckets[n_heap_buckets];
    bool buckets_used[n_heap_buckets]{};
};

Heap heap;

void* operator new(std::size_t n_bytes)
{
    heap.allocate(n_bytes);
}

void operator delete(void *p)
{
    heap.free(p);
}

[ne555]

    void* allocate(std::size_t bytes)
    {
        if (bytes > Bucket::data_size)
        {
            if (bytes > LargeBucket::data_size)
                throw std::bad_alloc{};
            else
            {
                for (int i{}; i < n_heap_buckets; ++i) //find empty bucket
                {
                    if (!buckets_used[i])
                    {
                        buckets_used[i] = true;
                        return buckets[i].data;
                    }
                }
            }
        }
        throw std::bad_alloc{};
    }

`bytes' is the size that the user want, say that you want to allocate one character, then bytes=1
at line 25 you test 1>4036, that fails and so you throw a bad allocation exception
¿does that make sense to you? you fail at allocating one single byte

lets say that bytes=8192, the test in line 25 succeed, the one in 27 fails so you find an empty Bucket and return it
but a bucket is too small to hold 8192 bytes...

¿at what point do you ever return a LargeBucket?
so, no, it's not done correctly

[mbozzi]

Looks like the pointer returned by allocate incorrectly ignores alignment requirements.

You forgot to return something from replacement operator new.

[26q2b7Xj]

Okay I obviously see the problem. Basically I am using the buckets from the smaller heap rather than the larger one. And for the other, change the logic.

[26q2b7Xj]

How is this:

struct Heap
{
    void* allocate(std::size_t bytes)
    {
        if (bytes > Bucket::data_size)
        {
            if (bytes < LargeBucket::data_size)
            {
                for (int i{}; i < n_heap_buckets; ++i)
                {
                    if (!buckets_used[i])
                    {
                        buckets_used[i] = true;
                        return buckets[i].data;
                    }
                }
            }
            else
            {
                throw std::bad_alloc{};
            }
        }
        throw std::invalid_argument{"Allocation must be greater than 4036."};
    }

    void free(void *p)
    {
        for(std::size_t i{}; i < n_heap_buckets; ++i)
        {
            if(buckets[i].data == p)
            {
                buckets_used[i] = false;
                return;
            }
        }
    }

    const static std::size_t n_heap_buckets{ 10 };
    LargeBucket buckets[n_heap_buckets];
    bool buckets_used[n_heap_buckets]{ };
};

[ne555]

> throw std::invalid_argument{"Allocation must be greater than 4036."};
¿shouldn't you give a normal Bucket in that case?
(also, 4096 and 1M = 1024*1024)

[26q2b7Xj]

I would assume so; however, the wording seems like he wants the allocation to be greater than 4036 bytes and under 4096? As for the 1024 * 1024, yeah, I was doing 10^3 bytes.

[ne555]

I don't get were did you get 4036, your assignment talks about 4096, so I guess that small_size should be 4096. however, that's just a detail, not so important

from a client perspective:
from 1 to 4096: give a Bucket, ¿ran out? give a LargeBucket, ¿ran out? fail
from 4097 to 1M: give a LargeBucket, ¿ran out? fail
more than 1M: fail to allocate

[26q2b7Xj]

Yeah I am over thinking it. I understand what need to be done now. Thanks!