Was ist die beste Datenstruktur, die geeignet zu implementieren-editor wie notepad?

Schrieben wir einen editor für eine alte Maschine (denken Sie daran, dies war vor einer Weile, etwa 1986, so ist dies aus der Erinnerung und dem Stand der Technik können fortgeschrittene etwas seitdem) wir haben es geschafft, zu Schreien entlang, Leistung klug, durch die Verwendung von festen Speicher-Blöcke von selbst-verwalteten pools.

Es hatte zwei pools, die jeweils eine Feste Anzahl von spezifischen-großen Blöcken (ein pool war für line-Strukturen, die andere für den line-segment-Strukturen). Es war im Grunde eine verknüpfte Liste von verketteten Listen.

Speicher wurde vorher reserviert (für jede region) von einem 'malloc()'-like nennen, und wir haben 65,535 Blöcke (0 bis 65,534 inclusive, block Anzahl 65,535 war als der null-block, ein Ende-der-Liste-Anzeiger).

Dies darf jeder für 65, 535 Zeilen (384 KB oder 512 KB für die gepolsterte version) und etwa 1.6 G der Dateigröße (unter 2G zugewiesenen Speicherplatz), die war ziemlich groß damals. Das war der theoretische - Datei Größe begrenzen - ich glaube nicht, dass wir jemals angesprochen, dass in der Realität, da wir nie reserviert, den vollen Satz von line-segment-Strukturen.

Nicht aufzurufen malloc() für jeden kleinen Speicherblock, der gab uns eine riesige Geschwindigkeit zu erhöhen, vor allem, wie könnten wir optimieren unsere eigenen Speicherzuordnung Routinen zur festen Größe der Blöcke (einschließlich inlining der Anrufe in der letzten optimierten version).

Die Strukturen in den beiden pools waren wie folgt, wobei jede Zeile ein einzelnes byte):

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:
                               +--------+

wo:

• Kleinbuchstaben andere als x Stelle auf das Liniensegment, pool.
• Großbuchstaben zeigen Sie auf die Zeile pool.
• N wurde eine block-Nummer für die nächste Zeile (null Bedeutung war dies die Letzte Zeile in der Datei).
• P dem die Satznummer für die Vorherige Zeile (null Bedeutung war dies die erste Zeile in der Datei).
• b war der block Nummer für die erste Zeile ein segment in Linie (null-was bedeutet die Zeile leer war).
• . reservierte Polsterung (bump die Struktur auf 8 Byte).
• n war der block Nummer für den nächsten Linienabschnitt (null Bedeutung dies war das Letzte segment in der Linie).
• p war der block Nummer für das Vorherige Liniensegment (null Bedeutung dies war das erste segment in der Linie).
• L war der block Nummer für das segment s line block.
• x war die 26 Zeichen in dieser Zeile segment.

Den Grund der zeilenstruktur wurde aufgefüllt wurde, um die Geschwindigkeit der Umwandlung der block-Nummern in die tatsächlichen Speicherorte (Verschiebung nach Links durch 3 bits war viel schneller als die Multiplikation von 6 in diesem besonderen Architektur und zusätzlichen Arbeitsspeicher war nur 128 KB, minimal im Vergleich zu den Gesamt-Speicher), obwohl wir zur Verfügung stellen die langsamere version für diejenigen, die gepflegt mehr über Speicher.

Hatten wir auch ein array von 100 16-bit-Werte, die die line segment (und die Zeilennummer und so konnten wir schnell zu bestimmten Zeilen) in etwa diesen Anteil (also so, dass array[7] war die Zeile, die in etwa 7% in der Datei) und zwei gratis-Zeiger zu erhalten, die freie Liste in jedem pool (dies war eine sehr einfache Art Liste, wo N oder n in der Struktur angegeben, der nächste freie block-und frei-Blöcke zugeteilt wurden, und zurück zu setzen, die front dieser Listen).

Gab es keine Notwendigkeit zu halten die Anzahl der Zeichen in jeder Zeile segment seit 0-bytes wurden keine gültigen Dateien. Jede Strecke erlaubt war, haben 0-bytes am Ende wurden völlig ignoriert. Zeilen komprimiert wurden (D. H., Liniensegmente miteinander verbunden wurden), wenn Sie geändert wurden. Dies hielt Sperrung der Nutzung niedrig (ohne seltene und langwierige garbage collection) und auch erheblich beschleunigt und die suchen-und-ersetzen-Operationen.

Die Verwendung dieser Strukturen erlaubt sehr schnelle Bearbeitung, Einfügung, Löschung, Suche und navigation, um den text, der ist, wo Sie wahrscheinlich die meisten Ihrer performance-Probleme in einem einfachen text-editor.

Die Verwendung von Selektionen (hatten wir das nicht implementieren, da es eine text-Modus-editor, die verwendet werden vi-Befehle wie 3d löschen 3 Zeilen oder 6x löschen 6 Zeichen) konnte realisiert werden, indem eine {line#/block, char-pos} Tupel zu markieren Positionen in den text, und verwenden Sie dann zwei der Tupel für eine Auswahl.

InformationsquelleAutor paxdiablo

Wikipedia sagt, viele Redakteure nutzen eine Gap-Puffer. Es ist im Grunde ein array mit einem unbenutzten Raum in der Mitte. Der cursor sitzt genau vor der Lücke, also löschen und einfügen an der cursor-O(1). Es sollte Recht einfach zu implementieren.

Sich den Quellcode von Notepad++ (als Chris Ballance vorgeschlagen in diesem thread hier) zeigt, dass Sie auch eine Lücke Puffer. Sie könnten einige der Umsetzung von Ideen aus.

InformationsquelleAutor Greg Rogers

Check-out die Umsetzung von Notepad++ anzeigen, können Sie die Quelle auf SourceForge

InformationsquelleAutor Chris Ballance