REDIM: Größenänderung von Feldern
Wohl jede höhere Programmiersprache bietet sie, wohl jeder Programmierer nutzt sie: die Datenfelder. Sie sind ja auch toll. Da kann man Tausende von Werten statt in Tausende von Variablen in einem Feld unter demselben Namen speichern. Allerdings kommt es vor, daß die Anzahl der benötigten Elemente nicht genau bekannt ist, weil man z.B. bei einer Adressen Verwaltung ja nicht weiß, wie viele Typen der Benutzer kennt.
Ist unbekannt, wie groß das Feld sein muß, kann sowohl eine zu große als auch eine zu geringe Dimensionierung unpraktisch sein. Eine zu große Dimensionierung verbrät unnötig Speicher für andere Zwecke, eine zu geringe engt das Programm in den Möglichkeiten ein. Man kann zwar in GFA-BASIC ein Feld löschen und danach mit anderer Dimensionierung neu erzeugen, was in einigen anderen Sprachen nicht geht. Das ist zwar wahnsinnig flott, jedoch geht der Inhalt des Feldes verloren.
Eine zweite Lösung wäre es, ein zweites Feld zu erzeugen, den Inhalt des ersten Feldes in das zweite zu kopieren, die Felder mittels SWAP zu vertauschen und dann das zweite Feld zu löschen. Das ist dann wohl die Lösung. Der Inhalt des Feldes bleibt erhalten, und bei mehreren größeren Feldern ist die dringend nötige Pause zum Kaffee holen gleich integriert.
Was ist aber, wenn man keinen Kaffee mag? Oder wenn man von Natur aus ungeduldig ist? Dann bleibt nur noch die dritte Lösung, nämlich die Anwendung des vorliegenden REDIM-Programms. Es ändert die Größe eines Feldes, ohne dessen Inhalt zu zerstören und ohne lange Wartezeiten. Dafür funktioniert es nur mit eindimensionalen Feldern.
Nun kommt die Standardfrage: Wie macht das Programm das bloß? Grundsätzlich unterscheidet REDIM zwischen numerischen (Bit-, Byte-, Word-, Integer-und Real-Felder) und String-Feldern.
Numerische Felder
In der Abbildung 1 finden Sie den Aufbau eines numerischen Feldes. Die Funktion Arrptr liefert die Adresse des Arraypointers oder Feldzeigers. Dieser Feldzeiger enthält als erstes einen Zeiger auf den Felddeskriptor, das folgende Wort enthält die Anzahl der Dimensionen. Der Zeiger auf den Felddeskriptor zeigt eigentlich auf das Ende des Felddeskriptors, zumindest bei eindimensionalen Feldern. Dies liegt daran, daß die Informationen im Deskriptor vor der Adresse, auf die der Zeiger zeigt, erst ab der GFA-BASIC-Version 3.0 enthalten sind. Gehen wir den Felddeskriptor einmal kurz durch. Das Langwort, auf das der Zeiger im Feldzeiger zeigt, enthält die Anzahl der Elemente des Feldes in der ersten Dimension. Das Langwort davor enthält die Länge des Feldes in Bytes plus der Länge des Deskriptors. Bei eindimensionalen Feldern ist er drei Langwörter, also 12 Bytes lang. Das Langwort vor der Längenangabe ist ein Backtrailer. Er zeigt auf den Feldzeiger zurück. Er dient zur Beschleunigung der Feldbearbeitung. Unmittelbar nach dem Eintrag, der die Anzahl der Elemente angibt, folgen die Feldelemente. Die Länge eines Elements ist abhängig vom Typ des Feldes. Wäre das Feld mehrdimensional, würden statt der Feldelemente zuerst die Anzahl der Elemente in der zweiten Dimension, danach die der dritten Dimension usw. folgen, je nach der Anzahl der Dimensionen. Aber wir betrachten ja sowieso nur eindimensionale Felder.
REDIM geht nun folgendermaßen vor: Als erstes erzeugt es, je nach Typ des Feldes, ein zweites Hilfsfeld mit der Größe der neuen Dimensionierung. Sämtliche Einträge für Feldzeiger und Felddeskriptor regelt also das GFA-BASIC für uns. Da die Feldelemente nun linear, also aufeinanderfolgend, im Speicher liegen, werden sie mittels BMOVE vom ersten Feld ins zweite kopiert. Wird das Feld kleiner gemacht, das heißt, ist das Hilfsfeld kleiner als das Original, wird nur soviel kopiert, wie hineinpaßt, ansonsten wird alles hineinkopiert. Anschließend werden Hilfsfeld und Originalfeld mittels SWAP vertauscht und das Hilfsfeld gelöscht. Fertig!
String-Felder
Schauen wir uns den Aufbau eines String-Feldes genauer an (s. Abb.2): Der Aufbau des Feldzeigers und des Felddeskriptors ist mit numerischen Feldern identisch. Es existieren also auch die Einträge für die Feldlänge und den Backtrailer. Diese waren in bisherigen Dokumentationen nicht angegeben. Anstelle der Feldeinträge allerdings finden wir nach dem Felddeskriptor pro String des Feldes einen String-Deskriptor. Er besteht aus einem Langwort und einem Wort. Das Langwort zeigt auf den Anfang des Strings, das Wort gibt die Länge des Strings an. Die Strings selbst sind irgendwo im Speicher verstreut. Da ihre Länge flexibel ist, kann man sie nicht linear im Speicher anordnen. Den Strings folgt nach ihrem letzten Zeichen der sog. Backtrailer. Er liegt immer auf einer geraden Adresse, so daß bei Strings mit ungerader Länge zwischen Inhalt und Backtrailer noch ein Lücken-Byte eingeschoben wird. Der Backtrailer des Strings zeigt aber nicht, wie sonst angegeben, auf den Anfang des Strings, sondern auf seinen String-Deskriptor! Das Gerücht, daß der Backtrailer auf den String-Anfang zeige, hält sich seit einiger Zeit. Ich habe es schon in verschiedenen Artikeln in unterschiedlichen Zeitschriften gefunden. Es ist aber falsch! Auch bei Strings, die nicht an ein Feld gebunden sind, zeigt der Backtrailer auf den String-Deskriptor zurück. Der Eintrag der Länge des Feldes im Felddeskriptor berücksichtigt übrigens nicht die Länge der Strings, sondern gibt die Länge der String-Deskriptoren zusammen plus der des Felddeskriptors an.
REDIM geht bei String-Feldern folgendermaßen vor: Es erzeugt wiederum wie bei den numerischen Feldern ein Hilfs-String-Feld. Die String-Deskriptoren des Onginalfeldes werden in die Deskriptoren des Hilfsfeldes kopiert. Dies genügt aber noch nicht, da die Backtrailer der Strings noch auf die Deskriptoren im Originalfeld zeigen. Erst, wenn diese auf die neuen Deskriptoren umgebogen sind, kann man die Felder tauschen und das Hilfsfeld löschen. Das Kopieren der Deskriptoren und das Verbiegen der Backtrailer erledigt eine kleine Maschinenspracheroutine, da das Verbiegen in einer B ASIC-Schleife zu lange dauern würde.
Geschwindigkeit
Wie oben bereits erwähnt, ist REDIM sehr viel schneller als eine vergleichbare normale BASIC-Routine, die jedes Element einzeln vertauscht. Wieviel schneller, läßt sich nicht genau festhalten. Dies hängt zu sehr vom Datentyp, der Größe des Feldes vorher und hinterher sowie vom Größenunterschied ab. Bei numerischen Feldern ist REDIM zehn- bis fünfzehnmal schneller. Bei sehr großen Feldern wächst dieser Vorsprung noch an, so ist z.B. REDIM mit 1,6 Sekunden gegenüber einer herkömmlichen Routine mit 46,1 Sekunden bei einem Integerfeld mit 250.000 Elementen rund 28mal schneller. Im Extremfall (5.000.000 Booleans) ist REDIM sogar rund 950mal schneller! Bei sehr kleinen Feldern (ca. 10 Elemente) sind die Zeiten dagegen ungefähr gleich. Diese Zeiten gehen davon aus, daß sich die Größe des Feldes nicht ändert. Allgemein wächst die Zeit, die eine normale Routine braucht, linear abhängig von der Anzahl der Elemente, während REDIM normalerweise auch bei riesigen Feldern unter zwei Sekunden benötigt. Bei String-Feldern gilt ungefähr das gleiche wie oben, nur daß die magische Zeitgrenze hier bei drei statt zwei Sekunden liegt.
Um in den Genuß von REDIM zu kommen, tippt man einfach das Listing REDIM.LST ein und speichert es auf Diskette. Nun kann man es einfach beliebigen Programmen hinzuMERGEn - fertig. Ach ja, die Bedienung. REDIM wird folgendermaßen aufgerufen:
REDIM(*Feld(),Anzahl%,Zurueck%)
Alternativ dazu geht auch:
REDIM(ARRPTR(Feld()),Anzahl%,Zurueck%)
Beim Parameter Feld dürfen Sie keinesfalls die Klammern nach dem Feldnamen vergessen! Ansonsten wird der Prozedur der Zeiger auf eine einfache Variable übergeben, womit sie nichts anfangen kann. Außerdem muß natürlich ein eventuelles Postfix mit angegeben werden, also z.B. für ein Integerfeld usw. Der Parameter Anzahl% gibt an, wie viele Elemente das Feld bekommen soll. Er ist identisch mit dem Wert, der einem normalen DIM-Befehl übergeben werden würde. Zurueck% ist eine Variable, der REDIM einen bestimmten Wert zu weist, je nachdem, wie die Redimensionierung ausgegangen ist. Ein Wert von Null signalisiert, daß alles glattgegangen ist. Werte ungleich Null signalisieren einen Fehler. Dabei bedeutet ein Wert von 8, daß der Speicherplatz nicht ausreicht. Da REDIM ein Hilfsfeld erzeugt, muß so viel Speicher frei sein, daß gleichzeitig sowohl das alte als auch ein Feld in der neuen Größe hineinpaßt. Eine zurückgegebene 17 bedeutet, daß ein negativer Wert als neue Feldgröße übergeben wurde, was ja nicht viel Sinn macht. Ein Wert von 28 bedeutet, daß irrtümlich ein mehrdimensionales Feld übergeben wurde. Wir erinnern uns, REDIM arbeitet nur mit eindimensionalen Feldern-. 64 bedeutet, daß eine normale Variable oder sonst irgendetwas übergeben wurde, aber kein Zeiger auf ein Feld. 15 schließlich bedeutet, daß das Feld gar nicht existiert. Wer nun fragt, wie die krummen Fehlerwerte zustandegekommen sind, möge sie mit den Fehlernummern des GFA-BASICs vergleichen. REDIM arbeitet übrigens unabhängig vom Rechnertyp und Betriebssystem, Hauptsache, GFA-BASIC läuft. Ach ja, die Versionsnummer des BASIC muß mindestens 3.0 sein.
Bei der Nutzung von REDIM muß man übrigens darauf achten, daß es bei der String-Redimensionierung eine kleine Maschinenspracheroutine benutzt. Dies ist deshalb wichtig, weil der Code aus DATA-Zeilen eingelesen wird. Man muß deshalb beachten, daß REDIM beim ersten Aufruf mit einem String-Feld als zu redimensionierendem Feld den Data-Zeilen-Zeiger verändert. Der erste Aufruf ist hierbei nicht nur der erste nach Programmstart, sondern auch nach jedem CLEAR-Befehl. Wer sich übrigens im Listing bei der Berechnung, ob der Speicherplatz ausreicht (Zeile 19), über den Offset von 524 wundert: Das GFA-BASIC braucht, um Befehle auszuführen, selbst einen gewissen Speicherplatz. Wenn aller Speicher durch Variablen belegt ist, kann es nicht einmal mehr eine Print-Anweisung durchführen. Wieviel Speicher das BASIC braucht, habe ich nicht genau ermittelt, also habe ich großzügig ein halbes Kilobyte offengehalten. Dazu kommen noch 12 Bytes für den Felddeskriptor des neuen Feldes - macht zusammen 524 Bytes.
Das Demoprogramm...
... zu REDIM ist zugegebenermaßen nicht sehr sinnvoll, verdeutlicht aber, so hoffe ich, den Einsatz von REDIM, gerade im Zusammenhang mit den BASIC-Befehlen Insert und Delete. Denn normalerweise bewirkt Insert (bei einem vollen Feld), daß das letzte Element verlorengeht, während Delete das Feld mit Nullen auffüllt. Dies kann man mit REDIM verhindern. Das Demoprogramm erzeugt zuerst ein Feld mit 10 Buchstaben. Anschließend wird pro Durchgang ein neuer Buchstabe zufällig aus dem Alphabet gesucht. Kommt dieser im Feld vor, wird er gelöscht. Wenn nicht, wird er alphabetisch richtig eingefügt. Dabei wird in jedem Durchgang das Feld automatisch auf die passende Größe gebracht. Wie gesagt, nicht sehr sinnvoll, aber anschaulich.
; Sourcecode zur Routine REDIM.INL, die von MKINLINE.GFA erzeugt wird.
; Kopiert die Stringzeiger eines Feldes in ein zweites und verbiegt dabei
; die Backtrailer der Strings, so daß diese dann zum zweiten gehören.
; Autor: Gerald Schmieder (c) MAXON Computer 1993
; Erstellt mit dem TURBOASS.
movea.l 4(sp),a0 ; Adr.d.Feldinformation d.Originals
movea.l 8(sp),a1 ; Adr.d.Feldinformation d.Ziels
moveq #-2,d3 ; Vorbelegt f. schnelleres 'and'
moveq #0,d4 ; Vorbelegt f. schnelleres 'cmp'
move.l (a0)+,d0 ; Anz.d.Einträge im Original
move.l (a1)+,d1 ; Anz.im neuen Array
cmp.l d1,d0 ; Ist das neue Array kleiner?
blo.s change ; nein => alles klar
move.l d1,d0 ; Sonst Anzahl der neuen Elemente nehmen
change:
movea.l (a0)+,a2 ; Adresse des Strings
cmpa.w d4,a2 ; ist a2 ein Nullzeiger?
beg.s empty ; ja => String ist leer
move.w (a0)+,d1 ; Länge in Bytese
move.w d1,d2 ; nochmal kopieren
addq.w #1,d2 ; + 1 \
and.w d3,d2 ; begradigen / wg. möglichem Nullbyte
move.l a1,0(a2,d2.w) ; Backtrailer verbiegen
move.l a2,(a1)+ ; Zeiger in Zielfeld kopieren
move.w d1,(a1)+ ; Länge in Zielfeld kopieren
next:
subq.l #1,d0 ; kein dbra, da Felddimension
bne.s change ; 16 Bit überschreiten könnte!
rts
empty:
addq.l #2,a0 ; Länge überspringen
addq.l #6,a1
bra.s next
END
' REDIM --- Redimensioniert beliebige eindimensionale Felder sehr schnell
' Autor: Gerald Schmieder (c) MAXON Computer 1993
'
' Aufruf: Redim(*Feld(),Elemente^,Zurueck%)
' Oder: Redim(Arrptr(Feld()), Elemente%, Zurueck%)
' Feld = Name des Feldes plus Postfix. Klammern '()' nicht vergessen!
' Elemente% = Anzahl der Elemente nach der Redimensionierung (wie DIM)
' Zurueck% = Rückgabewert. 0 => kein Fehler, sonst wie GFA-Fehlermeldungen
' ACHTUNG ! Beim ersten Aufruf (nach Programmstart oder nach jedem CLEAR)
' mit einem Stringfeld verbiegt REDIM den DATA-Zeilen-Zeiger!!!
PROCEDURE redim(ptr%,new%,VAR return%)
LOCAL elements%,ram%,typ%,adr%
IF new%>0 ! Neue Arraygrenze nicht negativ?
IF {ptr%}<>0 ! Gibt's das Feld überhaupt?
typ%=TYPE(ptr%)
IF (typ%>3 AND typ%<8) OR typ%=12 OR typ%=13 ! Zeigt der Pointer auf ein Feld?
IF WORD{ptr%+4}=1 ! Feld eindimensional?
elements%={{ptr%}}
ram%=({{ptr%}-4})-12
! Speicherverbrauch ohne Felddeskriptor
IF FRE(0)>(ram%/elements%)*new%+524 ! Reicht der Speicher aus?
IF typ%=5 ! String-Feld
INLINE change_backtrailer%,56
IF LPEEK(change_backtrailer%)<>&H206F0004 ! Code installiert?
RESTORE change_back_data ! Wenn nicht, Maschinencoderoutine
FOR i%=0 TO 55 ! i.d.Speicher bringen
READ j%
POKE change_backtrailer%+i%,
NEXT i%
change_back_data:
DATA 32,111,0,4,34,111,0,8,118,254, 120,0,32,24,34,25,176,129,101,2,32
DATA 1,36,88,180,196,103,22,50,24,52,1,82,66,196,67,37,137,32
DATA 0,34,202,50,193,83,128,102, 230,78,117,84,136,92,137,96,244
ENDIF
DIM hilfs__$(new%)
VOID C:change_backtrailer%(L:{ptr%}, L:(*hilfs__$()}) ! Verbiegt die Backtrailer u.kopiert d.Stringzeiger
SWAP *ptr%,hilfs__$() ! Nun wird endgültig vertauscht
ERASE hilfs__$()
ELSE
SELECT typ% ! Je nach Typ des Originalfeldes Hilfsfeld erzeugen und Zeiger dafür ermitteln
CASE 4 ! Real-Array
DIM hilfs___(new%)
adr%={*hilfs___()}+4
CASE 6 ! Integer-Array
DIM hilfs___%(new%)
adr%={»hilfs___%()}+4
CASE 7
DIM hilfs___!(new%) ! Boolean-Array
adr%={*hilfs___!()}+4
CASE 12 ! Word-Array
DIM hilfs___&(new%)
adr%={*hilfs___&()}+4
CASE 13 ! Byte-Array
DIM hilfs___|(new%)
adr%={*hilfs___|()}+4
ENDSELECT
IF new%<elements% ! Wird das Feld größer o. kleiner redimensioniert?
BMOVE {ptr%}+4,adr%, {adr%-8}-12
! Kleiner => kopiere soviel, wie ins neue Feld paßt
ELSE
BMOVE {ptr%}+4,adr%,ram% ! Größer => Verschiebe das ganze Feld
ENDIF
SELECT typ% ! Nun je nach Originalfeld dieses und Hilfsfeld tauschen und Hilfsfeld löschen
CASE 4
SWAP *ptr%,hilfs___()
ERASE hilfs___()
CASE 6
SWAP *ptr%,hilfs___%()
ERASE hilfs___%()
CASE 7
SWAP *ptr%,hilfs___!()
ERASE hilfs___!()
CASE 12
SWAP *ptr%,hilfs___&()
ERASE hilfs___&()
CASE 13
SWAP *ptr%,hilfs___|()
ERASE hilfs___|()
ENDSELECT
ENDIF
return%=0 ! Kein Fehler aufgetreten
ELSE
return%=8 ! Speicher voll
ENDIF
ELSE
return%=28 1 Feld muß eindimensional sein
ENDIF
ELSE
return%=64 ! Pointer falsch
ENDIF
ELSE
return%=15 ! Feld nicht dimensioniert
ENDIF
ELSE
return%=17 ! Dim zu groß (bei neg.Wert, macht GFA-Basic auch so!)
ENDIF
RETURN
’ Demo-Programm zu REDIM
' (c) MAXON Computer 1993
' Erzeugt ein Feld mit 10 Buchstaben (jeder 2.
' Buchstabe von A bis S). Sucht danach zufällig
' einen Buchstaben aus dem Alphabet. Ist dieser
' Buchstabe schon im Feld, wird er dort gelöscht
' und das Feld verkleinert. Sonst wird er
' alphabetisch eingefügt und das Feld vergrößert
' Beenden mit "Q"
OPTION BASE 1
DIM feld$(10)
FOR i%=1 TO 10
feld$(i%)=CHR$(63+2*i%)
NEXT i%
REPEAT
neu$=CHR$(65+RANDOM(26)) ! Neuer Buchstabe
CLS
PRINT "Arraygröße : ";DIM?(feld$());" Einträge Gewählter Buchstabe ";neu$
PRINT
FOR i%=1 TO DIM?(feld$()) ! Feld anzeigen (vor Änderung)
PRINT feld$(i%)'
NEXT i%
c%=INP(2)
i%=1
WHILE feld$(i%)<neu$ AND i%<DIM?(feld$())
! Hier werden bis auf den letzten
INC i% ! alle Buchstaben im Feld,
! die kleiner sind als
WEND ! der gewählte Buchstabe,
! übersprungen
IF feld$(i%)=neu$ ! Sind die Buchstaben gleich
DELETE feld$(i%) ! Ja => Buchstabe löschen
redim(*feld$(), DIM?(feld$())-1, void%)
! Feld verkleinern
ELSE ! Sonst ...
redim(*feld$(), DIM?(feld$())+1,void%)
! Erstmal Feld
! vergrößern
IF feld$(i%)>neu$ ! Ist der gewählte Buchstabe kleiner?
INSERT feld$ (i%)=neu$ ! Wenn ja => vor dem aktuellen im Feld einfügen
ELSE ! Ansonsten ist der gewählte größer als alle
INSERT feld$(i%+1)=neu$ ! im Feld => ganz hinten eintragen
ENDIF ! ( ist dann automatisch der letzte Feldbuchstabe)
ENDIF
UNTIL c%=81 OR c%=113 ! Wartet auf Taste "Q"
'
' Hier nun noch REDIM hinzuMERGEn ! !!
Gerald Schmieder