c - 编写文本编辑器时保存数据的好方法

Question

我打算用 c 做一个文本编辑器。所以就想知道用什么数据结构保存文本好。我读到使用链表是一种方法，但效率不高。请指出一些引用资料，以便我可以很好地了解需要使用的内容。我计划使用 ncurses 库获取用户输入并捕获键和 UI。

使用现有编辑器的源代码有点太复杂了，所有的文本编辑器都很大，甚至只有控制台的编辑器。任何简单的控制台编辑器源代码可供引用？

Answer 1

您将受益于 reading about Emacs buffers .另见 this blog ，特别是最后一条评论，引用在这里以方便引用:

Many versions of Emacs, including GNU, use a single contiguous character array virtually split in two sections separated by a gap. To insert the gap is first moved to the insertion point. Inserted characters fill into the gap, reducing its size. If there’s insufficient space to hold the characters the entire buffer is reallocated to a new larger size and the gaps coalesced at the previous insertion point.

The naive look at this and say the performance must be poor because of all the copying involved. Wrong. The copy operation is incredibly quick and can be optimized in a variety of ways. Gap buffers also take advantage of usage patterns. You might jump all over the window before focusing and inserting text. The gap doesn’t move for display – only for insert (or delete).

On the other hand, inserting a character block at the head of a 500MB file then inserting another at the end is the worst case for the gap approach, especially if the gap’s size is exceeded. How often does that happen?

Contiguous memory blocks are prized in virtual memory environments because less paging is involved. Moreover, reads and writes are simplfied because the the file doesn’t have to be parsed and broken up into some other data structure. Rather, the file’s internal representation in the gap buffer is identical to disk and can be read into and written out optimally. Writes themselves can be done with a single system call (on *nix).

The gap buffer is the best algorithm for editing text in a general way. It uses the least memory and has the highest aggregate performance over a variety of use cases. Translating the gap buffer to a visual window is a bit trickier as line context must be constantly maintained.