Alle Ordner fest im Griff! (Laser C)
Dieser Artikel soll zeigen, dass man ein Directory auch anders als mit der Methode der Rekursion bearbeiten kann. Ich werde die Struktur des Directorys als eine verkettete Baumstruktur darstellen und diese nach erfolgter Entkettung in einem Array des Typs String ablegen. Dies ermöglicht eine weitere Verwendung der Verzeichnispfade für unterschiedliche Anwendungen. Das Ziel ist es, ein Directory einmal einzulesen, um es dann in diversen Routinen bearbeiten zu können, ohne jedesmal sämtliche Verzeichnisse neu Einlesen zu müssen.
Betrachtet wird dabei das Beispiel eines Directorys, wie es sich in der Abbildung 1 darstellt. Ausgehend vom Wurzelverzeichnis, kann man die beiden Verzeichnisse TEXTV und GRAPHIK sehen, von denen aus sich weitere Verschachtelungen ergeben. Zur Vereinfachung wird diese Verschachtelung hier nicht allzu weit getrieben, um noch die Übersichtlichkeit zu erhalten. Zur Bearbeitung der Struktur werden einige der GEMDOS-Funktionen verwendet, die im folgenden kurz beschrieben werden.
1. Fgetdta
Diese Funktion erfragt die Adresse der sogenannten (D)isk (T)ransfer (A)dress. Dabei handelt es sich um eine Struktur, in der die Informationen zu einer Datei enthalten sind.
2. Fsetdta
Mit dieser Funktion kann man die DTA ändern, um die Auskunftsfunktionen zu veranlassen, ihre Informationen in eine eigene Struktur abzulegen.
3. Fsfirst
Mit dieser Funktion beginnt man die Suche nach einem ‘Pfad’ oder einer Datei. Die Informationen zu den gefundenen Dateien werden dann in die Struktur DTA geschrieben.
4. Fsnext
Mit dieser Funktion wird die mittels Fsfirst begonnene Suche fortgesetzt.
Weitere Funktionen werden zur ‘Baumanalyse’ nicht benötigt.
Im Programm wird zunächst eine Struktur definiert, die die Informationen erfassen soll, die von den Funktionen Fsfirst und Fsnext zur Verfügung gestellt werden. Diese Struktur hat folgendes Aussehen:
- einen String in der Länge von 21 Zeichen, der für GEMDOS reserviert ist.
- ein 8 Bit großer Char-Wert, der die Dateiattribute verschlüsselt.
- In den folgenden zwei Integern sind das Datum und die Uhrzeit der Dateierstellung im GEMDOS-Format abgelegt.
- die nächste Variable nimmt die Länge der Datei in Bytes auf.
- Und last but not least folgt ein String, der für den Dateinamen reserviert ist.
Die nachfolgende Struktur wird nun speziell für die nichtrekursive Baumsuche definiert. Sie hat folgende Elemente (Listing 1):
- ein Array, in dem der Verzeichnisname abgelegt werden soll.
- ein Integer, der die Indexnummer des übergeordneten Verzeichnisses aufnimmt.
- Der letzte Eintrag in der Struktur ist ein Test-Flag, das für die Abbruchbedingung der Suchschleife wichtig ist. Ist dieser Wert 1, ist dieses Verzeichnis bereits auf mögliche Unterverzeichnisse geprüft worden.
Von dieser Struktur reserviere ich 300 Elemente. Diese Anzahl ist auch auf einer ‘normalen’ Festplatte (-> 30 MB) durchaus ausreichend.
Das nächste definierte zweidimensionale Feld ist für die einzelnen Ordnerpfade reserviert. Auch dieses Array ist mit 300 Elementen ausreichend dimensioniert.
Das Integer-Array INDEX_-ARR verwaltet Zeiger, mit deren Hilfe die Verkettung von Verzeichnissen dargestellt wird.
Die folgenden globalen Variablen dienen der laufenden Bearbeitung und haben im einzelnen folgende Bedeutung. :
dir_ebene: Dies ist ein Zähler, der die aktuelle Ebene anzeigt, die momentan bearbeitet wird (Abb.).
frei_baum: Diese Variable ent’ hält den Index eines freien Ein’ träges in dem Array MED_-PFAD.
vater_ord: Dies zeigt auf das Aktuelle ‘Vaterverzeichnis’.
kind_ord: Diese Variable zeigt auf das nächste ‘Kindverzeichnis’.
In der Funktion MAIN werden das Programm initialisiert und die Eingabe eines Laufwerkes veranlaßt. Die Routinen PHASE_1 und PHASE_2 dienen der Initialisierung der Strukturen und Variablen.
Nun beginnt die eigentliche Suche, indem ein Such-String erstellt wird, der der Funktion Fsfirst übergeben wird. Der Such-String hat beim ersten Aufruf die Form „A:\.“. In diesem Pfad werden nun alle Verzeichnisse der nächsten Ebene gesucht, was in der Funktion GET_DIRECTOR Y erfolgt. Dieser Funktion wird noch die Indexnummer übergeben, an welche Stelle sie die gefundenen Verzeichnisse ablegen soll. Hier ist es der Wert ‘0’ , da es sich um das Wurzel-Directory handelt. In einer Schleife werden alle Dateien gesucht, die das Kriterium ‘16’ erfüllen, also Dateien, die ihrerseits Verzeichnisse sind. Bei jedem gefundenen Verzeichnis (Bsp. TEXTV und GRAPHIK) wird der Zähler ANZAL_ORD um 1’ erhöht, der Name in die Zwischenstruktur kopiert und die Ordner dem Vaterobjekt zugeordnet.
Hier ist es das Element ‘0’, also ‘A:V. Werden keine Ordner mehr gefunden, bricht die Funktion ihre Arbeit ab, und der gerade durchsuchte Ordner wird als ‘erledigt’ gekennzeichnet, indem die Variable Z_TFLAG auf ‘ 1 ’ gesetzt wird. Das Ordner-Array hat folgende Einträge:
| Pos. | Inhalt | Z_TFLAG | Vater |
|---|---|---|---|
| 0 | A:\ | 1 | 0 |
| 1 | TEXTV\ | 0 | 1 |
| 2 | GRAPHIK\ | 0 | 1 |
| 3 | 0 | -1 |
Die Funktion GET_FREI_-BAUM ermittelt eine freie Position im Zwischen-Array. Ein solcher freier Eintrag ist dann gegeben, wenn dort als Vaterobjekteine ‘-1’ eingetragen ist. Diese Position wird zurückgegeben und in der Variablen FREI_BAUM abgelegt. Wird keine freie Position mehr gefunden, folgt der Aufruf der Funktion TERMINATE. In diesem Fall wären die Arrays zu klein ausgelegt. Das Programm bricht seine Arbeit ab.
In unserem Beispiel würde die Funktion die Position ‘3’ als frei melden. Ab dieser Position werden weitere Verzeichnisse geschrieben.
In der nachfolgenden Schleife werden sukzessive alle Verzeichnisse gesucht und gefunden. Anschließend wird die Variable TESTFLAG ungleich ‘0’ und somit die Schleife abgebrochen.
Die Funktion GET_SUCH_-STRING synthetisiert aus den einzelnen Einträgen des Zwischen-Arrays einen kompletten Zugriffspfad, der der Funktion GET_DIRECTORY übergeben werden kann.
Prinzipiell erfolgt dies so, daß an das Wurzelverzeichnis ‘A:' der erste gefundene Ordner TEXTV angehängt wird. Zudem wird noch ein Suchmuster an-gefügt, so daß der Such-String dann folgendermaßen lautet:
‘A:\TEXTV\.‘ Mit diesem Such-String geht die Suche dann weiter, so daß unser Zwischen-Array folgendermaßen ausschaut:
| Pos. | Inhalt | Z_TFLAG | Vater |
|---|---|---|---|
| 0 | A:\ | 1 | 0 |
| 1 | TEXTV\ | 1 | 1 |
| 2 | GRAPHIK\ | 0 | 1 |
| 3 | WP\ | 0 | 2 |
| 4 | TEMP\ | 0 | 2 |
| 5 | 0 | -1 |
Analog dazu wird auch der Ordner GRAPHIK durchsucht, so daß das Zwischen-Array nun so aussieht:
| Pos. | Inhalt | Z_TFLAG | Vater |
|---|---|---|---|
| 0 | A:\ | 1 | 0 |
| 1 | TEXTV\ | 1 | 0 |
| 2 | GRAPHIK\ | 1 | 0 |
| 3 | WP\ | 0 | 1 |
| 4 | TEMP\ | 0 | 1 |
| 5 | STAD\ | 0 | 2 |
| 6 | PICS\ | 0 | 2 |
| 7 | 0 | -1 |
Die Positionen ‘ 1 ’ und ‘2’ sind nach dem Durchlauf als ‘durchsucht’ gekennzeichnet.
Die nächste Ebene, die durchsucht werden soll, ist die, die noch eine ‘0’ an der Stelle Z_TFLAG stehen hat. Dies ist der Ordner ‘WP’.
Von dieser Position (3) aus wird nun eine Kette bis zum Wurzelobjekt gebildet, die jeweils die Vaterobjekte beinhaltet. Diese Kette lautet nun : 3,1,0 d.h. WP->TEXTV->A. Sie wird in der Funktion GET_ORD_FOLGE ermittelt. Da sie aber leider falsch herum aufgebaut ist, wird sie in DREH_FOLGE umgekehrt.
Die neue Verkettung besteht aus den Einträgen 0,1,3. Diese Einträge werden innerhalb der Funktion GET_SUCH_-STRING wieder zu einem String zusammengefaßt, der dann so lautet: ‘A:\TEXTV\WP\.’. Nach erfolgter Suche in diesem Verzeichnis - das übrigens in das Ordner-Array kopiert wird - wird auch dieser Ableger ‘WP’ als durchsucht gekennzeichnet. Sind alle Positionen in dem Zwischen-Array als durchsucht gekennzeichnet, ist der Aufbau des Verzeichnisbaumes abgeschlossen. Nun liegen alle möglichen Zugriffspfade im Array ORD_PFADE vor und können bearbeitet werden.
Eine Möglichkeit wäre eine sortierte Ausgabe der Pfade, oder die weitere Verwendung der Pfade zur Suche nach speziellen Dateien.
Eine kurze Anwendung zeigt das Beispielprogramm, das die gefundenen Pfade auf dem Bildschirm ausgibt. Falls noch Unklarheiten bestehen sollten, werden eventuell die Kommentare des abgedruckten Listings weiterhelfen können.
So ähnlich kann man auch noch andere baumähnliche Strukturen entwirren, wie zum Beispiel die RSC-Dateien. Diese Lösung hat nämlich den Vorteil, daß sie auch für wildwuchernde Bäume geeignet ist; ein Problem kann dabei nur ein zu kleiner Speicherbereich sein. Während meiner diversen Tests hat das Programm in der abgedruckten Version den Festplattentest bestanden. Listing 2 stellt ein komplettes, lauffähiges Programm dar.
Literatur:
Jankowski/Reschke/Rabich, ATARI ST-Profibuch, Sybex-Verlag
/*
Zwischenstruktur für die Verzeichnisstruktur
*/
typedef struct _zwi {
char z_name[14]; /* Name des Ordners */
int z_vater; /* Nummer des 'Vaters' */
int z_tflag; /* Testflag 1=Baum auf Söhne getestet */
}ZWI;
/***********************************************
Programm : DirBaum
Version : 1.0
by LANTEC ComPro / R.Lanfermann
(c) 1992 MAXON Computer
---------------------------------------------
Was tut es : Nicht-rekursives Durchsuchen
des Directorys
---------------------------------------------
Sprache : LASER C von Megamax
***********************************************/
#include <osbind.h>
/*
Dimensionen der Arrays vordefinieren. Bei umfangreicheren
Dir's wird MAX_ANZ auf einen höheren Wert festgelegt.
*/
#define MAX_ANZ 300
#define SUCHOK 1 /* Knoten getestet */
#define SUCHNOT 0 /* Knoten noch nicht getestet */
#define VERZEI 16 /* Attributmaske für Ordner */
#define ALLES 255 /* Attributmaske für alle Dateien */
/* Struktur für Fsfirst/Fsnext */
typedef struct _dda{
char dda_gem[21]; /* reserviert für GEM */
char dda_att; /* Attribute d.Dateien*/
unsigned dda_time; /* Erstellungszeit */
unsigned dda_date; /* Erstellungsdatum */
long dda_size; /* Dateilänge */
char dda_name[14]; /* Dateiname */
} DDA;
/*
Zwischenstruktur für die Verzeichnisstruktur
*/
typedef struct _zwi {
char z_name[14]; /* Name des Ordners */
int z_vater; /* Nummer des 'Vaters' */
int z_tflag; /* Testflag 1=Baum auf Söhne getestet */
} ZWI ;
ZWI _zwischen[MAX_ANZ];
char ord_pfade[MAX_ANZ][255];
char such_str[255]; /* Suchstring */
int index_arr[MAX_ANZ]; /* Array der Verkettungen */
int direbene; /* Untersuchte Ebene */
char laufwerk; /* drive als Char 'C' */
int frei_baum; /* freier Baumeintrag */
int testflag; /* Ist tst!= 0 dann ist alles geprüft */
int vater_ord; /* Index für 'vater-ordner' */
int kind_ord; /* Index des nächsten Pfades der zu untersuchen ist */
int anzal_ord; /* Anzahl der gefundenen Ordnerpfade */
int aktdrv; /* Nummer des Laufwerkes */
main{)
{
puts("Dateien auf welchem Laufwerk ? 0=a 1=b ...");
scanf("%d",&aktdrv );
laufwerk = aktdrv+'A';
printf("Liste der Dateien von Drive %c\n", laufwerk);
phase_1();
gemdos(7);
}
phase_1()
{
phase_2();
phase_3();
}
phase_2()
{
initialisiere(); /* Initialisierung der Strukturen */
dir_ebene =0; /* Aktuelle Ebene ist Wurzelverzeichnis */
frei_baum =0; /* Erster freier Eintrag ist Position 0 */
vater_ord =0; /* Es gibt kein übergeordnetes Verzeichn. */
/*
Die Ordner der ersten Ebene finden. Im Beisp. werden dann die
Ordner TEXTV und GRAPHIK gefunden werden.
*/
strcpy( such_str, "A:\\*.*");
strcpy( _zwischen[0].z_name , "A:" );
_zwischen[0].z_name[0] = laufwerk;
such_str[0] = laufwerk;
get_directory(1);
/* Diesen Pfad z.B. A:\*.* als durchsucht gekennzeichnen */
_zwischen[0].z_tflag = SUCHOK;
/* Nächsten freien Baumplatz suchen */
frei_baum = get_frei_baum{);
kind_ord = 1;
/* Solange weitersuchen, bis alles geprüft wurde, das ist dann der
Fall, wenn tst !* 0 ist */
do {
/* Suchstring zusammensetzen */
get_such_string( kind_ord );
/* Freien Platz im Zwischenarray finden */
frei_baum=get_frei_baum();
/* Knoten als getestet markieren */
_zwischen[vater_ord].z_tflag = SUCHOK;
/* Suche wird fortgesetzt */
get_directory(frei_baum);
/* Prüfung, ob alle Ordner gefunden wurden */
get_test_erg();
/* Nächste Ebene beginnen */
get_kind_ord();
}while(testflag== 0) ; /* und weitermachen */
}
/***********************************
* Hier wird nach weiteren Ordnern *
* innerhalb eines Ordners gesucht *
***********************************/
get_directory( i )
int i;
{
DDA new_dta;
Fsetdta( &new_dta );
strcpy(ord_pfade[anzal_ord], such_str );
/* Diesen Ordner gibt es */
anzal_ord++; /* also merken */
if( !Fsfirst( such_str, ALLES ) )
/* Ist in der Ebene noch was? */
do {
if ( (new_dta.dda_att==VERZEI)&&(new_dta.dda_name[0]) ) /* Ja */
{
strcpy( _zwischen[i].z_name,new_dta.dda_name ); /* Einfügen */
_zwischen[i].z_vater = vater_ord;
/* Und merken, wer der */
i++;
/* Vater ist */
}
}
while(!Fsnext());
}
/*********************
* Initialisiert die *
* Baumstruktur *
*********************/
initialisiere()
{
register int i;
for( i=0;i<MAX_ANZ;i++)
{
_zwischen[i].z_vater = -1;
/* Alle sind noch Waisen und */
_zwischen[i].z_tflag = SUCHNOT;
/* noch nicht geprüft */
ord_pfade[i][0] = '\0';
/* Strings werden gelöscht */
}
anzal_ord=0; /* Es ist noch kein Ordner gefunden */
}
/************************
* Suchet einen freien *
* einen freien Eintrag *
* und findet ihn *
************************/
int get_frei_baum()
{
register int i;
for(i=1;i<MAX_ANZ;i++)
if( _zwischen[i].z_vater == -1 )
/* ist es noch ein Waise, dann */
return i; /* ist der Platz noch frei */
terminate(); /* Abbruch bei Platzmangel */
}
/****************************
* Müssen wir noch suchen ? *
****************************/
get_test_erg()
{
register int i;
if ( dir ebene < 0 )
{
testflag=1;
return;
}
for(i=1;i<MAX_ANZ;i++)
if ( _zwischen[i].z_tflag == SUCHNOT )
/* Da ist noch ein ungeprüfter */
{
testflag=0; /* also such gefälligst weiter */
return;
}
testflag=1; /* Super, alles schon untersucht */
}
/***********************
* Der Nächste bitte. *
***********************/
get_kind_ord()
{
register int i;
for(i=0;i<MAX_ANZ;i++)
{
if ( _zwischen[i].z_vater == dir_ebene && _zwischen[i].z_tflag == SUCHNOT )
{
kind_ord=i; /* Alle noch gleiche Ebene */
return ; /* Aber noch nicht untersucht. Dann mal los */
}
}
find_next_eben(); /* Alle Objekte eine Ebene untersucht, dann */
/* eben die nächste Ebene anfangen */
kind_ord=0;
}
/***************************
* Welchen Pfad haben wir *
* denn nun zu testen *
***************************/
get_such_string(i)
register int i;
{
register int j;
/* Ebene 0 ist das Rootverzeichnis also z.B.
C: daher fügen wir \\ und den ersten Ordner und ein
\\*.* an. ----> C:\\LASER\\*.*
*/
if ( dir_ebene == 0 )
{
strcpy( such_str, _zwischen[0].z_name);
strcat( such_str, "\\");
strcat( such_str, zwischen[i].z_name );
strcat( such_str, "\\*.*");
vater_ord=i;
}
else
/* Die Hirarchie ist etwas verzwickter geworden
die Folge der Ordner muß erst mal gefunden werden,
das passiert in getfolge.
Nach und nach wird dann der Pfad aufgebaut.
*/
{
get_ord_folge(); /* Verkettung ermitteln */
strcpy( such_str, _zwischen[0].z_name);
j=1;
/* Nun werden alle Kinder,Enkel,Urenkel, Ururenkel...
des Vaters angefügt */
while( index_arr[j] != -1 )
{
strcat( such_str, strcat( such_str,_zwischen[(index.arr[j])].z_name);
j++;
}
strcat(such_str,"\\*.*");
}
}
/**********************
* Wer ist der letzte *
* Ableger des Vaters *
**********************/
such_vater()
{
register int i;
for(i=0;i<MAX_ANZ;i++)
if ( zwischen[i].z_vater==dir_ebene && _zwischen[i].z_tflag==SUCHNOT )
return i;
return -1;
}
/*************************
* Finden wir die folge- *
* generation. *
*************************/
find_next_eben()
{
register int i;
/*
Ist der Vater nicht mehr in der aktuellen Ebene zu finden,
dann haben wir die Folgegeneration schon
gefunden. Gibt es keine Nachkommen mehr, dann ist die
Ebene eben -1.
*/
for(i=1;i<MAX_ANZ;i++)
if( _zwischen[i].z_vater>dir_ebene )
{
dir_ebene=_zwischen[i].z_vater;
return;
}
dir_ebene=-1;
}
/*******************************
* Stammbaum des zu prüfenden *
* Kindes ermitteln *
*******************************/
get_ord_folge()
{
register int i,woher;
/* Erst mal alles löschen */
for( i=0;i<MAX_ANZ;i++)
index_arr[i]= -1;
i=0;
woher=such_vater(); /* Wer ist denn das Kind? */
index_arr[i]= woher; /* Aha, merken */
vater_ord=woher; /* Das Kind wird nun Vater */
i++;
/*
Hier verfolgen wir die Linie vom Kind aus bis zum Vater zurück.
Sobald der Vater das Rootdir. ist, sind wir fertig.
*/
while( woher > 0 )
{
index_arr[i]=_zwischen[woher].z_vater;
woher=index_arr[i];
i++;
}
/*
Wir brauchen aber die Kette vom Vater bis zum Kinde, und
nicht die Kette vom Kind zum Vater, daher wenden wir die Folge.
*/
dreh_folge();
}
/********************
* Stammbaum drehen *
* warum ? s.o. *
********************/
dreh_folge()
{
int zfolg[MAX_ANZ];
register int i,oft;
for( i=0;i<MAX_ANZ;i++)
zfolg[i]=-1;
i=0;
while( index_arr[i] >= 0 ) /* Die alte Folge mal kopieren */
{
zfolg[i]=index_arr[i];
i++;
}
oft=i; /* Aha, soviele Objekte sind es */
oft--;
i=0;
while ( oft >= 0 )
{
index_arr[oft]=zfolg[i]; /* Dann drehen */
oft--;
i++;
}
}
phase_3()
{
int i,z;
long addi;
if ( anzal_ord>=1 )
anzal_ord--;
for( i=0;i<anzal_ord;i++ )
{
strcpy(such_str,ord_pfade[i]);
z=strlen(such_str);
suchestr[z-3]='\0';
strcat( such_str , "*.");
strcat( such_str , "*");
get_files();
}
}
get_files()
{
DDA new_dta;
Fsetdta (&new_dta) ;
if{!Fsfirst(such_str,ALLES))
do{
if ( (new_dta.dda_name[0]!='.')&&{new_dta.dda_att != VERZEI ))
{
printf("Gefunden %s\n",(new_dta.dda_name));
}
}
while(!Fsnext());
}
/*****************************
* Der Platz reich nicht aus *
* daher Abbruch *
*****************************/
terminate()
{
puts("Der Speicherplatz reicht leider nicht mehr");
gemdos(7);
PtermO();
}
Ralph Lanfermann