14

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

4

6 回答 6

8

我们为一台旧机器编写了一个编辑器（请记住，这是不久前，大约 1986 年，所以这是凭记忆，从那时起，最先进的技术可能已经有所进步）我们设法让它尖叫起来，性能方面，通过使用自管理池中的固定内存块。

它有两个池，每个池包含固定数量的特定大小的块（一个池用于线结构，另一个用于线段结构）。它基本上是一个链表的链表。

malloc()内存是从类似“ ”的调用中预先分配的（针对每个区域） ，我们使用了 65,535 个块（包括 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指向线段池。
  • 大写字母指向行池。
  • N是下一行的块号（null 表示这是文件中的最后一行）。
  • P上一行的块号（null 表示这是文件中的第一行）。
  • b是该行中第一条线段的块号（null 表示该行为空）。
  • .保留填充（将结构增加到 8 个字节）。
  • n是下一条线段的块号（null 表示这是该线中的最后一段）。
  • p是前一条线段的块号（null 表示这是该线的第一段）。
  • L是段的行块的块号。
  • x是该线段中的 26 个字符。

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

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

由于 0 字节在文件中无效，因此无需对每个行段中的字符进行计数。每个线段的末尾都允许有 0 字节，这些字节完全被忽略。每当它们被修改时，线就会被压缩（即，线段被合并）。这使块使用率保持在较低水平（没有不频繁且冗长的垃圾收集），并且还大大加快了搜索和替换操作。

使用这些结构可以非常快速地编辑、插入、删除、搜索和导航文本，这是您在简单的文本编辑器中可能遇到的大部分性能问题。

选择的使用（我们没有实现它，因为它是一个文本模式编辑器，使用类似 vi 的命令，例如3d删除 3 行或6x删除 6 个字符）可以通过使用{line#/block, char-pos}元组来标记文本中的位置来实现，并使用其中两个元组作为选择范围。

于 2009-03-16T05:58:37.730 回答
6

检查绳索。处理字符串的快速插入/删除/编辑。范围通常在 Rope 实现中得到支持，并且滚动可以通过在绳子中的倒排索引来完成。

于 2009-03-16T04:43:03.513 回答
5

维基百科说许多编辑使用Gap Buffer。它基本上是一个中间有一个未使用空间的数组。光标位于间隙之前，因此光标处的删除和插入是 O(1)。它应该很容易实现。

查看 Notepad++ 的源代码（正如 Chris Ballance 在此线程中所建议的那样）表明它们也使用了间隙缓冲区。你可以从中得到一些实现的想法。

于 2009-03-24T13:40:57.083 回答
3

HexEdit的作者 James Brown有一篇关于Piece Chains的优秀文章。

简而言之：片段链允许您记录对文本所做的更改。加载后，您有一个跨越整个文本的片段链。现在你在中间的某个地方插入。

您无需分配新缓冲区、复制文本等，而是创建两个新片段并修改现有片段：现有片段现在包含直到插入点的文本（即您只需更改片段的长度），然后你有一个包含新文本的片段，然后是一个包含插入后所有文本的新片段。原文保持不变。

对于撤消/重做，您只需记住您添加/删除/更改的部分。

使用片段链时最复杂的区域是可见文本中的偏移量和内存结构之间不再存在 1:1 映射。您要么必须搜索链，要么必须维护某种二叉树结构。

于 2009-05-13T14:16:49.063 回答
1

查看Notepad++的实现，可以在SourceForge上查看源码

于 2009-03-16T04:38:32.273 回答
-1

通常的事情是有一个列表或字符数组的数组。多年来在这方面做了很多工作：你可以看看这个谷歌搜索。

于 2009-03-16T04:46:07.483 回答