- This is called a "Slotted Heap Page":
- There is a header at the start which contains some information, including how many "slots" are on the page.
- Following that is a "Slot Directory", where each "slot" is like a "pointer" to a "record"/"tuple" on the page.
- The slot contains the length (in bytes) of the record's data and offset in the page it's located at.
In C++, I can write this efficiently like such:
constexpr auto PAGE_SIZE = 4096;
struct Slot
{
uint32_t offset;
uint32_t length;
};
struct HeapPage
{
uint32_t page_id;
uint32_t num_slots;
uint32_t free_space_end;
std::byte data[PAGE_SIZE - sizeof(uint32_t) * 3];
};
// Slot area is from after the header, and grows towards the end of the page.
auto get_slots(HeapPage* page) -> std::span<Slot>
{
return std::span(reinterpret_cast<Slot*>(page->data), page->num_slots);
}
// Data area is from the end of the page until FREE_SPACE_END, and grows backwards towards the start of the page.
auto get_data(HeapPage* page) -> std::span<std::byte>
{
auto data_size = PAGE_SIZE - page->free_space_end;
auto* data_start_ptr = reinterpret_cast<std::byte*>(page) + page->free_space_end;
return std::span(data_start_ptr, data_size);
}
How can I do something similar with Nim? I have tried, enabling the experimental views feature, and using openArray[] but I haven't managed to find the right syntax.
I would think the below would work, but unfortunately, it does not:
{.experimental: "strictFuncs".}
{.experimental: "views".}
type Slot = object
size: uint16
offset: uint16
type Page = object
pageId: uint32
numSlots: uint16
freeSpace: uint16
data: array[PAGE_SIZE - sizeof(uint16 * 2), byte]
func getSlots(page: Page): var openArray[Slot] =
cast[var openArray[Slot]](addr page.data[0])
From what I understand from the C++'s implementation, the data array removes the space that pageId, numSlots and freeSpace takes, so here it should rather be:
type Page = object
pageId: uint32
numSlots: uint16
freeSpace: uint16
data: array[PAGE_SIZE - sizeof(uint16)*2 - sizeof(uint32), byte]
Since the data is a fixed size array, this way might help
const PAGE_SIZE = 4096
type Slot = object
size: uint16
offset: uint16
type ByteData = array[PAGE_SIZE - (sizeof(uint16) * 2), byte]
type SlotData = array[sizeof(ByteData) div sizeof(Slot), Slot]
type Page = object
pageId: uint32
numSlots: uint16
freeSpace: uint16
data: ByteData
func getSlots(page: Page): ptr SlotData =
cast[ptr SlotData](addr page.data)
Ah, I didn't realize it was so simple as to just return the address of the first pointer
Are ptr types iterable in Nim? Could I do something like:
for each slot_ptr in slots:
do_something(slot_ptr)
Thanks all =)
let p = Page()
for s in p.getSlots[]:
echo s
Perfect, thank you!
The [] syntax is very familiar, reminds me of the syntax that D uses for "slices", which are non-allocating views over pointers. I like it =)