Search code examples
c++c++14hashtablememory-pool

Deterministic compile time mapping function for MemoryPool

please refer to the picture below where I tried to show what I am trying to implement: enter image description here

There are several memory Partitions statically allocated in the memory containing chunks of various sizes, known at the compile time. Each partition has chunks of different size. The Partition implements the IPartition interface. The pointers IPartition * are organized within the C-style array where idx is an index to that array in range of 0..nPartitions.

In my custom operator new(size_t size) implementation I am about to use the concept described above to return a memory chunk of appropriate size where the type of any size will fit. The obvious requirement is the chunk size must be equal or bigger than the size of the type.

GOAL / TASK/ QUESTION:

I need to design a function constexpr unsigned int func( size_t size ) which takes the size of the object to be allocated and returns the index idx to the array of IPartition * pointers which points to the "right" Partition having chunks of appropriate size.

To make things more complicated, the func() must take a constant time to keep the whole memory allocation using memory pool deterministic.

The whole thing points me to std::unordered_map but the target system is small MCU limited in resources. Maybe the solution could be a hash table where the hashes are calculated at compile time (num of Partitions as well as chunk sizes are known at compile time), I do not know...

I would be very happy if someone could help me to follow the optimal way of doing so...

Many thanks in advance to anyone willing to help!

Solution

  • You can do a binary search for the size. This is a constant number of instructions to each return, O(log(N)) in the number of partitions and only mildly annoying to write by hand. For your four chunk sizes that would be:

    constexpr unsigned int func( size_t size )
{
  if (size <= 4)
    if (size <= 3)
      return 0;
    else
      return 1;
  else
    if (size <= 8)
      return 2;
    else
      return 3;
}

    It should also be possible to template-metaprogram this given a (sorted) list of compile-time sizes, but I don't know if that's your use case.