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.
Ich denke mit den MHz die wir haben verschiebe ich den 40k Text schneller nach hinten als du realistischerweise tippen kannst.
@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.
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.