Rekursiver File-Finder in GFA-BASIC: Lost in Space?

Standen Sie auch schon vor dem Problem, auf einem Laufwerk einen Pfad nach Dateien zu durchsuchen, deren Name einem bestimmten Muster entspricht? Beispielsweise sollen alle Datendateien mit der Endung „DAT“ ab einem bestimmten Ordner bis maximal zwei Ordnerebenen tiefer gesucht werden, aber nur in Ordnern des Namens „NEUDATEN.*“?

Vor allen Dingen wollen Sie sich vorher nicht festlegen, wie viele Dateien denn maximal gefunden werden dürfen! Im Zeitalter stetig preiswerterer Massenspeicher könnte es Ihnen ja passieren, daß 20000 Dateien Ihren Vorgaben entsprechen. Sie wollen sicher nicht vorher ein Stringarray mit 20000 Elementen festlegen. Das braucht Speicher - und was machen Sie bei 20001 Dateien? Falls Sie in GFA-BASIC programmieren, haben wir die Lösung gefunden, die zudem noch leicht in ‘C’ oder ‘Pascal’ umsetzbar ist. Eine leicht veränderte Version dieser Routinen wird übrigens seit langer Zeit im VIRENDETEKTOR von Volker Söhnitz und mir eingesetzt.

RFF steht für ‘Recursive File Find’, einen Satz von Prozeduren und globalen Variablen, die es Ihnen ermöglichen, komfortabel nach Dateien zu suchen, ohne sich vorher auf eine maximale Anzahl zu bearbeitender Dateien festlegen zu müssen.

Da der Programmierer ja nicht wissen kann, wie viele Dateien auf seine Suchmaske zutreffen werden, gibt es bisher meist zwei Ansätze:

(a) Er trägt im Source-Text der Suchfunktion den Quelltext oder Aufruf einer Routine ein, die irgendwas mit der Datei macht. Nachteil: das ‘Black-Box’-Prinzip (Verstecken der internen Details) wird durchbrochen.

(b) Er übergibt der Suchfunktion einen Zeiger auf eine Routine, die mit dem Pfadnamen jeder gefundenen Datei aufgerufen wird. Nachteil: GFA-BASIC kennt keine Zeiger auf Prozeduren.

Die RFF-Routinen sind nach außen eine Black-Box und bieten ein Höchstmaß an Flexibilität.

Gehen wir die Routinen der Reihe nach durch:

(1) Am Anfang allen Schaffens steht rff.create. Im ersten Parameter geben Sie die Dateianzahl an, die maximal pro Aufruf der eigentlichen Suchroutine rff.find gefunden werden darf. Der zweite Parameter gibt die maximale Ordnertiefe an, mit der RFF klarkommt (16 reicht hier aus).

Mit diesen Werten werden globale Variablen und Felder initialisiert. In rff.pfname$() werden bei der Suche die gefundenen Dateinamen samt Pfad geschrieben, in rff.attrib|() das Dateiattribut der gefundenen Files. RFF verwendet bei der Suche intern rff.dta|() und rff.pname$(), doch später (bei rff.find) dazu mehr.

(2) rff.delete stellt das Gegenstück zu rff.create dar und löscht alle von rff.create angelegten Felder und Variablen. Da diese drei Felder sehr wenig Platz (einige KB) benötigen, brauchen Sie rff.delete nur aufzurufen, wenn Sie jedes letzte KB benötigen oder bei rff.create angegebene Einstellungen ändern möchten.

(3) rff.init müssen Sie vor jeder neuen Suche (mit rff.find) einmal aufrufen (siehe Listing). Der erste Parameter ist ein Dateisuchmuster, etwa „*.PRG“. Als zweiten Parameter geben Sie die Dateiattribute an, die die gefundenen Dateien aufweisen sollen. Genaueres zur Praxis (die sich von der Theorie hier ziemlich unterscheidet!) der Behandlung des Dateiattributs siehe [2]. Der dritte Parameter legt ein Suchmuster für Ordner fest. Der vierte Parameter gibt die maximale Ordnertiefe an, die relativ zum Startordner der Suche durchsucht wird. Ein Beispiel: Sie wollen nur in der Wurzel suchen sowie in Ordnern, die in der Wurzel liegen. Dann übergeben Sie für diesen Parameter eine Eins.

(4) rff.find ist die eigentliche Suchfunktion. rff.find sucht pro Aufruf maximal die bei rff.create angegebene Anzahl Dateien und kehrt dann zur Aufrufstelle zurück. Sie können dann die bis dahin gefundenen Dateien bearbeiten, dann wieder rff.find aufrufen usw., bis keine Dateien mehr gefunden worden sind (siehe Listing).

