Crude alphabetic sorting of SD card files (sdfat)

Post your cool example code here.
Post Reply
User avatar
madias
Posts: 1198
Joined: Mon Apr 27, 2015 11:26 am
Location: Vienna, Austria

Crude alphabetic sorting of SD card files (sdfat)

Post by madias » Tue Sep 25, 2018 7:46 am

Hello,
while working on my MP3 Player (V2) project, I needed a sorting function getting out a directory list alphabetically. I wondered, because there are less useful "ready made" sorting examples for Arduino. (Lazy mode=off)
I know there are better things like bubble sorting, but this is a crude and very fast version. Will only works with SDfat!
Maybe there are some suggestions/optimizations ?
How it works?
In the first loop only the filtered (no hidden...) files are countered, so I can fire up a dynamic char* array.
In a second loop the first 20 chars of each file name are stored into this char* array AND the index of each file is also be stored into an array (this one we keep!)
First char of each filename is set to upper case (to avoid wrong sorting)
After the sorting function, the char* array can be dropped, because we only need the (sorted) array of indexes.
The output function gives back the (sorted) long file names.
Limitations
To prevent too much memory consumption, I limited:
Only 255 entries of each directory (maybe the worst limitation)
Only the first 20 chars are compared (should be enough for sorting a mp3 folder list, as example)
So temporary we need an char* array of: 21*255 bytes= 5355 Bytes (=maximum, depends on countered files). Maybe too much for other projects...
If we need more files, the variables can be modified like: Only first 10 chars sorted, but 512 possible entries= 11*512=5632 Bytes and so on.
Maybe it's a better option to sort only the 8.3 file names.

Code: (Maybe there is some overhead inside, because I cut it out from my main project file)

Code: Select all

