Struggling with storing text on btree-rope, looking for guidance

Help
1

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!

2

you can look at what i made here:
https://codeberg.org/mappoTrell/ropez/src/branch/main/src/BTree.zig
but i haven’t solved your problem, i currently store the text on the leafs, but this is mainly because i reuse the same BTree for other stuff like the CRDT book keeping
but maybe you can still get something usefull from it

1 Like
3

I’m not an expert (I also come from a GC language originally), so someone can absolutely correct me if I’m wrong, but here is my understanding and my best ideas without reading the relevant literature, of which there is plenty if you want more serious solutions.

ArrayList will only copy when absolutely necessary. That is to say, at the point that it needs to copy, so would any other growable structure (that uses contiguous memory). If you want to avoid a copy at all costs, you can allocate lots of memory up-front. You’re probably better off just allocating a reasonable amount up-front and letting the allocator do its thing, though.

If you’re worried about the worst-case of writing to the beginning of a file: as long as your leaf nodes know where their bytes are, I don’t see why those bytes would need to be in order themselves, though maybe someone else knows a good reason. If you store it this way, you can just append to the end (or insert into known gaps) even if the cursor is moved back to the beginning. Only the leaves (or their indexes) would need to be moved around.

I think you’re probably overcomplicating things with your TextStorage and TextBlock structs? If the Leaf struct is supposed to have an index to the text, just actually have an index to the text.

Consider reading handles are the better pointers, although maybe you have based on your design goals.

If you don’t want serialization/deserialization, every type needs to have a well-defined size and a guaranteed layout. For that you want an extern struct. Then you just write the bytes when you save, read them as []T when you load. The standard library’s ArrayList has functions for this.

Multiple types without serialization might be tricky? I think it depends on your definition of serialization, honestly. You could have a small header at the beginning of your file that tells you the size of each list, then just compute the offsets. Maybe that’s too much deserialization, though? Separate files for each type array? Whatever floats your boat.

Does any of that help?