Damit Sie verstehen, wie RFF arbeitet, betrachten wir den Ablauf einer Dateisuche. GEMDOS stellt hierzu vier Funktionen zur Verfügung: FSFirst, FSNext, FGetDTA sowie FSetDTA. FSFirst steht für ‘File Search First’. Diese Funktion dient zum Initiieren einer Suche mit Suchpfad/Maske, z.B. „A:*.*“ sowie den Attribut-Bits, die beispielsweise angeben, ob bei den zu suchenden Dateien schreibgeschützte Dateien sein sollen. Findet FSFirst eine Datei, können Sie mit wiederholten Aufrufen von FSNext (‘File Search Next’, OHNE Übergabeparameter !!) alle weiteren Dateien suchen.

FSFirst/FSNext verwenden bei ihrer Suche eine Datenstruktur namens DTA, die Disk-Transfer-Adress. Mittels FGet DTA kann die Adresse dieser DTA abgefragt, mit FGetDTA eine neue DTA gesetzt werden. FSNext entnimmt alle Informationen für die Weitersuche aus einem Teil der DTA, der erstmalig von FSFirst initialisiert wird. Wir lesen aus einem anderen DTA-Abschnitt das Dateiattribut sowie den Dateinamen einer gefundenen Datei; deren Dateidatum und Uhrzeit sowie die Dateilänge sind dort ebenfalls zu finden.

Möchten wir Unterordner, Unterunterordner etc. des Startordners in die Suche einbeziehen, greifen wir zur Rekursion. Das heißt, nachdem wir einen Ordner komplett nach Dateien abgesucht haben, suchen wir nach allen Ordnern in diesem Verzeichnis und rufen die Suchfunktion mit einer Verkettung aus bisherigem Pfad sowie Ordnemamen rekursiv auf, und zwar für jeden Ordner, den wir finden, ausgenommen den unechten Ordnern V und In jedem rekursiven Aufruf der Suchfunktion wird die gerade gültige DTA der Suchfunktion gemerkt, eine neue eigene DTA gesetzt und vor der Rückkehr zur letzten Rekursionsebene der Suchfunktion deren DTA wieder restauriert.

Bricht die Suchfunktion ab, da die Maximalzahl der Dateien gefunden wurde, ist also gerade eine Kette von rekursiven Aufrufen aktiv. Der aktuelle Suchpunkt wird eindeutig beschrieben durch alle Pfade sowie alle DTAs, die in der Kette der Aufrufe gerade in den einzelnen Aufrufen aktiv (benutzt) sind. Überschreitet die Anzahl der gefundenen Dateien diejenige Zahl, die Sie bei rff.create angegeben haben, verlassen wir die ganze rekursive Kette der Aufrufe. Beim obersten, zuerst aktiven Aufruf der Suchfunktion (Rekursionstiefe 1) setzen wir ein Flag rff.go.down!.

Beim nächsten Aufruf der Suchfunktion rff.find zeigt dieses Flag, daß kein Erstaufruf vorliegt, sondern eine unterbrochene Suche fortgesetzt werden soll. Die alten Pfade und DTAs werden entsprechend der Rekursionstiefe restauriert. Ist die alte Rekursionstiefe durch Selbstaufruf der Suchfunktion erreicht, wird an die Stelle gesprungen, ab der die nächste Datei gesucht wird: dort stoppte rff.find vorher, als die Maximalzahl Dateien gefunden wurde.

rff.find gibt die Anzahl gefundener Dateien zurück, um möglichst einfach ein Suchende feststellen zu können. Diese Anzahl gefundener Dateien finden Sie zusätzlich auch noch in rff.fcount%. Jeder gefundene Dateiname (samt Pfad) steht im Array rff.pfname$(), die dazu gehörenden Dateiattribute in rff.attrib|(). Die Gesamtzahl gefundener Dateien nach einem kompletten Durchlauf erhalten Sie über rff.fcountall%.

Innerhalb von rff.find finden sich zwei GOTOs. Auf die Gefahr hin, mich unbeliebt zu machen: In der vorliegenden Situation sind GOTOs die ‘natürliche’ und bestechend einfache Lösung (versuchen Sie es ohne ...). Die zweifache Suche mit FSFirst/FSNext in jedem Ordner ist gewollt und stellt sicher, daß Dateien in jeweils einem Verzeichnis aufeinanderfolgend gefunden werden, bevor in tiefere Ordner verzweigt wird.

