Hallo Leute,
ich habe mal eine etwas theoretische Frage (der Betreff ist vielleicht
nicht ganz passend).
Wie würde man einen Text-Editor auf einem Mikrocontroller schreiben (ich
weiß der hat wenig speicher, aber bei den Mini-Computern mit 1-2 kB
gings ja auch :-), außerdem ist das wie gesagt eher hypotethischer
natur) ?
Mir geht es eigentlich nur um eine spezielle Sache :
Wenn ich irgendwo in einer zeile (mitten im text) bin, und füge dann
neue zeichen ein, wie wird das intern gehandhabt ? Ich kann mir nur
schwerlich vorstellen das in guter alter "mit-dem-kopf-durch-die-wand"
manier alle zeichen um eines nach hinten kopiert werden (dann würde das
editieren umso langsamer werden je größer der bisherige text ist, und je
weiter man am anfang des textes steht). Mir ist der Begriff verkettete
liste zwar geläufig (und auch verständlich), aber auch da kann ich mir
nur schwer vorstellen das für jedes/bzw. mehrere zeichen (bzw. jede
zeile in der man neue zeichen anhängt oder löscht) jeweils ein neues
element in einer liste eingetragen wird. vor allem wenn man oft zwischen
den zeilen hin und her springt kommt doch am ende nur noch eine
spaghetti-liste raus die unnötig speicher frisst. ich kann mir nur
schwer vorstellen das man das damals bei den 8 bittern mit 1-8kB
speicher so gemacht hat (abgesehen vom c64, der hatte speicher der
reicht bis 2050 :-))), oder täusche ich mich da ?
gruß
rene
> Ich kann mir nur> schwerlich vorstellen das in guter alter "mit-dem-kopf-durch-die-wand"> manier alle zeichen um eines nach hinten kopiert werden
Wie war das noch gleich - du wolltest das doch auf einen 1-2K Rechner
machen. Grad da ist diese Schieberei völlig akzeptabel.
Willst du Logfiles vom 50MB-Kaliber verarbeiten, ist das nicht drin
(probier's mal mit Windows Notepad). Aber da hast du i.A. Systeme, die
ausgiebig Verwendung dynamischen Speichers zulassen. Also jede Zeile
einzeln speichern können.
>Wie war das noch gleich - du wolltest das doch auf einen 1-2K Rechner>machen. Grad da ist diese Schieberei völlig akzeptabel.
ok jetzt bin ich mit meinem eigenen beispiel auf die nase gefallen :-)
da würde es sicherlich gehen. ich meine jetzt aber auch keine 50mb
log-files.
sagen wir mal texte im bereich 10-40kByte (also richtung c64).
da würde man also wirklich nur mit der methode der verketteten liste
vorankommen ?
ich meine speicherverwaltung muß dort schon sein, aber kann es dann
nicht sehr schnell passieren das durch die ganzen zusätzlichen
text-schnipsel der speicher ratz-fatz überläuft ?
oder muß man da einen kobminierten weg gehen (nach dem motto, die zeilen
[+ neuen textschnipsel] die gerade nicht sichtbar sind werden im
hintergrund zusammengefügt um den zusätzlich benötigten speicher für die
listeneinträge wieder freizugeben) ?
Bei einer "normalen" Verketteten Liste würdest Du aber pro gespeichertes
Zeichen (Byte) einen Zeiger (2/4 Byte) verbraten. Ein "gemischter"
Ansatz wäre effizienter: Verkettete Liste (bzw. Array) aus
Zeilen-Arrays. Dann muss man aber die Zeilenumbrüche extra behandeln.
Bei "kleinen" Datenmengen ist wahrscheinlich aber selbst der brute-force
Ansatz so schnell, dass man beim Text bearbeiten keine Verzögerung
mitbekommt.
Auch 10K sind nicht wirklich viel für's rumschieben auf einem 20 MIPS
AVR.
Aber das geht natürlich auch anders. Ein Ansatz wäre beispielsweise, die
grad aktive Region vom Text sozusagen herauszuschneiden, separat zu
verarbeiten und zum Hauptteil wieder anzufügen was dabei unten oder oben
rausfällt. Dann hast du Speicherstrukturen ohne Verlust durch dynamische
Speicherverwaltung und trotzdem gute Reaktionszeiten.
@micha
also für jedes eingefügte zeichen würde ich es auch nicht machen. da
bräuchte man pro eigegebenem zeichen etwa 3 zeichen (bei 16bit
adressraum) is ein bissl viel overhead. dachte da eher an den von dir
genannten ansatz mit festen blöcken (beispielsweise 16 zeichen) und der
verketteten liste.
und dann noch text im hintergrund bearbeiten (oder eben nur den aktiven
bereich bearbeiten) um speicher wieder freizumachen scheint mir der
ansatz ser wahl zu sein.
ich denke so oder so ähnlich hat man es zu c64 zeiten gemacht (dabei
meine ich noch nichteinmal den basic-editor, sondern editoren wie
vizawrite oder den input-64-assembler (der einen echt hammergeilen
editor hatte))
@realpotter
problematisch wirds aber wenn du einen langsamen externen speicher hast.
nicht jeder mikrocontroller hat 64kB on chip :-))
darauf zielte die frage auch ein wenig ab. da man kaum ein komplettes
text-file in der größe 10-100kB im internen ram eines uCs halten kann
(weil die i.d.r. halt nicht soviel haben) muß man sich mit einem
externen speicher behelfen, und da hören die etlichen mhz halt auf,
sodas man auf andere tricks&kniffe zurückgreifen muß
Was hälst Du vom Ansatz, den Text in unterschiedliche Files (Dateien
oder Arrays) aufzuteilen?
Im einfachsten Fall wären es immer zwei Files: File-A und File-B. File-A
geht bis zur aktuellen Curser-Position, File-B ist der Rest des Textes
bis zum Schluss.
Dargestellt, werden dann immer File-A + File-B, Zeilenumbrüche werden
erst bei der Darstellung dynamisch dargestelt, solange nicht ein [CR+LF]
explizit eingetippt wurde.
Das Umkopieren von Daten zwischen den Files wird erst erforderlich, wenn
ab einer neuen Curser-Position Zeichen eingefügt bzw. gelöscht werden
sollen.
So können auch Dateien auf einer Disk bearbeitet werden, die selber
längst nicht mehr ins RAM passen...
MfH Peter
@peter
>Im einfachsten Fall wären es immer zwei Files: File-A und File-B. File-A>geht bis zur aktuellen Curser-Position, File-B ist der Rest des Textes>bis zum Schluss.
das problem wird dasselbe sein : was passiert wenn ich 2 zeilen über der
aktuellen "ende"-position der datei was einfüge.
und bei den dateien müsste ich ja dann jedesmal nachdem ich zeichen
angefügt (oder gelöscht habe) diese wieder speichern und neu laden :-)
Hat das jetzt irgendeinen konkreten Bezug, oder geht es nur darum,
rauszufinden wie man vor 30 Jahren auf einem Rechner mit 8KB Speicher
arbeiten konnte?
Kein Schwein editiert heute Texte auf so einer Schmalspurbüchse, schon
garnicht welche die grösser sind als sein Hauptspeicher. Und noch der
kleinste PDA hat zig MB Speicher.
Um dieses grundsätzliche Problem wirst Du nicht herumkommen, irgendwann
muss der Text neu organisiert, geordnet, zusammengefügt bzw. gespeichert
werden, es sei denn Du arbeitest mit verketteten Listen, die Du nie
reorganisierst.
Du kannst natürlich mit mehreren Files arbeiten, bzw. für jede
Editierposition ein neues File generieren, und erst am Schluss beim
sichern der Arbeit die Fragmente neu zusammenfügen zu einer einzigen
Datei.
Was ich auch schon gesehen habe, dass sich ältere Editoren in ihrer
File-Struktur an die Sektorgrössen der Disk(ette) orientieren...
das ganze hat folgenden hintergrund :
ich habe ein fpga board und darauf eine vga-grafik-einheit implementiert
die mit hardware-unterstützung bitmaps sehr schnell kopieren kann.
nun kann ich mit dieser grafikkarte sehr einfach fenster-operationen
machen (die auch recht schnell sind). als eine anwendung (die schon
funktioniert) habe ich ein terminal das einfach den text runterrasselt.
ich möchte aber nun diesen text (den ich im speicher der grafikkarte
halten kann, da ich dort noch nette 256-512 kbyte frei habe) editieren
können.
das ganze ist zwar erstmal als "jux und dollerei" abzutun, aber da ich
auch einen parser bzw. tokenizer (auch recht schnell) habe kann man sehr
einfach einen interpreter bzw. eine scriptsprache implementieren. mit
einem text-editor (und noch einer speichermöglichkeit auf sd-karte o.ä.)
wäre dann ein komplettes mini-computer system fertig mit dem sich dann
auch recht große scripte/programme ausführen lassen.
das ganze kann man also eher richtung : me too ! oder projekte die die
welt nicht braucht :-) abtun. (aber spaß machts trotzdem :-))
gruß
rene
>Um dieses grundsätzliche Problem wirst Du nicht herumkommen, irgendwann>muss der Text neu organisiert, geordnet, zusammengefügt bzw. gespeichert>werden, es sei denn Du arbeitest mit verketteten Listen, die Du nie>reorganisierst.
gerade dieses reorganisieren scheint mir der einfachste weg zu sein.
man muß ja einfach nur die zeilen die man gerade nicht "anpackt" im
hintergrund neu zusammenfügen (quasi mehrere verkettete listen [durch
das editieren aufgesplittet] zu einer liste neu"aufräumen").
erst beim speichern werden die listen dann zeile für zeile einfach raw
weggeschrieben und man hat einen text ohne listenoverhead.
beim editieren kommt man wohl nicht drum herum.
