Каков наилучший подход для итерации и «хранения» файлов в каталоге в C (Linux)?

Question

Я написал функцию, которая проверяет, являются ли файлы дубликатами или нет. Эта функция подписи:

int check_dup_memmap(char *f1_name, char *f2_name)

Возвращает:

• (- 1) - Если что-то пошло не так;
• (0) - если два файла похожи;
• (+ 1) - если два файла разные;

Следующим шагом является написание функции, которая перебирает все файлы в определенном каталоге, применяет предыдущую функцию и выдает отчет о всех существующих дубликатах.

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

void *build_dir_tree(char *dirname, FILE *f)
{
    DIR *cdir = NULL;
    struct dirent *ent = NULL;
    struct stat buf;
    if(f == NULL){
        fprintf(stderr, "NULL file submitted. [build_dir_tree].\n");
        exit(-1);   
    }
    if(dirname == NULL){
        fprintf(stderr, "NULL dirname submitted. [build_dir_tree].\n");
        exit(-1);
    }
    if((cdir = opendir(dirname)) == NULL){
        char emsg[MFILE_LEN];
        sprintf(emsg, "Cannot open dir: %s [build_dir_tree]\t",dirname);
        perror(emsg);
    }
    chdir(dirname);
    while ((ent = readdir(cdir)) != NULL) {
        lstat(ent->d_name, &buf);
        if (S_ISDIR(buf.st_mode)) {
            if (strcmp(".", ent->d_name) == 0 ||
                    strcmp("..", ent->d_name) == 0) {
                continue;
            }
            build_dir_tree(ent->d_name, f);
        }
        else{
            fprintf(f, "/%s/%s\n",util_get_cwd(),ent->d_name);
        }
    }
    chdir("..");
    closedir(cdir);
}

Тем не менее я считаю этот подход немного неэффективным, поскольку мне приходится анализировать файл снова и снова.

По вашему мнению, какие еще подходы я должен использовать:

• Записать структуру данных и удерживать файлы вместо записи в файл? Я думаю, что для каталога с большим количеством файлов память станет очень фрагментированной.
• Храните все имена файлов в автоматически расширяемом массиве, чтобы я мог легко получить доступ к каждому файлу по их индексу, поскольку они будут находиться в смежной области памяти.
• Отобразить этот файл в памяти с помощью mmap ()? Но mmap может потерпеть неудачу, поскольку файл становится большим.

Любые мнения по этому поводу. Я хочу выбрать наиболее эффективный путь и получить доступ к как можно меньшему количеству ресурсов. Это требование программы ...

EDIT: Есть ли способ получить номера файлов в определенном каталоге, не просматривая его?

Answer 1

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

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

Эффективным методом обхода файлов и каталогов является использование ftw или nftw .