From 22c56bad4268ad90e2289ab218717e99deb7738c Mon Sep 17 00:00:00 2001 From: Aymen Dirar Date: Mon, 24 Oct 2022 20:24:31 -0700 Subject: c filesystem cache fib --- entries/adirar111/c-filesystem/cache/0 | 1 + entries/adirar111/c-filesystem/cache/1 | 1 + entries/adirar111/c-filesystem/cache/10 | 1 + entries/adirar111/c-filesystem/cache/11 | 1 + entries/adirar111/c-filesystem/cache/12 | 1 + entries/adirar111/c-filesystem/cache/13 | 1 + entries/adirar111/c-filesystem/cache/2 | 1 + entries/adirar111/c-filesystem/cache/3 | 1 + entries/adirar111/c-filesystem/cache/4 | 1 + entries/adirar111/c-filesystem/cache/5 | 1 + entries/adirar111/c-filesystem/cache/6 | 1 + entries/adirar111/c-filesystem/cache/7 | 1 + entries/adirar111/c-filesystem/cache/8 | 1 + entries/adirar111/c-filesystem/cache/9 | 1 + entries/adirar111/c-filesystem/fib-fs.c | 135 ++++++++++++++++++++++++++++++++ 15 files changed, 149 insertions(+) create mode 100644 entries/adirar111/c-filesystem/cache/0 create mode 100644 entries/adirar111/c-filesystem/cache/1 create mode 100644 entries/adirar111/c-filesystem/cache/10 create mode 100644 entries/adirar111/c-filesystem/cache/11 create mode 100644 entries/adirar111/c-filesystem/cache/12 create mode 100644 entries/adirar111/c-filesystem/cache/13 create mode 100644 entries/adirar111/c-filesystem/cache/2 create mode 100644 entries/adirar111/c-filesystem/cache/3 create mode 100644 entries/adirar111/c-filesystem/cache/4 create mode 100644 entries/adirar111/c-filesystem/cache/5 create mode 100644 entries/adirar111/c-filesystem/cache/6 create mode 100644 entries/adirar111/c-filesystem/cache/7 create mode 100644 entries/adirar111/c-filesystem/cache/8 create mode 100644 entries/adirar111/c-filesystem/cache/9 create mode 100644 entries/adirar111/c-filesystem/fib-fs.c (limited to 'entries') diff --git a/entries/adirar111/c-filesystem/cache/0 b/entries/adirar111/c-filesystem/cache/0 new file mode 100644 index 0000000..573541a --- /dev/null +++ b/entries/adirar111/c-filesystem/cache/0 @@ -0,0 +1 @@ +0 diff --git a/entries/adirar111/c-filesystem/cache/1 b/entries/adirar111/c-filesystem/cache/1 new file mode 100644 index 0000000..56a6051 --- /dev/null +++ b/entries/adirar111/c-filesystem/cache/1 @@ -0,0 +1 @@ +1 \ No newline at end of file diff --git a/entries/adirar111/c-filesystem/cache/10 b/entries/adirar111/c-filesystem/cache/10 new file mode 100644 index 0000000..7c6ba0f --- /dev/null +++ b/entries/adirar111/c-filesystem/cache/10 @@ -0,0 +1 @@ +55 \ No newline at end of file diff --git a/entries/adirar111/c-filesystem/cache/11 b/entries/adirar111/c-filesystem/cache/11 new file mode 100644 index 0000000..8643cf6 --- /dev/null +++ b/entries/adirar111/c-filesystem/cache/11 @@ -0,0 +1 @@ +89 diff --git a/entries/adirar111/c-filesystem/cache/12 b/entries/adirar111/c-filesystem/cache/12 new file mode 100644 index 0000000..70e1a64 --- /dev/null +++ b/entries/adirar111/c-filesystem/cache/12 @@ -0,0 +1 @@ +144 \ No newline at end of file diff --git a/entries/adirar111/c-filesystem/cache/13 b/entries/adirar111/c-filesystem/cache/13 new file mode 100644 index 0000000..f937f7e --- /dev/null +++ b/entries/adirar111/c-filesystem/cache/13 @@ -0,0 +1 @@ +233 \ No newline at end of file diff --git a/entries/adirar111/c-filesystem/cache/2 b/entries/adirar111/c-filesystem/cache/2 new file mode 100644 index 0000000..56a6051 --- /dev/null +++ b/entries/adirar111/c-filesystem/cache/2 @@ -0,0 +1 @@ +1 \ No newline at end of file diff --git a/entries/adirar111/c-filesystem/cache/3 b/entries/adirar111/c-filesystem/cache/3 new file mode 100644 index 0000000..d8263ee --- /dev/null +++ b/entries/adirar111/c-filesystem/cache/3 @@ -0,0 +1 @@ +2 \ No newline at end of file diff --git a/entries/adirar111/c-filesystem/cache/4 b/entries/adirar111/c-filesystem/cache/4 new file mode 100644 index 0000000..00750ed --- /dev/null +++ b/entries/adirar111/c-filesystem/cache/4 @@ -0,0 +1 @@ +3 diff --git a/entries/adirar111/c-filesystem/cache/5 b/entries/adirar111/c-filesystem/cache/5 new file mode 100644 index 0000000..7813681 --- /dev/null +++ b/entries/adirar111/c-filesystem/cache/5 @@ -0,0 +1 @@ +5 \ No newline at end of file diff --git a/entries/adirar111/c-filesystem/cache/6 b/entries/adirar111/c-filesystem/cache/6 new file mode 100644 index 0000000..301160a --- /dev/null +++ b/entries/adirar111/c-filesystem/cache/6 @@ -0,0 +1 @@ +8 \ No newline at end of file diff --git a/entries/adirar111/c-filesystem/cache/7 b/entries/adirar111/c-filesystem/cache/7 new file mode 100644 index 0000000..ca7bf83 --- /dev/null +++ b/entries/adirar111/c-filesystem/cache/7 @@ -0,0 +1 @@ +13 \ No newline at end of file diff --git a/entries/adirar111/c-filesystem/cache/8 b/entries/adirar111/c-filesystem/cache/8 new file mode 100644 index 0000000..b5045cc --- /dev/null +++ b/entries/adirar111/c-filesystem/cache/8 @@ -0,0 +1 @@ +21 \ No newline at end of file diff --git a/entries/adirar111/c-filesystem/cache/9 b/entries/adirar111/c-filesystem/cache/9 new file mode 100644 index 0000000..3e932fe --- /dev/null +++ b/entries/adirar111/c-filesystem/cache/9 @@ -0,0 +1 @@ +34 \ No newline at end of file diff --git a/entries/adirar111/c-filesystem/fib-fs.c b/entries/adirar111/c-filesystem/fib-fs.c new file mode 100644 index 0000000..d07c205 --- /dev/null +++ b/entries/adirar111/c-filesystem/fib-fs.c @@ -0,0 +1,135 @@ +/* fib, but the cache is a directory of files + * cache/ + * 0 -> 0 + * 1 -> 1 + * 2 -> 1 + * 3 -> 2 + * ... + * unix filesystem required +*/ +#include +#include +#include +#include +#include +#include +#include +#include + +static const char CACHE_DIR[] = "cache"; +static const int BUF_SIZE = 30; +static const int PATH_SIZE = 30; +static const int N_STR_SIZE = 30; +static const int LOF_INITIAL_SIZE = 1; + +long read_from_cache(char* path) { + char buf[BUF_SIZE]; + int fd = open(path, O_RDONLY); + + if (fd == -1) { + close(fd); + return 0; + } + + if (!read(fd, buf, BUF_SIZE)) { + close(fd); + return 0; + } + + close(fd); + return strtol(buf, NULL, 10); +} + +long write_to_cache(char* path, long result) { + char buf[BUF_SIZE]; + int fd = open(path, O_CREAT | O_RDWR, S_IRUSR | S_IWUSR); + sprintf(buf, "%ld", result); + + if (fd == -1) { + close(fd); + return 0; + } + + if (!write(fd, buf, strlen(buf))) { + close(fd); + return 0; + } + + close(fd); + return 1; +} + +long init_cache() { + char path_to_0[PATH_SIZE]; + char path_to_1[PATH_SIZE]; + sprintf(path_to_0, "%s/%s", CACHE_DIR, "0"); + sprintf(path_to_1, "%s/%s", CACHE_DIR, "1"); + + if (!write_to_cache(path_to_0, 0)) { + return 0; + } + + if (!write_to_cache(path_to_1, 1)) { + return 0; + } + + return 1; +} + +long get_list_of_files(long** list_of_files, long curr_size) { + mkdir("cache", 0777); + struct dirent *d; + DIR* cache_dir = opendir(CACHE_DIR); + + if (!cache_dir) { + closedir(cache_dir); + return 0; + } + + init_cache(); + + while ((d = readdir(cache_dir)) != NULL) { + if (d->d_type == DT_REG) { + *((*list_of_files) + curr_size - 1) = strtol(d->d_name, NULL, 10); + curr_size++; + *list_of_files = realloc(*list_of_files, curr_size * sizeof(long)); + } + } + + closedir(cache_dir); + return curr_size - 1; +} + + +int is_in_cache(long* list_of_files, long size_of_lof, long n) { + for (int i = 0; i < size_of_lof; i++) { + if (list_of_files[i] == n) return 1; + } + return 0; +} + +long fib(long n) { + char n_str[N_STR_SIZE]; + char path[PATH_SIZE]; + long* list_of_files = malloc(sizeof(long)); + long size_of_lof = get_list_of_files(&list_of_files, LOF_INITIAL_SIZE); + + sprintf(n_str, "%ld", n); + sprintf(path, "%s/%s", CACHE_DIR, n_str); + + if (is_in_cache(list_of_files, size_of_lof, n)) { + free(list_of_files); + long cached_value = read_from_cache(path); + return cached_value; + } + + free(list_of_files); + long toCache = fib(n-1) + fib(n-2); + write_to_cache(path, toCache); + return toCache; +} + + +int main() { + printf("FIB RESULT: %ld\n", fib(13)); +} -- cgit v1.2.3-70-g09d2