ГЕННАДИЙ МОХОВ, программист в НУЦ «Качество», Москва, mgw@yandex.ru

Разработка кросcплатформенной утилиты
поиска файлов по имени с применением языка D

В статье рассмотрен пример реализации кроссплатформенной утилиты индексирования файловых систем с применением языка программирования D. Показаны некоторые простейшие возможности самого языка, детально рассмотрен алгоритм утилиты. Проверена возможность работы на Windows 32/64, Linux 32/64 и Mac OS X 64

Одной из частых задач при системном администрировании является поиск файла по имени и расширению, без рассмотрения содержимого искомого файла. Это нужно и при настройке конфигураций, например при поиске файла конфигурации какого-либо сервиса, и для обычных пользователей, просто для поиска собственных файлов.

В современных ОС уже существуют встроенные механизмы для осуществления такого поиска. В Linux и Mac OS X – это как классические утилиты типа find и locate, так и различные утилиты сторонних авторов. В Windows также имеется механизм индексирования, встроенный уже в саму ОС. Работу этих утилит можно разделить на два принципиально различных подхода.

Первый – начать поиск перебором по файловой системе, сразу после поступления запроса. Так работает утилита find. Среди достоинств такого подхода – наиболее полный поиск, который может обнаружить файлы, созданные «только что…». Как недостаток – медленная скорость работы, особенно на сетевых подключаемых носителях.

Второй – предварительно осуществить индексацию файловой системы, сохранив полученный кэш. После получения запроса на поиск сам поиск осуществляется по предварительно полученным файлам кэша. Здесь ситуация обратная. Сам поиск осуществляется достаточно быстро, но есть вероятность ненахождения файла созданного «только что…», т.к. реально такой файл еще не попал в базу кэша при работе процесса индексации.

В этой статье будет рассмотрен опыт написания собственной утилиты поиска второго типа. Главным требованием при создании этой утилиты явилась кроссплатформенность, то есть возможность единообразной работы на Windows, Linux и Mac OS X. Также хотелось получить простую структуру файла индекса для дальнейшей обработки ее сторонними приложениями. И последний критерий – это скорость создания индексного файла, хотя со временем стало понятно, что это не самое важное, т.к. процесс индексирования обычно запускается ночью по расписанию.

Изначально данная утилита задумывалась как решение задачи по индексированию больших томов Windows файл-сервера, имеющего более миллиона хранящихся файлов. Имена файлов были длинные и довольно информативные, содержали русские буквы и цифры (пример: «143234 Иванов Иван Петрович РОНКТД 2015.doc») и фактически представляли собой базу данных. Не хватало только системы индексирования, которую и должна была выполнять проектируемая утилита.

Выбор компилятора

В качестве языка программирования для создания такой утилиты был выбран D [1]. Компилятор языка кроссплатформенный, создает приложения непосредственно в машинных кодах процессора, как в 32- так и в 64-разрядном исполнении, а значит, гарантирует максимальную скорость выполнения созданного приложения. Имеет похожий на С++ классический синтаксис, что значительно облегчает его изучение. RunTime-библиотека имеет структуру, основанную на пакетах, и содержит большое количество готовых реализаций различных алгоритмов, в том числе встроенную обработку строк в различных кодировках. Сам компилятор и его окружение бесплатные, сообщество программистов на специализированных форумах активное и всегда готово помочь в трудных вопросах. Существует достаточное количество литературы, в том числе русскоязычной, с подробным описанием принципов построения языка и возможностей внешних библиотек.

Те отличия возможностей D от классического С++, что мы будем применять в нашей разработке, подробно опишем непосредственно при встрече с ними при обсуждении алгоритма. Язык программирования D довольно сложный, имеет несколько уровней абстракций. Однако при написании нашей утилиты использовался простой, классический подход, без применения «синтаксического сахара», шаблонов функций, делегатов и прочих специализированных средств.

Структура индексного файла

При проектировании структуры индексного файла особый упор делался на его простоту и удобочитаемость. Сразу же было отклонено применение каких-либо БД, т.к. их поддержка требует дополнительных ресурсов.

