什么是最适合实现像记事本这样的编辑器的数据结构？

在记事本等编辑器的实现中使用了哪种数据结构.这个数据结构应该是可扩展的,并且应该支持各种功能,如编辑,删除,滚动,选择文本范围等？

我们为一台旧机器编写了一个编辑器(请记住,这是一段时间以前,大约在1986年,所以这是从记忆中,现有技术可能已经有所改进),我们设法让它们一起尖叫,性能方面,通过使用自我管理池中的固定内存块.

它有两个池,每个池包含固定数量的特定大小的块(一个池用于线结构,另一个池用于线段结构).它基本上是一个链表的链表.

内存是从' malloc()' 类似的调用预分配的(对于每个区域),我们使用65,535个块(0到65,534(包括0到65,534),块号65,535被认为是空块,列表末尾指示符).

这允许每个65,535行(填充版本为384K或512K)和大约1.6G的文件大小(占用2G的分配空间),这在当时非常大.这是理论文件大小限制 - 我认为我们从未接触到实际情况,因为我们从未分配过整套线段结构.

不必malloc()为每一小块内存调用都会给我们带来巨大的速度提升,特别是因为我们可以针对固定大小的块优化我们自己的内存分配例程(包括在最终优化版本中内联调用).

两个池中的结构如下,每行是单个字节):

Line structure (6/8 bytes)     Line-segment structure (32 bytes)
+--------+                     +--------+
|NNNNNNNN|                     |nnnnnnnn|
|NNNNNNNN|                     |nnnnnnnn|
|PPPPPPPP|                     |pppppppp|
|PPPPPPPP|                     |pppppppp|
|bbbbbbbb|                     |LLLLLLLL|
|bbbbbbbb|                     |LLLLLLLL|
|........|                     |xxxxxxxx|
|........|                     :25 more :
+--------+                     : x lines:
                               +--------+

大写字母指向行池.

x 是下一行的块编号(null表示这是文件中的最后一行).

N 前一行的块编号(null表示这是文件中的第一行).

P 是该行中第一个线段的块编号(null表示该行为空).

b 保留填充(将结构压缩到8个字节).

. 是下一个线段的块编号(null表示这是该行中的最后一个段).

n 是前一个线段的块编号(null表示这是该行中的第一个段).

p 是段的行块的块号.

L 是该线段中的26个字符.

线路结构填充的原因是为了加快块编号到实际存储器位置的转换(在该特定架构中,向左移3位比在6位左移快得多,并且使用的额外内存仅为128K,与总数相比最小虽然我们确实为那些关心内存的人提供了较慢的版本.

我们还有一个包含100个16位值的数组,其中包含大致该百分比的线段(以及行号,因此我们可以快速转到特定行)(因此数组[7]是大约7%的线路.文件)和两个自由指针来维护每个池中的空闲列表(这是一个非常简单的单向列表,其中x或N在结构中指示下一个空闲块和空闲块从这些列表的前面分配并放回到这些列表的前面).

由于0字节在文件中无效,因此无需在每个线段中保留字符数.允许每个线段在最后被完全忽略的0字节.无论何时修改线,都会压缩线(即,线段被组合).这使得块使用率很低(没有频繁和冗长的垃圾收集),并且大大加快了搜索和替换操作.

使用这些结构可以在文本周围进行非常快速的编辑,插入,删除,搜索和导航,这样您就可以在简单的文本编辑器中获得大部分性能问题.

使用选择(我们没有实现这个,因为它是一个文本模式编辑器,使用类似vi的命令,如n删除3行或3d删除6个字符)可以通过6x在文本中标记位置的元组来实现,并使用其中两个元组作为选择范围.

看看绳索.处理快速插入/删除/编辑字符串.在绳索实现中通常支持范围,并且可以使用倒置的索引进行滚动.