Text Editor Shifting Mechanics

[BigDumbDinosaur]

stefan1 wrote:

I know this thread is kind of old, but there’s some recent activity and I find the subject very interesting.

Welcome!

Topics around here can often run for years, especially with long-lived hardware projects.  We encourage members to continue adding relevant content to existing topics instead of spawning new ones and fragmenting things.

Quote:

- The text buffer is divided into 256 byte blocks.
- Each block starts with a link to the previous and the next block. The lenght of the text in a block is also stored in the block.
- If the link to the previous block is NULL you are at the first block. The link to next block is NULL you are in the last block.
- A block allocation table keeps track of which blocks are in use and which are free.
- When inserting a char, the subsequent text within the block is shifted forward. This is pretty fast, as a block is 256 bytes. If the block is full, the char is pushed into the next block. If that is also full, a new empty block is linked in after the current block. This is also fast as no copying is necessary.
- When deleting a char, the trailing chars in the block are shifted to the left and the block length is decremented. If the block becomes empty it is marked as free.
- A defragmentation routine runs when the editor is idle.

What you are describing appears to be organizing the text buffer into a linked list, and is similar in principle to what others have suggested.  The use of 256 byte blocks seems natural with the 6502 due to that being the largest data quantity that may be addressed without having to do pointer arithmetic.

Quote:

The drawback is of course code complexity.

There is never a free lunch when it comes to this stuff, especially with the 6502.  Lacking the means to easily index over the full address space, pointer manipulation becomes necessary as soon as your editing buffer’s size exceeds that of one page.  Fortunately, judicious use of page zero as a set of extended registers can make for reasonable performance.  It also helps that the current generation of the 65C02 may be run at double digit clock speeds.

Incidentally, text buffer manipulation mechanics become less difficult with the 65C816, since it can index over hundreds of KBs or MBs with ease using the indirect-long addressing modes.  Also, the MVN and MVP instructions could be used to rapidly shift the buffer during an insertion or deletion.  If the principle of a localized buffer is used to collect keystrokes and then said buffer is inserted into the main buffer via use of MVN and MVP, I suspect system response would be very good, even with hundreds of KBs in the main buffer.

[gfoot]

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.

[BigEd]

Indeed, welcome.

stefan1 wrote:

... a 6502 based text editor.

It is based on the following model:

- The text buffer is divided into 256 byte blocks.
...
- A defragmentation routine runs when the editor is idle.

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?

Quote:

...works pretty well. There is no noticeable performance hit even when handling large files...

So, more than an idea or a design, you've implemented it. Marvellous!

[BigDumbDinosaur]

BigEd wrote:

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.

Fragmentation could be also be addressed (!) when the user saves his/her work, or if a timed-save feature is implemented.  I could see where the code that saves the buffer to external storage also executes a sort of garbage collection process to claim slack space or perhaps to reorder links that connect blocks of text together.  That might reduce the user’s perception of the execution time required by memory-management functions.

gfoot wrote:

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.

That was brought up a number of posts ago...the phrase “sliding window” comes to mind.

Quote:

Moving data is costly but happens rarely.

It would depend on the point of insertion/deletion in the main buffer, and the algorithm used to shuffle memory.  Since insertion/deletion will be slowest when the cursor is at or near the beginning of text, the memory-shuffle code should probably be handling a different amount of data when the cursor is at the beginning of text (large memory move) than when at the end of text (small memory move).  That would infer the size of the “sliding window” and the gap within should vary with cursor position.

[commodorejohn]

BigDumbDinosaur wrote:

BigEd wrote:

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.

Fragmentation could be also be addressed (!) when the user saves his/her work, or if a timed-save feature is implemented.  I could see where the code that saves the buffer to external storage also executes a sort of garbage collection process to claim slack space or perhaps to reorder links that connect blocks of text together.  That might reduce the user’s perception of the execution time required by memory-management functions.

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.

[stefan1]

BigEd wrote:

So, more than an idea or a design, you've implemented it. Marvellous!

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?

[BigEd]

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

[barnacle]

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

[White Flame]

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.

[stefan1]

White Flame wrote:

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!

[drogon]

White Flame wrote:

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.

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.

malloc.tgz

(4.15 KiB) Downloaded 77 times

-Gordon

[commodorejohn]

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

[stefan1]

commodorejohn wrote:

(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.

[stefan1]

Hi Gordon,

Linked arrays in different forms are a common solution indeed.

Impressive work on ”Ruby”!

[barnacle]

stefan1 wrote:

commodorejohn wrote:

(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.

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

Neil