Forum: Mikrocontroller und Digitale Elektronik FAT Verzeichniseinträge nach Namen sortieren


von ape (Gast)


Lesenswert?

Hallo,
Der Betreff sagt ja eigentlich schon alles: Ich möchte die Einträge in
einer Verzeichnistabelle von einem FAT Dateisystem alphabetisch
sortieren.
Da der Speicher im AVR nicht ausreicht, kann ich nicht alle Dateinamen
in ein Array laden. Die üblichen Sortieralgorithmen wie Bubblesort,
Quicksort usw. fallen also flach, da diese ja darauf angewiesen sind
die Elemente verschieben zu können.
Ich würde es jetzt so machen, dass ich für den ersten Eintrag das
kleinste Element suche, und dieses im Speicher halte. Um weitere
Einträge zu erhalten, suche ich das kleinste Element das größer ist als
das gespeicherte Element, speichere dieses wieder usw.
Das ganze dürfte aber sehr schnell sehr langsam werden, gibts da
effizientere Algorithmen die nicht darauf angewiesen sind die einzelnen
Elemente verschieben zu können und möglichst wenig Speicher brauchen?

von Simon (Gast)


Lesenswert?

An deiner stelle würd ich folgendes versuchen: Du legst in deinem AVR
nicht die dateinamen sondenr nur einen index (quasi ein link/pointer)
zu dem entsprechenden Eintrag an. So kannst du prinzipiell deinen
Quicksort/Bubblesort wieder anwenden.
Beispiel:

Dateinamen:

Dateiname:    ADatei.txt    BDatei.txt     DDatei.txt    CDatei.txt
Adresse:      1             2              3             4

Speicher AVR: 1             2              3             4

nun der sort-algorythmus;
Ergebniss:
Speicher AVR: 1             2              4              3

Hab sowas noch nie gemacht, mein beitrag ist nur ein gedankt, daher wär
es nett, wenn ich eine rückmeldung ung den code bekommen könnte wenn du
diese sache hinbekommst.

MfG

von ape (Gast)


Lesenswert?

Hallo,
Im Prinzip würde das gehen denk ich, aber der Pointer auf eine Datei
(die Cluster-Adresse) ist bei FAT16 16 Bit und bei FAT32 sogar 32 Bit,
bei FAT16 kann das Root-Verzeichnis maximal 512 Einträge besitzen, bei
Unterverzeichnissen gibts glaub ich gar keine Beschränkung... Aber
selbst wenn man bei FAT16 und 512 Einträgen bleibt, wär das schon 1kB.
Mit nem mega128 müsste das schon noch drin sein, aber wenn ich auf
Festplatte mit FAT32 umsteige (arbeite momentan noch mit einer MMC)
würd das langsam echt unhandlich.

Wobei man müsste die Pointer Größe eigentlich auch bei FAT32 auf 16 Bit
beschränken können, in dem man nicht die Cluster-Adresse speichert
sondern die Nummer in der Verzeichnis-Tabelle...

Ich denke ich werds mal auf diese Weise probieren.

von Simon (Gast)


Lesenswert?

dann geb nur einmal einen den pointer auf den ersten eintrag in der
liste an. Dann nummerrierst du alle restlichen dateien von eins bis
256. Die Adressen kannst du dann berechnen/ermitteln. aber auf diese
art sind auch nur 256 dateien drin.
Als Alternative fällt mir nur noch folgendes ein:
Du schreibst dir eine funktion namens GetFile(int index);

bsp: index = 5;
nun durchsucht dein Programm die liste 5x jeweils nach dem Eintrag der
an erster stelle der sortierten liste stehen müsste und speichert
seinen index ab (sortiert ihn aus). nun bei dem nächsten durchgang (von
den 5 stück) wird der eintrag mit dem index, der aussortiert wurde,
einfach ignoriert und somit der 2. eintrag in der liste ermittelt. Dies
machst du nun so oft, bis du die entsprechende datei gefunden hast.

von Thorsten (Gast)


Lesenswert?

@Simon

>Die Adressen kannst du dann berechnen/ermitteln.

Es gibt da natürlich das Problem, daß die Dateien nicht alle schön brav
der Reihe nach angeordnet sind.

>Als Alternative fällt mir nur noch folgendes ein:
>Du schreibst dir eine funktion namens GetFile(int index);

Diesen Ansatz hatte ich mal probiert, hat soweit auch funktioniert.
Prolem ist nur, daß diese Methode bei SEHR vielen Datein extrem langsam
wird.

von Tobi (Gast)


Lesenswert?

ich denk daran wird jeder ansatz scheitern. entweder schnell und einiges
im speicher (indextabellen, dateinamen...) oder langsam und sparsam (1-2
speicherzugriffe pro vergleich). beides vereinen wird wohl kaum gehen...

von ape (Gast)


Lesenswert?

Also ich machs jetzt so:
Ich habe eine Funktion der ich das zu sortierende Verzeichnis übergebe.
Diese sucht dann alle gültigen Dateieinträge und speichert deren
Verzeichnistabellenindex in einem Array. Der Index ist ein 16 Bit Wert
ich habs jetzt auf maximal 512 Einträge pro Verzeichnis beschränkt,
damit ergibt sich eine Array-Größe von 1kB. Mit nem mega128 ist das
noch verschmerzbar. Außerdem wird die Start-Cluster-Adresse der
Verzeichnistabelle gespeichert.
Eine weitere Funktion kann dann jeweils 2 Einträge des Arrays
vergleichen. Dafür wird mit Hilfe der Start-Cluster-Adresse und dem
Index aus dem Array der Verzeichniseintrag erneut gelesen und der 8.3
Name, sowie die Dateiattribute gespeichert. Die Werte werden dann
verglichen und ein entsprechender Wert zurückgegeben.
Mit der Vergleichsfunktion und dem Index-Array kann ich dann den in der
avr-libc enthaltenen Quick-Sort Algorithmus drauf loslassen.
Hinterher stehen dann im Array die Indizes der Verzeichniseinträge in
alphabetisch sortierter Reihenfolge mit Verzeichnissen am Anfang.

Ich denke das ist ein annehmbarer Kompromis zwischen Geschwindigkeit
und Speichernutzung, und mehr als 512 Einträge zu sortieren würde auf
dem AVR wahrscheinlich eh zu lange dauern. (Wahrscheinlich sind auch
512 schon viel zu viel)
Mit 18,432MHz Takt und einem Verzeichnis mit 25 Einträgen brauch die
Funktion zum Lesen und Sortieren jedenfalls ca. 130ms, ich denke das
ist ein akzeptabler Wert.
Werd jetzt noch ein paar weitere Funktionen hinzufügen, dann gibs das
in der Codesammlung.

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.