Так или иначе сталкиваться с регулярными выражениями приходилось большинству разработчиков. Мое первое знакомство произошло с реализацией regex в STL std::regexp. Чаще всего регулярки используются в проверке входных данных, что-то вроде проверки корректности введенного пользователем URL, адреса IPv4, адреса IPv6, телефонного номера и при этом скорость выполнения операции regex не сильно влияет на время отклика от приложения. Но, что если вам приходится проверять сотни, тысячи или даже десятки тысяч правил и все это на постоянно меняющихся наборах входных данных в реальном времени? В этой ситуации вам не просто нужен быстрый алгоритм, вам понадобится лучший из них, вам понадобиться чемпион!

Преамбула

Я работаю в команде разработки встраиваемого ПО на базе GNU Linux для телекоммуникационного оборудования. В ходе разработки у нашей команды появляется огромное количество прошивок для нашего оборудования: релизные версии, предрелизные версии, тестовые отладочные сборки, сборки для разных веток из трекера задач — и все это для разных аппаратных платформ.

Для идентификации файлов прошивки в системе документооборота и трекере используются MD5 хеши в файлах *.md5. В итоге имеем несколько деревьев в файловой системе для хранения прошивок.

Обновление ПО, а именно передача прошивки в изделие, происходит через протокол TFTP.

Постановка задачи

Необходимо избавиться от "головной боли" при поиске и идентификации нужной прошивки, для чего необходимо чтобы сервер TFTP осуществлял поиск и выгрузку файлов используя их md5-хеш, осуществляя рекурсивный поиск по нескольким каталогам.