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
Links

Copyright-Bestimmungen: siehe Über diese Seite
Classic Computer Magazines
[ Join Now | Ring Hub | Random | << Prev | Next >> ]