Проведем небольшой расчет. Предположим, что нам надо хранить информацию об 10 миллионах файлов, причем средняя длина полного (FullPath) имени файла 100 символов. При использовании однобайтовой кодировки, например, стандартной для Windows CP1251, нам надо иметь 10M * 100 => приблизительно один 1G для хранения всех полных путей имени файла. Хотя 1G для современных компьютеров не очень много, но все равно достаточно затратно. Первое, что просится, – этоотделить полный путь от самого имени файла. Как правило, в одной папке всегда лежит несколько файлов. Допустим, что из 100 символов полного пути файла у нас 50 символов идет на имя и 50 символов на имя папки, в котором этот файл лежит. В среднем будем считать, что в папке лежит 10 файлов. Таким образом, на хранение только имен уйдет 10M * 50 = 500M. На хранение путей до папок уйдет 10M / 10 * 50 = 50M. Таким образом, в среднем нам надо иметь 550M символов дляхранения такого количества индексной информации. Такой объем информации вполне по силам полностью держать в памяти приложению разрядности 32.

Итак, у нас получается, что достаточно иметь два строчных массива: один для хранения имен, другой для хранения путей файлов. Расположим эти два массива друг за другом в нашем индексном файле. В начале идет перечень всех путей до папок, причем индексом в массиве в памяти будет просто номер строки в файле. Затем через разделитель идет второй массив, содержащий только имена файлов. Причем на имя файла можно подвесить дополнительную информацию, номер папки иразмер файла (в нашем случае).

Пример такого индексного файла:

r:\Каталог\Каталог_1

r:\Каталог\Каталог_2

r:\Каталог

#####

0|Файл_1.txt|3452

0|Файл_2.txt|345

1|Файл_10.txt|8675

1|Файл_11.txt|267865

2|Файл_1.txt|556778

3|Файл_2.txt|7654

Что соответствует следующей структуре:

• r:\Каталог\Файл_1.txt
• r:\Каталог\Файл_2.txt
• r:\Каталог\Каталог_1\Файл_1.txt
• r:\Каталог\Каталог_1\Файл_2.txt
• r:\Каталог\Каталог_2\Файл_10.txt
• r:\Каталог\Каталог_3\Файл_11.txt

Проведенный расчет показывает, что всю работу по созданию и обработке нашего индексного файла можно проводить в оперативной памяти приложения.

Алгоритм

Прежде чем описывать алгоритм, следует рассказать о тех возможностях языка программирования D, которыми мы будем пользоваться при проектировании алгоритма нашей задачи.

• Динамические массивы. Это массивы, размер которых может изменяться динамически во время работы приложения. Никакого предварительного объявления размеров массива не требуется. Это касается любых массивов, не важно, какого типа элементы они в себе содержат. Обозначаются пустыми скобками «[]». Пример: string[] – массив строк, char[] – строка и т.д.
• Строки. Фактически это следствие динамических массивов. Строки могут быть любой длины, иметь различную кодировку. Уже в самом языке есть поддержка всех необходимых строчных операций. char[] – строка.
• Конкатенация. Символ «~» производит добавление элемента в массив. С помощью него можно сцеплять строки («ABCD» = «AB» ~ «CD») или добавлять строки в массив.

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

Пример: имя приложения ffc:

Windows: ffc ИндексныйФайл.txt C:\Windows D:\ E:\

Linux: ffc ИндексныйФайл.txt /

Mac OS X: ffc ИндексныйФайл.txt /Users

Таким образом, первое наше действие после старта приложения будет следующим (далее исходный текст на языке программирования D):

string[]  dirs; // Список точек входа для индексации. Дин.Массив

string  nameFileIndex; // Имя файла индекса. Строка.

// При старте приложения args Дин.Массив строк

