Задача. Разработать консольную программу, которая следит за изменениями в директориях.
Изучаем задание, ужесточаем требования.
- Один поток обрабатывает не больше одной директории.
- Изменение файла определяется подсчетом контрольной суммы.
Вопрос многопоточности решается подключением заголовочного файла #include <pthread.h>, поэтому сосредоточим внимание на создании одного потока. Реализуем сначала простую программу — чтение директории и вывод её содержимого.
В стандарте языка С отсутствует понятие директории. Это проблема. А в стандарте POSIX определена структура директории, независимая от файловых систем. И это решение проблемы. Эти возможности заключены в заголовочном файле <dirent.h>.
#include <dirent.h>
#include <stdio.h>
int main()
{
DIR *dirp;
struct dirent *dp;
dirp = opendir(".");
if (dirp == NULL) { printf("couldn't open '.'"); return 1; }
while (1) {
dp = readdir(dirp);
if (dp == NULL) break;
printf("Inode %d, off %d, len %d, type %d, name %s\n",
dp->d_ino, dp->d_off, dp->d_reclen, dp->d_type, dp->d_name);
}
rewinddir(dirp);
closedir(dirp);
printf("%d, %d\n", DT_DIR, DT_REG);
return 0;
}
Теперь разберемся с контрольными суммами. Выбранный алгоритм должен обладать хорошей производительностью и простотой реализации. Под эти требования отлично укладывается циклический избыточный код (CRC), в частности crc32. Приведем наивную реализацию алгоритма.
unsigned compute_crc32(const void *data, int len)
{
unsigned crc_table[256];
unsigned crc;
const char *p = data;
for (int i = 0; i < 256; i++) {
for (int j = 0; j < 8; j++)
crc = i & 1 ? (i >> 1) ^ 0xedb88320 : i >> 1;
crc_table[i] = crc;
};
crc = 0xffffffff;
while (len--)
crc = crc_table[(crc ^ *p++) & 0xff] ^ (crc >> 8);
return crc ^ 0xffffffff;
};
Алгоритм обрабатывает данные побитово и для обработки одного байта требует восемь операций сдвига. Можно ускорить расчет, заменив операции сдвига одной операцией поиска по таблице. Таблицу заранее вычисленных величин можно посчитать при старте или записать в коде.
Позаимствуем готовую реализацию этого алгоритма из котобазы движка вконтакте.
#include "crc32.h"
#include <assert.h>
#include <stdio.h>
int main()
{
char test[] = "123456789";
unsigned check = 0xcbf43926;
unsigned crc = -1; /* 0xffffffff */
crc = crc32_partial(test, 3, crc);
crc = crc32_partial(test + 3, 4, crc);
crc = crc32_partial(test + 7, 2, crc) ^ -1;
printf("check: crc32(123456789) = 0xcbf43926\n");
assert(crc == check);
return 0;
}
Здесь не просто так использовано частичное вычисление суммы через функцию crc32_partial(). Рассмотрим полное вычисление суммы через эту функцию. Алгоритм действительно простой.
unsigned compute_crc32 (const void *data, int len) {
return crc32_partial (data, len, -1) ^ -1;
}
Поскольку вычислять контрольную сумму мы будем от файлов, нам потребуется буферизованная версия алгоритма. Размер буфера будет ориентироваться на диски, выполненные по технологии 4K. Возможности по работе с файлами стандартизованы и доступны через <stdio.h>.
unsigned crc32_buffered(const char *filename)
{
FILE *fp;
char buf[8 * 512];
unsigned size;
unsigned crc = -1; /* 0xffffffff */
fp = fopen(filename, "r");
if (!fp) { printf(open_error, filename); return 0; }
while(!feof(fp)) {
size = fread(buf, 1, 8 * 512, fp);
if (ferror(fp)) { printf(read_error, filename); return 0; }
crc = crc32_partial(buf, size, crc);
}
fclose(fp);
return crc ^ -1;
}
Теперь объединим две программы вместе и получим новую — чтение директории и вывод списка файлов с их контрольными суммами. Эта программа послужит основой для одной итерации слежения за изменениями.
void dirent(const char *dirname)
{
DIR *dirp;
struct dirent *dp;
char *full_name;
unsigned crc;
dirp = opendir(dirname);
if (dirp == NULL) { printf(dir_open_error, dirname); return; }
full_name = malloc(strlen(dirname) + FILENAME_MAX + 1);
while (1) {
dp = readdir(dirp);
if (dp == NULL) break;
if (dp->d_type != DT_REG) continue;
filename(full_name, dirname, dp->d_name); /* full_name = dirname + / + dp.d_name */
crc = crc32_buffered(full_name);
printf("%8x\t%s\n", crc, dp->d_name);
}
closedir(dirp);
free(full_name);
return;
}
Получив рабочую итерацию, можно определить рабочий поток программы. Одна итерация потока состоит из нескольких этапов:
- Чтение директории и поиск новых файлов;
- Проверка контрольной суммы для существующих файлов;
- Определение удаленных файлов.
Для этого потребуется структура данных, которая должна удовлетворять следующим требованиям:
- Быстрая вставка новых элементов;
- Быстрый поиск элементов;
- Быстрое удаление элементов;
- Простота реализации.
Для решения этой задачи можно использовать комбинацию из трех векторов (линейных списков). Первый вектор используется для хранения имен файлов и контрольной суммы. Второй — хранит хеши имен с ссылкой на первый вектор для быстрого поиска. В третьем отмечается обход элементов из второго вектора — для быстрого определения удаленных файлов. И все операции со структурой составляют простой интерфейс:
vector_t *init_vector(void);
/* insert_vector returns
0 : successful insert
1 : collision detected
*/
int insert_vector(vector_t *vec, const char *name, unsigned crc);
/* search_vector returns
0 : not found
1 : found
*/
int search_vector(vector_t *vec, const char *name);
/* update_crc_vector returns
0 : successful update
1 : stored crc same
-1 : name not found, use insert_vector
*/
int update_crc_vector(vector_t *vec, const char *name, unsigned crc);
void new_traverse_vector(vector_t *vec);
delete_query_t *delete_not_traversed(vector_t *vec);
void release_vector(vector_t *vec);
Объединив все наработки, получаем готовую программу. Исходный код доступен в архиве. После распаковки, сборка осуществляется командой.
gcc crc32.c read_directory.c -o {exe} -lpthread
Можно использовать компилятор clang.