Am Anfang von rff.find() werden diverse String-Initialisierungen durchgeführt, da GFA-B ASIC zumindest ab Version 3.0 einen Fehler in der Verwaltung lokaler Strings hat. Testhalber können Sie einen Absturz mit dem Beispiel-Listing CRASH provozieren (danach neu booten!). Fatal wirkt sich ein Medienwechsel aus, der vor einem FSNext stattfindet. Alle internen Strukturen werden dadurch freigegeben, das kann sogar einen Absturz verursachen [2]. Das heißt also, Disketten und Wechselplattenmedien sollten nicht gewechselt werden während eines Suchvorgangs. Falls Sie RFF in einem GEM-Programm (AES-Aufrufe) verwenden, sollten Sie die Kommentare vor WIND_UPDATE entfernen (das Beispielprogramm verwendet keine AES-Aufrufe).

Die Routinen gehen alle von OPTION BASE 0 aus, können aber leicht an OPTION BASE 1 angepaßt werden. Da RFF nur GEMDOS FSFirst/FSNext benutzt, sollte sogar eine Umsetzung auf MSDO-Sen möglich sein.

Eine genauere Fehlerbehandlung können Sie leicht realisieren. FSFirst liefert im wesentlichen -33 (Datei nicht gefunden) sowie -49 (Keine weiteren Dateien) zurück, FSNext -49. es könnten aber noch Fehler auf BIOS-Ebene auftreten (-1 ..-31) [1,2,3].

Beachten Sie bitte, daß das Beispiel-Listing zu Demonstrationszwecken nur Dateien mit gesetztem Attribut-Bit ausgibt. Möchten Sie alle Dateien ausgeben, kommentieren Sie das IF-ENDIF aus.

Für Anfragen können Sie mich nicht nur über die Redaktion, sondern auch über conrad@pool.informatik.rwth-aachen.de erreichen.

[1] Jankowski/Reschke/Rabich, ATARI ST Profibuch, Sybex Verlag

[2] Alex Esser, Auf der Schwelle zum Licht, Directory-Verwaltung Teil 2, ST-Computer August/September 88

[3] Kramer/Riebl/Hübner, Das TOS-Listing, BIOS-GEMDOS-VDI, Verlag Heinz Heise


