Используя C, я в основном хочу создать абстрактный тип данных, который представляет сводную информацию о файловой системе.Каждый каталог является узлом в дереве, который содержит информацию о файлах в этом каталоге и связанный список указателей на каждый подкаталог:
struct node:
int file count
struct node* head (pointer to "first next" of linked list of subdirectories)
struct node* next
В начале своего процесса я решил попробовать итеративный подход, гдефункция будет принимать каталог в качестве входных данных и возвращать связанный список «подкаталогов» подкаталогов для продолжения работы через функцию. Однако в этом процессе я обнаружил, что мой неправильно связанный список не был действительной памятью после возврата функции.
Действительно, я не возражал против рекурсивного подхода, так как этот инструмент будет использоваться только домасистемы и глубина рекурсии не будут большими.Но это заставило меня задуматься - как мне создать дерево в памяти с рекурсивными функциями , если я собираюсь потерять неправильно расположенные указатели при возврате каждой функции?
У меня есть чертеж структурыи написал «использовать вместо Python» в нижней части статьи - однако я хотел бы понять, что является обычной практикой для создания такого рода структур данных в C.
#include <stdio.h>
#include <dirent.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <string.h>
#include <cstring>
#define SLASH '\\' // WINDOWS SLASH
/*Classification is determined by analyzing what a folder contains. At the bottom there are Tracks
that are defined as audio files. A folder that contains one or more audio files and no subdirectories
is classified as an Album. A folder that contains one or more Albums is classified as a Collection.
A folder that contains one or more Collections is classified as a Library. The Folder classification
is reserved for folders that do not meet these classifications yet still contains Tracks.*/
enum classification{Folder, Library, Collection, Album, Track};
static int one(const struct dirent* unused)
{
return 1;
}
struct Queue_Node {
char* name;
struct Queue_Node* next;
};
struct Chain_Node {
struct Queue_Node* subdir_list;
struct Chain_Node* next;
};
struct Dir_Tree_Node {
char* name;
enum classification type;
struct Dir_Tree_Node* subdirs;
struct Dir_Tree_Node* next; //linked list of subdirectories
int audio_file_count; //current directory only
int other_file_count; //current directory only, not including folders
};
struct Cur_Dir_Info {
char* parent_path;
struct Queue_Node* subdir;
int audio_file_count;
int other_file_count;
struct Dir_Tree_Node* cursor;
};
struct Cur_Dir_Info list_and_count(char* current_directory, struct Dir_Tree_Node* cursor, struct Cur_Dir_Info* output) {
//directory listing stuff
struct dirent** eps;
int n;
n = scandir(current_directory, &eps, one, alphasort);
size_t path_length = strlen(current_directory);
struct stat* current_stat;
current_stat = (struct stat*) malloc(sizeof(struct stat));
//linked list queuing
struct Queue_Node* first = NULL;
first = (struct Queue_Node*)malloc(sizeof(struct Queue_Node));
if (!first) {
fprintf(stderr, "error: firstt (Queue_Node) allocation failed, exiting.\n");
exit(EXIT_FAILURE);
}
struct Queue_Node* current = first;
if (n >= 0) {
for (int i = 2; i < n; i++) { //scandir will index "." and ".." at 0 & 1, start at 2
//to-do parse out . & ..
char fullname[1000] = { NULL };
int j = 0;
while (j < path_length) {
fullname[j] = current_directory[j];
j++;
}
int l = 0;
if (fullname[path_length] != SLASH) {
fullname[path_length] = SLASH;
l = 1;
}
char shortname[261]; //need to dynamically allocate this in the future
if (!shortname) {
fprintf(stderr, "error: shortname (char*) allocation failed, exiting.\n");
exit(EXIT_FAILURE);
}
memcpy(shortname, eps[i]->d_name, sizeof(eps[i]->d_name));
for (unsigned int k = 0; k < strlen(eps[i]->d_name) / sizeof(char); k++) {
fullname[path_length + k + l] = shortname[k * sizeof(char)];
}
stat(fullname, current_stat);
if (current_stat != NULL && S_ISDIR(current_stat->st_mode) != 0) {
//printf("Found directory: %s\n", fullname);
// TO DO: . and .. are not valid directory names
current->name = (char*)malloc(sizeof(fullname));
if (!current->name) {
fprintf(stderr, "error: current->name (char*) allocation failed, exiting.\n");
exit(EXIT_FAILURE);
}
memcpy(current->name, fullname, sizeof(fullname));
struct Queue_Node* next = NULL;
next = (struct Queue_Node*)malloc(sizeof(struct Queue_Node));
if (!next) {
fprintf(stderr, "error: next (Queue_Node) allocation failed, exiting.\n");
exit(EXIT_FAILURE);
}
current->next = next;
current = next;
}
//TO DO: else { if (file is audio file) {count audio files} else {count other files}
}
}
else {
perror("Couldn't open the directory");
}
output->subdir = first;
return *output;
}
РЕДАКТИРОВАТЬ: Malloced памяти действует навозвращение функции, поэтому моя первоначальная рекурсивная реализация работала нормально, как только я ее отладил.Я многому учусь, и мой код выглядит вонючим в местах, где я буду признателен за предложения.
#include <stdio.h>
#include <dirent.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <string.h>
#include <cstring>
#define SLASH '\\' // WINDOWS SLASH
//Classification is determined by analyzing what a folder contains. At the bottom there are Tracks
//that are defined as audio files. A folder that contains one or more audio files and no subdirectories
//is classified as an Album. A folder that contains one or more Albums is classified as a Collection.
//A folder that contains one or more Collections is classified as a Library. The Folder classification
//is reserved for folders that do not meet these classifications yet still contains Tracks.
enum classification { Folder, Library, Collection, Album, Track };
//selector function for scandir (3rd argument)
static int one(const struct dirent* unused)
{
return 1;
}
struct Queue_Node {
char* name;
struct Queue_Node* next;
};
struct Chain_Node {
struct Queue_Node* subdir_list;
struct Chain_Node* next;
};
struct Dir_Tree_Node {
char* name;
enum classification type;
struct Dir_Tree_Node* parent;
struct Dir_Tree_Node* subdirs;
struct Dir_Tree_Node* next; //linked list of subdirectories
int audio_file_count; //current directory only
int other_file_count; //current directory only, not including folders
};
struct Cur_Dir_Info {
char* parent_path;
struct Queue_Node* subdir;
int audio_file_count;
int other_file_count;
struct Dir_Tree_Node* cursor;
};
struct Cur_Dir_Info* list_and_count(char* current_directory, struct Cur_Dir_Info* output) {
//directory listing stuff
struct dirent** eps;
int n;
n = scandir(current_directory, &eps, one, alphasort);
//printf("Files in path: %d\n", n);
size_t path_length = strlen(current_directory);
//printf("Length of pathname: %zd\n", path_length);
struct stat* current_stat;
current_stat = (struct stat*) malloc(sizeof(struct stat));
//linked list queuing
struct Queue_Node* first = (struct Queue_Node*)malloc(sizeof(struct Queue_Node));
if (!first) {
fprintf(stderr, "error: first (Queue_Node) allocation failed, exiting.\n");
exit(EXIT_FAILURE);
}
struct Queue_Node* current = first;
int count = 0;
if (n >= 3) {
for (int i = 2; i < n; i++) { //scandir will index "." and ".." at 0 & 1, start at 2
char fullname[1000] = { NULL };
int j = 0;
while (j < path_length) {
fullname[j] = current_directory[j];
j++;
}
int l = 0;
if (fullname[path_length] != SLASH) {
fullname[path_length] = SLASH;
l = 1;
}
char shortname[261]; //need to dynamically allocate this in the future
if (!shortname) {
fprintf(stderr, "error: shortname (char*) allocation failed, exiting.\n");
exit(EXIT_FAILURE);
}
memcpy(shortname, eps[i]->d_name, sizeof(eps[i]->d_name));
for (unsigned int k = 0; k < strlen(eps[i]->d_name) / sizeof(char); k++) {
fullname[path_length + k + l] = shortname[k * sizeof(char)];
}
stat(fullname, current_stat);
if (current_stat != NULL && S_ISDIR(current_stat->st_mode) != 0) {
//printf("Found directory: %s\n", fullname);
count++;
// TO DO: . and .. are not valid directory names
current->name = (char*)malloc(sizeof(fullname));
if (!current->name) {
fprintf(stderr, "error: current->name (char*) allocation failed, exiting.\n");
exit(EXIT_FAILURE);
}
memcpy(current->name, fullname, sizeof(fullname));
struct Queue_Node* next = (struct Queue_Node*)malloc(sizeof(struct Queue_Node));
if (!next) {
fprintf(stderr, "error: next (Queue_Node) allocation failed, exiting.\n");
exit(EXIT_FAILURE);
}
current->next = next;
current = next;
}
current->name = nullptr;
current->next = nullptr;
//TO DO: else { if (file is audio file) {count audio files} else {count other files}
}
current = nullptr;
//printf("Completed\n");
}
else {
perror("Couldn't open the directory");
first = nullptr;
}
output->parent_path = current_directory;
if (count > 0) {
output->subdir = first;
}
else {
output->subdir = nullptr;
}
output->audio_file_count = 1;
output->other_file_count = 2;
return output;
}
void explore_paths(struct Dir_Tree_Node* current_path, struct Dir_Tree_Node* tree_cursor) {
if (!current_path->name) {
return;
}
char* current_directory = current_path->name;
struct Queue_Node* current_subdirs = (struct Queue_Node*)malloc(sizeof(struct Queue_Node));
current_subdirs->name = current_directory;
current_subdirs->next = nullptr;
struct Cur_Dir_Info* output = (struct Cur_Dir_Info*)malloc(sizeof(struct Cur_Dir_Info));
if (!output) {
fprintf(stderr, "error: output (Cur_Dir_Info) allocation failed, exiting.\n");
exit(EXIT_FAILURE);
}
struct Queue_Node* cursor = current_subdirs; //initialize to root of path
//printf("Running: %s\n", current_directory);
tree_cursor->name = current_directory;
output = list_and_count(current_directory, output);
struct Dir_Tree_Node* head = (struct Dir_Tree_Node*)malloc(sizeof(struct Dir_Tree_Node));
if (!head) {
fprintf(stderr, "error: next (Queue_Node) allocation failed, exiting.\n");
exit(EXIT_FAILURE);
}
if (output->subdir) { //check if there are subdirectories
struct Queue_Node* list = output->subdir;
tree_cursor->subdirs = head;
struct Dir_Tree_Node* current = (struct Dir_Tree_Node*)malloc(sizeof(struct Dir_Tree_Node));
if (!current) {
fprintf(stderr, "error: next (Queue_Node) allocation failed, exiting.\n");
exit(EXIT_FAILURE);
}
current = head;
current->next = (struct Dir_Tree_Node*)malloc(sizeof(struct Dir_Tree_Node));
current->next->name = list->name;
current = current->next;
list = list->next;
while (list) {
current->next = (struct Dir_Tree_Node*)malloc(sizeof(struct Dir_Tree_Node));
current->next->name = list->name;
current->parent = current_path;
list = list->next;
current = current->next;
current->next = nullptr;
}
current = head->next;
while (current->next) { //won't work if there is a single subdirectory
printf("Checking Dir_Tree_Nodes %s\n", current->name);
current = current->next;
}
//printf("finished Dir_Tree_Node write\n");
head = head->next;
explore_paths(head, head); //recurse downward
current = nullptr;
}
//printf("Success and recursing\n");
if (current_path->next) {
current_path = current_path->next;
}
else {
return;
}
//current_path->next = (struct Dir_Tree_Node*)malloc(sizeof(struct Dir_Tree_Node));
explore_paths(current_path, current_path);
}
int main(int argc, char** argv) {
if (argc < 2) {
printf("Usage: One or more root paths to search from <path> <path> <path> ...");
return 1;
}
printf("\nSearching ");
for (int i = 1; i < argc; i++) {
printf(argv[i]);
} printf("\n\n");
char** path_list = argv;
char* current_directory = path_list[1];
struct Dir_Tree_Node* root = (struct Dir_Tree_Node*)malloc(sizeof(struct Dir_Tree_Node));
root->name = current_directory;
root->next = nullptr;
struct Dir_Tree_Node* tree_cursor = root;
explore_paths(root, tree_cursor);
/*cursor = first;
while (cursor != NULL) {
struct Queue_Node* next = cursor->next;
free(cursor);
cursor = next;
}*/
return 0;
}