diff options
Diffstat (limited to 'filesystem.c')
| -rw-r--r-- | filesystem.c | 713 |
1 files changed, 713 insertions, 0 deletions
diff --git a/filesystem.c b/filesystem.c new file mode 100644 index 0000000..e041f56 --- /dev/null +++ b/filesystem.c @@ -0,0 +1,713 @@ +/* + * File: filesystem.c + * + * This file contains the source code that simulates the UNIX file system using + * C code. Function prototypes are included from filesystem.h, which also + * includes the required structure declarations in filesystem-datastructure.h. + * + * Author: Filip Rabiega + */ + +/* -------------------- Include files -------------------- */ +#include "filesystem.h" +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +/* -------------------- Function Prototypes -------------------- */ +static File_node *search_file(Dir_node *const dir, const char name[]); +static Dir_node *search_subdir(Dir_node *const dir, const char name[]); +static void print_whole_dir(Dir_node *const dir); +static Name_node *insert_name(Name_node *head, char *name, int is_dir); +static int search_and_remove_dir(Dir_node *const cur_dir, const char name[]); +static void remove_dir(Dir_node *dir); +static int search_and_remove_file(Dir_node *const cur_dir, const char name[]); +static void remove_file(File_node *file); + +/* -------------------- Function Definitions -------------------- */ + +/* + * Initializes the FileSystem parameter filesystem. + * This allows more than one file systems to coexist, as each of them are + * initialized to their own unique memory addresses. + */ +void mkfs(FileSystem *const filesystem) { + /* Create and initialize root directory */ + Dir_node *root = malloc(sizeof(*root)); + + root->name = "root"; + root->path = ""; + root->file_list = NULL; + root->subdir_list = NULL; + root->next_dir = NULL; + root->par_dir = NULL; + + /* Assign root directory to the filesystem */ + filesystem->root = root; + filesystem->cur_dir = root; +} + +/* + * Creates a file with the specified name in the file system's current + * directory. + * - If a file with the same name already exists, then it simply + * updates the timestamp by incrementing it by 1. + * - If a subdirectory with the same name exists, then it will not make any + * modifications. + */ +int touch(FileSystem *const filesystem, const char name[]) { + File_node *cur, *prev = NULL, *new_file; + char *new_name; + int result = 0; + + /* Checks if parameters are valid, and also whether + name consists of a forward-slash character */ + if (filesystem != NULL && name != NULL && strlen(name) != 0 && + strchr(name, '/') == NULL) { + result = 1; + + /* These names would cause the function to have no + effects, but are not classified as error cases */ + if (strcmp(name, ".") != 0 && strcmp(name, "..") != 0 && + strcmp(name, "/") != 0) { + /* Searches subdirectories with the same name. + If there is no directory with the same name, continue. */ + if (search_subdir(filesystem->cur_dir, name) == NULL) { + /* Set cur to the head of the file + list in the current directory */ + cur = filesystem->cur_dir->file_list; + + /* Find location to insert node within file_list */ + while (cur != NULL && strcmp(name, cur->name) >= 0) { + /* If there is a file of the same name, + increment timestamp and return 1*/ + if (strcmp(name, cur->name) == 0) { + cur->timestamp += 1; + return result; + } + + prev = cur; + cur = cur->next_file; + } + + /* Insert new File node */ + new_file = malloc(sizeof(*new_file)); + if (new_file != NULL) { + new_name = malloc(sizeof(char) * (strlen(name) + 1)); + if (new_name != NULL) { + /* Copies name to the allocated string */ + strcpy(new_name, name); + + /* Initializes new file structure members */ + new_file->name = new_name; + new_file->timestamp = 1; + new_file->next_file = cur; + + /* Case: File is inserted at the head */ + if (prev == NULL) { + filesystem->cur_dir->file_list = new_file; + } + /* Case: File is inserted elsewhere */ + else { + prev->next_file = new_file; + } + } + } + } + } + } + + return result; +} + +/* + * Creates a subdirectory with the specified name in the file system's + * current directory. + * - If a subdirectory/file with the same name already exists, or if name + * is invalid, then it will return 0. + */ +int mkdir(FileSystem *const filesystem, const char name[]) { + Dir_node *cur, *prev = NULL, *new_dir; + char *new_name; + char *new_path; + int result = 0; + + /* Checks if parameters are valid, and also whether name is an illegal + special case in this context or it consists of a forward-slash character */ + if (filesystem != NULL && name != NULL && strlen(name) != 0 && + strcmp(name, ".") != 0 && strcmp(name, "..") != 0 && + strcmp(name, "/") != 0 && strchr(name, '/') == NULL) { + /* Searches files with the same name. + If there is no file with the same name, continue. */ + if (search_subdir(filesystem->cur_dir, name) == NULL) { + + result = 1; + + /* Set cur to the head of the + subdirectory list of the current directory */ + cur = filesystem->cur_dir->subdir_list; + + /* Find location to insert node within subdir_list */ + while (cur != NULL && strcmp(name, cur->name) >= 0) { + /* If there is a subdirectory of the same name, + do nothing and return 1 */ + if (strcmp(name, cur->name) == 0) { + return result; + } + prev = cur; + cur = cur->next_dir; + } + + /* Insert new Subdirectory node */ + new_dir = malloc(sizeof(*new_dir)); + if (new_dir != NULL) { + new_name = malloc(sizeof(char) * (strlen(name) + 1)); + if (new_name != NULL) { + new_path = + malloc(sizeof(char) * + (strlen(name) + strlen(filesystem->cur_dir->path) + 2)); + + if (new_path != NULL) { + /* Copies name to the allocated name string */ + strcpy(new_name, name); + /* Creates path name to the allocated path string */ + strcpy(new_path, filesystem->cur_dir->path); + strcat(new_path, "/"); + strcat(new_path, name); + + /* Initializes new directory structure members */ + new_dir->name = new_name; + new_dir->path = new_path; + new_dir->file_list = NULL; + new_dir->subdir_list = NULL; + new_dir->next_dir = cur; + new_dir->par_dir = filesystem->cur_dir; + + /* Case: Directory is inserted at the head */ + if (prev == NULL) { + filesystem->cur_dir->subdir_list = new_dir; + } + /* Case: Directory is inserted elsewhere */ + else { + prev->next_dir = new_dir; + } + } + } + } + } + } + + return result; +} + +/* + * Moves the current directory of filesystem. + * The directory to be moved to is specified by name using the parameter name. + * - If name is a single period (.), there will be no effect since this tells + * the function to "move to the current directory." + * However, it is not an error case. + * - If name is a double adjacent period (..), it will move the current + * directory to its parent directory. + * - If name is solely a forward-slash (/), it will move the current + * directory to the root directory. + * - If name is a valid name of an existing subdirectory, then it will move + * the current directory there. + * - Other cases would be errors, including consists a forward-slash, but + * is not solely a forward-slash. + */ +int cd(FileSystem *const filesystem, const char name[]) { + Dir_node *dir; + int result = 0; + + /* Checks if parameters are valid */ + if (filesystem != NULL && name != NULL && strlen(name) != 0) { + /* Move to current directory (no effect) */ + if (strcmp(".", name) == 0) { + result = 1; + } + /* Move to parent directory */ + else if (strcmp("..", name) == 0) { + /* If the current directory is the root directory, then its + parent directory would be NULL, and therefore, should be + prevented from crashing the program */ + if (filesystem->cur_dir->par_dir != NULL) { + filesystem->cur_dir = filesystem->cur_dir->par_dir; + } + result = 1; + } + /* Move to root directory */ + else if (strcmp("/", name) == 0) { + filesystem->cur_dir = filesystem->root; + result = 1; + } + /* Move to an existing subdirectory */ + else { + /* If name consists of a forward-slash, it is invalid */ + if (strchr(name, '/') == NULL) { + /* Searches for subdirectories with the specified name, + and sets the current directory to be inside it. If not + found, then 0 will be returned. */ + dir = search_subdir(filesystem->cur_dir, name); + if (dir != NULL) { + filesystem->cur_dir = dir; + result = 1; + } + } + } + } + + return result; +} + +/* + * Displays a subdirectory, a file, or a certain directory. + * - If name is an existing file in the current directory, then it will print + * its name followed by a timestamp. + * - If name is an existing subdirectory in the current directory, then it + * will print all the files and and subdirectories within it in + * lexicographic order. + * - If name is a single period (.), or name is an empty string, it will print + * out the current directory. + * - If name is a double adjacent period (..), it will print out the parent + * directory of the current directory. + * - If name is a forward-slash (/), it will print out the root directory. + * - Other cases would be errors, including consists a forward-slash, but + * is not solely a forward-slash. + */ +int ls(FileSystem *const filesystem, const char name[]) { + Dir_node *dir; + File_node *file; + int result = 0; + + /* Checks if parameters are valid */ + if (filesystem != NULL && name != NULL) { + + /* Prints out current directory */ + if (strcmp(".", name) == 0 || strlen(name) == 0) { + print_whole_dir(filesystem->cur_dir); + result = 1; + } + /* Prints out parent directory */ + else if (strcmp("..", name) == 0) { + /* If the current directory is the root directory, then its + parent directory would be NULL, and therefore, should be + prevented from crashing the program */ + if (filesystem->cur_dir->par_dir != NULL) { + print_whole_dir(filesystem->cur_dir->par_dir); + } + result = 1; + } + /* Prints out root directory */ + else if (strcmp("/", name) == 0) { + print_whole_dir(filesystem->root); + result = 1; + } + /* Prints out an existing file or subdirectory */ + else { + /* If name consists of a forward-slash, it is invalid */ + if (strchr(name, '/') == NULL) { + /* Searches for a subdirectory with the specified name and + prints it out. */ + dir = search_subdir(filesystem->cur_dir, name); + if (dir != NULL) { + print_whole_dir(dir); + result = 1; + } + /* If a subdirectory is not found, then it will try searching + for files with the specified name */ + else { + file = search_file(filesystem->cur_dir, name); + if (file != NULL) { + printf("%s %d\n", file->name, file->timestamp); + result = 1; + } + } + /* If both are not found, then function will return 0 */ + } + } + } + + return result; +} + +/* + * Prints out the current directories full path, all the way from the root, + * with each directory in between separated by forward-slashes. + */ +void pwd(FileSystem *const filesystem) { + /* Check if parameter is valid */ + if (filesystem != NULL) { + /* If the current directory is the root directory, then print out + a forward-slash. The root is initialized such that its path would + be an empty string, to simplify the process of keeping track of + other directory paths */ + if (strcmp(filesystem->cur_dir->path, "") == 0) { + printf("/\n"); + } else { + printf("%s\n", filesystem->cur_dir->path); + } + } +} + +/* + * Deallocates all dynamically-allocated memory that is being used by the + * Ournix file system. As a result, all allocated memory of subdirectories + * and files inside the root, and even the root itself, will be freed and + * returned to the memory pool for future use. This also means that + * whatever data the file system is holding will be removed. + */ +void rmfs(FileSystem *const filesystem) { + /* Checks if paramter is valid */ + if (filesystem != NULL) { + remove_dir(filesystem->root); + } +} + +/* + * Removes a file or subdirectory within the current directory. This also + * means that whatever content is stored within them is also removed, + * as any allocated memory being used within it freed and returned to the + * memory pool. + */ +int rm(FileSystem *const filesystem, const char name[]) { + int result = 0; + + /* Checks if parameters are valid, and also whether name is an illegal + special case in this context or it consists of a forward-slash character */ + if (filesystem != NULL && name != NULL && strlen(name) != 0 && + strcmp(name, ".") != 0 && strcmp(name, "..") != 0 && + strcmp(name, "/") != 0 && strchr(name, '/') == NULL) { + /* Tries removing a directory with the specified name */ + result = search_and_remove_dir(filesystem->cur_dir, name); + + /* If directory is not found, it will try + removing a file with the specified name */ + if (!result) { + result = search_and_remove_file(filesystem->cur_dir, name); + } + + /* If both a directory or file is not + found, then result would stay 0 */ + } + + return result; +} + +/* + * A helper function to search for a file with the specified name within + * the specified directory. + */ +static File_node *search_file(Dir_node *const dir, const char name[]) { + File_node *cur; + + /* Set cur to the head of the file + list in the specified directory */ + cur = dir->file_list; + + /* Traverses the file list to search for the desired file */ + while (cur != NULL) { + if (strcmp(cur->name, name) == 0) { + return cur; + } + cur = cur->next_file; + } + + /* If a file with the specified name is not found, + then it will return NULL */ + return NULL; +} + +/* + * A helper function to search for a directory with the specified name within + * the specified directory. + */ +static Dir_node *search_subdir(Dir_node *const dir, const char name[]) { + Dir_node *cur; + + /* Set cur to the head of the subdirectory + list in the specified directory */ + cur = dir->subdir_list; + + /* Traverses the subdirectory list to search for the + desired subdirectory */ + while (cur != NULL) { + if (strcmp(cur->name, name) == 0) { + return cur; + } + cur = cur->next_dir; + } + + /* If a subdirectory with the specified name is not found, + then it will return NULL */ + return NULL; +} + +/* + * A helper function to print the contents of the whole specified directory. + * To do this, the function takes two steps: + * 1. It will create an ordered linked list (arranged in lexicographic order) + * storing the names of all files and subdirectories (if any) within the + * specified directory. + * 2. Prints all the names being stored in the ordered linked list while + * deallocating any memory being used by it. We can safely do this since + * the linked list will be of no use for us in the future. + */ +static void print_whole_dir(Dir_node *const dir) { + Name_node *name_list = NULL, *printed_name; + Dir_node *cur_dir; + File_node *cur_file; + + /* Make an ordered Linked List of File/Directory names. */ + + /* Traverse directory's files. */ + cur_file = dir->file_list; + + while (cur_file != NULL) { + name_list = insert_name(name_list, cur_file->name, 0); + cur_file = cur_file->next_file; + } + + /* Traverse directory's subdirectories. */ + cur_dir = dir->subdir_list; + + while (cur_dir != NULL) { + name_list = insert_name(name_list, cur_dir->name, 1); + cur_dir = cur_dir->next_dir; + } + + /* Start printing names. If the name_list is NULL, it indicates that + the directory is empty, and therefore, nothing is printed. */ + while (name_list != NULL) { + printf("%s\n", name_list->name); + + /* Set printed_name to the name that has just been printed + and move name_list to the next node. */ + printed_name = name_list; + name_list = name_list->next_name; + + /* Free allocated memory being used by printed_name. */ + free(printed_name->name); + free(printed_name); + } +} + +/* + * A helper function to assist the print_whole_dir() function in creating + * an ordered linked list of names. + * - The head parameter represents the head of the name linked list. + * - The name parameter represents the name to be stored within the node. + * - The is_dir parameter indicates whether the node being inserted will + * store the name of a directory. This distinction is important since + * directories are printed with a preceding forward-slash. + */ +static Name_node *insert_name(Name_node *head, char *name, int is_dir) { + Name_node *cur, *prev = NULL, *new_node; + char *new_name; + + /* The boolean value flag is used to indicate whether an error has + occured in the process of allocating memory, to prevent the function + from executing more statements and causing the program to crash. */ + int flag = 1; + + /* Initialize new_name node. */ + new_node = malloc(sizeof(*new_node)); + + if (new_node != NULL) { + new_name = malloc(sizeof(char) * (strlen(name) + 2)); + if (new_name != NULL) { + strcpy(new_name, name); + + /* If the name being inserted is the name of a directory, + concatenate a forward-slash to the end of the string. */ + if (is_dir) { + strcat(new_name, "/"); + } + + /* Initialize values of new_name node */ + new_node->name = new_name; + new_node->next_name = NULL; + } else { + /* Malloc Error */ + flag = 0; + } + } else { + /* Malloc Error */ + flag = 0; + } + + /* Insert the new_name node into the linked list. */ + if (flag) { + /* If head is NULL, it means that the node to be + inserted is the first node in the linked list. */ + if (head == NULL) { + return new_node; + } + + cur = head; + + /* Find a location to insert the node */ + while (cur != NULL && strcmp(name, cur->name) >= 0) { + prev = cur; + cur = cur->next_name; + } + + /* Initializes the pointer to the next node. */ + new_node->next_name = cur; + + /* Case: File is inserted at the head */ + if (prev == NULL) { + head = new_node; + } + + /* Case: File is inserted elsewhere */ + else { + prev->next_name = new_node; + } + } + + return head; +} + +/* + * A helper method to search for a directory and remove it from the list + * of subdirectories. This function is distinct from simply searching for + * a directory using the search_dir() helper function and removing it using + * the remove_dir() helper function as it also modifies the links within + * the subdirectory linked list. + */ +static int search_and_remove_dir(Dir_node *const cur_dir, const char name[]) { + Dir_node *cur, *prev = NULL; + int result = 0; + + /* Traverses the subdirectory list to look for the desired subdirectory */ + cur = cur_dir->subdir_list; + + while (cur != NULL && strcmp(cur->name, name) != 0) { + prev = cur; + cur = cur->next_dir; + } + + /* If cur is NULL, it would indicate that the subdirectory with the + specified name is not found, and result would stay 0. */ + if (cur != NULL) { + result = 1; + + /* Case: The subdirectory to be removed is the head of the list */ + if (prev == NULL) { + cur_dir->subdir_list = cur->next_dir; + } + + /* Case: The subdirectory to be removed is between the list */ + else { + prev->next_dir = cur->next_dir; + } + + /* Remove all subdirectory contents and free all + allocated memory being used by it */ + remove_dir(cur); + } + + return result; +} + +/* + * A recursive helper function used to remove all the contents within a + * directory, which includes all files and subdirectories within it, and + * frees all allocated memory being used by any of the content. + */ +static void remove_dir(Dir_node *dir) { + File_node *cur_file, *file_to_be_removed; + Dir_node *cur_dir, *dir_to_be_removed; + + if (dir != NULL) { + /* Remove all files within this directory */ + cur_file = dir->file_list; + + /* If cur_file is NULL, this would indicate + that the directory has no files */ + while (cur_file != NULL) { + file_to_be_removed = cur_file; + cur_file = cur_file->next_file; + + remove_file(file_to_be_removed); + } + + /* Remove all subdirectories within this directory */ + cur_dir = dir->subdir_list; + + /* If cur_dir is NULL, this would indicate + that the directory has no subdirectories */ + while (cur_dir != NULL) { + dir_to_be_removed = cur_dir; + cur_dir = cur_dir->next_dir; + + remove_dir(dir_to_be_removed); /* Recursive call */ + } + + /* Free allocated memory being used + by other directory struct members */ + if (strcmp("root", dir->name) != 0) { + free(dir->name); + } + + if (strlen(dir->path) != 0) { + free(dir->path); + } + + /* Free allocated memory being used by the directory itself */ + free(dir); + } +} + +/* + * A helper method to search for a file and remove it from the list of files. + * This function is distinct from simply searching for a file using the + * search_file() helper function and removing it using the remove_file() + * helper function as it also modifies the links within the file linked list. + */ +static int search_and_remove_file(Dir_node *const cur_dir, const char name[]) { + File_node *cur, *prev = NULL; + int result = 0; + + /* Traverses the file list to look for the desired file */ + cur = cur_dir->file_list; + + while (cur != NULL && strcmp(cur->name, name)) { + prev = cur; + cur = cur->next_file; + } + + /* If cur is NULL, it would indicate that the file with the + specified name is not found, and result would stay 0. */ + if (cur != NULL) { + result = 1; + + /* Case: The file to be removed is the head of the list */ + if (prev == NULL) { + cur_dir->file_list = cur->next_file; + } + + /* Case: The file to be removed is between the list */ + else { + prev->next_file = cur->next_file; + } + + /* Remove all file contents and free all + allocated memory being used by it */ + remove_file(cur); + } + + return result; +} + +/* + * A helper function used to remove all the contents within a + * file, namely its name and timestamp. + */ +static void remove_file(File_node *file) { + if (file != NULL) { + + free(file->name); + free(file); + } +} |