Dateien, Unterverzeichnisse zählen?

[Mattze]

Hallo,

ich trau mich ja schon fast nicht...

Wie zähle ich günstig ALLE Dateien und Unterverzeichnisse eines Verzeichnisses?
(ALLE meint wirklich alle, also auch die Dateien, die in den Unterverzeichnissen liegen bzw. auch die Unterverzeichnisse von Unterverzeichnissen...)

Ich habe das bisher mit einer rekursiven Funktion gemacht und das geht auch sehr gut. Nur in dem neuen Programm stürzt er mit einer Zugriffsschutzverletzung ganz woanders ab. (In einer völlig fremden Unit, die damit vordergründig gar nichts zu tun hat!)

Vielleicht gibt es da noch eine direktere Möglichkeit?

Gruß
Mattze

[DeddyH]

Zeig doch mal die rekursive Funktion, damit würde ich das nämlich auch machen.

[himitsu]

'ne andere Möglichkeit, als die Verzeichnisse rekursiv durchzugehn gibt es doch eigentlich nicht?

Aber ich kann mir nicht vorstellen, wieso soeine Funktion das Programm zum Abstürzen bringen sollte.
Vielleicht solltes du anstatt nach 'ner anderen Möglichkeit zu suchen lieber mal suchen warum der Fehler an der anderen stelle auftritt und diesen Fehler dann beheben.

Das Schnellste und Resourcenschonenste sollte wohl eine Funktion direkt auf Basis der WinAPI sein.
(Die Delphi-Funktionen ala FindFirst machen intern ja noch mehr, da sie ja darauf ausgelegt sind mit einer Maske zu suchen und zu filtern)

[Fridolin Walther]

Zitat:

Zitat von himitsu

'ne andere Möglichkeit, als die Verzeichnisse rekursiv durchzugehn gibt es doch eigentlich nicht?

Eigentlich kann alles was in einer rekursiven Funktion gelöst wird, auch in einer nicht-rekursiven Funktion gelöst werden. Im Falle von Verzeichnisenumerierung ist es sogar sinnvoll.

Zitat:

Zitat von himitsu

Aber ich kann mir nicht vorstellen, wieso soeine Funktion das Programm zum Abstürzen bringen sollte.

Der Stack ist nicht unendlich groß. Je nachdem wir hoch die Rekursionstiefe ist, kanns dann schon mal krachen.

Zitat:

Zitat von himitsu

(Die Delphi-Funktionen ala FindFirst machen intern ja noch mehr, da sie ja darauf ausgelegt sind mit einer Maske zu suchen und zu filtern)

Der Filter wird eigentlich eins zu eins an die Windows API übergeben. Der einzige Overhead der entsteht besteht darin, das die Informationen aus der Windows Datenstruktur in die Delphi Datenstruktur kopiert werden.

[himitsu]

Zitat:

Zitat von 0xF30FC7

Der Filter wird eigentlich eins zu eins an die Windows API übergeben. Der einzige Overhead der entsteht besteht darin, das die Informationen aus der Windows Datenstruktur in die Delphi Datenstruktur kopiert werden.

also bis D2006 war das noch nicht der Fall und ich kann mir nicht vorstellen, daß die es jetzt noch geändert haben.

Zitat:

Der Stack ist nicht unendlich groß. Je nachdem wir hoch die Rekursionstiefe ist, kanns dann schon mal krachen.

die Verzeichnistiefe ist auch nicht unendlich Groß, also wird es wohl nicht so leicht zum Crash kommen :angel2:

Zitat:

Eigentlich kann alles was in einer rekursiven Funktion gelöst wird, auch in einer nicht-rekursiven Funktion gelöst werden. Im Falle von Verzeichnisenumerierung ist es sogar sinnvoll.

nur daß es eigentlich nahezu überall rekursiv gelöst wird (nja, so ist es halt auch noch irgendwie einfacher)

[Mattze]

Hallo,

meine Quelle sieht so aus:

Delphi-Quellcode:

type FG = array[0..2] of int64;  //Global definiert
     {0 - Größe, 1 - Anzahl Dateien, 2 - Anzahl unterverzeichnisse}

var FGAbbruch: Boolean = false;  //Global definiert

function GetFolderSize(const FolderName: string): FG;
var   FN: string;
      ex: fg;
      sr: Tsearchrec;
