Hey,
I am not an experienced dev in low-level concepts. My background is many years of writing backends mostly in Python.
I am struggling with goals I established for my own project.
I wrote (all by hand) a b-rope structure to store text.
My goal is to write a b-rope (something similar to GitHub - cessen/ropey: A utf8 text rope for manipulating and editing large texts. · GitHub), that has the following:
- more or less const insert/delete predictable time, not dependent on structure size
- small memory overhead over stored structure
- be fast
- load/store from disk without serialization (which requires no pointer usage in my understanding)
Currently I am rewriting already working versions where I used pointers, where I’am not satisfied with the memory usage of it.
My current problem is understanding how to store text itself, to fulfill my gols.
A simplified version of the structure of my code is
max_children: u8, // how many childs single node can have
leaf_size: u16,
leafs: std.FreeList(Leaf),
nodes: std.FreeList(InternalNode),
leafs_text: ??? // Here is my main issue
// If I were to store text in `ArrayList/FreeList` then adding
// one more element might lead to a copy of 1 GB of text.
// So I need some fragmented storage. (I consider it as no problem in case of leafs/nodes cus they are rly small, maybe I'm wrong).
const NodeIndex = enum(u32) {
_,
};
const LeafIndex = enum(u32) {
_,
};
const RopeNode = union(enum) {
node: NodeIndex,
leaf: LeafIndex,
}
const InternalNode = struct {
children: [max_childen]RopeNode,
children_prefix_sizes: [max_children]usize,
}
const Leaf = struct {
len: u16,
text: // index to text??
}
In my understanding, I need to build some Block/Pages list for those texts, and keep an index to them on Leaf itself.
Like,
const TextBlock = struct {
array: (text_page_size * leaf_size)[u8], // This suppose to be block of memory it manages.
free: text_page_size[u8],
};
const TextStorage = struct {
// It needs to have grovable list of TextBlocks,
// but how to do so without pointers? Or can i use them somehow, but i dont understand how
};
But I don’t understand how to do so without pointers.
Storing text on the leaf itself just moves the problem up.
My TextStorage should have logically continuous memory; to jump around using indexes + leaf max size offsets, but under the hood it should have multiple memory regions, whose number can grow dynamically (TextBlock).
Thanks for the help!