memory_arena.h

//  Copyright 2021 Herald Project Contributors
//  SPDX-License-Identifier: Apache-2.0
//
 
#ifndef HERALD_MEMORY_ARENA_H
#define HERALD_MEMORY_ARENA_H
 
#include <cstddef>
#include <bitset>
#include <array>
 
namespace herald {
namespace datatype {
 
struct MemoryArenaEntry {
  unsigned short startPageIndex = 0;
  unsigned short byteLength = 0;
 
  bool isInitialised() const {
    return 0 != byteLength;
  }
};
 
constexpr unsigned long pagesRequired(std::size_t size,std::size_t pageSize)
{
  return (size + pageSize - 1) / pageSize;
}
 
template <std::size_t MaxSize, std::size_t AllocationSize>
class MemoryArena {
public:
  static constexpr std::size_t Size = MaxSize;
  static constexpr std::size_t PageSize = AllocationSize;
 
  MemoryArena() noexcept
   : arena(), pagesInUse(false)
  {
    ;
  }
 
  ~MemoryArena() = default;
 
  void reserve(MemoryArenaEntry& entry,std::size_t newSize) {
    if (newSize <= entry.byteLength) {
      return;
    }
    auto newEntry = allocate(newSize);
    for (std::size_t i = 0;i < entry.byteLength;++i) {
      set(newEntry,i,get(entry,i));
    }
    deallocate(entry);
    entry = newEntry;
  }
 
  MemoryArenaEntry allocate(std::size_t size) {
    if (0 == size) {
      return MemoryArenaEntry{0,0};
    }
    // find first page location with enough space
    unsigned long pages = pagesRequired(size,PageSize);
    bool inEmpty = false;
    unsigned long lastEmptyIndex = 0;
    for (std::size_t i = 0;i < pagesInUse.size();++i) {
      if (!pagesInUse.test(i)) {
        // this one is empty
        if (!inEmpty) {
          inEmpty = true;
          lastEmptyIndex = i;
        }
        if (i - lastEmptyIndex + 1 == pages) {
          // flip bits and return
          for (unsigned long f = lastEmptyIndex;f <= i;++f) {
            pagesInUse.set(f,true);
          }
          return MemoryArenaEntry{(unsigned short)lastEmptyIndex,(unsigned short)size};
        }
      } else {
        inEmpty = false;
      }
    }
    // ran out of memory! Throw! (Causes catastrophic crash)
    throw std::runtime_error("Unable to allocate memory in arena");
  }
 
  void deallocate(MemoryArenaEntry& entry) {
    if (!entry.isInitialised()) {
      return; // guard
    }
    // set relevant bits to empty
    long pages = pagesRequired(entry.byteLength,PageSize);
    for (int i = 0;i < pages;++i) {
      pagesInUse.set(entry.startPageIndex + i,false);
    }
    entry.byteLength = 0;
    entry.startPageIndex = 0;
  }
 
  void set(const MemoryArenaEntry& entry, unsigned short bytePosition, unsigned char value) {
    if (!entry.isInitialised()) {
      return;
    }
    arena[(entry.startPageIndex * PageSize) + bytePosition] = value;
  }
 
  char get(const MemoryArenaEntry& entry, unsigned short bytePosition) {
    if (!entry.isInitialised()) {
      return '\0';
    }
    return arena[(entry.startPageIndex * PageSize) + bytePosition];
  }
 
  std::size_t pagesFree() const {
    return pagesRequired(Size,PageSize) - pagesInUse.count();
  }
 
private:
  std::array<unsigned char,Size> arena;
  std::bitset<pagesRequired(Size,PageSize)> pagesInUse;
};
 
}
}
 
#endif