Привет!
Думаю, как организовать функцию GUI (типа окна File Requester) со списком нужных файлов (длинные имена) текущей директории.
К примеру, для выбора .mp3 файлов для последующего воспроизведения, или любого другого требуемого типа из большого количества различных представленных - думаю, пока что должна быть возможность работать с 250-тью файлами (вместе с субдиректориями) максимум.
В окошке будет курсор, свободно перемещаемый по вертикальному списку.

Контроллер STM32 с 20к оперативы, поэтому затрачивать более 1к на нужды функции не вижу смысла.

Файловая система FatFS от Чана.

Пока остановился на таком методе:
1. Функцией f_readdir() последовательно вычитываем содержимое, индексы (порядковые номера) файлов с нужным расширением и субдиректорий сохраняем в таблице размером 250 байт. При этом остальные (не .mp3) файлы пропускаем, а индексы директорий записываем в начало таблицы, чтобы директории шли первыми.
2. Юзер, перемещая курсор GUI, фактически перемещает указатель на индекс файла в таблице.
3. Затем функцией dir_seek(индекс) устанавливаем указатель FatFS, и получаем имя файла через f_readdir().

Вроде как таким образом избегаем прямой работы с длинными именами.
Хотя по третьему пункту не уверен, что сработает - не пробовал пока...

Что скажете, уважаемые?

ЗЫ: вообще, конечно, хотелось бы формировать список в алфавитном порядке, но не вижу способа реализовать это на контроллере без большого кол-ва оперативки...

Поскольку юзер-интерфейс - штука неторопливая, то я бы сделал так:
написал обёртки поверх fatfs, типа:

int get_dir_count();
int get_file_count();
char * get_dir_name(int index);
char * get_file_name(int index);

Далее всё понятно. Имена в памяти держать не надо, при отрисовке каждый раз вызываем get_xx_name().

Сортировка с малыми затратами памяти тоже возможна, нужно лишь сортировать массив индексов. Но тут скорее всего понадобится два буфера под имена. Для экономии можно сравнивать по нескольким первым символам.

Согласен с АНТОХА


массив из 250 элементов, где каждый элемент - байт (номер файла в каталоге), и функция сравнения имен по индексу, запросто уложатся в 1kb.


Можно в стеке выделить, на время сортировки. Лучше уж стек увеличить на размер этих двух буферов.

Можно отсортировать без буферов под имена вообще, но такой способ, возможно, окажется слишком задумчивым: Массив с индексами сортировать каким-нибудь лёгким(в смысле памяти) алгоритмом( пузырёк ? ), на этапе сравнения вызывать каждый раз функцию f_readdir() (или предложенную char * get_file_name(int index)). Скорость сортировки будет упираться в вызовы этой самой функции.

А сравнения для сортировки лучше проводить по полному имени, так как для того же mp3 нередка ситуация с именами примерно такого типа:
"<Артист> - <альбом> - <номер трэка> - <трэк>.mp3" - очевидно, что добраться до значащих символов будет непросто...

Только мне не понятно, что нового предложил уважаемый Антоха?

По поводу алфавитной сортировки - сравнивать надо обязательно по полному имени (как справедливо заметил baralgin), это можно сделать и без больших затрат оперативы, но тогда количество вызовов f_readdir() будет просто зашкаливать: сначала путём сравнения имён ВСЕХ файлов директории выявляем самый "верхний" файл, затем, путём сравнения имён ВСЕХ-1 файлов директории выявляем второй файл и т.д.
Это не видится наиболее оптимальным методом по скорости работы...

А как можно сделать иначе?

Вот тут есть небольшая статья со сравнениями производительности различных алгоритмов. http://algolist.manual.ru/sort/

Пузырек - самы тормозной.

Способов - масса. Начните курить отсюда, благо способов сортировки как грязи

Не так важна скорость сортировки, когда все имена одновременно находятся в оперативе - прочитал, сохранил, отсортировал.
Сортировка в оперативке в любом случае займёт минимум времени по сравнению с чтением имени каждый раз непосредственно с диска\карты памяти...

Но не вижу другого способа, при отсутствии достаточного кол-ва памяти...

Не согласен. Бинарная сортировка приведет к количеству операций O(n*log2(n)). Точнее, сортировку достаточно будет заменить построением бинарного дерева - на это потребуется такой-же порядок операций. Для 256 узлов достаточно будет 768 байт памяти (left, right, значение). Если реализовывать красно-черное дерево, то памяти нужно будет примерно килобайт (если мне не изменяет память, для вменяемого по скорости построения красночерного дерева необходимо хранить еще и parent).

Спасибо, буду "курить" бинарную сортировку

Ну покурите заодно и поразрядную сортировку из приведенной мной статьи. На мой взгляд очень неплоха. Обращений к ФС нимимум, можно сортировать на нужную "глубину".

Просто уважаемый Антоха отвечал на ещё не отредактированное сообщение. Там ещё не было строк от
Пока остановился на таком методе:
до
Что скажете, уважаемые?



Ну тут уж либо скорость, либо память. Попробуйте, возможно всё будет не так уж и медленно.

Погодите курить, есть проще способ, с тем же результатом O(n*log2(n)). Попробую объяснить на пальцах.

У Вас есть массив индексов имен. Соответственно, любое имя однозначно определяется индексом. Допустим, массив уже отсортирован по возрастанию (не индексов, а имен). Тогда поиск места для добавления элемента будет занимать O(log2(n)), где n - текущий размер массива, это - банальный бинарный поиск. Операций извлечения настоящих имен будет требоваться столько-же. После того, как Вы нашли место, Вы в это место вставляете новый индекс. В результате массив увеличивается на один элемент и он остается отсортированным. Далее процесс повторяется. Суммарно это потребует всего лишь порядка 1800 операций извлечения имени файла на каталог из 256 файлов (если я не обсчитался). И в результате - у Вас отсортированный массив индексов, без всяких деревьев.

Спасибо, почитаю.

Хотя небольшой вопрос - все эти методы предполагают сравнение по значению некоего "ключа".
Но как получить этот "ключ" (например, в виде байта) из длиннющего имени файла?


А, тогда понятно


То есть все индексы массива, предшествующие вставке нового, будут считыватся через f_readdir() и сравниваться?

К сожалению, она не годится для рассматриваемого случая.



Не все. А только log2(n). Массив ведь сортирован, значит, оптимальным будет бинарный поиск - берем элемент по центру массива, сравниваем, в зависимости от того, больше или меньше - переходим к верхней или нижней половине, и повторяем. Если элементов в массиве, например, от 128 до 256, то необходимо будет выполнить 8 сравнений и соответственно, 8 извлечений.