int main(string[] args) {

    // Перебор всех элементов в массиве

    foreach (i, arg; args)  {

        switch(i) {

            case 0: break; // Имя программы

            // Имя файла индекса

            case 1: nameFileIndex = arg; break;

            // Дин.Массив dirs из папок для индексирования

            default: dirs ~= arg; break;

        }

    }

    // Проверка имени индекса

    if(nameFileIndex.length == 0) { writeln("Error: Not name file index");  return 1;  }

    // Проверка точек входа

    if(dirs.length == 0) { writeln("Error: Not dir for index"); help(); return 2;    }

	...

Здесь все просто. Читается динамический массив строк, который содержит все входные параметры запуска нашего приложения. Далее циклом foreach производится перебор этого массива, и далее switch выделяет (формирует) имя индексного файла и список (дин.массив) папок для индексирования. После цикла проверка на наличие имени индексного файла (длина имени файла должна быть не нулевая) и наличие имен папок для индексирования.

С этого момента мы имеем перечень готовых параметров для работы нашего приложения. Теперь самое время задействовать готовую функцию для перебора всех имен файлов в файловой системе. Такой возможностью обладает функция dirEntries из пакета std.file [2].

Если на вход этой функции подать имя папки, то, используя ее возможности, можно обойти все вложенные папки, получив полный список всех содержащихся в них файлов. Для унификации и экономии места сами строки в индексном файле будем хранить в кодировке CP1251 (стандартной для Windows). Для этого воспользуемся функциями пакета asc1251 [3], т.к. сам D работает со строками в UTF-8-кодировке.

Посмотрим, как выглядит данный алгоритм на псевдокоде:

ПеребратьВсеПапкиИзВходногоМассива(Папка; dirs) {

ПеребратьВсеФайлы(ЕдиничныйФайл; Папка) {

	// Разделим полное имя на путь и собственно имя,

	// используя стандартные функции пакета std.path

	ИмяФайла = baseName(ЕдиничныйФайл);

	ПутьФайла = dirName(ЕдиничныйФайл);

	// Переведем полученные имена в CP1251

	ИмяФайла = fromUtf8to1251(ИмяФайла);

	ПутьФайла = fromUtf8to1251(ПутьФайла);

	// Найдем номер (или добавим, если его нет) пути в массиве путей

	НомерПути = ПолучитьНомерПутиИзМассиваПуте(ПутьФайла);

	// Добавим имя файла в массив файлов

	СтрокаИмени = НомерПути + "|" + ИмяФайла + "|" + РазмерФайла(ИмяФайла);

	// Непосредственное добавление в массив

	СтрокаИмени ~= МассивИменФайлов;

}

}

Фактически функция «ПолучитьНомерПутиИзМассива-Путей()» формирует массив путей, осуществляя поиск по массиву путей, либо осуществляет добавление в этот массив при условии, что текущий путь не найден. Таким образом, при рассмотрении очередной строки с именем файла происходит добавление информации в два наших динамических массива.

Посмотрим поближе на функцию «ПолучитьНомерПутиИзМассиваПутей()». Алгоритм ее работы следующий: получить строку пути; осуществить перебор массива путей и поиск в нем полученной строки; если данная строка найдена, то вернуть ее порядковый номер, если строка не найдена, то добавить строку к массиву и вернуть ее порядковый номер. Это общий алгоритм. Однако такой вариант предполагает, что будет произведен полный перебор массива, в худшем случае, если в нем нет искомой строки. Встает задача придумать какое-то ускорение данного алгоритма.

Первое, что напрашивается, – это проверить, а не был ли данный путь (искомая строка) использован только что. Ведь в папке лежит несколько файлов, и, значит, их пути должны повторяться. Для этих целей введена статическая переменная «ПредыдущаяСтрока».

При начале поиска производится сравнение: а вдруг тот путь, который сейчас нам надо найти, был на предыдущем шаге? Если это так, то тут же выдается номер строки без дальнейшего перебора самого массива.

Применим еще один алгоритм уменьшения перебора массива, а значит, ускорение поиска. Дело в том, что к нам в функцию поступают пути разной длины. Очевидно, что искать в массиве путь (строку) той длины, которой мы туда не добавляли, нет необходимости. Осталось где-то запомнить, было ли добавление пути определенной длины или нет. Для этих целей используется глобальный массив:

size_t[1000] vec; // вектор кэша на строки до 1000 символов

В этом массиве номер элемента, есть строка определенной длины, а значение есть номер этой строки в массиве. Пример: строка на два символа, которая в массиве наших путей стоит 10-й, будет отражена следующим образом: vec[2] = 10. Таким образом, мы можем проверить, а есть ли в массиве вообще строки длинной 25, просто посмотрев, что записано в vec[25], и если там 0, то нет смысла искать строку в массиве, там ее нет, и надо просто ее туда добавить. С другой стороны, вячейках массива vec мы храним позицию в массиве последней записанной строки такой длины, а это значит, что за этим номером в массиве явно нет строк нужной нам длины и, значит, там эти строки искать не надо.

Ниже представлен псевдокод нашей функции:

// Вектор кэша на строки длины до 1000 символов

Size_t[1000] vec;

// Строка хранит предыдущий запрос на поиск

ПредыдущаяСтрока;

// Позиция предыдущего запрос на поиск в массиве

ПредыдущаяПозиция;

// Массив путей в котором и будем искать наши строки

String[] mPath;

ПолучитьНомерПутиИзМассиваПутей(ПутьФайла) {

    Bool найденоЧтоЛибо = false;

    // Результат, позиция найденная или добавленная

    size_t rez;

    If(ПутьФайла == ПредыдущаяСтрока) return ПредыдущаяПозиция;

    If(vec[ПутьФайла.Длина] > 0) {

	For(ПозицияВмассиве = vec[ПутьФайла.длина]; ПозицияВмассиве != 0; ПозицияВмассиве--) {

	    If(mPath[ПозицияВмассиве] == ПутьФайла) {

		rez = mPath[ПозицияВмассиве];

		найденоЧтоЛибо = true;

		ПредыдущаяСтрока = ПутьФайла;

		ПредыдущаяПозиция = rez;

		break;

	    }

	}

    }

// Ни чего не найдено в массиве

    If(!найденоЧтоЛибо) {

	mPath ~= ПутьФайла; // Добавим путь в массив

	rez = mPath.длина-1;

	ПредыдущаяСтрока = ПутьФайла;

	ПредыдущаяПозиция = rez;

    }

    Return rez;

}

Теперь, когда мы сформировали в памяти нашего приложения оба массива – массив путей и массив имен файлов, нам осталось выгрузить их в индексный файл. В начале в цикле foreach записываем массив mPath, затем разделитель (строка вида «#####») и в конце в цикле foreach записываем массив «МассивИменФайлов».

Реализация

В предыдущем параграфе мы детально разобрали алгоритм нашего приложения. Естественно, полностью приводить здесь листинги исходного кода нет смысла. Их вы можете посмотреть (скачать, компилировать) с сайта GitHub [4].

Это один из примеров, входящих в библиотеку QtE5, которая предоставляет возможность использовать ограниченное множество Qt-5 из языка программирования D. Данный пример состоит из двух приложений:

• FFC – то, что мы и разбирали в данной статье;
• FFX – приложение на D с применением Qt-5 для визуализации поиска по индексному файлу.

На рис. 1 и 2 представлена работа этих приложений. Поиск любого файла с использованием индекса не превышает двух секунд на используемом нами оборудовании.

Рисунок 1. Слева в командном окне показаны компиляция обоих приложений, их запуск и работа в Windows 7

Рисунок 2. Те же приложения, но в 64-разрядном исполнении в Mac OS X Yosemite

В качестве дальнейшего развития нашего приложения можно предложить сравнение двух индексных файлов, полученных с разницей в сутки. Тогда по ним можно вычислить, какие файлы в системе подверглись изменениям, и провести их архивацию. Либо можно следить за изменениями ключевых файлов ОС в целях проверки на заражение вирусами.

***

Подробным описанием этого приложения хотелось продемонстрировать несколько моментов:

• Современные языки программирования (D) позволяют легко писать утилиты для администрирования различных ОС благодаря встроенным механизмам кроcсплатформенности.
• Несмотря на обилие платных и бесплатных утилит с подобными рассматриваемыми свойствами, всегда остается место для самостоятельного творчества, причем получаемый результат бывает не хуже платных приложений.

1. Официальный сайт языка программирования D – https://dlang.org.
2. Стандартный библиотечный пакет std.file – https://dlang.org/phobos/std_file.html.
3. Пакет работы с кодировками Utf-8, cp1251, dos866 – https://github.com/MGWL/QtE5/tree/master/source.
4. Исходные тесты утилиты индексирования – https://github.com/MGWL/QtE5/tree/master/examples/FileFind.

Ключевые слова: QtE5, D, dlang.

Комментарии могут оставлять только зарегистрированные пользователи