c++ - MemoryPool 的确定性编译时映射函数

Question

请引用下图，我试图展示我正在尝试实现的内容:

在内存中静态分配了多个内存Partition，其中包含编译时已知的各种大小的chunks。每个分区都有不同大小的 block 。 Partition 实现了 IPartition 接口(interface)。指针 IPartition * 在 C 样式数组中组织，其中 idx 是该数组的索引，范围为 0..nPartitions。

在我的自定义 operator new(size_t size) 实现中，我将使用上述概念返回适当大小的内存块，其中适合任何大小的类型。明显的要求是 block 大小必须等于或大于类型的大小。

目标/任务/问题:

我需要设计一个函数 constexpr unsigned int func( size_t size ) 它接受要分配的对象的 size 并返回索引 idx 到 IPartition * 指针数组，该指针指向具有适当 大小 block 的“正确”分区。

为了让事情变得更复杂，func() 必须花费恒定的时间来保持使用内存池的整个内存分配确定性。

整件事让我指向 std::unordered_map 但目标系统是资源有限的小型 MCU。也许解决方案可能是一个哈希表，其中哈希值在编译时计算(分区数以及 block 大小在编译时已知)，我不知道...

如果有人能帮助我遵循这样做的最佳方式，我会很高兴......

非常感谢任何愿意提供帮助的人!

Answer 1

您可以对大小进行二分查找。这是每次返回的固定数量的指令，O(log(N)) 在分区数量中，手写只是有点烦人。对于您的四个 block 大小:

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

在给定(排序的)编译时大小列表的情况下，模板元编程也应该是可能的，但我不知道这是否是您的用例。