begin
   result[0]:=0; result[1]:=0; result[2]:=0;
   if FgAbbruch then exit;
   FN:=foldername;
   er:=findfirst(FN+'\*.*',faanyfile,sr);
   while er=0 do begin
      if fgabbruch then begin
        result[0]:=0; result[1]:=0; result[2]:=0;
        break;
      end;
      application.processmessages;
      if (sr.attr and fadirectory = fadirectory) then begin
         if (sr.name<>'..') and (sr.name<>'.') then begin
            inc(result[2]);
            ex:=getfoldersize(fn+'\'+sr.name);
            result[0]:=result[0]+ex[0];
            result[1]:=result[1]+ex[1];
            result[2]:=result[2]+ex[2];
         end
      end else begin
         inc(result[1]);
         result[0]:=result[0]+sr.size;
      end;
      er:=findnext(sr)
   end;
   sysutils.findclose(sr);
end;

Bei der Fremdunit, bei der ein Fehler auftritt, handelt es sich um EasyListview. Da ist es nicht so einfach möglich, alles zu ändern. (Zumal der Fehler an einer sehr wichtigen Stelle auftritt!)

Ich habe es auch mal versucht, das nichtrekursiv zu machen, weil ich eben auch mal gelesen habe, dass man alles rekursive auch nicht rekursiv machen kann. Ich bin da nicht weit gekommen, hab's einfach nicht hingekriegt.
Wie macht man das?

Gruß
Mattze

[Fridolin Walther]

Zitat:

Zitat von himitsu

Zitat:

Zitat von 0xF30FC7

Der Filter wird eigentlich eins zu eins an die Windows API übergeben. Der einzige Overhead der entsteht besteht darin, das die Informationen aus der Windows Datenstruktur in die Delphi Datenstruktur kopiert werden.

also bis D2006 war das noch nicht der Fall und ich kann mir nicht vorstellen, daß die es jetzt noch geändert haben.

Delphi 2007:

Delphi-Quellcode:

function FindMatchingFile(var F: TSearchRec): Integer;
var
  LocalFileTime: TFileTime;
begin
  with F do
  begin
    while FindData.dwFileAttributes and ExcludeAttr <> 0 do
      if not FindNextFile(FindHandle, FindData) then
      begin
        Result := GetLastError;
        Exit;
      end;
    FileTimeToLocalFileTime(FindData.ftLastWriteTime, LocalFileTime);
    FileTimeToDosDateTime(LocalFileTime, LongRec(Time).Hi,
      LongRec(Time).Lo);
    Size := FindData.nFileSizeLow or Int64(FindData.nFileSizeHigh) shl 32;
    Attr := FindData.dwFileAttributes;
    Name := FindData.cFileName;
  end;
  Result := 0;
end;

function FindFirst(const Path: string; Attr: Integer;
  var  F: TSearchRec): Integer;
const
  faSpecial = faHidden or faSysFile or faDirectory;
begin
  F.ExcludeAttr := not Attr and faSpecial;
  F.FindHandle := FindFirstFile(PChar(Path), F.FindData);
  if F.FindHandle <> INVALID_HANDLE_VALUE then
  begin
    Result := FindMatchingFile(F);
    if Result <> 0 then FindClose(F);
  end else
    Result := GetLastError;
end;

FindMatchingFile führt zwar Filterung durch auf Grund der angegebenen Attribute, aber der Vergleich bzw. die Bitweisen Operationen kaum ins Gewicht. Die von Dir angesprochene "Maske" wird 1 zu 1 an Windows übergeben.

Zitat:

Zitat von himitsu

die Verzeichnistiefe ist auch nicht unendlich Groß, also wird es wohl nicht so leicht zum Crash kommen :angel2:

Das kommt darauf an, wie die Systemsettings aussehen. Wie groß ist der Stack z.B. letztlich bzw. was ist angefordert. Dann kommt es darauf an ob und was für lokale Variablen auf dem Stack liegen. So ein Stacklimit überschreitet man bei Rekursion schneller als man denkt. Die maximale Pfadlänge beträgt bei NTFS 32767 Zeichen. Bedeutet Rekursionstiefen von 10000+ sind problemlos machbar (Pfad: \\.\C:\A\A\A\A\A\...). Wenn Du dann bei jeder Funktion n 50 kb Array auf dem Stack liegen hast, krachts.

Zitat:

Zitat von himitsu

nur daß es eigentlich nahezu überall rekursiv gelöst wird (nja, so ist es halt auch noch irgendwie einfacher)

Nur weil andere es auch falsch machen, wirds dadurch nicht besser ...

[himitsu]

Zitat:

Pfad: \\.\C:\A\A\A\A\A\...

Aber mal ganz im Ernst, wie oft kommt sowas vor?

Die 32767 Zeichen kommen nur in Verbindung mit UNC-Pfadnamen vor ... ansonsten ist bei 259 Zeichen Schluß. (MAX_PATH - die letzte #0)
Und ich glaub kaum, daß er in seinem Programm UNC verwendet.

[SirThornberry]

Ganz unberichtigt ist die Aussage das der Stack nicht unendlich groß ist nicht. Denn man kann unter anderem bei NTFS in einen Ordner eine Partition einhängen/mounten. Hat man also das Laufwerk C und drauf den Ordner A kann man in Ordner A durchaus auch wieder die Partition von Laufwerk C einhängen. Daraus resultiert eine unendliche Pfadtiefe. So etwas sollte man eventuell auch berücksichtigen. Eventuell durch festlegen einer maximalen Pfadtiefe um keine Endlosrekursion zu haben.

[Fridolin Walther]

Zitat:

Zitat von himitsu

Zitat:

Pfad: \\.\C:\A\A\A\A\A\...

Aber mal ganz im Ernst, wie oft kommt sowas vor?

Die 32767 Zeichen kommen nur in Verbindung mit UNC-Pfadnamen vor ... ansonsten ist bei 259 Zeichen Schluß. (MAX_PATH - die letzte #0)
Und ich glaub kaum, daß er in seinem Programm UNC verwendet.

Da wäre eine Rekursionstiefe von 125+ möglich. Das reicht mitunter für nen Crash. Kommt auf die lokalen Variablen an und wie groß der Stack werden darf.

Aber ansonsten ordne ich solche Aussagen wie "Das kommt so selten vor" immer in die "Famous last words" Kategorie ein ;). Ist nicht bös gemeint, aber ich erinner mich da immer an eine lustige Unterhaltung nach nem Code Audit. Zitat Entwickler: "Da würde doch niemals jemand auf die Idee kommen dort mehr als 255 Zeichen für einen Usernamen zu verwenden." Zwei Monate später gabs dann nen Exploit auf milw0rm.

Aber um wieder OnTopic zu werden:
An der Routine selbst ist nichts auszusetzen, ausser halt das der Stack ausgehen kann (was aber eher unwahrscheinlich ist, ich gebs ja zu). Hast Du aus der Funktion evtl. was rausgekürzt? Evtl. Zugriffe auf das Treeview bei dem es dann crashed? In welchem Kontext wird die Funktion ausgeführt? Aus dem Hauptthread heraus? Rennts in nem extra Thread? Wie lautet die exakte Fehlermeldung?

[himitsu]

Ich hoffe mal es läuft im Hauptthread, denn sonst wird wohl Application.ProcessMessages schuldig sein.

(im Normalfall wird es bei MAX_PATH nicht viel mehr als 30 Verzeichnisebenen geben ... aber egal)

[nat]

Zitat:

Zitat von 0xF30FC7

Eigentlich kann alles was in einer rekursiven Funktion gelöst wird, auch in einer nicht-rekursiven Funktion gelöst werden. Im Falle von Verzeichnisenumerierung ist es sogar sinnvoll.

wie würde denn dann so ein simples verzeichnis-auflistung ohne rekursion aussehen? nur mal so aus interesse.

[Mattze]

Hallo,

da habe ich ja was angestellt...
Ich hätte nicht gedacht, dass das doch ein ziemliches Problem zu sein scheint!

Ich habe aus der Function nichts rausgekürzt. Die ist schon sehr alt und es kam mir von vornherein darauf an, dass die möglichst "universell" einsetzbar ist, also möglichst in sich abgeschlossen mit genau definierten Schnittstellen von und nach draußen.

In der Delphi-Umgebung kommt weiterhin der Fehler. ("In der Klasse TVirtualExplorerEasyListview ist folgender Fehler aufgetreten: Zugriffsschutzverletzung bei Adresse... Lesen von Adresse 00000004.")
(Ich habe mir zur Vereinfachung eine globale Fehlerbehandlung gebastelt, deshalb der Klassenname.)

Ich habe jetzt FGAbbruch zum Abbruch der Rekursion gesetzt. In der Delphi-Umgebung kommt der Fehler immer noch, starte ich es standalone, kommt der Fehler nicht mehr. Muss ich aber noch eine Weile probieren. Allerdings ist das natürlich auch keine Lösung!

Wann der Fehler auftritt:
Ich habe links eine Liste von Verzeichnissen. Rechts eine Art Betrachterfenster.
Wenn ich nun auf ein Verzeichnis clicke, wird rechts im Betrachter eine neue Form erzeugt. (Oder, wenn vorhanden, deren Inhalt geändert.) In dieser Form wird nur ein Listview erzeugt und darin ein paar Informationen zum Verzeichnis angezeigt. Dafür wird eben "Foldersize" auch berechnet.
Mache ich aber einen Doppelclick, gibt es den Fehler(, aber nicht immer).

Mal sehen, ob ich das im OnClick machen kann, wo ich auf dann den Doppelclick warte. (Bisher OnItemSelectedChanged - wer's kennt. Evtl. geht es nicht anders, weil sonst die Tastatursteuerung nicht funktioniert - also Taste hoch oder so. OnKeyUp oder OnKeyDown gibt es leider nicht.)

So, fehlt noch was?

Gruß
Mattze

PS: Der Stack müsste eigentlich ausreichen. Soooo tief ist das nicht. Vielleicht 3 höchstens 4 Stufen.
Das "Lesen von Adresse 00000004" deutet eher darauf hin, dass ein Pointer nicht richtig zugewiesen wurde. Da der Fehler nur unter Delphi, aber nicht standalone auftritt, könnte das ein Zeitproblem sein!? Aber, was tun?

[Fridolin Walther]

Das würde in etwa so aussehen:

Delphi-Quellcode:

procedure EnumerateDirectory(Path : string);

  // Hilfsfunktion um aus dem Grundpfad und dem SearchRecord Array einen Pfad zu bilden
  function GetPath(Path : string; const SearchRecords : array of TSearchRec) : string;
  var
    i : Integer;
  begin
    Result := IncludeTrailingPathDelimiter(Path);
    for i := 0 to Length(SearchRecords) - 2 do
      Result := Result + SearchRecords[i].Name + '\';
  end;

var
  SearchRecords : array of TSearchRec;
  Index         : Integer;
  ErrorCode     : Integer;
begin
  SetLength(SearchRecords, 1);
  Index := 0;

  // So lang unser SearchRecords Array mindestens einen Eintrag hat, wird unsere Schleife ausgeführt ...
  while Index >= 0 do
    begin

      // Falls der derzeitige SearchRecord noch nicht initialisiert ist, tun wird dies mit FindFirst, ansonsten
      // wird FindNext benutzt um den nächsten Eintrag zu suchen
      if SearchRecords[Index].Name = ''
        then ErrorCode := FindFirst(GetPath(Path, SearchRecords) + '*.*', faAnyFile, SearchRecords[Index])
        else ErrorCode := FindNext(SearchRecords[Index]);

      while ErrorCode = 0 do
        begin
          // Falls das derzeitige Objekt kein Unterverzeichnis ist, geben wir es aus ...
          if SearchRecords[Index].Attr and faDirectory = 0
            then
              Writeln(GetPath(Path, SearchRecords) + SearchRecords[Index].Name)
            else
              // Falls es ein Unterverzeichnis ist und ungleich '.' oder '..' erweitern wir unser Array
              // und brechen die Schleife ab um von vorn zu beginnen
              if (SearchRecords[Index].Name <> '.') and (SearchRecords[Index].Name <> '..') then
                begin
                  SetLength(SearchRecords, Length(SearchRecords) + 1);
                  Index := Length(SearchRecords);
                  Break;
                end;
          ErrorCode := FindNext(SearchRecords[Index])
        end;

      Dec(Index);

      // Falls wir grade einen neuen SearchRecord in unser Array eingefügt haben ist
      // Index + 1 die Länge unseres Array. In dem Fall passiert also nichts.
      // Falls wir die Schleife normal durchlaufen haben und die Suche im derzeitigen Verzeichnis
      // somit beendet ist, ist Index + 1 die Länge des Arrays - 1. Entsprechend wird der letzte Record
      // im Array entfernt.
      SetLength(SearchRecords, Index + 1);
    end;
end;

Die Funktion ist kurz zusammengeschrieben. Ich habs zwar kurz auf Funktionstüchtigkeit getestet, allerdings übernehm ich keine Garantie das wirklich alles so funktioniert wie es soll bzw. das die generierte Dateiliste wirklich vollständig ist (will heißen ich hab den Output der Funktion nicht mit dem Output einer "normalen" rekursiven Funktion verglichen).

Prinzipiell wird in dem Falle der Stack durch ein Array simuliert. Sobald wir auf ein Unterverzeichnis stoßen, erzeugen wir einen neuen Eintrag im Array für unser Unterverzeichnis und brechen die derzeitige Schleife ab um im grade gefunden Unterverzeichnis nach Dateien zu suchen usw. usf.. Sobald ein (Unter-)Verzeichnis komplett durchsucht wurde, wird der letzte Record entfernt und die zuvor abgebrochene Schleife wieder aufgenommen. Das Ganze geschieht so lange, bis kein SearchRecord mehr im Array ist.

[Mattze]

Hallo 0xF30FC7,

vielen Dank für die nichtrekursive Variante!
Ich habe es zwar bei mir noch nicht eingebaut, aber mit der rekursiven Variante von oben
verglichen. (Etwas aufgebohrt für das FG.)

Es ergibt das gleiche Ergebnis und ist sogar etwa 1,5 ms schneller als das rekursive. (Bei dem von mir überprüften Ordner!)

Gefällt mir sehr!!!

Gruß
Mattze

[Fridolin Walther]

Das war eher ne Demonstration weil jemand gefragt hat wie man das Problem ohne Rekursion löst. Denke eher nicht das der Austausch der Funktion auch deine Access Violation behebt ;).

[nat]

die nicht-rekursive variante klingt logisch. hätte ich auch selber drauf kommen können ;)
aber is das denn nun wirklich schneller? konnte man da nich noch was rausholen wenn man
statt nem dyn. array ne verkettete liste o.ä. nehmen würde?

[Fridolin Walther]

Zitat:

Zitat von nat

die nicht-rekursive variante klingt logisch. hätte ich auch selber drauf kommen können ;)
aber is das denn nun wirklich schneller? konnte man da nich noch was rausholen wenn man
statt nem dyn. array ne verkettete liste o.ä. nehmen würde?

