Speicherverwaltung für die Textbearbeitung

Meine erste Reaktion wäre, ein großes externes RAM zu verwenden, um die zu bearbeitenden Daten zu speichern. Aber anstatt daraus eine direkte Bildkopie zu machen, würde ich RAM-Blöcke in einer verknüpften Liste vorab zuweisen. Jeder Block hätte einen Vorwärtszeiger, einen Rückwärtszeiger, eine verwendete Größe und den Datenpuffer fester Größe.

Machen Sie jeden Block zu einer Potenz von zwei Bytes in der Größe. Das bedeutet, dass die wenigen niedrigen Adressbits für jeden Block bekanntermaßen 0 sind und daher nicht gespeichert werden müssen. Die Vorwärts- und Rückwärtszeiger könnten dann 16 Bit und die verwendete Länge 1 Byte sein, für insgesamt 5 Byte Overhead pro Block. Bei 32-Byte-Blöcken bedeutet dies beispielsweise 16 % Overhead. 1 MB RAM würde 885 kByte tatsächlichen Datenspeicher ergeben, weit mehr als die 300 kByte, die Sie angefordert haben.

Tatsächlich erzeugt dieses Schema einen linearen Speicher, in den Daten mit geringem Overhead an beliebigen Stellen eingefügt oder gelöscht werden können. Beim Hinzufügen oder Löschen müssen Sie nicht über die angrenzenden Blöcke in der Kette hinausblicken, sodass dies problemlos in menschlicher Zeit erfolgen kann.

Sie behalten zwei Ketten, eine für die Blöcke, die die Daten enthalten, und eine für die nicht verwendeten Blöcke. Nur die richtige Art der Bearbeitung an genau den richtigen Stellen kann so viel Fragmentierungsaufwand verursachen, dass der Speicher viel kleiner aussieht und schließlich nicht mehr in der Lage ist, 300 kByte aufzunehmen. Es ist jedoch unwahrscheinlich, dass eine solche spezifische Bearbeitung auftritt, und Sie können immer einfache lokale Neukombinationen durchführen (wenn zwei benachbarte Blöcke weniger Daten als ein Block enthalten, dann führen Sie die beiden zusammen und setzen Sie einen wieder auf die freie Liste), die die meiste Zeit beibehalten werden Fragmentierung gut genug. Fragmentierung spielt keine Rolle, bis Sie einen freien Block benötigen und keiner vorhanden ist. Wenn das passiert, führen Sie eine Defragmentierung durch und der Benutzer muss einige Sekunden warten, aber das wird sehr selten sein. Eine gute Strategie wäre die automatische Defragmentierung im Hintergrund während der (aus Sicht des Prozessors) unvermeidlichen langen Zeiträume, in denen der Benutzer nichts tut. Mit dieser Strategie halte ich es für sehr sehr unwahrscheinlich, dass Ihnen jemals die freien Blöcke ausgehen und Sie defragmentieren müssen, während der Benutzer wartet.

Dieses Schema ist selbst in einem kleinen Mikrocontroller einfach zu verwalten, die Benutzerreaktion auf Bearbeitungsvorgänge ist schnell, und auf die SD-Karte wird nur zu Beginn und am Ende von Bearbeitungssitzungen zugegriffen.

Hinzugefügt:

Ich habe nach dem Schreiben des Beitrags mehr über Fragmentierung nachgedacht, und ich denke, es kann gezeigt werden, dass Sie nie mehr als die Hälfte des verfügbaren Speichers verlieren, solange Sie bei einer Einfüge- oder Löschoperation eine einfache lokale Defragmentierung durchführen. Wenn Sie das Beispiel von 1 MB Speicher mit 32-Byte-Blöcken erneut verwenden, werden Ihnen mindestens 442 kByte Speicherplatz garantiert.

Nach einem Löschvorgang führen Sie den Block, bei dem ein Byte gelöscht wurde, mit einem seiner Nachbarn zusammen, wenn die beiden zusammen jetzt Daten im Wert von einem Block oder weniger enthalten. Bei einer Byte-Hinzufügung fließen Daten vom aktuellen Block in einen Nachbarn, um Platz zu schaffen, anstatt einen neuen Block zu greifen, es sei denn, beide Nachbarn (und natürlich der aktuelle Block) sind vollständig voll.

Alle diese Operationen umfassen nie mehr als 3 Blöcke, sind also in menschlicher Zeit augenblicklich. Wenn Sie mit bis zur Hälfte des verfügbaren Speicherplatzes leben können, brauchen Sie nichts weiter zu tun. Es schadet jedoch kaum, eine Hintergrunddefragmentierung durchzuführen, wenn nichts anderes vor sich geht.

Dies ist ein grundlegendes Programmierproblem, das Sie bequemer auf einem PC lösen können, ohne sich sofort um den PIC zu kümmern, obwohl Sie offensichtlich nach einer kleinen effizienten Lösung suchen werden!

Ein anderer Ansatz – praktikabel, wenn Sie ein Zeichen oder eine Sequenz angeben können, die nicht im Text vorkommen können – besteht darin, einige Bytes in Ihrem Textpuffer (der ein externer RAM sein könnte) durch diese Sequenz gefolgt von einer Zahl zu ersetzen. Dies verhält sich wie ein Software-Haltepunkt in einem Debugger: Wenn File/Save diesen Haltepunkt sieht, schlagen Sie die Nummer in einer Liste der Änderungen nach. Es enthält die Zeichen, die Sie entfernt haben, sowie alle Änderungen.

