6502.org

Computerphile made a Youtube video recently explaining one approach here: https://youtu.be/g2hiVp6oPZc?si=xEfkIHxGBa5e6Vkk

I don't remember what it is called but it's a method where characters before the cursor are stored at the start of the block and characters after the cursor are at the end of the block, with a big gap in between to allow fast editing. When the cursor moves (or at least when an edit starts) you move a chunk of data to create this situation before inserting the new text. Moving data is costly but happens rarely.

Indeed, welcome.
I rather like this, thanks for sharing. Obviously a tradeoff between frequent operations being quick, because local, but possibly causing fragmentation, and then the other half of the solution, which is to defragment. Hopefully without holding the user up - perhaps done in several shorter operations so it can be interrupted?
So, more than an idea or a design, you've implemented it. Marvellous!

As long as chunk size isn't too huge, defragmentation could also be an "idle task" when the editor is waiting on user input (which, in a text editor, is gonna be a fair bit of the time) without causing noticeable lag.

Yes, it’s the Nano clone ”X16 Edit” for Commander X16. It’s built into the ROM nowadays.

As pointed out, most of the memory strategy isn’t a unique idea.

If I would start over, I’d like to check how well the piece table structure works on a 6502 system. The main benefit being unlimited undo. Has it been done by anyone?

ooh, undo on a small editor on a small system - that would be a thing!

I'm curious to see how the approach might be extended to files larger than the available memory. A linked list seems an obvious solution, with perhaps a 24 or 32 bit link address (oooh, overhead) but it needs a transparent virtual memory (i.e. on the disk, or whatever storage medium is chosen).

One might build a link table in memory by inspection of the stored file, allocating say 128 bytes per block. That lets you use the 256 byte window for insertion at very little cost, and allocation when one is full at little more... with everything glued back into a single file on save.

An editor for a 10k file on a 64k machine is easy. A 100k file, a bit harder. A couple of megabytes, or more? Hmmm.

Neil

Stefan, I've come up with an extremely similar design, and hadn't noticed this thread. I'm glad it's working out!

An interesting thing is that if you have this block allocation method (which is effectively like a filesystem, but with the ability to shove new sectors into the middle of the "file") then you can have multiple text streams stored in there, which could hold multiple files, or temporary clipboard & undo information. All you have to do is track multiple starting points, which could be held in a "file" in that block system as well.

That sounds interesting! Is your editor publicly available?

Yes, I was originally inspired by the 1541 BAM and the pointer to the next block present in all blocks.

I haven’t thought about it, but, as you say, it would be easy to store multiple data streams in the buffer. Currently I have a fixed size clipboard buffer and no undo. I might just use that idea if it’s OK with you!

Which is the essence of my editor prviously mentioned - a list of addresses to each line and each line is allocated from memory using malloc() in the C version and getvec() in the BCPL version.

The key is the implementations of malloc or getvec. cc65 has a reasonable implementation and I wrote my own using the 'best fit' algorithm in BCPL, however what may be of interest is a version of malloc/free I wrote in sweet16 when I was looking at other things at the time. It's essentially 'first fit' (look it up) and it works well, but it can suffer from fragmentation. My BCPL version has a merge function which vastly reduces this. Saying that, I simulated what might happen in something like a BASIC interpreter when extending and truncating strings - which is what usually 'kills' most 8-bit Basics and it coped well.

I've attached it here for interest - I suspect no-one will actually want to use it, especially as it's written in sweet16 (I wrote my own version of that too if anyones interested). but it may inspire someone to re-write it in native 6502.
-Gordon

(It occurs that, if you're using a linked-list-of-chunks structure, making the chunks 256 bytes cuts your pointer size in half.)

Yep, only storing MSB.

Hi Gordon,

Linked arrays in different forms are a common solution indeed.

Impressive work on ”Ruby”!

Limiting your file size to 64k... but you save the low byte whatever your pointer size is.

Neil