' ***************************
' RFF Recursive File Find 
' (c)1994 by MAXON-Computer
' Autor: Christoph Conrad 
' ***************************
'
' 42 Files maximal auf einmal finden 
' Maximale absolute Ordnertiefe 16 
@rff.create(42,16)
'
' Suche alles in allen Ordnern 
' Maximale relative Ordnertiefe 16 
@rff.init("*.*",0,"*.*",16)
DO
    ' Startdirectory Wurzel aktuelles Laufwerk
    EXIT IF @rff.find("\")=0
    FOR count%=0 TO rff.fcount%-1
        ' alle bis jetzt gefundenen Files ausgeben 
        IF BTST(rff.attrib|(count%),5)
            ' Nur Dateien mit gesetztem 
            ' Archivbit ausgeben 
            PRINT rff.pfname$(count%)
        ENDIF
    NEXT count% 
LOOP 
PRINT
' Gesamt gefundene Fileanzahl ausgeben 
IF rff.fcountall%=0
    PRINT "Keine Dateien mit Muster ";rff.fpattern$
ELSE
    PRINT rff.fcountall%;" Dateien gefunden"
ENDIF
@rff.delete
PROCEDURE rff.create(max.files|,max.depth|)
    ' Max. Files pro Aufruf @rff.find
    rff.max.files|=max.files| 
    ' Max. Ordnerverschachtelungstiefe 
    rff.max.depth|=max.depth|
    ' Gefundene Dateipfade: PathFileName 
    DIM rff.pfname$(rff.max.files|-1)
    ' Gefundene Dateiattribute
    DIM rff.attrib|(rff.max.files|-1)
    ' DTA's
    DIM rff.dta|(43,rff.max.depth|-1)
    ' Pfade bei rekursiver Suche 
    DIM rff.pname$(rff.max.depth|-1)
RETURN
PROCEDURE rff.delete 
    ' Aufräumen
    ERASE rff.pfname$()
    ERASE rff.attrib|()
    ERASE rff.dta|()
    ERASE rff.pname$()
RETURN
PROCEDURE rff.init(fpattern$,fattr&,dpattern$, max.reldepth|)
    ' Max. relative Suchtiefe 
    rff.max.reldepth|=max.reldepth| 
    ' sicherheitshalber depth auch auf Null 
    rff.rec.depth|=0
    ' Anzahl gesamt gefundener Dateien
    rff.fcountall%=0
    rff.go.down!=FALSE
    ' Dateisuchmuster
    rff.fpattern$=fpattern$+CHR$(0)
    ' Dateiattribut 
    rff.fattr&=fattr&
    ' Ordnersuchmuster
    rff.dpattern$=dpattern$+CHR$(0)
RETURN
FUNCTION rff.find(path$)
    '
    ' path$: Startpfad der Suche. Der erste ist optional
    ' der letzte muss (!!) immer vorhanden sein
    ' Erlaubt sind also:
    ' "\" == Suche ab Wurzel aktuelles Laufwerk
    ' "A:\" == Suche ab Wurzel A:
    ' "BLABLA\" == Suche ab Ordner "BLABLA" relativ zum Standardpfad
    ' "\BLABLA\“ == Suche ab Ordner "BLABLA" (auf der Wurzel)
    '
    ' Globale Variablen, siehe Text 
    ' rff.max.files| 
    ' rff.max.depth| 
    ' rff.last.depth| 
    ' rff.max.reldepth| 
    ' rff.rec.depth|
    ' rff.fcounts 
    ' rff.go.up!
    ' rff.go.down|
    ' rff.old.dta%
    ' rff.dname$
    ' DIM rff.pfname$(rff.max.files|-1)
    ' DIM rff.dta|(43,rff.max.depth|-1)
    ' DIM rff.pname$(rff.max.depth|-1)
    '
    LOCAL dta%
    '
    INC rff.rec.depth|
    IF rff.rec.depth|=1 
        ' dta% mal als Zählervariable missbrauchen 
        FOR dta%=0 TO rff.max.files|-1 
            rff.pfname$(dta%)=""
        NEXT dta%
        ~FRE(0)
        rff.fcount%=0
        rff.go.up!=FALSE
        rff.old.dta%=FGETDTA()
    ENDIF
    '
    dta%=V:rff.dta|(0,rff.rec.depth|-1)
    ~FSETDTA(dta%) ! lokalen DTA-Puffer setzen
    '
    IF rff.go.down!
        path$=rff.pname$(rff.rec.depth|-1)
        IF rff.last.depth|=rff.rec.depth| 
            rff.go.down!=FALSE 
            GOTO go.on 
        ELSE
            rff.dname$=""
            GOTO go.down 
        ENDIF 
    ELSE
        rff.last.depth|=rff.rec.depth| 
        rff.pname$(rff.rec.depth|-1)=path$
    ENDIF
    '
    ' ~WIND_UPDATE(1) ! BEG_UPDATE
    rff.err%=FSFIRST(path$+rff.fpattern$,rff.fattr&) 
    ' ~WIND_UPDATE(0) ! END_UPDATE
    WHILE rff.err%>=0 
        rff.pfname$(rff.fcount%)=path$+CHAR{dta%+30} 
        rff.attrib|(rff.fcount%)=BYTE{dta%+21}
        INC rff.fcounts 
        INC rff.fcountall%
        IF rff.fcount%>=rff.max.files| 
            rff.go.up!=TRUE 
            GOTO go.up 
        ENDIF 
    go.on:
        'nächste Datei suchen 
        ' ~WIND_UPDATE(1) ! BEG_UPDATE
        rff.err%=FSNEXT()
        ' ~WIND_UPDATE(0) ! END_UPDATE
    WEND
    '
    ' Test, ob die maximale relative Ordnertiefe 
    ' schon erreicht wurde.
    IF rff.rec.depth|<=rff.max.reldepth| 
        ' ersten Ordner suchen 
        ' ~WIND_UPDATE(1) ! BEG_UPDATE
        rff.err%=FSFIRST(path$+rff.dpattern$,16)
        ' ~WIND_UPDATE(0) ! END_UPDATE
        WHILE rff.err%>=0 
            ' Bei Attribut 16 werden auch 
            ' normale Dateien gefunden 
            IF BYTE{dta%+21}=16 ! Ordner ??
                rff.dname$=CHAR{dta%+30}
                IF rff.dname$<>"." AND rff.dname$<>".."
                go.down:
                    ' Dann schauen wir mal einen Ordner tiefer 
                    ~@rff.find(path$+rff.dname$+" \")
                    IF rff.go.up!
                        GOTO go.up 
                    ENDIF
                    ~FSETDTA(dta%)
                ENDIF
            ENDIF
            ‘ nächsten Ordner suchen
            ~WIND_UPDATE(1) ! BEG_UPDATE
            rff.err%=FSNEXT()
            ' ~WIND_UPDATE(0) ! END_UPDATE
        WEND 
    ENDIF
'
go.up:
    IF rff.rec.depth|=1 
        rff.go.down!=TRUE 
        ~FSETDTA(rff.old.dta%)
    ENDIF
    DEC rff.rec.depthI|
    RETURN rff.fcounts 
ENDFUNC


Christoph Conrad
Aus: ST-Computer 03 / 1995, Seite 68

Links

Copyright-Bestimmungen: siehe Über diese Seite