Wenn die Liste der Änderungen voll wird, müssen Sie das Dokument erneut synchronisieren, um die Liste zu leeren; Dies könnte auch eine automatische Speicheroperation sein. (Bis zu diesem Punkt haben Sie auch eine Undo-Funktion!)

Sie möchten die Anzahl der Schreibvorgänge auf der SD-Karte minimieren - also nur automatisches Speichern und Datei-/Speichervorgänge des Benutzers, anstatt jede Änderung auf SD zu schreiben.

Für einen einfachen Texteditor ist die Lückenpuffermethode sehr effektiv. Ich habe es verwendet, als ich Anfang der 1980er Jahre einen Editor für meinen Ferguson Big Board-Computer (Z80-basiertes CP/M) schrieb, und ich fand es sehr einfach, damit zu arbeiten. Natürlich konnte ich einige einfache Z80-Anweisungen verwenden, die es sehr effizient machten, Text über die Lücke zu verschieben.

Diese Methode lässt sich auch gut auf die gleichzeitige Bearbeitung mehrerer Dateien erweitern, vorausgesetzt, sie passen alle zusammen in den verfügbaren Arbeitsspeicher. Sie verketten sie einfach miteinander, und die Lücke besteht nur in der Datei, die derzeit den "Bearbeitungsfokus" hat. Sie müssen einige Zeiger (oder Markierungen) für die Dateigrenzen behalten und sie nach Bedarf behandeln, wenn Sie die Lücke verschieben.

Die externe RAM-Nutzung ist sicherlich das beste Schema. Ein Lückenpuffer kann den Teststrom in die untere Hälfte an einem Ende Ihres Speicherpools und die obere Hälfte an der anderen Seite des Speicherpools aufteilen. Lokale Einfügungen und Löschungen können dann über die Lückenspanne hinweg durchgeführt werden, indem einfach kleine Datenmengen über den Lückenrand auf die eine oder andere Weise verschoben werden.

Die Verwendung eines Lückenpuffers kann eine gute Strategie für eine dynamische Verwendung sein. Sie können sich darauf konzentrieren, an der aktuellen Position des Bearbeitungsfokus ein Loch zu öffnen, damit neue Daten Platz haben. Zunächst können Sie ein Umleitungs-Tag an der Fokusposition platzieren, indem Sie gerade genug vorhandenen Text entfernen, um Platz für das Einfügen des Tags zu schaffen. Dann können Sie in einem separaten Arbeitspuffer, auf den das Tag verweist, den ursprünglich entfernten Text erfassen und dann jeden neu eingegebenen Text hinzufügen. Mit einer cleveren Programmierung können Sie einen parallelen Prozess ausführen, der das In-Memory-Bild aufteilt, um die Lücke zu aktualisieren und entfernt dann das Umleitungs-Tag und den damit verbundenen temporären Bearbeitungspuffer.

Dieses Schema ermöglicht, dass eine Liste von Umleitungs-Tags (und ihren Arbeitspuffern) dynamisch zurückgefordert wird, sodass Sie selten eine „Liste voll“-Bedingung erhalten würden. Die Prämisse ist natürlich, dass während einer Editiersitzung die durchschnittliche Ankunftsrate neuer Daten langsamer kommt, als das Programm den Lückenbereich verschieben und die Umleitungs-Tags zurückfordern kann.

Noch ein Hinweis zur Idee, Tags in den Textfluss einzufügen. Tags können auch für andere Zwecke verwendet werden, als nur zu markieren, wo Sie ein Umleitungs-Tag platziert haben. Es kann eine gute Idee sein, Tags so zu markieren, dass Sie sie im Textstrom finden können, egal ob Sie den Text vorwärts oder rückwärts durchsuchen. Am einfachsten ist es natürlich, das Tag mit demselben Tag-Indikator an jedem Ende einzubetten.

Vieles hängt von der Art der Operationen ab, die Sie durchführen müssen. Wenn Sie Daten vorübergehend als Liste von Zeilen mit fester Länge speichern können, können Sie einen Blockzuordner mit fester Größe verwenden, um die einzelnen Zeilen in beliebiger Reihenfolge zu speichern, und dann ein RAM-Array oder einen Lückenpuffer (möglicherweise in einem externen RAM-Gerät) verwenden ), um lineare Zeilennummern in Chunk-Positionen umzuwandeln. Man könnte auch Zeilen variabler Länge mit einem Stückzuordner variabler Länge verwenden oder Stücke mit fester Größe verwenden, aber jedes Stück eine Zahl enthalten lassen, die entweder die Anzahl der verwendeten Bytes oder die Länge des nächsten Stücks angibt. Verwenden Sie einen RAM-Puffer, um die aktuelle Zeile zu halten, sodass auf das Chunk-Array nur zugegriffen werden muss, wenn der Cursor davon weg bewegt wird. SD-Karten sind ausreichend groß, selbst wenn jede Zeile in einer temporären Datei auf 256 Bytes aufgefüllt wird, sollte dies wahrscheinlich nicht der Fall sein. t stellen zu viele Schwierigkeiten. Alle 256 Bytes würden entweder ein FF-Byte und eine Länge oder eine Zwei-Byte-Blocknummer enthalten; das würde Dateien von bis zu etwa 8 Megabyte und 32767 Zeilen ermöglichen.