Klar, da kann man noch ne Menge rausholen. Die Liste ist da z.B. ein Ansatz. Dann könnte man den Pfadnamen zwischenspeichern, damit nicht dauernd GetPath aufgerufen wird, was ja jedes Mal fast das komplette Array durchgeht und den Pfad zusammen setzt. Gibt viele Möglichkeiten um da noch deutlich mehr Leistung heraus zu kitzeln. Aber es ging ja nur darum zu zeigen wie man es lösen könnte und nicht um die performanteste Implementation. Das Array ist halt meiner Ansicht nach am einfachsten zu verstehen.

[GerhardS]

Vielleicht sehe ich den Wald vor lauter Bäumen nicht: ich brauche eine Funktion, die mir einen Byte-Wert zurückliefert, wieviel Unterverzeichnisse eine Verzeichnis hat.
Hintergrund:
Ich möchte eine Anwendung schreiben, die das Bearbeiten von HTML-Dateien erleichtert. In diesen Dateien werden Pfade in der Regel so ausgedrückt:
MeinBild
Als Ausgangsverzeichnis liegt D:\MeineWebsites\RumsdaBumsda vor, es ist eine 1:1-Kopie der Dateien auf dem Webserver.
Nun möchte ich die maximale Verzeichnistiefe von D:\MeineWebsites\RumsdaBumsda herausfinden, denn damit kann ich mittels SearchTreeForFiles alle Verzeichnisebene durchforsten, ob
"images/myimage.jpg" auf "../images/myimage.jpg" oder "../../images/myimage.jpg" liegt. Wie man sieht, liegt der Unterschied in der Anzahl der von myimage.jpg zur Root liegenden Ebenen.

[Luckie]

Zitat:

Zitat von Mattze

Hallo,

meine Quelle sieht so aus:

Delphi-Quellcode:

type FG = array[0..2] of int64;  //Global definiert
     {0 - Größe, 1 - Anzahl Dateien, 2 - Anzahl unterverzeichnisse}

Was ist denn das für ein Konstrukt? Wie wäre es mit einem Record:

Delphi-Quellcode:

type
  TFoo = record
    Size: Int64;
    NumFiles: Integer;
    NumFolders: Integer;
  end;