#include "itoa.h"
#include "SdFat.h"
#include "FreeStack.h"
// **************** SD CARD
const uint8_t SD_CS_PIN = SS;
const char MP3DirPath[] = "MP3/"; // MP3 path
SdFat audio_SD;
SdFile file;
SdFile dirFile;
void setup() {
  Serial.begin(9600);
  delay(100);
  while (!Serial);
  Serial.println("SD Card directory sorting...");
  if (!audio_SD.begin(SD_CS_PIN, SD_SCK_MHZ(50))) {
    Serial.println("SD card error!");
  }
  Serial.print(F("FreeStack: "));
  Serial.println(FreeStack());
  Serial.println();
}
int count = 0;
void loop() {
  getMP3dir() ;
  Serial.println(count);
  count++;
  Serial.print(F("FreeStack: "));
  Serial.println(FreeStack());
  Serial.println();
  delay(1000);
}
void getMP3dir() {
  int MAXFILES = 255; // MAX files in directory allowed
  int numberElementsInArray = 0; // helper
  int dirfilecounter = 0; // counter of directory files
  int dirIDlist[MAXFILES];
  char xstring[20]; // temp string
  char tempString[21]; // temp string
  memset (xstring, 0, sizeof(xstring));
  memset (tempString, 0, sizeof(tempString));
  memset (dirIDlist, 0, sizeof(dirIDlist));
  if (!dirFile.open(MP3DirPath, O_READ)) {
    Serial.print("open MP3-dir Path folder failed");
  }
  while ( file.openNext(&dirFile, O_READ) && dirfilecounter < MAXFILES) { // count  MP3 subfolders
    if (  !file.isHidden()) { // avoid hidden files
      dirfilecounter++;
    }
    file.close();
  }
  if (file.isOpen())
    file.close();
  dirFile.close();
  char *fileName[dirfilecounter + 1];
  dirFile.open(MP3DirPath, O_READ); // reopen dir (rewind doesn't work?)
  while ( file.openNext(&dirFile, O_READ) && numberElementsInArray < dirfilecounter) { // getting number of MP3 subfolders
    if (  !file.isHidden()) { // avoid hidden files
     file.getName(xstring, 20); // get only 20 chars from each file name
     // file.getSFN(xstring ); // better alternative get 8.3 filename? saves RAM  
      dirIDlist[numberElementsInArray] = file.dirIndex();
      xstring[0] = toupper(xstring[0]); // upper case the first char
      sprintf(tempString, "%s", xstring);
      numberElementsInArray++;
      fileName[numberElementsInArray - 1] = (char *)malloc(21);
      sprintf(fileName[numberElementsInArray - 1], "%s", tempString);
    }
    file.close();
  }
  if (file.isOpen())
    file.close();
  dirFile.close();
  // sorting the file list (only first 20 chars)
  char *  temp;
  int temp2 = 0;
  for (int j = 0; j < numberElementsInArray - 1; j++)
  {
    for (int i = 0; i < numberElementsInArray - 1; i++)
    {
      if (strncmp(fileName[i], fileName[i + 1], 20) > 0)
      {
        temp = fileName[i];
        temp2 = dirIDlist[i];
        fileName[i] = fileName[i + 1];
        dirIDlist[i] = dirIDlist[i + 1];
        fileName[i + 1] = temp;
        dirIDlist[i + 1] = temp2;
      }
    }
  }
  // output file list
  if (!dirFile.open(MP3DirPath, O_READ)) {
    Serial.print("open MP3-dir Path folder failed");
  }
  for (int sortnumber = 0; sortnumber < numberElementsInArray ; sortnumber++) {
    file.open(&dirFile, dirIDlist[sortnumber], O_READ);
    if (sortnumber < 10)
      Serial.print("0");
    Serial.print(sortnumber);
    Serial.print(": ");
    file.printName(&Serial);
    Serial.println();
    file.close();
  }
  if (file.isOpen())
    file.close();
  dirFile.close();
  Serial.println();
  Serial.print  ("MP3 sub dir in Dir: ");
  Serial.println(dirfilecounter);
  for (int x=0;x

stevestrong
Posts: 3053
Joined: Mon Oct 19, 2015 12:06 am
Location: Munich, Germany
Contact:

Re: Crude alphabetic sorting of SD card files (sdfat)

Post by stevestrong » Tue Sep 25, 2018 9:12 am

Cool, thanks for sharing.

One short remark, you wrote that rewind() does not work?
I wonder why, because if you change the cwd, which is same as vwd, then it should work, like here: https://github.com/greiman/SdFat/blob/m ... ns.ino#L55
I use it in another project and it works for me.
Take care about using "file.open(...);" or "file = sd.open(...);", which should be the same but I have the feeling they are not quite identical (from experience), the latest working more robustly.

User avatar
zoomx
Posts: 835
Joined: Mon Apr 27, 2015 2:28 pm
Location: Mt.Etna, Italy

Re: Crude alphabetic sorting of SD card files (sdfat)

Post by zoomx » Tue Sep 25, 2018 10:39 am

For a project of mine I had to do a similar task but my matrix was different since in each filed I have a namefile of same lenght and a index. I have to sort that matrix by index, not by name.

Since I am lazy I used ArduinoSort library
https://github.com/emilv/ArduinoSort


You sort algorithm seems me a bubble sort

Code: Select all

if (strncmp(fileName[i], fileName[i + 1], 20) > 0)
but maybe it lacks a flag to indicate that a change was made and a control that if there is no change you have finished and it seems that you cycle the array only one time.
Maybe I don't understand something....

User avatar
madias
Posts: 1198
Joined: Mon Apr 27, 2015 11:26 am
Location: Vienna, Austria

Re: Crude alphabetic sorting of SD card files (sdfat)

Post by madias » Tue Sep 25, 2018 11:16 am

You are right, it's a kind of bubble sort ;) (I swapped the algorithm to a better one and I forgot about that).
Maybe it's also too overcomplicate, but in my first version I thought that I have "unknown" file name lengths, but I cut it down to 20, so the dynamic char* array isn't compellingly needed. (But it works, only thing to remember is to (free) it, otherwise you'll get into troubles as quick as you can think - and the "blink of death" isn't a real meaningful debugging method - believe me ;) )
The ArduinoSort "library" (can't call that little code library) sorts only numbers, but not char* arrays - surly enough for sorting the index. But I needed the alphabetical order of the filenames and storing the index sequence.

stevestrong
Posts: 3053
Joined: Mon Oct 19, 2015 12:06 am
Location: Munich, Germany
Contact:

Re: Crude alphabetic sorting of SD card files (sdfat)

Post by stevestrong » Tue Sep 25, 2018 11:21 am

ArduinoSort:
Easy

This is almost always what you want:

sortArray(nameOfYourArray, 10);

This will sort an array of 10 elements. Works with int, float, bool, char, String and char*.
https://github.com/emilv/ArduinoSort/bl ... .h#L29-L31

User avatar
madias
Posts: 1198
Joined: Mon Apr 27, 2015 11:26 am
Location: Vienna, Austria

Re: Crude alphabetic sorting of SD card files (sdfat)

Post by madias » Tue Sep 25, 2018 11:25 am

Ok, I only read the first intro:
ArduinoSort
Easy sorting of arrays for Arduino, with focus on low memory footprint.

Easy to use
Small. Less program storage space than bubble sort or qsort!
Fast
Works with most data types, including int, float, String and bool
Advanced users can add their own comparison function!
Maybe I read over "String", because I avoid strings (or Strings as class) like the devil the holy water. (maybe this is obsolete these days in Arduino land...)
The sorting algorithm itself wasn't / isn't the problem. More about how to sort a whole directory with many (long named) files and this can only be a compromise between RAM usage and speed and accuracy. Maybe a better approach with very many files could be to sort them by the first letter: So taking every filename beginning with "0", then "1" (...) and doing a "first letter array", so if the user is cruising through the directory you only handle a sublist. But remember: A long file name can be up to 255 chars. As we are talking about sorting SD Card files, the next approach could be writing sublists to the card (csv) as "external memory". This should only be triggered if something changed - so counting every file on the SD card (or a date/time stamp/flag) and comparing it to older results (something like that).

User avatar
zoomx
Posts: 835
Joined: Mon Apr 27, 2015 2:28 pm
Location: Mt.Etna, Italy

Re: Crude alphabetic sorting of SD card files (sdfat)

Post by zoomx » Tue Sep 25, 2018 2:08 pm

madias wrote:
Tue Sep 25, 2018 11:16 am
The ArduinoSort "library" (can't call that little code library) sorts only numbers,
No, you can define you own custom comparison function, I made it. It is described in readme.
I didn't check if this library waste memory or not, I tested only with a small array with my custom comparison function.
I used a char array, not String, like you.
That was my test Struct

Code: Select all

struct FileScore {
  char filename [11];
  uint16_t score;
};
and that was the simple test array

Code: Select all

FileScore my2dArray[5] = {
  {"FirstFile", 2},
  {"SeconFile", 4},
  {"ThirdFile", 8},
  {"FourtFile", 7},
  {"SixthFile", 1}
};
I used sortArray in this way

Code: Select all

sortArray(my2dArray, 5, firstIsLarger2);
and my custom function was

Code: Select all

bool firstIsLarger2(FileScore first, FileScore secondo) {
  if (first.score > secondo.score) {
    return true;
  } else {
    return false;
  }
}
Arduino C++ support qsort function but I was not able to use it with my test array.

stevestrong
Posts: 3053
Joined: Mon Oct 19, 2015 12:06 am
Location: Munich, Germany
Contact:

Re: Crude alphabetic sorting of SD card files (sdfat)

Post by stevestrong » Tue Sep 25, 2018 2:20 pm

Use a temp file on SD card to store the unsorted file list.
The row number can point/offset to the file index.
Store onto SD card the sorted file list, too, in a file called "__index.txt" or so to be sure it will be the first or last after sorting files.
Eventually make it hidden.
Then run a check each time you start the application (or change files) and update the index file accordingly only with differences. This check/update should be much faster than sorting again from scratch.

User avatar
zoomx
Posts: 835
Joined: Mon Apr 27, 2015 2:28 pm
Location: Mt.Etna, Italy

Re: Crude alphabetic sorting of SD card files (sdfat)

Post by zoomx » Tue Sep 25, 2018 3:21 pm

This is in the plan but it is also a bit more complicated. The high score indicate that the associated file is to be transmitted before the others then it will be deleted from the list. Meanwhile others file are created and some of then can get an high score !

Post Reply